problem

RSAの公開鍵$(n, e_1), (n, e_2)$と同じ$m$に対する暗号文$c_1, c_2$が与えられる。 $m$を求めよ。 ただし$e_1, e_2$は素数。

solution

Euclidの互除法をする。 $e_2 = qe_1 + r$とする互除法に合わせて$c_2 \cdot c_1^{- q} \equiv m^r$のようにしていけば$m^{\mathrm{gcd}(e_1, e_2)}$が求まる。 $e_1, e_2$は素数なので自明に互いに素つまり$\mathrm{gcd}(e_1, e_2) = 1$なので$m$が得られる。

implementation

#!/usr/bin/env python3
import ast
import gmpy2
from Crypto.Util.number import long_to_bytes

# input
with open('transcript.txt') as fh:
    n, e1 = ast.literal_eval(fh.readline().split(': ')[1].replace('L', ''))
    c1 = int(fh.readline().split('=')[1])
    fh.readline()
    n, e2 = ast.literal_eval(fh.readline().split(': ')[1].replace('L', ''))
    c2 = int(fh.readline().split('=')[1])

# Euclidean algorithm
assert e1 < e2
while e1:
    c1, c2 = (c2 * pow(gmpy2.invert(c1, n), e2 // e1, n) % n), c1
    e1, e2 = e2 % e1, e1
assert e2 == 1
m = c2

# output
print(long_to_bytes(m).decode())