作者： 阮一峰

日期： 2013年7月 4日

上一次，我介紹了一些數論知識。

有了這些知識，我們就可以看懂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：

　　m^e ≡ c (mod n)

愛麗絲的公鑰是 (3233, 17)，鮑勃的m假設是65，那么可以算出下面的等式：

　　65¹⁷ ≡ 2790 (mod 3233)

于是，c等于2790，鮑勃就把2790發給了愛麗絲。

（2）解密要用私鑰(n,d)

愛麗絲拿到鮑勃發來的2790以后，就用自己的私鑰(3233, 2753) 進行解密。可以證明，下面的等式一定成立：

　　c^d ≡ m (mod n)

也就是說，c的d次方除以n的余數為m。現在，c等于2790，私鑰是(3233, 2753)，那么，愛麗絲算出

　　2790²⁷⁵³ ≡ 65 (mod 3233)

因此，愛麗絲知道了鮑勃加密前的原文就是65。

至此，"加密--解密"的整個過程全部完成。

我們可以看到，如果不知道d，就沒有辦法從c求出m。而前面已經說過，要知道d就必須分解n，這是極難做到的，所以RSA算法保證了通信安全。

你可能會問，公鑰(n,e) 只能加密小于n的整數m，那么如果要加密大于n的整數，該怎么辦？有兩種解決方法：一種是把長信息分割成若干段短消息，每段分別加密；另一種是先選擇一種"對稱性加密算法"（比如DES），用這種算法的密鑰加密信息，再用RSA公鑰加密DES密鑰。

九、私鑰解密的證明

最后，我們來證明，為什么用私鑰解密，一定可以正確地得到m。也就是證明下面這個式子：

　　c^d ≡ m (mod n)

因為，根據加密規則

　　ｍ^e ≡ c (mod n)

于是，c可以寫成下面的形式：

　　c = m^e - kn

將c代入要我們要證明的那個解密規則：

　　(m^e - kn)^d ≡ m (mod n)

它等同于求證

　　m^ed ≡ m (mod n)

由于

　　ed ≡ 1 (mod φ(n))

所以

　　ed = hφ(n)+1

將ed代入：

　　m^hφ(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，所以

　　m^ed ≡ m (mod n)

原式得到證明。

（完）

留言（124條）

楊琪 說：

數學乃萬物之源吶

2013年7月 4日 12:47 | # | 引用

會林 說：

第一時間過來感謝阮先生無私奉獻如此易懂的算法原理！

2013年7月 4日 12:52 | # | 引用

我叫小井 說：

終于體會到什么叫“深入淺出”

2013年7月 4日 12:53 | # | 引用

Black 說：

受益匪淺，謝謝！

2013年7月 4日 14:10 | # | 引用

joymufeng 說：

又一篇好文，感謝阮兄的無私分享！

2013年7月 4日 15:47 | # | 引用

Du 說：

如果量子計算機實現的話是不是就能破解了?

2013年7月 4日 17:33 | # | 引用

Ray 說：

引用Du的發言：

如果量子計算機實現的話是不是就能破解了?

RSA的困難性是基于大整數因子分解在計算上不可行，如果計算能力上去的話，當然是可以破解現有的密碼。

2013年7月 5日 02:38 | # | 引用

RayJoy 說：

引用楊琪的發言：

數學乃萬物之源吶

數學自有其獨特的魅力。

2013年7月 5日 08:46 | # | 引用

t.k. 說：

九的子標題（2）m與n不是互質關系中

考慮到這時k與q必然互質

應該是“m與q必然互質”。

另外，數學公式用mathjax會更好看一些。

2013年7月 5日 16:56 | # | 引用

asdf 說：

[(kp)q-1]h(p-1) × kp ≡ kp (mod q)
可以直接一步得到結論了，何必之后那幾步推導？

2013年7月 5日 18:48 | # | 引用

iljyya 說：

沒看懂好傷心。

2013年7月 7日 08:33 | # | 引用

zhangyuqin 說：

不太明白，繼續琢磨一下！

2013年7月 8日 10:34 | # | 引用

zz 說：

第四步計算模反元素下面這倆式子貌似符號弄錯了～

ex + φ(n)y = 1
已知 e=17, φ(n)=3120，
　 　17x + 3120y = 1

2013年7月 9日 00:06 | # | 引用

軟件局局長 說：

當年數學沒學好，看得快哭了。

2013年7月17日 09:42 | # | 引用

鄒鄒 說：

只看懂了個大概，不過對RSA算法有一個很好的印象了。這真是一篇好文章呀，阮兄的文章沒有白付費呀。

2013年8月10日 16:56 | # | 引用

felix021 說：

別說DES……這個加密算法因為太容易被破解早就被廢除了，建議改成3DES或AES.

2013年8月14日 10:57 | # | 引用

waveacme 說：

精彩啊，這兩篇文章

2013年8月14日 13:16 | # | 引用

wusuopubupt 說：

精彩！！！

2013年8月16日 12:02 | # | 引用

STL 說：

謝謝你的文章。想問個問題，那個鮑勃向愛麗絲發消息的例子是單向的，如果愛麗絲想回復的話該怎么辦呢？這時候是不是必須先協商一個密鑰然后對稱加密？

2013年9月10日 12:15 | # | 引用

nkAmerica 說：

引用asdf的發言：

[(kp)q-1]h(p-1) × kp ≡ kp (mod q)
可以直接一步得到結論了，何必之后那幾步推導？

為了讓mod作用于n，而不是q。

2013年9月10日 17:17 | # | 引用

nkAmerica 說：

引用STL的發言：

謝謝你的文章。想問個問題，那個鮑勃向愛麗絲發消息的例子是單向的，如果愛麗絲想回復的話該怎么辦呢？這時候是不是必須先協商一個密鑰然后對稱加密？

根本沒有協商過程啊。都是用對方的公鑰加密

2013年9月10日 17:19 | # | 引用

Lynx 說：

謝謝博主的文章。
請問一下，
m^e ≡ c (mod n)這公式怎么來的？
只是e跟φ(n)互質啊

2013年9月24日 15:42 | # | 引用

李華 說：

想到這個算發的人太偉大了，這是一個回答純數學有什么用的最好案例。還有沒有其他的像RSA這樣簡單有效的非對稱加密方法呢？恐怕像找外星人一樣難了。

2013年10月 9日 14:16 | # | 引用

frank 說：

引用felix021的發言：

別說DES……這個加密算法因為太容易被破解早就被廢除了，建議改成3DES或AES.

DES廢除的原因一個是密鑰位數太少，在現在的計算能力下，已經無法保證安全，第二個原因是，DES是為硬件加密設計的，對于現在軟件來說計算效率不夠好，第三個原因是，一直有人懷疑DES的S盒中隱藏著后門，而這個后門被美國安全局掌握。所以提出了AES

3DES理論密鑰長度為56*3=168bits，但是，在受到中間人攻擊的條件下，退化為112bits。其安全性仍然不夠好

2013年10月15日 22:52 | # | 引用

Martin.Hsuching 說：

寫的很不錯，淺顯易懂，但看完，覺得最后一段有個疑惑，請教一下：(kp)ed = tq + kp
這時t必然能被p整除，即 t=t'p，這個必然性是如何證明的？請指導下~~謝謝

2013年10月28日 21:44 | # | 引用

LCS 說：

為什么公匙不能猜測的進行解密呢。。。

2013年11月 2日 23:14 | # | 引用

錦衣衛加密顧問 說：

正在做加密產品，以應對來自霉國的竊聽威脅，感謝樓主的理論分析。

2013年11月 3日 03:51 | # | 引用

Chil 說：

這兩篇文章寫的太好了，對RSA算法淺入深出，讓我明白很多。但有一個地方沒看明白：博主寫道

加密就是算出 me ≡ c (mod n)中的c

我想問一下，為什么要這樣做？和上篇文章中什么地方有聯系？還是就是這么規定的？

2013年11月11日 07:27 | # | 引用

哇哈哈 說：

此時，由于n等于質數p和q的乘積，所以m必然等于kp或kq

這個怎麼得來的?
m不是明文嗎,明文爲什麼一定等於kp或者kq?

2013年11月11日 16:35 | # | 引用

guanwh 說：

引用STL的發言：

謝謝你的文章。想問個問題，那個鮑勃向愛麗絲發消息的例子是單向的，如果愛麗絲想回復的話該怎么辦呢？這時候是不是必須先協商一個密鑰然后對稱加密？

想雙向通信的話肯定要定義兩套公鑰和秘鑰了，都用對方的公鑰加密發送，然后接收方用自己的秘鑰解密就OK了！

2013年11月19日 20:29 | # | 引用

明天有風吹 說：

終于明白rsa是怎么一回事了，thanks！！

2013年11月26日 16:15 | # | 引用

L 說：

引用Ray的發言：

RSA的困難性是基于大整數因子分解在計算上不可行，如果計算能力上去的話，當然是可以破解現有的密碼。

量子計算機是并行的，1024位的密碼用1024個量子處理單元做計算，只要1秒。只是現在技術最多能做到8位量子處理單元的級別。so...

2013年12月12日 19:54 | # | 引用

Leon 說：

引用Martin.Hsuching的發言：

寫的很不錯，淺顯易懂，但看完，覺得最后一段有個疑惑，請教一下：(kp)ed = tq + kp
這時t必然能被p整除，即 t=t'p，這個必然性是如何證明的？請指導下~~謝謝

兩邊同時整除p，又p、q互質，于是t必定是p的整數倍。

2013年12月30日 21:08 | # | 引用

Leon 說：

引用哇哈哈的發言：

此時，由于n等于質數p和q的乘積，所以m必然等于kp或kq

這個怎麼得來的?
m不是明文嗎,明文爲什麼一定等於kp或者kq?

數學角度：m、n不是互質關系，說明m、n必定含有非1公因子，而n等于質數p和q的乘積，因此m必然等于kp或kq。

2013年12月30日 21:16 | # | 引用

Gavin 說：

一直在使用RSA，但是不是很清楚RSA的數學原理，今天一看，勝讀幾年書！！！

1、to 哇哈哈：
此時，由于n等于質數p和q的乘積，所以m必然等于kp或kq
因為m與n不是互質關系，說明m與n有共同的公因子g，假設m=hg，由于n=pq，p與q互質，n只有p和q兩個因子，所以g和h必然有一個等于q或者p， 所以才有結論“m必然等于kp或kq”

2、to Martin.Hsuching ：
因為(kp)ed = tq + kp,=>(p)ed*(k)ed = tq + kp,=>
(p)ed*(k)ed - kp = tq,=>
p[(p)(ed-1)*(k)ed - k ] = tq,
左邊是p的倍數，那右邊必然也是p的倍數。因為p與q互質，所以t必然是p倍數，即 t=t'p

3、

2013年12月31日 16:43 | # | 引用

趙三 說：

引用Gavin的發言：

一直在使用RSA，但是不是很清楚RSA的數學原理，今天一看，勝讀幾年書！！！

1、to 哇哈哈：
此時，由于n等于質數p和q的乘積，所以m必然等于kp或kq
因為m與n不是互質關系，說明m與n有共同的公因子g，假設m=hg，由于n=pq，p與q互質，n只有p和q兩個因子，所以g和h必然有一個等于q或者p， 所以才有結論“m必然等于kp或kq”

2、toMartin.Hsuching ：
因為(kp)ed = tq + kp,=>(p)ed*(k)ed = tq + kp,=>
(p)ed*(k)ed - kp = tq,=>
p[(p)(ed-1)*(k)ed - k ] = tq,
左邊是p的倍數，那右邊必然也是p的倍數。因為p與q互質，所以t必然是p倍數，即 t=t'p

3、

幫我理解了不少，感謝！還有一點向您請教下：1.“（1）m與n互質。根據歐拉定理，此時mφ(n) ≡ 1 (mod n)得到(mφ(n))h × m ≡ m (mod n)”這個是怎么得到啊？(mφ(n))h≡1(mod n)這樣寫，對嗎？接著，后面又多乘以個m,就能變成這樣啦(mφ(n))h × m ≡ m (mod n)，這個是為什么呢？2.這個跟1.應該是同樣的問題“(kp)q-1 ≡ 1 (mod q)進一步得到[(kp)q-1]h(p-1) × kp ≡ kp (mod q)”這個也是，左右都乘以kp，這是為什么呢？3.這個是我看RSA算法原理（一）中的疑問：“因此，7的任意次方的個位數（例如7的222次方），心算就可以算出來”這是怎么得到的呢？我只想到了：7的222次方=7的2次方*7的（4*55）次方，下面就不知道了。還望解惑，不勝感激~

2014年1月 2日 15:19 | # | 引用

趙三 說：

引用Gavin的發言：

一直在使用RSA，但是不是很清楚RSA的數學原理，今天一看，勝讀幾年書！！！

1、to 哇哈哈：
此時，由于n等于質數p和q的乘積，所以m必然等于kp或kq
因為m與n不是互質關系，說明m與n有共同的公因子g，假設m=hg，由于n=pq，p與q互質，n只有p和q兩個因子，所以g和h必然有一個等于q或者p， 所以才有結論“m必然等于kp或kq”

2、toMartin.Hsuching ：
因為(kp)ed = tq + kp,=>(p)ed*(k)ed = tq + kp,=>
(p)ed*(k)ed - kp = tq,=>
p[(p)(ed-1)*(k)ed - k ] = tq,
左邊是p的倍數，那右邊必然也是p的倍數。因為p與q互質，所以t必然是p倍數，即 t=t'p

3、

幫我理解了不少，感謝！還有一點向您請教下：

1.“（1）m與n互質。

根據歐拉定理，此時mφ(n) ≡ 1 (mod n)

得到(mφ(n))h × m ≡ m (mod n)”這個是怎么得到啊？(mφ(n))h≡1(mod n)這樣寫，對嗎？接著，后面又多乘以個m,就能變成這樣啦(mφ(n))h × m ≡ m (mod n)，這個是為什么呢？

2.這個跟1.應該是同樣的問題“(kp)q-1 ≡ 1 (mod q)

進一步得到[(kp)q-1]h(p-1) × kp ≡ kp (mod q)”這個也是，左右都乘以kp，這是為什么呢？

3.這個是我看RSA算法原理（一）中的疑問：“因此，7的任意次方的個位數（例如7的222次方），心算就可以算出來”這是怎么得到的呢？我只想到了：7的222次方=7的2次方*7的（4*55）次方，下面就不知道了。還望解惑，不勝感激~

2014年1月 2日 17:52 | # | 引用

dongxf 說：

如果量子計算機可以破解1024bit的RSA,那么可以用量子計算機做更長bit位的加密,比如2048bit...,直到無法破解

2014年1月 5日 17:07 | # | 引用

none 說：

to:趙三

1，(mφ(n))h≡1(mod n)這樣寫是對的，這個可以通過≡的含義，然后通過一個推導（也就是從h-1到h的推導）可以看出是正確的。比如設(mφ(n))h=r1*n+1,然后(mφ(n))h*m=(r1*n+1)*m,這個和n的余數就是m。

2，RSA算法原理（1）中回復里面有這個問題。7的（4*55）的余數就是1，然后7的2次方的余數為9，那結果就是9

2014年1月 7日 21:26 | # | 引用

colde 說：

證明
　　(m^e - kn)^d ≡ m (mod n)
等同于證明
　 m^ed ≡ m (mod n)

卡住在這里了,麻煩幫忙解釋一下。

2014年1月12日 10:40 | # | 引用

八戒 說：

相當詳實生動，非常感謝，，，，就是舉例子的數字有點大了，，普通計算機直接正無窮大了，，，

2014年1月12日 22:59 | # | 引用

ssapym 說：

問個問題，
1，這個巨大的質數或那兩個相乘質數從哪來的，2048位的從哪來的。RSA算法的可靠性依賴于大整數的因數分解，是一件非常困難的事情，那大整數現在最大到多少了，2048位以上的現在有么，好像還有什么美國輸出限制。
2，如果分解困難，用現在產生大質數的算法，是否可以反推出來大質數，產生一個對應列表，就像md5的彩虹表，是否就可以破解。

謝謝

2014年1月13日 15:32 | # | 引用

王為雄 說：

你好，我覺得第五步驟里面：
所謂"模反元素"就是指有一個整數d，可以使得ed被φ(n)除的余數為1。

這句話后半句，應該是使得 φ(n) 被ed除的余數為1。

這是來自wiki的除法舉例:
15 可以被 5 整除，記作 5|15。

文章中本意應該是ed除以φ(n)的余數是1的邏輯。

2014年1月14日 10:37 | # | 引用

luke 說：

其它都很清晰，第5步跳的太快了：
ed ≡ 1 (mod φ(n))
怎么就得到
ed - 1 = kφ(n)? K從哪里來？是不是從第一篇中這里來（b+kn 都是a的模反元素）？
再變成
ex + φ(n)y = 1，這時候K是不是就是Y了？X就是D了？

2014年1月19日 22:57 | # | 引用

luke 說：

引用luke的發言：

其它都很清晰，第5步跳的太快了：
ed ≡ 1 (mod φ(n))
怎么就得到
ed - 1 = kφ(n)? K從哪里來？是不是從第一篇中這里來（b+kn 都是a的模反元素）？
再變成
ex + φ(n)y = 1，這時候K是不是就是Y了？X就是D了？

問了一下同事，明白了！！！ ed ≡ 1 (mod φ(n)) 意味著，ed除以φ(n)余1，于是，ed-1就能被φ(n)整除。能被整除就意味著 ed-1=kφ(n)，k是任意一個整數。

2014年1月20日 17:53 | # | 引用

luke 說：

引用colde的發言：

證明
　　(m^e - kn)^d ≡ m (mod n)
等同于證明
　m^ed ≡ m (mod n)

卡住在這里了,麻煩幫忙解釋一下。

唉，我也卡在這里了。求高人繼續。

2014年1月21日 15:48 | # | 引用

luke 說：

引用luke的發言：

唉，我也卡在這里了。求高人繼續。

想通了。(m^e - kn)^d 等同于 m^(ed)-kn

而 (m^e - kn)^d ≡ m (mod n)

意味著，(m^e-kn)^d - m = kn

所以，m^(ed)-kn - m = kn

得到，m^(ed) - m = 2kn => m^(ed) - m = kn （這里k只是代表一個整數倍的關系，值并不重要）

而 m^(ed) - m = kn 正意味著 m^(ed) ≡ m (mod n)

2014年1月21日 17:23 | # | 引用

mine260309 說：

引用ssapym的發言：

問個問題，
1，這個巨大的質數或那兩個相乘質數從哪來的，2048位的從哪來的。RSA算法的可靠性依賴于大整數的因數分解，是一件非常困難的事情，那大整數現在最大到多少了，2048位以上的現在有么，好像還有什么美國輸出限制。
2，如果分解困難，用現在產生大質數的算法，是否可以反推出來大質數，產生一個對應列表，就像md5的彩虹表，是否就可以破解。

謝謝

2^1024大約是10^308這個數量級，包含的素數可以由素數定理知道大約是x/ln(x)這個數量級，可選的素數p和q太多了，p*q的組合就更多了，怎么做彩虹表？
彩虹表是基于有一些常用的密碼（比如password, 123456）算出來的，你隨機選一個密碼，多半不會出現在彩虹表中。同理，你隨機選兩個p,q，怎么查彩虹表？

2014年1月24日 11:23 | # | 引用

鹿 說：

找到高人了，寫得清楚，有例子，每步都寫出原理。

2014年2月14日 22:00 | # | 引用

gk 說：

謝謝阮老師深入淺出的講解，我知道了RSA算法是怎么回事兒了。
我感覺那些嚴謹的證明過程不必細致追究，主要是搞清楚RSA算法是什么，除非那些數學專業的。

2014年2月18日 21:47 | # | 引用

介木 說：

我無法讀懂上面的數學公式.
請問,高中水平的我,需要學習那些書本,才能看懂上面的公式呢?
謝謝各位.

我懂質數

2014年2月24日 14:57 | # | 引用

David 說：

引用介木的發言：

我無法讀懂上面的數學公式.
請問,高中水平的我,需要學習那些書本,才能看懂上面的公式呢?
謝謝各位.

我懂質數

高中確實不涉及這方面的知識。找點關于余數的數論書看，知道基本的同余定理就行了。

2014年2月24日 20:38 | # | 引用

llxxtnt 說：

我有個問題

根據　　　c^d ≡ m (mod n)

加密者不知道私鑰d，但是他知道明文m，密文c，以及n，是否可以推算出私鑰d

2014年3月 4日 13:57 | # | 引用

llxxtnt 說：

還有一個問題，我是做金融的，在金融領域經常用到轉加密這個概念
1. 老張先用公鑰e1對明文m加密得到密文c1，然后將密文c1傳遞給老王
2. 老王收到密文c1后，用公鑰e2替換公鑰e1，得到密文c2

我想知道公鑰e2替換公鑰e1的具體過程
是先用私鑰d1解密密文c1，還原出明文m以后，再用公鑰e2對明文m加密得到密文c2
還是在一個原子過程中，直接就可以用私鑰d1，公鑰e2，密文c1計算出新密文c2，在計算過程中可以避免出現明文m？

2014年3月 4日 14:38 | # | 引用

袁定平 說：

您好，以前看過你的這篇文章了，最近在看一個系統teamcity的登錄過程，它會先給用戶發一個公鑰，然后用這個公鑰對密碼進行加密，發給服務器，從我看來，好像每次它發過來的公鑰都是同一個串，是不是說只要有足夠的計算力和足夠的時間，我從這個公鑰推出了其中的私鑰，就可以破解用戶發給它的所有密碼？
我比較困惑的是，如果一個系統的安全系數要求很高的話，不需要經常更換公鑰嗎？
有沒有可能一個經常破解密碼的人，在一個地方看到一個公鑰正好是他之前破解過的，那他也就能輕易破解新系統的密碼？ 我們所能使用的公鑰理論上市無限的嗎？

希望能夠解答，謝謝

2014年3月 7日 16:54 | # | 引用

tommyqian_2008 說：

第四步，隨機選擇一個整數e，條件是1

e不一定要小于φ(n)吧，根據歐拉定律，e只要跟φ(n) 互質就可以了

求大神解惑

2014年5月 9日 11:09 | # | 引用

hai 說：

引用袁定平的發言：

您好，以前看過你的這篇文章了，最近在看一個系統teamcity的登錄過程，它會先給用戶發一個公鑰，然后用這個公鑰對密碼進行加密，發給服務器，從我看來，好像每次它發過來的公鑰都是同一個串，是不是說只要有足夠的計算力和足夠的時間，我從這個公鑰推出了其中的私鑰，就可以破解用戶發給它的所有密碼？
我比較困惑的是，如果一個系統的安全系數要求很高的話，不需要經常更換公鑰嗎？
有沒有可能一個經常破解密碼的人，在一個地方看到一個公鑰正好是他之前破解過的，那他也就能輕易破解新系統的密碼？ 我們所能使用的公鑰理論上市無限的嗎？

希望能夠解答，謝謝

個人觀點：
1，公鑰本來就是公開的，沒有必要更換；
2，公鑰不可能（所需時間和計算力無比的巨大）推算出私鑰；
3，首先一個人不可能破解過一個公鑰。其次是簡單的算法，私鑰對應一個確定的公鑰，這是有風險的，所以現在的加密算法還使用了隨機數，破解不可能，運氣更不可能。

2014年6月 5日 17:46 | # | 引用

啊啊 說：

引用STL的發言：

謝謝你的文章。想問個問題，那個鮑勃向愛麗絲發消息的例子是單向的，如果愛麗絲想回復的話該怎么辦呢？這時候是不是必須先協商一個密鑰然后對稱加密？

每個個體都有自己的公鑰和私鑰，在通信中，故愛麗絲也有自己的公鑰和私鑰。

2014年6月 8日 16:18 | # | 引用

jimohou 說：

引用Martin.Hsuching的發言：

寫的很不錯，淺顯易懂，但看完，覺得最后一段有個疑惑，請教一下：(kp)ed = tq + kp
這時t必然能被p整除，即 t=t'p，這個必然性是如何證明的？請指導下~~謝謝

(kp)^ed = tq + kp => tq = (kp)(kp^ed-1 - 1)
因為p,q是互質,所以kp必然不能整除q,那么就必然整除t,t=t'p

2014年6月26日 15:32 | # | 引用

littlephoenix@163.com 說：

引用ssapym的發言：

問個問題，
1，這個巨大的質數或那兩個相乘質數從哪來的，2048位的從哪來的。RSA算法的可靠性依賴于大整數的因數分解，是一件非常困難的事情，那大整數現在最大到多少了，2048位以上的現在有么，好像還有什么美國輸出限制。
2，如果分解困難，用現在產生大質數的算法，是否可以反推出來大質數，產生一個對應列表，就像md5的彩虹表，是否就可以破解。

謝謝

引用mine260309的發言：

2^1024大約是10^308這個數量級，包含的素數可以由素數定理知道大約是x/ln(x)這個數量級，可選的素數p和q太多了，p*q的組合就更多了，怎么做彩虹表？
彩虹表是基于有一些常用的密碼（比如password, 123456）算出來的，你隨機選一個密碼，多半不會出現在彩虹表中。同理，你隨機選兩個p,q，怎么查彩虹表？

我的看法：
p*q的積的二進制的位數如果固定并確定為1024，則p和q的取值只能在一定范圍內取，這在RSA密鑰生成軟件中自然會有指定。如果所有的密鑰生成機制都按同一規定，那么由于素數資源不是隨機無限的（有素數生成機制的限制，有隨意取兩個素數的乘積的二進制位數的限制），設素數資源的個數為n，在有限的素數資源中取出兩個數的可能組合將是C|（2，n）。將每個組合的乘積一一列出，就可以組成彩虹表，可以從乘積列表中查找出對應的素數組合，進而推出公鑰和私鑰。素數資源不夠的軟件產生的密鑰，尤其具有這樣的隱患，看似很安全，實際上人家大的機構很容易破解出私鑰來。所以，生產大素數的機構就像開礦公司，也像數字銀行，擁有的素數資源越多越安全。不知是否可以這樣理解？

不同機構產生的證書（包括私鑰、公鑰）的質量（指安全保證）是良莠不齊的。

我想ssapym彩虹表的本意即在如此。

2014年7月21日 12:40 | # | 引用

alphaqcode 說：

引用luke的發言：

唉，我也卡在這里了。求高人繼續。

　　(m^e - kn)^d ≡ m (mod n)
分解下左邊公式
(m^e - kn)^d = m^ed + [(m^e)^d-1]*kn + [(m^e)^d-2]*kn^2 + ....
除了第一個m^ed,后面的數都含有XXX*kn,所以都能被n整除

　

2014年7月22日 16:23 | # | 引用

xidactw 說：

受益匪淺

2014年7月24日 11:28 | # | 引用

lbs 說：

大哥，那個模反元素有問題
一說：
a* a的[φ(n)-1] % n = 1
二說：
a* a的[φ(n)-1] % φ(n) = 1
明顯不一樣了丫、。。。。

2014年7月24日 21:41 | # | 引用

shindo 說：

這步mφ(n) ≡ 1 (mod n)
到
(mφ(n))h × m ≡ m (mod n)
實在看不懂，能否詳細解釋下？

2014年7月31日 10:09 | # | 引用

shindo 說：

引用shindo的發言：

這步mφ(n) ≡ 1 (mod n)
到
(mφ(n))h × m ≡ m (mod n)
實在看不懂，能否詳細解釋下？

我懂了， mφ(n) ≡ 1 (mod n) => mφ(n) = K n +1 , k為自然數
(kn + 1)^h 展開多項式，除了1以外，全部含有kn， 所以其他項都能被n整除而余1..
也就是能推出 (mφ(n))h ≡ 1 (mod n)
然后m 這個中間數學gap還是挺大的...

2014年7月31日 14:26 | # | 引用

nan 說：

調理清晰，把一個復雜難懂的數學問題，一步一步分解，深入淺出，容易理解，學習了！

2014年8月23日 19:07 | # | 引用

Jayce 說：

文章超贊……
要是你能加上怎么快速生成的方法，相信對讀者更有幫助，因為我找到這篇文章是因為我想快速生成公鑰私鑰來用，而我又是剛接觸linux：
ssh-keygen -t rsa

2014年9月 4日 10:42 | # | 引用

ax_pokl 說：

RSA加密解密算法中，已知公鑰和密匙n,e,d，是否能將合數n=p*q分解？

先溫故一下RSA算法：
1、兩個大質數p,q。
2、模數n=p*q。
3、歐拉函數f=(p-1)(q-1)。
4、隨機數e，15、模逆d，即最小整數d，e*d=1 mod f。
也就是說：
知道了p,q也就知道了n,f；
知道了f,e也就知道了d。

下面溫故一下加密解密算法：
已知明文m，滿足m加密：密文c=m^e mod n。
解密：明文x=c^d mod n。

證明一下解密得到的明文x=m：
由c=m^e mod n，得c=m^e+k*n。
代入x=c^d mod n，得x=(m^e+k*n)^d mod n。
于是x=m^e^d mod n，即x=m^(e*d) mod n。
由于e^d=1 mod f，得e*d=k*f+1。
代入得x=m^(kf+1) mod n，x=m*m^(kf) mod n。
當m與n互質時，x=m*(m^f)^k mod n,由歐拉定理可知x=m mod n。
又m當m與n不互質時，由于n=p*q且m若m=kp，則m^(q-1)=(k*p)^(q-1)=1 mod q。
接著[(k*p)^(q-1)]^[k*(p-1)]*kp=kp mod q，即(k*p)^(e*d)=k*p mod q。
又由于(k*p)^(ed)=k*q+k*p，(k*p)^(ed)=k*q*p+k*p，。
所以m^(ed)=m mod n，x=m。
即證。

2014年9月 9日 22:05 | # | 引用

ax_pokl 說：

現在考慮以下問題：
已知n和d，是否能將n分解？
可將這個問題分為幾個問題：
1、已知n和f，是否能將n分解？
2、已知n,e和d，是否能得到f？
3、已知n和d，是否能得到e？
4、已知d和f，是否能得到e？
對于問題1的回答是肯定的。
n-f+1=sum=p+q，用二分法厲遍p，得p(sum-p)和n比較大小，即可快速確定p,q的值。
所以知道了n,f，就知道了p和q。也就是說，p,q,n,f四個數知道任意兩個就可以知道全部。
那么，問題2就來了。如果p,q,n,f只知其一，又知道了e和d，是否能知道其它三個數呢？
最常見的情況就是知道了n,e和d。
由e*d=1 mod f，知e*d=k*f+1。
根據的同余方程定理可以知道存在k并且d,k始終互質，由e,f互質又可推出e,k互質和f,d互質。
現在的問題又變為，e,d,f三個數各知道兩個，能否知道第三個數？在已知n的情況下又是如何呢？
已知e,f可知道d，已知e,d不可知道f。
已知d,f，因為d,f互質，所以模逆e必存在，e必然在f的同余類中。又e也就是說，e,f求d和d,f求e的過程是相同的。
這樣，問題4的回答就是肯定的。
我們還可以發現，問題3的回答是否定的。
e和d對于f的地位是等價的，我們顯然不可能用公匙n,e得到密匙n,d，所以反之亦然。
于是我們發現，f是十分重要的。知道了f，那么e和d就能互求。知道了f，那么n,p,q就能互求。
最后我們回到問題2。由于n,p,q的地位是等價的，我們可以換個死路考慮。
在已知p,e,d的情況下能否知道f和n？由e*d=k*f+1可以算出k*f。
然后又知道了p，可以算出k*(p-1)(q-1)/(p-1)=k*(q-1)。
然而這樣組合的數量是很多的，如果不知打k，我們不可能知道q。所以知道p,e,d不能知道f或n。
那么知道n,e,d，也就是知道n和k*f，也就是知道p*q和k(p-1)(q-1)的情況下呢？
由于k是不可知的，k值的不同會導致f產生很大的變化。
我們雖然知道上限n，但直接拿f去除以n顯然不能得到正確的k。
由于p和q的差值可能很大也可能很小，所以除出來的結果可能十分接近k也可能和k差很多。
于是無法縮小搜索p和q的范圍，也無從使用二分法。
所以我認為，已知n,e,d是無法得到f的，同樣也無法得到p和q。

如果大家有辦法分解n的話，求詳細的算法。

2014年9月 9日 22:05 | # | 引用

陳佳 說：

正在查rsa的資料，又回到了這里，想自己實現一個簡易的rsa。

2014年9月 9日 22:50 | # | 引用

盧磊 說：

引用Leon的發言：

兩邊同時整除p，又p、q互質，于是t必定是p的整數倍。

這種解釋說法就是“雞生蛋，蛋生雞”問題，拿著要證明的結果作為證明的已知條件來證明問題！！！

2014年9月13日 23:15 | # | 引用

link 說：

第一次看懂了rsa算法, 真是好文章

2014年9月13日 23:24 | # | 引用

盧磊 說：

引用shindo的發言：

我懂了， mφ(n) ≡ 1 (mod n) => mφ(n) = K n +1 , k為自然數
(kn + 1)^h 展開多項式，除了1以外，全部含有kn， 所以其他項都能被n整除而余1..
也就是能推出 (mφ(n))h ≡ 1 (mod n)
然后m
這個中間數學gap還是挺大的...

去看數論中同余性質吧，

性質5：若a≡b（mod m），c≡d（mod m），那么ac≡bd（mod m）（可乘性）。
性質6：若a≡b（mod m），那么an≡bn（mod m）（其中n為自然數）。

可以看成是
由h個式子相乘，然后再與m≡m(mod n)相乘，這里m得到。。。

引用asdf的發言：

[(kp)q-1]h(p-1) × kp ≡ kp (mod q)
可以直接一步得到結論了，何必之后那幾步推導？

對頭，到這就可以截止了，況且后面證明的很亂

2014年9月14日 00:28 | # | 引用

電小弟 說：

好像和CLRS算法差不多，但是各有各的特點及其長處.

2014年9月14日 03:09 | # | 引用

ax_pokl 說：

突然發現，雙方的公鑰和私鑰對換，還是能夠順利加密和解密的。

2014年9月19日 07:49 | # | 引用

NeroLee 說：

以 m = kp為例，考慮到這時k與q必然互質。

這句話不對吧，比如說m=3n=3qp不行嗎，那么k=3q,哪來必然互質？應該再細分

2014年9月30日 16:52 | # | 引用

zoudaokou2006 說：

引用NeroLee的發言：

以 m = kp為例，考慮到這時k與q必然互質。

這句話不對吧，比如說m=3n=3qp不行嗎，那么k=3q,哪來必然互質？應該再細分

根據RSA規范，要加密的信息m，范圍為0~n-1，所以你說的不成立。

5.1.1 RSAEP
RSAEP ((n, e), m)
Input: (n, e) RSA public key
m message representative, an integer between 0 and n– 1
Output: c ciphertext representative, an integer between 0 and n– 1

2014年10月23日 11:42 | # | 引用

NeroLee 說：

引用zoudaokou2006的發言：

根據RSA規范，要加密的信息m，范圍為0~n-1，所以你說的不成立。

5.1.1RSAEP
RSAEP ((n, e), m)
Input: (n, e) RSA public key
m message representative, an integer between 0 and n– 1
Output: c ciphertext representative, an integer between 0 and n– 1

Thanks. 現在懂了。

2014年10月27日 14:49 | # | 引用

番石榴 說：

我看到了未來的密鑰是1mb起碼。。。。。。

2014年11月11日 09:48 | # | 引用

王軍 說：

65^17 ≡ c (mod 3233)
說等于
65^17 ≡ 2790 (mod 3233)
即c等于2790
想請問下，這里的2790是怎么算出來的？？

2014年11月26日 14:46 | # | 引用

Lin 說：

引用t.k.的發言：

九的子標題（2）m與n不是互質關系中

應該是“m與q必然互質”。

另外，數學公式用mathjax會更好看一些。

“m與q必然互質”沒錯，因為m=kq

2014年11月26日 14:49 | # | 引用

王軍 說：

65^17 ≡ c (mod 3233)
說等于
65^17 ≡ 2790 (mod 3233)
即c等于2790
想請問下，這里的2790是怎么算出來的？？
我指的是口算或者筆算 不是利用計算機算65的17次方除以3233
有沒有簡單算法 如果筆算65的17次方 會死人的。。。

2014年11月26日 15:59 | # | 引用

Jecvay 說：

一口氣看完兩篇, 果然精彩

2014年11月30日 02:07 | # | 引用

wfade 說：

k與q必然互質
卡在這里了

2014年12月18日 16:36 | # | 引用

君升 說：

你好，請教一下：像12306這樣的網站，在使用時要下載他的證書并導入，這時下載的證書是證書請求文件CSR嗎？還是已經經過簽名的公鑰了？

2014年12月22日 12:49 | # | 引用

kellen_yan2014 說：

終于搞懂了，非常感謝！

2014年12月26日 10:54 | # | 引用

漠上花開 說：

剛接觸RSA時看過其他網上的微博，要么是粘貼過來的，要么是片面不詳細。今天看了阮先生描寫的原理，頓時醍醐灌頂，把我所有沒有搞懂的、有疑問的統統說清楚了，特別是數論原理，推導的過程描述的很詳細。還結合實際中的密鑰的長度、實際當中的數值，這些是剛接觸加密算法的時候都有的疑問，這兩篇文章都描寫的非常詳細，真的受益匪淺，而且特別欣賞這種寫作風格，嚴謹、有據。真的謝謝

2015年1月 8日 10:45 | # | 引用

tim 說：

博主寫的文章讓人漲知識！

2015年1月14日 21:38 | # | 引用

tomas 說：

這是我見過的最通俗易懂的解釋！！

2015年1月27日 19:52 | # | 引用

Jack 說：

謝謝lz。
但有個問題，“如果私鑰被攻破，那么消息就會被破解”。這里是不是隱含了解密算法或者是加密算法，可以認為是公開的了，至少是容易獲得的。
如果是這樣，為什么不能從加密算法和已知的公鑰已經加密后的信息，反推出原始信息呢？

2015年2月 3日 14:42 | # | 引用

傅琦佳 說：

您好，我看了網易公開課中的現代密碼學，再看了您的文章感覺清晰很多，但有一點一直不大懂，求d時用到“拓展歐幾里得算法”具體應該怎么算？
我對這方面很有興趣，高中數學競賽也學過一些數論知識(現在大一)，但受專業限制接觸不到這方面知識，打算通過網易公開課自學，純粹出于興趣。希望有機會與您多交流學習。

2015年2月27日 15:29 | # | 引用

小史 說：

引用傅琦佳的發言：

您好，我看了網易公開課中的現代密碼學，再看了您的文章感覺清晰很多，但有一點一直不大懂，求d時用到“拓展歐幾里得算法”具體應該怎么算？
我對這方面很有興趣，高中數學競賽也學過一些數論知識(現在大一)，但受專業限制接觸不到這方面知識，打算通過網易公開課自學，純粹出于興趣。希望有機會與您多交流學習。

百度百科里關于擴展歐幾里得算法有講具體怎么做。

2015年3月11日 15:17 | # | 引用

陳睿 說：

豁然開朗，十分感謝

2015年4月16日 15:47 | # | 引用

袁宇陽 說：

有一個疑問，就是在加密的時候 用的這個式子：m的e次方 ≡ c (mod n) 來計算出的c ，然后之后是把c給了愛麗絲讓愛麗絲拿私鑰去解m，我想問的是這時候知道c，可不可以還用之前那個得出c的式子： m的e次方 ≡ c (mod n) 再反過去解出m，因為這時候n，c，e都已知。m就等于 c (mod n)再開e次方了。 大神快粗來，急，在線等~~

2015年4月25日 14:42 | # | 引用

楊國寶 說：

第二次看了，還是沒看太懂。下次繼續學習。謝謝阮老師

2015年4月29日 17:13 | # | 引用

Caleb 說：

65^17 ≡ 2790 (mod 3233) 這個式子成立嗎？

2790 mod 3233 = 2790

65^17 mod 3233 = 887 (matlab得到的結果)

另外 2790^2753 ≡ 65 (mod 3233) 這個式子中的 2790^2753 這個值，計算機可以算出來嗎？

謝謝

2015年5月29日 18:11 | # | 引用

Codisan 說：

還是有個疑問：
alice 回信的時候，咋整？

bob發信： bob(公鑰加密) -> alice (私鑰解密)，這個邏輯我明白

alice 回信， 這個怎么處理？求解！！

2015年6月12日 20:54 | # | 引用

我大哥海鵬 說：

引用luke的發言：

想通了。
(m^e - kn)^d 等同于 m^(ed)-kn

而 (m^e - kn)^d ≡ m (mod n)

意味著，(m^e-kn)^d - m = kn

所以，m^(ed)-kn - m = kn

得到，m^(ed) - m = 2kn => m^(ed) - m = kn （這里k只是代表一個整數倍的關系，值并不重要）

而 m^(ed) - m = kn 正意味著 m^(ed) ≡ m (mod n)

把(m^e - kn)^d 完全展開后只有一項不包含n的項 m^ed m^ed對n取余就等于 (m^e - kn)^d 對n取余

2015年6月15日 18:49 | # | 引用

我誰也不是 說：

引用Codisan的發言：

還是有個疑問：
alice 回信的時候，咋整？

bob發信： bob(公鑰加密) -> alice (私鑰解密)，這個邏輯我明白

alice 回信， 這個怎么處理？求解！！

bob給alice發信，用的是Alice的公鑰，Alice用自己的私鑰解密；如果Alice要給bob回信，就換成bob的公鑰加密，bob用自己的私鑰解密。

2015年6月18日 13:16 | # | 引用

駱駝 說：

怒贊！！！！

2015年7月10日 11:32 | # | 引用

ax_pokl 說：

引用王軍的發言：

65^17 ≡ c (mod 3233)
說等于
65^17 ≡ 2790 (mod 3233)
即c等于2790
想請問下，這里的2790是怎么算出來的？？
我指的是口算或者筆算不是利用計算機算65的17次方除以3233
有沒有簡單算法 如果筆算65的17次方 會死人的。。。

模冪法：
依次計算65^2 mod 3233, 65^4 mod 3233, 65^8 mod 3233, 65^16 mod 3233，最后再將65^16 mod 3233的結果和65相乘再mod 3233，這樣可以保證最多只要做2*log3(n)次大數乘法和大數取模運算就可以得出結果了。

2015年7月13日 19:50 | # | 引用

悟空 說：

感謝博主，雖然對數學的還沒有完全搞懂，但是基本上能淺顯理解RSA的理論基礎了，感謝感謝。

2015年7月17日 16:24 | # | 引用

lingjie_ding 說：

阮先生好，我在看的時候也會有@袁宇陽 的問題，可以直接拿公鑰和加密后的數據反推出加密之前的數據嗎？

2015年8月16日 17:48 | # | 引用

scateu 說：

"以 m = kp為例，考慮到這時k與q必然互質，則根據歐拉定理，下面的式子成立："

這一句疑似應為

"考慮到這時kp與q必然互質"

2015年8月19日 13:56 | # | 引用

嘿嘿 說：

引用王軍的發言：

65^17 ≡ c (mod 3233)
說等于
65^17 ≡ 2790 (mod 3233)
即c等于2790
想請問下，這里的2790是怎么算出來的？？
我指的是口算或者筆算不是利用計算機算65的17次方除以3233
有沒有簡單算法 如果筆算65的17次方 會死人的。。。

請自行百度快速冪取模算法，這是CS算法中一個比較基本的算法。

2015年10月 7日 16:59 | # | 引用

mentos 說：

太棒！！！！邏輯清晰，描述清楚！感謝博主！真的是三言兩語我完全看懂了！還有當時一直就在想能不能由n反推私鑰的問題，還有私鑰一定能解的證明，真是好感謝！
教材和老師巴拉了一堆我什么都不知道

2015年10月18日 07:31 | # | 引用

哈哈 說：

以 m = kp為例，考慮到這時k與q必然互質這塊為什么？？

2015年10月22日 17:21 | # | 引用

samaritan 說：

如果事先能找到的目前發現的質數數據集，進行計算出數據庫，這樣的數據庫會有多大。

2015年11月 9日 16:13 | # | 引用

路人甲 說：

引用nkAmerica的發言： 根本沒有協商過程啊。都是用對方的公鑰加密

你的意思是在我們生成的密鑰對里，并將公鑰給了鮑勃，然后鮑勃也將自己生成的密鑰對里的公鑰給了愛麗絲？
但我們在用 SSH-KEYGEN生成密鑰對時，給了鮑勃公鑰，鮑勃是怎么將自己的密鑰對里的公鑰給愛麗絲的？

2015年11月28日 20:58 | # | 引用

Conleyfree 說：

文章很好，學到了，真心感謝，但里面一些圖片顯示不出來，是否是來源網站被墻的問題呢？

2015年12月12日 16:57 | # | 引用

lambda 說：

引用我誰也不是的發言：

bob給alice發信，用的是Alice的公鑰，Alice用自己的私鑰解密；如果Alice要給bob回信，就換成bob的公鑰加密，bob用自己的私鑰解密。

如果ALice用自己的私鑰加密給Bob回信，bob可以用ALice的公鑰來解密么？

2015年12月29日 17:54 | # | 引用

iamzken 說：

博主高人也！

2016年1月20日 17:18 | # | 引用

zzzp 說：

引用zz的發言：

第四步計算模反元素下面這倆式子貌似符號弄錯了～

ex + φ(n)y = 1
已知 e=17, φ(n)=3120，
　　17x + 3120y = 1

應為: 17x-3120y=1

2016年1月23日 06:52 | # | 引用

zzzp 說：

引用zzzp的發言：

應為: 17x-3120y=1

d=2753 k=15.

2016年1月23日 06:53 | # | 引用

qwer 說：

引用zzzp的發言：

d=2753 k=15.

y = -k
兩項相加的話好像才可以滿足擴展歐幾里德算法的要求 ax+by = gcd(a, b)

2016年1月25日 09:43 | # | 引用

braintaust 說：

引用scateu的發言：

"以 m = kp為例，考慮到這時k與q必然互質，則根據歐拉定理，下面的式子成立："

這一句疑似應為

"考慮到這時kp與q必然互質"

k與q必然互質，

原因是m小于n,m取整數，所以m必然為kp或是kq

同時得到m為kp（k小于q），n為kq（k小于p）

取m為kp，由于q是質數，k小于q，k與q互質

我的理解

2016年2月16日 18:37 | # | 引用

matcloud 說：

阮老師，你看云文檔有處公式寫錯了:使用公鑰加密的公式.

2016年3月12日 11:21 | # | 引用

ｒａｍｓｅｙ 說：

有個問題：
　　因為決定是否能夠破解的關鍵在分解ｎ＝ｐ×ｑ，而您提到目前最大的是破解到７６８位，是否意味著７６８位（包括７６８）位以下ＲＳＡ加密的都已經是不安全的了？

2016年4月13日 14:42 | # | 引用

hacker 說：

看懂了原理，數論知識也看懂了大概，不過博主真牛！

2016年4月28日 10:48 | # | 引用

sherlook 說：

引用Caleb的發言：

65^17 ≡ 2790 (mod 3233) 這個式子成立嗎？

2790 mod 3233 = 2790

65^17 mod 3233 = 887 (matlab得到的結果)

另外 2790^2753 ≡ 65 (mod 3233) 這個式子中的 2790^2753 這個值，計算機可以算出來嗎？

謝謝

我用python算 65^17 mod 3233 = 2790 你matlab用錯了吧
2790^2753 這個值計算機當然算的出來，python算了一下，結果占了我半個屏幕。。。

2016年5月13日 15:52 | # | 引用

李耀東 說：

這個不對稱算法絕對是有漏洞的！根據已知e17和n模3233可以算得d＝1193 雖然我不知道真的d為3233但是可以等效算出加密值！其實這個基于的是素數的耦合！既自然數的n次冪mod一個素數＝自然數本身 而求出那個幕與素數的關系的這個數學推論我感覺可以寫個猜想

2016年5月18日 10:34 | # | 引用

Bruce 說：

好文章，感謝。

2016年6月27日 14:12 | # | 引用

HuKeping 說：

引用colde的發言：

證明
　　(m^e - kn)^d ≡ m (mod n)
等同于證明
　m^ed ≡ m (mod n)

卡住在這里了,麻煩幫忙解釋一下。

你可以把 (m^e -kn)^d 這個等式展開，形式為： C(d,0) * m^ed * (kn)^0 + C(d,1) * m^e(d-1) * (kn)^1 + ...

所以只有一項是不包含kn的，而所有包含n的項在對n取余的操作中都可以消掉。因此得出了那個結論

2016年8月10日 11:29 | # | 引用

胡帆 說：

在第二種m與n不互質的情況下，只有當m小于n時，才會有k與q互質。否則若m大于n，則k值可取成q的倍數，這時卻也依然滿足m與n不互質的前提條件。

2016年8月13日 22:52 | # | 引用

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的RSA算法原理2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。