Help understanding basic Franklin-Reiter related message attack

Question

I am trying to understand this attack at the most basic level. I set up the following basic scenario:
Let the public encryption exponent, e = 3.
Let p, be some arbitrary but known (to the eavesdropper) padding of a couple characters. Suppose an eavesdropper has intercepted two encrypted messages $C_1$ and $C_2$ from Bob to Alice, where,

$C_1 \equiv M_1^3$ (mod n); and,
$C_2 \equiv (M_1 + p)^3$ (mod n)

In the answer to this question, if I am understanding it correctly, that to find M, we must determine $gcd(M_1^3 - C_1, (M_1 + p)^3-C_2)$.
Do I have this right? If so how would I go about using the Euclidean Algorithm to do this? These look like polynomials to me and I am somewhat familiar with finding the gcd of two polynomials using the EA, but I just can't seem to figure out how to apply that here.

Answer 1

It seems you are well on your way to understanding the attack. After you compute the GCD of these two polynomials you are left with a polynomial of the form $X - m$. It is clear why—if $f_1(X) = X^3 - C_1$ and $f_2(X) = (X + p)^3 - C_2$ have a common root $m$, then they are of the form $(X - m)g_1$ and $(X - m)g_2$, for some arbitrary $g_1$ and $g_2$.

So, $-m$ is the coefficient of degree $0$ of this common polynomial, and all that is left to do is to extract it. Here's a worked out example in Sage:

p = random_prime(2^512)
q = random_prime(2^512)
n = p * q # 1024-bit modulus

m = randint(0, n) # some message we want to recover
r = randint(0, n) # random padding

c1 = pow(m + 0, 3, n)
c2 = pow(m + r, 3, n)

R.<X> = Zmod(n)[]
f1 = X^3 - c1
f2 = (X + r)^3 - c2

# GCD is not implemented for rings over composite modulus in Sage
# so we'll do it ourselves. Might fail in rare cases, but we
# don't care.
def my_gcd(a, b): 
    return a.monic() if b == 0 else my_gcd(b, a % b)

print m
print - my_gcd(f1, f2).coefficients()[0] # coefficient 0 = -m