今年の6月に開催されたredpwnCTFで解けなかったCrypto問題であるratificationの復習をようやく終えたのでそのWriteupになります。

Writeup §

Outline §

通常とは異なり、ではなくが与えられているRSA署名で、署名だけでなくアルゴリズム中で使われている一部のパラメータも与えられている。

この内aで定義されているパラメータはbit数が小さい事を利用して導出出来る。そしてこの値を利用すると、もう1つの素数であるに対してを法とした合同式が手に入り、これは以外の値が既知である式なのでの倍数を生成することが出来る。

この署名は(フラグ開示用のメッセージでなければ)何度でも署名が出来、その度には固定だがaは異なる為、毎回異なったの倍数を生成することが出来る。これを利用して最大公約数をが素数になってかつbit数も合うようになるまで取っていけばを求めることが出来るので、これを利用してフラグ開示用のメッセージの署名を手元で作る事ができる。

配布ソースコード §

#!/usr/bin/env python3
import numpy as np
from Crypto.Util.number import *
from random import randint

flag = open('flag.txt','rb').read()

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537

message = bytes_to_long(b'redpwnCTF is a cybersecurity competition hosted by the redpwn CTF team.')

def menu():
    print()
    print('[1] Sign')
    print('[2] Verify')
    print('[3] Exit')
    return input()

print(p)

while True:
    choice = menu()

    if choice == '1':
        msg = bytes_to_long(input('Message: ').encode())
        if msg == message:
            print('Invalid message!')
            continue

        n1 = [randint(0,11) for _ in range(29)]
        n2 = [randint(0,2**(max(p.bit_length(),q.bit_length())-11)-1) for _ in range(29)]
        a = sum(n1[i]*n2[i] for i in range(29))

        enc = [pow(msg,i,n) for i in n2]
        P = np.prod(list(map(lambda x,y: pow(x,y,p),enc,n1)))
        Q = np.prod(list(map(lambda x,y: pow(x,y,q),enc,n1)))
        b = inverse(e,(p-1)*(q-1))-a
        sig1 = b%(p-1)+randint(0,q-2)*(p-1)
        sig2 = b%(q-1)+randint(0,p-2)*(q-1)
        print(sig1,sig2)

        sp = pow(msg,sig1,n)*P%p
        sq = pow(msg,sig2,n)*Q%q
        s = (q*inverse(q,p)*sp + p*inverse(p,q)*sq) % n

        print(s)
        print("Signed!")

        b_p = sig1 % (p-1)
        d_p = inverse(e, (p-1))
        a_p = (d_p - b_p) % (p-1)
        print(a_p)
        print(a)

    elif choice == '2':
        try:
            msg = bytes_to_long(input('Message: ').encode())
            sig = int(input('Signature: '))
            if pow(sig,e,n) == msg:
                print("Verified!")
                if msg == message:
                    print("Here's your flag: {}".format(flag))
            else:
                print("ERROR HAS OCCURRED...")
        except:
            print("Invalid signature!")

    elif choice == '3':
        print("Good bye!")
        break

よくある署名問題同様、任意のメッセージを署名出来て、フラグを開示する為のメッセージ(ここでは'redpwnCTF is a cybersecurity competition hosted by the redpwn CTF team.')とその署名を提出するとフラグをくれる。当然このメッセージを署名する事は出来ない。

普通の署名であれば公開鍵であるをくれるのだがここでは何故かその素因数の片割れであるをくれる。指数公開鍵であるもくれる。

使われている変数の解析 §

まずn1, n2, encであるがこれらは乱数列である。n1の各要素は高々11まででn2の各要素はまでである。encenc[i] = pow(msg, n2[i], n)となる数列である。

aは一旦飛ばしてP, Qを観察すると、_p[i] = pow(enc[i], n1[i], p), _q[i] = pow(enc[i], n[i], q)となる_p, _qの総積がP, Qになる。先程のencと併せて式にすると次のようになる。

$$ P : \equiv \prod_i {enc}_i^{n1_i} \equiv \prod_i {{msg}^{n1_i+n2_i}} \equiv msg^{\sum_i n1_in2_i} \bmod p $$

$$ Q : \equiv \prod_i {enc}_i^{n1_i} \equiv \prod_i {{msg}^{n1_i+n2_i}} \equiv msg^{\sum_i n1_in2_i} \bmod q $$

なお、encを法とした値なのにP, Qの計算ではを法とした値として良いのかという疑問が浮かぶかもしれないが

$$ x \equiv y \bmod (pq) \Rightarrow \exist k \in \mathbb{Z} \ (x-y = kpq) \Rightarrow x \equiv y \bmod p $$

これが成り立つので特に問題は無い。以後断り無くこれを適用する場面が存在する。

ここで先程飛ばしたaに注目すると

$$ a = \sum_i n1_in2_i $$

であるので、に代入すると次のようになる。

$$ P = msg^a \bmod p $$

$$ Q = msg^a \bmod q $$

続いて登場するのはbだが、これは単純で

$$ e(a + b) \equiv 1 \bmod (p-1)(q-1) $$

となるbを生成している。そしてこのbを用いてsig1, sig2を生成している。これらに関して次のような関係がある。

$$ sig1 \equiv b \bmod (p-1) $$

$$ sig2 \equiv b \bmod (q-1) $$

続いてsp, sqが出現するがそれぞれ最終的にp, qで法を取っているのでpow(msg, sig1, n)npにしても問題無い。Psqに関しても同様でこれを利用すると次のようになる。

$$ sp :\equiv msg^{sig1}msg^{a} \equiv msg^{a+b} \bmod p $$

$$ sq :\equiv msg^{sig1}msg^{a} \equiv msg^{a+b} \bmod q $$

ここで先程のsig1, sig2に関してbと合同であるという事実を用いた(フェルマーの小定理)。

そして最後に署名であるsが計算される。s % p, s % qをそれぞれ計算するとs % p = q*inverse(q, p)*sp % p, s % q = p*inverse(p, q)*sq % qになる。ここである整数k, lを用いてq*inverse(q, p) = kp+1, p*inverse(p, q) = lq+1とおくことが出来るので最終的にq*inverse(q, p)*sp % p = sp % p = pow(msg, a+b, p), p*inverse(p, q)*sq % q = sq % q = pow(msg, a+b, q)になる。

これよりs, p, qに関して整数を用いて次のような関係が成り立つ

$$ s = k_1 p + msg^{a+b} = k_2q + msg^{a+b} $$

右の等式が成り立つ為にはでなくてはならず、は互いに素なのでを、をそれぞれ素因数として含む。

したがってとなるような整数が存在する事から

$$ s \equiv msg^{a+b} \bmod N $$

である。であることから、である(オイラーの定理)。よって最終的にRSA署名を生成している事がわかる。

aのbit数 §

ここでaのbit数を見積もってみるとn1, n2の各要素はそれぞれ4, 1013bit以下であることからn1[i]*n2[i]の各要素は大きくても1017bitである。これが29個あり、その総和がaであるのでaは大きくても1022bitに収まることがわかる。

一方のbit数は1024bitである事からaは明らかにこれらより小さい。よってを法とする式にaが出現し、そこからaと合同な値を求める事が出来た場合はこれに一致する。

ここでの関係があり、この法をに下げると

$$ a \equiv 1/e - b \bmod (p-1) $$

である。を法としてと合同な値はsig1であることを既に示しているのでこれを使ってa = (pow(e, -1, p-1) - sig1) % (p-1)と求めることが出来る。

q-1の抽出 §

一方でを法とした時のaはどうなるかを考える。であることから

が成り立つのでこれを変形して

$$ \exists k \in \mathbb{Z} \ ((a + sig2)e - 1 = k(q - 1)) $$

が成り立つ。故に(a + sig2) * e - 1の倍数になる。

ここで署名毎にa, sig2が変わる一方では変わらないので署名毎に異なるの倍数を手に入れることが出来る。ということは幾つかこの値を手に入れて最大公約数を取っていけばいつかが手に入るはずである(下記ソースコード中では5回で試しているが殆どの場合で手に入った)。

フラグ開示メッセージ署名の作成 §

これでが手に入ったので目標としてるメッセージのRSA署名を手元で作成することが出来る。これをメッセージと共に提出するとフラグが手に入る。

Code §

from pwn import remote
from Crypto.Util.number import isPrime, long_to_bytes, bytes_to_long
from xcrypto import list_gcd
from xcrypto.prime import is_prime


if __name__ == '__main__':
    target = "localhost"
    port = 13337


    e = 65537
    sc = remote(target, port)
    p = int(sc.recvline().rstrip())

    print("[+] p:", p)
    print(p.bit_length())
    assert isPrime(p)

    target_msg = b'redpwnCTF is a cybersecurity competition hosted by the redpwn CTF team.'
    target_n = bytes_to_long(target_msg)

    q_g = []
    for _ in range(5):
        sc.sendline("1")

        sc.recvuntil(b"Message: ")
        msg = b"\x02"
        sc.sendline(msg)

        sig1, sig2 = map(int, sc.recvline().split(b" "))

        print("[+] sig1", sig1)
        print("[+] sig2", sig2)

        a = pow(e, -1, p-1) - (sig1 % (p-1))
        print("[+] a:", a)
        print(a.bit_length())

        s = int(sc.recvline())
        print("[+] s:", s)

        q_g.append((a + sig2)*e - 1)

        sc.recvuntil("Signed!\n")

    q = list_gcd(q_g) + 1
    print("[+] q:", q)
    assert is_prime(q)

    n = p*q
    d = pow(e, -1, (p-1)*(q-1))
    sig = pow(bytes_to_long(target_msg), d, n)

    sc.sendline("2")
    sc.recvuntil(b"Message: ")
    sc.sendline(target_msg)
    sc.recvuntil(b"Signature: ")
    sc.sendline(str(sig))
    sc.recvuntil(b"flag: ")
    flag = sc.recvline().strip().decode()

    print(f"[+] flag: {flag}")

    sc.close()

Flag §

flag{random_flags_are_secure-2504b7e69c65676367aef1d9658821030011f8968a640b504d320846ab5d5029b}

感想 §

当日は解けませんでしたが面白かった上に暗号を解く上でよく使うテクニックが入っていて良かったです。qが署名ごとに変わらない事を忘れていて、1回の署名でq-1を公約数に含むものを探して1時間溶かしたのは内緒です。

リンク, 参考にしたWriteup §