Zenn
🔓

SECCON 2022 CTF writeup (pqpq)

2022/11/14に公開
#
CTF
#
seccon
tech

問題

暗号化の手順を示したソースコードと、その実行結果が与えられる。特殊な RSA 暗号で暗号化されている cm を復号すればいい問題。

source.py
from Crypto.Util.number import *
from Crypto.Random import *
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
e = 2 * 65537

assert n.bit_length() // 8 - len(flag) > 0
padding = get_random_bytes(n.bit_length() // 8 - len(flag))
m = bytes_to_long(padding + flag)

assert m < n

c1p = pow(p, e, n)
c1q = pow(q, e, n)
cm = pow(m, e, n)
c1 = (c1p - c1q) % n
c2 = pow(p - q, e, n)

print(f"e = {e}")
print(f"n = {n}")
# p^e - q^e mod n
print(f"c1 = {c1}")
# (p-q)^e mod n
print(f"c2 = {c2}")
# m^e mod n
print(f"cm = {cm}")
output.txt
e = 131074
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866

問題の詳細

普通の RSA だと 2 つの素数を使って暗号化するが、この問題では 3 つの素数 p, q, r を使って暗号化されている。また、通常 e は \phi(n) と互いに素になるように置かれるが、この問題ではそうではない。ただ、普通の RSA の考え方がそのまま応用できる。

また、出力として、 n, e の他に、 p, q による多項式の値が 2 つ与えられている。
c1 = p^e - q^e \mod n
c2 = (p - q)^e \mod n

方針

まず n を素因数分解をする。与えられた p, q の多項式から p, q を求める。
次に d = (e/2)^{-1} \mod \phi(n) を求める。 e は偶数となるため、 \phi(n) と互いに素にならず逆元を持たない。
その d を使うことで m^2 が求められるので、平方余剰を求める。

つまり、以下の 3 ステップで求められる。

  1. n を素因数分解する
  2. cm を復号して m^2 を得る
  3. m^2 の平方剰余を求める

n を素因数分解する

c2 = (p - q)^e \mod n の両辺に r を掛けて e 乗を展開すると、法が n であることと、 e が偶数であることに注意すると、

r * c2 = r(p -q)^e = rp^e + (pqr 倍の多項式) + rq^e = rp^e + rq^e \mod n

という式が得られる。 n = pqr なので、 r を無視して

c2 = p^e + q^e \mod pq

が言える。 c1 の方も、法を pq として考えると、

c1 = p^e - q^e \mod pq

が成り立つことがわかる。それぞれ足したり引いたりすることで、

c1 + c2 = 2p^e \mod pq
c1 - c2 = 2q^e \mod pq

が得られる。上の式の左辺は p の倍数、下の式の左辺は q の倍数でないといけないことがわかる。 n = pqr なので、 \gcd(c1 + c2, n)、\gcd(c1 - c2, n) を求めることで、 p と q が求められる。そして r も求められる。

cm を復号して m^2 を得る

\phi(n) = (p - 1) * (q - 1) * (r - 1) であるので、それを法として e/2 の逆元を求める。それを d とおくと、

cm^d = m^{2ed} = m^2 \mod n

と求めることができる。

m^2 の平方剰余を求める

後は n の法の下で平方をとればいい。素数の法の方がやりやすいので、各 p, q, r に分解してそれぞれ平方を求める。その後中国の剰余定理を使って復元する。

c_p = mc \mod p
c_q = mc \mod q
c_r = mc \mod r

と分解して、それぞれの平方剰余を求める。ここで注意するのは平方根は剰余であっても(存在すれば) 2 つ出ることである。なので元に戻すのは 8 パターンある。
今回はフラグの文字列として SECCON が含まれることが保証されているので、その文字列が含まれているかで確認する。

求めるコード

import math
import random
import sympy.ntheory.modular as mod

e = 131074
n = 587926815910957928506680558951380405698765957736660571041732511939308424899531125274073420353104933723578377320050609109973567093301465914201779673281463229043539776071848986139657349676692718889679333084650490543298408820393827884588301690661795023628407437321580294262453190086595632660415087049509707898690300735866307908684649384093580089579066927072306239235691848372795522705863097316041992762430583002647242874432616919707048872023450089003861892443175057
c1 = 92883677608593259107779614675340187389627152895287502713709168556367680044547229499881430201334665342299031232736527233576918819872441595012586353493994687554993850861284698771856524058389658082754805340430113793873484033099148690745409478343585721548477862484321261504696340989152768048722100452380071775092776100545951118812510485258151625980480449364841902275382168289834835592610827304151460005023283820809211181376463308232832041617730995269229706500778999
c2 = 46236476834113109832988500718245623668321130659753618396968458085371710919173095425312826538494027621684566936459628333712619089451210986870323342712049966508077935506288610960911880157875515961210931283604254773154117519276154872411593688579702575956948337592659599321668773003355325067112181265438366718228446448254354388848428310614023369655106639341893255469632846938342940907002778575355566044700049191772800859575284398246115317686284789740336401764665472
cm = 357982930129036534232652210898740711702843117900101310390536835935714799577440705618646343456679847613022604725158389766496649223820165598357113877892553200702943562674928769780834623569501835458020870291541041964954580145140283927441757571859062193670500697241155641475887438532923910772758985332976303801843564388289302751743334888885607686066607804176327367188812325636165858751339661015759861175537925741744142766298156196248822715533235458083173713289585866


def sqrtPrime(n, p):
    q = p - 1
    m = 0
    while q & 1 == 0:
        q >>= 1
        m += 1

    z = 1
    while pow(z, (p - 1) >> 1, p) == 1:
        z = random.randint(1, p - 1)

    c = pow(z, q, p)
    t = pow(n, q, p)
    r = pow(n, (q + 1) >> 1, p)
    if t == 0:
        return 0
    m -= 2
    while t != 1:
        while pow(t, 2**m, p) == 1:
            c = c * c % p
            m -= 1
        r = r * c % p
        c = c * c % p
        t = t * c % p
        m -= 1
    return r


p = math.gcd(c1 + c2, n)
q = math.gcd(c1 - c2, n)

r = n // (p * q)
d = pow(e // 2, -1, (p - 1) * (q - 1) * (r - 1))

m2 = pow(cm, d, n)

m2p = m2 % p
m2q = m2 % q
m2r = m2 % r

pm = sqrtPrime(m2p, p)
qm = sqrtPrime(m2q, q)
rm = sqrtPrime(m2r, r)

m = 0
for tp in [pm, p - pm]:
    for tq in [qm, q - qm]:
        for tr in [rm, r - rm]:
            (ttt, _) = mod.crt([p, q, r], [tp, tq, tr])
            t = ttt.to_bytes(256, byteorder="big")
            if b"SECCON" in t:
                print(t[t.find(b"SECCON") :].decode("utf-8"))

※平方剰余のアルゴリズムはこのサイトを参考にさせていただきました。
https://tjkendev.github.io/procon-library/python/math/tonelli-shanks.html

余談

めっちゃ分かった風に書いているが、実は解けなかった問題である(笑)。
c1 + c2 が p の倍数、 c1 - c2 が q の倍数までは分かったが、その次の最大公約数をとるところが気づかなかった。つらい。

Discussion