1、第第5章章 公钥密码2022-12-92主要内容主要内容公钥密码的理论基础RSA 公钥密码大素数的生成EIGamal 公钥密码椭圆曲线上的Menezes-Vanstone 公钥密码2022-12-935.1 公钥密码的理论基础在公钥密码中,加密密钥和解密密钥是不一样的。加密密钥简称公钥(publickey),解密密钥简称私钥(private key)。加密密钥可以公开,解密密钥当然必须保密。定义5.1 设f 是一个函数.如果对任意给定的x,计算y 使得y=f(x)是容易的,但对任意给定的y,计算x 使得f(x)=y 是难解的,即求f 的逆函数是难解的,则称f 是一个单向函数(one-way f
2、unction)。定义5.2 设f 是一个函数,t 是与f 有关的一个参数.对任意给定的x,计算y 使得y=f(x)是容易的.如果当不知参数t 时,计算f 的逆函数是难解的,但当知道参数t 时,计算f 的逆函数是容易的,则称f 是一个陷门单向函数(trapdoorone-way function),参数t 称为陷门.2022-12-945.2 RSA公钥密码中国剩余定理Euler 函数Euler 定理和Fermat 小定理RSA 公钥密码体制RSA 的安全性讨论模n 求逆的算法模n 的大数幂乘的快速算法.因子分解2022-12-955.2.1 中国剩余定理定义5.3 设a、b、m 都是整数.如
3、果m|(a-b)，则称a 和b 模m 同余，记为a b(modm)，m 称为这个同余式的模。定理5.1(中国剩余定理)设 是两两互素的正整数.设 是整数,则同余方程组模 有唯一解2022-12-965.2.2 Euler 函数定义5.4 设n 是一个正整数称为Euler函数.Euler函数是定义在正整数集合上的函数.显然,为小于n 并且与n 互素的非负整数的个数.定理5.2 如果 和 互素,则 定理5.3 如果其中，为不同的素数为正整数,则定理5.4 设n 是一个正整数,则2022-12-975.2.3 Euler定理和Fermat小定理定理5.5(Euler 定理)设x 和n 都是正整数.如
4、果gcd(x;n)=1,则推论5.1(Fermat 小定理)设x 和p 都是正整数.如果p 是素数并且gcd(x;p)=1,则定理5.6(Fermat 小定理)设x 和p 都是正整数.如果p 是素数,则2022-12-985.2.4 RSA 公钥密码体制选取两个大素数p 和q，p 和q 保密计算 ，公开，保密随机选取正整数1 e ，满足 e 是公开的加密密钥计算d，满足 。d 是保密的解密密钥加密变换：对明文 密文为解密变换：对密文 明文为RSA 公钥密码体制描述如下：2022-12-995.2.5 RSA 的安全性讨论 RSA 公钥密码体制的安全性是基于大整数的素分解问题的难解性。尽管尚未在
5、理论上严格证明因子分解问题一定是难解的,但经过长期的研究迄今没有找到一个有效算法的事实,使得因子分解问题成为众所周知的难题。这是RSA 公钥密码体制建立的基础。2022-12-9105.2.6 模n求逆的算法设n 和u 都是正整数，u n。u 模n 的逆就是满足的整数v，0 v n。定理5.7 设n 是一个正整数，对于 存在 使得 的充分必要条件是 gcd(u;n)=1。2022-12-9115.2.7 模n的大数幂乘的快速算法如果b=0，则输出结果c，结束如果b mod 2 0，则转到第5 步转第3 步.转第5 步计算 的快速算法2022-12-9125.2.8 因子分解a 2计算d gcd
6、(a 1，n)。p 1因子分解算法描述如下输入奇整数n，输入整数B对j=2 到B，计算如果1 d 0,(x)为不大于x 的素数的个数,则素数的分布极不均匀，素数越大，分布越稀疏。2022-12-9155.3.2 模奇素数的平方剩余定义5.5 设p 2 是一个素数,a 是一个整数,gcd(a，p)=1.如果同余方程X a(mod p)有解 则称a 是模p 的平方剩余(quadratic residue);否则,称a 是模p 的平方非剩余(quadratic non-residue).定理5.10(Euler 准则)设p 2 是一个素数,x 是一个整数,gcd(x;p)=1,则1)x 是模p 的平
7、方剩余当且仅当2)x 是模p 的平方非剩余当且仅当2022-12-9165.3.3 Legendre 符号定义5.6 设p 2 是一个素数.对任意整数a,若a 0(modp)若a是模p的平方剩余若a是模p的非平方剩余定理5.11 设p 2 是一个素数,则对任意整数a,定理5.12 设p 2 是一个素数。如果m1 m2(mod p)，则定理5.13 设p 2 是一个素数,q 2 也是一个素数，p q2022-12-9175.3.4 Jacobi 符号定义5.7 设n 2 是一个奇整数,n 的素分解为其中 是素数,对任意整数a,称为 Jacobi符号定理5.14 设n 2 是一个奇整数。1)如果
8、则2)3)4)如果m 2 是奇整数,则引理5.1 设n 2 是一个奇整数,n 的素分解为其中 是素数,则2022-12-9185.3.5 Solovay-Strassen 素性测试法 由Fermat 小定理可知,对于一个正整数n,如果存在正整数b 满足gcd(b，n)=1,并且 不成立，则n一定是合数 定理5.15 如果n 2 是一个奇合数,则至少有50%的 使得同余式不成立。2022-12-9195.3.6 Miller-Rabin 素性测试法定义5.8 设n 2 是一个奇数.设 其中s 是非负整数,m 0是奇数。设0 b n。如果 或者存在一个r,0 6 r 2 是一个素数.对任意整数b
9、0,如果gcd(b，p)=1,则p一定可以通过以b 为基的Miller-Rabin测试。定理5.17 如果n 2 是一个奇合数,则至多有 个b,0 b 0 有一个实根和一对共轭复根=0 有三个实根，分别为 3 是一个素数.有限域 上的椭圆曲线是由一个称为无穷远点的特殊点O 和满足的所有点同余方程组成的集合E,其中对任意定义其中定义加法运算2022-12-9315.5.6 有限域上的椭圆曲线的性质定理5.20(Hasse 定理)设E 是有限域 上的椭圆曲线,则定理5.21(Hasse 定理)设E 是有限域 上的椭圆曲线,则其中t 的绝对值定理5.22(椭圆曲线的群结构)设E 是有限域 上的椭圆曲
10、线,p 3 为素数,则存在正整数 和 ，使得E 与 同构,和 满足 并且2022-12-9325.5.7 椭圆曲线上的离散对数问题定义5.11 设E 是有限域 上的椭圆曲线,的阶是满足的最小正整数n,记为ord(P),其中O 是无穷远点。定义5.12 设p 3 是一个素数,E 是有限域 上的椭圆曲线.设G 是E的一个循环子群,P 是G 的一个生成元,Q G.已知P 和Q,求满足nP=Q的唯一整数 称为椭圆曲线上的离散对数问题。2022-12-9335.5.8 Menezes-Vanstone 公钥密码体制随机选取整数d，1 d ord()1。计算=d，是公开的加密密钥，d是保密的解密密钥Men
11、ezes-Vanstone公钥密码体制描述如下设p 3 是一个大素数，E 是有限域Zp 上的椭圆曲线。E是椭圆曲线上的一个点，并且的阶足够大，使得在由生成的循环子群中离散对数问题是难解的。p 和E 以及都公开明文空间为密文空间为加密变换：对任意明文 ，秘密随机选取一个整数k，1 k ord()1，密文为其中解密变换：对任意密文 明文为其中2022-12-935点击此处返回2022-12-936在线教务辅导网：在线教务辅导网：http:/ 更多课程配套课件资源请访问在线教务辅导网更多课程配套课件资源请访问在线教务辅导网2022-12-9372022-12-9382022-12-9392022-12-9402022-12-9412022-12-942馋死2022-12-9432022-12-9442022-12-9452022-12-9462022-12-9472022-12-9482022-12-9492022-12-9502022-12-9512022-12-9522022-12-9532022-12-9542022-12-955PPT研究院P O W E R P O I N T A C A D E M Y2022-12-9562022-12-957
