现代密码学(第二版)-第5章-公钥密码新课件

第5章公钥密码2023/9/181第5章公钥密码2023/8/61主要内容公钥密码的理论基础RSA公钥密码大素数的生成EIGamal公钥密码椭圆曲线上的Menezes-Vanstone公钥密码2023/9/182主要内容公钥密码的理论基础RSA公钥密码大素数的生成EIG5.1公钥密码的理论基础在公钥密码中,加密密钥和解密密钥是不一样的。加密密钥简称公钥(publickey),

解密密钥简称私钥(privatekey)。加密密钥可以公开,

解密密钥当然必须保密。

定义5.1设f是一个函数.如果对任意给定的x,计算y使得y=f(x)是容易的,但对任意给定的y,计算x使得f(x)=y是难解的,即求f的逆函数是难解的,则称f是一个单向函数(one-wayfunction)。定义5.2设f是一个函数,t是与f有关的一个参数.对任意给定的x,计算y使得y=f(x)是容易的.如果当不知参数t时,计算f的逆函数是难解的,但当知道参数t时,计算f的逆函数是容易的,则称f是一个陷门单向函数(trapdoorone-wayfunction),参数t称为陷门.2023/9/1835.1公钥密码的理论基础在公钥密码中,加密密钥和解密密5.2

RSA公钥密码中国剩余定理Euler函数Euler

定理和Fermat小定理RSA

公钥密码体制RSA

的安全性讨论模n

求逆的算法模n

的大数幂乘的快速算法.因子分解2023/9/1845.2RSA公钥密码中国剩余定理Euler函数Eul5.2.1

中国剩余定理定义5.3

设a、b、m都是整数.如果m|(a-b)，则称a和b模m同余，记为a≡b(modm)，m称为这个同余式的模。定理5.1(中国剩余定理)

设是两两互素的正整数.设是整数,则同余方程组模有唯一解2023/9/1855.2.1中国剩余定理定义5.3设a、b、m都是5.2.2

Euler

函数定义5.4

设n是一个正整数称为Euler函数.Euler函数是定义在正整数集合上的函数.显然,为小于n并且与n互素的非负整数的个数.定理5.2

如果

和

互素,则定理5.3

如果其中，为不同的素数为正整数,则定理5.4

设n是一个正整数,则2023/9/1865.2.2Euler函数定义5.4设n是一个正5.2.3

Euler定理和Fermat小定理定理5.5

(Euler定理)

设x和n都是正整数.如果gcd(x;n)=1,则推论5.1(Fermat小定理)

设x和p都是正整数.如果p是素数并且gcd(x;p)=1,则定理5.6(Fermat小定理)

设x和p都是正整数.如果p是素数,则2023/9/1875.2.3Euler定理和Fermat小定理定理5.55.2.4

RSA公钥密码体制选取两个大素数p和q，p和q保密计算，公开，保密随机选取正整数1<e<，满足

e

是公开的加密密钥计算d，满足

。d是保密的解密密钥加密变换：对明文

密文为解密变换：对密文明文为RSA

公钥密码体制描述如下：2023/9/1885.2.4RSA公钥密码体制选取两个大素数p和q，5.2.5

RSA的安全性讨论

RSA公钥密码体制的安全性是基于大整数的素分解问题的难解性。尽管尚未在理论上严格证明因子分解问题一定是难解的,但经过长期的研究迄今没有找到一个有效算法的事实,使得因子分解问题成为众所周知的难题。这是RSA公钥密码体制建立的基础。2023/9/1895.2.5RSA的安全性讨论RSA公钥密码体制的安5.2.6

模n求逆的算法设n和u都是正整数，u<n。u模n的逆就是满足的整数v，0<v<n。

定理5.7

设n是一个正整数，对于存在使得的充分必要条件是gcd(u;n)=1。2023/9/18105.2.6模n求逆的算法设n和u都是正整数，u5.2.7

模n的大数幂乘的快速算法如果b=0，则输出结果c，结束如果bmod2≠0，则转到第5步转第3步.

转第5步计算的快速算法2023/9/18115.2.7模n的大数幂乘的快速算法如果b=0，则5.2.8

因子分解a←2计算d←gcd(a−1，n)。p−1因子分解算法描述如下输入奇整数n，输入整数B对j=2到B，计算如果1<d<n，则d是n的因子，对n因子分解成功；否则，没找到n的因子，对n因子分解失败2023/9/18125.2.8因子分解a←2计算d←gcd(a−5.3

大素数的生成模奇素数的平方剩余Legendre符号Jacobi

符号Solovay-Strassen

素性测试法Miller-Rabin素性测试法素数的分布2023/9/18135.3大素数的生成模奇素数的平方剩余Legendre符号5.3.1素数的分布定理5.8

存在无穷多个素数。定理5.9(素数定理)

设x>0,π(x)为不大于x的素数的个数,则素数的分布极不均匀，素数越大，分布越稀疏。2023/9/18145.3.1素数的分布定理5.8存在无穷多个素数。定理5.3.2模奇素数的平方剩余定义5.5

设p>2是一个素数,a是一个整数,gcd(a，p)=1.如果同余方程X²≡a(modp)有解则称a是模p的平方剩余(quadraticresidue);否则,称a是模p的平方非剩余(quadraticnon-residue).定理5.10(Euler准则)

设p>2是一个素数,x是一个整数,gcd(x;p)=1,则1)x是模p的平方剩余当且仅当2)x是模p的平方非剩余当且仅当2023/9/18155.3.2模奇素数的平方剩余定义5.5设p>25.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(modp)，则定理5.13

设p>2是一个素数,q>2也是一个素数，p≠

q2023/9/18165.3.3Legendre符号定义5.6设p>5.3.4

Jacobi

符号定义5.7

设n>2是一个奇整数,n的素分解为其中是素数,对任意整数a,称为Jacobi符号定理5.14

设n>2是一个奇整数。1)如果则2)3)4)如果m>2是奇整数,则引理5.1

设n>2是一个奇整数,n的素分解为其中是素数,则2023/9/18175.3.4Jacobi符号定义5.7设n>25.3.5

Solovay-Strassen

素性测试法由Fermat小定理可知,对于一个正整数n,如果存在正整数b满足gcd(b，n)=1,并且不成立，则n一定是合数定理5.15

如果n>2是一个奇合数,则至少有50%的使得同余式不成立。2023/9/18185.3.5Solovay-Strassen素性测试法5.3.6

Miller-Rabin

素性测试法定义5.8

设n>2是一个奇数.设其中s是非负整数,m>0是奇数。设0<b<n。如果或者存在一个r,06r<s,使得则称n通过以b为基的Miller-Rabin测试。定理5.16

设p>2是一个素数.对任意整数b>0,如果gcd(b，p)=1,则p一定可以通过以b为基的Miller-Rabin测试。定理5.17

如果n>2是一个奇合数,则至多有个b,0<b<n,使得n通过以b为基的Miller-Rabin测试.2023/9/18195.3.6Miller-Rabin素性测试法定义5.5.4EIGamal公钥密码EIGamal公钥密码体制EIGamal公钥密码体制的安全性有限域上离散对数的计算方法主要内容2023/9/18205.4EIGamal公钥密码EIGamal公钥密码5.4.1

EIGamal

公钥密码体制EIGamal

公钥密码体制描述如下：选取大素数

p是一个本原元.p和α公开.随机选取整数

计算，β公开是公开的加密密，d是保密的解密密钥明文空间为

，密文空间为加密变换：对任意明文

秘密随机选取一个整数k，1k

p−2,密文为其中解密变换：对任意密文明文为2023/9/18215.4.1EIGamal公钥密码体制EIGamal5.4.2

EIGamal

公钥密码体制的安全性定义5.9

设p是一个素数,是一个本原元,已知α和β，求满足的唯一整数n,0≤

n≤

p−2,称为有限域上的离散对数问题.常将n记为2023/9/18225.4.2EIGamal公钥密码体制的安全性定义5.5.4.3有限域上离散对数的计算方法Shanks算法指标计算法Pohlig-Hellman算法主要内容2023/9/18235.4.3有限域上离散对数的计算方法Shanks算5.5

椭圆曲线上的Menezes-Vanstone公钥密码椭圆曲线的定义实数域上椭圆曲线的图像实数域上椭圆曲线点的加法运算实数域上椭圆曲线点的加法运算的性质有限域上的椭圆曲线有限域上的椭圆曲线的性质椭圆曲线上的离散对数问题Menezes-Vanstone公钥密码体制2023/9/18245.5椭圆曲线上的Menezes-Vanstone公5.5.1

椭圆曲线的定义设F是一个域.域F上的椭圆曲线是指由Weierstrass方程确定的所有点(x,y)∈F×F以及一个特殊的无穷远点O所构成的集合,其中2023/9/18255.5.1椭圆曲线的定义设F是一个域.域F上的椭5.5.2

实数域上椭圆曲线的图像方程根的情况是Δ>0有一个实根和一对共轭复根Δ=0有三个实根，分别为Δ<

0有三个不同的实根实数域上的椭圆曲线方程关于x轴是对称的。如果判别式Δ≠0，则称其为非奇异椭圆曲线；否则称其为奇异椭圆曲线。点击查看图例2023/9/18265.5.2实数域上椭圆曲线的图像方程5.5.2

实数域上椭圆曲线的图像定理5.18(代数基本定理)

设为实数域上的一个一元n次多项式,n为整数,并且n≥1,则f(x)在复数域上有且仅有n个根。定理5.19(一元多项式根与系数的关系)

设为实数域上的一个一元n次多项式,n为整数,并且n≥1。设为f(x)的n个根,则对于2023/9/18275.5.2实数域上椭圆曲线的图像定理5.18(代数基5.5.3

实数域上椭圆曲线点的加法运算设a和b为实数为实数域上的非奇异椭圆曲线,其中O为无穷远点。在椭圆曲线E上定义加法运算如下：对任意定义其中另外,对任意定义P+O=O+P=P2023/9/18285.5.3实数域上椭圆曲线点的加法运算设a和b为实5.5.4

实数域上椭圆曲线点加法运算的性质(封闭性)对任意P∈E和

Q∈E,P+Q∈E(结合律)对任意P∈E,Q∈E以及R∈E,(P+Q)+R=P+(Q+R)(单位元)对任意P∈E,P+O=O+P=P(负元素)对任意P∈E,存在Q∈

E,满足P+Q=Q+P=O(交换律)对任意P∈E和Q∈E,P+Q=Q+P2023/9/18295.5.4实数域上椭圆曲线点加法运算的性质(封闭性)5.5.5

有限域上的椭圆曲线定义5.10

设p>3是一个素数.有限域上的椭圆曲线是由一个称为无穷远点的特殊点O和满足的所有点同余方程组成的集合E,其中对任意定义其中定义加法运算2023/9/18305.5.5有限域上的椭圆曲线定义5.10设p>35.5.6

有限域上的椭圆曲线的性质定理5.20(Hasse定理)

设E是有限域上的椭圆曲线,则定理5.21(Hasse定理)

设E是有限域上的椭圆曲线,则其中t的绝对值定理5.22(椭圆曲线的群结构)

设E是有限域

上的椭圆曲线,p>3为素数,则存在正整数和，使得E与同构,和

满足并且2023/9/18315.5.6有限域上的椭圆曲线的性质定理5.20(Ha5.5.7

椭圆曲线上的离散对数问题定义5.11

设E是有限域上的椭圆曲线,的阶是满足的最小正整数n,记为ord(P),其中O是无穷远点。定义5.12

设p>3是一个素数,E是有限域上的椭圆曲线.设G是E的一个循环子群,P是G的一个生成元,Q∈

G.已知P和Q,求满足nP=Q的唯一整数称为椭圆曲线上的离散对数问题。2023/9/18325.5.7椭圆曲线上的离散对数问题定义5.11设E5.5.8

Menezes-Vanstone公钥密码体制随机选取整数d，1≤d≤ord(α)−1。计算β=dα，

β是公开的加密密钥，d是保密的解密密钥Menezes-Vanstone公钥密码体制描述如下设p>3是一个大素数，E是有限域Zp上的椭圆曲线。α∈E是椭圆曲线上的一个点，并且α的阶足够大，使得在由α生成的循环子群中离散对数问题是难解的。p和E以及α都公开明文空间为密文空间为加密变