RSA algorithom
介紹
一種使用質數的非對稱加密法
數學的部分
歐拉函數 $\phi(n)$
$\phi(n)$是從0~n-1與n互質數量 eg. $\phi(8) = 4$ 因為 $8和1, 3 ,5 ,7互質$ ps. 質數的$\phi(n)$是n-1喔
模數(mod)
aka取餘數 eg. $8mod3 = 2$
反模數(mod)
一整數a對同餘n之模反元素是指滿足以下公式的整數 $ab\mod(n)=1$
取得方法用擴展歐幾里得
共餘 $\equiv$
兩數的餘數相同，即是共餘 $8\equiv13\mod(5)$
RSA 公鑰私鑰的生成
- 隨機取兩質數$p,q$
- $N = p * q$
- $\phi(N)=\phi(p)*\phi(q)$
public key 選擇一數字e，使e<r，且r e互質 則公鑰為{N,e}
private key 取e對$\phi(n)$反模得到d 則私鑰為{N,d}
加密解密
加密
x是明文，y是密文 $x^e\mod(n)=y$
解密
y是密文，x是明文 $y^d\mod(n)=x$
