きっかけ

現在使われている暗号の中で、一番処理の流れを紹介しやすいのはRSAだと思っています。
特に数学が嫌いな人に暗号化/復号の説明をするとごちゃごちゃしてしまうので、頭の整理がてらアウトプットします。

検証環境

python3.7.2

実際に計算してみる

何はともあれ、まずは計算してみましょう。
鍵情報は下記を例にやってみます。

p = 8 # 平文
public_key = 3 # 公開鍵
private_key = 7 # 秘密鍵
number = 33 # 共有情報(公開してOK) ※公開鍵を(3, 33)のペア、秘密鍵を(7, 33)のペアと書くことも多いです。

Pythonでも定義しておきましょう。

>>> text = 8
>>> public_key = 3
>>> private_key = 7
>>> number = 33

暗号化

RSAの計算方法はとてもシンプルです。

平文の数字を公開鍵の回数だけ掛けます
1の計算結果を共有情報で割り、その余りを暗号文とします

簡単ですね。Pythonでは1行で書けます。

>>> encrypt = ( text ** public_key ) % number
>>> print(encrypt)
17

復号

RSAの凄いところは、復号の手順も暗号化と同じというところです。
使う鍵だけ変わります。

暗号文の数字を秘密鍵の回数だけ掛けます
1の計算結果を共有情報で割り、その余りを復号文とします(平文と一致します)

>>> decrypt = ( encrypt ** private_key ) % number
>>> print(decrypt)
8
>>> text == decrypt
True

電子署名への応用

RSAのさらに凄いところは、このアルゴリズムを電子署名にも活用できることです。
つまり、秘密鍵で暗号化して公開鍵で復号できる、ということですね。
※今回は動きだけ紹介するので、平文データでまるっと署名しています

>>> fingerprint = ( text ** private_key ) % number # 署名
>>> print(fingerprint)
2
>>> verification = ( fingerprint ** public_key ) % number # 署名検証
>>> print(verification)
8
>>> verification == text
True

解説

数学的背景(を少しだけ)

今回は数をある数字で割った余りという世界でのお話です。
今回は、number = 33 で割った余りの世界で話を進めました。

コンピュータの世界で登場する数字は日常生活と同じく無限に続くものですが、
これを「ある数で割った余り」という視点で見ることで、登場する数字は有限になります。
今回もどんな計算を行っても33で割った余りは必ず、「0 ~ 32」の33種類になります。

無限に続く数を有限個で表現しなくてはいけないので、当然計算結果には「被り」が出てきます。
10で割った余りを考えるとわかりやすいですね。1も11も21も1111もすべて、10で割った余りの世界では「1」です。

RSAでは下記のような数学的性質を利用しています(実際はもっと色々な前提条件があります)。
「mで割った余りの世界において、ある数nを何度か掛けるとn自身になる」
今回の例では、平文8を21回かけて33で割った余りは8自身になります。平文の値を変えても同様です。

>>> ( 8 ** 21 ) % 33
8
>>> ( 5 ** 21 ) % 33
5
>>> ( 19 ** 21 ) % 33
19

また掛け算のルールとして、下記実行結果のように21 = 3 × 7と分割して計算することもできます。
この場合、8を3回掛けた結果を7回掛けても、8を7回掛けた結果を3回掛けても結果は同じです。
※周りくどい言い方になっていますが、高校でやる指数計算のルールです。

>>> ( 8 ** 21 ) % 33 # 元の式
8
>>> (( 8 ** 3 ) ** 7 ) % 33 # 元の式を変形したもの
8
>>> (( 8 ** 7 ) ** 3 ) % 33 # 元の式を変形したもの
8

今回は、3と7をそれぞれ公開鍵、秘密鍵としたことによって、平文"8"とは全く異なる"17"や"2"という暗号文を作ることができ、
またそれを"8"に戻すことができたということになります。
勿論、33や21というキーナンバーは適当に作ったわけではなく、様々な数学的性質のお膳立てがあるわけなのですが、次のトピックで。

暗号の強度について

今回出てきたnumberで指定した値33は、「3 × 11」という2つの数の積から作られています。
実はこの2数がとても重要で、21回掛けるという回数もこの2数から計算で導かれたものです。
さらに言うと、鍵の3や7といった数字もこの2数から始まり計算で求まりました。
裏を返すと、numberの値が何の数の積であるかがバレると、公開鍵の情報と計算で秘密鍵が特定されます。

この2数は、素数と呼ばれる特別な整数を使用します。
素数の性質により、numberはただ1つの組み合わせからしか存在しない数となります。
暗号強度の問題からnumberはとてつもなく大きな数をとるため、その中からたった一組のペアを探し出すのは至難の業です。
ちなみにwikipedia先生によると、現在知られている素数は(10進数で)24桁の中に約184垓個存在するみたいです。
ちなみに、このペア探しは数学的に効率のいい探し方が見つかっておらず、素数リスト184垓個の総当たりと大きく変わりません。
逆に、効率の良いペア探しの方法が見つかった瞬間、RSAアルゴリズムの安全性は破綻します。

何故RSA暗号は暗号処理に時間がかかるのか？

またまたwikipedia先生によると、現在見つかっている最大の素数は(10進数で)24,862,048 桁あるそうです。
極端な話、これを使ってnumberを求めると単純計算49724096桁。さすがのコンピュータも時間がかかりますｗ

暗号強度の話とも関わりますが、この計算に時間がかかることと効率のよい探索方法が見つからないことがRSAの強みでもあるのです。

おわりに

数学用語は極力使わないようにしました。余計見づらくなった気がしなくもない。。。
前提条件の補足が足りないところも多いのですが、これでざっくりと暗号/復号の流れをイメージできたら幸いです。