學術向 | RSA加密原理：非對稱加密鼻祖
加密演算法，RSA是繞不開的話題，因為RSA演算法是目前最流行的公開金鑰演算法，既能用於加密，也能使用者數字簽名。不僅在加密貨幣領域使用，在傳統網際網路領域的應用也很廣泛。從被提出到現在20多年，經歷了各種考驗，被普遍認為是目前最優秀的公鑰方案之一。比特幣所使用的Sha256演算法，也是在其基礎之上建立的。瞭解RSA演算法，相信你會對區塊鏈有更深的認識。
非對稱加密
直到1970年代，密碼學都是基於對稱金鑰，也就是傳送者使用特定金鑰加密資訊，而接收者使用相同金鑰解密，加密也就是一種來自資訊的對映， 使用特定金鑰來加密資訊，要解密密文，需要使用相同金鑰，將對映逆轉過來。假設Alice想要和Bob通訊，他們必須共享相同的金鑰，但如果Alice和Bob不能實際見面，建立共享金鑰通常不太可能，或者需要額外的通訊開銷，比如使用迪菲赫爾曼金鑰交換。
另外，如果Alice希望同很多人通訊，比如，她開了一家銀行，那麼她需要同每個人交換不同金鑰，她必須管理好所有這些金鑰，傳送數以千計的資訊。於是，密碼學家不禁會想，是否有更簡單的方式呢？
1970年，英國工程師兼數學家詹姆斯·艾麗斯，試圖公開金鑰加密， 這基於一種簡單但聰明的概念，加鎖和解鎖是互逆操作。
為了理解這些，我們用顏色為比喻進行說明，Bob是如何發給Alice一個特定的顏色，而不讓監聽者截獲資訊的。
每種顏色都具有互補色，同互補色疊加會得到白光，這能去掉第一種顏色的作用，這裡我們假設，混合顏色是一個單向函式，混合顏色輸出第三種顏色很容易，但反向過程就難了，Alice首先生成自己的私有金鑰，也就是可以隨便選擇一個顏色，比如紅色，下面，假設Alice有一種神祕的顏色機器，能夠找到這種紅色的互補色，沒有其他人能夠知道這個，這得到藍綠色，他將這發給Bob作為公開金鑰，假設Bob想傳送一種神祕的黃色給Alice。
他將黃色同公開顏色混合然後得到的混合色發給Alice，此時，Alice能夠將自己的私有色疊加到Bob的混合色，這將解除公開色的作用，剩下Bob的祕密顏色，而竊聽者無法簡單破譯Bob的黃色，除非他有Alice的紅色。
我們還需要一種數學方法，讓這能用於實踐。
模冪計算
解決方法由另一位數學家找到——克利福德科克斯，科克斯需要構建一種特殊的單向函式，也就是陷門 單向函式，這種函式從一個方向計算很容易，反過來就難了，除非你有關於陷門的特殊資訊，為此，他考慮到了模冪計算。
之前講的菲迪赫爾曼金鑰交換，我曾經介紹過，這裡在簡單說下，具體方法如下：取一個數字的某次方，除以模數，輸出餘數，這可以被這樣用於加密資訊，假設Bob有一段資訊被化為數字m，他可以將這個數字自乘e次，其中e是公開指數，然後他可以將結果除以隨機數N，並輸出除法的餘數，這會得到數字c，這個計算很容易完成，但已知c e N，很難求出m是什麼，因為我們需要某種試錯的過程，這就是可以用於m的單向函式。
正向執行容易，但是反過來難，這就是，我們是數字鎖，鑰匙就是陷門，這是某種讓加密逆過程很容易的資訊，我們需要取c的其他次冪，比如d次冪，解除我們原來對m所進行的運算，得到最初的資訊m，兩個運算合起來也就是m的e次方。然後整個的d次方，也就是m的e乘以d次方，e表示加密，d表示解密。
因此，Alice需要有一種方法構建e和d，導致其他人很難求出d的值。這需要第二個單向函式，使用者生成d，為此，他想到了歐幾里得。
歐幾里得的證明
2000多年前，歐幾里得證明了，每個數只有一種質因數分解，這可以考慮為一個金鑰，我們知道，質因數分解是一個非常難的問題，我明確一下這裡的“難”是什麼意思，我將通過介紹所謂事件複雜度來講解，我們都進行過乘法運算，每個人都有自己的計算加速方法，如果程式設計，讓計算機計算乘法，它能比任何人類算起來快得多。
將這同質因數分解對比，如果有人讓你將589質因數分解，你可能會感到問題比較難，無論如何，這都需要採用試錯法，直到找到某數能夠均分589，經過一系列是錯，你會發現其質因數分解是19*31，如果有人讓你將437231質因數分解，你可能直接放棄，然後找計算機幫忙，較小的數字這還行得通，但隨著數字越來越大，電腦也將開始無法駕馭，隨著數字增大，計算步驟增多，需要的時間將大幅增加，大一點的數字計算機可能需要幾分鐘，再大可能需要數小時，最終，可能需要成千上百年才能分解非常大的數字。
因此，我們說這是一個很難的問題，求解問題所需要的事件會飛速增長，因數分解正是科克斯用於構建陷門的方法。
第一步，假設Alice隨機生成一個超過150位的質數，記作p1，然後隨機生成位數相當的第二個質數，記作p2，然後將兩個質數相乘，得到合數N，乘法需要的事件不到一秒，用瀏覽器就能輕鬆計算，然後，她將N的分解P1乘P2隱藏起來，而將N告訴所有人，其他人想要計算機計算，可能需要幾年時間。
第二步，科克斯需要找到一個函式，依賴於知道N的因數分解，為此，他回頭考慮了1765年瑞士數學家萊昂哈德尤拉的函式。
尤拉函式
尤拉繼續研究了質數分佈的性質， 他定義了一個重要的函式，叫 phi函式，它平衡的是數的可分性，對於給定數字N，函式的輸出是，有多少小於等於N的整數，不同N具有任何公因數，我以phi（8）為例講解一下。
我們考慮從1到8的整數，然後數有多少整數，同8沒有大於1的公因數，比如6就不算，因為6和8有公因數2，而1357都算，這些同8只有公因數1，因此（8）=4。
對於任意質數P都有（P）=P-1，比如質數7，（7），需要算進小於7的所有整數，這些數同7都沒有公因數，所以（7）=6，如果要求質數21377的phi函式值，只需要減1，就能得到答案是，21376，任意質數的phi函式值都好算，這就引出了一個有趣的結果，基於phi的乘法性質phi（A·B）=phi（A）·phi（B），如果知道數字N，是兩質數P1和P2的乘積。那麼phi（N）就等於兩個質數分別phi值的乘積。也就是（P1-1）·（P2-1）。
RSA加密
我們現在有了求解phi的陷門，如果你知道N如何因數分解，那麼求解phi（N）就很容易，比如77的質因數分解是7×11，那麼phi（77）=6×10=60。
第三步，如果將phi函式和模冪運算聯絡起來，為此，他想到了尤拉定理，也就是phi函式和模冪運算之間的入下關係，m的phi（n）次方=1mod n，這意味著你可以選擇任何2個數字，讓他們沒有公因數，假設是m和n，這裡令m=5，n=8，取m的phi（n）次方，也就是4次方，然後除以n，將總餘下1，下面只需使用兩條簡單規則處理這個等式。
首先，1的任意次方，記作1的k次方，他總是等於1，同理，我們可以將指數phi（n）乘以任意數k，結果任然是1，然後1乘以任何數m結果總是m，同理，左側可以乘以m，右側也得到m，這可以化簡為m的k·phi（n）+1次方，突破就在這裡。
現在我們有了求e乘以d 的等式，這依賴於phi（n），因此，只有當n的因數分解已知時，計算d才容易，這裡d可以作為Alice的金鑰，這是一扇陷門，讓她能夠解除e的作用，我用個例子簡單講一下：
假設Bob有一條資訊，他使用某種填充方案將其轉化為數字，假設這裡是m，然後Alice按入下方式生成她的公開和私有私鑰，首先，她生成2個大小類似的隨機質數，將這兩者相乘得到n，假設n是3127，然後很容易計算出phi（n），因為她知道n如何因數分解，這裡phi（n）=3016，然後她選取一個小的公開指數e，前天是這個e必須是奇數，而且不同phi（n）具有公因數，這裡選擇e=3，最後她求出私有指數d 的值，這裡也就是（2·phi（n）+1）/3，也就是2011。
他將這些都隱藏起來，只留下n和e的值，因為n和e組成她的公開金鑰，這可以考慮為開著的鎖，她把這些發給Bob，讓Bob能夠上鎖自己的資訊，Bob上鎖是通過計算m的e吃飯mod n，記作c這是他的加密資訊，他將這個發回給Alice，最後，Alice使用她的私鑰d解密這個資訊，通過陷門來訪問，c的d次方mod n，等於Bob的原始資訊m，任何知道c n e 的人，想知道計算指數d，智慧通過計算phi（n），這要求他們知道n 的質因數分解。
當n足夠時，Alice能夠確保哪怕最先進的計算機網路，想計算出這個也需要數百年時間，該技術釋出後，立刻被當做國家機密，不過1977年，該技術被獨立地在發現，發現者是羅納德·裡維斯特，阿迪·薩莫爾，倫納德·阿德曼，該加密於是以他們人人姓氏首字母RSA命名，RSA是使用最廣泛的公開金鑰演算法，也是歷史上使用最多的加密演算法。
目前，世界上網際網路使用者幾乎都在使用RSA，或者某種相關的版本，不管他們意識到沒有，RSA加密強度以來於質因數分解的困難程度，這是質數分佈這一深層次問題的結果，這個問題存在了數千年，人類至今人無法解決。