SECCON Beginners CTF 2022 作問者Writeup

# はじめに
昨年に引き続きSECCON Beginners CTF 2022のCryptoの作問(&review)を担当させていただきました。
CoughingFox, PrimeParty, omni-RSAの作問をしたのでそれぞれの作問者想定解法とお気持ちを書いていきます。
- 開催概要
    - スコアサーバURL：https://score.beginners.azure.noc.seccon.jp/
    - 開始時刻：2022/06/04（土）14:00 JST
    - 終了時刻：2022/06/05（日）14:00 JST


## [Beginner] CoughingFox ( 55points / 443solves )

```python:problem.py
from random import shuffle

flag = b"ctf4b{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"

cipher = []

for i in range(len(flag)):
    f = flag[i]
    c = (f + i)**2 + i
    cipher.append(c)

shuffle(cipher)
print("cipher =", cipher)
```

`flag`はリスト型でアスキーコードに基づき符号化されており、`flag`の各要素について、

```
cipher[0] = (flag[0] + 0)^2 + 0
cipher[1] = (flag[1] + 1)^2 + 1
cipher[2] = (flag[2] + 2)^2 + 2
               :
cipher[N] = (flag[N] + N)^2 + N
```

と計算し、`cipher`を`random`モジュールの`shuffle()`でシャッフルしていることがわかります。

先ほどの暗号化の計算式は一方方向ではないので`shuffle()`によってぐちゃぐちゃにされてる各`cipher`が何文字目の`flag`により計算されているか特定できれば、`flag`を復号できると考えられます。何文字目かを特定するには各`cipher`について、`i (0 ≤ i ≤ N)`を引いて平方数となった`i`が`flag[i]`となります。

実装には`gmpy2`モジュールの`iroot`メソッドを使用しました。

```python:solve.py
from gmpy2 import iroot

cipher = [12147, 20481, 7073, 10408, 26615, 19066, 19363, 10852, 11705, 17445, 3028, 10640, 10623, 13243, 5789, 17436, 12348, 10818, 15891, 2818, 13690, 11671, 6410, 16649, 15905, 22240, 7096, 9801, 6090, 9624, 16660, 18531, 22533, 24381, 14909, 17705, 16389, 21346, 19626, 29977, 23452, 14895, 17452, 17733, 22235, 24687, 15649, 21941, 11472]
length = len(cipher)
flag = [""] * length

for c in cipher:
    for i in range(length):
        f, going = iroot(c - i, 2)
        if going:
            flag[i] = chr(f - i)
            break

print("".join(flag))
```

## [Easy] PrimeParty ( 127points / 58solves )

```python:server.py
from Crypto.Util.number import *
from secret import flag
from functools import reduce
from operator import mul


bits = 256
flag = bytes_to_long(flag.encode())
assert flag.bit_length() == 455

GUESTS = []

def invite(p):
    global GUESTS
    if isPrime(p):
        print("[*] We have been waiting for you!!! This way, please.")
        GUESTS.append(p)
    else:
        print("[*] I'm sorry... If you are not a Prime Number, you will not be allowed to join the party.")
    print("-*-*-*-*-*-*-*-*-*-*-*-*-")


invite(getPrime(bits))
invite(getPrime(bits))
invite(getPrime(bits))
invite(getPrime(bits))

for i in range(3):
    print("[*] Do you want to invite more guests?")
    num = int(input(" > "))
    invite(num)


n = reduce(mul, GUESTS)
e = 65537
cipher = pow(flag, e, n)

print("n =", n)
print("e =", e)
print("cipher =", cipher)

```
RSA暗号の公開鍵$n$に含まれる素数を自由に追加できるRSA暗号です。

問題サーバから与えられる情報について考えると
$$
cipher  = m^e \mod n
$$
が分かります。ここで$n$の素因数が十分大きな素数であることから、
$$
cipher ≡ m^e \mod p
$$
が確かめられ、法が素数1個だけのRSA暗号に落とし込むことができます。

以上より問題サーバに対して$flag$より十分大きな素数$p$を$n$に含ませ、得られた暗号文から秘密鍵$d=e^{-1} \mod p - 1$を計算すれば$n$が素因数分解できずとも復号することができます。

```output.txt
$ nc primeparty.quals.beginners.seccon.jp 1336
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] Do you want to invite more guests?
 > 7125542541015089382665540838109147669178367364945725639475647981053827179059524720886882567884452880517281519977560328608747082652488826892110086607334999
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] Do you want to invite more guests?
 > 1
[*] I'm sorry... If you are not a Prime Number, you will not be allowed to join the party.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] Do you want to invite more guests?
 > 1
[*] I'm sorry... If you are not a Prime Number, you will not be allowed to join the party.
-*-*-*-*-*-*-*-*-*-*-*-*-
n = 178846388997216303715324153141838504003016418851292634742753578454485646720639916499779812225291101109653406078996218604427343541609942612772911790627024410990857513342854440983604186542335668029589847253852978692348236477713723237771432908829786352167840948665719726850714699820681384415188349276825761601946764237397853702940931185202203811617595950497923622020665965918938218841058740480054638732025184164831356747218114628857562050624283343956599233295481517
e = 65537
cipher = 122335582115854131041204881945410154379105215140510832597034121195514778324761929803452646784073884484726324022016133776522171011038025147692827538027909300105961756614227254932737776675941866945229307131604285421777412599987923549611084220901143256189238791328117065281855896949367780873366170826522857346463675049589707840426897571976323627611915708906039539647722427200922762856864063827946491173886190995810459498587855347282835963487238970889982282489313411
```

```python:solve.py
from Crypto.Util.number import *

n = 178846388997216303715324153141838504003016418851292634742753578454485646720639916499779812225291101109653406078996218604427343541609942612772911790627024410990857513342854440983604186542335668029589847253852978692348236477713723237771432908829786352167840948665719726850714699820681384415188349276825761601946764237397853702940931185202203811617595950497923622020665965918938218841058740480054638732025184164831356747218114628857562050624283343956599233295481517
e = 65537
cipher = 122335582115854131041204881945410154379105215140510832597034121195514778324761929803452646784073884484726324022016133776522171011038025147692827538027909300105961756614227254932737776675941866945229307131604285421777412599987923549611084220901143256189238791328117065281855896949367780873366170826522857346463675049589707840426897571976323627611915708906039539647722427200922762856864063827946491173886190995810459498587855347282835963487238970889982282489313411
p = 7125542541015089382665540838109147669178367364945725639475647981053827179059524720886882567884452880517281519977560328608747082652488826892110086607334999

phi = p - 1
d = inverse(e, phi)
m = pow(cipher, d, p)

print(long_to_bytes(m))
```

## [Hard] omni-RSA ( 240points / 14solves )

```python:problem.py
from Crypto.Util.number import *
from flag import flag

p, q, r = getPrime(512), getPrime(256), getPrime(256)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
e = 2003
d = inverse(e, phi)

flag = bytes_to_long(flag.encode())
cipher = pow(flag, e, n)

s = d % ((q - 1)*(r - 1)) & (2**470 - 1)

assert q < r
print("rq =", r % q)

print("e =", e)
print("n =", n)
print("s =", s)
print("cipher =", cipher)
```

秘密鍵$d$がマスクされて渡される問題です。

マスク量は$470bit$で未知部分は$41,42bit$なので総当たりは厳しいと思います。
方針としては$d$の未知部分を$x$とおいてモニック多項式に帰着させCopperSmith's Attackを行います。

公開鍵$e$と秘密鍵$d$の関係より、
$$
ed≡1 \mod φ(n) \\\\
⇔iφ(n) + 1 = ed \\
$$
がわかります。ここで、
$$
d'≡d \mod (q - 1)(r - 1) \\\\
⇔ d = j((q - 1)(r - 1)) + d' \\
$$
とすると、
$$
iφ(n) + 1 = ed \\\\
⇔iφ(n) + 1 = e(j(q - 1)(r - 1) + d') \\\\
⇔1 ≡ ed' \mod (q - 1)(r - 1) \\\\
⇔ed' = 1 + k(q - 1)(r - 1) \\
$$
となります。ここで$k$は未知の値です。しかし$ed' = 1 + k(q - 1)(r - 1)$という式の右辺と左辺を比較してみると、$d'=d \mod (q - 1)(r - 1)$であることから$k$は高々$e$であることが分かります。$e=2003$なので十分総当たり可能です。
さらに式変形を進め、
$$
e(2^{470}x + s) = 1 + (q - 1)(r - 1)k \\\\
e(2^{470}x + s) - 1 - (q - 1)(r - 1)k = 0 \\\\
e(2^{470}x + s) - 1 - k(1 - r) ≡ 0 \mod q \\
$$
と、ここまで変形すればあとはsagemathの`monic`メソッドを使用して$x$のモニック多項式が得られます。
モニック多項式を解くにはsagemathの場合`small_roots()`が用意されていますが、今回パラメータ調整がちょっとめんどくさいです。[ドキュメント](https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots)より、引数`X`は$x$が$42bit$以下の数であることから`X=2^42`。`beta`は$f(x) ≡ 0 \mod q$を解くことから$N^β≤q$という式より$β ≤ log_qN$が`beta`の条件となります。$q$が$256bit$で$N$が$1024bit$の数であることから$β ≤ log_qN ≃ 0.25$ぐらいだとわかります。実際の値より少しでも大きいだけで`small_roots`で解くことができないので、`beta=0.20`と定めます。


```python
f.small_roots(
    X = 2^42,
    beta = 0.20,
    epsylon = 1/16
)
```

$d'$が復元出来たらそこから$r, q$の順で復元し素因数分解を行います。
問題文では$r_q=r \mod q$が与えられていますが、$r > q$でなおかつ$r, q$は同じビット長であることから$r//q$は1に定まると考えられます。なので、

$$
r_q=r \mod q \\\\
⇔ r_q + q = r
$$

が成り立ちます。
先ほど計算した$d'$と連立方程式を立てると、

```math
\begin{equation}
\left\{ \,
    \begin{aligned}
    & ed' = 1 + k(q - 1)(r - 1) \\
    & q = r - r_q
    \end{aligned}
\right.
\end{equation}
```

となるので下の式を上に代入して、

$$
ed' = 1 + k(r - r_q - 1)(r - 1) \\\\
1 + k(r - r_q - 1)(r - 1) - ed' = 0
$$

となります。左辺に未知数は$r$しかないので、二次方程式を解けば$r$が計算できます。
$r$がわかれば$q = r - r_q$より$q$が計算でき、$n=pqr$から$p$が求まります。これで素因数分解できたので復号することができます。


```python:solve.sage
from Crypto.Util.number import *

rq = 7062868051777431792068714233088346458853439302461253671126410604645566438638
e = 2003
n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666

shift = 2^470
for k in range(1, e):
    print(f"[*] {k} / {e}")
    F.<x> = PolynomialRing(Zmod(n))
    f = e*(x*shift + s) - 1 + k*rq - k
    f = f.monic()
    x0 = f.small_roots(X=2^42, beta=0.20, epsylon=1/16)
    if len(x0) != 0:
        d_ = int(x0[0])*shift + s 
        print("ok")
        break


var("r")
fr = 1 + k*(r - rq - 1)*(r - 1) - e*d_
print(solve(fr, r))
# [
# r == 115782269004778310532099644136706472617339510140211345931055084365526756095881,
# r == -108719400953000878740030929903618126158486070837750092259928673760881189657241
# ]

r = 115782269004778310532099644136706472617339510140211345931055084365526756095881
q = r - rq
p = n // q // r
assert p*q*r == n

phi = (p - 1)*(q - 1)*(r - 1)
d = inverse(e, phi)
flag = pow(cipher, d, n)

print(long_to_bytes(flag))

```