1. はじめに

我々は一晩で人権を失った！
しかし、これは敗北を意味するのか！？
否！始まりなのだ！

2019/8/10 15:00(JST) - 8/11 15:00(JST)で「Crypto CTF」にソロ参加しました。
・・・が、どうにか１問解答しようとしたところで時間切れ！やっちまいました。人権喪失。
気を取り直して、事後に解けたもの２問について供養します。

2. Write up(s)

2-1. Alone in the dark

問題文

We are alone in the dark with a single line!

ファイル

alone_in_the_dark.py

# !/usr/bin/env python

import gmpy2
from hashlib import sha256
from secret import u, v, x, y

assert ((u+1)**2 + u**2 - v**2)**2 + ((x+1)**3 - x**3 - y**2)**4 + (gmpy2.is_prime(v) + 1)**6 
+ (gmpy2.is_prime(y) - 1)**8 + (len(bin(u)[2:]) - 664)**10 + (len(bin(x)[2:]) - 600)**12 ==  664 - 600

flag = 'CCTF{' + sha256(str(u) + str(v) + str(x) + str(y)).hexdigest() + '}'

解法

初等整数論の知識＋αで解決しました。
まずは、assertの内容を吟味します。

A**2+B**4+C**6+D**8+E**10+F**12 == 64

の形ですが、

「A, B, D, E, F が全て 0」かつ「C が 2」

の場合は True です。つまり、

A) (u+1)**2 + u**2 - v**2 が 0、つまり (u+1)**2 + u**2 = v**2
B) (x+1)**3 - x**3 - y**2 が 0、つまり 3*x**2 + 3*X + 1 = y**2
C) gmpy2.is_prime(v) + 1 が 2、つまり v が素数（正確には、is_primeで素数と判定される）
D) gmpy2.is_prime(y) - 1 が 0、つまり y が素数（正確には、is_primeで素数と判定される）
E) (len(bin(u)[2:]) - 664) が 0、つまり len(bin(u)[2:]) が 664 となること
F) (len(bin(x)[2:]) - 600) が 0、つまり len(bin(x)[2:]) が 600 となること

以上A)～F)を満たす u, v, x, y が求められれば良いということです。

u, v について、条件A)については「隣り合ったピタゴラス数」を求める計算をすればよいのですが、

u = 2*m*n または m**2 - n**2
v = m**2 + n**2
m, n は以下の数列{a_n}の第k項と第k-1項： a_n = 2*a_(n-1) + a_(n-2), a_1=1, a_2=2

で求められることが知られています。これに v の素数条件C)とuのサイズ条件E)を加味したコードが以下となります。

import gmpy2

a = 1
n = 2
while(1):
    m = 2 * n + a
    v = m ** 2 + n ** 2
    u1 = 2 * m * n
    u2 = m ** 2 - n ** 2
    if(u1 > u2):
        u = u2
    else:
        u = u1
    if((len(bin(u)[2:]) - 664)==0 and gmpy2.is_prime(v)):
		print(u)
		print(v)
		break
	if(len(bin(u)[2:]) > 664):
		break
    a = n
    n = m

実行すると

u = 38870796548368940451592529482185869982938448205812640195914560739542103841403178847163517462769143179065031576973812014377488506777895445800461891869308645201761858965032907136032847098509289762520539
v = 54971607658948646301386783144964782698772613513307493180078896702918825851648683235325858118170150873214978343601463118106546653220435805362395962991295556488036606954237309847762149971207793263738989

を得ます。

x, y については、B)の条件を変形させると、Pell方程式

a**2 - 3 * b **2 = 1
ただし、a = 2*y、b = 2*x + 1

に変形できます。
上記 Pell 方程式の基本解は a_1=2, b_1=1 で、残りの解はすべて

a_n+b_n*sqrt(3) = (a_1+b_1*sqrt(3))**n

（式みづらくてスミマセン）から求められることが知られています。
これに、素数判定条件D)とサイズ条件F)を加味したコードが以下です。
（条件から、a が偶数かつ b が奇数の解のみ採用する点に注意）

import gmpy2
a1 = 2
b1 = 1
while(1):
	a = 2 * a1 + b1 * 3
	b = 2 * b1 + a1
	if(a % 2 == 0 and b % 2 == 1):
		y = a//2
		x = (b-1)//2
		if((len(bin(x)[2:]) - 600)==0 and gmpy2.is_prime(y)):
			print(x)
			print(y)
			break
		if(len(bin(x)[2:]) > 600):
			break
	a1 = a
	b1 = b

実行結果から以下を得ることができます。

x = 2929219721139577720733862051859801690342725739320715630102152440665051724895027651815801589822478988305846846083549661332897318938724576681923803796059612952236038798314710140134264
y = 5073557383546487137945410473466556718830129339025213837451156233563658135296353459994544781708539660966095175852902937975236171859961262538393568510313468641105066779787434237464141

あとは、判明した u, v, x, y を、提示されたプログラムにぶち込めば OK です。ただし Python3.x 環境だと若干の補正が必要でした（このせいでタイムアップしてしまった！）

import gmpy2
from hashlib import sha256

x = 2929219721139577720733862051859801690342725739320715630102152440665051724895027651815801589822478988305846846083549661332897318938724576681923803796059612952236038798314710140134264
y = 5073557383546487137945410473466556718830129339025213837451156233563658135296353459994544781708539660966095175852902937975236171859961262538393568510313468641105066779787434237464141
u = 38870796548368940451592529482185869982938448205812640195914560739542103841403178847163517462769143179065031576973812014377488506777895445800461891869308645201761858965032907136032847098509289762520539
v = 54971607658948646301386783144964782698772613513307493180078896702918825851648683235325858118170150873214978343601463118106546653220435805362395962991295556488036606954237309847762149971207793263738989

# verify
assert ((u+1)**2 + u**2 - v**2)**2 + ((x+1)**3 - x**3 - y**2)**4 + (gmpy2.is_prime(v) + 1)**6 + (gmpy2.is_prime(y) - 1)**8 + (len(bin(u)[2:]) - 664)**10 + (len(bin(x)[2:]) - 600)**12 == 664 - 600

c = 'utf-8'
flag = 'CCTF{' + sha256(str(u).encode(c) + str(v).encode(c) + str(x).encode(c) + str(y).encode(c)).hexdigest() + '}'
print(flag)

CCTF{07f594e5fb8f6d5f82e5cce06e2a2c74c1bffce370cd904821fdd71027faa084}

ギリギリまで残さないで最初にやっておけば時間内に解けていた…かも。

2-2. Time Capcule

問題文

You neither need 35 years nor even 20 years to solve this problem!

ファイル

time_capcule.txt

(302639514920034304189440358447239768437615153204806889944888464316367823604888881880676558417
2011019394208155454727217629079121396251370188483785682320943220936795167330162253594039529582
6053396595886942990258678430777333636450042181585837395671842878310404080487115827773100028876
7752301215095702273033746725240631657145099578509661896054694842010287043630523178302549201086
6491613902674133155212784905689753496088664738242920226984639280964132261334154802576020928061
1758326300214885296175538901366986310471066687700879304860668964595202268317011117634615297226
602309205086105573924029744405559823548638486054634428L, 
1680116646510905298495679670221947913670069215260364000147247049360000261700229830268183221594
2994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287
3938119344577891032090908734724858653284141545743922746115746548194958941379178003045801194523
9031844060182727383452278369647225772732981995236309949844600626611501127197814314934776507321
1516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618
0665688546732609789689789744098022115380116382139767322861503119713548613001954402865822557694
21094876667270445809991401456443444265323573485901383L, 
6039738711082505929, 
1399175759713215657404059324206254573100362710793380038867843241825147417774539416752832552455
2592875014173967690166427876430087295180152485599151947856471802414472083299904768768434074446
5658807730292150571319084956271231037799321288077978691644096621468216266282006006789662233823
5475228090165721335714666805652523444674795964222095429423001809461246973805194202646376717262
5588865125393400027831917763819584423585903587577154729283694206436985549513217882666427997109
5496868252359589094286052472219983660060184100263924460647207474242874007289612834719322798240
49509228058334419865822774654587977497006575152095818L)

time_capcule.py

# !/usr/bin/python

from Crypto.Util.number import *
from secret import flag, n, t, z



def encrypt_time_capsule(msg, n, t, z):
	m = bytes_to_long(msg)
	l = pow(2, pow(2, t), n)
	c = l ^ z ^ m
	return (c, n, t, z) 

print encrypt_time_capsule(flag, n, t, z)

解法

mを求めるにはc＾z＾lを計算すればよいのですが、lを上式の方法で求めると、問題文にある通り何年かかるか分かりません！
φ(n)（φはオイラー関数）が計算できれば、

l = pow(2, pow(2, t, φ(n)), n)

で「サクッと」出せますが、nの値が大きすぎてmsieveが食ってくれず、φ(n)がワカラン！
ここで諦めてしまいました。
終了後、IRCを覗いたら「factordb」を使うとできる旨が！
nの素因数が分かったので、ハードコードして以下の通りできました。

from crypto.Util.number import *
c = 3026395149200343041894403584472397684376151532048068899448884643163678236048888818806765584172
0110193942081554547272176290791213962513701884837856823209432209367951673301622535940395295826
0533965958869429902586784307773336364500421815858373956718428783104040804871158277731000288767
7523012150957022730337467252406316571450995785096618960546948420102870436305231783025492010866
4916139026741331552127849056897534960886647382429202269846392809641322613341548025760209280611
7583263002148852961755389013669863104710666877008793048606689645952022683170111176346152972266
02309205086105573924029744405559823548638486054634428
n = 1680116646510905298495679670221947913670069215260364000147247049360000261700229830268183221594
2994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287
3938119344577891032090908734724858653284141545743922746115746548194958941379178003045801194523
9031844060182727383452278369647225772732981995236309949844600626611501127197814314934776507321
1516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618
0665688546732609789689789744098022115380116382139767322861503119713548613001954402865822557694
21094876667270445809991401456443444265323573485901383
t = 6039738711082505929
z = 1399175759713215657404059324206254573100362710793380038867843241825147417774539416752832552455
2592875014173967690166427876430087295180152485599151947856471802414472083299904768768434074446
5658807730292150571319084956271231037799321288077978691644096621468216266282006006789662233823
5475228090165721335714666805652523444674795964222095429423001809461246973805194202646376717262
5588865125393400027831917763819584423585903587577154729283694206436985549513217882666427997109
5496868252359589094286052472219983660060184100263924460647207474242874007289612834719322798240
49509228058334419865822774654587977497006575152095818

# using http://factordb.com/ to get factors
factors = [15013, 583343756982313, 585503197547927, 609245815680559, 612567235432583, 634947980859229, 
635224892351513, 639438000563939, 654170414254271, 654269804672441, 667954470985657, 706144068530309, 
721443717105973, 737993471695639, 744872496387077, 746232585529679, 795581973851653, 815694637597057, 
817224718609627, 841183196554507, 864339847436159, 873021823131881, 884236929660113, 899583643974479, 
922745965897867, 942872831732189, 951697329369323, 971274523714349, 1017566110290559, 1018452110902339, 
1025985735184171, 1027313536626551, 1059774237802229, 1067609726096989, 1070689247726159, 1079289330417443, 
1098516592571807, 1107673252158281, 1108654254305327, 1110918654474373, 1111516996694389, 1112193819715441]

def decrypt_time_capsule(c, n, t, z, factors):
	en = 1
	for i in range (0 , len(factors)):
		en = en * (factors[i]-1)
	l = pow(2, pow(2, t, en), n)
	msg = long_to_bytes(l ^ z ^ c)
	return (msg) 

print(decrypt_time_capsule(c, n, t, z, factors))

コードが雑なのはご容赦ください。

CCTF{_Happy_Birthday_LCS}
素因数分解ツールの知識不足が悔やまれます。

3. おわりに

サイバー空間で暮らせるようになった我々は、人の革新の道を歩んでいるニュータイプである。

（そうありたいと思う今日この頃であります…）