去年有个财大气粗的甲方爸爸给我们一堆非对称加密的通信数据叫我们给他解开，不止一次给他做了解释说解不了，奈何对方非要不可，没办法，甲方就是爸爸，逼急了我把算法和通信过程以及数学证明全给他做了一次免费科普，事后把资料整理了下。

一，RSA算法基础

RSA算法是典型的非对称算法，

原理

求两个大素数的乘积是非常容易的；而通过乘积求这两个大素数是非常困难的。
例如一个2048bit的数，如下

0x890e23101a542913da8a4350672c9ef8e7b34c2687ce8cd8db3fb34244a791d60c9dc0a53172a56dcc8a66f553c0ae51e9e2e2ce9486fa6b00a6c556bfed139001133cdfe5921c425eb8823b1bd0a4c00920d24bee2633256328502eadbfac1420f9a5f47139de6f14d8eb7c2b7c0cec42530c0a71dadb80c7214f5cd19a3f2f 

他可以分解成一个155位和154位的因数，如果要暴力破解的话基本是不可能的。
12026655772210679470465581609002525329245773732132014742758935511187863487919026457076252932048619706498126046597130520643092209728783224795661331197604583
8002511426596424351829267099531651390448054153452321185350746845306277585856673898048740413439442356860630765545600353049345324913056448174487017235828857

密钥对生成

举例，为了计算方便，用67和71两个素数代替上面两个大素数。
P=67，Q=71

1. 求乘积，n = P * Q = 4757
2. 计算n的欧拉函数（<=n的与n互质的正整数的个数），m = φ (n) = (P-1)(Q-1) = 4620
3. 在1~m之间选一个随机的m的互质数e，e=101
4. 求d，满足 (e*d)% m = 1
   化简得 e * d - m * y = 1 (y is an integer)
   101 * d - 4620 * y = 1
   最后得到4中的二元一次方程，对于二元一次方程可以使用扩展欧几里得算法
   得到一组(d,y) = (1601,35)
   ∴ d取值1601
   那么就得到了我们需要的密钥对，

公钥对：(n,e) = (4757,101)
私钥对：(n,d) = (4757,1601)

密钥对的使用

加解密公式

举个栗子：
明文: ILOVEU
ASCII:73 76 79 86 69 85

公钥加密，私钥解密

同时也可以私钥加密，公钥解密，通常用在数字签名验证过程：

私钥加密，公钥解密

公式证明

加密：𝑚^𝑒 𝑚𝑜𝑑 𝑛=𝑐
解密：𝑐^𝑑 𝑚𝑜𝑑 𝑛=𝑚
由加密公式得：

将c带入解密公式得：
二项式展开：
已知 *𝑒𝑑 𝑚𝑜𝑑 (𝜑(𝑛)) = 1 *（密钥对生成时的第四步）
所以

那么问题就变成了证明上式。
分情况处理：
一，假设mn互质，通过欧拉定理，𝑚^(𝜑(𝑛)) 𝑚𝑜𝑑 𝑛=1

得证；
二，mn不互质，
因为mn不互质，且n=pq，则必有 m=kp 或者 m=kq，
假设m=kp，因为q是质数，所以k和q互质（q不可能是k的质因数，因为若k=lq，则 m = kp = lpq = ln > n）
根据欧拉定理
得
同情景一的原理：

即
代入ed的公式 𝑒𝑑= ℎ𝜑(𝑛)+1

即
这时t必然能被p整除，即 t=t′𝑝
将m=kp ,n=pq代入得

即
得证。

二，SSL/TLS协议

• 加密数据是通过对称算法传输的
• 密钥的生成是随机的
• 密钥是通过非对称算法传输的

Client Hello
Server Hello
Server Hello Done
Server Finished
send encrypted data