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

非對(duì)稱加密

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

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

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

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

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

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

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

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

模冪計(jì)算

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

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

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

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

歐幾里得的證明

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

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

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

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

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

歐拉函數(shù)

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

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

對(duì)于任意質(zhì)數(shù)P都有（P）=P-1，比如質(zhì)數(shù)7，（7），需要算進(jìn)小于7的所有整數(shù)，這些數(shù)同7都沒有公因數(shù)，所以（7）=6，如果要求質(zhì)數(shù)21377的phi函數(shù)值，只需要減1，就能得到答案是，21376，任意質(zhì)數(shù)的phi函數(shù)值都好算，這就引出了一個(gè)有趣的結(jié)果，基于phi的乘法性質(zhì)phi（A·B）=phi（A）·phi（B），如果知道數(shù)字N，是兩質(zhì)數(shù)P1和P2的乘積。那么phi（N）就等于兩個(gè)質(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ù)和模冪運(yùn)算聯(lián)系起來，為此，他想到了歐拉定理，也就是phi函數(shù)和模冪運(yùn)算之間的入下關(guān)系，m的phi（n）次方=1mod n，這意味著你可以選擇任何2個(gè)數(shù)字，讓他們沒有公因數(shù)，假設(shè)是m和n，這里令m=5，n=8，取m的phi（n）次方，也就是4次方，然后除以n，將總余下1，下面只需使用兩條簡(jiǎn)單規(guī)則處理這個(gè)等式。

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

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

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

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

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

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