Write `crack(C, e, n)` — trial-divide the modulus, compute φ(n), invert e, decrypt — and run it on the intercepted values C = 105, e = 7, n = 403.
Write `crack(C, e, n)` — trial-divide the modulus, compute φ(n), invert e, decrypt — and run it on the intercepted values C = 105, e = 7, n = 403.
Answer
def crack(C, e, n): p = next(i for i in range(2, n) if n % i == 0) q = n // p phi = (p - 1) * (q - 1) d = pow(e, -1, phi) M = pow(C, d, n) return p, q, phi, d, M p, q, phi, d, M = crack(105, 7, 403) print(p, q, phi, d, M) print("re-encrypt:", pow(M, 7, 403))
Stallings & Brown 5e ch2 §2.3; ch21 §21.4