3年前，我以POJ2447作為切入點介紹了什么是非對稱加解密，RSA加解密的步驟。然而RSA為什么可以用兩個“風馬牛不相及乎”的數(shù)字，就能讓所有的數(shù)字(數(shù)據(jù))完成一個輪回(加解密)？為什么在能做到AC POJ2447的情況下，卻看不懂OpenSSL公私鑰證書的格式？你知道“兔死狗烹”說的是劉邦韓信，那你知道要是劉邦不殺韓信，說不定非對稱加解密就是韓信發(fā)明的了嗎(大霧)？你知道這個世界上最偉大的民科(業(yè)余數(shù)學家)費馬，在寫下了“我找到了一個精彩絕倫的證明方法，證明了a^n +bn=cn在n大于2時，沒有滿足條件的正整數(shù)解a、b、c。但是這里空間不夠?qū)懖幌铝?，我以后再證明?！焙?，駕鶴西去。后人花了300年的時間，直到上個世紀末才完全證明了，這條被稱為費馬大定理的猜想是正確的。但是你知道費馬還為我們留下了一條費馬小定理，在證明的時候，費馬同樣也用了“精彩絕倫”這樣的形容嗎？你知道作為RSA算法理論基礎的費馬小定理，費馬真的只用了一行就證明了他的正確性嗎？對于奧數(shù)學習大家有很多爭論，我無意對此做出任何評論。但是學了小學奧數(shù)就能找到一種比 Ron Rivest、Adi Shamir、Leonard Adleman在1977年第一次提出非對稱加解密論文中的解密算法快3-4倍的算法，如果你學了小學奧數(shù)，那你想到了是什么方法嗎？
實際上，如果說當前的安全通信體系是武器的話，RSA非對稱加解密只能算好鋼，要把好鋼做成“十步殺一人，千里不留行”的武器，中間又會有什么樣的過程呢？這篇文章將會介紹，RSA算法的理論基礎，讓大家知其然也知其所以然。只有這樣，在后續(xù)介紹到OpenSSL證書實現(xiàn)方式時，才能游刃有余.
RSA原理與數(shù)字證書
// RSA算法偽代碼+一個實際例子
#define LL long long
// 首先選取兩個素數(shù)P和Q
LL P = 601, Q = 997
// 分別計算N=P*Q和T=(P-1)*(Q-1)
LL N = P*Q = 599197
LL T = (P-1)*(Q-1) = 597600
// 尋找一個和T互素的數(shù)E。因為素數(shù)和任何數(shù)都是互素的，所以我們直接選一個素數(shù)作為E
LL E = 89
// 尋找一個數(shù)D滿足公式 (E*D) mod T = 1
LL D = 188009
// 公鑰即為 {E,N}={89,599197}
// 私鑰即為 {D,N}={188009,599197}
// 假設明文為M，密文為C
// 加密過程為 C = M的E次方 mod N
// 解密過程為 M = C的D次方 mod N
LL M = 386
LL C = (386^89)%599197 = 192403
M = (192403^188009)%599197 = 386
首先我們來做個游戲，游戲的名字叫“我知道你在想什么”，做完這個游戲你會不服。請你任意想一個4位數(shù)，比如m=6,996。將m乘以e=19，m*e=6,996*19=132,924=c1，將得到的結果c1的后4位數(shù)取出來，構成c=2,924。你不用告訴我你想的數(shù)是多少，只要告訴我它經(jīng)過乘19后的結果的后4位數(shù)c，我就能知道你想的是哪個數(shù)。不信？我們接著來。將c乘以d=1579，c*d=2,924*1,579=4,616,996=m1，將得到的結果m1的后4位數(shù)取出來，構成m=6,996。恰好就是你剛開始想的這個數(shù)6,996，是不是有一點點神奇，又有一點不服？
