SECCON Beginners CTF2021 作問者Writeup

# はじめに
ctf4b2021お疲れさまです。
今回作問に携わらせていただいたので、自分が作問したCrypto4問についての想定解法とお気持ちを書きます。
Cryptoの残りの2問(GFM, Imaginary)については[れっくすさんのWriteup](https://rex.gs/2021/05/seccon-beginners-ctf-2021-crypto-解説/)を参照していただければと思います。


## [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ナップザック暗号です。密度を計算すると

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

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

<img src="https://user-images.githubusercontent.com/46185629/116289030-0f31fa80-a7cd-11eb-970d-66b1b48774d7.png" width="280" height="120">

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

```python: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でなんか[こんな投稿](https://twitter.com/Xornet_Euphoria/status/1369893260555026432)を見つけてしまって、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$を求めることができません。ここで使用するのがカーマイケルの定理です。[記事](https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e/)を参考に

```math
λ=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?}
```