第7讲 公钥密码体制

1、韦宝典 副教授 中山大学电子系第第7讲：公钥密码体制讲：公钥密码体制一：公钥密码原理一：公钥密码原理二：二：RSA密码体制密码体制三：三：Rabin密码体制密码体制四：离散对数四：离散对数五：五：ElGamalElGamal密码体制密码体制 六：六：DiffieDiffie- -HellmanHellman密钥协商密钥协商 七：公钥密码总结七：公钥密码总结一、一、公钥密码原理公钥密码原理双双(公公)钥密码体制钥密码体制1976年年W. Diffie和和M. Hellman; R. Merkle1978可用于可用于保密通信保密通信，也可用于也可用于数字签字数字签字密码学史上密码学史上划时代划时代

2、的事件的事件为解决计算机信息网中的安全为解决计算机信息网中的安全提供了新的理论和技术基础提供了新的理论和技术基础加密变换加密变换(公钥公钥)公开公开解密变换解密变换(私钥私钥)保密保密一、一、公钥密码原理公钥密码原理公钥密码方案公钥密码方案RSA scheme (78) : R.L.Rivest, A.Shamir, L.Adleman, “A Method for Obtaining Digital Signatures and Public Key Cryptosystems”,CACM, Vol.21, No.2, pp.120-126,Feb,1978McEliece scheme (

3、78)Rabin scheme (79)Knapsack scheme (79-): Merkle-Hellman, Chor-RivestWilliams scheme (80)ElGamal scheme (85)Elliptic Curve based scheme(85): Koblitz, MillerHidden Field Equations(95): C*,PatarinLattice Cryptography(97-): Ajtai (AD, DDH, NTRU)Nonabeliangroup Cryptography(2000): Braid一、一、公钥密码原理公钥密码原理

4、二、二、RSA密码体制密码体制1978年年 MIT三位年青数学家三位年青数学家R.L.Rivest，A.Shamir和和L.Adleman用数论构造双钥密码的方法，称作用数论构造双钥密码的方法，称作MIT体制，后被广泛称为体制，后被广泛称为RSA体制体制它既可用于它既可用于加密加密、又可用于数字、又可用于数字签名签名易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制国际上一些国际上一些标准化组织标准化组织ISO、ITU、及及SWIFT等均已接受等均已接受RSA体制作为标准体制作为标准Internet采用的采用的PGP(Prett

5、y Good Privacy)也将也将RSA作为作为 传送会话密钥传送会话密钥和和数字签名数字签名的标准算法的标准算法RSA算法的安全性基于算法的安全性基于数论中大整数分解数论中大整数分解的困难性的困难性参数选择：参数选择： 独立地选取两大独立地选取两大素数素数p1和和p2(各各512bit的数的数)， 计算计算 n=p1p2 其欧拉函数值其欧拉函数值 (n)=(p11)(p21) 随机选一整数随机选一整数e， 1 e (n)，( (n), e)=1(因而在模因而在模 (n)下下e有逆元有逆元) d=e-1 mod (n) 公钥公钥为为n，e; 私钥私钥为为d (p1, p2不再需要，可以销毁

6、不再需要，可以销毁)二、二、RSA密码体制密码体制加密、解密：加密、解密： 将明文分组，各组长将明文分组，各组长1024比特比特 明文集明文集 Az=x：1 xn, (x, n)=1 注意，注意，(x, n) 1是很危险的是很危险的 x Az的概率：的概率： 加加 密密 y=xe mod n 解解 密密 x=yd mod n 证明：证明： yd=(xe)d=xde， 因为de1 mod (n) 即de=q(n)1 由欧拉定理，(x, n)=1意味x(n)1 mod n， 故有yd=xde=xq(n)+1xxq(n)=x1=x mod n 陷门函数陷门函数：Z=(p1, p2, d)11111)

7、1)(1()(21212121 ppppppppnn 二、二、RSA密码体制密码体制例例 子：子：p1=47，p2=71，n=4771=3337， (n)=4670=3220e=79，d=e-1 (mod 3220)=1019公开公开n=3337和和e=79 保密私钥保密私钥d=1019 销毁销毁p1, p2 令令 x=688 232 687 966 668 3，分组分组x1=688，x2=232，x3=687，x4=966，x5=668，x6=3x1的加密为的加密为(688)79 (mod 3337)=1570=C1，类似计算出其他各组密文，类似计算出其他各组密文，y=1570 2756 2

8、091 2276 2423 158第一组密文解密为第一组密文解密为(1570)1 019 mod 3337=688=x类似解出其他各组密文类似解出其他各组密文二、二、RSA密码体制密码体制RSA加密实质加密实质上是一种上是一种Zn*Zn*上的上的单表代换单表代换！ 给定给定n=p1p2和合法明文和合法明文x Zn*，密文密文y=xe mod n Zn* 对于对于x x，必有必有y y Zn*中的元素是一个明文，也是与某个明文相对应的中的元素是一个明文，也是与某个明文相对应的一个密文一个密文 因此，因此，RSA是是ZnZn的一种单表代换密码的一种单表代换密码 关键关键在于：在于：n极大时，若不知

9、陷门信息，极大时，若不知陷门信息， 则极难确定这种对应关系则极难确定这种对应关系 由于这种一一对应性，由于这种一一对应性， RSA不仅可以用于加密也可用于数字签名不仅可以用于加密也可用于数字签名二、二、RSA密码体制密码体制安全性安全性:分解模数分解模数n 理论上，理论上，RSA的安全性取决于的安全性取决于模模n分解的困难性分解的困难性， 但数学上至今还未证明分解模就是攻击但数学上至今还未证明分解模就是攻击RSA的最佳方法，的最佳方法， 也未证明分解大整数就是也未证明分解大整数就是NP问题，问题， 可能有尚未发现的多项式时间分解算法。可能有尚未发现的多项式时间分解算法。 人们完全可以设想有另外

10、的途径破译人们完全可以设想有另外的途径破译RSA， 如求出解密指数如求出解密指数d或找到或找到(p11)(p21)等。等。 但这些途径都不比分解但这些途径都不比分解n来得容易。来得容易。 甚至甚至Alexi等等1988曾揭示，从曾揭示，从RSA加密的密文恢复某些比特的困难性也和加密的密文恢复某些比特的困难性也和恢复整组明文一样困难。恢复整组明文一样困难。 这一视在困难性问题是个这一视在困难性问题是个NP问题，但还没人证明它为问题，但还没人证明它为NPC问题。问题。二、二、RSA密码体制密码体制采用广义数域筛分解不同长度采用广义数域筛分解不同长度RSA公钥模所需的计算机资源公钥模所需的计算机资源

11、二、二、RSA密码体制密码体制 密钥长密钥长(bit) 所需的所需的MIPS-年年* 116 400 129 5,000 512 30,000 768 200,000,000 1024 300,000,000,000 2048 300,000,000,000,000,000,000 * MIPS-年指以每秒执行年指以每秒执行1,000,000条指令的计算机运行一年条指令的计算机运行一年 安全性安全性:分解模数分解模数n技术进展使分解算法和计算能力在不断提高，计算所需的硬件费用在不断下降技术进展使分解算法和计算能力在不断提高，计算所需的硬件费用在不断下降 RSA-129： 110位十进制数字早已

12、能分解。位十进制数字早已能分解。 Rivest等最初悬赏等最初悬赏$100的的RSA-129，已经已经 由包括五大洲由包括五大洲43个国家个国家600多人参加，用多人参加，用1600台机子同时产生台机子同时产生820条指令数据，条指令数据， 通过通过Internet网，耗时网，耗时8个月，于个月，于1994年年4月月2日日 利用二次筛法分解出为利用二次筛法分解出为64位和位和65位的两个因子，位的两个因子， 所给密文的译文为所给密文的译文为“这些魔文是容易受惊的鱼鹰这些魔文是容易受惊的鱼鹰”。 这是有史以来最大规模的数学运算。这是有史以来最大规模的数学运算。 原来估计要用原来估计要用4亿亿年。

13、亿亿年。RSA-130于于1996年年4月月10日日利用利用数域筛法数域筛法分解出来。分解出来。RSA-140于于1999年年2月月分解出来。分解出来。 RSA-154(512bit)于于1999年年8月月分解出来。分解出来。 RSA-160, 2003.01 (http:/www.loria.fr/zimmerma/records/rsa160) RSA-174(576bit), 2003. 12二、二、RSA密码体制密码体制安全性安全性:分解模数分解模数n从从n若能求出若能求出 (n)，则可求得则可求得p1, p2。 n (n)1=p1p2(p11)(p21)1=p1p2 (p1+p2)2

14、-4n)1/2=p1-p2 但已证明：但已证明：求求 (n)等价于分解等价于分解n的困难的困难从从n求求d亦等价于分解亦等价于分解n目前尚目前尚不知不知是否存在一种是否存在一种无需籍助于分解无需籍助于分解n的攻击法的攻击法也也未能证明未能证明破译破译RSA的任何方法都的任何方法都等价于大整数分解问题等价于大整数分解问题二、二、RSA密码体制密码体制安全性安全性:其它途径其它途径Simmons和和Norris提出提出迭代迭代/循环攻击法循环攻击法： 给定一给定一RSA的参数为的参数为(n, e, y)=(35, 17, 3)， 由由y0=y=3计算计算y1=317=33 mod 35 再由再由y

15、1计算计算y2=y117=3 mod 35 从而得到明文从而得到明文x=y1=33 mod 35。 一般一般对明文对明文x加密多次，直到再现加密多次，直到再现x为止为止。Rivest证明：当证明：当p11和和p21中含有中含有大素数因子大素数因子， 且且n足够大时，这种攻击法成功的概率趋于足够大时，这种攻击法成功的概率趋于0。二、二、RSA密码体制密码体制安全性安全性:迭代攻击法迭代攻击法消息破译消息破译 0）收集用户）收集用户A以公钥以公钥e加密的密文加密的密文y = xe mod n，目标分析出消息目标分析出消息x1）选随机数）选随机数rn，计算计算y1 = re mod n，这意味这意味

16、r = y1d mod n2）计算）计算y2 = y1y mod n3）令）令t = r-1 mod n = y1-d mod n4）请）请A对消息对消息y2进行签字进行签字(用私钥，但不能用用私钥，但不能用Hash函数函数) 得到得到s = y2d mod n5）攻击者计算）攻击者计算t s mod n = y1-dy2d mod n = y1-d(y1dyd) mod n = yd mod n = x 得到了明文。得到了明文。二、二、RSA密码体制密码体制安全性安全性:选择明文攻击选择明文攻击消息破译消息破译 y = xe mod n，目标分析出消息目标分析出消息x = yd mod n

17、= yd y1d y1-d mod n = (y y1)d y1-d mod n = (y re)d (re)-d mod n = y2d r-1 mod n = y2d t mod n y1 = re mod n y2 = y y1 = yre mod n t = r-1 mod n二、二、RSA密码体制密码体制安全性安全性:选择明文攻击选择明文攻击多人共用同一模数多人共用同一模数n，各自选择不同各自选择不同e和和d，实现简单但不安全实现简单但不安全若消息以两个互素若消息以两个互素(一般如此一般如此)的密钥加密，在共用同一个模下，的密钥加密，在共用同一个模下，则可用任一密钥恢复明文则可用任一

18、密钥恢复明文e1和和e2是两个互素的不同密钥，共用模为是两个互素的不同密钥，共用模为n，对同一消息对同一消息x加密得加密得 y1 = xe1 mod n, y2 = xe2 mod n 分析者知道分析者知道n, e1, e2, y1和和y2 因为因为(e1, e2,)=1，所以由所以由Euclidean算法有算法有r e1+s e2=1 计算计算 (y1-1)-r y2s = x mod n (假设假设r是负数是负数)二、二、RSA密码体制密码体制安全性安全性:公用模攻击公用模攻击小的小的e可可加快加密和验证签字速度加快加密和验证签字速度，且所需的，且所需的存储密钥空间小存储密钥空间小但但若加

19、密钥若加密钥e选择得太小，则容易受到攻击选择得太小，则容易受到攻击网中三用户的加密钥网中三用户的加密钥e均选均选3，分别模，分别模n1, n2, n3 (互素，否则可求出公因子，而降低安全性互素，否则可求出公因子，而降低安全性) 一用户将消息一用户将消息x传给三个用户的密文分别为传给三个用户的密文分别为 y1=x3 mod n1 x n1 利用中国余定理，利用中国余定理， y2=x3 mod n2 x n2 可从可从y1, y2, y3求出求出 y3=x3 mod n3 x n3 y=x3 mod (n1 n2 n3)由由xn1, xn2, xn3，可得可得x3e(e+1)/2， 采用低指数亦

20、可有效攻击采用低指数亦可有效攻击为抗击这种攻击为抗击这种攻击e必须选得足够大必须选得足够大 e选为选为16位素数，既可兼顾快速加密，又可防止这类攻击位素数，既可兼顾快速加密，又可防止这类攻击二、二、RSA密码体制密码体制安全性安全性:低加密指数攻击低加密指数攻击 在在x后加时戳后加时戳 y1=(2t x+t1)3 mod n1 y2=(2t x+t2)3 mod n2 y3=(2t x+t3)3 mod n3 t是是t1, t2, t3的二元表示位数的二元表示位数 可防止这类攻击可防止这类攻击对短的消息，可用对短的消息，可用随机数字填充随机数字填充以防止低加密指数攻击以防止低加密指数攻击d小也

21、不行小也不行：对：对en，dn1/4，也可以攻破这类也可以攻破这类RSA体制体制二、二、RSA密码体制密码体制安全性安全性:低加密指数攻击低加密指数攻击构造构造y=xe mod n，猜测猜测d值，做值，做yd mod n，直到试凑出直到试凑出yd x mod n Wiener给出对小给出对小d的系统攻击法，证明了当的系统攻击法，证明了当d长度小于长度小于n的的1/4时，时， 由由连分式连分式算法，可在多项式时间内求出算法，可在多项式时间内求出d值值利用利用测定测定RSA解密解密所进行的模指数运算的所进行的模指数运算的时间时间来估计解密指数来估计解密指数d，而后再精确定出而后再精确定出d的取值。

22、的取值。可通过将解密运算量与参数可通过将解密运算量与参数d无关化无关化来挫败此攻击来挫败此攻击(R. Rivest)还可采用还可采用盲化盲化技术：将数据盲化后再密，而后做去盲运算技术：将数据盲化后再密，而后做去盲运算 这样做虽然不能使解密运算时间保持不变，但这样做虽然不能使解密运算时间保持不变，但 计算时间被随机化而难于推测解密进行的指数运算的时间计算时间被随机化而难于推测解密进行的指数运算的时间 二、二、RSA密码体制密码体制安全性安全性:定时攻击法定时攻击法(Timing: P. Kocher)对明文对明文x，0 x n1，采用采用RSA体制加密，体制加密，可能出现可能出现xe=x mod

23、 n，致使消息暴露致使消息暴露这是明文在这是明文在RSA加密下的加密下的不动点不动点总有一些不动点，如总有一些不动点，如x=0，1和和n1一般有一般有1+gcd(e1, p1) 1+gcd(e1, q1)个不动点个不动点由于由于e1，p1和和q1都是偶数都是偶数所以不动点至少为所以不动点至少为9个个一般来说，不动点个数相当一般来说，不动点个数相当少少而可忽略而可忽略二、二、RSA密码体制密码体制安全性安全性:消息隐匿问题消息隐匿问题D. Boneh. Twenty Years of Attacks on the RSA Cryptosystem. Notices of the American

24、 Mathematical Society, 46(2):203-213, 1999./dabo/abstracts/RSAattack-survey.html二、二、RSA密码体制密码体制安全性安全性(1) n =pq的确定：的确定： p与与q必须为强素数必须为强素数强素数强素数p的条件的条件： (a)存在两个大素数存在两个大素数p1和和p2，p1|(p1)，p2|(p1) (b)存在存在4个大素数个大素数r1, s1, r2及及s2，使使r1|(p11), r2|(p21), s1|(p11), s2|(p21)。p1和和p2为二级素数；为

25、二级素数； r1, r2, s1和和s2为三级素数为三级素数二、二、RSA密码体制密码体制RSA参数的选择参数的选择采用强素数的采用强素数的理由理由如下：如下： 若若 ，pi为素数，为素数，ai为正整数为正整数 分解式中分解式中piB，B为已知一个小整数为已知一个小整数 则则存在一种存在一种p1的分解法，使我们易于分解的分解法，使我们易于分解n 令令n=pq，且且p1满足上述条件，满足上述条件，piB 令令a ai，i=1, 2, , t 可构造可构造 显然显然(p1) R，由费尔马定理由费尔马定理2R 1 mod p 令令2R=x mod n，若若x =1则选则选3代代2，直到出现，直到出现

26、x 1 此时，此时，kR = 1 mod p 有解的充要条件是有解的充要条件是 kR = x mod n (p, n)=p | x-1 由由GCD(x1, n)=p，就得到就得到n的分解因子的分解因子p和和q二、二、RSA密码体制密码体制RSA参数的选择参数的选择iaitipp11aitipR1p与与q之差要大之差要大 若若p与与q之差很小，则可由之差很小，则可由n=pq估计估计(pq)/2 =n1/2， 由由(pq)/2)2n=(pq)/2)2，等式右边为小的平方数，等式右边为小的平方数， 可以试验给出可以试验给出p, q的值的值 例：例：n = 164009，估计估计(pq)/2 405，

27、 由由4052n=16=42，可得可得 (pq)/2=405，(pq)/2=4， p=409，q=401二、二、RSA密码体制密码体制RSA参数的选择参数的选择p1与与q1的最大公因子要小的最大公因子要小惟密文攻击下，设破译者截获密文惟密文攻击下，设破译者截获密文y=x e mod n破译者做下述递推计算：破译者做下述递推计算： xi=xi-1e mod n=(xe)i mod n 若若ei=1 mod (n)，则有则有xi=x mod n，且且ei+1=e mod (n)，即即xi+1=x 若若i小，则由此攻击法易得明文小，则由此攻击法易得明文x。 由由Euler定理知，定理知，i= (p1

28、)(q1)， 若若p1和和q1的最大公因子小，则的最大公因子小，则i值大，值大， 如如i=(p1)(q1)/2，此攻击法难于奏效。此攻击法难于奏效。二、二、RSA密码体制密码体制RSA参数的选择参数的选择p，q要足够大，以使要足够大，以使n分解在计算上不可行分解在计算上不可行二、二、RSA密码体制密码体制RSA参数的选择参数的选择e的选取原则的选取原则(e, (n)=1条件易于满足，因为两个随机数互素的概率约为条件易于满足，因为两个随机数互素的概率约为3/5e不可过小不可过小：若：若e小，小，x小，小，y=xe mod n，当当xen，则未取模，则未取模， 由由y直接开直接开e次方可求次方可求

29、x，易遭低指数攻击易遭低指数攻击 e小时，加密速度快，小时，加密速度快，Knuth和和Shamir曾建议采用曾建议采用e=3 但但e太小存在一些问题太小存在一些问题 选选e在在mod (n)中的阶数中的阶数i(ei 1 mod (n)达到达到(p1)(q1)/2二、二、RSA密码体制密码体制RSA参数的选择参数的选择p，q要足够大，以使要足够大，以使n分解在计算上不可行分解在计算上不可行d的选择的选择 e选定后可用选定后可用Euclidean算法在多项式时间内求出算法在多项式时间内求出dd小，签字和解密快，在小，签字和解密快，在IC卡中尤为重要卡中尤为重要(复杂的加密和验证签字可由主机来做复杂

30、的加密和验证签字可由主机来做)d要大于要大于n1/4：类似于加密下的情况，：类似于加密下的情况，d不能太小不能太小 否则由已知明文攻击，构造否则由已知明文攻击，构造y=xe mod n，猜测猜测d的的值：值：做做yd mod n，直到试凑出直到试凑出yd x mod n Wiener给出对小给出对小d的系统攻击法，的系统攻击法，证明了当证明了当d长度小于长度小于n的的1/4时，时， 由由连分式连分式算法，可在多项式时间内求出算法，可在多项式时间内求出d值值二、二、RSA密码体制密码体制RSA参数的选择参数的选择不可用公共模不可用公共模 由一密钥产生中心由一密钥产生中心(KGC)采用一公共模，分

31、发多对密钥，公布相应公钥采用一公共模，分发多对密钥，公布相应公钥ei 这当然使密钥管理简化，存储空间小，且无重新分组问题这当然使密钥管理简化，存储空间小，且无重新分组问题 但如前所述，它在安全上会带来问题。但如前所述，它在安全上会带来问题。明文熵要尽可能地大明文熵要尽可能地大 明文熵要尽可能地大，以使在已知密文下，明文熵要尽可能地大，以使在已知密文下， 要猜测明文无异于完全随机等概情况。要猜测明文无异于完全随机等概情况。用于用于签字时签字时，要采用，要采用Hash函数函数 二、二、RSA密码体制密码体制RSA体制实用中的其它问题体制实用中的其它问题 Set-up of the Rabin Sy

32、stem Choose two distinct primes p, q s.t. and put n=pq. Encryption function 4mod3 qpnnZZnxxe:mod)(2三、三、Rabin密码体制密码体制Encryption algorithm: )(mod2nmcmDecryption algorithm: step 1: Find a, b s.t. ap+bq=1 using the Euclidean algorithm. step 2: put step 3: Compute qcspcrqpmod,mod4/ )1(4/ )1(nbqrapsnbqrap

33、smod)(,mod)(三、三、Rabin密码体制密码体制Claim: ,are four roots of ncxmod2and m is one of these four.Chose one which makes sense!Theorem. Let n=pq be the product of two distinct odd primes p, q. (i)If , then has no solutions or exactly four solutions(ii)Let r, s be a solution of , respectively, then the four so

34、lutions of are (aps+bqr); -(aps+bqr); (aps-bqr); -(aps-bqr), where a, b satisfy ap+bq=1.(iii) If , then is a solution of 4mod3ppcpmod4/ )1( ncxmod2pcxmod2qcxmod2pcxmod2*nZc三、三、Rabin密码体制密码体制 c=x2 mod p cp-1=1 mod p c(p-1)/2=xp-1=1 mod pc=x2 mod n c=x2 mod q cq-1=1 mod q c(q-1)/2=xq-1=1 mod qc(p-1)/2c

35、=x2 mod p x=c(p+1)/4 mod p CRT:c(q-1)/2c=x2 mod q x=c(q+1)/4 mod q x =c(p+1)/4 bq c(q+1)/4 ap mod nncxmod2Theorem : Solving for all is equivalent to factoring n.nZc Cryptanalysis 三、三、Rabin密码体制密码体制四、离散对数四、离散对数The discrete logarithm problem applies to mathematical structures called groups. Given an el

36、ement g in a finite group G and another element h in G, find an integer x such that gx = h. Like the factoring problem, the discrete logarithm problem is believed to be difficult and also to be the hard direction of a one-way function. For this reason, it has been the basis of several public-key cry

37、ptosystems, including the ElGamal system and DSS. The discrete logarithm problem bears the same relation to these systems as factoring does to the RSA system: the security of these systems rests on the assumption that discrete logarithms are difficult to compute. The discrete logarithm problem has r

38、eceived much attention in recent years; descriptions of some of the most efficient algorithms for discrete logarithms over finite fields can be found. The best discrete logarithm algorithms have expected running times similar to those of the best factoring algorithms. Rivest has analyzed the expecte

39、d time to solve the discrete logarithm problem both in terms of computing power and cost. In general, the discrete logarithm in an arbitrary group of size n can be computed in running time O(n1/2), though in many groups it can be done faster. 四、离散对数四、离散对数四、离散对数四、离散对数ElGamal1984,1985提出、基于提出、基于离散对数问题离

40、散对数问题的双钥密码体制的双钥密码体制既可用于既可用于加密加密，又可用于，又可用于签字签字(1) 方案：方案： Zp 是一个有是一个有p个元素的有限域，个元素的有限域，p是一个素数，是一个素数， g是是Zp的一个生成元的一个生成元 明文集明文集MM为为Zp，密文集密文集C C为为ZpZp。 公钥：公钥： y g x mod p 秘密钥：秘密钥：x p(2) 加密：选择随机数加密：选择随机数k Zp-1，且且(k,p1)=1， 对明文组对明文组M计算：计算： c1=g k mod p (随机数随机数k被加密被加密)c2=My k mod p (明文被随机数明文被随机数k和公钥和公钥 加密加密)

41、密文由密文由y1、y2级连构成，即密文级连构成，即密文C=c1|c2。 (3)解密：收到密文组解密：收到密文组C后，计算后，计算c2=My k=M(gx)k=M(gk)x =M(c1)xM=c2/c1x=My k/gkx=Mgxk/gk mod p五、五、 ElGamalElGamal密码体制密码体制c1=g k c2=My k = M (gx) k = M (gk)x = M (c1)xM=c2/c1x=My k/gkx=Mgxk/gkx mod p特点：密文由明文和所选随机数特点：密文由明文和所选随机数k来定，来定， 因而是因而是非确定性非确定性加密，一般称之为加密，一般称之为随机化加密随

42、机化加密， 对同一明文不同时刻的随机数对同一明文不同时刻的随机数k不同会给出不同的密文不同会给出不同的密文 代价是代价是数据扩展一倍数据扩展一倍例例 p=2579，g=2，x=765，y=g765 mod 2579=949 明文为明文为M=1 299，选随机数选随机数k=853 c1 2853 mod 2 579=435 c2 1 299949853 mod 2579=2 396 密文密文C=(435,2 396) 解密：解密：C算出消息组算出消息组M 2 396/(435)765 mod 2 579= 1 299。安全性：本体制基于安全性：本体制基于Zp中有限群上的中有限群上的离散对数的困难

43、性离散对数的困难性。五、 ElGamal密码体制 算法算法 双方选择素数双方选择素数p以及以及p的一个本原根的一个本原根g 用户用户A选择一个随机数选择一个随机数Xa p，计算计算 Ya=gXa mod p 用户用户B选择一个随机数选择一个随机数Xb p，计算计算 Yb=gXb mod p 每一方保密每一方保密X值，而将值，而将Y值交换给对方值交换给对方 用户用户A计算出计算出 K=YbXa mod p 用户用户B计算出计算出 K=YgXb mod p 双方获得一个共享密钥双方获得一个共享密钥(gXaXbmod p) 素数素数p以及以及p的本原根的本原根g可由一方选择后发给对方可由一方选择后发

44、给对方六、六、Diffie-Hellman密钥交换密钥交换 Generate randomXa pCalculateYa=gXa mod pGenerate randomXb pCalculateYb=gXb mod pUser AUser BYaYbCalculateK=(Yb)Xa mod pCalculateK=(Ya)Xb mod pDiffie-Hellman Key Exchange六、六、Diffie-Hellman密钥交换密钥交换 Diffie-Hellman密钥交换的攻击密钥交换的攻击 replay攻击攻击中间人攻击图示中间人攻击图示ABK = gXaXbOABK = gXa

45、XoOK = gXbXo六、六、Diffie-Hellman密钥交换密钥交换 中间人攻击中间人攻击1 双方选择素数双方选择素数p以及以及p的一个原根的一个原根g(假定假定O知道知道)2 A选择选择Xap,计算计算Ya=gXa mod p, AB: Ya3 O截获截获Ya,选选Xo,计算计算Yo=gXo mod p,冒充冒充AB:Yo4 B选择选择Xbp,计算计算Yb=gXb mod p, BA: Yb5 O截获截获Yb,冒充冒充BA:Yo6 A计算计算: (Yo)Xa (gXo)Xa gXoXa mod p7 B计算计算: (Yo)Xb (gXo)Xb gXoXb mod p8 O计算计算:

46、(Ya)Xo gXaXo mod p, (Yb)Xo gXbXo mod pO无法计算出无法计算出gXaXb mod p 虽然不需要计算出这个数，虽然不需要计算出这个数，但但O必须实时截获每一数值，并冒充转发必须实时截获每一数值，并冒充转发,否则会被发现否则会被发现Diffie-Hellman密钥交换的攻击密钥交换的攻击六、六、Diffie-Hellman密钥交换密钥交换双钥体制的加密变换是公开的，任何人都可以采用选择明文选择明文来攻击双钥体制，明文空间必须足够大才能防止穷尽搜索明文空间攻击。这在双钥体制应用中特别重要(如用双钥体制加密会话密钥时，会话密钥要足够长)。一种更强有力的攻击法是选择

47、密文攻击选择密文攻击： 攻击者选择密文，而后通过某种途径得到相应的明文。多数双钥体制对于选择密文攻击特别敏感。通常采用两类选择密文攻击两类选择密文攻击： (1) 冷漠冷漠(Indifferent)选择明文攻击选择明文攻击。在接收到待攻击的密文之前，可以向 攻击者提供他们所选择的密文的解密结果。 (2) 自适应选择密文攻击自适应选择密文攻击，攻击者可能利用(或接入)被攻击者的解密机(但不知其秘密钥)，而可以对他所选择的、与密文有关的待攻击的密文，以及以前询问得到的密文进行解密。七、七、公钥密码总结公钥密码总结双钥密码体制的设计双钥密码体制的设计 双钥密钥保密、认证系统的的安全性主要取决于 构造双

48、钥算法所依赖的数学问题构造双钥算法所依赖的数学问题。 要求加密函数具有单向性单向性，即求逆的困难性求逆的困难性。因此， 设计双钥体制的关键是先要寻求一个合适的单向函数关键是先要寻求一个合适的单向函数。七、七、公钥密码总结公钥密码总结单向函数单向函数 令函数f是集A到集B的映射，以f：AB表示。 若对任意x1x2，x1, x2A，有f(x1)f(x2)， 则称f为单射单射，或11映射映射，或可逆的函数可逆的函数。 f为可逆的充要条件是，存在函数g：B A，使对所有xA有gf(x)=x。一个可逆函数f：AB，若它满足： 1、 对所有xA，易于计算f(x)。 2 、 对“几乎所有xA”由f(x)求x

49、“极为困难”，以至于实际上不可能做到则称f为一单向(One-way)函数。“极为困难”是对现有的计算资源和算法而言。Massey称此为视在困难性视在困难性(apparent difficulty)，相应函数称之为视在单向函数视在单向函数。以此来和本质上本质上(Essentially)的困难性相区分 Massey 1985。 七、七、公钥密码总结公钥密码总结 例例 令f是在有限域GF(p)中的指数函数指数函数，其中p是大素数，即 y=f(x)=x , 式中，xGF(p)，x为满足0 xp1的整数， 其逆运算是GF(p)中定义的对数运算对数运算，即 x=logx 0 xp1 显然，由x求y是容易的

50、，即使当p很大，例如p2100时也不难实现。 为方便计算以下令=2。 所需的计算量为ln2 p次乘法，存储量为(ln2 p)2比特 例如p=2100时，需作100次乘法。 利用计算机由x计算x可在0.1毫秒内完成。 但是，相对于当前计算GF(p)中对数最好的算法，要从x计算x 所需存储量大约为(2/3)*(p)1/2*log p比特、运算量大约为(1/2)*(p)1/2*log p 例如p=2100时，所需的计算量为(1/2)*250*100次，以计算指数一样快的 计算机进行计算需时约1010.7秒(1年=107.5秒，约为1600年！其中假定 存储量的要求能够满足)。 可见，当当p很大时，很

51、大时，GF(p)中的中的f(x)= x，xp1是个单向函数。是个单向函数。七、七、公钥密码总结公钥密码总结Pohlig和Hellman对(p1)无大素因子无大素因子时给出一种快速求对数的算法Pohlig等1978。特别是，当p=2n1时，从x求x的计算量仅需(log p)2次乘法。对于p=2160，在高速计算机上大约仅需时10毫秒。因此，在这种情况下，f(x)=x就不能被认为是单向函数。 当对素数当对素数p，且且p1有大的素因子时，有大的素因子时，GF(p)上的函数上的函数f(x)= x是一个视在单向函数。是一个视在单向函数。寻求在GF(p)上求对数的一般快速算法是当前密码学研究中的一个重要课

52、题。七、七、公钥密码总结公钥密码总结陷门单向函数陷门单向函数 单向函数单向函数是求逆困难的函数，而 单向陷门函数单向陷门函数(Trapdoor one-way function)是 在不知陷门信息陷门信息下求逆困难的函数， 当知道陷门信息后求逆是易于实现的。Diffie和Hellmam1976引入的有用概念。 例例：号码锁、太平门。 但如何给陷门单向函数下定义则很棘手，因为 (1)陷门函数其实不是单向函数，因为单向函数在任何条件下求逆都是困难的； (2)陷门可能不止一个，通过试验,一个个陷门就可容易地找到逆。如果陷门信息的保密性不强，求逆也就不难。七、七、公钥密码总结公钥密码总结公钥系统公钥系

53、统一个公钥系统中，所有用户共同选定一个陷门单向函数、加密运算E及可用消息集鉴别函数F。用户i从陷门集中选定zi，并公开Ezi和Fzi。任一要向用户i送机密消息者，可用Fzi检验消息x是否在许用明文之中， 而后送y=Ezi(x)给用户x即可。在仅知y，Ezi和Fzi下，任一用户不能得到x。但用户i利用陷门信息zi，易于得到Dzi(y)=x。定义定义 对zZ和任意xX，Fi(x)yY=X。若Fj(Fi(x)=Fi(Fj(x) 成立， 则称F为可换单向函数可换单向函数。 可换单向函数在密码学中更有用。七、七、公钥密码总结公钥密码总结用于构造双钥密码的单向函数用于构造双钥密码的单向函数 1976年Di

54、ffie和Hellman发表的文章中虽未给出陷门单向函数， 但大大推动了这方面的研究工作。 双钥密码体制的研究在于双钥密码体制的研究在于 给出这种函数的构造方法以及它们的安全性给出这种函数的构造方法以及它们的安全性。 陷门单向函数的定义并没有给出这类函数是否存在。 目前多数双钥体制所用的单向函数的例子多项式求根多项式求根离散对数离散对数大整数分解大整数分解/RSA问题问题背包问题背包问题Diffie-Hellman问题问题(DHP)二次剩余问题二次剩余问题模模n的平方根问题的平方根问题七、七、公钥密码总结公钥密码总结 多项式求根多项式求根 有限域有限域GF(p)上的一个多项式上的一个多项式y=f(x)=xnan-1xn-1a1xa0 mod p 当给定当给定a0, a1, , an-1，p及及x时，易于求时，易于求y，利用利用Honers 法则，即法则，即 f(x)=(xan-1)xan-2)xan-3)xa1)xa0 mod p。 最多有最多有n次乘法和次乘法和n1次加法。次加法。 反之，已知反之，已知y, a0, , an-1，要求解要求解x需能对高次方程求根。需能对高次方程求根。 这至少要这至少要 n2