使用素数 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.