ACTF 2022 | RSA LEAK - crypto-writeup-public

#ACTF_2022

from sage.all import *
from secret import flag
from Crypto.Util.number import bytes_to_long


def leak(a, b):
    p = random_prime(pow(2, 64))
    q = random_prime(pow(2, 64))
    n = p*q
    e = 65537
    print(n)
    print((pow(a, e) + pow(b, e) + 0xdeadbeef) % n)


def gen_key():
    a = randrange(0, pow(2,256))
    b = randrange(0, pow(2,256))
    p = pow(a, 4)
    q = pow(b, 4)
    rp = randrange(0, pow(2,24))
    rq = randrange(0, pow(2,24))
    pp = next_prime(p+rp)
    qq = next_prime(q+rq)
    if pp % pow(2, 4) == (pp-p) % pow(2, 4) and qq % pow(2, 4) == (qq-q) % pow(2, 4):
        n = pp*qq
        rp = pp-p
        rq = qq-q
        return n, rp, rq
    
n, rp, rq = gen_key()
e = 65537
c = pow(bytes_to_long(flag), e, n)
print("n =", n)
print("e =", e)
print("c =", c)
print("=======leak=======")
leak(rp, rq)

'''
n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
=======leak=======
122146249659110799196678177080657779971
90846368443479079691227824315092288065
'''

$p = a^4 + \delta_p, q = b^4 + \delta_q$ というRSA で、 $n, e, c$ の他に $n_2, leak = \delta_p^e + \delta_q^e + 0xdeadbeef \mod n_2$ がもらえる

$n_2$ は64bit程度の小さい値なので素因数分解でる
$\delta_p, \delta_q$ は24bit程度の小さい値なので全探索可能
- $leak$ に関する式より、片方を全探索するともう片方が一意に定まる
- $\delta_p$ の候補を全探索して、 $\delta_q$ が十分小さい値になればそれを正しいペアと置ける
$n$ の殆どは $a^4b^4$ なので $n^{1/4} \simeq ab$ が成り立つ

あとは $n = (a^4 + \delta_p)(b^4 + \delta_q), ab = ab$ で2式でて2変数未知なので単に連立方程式を解く問題

from tqdm import tqdm
from sympy.solvers import solve
from sympy import symbols
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes


n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840

ab, _ = iroot(n, 4)
a, b = symbols("a, b", integer=True)

n2 = 122146249659110799196678177080657779971
leak = 90846368443479079691227824315092288065

p2 = 8949458376079230661
q2 = 13648451618657980711

d2 = pow(e, -1, (p2-1)*(q2-1))
x = leak - 0xdeadbeef

for rp in tqdm(range(0, 2**24)):
    rq = pow(x - pow(rp, e, n2), d2, n2)
    if rq < 2**24:
        print((rp, rq))

        y = n - (ab**4 + rp*rq)
        solutions = solve([a**4*rq + b**4*rp - y, ab - a*b])
        for sol in solutions:
            print(sol)
            a_ = int(sol[a])

            p = a_**4 + rp
            q = n // p

            d = pow(e, -1, (p-1)*(q-1))
            m = pow(c, d, n)
            print(long_to_bytes(m))

こういうやりかたで、bezout でも解けるらしい

ab  = floor(N^(1/4))
rhs = (N - ab^4 - rp * rq) % N

R.<x> = PolynomialRing(QQ)
f = rq*x^4 + rp*(ab / x)^4 - rhs
a = f.numerator().roots()[0][0]
assert ab % a == 0

b = ab // a
p = (a^4 + rp)
q = N // p
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, N)
print(bytes.fromhex(hex(m)[2:]))