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)`