MathⅠ
RSAで暗号化された文を復号する問題
RSA暗号
https://ja.wikipedia.org/wiki/RSA暗号
桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つ。
暗号化
平分を暗号化するには以下の式を計算する必要がある。
c = m^e\; mod\; n
cは暗号化文、mは平分、eは適当に決める値、nは２つの大きな素数p,qの積であり、これらは自分で設定する。問題では既にこれらの値はわかっている。
暗号化する時には、復号に必要な秘密鍵dを一緒に作成しているが、詳しいことは後述する。
復号化
暗号文を復号するには以下の式を計算する必要がある。
m = c^d\; mod\; n
今回の問題は秘密鍵dを求めることが肝になっている。
解く
cを復号して平分mを求める問題になっている。
問題をみると、e,n,c,p,qは既に決まっている。
復号化で述べたように復号するには秘密鍵dが必要になる。dは以下の計算で求められる。
d = e^{-1}\; mod\; lcm((p-1),(q-1))
lcm((p-1),(q-1))は、p-1とq-1の最小公倍数、a mod bはaをbで割ったあまりのこと。
これでdが求められるので実際にpythonで計算してみる。
import math
e=65537
n=1517330236262917595314610888889322115651087080826711948897066340883208205571592392362650858571076247939805436226544833224526137582834770402681005343930059463684528957271778199162575053306238099823295117697031968370690372250916935800738698142103275969223264184374648246277564306900886005299731265812255274723175925185522344831066577166867786835955092059346244885587228196357297758371381557924676260190209536670230008561217008649261974735505203813478978893582292682827884118215872470401293272325715864815977064075988643101088355047954735427424641386870772845440782632933485165110172437511822736907550777817722248753671107339823410418938404382732079381329288400012929311347390423061254658780185245562668131009832293474920208834795460061115101364091252176594144096675899952570380792978037217747311595899301451192342027799533264325948876556110474850761538179748318187805312451895898751337975457949549497666542175077894987697085521882531938339334715190663665300179658557458036053188152532948734992896239950564081581184284728802682982779186068791931259198917308153082917381616147108543673346682338045309449569430550618884202465809290850964525390539782080230737593560891353558335337408957948041667929154230334506735825418239563481028126435029
c=225549592628492616152632265482125315868911125659971085929712296366214355608049224179339757637982541542745010822022226409126123627804953064072055667012172681551500780763483172914389813057444669314726404135978565446282309019729994976815925850916487257699707478206132474710963752590399332920672607440793116387051071191919835316845827838287954541558777355864714782464299278036910958484272003656702623646042688124964364376687297742060363382322519436200343894901785951095760714894439233966409337996138592489997024933882003852590408577812535049335652212448474376457015077047529818315877549614859586475504070051201054704954654093482056493092930700787890579346065916834434739980791402216175555075896066616519150164831990626727591876115821219941268309678240872298029611746575376322733311657394502859852213595389607239431585120943268774679785316133478171225719729917877009624611286702010936951705160870997184123775488592130586606070277173392647225589257616518666852404878425355285270687131724258281902727717116041282358028398978152480549468694659695121115046850718180640407034795656480263573773381753855724693739080045739160297875306923958599742379878734638341856117533253251168244471273520476474579680250862738227337561115160603373096699944163
q=44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223
p=34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323
n=p*q
lcm = ((p-1)*(q-1) // math.gcd(p-1,q-1))
print(lcm)
d=pow(e,-1) % lcm
print(d)
int too large to convert to floatというエラーが出てきた。
値が大きすぎてオーバーフローしてしまった。
他のやり方でdを計算してみる。
F=lcm((p-1),(q-1))
とする。dはFを法としたeの逆数であることから、以下の式が成り立つ。
de \equiv 1\; mod\; F
この計算は拡張されたユークリッド互除法で容易に求められる。
ちなみに上の式の意味は、deをFで割ったあまり＝1をFで割ったあまりであることを意味している。当然1をFで割ったあまりは1であるため、deをFで割ったあまりは1であり、0 = de-1 mod Fとも書ける。
拡張されたユークリッド互除法を使ってpythonで解いてみる。
参考：https://tech.camph.net/rsa-public-key-encryption/
import math
import binascii
def ex_euclid(x, y):
c0, c1 = x, y
a0, a1 = 1, 0
b0, b1 = 0, 1
while c1 != 0:
m = c0 % c1
q = c0 // c1
c0, c1 = c1, m
a0, a1 = a1, (a0 - q * a1)
b0, b1 = b1, (b0 - q * b1)
return a0
e=65537
n=1517330236262917595314610888889322115651087080826711948897066340883208205571592392362650858571076247939805436226544833224526137582834770402681005343930059463684528957271778199162575053306238099823295117697031968370690372250916935800738698142103275969223264184374648246277564306900886005299731265812255274723175925185522344831066577166867786835955092059346244885587228196357297758371381557924676260190209536670230008561217008649261974735505203813478978893582292682827884118215872470401293272325715864815977064075988643101088355047954735427424641386870772845440782632933485165110172437511822736907550777817722248753671107339823410418938404382732079381329288400012929311347390423061254658780185245562668131009832293474920208834795460061115101364091252176594144096675899952570380792978037217747311595899301451192342027799533264325948876556110474850761538179748318187805312451895898751337975457949549497666542175077894987697085521882531938339334715190663665300179658557458036053188152532948734992896239950564081581184284728802682982779186068791931259198917308153082917381616147108543673346682338045309449569430550618884202465809290850964525390539782080230737593560891353558335337408957948041667929154230334506735825418239563481028126435029
c=225549592628492616152632265482125315868911125659971085929712296366214355608049224179339757637982541542745010822022226409126123627804953064072055667012172681551500780763483172914389813057444669314726404135978565446282309019729994976815925850916487257699707478206132474710963752590399332920672607440793116387051071191919835316845827838287954541558777355864714782464299278036910958484272003656702623646042688124964364376687297742060363382322519436200343894901785951095760714894439233966409337996138592489997024933882003852590408577812535049335652212448474376457015077047529818315877549614859586475504070051201054704954654093482056493092930700787890579346065916834434739980791402216175555075896066616519150164831990626727591876115821219941268309678240872298029611746575376322733311657394502859852213595389607239431585120943268774679785316133478171225719729917877009624611286702010936951705160870997184123775488592130586606070277173392647225589257616518666852404878425355285270687131724258281902727717116041282358028398978152480549468694659695121115046850718180640407034795656480263573773381753855724693739080045739160297875306923958599742379878734638341856117533253251168244471273520476474579680250862738227337561115160603373096699944163
q=44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087386855491152795237153901319521506429873434336969666536995399866125781057768075533560120399184566956433129854995464893265403724034960689938351450709950699740508459206785093693277541785285699733873530541918483842122691276322286810422297015782658645129421043160749040846216892671031156465364652681036828461619272427318758098538927727392459501761203842363017121432657534770898181975532066012149902177196510416802134121754859407938165610800223
p=34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595977471949767235426490850284286661592357779825212265055931705799916913817655743434497422993498931394618832741336247426815710164342599150990608143637331068220244525541794855651643135012846039439355101027994945120698530177329829213208761057392236875366458197098507252851244132455996468628957560178868724310000317011912994632328371761486669358065577269198065792981537378448324923622959249447066754504943097391628716371245206444816309511381323
n=p*q
F = ((p-1) * (q-1)) // math.gcd(p-1, q-1)
d=ex_euclid(e,F)
m = pow(c,d,n)
print("%0512x"%m)
binascii.unhexlify('546869732069732034303936626974205253412e0a54686520666c616720697320464c41475f4e625a366751654b444d56464a4d61550a50414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050414444494e472050')
FLAGが得られた。
print ("%0512x"%m).decode("hex")でうまくデコードできなかったためbinasciiを使ってデコードした。ここからでもできる。
まとめ
RSAの復号ができた。
p、qが知られると秘密鍵が計算できてしまい第3者に復号されてしまう危険性があることがわかった。