1. はじめに
2022/2/5(土) 06:00 JST ～ 2021/2/7(月) 6:00:00 JST で「DiceCTF 2022」にソロ参加し、391 点（得点を得た 1127 チーム中 132 位）を獲得しました。
最初の2時間頑張った後はバテてしまい、最後の半日で奮闘するも最終的に Crypto を 2 問解くのがやっとでした。
問題が解けず時間が溶けるのはいつものことなのでヨシ！？
2. Writeup
2-1. baby-rsa (crypto, 117 points, 162 solves)
☆設問
I messed up prime generation, and now my private key doesn't work!
generate.py
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
def getAnnoyingPrime(nbits, e):
while True:
p = getPrime(nbits)
if (p-1) % e**2 == 0:
return p
nbits = 128
e = 17
p = getAnnoyingPrime(nbits, e)
q = getAnnoyingPrime(nbits, e)
flag = b"dice{???????????????????????}"
N = p * q
cipher = pow(bytes_to_long(flag), e, N)
print(f"N = {N}")
print(f"e = {e}")
print(f"cipher = {cipher}")
output.txt
N = 57996511214023134147551927572747727074259762800050285360155793732008227782157
e = 17
cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971
☆方針・解法
某 CTF みたいに baby という名の超難問…ではなさそうですが、一癖ありそうです。
N は msieve で現実的な時間内に素因数分解可能なくらい小さいのでヨシ！
しかし、各素因数から 1 を引いた数はすべて e の 2 乗で割り切れてしまいます。
e は十分小さいので、p, q それぞれを法として全ての e 乗根を出し、それらを総当たりで CRT して "dice{" を含むものを選べば OK です。
☆ソルバ
solve.sage
from Crypto.Util.number import *
N = 57996511214023134147551927572747727074259762800050285360155793732008227782157
e = 17
cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971
# by msieve:
p = 172036442175296373253148927105725488217
q = 337117592532677714973555912658569668821
Fp = GF(p)
c_p = Fp(cipher)
Fq = GF(q)
c_q = Fq(cipher)
pt_ps = c_p.nth_root(17, all=True)
pt_qs = c_q.nth_root(17, all=True)
for pt_p in pt_ps:
for pt_q in pt_qs:
pt = long_to_bytes(crt([int(pt_p),int(pt_q)],[p,q]))
if b"dice{" in pt:
print(pt.decode())
毎度雑なソルバですみません。
☆フラグ
dice{cado-and-sage-say-hello}
ダッシュで頑張ったのですが、残念ながら 1st blood は取れませんでした（4th でした）。
2-2. commitment-issues (crypto, 272 points, 16 solves)
☆設問
I created a new commitment scheme, but commitment is scary so I threw away the key.
scheme.py
from random import randrange
from Crypto.Util.number import getPrime, inverse, bytes_to_long, GCD
flag = b'dice{?????????????????????????}'
n = 5
def get_prime(n, b):
p = getPrime(b)
while GCD(p - 1, n) != 1:
p = getPrime(b)
return p
p = get_prime(n, 1024)
q = get_prime(n, 1024)
N = p*q
phi = (p - 1)*(q - 1)
e = 0xd4088c345ced64cbbf8444321ef2af8b
d = inverse(e, phi)
def sign(message):
m = bytes_to_long(message)
return pow(m, d, N)
def commit(s, key, n):
return (s + key) % N, pow(key, n, N)
def reveal(c1, c2, key, n):
assert pow(key, n, N) == c2
return (c1 - key) % N
r = randrange(1, N)
s = sign(flag)
c1, c2 = commit(s, r, n)
print(f'N = {hex(N)}')
print(f'c1 = {hex(c1)}')
print(f'c2 = {hex(c2)}')
output.txt
N = 0xba8cb3257c0c83edf4f56f5b7e139d3d6ac8adf71618b5f16a02d61b63426c2c275ce631a0927b2725c6cc7bdbe30cd8a8494bc7c7f6601bcee5d005b86016e79919e22da4c431cec16be1ee72c056723fbbec1543c70bff8042630c5a9c23f390e2221bed075be6a6ac71ad89a3905f6c706b4fb6605c08f154ff8b8e28445a7be24cb184cb0f648db5c70dc3581419b165414395ae4282285c04d6a00a0ce8c06a678181c3a3c37b426824a5a5528ee532bdd90f1f28b7ec65e6658cb463e867eb5280bda80cbdb066cbdb4019a6a2305a03fd29825158ce32487651d9bfa675f2a6b31b7d05e7bd74d0f366cbfb0eb711a57e56e6db6d6f1969d52bf1b27b
c1 = 0x75240fcc256f1e2fc347f75bba11a271514dd6c4e58814e1cb20913195db3bd0440c2ca47a72efee41b0f9a2674f6f46a335fd7e54ba8cd1625daeaaaa45cc9550c566f6f302b7c4c3a4694c0f5bb05cd461b5ca9017f2eb0e5f60fb0c65e0a67f3a1674d74990fd594de692951d4eed32eac543f193b70777b14e86cf8fa1927fe27535e727613f9e4cd00acb8fab336894caa43ad40a99b222236afc219397620ca766cef2fe47d53b07e302410063eae3d0bf0a9d67793237281e0bfdd48255b58b2c1f8674a21754cf62fab0ba56557fa276241ce99140473483f3e5772fcb75b206b3e7dfb756005cec2c19a3cb7fa17a4d17f5edd10a8673607047a0d1
c2 = 0xdb8f645b98f71b93f248442cfc871f9410be7efee5cff548f2626d12a81ee58c1a65096a042db31a051904d7746a56147cc02958480f3b5d5234b738a1fb01dc8bf1dffad7f045cac803fa44f51cbf8abc74a17ee3d0b9ed59c844a23274345c16ba56d43f17d16d303bb1541ee1c15b9c984708a4a002d10188ccc5829940dd7f76107760550fac5c8ab532ff9f034f4fc6aab5ecc15d5512a84288d6fbe4b2d58ab6e326500c046580420d0a1b474deca052ebd93aaa2ef972aceba7e6fa75b3234463a68db78fff85c3a1673881dcb7452390a538dfa92e7ff61f57edf48662991b8dd251c0474b59c6f73d4a23fe9191ac8e52c8c409cf4902eeaa71714
☆方針・解法
N が 2048 ビット、s^e mod N が 256 ビット程度のフラグなので、フラグを直接 small_rootsで計算する流れなのかなぁ、という見立てでしたが、なかなかたどり着かず。
c1、c2 の式を使って r と x := s^e の式を作りゴニョゴニョしてたら 8 次式とかが出てきて閉口したのですが、終結式を使えば良いということを思い出して x だけの 5 次式を得ました。
small_roots が刺さらず、いろいろと寄り道をした挙句、最後ヤケクソで epsilon=0.01 にしたら見事に刺さりました。
☆ソルバ
solve.sage
from Crypto.Util.number import *
N = 0xba8cb3257c0c83edf4f56f5b7e139d3d6ac8adf71618b5f16a02d61b63426c2c275ce631a0927b2725c6cc7bdbe30cd8a8494bc7c7f6601bcee5d005b86016e79919e22da4c431cec16be1ee72c056723fbbec1543c70bff8042630c5a9c23f390e2221bed075be6a6ac71ad89a3905f6c706b4fb6605c08f154ff8b8e28445a7be24cb184cb0f648db5c70dc3581419b165414395ae4282285c04d6a00a0ce8c06a678181c3a3c37b426824a5a5528ee532bdd90f1f28b7ec65e6658cb463e867eb5280bda80cbdb066cbdb4019a6a2305a03fd29825158ce32487651d9bfa675f2a6b31b7d05e7bd74d0f366cbfb0eb711a57e56e6db6d6f1969d52bf1b27b
c1 = 0x75240fcc256f1e2fc347f75bba11a271514dd6c4e58814e1cb20913195db3bd0440c2ca47a72efee41b0f9a2674f6f46a335fd7e54ba8cd1625daeaaaa45cc9550c566f6f302b7c4c3a4694c0f5bb05cd461b5ca9017f2eb0e5f60fb0c65e0a67f3a1674d74990fd594de692951d4eed32eac543f193b70777b14e86cf8fa1927fe27535e727613f9e4cd00acb8fab336894caa43ad40a99b222236afc219397620ca766cef2fe47d53b07e302410063eae3d0bf0a9d67793237281e0bfdd48255b58b2c1f8674a21754cf62fab0ba56557fa276241ce99140473483f3e5772fcb75b206b3e7dfb756005cec2c19a3cb7fa17a4d17f5edd10a8673607047a0d1
c2 = 0xdb8f645b98f71b93f248442cfc871f9410be7efee5cff548f2626d12a81ee58c1a65096a042db31a051904d7746a56147cc02958480f3b5d5234b738a1fb01dc8bf1dffad7f045cac803fa44f51cbf8abc74a17ee3d0b9ed59c844a23274345c16ba56d43f17d16d303bb1541ee1c15b9c984708a4a002d10188ccc5829940dd7f76107760550fac5c8ab532ff9f034f4fc6aab5ecc15d5512a84288d6fbe4b2d58ab6e326500c046580420d0a1b474deca052ebd93aaa2ef972aceba7e6fa75b3234463a68db78fff85c3a1673881dcb7452390a538dfa92e7ff61f57edf48662991b8dd251c0474b59c6f73d4a23fe9191ac8e52c8c409cf4902eeaa71714
n = 5
e = 0xd4088c345ced64cbbf8444321ef2af8b
PR.<x,r> = PolynomialRing(Zmod(N))
def reduct(f):
g = f % (r^n)
h = (f - g) // (r^n)
assert r^n * h + g == f
return (c2 * h + g) % N
def ppow(f, x):
res = 1
while(x):
if x % 2:
res = reduct((res * f) % N)
f = reduct(f * f % N)
x >>= 1
return res
f = ppow(c1 - r, e)
# f = 14117722674361863286590040096372457287622420866329431749050556750614745748356003282022268994351814862178621531181225199058872191366119018682615373718376417554494143881137290867429260102243915408308536826516009685297154294115333661611279783866660839421056249795544989853772463935789571302053073596808101592415044876033571592305415509213549341269429267243692292183573872683908229497382721026967034839802532688279381971389263500391109168943858255261895609463766102470370175937939261942561893443554685517156930775390120475064945812121508504332772784703943689363194919028208629545334173260939418202766394635300211665749617*r^4 + 5873863517369394545983549104970246945609520202521818311731190376655022919333750322681685955632544422226074332985655102099974702285196618543538179413353677583872951735983856609026727005760667365696470019189026970143041373015305029037165683389977341413280366254494556845568164224382529324282745735891430655062052066943379760947847699992542230576233015282575242983572666681981852244000749202054069408904847105141698884801094715200484728626904835736233951839639292488160936005151023588289843686723501470895504958430063291139341312149303384222271064935473915225530510121765351041832997549818433192845097153114522621869978*r^3 + 21611452462068822195260824689420450746624138578918021979365713945922475473366761178879260731879296359538156834296348679280911394770238500768484949121424022192339656000802865619265611794737315707792271848300069499702772187043418801509102434773091590999929110722598506427232550981420226099246809633209624501229742922699765197733899027682253041029207147041722179664973899576672039924977389554953742293916715525035321644919352199231166450999164545267849698844450433840464824070111779568530757450071023810069911883893819599094705649975495754387979847949863034758599792560232531742304594385345433405067015805498873397689925*r^2 + 18380957518269288615756444059168524132141182508162415213451894402866293145291058266884298945374580378510617687295277851054444800331303673347662441183122418194692266612288127100069660929895637517684333939615382946703098356608446412542849201915298618849839848676258079996599818733240346055921445999902622855756241153787596544923253586046294506270747774563549467429912737780337613418351615380502319818439543853700008013854428950382197990327744596925643137978292202554105625274958835349102200901097656788794440567043327573991937093256451904152543371300362396837854169760013536395757353077080666396941384484946837836585973*r + 13257762133319378511724129749109819320171706828349922801640378254137306185257533572918621889926911355653792543915149496558622497241951630414468548164749392093413484237076799055750697889441889608968957384516358751113920685682027273612823569389890399257969314926737279805388789833805778857751105587542743174637330541231706891116823979630637412056302819820582271575592869431824200374749133866931116590464789679656155782644529744612942291906855174227215285016471655928959491966835975235845209501393890222454769037271874486160218321382218265189976100994554518667891622013186469120808729961321530702922973792151362211392906
f = PR(f - x) # x:= s^e
g = PR(r^5 - c2)
PR2.<xz,yz> = PolynomialRing(Zmod(N))
q1 = f.change_ring(PR2)
q2 = g.change_ring(PR2)
h = q2.resultant(q1, variable=r)
PR3.<x> = PolynomialRing(Zmod(N))
h = PR3(h).monic()
root = h.small_roots(X=2^256, beta=0.5, epsilon=0.01)[0]
# root = 177412069566304093463259591744550462292826246634155816335091162756238506365
print(long_to_bytes(int(root)).decode())
☆フラグ
dice{wh4t!!-wh0_g4ve_u-thE-k3y}
3 おわりに
気が付いたら夜明けが近く、予期せぬ徹夜となってしまいました。
2 月から 3 月にかけてスケジュールが詰んでいるので、おそらく zer0pts CTF 2022 までお休みです。