# HTB Cyber Apocalypse CTF 2024 (Crypto)

## Primary Knowledge (Solved)
> HTB{0h_d4mn_4ny7h1ng_r41s3d_t0_0_1s_1!!!}

* RSA暗号。

~~~
n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215
~~~

~~~
import math
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

m = bytes_to_long(FLAG)

n = math.prod([getPrime(1024) for _ in range(2**0)])
e = 0x10001
c = pow(m, e, n)

with open('output.txt', 'w') as f:
f.write(f'{n = }\n')
f.write(f'{e = }\n')
f.write(f'{c = }\n')
~~~

* 暗号化のスクリプトをよく見ると、`n`を求めるときに素数が一つしか使われていない。
* しばらく気づかなかった。やられた。
* `phi` は単純に`n-1`となるので、`d`を求めて普通に復号してあげれば良い。

~~~
from Crypto.Util.number import long_to_bytes

n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215

phi = n - 1
d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(m))
~~~

~~~
mito@mito-Virtual-Machine:~/ctf/hackthebox-cyber-apocalypse-ctf-2024/crypto-primary-knowledge/crypto_primary_knowledge$ python3 solve.py
b'HTB{0h_d4mn_4ny7h1ng_r41s3d_t0_0_1s_1!!!}'
~~~
## Blunt (Solved)
> HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}

* AES暗号。

~~~
p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9
ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'
~~~

~~~from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime, long_to_bytes
from hashlib import sha256

from secret import FLAG

import random

p = getPrime(32)
print(f'p = 0x{p:x}')

g = random.randint(1, p-1)
print(f'g = 0x{g:x}')

a = random.randint(1, p-1)
b = random.randint(1, p-1)

A, B = pow(g, a, p), pow(g, b, p)

print(f'A = 0x{A:x}')
print(f'B = 0x{B:x}')

C = pow(A, b, p)
assert C == pow(B, a, p)

# now use it as shared secret
hash = sha256()
hash.update(long_to_bytes(C))

key = hash.digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print(f'ciphertext = {encrypted}')
~~~

* `C ≡ g ^ ab (mod p)` なので、`A` と `B` から `a` と `b` が求まればいけそう。

* `y ≡ g ^ x (mod p)` となる `x` を求めることを離散対数問題というらしい。
* https://tex2e.github.io/blog/crypto/DLP
* `y` を `A` に対応させれば、`a` が求まる。(`b` も同様。)

* スクリプトを書いて復号。
~~~
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9
ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'

def babystep_giantstep(g, y, p):
m = int((p-1)**0.5 + 0.5)

table = {}
gr = 1
for r in range(m):
table[gr] = r
gr = (gr * g) % p

gm = pow(g, -m, p)
ygqm = y
for q in range(m):
if ygqm in table:
return q * m + table[ygqm]
ygqm = (ygqm * gm) % p

return None

a = babystep_giantstep(g, A, p)
b = babystep_giantstep(g, B, p)
print("a : {}".format(a))
print("b : {}".format(b))

C = pow(B, a, p)
assert C == pow(A, b, p)

hash = sha256()
hash.update(long_to_bytes(C))

key = hash.digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)

pt = cipher.decrypt(ciphertext)
print(pt)
~~~

~~~
mito@mito-Virtual-Machine:~/ctf/hackthebox-cyber-apocalypse-ctf-2024/crypto-blunt/challenge$ python3 solve.py
a : 2766777741
b : 1913706799
b'HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}\x01'
~~~

* ちょっとごみ入っちゃっているのは、パディング消し忘れてたせい。

## Partial Tenacity (Solved)
> HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}

* RSAの鍵を求める問題。
* 説明むずい。イメージは虫食い算みたいな感じ。↓こんなやつの掛け算版。


* n と p と q が与えられ、p と q に関して、どちらも10進数で与えられるが、下記のような感じとなっている。
* n は p * q
* p は先頭の文字から1文字飛ばし (12345 の場合、135)
* q は2文字目から1文字飛ばし (12345 の場合、24)

* n の1の位は、p の 1の位と q の1の位を掛け算したものなので、「pの1の位とqの1の位の積」の 1の位が n の1の位と等しくなるようにqの1の位を選ぶ。
* 同じように、n の10の位は「pの1の位とqの10の位の積の1の位」「pの10の位とqの1の位の積の1の位」「pの1の位とqの1の位の積の10の位」「nの1の位を計算したときの繰り上がり」の4つの数字を足したものの1の位となるので、それを満たすようにpの10の位を選ぶ。
* みたいなことをずーーーーーーーーーーーーーーーーーーーーーーーーーーーーっとやっていくとpとqが求まるので、それを使ってRSAの鍵を作って復号する。

* もっと良い方法がありそうな気もするが、思いつかなかった。
* コードめっちゃ汚いけど許してください。
~~~
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import long_to_bytes

ct = long_to_bytes(int('7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476', 16))

#Test
#n = '174803567'
#partial_p = '163'
#partial_q = '35'

n = '118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003'
partial_p = '151441473357136152985216980397525591305875094288738820699069271674022167902643'
partial_q = '15624342005774166525024608067426557093567392652723175301615422384508274269305'

arr_n = []
for i in range(len(n)):
arr_n.append(int(n[i]))
arr_n.reverse()

arr_p = []
for i in range(len(partial_p)):
arr_p.extend([int(partial_p[i]), 'x'])
arr_p = arr_p[:-1]
arr_p.reverse()

arr_q = []
for i in range(len(partial_q)):
arr_q.extend([int(partial_q[i]), 'x'])
arr_q.reverse()
arr_q.append('x')

table_current = [['x' for i in range(len(arr_p))] for j in range(len(arr_q))]
table_moveup = [[0 for i in range(len(arr_p))] for j in range(len(arr_q))]
moveup = 0
target = []
previous_target = []

for pi in range(len(arr_p)):
for qi in range(len(arr_q)):
if(arr_p[pi] != 'x' and arr_q[qi] != 'x'):
table_current[pi][qi] = (arr_p[pi] * arr_q[qi]) % 10
table_moveup[pi][qi] = (arr_p[pi] * arr_q[qi]) // 10

for ni in range(len(arr_n)):
for pi in range(len(arr_p)):
for qi in range(len(arr_q)):
if(pi + qi == ni):
target.append([pi, qi])

digit_current = 0
update = []
for item in target: # item : [pi, qi]
tmp = table_current[item[0]][item[1]]
if(tmp != 'x'):
digit_current += table_current[item[0]][item[1]]
else:
update = item

if(len(update) == 0):
break

x = 0
for item in previous_target:
digit_current += table_moveup[item[0]][item[1]]

digit_current += moveup

for i in range(10):
if((digit_current + i) % 10 == arr_n[ni]):
x = i

table_current[update[0]][update[1]] = (digit_current + x) % 10
table_moveup[update[0]][update[1]] = (digit_current + x) // 10

candidate = []
if(arr_p[update[0]] == 'x'):
update.append('p')
for i in range(10):
if((i * arr_q[update[1]]) % 10 == x):
candidate.append(i)
elif(arr_q[update[1]] == 'x'):
update.append('q')
for i in range(10):
if((i * arr_p[update[0]]) % 10 == x):
candidate.append(i)
else:
print('something wrong.')
exit()

if(len(candidate) > 1):
print('too many candidate is appear. it needs a recursive function.')
exit()
else:
if(update[2] == 'p'):
arr_p[update[0]] = candidate[0]
for i in range(len(arr_q)):
if(arr_q[i] != 'x'):
table_current[update[0]][i] = (arr_p[update[0]] * arr_q[i]) % 10
table_moveup[update[0]][i] = (arr_p[update[0]] * arr_q[i]) // 10
else:
arr_q[update[1]] = candidate[0]
for i in range(len(arr_p)):
if(arr_p[i] != 'x'):
table_current[i][update[1]] = (arr_p[i] * arr_q[update[1]]) % 10
table_moveup[i][update[1]] = (arr_p[i] * arr_q[update[1]]) // 10

previous_target = target
target = []
moveup = (digit_current + x) // 10

arr_p.reverse()
arr_q.reverse()

p = ''
for i in arr_p:
p += str(i)
q = ''
for i in arr_q:
q += str(i)

print('p : {}'.format(p))
print('q : {}'.format(q))

n = int(n)
p = int(p)
q = int(q)

e = 65537
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
u = pow(p, -1, q)

component = (n, e, d, p, q, u)
key = RSA.construct(component)
cipher = PKCS1_OAEP.new(key)

pt = cipher.decrypt(ct)
print(pt)

~~~

~~~
mito@mito-Virtual-Machine:~/ctf/hackthebox-cyber-apocalypse-ctf-2024/crypto-partial-tenacity/crypto_partial_tenacity$ python3 solve.py
p : 10541549431842783633587614316112542499895727166990860537947158205451961334065983715903944224868775308489240169949600619123741969714205272515647199022167453
q : 11254692541324720060752707148186767582750062945630785066774422168535575089335596479399029695524722638167959390210621853422825328846580189277644256392390351
b'HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}'
~~~

## Iced TEA (Solved)
> HTB{th1s_1s_th3_t1ny_3ncryp710n_4lg0r1thm_____y0u_m1ght_h4v3_4lr34dy_s7umbl3d_up0n_1t_1f_y0u_d0_r3v3rs1ng}

* 関数 `encrypt` で実行されることと逆のことをしてあげればよい。

~~~
import os
#from secret import FLAG
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b
from enum import Enum

class Mode(Enum):
ECB = 0x01
CBC = 0x02

class Cipher:
def __init__(self, key, iv=None):
self.BLOCK_SIZE = 64
self.KEY = [b2l(key[i:i+self.BLOCK_SIZE//16]) for i in range(0, len(key), self.BLOCK_SIZE//16)]
self.DELTA = 0x9e3779b9
self.IV = iv
if self.IV:
self.mode = Mode.CBC
else:
self.mode = Mode.ECB

def _xor(self, a, b):
return b''.join(bytes([_a ^ _b]) for _a, _b in zip(a, b))

def encrypt(self, msg):
msg = pad(msg, self.BLOCK_SIZE//8)
blocks = [msg[i:i+self.BLOCK_SIZE//8] for i in range(0, len(msg), self.BLOCK_SIZE//8)]

ct = b''
if self.mode == Mode.ECB:
for pt in blocks:
ct += self.encrypt_block(pt)
elif self.mode == Mode.CBC:
X = self.IV
for pt in blocks:
enc_block = self.encrypt_block(self._xor(X, pt))
ct += enc_block
X = enc_block
return ct

def decrypt(self, msg):
blocks = [msg[i:i+self.BLOCK_SIZE//8] for i in range(0, len(msg), self.BLOCK_SIZE//8)]

ct = b''
if self.mode == Mode.ECB:
for pt in blocks:
ct += self.decrypt_block(pt)
elif self.mode == Mode.CBC:
X = self.IV
for pt in blocks:
enc_block = self.encrypt_block(self._xor(X, pt))
ct += enc_block
X = enc_block
return ct

def encrypt_block(self, msg):
m0 = b2l(msg[:4])
m1 = b2l(msg[4:])
K = self.KEY
msk = (1 << (self.BLOCK_SIZE//2)) - 1

s = 0
for i in range(32):
s += self.DELTA
m0 += ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
m0 &= msk
m1 += ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
m1 &= msk

m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1

return l2b(m)

def decrypt_block(self, msg):
m0 = b2l(msg[:4])
m1 = b2l(msg[4:])
K = self.KEY
msk = (1 << (self.BLOCK_SIZE//2)) - 1

s = self.DELTA * 32
for i in range(32):
m1 -= ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
m1 &= msk
m0 -= ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
m0 &= msk
s -= self.DELTA

m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1

return l2b(m)

if __name__ == '__main__':
KEY = l2b(int('850c1413787c389e0b34437a6828a1b2', 16))
cipher = Cipher(KEY)
ct = l2b(int('b36c62d96d9daaa90634242e1e6c76556d020de35f7a3b248ed71351cc3f3da97d4d8fd0ebc5c06a655eb57f2b250dcb2b39c8b2000297f635ce4a44110ec66596c50624d6ab582b2fd92228a21ad9eece4729e589aba644393f57736a0b870308ff00d778214f238056b8cf5721a843', 16))
pt = cipher.decrypt(ct)
print(pt)
~~~