1. はじめに
2019/10/12 11:00(JST) - 10/14 11:00(JST)で、HITCON CTF 2019 Qualsに参加しました。
CTFは、国籍・性別・職業・職位（階級）・年齢などの壁のない世界で、ただ自分らのもつスキル（とチームワーク）でのみ戦い、戦った後はラグビーでいう「ノーサイドの精神」でwrite upを通じ知識の共有を図る、理想的な競技であると常々思います。
結果ですが、いつもどおり一人親方（ソロチーム）として参戦、WelcomeのほかCrypto1問だけ解いて250点135位でした。
2. Write up
Lost Modulus Again(200pt)
問題文
It seems something wrong with my modulus.
ファイル
from Crypto.Util.number import *
class Key:
def __init__(self, bits):
assert bits >= 512
self.p = getPrime(bits)
self.q = getPrime(bits)
self.n = self.p * self.q
self.e = 0x100007
self.d = inverse(self.e, (self.p-1)*(self.q-1))
self.dmp1 = self.d%(self.p-1)
self.dmq1 = self.d%(self.q-1)
self.iqmp = inverse(self.q, self.p)
self.ipmq = inverse(self.p, self.q)
def encrypt(self, data):
num = bytes_to_long(data)
result = pow(num, self.e, self.n)
return long_to_bytes(result)
def decrypt(self, data):
num = bytes_to_long(data)
v1 = pow(num, self.dmp1, self.p)
v2 = pow(num, self.dmq1, self.q)
result = (v2*self.p*self.ipmq+v1*self.q*self.iqmp) % self.n
return long_to_bytes(result)
def __str__(self):
return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)
def main():
key = Key(1024)
flag = open('flag').read()
encrypt_flag = key.encrypt(flag)
assert key.decrypt(encrypt_flag) == flag
print key
print encrypt_flag.encode('hex')
if __name__ == '__main__':
main()
Key([e = 1048583, n = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927, x = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743, y = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331])
32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703
解法
【注意】以下、「エレガントな解答」ではありません。どう考え、どう正解に至ったのかを泥臭くトレースするものです。
この問題はRSAで、$e$ と $c$ と $d$ が与えられているが、$n$ が判らず、その代わりに $p_{q}:=p^{-1}\mod{q}$ と $q_{p}:=q^{-1}\mod{p}$ とが判明している、というものです。
方針は、
・（$de-1$の約数と各値のサイズから）$\phi(n)$ の候補を列挙
・$\phi(n)$と$p_{q}$と$q_{p}$ から $p$ と $q$ を求める
としました。
経過
まず、$ed-1 (=t\phi(n))$ を計算すると
21914950166680354199543721695339346739590116649826945866391891798390353698897362969835141374670696467477349950617657569543047368455616176779521034533938092969232006374010511300971579825295365578913858786918974175349878623678205201167442590771608135636383425592599099694105177896329050386741246197182300184443338268148756714457586242136122029693613268708479073937836452919867689590945093169810077031258698097334252554259525908834845971382079816628974465853427529757754118732983373565643240172900993025575817393659671257770949087612667099147456550480732819072975367473649332656318514410783426842080258478505498856033239889440
で、これをfactordbに投げると
2^5 * 3^5 * 5 * 13 * 31 * 47 * 331 * 449 * 1381 * 37693 * 2444137 * 7731502019 * Res
但し、Res = 203560350540241114863429835289761257239483717040193233874117904230169286234571482421387546631832059449971585954738357051759957677556703265583032619176493432315622968547519256392594813436875530796380978972639071067604902867158059055183572699320156399296460100239708804816649576605492689112864813270324565325930424653852574984603584730127790999375871038185295950722323523126290532972720746428285428362949221776576353836507632212665527900259111518152929325537963809556478012703900203723351332139532798741458461424009021983902742970898100142104817157523104393840272925587625053051536569203 の約数は不明
と出ました。ここで、Res は大きな約数しか持たないと判断し、また $e$、$d$ のサイズから、size(t)=19 or 20 くらいと見立てて、$t$ の候補を以下のプログラム（ひでぇ！）から列挙しました。
from crypto.Util.number import *
f1 = [1,2,4,8,16,32]
f2 = [1,3,9,27,81,243]
f3 = [1,5]
f4 = [1,13]
f5 = [1,31]
f6 = [1,47]
f7 = [1,331]
f8 = [1,449]
f9 = [1,1381]
fa = [1,37693]
for n1 in f1:
for n2 in f2:
for n3 in f3:
for n4 in f4:
for n5 in f5:
for n6 in f6:
for n7 in f7:
for n8 in f8:
for n9 in f9:
for na in fa:
t = n1*n2*n3*n4*n5*n6*n7*n8*n9*na
if(size(t) == 19 or size(t) == 20):
print(t)
次に、$\phi(n)$、$p_{q}$、$q_{p}$ から $p$、$q$を計算する方法ですが、$l$、$m$を
p_{q} * p - lq = 1・・・(1) \\
q_{p} * q - mp = 1・・・(2)
となるようにとれば、(1)、(2)より
p = \frac{l+q_{p}}{p_{q}q_{p}-ml}\\
q = \frac{m+p_{q}}{p_{q}q_{p}-ml}
ですが「分母は$1$でないとムリゲーだ！」とエスパーして（数論的裏付けは眠かったので考えず！）
p = l+q_{p}・・・(3)\\
q = m+p_{q}・・・(4)\\
p_{q}q_{p}-lm=1・・・(5)
を得ます。これらと、
$(p-1)(q-1)=\phi(n)・・・(6)$
を連立させて、$l$に関する二次方程式を作る。この二次方程式と解ける$\phi(n)$がビンゴ。
ただし、実装上は$\phi(n)$を列挙するのではなく$t$を列挙した。
test.pyの結果を受けた最終的なソルバーは以下（プログラムが汚いのはご容赦）。
from crypto.Util.number import *
import gmpy2
from decimal import *
import math
getcontext().prec = 1000
ts = [620069,457111,654193,482267,490009,843791,274339,556543,743095,324535,1011205,904735,666965,445857,823017,606723,542841,400179,565395,973605,316545,642165,269295,284115,339237,584163,385299,949635,700065,626355,461745,807885,262665,852345,1017711,569781,420039,375813,277047,484731,511407,787995,580905,831141,472797,348543,559305,590085,335583,354051,1045629,545535,402165,742365,489645,914222,297238,964534,980018,548678,404482,361894,266786,376930,649070,428110,891714,389442,800358,633090,466710,417570,307830,538590,568230,678474,379854,280026,770598,323154,340938,923490,525330,387270,840078,751626,554094,969462,315198,1022814,372870,393390,945594,697086,363690,268110,494910,326430,671166,708102,296946,804330,979290,594476,808964,723788,533572,753860,422060,311140,856220,278380,359060,378820,452316,778884,513732,933420,835140,615660,350220,759708,560052,501084,369396,646308,681876,262260,774540,630396,464724,745740,786780,329940,447444,472068,727380,536220,989820,652860,436428,321732,593892,391716,301544,519256,342488,844120,622280,556760,410440,718120,757640,904632,506472,373368,1027464,334056,430872,454584,700440,516360,1002168,738792,420264,309816,497160,524520,298296,314712,929448,484920,357480,659880,435240,894888,290952,944136,395928,872856,643464,783432,456840,301320,603088,1038512,337648,684976,287248,303056,820880,466960,344240,1012944,746736,668112,492528,861744,280176,909168,331440,349680,1032720,840528,619632,994320,323280,439920,290160,596592,629424,263952,969840,714960,870480,581904,428976,791856,522288,304560,913680,602640,675296,497824,445408,328352,574496,606112,933920,688480,985056,560352,413088,662880,699360,293280,397728,419616,646560,476640,879840,580320,387936,285984,527904,348192,857952,1044576,609120,401760,365472,505440]
iqmp = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743
ipmq = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331
e = 1048583
d = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927
c = 0x32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703
for t in ts:
phi_n = t_phi_n // t
aa = ipmq-1
bb = 2 * ipmq * iqmp - ipmq - iqmp - phi_n
cc = (ipmq * iqmp - 1) * (iqmp - 1)
dd = bb * bb - 4 * aa * cc
if(gmpy2.is_square(dd)):
s_d = int(Decimal(dd).sqrt())
print(s_d)
l = (-1 * bb +s_d) // (2*aa)
m = (ipmq * iqmp - 1) // l
n = (l + iqmp) * (m + ipmq)
result = pow(c,d,n)
print(long_to_bytes(result))
hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}
疲れた。
3. おわりに
とりあえず、体調の良い時には「ソロで出てWelcome以外1問解く」はほぼ出来るようになったので、
・ソロで出て3問以上解く
・ソロで出てCryptoとpwmは1問以上解く
・ソロで出て100位以内に入る
・チームを結成して本格参戦！
と、ステップアップしてゆきたいと思います。