流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【RSA暗号】試しに作ってみた【Python】

オリジナル RSA暗号数学 Python 数論暗号

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

RSA暗号

自然数 $a$ を大きな素数の積 $N=pq$ と公開鍵と秘密鍵と呼ばれる自然数 $b,d$ を使う。 $b,N$ のみを使って、 $a$ を暗号と呼ばれる別の数 $c$ にしたり、元に戻したりすること。

アルゴリズム

まず、素数 $b,p,q$ を決める。 $N=pq$ を計算する。ここで、素数 $p,q$ はヒミツにしておくのがポイント。ある自然数 $k$ を用いて、

$bd=k(p-1)(q-1)+1$

つまり、

$bd\equiv \mod (p-1)(q-1)$

を満たす。 $d$ を見つける。この $d$ を秘密鍵という。

自然数 $a$ を暗号化するには、

$a^b\equiv c \mod N$

を計算する。

元に戻すには、オイラーの定理 (数論) - Wikipediaより、

$c^d \equiv a^{bd} \equiv a^{k(p-1)(q-1)+1}\equiv a \mod N$

とすれば、元の数字に戻せる。

プログラム

以下のサイトを参考にプログラムを作成した。

tex2e.github.io

gist3fba0be9c42e5b712b6d72a4b25c71d0