2011年~ 2012 学年第一学期密码学基础网络工程0901-0902 开课时间:2011-08
第四章习题:
1.用Fermat定理计算
(1)3201mod 11,(2)2325mod 5,(3)3516mod 7,(4)81003mod 11。
2.用推广的Euclid算法求67 mod 119的逆元。
3.求(4655,12075)。
4.设通信双方采用RSA密码体制,接收方的公开钥(e,n)=(5,35),接收到的密文c=10,求明文m。
5.RSA密码取p=5,q=7,n=35,e=7,以00~25表示A~Z,每个字段是2位数字。
(1)把STOP变换成密文
(2)收到密文32 14 32,把它变换成明文。
习题解答:
1.用Fermat定理计算
(4)81003mod 11。
解:因(8,11)=1,⇒810≡1mod 11⇒81003mod 11≡(810)10083mod 11≡6mod 11
2.用推广的Euclid算法求67 mod 119的逆元。
解:119=1╳67+52,67=1╳52+15,52=3╳15+7,15=2╳7+1。
1=15-2╳7,7=52-3╳15,15=67-1╳52,52=119-1╳67。
1=15-2╳7=15-2╳(52-3╳15)=7╳15-2╳52=7╳(67-1╳52)-2╳52=7╳67-9╳52=7╳67-9╳(119-1╳67)=16╳67-9╳119。
得67-1≡16 mod 119。
4.设通信双方采用RSA密码体制,接收方的公开钥(e,n)=(5,35),接收到的密文c=10,求明文m。
解:n=p╳q=5╳7=35,φ(n)=(5-1)(7-1)=24,e=5,(e,φ(n))=(5,24)=1,计算d,满足de ≡1 modφ(n)或5d≡1 mod 24。
24=4╳5+4,5=1╳4+1,1=5-4,4=24-4╳5。
1=5-4=5-(24-4╳5)=5╳5+24╳(-1)。
得d=5-1=5。
m=D(c)≡c d mod 35≡105mod 35≡100000mod 35=25。
《现代密码学》,杨波,清华大学出版社,2007年4月第4章公钥密码- RSA算法 1。