p和q都是質數

n = pq

取n歐拉函數 phi(n)

phi(n) = (p-1)(q-1)

取 e,d < phi(n) ,e,d與phi(n) 互質,且滿足:

ed equiv 1 pmod {phi(n)} ag{1}

所以:

ed = kphi(n)+1 ag{2}

公鑰就是 (n,e) , 私鑰就是 (n,d) 。

假設明文內容: m , 密文內容: c 。

加密過程: m^{ed} equiv m pmod {n} ag{3}

m^e = c pmod{n}

解密過程:

c^d = m pmod{n}

以上RSA加解密等同於證明:

把2代入3，則:

m^{kphi(n)+1} equiv m pmod{n} ag{4}

即:

m^{kphi(n)}m equiv m pmod{n} ag{5}

當m和n互質時

m^{phi(n)} equiv 1 pmod{n}

(m^{phi(n)})^k equiv 1 pmod{n} ag{7}

m equiv m pmod{n} ag{8}

7和8根據同餘式相乘法則，即可證明式5，4,最終證明3

m^{ed} equiv m pmod {n} ag{3}


推薦閱讀：
查看原文 >>
相關文章