pbctf2020 | Special Gift - crypto-writeup-public

#!/usr/bin/env python3

from Crypto.Util.number import getStrongPrime, inverse, bytes_to_long, GCD as gcd
from Crypto.Random.random import randint
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q
phi = (p - 1) * (q - 1)

# Hehe, boi
while True:
    d = randint(int(N ** 0.399), int(N ** 0.4))
    if gcd(d, phi) == 1:
        break

e = inverse(d, phi)

# Here's a special gift. Big.
gift = d >> 120

enc = pow(bytes_to_long(flag), e, N)

print("N =", N)
print("e =", e)
print("gift =", gift)
print("enc =", enc)

$d \simeq N^{0.4}$ で、かつ $d$ の一部 $d'$ が与えられている。未知数 $d_0$ を用いて $d = d' + d_0$ とする

RSAのパラメータ同士の関係より適当な正整数 $k$ を導入して

$ed \equiv 1 \mod \phi$

$ed = 1 + k(N - (p+q) + 1)$

$N \simeq (N - (p+q) + 1)$ なので

$k \simeq \frac{ed-1}{N}$

今は $d \simeq d'$ なので更に

$k \simeq \frac{ed'-1}{N} = k'$

$k$ についても未知数 $k_0$ を用いて $k = k' + k_0$ と表す

これを $ed = 1 + k(N-(p+q)+1)$ に代入、また $s = p + q - 1$ とおいて

$e(d' + d_0) = 1 + (k' + k_0)(N - s)$

$\mod e$ とってみると

$0 \equiv 1 + k'N-k's+k_0N-k_0s \mod e$

これは $s, k_0$ を変数として持つMultivariate Polynomialであることがわかる。ので解く

import itertools
from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence

# https://github.com/defund/coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = PolynomialSequence([], f.parent())
    for i in range(m+1):
        power = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = power
            for variable, shift in zip(f.variables(), shifts):
                g *= variable^shift
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    B = B.change_ring(ZZ)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in B*monomials:
        if h.is_zero():
            continue
        H.append(h.change_ring(QQ))
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            V = I.variety(ring=ZZ)
            if V:
                roots = []
                for root in V:
                    root = map(R, map(root.__getitem__, f.variables()))
                    roots.append(tuple(root))
                return roots

    return []


N = 124588792854585991543122421017579759242707321792822503200983206042530513248160179498235727796077646122690756838184806567078369714502863053151565317001149999657802192888347495811627518984421857644550440227092744651891241056244522365071057538408743656419815042273198915328775318113249292516318084091006804073157
e = 109882604549059925698337132134274221192629463500162142191698591870337535769029028534472608748886487359428031919436640522967282998054300836913823872240009473529848093066417214204419524969532809574214972094458725753812433268395365056339836734440559680393774144424319015013231971239186514285386946953708656025167
gift = 870326170979229749948990285479428244545993216619118847039141213397137332130507928675398
enc = 67594553703442235599059635874603827578172490479401786646993398183588852399713973330711427103837471337354320292107030571309136139408387709045820388737058807570181494946004078391176620443144203444539824749021559446977491340748598503240780118417968040337516983519810680009697701876451548797213677765172108334420
d_ = gift << 120
k_ = round((e * d_ - 1) / N)


PR.<x, y> = PolynomialRing(Zmod(e))
f = 1 + k_*N - k_*y + x*N - x*y
k0, s = small_roots(f, [2^120, floor(3 * N^0.5)], m=3, d=5)[0]
print(s)

from Crypto.Util.number import inverse, long_to_bytes
phi = N - int(s)
d = inverse(e, phi)
m = pow(enc, d, N)

print(long_to_bytes(m))