OpenSSLで実際のRSA秘密鍵を作り、n・e・d・p・qが本物の鍵にも存在することを確認。さらにDP・DQ・InverseQと中国剰余定理の関係を、小さな数字で追います。
暗号化と認証④
OpenSSLとC#でRSA鍵の中身を見る
前回は、小さな数字を使ってRSAの鍵を作りました。
p = 5 q = 11 n = p × q = 55 φ(n) = 40 e = 3 d = 27
そして、
公開鍵 = (n, e) 秘密鍵 = (n, d)
として、暗号化した値が秘密鍵で元に戻ることを確認しました。さらに、13²⁷ mod 55 を紙で追い、C#では BigInteger.ModPow(13, 27, 55) で同じ計算ができるところまで見ました。
ここで少し気になります。
前回、紙の上で使った n、e、d、p、q は、本物のRSA鍵にも本当に入っているのでしょうか。
今回は、実際にRSA鍵を作って中を見てみます。使うのはOpenSSLとC#です。
今回作る秘密鍵は、この記事の実験用です。実際に使用している秘密鍵の内容を、画面やログ、ブログなどへ出してはいけません。
OpenSSLでRSA鍵を作る
まず、OpenSSLで2048bitのRSA秘密鍵を作ります。
Bash
openssl genpkey \
-algorithm RSA \
-pkeyopt rsa_keygen_bits:2048 \
-out rsa-private.pemこれで rsa-private.pem という秘密鍵ができます。では、中を見てみます。
Bash
openssl pkey \
-in rsa-private.pem \
-text \
-noout数字そのものは非常に長いので、項目名だけ抜き出すと、こんなものが表示されます。
modulus publicExponent privateExponent prime1 prime2 exponent1 exponent2 coefficient
前回より多い。ただし、上の5つには見覚えがあります。
前回の n、e、d、p、q が本当にあった
OpenSSL RSA modulus → n publicExponent → e privateExponent → d prime1 → p prime2 → q
前回、紙の上で使った n、e、d、p、q が、本物のRSA秘密鍵にもちゃんと入っています。
でも exponent1、exponent2、coefficient って何？
ここで、知らないものが残ります。exponent1、exponent2、coefficient です。C#側では、それぞれ DP、DQ、InverseQ という名前で出てきます。
DP、DQ、InverseQ は、前回一瞬だけ触れた中国剰余定理（CRT）を使って、RSAの秘密鍵演算を効率よく行うための値です。このあと、小さな数字を使って実際に確かめます。
ここではまだ式を覚えなくて大丈夫です。
同じ秘密鍵をC#から読んでみる
OpenSSLで作った rsa-private.pem を、そのままC#から読み込んでみます。
C#
using System.Security.Cryptography;
string pem =
File.ReadAllText("rsa-private.pem");
using RSA rsa = RSA.Create();
rsa.ImportFromPem(pem);
RSAParameters parameters =
rsa.ExportParameters(true);ExportParameters(true) とすると、公開鍵だけでなく、秘密鍵側のパラメータも取得できます。
parameters.Modulus parameters.Exponent parameters.D parameters.P parameters.Q parameters.DP parameters.DQ parameters.InverseQ
OpenSSLとC#で名前は違いますが、同じRSA鍵を見ています。
D、P、Q、DP、DQ、InverseQ は秘密情報です。実際に使用している秘密鍵で値そのものを表示したり、ログへ出したりしないようにします。
なぜ秘密鍵に P と Q まで残してあるのか
前回、RSAの復号は m = c^d mod n でした。そして秘密鍵は (n, d) と考えました。
それなら n と d だけ持っていれば十分に見えます。鍵を作るときに使った p と q は捨ててもよさそうです。まして DP、DQ、InverseQ まで保存してある理由は、まだ分かりません。
ここで出てくるのが、中国剰余定理です。
中国剰余定理とは
中国剰余定理は、いくつかの「割った余り」が分かれば、元の数をある範囲の中で一つに絞れるという考え方です。
例えば、ある整数 x について、
x ≡ 3 mod 5 x ≡ 1 mod 11
だとします。5で割ると3余る数は 3, 8, 13, 18, 23, 28, ...。11で割ると1余る数は 1, 12, 23, 34, 45, ...。最初に両方へ現れるのは23です。
ただし23だけではなく、78、133、188……と55ごとにまた現れます。つまり、
x ≡ 23 mod 55
と一つに決まります。5と11は互いに素で、5 × 11 = 55。55を足しても5でも11でも余りは変わりません。
ちなみに「中国剰余定理」という名前はかなり古く、その原型は古代中国の数学書『孫子算経』の「割った余りから元の数を求める」問題まで遡ります。今回のアイキャッチにも、その漢文を使っています。
これをRSAに使う
ここで前回のRSAへ戻ります。
p = 5 q = 11 n = p × q = 55
つまり、mod 55 の世界を、mod 5 と mod 11 の二つに分けられます。RSAの復号 c^d mod 55 をいきなり計算する代わりに、P側とQ側で別々に計算し、最後に中国剰余定理で一つに戻します。
DP と DQ を作る
前回の鍵は p = 5、q = 11、d = 27 でした。
DP = d mod (p - 1) = 27 mod 4 = 3 DQ = d mod (q - 1) = 27 mod 10 = 7
ここまでで、P = 5、Q = 11、DP = 3、DQ = 7 です。
InverseQ も作る
InverseQ は、Q × InverseQ ≡ 1 mod P となる値です。今回なら 11 × InverseQ ≡ 1 mod 5。11を5で割った余りは1なので、今回は InverseQ = 1 で成立します。
Modulus = 55 Exponent = 3 D = 27 P = 5 Q = 11 DP = 3 DQ = 7 InverseQ = 1
OpenSSLやC#で出てきた値を、小さな数字でも全部作れました。
本当にこれで復号できるのか
では、実際に試します。同じRSA鍵を使い、今回は平文を m = 23 とします。公開鍵は (n, e) = (55, 3) なので、暗号化すると、
c = 23³ mod 55 = 12
普通に復号するなら 12²⁷ mod 55 を計算します。今回は、それを二つに分けます。
P側で計算する
12³ mod 5 = 2³ mod 5 = 8 mod 5 = 3
Q側で計算する
12⁷ mod 11 = 1⁷ mod 11 = 1
つまり、
m ≡ 3 mod 5 m ≡ 1 mod 11
です。これは、さっき中国剰余定理の説明で使ったものと同じです。したがって m ≡ 23 mod 55。元の平文23に戻りました。
実際のRSA実装では、候補を一つずつ並べて23を探すわけではありません。InverseQ を使えば、二つの結果から直接合成できます。
今回なら h = (3 - 1) × 1 mod 5 = 2、m = 1 + 11 × 2 = 23 です。
だから秘密鍵に P、Q、DP、DQ、InverseQ がある
これで、最初の疑問へ戻れます。RSA秘密鍵に P、Q、DP、DQ、InverseQ まで入っているのは、秘密鍵演算をP側とQ側に分け、中国剰余定理を使って合成できるようにするためです。
教科書では 秘密鍵 = (n, d) と考えるだけでもRSAの仕組みは理解できます。実際の鍵には、効率よく計算するための情報も一緒に入っています。
では、この中国剰余定理の処理はC#の標準ライブラリのどこにあるのでしょうか。
この点は③と同じです。RSA.Decrypt() などの実際のRSA秘密鍵演算は、.NETのC#コードだけで完結せず、OS側の暗号実装に委ねられています。そのため、C#の標準ライブラリを追っても、今回の中国剰余定理の計算がそのまま出てくるわけではありません。
Linuxでは、さらにOpenSSLのソースまで降りると、p、q、dmp1、dmq1、iqmp を使ったCRTの処理を確認できます。
……ただし、そこから先はCのコードです。C#じゃないので、今回は「本当に使われている」ことだけ確認して撤退します。
では「秘密鍵 = (n, d)」は間違いだったのか
いいえ。前回はRSAの数学を理解するために (n, e) と (n, d) を使いました。今回はそこから一段下へ降りて、実際の鍵に入っている p、q、DP、DQ、InverseQ まで見ています。見ている深さが違うだけです。
まとめ
今回は、OpenSSLでRSA秘密鍵を作り、その中身をC#からも確認しました。前回使った n、e、d、p、q は、本物のRSA鍵にも実際に存在しました。
さらに DP、DQ、InverseQ という値がありました。これらは、中国剰余定理を使って秘密鍵演算を分けて計算するために使われます。
中国剰余定理は、いくつかの「割った余り」が分かれば、元の数をある範囲の中で一つに絞れるという考え方です。
今回なら、mod 5では3、mod 11では1という二つの情報から、mod 55では23と決まりました。
前回はRSAの数式を追いました。今回は、その数式が実際の鍵の中にどう現れているのかを追いました。
次回
RSA鍵の中身はかなり見えてきました。しかし、公開鍵暗号にはまだ大きな問題があります。
その公開鍵は、本当に相手のものなのか。
公開鍵をすり替えられてしまえば、暗号化そのものが正常に動いていても、安全とは言えません。そこで登場するのが電子証明書です。
次回は、暗号化と認証⑤ ― 誰の紹介なら、その公開鍵を信用できるのか。ルート証明書・中間証明書・証明書チェーンを実際に追ってみます。