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

はじめに

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

はじめに
RSA 暗号のしくみ
おわりに
追記（2020/03/13）

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

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$ というふたつの $1$ に $0$ が 15 個挟まれるかたちとなり、コンピュータにとって計算しやすいという理由もあるそうです。

復号化指数 $d$

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

$d$ は $e, p, q$ から導かれる値です。

その他の値

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