RSA算法中选择p=7q=17e=13计算其公钥与私钥并采用快速模乘反复平方乘方法加密明文m=19
- 计算n=pq=717=119
- 计算φ(n)=(p-1)(q-1)=(7-1)(17-1)=96
- 选择e=13，验证e与φ(n)互质，即gcd(e,φ(n))=1
- 计算d使得de≡1(mod φ(n))，即13d≡1(mod 96)，可以通过扩展欧几里得算法求解得到d=73
- 公钥为(n,e)=(119,13)，私钥为(n,d)=(119,73)
- 加密明文m=19，计算密文c=m^e(mod n)=19^13(mod 119)
- 首先计算19^2=361，然后将361对119取模得到3，即19^2≡3(mod 119)
- 接着计算19^4=(19^2)^2≡3^2=9(mod 119)
- 再计算19^8=(19^4)^2≡9^2=81(mod 119)
- 最后计算19^13=19*(19^8)(19^4)≡1981*9=13761≡44(mod 119)
- 密文为c=44，解密密文得到明文m'=c^d(mod n)=44^73(mod 119)
- 首先计算44^2=1936，然后将1936对119取模得到4，即44^2≡4(mod 119)
- 接着计算44^4=(44^2)^2≡4^2=16(mod 119)
- 再计算44^8=(44^4)^2≡16^2=256≡20(mod 119)
- 接着计算44^16=(44^8)^2≡20^2=400≡5(mod 119)
- 然后计算44^32=(44^16)^2≡5^2=25(mod 119)
- 接着计算44^64=(44^32)^2≡25^2=625≡49(mod 119)
- 最后计算44^73=44*(44^64)(44^8)(44)≡444920*44=2438560≡19(mod 119)
- 明文为m'=19，与原明文相同
原文地址: https://www.cveoy.top/t/topic/g91y 著作权归作者所有。请勿转载和采集!