 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/computer-security/1/c/i/solution

n

. Expand the two expressions appearing in the proposed quotient:

c_{2} + 2 c_{1} - 1 c_{2} - c_{1} + 2 \equiv (m + 1)^{3} + 2 m^{3} - 1 = 3 m^{3} + 3 m^{2} + 3 m, \equiv (m + 1)^{3} - m^{3} + 2 = 3 m^{2} + 3 m + 3.

The first is exactly

m

m \equiv (c_{2} + 2 c_{1} - 1) (c_{2} - c_{1} + 2)^{- 1} (mod n) .

The representative in

{0, \dots, n - 1}

is the plaintext. This RSA related-message attack uses a relation between messages to turn two cubic equations into a linear equation; it does not recover the private key or factor

n

in the invertible case.

 New to topics? Read the docs here!