SECCON Beginners CTF2021 作問者Writeup

はじめに

ctf4b2021お疲れさまです。
今回作問に携わらせていただいたので、自分が作問したCrypto4問についての想定解法とお気持ちを書きます。
Cryptoの残りの2問(GFM, Imaginary)についてはれっくすさんのWriteupを参照していただければと思います。

[Beginner] simple_RSA ( 75points / 289solves )

problem.py

from Crypto.Util.number import *
from flag import flag

flag = bytes_to_long(flag.encode("utf-8"))

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

assert 2046 < n.bit_length()
assert 375 == flag.bit_length()

print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))

flagのbit長が375bitでnのbit長が2047bit以上（⇔nのbit長がflagのbit長のe倍以上）であることから、$m^e<n$であると推測できます。$m^e<n$のとき$m^e$は法$n$に引っかからないこので、暗号化の計算式は$c=m^e$と等価になります。なので暗号文のe乗根を計算することで復号できます。

solve.py

from Crypto.Util.number import *

def cubic_root(x):
    imin = 0
    imax = x
    while imin <= imax:
        imid = (imin + imax) // 2
        imid_squared = imid ** 3
        if imid_squared <= x:
            imin = imid + 1
        else:
            imax = imid - 1
    return imin - 1

n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613

flag = cubic_root(c)

print(long_to_bytes(flag))

ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}

[Beginner] Logical_SEESAW ( 118points / 190solves )

problem.py

from Crypto.Util.number import *
from random import random, getrandbits
from flag import flag

flag = bytes_to_long(flag.encode("utf-8"))
length = flag.bit_length()
key = getrandbits(length)
while not length == key.bit_length():
    key = getrandbits(length)

flag = list(bin(flag)[2:])
key = list(bin(key)[2:])

cipher_L = []

for _ in range(16):
    cipher = flag[:]
    m = 0.5
    
    for i in range(length):
        n = random()
        if n > m:
            cipher[i] = str(eval(cipher[i] + "&" + key[i]))
            
    cipher_L.append("".join(cipher))

print("cipher =", cipher_L)

flagの各bitに対して適用確立0.5でflagとkeyのand演算を行っています。and演算というのがポイントで、以下の真理値表の通り任意の$i\ (0 ≤ i ≤ 15)$, $j\ (0 ≤ j ≤ 286)$においてcipher[i][j]が1のときflag[i][j]は確実に1、cipher[i][j]が0のときでもflag[i][j]は8割0であることがわかります。

flag	key	n>m	cipher
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

以上の特性を利用すると、16個の暗号文の各bitにおいて1つでもbitが立っていたら1を、すべて0なら0。言い換えるとcipher[0, 15)の論理和を計算することで、平文を復号できます。

solve.py

from Crypto.Util.number import *

cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']

flag = int(cipher[0], base=2)
for c in cipher:
    flag |= int(c, base=2)

print(long_to_bytes(flag).decode("utf-8"))

ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

She saw a seesaw, she said so.なんつって。

[Medium] Field_trip ( 394points / 28solves )

problem.py

from Crypto.Util.number import *
from random import getrandbits
from flag import flag


flag = bytes_to_long(flag.encode("utf-8"))
flag = bin(flag)[2:]
length = len(flag)

A = []
a, b = 0, 0
for _ in range(length):
    a += getrandbits(32) + b
    b += a
    A.append(a)

p = getStrongPrime(512)
q = getStrongPrime(512)

assert q > sum(A)

pub_key = [a * p % q for a in A]
cipher = sum([int(flag[i]) * pub_key[i] for i in range(length)])

f = open("output.txt", "w")
f.write("pub_key = " + str(pub_key) + "\n")
f.write("cipher = " + str(cipher) + "\n")
f.close()

Merkle-Hellmanナップザック暗号です。密度を計算すると

d=\frac{n}{\log_2 max(pub\_key)} ≒ 0.6232

となります。ここで$d≤0.9408$を満たすとき、低密度攻撃（CLOS法）で復号することができます。基底Mを

とおき、Mが貼る格子をLLLで殴れば適当なiにおいてM[i][0]が0でそれ以外が1か-1のベクトルが得られそれがフラグとなります。

solve.sage

from Crypto.Util.number import *
# Chabnge the file name from "output.txt" ot "output.py"
from output import pub_key, cipher

def create_matrix(pub, c):
    N = len(pub)
    m_id = matrix.identity(N) * 2
    m = matrix(ZZ, 1, N + 1, pub[:] + [-c])
    B = m_id.augment(matrix(ZZ, N, 1, [-1] * N))
    m = m.stack(B)
    return m

def vec(matrix):
    for i in matrix.columns():
        if not(i[0]) and all([(j == -1 or j == 1) for j in i[1:]]):
            return i

M = create_matrix(pub_key, cipher)
LLL_M = M.transpose().LLL().transpose()
V = vec(LLL_M)

flag = "".join(list(map(str, V)))
flag = flag.replace("0", "")
flag = flag.replace("-1", "0")

print(long_to_bytes(int(flag, base=2)))

ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}

twitterでなんかこんな投稿を見つけてしまって、LLLがそのまま適用できる例としてちょうどいい題材ないかなーって考えて作った問題です。初見は厳しいかもしれませんが、solverのとおりLLLの基本なのでぜひ復習していただきたい問題です。

[Hard] p-8RSA ( 387points / 30solves )

problem.py

from Crypto.Util.number import *
from random import getrandbits
from os import urandom
from flag import flag


def gen_primes(bits, e):
    q = getStrongPrime(bits)
    p = q
    while True:
        p = p-8 # p-8
        phi = (p - 1) * (q - 1)
        if isPrime(p) and GCD(phi, e) != 1:
            break
    return p, q

flag = flag.encode("utf-8") + urandom(64)
flag = bytes_to_long(flag)

e = 17
p, q = gen_primes(512, e)
n = p * q

print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))

RSA暗号は素因数分解の難しさを利用した暗号です。しかし今回の場合素数の生成方法が512bitの素数pから8引き続けて素数qを決定しているので、素数p, qが非常に近いと予想できます。素数p, qが近いときの素因数分解方法としてフェルマー法がありますが今回の場合nの平方根周辺を総当たりしてp, qを求めることができます。
また通常のRSA暗号ではオイラーの定理を適用するため、$e$と$φ(n)$が互いに素になるように素数$p, q$を選びます。しかし$gcd(e, φ(n)) = e$のとき、通常の方法で秘密鍵$d$を求めることができません。ここで使用するのがカーマイケルの定理です。記事を参考に

λ=lcm(p-1, \ q-1)\\
d=e^{-1} \mod \frac{λ}{e}\\
L=2^{\frac{λ}{e}} \mod n

のときの、$C^d・L^i \mod n \ (0 ≤ i < e)$が平文の候補となります。あとは$i$についての総当たりでflagを得ることができます。

以降実装。

solve.py

from Crypto.Util.number import *
from gmpy2 import isqrt

n = 169221770188000341507764005330769042705223611712308424479120192596136318818708135716157255550936563268500310852894489839470320516645317338473018150885997977008925839939560590924435380239519554475266121835753044660177349444503693993991253475530436734034224314165897550185719665717183285653938232013807360458249
e = 17
c = 100233131931360278332734341652304555814094487252151131735286074616555402795190797647001889669472290770925839013131356212574455274690422113278015571750653365512998669453161955302008599029919101244702933443124944274359143831492874463245444294673660944786888148517110942002726017336219552279179125115273728023902

p = isqrt(n)
for i in range(10**6):
    p += 1
    if n % p == 0:
        q = n // p
        break

X = (p - 1) * (q - 1) // GCD(p - 1, q - 1)
L = pow(2, X // e, n)
d = inverse(e, X // e)

for i in range(e):
    flag = long_to_bytes(pow(c, d, n) * pow(L, i, n) % n)
    if b"ctf4b" in flag:
        print(flag)
        break

ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}