在RSA密码算法中,取两个素数7和17,e取5,根据密码算法,计算一组公钥和私钥.如果明文为15,则密文是什么值?计算N=pq=7*17=119欧拉函数∮(n)=(p-1)(q-1)=6*16=96计算私钥d:5d=1mod96,解得d=77所有,公钥PK=(e,N)={

Question

在RSA密码算法中,取两个素数7和17,e取5,根据密码算法,计算一组公钥和私钥.如果明文为15,则密文是什么值?
计算N=pq=7*17=119
欧拉函数∮(n)=(p-1)(q-1)=6*16=96
计算私钥d:5d=1mod96,解得d=77
所有,公钥PK=(e,N)={5.119};私钥SK=(d.N)={77.119}
密文C=15^5mod119=36
为什么:
d:5d=1mod96,解得d=77?怎么就等于77了啊?
C=15^5mod119=36?是怎么算的啊?怎么就等于36了啊?
不好意思啊,,我好象真的是个菜菜...我就是不知mod的意思.好久没看书了...帮我解释下...在此感激不尽...

Answer 1

题目很简单,出现这种问题证明你要好好看下数论了.特别是欧拉定理.根据数论,若x与y互为素数,则x^-1 mod y存在唯一整数解.由此,告诉你一种简洁的求d的方法,该法是根据模的逆运算的原始定义求解,即：ed=k(p-1)(q-1)+1 式中d和k都是整数.因为e与(p-1)(q-1)互为素数,所以存在唯一整数解.这样可以通过搜索法找到d.
由上题：e=5,(p-1)(q-1)=96
带入公式试值得：5d=96*k+1 k=4,d=77 (k与d同时为整数)
c的求法：
由15^5mod119=(((15^2mod119)^2mod119)*15)mod119=36
以上全是手算,当然还可以用计算器,有mod功能的,太简单了.
别这么说,什么菜不菜的,大家一起讨论.
mod就是求余,比如：7mod2=1,就是7/2余1
公式：余数=|被除数-商*除数|