ネットワークやってるくせに暗号技術全然わからなかったので覚え書き。
背景
この問題を解いていた。
RSAをざっくり理解する
最初に与えられた文字列
Decrypt my super sick RSA:
c: 240986837130071017759137533082982207147971245672412893755780400885108149004760496
n: 831416828080417866340504968188990032810316193533653516022175784399720141076262857
e: 65537
wikiをもとに計算する
https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7
m = c^d \mod{n}
ここでmが複合文となるので、未知数dを求めなくてはならない。
dの定義は以下である。
d = e^{-1} \mod{\phi} \\
φは以下で表せる。
\phi = \mathrm{lcm}(p-1,q-1) \\
n = p * q
lcmは最小公倍数を表す。
lcmはpythonのmathモジュールのlcm関数で計算できる。
ここまでで、pとqを計算できれば未知数dを求められることが分かった。
pとqを求める
ここで、nを素因数分解することを考えてみる。
素因数分解は前の記事を参考に。
mseiveを使用してnを素因数分解すると、以下の結果が得られた。
p40 factor: 1593021310640923782355996681284584012117
p42 factor: 521911930824021492581321351826927897005221
nは2つの素数の積だったため、うまくpとqが一意に定まった。
秘密鍵dを求める
次に秘密鍵dを計算する
d = e^{-1} \mod{\phi} \\
ここでポイントなのが、
e^{-1} \neq \frac{1}{e}
という点。
これはモジュラ逆数というものらしい。
組み込み関数で頑張りたかったが見つけられなかったので、ネットに落ちてた関数を使用
これで秘密鍵dが求まった。
複合文mを求める
mを計算できればほぼゴール。
m = c^d \mod{n}
桁数の多い数のpython計算モジュールのgmpyに、ちょうどよい関数があった。
windowsではgmpy2しか入らなかったので注意。
pip install gmpy2
>>> m = gmpy2.powmod(c,d,n)
>>> m
mpz(13016382529449106065927291425342535437996222135352905256639592405461024281868413)
逆が成り立つことも確認した。
>>> gmpy2.powmod(m,e,n)
mpz(240986837130071017759137533082982207147971245672412893755780400885108149004760496)
複合文mを文字列に変換する
正直ここにも時間をかけてしまったのだが、案外単純だった。
数値をバイト列に変換する。
長さは決め打ちで入れたがうまいやり方があるのかもしれない。
>>> m.to_bytes(100,'big')
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00picoCTF{sma11_N_n0_g0od_23540368}'
以上。