おれさまラボの実験ノート

実際に手を動かして理解を深めるブログ。

RSA暗号のしくみを紐解いてみる

はじめに

前回に引き続き、鍵と証明書のしくみの理解を実際に手を動かしながら深めていきます。

前回までの記事はこちらを参照ください。

skkskynw.hateblo.jp

skkskynw.hateblo.jp

RSA 暗号のしくみ

今回は RSA 暗号のしくみを紐解いていきましょう。

前回の復習

秘密鍵に含まれる情報はこちらでした。

$ openssl rsa -text -in s.key
Private-Key: (16 bit)
modulus: 53297 (0xd031)
publicExponent: 65537 (0x10001)
privateExponent: 39653 (0x9ae5)
prime1: 239 (0xef)
prime2: 223 (0xdf)
exponent1: 145 (0x91)
exponent2: 137 (0x89)
coefficient: 224 (0xe0)
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MCYCAQACAwDQMQIDAQABAgMAmuUCAgDvAgIA3wICAJECAgCJAgIA4A==
-----END RSA PRIVATE KEY-----

公開鍵に含まれる情報はこちらでした。

$ openssl rsa -text -pubin < p.key
Public-Key: (16 bit)
Modulus: 53297 (0xd031)
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MB4wDQYJKoZIhvcNAQEBBQADDQAwCgIDANAxAgMBAAE=
-----END PUBLIC KEY-----

秘密鍵に含まれる情報と公開鍵に含まれる情報では、公開鍵の情報が圧倒的に少ないです。さらに、公開鍵の情報は秘密鍵の中にすべて含まれていることがわかります。

鍵の中身

RSA 暗号の難しい計算は他の人に任せるとして、鍵の中身を項目ベースでみてみましょう。

鍵の中身について簡単に表にまとめてみました。

素数 p, q

RSA 暗号は素数 p, q からはじまります。この2つの値はランダムに決まります。

RSA モジュール n

RSA モジュールは、素数 p, q から作られる合成数です。

n=p \times q が成り立ちます。

暗号化指数 e

その名の通り、暗号化または署名検証する際に使用される数値です。公開鍵をもっている側はこの値を使ってデータを暗号化または署名検証をします。

計算量削減の観点から、暗号化指数は e=65537 という固定値が使用されます。少なくとも openssl では 65537 がデフォルト値です。

この固定値は短い暗号化指数として知られており、2020 年現在においては十分な安全性が確保可能されるということが証明されているそうです。

なお、65537 はビット列で表すと 10000000000000001 というふたつの 10 が 15 個挟まれるかたちとなり、コンピュータにとって計算しやすいという理由もあるそうです。

復号化指数 d

その名の通り、復号化または署名する際に使用される数値です。この値は秘密鍵にしか含まれない情報です。秘密鍵をもっている側はこの値を使ってデータを暗号化または署名をします。

de, p, q から導かれる値です。

その他の値

exponent1, exponent2, coefficient という3つの値が残ります。これらは中国人の剰余定理(CRT: Chinese Remainder Theorem)を使って高速に複合するアルゴリズムで使われる数値です。事前にこの値を計算しておいて秘密鍵に含めておくことで、暗号化指数 e を使った計算処理量を少なくして、高速化を図っているそうです。これにより約 1/4 まで時間を短縮できるとされています。

暗号化と復号化

実際のところどのような暗号化/復号化処理が行われているのかを見てみます。

暗号化アルゴリズム

暗号化アルゴリズムは以下の数式で説明されます。

入力 元データ m
公開鍵 pk
出力 暗号文 C
動作 c=m^e mod n を計算して出力。

簡単にまとめると暗号化指数 eRSA モジュール n を使って暗号化するということです。

復号化アルゴリズム

復号化アルゴリズムは以下の数式で説明されます。

入力 暗号文 C
公開鍵 pk
秘密鍵 sk
出力 複合結果 m'
動作 m'=c^d mod n を計算して出力。

簡単にまとめると dRSA モジュール n を使って複合化するということです。

おわりに

秘密鍵で暗号化したい場合は ed にすれば良いということ?

追記(2020/03/13)

SSL/TLS ハンドシェイクを理解してなかったからトンチンカンなことを言ってしまいました。

RSA はあくまで一方向性。

SSL/TLS ハンドシェイクではサーバとクライアントそれぞれがそれぞれの秘密鍵と公開鍵を作成し、お互いの公開鍵を交換します。

サーバからクライアントへ暗号文を送るときには、クライアントの公開鍵で暗号化し、サーバからクライアントに暗号文を送り、クライアントはクライアントの作った秘密鍵で復号化します。

逆もまた然り。なるほど~。

以上