SECCON 14 quals: yukari Writeup

yukari

authored by chocorusk

yukari zone♡

#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime, isPrime

with open("flag.txt", "r") as f:
    FLAG = f.read()

for _ in range(32):
    p = getPrime(1024)
    print("p =", p)

    q = int(input("q: "))
    assert p != q
    assert q.bit_length() >= 1024
    assert isPrime(q)

    n = p * q
    e = getPrime(64)
    d = pow(e, -1, (p - 1) * (q - 1))

    try:
        cipher = RSA.construct((n, e, d))
    except:
        print("error!")
        continue
    print("key setup successful")
    exit()

print(FLAG)

いつも通りのRSA暗号です。
ランダムな$p$が与えられ、RSA.construct関数が失敗するように$q$を取る必要があります。
$q$の条件としては、

1. p != q
2. $q$のビットが1024ビット以上
3. $q$は素数
   の3つを満たす必要があります。

解法

大会中はyukari-infinityのアイデアで解いてしまったので、warmup用の解き方で説明します。

https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/PublicKey/RSA.py
上記のコードはRSA.constructが書かれているコードです(539行以下)。
さて、ここで気になるのは以下になります。

            if hasattr(key, 'u'):
                # CRT coefficient
                if u <= 1 or u >= q:
                    raise ValueError("Invalid RSA component u")

この uは

            u = p.inverse(q)

で定義されています。
さて、このコードから
$$
u \equiv q \pmod p
$$
となるとき、$u\leq 1$の時にエラーが返されます。
つまり、
$$
q \equiv 1 \pmod p
$$
となるような$q$を見つけたらいい。
ここで、$p$がランダムに与えられるので、$q$を$p$に依存した形で定義したい。
$\text{mod}\space p$であることを考えると
$$
q = kp + 1 (k \in \mathbb{Z})
$$
とすればよいことがわかる。
すると、
$$
q \equiv kp + 1 \equiv 0 + 1 \equiv 1 \pmod p
$$
となるため、$u$の値が1となりエラーとなる。
最後に、このまま実装すると、奇数->偶数->奇数と続いてしまう。そのため、$q = 2kp +1$とすることで毎回奇数にできる。
これを実装すると以下となる。

from pwn import *
from Crypto.Util.number import isPrime, getPrime
from Crypto.PublicKey import RSA

HOST = "yukari.seccon.games"
PORT = 15809
io = remote(HOST, PORT)

for i in range(32):
    k=1
    log.info(f"{i+1}/32")
    p = int(io.recvline()[4:].strip())
    while True:
        q = 2*k*p + 1
        k += 1
        try:
            assert p != q
            assert q.bit_length() >= 1024
            assert isPrime(q)
        except:
            continue

        n = p * q
        e = getPrime(64)
        d = pow(e, -1, (p - 1) * (q - 1))

        try:
            RSA.construct((n, e, d))
        except:
            break
    
    log.info("send q")
    io.sendline(str(q).encode())
    io.recvline()

io.interactive()

Flag: SECCON{9cb27d297988cdae22deca33d5e54a6955d6f95a010c6aec737ff7509f4ac715}