ångstromCTF 2021 - Relatively Simple Algorithm

問題概要

RSA strikes strikes again again! Source

RSAにおける$n,p,q,e,c$が与えられるので、復元してね！という問題です。

解説

実は復元に必要な情報は十二分に与えられています。RSAの原理を復習すると、

• $n = pq$ で大きな素数$p,q$から$n$を生成
• $c = m^e (\mod n)$ で暗号化
• $ed = 1 (\mod (p-1)(q-1))$ となるように $d$を用意。これは拡張ユークリッドの互除法で出来ます。
• $m = c^d (\mod n)$ で復号出来る

です。$p,q,e$が既知なので$d$は求められて、$n,d,c$から$m$が求められそうですね。

solve.py

from Crypto.Util.number import *
n = 113138904645172037883970365829067951997230612719077573521906183509830180342554841790268134999423971247602095979484887092205889453631416247856139838680189062511282674134361726455828113825651055263796576482555849771303361415911103661873954509376979834006775895197929252775133737380642752081153063469135950168223
p = 11556895667671057477200219387242513875610589005594481832449286005570409920461121505578566298354611080750154513073654150580136639937876904687126793459819369
q = 9789731420840260962289569924638041579833494812169162102854947552459243338614590024836083625245719375467053459789947717068410632082598060778090631475194567
e = 65537
c = 108644851584756918977851425216398363307810002101894230112870917234519516101802838576315116490794790271121303531868519534061050530562981420826020638383979983010271660175506402389504477695184339442431370630019572693659580322499801215041535132565595864123113626239232420183378765229045037108065155299178074809432

d = inverse(e, (p-1) * (q-1))
m = pow(c, d, n)
print(long_to_bytes(m, 64))