RSA加密

利用大整数分解的困难性

• 公钥(加密)：$\left(e,n\right)$

• 私钥(解密)：$\left(d,n\right)$

$n=p\cdot q$，$p$和$q$为两个大素数

$\left(e,\varphi\left(n\right)\right)=1$

$e\cdot d\equiv 1\left(\mod \varphi\left(n\right)\right)$

• 加密

  $E\left(P\right)=C\equiv P^e\left(\mod n\right)$

  • 准备好$p,q$，计算$n=p\cdot q,\varphi\left(n\right)$

  • 假设一个与$\varphi\left(n\right)$互质的$e$，求出$d$

  • 使用公钥加密信息$m$：$m^e\equiv c\left(\mod n\right)$

• 解密

  $D\left(C\right)=C^d\equiv {\left(P^e\right)}^{d}\equiv P^{e\cdot d}$

  $\equiv P^{k\cdot\varphi\left(n\right)+1}\equiv\left(P^{\varphi\left(n\right)}\right)P\equiv P\left(\mod n\right)$

  • 求解$c^d\left(\mod n\right)$