# Help understanding basic Franklin-Reiter related message attack

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.

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() # coefficient 0 = -m