去年有個(gè)財(cái)大氣粗的甲方爸爸給我們一堆非對(duì)稱加密的通信數(shù)據(jù)叫我們給他解開(kāi)，不止一次給他做了解釋說(shuō)解不了，奈何對(duì)方非要不可，沒(méi)辦法，甲方就是爸爸，逼急了我把算法和通信過(guò)程以及數(shù)學(xué)證明全給他做了一次免費(fèi)科普，事后把資料整理了下。

一，RSA算法基礎(chǔ)

RSA算法是典型的非對(duì)稱算法，

原理

求兩個(gè)大素?cái)?shù)的乘積是非常容易的；而通過(guò)乘積求這兩個(gè)大素?cái)?shù)是非常困難的。
例如一個(gè)2048bit的數(shù)，如下

0x890e23101a542913da8a4350672c9ef8e7b34c2687ce8cd8db3fb34244a791d60c9dc0a53172a56dcc8a66f553c0ae51e9e2e2ce9486fa6b00a6c556bfed139001133cdfe5921c425eb8823b1bd0a4c00920d24bee2633256328502eadbfac1420f9a5f47139de6f14d8eb7c2b7c0cec42530c0a71dadb80c7214f5cd19a3f2f

他可以分解成一個(gè)155位和154位的因數(shù)，如果要暴力破解的話基本是不可能的。
12026655772210679470465581609002525329245773732132014742758935511187863487919026457076252932048619706498126046597130520643092209728783224795661331197604583
8002511426596424351829267099531651390448054153452321185350746845306277585856673898048740413439442356860630765545600353049345324913056448174487017235828857

密鑰對(duì)生成

舉例，為了計(jì)算方便，用67和71兩個(gè)素?cái)?shù)代替上面兩個(gè)大素?cái)?shù)。
P=67，Q=71

求乘積，n = P * Q = 4757
計(jì)算n的歐拉函數(shù)（<=n的與n互質(zhì)的正整數(shù)的個(gè)數(shù)），m = φ (n) = (P-1)(Q-1) = 4620
在1~m之間選一個(gè)隨機(jī)的m的互質(zhì)數(shù)e，e=101
求d，滿足 (e*d)% m = 1
化簡(jiǎn)得 e * d - m * y = 1 (y is an integer)
101 * d - 4620 * y = 1
最后得到4中的二元一次方程，對(duì)于二元一次方程可以使用擴(kuò)展歐幾里得算法
得到一組(d,y) = (1601,35)
∴ d取值1601
那么就得到了我們需要的密鑰對(duì)，

公鑰對(duì)：(n,e) = (4757,101)
私鑰對(duì)：(n,d) = (4757,1601)

密鑰對(duì)的使用

加解密公式

舉個(gè)栗子：
明文: ILOVEU
ASCII:73 76 79 86 69 85

公鑰加密，私鑰解密

同時(shí)也可以私鑰加密，公鑰解密，通常用在數(shù)字簽名驗(yàn)證過(guò)程：

私鑰加密，公鑰解密

公式證明

加密：??^?? ?????? ??=??
解密：??^?? ?????? ??=??
由加密公式得：

將c帶入解密公式得：

二項(xiàng)式展開(kāi)：

已知 *???? ?????? (??(??)) = 1 *（密鑰對(duì)生成時(shí)的第四步）
所以

那么問(wèn)題就變成了證明上式。
分情況處理：
一，假設(shè)mn互質(zhì)，通過(guò)歐拉定理，??^(??(??)) ?????? ??=1

得證；
二，mn不互質(zhì)，
因?yàn)閙n不互質(zhì)，且n=pq，則必有 m=kp 或者 m=kq，
假設(shè)m=kp，因?yàn)閝是質(zhì)數(shù)，所以k和q互質(zhì)（q不可能是k的質(zhì)因數(shù)，因?yàn)槿鬹=lq，則 m = kp = lpq = ln > n）
根據(jù)歐拉定理