Franklin-Reiter Related Message Attack

$C_1 = m^e \mod n$

$C_2 = (am + b)^e \mod n$

であり、 $a, b$ 既知のときに有効な攻撃

多項式 $f_1(X) = X^e - C_1$ と $f_2(X) = (aX + b)^e - C_2$ をそれぞれ $Z_n$ 上で考えると、 $f_1(m) = f_2(m) = 0$ なので、 $f_1, f_2$ は $X-m$ を因数に持つ。従って一変数多項式のgcdをやると

$gcd(f_1, f_2) = X - m$ が得られる

という攻撃。別にeが共通である必要はない

from sage.all import *

_, x = PolynomialRing(Zmod(N), name='x').objgen()
f1 = (a1*x + b1)**e1 - c1
f2 = (a2*x + b2)**e2 - c2

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

m = -gcd(f1, f2).coefficients()[0]

def pgcd(a, b):
  while b:
    a, b = b, a % b
  return a.monic()