4th Crypto CTF 2022 Writeup

# 1. はじめに
　2022/7/15(金) 23:00 JST ～ 7/16(土) 23:00 JSTに開催された「4th Crypto CTF 2022」にチーム「N30Z30N」でソロ参加し、"Mic Check"問以外で18問を解き、1782点（得点を得た421チーム中23位）を獲得しました。
　Crypto CTF には毎年出場していますが、自分にとって比較的解きやすい問題が多数出題されているので、ソロで出て 24 時間頑張れる感じです。反省点としては、難易度 hard の問題をすべて残してしまった（トライすらしなかった）点です。
　以下、簡単にですが（難易度易しい順、solve数多い順に） Writeupを記します。

# 2. Writeup
## 2-1. Baphomet (難易度：easy, 56 points, 93 solves)
### ☆設問

　以下のスクリプトと、暗号化データの入った「flag.enc」が与えられます。

```baphomet.py
#!/usr/bin/env python3

from base64 import b64encode
from flag import flag

def encrypt(msg):
	ba = b64encode(msg.encode('utf-8'))
	baph, key = '', ''

	for b in ba.decode('utf-8'):
		if b.islower():
			baph += b.upper()
			key += '0'
		else:
			baph += b.lower()
			key += '1'

	baph = baph.encode('utf-8')
	key = int(key, 2).to_bytes(len(key) // 8, 'big')

	enc = b''
	for i in range(len(baph)):
		enc += (baph[i] ^ key[i % len(key)]).to_bytes(1, 'big')

	return enc

enc = encrypt(flag)
f = open('flag.enc', 'wb')
f.write(enc)
f.close()
```

### ☆方針・解法

　既知平文攻撃的な考え方で解けます。
　暗号文の長さは 48 バイトで、また Key の作り方から Key の長さは 6 バイトであることが分かります。フラグの始まりは「CCTF」なので[^1]、Base64 エンコードした結果の先頭 6バイトは必ず「Q0NURn」になります。Key と xor する直前のデータの先頭は「q0nurN」ですから、これと暗号文の先頭 6 バイトを xor すれば Key は求まります。この Key を使って暗号化と逆の手順を踏めば復号できます。

### ☆ソルバ

```solve.py
from base64 import b64decode
from pwn import xor

enc = open('flag.enc', 'rb').read()

_k = b"q0nurN"
key = xor(_k, enc[0:6])

_dec = b''
for i in range(len(enc)):
  _dec += (enc[i] ^ key[i % len(key)]).to_bytes(1, 'big')

dec = ""
for b in _dec.decode('utf-8'):
  if b.islower():
    dec += b.upper()
  else:
    dec += b.lower()

dec = b64decode(dec.encode('utf-8'))

print(dec) 
```

### ☆フラグ
**CCTF{UpP3r_0R_lOwER_17Z_tH3_Pr0bL3M}**


## 2-2. Klamkin (難易度：easy, 61 points, 83 solves)
### ☆設問
　サーバに接続して解く問題です。
　q, r, s が指定され、(a * r + b * s) % q == 0 となる a, b に対し (a * x + b * y) % q == 0 となる x, yを求めます。但し x, y いずれかのビット数が指定されます。

### ☆方針・解法
　q, r, s が与えられた段階で、拡張ユークリッド互除法で条件を満た a, b を計算します。x や y の条件（ビット数、以下 "bits" と記す）が示されたら、サーバに以下の x, y を送ります。

　・ x にビット数指定があった場合： x = 2**(bits-1)+1, y = s * x * a % q
　・ y にビット数指定があった場合： x = -r * y * b % q, y = 2**(bits-1)+1

　5 問正答するとフラグを得られました。

### ☆フラグ
**CCTF{f1nDin9_In7Eg3R_50Lut1Ons_iZ_in73rEStIn9!}**


## 2-3. polyRSA (難易度：medium-easy, 42 points, 145 solves)
### ☆設問

　以下のスクリプト等が与えられます。

```polyRSA.py
#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def keygen(nbit = 64):
	while True:
		k = getRandomNBitInteger(nbit)
		p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
		q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
		if isPrime(p) and isPrime(q):
			return p, q

def encrypt(msg, n, e = 31337):
	m = bytes_to_long(msg)
	return pow(m, e, n)

p, q = keygen()
n = p * q
enc = encrypt(flag, n)
print(f'n = {n}')
print(f'enc = {enc}')
```

```output.txt
n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
```

### ☆方針・解法
　SageMath の力を借りて解くことにしました。
　競技中に行った解法は、「p, q を k を変数とする多項式と見たとき、p * q の定数項 を n から引いた数は k を割りるので、n - [p * q の定数項] の約数から k の候補を探索する」というものでした。
　しかし、素直に f = p * q - n と置き、f の factor を見ればすぐ解けました。反省。

### ☆ソルバ（反省後）

```python:solve2.sage
from Crypto.Util.number import *

n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
e = 31337

PR.<k> = PolynomialRing(ZZ)
_p = k**6 + 7 * k**4 - 40 * k**3 + 12 * k**2 - 114 * k + 31377
_q = k**5 - 8 * k**4 + 19 * k**3 - 313 * k**2 - 14 * k + 14011
f = _p * _q - n

for x in f.factor():
  if x[0].degree() == 1:
    _k = -x[0].coefficients()[0]
    p = _p(k=_k)
    q = _q(k=_k)
    phi = (p-1)*(q-1)
    d = inverse(e, int(phi))
    _pt = pow(int(enc), int(d), int(n))
    m = long_to_bytes(pow(int(enc), int(d), int(n)))
    if b"CCTF{" in m:
      print(m)
      break
```

### ☆フラグ
**CCTF{F4C70r!N9_tRIcK5_aR3_fUN_iN_RSA?!!!}**


## 2-4. SOTS (難易度：medium-easy, 49 points, 113 solves)
### ☆設問
　サーバに接続して解く問題です。
　n が示され、 x^2 + y^2 == n  を満たす x と y を求める問題です。

### ☆方針・解法
　Gauss 数体（の整数環）での素因数分解を考えれば OK です。
　yafu を使ってn を素因数分解し、各素因数に対して SageMath で Gauss 数体での分解を計算し、その結果をもとに送信する x, y を構築しました。
　競技時に示された n は整数の範囲で 3 つの素因数に分解されたため、
　
　$$(x_1^2 + y_1^2) (x_2^2 + y_2^2)  (x_3^2 + y_3^2) = X^2 + Y^2$$

ただし

　$$(X,Y) := (x_1x_2x_3 + x_3y_1y_2 - x_2y_1y_3 + x_1y_2y_3,  x_2x_3y_1 - x_1x_3y_2 + x_1x_2y_3 + y_1y_2y_3)$$
　
　を利用して解を求めました。

### ☆ソルバ（n を素因数分解した後の計算に使ったもの）

```python:solve.sage
n1 = 1403575103598950078497501
n2 = 1832215985571864173006269
n3 = 824314708499254102530821

R = ZZ[I]
n1 = R(n1)
x1 = factor(n1)[1][0][0]
y1 = factor(n1)[1][0][1]
n2 = R(n2)
x2 = factor(n2)[1][0][0]
y2 = factor(n2)[1][0][1]
n3 = R(n3)
x3 = factor(n3)[1][0][0]
y3 = factor(n3)[1][0][1]

X = abs(x1*x2*x3 + x3*y1*y2 - x2*y1*y3 + x1*y2*y3)
Y = abs(x2*x3*y1 - x1*x3*y2 + x1*x2*y3 + y1*y2*y3)

print(n1*n2*n3)
print((x1^2+y1^2)*(x2^2+y2^2)*(x3^2+y3^2))
print(X+Y)
print(f"{X},{Y}")
```


### ☆フラグ
**CCTF{3Xpr3sS_4z_Th3_sUm_oF_7w0_Squ4rE5!}**


## 2-5. Volgo (難易度：medium-easy, 65 points, 77 solves)
### ☆設問
　Web サイトが示され、そこでは M-209 [^2] で任意（アルファベット大文字のみ）の平文を暗号化するサービスと、同じ暗号化方式・キーで暗号化したフラグが提供されます。

### ☆方針・解法
　この暗号装置では 5 文字 1 ブロックで扱われ、またいろいろ試してみると先頭 2 ブロックと末尾 2 ブロックは Padding であることが推測されます。
　また、鍵はわかりませんが、試してみると各文字の暗号化は独立している（他の暗号文に影響されない）ことが推測されます。
　以上のことから、平文に相当する文字数（155文字）分、各アルファベット大文字を暗号化し。その結果から平文を求めることができます。

### ☆ソルバ

```solve.py
import requests

alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
url1 = "http://<省略>/flag/fetch"
res = requests.get(url1)
enc = eval(res.text)['flag'].replace(' ', '')[10:-10]

d = {}
url2 = "http://<省略>/m209/encipher"
for i in range(0x41, 0x41+26):
  to_send = chr(i)*155
  res = requests.post(url2,data={"plain":to_send})
  d[chr(i)] = eval(res.text)['cipher'].replace(' ', '')[10:-10]

flag = ""
for i in range(len(enc)):
  for c in alpha:
    print(enc[i], d[c][i], c)
    if enc[i] == d[c][i]:
      flag += c
      break

print(flag.replace("Z"," "))
#YOU KNOW HOW TO FORMAT FLAG JUST PUT UPCOMING LETTERS WITHIN CURLY BRACES FOLLOWED BY CCTF OOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR
```

### ☆フラグ
**CCTF{OOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR}**


## 2-6. Jeksign (難易度：medium-easy, 100 points, 45 solves)
### ☆設問

　サーバに接続して解く問題です。
　本問ではスクリプトが示されています[^3]。
　1337(z^4 - x^2) == 31337(y^2 - z^4) を満たす x, y, z を答える問題です。設問は 19 個あり、z のビット数は 30-bit から 1 ずつ増え 48-bit まで指定されます。

```jeksign.py
#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import gensol, nbit_gensol
from flag import flag

m = bytes_to_long(flag.encode('utf-8'))
print(m)

a = 1337
b = 31337

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.readline().strip()

def main():
	border = "|"
	pr(border*72)
	pr(border, "Welcome crypto guys! Here we are looking for the solution of special", border)
	pr(border, "Diophantine equation: 1337(z^4 - x^2) = 31337(y^2 - z^4) in natural ", border)
	pr(border, "numbers, in each stage solve the equation in mentioned interval :)  ", border)
	pr(border*72)

	STEP, level = 0, 19

	while True:
		p, q = nbit_gensol(1337, 31337, STEP + 30)
		x, y, z = gensol(a, b, p, q)
		pr(border, f"Send a solution like `x, y, z' such that the `z' is {STEP + 30}-bit: ")
		ans = sc()
		try:
			X, Y, Z = [int(_) for _ in ans.split(',')]
			NBIT = Z.bit_length()
		except:
			die(border, 'Your input is not valid, Bye!')
		if 1337*(Z**4 - X**2) == 31337*(Y**2 - Z**4) and NBIT == STEP + 30:
			if STEP == level - 1:
				die(border, f'Congrats, you got the flag: {flag}')
			else:
				pr('| good job, try to solve the next challenge :P')
				STEP += 1
		else:
			die(border, 'your answer is not correct, Bye!!')

if __name__ == '__main__':
	main()
```

### ☆方針・解法
　z を 1 つ決めてしまえば、x = y = z^2 という自明な解が塞がれていないので簡単に通ってしまいます。

### ☆ソルバ

```solve.py
import telnetlib

HOST = <省略>
PORT = <省略>

def readline():
    return tn.read_until(b"\n")

def sendline(to_send):
    tn.write(to_send.encode() + b"\n")

tn = telnetlib.Telnet(HOST, PORT)

for i in range(5):
  readline()

for i in range(30, 49):
  print(readline())
  z = 2**(i-1)
  x = z**2
  y = z**2
  to_send = str(x) + "," + str(y) + "," + str(z)
  sendline(to_send)
  print(readline())
```

### ☆フラグ
**CCTF{4_diOpH4nT1nE_3Qua7i0n__8Y__Jekuthiel_Ginsbur!!}**


## 2-7. Keydream (難易度：medium-easy, 105 points, 42 solves)
### ☆設問
　RSA 問です。以下のスクリプト等が提示されます。

```keydream.py
#!/usr/bin/env python3

from Crypto.Util.number import *
import string
from flag import flag

def randstr(l):
	rstr = [(string.printable[:62] + '_')[getRandomRange(0, 62)] for _ in range(l)]
	return ''.join(rstr)


def encrypt(msg, l):
	while True:
		rstr = 'CCTF{it_is_fake_flag_' + randstr(l) + '_90OD_luCk___!!}'
		p = bytes_to_long(rstr.encode('utf-8'))
		q = bytes_to_long(rstr[::-1].encode('utf-8'))
		if isPrime(p) and isPrime(q):
			n = p * q
			e, m = 65537, bytes_to_long(msg.encode('utf-8'))
			c = pow(m, e, n)
			return n, c

n, c = encrypt(flag, 27)

print(f'n = {n}')
print(f'c = {c}')
```

```output.txt
n = 23087202318856030774680571525957068827041569782431397956837104908189620961469336659300387982516148407611623358654041246574100274275974799587138270853364165853708786079644741407579091918180874935364024818882648063256767259283714592098555858095373381673229188828791636142379379969143042636324982275996627729079
c = 3621516728616736303019716820373078604485184090642291670706733720518953475684497936351864366709813094154736213978864841551795776449242009307288704109630747654430068522939150168228783644831299534766861590666590062361030323441362406214182358585821009335369275098938212859113101297279381840308568293108965668609

```

### ☆方針・解法
　pの（qもですが）十分小さい一部分だけが未知ですので、Coppersmith（SageMath の small_roots）で解けます。

### ☆ソルバ

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

n = 23087202318856030774680571525957068827041569782431397956837104908189620961469336659300387982516148407611623358654041246574100274275974799587138270853364165853708786079644741407579091918180874935364024818882648063256767259283714592098555858095373381673229188828791636142379379969143042636324982275996627729079
c = 3621516728616736303019716820373078604485184090642291670706733720518953475684497936351864366709813094154736213978864841551795776449242009307288704109630747654430068522939150168228783644831299534766861590666590062361030323441362406214182358585821009335369275098938212859113101297279381840308568293108965668609
e = 65537

l = 27

PR.<x> = PolynomialRing(Zmod(n))
base = bytes_to_long(b'CCTF{it_is_fake_flag_' + b'\x00' * l + b'_90OD_luCk___!!}')
f = 256**16 * x + base
f = f.monic()
r = f.small_roots(X=256**l, beta=0.3)

p = int(256**16 * r[0] + base)
q = n // p
assert p * q == n

phi = (p-1)*(q-1)//GCD(p-1,q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(int(c),int(d),int(n))))
```

### ☆フラグ
**CCTF{h0M3_m4dE_k3Y_Dr1vEn_CrYp7O_5ySTeM!}**


## 2-8. Infinity castle (難易度：medium-easy, 131 points, 32 solves)
### ☆設問
　以下のスクリプト等が提示されます。
　RSA 問で、p, q の計算に必要な情報が示されますが、何も考えずそのまま計算式を実行するとベラボーな時間がかかる仕掛けとなっています。

```infinity_castle.py
#!/usr/bin/env python3

from Crypto.Util.number import *
from os import urandom

class TaylorSeries():

	def __init__(self, order):
		self.order = order
		
	def coefficient(self, n):
		i = 0
		coef = 1
		while i < n:
			i += 1
			coef *= (coef * (1/2-i+1)) / i
		return coef

	def find(self, center):
		sum = 0
		center -= 1
		i = 0
		while i < self.order:
			sum += (center**(1/2-i) * self.coefficient(i))
			i += 1
		return sum

def xor(cip, key):
	repeation = 1 + (len(cip) // len(key))
	key = key * repeation
	key = key[:len(cip)]
	
	msg = bytes([c ^ k for c, k in zip(cip, key)])
	return msg

# If you run these 3 functions (diamond, triage, summarize) with big numbers, they will never end
# You need to optimize them first

def diamond(num):
	output = 0
	for i in range(num):
		output += i*2 + 1
	return output

def triage(num):
	output = 0
	index = 0
	for i in range(num):
		output += (i+index)*6 + 1
		index += i
	return output

def summarize(b):
	order = getRandomRange(1000, 2000)
	t = TaylorSeries(order)
	output = 0
	
	i = 2
	while i < b:
		b1 = t.find(i)
		b2 = t.find(i+1)
		output += (b1+b2) / 2
		i += 1
	return output

KEY_SIZE = 2048
p, q = [getPrime(KEY_SIZE) for _ in '01']

e, n = 0x10001, p*q

f = open ('./message.txt', 'rb')
message = f.read()
f.close()
msg_length = len(message)
padded_msg = message + urandom(len(long_to_bytes(n)) - msg_length)
padded_msg_length = len(padded_msg)

xor_key = long_to_bytes(int(summarize(n)))[:padded_msg_length]
assert(len(xor_key) == 512)

enc0 = xor(padded_msg, xor_key)
assert(bytes_to_long(enc0) < n)

c0 =  abs(diamond(p) - diamond(q))
c1 =  triage(p)
c1 += 3*n*(p+q)
c1 += triage(q)

m = bytes_to_long(enc0)
enc1 = pow(m, e, n)

print(f"c0 = {c0}")
print(f"c1 = {c1}")
print(f"enc = {enc1}")
```

```output.txt
c0 = 194487778980461745865921475300460852453586088781074246328543689440168930873549359227127363759885970436167330043371627413542337857082400024590112412164095470165662281502211335756288082198009158469871465280749846525326701136380764079685636158337203211609233704905784093776008350120607841177268965738426317288541638374141671346404729428158104872411498098187946543666987926130124245185069569476433120128275581891425551325847219504501925282012199947834686225770246801353666030075146469275695499044424390475398423700504158154044180028733800154044746648133536737830623670383925046006108348861714435567006327619892239876863209887013290251890513192375749866675256952802329688897844132157098061758362137357387787072005860610663777569670198971946904157425377235056152628515775755249828721767845990597859165193162537676147173896835503209596955703313430433124688537275895468076469102220355973904702901083642275544954262724054693167603475188412046722656788470695566949847884250306735314144182029335732280420629131990311054229665691517003924788583771265625694414774865289407885678238795596912006567817508035434074250123869676396153982762032750080222602796273083162627489526255501643913672882350236497429678928099868244687228703074267962827621792960
c1 = 102325064080381160170299055162846304227217463467232681115953623386548494169967745781550171804781503102663445039561476870208178139548389771866145006535051362059443515034504958703659546162037904784821960707630188600064568878674788077706711506213779443920430038560373854184526850365974450688458342413544179732143225845085164110594063440979455274250021370090572731855665413325275414458572412561502408983107820534723804225765540316307539962199024757378469001612921489902325166003841336027940632451584642359132723894801946906069322200784708303615779699081247051006259449466759863245508473429631466831174013498995506423210088549372249221415401309493511477847517923201080509933268996867995533386571564898914042844521373220497356837599443280354679778455765441375957556266205953496871475611269965949025704864246188576674107448587696941054123618319505271195780178776338475090463487960063464172195337956577785477587755181298859587398321270677790915227557908728226236404532915215698698185501562405374498053670694387354757252731874312411228777004316623425843477845333936913444143768519959591070492639650368662529749434618783626718975406802741753688956961837855306815380844030665696781685152837849982159679122660714556706669865596780528277684800454866433826417980212164051043504955615794706595412705883261111953152250227679858538249797999044336210905975316421254442221408945203647754303635775048438188044803368249944201671941949138202928389951227347433255867504906597772044398973241425387514239164853656233776024571606159378910745571588836981735827902305330330946219857271646498602227088657739442867033212012876837654750348578740516798444734534291467314881324902354425889448102902750077077381896216130734894767553834949561471219923459897244690006643798812989271282475503126962274052192342840870308710338336817452628324667507548265612892611100350882163205858101959976
enc = 122235247669762131006183252122503937958296387791525458429403709404875223067116491817728568224832483391622109986550732469556761300197133827976956875865159629512476600711420561872409721582387803219651736262581445978042694384374119142613277808898398213602093802571586386354257378956087240174787723503606671543195193114158641301908622673736098768829071270132073818245595918660134745516367731595853832524328488074054536278197115937409643221809577554866060292157239061557708159310445977052686561229611117673473208278176118561352693319461471419694590218295911647368543698198762827636021268989705079848502749837879584394379300566277359149621932579222865430374652678738198451655509408564586496375811666876030847654260305392984710580761255795785508407844683687773983669843744274915862335181251050775093896006210092665809300090715190088851654138383362259256212093670748527819287681468901379286722214112321906917311154811516336259463356911326393701445497605365038857575515541024824906818473933597129846235905072394148879079996812146836910199111439031562946495046766063326815863624262541346543552652673629442370320109404700346028639853707278295255350982238521659924641921142615894039995513480511108116053798143154593343124822462519555715118822045
```

### ☆方針・解法
　「膨大な計算量を数学の力で何とかする」的な問題です。個人的な好き嫌いで言えば、こういうのが「大好き」です。
　コードを読み解くと、diamond は平方、triage は立方を計算するものであることが分かります（高校数学のΣ計算を思い出しましょう）。
　よって、c0 = |p^2-q^2|、c1 = (p+q)^3 であることがわかり、これらから容易に p, q が計算できます。
　また、TaylorSeries の find は平方根の近似計算にほかなりません。summarize は平方根の総和をベースに算出できますが、平方根の総和には近似式
　
　$$\sum_{k=1}^n \sqrt{k} \fallingdotseq \frac{2n^{\frac{3}{2}}}{3} + \frac{\sqrt{n}}{2} $$
　
　があるのでそれを利用します[^4]。

### ☆ソルバ

```python:solve.sage
from Crypto.Util.number import *
from ptrlib import xor
import gmpy2

def summarize(n):
  K = RealField(4096)
  x = K(n)
  sum = 2 * x^(3/2) /3 + x^(1/2)/2
  return sum - 1 - K(2).nth_root(2)/2 - x.nth_root(2)/2
  
c0 = 194487778980461745865921475300460852453586088781074246328543689440168930873549359227127363759885970436167330043371627413542337857082400024590112412164095470165662281502211335756288082198009158469871465280749846525326701136380764079685636158337203211609233704905784093776008350120607841177268965738426317288541638374141671346404729428158104872411498098187946543666987926130124245185069569476433120128275581891425551325847219504501925282012199947834686225770246801353666030075146469275695499044424390475398423700504158154044180028733800154044746648133536737830623670383925046006108348861714435567006327619892239876863209887013290251890513192375749866675256952802329688897844132157098061758362137357387787072005860610663777569670198971946904157425377235056152628515775755249828721767845990597859165193162537676147173896835503209596955703313430433124688537275895468076469102220355973904702901083642275544954262724054693167603475188412046722656788470695566949847884250306735314144182029335732280420629131990311054229665691517003924788583771265625694414774865289407885678238795596912006567817508035434074250123869676396153982762032750080222602796273083162627489526255501643913672882350236497429678928099868244687228703074267962827621792960
c1 = 102325064080381160170299055162846304227217463467232681115953623386548494169967745781550171804781503102663445039561476870208178139548389771866145006535051362059443515034504958703659546162037904784821960707630188600064568878674788077706711506213779443920430038560373854184526850365974450688458342413544179732143225845085164110594063440979455274250021370090572731855665413325275414458572412561502408983107820534723804225765540316307539962199024757378469001612921489902325166003841336027940632451584642359132723894801946906069322200784708303615779699081247051006259449466759863245508473429631466831174013498995506423210088549372249221415401309493511477847517923201080509933268996867995533386571564898914042844521373220497356837599443280354679778455765441375957556266205953496871475611269965949025704864246188576674107448587696941054123618319505271195780178776338475090463487960063464172195337956577785477587755181298859587398321270677790915227557908728226236404532915215698698185501562405374498053670694387354757252731874312411228777004316623425843477845333936913444143768519959591070492639650368662529749434618783626718975406802741753688956961837855306815380844030665696781685152837849982159679122660714556706669865596780528277684800454866433826417980212164051043504955615794706595412705883261111953152250227679858538249797999044336210905975316421254442221408945203647754303635775048438188044803368249944201671941949138202928389951227347433255867504906597772044398973241425387514239164853656233776024571606159378910745571588836981735827902305330330946219857271646498602227088657739442867033212012876837654750348578740516798444734534291467314881324902354425889448102902750077077381896216130734894767553834949561471219923459897244690006643798812989271282475503126962274052192342840870308710338336817452628324667507548265612892611100350882163205858101959976
enc = 122235247669762131006183252122503937958296387791525458429403709404875223067116491817728568224832483391622109986550732469556761300197133827976956875865159629512476600711420561872409721582387803219651736262581445978042694384374119142613277808898398213602093802571586386354257378956087240174787723503606671543195193114158641301908622673736098768829071270132073818245595918660134745516367731595853832524328488074054536278197115937409643221809577554866060292157239061557708159310445977052686561229611117673473208278176118561352693319461471419694590218295911647368543698198762827636021268989705079848502749837879584394379300566277359149621932579222865430374652678738198451655509408564586496375811666876030847654260305392984710580761255795785508407844683687773983669843744274915862335181251050775093896006210092665809300090715190088851654138383362259256212093670748527819287681468901379286722214112321906917311154811516336259463356911326393701445497605365038857575515541024824906818473933597129846235905072394148879079996812146836910199111439031562946495046766063326815863624262541346543552652673629442370320109404700346028639853707278295255350982238521659924641921142615894039995513480511108116053798143154593343124822462519555715118822045

p_plus_q = gmpy2.iroot(c1,3)[0]
p_minus_q = c0 // p_plus_q

p = int((p_plus_q + p_minus_q) // 2)
q = int(p_plus_q - p)
n = p * q

phi = (p-1)*(q-1)//GCD(p-1,q-1)
d = inverse(0x10001, phi)

m = pow(enc, d, n)

xor_key = long_to_bytes(int(summarize(n)))[:512]
msg  = xor(long_to_bytes(int(m)), xor_key)
print(msg)
```

### ☆フラグ
**CCTF{Mix1ng_c4lcUluS_w17h_Numb3r_The0Rry_S33ms_s7r0ng_cRyp70_Sch3m4!!}**


## 2-9. Aniely (難易度：medium, 66 points, 76 solves)
### ☆設問
　以下のスクリプト等が提示されます。
　chacha20 の亜流のような stream 暗号です。

```aniely.py
#!/usr/bin/env python3

from struct import *
from os import *
from secret import passphrase, flag

def aniely_stream(passphrase):
	def mixer(u, v):
		return ((u << v) & 0xffffffff) | u >> (32 - v)

	def forge(w, a, b, c, d):
		for i in range(2):
			w[a] = (w[a] + w[b]) & 0xffffffff
			w[d] = mixer(w[a] ^ w[d], 16 // (i + 1))
			w[c] = (w[c] + w[d]) & 0xffffffff
			w[b] = mixer(w[b] ^ w[c], (12 + 2*i) // (i + 1))

	bring = [0] * 16
	bring[:4] = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
	bring[4:12] = unpack('<8L', passphrase)
	bring[12] = bring[13] = 0x0
	bring[14:] = [0] * 2

	while True:
		w = list(bring)
		for _ in range(10):
			forge(w, 0x0, 0x4, 0x8, 0xc)
			forge(w, 0x1, 0x5, 0x9, 0xd)
			forge(w, 0x2, 0x6, 0xa, 0xe)
			forge(w, 0x3, 0x7, 0xb, 0xf)
			forge(w, 0x0, 0x5, 0xa, 0xf)
			forge(w, 0x1, 0x6, 0xb, 0xc)
			forge(w, 0x2, 0x7, 0x8, 0xd)
			forge(w, 0x3, 0x4, 0x9, 0xe)
		for c in pack('<16L', *((w[_] + bring[_]) & 0xffffffff for _ in range(16))):
			yield c
		bring[12] = (bring[12] + 1) & 0xffffffff
		if bring[12] == 0:
			bring[13] = (bring[13] + 1) & 0xffffffff

def aniely_encrypt(msg, passphrase):
	if len(passphrase) < 32:
		passphrase = (passphrase * (32 // len(passphrase) + 1))[:32]
	rand = urandom(2) * 16
	return bytes(a ^ b ^ c for a, b, c in zip(msg, aniely_stream(passphrase), rand))

key = bytes(a ^ b for a, b in zip(passphrase, flag))
enc = aniely_encrypt(passphrase, key)
print(f'key = {key.hex()}')
print(f'enc = {enc.hex()}')
```

```output.txt
key = 4dcceb8802ae3c45fe80ccb364c8de19f2d39aa8ebbfb0621623e67aba8ed5bc
enc = e67a67efee3a80b66af0c33260f96b38e4142cd5d9426f6f156839f2e2a8efe8
```

### ☆方針・解法
　「rand を固定したとき aniely_encrypt(enc, key) = passphrase」をエスパーしたので解けました。
　rand の部分は 2 バイトなので総当たりします。

### ☆ソルバ

```solve.py
from Crypto.Util.number import *
from struct import *
from os import *
from pwn import xor
key = bytes.fromhex("4dcceb8802ae3c45fe80ccb364c8de19f2d39aa8ebbfb0621623e67aba8ed5bc")
enc = bytes.fromhex("e67a67efee3a80b66af0c33260f96b38e4142cd5d9426f6f156839f2e2a8efe8")

def aniely_stream(passphrase):
  def mixer(u, v):
    return ((u << v) & 0xffffffff) | u >> (32 - v)
  def forge(w, a, b, c, d):
    for i in range(2):
      w[a] = (w[a] + w[b]) & 0xffffffff
      w[d] = mixer(w[a] ^ w[d], 16 // (i + 1))
      w[c] = (w[c] + w[d]) & 0xffffffff
      w[b] = mixer(w[b] ^ w[c], (12 + 2*i) // (i + 1))
  bring = [0] * 16
  bring[:4] = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
  bring[4:12] = unpack('<8L', passphrase)
  bring[12] = bring[13] = 0x0
  bring[14:] = [0] * 2
  while True:
    w = list(bring)
    for _ in range(10):
      forge(w, 0x0, 0x4, 0x8, 0xc)
      forge(w, 0x1, 0x5, 0x9, 0xd)
      forge(w, 0x2, 0x6, 0xa, 0xe)
      forge(w, 0x3, 0x7, 0xb, 0xf)
      forge(w, 0x0, 0x5, 0xa, 0xf)
      forge(w, 0x1, 0x6, 0xb, 0xc)
      forge(w, 0x2, 0x7, 0x8, 0xd)
      forge(w, 0x3, 0x4, 0x9, 0xe)
    for c in pack('<16L', *((w[_] + bring[_]) & 0xffffffff for _ in range(16))):
      yield c
    bring[12] = (bring[12] + 1) & 0xffffffff
    if bring[12] == 0:
      bring[13] = (bring[13] + 1) & 0xffffffff

def aniely_encrypt(msg, passphrase):
  if len(passphrase) < 32:
    passphrase = (passphrase * (32 // len(passphrase) + 1))[:32]
  #rand = urandom(2) * 16
  rand = b"\x00"*32
  return bytes(a ^ b ^ c for a, b, c in zip(msg, aniely_stream(passphrase), rand))

_passphrase = aniely_encrypt(enc, key)
for i in range(0x10000):
  passphrase = xor(_passphrase, i.to_bytes(2,"big"))
  flag = xor(passphrase, key)
  if b"CCTF{" in flag:
    print(flag)
    break
```

### ☆フラグ
**CCTF{7rY_t0_D3cRyPT_z3_ChaCha20}**

## 2-10. Diploma (難易度：medium, 72 points, 68 solves)
### ☆設問
　行列の order を求める問題が複数出されます。

### ☆方針・解法
　Jordan 標準形を求め、対角成分（固有多項式の根）の order の LCM を計算します[^5]。
　order の計算では他に乗ずるべき値があるのですが、結果的に 1 になるものしか出題されなかったので無視できました。
　（2022/7/26追記：Jordan 標準形の計算を手で行わず、直接 M.multiplicative_order() で行列の order は計算できました。SageMath 強いです。）

### ☆ソルバ（汚いです。スミマセン。）

```python:solve.sage
from Crypto.Util.number import *
import telnetlib

HOST = <省略>
PORT = <省略>

def readline():
    return tn.read_until(b"\n")

def readuntil(stopper):
    return tn.read_until(stopper.encode())

def sendline(to_send):
    tn.write(to_send.encode() + b"\n")

def linestrip(s):
  s = s.strip()
  while(True):
    _s = s
    s = s.replace("  ", " ")
    if _s == s:
      break
  s = s.replace("[ ", "[")
  s = s.replace(" ]", "]")
  s = s.replace(" ", ",")
  return eval(s)

tn = telnetlib.Telnet(HOST, PORT)

for i in range(6):
  readline()

while(True):
  p = int(readline().decode().replace("| Generating the parameters for p = ", "").replace(", please wait...", ""))
  print("p=", p)
  readline()
  data = readuntil("| Send the order of matrix M:").decode().split("\n")
  #print(data)
  m = []
  for i in range(len(data)-1):
    m.append(linestrip(data[i]))
  print(m)
  M = Matrix(GF(p),m)
  s = len(M.rows())
  chM = M.charpoly()
  K.<a> = chM.splitting_field()
  _M = Matrix(K, M)
  J, X = _M.jordan_form(transformation=True)
  ans = 1
  for i in range(s):
    ans = LCM(ans, J[i][i].multiplicative_order())
  print(ans)
  sendline(str(ans))
  readline()
  result = readline()
  print(result)
  if b"CCTF" in result:
    break
```

### ☆フラグ
**CCTF{ma7RicES_4R3_u5EfuL_1n_PUbl!c-k3y_CrYpt0gr4Phy!}**

## 2-11. Cantilever (難易度：medium, 79 points, 60 solves)
### ☆設問
　以下の通り、スクリプト等が提示されます。
　
```cantilever.py
#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def gen_primes(nbit, imbalance):
	p = 2
	FACTORS = [p]
	while p.bit_length() < nbit - 2 * imbalance:
		factor = getPrime(imbalance)
		FACTORS.append(factor)
		p *= factor
	rbit = (nbit - p.bit_length()) // 2

	while True:
		r, s = [getPrime(rbit) for _ in '01']
		_p = p * r * s
		if _p.bit_length() < nbit: rbit += 1
		if _p.bit_length() > nbit: rbit -= 1
		if isPrime(_p + 1):
			FACTORS.extend((r, s))
			p = _p + 1
			break

	FACTORS.sort()
	return (p, FACTORS)

def genkey(nbit, imbalance, e):
	while True:
		p, FACTORS = gen_primes(nbit // 2, imbalance)
		if len(FACTORS) != len(set(FACTORS)):
			continue
		q, q_factors = gen_primes(nbit // 2, imbalance + 1)
		if len(q_factors) != len(set(q_factors)):
			continue
		factors = FACTORS + q_factors
		if e not in factors:
			break
	n = p * q
	return n, (p, q)

nbit = 2048
imbalance = 19
e = 0x10001

m_1 = bytes_to_long(flag[:len(flag) // 2])
m_2 = bytes_to_long(flag[len(flag) // 2:])

n, PRIMES = genkey(nbit, imbalance, e)

c_1 = pow(m_1, e, n)
c_2 = pow(e, m_2, n)

print(f'n = {n}')
print(f'c_1 = {c_1}')
print(f'c_2 = {c_2}')
```

```output.txt
n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212

```

### ☆方針・解法
　n の素因数は 2^19-smooth なので、p, q の算出には p-1 法が使えます。
　c_1 は通常の RSA で復号できますが、 c_2 は discrete log の計算が必要でしたので SageMath の力を借りました。

### ☆ソルバ

```solve1.py
#https://haru-note3.com/prime/Pollards-p-minus-1-algorithm.html
from sympy import primerange, nextprime
import math

def p_minus_1_method(n, B, a=2):
    for prime in primerange(1, B + 1):
        l = math.floor(math.log(n) / math.log(prime))
        a = pow(a, prime**l, n)
        #print(prime)
    d = math.gcd(a - 1, n)
    if 1 < d and d < n:
        return d
    else:
        return "unsolved"

n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
B = 2**19
a = 2
while(True):
  res = p_minus_1_method(n, B, a)
  if res != "unsolved":
    print(res)
    break
  a = nextprime(a)
  print(a)

#83408372012221120677052349409462320990177094246143674474872152829440524098582262384066400107950985845255268335597502228206679771838750219696329523257176739436871327238322817403970284015587320158034304282786944710043150568360761457471641695390427267786485448748458445872307883254297662715749746270343116946519
```

```python:solve2.sage
from Crypto.Util.number import *

n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
e = 0x10001

p = 83408372012221120677052349409462320990177094246143674474872152829440524098582262384066400107950985845255268335597502228206679771838750219696329523257176739436871327238322817403970284015587320158034304282786944710043150568360761457471641695390427267786485448748458445872307883254297662715749746270343116946519
q = n // p

assert p*q == n

phi = (p-1)*(q-1)//GCD(p-1,q-1)
d1 = int(inverse(e, phi))

m1 = int(pow(int(c_1), d1,n))

Fp = GF(p)
Fq = GF(q)

c2p = Fp(c_2)
c2q = Fq(c_2)
ep = Fp(e)
eq = Fq(e)

dp = discrete_log(c2p, ep)
dq = discrete_log(c2q, eq)
m2 = int(crt([dp,dq],[p-1,q-1]))

m = long_to_bytes(m1) + long_to_bytes(m2)

print(long_to_bytes(m1))
```

### ☆フラグ
**CCTF{5L3Ek_4s__s1lK__Ri9H7?!}**


## 2-12. DBB (難易度：medium, 103 points, 43 solves)
### ☆設問
　ECDLP 問です。以下の通りスクリプト等が提示されます。

```python:dbb.sage
#!/usr/bin/env sage

from Crypto.Util.number import *
from secret import n, B, BASE_POINT, FLAG

m = bytes_to_long(FLAG)
assert m < n

F = IntegerModRing(n)
E = EllipticCurve(F, [31337, B])

BASE_POINT = E(BASE_POINT)

P = m * BASE_POINT
print(f'n = {n}')
print(f'BASE_POINT.x = {BASE_POINT.xy()[0]}')
print(f'P = {P.xy()[0], P.xy()[1]}')

```

```output.txt
n = 34251514713797768233812437040287772542697202020425182292607025836827373815449
BASE_POINT.x = 7331
P = (10680461779722115247262931380341483368049926186118123639977587326958923276962, 4003189979292111789806553325182843073711756529590890801151565205419771496727)
```

### ☆方針・解法
　n が合成数なので、n の各素因数を法とした楕円曲線での DLP を解き、その結果を CRT して元の楕円曲線での DLP の解を導きます（Pohlig-Hellman法）。
　CRT するときの modulo は各楕円曲線における G の order となることに注意します。

### ☆ソルバ

```python:solve.sage
n = 34251514713797768233812437040287772542697202020425182292607025836827373815449
bx = 7331
P = (10680461779722115247262931380341483368049926186118123639977587326958923276962, 4003189979292111789806553325182843073711756529590890801151565205419771496727)
B = P[1]^2 - P[0]^3 - 31337 * P[0] % n

F = IntegerModRing(n)
E = EllipticCurve(F, [31337, B])
G = E.lift_x(bx)
P = E(P)

ps = [11522256336953175349, 14624100800238964261, 203269901862625480538481088870282608241]

assert n == ps[0]*ps[1]*ps[2]

E0 = EllipticCurve(GF(ps[0]), [31337, B])
P0 = E0(P)
G0 = E0(G)
d0 = G0.discrete_log(P0)

E1 = EllipticCurve(GF(ps[1]), [31337, B])
P1 = E1(P)
G1 = E1(G)
d1 = G1.discrete_log(P1)

E2 = EllipticCurve(GF(ps[2]), [31337, B])
P2 = E2(P)
G2 = E2(G)
d2 = G2.discrete_log(P2)

m = crt([int(d0),int(d1),int(d2)],[G0.order(),G1.order(),G2.order()])
print(long_to_bytes(m))

```

### ☆フラグ
**CCTF{p0Hl!9_H31LmaN_4tTackin9!}**


## 2-13. Starter ECC (難易度：medium, 103 points, 43 solves)
### ☆設問
　ECDLP 問・・・と見せかけて、実は合成数における平方根算出問題です。

```python:starter_ecc.sage
#!/usr/bin/env sage

from Crypto.Util.number import *
from secret import n, a, b, x, flag

y = bytes_to_long(flag.encode('utf-8'))

assert y < n
E = EllipticCurve(Zmod(n), [a, b])

try:
	G = E(x, y)
	print(f'x = {x}')
	print(f'a = {a}')
	print(f'b = {b}')
	print(f'n = {n}')
	print('Find the flag :P')
except:
	print('Ooops, ERROR :-(')
```

```output.txt
x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
Find the flag :P
```

### ☆方針・解法
　n をいくつかに分解し、それぞれの mod. で平方根を計算して CRT をとります。
　平方根は各々の mod. で複数存在し得るので、フラグ（b"CCTF{"）を含むものを全探索します。
　各 mod. での平方根計算では、sqrt だとなぜか失敗することが多いので、nth_root を使ったところサクッと計算できました。

### ☆ソルバ（競技で使ったものを一部改良）

```python:solve.sage
from Crypto.Util.number import *
x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
n0 = 2^63
n1 = 690712633549859897233^6
n2 = 651132262883189171676209466993073^5

assert n == n0*n1*n2

R0 = Zmod(n0)
x0 = R0(x)
y0s = R0(x0^3 + a*x0 + b).nth_root(2, all=True)

R1 = Zmod(n1)
x1 = R1(x)
y1s = R1(x1^3 + a*x1 + b).nth_root(2, all=True)

R2 = Zmod(n2)
x2 = R2(x)
y2s = R2(x2^3 + a*x2 + b).nth_root(2, all=True)

for y0 in y0s:
  for y1 in y1s:
    for y2 in y2s:
      y = crt([int(y0),int(y1),int(y2)],[int(n0),int(n1),int(n2)])
      m = long_to_bytes(y)
      if b"CCTF{" in m:
        print(m)
        break
```

### ☆フラグ
**CCTF{8E4uTy_0f_L1f7iN9_cOm3_Up!!}**


## 2-14. Oak land (難易度：medium, 122 points, 35 solves)
### ☆設問
　DLP っぽい問題です。以下のスクリプト等が提示されます。
　
```oak_land.py
#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576

x = bytes_to_long(flag.encode('utf-8'))
assert x < p
c = (110 * pow(e, x, p) + 313 * pow(f, x, p) + 114 * pow(g, x, p)) % p
print(f'c = {c}')
```

```output.txt
c = 871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356
```

### ☆方針・解法
　最初見たときは無理ゲーじゃね？と思ったのですが、f や g を e のべき乗で表現して pow(e, x, p) を X と置けば、 c は X の多項式で表せるので、X が計算できさらに DLP で x が分かりそうです。

### ☆ソルバ（実際は SageMath のコンソールに 1 行ずつ入力して計算を進めました）

```python:solve.sage
from Crypto.Util.number import *
c = 871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356
p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576

F = GF(p)
g = F(g)
f = F(f)
e = F(e)
c = F(c)
a = discrete_log(f, e) #p-2
b = discrete_log(g, e) #p-3

PR.<X> = PolynomialRing(F)
pol = (110*X^3 + 313*X + 114 - c * X^2 ).monic()
xx = pol.roots()[0][0] #6621736714803975486469770941631918297557515256645141403866696899656801529069492623812629032566382224631133756513615225604518504150834965984951182186972792703483282014259169249309903503054330793332575590535531

x = discrete_log(xx,e)
#130669746807581038734209381694055163726297497321549047017439654852953086676029610991997
print(long_to_bytes(x))
```

### ☆フラグ
**CCTF{V33333rY_eeeeZy_DLP_cH41L3n9E!}**

## 2-15. Resign (難易度：medium, 122 points, 35 solves)　
### ☆設問
　サーバに接続して解く署名系の問題です。
　以下の通り、スクリプトが提示されます。

```resign.py
#!/usr/bin/env python3

from Crypto.Util.number import *
from hashlib import sha1
import sys
from flag import flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.readline().strip()

def main():
	border = "|"
	pr(border*72)
	pr(border, " Hi, Try to guess our RSA private key to sign my message, talented  ", border)
	pr(border, " hackers like you ;) are able to do it, they are *Super Guesser* :) ", border)
	pr(border*72)

	p, q = [getPrime(1024) for _ in '__']
	n, e = p * q, 65537
	phi = (p - 1) * (q - 1)
	d = inverse(e, phi)

	MSG = b'::. Can you forge any signature? .::'
	h = bytes_to_long(sha1(MSG).digest())
	SIGN = pow(h, d, n)

	while True:
		pr("| Options: \n|\t[G]uess the secret key \n|\t[R]eveal the parameters \n|\t[S]ign the message \n|\t[P]rint the signature \n|\t[Q]uit")
		ans = sc().lower()
		if ans == 'g':
			pr(border, f"please send the RSA public exponent and PARAMS p, q separated by comma like e, p, q: ")
			PARAMS = sc()
			try:
				E, P, Q = [int(_) for _ in PARAMS.split(',')]
				if P.bit_length() == Q.bit_length() == 1024 and P != Q:
					N = P * Q
					PHI = (P - 1) * (Q - 1)
					D = inverse(E, PHI)
					if pow(h, D, N) == SIGN:
						e, n, d = E, N, D
						pr(border, 'Great guess, now you are able to sign any message!!!')
					else:
						pr(border, 'Your RSA parameters are not correct!!')
				else: raise Exception('Invalid RSA parameters!!')
			except: pr(border, "Something went wrong!!")
		elif ans == 'r':
			pr(border, f'e = {e}')
			pr(border, f'n = {n}')
		elif ans == "p":
			pr(border, f'SIGN = {SIGN}')
		elif ans == 's':
			pr(border, "Please send the signature of this message: ")
			pr(border, f"MSG = {MSG[4:-4]}")
			sgn = sc()
			try:
				sgn = int(sgn)
				_continue = True
			except:
				pr(border, "Something went wrong!!")
				_continue = False
			if _continue:
				_MSG = MSG[4:-4]
				_h = bytes_to_long(sha1(_MSG).digest())
				if pow(sgn, e, n) == _h:
					die(border, "Congrats! your got the flag: " + flag)
				else: 
					pr(border, "Sorry, your signature is not correct!")
		elif ans == 'q': die("Quitting ...")
		else: die("Bye bye ...")

if __name__ == "__main__": main()
```

### ☆方針・解法
　競技終了が近かったので、思考回路がgdgdで以下のようにしか考えられませんでした。

　やるべきこと：pow(sgn, e, n) == _h となる sgn を答える
　できること：e, n（,d） を別の E. N (,D) にすげ替える（ただし、D = inverse(E,phi(N)としたとき、pow(h, D, N) == SIGNを満たさなければならない）
　どうすればよいか： sign = pow(_h, D, N) を送ればよい。ただし、D, N は pow(h, D, N) == SIGN を満たさなければいけない。
　⇒ smooth な P, Q で N を構成し、D = discrete_log(SIGH, h) を探索します。mod.P（mod.Q）でこの DLP が解をもつとは限らないので、解を持つようなもので、なおかつ E = inverse(D, phi(N))が計算できるようなものを選定しなければならない。
　⇒ smooth な P, Q で、D に関する DLP が解けて E が計算できるようなものをガチャ
　
　・・・とこんな具合に考えて作ったのが以下のソルバです。

　☆ソルバ（競技でつかったものほぼそのままですので、超汚いです）
```python:solve.sage
from Crypto.Util.number import *
import telnetlib
from hashlib import sha1
from random import randint
import sys

HOST = <省略>
PORT = <省略>

def readline():
    return tn.read_until(b"\n")

def readuntil(stopper):
    return tn.read_until(stopper.encode())

def sendline(to_send):
    tn.write(to_send.encode() + b"\n")

S = 20 #20はテキトー
def getSmoothPrime():
  base = 1
  for i in range(1024 // S):
     base *= getPrime(S)
  #L = 1024 - int(base).bit_length()
  L = 1024 -  base.nbits()
  print(L)
  while(True):
    #x = int(base * randint(2**(L-1),2**L) + 1)
    x = 2*getPrime(L-1)*base + 1
    #print(x.nbits())
    #if isPrime(x) and x.bit_length() == 1024:
    if isPrime(x) and x.nbits() == 1024:
      return x

smoothprimes = []
for i in range(30):#30はテキトー
  smoothprimes.append(getSmoothPrime())

print("start:")
tn = telnetlib.Telnet(HOST, PORT)


for i in range(10):
  readline()

MSG = b'::. Can you forge any signature? .::'
h = bytes_to_long(sha1(MSG).digest())

sendline("P")
SIGN = int(readline().decode().replace("| SIGN = ",""))
print(f"SIGN={SIGN}")

cands=[]
ok = False

i = 0
while(True):
  try:
    p = smoothprimes[i]
    i += 1
    Fp = GF(p)
    hp = Fp(h)
    SIGNp = Fp(SIGN)
    dp = discrete_log(SIGNp, hp)
    cand = (int(p), int(dp))
    print(cand)
    if not cand in cands:
      for _cand in cands:
        try:
          P = cand[0]
          Q = _cand[0]
          D = int(crt([cand[1],_cand[1]],[P-1, Q-1]))
          PHI = (P-1)*(Q-1)
          E = inverse(D, PHI)
          N = P * Q
          if (E*D - 1) % PHI != 0:
            print("bad E and D")
            print(GCD(E, PHI), GCD(D, PHI))
          elif pow(int(h), D, int(N)) != SIGN % N:
            print("bad D")
          else:
            ok = True
            break
        except Exception as ex:
          print(ex)
          pass
      cands.append(cand)
  except Exception as ex:
    print(ex)
    continue
  if ok:
    break
  if i >= 30: #30はテキトー
    exit()

print(f"P={P}")
print(f"Q={Q}")
print(f"E={E}")
print(f"D={D}")
print(f"N={N}")

for i in range(6):
  readline()

#print(readline())
sendline("G")
print(readline())
to_send = str(E) + ", " + str(P) + ", " + str(Q)
sendline(to_send)
print(readline())

for i in range(6):
  readline()

sendline("S")
print(readline())
print(readline())
_MSG = MSG[4:-4]
_h = bytes_to_long(sha1(_MSG).digest())
sgn = pow(_h, D, N)
to_send = str(sgn)
sendline(to_send)
print(readline())
print(readline())


```

### ☆フラグ
**CCTF{Unkn0wN_K3y_5h4rE_4t7aCk_0n_Th3_RSA!}**

※おそらくもっとスマートに解けるはずです。。。

## 2-16. Sparse (難易度：medium-hard, 114 points, 38 solves)
### ☆設問
　RSA 問です。以下の通りスクリプト等が提示されます。

```sparse.py
#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def sparse(p, k):
	nbit = p.bit_length()
	while True:
		CF = [getRandomRange(-1, 1) for _ in '_' * k]
		XP = [getRandomRange(3, nbit - 3) for _ in '_' * k]
		A = sum([CF[_] * 2 ** XP[_] for _ in range(0, k)])
		q = p + A
		if isPrime(q) * A != 0:
			return q

p = getPrime(417)
q = sparse(p, 5)
e, n = 65537, p * q
print(f'n = {n}')
m = bytes_to_long(flag.encode('utf-8'))
assert m < n
c = pow(m, e, n)
print(f'c = {c}')
```

```output.txt
n = 94144887513744538681657844856583985690903055376400570170371837200724227314957348031684706936655253125445176582486308241015430205703156336248578475428712275706238423997982248462635972817633320331030484841129628650918661036694615254018290264619628335177
c = 80250313885079761377138486357617323555591919111371649902793873860183455237161293320577683249054725852540874552433031133240624696119120378419135912301004715004977978507247634217071922495893934816945961054193052791946557226599493364850793396744903765857
```

### ☆方針・解法
　p, q の構成法に問題があり、p に対し、q = p - d, d = (1～5個の2冪の和)という形で作っています。
　つまり、d を全探索し、X^2 - X*d - n = 0 が素数の解を持った時それが p の候補となります。
　実際、d は 2**284 でしたが、もし d が 5 個の 2 ベキの和だと計算時間的に苦しく、う～んと思った問題でした。

### ☆ソルバ（例によって汚いです）

```solve.py
import itertools
import gmpy2
from Crypto.Util.number import *

n = 94144887513744538681657844856583985690903055376400570170371837200724227314957348031684706936655253125445176582486308241015430205703156336248578475428712275706238423997982248462635972817633320331030484841129628650918661036694615254018290264619628335177
c = 80250313885079761377138486357617323555591919111371649902793873860183455237161293320577683249054725852540874552433031133240624696119120378419135912301004715004977978507247634217071922495893934816945961054193052791946557226599493364850793396744903765857
e = 65537

def check(d):
  if gmpy2.iroot(d**2 + 4*n,2)[1] != True:
    return False
  D = gmpy2.iroot(d**2 + 4*n,2)[0]
  if GCD((d + D) // 2, n) != 1:
    p = (d + D) // 2
    q = n // p
    print(p, q)
    phi = (p-1)*(q-1)//GCD(p,q)
    d = inverse(e, phi)
    print(long_to_bytes(pow(c,d,n)))
    return True
  else:
    return False

table = []
for i in range(3, 414):
  table.append(2**i)

for i in [1,5]:
  print(i)
  for X in itertools.combinations(table, i):
    d = 0
    for x in X:
      d += x
    if check(d):
      exit()
```

### ☆フラグ
**CCTF{5pArs3_dIfFeRenc3_f4ct0r1za7iOn_m3th0d!}**


## 2-17. Lagima (難易度：medium-hard, 164 points, xx solves)
### ☆設問
　以下のスクリプト等が提示されます。
　対称群における DLP のような問題です。

```python:lagima.sage
#!/usr/bin/env sage

from flag import flag

def genperm(n):
	_ = list(range(1, n + 1))
	shuffle(_)
	return _

def genlatrow(n):
	A = []
	for _ in range(n): A.append(genperm(n))
	return A

def prodlat(A, B):
	assert len(A) == len(B)
	C, G = [], SymmetricGroup(len(A))
	for _ in range(len(A)):
		g = (G(A[_]) * G(B[_])).tuple()
		C.append(list(g))
	return C

def powlat(A, n):
	assert n >= 0
	B = bin(n)[2:]
	c, R = len(B), [list(range(1, len(A) + 1)) for _ in range(len(A))]
	if n == 0: return R
	else:	
		for b in B:
			if b == '1':
				if c == 1: R = prodlat(R, A)
				else:
					T = A
					for _ in range(c - 1): T = prodlat(T, T)
					R = prodlat(R, T)
			c -= 1
	return R

G = genlatrow(313)
secret = int.from_bytes(flag.lstrip(b'CCTF{').rstrip(b'}'), 'big')
H = powlat(G, secret)

print(f'G = {G}')
print(f'H = {H}')
```

```output.txt
G = <313×313の配列、省略>
H = <313×313の配列、省略>
```

### ☆方針・解法
　数学的なウラをとらず、カンだけで解きました（競技なのでヨシ！）
　LCM(1,2,...,313)を考え、各素因数の冪の形で表します。Pohlig-Hellman法のような形で DLP を解きますが、order の倍数が出てきてしまいました。
　そこで、各 mod での解のうち 1 は怪しいので除外！のような形で CRT し直したところフラグゲットできました（極めてイイカゲンですけど競技なのでヨシ！）。
　問題の本質は違いますが、個人的には「Larisaのツラい版」という印象でした。

### ☆ソルバ（御多分に漏れず汚いです）
```python:solve.sage
#!/usr/bin/env sage
from Crypto.Util.number import *
import copy

G = <313×313の配列、省略>
H = <313×313の配列、省略>

def genperm(n):
  _ = list(range(1, n + 1))
  shuffle(_)
  return _

def genlatrow(n):
  A = []
  for _ in range(n): A.append(genperm(n))
  return A

def prodlat(A, B):
  assert len(A) == len(B)
  C, G = [], SymmetricGroup(len(A))
  for _ in range(len(A)):
    g = (G(A[_]) * G(B[_])).tuple()
    C.append(list(g))
  return C

def powlat(A, n):
  assert n >= 0
  B = bin(n)[2:]
  c, R = len(B), [list(range(1, len(A) + 1)) for _ in range(len(A))]
  if n == 0: return R
  else:  
    for b in B:
      if b == '1':
        if c == 1: R = prodlat(R, A)
        else:
          T = A
          for _ in range(c - 1): T = prodlat(T, T)
          R = prodlat(R, T)
      c -= 1
  return R

L = 313
od = 1
primes = []
for i in range(2, L+1):
  if isPrime(i):
     j = 1
     while(True):
       if i**(j+1) > L:
         break
       j+=1
     primes.append(i**j)
     od *= (i**j)

print(primes)

def powl2(A, facs, p):
  AA = copy.copy(A)
  for f in facs:
    if f != p:
      AA = powlat(AA, f)
  return AA

def dlog(B, X, p):
  BB = copy.copy(B)
  for i in range(1, p+1):
    if BB == X:
      return i
    BB = prodlat(BB, B) 
  return None

ms = []
ds = []
for i in range(len(primes)):
  p = primes[i]
  GG = powl2(G, primes, p)
  assert powlat(GG, p+1) == GG
  HH = powl2(H, primes, p)
  assert powlat(HH, p+1) == HH
  d = dlog(GG, HH, p)
  print(f"p:{p}")
  print(f"d:{d}")
  ms.append(p)
  ds.append(d)
print(ms)
print(ds)

_ms = []
_ds = []
for i in range(len(ms)):
  if ds[i] != 1:
    _ms.append(ms[i])
    _ds.append(ds[i])

d = crt(_ds, _ms)
print(d)
print(long_to_bytes(d))
```

### ☆フラグ
**CCTF{3lGam4L_eNcR!p710n_4nD_L4T!n_5QuarS3!}**


## 2-18. Larisa (難易度：medium-hard, 174 points, 22 solves)
### ☆設問
　以下のスクリプト等が提示されます。
　「Lagima」と同じく対称群が出てきますが若干毛色が違う問題です。

```python:larisa.sage
#!/usr/bin/env sage

from flag import flag

def genperm(n):
	_ = list(range(1, n + 1))
	shuffle(_)
	return _

def genlatrow(n):
	A = []
	for _ in range(n): A.append(genperm(n))
	return A

def prodlat(A, B):
	assert len(A) == len(B)
	C, G = [], SymmetricGroup(len(A))
	for _ in range(len(A)):
		g = (G(A[_]) * G(B[_])).tuple()
		C.append(list(g))
	return C

def powlat(A, n):
	assert n >= 0
	B = bin(n)[2:]
	c, R = len(B), [list(range(1, len(A) + 1)) for _ in range(len(A))]
	if n == 0: return R
	else:	
		for b in B:
			if b == '1':
				if c == 1: R = prodlat(R, A)
				else:
					T = A
					for _ in range(c - 1): T = prodlat(T, T)
					R = prodlat(R, T)
			c -= 1
	return R

def pad(msg, n):
	assert len(msg) <= n
	return msg + msg[-1] * (n - len(msg))

def embed(msg, n):
	assert len(msg) < n
	msg = pad(msg, n)
	while True:
		r, s = [randint(2, n) for _ in '__']
		if gcd(r, len(msg)) == 1:
			break
	A = []
	for _ in range(n):
		while True:
			R = genperm(n)
			if R[(_ * r + s) % n] == ord(msg[_]):
				A.append(R)
				break
	return A

def encrypt(A, e = 65537):
	return powlat(A, e)

l, e = 128, 65537
M = embed(flag, l)
C = encrypt(M, e)
print(C)
```

```enc.txt
<127×127の配列、省略>
```

### ☆方針・解法
　powlat(A, x) == powlat(A, 0) となる x (>0) を考えたとき、e*d = 1 mod x となる e, d について、
　powlat(powlat(A, e),d) == A となることに注意します。
　このことを用いて C を「decrypt」し、embed の逆操作をすればフラグをゲットできます。

### ☆ソルバ

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

C = <127×127の配列、省略>

def prodlat(A, B):
  assert len(A) == len(B)
  C, G = [], SymmetricGroup(len(A))
  for _ in range(len(A)):
    g = (G(A[_]) * G(B[_])).tuple()
    C.append(list(g))
  return C

def powlat(A, n):
  assert n >= 0
  B = bin(n)[2:]
  c, R = len(B), [list(range(1, len(A) + 1)) for _ in range(len(A))]
  if n == 0: return R
  else:  
    for b in B:
      if b == '1':
        if c == 1: R = prodlat(R, A)
        else:
          T = A
          for _ in range(c - 1): T = prodlat(T, T)
          R = prodlat(R, T)
      c -= 1
  return R

def readflag(A, n):
  for r in range(2, n):
    for s in range(2, n):
      flag = b""
      for i in range(n):
        flag += (A[i][(i * r + s) % n]).to_bytes(1 , "big")
      if b"CCTF" in flag:
        return flag
  return None

def encrypt(A, e = 65537):
  return powlat(A, e)

l, e = 128, 65537
od = 1
for i in range(2, l+1):
  if isPrime(i):
     j = 1
     while(True):
       if i**(j+1) > l:
         break
       j+=1
     od *= (i ** j)

d = inverse(e, od)
P = encrypt(C, d)
assert encrypt(P,e) == C
print(readflag(P, l))
```

### ☆フラグ
**CCTF{pUbliC_k3y_crypt0graphY_u5in9_rOw-l4t!N_5quAr3S!}**

# 3. おわりに
　途中細かい休憩や食事は挟みましたが、ほぼ 24 時間稼働していたので疲れました。
　この週末の気力体力を全振りしてしまったため、謎解き CTF はそもそも登録しそびれ、Imaginary CTF はほぼ手つかずとなってしまいました。
　来年も元気ならばソロ参加してさらに上（順位的にというよりは、solveの数と質の向上）を目指したいと思います。
　ジーク、ジオン！

[^1]: 平文は Base64 エンコード前で 36 バイトなので、これくらいの guess は許容されるでしょう。
[^2]: 第二次世界大戦で米軍が使用した暗号機。
[^3]: 原則、そうあるべきだと思っています（個人の感想です）。
[^4]: https://maxima.hatenablog.jp/entry/2020/06/15/232154 
[^5]: Menezes, A. J., Wu, Y.: The Discrete Logarithm Problem in GL(n, q), Ars Combinatioria, 47, 23-32