Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
13
Help us understand the problem. What is going on with this article?
@ushigai_sub

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でflagkeyの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?}
13
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
13
Help us understand the problem. What is going on with this article?