RSA算法
－摘自http://tanghuanliang.go.nease.net/ec/rsa.htm#
假设资料要由A机器传至B机器,那,由B机器用乱数决定一个key,我们称之为privatekey,这个key自始至终都只留在B机器里不送出来然後,由这个privatekey计算出另一个key,我们称之为publickey.这个publickey的特性是几乎不可能反演算出privatekey来然後将这个publickey透过网路丢给A机器.A机器将资料用这个publickey编码,这个编码过的资料一定得使用privatekey才解得开然後A机器将编码过的资料透过网路传给B,B再用privatekey将资料解码这时,如果有第三者窃听资料时,他只得到B传给A的publickey,以及A用这个publickey编码後的资料没有privatekey,第三者根本无法解码所以这个方法确实能防止第三者的窃听
它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。
RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数（ 大于 100 个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。
密钥对的产生。选择两个大素数，p 和q 。计算：
n = p * q
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后，利用 Euclid 算法计算解密密钥d,满足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互质。数e和 n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。
加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s ，其中 <= n, s 尽可能的
大。对应的密文是：
ci = mi^e ( mod n ) ( a )
解密时作如下计算：
mi =ci^d ( mod n ) ( b )
RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先作 HASH 运算。
RSA 的安全性。 RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。
RSA的速度。 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
RSA的选择密文攻击。 RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind)，让拥
有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：
( XM )^d = X^d *M^d mod n
前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way HashFunction 对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。
RSA的公共模数攻击。 若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：
C1 = P^e1 mod n
C2 = P^e2 mod n
密码分析者知道n、e1、e2、C1和C2，就能得到P。 因为e1和e2互质，故用Euclidean算法能找到r和s，满足：
r * e1 + s * e2 = 1
假设r为负数，需再用Euclidean算法计算C1^(-1)，则
( C1^(-1) )^(-r) * C2^s = P mod n
另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。解决办法只有一个，那就是不要共享模数n。
RSA的小指数攻击。 有一种提高 RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有
所提高。但这样作是不安全的，对付办法就是e和d都取较大的值。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。 RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET( Secure Electronic Transaction )协议中要求CA采用比特长的密钥，其他实体使用比特的密钥
首先,找出三个数,其中p,q是两个相异的质数,r是与(p-1)(q-1)互质的数这三个数便是privatekey
接著,找出m,使得rm==1mod(p-1)(q-1)这个m一定存在,因为r与(p-1)(q-1)互质,用辗转相除法就可以得到了再来,计算n=pqm,n这两个数便是publickey编码过程是,若资料为a,将其看成是一个大整数,假设a<n如果a>=n的话,就将a表成s进位(s<=n,通常取s=2^t),则每一位数均小於n,然後分段编码接下来,计算b==a^mmodn,(0<=b<n),b就是编码後的资料解码的过程是,计算c==b^rmodpq(0<=c<pq),於是乎,解码完毕等会会证明c和a其实是相等的
如果第三者进行窃听时,他会得到几个数:m,n(=pq),b他如果要解码的话,必须想办法得到r所以,他必须先对n作质因数分解要防止他分解,最有效的方法是找两个非常的大质数p,q,使第三者作因数分解时发生困难
<定理>
若p,q是相异质数,rm==1mod(p-1)(q-1),a是任意一个正整数b==a^mmodpq,c==b^rmodpq,
则c==amodpq
证明的过程,会用到费马小定理,叙述如下:
m是任一质数,n是任一整数,则n^m==nmodm 换另一句话说,如果n和m互质,则n^(m-1)==1modm)
运用一些基本的群论的知识,就可以很容易地证出费马小定理的 ><证明>
因为rm==1mod(p-1)(q-1),所以rm=k(p-1)(q-1)+1,其中k是整数,因为在modulo中是preserve乘法的x==ymodzandu==vmodz=>xu==yvmodz),
所以,c==b^r==(a^m)^r==a^(rm)==a^(k(p-1)(q-1)+1)modpq
1.如果a不是p的倍数,也不是q的倍数时,则a^(p-1)==1modp(费马小定理)=>a^(k(p-1)(q-1))==1modp,a^(q-1)==1modq(费马小定理)=>a^(k(p-1)(q-1))==1modq 所以p,q均能整除a^(k(p-1)(q-1))-1=>pq|a^(k(p-1)(q-1))-1,即a^(k(p-1)(q-1))==1modpq
=>c==a^(k(p-1)(q-1)+1)==amodpq
2.如果a是p的倍数,但不是q的倍数时,则a^(q-1)==1modq(费马小定理)
=>a^(k(p-1)(q-1))==1modq=>c==a^(k(p-1)(q-1)+1)==amodq=>q|c-a
因p|a
=>c==a^(k(p-1)(q-1)+1)==0modp
=>p|c-a所以,pq|c-a=>c==amodpq
3.如果a是q的倍数,但不是p的倍数时,证明同上
4.如果a同时是p和q的倍数时,则pq|a=>c==a^(k(p-1)(q-1)+1)==0modpq>pq|c-a
=>c==amodpq
Q.E.D.
这个定理说明a经过编码为b再经过解码为c时,a==cmodn(n=pq)....
但我们在做编码解码时,限制0<=a<n,0<=c<n,
所以这就是说a等於c,所以这个过程确实能做到编码解码的功能
还有一些事值得探讨的
首先是质数的选取
上一篇提到为了使因数分解发生困难, 所选择的质数要愈大愈好,但这也意味著, 质数的选取也同样的困难因为就目前而言, 跟本没有一个所谓的质数产生公式可用
解析数论上有一个定理, 当 p 很大时, 质数的分布密度与 1/log p 成正比,也就是说一个质数和下一个质数的差平均而言与 log p 成正比还好 log p 的成长并不会很快, 所以就采用一个方法 --- 暴力搜寻法一个数接著一个数找 直到找到质数为止.
即使 n 大到 2^512, 所要花的时间也不会大到天文数字,用 486 的话, 大概在数秒钟至数十秒之内会找到 (包括判定的时间).
现在有一个问题了 如何去判定一个数是否是质数,因为到目前为止, 并没有一个很有效的方法来判定,当然有人会问, 为什麽不用试除法.嗯 如果用这个方法, 2^512 这麽大的数, 大概要除个大於 10^30 年.虽然如此, 但还是得去判断啊
有一个方法, 是利用费马小定理去做判定的.假设一数 p, 如果 p 是质数, a^p == a mod p,如果 p 不是质数, 那麽 a^p == a mod p 虽然也有可能成立,但成立的机率非常小, 而且 p 愈大时机率愈小。用这种方法, 我们就找一些质数来测定, 比如验证。2^p == 2 mod p, 3^p == 3 mod p, 5^p == 5 mod p 等式是否成立，如此一来, p 是质数的机率就变得非常非常高了
现在来讨论 RSA 演算法编码解码的速度
因为我们是对一些很大的数作计算,所以, 一些加减乘除的运算, 必须自己写成函式来处理这些事就 N-digit key 的资料而言, 加减法需要 O(N) 的时间, 乘除法需要 O(N^2) 的时间至於计算 a^b mod c, 则是需要 O(N^3) 的时间, 亦即, 要对 N-digit 的资料用 N-digit key 作编码解码, 是需要 O(N^3) 的时间一般的实作, N 是介於 512 至 1024 之间, (太小的话很有可能被因数分解开) 所以算算 N^3, 其计算量也是相当惊人的这意味著, 用 RSA 演算法来编码解码其速度是非常慢的 既然 RSA 的速度很慢, 这就表示它并不适合所有情况..... 比如 ftp, 这就不适合全程使用 RSA 作编码解码
如何去改善速度? 还记得之前所提到的 DES 吧? RSA 搭配上 DES 的话, 就可以弥补编码解码时速度太慢的问题了 先前提到用 DES 作编码解码时, 双方必须使用同一个 key所以, 我们可以用 RSA 演算法将 DES key 送给对方, 而後接下来的资料, 就全部利用 DES 来做编码解码, 如此, 整个过程中, 因使用 RSA 而耗掉的时间就不会太多 再者, 产生 RSA key 所耗掉的时间, 也是相当惊人的先前提到, 以 N-digit key 为例, 两个相邻质数平均间隔为 O(N), 对於这些数, 我们要利用费马小定理去判定是否可能为质数, 而计算 a^b mod c 所花的时间为 O(N^3), 所以算一算, 平均要找到一个 N-digit 质数, 需费时 O(N^4)所以在产生 RSA key 时也是一件非常耗时的工作所以, 一般的作法是, 先花一大把时间去找 RSA key, 往後的编码解码就使用这一组 key 就以 stand-alone telnet daemon 为例好了, 可行的做法是 telnetd 一开始执行时, 先花时间运算出 RSA key, 之後 telnet 连上这个 telnetd 之後, 丢给 telnet 这个 RSA key (public), 然後 telnet 将 DES key 用这个 RSA key 编码丢後回给 telnetd, 之後的通讯就用这个 DES key 作编码解码
本文地址：http://com.8s8s.com/it/it42782.htm