使用素数 29 61 根据RSA算法生成密钥 写出完整过程

题目

使用素数 29 61 根据RSA算法生成密钥 写出完整过程

答案

取n=29×61=1769； Φ(n)=(29-1)×(61-1)=1680=(2∧4)×3×5×7； dw≡1(mod 1680)；d、w为正整数,且w和Φ(n)即1680互素； 取dw=1681,则d=w=41； 假设明文为m、密文c(m＜n、c＜n),则:加密算法:c=m∧w (mod n)； 解密算法:m=c∧d(mod n)；即:c=m∧41(mod 1769)； m=c∧41(mod 1769).比如:m=2；d和w的二进制形式为101001；加密计算如下:E0≡m≡2(mod 1769)； E1≡2∧2≡4(mod 1769)； E2≡4∧2≡16(mod 1769)； E3≡16∧2≡256(mod 1769)； E4≡256∧2≡83(mod 1769)； E5≡83∧2≡1582(mod 1769)； c≡2∧41≡E0×E3×E5≡2×256×1582≡1551(mod 1769),即密文为c=1551；解密计算如下:D0≡c≡1551(mod 1769)； D1≡1551∧2≡1530(mod 1769)； D2≡1530∧2≡513(mod 1769)； D3≡513∧2≡1357(mod 1769)； D4≡1357∧2≡1689(mod 1769)； D5≡1689∧2≡1093(mod 1769)； 所以m≡D0×D3×D5≡1551×1357×1093≡2(mod 1769),即明文为m=2.