簡介：不羈將在本文中介紹RSA的原理川蒙，但與其他的講解不同的是，本文是循著發(fā)明者的思路蹈矮，一步步來得出RSA算法的砰逻。這種方式更有助于理解。
朋友勿笑泛鸟，亦勿怒蝠咆。
這里的標(biāo)題用了“重新發(fā)明”這個(gè)詞，其實(shí)代表的是北滥，假設(shè)我們回到了上世紀(jì)70年代刚操，在RSA非對(duì)稱加密算法被發(fā)明之前，我們?cè)撛趺此伎疾拍馨l(fā)明出RSA算法呢碑韵？當(dāng)然了赡茸，現(xiàn)在RSA已經(jīng)被發(fā)明出來了，我們這里不免還是會(huì)受到它的影響祝闻，但我們這里將試圖循著發(fā)明人的思路占卧，一點(diǎn)點(diǎn)推導(dǎo)出RSA算法遗菠。
我學(xué)習(xí)一樣?xùn)|西，比較喜歡這種從未知到探索出一個(gè)解決方案的過程华蜒；可惜目前國內(nèi)的學(xué)習(xí)資料辙纬，不管是哪個(gè)方面的(特別是教材里面的知識(shí))，都是先告訴你個(gè)結(jié)果叭喜，然后去證明這個(gè)結(jié)果贺拣，少了很多在摸索中思考的樂趣。
好了捂蕴，言歸正傳譬涡。
目標(biāo)
我們先從思考如何實(shí)現(xiàn)一個(gè)非對(duì)稱加密算法開始。我們希望的達(dá)到的目的是啥辨，我們有一對(duì)公鑰和私鑰劝贸，公鑰是可以公開出去顶考，私鑰是保密的，別人要發(fā)給我一段不想讓外人竊取的信息的時(shí)候，可以先用我的公鑰加密瓣颅，我們把加密后的消息稱為密文恨闪，然后我收到密文之后徘公，用我的私鑰解密竣贪，即可變?yōu)槊魑模欢乙ＷC無法從公鑰推導(dǎo)出私鑰玫荣，這樣甚淡，即便密文消息即便被黑客截獲了，因?yàn)門a沒有私鑰崇决，就無從得到明文材诽，從而起到保密的作用。
初步方案
我們給出的方案需要滿足如下特性：
- 無法從密文得出明文
- 私鑰可以解密密文得到明文
- 無法從公鑰得出私鑰
也就是說恒傻，我們先從第一個(gè)特性開始脸侥，假設(shè)我們密文是m, f是加密函數(shù)，c代表密文盈厘，e代表公鑰睁枕，那么我們需要一個(gè)這樣的f，滿足:
f(m, e) = c沸手，并且通過m,e很容易得到c, 而無法通過c得到m外遇。
也就是說，f必須是一個(gè)單向函數(shù)契吉，正向求解容易跳仿，而反向求解很難。
那么什么樣的f才能滿足這個(gè)要求呢捐晶？
這時(shí)菲语，突然靈光一閃妄辩，有這么一個(gè)求余的函數(shù)出現(xiàn)了:
m^e = c (mod\ N)，N是一個(gè)正整數(shù)常量山上。
這個(gè)函數(shù)的意思是m^e除以N得到的余數(shù)與c除以N得到的余數(shù)相同眼耀。我們發(fā)現(xiàn)，當(dāng)給定m,e,N的時(shí)候佩憾，比較容易得到c哮伟，但如果給定c,e,N，則很難得到m妄帘，因?yàn)橐龅竭@一點(diǎn)楞黄，我們只能使用窮舉法一個(gè)個(gè)去試，當(dāng)N和e都很大的時(shí)候寄摆，窮舉法的計(jì)算量就大的驚人了谅辣，當(dāng)N,e大到一定程度的時(shí)候，也就是從c得到m需要的運(yùn)算時(shí)間很長很長的時(shí)候婶恼，我們就可以認(rèn)為不可能從c得到m。
第一個(gè)特性解決了柏副，那么如何滿足第二個(gè)特性（私鑰可以解密密文得到明文）呢勾邦？
如何從密文得到明文呢？我們用d表示私鑰割择，那么要滿足第二個(gè)特性眷篇，如果利用同樣的函數(shù)，也就是要滿足：
c^d = m (mod\ N)荔泳，我們把c = m^e (mod\ N)蕉饼，帶入進(jìn)去，從而得到:
(m^e)^d = m (mod\ N)玛歌，也就是：
m^{ed} = m(mod\ N)昧港，這個(gè)式子又等價(jià)于：
m^{ed-1} = 1(mod\ N)
注意，上面的推導(dǎo)中支子，我們用到了如下數(shù)學(xué)事實(shí)：
m^e = c (mod\ N) 等價(jià)于 c = m^e (mod\ N)
再來看下我們得到的結(jié)果:
m^{ed-1} = 1(mod\ N)
于是创肥，只要我們能在e和d之間建立聯(lián)系，使得上面的式子成立值朋，那么我們就可以用(e,N)作為公鑰叹侄，(d,N)作為私鑰。如此別人用(e,N)對(duì)明文m加密之后得到密文c昨登，我們就可以用私鑰d做這個(gè)操作c^d(mod\ N)進(jìn)行解密了趾代。
那么我們?cè)撊绾问沟?span id="s2coiuw" class="math-inline">m^{ed-1} = 1(mod\ N)成立并且滿足特性三(無法從公鑰e得出私鑰d)的要求呢？
救星：歐拉公式
先看如何滿足m^{ed-1} = 1(mod\ N)丰辣，最簡單的情況是讓ed=1撒强，但是這樣的話禽捆，要么e=d=1或者-1，要么其中一個(gè)是小數(shù)尿褪；前者將導(dǎo)致起不到加密的作用睦擂，后者將會(huì)面臨小數(shù)運(yùn)算誤差的問題。
看來讓ed=1是行不通的杖玲。
再一次靈光閃顿仇，這個(gè)形式和歐拉公式特像，看下歐拉公式：
m^{\phi(N)} = 1 (mod\ N)
是不是仿佛看到了救星摆马。
我們從歐拉公式開始：
m^{\phi(N)} = 1 (mod\ N) 等價(jià)于 (m^{\phi(N)})^k = 1^k (mod\ N)臼闻，k是任意的整數(shù)
也就是:
m^{k*\phi(N)} = 1 (mod\ N)
也就是說我們只需要讓ed滿足ed -1 = k*\phi(N)即可， 這樣就可以計(jì)算d了：
d = (k*\phi(N) + 1)/e囤采。
那么\phi(N)是什么呢述呐？怎么求呢？根據(jù)歐拉定理中對(duì)\phi(N)的定義蕉毯，它代表1~N中乓搬，所有與N互質(zhì)的數(shù)的數(shù)量。所謂互質(zhì)代虾，是指兩個(gè)數(shù)除了1之外沒有其他公因子进肯，比如9和4互質(zhì)，7和6互質(zhì)等棉磨。很容易得出江掩，對(duì)于質(zhì)數(shù)X而言，\phi(X) = X - 1乘瓤，因?yàn)槿魏我粋€(gè)比它小數(shù)都和它互質(zhì)环形。
又遇攔路虎
然而，歐拉定理有一個(gè)前置條件衙傀，即：m必須與N互質(zhì)抬吟。可是差油，m代表的是消息拗军，我不能對(duì)m做任何限定，所以我們只能從N入手蓄喇。
先來個(gè)最簡單的发侵，讓N為質(zhì)數(shù)，這樣的話妆偏，無論m是什么刃鳄，m和N都互質(zhì)了，如此\phi(N)也簡單了钱骂，等于N-1叔锐，可這就有問題了：
別人根據(jù)我們的公鑰(e,N)很容易就能計(jì)算出\phi(N)挪鹏，于是很容易就能得到我們的私鑰d了∮淅樱看來這個(gè)方案不行讨盒。
看來既要滿足m和N互質(zhì)，還要滿足難以計(jì)算出\phi(N)才行步责，不容易啊
柳暗花明
我們?cè)僭囋嚻渌椒ǚ邓场｀牛琋是質(zhì)數(shù)蔓肯，會(huì)使得\phi(N)太容易計(jì)算遂鹊，那我們只能允許m和N不互質(zhì)了，只要不互質(zhì)的概率比較小就行蔗包。于是秉扑，我們不讓N單獨(dú)作為一個(gè)質(zhì)數(shù)了，我們把N表示成兩個(gè)質(zhì)數(shù)p和q的乘積调限，這樣舟陆，除非m=hp或者m=hq，否則m與N仍是互質(zhì)的耻矮；而當(dāng)m=hp或者m=hq時(shí)吨娜，即便歐拉定理不滿足了，我們也可以重新選擇p和q淘钟，這個(gè)計(jì)算量不大。因?yàn)镹=p*q陪毡，而且p,q都是質(zhì)數(shù)米母，所以：
\phi(N) = \phi(p) * \phi(q)
這個(gè)式子根據(jù)\phi(N)的定義，也是可以想到的毡琉，這里就不再證明了铁瞒。考慮p,q都是質(zhì)數(shù)桅滋，所以\phi(p) = p-1, \phi(q) = q -1慧耍，所以\phi(N) = (p-1)*(q-1)
好，那我們看看這個(gè)時(shí)候丐谋，黑客如何通過公鑰(e,N)計(jì)算\phi(N)芍碧，他有兩種辦法：
- 把N進(jìn)行質(zhì)數(shù)分解
- 從1~N中，依次檢查是否與N互質(zhì)
當(dāng)N很大的時(shí)候号俐，這兩種方案的計(jì)算量都會(huì)大的驚人泌豆。
因而這個(gè)方案是安全的。
自此吏饿，我們已經(jīng)得出了RSA的方案了踪危，還差一點(diǎn)需要確認(rèn)：
當(dāng)m=hp或者m=hq的時(shí)候蔬浙，m^{ed-1} = 1(mod\ N)還成立嗎？
如果成立贞远，就太好了畴博，我們就不用根據(jù)m的取值來調(diào)整p和q的取值了。
我們來分析一下：
假設(shè)m= hp蓝仲，因?yàn)閜和q是質(zhì)數(shù)俱病，所以h和p也必然互質(zhì)，所以由歐拉定理知：
(hp)^{q-1} = 1 (mod\ q)
進(jìn)一步得到：
[(hp)^{q-1}]^{k(p-1)} × hp ≡ hp (mod\ q)
即：
(hp)^{ed} ≡ hp (mod\ q)
將它改寫成下面的等式:
(hp)^{ed} = tq + hp
因?yàn)閜互質(zhì)杂曲，這時(shí)t必然能被p整除庶艾，因而t = t'p，因而：
(hp)^{ed} = t'pq + hp
因?yàn)?m=hp擎勘，n=pq咱揍，所以
m^{ed} = m (mod\ n)
等價(jià)于
m^{ed-1} = 1 (mod\ n)
所以，當(dāng)m=hp或者m=hq的時(shí)候棚饵，m^{ed-1} = 1(mod\ N)依然成立煤裙。
完美結(jié)局。
自此我們就得到的RSA加密算法了噪漾。其實(shí)不難硼砰，對(duì)吧？
總結(jié)
總結(jié)上面得出的RSA過程如下：
選取兩個(gè)正的大質(zhì)數(shù)p, q欣硼，然后計(jì)算出N题翰，以及\phi(N) = (p-1)*(q-1)，然后隨機(jī)選取一個(gè)正整數(shù)e, 然后在計(jì)算出
d = (k*\phi(N) + 1)/e
由此得出公鑰(e, N)和私鑰(d, N)诈胜，p和q就可以丟棄掉了豹障，但不能泄漏出去。
從明文m到密文c(也即加密)的過程：
c = m^e(mod\ N)
從密文c到明文m(也即解密)的過程：
m=c^d(mod\ N)
