简介

RSA加密算法是一种非对称加密算法，所谓非对称，就是指该算法加密和解密使用不同的密钥，即使用加密密钥进行加密、解密密钥进行解密，分别称为公钥和私钥

在RAS算法中，公钥是公开的，而私钥是需要保密的。加密算法和解密算法也都是公开的。虽然私钥是由公钥决定的，但由于无法计算出大数n的欧拉函数phi(N)，所以不能根据公钥计算出私钥，这就是RSA的安全性

使用方法：

• 乙方生成两把密钥(公钥和私钥)。公钥是公开的，任何人都可以获得，私钥则是保密的。
• 甲方获取乙方的公钥，然后用它对信息加密。
• 乙方得到加密后的信息，用私钥解密。

数论基础

欧拉函数

φ(n)表示小于n且与n互素的正整数

• 对于素数来说，φ(n) = n – 1
• 对于不是素数的数来说，可以将n进行质因数分解，再套用$φ(n)=n*(1-\frac{1}{p_1})(1-\frac{1}{p_2})......(1-\frac{1}{p_c})$

欧拉函数的原理这里就不介绍了，只需要知道素数的欧拉函数等于它-1即可

欧拉定理

a^φ(n) % n = 1

乘法逆元

(a*b)%n=1，就称b是a在模n下的乘法逆元，求逆元的方法有两种，如果n是素数，那利用费马小定理可以知道逆元b = a ^n-1%n,如果不是素数，就只能用扩展欧几里得计算了，这里就不展开

RSA算法流程

密钥的产生

• 取两个保密的大素数p和q
• 计算n = p * q, n的欧拉函数值为φ(n) = (p – 1) * (q – 1)
• 任取一个整数 e， 1<e<φ(n)，且与φ(n)互素
• 计算e在模φ(n)意义下的乘法逆元d
• 公钥为(e, n), 私钥为(d, n)

加密

也就是$c = m^emodN$,m为明文，c为密文

解密

也就是$m = c^dmodN$

RSA解密的正确性证明