1. はじめに
2021/8/28(土) 08:00 JST 〜 2021/8/29(日) 20:00:00 JST で「CakeCTF2021」に参加しました。競技中 1028 点を獲得し、（得点を得た 157 チーム中） 35 位の成績でした。
・・・というか、Warmup以外は 1 問しか出来ていません！ケーキは甘くなかった！！
ということで、例によって Crypto の Writeup を記します。
2. Writeup
2-1. Together as one
☆設問
Stay safe everyone!!!
chall.py
from Crypto.Util.number import getStrongPrime, bytes_to_long
p = getStrongPrime(512)
q = getStrongPrime(512)
r = getStrongPrime(512)
n = p*q*r
x = pow(p + q, r, n)
y = pow(p + q*r, r, n)
m = bytes_to_long(open("./flag.txt", "rb").read())
assert m.bit_length() > 512
c = pow(m, 0x10001, n)
print(f"{n = :#x}")
print(f"{c = :#x}")
print(f"{x = :#x}")
print(f"{y = :#x}")
output.txt
n = 0xa723365ef4e3133221c487fd3721401f2e63150904c596ada919e825ecde6b8481a478199a9a9bda094fd48e14280825e293f43800a460aa892f2c9296c75216191a2fc149176ee60f2ccbe00fdbef3ffc2859b9904133c4f9b9527de5434ecaa55e9e8032d469e548d29c9f6ac18e29ea5e0d388aa78b65cd4f74fb5c392ea683db6f12c0772c929b2fab302cffd6e091c26ce9b19d43fb7cbe974aa40f2426cd9f3c9c61f3a331a33091df86d7c927563794135b4bb2bb469e85cf07ab6cf7
c = 0xff0952eca2348a6b29f265f590252dbd13f39c4c2cbad8fe426bfc60f1f468730724ed2a2567887616a86afd3fb910e5dde6d5e7140cfdb0e00dd570585ff7a786a40e5da0e5771146d4ac196cb504953f06cdbbd976897b625567f499d04b996e904121051c04cd0c57221567e2ace197e1b0e3c7394eb9b0949512051382d966e7c9097297353fade9daa493214f9c3aa4616b6e505f965466f692b5cf992234788d1bb2c89e44efb6e54242f3bb40fc86f77e788fb3fa5290d3430cd9632
x = 0x98ebc634bb509c14985a922fda4fc06e603771d0fa311fcd4c0c8cf3bb82a5b951519fcfae0483289eeb23a20a1f89b3069b54fc8943135ea6156efb4d70593f4661b11b5fcc2901f05aa03538c4fb7c8c0c17ed03d995183e0ef75a6e3870983847ca1c067a276df5457f102d552f41d3ea551ae0443816afbb063e9a767e0f032106c47bfa495e0fce9755c9bd276e6ca7799eedce3d6eb9331e60840f4d9b6370a2ff0593326665e36c64187799de27805afad6a5dfd553acfd04909b00db
y = 0x45c71b4f8d838be9305682b601b4c02b2c00dd2c2f96397fb31ea6c6053e99d09f8d3948f381e9125c9b575040858cf77a22244eb5cc83022b22d55436a1bffeffd50b90acb6d96e333413ad8df4d952a462ac2300f8d42633f34d8b0afc722786bc4348aba53f075a75cbb9011f88d9fac8f8b7807514e8a57c1aa53ad6f84cacb093c778f739870bd91f085ca2dc2aa0cdb9cf73ee15c6f1c48fd86010c4848ed1ac30c73303ca306e2e254b0f6a48d9b5f41b50acc182a027670c648a40a2
☆方針・解法
RSA 問で、公開鍵・暗号文（c=pow(m,0x10001,n)）のほか、$x:=(p+q)^{r} \mod{n}$ と $y:=(p+qr)^{r} \mod{n}$ が示されています。公開鍵のうち $n$ は（すべて異なる）3つの素数 $p,q,r$（各512bit）の積です。
m の ビット長は 512bit 超のため、$p,q,r$ のうち少なくとも2つ（したがって全部）を判明させるか、秘密鍵 $d$ を直接求めるしかありません。そこで、$x,y$ から $n$ の素因数の算出を試みます。
まず $q$ に着目すると、 $(p+q)^{r} \equiv (p+qr)^{r} \equiv p^{r} mod{q} $ で、$y-x$ と $p, r$ は互いに素であると考えられるので、$n$ との GCD をとれば $q$ が出そうです。
また、フェルマーの小定理から $q^{r} \equiv q \mod{r}$ が成立するので、$y+q-x$ は $r$ で割り切れます。$q$ が判明すれば、$y+q-x$ と $n$ との GCD をとることで $r$ を計算でき、 Case Closed となります。
☆ソルバ
solve.py
from Crypto.Util.number import *
import gmpy2
n = 0x94cf51734887aa44204e7d64ed2b30763fd0715060afd5d15b697c940c272422b4ca765485f7c3116db1166ad1fec4cd4d82d3b32e881ed49f52efe31a226b307d60f2fb375400f9a19b0142e7d88d6118e02971724186e1ef13e586c744240b3ee7d6a105b82a3e3126ae364550e9b3a19d6b012083b8633ad428cf75cb200fe31121e6bf095418c5ed3819225910bc69ebe2e6a219638b830df45015c75ca9a507dc924718a540cfb5d2df09ff28d7cf8feb0e5e69a3d71057004132bb3e79
c = 0x8c0450dff19d853673d51cb2eab4cb84ffa7fa3eba900c1e96adbb2ccb6708320233e18b2d6ce487dbfb88f15b0ccac5829818ca49ac8ab08a1e5b94e27550798e6d1aae48812b784144dc7bed55cec6283042a296e25490990e07b8ff51b1a500b6d8c39af1c07c1ef57ca2b3774a4d38f6006a64f37133915f9afcbd08394e74c616fabd77d79cd9559a3eee41f2507556637bac6145bfba22319f424f07a33221a8fb9c89dc3c68e188230ed36e95a6baf977ca58d2036d136ebd55bd45d3
x = 0x38f530204337208b5bbfadd20fcd4416d8be1563c338c0ba464abbcd3699794c0c8e0b6f17f41bc5e42dd5f900d3644b34f4530157cc8c026894f97f2feb5475e58cdf9125d96bdae25bbf6afdf58129c8e1c70a5b47f2dbe3f89e851c124bed2b40f6e8ec8d6d3ff941fa5dcde893c661059fffdb5086863e35228bc79b1ba830555c3168c88a53e3c7eee17312c401914442d4e04c5014aa484994d0c680980f53aeef01c9c246ec76dcdf8816036b77629610709ccc533cbd09a818146060
y = 0x607e4383ee2f5bb068a4fb51205396c784a56e971cee8f2b2c79fbf1ce4161a4031aa10df22723005024ef592764c4391f31ca35137221a7431c68033b5f92ab5bf9c660e5cda375faf4f4e734cb8745d0b7b056b2d9ba38a733fae118f07ceb1af4fbb2818b6cf4394f166f3790a9ad39efb27a970399ed1fc04b96a282681109825c96e3784f1ee3ac1a787f28dd7c74cc6cccecffb0ce534e1ed7192ccc2bc3f822ad16dc42608d6fe1de447e4ed9474d1113bd0514d1f90b92f04769059
q = gmpy2.gcd (y-x,n)
pr = n // q
r = gmpy2.gcd((y+q-x)//q, n)
p = pr // r
e = 0x10001
d = inverse(e, (p-1)*(q-1)*(r-1))
print(long_to_bytes(pow(c, d, n)))
☆フラグ
CakeCTF{This_chall_is_inspired_by_this_music_Check_out!_https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}
このような、数学的な考察を主体に解く問題は大好きです。
2-2.
☆設問
People conclude discrete log is hard problem up to now.
task.py
from Crypto.Util.number import getPrime, isPrime, getRandomRange
def getSafePrime(bits):
while True:
p = getPrime(bits - 1)
q = 2*p + 1
if isPrime(q):
return q
with open("flag.txt", "rb") as f:
flag = f.read().strip()
p = getSafePrime(512)
g = getRandomRange(2, p)
r = getRandomRange(2, p)
cs = []
for m in flag:
cs.append(pow(g, r*m, p))
print(p)
print(g)
print(cs)
output.txt
10577926960839937947442162797370864980541285292536671603546595533193324977125572190720609448828374782284663027664894813711243894320697692129630847705557539
9947724104164898694903023872711663896409433873530762235716749042436185304062119886390357927264325412355223958396239523671881766361219889894069645084522127
[1229288066188188446140572951590585838131579917371511162649288281094421402493758271918280416055465305258850798174813421022714679676287728499647253120374695, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 8846898594122745402315346660588103073817097798204431437711034651813289442774837730820134043682352683522453026507938275715350738931942754620858572095894833, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 1229288066188188446140572951590585838131579917371511162649288281094421402493758271918280416055465305258850798174813421022714679676287728499647253120374695, 1945428232655195080994800854254286050005395375198086738205807646894444509288423023719076721279967584478447554044287458681202684205941300518455664909896770, 10354621433690291080863817499954203913680345790427806490217953854290390664868635054642758139322526900976315271173855068718334823237601765344488054950961045, 6450396411196778288237471377707156944771360666868782593043200729952706897922338702645020446957804453347793935766075212035314665465699530609262139446841794, 6603165839364347784941569364866161781386478404222821544628017382892389369481107861540318475846446163066953093646715054906626664043485319179748812018187608, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 9753045617655554075535397949256980647454831331391019636944817636801025863316405956657883053760816735577807443396030910262012333972455514593468821229847216, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 5705490906960110528538635141558499052089268217498141288524505028321355953649986725466752682611329558447209023808467500672466053160864942319360366767522428, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 5705490906960110528538635141558499052089268217498141288524505028321355953649986725466752682611329558447209023808467500672466053160864942319360366767522428, 8518396356987073160446226593505514680842064427706567536033369420610810908882528653260766790896766994789384117506763080763933744536854279875382388996716393, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 1451759830404925477558275270642407378934999719484439203872342683020817625642737205582986542429047217317435872276960585914530151288082605818539662897325059, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 3844728289551481985429176289449289604000304789858654366566902189290267618563940933188833996034764887276042750051165636121466021492112395693389564386737849, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 6603165839364347784941569364866161781386478404222821544628017382892389369481107861540318475846446163066953093646715054906626664043485319179748812018187608, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 9753045617655554075535397949256980647454831331391019636944817636801025863316405956657883053760816735577807443396030910262012333972455514593468821229847216, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 6075040072394386353700068186624559720007996691077752316710222658102597630426876503425968551345482454171942016710393973778088713964073715708282771166108340, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 2319394889752437261970357119967349450311229179467143254112633795132104201041540419394974595546896804379819748025776699134680309317217660482163282654767536]
☆方針・解法
$1$ 文字ずつの独立した（前の結果に依存しない）暗号化で、平文の最初の文字は「C」であることがわかっているので、暗号文を1文字ずつ、各文字（Ascii文字）の暗号化結果と照合すれば平文がわかります。
なお計算をわかりやすくするため、暗号文 1 文字目を 「ord("C") の mod p-1 での逆数」乗することで $g^{r}$ を計算しています。
平文と暗号文との対応付けは辞書に入れたほうがスマートかと思いますが、大した計算量ではないのでサボっています。
☆ソルバ
solve.py
from Crypto.Util.number import *
p = 10577926960839937947442162797370864980541285292536671603546595533193324977125572190720609448828374782284663027664894813711243894320697692129630847705557539
g = 9947724104164898694903023872711663896409433873530762235716749042436185304062119886390357927264325412355223958396239523671881766361219889894069645084522127
ct = [1229288066188188446140572951590585838131579917371511162649288281094421402493758271918280416055465305258850798174813421022714679676287728499647253120374695, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 8846898594122745402315346660588103073817097798204431437711034651813289442774837730820134043682352683522453026507938275715350738931942754620858572095894833, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 1229288066188188446140572951590585838131579917371511162649288281094421402493758271918280416055465305258850798174813421022714679676287728499647253120374695, 1945428232655195080994800854254286050005395375198086738205807646894444509288423023719076721279967584478447554044287458681202684205941300518455664909896770, 10354621433690291080863817499954203913680345790427806490217953854290390664868635054642758139322526900976315271173855068718334823237601765344488054950961045, 6450396411196778288237471377707156944771360666868782593043200729952706897922338702645020446957804453347793935766075212035314665465699530609262139446841794, 6603165839364347784941569364866161781386478404222821544628017382892389369481107861540318475846446163066953093646715054906626664043485319179748812018187608, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 9753045617655554075535397949256980647454831331391019636944817636801025863316405956657883053760816735577807443396030910262012333972455514593468821229847216, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 5705490906960110528538635141558499052089268217498141288524505028321355953649986725466752682611329558447209023808467500672466053160864942319360366767522428, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 5705490906960110528538635141558499052089268217498141288524505028321355953649986725466752682611329558447209023808467500672466053160864942319360366767522428, 8518396356987073160446226593505514680842064427706567536033369420610810908882528653260766790896766994789384117506763080763933744536854279875382388996716393, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 1451759830404925477558275270642407378934999719484439203872342683020817625642737205582986542429047217317435872276960585914530151288082605818539662897325059, 4042600243432470792279319238797089674031093707099421074301129639348359908738591074209975141693531653698877970720299975180608931933840731135919239266129531, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 3844728289551481985429176289449289604000304789858654366566902189290267618563940933188833996034764887276042750051165636121466021492112395693389564386737849, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 6603165839364347784941569364866161781386478404222821544628017382892389369481107861540318475846446163066953093646715054906626664043485319179748812018187608, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 9753045617655554075535397949256980647454831331391019636944817636801025863316405956657883053760816735577807443396030910262012333972455514593468821229847216, 2785996600898026596024204925975309018606205305214377134460494244584059497511759664894757187838328097195872398784106625161459942753354545213358279449633332, 10432993487247272012480923097160918670223939440020584956672587338819387564406156095947231487677556954828864387429116143245429963057004783904414488840483883, 6075040072394386353700068186624559720007996691077752316710222658102597630426876503425968551345482454171942016710393973778088713964073715708282771166108340, 5940089364090396255891114323486822488149883598124290813680817411219364338155445538437115753453598481449101247255466882855753225125970871768839102953427252, 4045640615389787749853661262284447508612987648607573956251553736198615257540512882528800714431424850616135969142451005730805426191941965206855411616865846, 10446004960956011058336954345576506542925522395495166475000278575199457691832910056903330578472321806954810895742286832849843203812788582215022283968968442, 2319394889752437261970357119967349450311229179467143254112633795132104201041540419394974595546896804379819748025776699134680309317217660482163282654767536]
t = inverse(ord("C"), p-1)
gr = pow(ct[0], t, p)
m = ""
for c in ct:
for i in range(0x20, 0x7f):
if(pow(gr, i, p) == c):
m += chr(i)
break
print(m)
☆フラグ
CakeCTF{ba37a0f409ef3ec23a6cffbc474a1cef}
3 おわりに
結局Crypto 問はこれで打ち止め、Warmup を解いておしまいとなりました。次回は「Cryptoは全完、各分野でwarmup+1問」を目標に精進したいと思います。
ジーク、ジオン！!