It's akin to me having the secret number 17, giving you 221 (17*13) and then, during a solar flare, fucking it up once and giving you 187 (17*11). You know that the numbers are the product of a multiplication, and you know that a common factor is my private secret number. You figure out that the only way to get to 187 and 221 while keeping a common factor is if that factor is 17. That's just computing the GCD.
>An RSA public key consists of a public exponent ๐ and a modulus ๐ = ๐๐ that is the product of two primes. The private key consists of the private exponent ๐ = ๐ โ1 mod ๐ (๐) and ๐ . A textbook RSA signature on a message ๐ is the value ๐ = ๐๐ mod ๐ . To verify the signature, a user checks if ๐ ๐ mod ๐ = ๐
> these attacks exploit the fact that if an error is made while computing modulo one prime, say ๐, then the resulting invalid signature ห๐ is equivalent to the correct signature modulo one prime factor ๐, but not ๐. 2.2.1 GCD attack on fully known messages. Boneh, DeMillo, and Lipton noted [11] that if an attacker had a correct signature ๐ and an incorrect signature ห๐ of this form then the attacker could compute gcd(๐, ห๐ โ ๐ ) = ๐
