ksnctf 16 Math I 150pt

問題

数字は右にもっと続きます。

解いてみた

ただの数学の問題かと一瞬思いましたが、暗号化の話でした。RSAです。
RSAの細かい計算方法はwikipediaを見てください。
RSA暗号

mを求めなさいということなので、wikipedia通り考えると以下を計算すると良いそうです。

m = c^d mod n

問題文から判明している変数を一度まとめます。

e = 65537
n = 1517330236262917595314610888889322115651087080826711948897066340883208205571592392362650858571076247939805436226544833224526137582834770402681005343930059463684528957271778199162575053306238099823295117697031968370690372250916935800738698142103275969223264184374648246277564306900886005299731265812255274723175925185522344831066577166867786835955092059346244885587228196357297758371381557924676260190209536670230008561217008649261974735505203813478978893582292682827884118215872470401293272325715864815977064075988643101088355047954735427424641386870772845440782632933485165110172437511822736907550777817722248753671107339823410418938404382732079381329288400012929311347390423061254658780185245562668131009832293474920208834795460061115101364091252176594144096675899952570380792978037217747311595899301451192342027799533264325948876556110474850761538179748318187805312451895898751337975457949549497666542175077894987697085521882531938339334715190663665300179658557458036053188152532948734992896239950564081581184284728802682982779186068791931259198917308153082917381616147108543673346682338045309449569430550618884202465809290850964525390539782080230737593560891353558335337408957948041667929154230334506735825418239563481028126435029
c = 225549592628492616152632265482125315868911125659971085929712296366214355608049224179339757637982541542745010822022226409126123627804953064072055667012172681551500780763483172914389813057444669314726404135978565446282309019729994976815925850916487257699707478206132474710963752590399332920672607440793116387051071191919835316845827838287954541558777355864714782464299278036910958484272003656702623646042688124964364376687297742060363382322519436200343894901785951095760714894439233966409337996138592489997024933882003852590408577812535049335652212448474376457015077047529818315877549614859586475504070051201054704954654093482056493092930700787890579346065916834434739980791402216175555075896066616519150164831990626727591876115821219941268309678240872298029611746575376322733311657394502859852213595389607239431585120943268774679785316133478171225719729917877009624611286702010936951705160870997184123775488592130586606070277173392647225589257616518666852404878425355285270687131724258281902727717116041282358028398978152480549468694659695121115046850718180640407034795656480263573773381753855724693739080045739160297875306923958599742379878734638341856117533253251168244471273520476474579680250862738227337561115160603373096699944163
p = 34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323
q = 44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223

必要な変数とわかってる変数をあわせるとあとdが判明すれば全部の変数が明らかになるということがわかります。
dを求める計算式もWikipediaに書いていました。

d = e^(-1)(mod(p-1)(q-1))

ちょっとわかりづらい式です。wikipediaはもっと見やすい。
dを求めるための変数もすべてわかっているので単純に計算式をプログラムします。
問題文にpythonが少し書かれていたのでpythonで作ってみます。

e=65537
p = 34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323
q = 44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223


tmp = pow(e, -1)
tmp2 = (p-1)*(q-1)
d = tmp % tmp2
print(d)

素直に書けばこうなる。
実行してみるとd = tmp % tmp2のところでオーバーフローしてしまうというエラーが。
直接はこの計算ができないみたいなのでdを求める他の方法を検索してみます。
Python で公開鍵暗号アルゴリズム RSA を実装してみる
これを参考にしました。

まずp-1とq-1の最小公倍数を求める。

import math

e=65537
p = 34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323
q = 44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223


L = (p-1) * (q-1)) / gcd(p-1, q-1)
print(L)

実行すると以下の結果が得られました。

次に(e*d)mod L = 1を計算する。

from fractions import gcd

e=65537
p = 34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323
q = 44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223
L = 84296124236828755295256160493851228647282615601483997160948130049067122531755132909036158809504235996655857568141379623584785421268598355704500296885003303538029386515098788842365280739235449990183062094279553798371687347273163100041038785672404220512403565798591569237642461494493666961096181434014181929065329176973463601725920953714877046441949558852569160310401566464294319909521197662482014455011640926123889364512056036070109707528066878526609938532349593490438006567548470577849626240317548045332059115332702394504908613775263079301368965937265158080043479607415842506120690972879040939308376545429013819648390485935794450615898958353067616834620525918090857785857386064201656062162479977365475744402936160462725848773696706919076088977774264353849497982111223048654302053359923581516772918609667237350631341932314473210047462494239592712774736257925119172802057115385038544143487469511024761330324631420828143510952462371722743318909328271983585955272776528260618472853022289420098014703890951951042220157282038147741762284049660911709073315391605377178884477278893384365501359415452208704330546728410396192866583877887324203642431037251063767954409221007463068318828757916045833958167479029226438074023231872818141833569638

for i in range(2, L):
	if (e * i) % L == 1:
		d = i
		break

print(d)

実行すると以下のエラーが出てしまい、計算できないことがわかりました。

OverflowError: range() result has too many items

単純な計算ではなく、ちょっと負荷が軽めな計算方法を検索したところ拡張ユークリッドの互除法という計算方法を使うそうです。

これをやるとdの値は以下になります。

d = 10136834995658138463492588932237385491695291111208864940803396751708164741638497374858690015986433371830337267414166239124032133070140892035143000743865465846517380947029823685348440995253285645858564053359433045225861238443319016607770063778998392692040412317602272871230911378886805763467949492370199548086788520129512590524466836080793231350367036533822078404661103579735165405907144952897153606664124725556286862104147483410417544364690099785895187841577233414683948452917428271419700389092308102983993131939774899233916486643618846269650561065529192835021784072906056956997378054492267293936086722836352868038649395298228421583287298637113781349064564517150221252274929575231903374062018473558712091515320198980831322980690354261397968433615194125039106056075477193744671780559524508993907065803481811763741483524857261750894670978486995592861707073084026797089476358795024013403036830297639289928502806357134849001477277811794054352447082046958247110998439840383629616621979472098506072201677900915912594977791777814705476731626338978671272819912434837992993096501746475459427746365460409490804111246572200930710614577133985413566473885050820659402302501957059621914654156295472133564617207107883082204882388427753479344345367

それでもとに立ち戻るとmを求めたかったんです。

m = c^d mod n

この式です。
それぞれの値を改めて書きます。

c = 225549592628492616152632265482125315868911125659971085929712296366214355608049224179339757637982541542745010822022226409126123627804953064072055667012172681551500780763483172914389813057444669314726404135978565446282309019729994976815925850916487257699707478206132474710963752590399332920672607440793116387051071191919835316845827838287954541558777355864714782464299278036910958484272003656702623646042688124964364376687297742060363382322519436200343894901785951095760714894439233966409337996138592489997024933882003852590408577812535049335652212448474376457015077047529818315877549614859586475504070051201054704954654093482056493092930700787890579346065916834434739980791402216175555075896066616519150164831990626727591876115821219941268309678240872298029611746575376322733311657394502859852213595389607239431585120943268774679785316133478171225719729917877009624611286702010936951705160870997184123775488592130586606070277173392647225589257616518666852404878425355285270687131724258281902727717116041282358028398978152480549468694659695121115046850718180640407034795656480263573773381753855724693739080045739160297875306923958599742379878734638341856117533253251168244471273520476474579680250862738227337561115160603373096699944163
d = 10136834995658138463492588932237385491695291111208864940803396751708164741638497374858690015986433371830337267414166239124032133070140892035143000743865465846517380947029823685348440995253285645858564053359433045225861238443319016607770063778998392692040412317602272871230911378886805763467949492370199548086788520129512590524466836080793231350367036533822078404661103579735165405907144952897153606664124725556286862104147483410417544364690099785895187841577233414683948452917428271419700389092308102983993131939774899233916486643618846269650561065529192835021784072906056956997378054492267293936086722836352868038649395298228421583287298637113781349064564517150221252274929575231903374062018473558712091515320198980831322980690354261397968433615194125039106056075477193744671780559524508993907065803481811763741483524857261750894670978486995592861707073084026797089476358795024013403036830297639289928502806357134849001477277811794054352447082046958247110998439840383629616621979472098506072201677900915912594977791777814705476731626338978671272819912434837992993096501746475459427746365460409490804111246572200930710614577133985413566473885050820659402302501957059621914654156295472133564617207107883082204882388427753479344345367
n = 1517330236262917595314610888889322115651087080826711948897066340883208205571592392362650858571076247939805436226544833224526137582834770402681005343930059463684528957271778199162575053306238099823295117697031968370690372250916935800738698142103275969223264184374648246277564306900886005299731265812255274723175925185522344831066577166867786835955092059346244885587228196357297758371381557924676260190209536670230008561217008649261974735505203813478978893582292682827884118215872470401293272325715864815977064075988643101088355047954735427424641386870772845440782632933485165110172437511822736907550777817722248753671107339823410418938404382732079381329288400012929311347390423061254658780185245562668131009832293474920208834795460061115101364091252176594144096675899952570380792978037217747311595899301451192342027799533264325948876556110474850761538179748318187805312451895898751337975457949549497666542175077894987697085521882531938339334715190663665300179658557458036053188152532948734992896239950564081581184284728802682982779186068791931259198917308153082917381616147108543673346682338045309449569430550618884202465809290850964525390539782080230737593560891353558335337408957948041667929154230334506735825418239563481028126435029

あの計算式をプログラムで表すと以下になるそうです。
非常に便利なものがあるんですね。

m = pow(c,d,n)

そして実際に計算した結果は以下です。