现代密码学杨波课后习题讲解课件.ppt

习题 1.证明以下关系： (1) (2) (3) （2）由 ，则存在整数k使a=b+kn，则b=a+(-k)n 解：（1）设 ，由题意得 ，且存在整数 ，使得 可得 即 证得 精选 * 习题 2.证明以下关系： (1) (2) 精选 * 习题 3. 用 Fermat 定理求 3201 mod 11 Fermat定理：若p是素数，a是正整数且gcd(a, p)=1，则ap-1≡1 mod p。 解： p=11，a=3，gcd（3,11）=1 由 Fermat 定理，可知 310≡1 mod 11，则(310)k ≡1 mod 11 ? 所以 3201 mod 11= [(310)20×3] mod 11 = [( (310)20 mod 11)×(3 mod 11)] mod 11 = 3。 精选 * 习题 4. 用推广的 Euclid 算法求 67 mod 119 的逆元。 因此， Euclid算法（辗转相除法） 推广的Euclid（P97） 解： 精选 * 习题 5. 求 gcd(4655, 12075) 。 解： 12075 = 2×4655 + 2765 4655 = 1×2765 + 1890 2765 = 1×1890 + 875 1890 = 2×875 + 140 875 = 6×140 + 35 140 = 4×35+0 所以 gcd(4655, 12075)=35。 精选 * 习题 6.求下列同余方程组 （中国剩余定理） 精选 * 习题 10. 设通信双方使用 RSA 加密体制，接收方的公钥是(e,n)=(5,35)，接收到的密文是 C=10，求明文 M 解： ?(n)=35=5*7 ?(n)= ?(5)*?(7)=( = ( 5-1)*(7-1)=24 因为d*e≡1mod ?(n)， 解得d=5 M=cdmodn=105mod35=5 RSA？密钥产生、加密、解密 精选 * 习题 13. 在 ElGamal 加密体制中，设素数 p=71，本原根 g=7， (1)如果接收方 B 的公开钥是 yB=3，发送方 A 选择的随机整数 k=2，求明文 M=30 所对应的密 文。 (2)如果 A 选择另一个随机整数 k，使得明文 M=30 加密后的密文是 C=(59, C2)，求 C2。 Elgamal：y,p,g,x；密文对 解：(1) C1≡gk mod p = 72 mod 71 = 49， C2≡yBk M mod p = (32×30) mod 71= 57 密文为 C=(C1, C2)=(49, 57)。 (2)由 C1≡ 7k mod 71 = 59 ，解得 k=3 。 所以 C2 = (3k×30) mod 71 = 29。 精选 * 习题 精选 * 习题 精选 * 习题 精选 * 第一章 精选 * 习题 1. 设仿射变换的加密是 E11,23(m)≡11m+23 (mod 26)，对明文“THE NATIONAL SECURITY AGENCY”加密，并使用解密变换 D11,23(c)≡11-1(c-23) (mod 26) 验证你的加密结果。 解：明文用数字表示： m=[19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 4 13 2 24] 密文 C= E11,23(m)≡11*m+23 (mod 26) =[24 22 15 10 23 24 7 21 10 23 14 13 15 19 9 2 7 24 1 23 11 15 10 19 1] = YWPKXYHVKXONPTJCHYBXLPKTB  精选 * 习题 ∵ 11*19 ≡ 1 mod 26 (说明：求模逆元可采用第 4 章的“4.1.7 欧几里得算法”，或者直接穷举 1~25) 对密文 C 进行解密： m’=D(C)≡ 19*(c-23) (mod 26) =[19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 1