第四章_公钥密码-new

1、信息安全理论及应用信息安全理论及应用第第4章章 公钥密码公钥密码1.公钥密码体制简介公钥密码体制简介2. 常用数论知识常用数论知识3. RSA算法算法4. Rabin密码体制密码体制5. 椭圆曲线密码体制椭圆曲线密码体制信息安全理论及应用信息安全理论及应用1.1 公钥密码体制简介公钥密码体制简介对称密码体制：对称密码体制：保密性，运算速度快，适合加密保密性，运算速度快，适合加密 大量数据大量数据公钥密码体制：公钥密码体制：保密性，密钥分配，认证；运算保密性，密钥分配，认证；运算 速度慢，适合加密少量数据。如：速度慢，适合加密少量数据。如： 用公钥密码加密传送分组密码的密钥。用公钥密码加密传送分

2、组密码的密钥。(1) 公钥密码体制与对称密码体制比较公钥密码体制与对称密码体制比较:信息安全理论及应用信息安全理论及应用公钥密码的理论基础公钥密码的理论基础: 陷门单向函数陷门单向函数单向函数单向函数: 已知已知x, 计算计算y使得使得y=f(x)容易容易; 已知已知y, 计算计算x使得使得y=f(x)是难解的。是难解的。陷门单向函数陷门单向函数: t是与是与f有关的一个参数有关的一个参数 已知已知x, 计算计算y使得使得y=f(x)容易容易; 如果不知道如果不知道t，已知已知y, 计算计算x使得使得y=f(x)是难的，是难的， 但知道但知道t时，已知时，已知y, 计算计算x使得使得y=f(x

3、)是容易的。是容易的。 参数参数t称为陷门（称为陷门（Trapdoor）。信息安全理论及应用信息安全理论及应用最大特点是采用两个相关密钥将加密和解密能力分最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。的，称为秘密密钥，简称秘密钥，用于解密。公钥密码体制也称为公钥密码体制也称为双钥密码体制或非对称密码体双钥密码体制或非对称密码体制制。算法有以下重要特性：算法有以下重要特

4、性： 已知密码算法和加密密钥，求解密密钥在计算上是已知密码算法和加密密钥，求解密密钥在计算上是不可行的。不可行的。(2) 公钥密码体制的原理公钥密码体制的原理信息安全理论及应用信息安全理论及应用图图4.1 公钥体制加密的框图公钥体制加密的框图信息安全理论及应用信息安全理论及应用公钥密码算法应满足以下要求公钥密码算法应满足以下要求: 接收方接收方B产生密钥对（产生密钥对（PKB和和SKB）在计算上是在计算上是容易的。容易的。 发方发方A对消息对消息m加密以产生加密以产生密文密文c，即即c=EPKBm在计算上是容易的。在计算上是容易的。 收方收方B用自己的秘密钥对用自己的秘密钥对c解密，即解密，即

5、m=DSKBc在在计算上是容易的。计算上是容易的。(3) 公钥密码算法应满足的要求公钥密码算法应满足的要求信息安全理论及应用信息安全理论及应用 敌手敌手由由PKB求求SKB在计算上是不可行的。在计算上是不可行的。 敌手由敌手由密文密文c和和PKB恢复明文恢复明文m在计算上是不可在计算上是不可行的。行的。以上要求的本质之处在于要求一个陷门单向函数。以上要求的本质之处在于要求一个陷门单向函数。因此，研究公钥密码算法就是要找出合适的陷门单因此，研究公钥密码算法就是要找出合适的陷门单向函数。向函数。信息安全理论及应用信息安全理论及应用数论是密码学特别是公钥密码学的基本工具，本章数论是密码学特别是公钥密

6、码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制几种重要算法。公钥密码体制几种重要算法。信息安全理论及应用信息安全理论及应用1.2 常用数论知识常用数论知识1. 费尔玛定理和欧拉定理费尔玛定理和欧拉定理2. 素性检验素性检验: Miller-Rabin的素性概率检测法的素性概率检测法3. 广义欧几里得除法广义欧几里得除法4. 中国剩余定理中国剩余定理离散对数离散对数5. 平方剩余平方剩余信息安全理论及应用信息安全理论及应用定理定理4.1 设设aZn，gcd(a, n)=1，则则a在在Zn中有乘法逆元。中有乘法逆元。证明：证

7、明： 首先证明首先证明a与与Zn中任意两个不相同的数中任意两个不相同的数b、c（不妨设不妨设cb）相乘，其结果必然不同。相乘，其结果必然不同。 否则设否则设abac mod n，则则存在两个整数存在两个整数k1,k2，使得使得ab=k1n+r，ac=k2n+r，可得可得a(b-c)=(k1-k2)n，所以所以a是是(k1-k2)n的一个因子。又由的一个因子。又由gcd(a，n)=1，得得a是是k1-k2的的一个因子，设一个因子，设k1-k2=k3a，所以所以a(b-c)=k3an，即即b-c=k3n，与与0cb0. 则则存在唯一的整数存在唯一的整数q, r使得使得 a=bq+r, 0 rb信息

8、安全理论及应用信息安全理论及应用广义广义欧几里得欧几里得除法除法设设a, b是任意两个正整数是任意两个正整数, 记记 r0=a, r1=b, 用用欧几里得欧几里得除法除法:1221100,rrrqrr 2332210,rrrqrr 11120, nnnnnnrrrqrr0,111 nnnnnrrqrrbrrrrrnnn 12110定理定理4 设设a, b是任意两个正整数是任意两个正整数, 则则 (a, b)=rn信息安全理论及应用信息安全理论及应用定理定理 设设a, b是任意两个正整数是任意两个正整数, 则则 (a, b)=rn1221100,rrrqrr 2332210,rrrqrr 111

9、20, nnnnnnrrrqrr0,111 nnnnnrrqrr证证),(),(2rbba ),(32rr),(1nnrr nnnnrrrr ) 0 ,(),(1信息安全理论及应用信息安全理论及应用1102qrrr 2213qrrr 112 nnnnqrrr1221100,rrrqrr 2332210,rrrqrr 11120, nnnnnnrrrqrr0,111 nnnnnrrqrrr0=a, r1=b有有s, t 满足满足 s a + t b =(a, b) 信息安全理论及应用信息安全理论及应用定理定理 整数整数a, b互素互素 存在整数存在整数 s, t 满足满足 s a + t b =

10、1证证: 必要性显然必要性显然。充分性：已知充分性：已知s a + t b =1，则则a, b互素互素 设设 d=(a, b), 则则d|a, d|b, 有有d | s a + t b =1，则则d=1, 故故a, b互素互素 求乘法逆元：求乘法逆元：如果如果gcd(a, b)=1 ，则则b在在mod a下有乘法逆元下有乘法逆元, 即即存在一存在一x (xa)，使得使得bx1 mod a。信息安全理论及应用信息安全理论及应用 中国剩余定理是数论中最有用的一个工具，中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同定理说如果已知某个数关于一些两两互素的数的同余类集

11、，就可重构这个数。余类集，就可重构这个数。 例如：例如：Z10中每个数都可从这个数关于中每个数都可从这个数关于2和和5（10的两个互素的因子）的同余类重构。的两个互素的因子）的同余类重构。 比如已知比如已知x关于关于2和和5的同余类分别是的同余类分别是0和和3，即即x mod 20，x mod 53。可知是偶数且被可知是偶数且被5除后除后余数是余数是3，所以可得，所以可得8是满足这一关系的惟一的是满足这一关系的惟一的x。4. 中国剩余定理中国剩余定理信息安全理论及应用信息安全理论及应用定理定理4.6（中国剩余定理）（中国剩余定理） 设设m1,m2,mk是两两互是两两互素的正整数，素的正整数，

12、，则一次同余方程组则一次同余方程组对模对模M有惟一解有惟一解:其中其中ei满足满足1122modmodmodkkamxamxamx1kiiMm1 12212modkkkMMMxe ae ae aMmmm1 mod1, 2,iiiMemikm信息安全理论及应用信息安全理论及应用证明：设证明：设 ,i=1,2,k，由由Mi的定的定义得义得Mi与与mi是互素的，可知是互素的，可知Mi在模在模mi下有惟一的下有惟一的乘法逆元，即满足乘法逆元，即满足 的的ei是惟一的。是惟一的。1kilill iMMmm1 modiiiMemm信息安全理论及应用信息安全理论及应用下面证明对下面证明对 i1,2,k，上述

13、上述x满足满足ai(mod mi)x。注意到当注意到当ji时，时，mi|Mj，即即Mj0(mod mi)。所以所以(Mjej mod mj) mod mi (Mj mod mi)(ej mod mj) mod mi) mod mi 0而而(Mi(ei mod mi) mod mi(Miei) mod mi1所以所以x(mod mi)ai，即即ai(mod mi)x信息安全理论及应用信息安全理论及应用下面证明方程组的解是惟一的。设下面证明方程组的解是惟一的。设x是方程组的另是方程组的另一解，即一解，即xai(mod mi)(i=1,2,k)由由xai(mod mi)得得x-x0(mod mi)，

14、即即mi|(x-x)。再再根据根据mi两两互素，有两两互素，有M|(x-x)，即即x-x0(mod M)，所以所以x(mod M)=x(mod M)。(证毕证毕) 中国剩余定理提供了一个非常有用的特性，即中国剩余定理提供了一个非常有用的特性，即在模在模M下可将非常大的数下可将非常大的数x由一组小数由一组小数(a1,a2,ak)表达。表达。信息安全理论及应用信息安全理论及应用例例4.14 由以下方程组求由以下方程组求x。解：解： M=2357=210，M1=105，M2=70，M3=42，M4=30,易求易求e1M-11 mod 21,e2M-12mod 31,e3M-13 mod 53,e4M

15、-14 mod 74, 所以所以x mod 210(10511+7012+4233+3045) mod 210173，或写成或写成x173 mod 210。1mod22mod33mod55mod7xxxx信息安全理论及应用信息安全理论及应用例例4.15 将将973 mod 1813由模数分别为由模数分别为37和和49的两个的两个数表示。数表示。解：解： 取取x=973, M=1813, m1=37,m2=49。由由a1973 mod m111,a2973 mod m342得得x在模在模37和模和模49下的表达为（下的表达为（11,42）。）。信息安全理论及应用信息安全理论及应用1. 求模下的整

16、数幂求模下的整数幂Euler定理指出如果定理指出如果gcd(a, n)=1，则则a(n)1 mod n。现在考虑如下的一般形式现在考虑如下的一般形式:am1 mod n如果如果a与与n互素，则至少有一整数互素，则至少有一整数m（比如比如m=(n)）满足这一方程。称满足方程的最小正整数满足这一方程。称满足方程的最小正整数m为模为模n下下a的阶。的阶。5. 离散对数离散对数信息安全理论及应用信息安全理论及应用例如：例如： a=7，n=19，则易求出则易求出717 mod 19,7211 mod 19,731 mod 19，即即7在模在模19下的阶为下的阶为3。由于由于73+j=737j7j mod

17、 19, 所以所以747 mod 19,7572 mod 19, , 即从即从74 mod 19开始所求的幂出现循环，循环周期开始所求的幂出现循环，循环周期为为3，即循环周期等于元素的阶。，即循环周期等于元素的阶。信息安全理论及应用信息安全理论及应用定理定理4.7设设a的阶为的阶为m，则则ak1 mod n的充要条件是的充要条件是k为为m的倍数。的倍数。证明：设存在整数证明：设存在整数q，使得使得k=qm，则则ak(am)q1 mod n。反之，假定反之，假定ak1 mod n，令令k=qm+r,其中其中00,a1)的逆函数称为以的逆函数称为以a为底为底x的对数，记为的对数，记为y=logax

18、。对数函数有以下性质：对数函数有以下性质： loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模运算中也有类似的函数。在模运算中也有类似的函数。p是一素数，是一素数，a是是p的本原根，则的本原根，则a,a2,ap-1产生出产生出1到到p-1之间的所有值，且每一值只出现一次。因此之间的所有值，且每一值只出现一次。因此对任意对任意b1,p-1，都存在惟一的都存在惟一的i(1ip-1)，使使得得bai mod p。称称i为模为模p下以下以a为底为底b的指标，记为的指标，记为i=inda,p(b)。信息安全理论及应用信息安全理论及应用指标有以下性质：指标

19、有以下性质： inda,p(1)=0。 inda,p(a)=1。 分别由以下关系得出：分别由以下关系得出： a0 mod p=1 mod p=1,a1 mod p=a。以上假定模数以上假定模数p是素数，对于非素数也有类似的结是素数，对于非素数也有类似的结论。论。信息安全理论及应用信息安全理论及应用例例4.6 设设p=9，则则(p)=6，a=2是是p的一个本原根，的一个本原根，a的不同的幂为（模的不同的幂为（模9下）下）201, 212, 224,238, 247, 255, 261由此可得由此可得a的指数表如表的指数表如表4.3（a）所示。所示。重新排列表重新排列表4.4（a），），可求每一与

20、可求每一与9互素的数的指互素的数的指标如表标如表4.4（b）所示。所示。 在讨论指标的另两个性质时，需要利用如下在讨论指标的另两个性质时，需要利用如下结论：结论： 若若azaq mod p，其中其中a和和p互素，则有互素，则有zq mod (p)。信息安全理论及应用信息安全理论及应用证明：因证明：因a和和p互素，所以互素，所以a在模在模p下存在逆元下存在逆元a-1，在在azaq mod p两边同乘以两边同乘以(a-1)q，得得az-q1 mod p。由由Euler定理定理a(p)1 mod p知知, 存在一整数存在一整数k，使得使得z-qk(p)，所以所以zq mod (p)。由上述结论可得指

21、标的以下两个性质：由上述结论可得指标的以下两个性质： inda,p(xy)=inda,p(x)+inda,p(y) mod (p)。 inda,p(yr)=rinda,p(y) mod (p)。信息安全理论及应用信息安全理论及应用性质的证明：设性质的证明：设由模运算的性质得：由模运算的性质得：所以所以inda,p(xy)=inda,p(x)+inda,p(y) mod (p)（证毕）证毕） ,mod ,mod ,mod ,a pa pa pindxindyindxyxap yap xyap ,mod(mod) (mod)()moda pa pa pa pa pindxyindxindyindx

22、indyapapapap性质是性质的推广。性质是性质的推广。从指标的以上性质可见，指标与对数的概念极为相从指标的以上性质可见，指标与对数的概念极为相似。似。信息安全理论及应用信息安全理论及应用离散对数离散对数设设p是素数，是素数，a是是p的本原根，即的本原根，即a1,a2,ap-1在在 mod p下产生下产生1到到p-1的所有值，所以对的所有值，所以对b1,p-1，有惟一的有惟一的i1,p-1使得使得bai mod p。称称i为模为模p下以下以a为底为底b的离散对数，记为的离散对数，记为ilogab(mod p)。当当a、p、i已知时，用快速指数算法可比较容易地已知时，用快速指数算法可比较容易

23、地求出求出b，但如果已知但如果已知a、b和和p，求求i则非常困难。目则非常困难。目前已知的最快的求离散对数算法其时间复杂度为：前已知的最快的求离散对数算法其时间复杂度为：所以当所以当p很大时，该算法也是不可行的。很大时，该算法也是不可行的。2133explnln lnOpp信息安全理论及应用信息安全理论及应用2 (mod), ( ,)1 mxama mamam 设设 是是正正整整数数, ,若若同同余余式式有有解解, ,则则 叫叫做做模模 的的( (或或),),否否则则 叫叫做做模模 的的平平方方剩剩余余平平方方非非剩剩余余 定定二二次次剩剩余余二二次次非非义义( (或或剩剩余余) ). .6

24、6、平方剩余、平方剩余信息安全理论及应用信息安全理论及应用 11 4, 14 是是模模 平平方方剩剩余余是是模模 平平方方例例非非剩剩余余. .21 (mod4)1,3 (mod4)xx 解解 因因 有有解解 21 (mod4)x 而而 无无解解. .1,2,4,7, 1,3 ,25 7 是是模模 平平方方剩剩余余是是模模 平平方方 例例非非剩剩余余. .22 24, 54 (mod7)2211, 61 (mod7) 解解 因因 22 32, 42 (mod7) 2221 (mod7),3 (mod7),5 (mod7)xxx 而而 均均无无解解. .信息安全理论及应用信息安全理论及应用23

25、:1 (m3 od7)Eyxx 求求 满满足足方方 程程例例的的所所有有点点. .0,1,2,3,4,5,6, .xy 解解 对对分分别别求求出出20,1 (mod7),xy 时时1,6 (mod7)y21,3 (mod7),xy时时无无解解22,4 (mod7),xy 时时2,5 (mod7)y 23,3 (mod7),xy 时时无无解解24,6 (mod7),xy 时时无无解解25,5 (mod7),xy 时时无无解解26,6 (mod7),xy 时时无无解解信息安全理论及应用信息安全理论及应用模为奇素数的平方剩余与平方非剩余模为奇素数的平方剩余与平方非剩余 奇素数模奇素数模 p 的平方的

26、平方( (非非) )剩余判别条件剩余判别条件2 (mod), ( ,)1apxapa p 且且若若 是是模模 的的平平方方剩剩余余, ,则则同同余余式式恰恰有有两两解解. .11()( , )1, (i) 1 (mod);(ii) 1 (mod);ppa papapapap 2 22 2 若若则则是是模模 的的平平方方剩剩欧欧拉拉判判别别条条件件余余是是模模 的的平平方方非非剩剩定定余余理理1 1奇素数模的二次同余式要奇素数模的二次同余式要么无解，要么恰有两解么无解，要么恰有两解信息安全理论及应用信息安全理论及应用(i)p证证因因 是是奇奇素素数数所所以以有有 ，122()( )(1)pxa

27、xq xax ( )q x其其中中是是整整系系数数多多项项式式. .0 (mod),()pxxp因因费费尔尔马马定定理理 1220 (mod)10 (mod)pxapap 于于是是有有两两解解1112222()(1)ppppxxxxaax 122()( )(1)0 (mod)pxa xq xaxp 所所以以 信息安全理论及应用信息安全理论及应用1(ii) 1 (mod), pa, pap 因因( () )= =1 1, ,由由有有1122|1) |1)pppapa 于于是是( (或或( ( 12|1)papa 但但 是是平平方方剩剩余余( (12|1)papa 故故 是是平平方方非非剩剩余余(

28、 (1122 1)1)0 (mod)ppaap ( ( (121 (mod)pap 即即 信息安全理论及应用信息安全理论及应用12121212121212 (, )1,(, )1, (i) , , (ii) , , (iii) , , papapa apa apa apa apapapa ap 设设是是奇奇素素数数, ,则则如如果果都都是是模模的的平平方方剩剩余余 则则是是模模的的平平方方剩剩余余；如如果果都都是是模模的的平平方方非非剩剩余余 则则是是模模的的平平方方剩剩余余；如如果果 是是模模的的平平 推推论论方方剩剩余余是是模模的的平平方方非非剩剩余余 则则是是模模 的的平平方方非非剩剩余

29、余. .1112221212()pppa aaa 证证 因因 1由由定定理理 即即得得结结论论. .信息安全理论及应用信息安全理论及应用奇素数模奇素数模 p 的平方的平方( (非非) )剩余的个数剩余的个数222112211 , 2 , ()2ppppp 设设 是是奇奇素素数数, ,则则模模 的的简简化化剩剩余余系系中中平平方方剩剩余余与与平平方方非非剩剩余余的的个个数数各各为为, ,且且个个平平方方 定定理理剩剩余余与与序序列列 中中的的一一个个数数同同余余, ,且且仅仅与与2 2一一个个数数同同余余. .12 1 (mod)pxp 证证 由由定定理理1 1知知平平方方剩剩余余的的个个数数等

30、等于于同同余余式式信息安全理论及应用信息安全理论及应用的的解解数数. .1121|1, ppxx 但但 121|ppxxx 即即 112pp 而而平平方方非非剩剩余余的的个个数数是是1,2p 所所以以此此同同余余式式的的解解数数为为故故平平方方剩剩余余的的个个数数1.2p 1,2p 是是再再证证定定理理的的第第二二部部分分. .p显显然然序序列列中中的的数数都都是是平平方方剩剩余余, ,下下面面只只需需证证明明它它们们对对于于模模 互互不不同同余余即即可可. .信息安全理论及应用信息安全理论及应用|() |(), pklpkl 因因此此或或 11,2pk l 但但 21, |1,klppklp

31、p 故故 , .kl 从从而而矛矛盾盾()()0 (mod)kl klp 则则 22, (mod)klklp 若若存存在在使使得得信息安全理论及应用信息安全理论及应用求求出出模模7 7的的平平方方剩剩余余与与平平例例2 2 方方非非剩剩余余. .222 1 ,2 ,3 (mod7)a 解解 模模7 7的的平平方方剩剩余余为为1,2,3,4,5,6又又模模7 7的的简简化化剩剩余余系系为为 232 (mod7) 而而 1,2,4 (mod7)a 所所以以模模7 7的的平平方方剩剩余余为为 3,5,6 (mod7)a 而而平平方方非非剩剩余余为为 信息安全理论及应用信息安全理论及应用819 23例

32、例 、求求出出， 的的平平方方剩剩余余和和平平方方非非剩剩余余。731例例 、在在与与模模互互素素的的剩剩余余中中，指指出出平平方方剩剩余余。信息安全理论及应用信息安全理论及应用Legendre符号符号Legendre | .appapaappp a 设设 是是素素数数, ,符符号号定定义义如如下下: :1 1, , 若若 是是模模的的平平方方剩剩余余; ; - -1 1, , 若若 是是模模的的平平方方非非剩剩余余; ;0 0, , 若若 定定义义由由定定义义可可知知, , 同同余余式式2 (mod) 1.axapp 有有解解信息安全理论及应用信息安全理论及应用1,2,4,7, 1,3,51

33、 7 因因是是模模 平平方方剩剩余余是是模模 平平方方 例例非非剩剩余余. .1241,777所所以以 1351777 12() , (m1od) ppaaapp 设设 是是奇奇素素数数 则则对对任任意意欧欧拉拉判判 整整别别定定理理法法数数Legendre,4.21利利用用符符号号定定理理 欧欧拉拉判判别别条条件件可可叙叙述述为为信息安全理论及应用信息安全理论及应用12 ,1(1) 11;1(2) ( 1)pppp 则则推推设设 是是奇奇素素数数论论 ,1, 1 (mod4)1 1, 3 (mod ) 24pppp 设设 是是奇奇素素数数 则则推推论论若若 若若 信息安全理论及应用信息安全理

34、论及应用12,1 ( 1)pp 证证 由由推推论论1 1 有有1 (mod4),14 ,pkpk若若则则存存在在正正整整数数使使得得则则1221( 1)( 1)1pkp 3 (mod4),34 ,pkpk若若则则存存在在正正整整数数使使得得则则12121( 1)( 1)1pkp 信息安全理论及应用信息安全理论及应用Legendre符号符号Legendre | .appapaappp a 设设 是是素素数数, ,符符号号定定义义如如下下: :1 1, , 若若 是是模模的的平平方方剩剩余余; ; - -1 1, , 若若 是是模模的的平平方方非非剩剩余余; ;0 0, , 若若 定定义义1 1由

35、由定定义义可可知知, , 同同余余式式2 (mod) 1.axapp 有有解解信息安全理论及应用信息安全理论及应用1,2,4,7, 1,3,51 7 因因是是模模 平平方方剩剩余余是是模模 平平方方 例例非非剩剩余余. .1241,777所所以以 1351777 12() , (m1od) ppaaapp 设设 是是奇奇素素数数 则则对对任任意意欧欧拉拉判判 整整别别定定理理法法数数Legendre,1利利用用符符号号 定定理理 欧欧拉拉判判别别条条件件可可叙叙述述为为信息安全理论及应用信息安全理论及应用12 ,1(1) 11;1(2) ( 1)pppp 则则推推设设 是是奇奇素素数数论论 ,

36、1, 1 (mod4)1 1, 3 (mod ) 24pppp 设设 是是奇奇素素数数 则则推推论论若若 若若 信息安全理论及应用信息安全理论及应用12,1 ( 1)pp 证证 由由推推论论1 1 有有1 (mod4),14 ,pkpk若若则则存存在在正正整整数数使使得得则则1221( 1)( 1)1pkp 3 (mod4),34 ,pkpk若若则则存存在在正正整整数数使使得得则则12121( 1)( 1)1pkp 信息安全理论及应用信息安全理论及应用1212 (i) ;(ii) ; (iii) ( , )1, 21nniipapappababpppa aaappaa pp 设设 是是奇奇素素

37、数数, ,则则设设则则定定理理信息安全理论及应用信息安全理论及应用2 (mod)xap apapp 所所以以 (ii) 由由欧欧拉拉判判别别法法, ,有有 1122(mod),(mod)ppabapbppp 12()(mod)pababpp 及及(i) 证证 因因同同余余式式2 (mod)xapp 等等价价于于同同余余式式信息安全理论及应用信息安全理论及应用(iii)( , )=1,|,1 ,aa ppap 因因所所以以于于是是 = 111222()pppabababp 因因此此 (mod)abppp 22ababpppp 又又而而 ababppp 所所以以22 1aapp 所所以以信息安全理

38、论及应用信息安全理论及应用 (mod),. ababppp 若若则则推推论论2 22 , |,1 .abappbpp 设设 是是奇奇素素数数 若若则则推推论论 11 (1,2,)22 (Gauss ( 1) .)mpaa , ppakk =ppmap 设设 是是奇奇素素数数, , 是是整整数数, ,如如果果整整数数中中模模 的的最最小小正正剩剩余余大大于于的的个个数数是是, ,则则 引引理理( () ), ,信息安全理论及应用信息安全理论及应用,2p于于的的最最小小正正剩剩余余 则则121,1,2,2tpa aaaaa 证证 设设是是整整数数关关2pp于于模模 的的小小于于的的最最小小正正剩剩

39、余余, ,12 ,mb bb是是一一切切大大1211!(1)(2)()22pppaaaa 1212 (mod )tma aa b bbp 1212( 1)()()() (mod)mtma aapbpbpbp ()(mod)jjpbbp信息安全理论及应用信息安全理论及应用 0 (mod )jiijpakakakakp 或或111.22ijppkkp 因因为为 12, mpbpbpbp 是是模模 两两两两不不同同余余的的. .1212, tma aapbpbpbp 易易知知是是模模 两两两两不不同同余余的的. .12,ta aap事事实实上上, ,是是模模 两两两两不不同同余余的的, ,若若有有

40、(mod),jipbap ,ijk k则则有有使使( , )1, 0 (mod),ijp akkp 因因所所以以这这不不可可能能, ,信息安全理论及应用信息安全理论及应用12121,1,2,2tmpa aapbpbpb 是是的的一一1211!(1)(2)()22pppaaaa 1212(1)()()()mtma aapbpbpb1(1)! (mod)2mpp 于于是是1(, )1, 1,2,2pak pk 因因为为1 2p 所所以以个个整整数数个个排排列列. .信息安全理论及应用信息安全理论及应用12 (1) (mod)pmaapp 因因此此引引理理得得证证. .1,ap 注注意意到到 ( 1

41、) .map 故故 信息安全理论及应用信息安全理论及应用212118 (i) ( 1)(ii) ( ,2 )1, ( 1)pkpakpppapap 设设 是是奇奇素素数数定定理理若若3 32 2则则 , ,1,0,1,2,2kkakpakprrp kp 证证 因因11,2,2pk 对对求求和和 有有信息安全理论及应用信息安全理论及应用111222111()pppkkkkakakprp12211118ptmijkijpakapabp 即即 121111()2ptmmijjkijjakpapbbmpp 由引理由引理的证明的证明12211128pmjkjakppmpbp 信息安全理论及应用信息安全理

42、论及应用122111, (1)28pmjkjpakapmpbp 因因此此1122111(1)(1)2ppmjkkjakakmpm pbpp 12211 (1) (mod2)8pkpakamp 所所以以2 2的倍数的倍数12,00,akpapp 若若则则21 (mod2)8pm 于于是是212 8pmr 信息安全理论及应用信息安全理论及应用22112222( 1)( 1)( 1)pprmp 由由引引理理121 (mod2)pkakamp 若若 为为奇奇数数, , 则则112211 +2( 1)( 1)( 1)ppkkakaktppmap 由由引引理理121 +2pkakmtp 即即 信息安全理论

43、及应用信息安全理论及应用 81, 2 83, 2pmpm 即即 当当时时是是平平方方剩剩余余当当时时是是平平方方非非剩剩余余, , . .,1, 1 (mod8)2 1, 3 (mod8) pppp 设设 是是奇奇素素数数 则则若若推推论论 若若= =3, 证证 由由定定理理2182 ( 1)pp 1 (mod8),81,ppm 若若即即有有于于是是信息安全理论及应用信息安全理论及应用22(81)18282 ( 1)( 1)1mmmp 3 (mod8),83,ppm 若若即即有有于于是是22(83)1(86) 182 ( 1)( 1)1mmmp 1122 ( 1)pqpqqppq () ()

44、若若 及及定定理理是是互互素素的的奇奇素素数数二二律律4 4次次, ,则则互互反反信息安全理论及应用信息安全理论及应用717 213是是模模的的平平方方剩剩余余，是是模模的的平平方方例例2 2 非非剩剩余余. .21713682 ( 1)( 1)117 解解 因因217所所以以, , 是是模模的的平平方方剩剩余余. .17 1 3 122317( 1)173 3 12( 1) 173 13 1 317所所以以, , 是是模模的的平平方方非非剩剩余余. .信息安全理论及应用信息安全理论及应用2 1 (mod 365) x 判判断断同同余余式式是是否否有有解解, ,有有解解时时, , 求求出出例例

45、4 4 其其解解数数. .221 (mod 5) 1 (mod 73)xx 解解 3 36 65 5= =5 57 73 3, ,原原同同余余式式等等价价于于同同余余式式组组5 121( 1)1, 5 因因4.故故同同余余式式组组有有解解, , 因因而而原原同同余余式式有有解解, ,解解数数为为73 121 ( 1)173 信息安全理论及应用信息安全理论及应用Jacobi 符号符号信息安全理论及应用信息安全理论及应用3.3 Jacobi 符号符号信息安全理论及应用信息安全理论及应用3.3 Jacobi 符号符号信息安全理论及应用信息安全理论及应用3.3 Jacobi 符号符号信息安全理论及应用

46、信息安全理论及应用3.3 Jacobi 符号符号 Jacobi 符号与Legendre 符号的关系：信息安全理论及应用信息安全理论及应用定理定理 已知已知n为两个素数乘积为两个素数乘积, a是模是模n的平方剩余，则的平方剩余，则求解方程求解方程x2a mod n与分解与分解n是等价的。是等价的。(1)已知已知n的分解的分解n=pq，且且a是模是模n的平方剩余，的平方剩余，就可求得就可求得a mod n的的4个平方根个平方根由中国剩余定理可求得由中国剩余定理可求得a mod n的的4个平方根，记为个平方根，记为u mod n和和w mod n，且且u w mod n。 qzxpyxmodmod

47、qzxpyxmodmod qzxpyxmodmod qzxpyxmodmodnaxmod2 qaxpaxmodmod22 qzxpyxmodmod信息安全理论及应用信息安全理论及应用(2) 已知已知a mod n的两个不同的平方根（的两个不同的平方根（u mod n和和w mod n，且且u w mod n），），就可分解就可分解n。由由u2w2 mod n,得得(u+w)(u-w)0 mod n，但但n不能整不能整除除u+w也不能整除也不能整除u-w，所以必有所以必有p|(u+w), q|(u-w)或或 p|(u-w), q|(u+w)所以所以 gcd(n, u+w)=p, gcd(n, u

48、-w)=q或或gcd(n, u-w)=p, gcd(n, u+w)=q因此得到了因此得到了n的分解式。的分解式。信息安全理论及应用信息安全理论及应用1. 费尔玛定理和欧拉定理费尔玛定理和欧拉定理2. 素性检验素性检验: Miller-Rabin的素性概率检测法的素性概率检测法3. 广义欧几里得除法广义欧几里得除法4. 中国剩余定理中国剩余定理离散对数离散对数求解求解x2a mod n与分解与分解n等价等价数论知识总结数论知识总结信息安全理论及应用信息安全理论及应用4.3 RSA密码算法密码算法 MIT三位年青学者三位年青学者Rivest，Shamir和和Adleman 在在1978年发现了一种

49、用数论构造双钥体制的方法，年发现了一种用数论构造双钥体制的方法，称作称作MIT体制，后来被广泛称之为体制，后来被广泛称之为RSA体制。体制。 它既可用于加密、又可用于数字签名。它既可用于加密、又可用于数字签名。 RSARSA算法的安全性基于数论中大整数分解的困难算法的安全性基于数论中大整数分解的困难性性。信息安全理论及应用信息安全理论及应用4.3.1 算法描述算法描述-密钥生成密钥生成 选取两互异大素数选取两互异大素数p p和和q q 计算计算 n n=p pq q 和其欧拉函数值和其欧拉函数值 ( (n n)=()=(p p1)(1)(q q1) 1) 选一整数选一整数e e，1 1 e e

50、 ( (n n) )，使得，使得 gcd(gcd( ( (n n), ), e e)=1)=1 在模在模 ( (n n) )下，计算下，计算e e的逆元的逆元d d. . 即求即求d, d, 使得使得 e ed d 1 1 mod mod ( (n n) ) 以以( (n n，e e ) )为公钥。为公钥。d d 为秘密钥。为秘密钥。 ( (p p, , q q不再需要，可以销毁。不再需要，可以销毁。) ) 信息安全理论及应用信息安全理论及应用 加密 将明文分组，各组对应的十进制数mn, 计算 c =E(m) me mod n 解密 m = D(c) cd mod n信息安全理论及应用信息安全

51、理论及应用RSA算法算法解密过程的正确性解密过程的正确性。证明：证明： 由加密过程知由加密过程知cme mod n，所以所以cd mod nmed mod n mk(n)+1 mod n分两种情况：分两种情况： m与与n互素互素，则由，则由Euler定理得定理得m(n)1 mod n,mk(n)1 mod n,mk(n)+1m mod n即即cd mod nm。加密：加密： cme mod n解密：解密：mcd mod n信息安全理论及应用信息安全理论及应用由由gcd(m,q)=1及及Euler定理得定理得m(q)1 mod q，所以所以mk(q)1 mod q,mk(q)(p)1 mod q

52、, mk(n)1 mod q因此存在一整数因此存在一整数r，使得使得mk(n)=1+rq，两边同乘以两边同乘以m=cp得得mk(n)+1=m+rcpq=m+rcn即即mk(n)+1m mod n，所以所以cd mod nm。(证毕证毕)qcnm 1 ,1 gcd(m,n)1, 不妨设不妨设 m=cp，信息安全理论及应用信息安全理论及应用例例: 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。因

53、此公钥为因此公钥为5, 119，私钥为，私钥为77, 119。设明文设明文m=19，则由加密过程得密文为则由加密过程得密文为c195 mod 1192476099 mod 11966解密为解密为6677mod 11919信息安全理论及应用信息安全理论及应用1. RSA的加密与解密过程的加密与解密过程 RSA的加密、解密过程都为求一个的加密、解密过程都为求一个整数的整数次整数的整数次幂幂，再取模再取模。如果按其含义直接计算，则中间结果。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。非常大，有可能超出计算机所允许的整数取值范围。而用模运算的性质：而用模运算的性质：(

54、ab) mod n=(a mod n)(b mod n) mod n就可减小中间结果。就可减小中间结果。4.3.2 RSA算法中的计算问题算法中的计算问题信息安全理论及应用信息安全理论及应用 再者，考虑如何提高加、解密运算中指数运算的再者，考虑如何提高加、解密运算中指数运算的有效性。例如求有效性。例如求x16，直接计算的话需做直接计算的话需做15次乘法。次乘法。然而如果重复对每个部分结果做平方运算即求然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需则只需4次乘法。次乘法。求求am可如下进行，其中可如下进行，其中a，m是正整数：是正整数： 将将m表示为二进制形式表示为二

55、进制形式bk bk-1b0，即即因此因此12012222kkkbbbbbmaaaaaa 信息安全理论及应用信息安全理论及应用d=1；For i=k downto 0 do d=(dd) mod n;if bi=1 then d=(da) mod nreturn d.m=bk2k+bk-12k-1+b12+b012012222kkkbbbbbmaaaaaa 快速指数算法快速指数算法信息安全理论及应用信息安全理论及应用2. RSA密钥的产生密钥的产生两个大素数两个大素数p、q的选取。的选取。 Miller-Rabin算法算法;(2) e的选取和的选取和d的计算。的计算。 选取满足选取满足1eq，由

56、由(n)=(p-1)(q-1)，则有则有p+q=n-(n)+1以及以及得：得：由此可见，由此可见，不对不对n进行因式分解而直接计算进行因式分解而直接计算(n)并不比对并不比对n进行因式分解更容易。进行因式分解更容易。224( )14pqpqnnnn1212ppqpqqpqpq信息安全理论及应用信息安全理论及应用为保证算法的安全性，还对为保证算法的安全性，还对p和和q提出以下要求：提出以下要求： （1） |p-q|要大。要大。（2）p和和q的长度应该相差不多。的长度应该相差不多。（3） p-1和和q-1都应有大素因子。都应有大素因子。（4） gcd(p-1, q-1)应该很小。应该很小。信息安全

57、理论及应用信息安全理论及应用1. 共模攻击共模攻击 在实现在实现RSA时，为方便起见，可能给每一用户相时，为方便起见，可能给每一用户相同的模数同的模数n，虽然加解密密钥不同，然而这样做是虽然加解密密钥不同，然而这样做是不行的。不行的。4.3.4 对对RSA的攻击的攻击信息安全理论及应用信息安全理论及应用设两个用户的公开钥分别为设两个用户的公开钥分别为e1和和e2，且且e1和和e2互素，互素，明文消息是明文消息是m，密文分别是密文分别是敌手截获敌手截获c1和和c2后，可如下恢复后，可如下恢复m。用推广的用推广的Euclid算法求出满足算法求出满足re1+se2=1的两个整数的两个整数r和和s，其

58、中一个为负，设为其中一个为负，设为r。再次用再次用推广的推广的Euclid算法求出算法求出 ，由此得由此得11 cnmccccsrsrmod)(21121 nmcnmceemodmod2121 信息安全理论及应用信息安全理论及应用2. 低指数攻击低指数攻击 将将RSA同时用于多个用户，然而每个用户的同时用于多个用户，然而每个用户的加密加密指数指数都很小。设都很小。设3个用户的模数分别为个用户的模数分别为ni(i=1,2,3)，当当ij时，时，gcd(ni, nj)=1，否则通过否则通过gcd(ni, nj)有可能有可能得出得出ni 和和nj 的分解。设明文消息是的分解。设明文消息是m，密文分别

59、是密文分别是c1m3(mod n1)c2m3(mod n2)c3m3(mod n3)由中国剩余定理可求出由中国剩余定理可求出m3(mod n1 n2 n3 )。由于由于m3 n1 n2 n3 ，可直接由可直接由m3开立方根得到开立方根得到m。信息安全理论及应用信息安全理论及应用RSA是是确定性的加密算法确定性的加密算法, 不能抵御不能抵御选择密文攻击选择密文攻击。3. 选择密文攻击选择密文攻击假设攻击者得到了假设攻击者得到了RSA公钥公钥(n,e)，截获到某个密文，截获到某个密文c1，假设其明文为，假设其明文为m1,即即 11modecmn然后，攻击者选取明文然后，攻击者选取明文m，构造新密文

60、，构造新密文c2：21modeccmn攻击者让解密者对攻击者让解密者对c2解密，获得明文解密，获得明文m2，则计算，则计算 ：21modmmnm信息安全理论及应用信息安全理论及应用 鹗鸟（鹗鸟（ossifrage），又名髭兀鹰（），又名髭兀鹰（lammergeier），是阿），是阿尔卑斯山上一种稀有的肉食秃鹰。它的翅膀展开将近十米尔卑斯山上一种稀有的肉食秃鹰。它的翅膀展开将近十米宽。鸟名的字面含义是宽。鸟名的字面含义是“碎骨碎骨”。顾名思义，其习性令人。顾名思义，其习性令人毛骨悚然。毛骨悚然。 Mirtin Gardner在在1977年年“Scientific American”的专栏文的专栏