Crypto問のRSAの簡単な復号手順、参考になるサイトをメモ。
RSA暗号
- ■ 与えられるもの
- 公開鍵：$n, e$
- 暗号文：$c$
- ■ 導くもの
- 秘密鍵：$d$
- 平文：$m$
■ 暗号化
c \equiv m^e \pmod n
■ 復号化
m \equiv c^d \pmod n
■ 式関係
\begin{gather}
n = p*q \\
\varphi(n): (p-1)*(q-1) \\
d*e \equiv 1 \pmod {\varphi(n) }
\end{gather}
※途中計算
\begin{gather}
c^d \equiv (m^e)^d \equiv m \pmod n
\end{gather}
手順
(1) nを素因数分解
ここが肝。これがクリアできれば解ける。
$n$を素因数分解し、$p$と$q$を求める。
以下のサイトでペアが見つかれば嬉しい。（誰かが素因数分解のペアを登録していないと見つからないらしい）
見つからなかった場合は、与えられた情報に素因数分解するためのヒントがあるはず。
(2) 秘密鍵dを計算
復号化の式から$d$が求まれば$m$が分かる。次の計算で$e$の逆元$d$を求める。
\begin{gather}
\varphi(n): (p-1)*(q-1) \\
d \equiv e^{-1} \pmod {\varphi(n) }
\end{gather}
(3) 復号化
次の計算で$m$を求める。
\begin{gather}
m \equiv c^d \pmod n
\end{gather}
最後に$m$を文字列に変換する。
プログラム
pythonでは次のように求められる。
pycryptodomeをインストール
pip install pycryptodome
from Crypto.Util.number import *
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())
pycryptodome関連のエラーが出た場合
pip installはできているが、下記のようなエラーが出たため、次のサイトを参考に対処した。（uninstall→installも試したが変わらず）
ModuleNotFoundError: No module named 'Crypto'
pycryptodomeが上手くいかなくても次のように16進数から2桁ごとに区切って10進数の変換を行い、対応する文字に変換すれば良い。
number = 123456
decoded_string = bytes.fromhex(hex(number)[2:]).decode('ascii')
print(decoded_string)
参考