Jimmy's Blog: RSA非對稱加密演算法 (三) 演算法證明

根據上一篇的數學理論，可以證明RSA演算法的解密是正確的

先把RSA產生key的過程再寫一次

1.

$選擇兩相異質數p,q，求得N=pq$
2.

$\phi(N)=(p-1)(q-1)$
3.

$選一數e當公鑰1 <= e < \phi(N)，求出模反原數，ed -= 1 ( mod \phi(N))$ 接下來就能加解密了訊息為

$m$ 加密後為

$C$ ，

$C=m^e mod N$ 解密方法

$C^d mod N$ 也就是要證明

$m^(ed) -= m (mod N)$

$分成m=0，m!=0來討輪$

$m=0時，0^(ed)-=0 (mod N)$

$m^(ed)-=m (mod N)$

$m!=0時$

$ed -= 1 (mod \phi(N))$

$ed -= 1 (mod (p-1)(q-1) )$

$=>ed -= 1 (mod (p-1)) , ed -= 1 (mod (q-1))$

$可以看成ed除以(p-1)的餘數是1，把它寫成ed=k(p-1)+1$

$m^(ed)=m^(k(p-1))m=(m^(p-1))^km$
再利用費馬小定理

$m^(p-1)-=1 (mod p)$

$m^(ed)=(m^(p-1))^km-=1^km-=m (mod p)$
同理

$m^(ed)-=m (mod q)$

$p,q為質數，lcm(p,q)=pq$

$=>m^(ed)-=m (mod pq)$

$=>m^(ed)-=m (mod N)$

Jimmy's Blog