CYBER APOCALYPSE CTF 2021 | RSA JAM - crypto-writeup-public

#cyber_apocalypse_ctf_2021

from Crypto.Util.number import getPrime, inverse
import random

def main():
    print("They want my private key, but it has sentimental value to me. Please help me and send them something different.")
    p = getPrime(512)
    q = getPrime(512)
    N = p*q
    phi = (p - 1) * (q - 1)
    e = 0x10001
    d = inverse(e, phi)
    print({'e': e, 'd': d, 'N': N})
    d2 = int(input("> "))
    assert d2 != d
    assert 0 <= d2 < phi
    with open("flag.txt") as f:
        flag = f.read()
    random.seed(str(d2) + flag)
    for _ in range(50):
        m = random.randrange(N)
        c = pow(m, e, N)
        assert m == pow(c, d2, N)
    print(flag)

if __name__ == "__main__":
    import os
    os.chdir(os.path.abspath(os.path.dirname(__file__)))
    main()

overview

RSA で $N, e, d$ が与えられるので $d \ne d_2$ かつ $m^{ed_2} \equiv m \mod n$ となるような $d_2$ を求める問題

solution

通常は $ed \equiv 1 \mod \phi(N)$ を満たすような $e, d$ をつかっているが、これはいわゆるオイラーの定理というものをつかったやつで、更に一般化されたカーマイケルの定理を用いて $\lambda(N)$ で $ed \equiv 1 \mod \lambda(N)$ となるような $d$ でも RSA は成り立つ
$\lambda(N)$ は要するに $lcm(\lambda(p), \lambda(q)) = lcm(p-1, q-1) = \frac{(p-1)(q-1)}{\gcd(p-1, q-1)}$

from ptrlib import Socket
import ast
from math import gcd


def factorize(N, e, d):
    from math import gcd
    import gmpy2

    k = d*e - 1
    t = k
    while t % 2 == 0:
        t //= 2

    g = 3
    while True:
        x = pow(g, t, N)
        if x > 1:
            y = gcd(x - 1, N)
            if y > 1:
                return y, N//y
        g = gmpy2.next_prime(g)

sock = Socket("localhost", 19999)
sock.recvline()
params = ast.literal_eval(sock.recvline().decode())

e = params['e']
d = params['d']
N = params['N']

p, q = factorize(N, e, d)
lam = (p-1)*(q-1) // gcd(p-1, q-1)
d_ = pow(e, -1, lam)
while True:
    if d_ != d:
        break
    d_ += lam

sock.sendlineafter("> ", str(d_))
print(sock.recvline())

how to factorize N given d