解けた問題
cryに専念して、2問解きました。
次のRSAの問題も解きたかったなぁ
CoughingFox2
配布ファイル
# 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 = [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')とします。
(x+y)**2 == k, \\
(y+z)**2 == l
とすると、
x = c_1(任意定数)\\
y = \sqrt k-x\\
z = \sqrt l-y
c_1
は'c'と分かっているのでこれで暗号を完全に復号することが出来ます。
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
征服?題名と問題は特に関連性はなかった。。
配布ファイル
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)
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かしてあげてください。
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)