2nd Crypto CTF Writeup Part1

#1. はじめに
2020/8/15 00:00(JST) - 8/15 24:00(JST)で「2nd Crypto CTF」にソロ参加しました。
Welcomeを含め $6$ 問解答して$426$ 点を獲得、スコアボートに載った $552$ チーム中の $43$ 位でした。昨年はWelcome以外はダンゴ（ゼロ）でしたので、上首尾であったと言えるでしょう。
とは言いながらも、問題データを準備しながらも着手できなかったものも多数あったので、他の方のWriteupを参考に復習をしたいと思います。
今回は、時間内に自力で解けたものについてWriteupします。なお、毎度のことですが、非効率な解法や汚いSolverを含みます。この点はご容赦ください。
#2. Writeup
##2-1. Welcome (Warm-up)
###問題文
>Welcome to 2nd CryptoCTF. Let's enjoy the beauty of Cryptography with a sweet flag:
>
>CCTF{Crypt0Graphy_is_C00l_lets_s33_its_beauty}

###解法
　そのまま入力（コピペ）するだけです。なお、他の問題もそうですが、テキストボックスにはグレー文字で「Answer　ASIS{\_\_some_l33t_string l1k3_7hi5\_\_}」とありますが無視します（ASISではなくCCTFです）。

###flag
>**CCTF{Crypt0Graphy_is_C00l_lets_s33_its_beauty}**

##2-2. Trailing Bits (Baby)
###問題文
>The text that includes the flag is transmitted while unfortunately both of its head and tail bits are lost 😟

###配布ファイル（解凍後）
```output.txt
01001000000110001001100001011100110110100101100011001000000111010101101110011010010111010000100000011011110110011000100000011010010110111001100110011011110111001001101101011000010111010001101001011011110110111000100000011010010110111000100000011000110110111101101101011100000111010101110100011010010110111001100111001000000110000101101110011001000010000001100100011010010110011101101001011101000110000101101100001000000110001101101111011011010110110101110101011011100110100101100011011000010111010001101001011011110110111001110011001011100010000001010100011010000110010100100000011011100110000101101101011001010010000001101001011100110010000001100001001000000111000001101111011100100111010001101101011000010110111001110100011001010110000101110101001000000110111101100110001000000110001001101001011011100110000101110010011110010010000001100100011010010110011101101001011101000010111001011011001100010101110100100000010101000110100001100101001000000110001001101001011101000010000001110010011001010111000001110010011001010111001101100101011011100111010001110011001000000110000100100000011011000110111101100111011010010110001101100001011011000010000001110011011101000110000101110100011001010010000001110111011010010111010001101000001000000110111101101110011001010010000001101111011001100010000001110100011101110110111100100000011100000110111101110011011100110110100101100010011011000110010100100000011101100110000101101100011101010110010101110011001011100010000001010100011010000110010101110011011001010010000001110110011000010110110001110101011001010111001100100000011000010111001001100101001000000110110101101111011100110111010000100000011000110110111101101101011011010110111101101110011011000111100100100000011100100110010101110000011100100110010101110011011001010110111001110100011001010110010000100000011000010111001100100000011001010110100101110100011010000110010101110010001000000011000001101111011100100011000100101100001000000110001001110101011101000010000001101111011101000110100001100101011100100010000001110010011001010111000001110010011001010111001101100101011011100111010001100001011101000110100101101111011011100111001100100000011100110111010101100011011010000010000001100001011100110010000001110100011100100111010101100101001011110110011001100001011011000111001101100101001011000010000001111001011001010111001100101111011011100110111100101100001000000010101100101111111000101000100010010010001011000010000001101111011100100010000001101111011011100010111101101111011001100110011000100000011000010111001001100101001000000110001101101111011011010110110101101111011011100010111000001010010101000110100001100101001000000110011001101100011000010110011100100000011010010111001100100000010000110100001101010100010001100111101101101001011101000011010101011111001100110110111000110000011101010011100101101000010111110110101001010101001101010101010001011111011101000100111101011111011100110100100000110001011001100111010001011111010011010011001101111101000010100101010001101000011001010010000001100011011011110111001001110010011001010111001101110000011011110110111001100100011001010110111001100011011001010010000001100010011001010111010001110111011001010110010101101110001000000111010001101000011001010111001101100101001000000111011001100001011011000111010101100101011100110010000001100001011011100110010000100000011101000110100001100101001000000111000001101000011110010111001101101001011000110110000101101100001000000111001101110100011000010111010001100101011100110010000001101111011001100010000001110100011010000110010100100000011101010110111001100100011001010111001001101100011110010110100101101110011001110010000001110011011101000110111101110010011000010110011101100101001000000110111101110010001000000110010001100101011101100110100101100011011001010010000001101001011100110010000001100001001000000110110101100001011101000111010001100101011100100010000001101111011001100010000001100011011011110110111001110110011001010110111001110100011010010110111101101110001011000010000001100001011011100110010000100000011001000110100101100110011001100110010101110010011001010110111001110100001000000110000101110011011100110110100101100111011011100110110101100101011011100111010001110011001000000110110101100001011110010010000001100010011001010010000001110101011100110110010101100100001000000110010101110110011001010110111000100000011101110110100101110100011010000110100101101110001000000111010001101000011001010010000001110011011000010110110101100101001000000110010001100101011101100110100101100011011001010010000001101111011100100010000001110000011100100110111101100111011100100110000101101101001011100010000001001001011101000010000001101101011000010111100100100000011000100110010100100000011100000110100001111001011100110110100101100011011000010110110001101100011110010010000001101001011011010111000001101100011001010110110101100101011011100111010001100101011001000010000001110111011010010111010001101000001000000110000100100000011101000111011101101111001011010111001101110100011000
```

###解法
baby問題なので、フラグそのものは欠損していないと予想しました。ですので、先頭bitの欠損は無視して、末尾の欠損 $n$bit に対し $(-n \mod{8})$bit を適当に補って文字列に変換すればフラグ部分を回復できるはずです。そこで、末尾に $0$ を $0$ ~ $7$bit 分補って文字列への変換結果を確認する、という方針で以下のsolverを作りました、

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

with open("output.txt") as f:
  a = f.read().strip("\n")
  for i in range(8):
    x = "0b" +  a + "0" * i
    dec = long_to_bytes(int(x, 2))
    if(dec.find(b"CCTF") > 0):
      start = dec.find(b"CCTF")
      end = dec.find(b"}")
      print(dec[start:end+1].decode())
      break
```

###flag
>**CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}**

##2-3. Amsterdam (Easy)
###問題文
>Is it normal to have such encoding?

###配布ファイル（解凍後）
```amsterdam.py
#!/usr/bin/env python3

from Crypto.Util.number import *
from functools import reduce
import operator
from secret import flag, n, k

def comb(n, k):
	if k > n :
		return 0
	k = min(k, n - k)
	u = reduce(operator.mul, range(n, n - k, -1), 1)
	d = reduce(operator.mul, range(1, k + 1), 1)
	return u // d 

def encrypt(msg, n, k):
	msg = bytes_to_long(msg.encode('utf-8'))
	if msg >= comb(n, k):
		return -1
	m = ['1'] + ['0' for i in range(n - 1)]
	for i in range(1, n + 1):
		if msg >= comb(n - i, k):
			m[i-1]= '1'
			msg -= comb(n - i, k)
			k -= 1
	m = int(''.join(m), 2)
	i, z = 0, [0 for i in range(n - 1)]
	c = 0
	while (m > 0):
		if m % 4 == 1:
			c += 3 ** i 
			m -= 1
		elif m % 4 == 3:
			c += 2 * 3 ** i
			m += 1
		m //= 2
		i += 1
	return c

enc = encrypt(flag, n, k)
print('enc =', enc)
```

```output.txt
enc = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493
```

###解法
　最後に解いた問題で、愚直に順を追ってdecryptします。具体的には、STEP1: 暗号文を $3$ 進展開、STEP2: $m$を求める、STEP3: $K$を総当たりでencryptの逆演算、という $3$ステップで解きました。ヘロヘロになりながらやったのでsolverはグチャグチャです((+_+))。

```solve.py
from Crypto.Util.number import *
from functools import reduce
import operator
import math

def comb(n, k):
  if k > n :
    return 0
  k = min(k, n - k)
  u = reduce(operator.mul, range(n, n - k, -1), 1)
  d = reduce(operator.mul, range(1, k + 1), 1)
  return u // d 

with open("output.txt","r") as f:
  exec(f.read())

#STEP1
ceil = (int)(math.log(enc,3))
ts = []
target = enc
for i in range(ceil + 1):
  ts.append(target % 3)
  target = target // 3

#STEP2
m = 1
cnt = 1
for rt in reversed(ts):
  if(cnt >= 3):
    m = m * 2
  if(rt == 2):
    m = m - 1
  elif(rt == 1):
    m = m + 1
  cnt = cnt + 1

#STEP3
mm = bin(m)[2:]
N = len(mm)
for k in range(0, N//2):
  msg = 0
  i = N
  K = k
  for b in reversed(mm):
    if(int(b) == 1 and i != 1):
      msg += comb(N - i, K)
      K += 1
    i -= 1
  dec = long_to_bytes(msg)
  if(dec.find(b"CCTF{")>0):
    print(dec[dec.find(b"CCTF{"):dec.find(b"}")+1].decode())
    break
```

###flag
>**CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}**

##2-4. Three Ravens (Midium)
###問題文
>There were three ravens sat on a tree, Downe a downe, hay downe, a downe, They were as black as they might be.

###配布ファイル（解凍後）
```three_ravens.py
#!/usr/bin/python

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

def keygen(nbit):
	while True:
		p, q, r = [getPrime(nbit) for _ in range(3)]
		if isPrime(p + q + r):
			pubkey = (p * q * r, p + q + r)
			privkey = (p, q, r)
			return pubkey, privkey

def encrypt(msg, pubkey):
	enc = pow(bytes_to_long(msg.encode('utf-8')), 0x10001, pubkey[0] * pubkey[1])
	return enc

nbit = 512
pubkey, _ = keygen(nbit)
print('pubkey =', pubkey)

enc = encrypt(flag, pubkey)
print('enc =', enc)
```

```output.txt
pubkey = (1118073551150541760383506765868334289095849217207383428775992128374826037924363098550311115755885268424829560194236035782255428423619054826556807583363177501160213010458887123857150164238253637312857212126083296001975671629067724687807682085295986049189947830021121209617616433866087257702543240938795900959368763108186758449391390546819577861156371516299606594152091361928029030465815445679749601118940372981318726596366101388122993777320367839724909505255914071, 31678428119854378475039974072165136708037257624045332601158556362844808093636775192373992510841508137996049429030654845564354209680913299308777477807442821)
enc = 8218052282226011897229703907763521214054254785275511886476861328067117492183790700782505297513098158712472588720489709882417825444704582655690684754154241671286925464578318013917918101067812646322286246947457171618728341255012035871158497984838460855373774074443992317662217415756100649174050915168424995132578902663081333332801110559150194633626102240977726402690504746072115659275869737559251377608054255462124427296423897051386235407536790844019875359350402011464166599355173568372087784974017638074052120442860329810932290582796092736141970287892079554841717950791910180281001178448060567492540466675577782909214
```

###解法
鍵は $512$bit の素数 $p$、$q$、$r$ をもとに生成され、基本対称式のうちの $2$ つである $p+q+r(:=s)$ と $p*q*r(:=t)$ が public key、素数そのものは（当然）private keyとなります。
暗号化は、$e=65537$、$n = st$ を用いて $C=M^e \mod{n}$で行われています。
しかし基本対称式のうち $p*q+q*r+r*p$ が欠けているので、$p$、$q$、$r$はもちろん、totientもすんなりと計算できません。ここで、$s$ が素数であることを思い出して、とりあえず $e$ の $\mod{s-1}$ での逆元 
$d_s$ を計算し、$C^{d_s} \mod{s}$ を計算したらフラグが出てきてしまいました。

```solve.py
from Crypto.Util.number import *
with open("output.txt","r") as f:
  exec(f.read())

s = pubkey[1]
e = 65537
d = inverse(e,s-1)
print(long_to_bytes(pow(enc,d,s)).decode())
```

###flag
>**CCTF{tH3_thr3E_r4V3n5_ThRe3_cR0w5}**

##2-5. Gambler (Hard)
###問題文
>Gamble as an ancient Philossepher!
>
>nc 05.cr.yp.toc.tf 33371

###解法
サーバに接続するタイプの問題で、最初に proof of work を求められます。pwntool などを使って自動化させればカッコよかったのかもしれませんが、以下のプログラムでお茶を濁しました。

```pow.py
import hashlib

def proof_of_work(leng, req, method):
  h = ""
  for _ in range(leng):
    h = h + "0"
  i = 0
  while(1):
    c = str(i)
    s = (h + c)[len(c):]
    n = method(s.encode()).hexdigest()[-6:]
    if(n == req):
      print(s)
      exit()
    i = i + 1

leng = int(input("length: "))
req = input("req(6 chars): ")
hash = int(input("hash 1:md5 2:sha1 3:sha224 4:sha256 5:sha384 6:sha512 :"))
if(hash == 1):
  proof_of_work(leng,req, hashlib.md5)
elif(hash == 2):
  proof_of_work(leng,req, hashlib.sha1)
elif(hash == 3):
  proof_of_work(leng,req, hashlib.sha224)
elif(hash == 4):
  proof_of_work(leng,req, hashlib.sha256)
elif(hash == 5):
  proof_of_work(leng,req, hashlib.sha384)
elif(hash == 6):
  proof_of_work(leng,req, hashlib.sha512)
```

実際、サーバに接続すると、

``` 
Please submit a printable string X, such that sha512(X)[-6:] = 26af9a and len(X) = 23
```
と proof of work を要求されたため、前出のプログラムを使用して計算をした結果を入力しました。

``` 
00000000000000000973086
```

以下、少し長くなるので、サーバでの操作内容を示します。

``` 
C
| encrypt(bytes_to_long(flag)) = 9929819211362905540059227900676589179447869982721184577273147774128295999115132813799806306519817941910069734918334969082941550690395647828502581257340668
| Options: 
|	[C]ipher flag! 
|	[E]ncryption function! 
|	[T]ry the encryption 
|	[Q]uit
E
def encrypt(m, p, a, b):
    assert m < p and isPrime(p)
    return (m ** 3 + a * m + b) % p

| Options: 
|	[C]ipher flag! 
|	[E]ncryption function! 
|	[T]ry the encryption 
|	[Q]uit
T
| please enter your message to encrypt:
1
| encrypt(1) = 813935620994157277924133945446358601248857738240434980648988927602135785676583953135632526887462928444266072686574156208973068467696303325000666671662167
| Options: 
|	[C]ipher flag! 
|	[E]ncryption function! 
|	[T]ry the encryption 
|	[Q]uit
T
| please enter your message to encrypt:
0
| encrypt(0) = 9473552622807453293098587870153009239205808345459548230756422944531147351056719218022921400433529554308315322836856781828132400887706084640122240078876012
| Options: 
|	[C]ipher flag! 
|	[E]ncryption function! 
|	[T]ry the encryption 
|	[Q]uit
T
| please enter your message to encrypt:
-1
| encrypt(-1) = 7487832703402899790593968733357164103506701010839038150806547349958821903445673707888244524067482600032290738034021524374638580742217144255749249109215514
| Options: 
|	[C]ipher flag! 
|	[E]ncryption function! 
|	[T]ry the encryption 
|	[Q]uit
```

具体的には、暗号文と暗号化関数を表示した後、暗号化関数で使われているパラメータを計算するために必要な値を収集しています。
さてこの後ですが、STEP1: $a$、$b$、$p$を計算、STEP2: sageでxを計算、STEP3: xを選ぶ（検証）という順で進めました。 

■STEP1

```solve1.py
import sympy
def F(x):
  return(x**3 + a*x + b)

enc= 9929819211362905540059227900676589179447869982721184577273147774128295999115132813799806306519817941910069734918334969082941550690395647828502581257340668
b = 9473552622807453293098587870153009239205808345459548230756422944531147351056719218022921400433529554308315322836856781828132400887706084640122240078876012
a = 813935620994157277924133945446358601248857738240434980648988927602135785676583953135632526887462928444266072686574156208973068467696303325000666671662167 - b - 1
ff = 7487832703402899790593968733357164103506701010839038150806547349958821903445673707888244524067482600032290738034021524374638580742217144255749249109215514

assert(sympy.isprime(F(-1) - ff))
p = F(-1) - ff
print("p = ", p)
```

>p =  10645336921217849517679073061502495773656057941839623330057309611501337012991180775021965749912113580140073834953117883072653152565498721699494564376874343

■STEP2
$a$、$b$、$p$ が計算できたので、sageを使って $x^3+ax+b=E$ を $\mod{p}$ で解きます。

``` sage
sage: p = 1064533692121784951767907306150249577365605794183962333005730
....: 96115013370129911807750219657499121135801400738349531178830726531
....: 52565498721699494564376874343
....: P.<x> = PolynomialRing(GF(p))
....: b = 9473552622807453293098587870153009239205808345459548230756422
....: 94453114735105671921802292140043352955430831532283685678182813240
....: 0887706084640122240078876012
....: a = 8139356209941572779241339454463586012488577382404349806489889
....: 27602135785676583953135632526887462928444266072686574156208973068
....: 467696303325000666671662167 - b - 1
....: enc = 99298192113629055400592279006765891794478699827211845772731
....: 47774128295999115132813799806306519817941910069734918334969082941
....: 550690395647828502581257340668
....: f = x ** 3 + a*x + b - enc
....: f.factor()
```
>(x + 8636242476960426882278390600335384714227149135436685906735457243392273732773494045151018116113171140766258637659647093024819102) * (x + 97817126735218068294512340014689591302517138811885177836768501174025411348533231764828759074853281814461806831227227371905109574) * (x + 10645336921230615024957736560579412225528974080495608592389863981873732736250819742279859166870564791789600169571211466382382001

■STEP3
$x$ がflagの候補です。（負の値で出るので、%pの計算で正の値に調整してから）バイト列に変換し、b"CCTF"を含むものからフラグを得ます。

```solve2.py
from Crypto.Util.number import *

p = 10645336921217849517679073061502495773656057941839623330057309611501337012991180775021965749912113580140073834953117883072653152565498721699494564376874343
candidates = [-863624247696042688227839060033538471422714913543668591318450810365067354572433922737327734940451510181161131711407662586376572773188916459647093024819102%p, -9781712673521806829451234001468957302233343028913025171388118851778367685011740254113485332317648287590789115396236434853281814461806831227227371905109574%p, -10645336921217849517679073061502495773656057941222552897408049560859238986398187373193118432566127362508197422798591668705647917896001695712114663823820010%p]

for c in candidates:
  if(long_to_bytes(c)[0:4]==b"CCTF"):
    print(long_to_bytes(c).decode())
```

###flag
>**CCTF{__Gerolamo__Cardano_4N_itaLi4N_p0lYma7H}**

##2-6. One Line Crypto (Hard)
###問題
>A profile, a look, a voice, can capture a heart ♥ in no time at all.

###配布ファイル（解凍後）
```one_line_crypto.py
#!/usr/bin/python

from Crypto.Util.number import *
from secret import m, n, x, y, flag

p, q = x**(m+1) - (x+1)**m, y**(n+1) - (y+1)**n
assert isPrime(p) and isPrime(q) and p < q < p << 3 and len(bin(p*q)[2:]) == 2048
enc = bytes_to_long(flag)
print(pow(enc, 0x10001, p*q))
```

```flag.enc
14608474132952352328897080717325464308438322623319847428447933943202421270837793998477083014291941466731019653023483491235062655934244065705032549531016125948268383108879698723118735440224501070612559381488973867339949208410120554358243554988690125725017934324313420395669218392736333195595568629468510362825066512708008360268113724800748727389663826686526781051838485024304995256341660882888351454147057956887890382690983135114799585596506505555357140161761871724188274546128208872045878153092716215744912986603891814964771125466939491888724521626291403272010814738087901173244711311698792435222513388474103420001421
```

###解法
$x$ と $m$ の範囲を適当に定め、$p$、$q$ の候補を列挙します。次に、候補の中から条件（$p<q<8p$ かつ $pq$ は $2048$bit）を満たすものを探し、それを秘密鍵と仮定してdecryptします。

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

enc = 14608474132952352328897080717325464308438322623319847428447933943202421270837793998477083014291941466731019653023483491235062655934244065705032549531016125948268383108879698723118735440224501070612559381488973867339949208410120554358243554988690125725017934324313420395669218392736333195595568629468510362825066512708008360268113724800748727389663826686526781051838485024304995256341660882888351454147057956887890382690983135114799585596506505555357140161761871724188274546128208872045878153092716215744912986603891814964771125466939491888724521626291403272010814738087901173244711311698792435222513388474103420001421
e = 0x10001
candidates = []

x_range = 2 ** 12
m_range = 2 ** 12

for x in range(x_range):
  for m in range(m_range):
    c = x ** (m+1) - (x+1) ** m
    if(sympy.isprime(c) and c.bit_length() >= 1022 and c.bit_length() <= 1026):
      candidates.append(c)
    if(c.bit_length() > 1026):
      break

for a,b in itertools.combinations(candidates,2):
  if(a > b):
    p = b
    q = a
  else:
    p = a
    q = b
  n = p * q
  if(n.bit_length() == 2048 and q // p < 8):
    print("p=",p)
    print("q=",q)
    phi = (p-1) * (q-1)
    d = inverse(e,phi)
    print("d=",d)
    print(long_to_bytes(pow(enc,d,n)).decode())
```

###flag
>**CCTF{0N3_1!nE_CrYp7O_iN_202O}**

#3. おわりに
正直、体力をだいぶ持っていかれました。知識経験の積み重ねとともに体力UPして、来年は一桁を狙いたいです。