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.