ネットワークやってるくせに暗号技術全然わからなかったので覚え書き。

背景

この問題を解いていた。

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}'

以上。