RSA算法

算法简介

RSA是一种非对称加密方式。发送者把明文通过公钥加密后发送出去，接受者把密文通过私钥解密得到明文。

算法过程

生成公钥和私钥

选取两个质数p和q，n=p*q。n的长度就是密钥长度。

φ(n)=(p-1)*(q-1)

φ(n)为n的欧拉函数。

找到1-φ(n)间与φ(n)互质的一个数 e,将n和e封装成公钥。

d*e ≡ 1（mod φ(n)），将n和d封装成私钥。

加密过程

假设明文为X

密文 Y=X^e mod N

解密过程

X = Y^d mod N

算法的可靠性

上述加解密过程一共涉及6个数字：

n p q φ(n) e d

公钥 n e 私钥 n d。算法的可靠性即在已知 n和e的情况下能否推出d。

ed ≡ 1（mod φ(n)） 只有知道e和φ(n) 才能得出d

φ(n)=(p-1)*(q-1) 只有知道p和q才能得出φ(n) 

n=p*q 只有将n因数分解 才能得到p和q

算法可靠性在于n因数分解，由于大数的因数分解是指数级别复杂程度，所以保证了加密算法的可靠性。

由RSA算法中大数因数分解复杂程度的延伸

大数分解因数为何困难

分解因数是把合数分解为非平凡解（非平凡解：排除1和本身的质因数）。

常规的因数分解 就是判断这个数能否被某一个质数整除，即 a%b==0。

求余的过程其实是用到了除法。除数较小的情况下，求余不是难事。但是当除数很大时，类似高精度除以高精度，除法的效率就不那么高了。

个人认为，计算机在处理大数的除法效率问题导致了大数分解因数困难。

计算机是如何处理除法运算

计算机的四则运算

传统的数学思维里并不能直接用在计算机的四则运算中，例如加法，13+29=42，传统思维直接对位相加，有进位再加上进位。这种思维对应计算机的处理就要用到异或运算，与运算，和左移运算。

13 的二进制 0000 1101 

29 的二进制 0001 1101

异或运算 ：处理0+1的情况

​ 0000 1101 ⊕ 0001 1101 = 0001 0000  ①

与运算：处理1+1的情况，有1代表需要进位，

​ 0000 1101 & 0001 1101 = 0000 1101 

左移运算：非全0就需要左移

​  0000 1101 << 1 =  0001 1010  ②

用 ①、②重复异或运算、与运算、左移运算

0001 0000  ⊕   0001 1010 = 0000 1010  ③ 

0001 0000 & 0001 1010 = 0001 0000 

0001 0000 << 1 = 0010 0000 ④

处理   ③  ④

0000 1010  ⊕ 0010 0000 = 0010 1010 ⑤ 

0000 1010 & 0010 0000 = 0000 0000 ⑥

因为⑥结果全为0，所以 ⑤ 就是最终答案。 ⑤ 转为10进制即2^5+2^3+2^1 = 32+8+2=42。

计算机除法结论

减法就是用补码参与加法运算，乘法就是多个加法运算，本次讨论的除法就是不断地减法操作。所以大数的除法就涉及到不断地异或、与、左移运算导致运算复杂程度升高。

本文由 mdnice 多平台发布