首页 >> 数学 >> 计算机科学 >> 文章

RSA算法原理(二)Comments>>

发表于 2013-09-09 14:17 | Tags 标签:, ,

作者: 阮一峰

上一次,我介绍了一些数论知识

有了这些知识,我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。

六、密钥生成的步骤

我们通过一个例子,来理解RSA算法。假设爱丽丝要与鲍勃进行加密通信,她该怎么生成公钥和私钥呢?

第一步,随机选择两个不相等的质数p和q。

爱丽丝选择了61和53。(实际应用中,这两个质数越大,就越难破解。)

第二步,计算p和q的乘积n。

爱丽丝就把61和53相乘。

n = 61×53 = 3233

n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

第三步,计算n的欧拉函数φ(n)。

根据公式:

φ(n) = (p-1)(q-1)

爱丽丝算出φ(3233)等于60×52,即3120。

第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。

爱丽丝就在1到3120之间,随机选择了17。(实际应用中,常常选择65537。)

第五步,计算e对于φ(n)的模反元素d。

所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。

ed ≡ 1 (mod φ(n))

这个式子等价于

ed - 1 = kφ(n)

于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。

ex + φ(n)y = 1

已知 e=17, φ(n)=3120,

17x + 3120y = 1

这个方程可以用"扩展欧几里得算法"求解,此处省略具体过程。总之,爱丽丝算出一组整数解为 (x,y)=(2753,-15),即 d=2753。

至此所有计算完成。

第六步,将n和e封装成公钥,n和d封装成私钥。

在爱丽丝的例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。

实际应用中,公钥和私钥的数据都采用ASN.1格式表达(实例)。

七、RSA算法的可靠性

回顾上面的密钥生成步骤,一共出现六个数字:

p
q
n
φ(n)
e
d

这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。

那么,有无可能在已知n和e的情况下,推导出d?

(1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。

(2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。

(3)n=pq。只有将n因数分解,才能算出p和q。

结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。

可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。维基百科这样写道:

"对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。

假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。

只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。"

举例来说,你可以对3233进行因数分解(61×53),但是你没法对下面这个整数进行因数分解。

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

它等于这样两个质数的乘积:

33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917

事实上,这大概是人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。

八、加密和解密

有了公钥和密钥,就能进行加密和解密了。

(1)加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

所谓"加密",就是算出下式的c:

me ≡ c (mod n)

爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式:

6517 ≡ 2790 (mod 3233)

于是,c等于2790,鲍勃就把2790发给了爱丽丝。

(2)解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立:

cd ≡ m (mod n)

也就是说,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),那么,爱丽丝算出

27902753 ≡ 65 (mod 3233)

因此,爱丽丝知道了鲍勃加密前的原文就是65。

至此,"加密--解密"的整个过程全部完成。

我们可以看到,如果不知道d,就没有办法从c求出m。而前面已经说过,要知道d就必须分解n,这是极难做到的,所以RSA算法保证了通信安全。

你可能会问,公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种"对称性加密算法"(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

九、私钥解密的证明

最后,我们来证明,为什么用私钥解密,一定可以正确地得到m。也就是证明下面这个式子:

cd ≡ m (mod n)

因为,根据加密规则

me ≡ c (mod n)

于是,c可以写成下面的形式:

c = me - kn

将c代入要我们要证明的那个解密规则:

(me - kn)d ≡ m (mod n)

它等同于求证

med ≡ m (mod n)

由于

ed ≡ 1 (mod φ(n))

所以

ed = hφ(n)+1

将ed代入:

mhφ(n)+1 ≡ m (mod n)

接下来,分成两种情况证明上面这个式子。

(1)m与n互质。

根据欧拉定理,此时

mφ(n) ≡ 1 (mod n)

得到

(mφ(n))h × m ≡ m (mod n)

原式得到证明。

(2)m与n不是互质关系。

此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。

以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:

(kp)q-1 ≡ 1 (mod q)

进一步得到

[(kp)q-1]h(p-1) × kp ≡ kp (mod q)

(kp)ed ≡ kp (mod q)

将它改写成下面的等式

(kp)ed = tq + kp

这时t必然能被p整除,即 t=t'p

(kp)ed = t'pq + kp

因为 m=kp,n=pq,所以

med ≡ m (mod n)

原式得到证明。

(完)

关于本文

本文授权转载自阮一峰的网络日志

0
为您推荐

41 Responses to “RSA算法原理(二)”

  1. 东方木说道:

    rsa加密算法原理。讲得透彻,赞。

  2. Civ说道:

    又见Alice 和 Bob, 好久没见到他们了 ^_^

  3. 的了哈说道:

    如果你不想搞明白数学原理是怎样的,而又想了解RAS算法是如何实现这种看似不可能的密钥和密文放在一起却无法破解的难题,那么请看我的简要分析。
    1.bob和alice正在通讯,bob的回复是极为机密的,只有alice一个人才可以知道,被别人知道的话,alice和bob的几亿元的财富就被别人所占有了。
    2.alice问bob,你给我发过来我想要的答案,顺便给了bob一个几千位的字符串【A】。这句话被几万人所传阅,所有的人都看到了alice想要bob的答案,也看到了这个几千位的字符串【A】。这个字符串【A】是由一种大家都明白的方法生成的。由两个只有alice知道的字符串【A1】【A2】通过这种大家都明白的数学方法得到一个超级无敌长的字符串【A】。这个方法的好处就是,全世界只有alice才知道怎么把这个字符串【A】分解成之前的两个字符串【A1】【A2】,而别人想要分解的话,需要几万年的时间。其实,在这个特例中,别人只要一个月以上才可以破解的话,alice就已经没有任何需要担心的了,信息的时效性是非常重要的。如果这个字符串可以被别人一个月破解,那么alice只需要把这个字符串提高几位,这就需要几十年才可以破解了。
    3.bob和所有人都受到了这条信息,于是bob就把自己的答案【Answer】通过特定的方法与alice给的字符串【A】融合,生成一个复杂的字符串【B】。由于这种深奥的数学原理的特性,造成了这么一个结果:只有alice的两个字符串【A1】【A2】才可以用作拆分bob的字符串【B】的工具,如果没有alice的两个字符串【A1】【A2】,那么bob的回答【B】也是无法破解的。此时需要注意的是,bob也不知道【A1】【A2】是什么,而且如果bob忘记了自己的回答【Answer】,那么他自己也无法从【B】中破解出自己的真实回答【Answer】,bob只是利用了alice给的字符串【A】结合自己的真实回答【Answer】才生成了【B】。如果bob没有用【A】反而直接回答:“我们公司正在研究xxxx”【Answer】,那么所有人都呵呵了。
    4.所有人都在费力破解【B】的时候,Alice利用【A1】【A2】很容易的就分解了【B】,从而得到了准确的答复【Answer】。
    5.以上只是alice单方面的加密,如果bob给了Alice一个长字符串【C】,这是由【C1】【C2】生成的,那么双方的通信内容将全都不可知。

    综上所述,
    alice:【A1】+【A2】→【A】
    bob:【Answer】+【A】→【B】
    alice:【B】→利用【A1】【A2】作为工具→【Answer】
    其中【A】→【A1】+【A2】几乎无法实现
    【B】→【Answer】不借助【A1】+【A2】也是几乎无法实现
    至于算法如何,那就是数学家的事了。
    以上纯属一派胡言,只是作为帮助我自己理解用的。

    • hotechboy说道:

      这样理解通俗易懂。完全可以的。呵呵。
      只是细节不同,公钥包含的是乘积 A1*A2 而已。具体的算法不用关心了。

  4. yy说道:

    分解大数很不容易,但是加密者找大素数也是很不容易啊,估计不会是暴力寻找,而是在类似素数库里找。那么是不是就看,谁的素数库够大了?

  5. sheldon说道:

    绝大多数外行人都不知道数论有如此巨大的用处吧?

  6. airaria说道:

    上标全都没了啊...

  7. E说道:

    m与n互质部分的证明写得不清楚,好像还有些错误

  8. E说道:

    指数的地方应该用明确的指数符号标记出来

  9. cruelworm说道:

    一个大数A,求其进行大数B次方后对大数C次方的模
    这个有什么容易简便的算法?
    总不至于计算机要真的乘方那么多次吧

  10. k19说道:

    鲍勃和爱丽丝堪比李雷和韩梅梅啊,不晓得在说些什么悄悄话,求大神破解

  11. Deria说道:

    信息领域外行,瞎问几句
    由此看来,RSA的信息加密通过数学过程也不复杂;那么用于网络安全系统加密,是否意味着黑客破解的不可能?可为什么经常有黑客攻破某某系统的新闻呢?

    • Pasternak说道:

      黑客想直接攻破RSA加密是不可能的,但是系统还有别的漏洞,用户本身也有漏洞,这些是可以攻破的。比方说,用户在多个系统中使用相同的email和密码,那么只要有一个系统的密码泄漏,黑客就可以尝试用于其它系统。一个企业的防火墙可能难以突破,但往往有些员工为电脑设置远程控制,从而在家工作。那么只要能侵入他家里的电脑,就有可能进入远程控制的企业电脑,并进而入侵企业的其它电脑。

      今天还看到一个例子,说美国安全局可以侵入iPhone,采用的办法不是直接破解iPhone,那是极端困难的,而是侵入电脑,当用户的iPhone连接电脑的时候,就可以通过电脑侵入手机。

    • Biaaaa说道:

      并且在实际通讯中,并不一定都使用RSA加密,所有的非对称加密都相对更需要计算机的运算能力。有的时候要考虑实际(1)通讯是否需要那么机密,(2)通讯的响应时间,(3)网络传输的误码与校正。
      而且网络攻击有很多方法,很多时候不是破解,而是暴力致使瘫痪,或者采用身份冒充。RSA只能保证信息在传递过程中安全。至于身份问题,正好像下边说的,期待一下作者讲解数字签名。

  12. 黑暗之蛊说道:

    期待作者讲一讲另外一个重要应用:数字签名技术

  13. 三江说道:

    有一点不太明白,在私钥证明中,出现kp (mod q),这是不是说明kp也就是m一定小于q,这不合理啊

  14. xiaocos说道:

    分解的那个数把我看晕了

  15. neusxw说道:

    “爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式:

    6517 ≡ 2790 (mod 3233)”,6517 怎么来的?前文介绍的时候不是乘吗?这怎么变成连接了?

  16. neusxw说道:

    证明部分写的一塌糊涂!

  17. hrers说道:

    RSA算法原理(三)?
    尚未涉及不R S A 算法的精髓,请 继续讲解RSA 为什么是不可逆的?

  18. 0O说道:

    还想知道MD5加密算法

  19. 不吃豆子说道:

    指数的符号都漏掉了

    加密:
    c ≡ m^e (mod n)

    解密:
    m≡ c^d (mod n)

  20. versugw www.kuaipu.com.cn说道:

    感恩节,感谢分享

  21. 还想知道更多算法说道:

    1,这能说明一下为什么证明p=np美国五角大楼就要破产吗?
    2,阮先生的确厉害。
    3,作者涉猎也很广啊!

  22. 不吃豆子说道:

    格式坏掉了,还是原版比较清晰:
    http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

  23. benf说道:

    证明部分写得是一塌糊涂+1,次幂没了不说,连后面的算法都很奇怪,那个6517到底是怎么回事?

  24. panqiuhui说道:

    证明部分的公式写的太乱了。。。

  25. MD5不是加密算法说道:

    作者不负责任啊,居然懒得把指数运算标出来,弄成乘积,只能让人越看越糊涂,呵呵

  26. 世慷说道:

    很通熟易懂!

  27. 被打的松鼠说道:

    非对称

  28. live.it说道:

    大概什么看明白了这个大道理了,至于中间的那么多证明,全是靠脑补的了

  29. good说道:

    模板元素并不是唯一的吧?那说明公私钥并不是成对的?
    e和n为公钥,d为e的模反元素,d并不唯一的话,私钥(d,n)就有多个了?
    还是说模反元素是唯一的?

  30. kok说道:

    SHA256算法才是王道,RSA算法被NSA留有后门

  31. 匿名说道:

    怎么传递私钥,对方怎么知道私钥

Leave a Reply