RSA

RSA算法是1977年由 Ron Rivest, Adi Shamir, Leonard Adleman 提出的公钥密码体制public-key cryptosystem；公钥密码体制也称非对称密码体制asymmetric cryptosystem

在公钥密码体制中，加密密钥与解密密钥是不同的，加密密钥简称公钥public key，解密密钥简称私钥private key

Details

1. 随机选择两个不等大素数 $p$ 和 $q$
2. 计算出 $n=p*q$ ($n$ 的长度就是密钥的长度)
3. 选择一个数 $e$ 使它和 $\phi(n)=(p-1)(q-1)$ 互素，且满足 $1<e<\phi(n)$
4. 计算 $e$ 在模 $(p-1)(q-1)$ 的逆元 $d$
5. 公开 $(e,n)$ 作为RSA公钥，保留 $(d,n)$ 作为RSA私钥
6. 加密公式：$c=m^e(mod\ n)$；解密公式：$m=c^d(mod\ n)$

Note - 加密时明文$m$的位数应该与$N$相同

<aside> 📌 加密与解密时都没有用到：p、q、(p-1)*(q-1)，只要n足够大，比如达到1024位，即2^1024，则在 短时间内无法把n分解成p、q的乘积

</aside>

Proof

设 $m$ 是明文，$c$ 是密文：$c=m^e\ mod\ n$，现要证明 $m=c^d\ mod\ n$

$\because ed = 1 \mod (p-1)(q-1)$，

$\therefore \exist k$ 使得 $ed = 1 + k(p-1)(q-1)$ 成立，于是

$\because\phi(n)= \phi(pq) = \phi(p)\phi(q)= (p-1)(q-1)$

$\therefore c^d = m^{ed} = m^{1 + k(p-1)(q-1)} = m * m^{k(p-1)(q-1)} = m * m^{\phi(n)k} (\mod n)$