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!
ファイル
# !/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!
ファイル
(302639514920034304189440358447239768437615153204806889944888464316367823604888881880676558417
2011019394208155454727217629079121396251370188483785682320943220936795167330162253594039529582
6053396595886942990258678430777333636450042181585837395671842878310404080487115827773100028876
7752301215095702273033746725240631657145099578509661896054694842010287043630523178302549201086
6491613902674133155212784905689753496088664738242920226984639280964132261334154802576020928061
1758326300214885296175538901366986310471066687700879304860668964595202268317011117634615297226
602309205086105573924029744405559823548638486054634428L,
1680116646510905298495679670221947913670069215260364000147247049360000261700229830268183221594
2994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287
3938119344577891032090908734724858653284141545743922746115746548194958941379178003045801194523
9031844060182727383452278369647225772732981995236309949844600626611501127197814314934776507321
1516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618
0665688546732609789689789744098022115380116382139767322861503119713548613001954402865822557694
21094876667270445809991401456443444265323573485901383L,
6039738711082505929,
1399175759713215657404059324206254573100362710793380038867843241825147417774539416752832552455
2592875014173967690166427876430087295180152485599151947856471802414472083299904768768434074446
5658807730292150571319084956271231037799321288077978691644096621468216266282006006789662233823
5475228090165721335714666805652523444674795964222095429423001809461246973805194202646376717262
5588865125393400027831917763819584423585903587577154729283694206436985549513217882666427997109
5496868252359589094286052472219983660060184100263924460647207474242874007289612834719322798240
49509228058334419865822774654587977497006575152095818L)
# !/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. おわりに
サイバー空間で暮らせるようになった我々は、人の革新の道を歩んでいるニュータイプである。
（そうありたいと思う今日この頃であります…）