SECCON Beginners CTF 2023 write up

# 解けた問題
cryに専念して、2問解きました。
次のRSAの問題も解きたかったなぁ
# CoughingFox2
配布ファイル
```python:main.py
# coding: utf-8
import random
import os

flag = b"ctf4b{xxx___censored___xxx}"

# Please remove here if you wanna test this code in your environment :)
flag = os.getenv("FLAG").encode()

cipher = []

for i in range(len(flag)-1):
    c = ((flag[i] + flag[i+1]) ** 2 + i)
    cipher.append(c)

random.shuffle(cipher)

print(f"cipher = {cipher}")
```
```cipher.txt
cipher = [4396, 22819, 47998, 47995, 40007, 9235, 21625, 25006, 4397, 51534, 46680, 44129, 38055, 18513, 24368, 38451, 46240, 20758, 37257, 40830, 25293, 38845, 22503, 44535, 22210, 39632, 38046, 43687, 48413, 47525, 23718, 51567, 23115, 42461, 26272, 28933, 23726, 48845, 21924, 46225, 20488, 27579, 21636]
```

### solve
cipherのi文字目がflagのi文字目とi+1文字目で構成されています。
この問題を解くための前提知識としてflag[i]はasciiコードの数値なので大体100くらいの数値であることを思い出しながら考察していきます。
(flag[i]+flag[i+1])**2の値はlen(flag)-1の値に比べて十分に大きいので、cの根号は(flag[i]+flag[i+1])になりそうです。
cの根号が整数になるようにiの値を0 <= i <= len(flag)-1として総当たりすれば各iが分かります。

後は方程式を解いていきます。
例として、flag = b'abc', x=ord('a'), y=ord('b'), z = ord('c')とします。
```math
(x+y)**2 == k, \\
(y+z)**2 == l
```
とすると、
```math
x = c_1(任意定数)\\
y = \sqrt k-x\\
z = \sqrt l-y
```
`c_1`は'c'と分かっているのでこれで暗号を完全に復号することが出来ます。
```python:solve.py
import math
cipher = [4396, 22819, 47998, 47995, 40007, 9235, 21625, 25006, 4397, 51534, 46680, 44129, 38055, 18513, 24368, 38451, 46240, 20758, 37257, 40830, 25293, 38845, 22503, 44535, 22210, 39632, 38046, 43687, 48413, 47525, 23718, 51567, 23115, 42461, 26272, 28933, 23726, 48845, 21924, 46225, 20488, 27579, 21636]

index = []
for i in cipher:
    for j in range(49):
        if math.sqrt((i-j)) % 1 == 0:
#            print("Yes")
            index.append(j)

tmp = cipher.copy()
count = 0
for i in index:
    tmp[i] = int(math.sqrt(cipher[count] - i))
    count += 1

hoge = ord('c')
print('c', end='')
for i in tmp:
    print(chr(i-hoge), end='')
    #print(i-hoge+base)
    hoge = i-hoge
```

# Conquer
征服？題名と問題は特に関連性はなかった。。
配布ファイル
```python:problem.py
from Crypto.Util.number import *
from random import getrandbits
from flag import flag


def ROL(bits, N):
    for _ in range(N):
        bits = ((bits << 1) & (2**length - 1)) | (bits >> (length - 1))
    return bits


flag = bytes_to_long(flag)
length = flag.bit_length()

key = getrandbits(length)
cipher = flag ^ key

for i in range(32):
    key = ROL(key, pow(cipher, 3, length))
    cipher ^= key

print("key =", key)
print("cipher =", cipher)
```
```output.txt
key = 364765105385226228888267246885507128079813677318333502635464281930855331056070734926401965510936356014326979260977790597194503012948
cipher = 92499232109251162138344223189844914420326826743556872876639400853892198641955596900058352490329330224967987380962193017044830636379
```

### solve
xorの問題です。
xorの基本的な性質として`c = a^b, c^a = b, c^b = a`が成り立ちます。(xorについて知りたい人はcrypto hackをやってみることをオススメします。)

ROLでは1週するたびにbitsの最上位桁が最下位桁に落ちてきます。下から上にbitがぐるぐる回っているような感じです。一番上まで行ったら一番下からまた回ってきます。

この操作を逆にたどればflagが復号できます。
注意点として、keyのlengthとflagのlengthはずれている可能性があります。keyのlengthでうまくいかなかったらlenghtを+1か+2かしてあげてください。

```python:solve.py
from Crypto.Util.number import *

key = 364765105385226228888267246885507128079813677318333502635464281930855331056070734926401965510936356014326979260977790597194503012948
cipher = 92499232109251162138344223189844914420326826743556872876639400853892198641955596900058352490329330224967987380962193017044830636379

def r_ROL(bits, N):
    for _ in range(N):
        bits = (bits >> 1) | ((bits&1) << (length-1))
    return bits

flag = cipher ^ key
length = key.bit_length()+1
print(length)

for i in range(32):
    key = r_ROL(key, pow(flag, 3, length))
    flag ^= key

flag = long_to_bytes(flag)
print(flag)
```