1公钥密码技术2RSARSA公钥密码算法公钥密码算法n主要内容：RSA公钥密码算法，RSA公钥密 码的实现。n重点： RSA算法，脱密的快速实现，素数 生成算法。n难点：素数生成算法。3RSA体制 由Rivest、Shamir、Adleman于1978年首次 发表； 最容易理解和实现的公钥算法; 经受住了多年深入的攻击; 其理论基础是一种特殊的可逆模幂运算，其 安全性基于分解大整数的困难性； RSA既可用于加密，又可用于数字签名，已 得到广泛采用； RSA已被许多标准化组织(如ISO、ITU、IETF 和SWIFT等)接纳； 目前许多国家标准仍采用RSA或它的变型 4假设m为要传送的报文。 1、任产生两个素数p与q，使得n=pqm 2、随机选择数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 n一、一、RSARSA算法算法1、RSA算法描述5定义：任给一个正整数m，如果用m去除任意两个整 数a、b所得的余数相同，称a、b对模m同余。记为： ，若余数不同，则a、b对模m不同余。记为： 。 定理： ，当且仅当m|(a-b)。定理：欧拉定理，对任意 有 推论:费尔马定理，若p为素数，则 其中2、工作原理6RSA算法论证 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 ，只需证明M t(n)+1 M mod n 。7RSA算法论证在（M，n）1的情况下，根据数论(Euler定理)，M t(n) 1 mod n ，于是有，M t(n)+1 M mod n 。8RSA算法论证在（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矛盾。9RSA算法论证10RSA算法论证不妨设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)+1 M mod n 。RSA算法论证12第二种情况：M0当M0时，直接验证，可知命题成立。RSA算法论证13RSA算法论证加密和解密运算的可交换性D(E(M)=(Me)d =Med =(Md)e =E(D(M) mod n所以，RSA密码可同时确保数据的秘密性和数据的真实性。14RSA算法论证加解密算法的有效性RSA密码的加解密运算是模幂运算，有比较有效的算法。15RSA算法论证在计算上由公开密钥不能求出解密钥小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这一时间下限将不低于O（EXP（lnNlnlnN）1/2）。根据这一结论，只要合数足够大，进行因子分解是相当困难的。16RSA算法论证假设截获密文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进行因子分解。而当n足够大时 ，这是很困难的。RSA算法论证只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破译RSA密码的困难性对n因子分解的困难性。目前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。183、例子：假设RSA体制中p=3,q=11,取加密密钥e=7.(1) 求脱密密钥d;(2) 写出相应的加密算法和脱密算法;(3) 对明文m=8加密。7d mod20=1因e=7与 互素, 故可解模方程 ，即解: 此时npq33，且得到d3。19故RSA体制明、密文空间: Z/(33) 加密密钥：(e, n) =(7, 33) 脱密密钥：(d, p, q) =(3, 3,11)加密算法: cm7mod33 脱密算法: mc3mod33对明文m8加密，得: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）和（q-1）的最大公因子要小。如果（ p-1）和（q-1）的最大公因子太大，则易受迭代加密攻击。 e的选择随机且含1多就安全，但加密速度慢。于是，有的学者建议取e216+165537 d的选择d不能太小，要足够大 不要许多用户共用一个模n；易受共模攻击22 1989年Lenstra, Manasse利用二次筛法使用数百 台工作站分解了106位十进制数； 1990年Lenstra, Manasse, Pollar利用数域筛法 使用700台工作站花费个月时间将155位十进制 数分解成三个素数之积； 1994年Atkins, Graff, Lenstra, Lerland利用 多重二次筛法的双重大素数算法动用1600台计算 机联网，600名志愿者花费个月时间分解了129 位十进制数； 2002年成功分解158位的十进制数。 结论：154位十进制数（512bit）的模长已经不 安全，应使用308位十进制数（1024bit）模长。23三、三、RSARSA算法中大素数生成算法中大素数生成l RSA的安全性基础是基于大合数分解的困 难性，在RSA算法中要求模数N是两个大素数 p和q的乘积。l 用户选择模数N的方法是先找到两个素数， 然后生成相应的模数N。l 素数判定是要解决的首要问题。241、产生大素数的算法（Rabin素性检测算法）由欧拉定理知，若n为素数：则n可能为素数，也可能为合数。 Rabin由此设计了 一个判定n是否为素数的算法。反过来若： ，则n必为合数。若251、产生大素数的算法Rabin素性检测算法Rabin素性检测法是一种概率素数测试法。其输入为一奇数，输出为两种状态Yes或 No。若输入一奇数N，而输出为No，即表示 N必定为合数。若输出为Yes，则表示N为素 数的概率为1-，其中为此素数测试法中可 控制的任意小数，但不能为0。（ 是在N是 合数的条件下误判为素数的条件概率。）26Rabin素性检测算法：（1）任取一个大奇数n（2）任取 且(a,n)=1（3）如果, 则判n是素数；否则判n是合数，重新选取n重复上过程。Rabin证明了由上述算法所产生的素数的误判概率:由此,我们将算法中的第(2)和(3)步骤重复k次,这样判定n为素数的误判概率小于等于(1/4)k。计算复杂度为：O(log2n)3)27Miller-Rabin算法 l 随机选择一个奇整数n(如利用伪随机数产生器 )；l 随机选择一个整数an；l 执行诸如Miller-Rabin等概率素数测试。若n 未通过测试，则转到第一步；l 若n通过足够多次的测试，则接受n；否则转 向第2步。28在实际使用中,通过首先检验待检测的随机数是否 是小素数(例如所有小于1000的素数)的倍数，待检测 通过后再执行Rabin检测。Miller-Rabin素数检测算法，已经作为标准的检测算法列入IEEE P1363的附录和NIST的数字签名标准的 附录，作为密码学标准使用。 29RSA的加脱密计算都是在模N运算下 进行的，尽管这两个加脱密计算公式形式 上比较简单，但由于其加、脱密的两个主 要运算，即指数运算与模大整数运算均涉 及到很大的数，故RSA的实现还是有较大 的难度。 快速乘方算法30指数运算 最简单而直接的计算方 法，就是将m连续乘e-1次，如此就可 以获得的值了。当m或e很大时，其计算复杂度将是 非常高的。在指数运算中，比较有名的是二元法 （也称为平方乘法） 31设e为k位二进制数，w(e)为e的二进制系数中为1的个数，则最多只需要计算w(e) -1次平方和w(e)次数的模乘。从而大大简化了计算。32以512比特加密指数为例，整数e的二进制表示为:一般的加密过程为:33当要对明文进行加密时，可先进行预处理， 计算出m2、m3等，这种方法我们称之为窗口法。34例：计算:35第一步首先计算第二步计算第三步计算第四步计算最后一步计算结论：36快速模乘算法反复平方乘算法解决了快速乘方取模的问题 ，仍未解决快速模乘的问题；Montgomery算法是一种快速模乘的好算法； 将以上两种算法结合成为实现RSA密码的有效方法。37Montgomery算法的思路： 要计算Y=AB mod n ,因为n很大，取模运算困难，采取一个小的模R，回避大模数的计算。利用空间换时间，多用存储空间换取快速。 缺点：不能直接计算出Y=AB mod n ，只能计算出中间值ABR-1 mod n ，因此还需要预处理和调整运算。一次性计算Y=AB mod n并不划算。 适合：RSA等密码中多次的模乘计算。38对称密钥密码学与公钥密码学1、对称密钥密码学的优点（1）能够设计为具有很高的数据吞吐率。硬件实现可以 达到每秒加密几百兆字节，而软件实现的吞吐率也达到了 每秒兆字节的数量级。（2）对称密码的密钥相对较短。 （3）对称密钥密码可以作为要素来构造各种密码机制 。比如伪随机数生成器、杂凑函数、快速数字签名方案 等 （4）对称密钥密码能合成强密码。简单变换容易被分 拆，但是研究其弱点后，可用来构造强的乘积密码。392、对称密钥密码学的缺点（1）在一个双方的通信中，密钥必须在两端都保密。（2）在大型网络中，要管理许多密钥对。其结果是，有效的 密钥管理需要一个无条件可信的TTP。（称一个TTP是无条 件可信的，如果它在所有事情上都可信。例如它也许可以访 问用户的秘密密钥和私钥，还承担着公钥和标识符的联系）（3）对实体A与B之间的一个双方通信，使用密钥的良好习 惯是：经常更换密钥，通常是会话密钥一次一换。（4）源自对称密钥加密的数字签名机制通常需要关于公开验 证函数的大密钥，或者使用TTP。403、公钥密码学的优点（1）只有私钥必须保密。（但必须保证公钥的真实性）（2）与无条件可信的TTP相反，公钥密码管理需要的只是一 个功能上可信的TTP（称一个TTP是功能上可信的，如果它 是诚实且公正的，但是不可以访问用户的秘密密钥和私钥） 。关于使用方式，和实时的需要使用相反，这个TTP也许只 需以离线方