Document Text Contents
Page 15
-15-
9.7 No. We require that ed = 1 mod φ(n), where d is the decryption exponent. But
φ(n) = (p – 1)(q – 1) is an even number, so if e is even, we cannot find such a d.
9.8 The adversary has eavesdropped and thus knows C = Me and C' = Me'. He also
knows e and e'. Furthermore, gcd (e, e') = 1, because e' = e + 2i for some i. (Any non-
trivial divisor of e must be odd, hence not a divisor of 2i, hence not a divisor of e'.)
So the adversary can find integers x and y such that ex + e'y = 1. Hence
Cx × C'y = Mex+e'y = M.
9.9 a. Mallory’s assumption is that Alice’s message is 10x for some integer x. Then we
have c = (10m)e = 10eme, where the computations are modulo n. Mallory can
compute 10e and invert it using the extended Euclidean algorithm to get 10−e.
Finally, he constructs the bid c × (10)−e × 11e, which equals (11m)e, i.e. the
encryption of 11m.
b. Two main ingredients in padding are randomization (to avoid that the same
message encrypted twice gives the same encryption) and redundancy (so that
randomly constructed cipher texts are unlikely to be encryptions of a valid
message)
9.10 n = (p – 1)(q – 1) = 10,200 = 23 3 52 17. e can be any integer relatively prime to n,
such as 7, 143, 689.
-15-
9.7 No. We require that ed = 1 mod φ(n), where d is the decryption exponent. But
φ(n) = (p – 1)(q – 1) is an even number, so if e is even, we cannot find such a d.
9.8 The adversary has eavesdropped and thus knows C = Me and C' = Me'. He also
knows e and e'. Furthermore, gcd (e, e') = 1, because e' = e + 2i for some i. (Any non-
trivial divisor of e must be odd, hence not a divisor of 2i, hence not a divisor of e'.)
So the adversary can find integers x and y such that ex + e'y = 1. Hence
Cx × C'y = Mex+e'y = M.
9.9 a. Mallory’s assumption is that Alice’s message is 10x for some integer x. Then we
have c = (10m)e = 10eme, where the computations are modulo n. Mallory can
compute 10e and invert it using the extended Euclidean algorithm to get 10−e.
Finally, he constructs the bid c × (10)−e × 11e, which equals (11m)e, i.e. the
encryption of 11m.
b. Two main ingredients in padding are randomization (to avoid that the same
message encrypted twice gives the same encryption) and redundancy (so that
randomly constructed cipher texts are unlikely to be encryptions of a valid
message)
9.10 n = (p – 1)(q – 1) = 10,200 = 23 3 52 17. e can be any integer relatively prime to n,
such as 7, 143, 689.
