When primes share a secret

The challenge

This toy exercise uses tiny integers to illustrate a key-generation failure. The numbers are intentionally unsuitable for real cryptographic use.

The shared factor

If two moduli reuse a prime $p$, their greatest common divisor reveals that shared factor:

For distinct primes $p$, $q_1$ and $q_2$:

Reproducing the observation

from math import gcd

n1 = 61 * 53
n2 = 61 * 47
p = gcd(n1, n2)

assert 1 < p < min(n1, n2)
print(p, n1 // p, n2 // p)

61 53 47

Lessons learned

This example demonstrates factor recovery only. A real assessment would separately verify the relevant public keys, algorithm parameters and authorization to test them. Reliable key generation depends on a correctly initialized, cryptographically secure source of randomness.