密码学小记

Reference

RSA

探秘公钥加密算法 RSA

RSA加密算法

RSA 算法

符号定义

• $m$：message
• $N$：
• $e$：encrypt
• $d$：decrypt
• $c$：cypher

加密与解密的过程

Encryptian 加密

=> $(N,e)$

$$m^{e}modN=c$$

Decryptian 解密

=> $(N,d)$

$$c^{d}modN=m$$

推导

$$m^{ed}modN=m$$

欧拉定理：$m^{\phi (n)}\equiv 1(modn)$

• $\phi (n)$：欧拉公式

$$\begin{array}{rl}(m^{\phi (n)}{)}^k& \equiv 1^k(modn)\\ m^{k\phi (n)}& \equiv 1(modn)\\ m^{k\phi (n)+1}& \equiv m(modn)\\ m^{k\phi (n)+1}modn& \equiv m\end{array}$$

$$ed=k\phi (n)+1$$$$d=\frac{k\phi (n)+1}{e}$$

关于如何确保d始终是整数这件事我还十分困惑呜呜呜

举个例子

$e$ 和 $d$ 的产生

• $p=17$
• $q=23$
• $\phi (17\times 23)=\phi (391)=352$

$$d=\frac{k\phi (n)+1}{e}=\frac{5\times 352+1}{3}=587$$

$e=3$ 是人为选取的

模拟加密过程

利用上述 $e$ 和 $d$ 加密字符 "a" -> 97

$$c={97}^{3}mod391=79$$

模拟解密过程

$$m={79}^{587}mod391=97$$