LoginSignup
20
11

More than 1 year has passed since last update.

@ushigai_sub

SECCON Beginners CTF2021 作問者Writeup

Last updated at Posted at 2021-05-23

はじめに

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?}
20
11
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
20
11