加密算法，RSA是繞不開的話題，因為RSA算法是目前最流行的公開密鑰算法，既能用于加密，也能用戶數(shù)字簽名。不僅在加密貨幣領域使用，在傳統(tǒng)互聯(lián)網(wǎng)領域的應用也很廣泛。從被提出到現(xiàn)在20多年，經(jīng)歷了各種考驗，被普遍認為是目前最優(yōu)秀的公鑰方案之一。比特幣所使用的Sha256算法，也是在其基礎之上建立的。了解RSA算法，相信你會對區(qū)塊鏈有更深的認識。

非對稱加密

直到1970年代，密碼學都是基于對稱密鑰，也就是發(fā)送者使用特定密鑰加密信息，而接收者使用相同密鑰解密，加密也就是一種來自信息的映射，使用特定密鑰來加密信息，要解密密文，需要使用相同密鑰，將映射逆轉(zhuǎn)過來。

假設Alice想要和Bob通信，他們必須共享相同的密鑰，但如果Alice和Bob不能實際見面，建立共享密鑰通常不太可能，或者需要額外的通信開銷，比如使用迪菲赫爾曼密鑰交換。

另外，如果Alice希望同很多人通信，比如，她開了一家銀行，那么她需要同每個人交換不同密鑰，她必須管理好所有這些密鑰，發(fā)送數(shù)以千計的信息。于是，密碼學家不禁會想，是否有更簡單的方式呢？

1970年，英國工程師兼數(shù)學家詹姆斯·艾麗斯，試圖公開密鑰加密，這基于一種簡單但聰明的概念，加鎖和解鎖是互逆操作。

為了理解這些，我們用顏色為比喻進行說明，Bob是如何發(fā)給Alice一個特定的顏色，而不讓監(jiān)聽者截獲信息的。

每種顏色都具有互補色，同互補色疊加會得到白光，這能去掉第一種顏色的作用，這里我們假設，混合顏色是一個單向函數(shù)，混合顏色輸出第三種顏色很容易，但反向過程就難了，Alice首先生成自己的私有密鑰，也就是可以隨便選擇一個顏色，比如紅色，下面，假設Alice有一種神秘的顏色機器，能夠找到這種紅色的互補色，沒有其他人能夠知道這個，這得到藍綠色，他將這發(fā)給Bob作為公開密鑰，假設Bob想發(fā)送一種神秘的黃色給Alice。

他將黃色同公開顏色混合然后得到的混合色發(fā)給Alice，此時，Alice能夠?qū)⒆约旱乃接猩B加到Bob的混合色，這將解除公開色的作用，剩下Bob的秘密顏色，而竊聽者無法簡單破譯Bob的黃色，除非他有Alice的紅色。

我們還需要一種數(shù)學方法，讓這能用于實踐。

模冪計算

解決方法由另一位數(shù)學家找到——克利福德科克斯，科克斯需要構建一種特殊的單向函數(shù)，也就是陷門單向函數(shù)，這種函數(shù)從一個方向計算很容易，反過來就難了，除非你有關于陷門的特殊信息，為此，他考慮到了模冪計算。

之前講的菲迪赫爾曼密鑰交換，我曾經(jīng)介紹過，這里在簡單說下，具體方法如下：取一個數(shù)字的某次方，除以模數(shù)，輸出余數(shù)，這可以被這樣用于加密信息，假設Bob有一段信息被化為數(shù)字m，他可以將這個數(shù)字自乘e次，其中e是公開指數(shù)，然后他可以將結果除以隨機數(shù)N，并輸出除法的余數(shù)，這會得到數(shù)字c，這個計算很容易完成，但已知c e N，很難求出m是什么，因為我們需要某種試錯的過程，這就是可以用于m的單向函數(shù)。

正向執(zhí)行容易，但是反過來難，這就是，我們是數(shù)字鎖，鑰匙就是陷門，這是某種讓加密逆過程很容易的信息，我們需要取c的其他次冪，比如d次冪，解除我們原來對m所進行的運算，得到最初的信息m，兩個運算合起來也就是m的e次方。然后整個的d次方，也就是m的e乘以d次方，e表示加密，d表示解密。

因此，Alice需要有一種方法構建e和d，導致其他人很難求出d的值。這需要第二個單向函數(shù)，用戶生成d，為此，他想到了歐幾里得。

歐幾里得的證明

2000多年前，歐幾里得證明了，每個數(shù)只有一種質(zhì)因數(shù)分解，這可以考慮為一個密鑰，我們知道，質(zhì)因數(shù)分解是一個非常難的問題，我明確一下這里的“難”是什么意思，我將通過介紹所謂事件復雜度來講解，我們都進行過乘法運算，每個人都有自己的計算加速方法，如果編程，讓計算機計算乘法，它能比任何人類算起來快得多。

將這同質(zhì)因數(shù)分解對比，如果有人讓你將589質(zhì)因數(shù)分解，你可能會感到問題比較難，無論如何，這都需要采用試錯法，直到找到某數(shù)能夠均分589，經(jīng)過一系列是錯，你會發(fā)現(xiàn)其質(zhì)因數(shù)分解是19*31，如果有人讓你將437231質(zhì)因數(shù)分解，你可能直接放棄，然后找計算機幫忙，較小的數(shù)字這還行得通，但隨著數(shù)字越來越大，電腦也將開始無法駕馭，隨著數(shù)字增大，計算步驟增多，需要的時間將大幅增加，大一點的數(shù)字計算機可能需要幾分鐘，再大可能需要數(shù)小時，最終，可能需要成千上百年才能分解非常大的數(shù)字。

因此，我們說這是一個很難的問題，求解問題所需要的事件會飛速增長，因數(shù)分解正是科克斯用于構建陷門的方法。

第一步，假設Alice隨機生成一個超過150位的質(zhì)數(shù)，記作p1，然后隨機生成位數(shù)相當?shù)牡诙€質(zhì)數(shù)，記作p2，然后將兩個質(zhì)數(shù)相乘，得到合數(shù)N，乘法需要的事件不到一秒，用瀏覽器就能輕松計算，然后，她將N的分解P1乘P2隱藏起來，而將N告訴所有人，其他人想要計算機計算，可能需要幾年時間。

第二步，科克斯需要找到一個函數(shù)，依賴于知道N的因數(shù)分解，為此，他回頭考慮了1765年瑞士數(shù)學家萊昂哈德歐拉的函數(shù)。

歐拉函數(shù)

歐拉繼續(xù)研究了質(zhì)數(shù)分布的性質(zhì)，他定義了一個重要的函數(shù)，叫 phi函數(shù)，它平衡的是數(shù)的可分性，對于給定數(shù)字N，函數(shù)的輸出是，有多少小于等于N的整數(shù)，不同N具有任何公因數(shù)，我以phi（8）為例講解一下。

我們考慮從1到8的整數(shù)，然后數(shù)有多少整數(shù)，同8沒有大于1的公因數(shù)，比如6就不算，因為6和8有公因數(shù)2，而1357都算，這些同8只有公因數(shù)1，因此（8）=4。

對于任意質(zhì)數(shù)P都有（P）=P-1，比如質(zhì)數(shù)7，（7），需要算進小于7的所有整數(shù)，這些數(shù)同7都沒有公因數(shù)，所以（7）=6，如果要求質(zhì)數(shù)21377的phi函數(shù)值，只需要減1，就能得到答案是，21376，任意質(zhì)數(shù)的phi函數(shù)值都好算，這就引出了一個有趣的結果，基于phi的乘法性質(zhì)phi（A·B）=phi（A）·phi（B），如果知道數(shù)字N，是兩質(zhì)數(shù)P1和P2的乘積。那么phi（N）就等于兩個質(zhì)數(shù)分別phi值的乘積。也就是（P1-1）·（P2-1）。

RSA加密

我們現(xiàn)在有了求解phi的陷門，如果你知道N如何因數(shù)分解，那么求解phi（N）就很容易，比如77的質(zhì)因數(shù)分解是7×11，那么phi（77）=6×10=60。

第三步，如果將phi函數(shù)和模冪運算聯(lián)系起來，為此，他想到了歐拉定理，也就是phi函數(shù)和模冪運算之間的入下關系，m的phi（n）次方=1mod n，這意味著你可以選擇任何2個數(shù)字，讓他們沒有公因數(shù)，假設是m和n，這里令m=5，n=8，取m的phi（n）次方，也就是4次方，然后除以n，將總余下1，下面只需使用兩條簡單規(guī)則處理這個等式。

首先，1的任意次方，記作1的k次方，他總是等于1，同理，我們可以將指數(shù)phi（n）乘以任意數(shù)k，結果任然是1，然后1乘以任何數(shù)m結果總是m，同理，左側(cè)可以乘以m，右側(cè)也得到m，這可以化簡為m的k·phi（n）+1次方，突破就在這里。

現(xiàn)在我們有了求e乘以d 的等式，這依賴于phi（n），因此，只有當n的因數(shù)分解已知時，計算d才容易，這里d可以作為Alice的密鑰，這是一扇陷門，讓她能夠解除e的作用，我用個例子簡單講一下：

假設Bob有一條信息，他使用某種填充方案將其轉(zhuǎn)化為數(shù)字，假設這里是m，然后Alice按入下方式生成她的公開和私有私鑰，首先，她生成2個大小類似的隨機質(zhì)數(shù)，將這兩者相乘得到n，假設n是3127，然后很容易計算出phi（n），因為她知道n如何因數(shù)分解，這里phi（n）=3016，然后她選取一個小的公開指數(shù)e，前天是這個e必須是奇數(shù)，而且不同phi（n）具有公因數(shù)，這里選擇e=3，最后她求出私有指數(shù)d 的值，這里也就是（2·phi（n）+1）/3，也就是2011。

他將這些都隱藏起來，只留下n和e的值，因為n和e組成她的公開密鑰，這可以考慮為開著的鎖，她把這些發(fā)給Bob，讓Bob能夠上鎖自己的信息，Bob上鎖是通過計算m的e吃飯mod n，記作c這是他的加密信息，他將這個發(fā)回給Alice，最后，Alice使用她的私鑰d解密這個信息，通過陷門來訪問，c的d次方mod n，等于Bob的原始信息m，任何知道c n e 的人，想知道計算指數(shù)d，智能通過計算phi（n），這要求他們知道n 的質(zhì)因數(shù)分解。

當n足夠時，Alice能夠確保哪怕最先進的計算機網(wǎng)絡，想計算出這個也需要數(shù)百年時間，該技術發(fā)布后，立刻被當做國家機密，不過1977年，該技術被獨立地在發(fā)現(xiàn)，發(fā)現(xiàn)者是羅納德·里維斯特，阿迪·薩莫爾，倫納德·阿德曼，該加密于是以他們?nèi)巳诵帐鲜鬃帜窻SA命名，RSA是使用最廣泛的公開密鑰算法，也是歷史上使用最多的加密算法。

目前，世界上互聯(lián)網(wǎng)使用者幾乎都在使用RSA，或者某種相關的版本，不管他們意識到?jīng)]有，RSA加密強度以來于質(zhì)因數(shù)分解的困難程度，這是質(zhì)數(shù)分布這一深層次問題的結果，這個問題存在了數(shù)千年，人類至今人無法解決。