はじめに
昨年に引き続き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 )
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メソッドを使用しました。
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 )
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$が素因数分解できずとも復号することができます。
$ 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
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 )
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()が用意されていますが、今回パラメータ調整がちょっとめんどくさいです。ドキュメントより、引数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と定めます。
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'$と連立方程式を立てると、
\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$が求まります。これで素因数分解できたので復号することができます。
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))