RSA

RSA介绍：

• RSA是一种非对称加密算法，即加密和解密时用到的密钥不同。
• 加密密钥是公钥，可以公开；解密密钥是私钥，必须保密保存。
• 基于一个简单的数论事实：两个大质数相乘很容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥，即公钥；而两个大质数组合成私钥。

RSA步骤：

取两个大质数p和q，相乘得到n

p
q
n = p * q

根据(p-1)*(q-1)得到加密密钥e

1 < e < (p-1)*(q-1)
gcd(e, (p-1)*(q-1)) = 1

根据e和(p-1)*(q-1)得到解密密钥d

1 < d < (p-1)*(q-1)
d = e^-1 mod((p-1)*(q-1))
#  e*d ≡ 1 mod((p-1)*(q-1))
#  e*d % (p-1)*(q-1) = 1

对A加密

B = A^e mod n

对B解密

A = B^d mod n