Layer7 CTF 2020 | Baby Coppersmith - crypto-writeup-public

#!/usr/bin/env sage
from Crypto.Util.number import bytes_to_long as b2l

def generate():
    p = random_prime(2 ** 1024)
    q = random_prime(2 ** 1024)
    e = random_prime(200, False, 150)
    d = inverse_mod(e, (p-1)*(q-1))
    n = p * q
    return [n, e, p, q, d]

if __name__ == '__main__':
    n, e, p, q, d = generate()
    key = [n, e, p, q, d]

    flag = b2l(open("flag.txt").read())
    ct = pow(flag, e, n)

    secret = d % (p-1)
    bits = secret.nbits()
    bias = bits // 10

    secret = secret >> (bits//2 - bias)

    print (n, secret)
    print (ct)

RSA univariate coppersmith method

RSA-CRTで、 $d_p$ の上位bitが判っている

削られるのは $d_p$ の半分より小さいbit数であることもわかっている

こういう場合、 How to recover cryptographic keys from partial informationにのっている手法が使える

$d_p = a + r$ （ $a$ 既知、 $r$ 未知）とおいて、

$ed_p = 1 + k_p(p - 1)$ より

$ed_p - 1 + k_p = k_pp$

$d_p$ を展開して $\mod p$ とると

$ea + er - 1 + k_p \equiv 0 \mod p$

で、未知数は $k_p, r$ だが、 $k_p$ が小さいことを期待してブルートフォースできる

$d_p$ がわかればあとはdpがわかっているときの素因数分解をやるだけ

def factor_by_dp(n, e, dp):
    a = 2
    while True:
        x = pow(a, e * dp - 1, n) - 1
        p = int(gcd(x, n))
        if p != n and p != 1 and n % p == 0:
            break
        a += 1

    q = n // p
    if p > q:
        p, q = q, p

    return p, q

na, c = open("encrypt").read().strip().split("\n")

n, a = eval(na)
c = int(c)

from subprocess import run
r = run(["/usr/bin/python3", "size.py", str(a.bit_length())], capture_output=True)
size = int(r.stdout.decode().strip())
a = a << size

for e in range(150, 200):
    print("[+] e:", e)
    for kp in range(0, e):

        PR.<x> = PolynomialRing(Zmod(n), implementation="NTL")
        f = e * (x + a) + kp - 1
        f = f.monic()

        r = f.small_roots(X=2**size, beta=0.5, epsilon=0.05)
        if r:
            print("[+]kp:",kp)
            dp = a + r[0]

            p, q = factor_by_dp(n, e, dp)
            phi = (p-1)*(q-1)
            d = inverse_mod(e, phi)
            m = power_mod(c, d, n)
            print(bytes.fromhex(hex(m)[2:]))
            quit()

import sys

sys.path.append("/home/user/.local/lib/python3.8/site-packages")

from z3 import *

solver = Solver()
s = Int("size")
solver.add(s - (s / 2 - s / 10) == int(sys.argv[1]))
r = solver.check()
if r != sat:
    quit()
s = solver.model()[s].as_long()
print(s // 2 - s // 10)