1、1公钥密码技术2n主要内容：主要内容：RSA公钥密码算法，公钥密码算法，RSA公钥密公钥密码的实现。码的实现。n重点：重点：RSA算法，脱密的快速实现，素数算法，脱密的快速实现，素数生成算法。生成算法。n难点：难点：素数生成算法。素数生成算法。3RSARSA体制体制 由Rivest、Shamir、Adleman于1978年首次发表；最容易理解和实现的公钥算法;经受住了多年深入的攻击;其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；RSA既可用于加密，又可用于数字签名，已得到广泛采用；RSA已被许多标准化组织(如ISO、ITU、IETF和SWIFT等)接纳；目前许多国家标准仍
2、采用RSA或它的变型 4假设m为要传送的报文。1、任产生两个素数p与q，使得n=pqm2、随机选择数e：e与(p-1)(q-1)互素3、用辗转相除法求d：ed=1 mod(p-1)(q-1)4、公开：（e，n），保密：d 加密过程：c=me mod n 解密过程：m=cd mod n1、RSA算法描述算法描述5定义定义：任给一个正整数：任给一个正整数m，如果用，如果用m去除任意两个整去除任意两个整数数a、b所得的余数相同，称所得的余数相同，称a、b对模对模m同余。记同余。记为：为：，若余数不同，则，若余数不同，则a、b对模对模m不同余。不同余。记为：记为：。mbamodmbamod定理定理：，
3、当且仅当，当且仅当m|(a-b)。mbamod定理定理：欧拉定理，对任意：欧拉定理，对任意 有有*nZananmod1)(推论推论:费尔马定理，费尔马定理，若若p为素数，则为素数，则 papmod111,2,1,0nZn1),(,:*naZaaZnn其中其中2 2、工作原理、工作原理6RSARSA算法论证算法论证 E和和D的可逆性的可逆性要证明：要证明：D(E(M)=MMCd(Me)dMed mod n因为因为ed1 mod(n)，这说明，这说明edt(n)+1,其中其中t为某整数。所以为某整数。所以,Med Mt(n)+1 mod n。因此要证明因此要证明Med M mod n，只需证明，只
4、需证明M t(n)+1 M mod n。7RSARSA算法论证算法论证在（在（M，n）1的情况下，根据数论的情况下，根据数论(Euler定理定理)，M t(n)1 mod n，于是有，于是有，M t(n)+1 M mod n。8RSARSA算法论证算法论证在（在（M，n）1的情况下，分两种情况：的情况下，分两种情况：第一种情况：第一种情况：M1,2,3,n-1因为因为n=pq，p和和q为素数，为素数，M1,2,3,n-1，且（，且（M，n）1。这说明这说明M必含必含p或或q之一为其因子，而且不能同之一为其因子，而且不能同时包含两者，时包含两者，否则将有否则将有Mn，与与M1,2,3,n-1矛盾
5、。矛盾。9RSARSA算法论证算法论证10RSARSA算法论证算法论证不妨设不妨设Map。又因又因q为素数，且为素数，且M不包含不包含q，故有（，故有（M，q）1，于是有，于是有，M(q)1 mod q。进一步有，进一步有，M t(p-1)(q)1 mod q。因为因为q是素数，是素数，(q)（q-1），所以），所以t(p-1)(q)t(n)，所以有所以有M t(n)1 mod q。11于是，于是，M t(n)bq+1，其中，其中b为某整数。为某整数。两边同乘两边同乘M，M t(n)+1 bqM+M。因为因为Map，故，故M t(n)+1 bqap+M=abn+M。取模取模n得，得，M(n)+
6、1 M mod n。RSARSA算法论证算法论证12第二种情况：第二种情况：M0当当M0时，直接验证，可知命题成立。时，直接验证，可知命题成立。RSARSA算法论证算法论证13RSARSA算法论证算法论证加密和解密运算的可交换性加密和解密运算的可交换性D(E(M)=(Me)d=Med=(Md)e=E(D(M)mod n所以，所以，RSA密码可同时确保数据的秘密性和数据的密码可同时确保数据的秘密性和数据的真实性。真实性。14RSARSA算法论证算法论证加解密算法的有效性加解密算法的有效性RSA密码的加解密运算是密码的加解密运算是模幂运算模幂运算，有比较有效，有比较有效的算法。的算法。15RSAR
7、SA算法论证算法论证在计算上由公开密钥不能求出解密钥在计算上由公开密钥不能求出解密钥小合数的因子分解是容易的，然而大合数的因子分小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们种因子分解算法提示人们这一时间下限这一时间下限将不低于将不低于O（EXP（lnNlnlnN）1/2）。根据这一结论，只要合数足够大，进行因子分解是根据这一结论，只要合数足够大，进行因子分解是相当困难的。相当困难的。16RSARSA
8、算法论证算法论证假设截获密文假设截获密文C，从中求出明文，从中求出明文M。他知道。他知道MCd mod n，因为因为n是公开的，要从是公开的，要从C中求出明文中求出明文M，必须，必须先求先求出出d，而，而d是保密的是保密的。但他知道，。但他知道，ed1 mod(n)，e是公开的，要从中求出是公开的，要从中求出d，必须先求出，必须先求出(n)，而，而(n)是保密的是保密的。但他又知道，。但他又知道，(n)=(p-1)(q-1)，17要从中求出要从中求出(n)，必须，必须先求出先求出p和和q，而，而p和和q是保密的是保密的。但他知道，但他知道，n=pq，要从要从n求出求出p和和q，只有对，只有对n
9、进行因子分解。而当进行因子分解。而当n足够大时，足够大时，这是很困难的。这是很困难的。RSARSA算法论证算法论证只要能对只要能对n进行因子分解，便可攻破进行因子分解，便可攻破RSA密码。由此可以密码。由此可以得出，得出，破译破译RSA密码的困难性密码的困难性对对n因子分解的困难性。因子分解的困难性。目目前尚不能证明两者是否能确切相等，因为不能确知除了对前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方进行因子分解的方法外，是否还有别的更简捷的破译方法。法。18 3 3、例子：、例子：假设假设RSARSA体制中体制中p=3,q=11,p=3,q
10、=11,取加密密钥取加密密钥e=7.e=7.(1)(1)求脱密密钥求脱密密钥d;d;(2)(2)写出相应的加密算法和脱密算法写出相应的加密算法和脱密算法;(3)(3)对明文对明文m=8m=8加密。加密。7d7d mod20=1mod20=1因因e=7e=7与与 互素互素,故可解模方程故可解模方程 ，即，即1)(modned20)(n20)1)(1()(qpn 解解:此时此时npq3333，且，且得到得到d d3 3。19故故RSARSA体制明、密文空间体制明、密文空间:Z/(33)加密密钥：加密密钥：(e,n)=(7,33)脱密密钥：脱密密钥：(d,p,q)=(3,3,11)加密算法加密算法:
11、cm7mod33脱密算法脱密算法:mc3mod33对明文对明文m8 8加密，得加密，得:c87mod33=220二、二、RSA算法的参数选择算法的参数选择为了确保为了确保RSA密码的安全，必须认真选择密码参数：密码的安全，必须认真选择密码参数：p和和q要足够大；要足够大；一般应用：一般应用：p和和q应应512 bits 重要应用：重要应用：p和和q应应1024 bitsp和和q应为强素数应为强素数文献指出，只要文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四四个数之一只有小的素因子，个数之一只有小的素因子，n就容易分解。就容易分解。p和和q的差要大；的差要大；21（p-1）和（）
12、和（q-1）的最大公因子要小）的最大公因子要小。如果（如果（p-1）和（）和（q-1）的最大公因子太大，则易受）的最大公因子太大，则易受迭代加密迭代加密攻击攻击。e的选择的选择随机且含随机且含1多就安全，但加密速度慢。于是，有的学者建议取多就安全，但加密速度慢。于是，有的学者建议取e216+165537 d的选择的选择d不能太小，要足够大不能太小，要足够大 不要许多用户共用一个模不要许多用户共用一个模n；易受共模攻击易受共模攻击22 1989年Lenstra,Manasse利用二次筛法使用数百台工作站分解了106位十进制数；1990年Lenstra,Manasse,Pollar利用数域筛法使用
13、700台工作站花费个月时间将155位十进制数分解成三个素数之积；1994年Atkins,Graff,Lenstra,Lerland利用多重二次筛法的双重大素数算法动用1600台计算机联网，600名志愿者花费个月时间分解了129位十进制数；2002年成功分解158位的十进制数。结论：154位十进制数（512bit）的模长已经不安全，应使用308位十进制数（1024bit）模长。23l RSA的安全性基础是基于的安全性基础是基于大合数分解大合数分解的困的困难性，在难性，在RSA算法中要求模数算法中要求模数N是两个大素数是两个大素数p和和q的乘积。的乘积。l 用户选择模数用户选择模数N的方法是先找到
14、两个素数，的方法是先找到两个素数，然后生成相应的模数然后生成相应的模数N。l 素数判定素数判定是要解决的首要问题。是要解决的首要问题。241 1、产生大素数的算法（、产生大素数的算法（RabinRabin素性检测算法素性检测算法）由欧拉定理知，若由欧拉定理知，若n为素数：为素数：*nZananmod11则则n可能为素数，也可能为合数可能为素数，也可能为合数。RabinRabin由此设计由此设计了一个了一个判定判定n n是否为是否为素数的算法素数的算法。反过来若：反过来若：，则，则n必为合数。必为合数。nanmod11nanmod11若若251 1、产生大素数的算法、产生大素数的算法RabinR
15、abin素性检测算法素性检测算法Rabin素性检测法是一种素性检测法是一种概率概率素数测试法。素数测试法。其输入为一奇数，输出为两种状态其输入为一奇数，输出为两种状态Yes或或No。若输入一奇数。若输入一奇数N，而输出为，而输出为No，即表示，即表示N必定为合数。若必定为合数。若输出为输出为Yes，则表示，则表示N为素为素数的数的概率为概率为1-，其中，其中为此素数测试法中为此素数测试法中可可控制的任意小数控制的任意小数，但不能为，但不能为0。（。（是在是在N是是合数的条件下误判为素数的条件概率。）合数的条件下误判为素数的条件概率。）26RabinRabin素性检测算法：素性检测算法：（1 1
16、）任取一个大奇数任取一个大奇数n n（2 2）任取）任取 且且(a,n)=1(a,n)=1（3 3）如果）如果,则判则判n n是素数；是素数；否则判否则判n n是合数，重新选取是合数，重新选取n n重复上过程。重复上过程。2,3,2nanpnRabinRabin证明了由上述算法所产生的素数的误判概率证明了由上述算法所产生的素数的误判概率:41)(是合数数判定为素nnP由此由此,我们将算法中的第我们将算法中的第(2)(2)和和(3)(3)步骤重复步骤重复k k次次,这样判定这样判定n n为素数的误判概率小于等于为素数的误判概率小于等于(1/4)(1/4)k k。计算复杂度为：计算复杂度为：O(l
17、ogO(log2 2n)n)3 3)27Miller-Rabin算法算法 l 随机选择一个奇整数随机选择一个奇整数n(如利用伪随机数产生如利用伪随机数产生器器)；l 随机选择一个整数随机选择一个整数an；l 执行诸如执行诸如Miller-Rabin等概率素数测试。若等概率素数测试。若n未通过测试，则转到第一步；未通过测试，则转到第一步；l 若若n通过足够多次的测试，则接受通过足够多次的测试，则接受n；否则转；否则转向第向第2步。步。28 在实际使用中在实际使用中,通过首先检验待检测的随机数是否通过首先检验待检测的随机数是否是小素数是小素数(例如所有小于例如所有小于10001000的素数的素数)
18、的倍数，待检测的倍数，待检测通过后再执行通过后再执行RabinRabin检测。检测。Miller-RabinRabin素数检测算法，已经作为标准的检测素数检测算法，已经作为标准的检测算法列入算法列入IEEE P1363IEEE P1363的附录的附录和和NISTNIST的数字签名标准的的数字签名标准的附录附录，作为密码学标准使用。，作为密码学标准使用。29 RSA的加脱密计算都是在模的加脱密计算都是在模N运算下运算下进行的，尽管这两个加脱密计算公式形式进行的，尽管这两个加脱密计算公式形式上比较简单，但由于其加、脱密的两个主上比较简单，但由于其加、脱密的两个主要运算，即要运算，即指数运算指数运算
19、与与模大整数运算模大整数运算均涉均涉及到很大的数，故及到很大的数，故RSA的实现还是有较大的实现还是有较大的难度。的难度。快速乘方算法快速乘方算法30 指数运算指数运算 最简单而直接的计算方最简单而直接的计算方法，就是将法，就是将m连续乘连续乘e-1次，如此就可次，如此就可以获得的值了。以获得的值了。当当m或或e很大时，其计算复杂度将是很大时，其计算复杂度将是非常高的。非常高的。em 在指数运算中，比较有名的是在指数运算中，比较有名的是二元法二元法（也称为平方乘法）（也称为平方乘法）31设设e为为k位二进制数，位二进制数，w(e)为为e的二进制系数中为的二进制系数中为1的个的个数，则最多只需要
20、计算数，则最多只需要计算w(e)-1次平方次平方和和w(e)次数的模次数的模乘乘。从而大大简化了计算。从而大大简化了计算。32以以512512比特加密指数为例，整数比特加密指数为例，整数e e的二进制表示为的二进制表示为:5115112210222eeeee一般的加密过程为一般的加密过程为:Nmmmmmeeeeemod)(015105112223323120212222()(mod)lllleeeeemmmmmNNmemod3412302122222()(mod)lllleeeeeemmmmmmN1201222()(mod)lleeeemmmmN201222()(mod)leeemmmmN 当
21、要对明文进行加密时，可先进行预处理，当要对明文进行加密时，可先进行预处理，计算出计算出m m2 2、m m3 3等，这种方法我们称之为窗口法。等，这种方法我们称之为窗口法。34例：例：131520(mod2539)计算计算:B11011202121323)1,0,1,1(),(0123eeee2539mod1520133021222(1520)1520)1520)1520(mod2539)eeee2202(1520 1520)1520)1520(mod2539)35第一步首先计算第一步首先计算215202449(mod2539)第二步计算第二步计算2449 1520306(mod2539)第三
22、步计算第三步计算23062232(mod2539)第四步计算第四步计算22232306(mod2539)最后一步计算最后一步计算306 1520483(mod2539)131520483(mod2539)结论：结论：36快速模乘算法快速模乘算法反复平方乘算法解决了快速乘方取模的问题，反复平方乘算法解决了快速乘方取模的问题，仍未解决快速模乘的问题；仍未解决快速模乘的问题；Montgomery算法算法是一种快速模乘的好算法；是一种快速模乘的好算法；将以上两种算法结合成为实现将以上两种算法结合成为实现RSA密码的密码的有效有效方法。方法。37Montgomery算法的思路：算法的思路：要计算要计算Y
23、=AB mod n,因为因为n很大，取模运算困难，采取一很大，取模运算困难，采取一个小的模个小的模R，回避大模数的计算。，回避大模数的计算。利用空间换时间，多用存储空间换取快速。利用空间换时间，多用存储空间换取快速。缺点：不能直接计算出缺点：不能直接计算出Y=AB mod n，只能计算出中间，只能计算出中间值值ABR-1 mod n，因此还需要预处理和调整运算。一次性，因此还需要预处理和调整运算。一次性计算计算Y=AB mod n并不划算。并不划算。适合：适合：RSA等密码中多次的模乘计算。等密码中多次的模乘计算。38对称密钥密码学与公钥密码学对称密钥密码学与公钥密码学1、对称密钥密码学的优点
24、、对称密钥密码学的优点（1）能够设计为具有很高的数据吞吐率。硬件实现可以）能够设计为具有很高的数据吞吐率。硬件实现可以达到每秒加密几百兆字节，而软件实现的吞吐率也达到了达到每秒加密几百兆字节，而软件实现的吞吐率也达到了每秒兆字节的数量级。每秒兆字节的数量级。（2）对称密码的密钥相对较短。）对称密码的密钥相对较短。（3）对称密钥密码可以作为要素来构造各种密码机制。）对称密钥密码可以作为要素来构造各种密码机制。比如伪随机数生成器、杂凑函数、快速数字签名方案等比如伪随机数生成器、杂凑函数、快速数字签名方案等（4）对称密钥密码能合成强密码。简单变换容易被分）对称密钥密码能合成强密码。简单变换容易被分拆
25、，但是研究其弱点后，可用来构造强的乘积密码。拆，但是研究其弱点后，可用来构造强的乘积密码。392、对称密钥密码学的缺点、对称密钥密码学的缺点（1）在一个双方的通信中，密钥必须在两端都保密。）在一个双方的通信中，密钥必须在两端都保密。（2）在大型网络中，要管理许多密钥对。其结果是，有效）在大型网络中，要管理许多密钥对。其结果是，有效的密钥管理需要一个无条件可信的的密钥管理需要一个无条件可信的TTP。（称一个。（称一个TTP是无是无条件可信的，如果它在所有事情上都可信。例如它也许可以条件可信的，如果它在所有事情上都可信。例如它也许可以访问用户的秘密密钥和私钥，还承担着公钥和标识符的联系）访问用户的
26、秘密密钥和私钥，还承担着公钥和标识符的联系）（3）对实体）对实体A与与B之间的一个双方通信，使用密钥的良好习之间的一个双方通信，使用密钥的良好习惯是：经常更换密钥，通常是会话密钥一次一换。惯是：经常更换密钥，通常是会话密钥一次一换。（4）源自对称密钥加密的数字签名机制通常需要关于公开）源自对称密钥加密的数字签名机制通常需要关于公开验证函数的大密钥，或者使用验证函数的大密钥，或者使用TTP。403、公钥密码学的优点、公钥密码学的优点（1）只有私钥必须保密。（但必须保证公钥的真实性）只有私钥必须保密。（但必须保证公钥的真实性）（2）与无条件可信的）与无条件可信的TTP相反，公钥密码管理需要的只是一
27、相反，公钥密码管理需要的只是一个功能上可信的个功能上可信的TTP（称一个（称一个TTP是功能上可信的，如果它是功能上可信的，如果它是诚实且公正的，但是不可以访问用户的秘密密钥和私钥）。是诚实且公正的，但是不可以访问用户的秘密密钥和私钥）。关于使用方式，和实时的需要使用相反，这个关于使用方式，和实时的需要使用相反，这个TTP也许只需也许只需以离线方式使用。以离线方式使用。（3）依赖于使用方式的差别，一个私钥）依赖于使用方式的差别，一个私钥/公钥对可以在一段公钥对可以在一段相当长的时期内保持不变，甚至数年。比如多次会话使用相相当长的时期内保持不变，甚至数年。比如多次会话使用相同密钥。同密钥。41（
28、4）许多公钥方案产生了相对有效的数字签名机制。用于）许多公钥方案产生了相对有效的数字签名机制。用于刻画公开验证函数的密钥通常比对称密钥小很多。刻画公开验证函数的密钥通常比对称密钥小很多。（5）在大型网络中，所需密钥的数量要比对称密钥情形下）在大型网络中，所需密钥的数量要比对称密钥情形下少很多。少很多。424、公钥密码学的缺点、公钥密码学的缺点（1）在吞吐率方面，大多流行的公钥加密方法要比已知）在吞吐率方面，大多流行的公钥加密方法要比已知最好的对称密钥加密方案慢几个数量级。最好的对称密钥加密方案慢几个数量级。（2）密钥长度（如）密钥长度（如RSA的的1024比特）明显要比对称密钥比特）明显要比对
29、称密钥（如（如64比特或比特或128比特）加密所需大得多（比特）加密所需大得多（10倍或更多）。倍或更多）。这是因为针对对称密钥系统的最有效的攻击是密钥穷搜这是因为针对对称密钥系统的最有效的攻击是密钥穷搜（这一般是设计要求），而对公钥系统来说，快捷攻击（这一般是设计要求），而对公钥系统来说，快捷攻击（如因子分解）比穷搜有效得多。（如因子分解）比穷搜有效得多。43（3）没有公钥方案被证明是安全的（对分组秘密也一）没有公钥方案被证明是安全的（对分组秘密也一样）。至今发现的最有效的公钥加密方案都把安全性建样）。至今发现的最有效的公钥加密方案都把安全性建立在一小批数论问题的困难性假定之上。立在一小批数
30、论问题的困难性假定之上。（4）公钥密码学没有对称密钥加密那样长久的历史，它）公钥密码学没有对称密钥加密那样长久的历史，它在在20世纪世纪70年代中期才被发现。年代中期才被发现。445、总结、总结 对称密钥加密和公钥加密有许多互补的优点。目前对称密钥加密和公钥加密有许多互补的优点。目前的密码系统融合了两者的优势。的密码系统融合了两者的优势。凭借公钥加密技术来建立密钥，然后用于实体凭借公钥加密技术来建立密钥，然后用于实体A和和B进行通信的对称密钥密码系统。进行通信的对称密钥密码系统。A和和B就可综合利用公钥就可综合利用公钥方案的公钥与私钥对长期性，以及对称密钥方案的高效性。方案的公钥与私钥对长期性
31、，以及对称密钥方案的高效性。数据加密通常是加密过程耗费时间最多的部分，而公钥方数据加密通常是加密过程耗费时间最多的部分，而公钥方案实现的密钥建立只是案实现的密钥建立只是A和和B之间整个加密过程的一小部之间整个加密过程的一小部分（从耗时来考虑）。分（从耗时来考虑）。45 在计算效率上，公钥加密比不上对称加密，但也在计算效率上，公钥加密比不上对称加密，但也没有证明说一定是这样。总得来说，公钥密码学推动没有证明说一定是这样。总得来说，公钥密码学推动有效的签名（特别是不可抵赖性）和密钥管理，对称有效的签名（特别是不可抵赖性）和密钥管理，对称密钥密码学对加密及一些数据完整性应用很有效。密钥密码学对加密及一些数据完整性应用很有效。谢谢46
