Coppersmith's Short Pad Attack - crypto-writeup-public

RSAで同一modにおける2つの暗号文があり、2つの平文の差が小さい時に使える攻撃。つまり

$c_1 \equiv m^{e_1} \mod n$

$c_2 \equiv (m + \delta)^{e_2} \mod n$

このとき、 $f_1 = m^{e_1} - c_1, f_2 = (m + \delta)^{e_2} - c_2$ としてresultantで $m$ を消去した $f$ を求めると $f$ は $\delta$ だけの式になり、univariate coppersmith methodで小さい根 $\delta$ を求められれば、Franklin-Reiter Related Message Attackの要領でGCDをとって $m$ が求まる

def resultant(f1, f2, remove_var):
    """
    PR.<x, y> = PolynomialRing(Zmod(n))
    f1 = ...
    f2 = ...

    fn, xn = resultant(f1, f2, y) # yを消去する
    # fnはxnについての1変数多項式であることが期待できる
    """

    modulus = f1.base_ring().cardinality()
    gens = f1.parent().gens()
    assert len(gens) == 2
    gen_idx = list(gens).index(remove_var)

    gen_name = f1.parent().variable_names()[1 - gen_idx]
    namez = [name + "z" for name in f1.parent().variable_names()]
    namen = gen_name + "n"

    PRz = PolynomialRing(Zmod(modulus), namez)
    q1 = f1.change_ring(PRz)
    q2 = f2.change_ring(PRz)

    PRn = PolynomialRing(Zmod(modulus), [namen])
    xn = PRn.gen()
    f = q1.resultant(q2, gens[gen_idx])
    f = f.univariate_polynomial().change_ring(PRn).subs(**{gen_name: xn})
    return f, xn

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

p = random_prime(2**512)
q = random_prime(2**512)

n = p * q
e = 3

m1 = randint(2, n-1)
delta = randint(2, 2**60)
m2 = m1 + delta

assert m2 < n

c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

PR.<m, d> = PolynomialRing(Zmod(n))

f1 = m**e - c1
f2 = (m + d)**e - c2

fn, dn = resultant(f1, f2, m)
roots = fn.small_roots(X=2**60, beta=1, epsilon=0.05)
assert len(roots) > 0

PR.<x> = PolynomialRing(Zmod(n))
f1 = x**e - c1
f2 = (x + roots[0])**e - c2
m = -gcd(f1, f2).constant_coefficient()
assert m == m1