现代密码学第七讲：公钥密码学2

1、1公钥密码（二）现代密码学第七章上节内容回顾公钥密码体制的提出及分类公钥密码体制的基本概念单向陷门函数的概念设计公钥加密算法-背包密码体制3本节主要内容RSA算法及其分析ElGmal算法椭圆曲线密码体制其它公钥密码算法4 RSA算法是1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。 它既可用于加密、又可用于数字签字。 RSA算法的安全性基于数论中大整数分解的困难性。 R L Rivest, A Shamir, L Adleman, On Digital Signatures and

2、 Public Key Cryptosystems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978RSA算法51. 密钥的产生 选两个安全的大素数p和q。 计算n=pq，(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。 选一整数e，满足1e(n)，且gcd(n),e)=1。 计算d，满足de1 mod (n),即d是e在模(n)下的乘法逆元，因e与(n)互素，由模运算可知，它的乘法逆元一定存在。 以e,n为公开钥,d,n为秘密钥。RSA算法1 选取大素数的方法：随机产生一个大整数，利用素性检测算法判定该整数是否

3、为素数2 以往素检测的算法都是概率性的，即存在一定的错误概率；3 2003年，印度人发表文章“Primes is in P”，证明了素判定问题是一个多项式时间问题。1）辗转相除法2）利用欧拉定理求e( (n)-1思考：分析两种计算方法的效率62. 加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算： cme mod nRSA算法73. 解密对密文分组的解密运算为：mcd mod n证明RSA算法中解密过程的正确性.证明： 由加密过程知cme mod n，所以cd mod nmed mod nm1 mod (n) mod

4、n mk(n)+1 mod nRSA算法8下面分两种情况： m与n互素，则由Euler定理得m(n)1 mod n,mk(n)1 mod n,mk(n)+1m mod n即cd mod nm。 gcd(m,n)1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)1意味着m是p的倍数或q的倍数，不妨设m=tp，其中t为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾RSA算法9 由gcd(m,q)=1及Euler定理得m(q)1 mod q，所以mk(q)1 mod q,m

5、k(q)(p)1 mod q, mk(n)1 mod q 因此存在一整数r，使得mk(n)=1+rq，两边同乘以m=tp得mk(n)+1=m+rtpq=m+rtn即mk(n)+1m mod n，所以cd mod nm.RSA算法10例： 选p=7，q=17. 求得n=pq=119，(n)=(p-1)(q-1)=96.取e=5，满足1e(n)，且gcd(n),e)=1，计算满足de=1 mod 96且小于96的d.因为775=385=496+1，所以d为77，因此公开钥为5，119，秘密钥为77，119.设明文m=19，则由加密过程得密文为c195 mod 1192476099 mod 1196

6、6;解密过程为 m 6677mod 11919.RSA算法11RSA中的计算问题1. RSA的加密与解密过程 RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(ab) mod n=(a mod n)(b mod n) mod n就可减小中间结果。RSA算法12 2. 模指数运算的快速算法 例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x

7、4，x8，x16则只需4次乘法。 求am可如下进行，其中a，m是正整数： 将m表示为二进制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此RSA算法13例：求a1919=124+023+022+121+120所以 a19=(a1)2a0)2a0)2a1)2a1练习：求a7和a8，并统计快速运算法的运算次数. RSA算法14RSA算法RSA的快速实现加密很快，指数小；解密比较慢，指数较大. 利用中国剩余定理CRT，加快计算速度.CRT 对RSA解密算法生成两个解密方程（利用M=Cd mod R） 即: M1 = M mod p = (C mod p )d mod (p-

8、1) mod p M2 = M mod q = (C mod q )d mod (q-1) mod q 解方程组 M = M1 mod p ; M = M2 mod q .利用CRT, 具有唯一解：M = (M2 +q - M1)u mod q p + M1.其中 p.u mod q = 1 .15 整数分解问题：已知n是两个大素数的乘积，求n的素分解RSA的安全性 是基于分解大整数困难的假定 如果RSA的模数n被成功地分解为pq，则获得(n)=(p-1)(q-1)，从而攻击者能够从公钥e解出d，即de-1 mod (n)，攻击成功. RSA算法的安全性16 至今还未能证明分解大整数就是NPC

9、问题，也许有尚未发现的多项式时间分解算法. 随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解.例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解.RSA算法的安全性17 分解算法的进一步改进.过去分解算法都采用二次筛法, 如对RSA-129的分解. 而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%. 1）在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的

10、时期，密钥长度介于1024比特至2048比特之间的RSA是安全的.RSA算法的安全性18 2） |p-q|要大由 ，如果|p-q|小，则 (p-q)2/4 也小；因此(p+q)2/4 稍大于n, 即(p+q)/2稍大于n1/2。那么 顺序检查大于n1/2的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。 由x2-n=y2，得n=(x+y)(x-y)，可得n的分解 .RSA算法的安全性19 3） p-1和q-1都应有大素因子设攻击者截获密文c，可如下进行重复加密：RSA算法的安全性20若 ，即 ，则有 ，即 ，所以在重复加密的倒数第2步就可以恢复出明文m.这种攻击法只有在t较小

11、时才是可行的，为抵抗这种攻击，应保证使t很大.所以为使t大，p-1和q-1都应有大的素因子，且(p-1)*(q-1)有大的素因子RSA算法的安全性RSA算法的安全性4）RSA的选择密文攻击 一般攻击者是将希望解密的信息C作一下伪装reC，让拥有私钥的实体解密。然后，经过解密计算就可得到它所想要的信息。 ( reC ) d = red * Cd mod n = r * M mod n ，所以 M= ( reC ) d * r-1这个固有的问题来自于公钥密码系统的最有用的特征-每个人都能使用公钥。但从算法上无法解决这一问题，只有采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密。R

12、SA算法的安全性5）RSA的公共模数攻击若系统中用户共有一个模数n ，而拥有不同的e和d。若存在同一信息（设为P）分别用不同的公钥（e1和e2）加密，C1 = Pe1 mod n ；C2 = pe2 mod n 设密码分析者截获n、e1、e2、C1和C2， 若恰好e1和e2互质，则他可以得到P。RSA算法的安全性证明：因为e1和e2互质，故用Euclidean算法能找到r和s，满足： r * e1 + s * e2 = 1 则 (C1) r * (C2) s = ( Pe1) r * (pe2) s mod n = P r * e1 + s * e2 mod n =P mod n不要共享模数n

13、其它共模攻击方法：在共模假设下，一对e和d将有利于攻击者分解模数；或者计算出其它成对的e和d，而无需分解模数。24RSA算法的安全性RSA存在很多种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的，为保证算法足够安全，参数须满足下面几个基本要求：需要选择足够大的素数 p, q, |p-q|较大，且(p-1)和(q-1)没有小的素因子.通常选择小的加密指数e, 且与(N) 互素， e对所有用户可以是相同的，最初建议使用e=3，现在3太小，常使用 e=216-1 = 65535.解密指数比较大25Diffie-Hellman key distribution scheme 的变形 能够

14、用于安全交换密钥Published in 1985 by ElGamal: T. ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985. 安全性基于有限域上的离散对数问题的困难性. 缺点：增加了传送信息长度（2倍） ElGamal算法261) 密钥产生过程： 首先选择一素数p,生成元g和小于p的随机数x，计算ygx mod p，以(y, g,

15、 p)作为公开密钥，x作为秘密密钥.2)加密过程：设欲加密明文消息为M. 随机选一与p-1互素的整数k，0=k=p-1； 计算密文对: C = C1,C2, 发送给接收者. C1gk mod p, C2ykM mod p. ElGamal算法27 3) 解密过程: 计算明文: 因为 .ElGamal算法k 需要永久保密，且不能重复使用.为什么？281) 密钥生成. 选择公开参数：p=97 及本原根 a=5 ； Bob 选择 秘密钥xB=58，计算并发布公钥yB=558=44 mod 97. 2) Alice 要加密 M=3 给 Bob. 首先得到 Bob的公开密钥 yB=44，选择随机 k=3

16、6 计算:K=4436=75 mod 97.计算密文对: C1 = 536 = 50 mod 97 ； C2 = 75.3 mod 97 = 31 mod 97.发送 50,31 给Bob .3) Bob 解密消息.恢复消息密钥 K=5058=75 mod 97.Bob 计算 K-1 = 22 mod 97.Bob 恢复明文 M = 31*22 = 3 mod 97.ElGamal算法ElGamal算法有限域上离散对数问题 已知（Zp，+，*）是一个有限域，g为Zp*的生成元，y Zp ，求x使得y=gx mod p如果求离散对数问题是容易的，则获得公钥攻击者能够解出x，则算法完全破译.ElG

17、amal算法为什么离散对数问题难解？RSA与ElGamal比较RSAElGamal加密一次模幂运算两次模幂+一次模乘解密一次模幂运算一次模幂运算密文密文不扩张密文扩张确定算法不确定算法安全RSA问题离散对数问题32椭圆曲线密码体制ECC（elliptic curve cryptography）被IEEE公钥密码标准P1363采用.椭圆曲线并非椭圆，一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e 其中a，b，c，d，e是满足某些简单条件的实数. 定义中包括一个称为无穷点的元素，记为O.椭圆曲线密码体制33椭圆曲线的两个例子椭圆曲线密码体制34椭圆曲

18、线关于x轴对称, 定义椭圆曲线上的加法律（加法法则）如下： O为加法单位元，即对椭圆曲线上任一点P，有P+O=P. 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是唯一的，除非所做的直线是Q点或R点的切线，由Q+R+P1=O得Q+R=-P1.椭圆曲线密码体制35 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，等.设P1=(x,y)是椭圆曲线上的一点（如图所示），它的加法逆元定义为P2=-P1=(x, -y).以上定义的加法具有一般数域加法运算的一般

19、性质，如交换律、结合律等. 椭圆曲线密码体制这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，P1+P2+O=O，P1+P2=O，所以P2=-P1. 由O+O=O，还可得O=-O.36密码学中通常采用有限域上的椭圆曲线，它指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）.其中最为常用的是y2x3+ax+b(mod p)(a,bGF(p), 4a3+27b2(mod p)0)定义的曲线.椭圆曲线密码体制37例： p=23，a=b=1，4a3+27b2(mod 23)80 方程为y2x3+x+1.椭圆曲线密码体制

20、其图形是连续曲线, 我们只考虑曲线在第一象限中的整数点椭圆曲线密码体制设Ep(a,b)表示上面方程所定义的椭圆曲线上的点集(x,y)|0 xp,0yp，且x,y均为整数并上无穷远点O.Ep(a,b)由以下方式计算： 对每一x(0 xp且x为整数），计算x3+ax+b(mod p). 决定中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0 时只有一个平方根）.39本例中E23(1,1)由下表给出（表中不包含O）.椭圆曲线密码体制40Ep(a,b)上的加法定义 设P，QEp(a,b)，则 P+O=P. 如果P=(x,y)，那么(x, y)+(

21、x, -y)=O，即 (x, -y)是P的加法逆元，表示为-P. 由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如上例，P=(13,7)E23(1,1)，-P=(13, -7)，而-7 mod 2316，所以-P=(13, 16)，也在E23(1,1)中.椭圆曲线密码体制思考：根据曲线和两点确定的直线推导P+Q和2P的求解公式41 设P=(x1,y1)，Q=(x2,y2)，P-Q，则P+Q=(x3,y3)由以下规则确定：x32-x1-x2(mod p)y3(x1-x3)-y1(mod p)其中椭圆曲线密码体制42 例： 以E23(1,1)为例，设P=(3,10)，Q=(9,7)，

22、则 所以P+Q=（17,20），仍为E23(1,1)中的点.椭圆曲线密码体制43 若求2P则 所以2P=(7,12) ，仍为E23(1,1)中的点.椭圆曲线密码体制44 从上例看出，加法运算在E23(1,1)中是封闭的，且能验证还满足交换律. 对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以Ep(a,b)是一个Abel群.椭圆曲线密码体制45 在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，QEp(a,b)，kp，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制.倍

23、点运算仍定义为重复加法，如4P=P+P+P+P椭圆曲线密码体制为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题.46利用椭圆曲线实现ElGamal密码体制 1 密钥生成 选取一条椭圆曲线，并得Ep(a,b)，取Ep(a,b)的一个生成元G，Ep(a,b)和G作为公开参数. 用户A选nA作为秘密钥，并以PA=nAG作为公开钥. 椭圆曲线密码体制472 加解密运算任一用户B若想向A发送消息Pm，可选取一随机正整数k，产生以下点对作为密文：Cm=kG, Pm+kPA A解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点的倍乘，即 Pm+kPA-nAkG=Pm+k(nAG)-nAk

24、G=Pm椭圆曲线密码体制将明文消息m通过编码嵌入到曲线上的点Pm，再对点Pm做加密变换.这里不对具体的编码方法做进一步介绍，读者可参考有关文献.攻击者若想由Cm得到Pm，就必须知道k。而要得到k，只有通过椭圆曲线上的两个已知点G和kG，这意味着必须求椭圆曲线上的离散对数，因此不可行.48例：取p=751，Ep(-1,188)，即椭圆曲线为y2x3-x+188, Ep(-1,188)的一个生成元是G=(0,376)，设A的公开钥为PA=(201,5).假定B已将欲发往A的消息嵌入到椭圆曲线上的点Pm=(562,201)，B选取随机数k=386，由kG=386(0,376)=(676,558)，P

25、m+kPA=(562，201)+386(201,5)=(385,328)，得密文为(676,558),(385,328).椭圆曲线密码体制49与基于有限域上离散对数问题的公钥体制相比，椭圆曲线密码体制有如下优点: 1） 安全性高攻击有限域上的离散对数问题可以用指数积分法，其运算复杂度为 ，其中p是模数（为素数）, 而这种方法对椭圆曲线上的离散对数问题并不有效.椭圆曲线密码体制50目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群上离散对数问题的大步小步法，其运算复杂度为 ，其中pmax是椭圆曲线所形成的Abel群的阶的最大素因子. 因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全.椭圆曲线密码体制51 2) 密钥量小 由攻击两者的算法复杂度可知，在实现相同的安全性能条件下，椭圆曲线密码体制所需的密钥量远比基于有限域上的离散