习题_07_08.md

P7 如题:

a. 使用 RSA，选择 p = 3 和 q = 11，采用对每个字母独立地加密的方法加密短语 “dog”。对已加密报文应用解密算法恢复出原报文。

b. 重复 (a), 而此时加密 “dog” 作为一个报文 m。

• a.

  • n = pq = 33
  • z = (p - 1)(q - 1) = 20
  • e = 7 选择 e < n 并且 e 与 z 互质。
  • 求 d 使得 ed mod z = 1，即满足 7d mod 20 = 1, d = 3
  • 故公钥为 (33, 7)，私钥为 (33, 3)
  • 现在使用公钥加密 "dog" 如下所示

  ASCII	10 进制	m^e	m^e mod n
  d	4	4^7	16
  o	15	15^7	27
  g	7	7^7	28

  • 使用私钥解密如下所示

  10 进制	c^d	c^d mod n	ASCII
  16	16^3	4	d
  27	27^3	15	o
  28	28^3	7	g

• b.

  • 假设 d = 00100，o = 01111, g = 00111，拼接起来，就是 001000111100111 = 4583。因为必须要让 n > m，所以重新取 p = 43, q = 107, n = pq = 4601, z = (p-1)(q-1) = 4452. e = 61, d = 73
  • 现在使用公钥加密 4583 如下所示

  m^e	m^e mod n
  4583^61	4583^61 mod 4601 = 402

  • 然后使用私钥解密如下

  c^d	c^d mod n
  402^73	402^73 mod 4601 = 4583

P8 考虑具有 p = 5 和 q = 11 的 RSA。

a. n 和 z 是什么？

b. 令 e = 3。为什么这是一个对 e 的可接受的选择。

c. 求 d 使得 de = 1 mod (z) 和 d < 160

d. 使用密钥 (n, e) 加密报文 m = 8。令 c 表示对应的密文。显示所有工作。提示：为了简化计算，使用如下事实。[(a mod n) * (b mod n)] mod n = (a * b) mod n

• a.

  • n = 55, z = 40

• b.

  • e < n 并且 e 与 z 互质

• c.

  • d = 27, ed = 81, 所以 ed mod z = 1

• d.

  • 加密 : c = m^e mod n = 8^3 mod 55 = 17
  • 解密 : m = c^d mod n = 17^27 mod 55 = 8