Untitled
CM30173: Example sheet 7
20th March
All questions relate to RSA and factoring.
1. [Question 5.15 p. 228 from Stinson:]
This exercise exhibits what is called a protocol failure. It provides an example where
ciphertext can be decrypted by an opponent, without determining the key, if a cryptosys-
tem is used in a careless way. The moral is that it is not sufficient to use a “secure”
cryptosystem in order to guarantee “secure” communication.
Suppose Bob has an RSA Cryptosystem with a large modulus n for which the factorization
cannot be found in a reasonable amount of time. Suppose Alice sends a message to Bob by
representing each alphabetic character as an integer between 0 and 25 (i.e., A↔ 0, B ↔ 1,
etc.), and then encrypting each residue modulo 26 as a separate plaintext character.
(a) Describe how Oscar can easily decrypt a message which is encrypted in this way
(b) Illustrate this attack by decrypting the following ciphertext (which was encrypted
using an RSA Cryptosystem with n = 18721 and b = 25) without factoring the
modulus:
365, 0, 4845, 14930, 2608, 2608, 0
2. Let n = 2147713027 be an RSA modulus and φ(n) = 2147614720, factor n using your
knowledge of φ(n).
3. Let (n, b) = (25591, 5) be a public RSA key and suppose you have found out the private
exponent a = 10109. Use a to factor n.
4. Factor n = 1411 with Dixon’s random squares method (select auxiliary numbers at ran-
dom) or using the same method but with auxiliary numbers of the form j + ⌈
√
n⌉ for
j = 0, 1, 2, . . .. Use B = 11 as the factor base bound.
5. [Question 5.13 p. 227 from Stinson:]
A common way to speed up RSA decryption incorporates the Chinese remainder theorem,
as follows. Suppose that dk(y) = y
d (mod n) and n = pq. Define dp = d (mod p−1) and
dq = d (mod q − 1); and let Mp = q−1 (mod p) and Mq = p−1 (mod q). Then consider
the following algorithm:
Algorithm (5.15).
CRT-optimized RSA decryption(n, dp, dq, Mp, Mq, y)
xp ← ydp (mod p)
xq ← ydq (mod q)
x←Mpqxp + Mqpxq (mod n)
return (x)
Question continues…
Algorithm 5.15 replaces an exponentiation modulo n by modular exponentiations modulo
p and q. If p and q are l-bit integers and exponentiation modulo an l bit integer takes
time cl3, then the time to perform the required exponentiation(s) is reduced from c(2l)3 to
2cl3, a saving of 75%. The final step, involving the Chinese remainder theorem, requires
O(l2) if dp, dq, Mp and Mq have been pre-computed.
(a) Prove that the value x returned by algorithm 5.15 is, in fact, yd (mod n).
(b) Given that p = 1511, q = 2003 and d = 1234577, compute dp, dq, Mp and Mq.
(c) Given the above values of p, q and d, decrypt the ciphertext y = 152702 using
algorithm 5.15.