暗号化と認証③
― RSAを小さな数字から理解する 公開鍵と秘密鍵はどうやって作られるのか
前回は、C#でRSAの鍵ペアを作りました。
using RSA juliet = RSA.Create(2048);たったこれだけです。
さらに公開鍵だけを取り出して相手へ渡し、
Encrypt(...)
Decrypt(...)を使えば、実際に暗号化と復号もできました。
便利です。
でも、ここで一つ疑問が残ります。
RSA.Create()は、いったい何を作っているのか。
前回は、公開鍵と秘密鍵を数学的に関係した1組の鍵と説明しました。
では、その「数学的な関係」とは何なのでしょう。
今回は、公開鍵暗号の代表例であるRSAを、あえて手で計算できるほど小さな数字まで縮めて、その中身を追ってみます。
今回使うRSAは、仕組みを理解するための教科書用のおもちゃRSAです。
実際の通信に使える安全性はありません。
ただし、鍵がどう作られるのか、公開鍵で暗号化すると何が起きるのか、秘密鍵でなぜ元へ戻るのか、そしてC#のライブラリでは何が起きているのかを見るには十分です。
まず2つの素数から鍵を作る
RSAの鍵作りは、2つの素数から始まります。
今回は、
p = 5 q = 11
とします。
まず、この2つを掛けます。
n = p × q = 5 × 11 = 55
この n = 55 は、公開鍵にも秘密鍵にも使われる重要な数字です。
次に、
φ(n) = (p - 1)(q - 1) = 4 × 10 = 40
を求めます。
ここまでで、
p = 5 q = 11 n = 55 φ(n) = 40
公開鍵の e を決める
次に、公開鍵で使う数字 e を選びます。
ここでは、
1 < e < φ(n) かつ gcd(e, φ(n)) = 1
となる数字を選びます。つまり、φ(n) と互いに素な数字です。
今回は、
e = 3
3 と 40 の最大公約数は1なので、条件を満たします。
これで公開鍵は、
(n, e) = (55, 3)
となります。
では秘密鍵の d はどうやって決める？
次は、秘密鍵で使う d です。
d は、
e × d ≡ 1 mod φ(n)
となるように選びます。今回なら、
3 × d ≡ 1 mod 40
です。d = 27 とすると、
3 × 27 = 81 81 = 40 × 2 + 1
なので、
81 ≡ 1 mod 40
となります。したがって、
d = 27
です。これで、
公開鍵 = (55, 3) 秘密鍵 = (55, 27)
ができました。
前回、C#では、
RSA.Create(2048)と一行書くだけでRSA鍵を作りました。今回やっているのは、その下に隠れていた数学を、数字を小さくして見えるようにしたものです。
作った鍵で実際に暗号化してみる
鍵を作っただけでは面白くありません。実際に暗号化してみます。
平文を、
m = 7
とします。教科書的なRSAの暗号化は、
c = m^e mod n
です。今回の値を入れると、
c = 7^3 mod 55 = 343 mod 55
となります。343は、
343 = 55 × 6 + 13
なので、
c = 13
です。つまり、
平文 7 ↓ 公開鍵 (55, 3) で暗号化 ↓ 暗号文 13
となりました。ここまでは簡単です。問題は復号です。
では 13²⁷ mod 55 をどう計算する？
秘密鍵は、
(n, d) = (55, 27)
でした。教科書的なRSAの復号は、
m = c^d mod n
です。したがって、
m = 13^27 mod 55
を計算すればよいことになります。
……27乗。
13 × 13 × 13 × 13 × …
と27回掛けても計算できます。でも、あまりやりたくありません。
しかも本物のRSAで扱う数字は、こんなものではありません。そこで、先に2つだけ確認します。
掛け算でも余りに置き換えてよい
例えば、
a₁ ≡ c₁ mod b a₂ ≡ c₂ mod b
だとします。すると、
a₁ = bI₁ + c₁ a₂ = bI₂ + c₂
と書けます。この2つを掛けると、
a₁a₂ = (bI₁ + c₁)(bI₂ + c₂) = b(bI₁I₂ + I₁c₂ + I₂c₁) + c₁c₂
です。したがって、
a₁a₂ ≡ c₁c₂ mod b
になります。
掛け算では、元の数を余りに置き換えて計算してよい。
掛け算の途中で mod を取ってもよい
もう一つ使う性質があります。例えば、
c₁c₂ = bI + r
だったとします。さらに c₃c₄ を掛けると、
c₁c₂c₃c₄ = (bI + r)c₃c₄ = bIc₃c₄ + rc₃c₄
です。最初の項は b の倍数なので、mod b を考えると消えます。したがって、
c₁c₂c₃c₄ ≡ rc₃c₄ mod b
です。
つまり、掛け算を全部終えるまで巨大な数字を保持する必要はありません。途中で、
modを取る ↓ 余りだけ残す ↓ 続きを計算する
として構いません。
① 掛け算では 元の数を余りに置き換えてよい ② 掛け算の途中でも modを取って余りだけ残してよい
13²⁷ mod 55 を効率よく計算する
27は、
27 = 16 + 8 + 2 + 1
と分解できます。つまり、
27 = 2⁴ + 2³ + 2¹ + 2⁰
です。そこで、
13¹ 13² 13⁴ 13⁸ 13¹⁶
を順番に作ります。
13² = 169 = 55 × 3 + 4
なので、
13² mod 55 = 4
です。次は、
13⁴ mod 55 = 4² mod 55 = 16
さらに、
13⁸ mod 55 = 16² mod 55 = 256 mod 55 = 36
さらに、
13¹⁶ mod 55 = 36² mod 55 = 1296 mod 55 = 31
となります。整理すると、
13¹ mod 55 = 13 13² mod 55 = 4 13⁴ mod 55 = 16 13⁸ mod 55 = 36 13¹⁶ mod 55 = 31
27は 16 + 8 + 2 + 1 だったので、
13²⁷ mod 55 = 13¹⁶ × 13⁸ × 13² × 13 mod 55
です。ここでも途中で余りを取ります。
31 × 36 = 1116 1116 mod 55 = 16
次に、
16 × 4 = 64 64 mod 55 = 9
最後に、
9 × 13 = 117 117 mod 55 = 7
です。したがって、
13²⁷ mod 55 = 7
元の平文に戻りました。
平文 7 ↓ 公開鍵 (55, 3) 暗号文 13 ↓ 秘密鍵 (55, 27) 平文 7
ここでC#に戻ってみる
ここまで、かなり長い時間を使って、
13²⁷ mod 55
を計算しました。ところがC#なら、同じべき剰余計算は一行です。
C#
using System.Numerics;
BigInteger result =
BigInteger.ModPow(13, 27, 55);
Console.WriteLine(result);結果は、
7
です。
終わりました。さっきまで黒板いっぱい使っていた計算が一行です（笑）。
では、この一行の中では何が行われているのでしょう。
BigInteger.ModPow() の中を追ってみる
ここで、.NETのソースコードを追ってみます。
BigInteger.ModPow() から内部実装へ降りていくと、べき剰余計算を行う処理にたどり着きます。現在の.NETには、数値や法の大きさによって複数の経路があります。
今回の 13²⁷ mod 55 のような小さな例を追うと、そこにはsquare-and-multiply（繰り返し二乗法）の考え方が現れます。
つまり、先ほど紙の上でやった計算と同じ発想です。
該当する処理を、細部を省いて流れだけ要約すると、次のようになります。
C#
while (power != 0)
{
if ((power & 1) == 1)
{
result =
(result * value) % modulus;
}
if (power != 1)
{
value =
(value * value) % modulus;
}
power >>= 1;
}やっていることを順番に見ると、
指数の最下位bitを見る ↓ 1なら現在のvalueをresultへ掛ける ↓ modを取る valueを二乗する ↓ modを取る 指数を右へ1bitずらす ↓ 繰り返す
です。
例えば 27 は2進数では、
11011
です。これは、
16 + 8 + 2 + 1
に対応します。さきほど紙の上で 13¹, 13², 13⁴, 13⁸, 13¹⁶ を作り、必要なものだけ掛け合わせたのと同じ発想です。
参考：.NETのBigIntegerCalculator.PowMod.cs
これは「BigInteger.ModPow() は常にこの数行だけで実装されている」という意味ではありません。
現在の.NET実装は、値や法の大きさなどによって処理を分けています。実装は将来変更される可能性もあります。
ここで大切なのは、今回の小さな例では、指数のbitを見ながら、二乗と乗算を行い、その都度modを取るという考え方が実際のライブラリ実装にも現れる、という点です。
紙でやった計算が、ライブラリの中にあった
ここまでの流れを振り返ると、最初は、
13²⁷ mod 55
をどう計算すればよいのか分かりませんでした。
そこで、掛け算では余りに置き換えてよいこと、途中でmodを取ってよいことを確認し、
27 = 16 + 8 + 2 + 1
と分解して、繰り返し二乗法で 7 までたどり着きました。
C#なら、
BigInteger.ModPow(13, 27, 55)の一行です。
さらに.NETのソースまで追ってみると、そこにもsquare-and-multiplyの考え方がありました。
紙で考えた
繰り返し二乗法
↓
BigInteger.ModPow()
↓
.NETのソースを追う
↓
指数のbitを見る
↓
必要なら掛ける
↓
二乗する
↓
modを取る
ライブラリが一行で隠していた処理の中に、さっき自分で追った数学がちゃんとありました。
では RSA.Decrypt() も BigInteger.ModPow() を使っているのか
ここまで来ると、次の疑問が出てきます。前回は、
C#
byte[] plainText =
juliet.Decrypt(
cipherText,
RSAEncryptionPadding.OaepSHA256
);と書きました。
RSAの数学では、
c^d mod n
を計算するのですから、
RSA.Decrypt()の中でもBigInteger.ModPow(cipher, d, n)を呼んでいるのでは？
と思いたくなります。ところが、ここで話が変わります。
.NETの実用RSA処理は、BigInteger.ModPow() を使ってC#側で教科書どおりのRSAを組み立てているわけではありません。
Microsoftのドキュメントでは、RSAの鍵生成と鍵演算はプラットフォームの暗号ライブラリを利用すると説明されています。WindowsではCNG、LinuxではOpenSSLが使われます。これは実装詳細であり、将来変更される可能性があります。
BigInteger.ModPow()
↓
.NETの汎用数値演算
↓
べき剰余を計算
RSA.Decrypt()
↓
.NETのRSA API
↓
OS / ネイティブ暗号実装
↓
Windows : CNG
Linux : OpenSSL
など
参考：Microsoft Learn – Cross-platform cryptography
つまり、
BigInteger.ModPow(cipher, d, n)はRSAの数学を理解するには非常に便利です。
しかし、
RSA.Decrypt(...)の代用品として自分で書くものではありません。
なぜ実用のRSAは暗号ライブラリへ任せるのか
理由は、単にネイティブコードの方が速いから、だけではありません。
暗号処理では、正しい答えが出ることだけでは不十分だからです。
例えば、RSAの秘密鍵を使う処理では、
c^d mod n
の d が秘密情報です。
先ほど見たsquare-and-multiplyをそのまま考えると、
指数のbitが1 ↓ 掛け算する 指数のbitが0 ↓ 掛け算しない
という分岐があります。
もし秘密指数 d のbitによって処理時間にわずかな違いが生まれ、それを攻撃者が何度も観測できたら、秘密鍵についての情報が漏れる可能性があります。
これがタイミング攻撃と呼ばれる、サイドチャネル攻撃の一種です。
BigInteger.ModPow(cipher, d, n)でRSAの数式を再現できることと、それを秘密鍵処理として安全に使えることは別の話です。
BigInteger.ModPow() は、秘密鍵演算専用のAPIではありません。
OpenSSLには、秘密の指数を扱うことを想定し、データ依存性を減らすための定数時間向けべき剰余処理があります。
RSAではさらに、blinding と呼ばれるタイミング攻撃対策も使われます。
つまり、実用のRSAには、
RSAの数学 ＋ パディング ＋ 高速化 ＋ サイドチャネル対策 ＋ 鍵の安全な取り扱い
まで必要になります。
BigInteger.ModPow()
↓
RSAの数学を理解するための
観測装置
RSA.Decrypt()
↓
実際に秘密を扱う暗号処理
↓
実績のある
暗号ライブラリへ任せる
理解するためには自分で再現する。実際に守るときには、暗号ライブラリへ任せる。
自分で中身を追ったからこそ、なぜ任せる必要があるのかも見えてきます。
なぜちゃんと元に戻るのか
さて、数学へ戻ります。ここまで、
7 ↓ 7³ mod 55 ↓ 13 ↓ 13²⁷ mod 55 ↓ 7
となることを確認しました。これは偶然ではありません。
今回、
e = 3 d = 27
なので、
e × d = 3 × 27 = 81
です。そして、
81 = 1 + 2 × 40
でした。つまり、
ed ≡ 1 mod φ(n)
となるように d を選んでいます。
暗号化したものを復号すると、
(m^e)^d = m^(ed)
です。今回なら、
7^81
になります。
また、
φ(55) = 40
でした。7 と 55 は互いに素なので、オイラーの定理から、
7^40 ≡ 1 mod 55
です。したがって、
7^81 = 7^(1 + 2×40) = 7 × (7^40)^2 ≡ 7 × 1² ≡ 7 mod 55
となります。だから元へ戻ります。
RSAをすべての場合について厳密に説明すると、ここから中国剰余定理なども関係してきます。
この記事では、e と d を、暗号化した値が復号で元へ戻るよう数学的に関係づけて選んでいるというところまで分かれば十分です。
でも、公開鍵から秘密鍵を計算できないの？
公開鍵は、
(n, e) = (55, 3)
です。n = 55 を見れば、
55 = 5 × 11
と簡単に分かります。つまり、
p = 5 q = 11
です。すると、
φ(n) = (5 - 1)(11 - 1) = 40
も分かります。
φ(n) が分かれば、
3d ≡ 1 mod 40
から、
d = 27
を求められます。今回のおもちゃRSAでは、秘密鍵はほとんど丸見えです。
では、本物のRSAはなぜ成立するのでしょう。
実用のRSAでは、p と q に非常に大きな素数を使います。
公開されている、
n = p × q
から p と q を求める、つまり大きな整数の素因数分解の難しさがRSAの安全性と深く関係しています。
実用RSAは、この記事の
m^e mod n
だけを裸で使うものではありません。前回C#で使ったように、暗号化ではRSA-OAEP、署名ではRSA-PSSなど、用途に応じた方式を使います。
では「秘密鍵で暗号化」が署名なのか
RSAの数式まで見ると、前回の記事で扱った疑問がもう一度出てきます。
公開鍵で暗号化して秘密鍵で復号する。
逆に秘密鍵で暗号化して公開鍵で戻すのが署名。
と説明されることがあります。数学の対応関係を見る入口としては分かりやすい説明です。
しかし、実際の電子署名をそのまま秘密鍵による暗号化と考えるのは正確ではありません。
前回、C#では、
Encrypt(...)
Decrypt(...)と、
SignData(...)
VerifyData(...)は別のAPIでした。
署名ではメッセージ全体を単純に秘密鍵で暗号化しているのではありません。前回使ったRSA-PSSなら、
メッセージ ↓ ハッシュ ↓ RSA-PSSの署名処理 ↓ 署名
となります。
RSAの根底にある数学には対応関係がある。
しかし、実際のRSA暗号化とRSA署名は同じ処理ではない。
まとめ
今回は、前回C#で一行だった、
RSA.Create(2048)の下へ降りてみました。
p = 5
q = 11
↓
n = 55
φ(n) = 40
↓
e = 3
d = 27
↓
公開鍵 = (55, 3)
秘密鍵 = (55, 27)
↓
平文 7
↓ 暗号化
暗号文 13
↓ 復号
平文 7
という流れが見えてきます。
そして、
13²⁷ mod 55
という一見大変な計算も、
余りに置き換える ＋ 途中でmodを取る ＋ 指数を2のべき乗へ分解する
ことで効率よく計算できました。
C#なら、
BigInteger.ModPow(13, 27, 55)の一行です。
しかし、今回はそこで終わらず、.NETのライブラリまで追いました。
紙で使った 繰り返し二乗法 ↓ BigInteger.ModPow() ↓ .NETの実装 ↓ square-and-multiply
と、同じ考え方が出てきました。
さらに、
BigInteger.ModPow() ≠ RSA.Decrypt() の実装そのもの
だということも分かりました。
BigInteger.ModPow() は汎用的な数値演算です。一方、実際のRSA鍵演算はOSの暗号ライブラリへ委譲され、パディングや高速化だけでなく、タイミング攻撃などのサイドチャネルまで考慮する必要があります。
RSA.Create()
↓
中身が気になる
小さなRSAを手計算
↓
13²⁷ mod 55 が出てくる
繰り返し二乗法
↓
7まで計算できた
BigInteger.ModPow()
↓
C#なら一行
.NETのソースを追う
↓
同じsquare-and-multiplyが出てくる
ではRSA.Decrypt()も同じ？
↓
そこは違う
実用RSAは
OS / ネイティブ暗号実装へ
↓
高速性だけでなく
サイドチャネル対策も必要
ライブラリが一行で隠してくれる処理の下には、理解できる数学がある。
そして、その数学が分かったからこそ、なぜ実用の暗号処理を、自作せず暗号ライブラリへ任せるのかまで見えてきました。
次回
ここまで、教科書上のRSA秘密鍵を、
(n, d)
と書いてきました。
なら、本物のRSA秘密鍵をC#で覗いたら、n と d だけが入っているのでしょうか。
実際に.NETで秘密鍵を取り出すと、
Modulus Exponent D P Q DP DQ InverseQ
という値が出てきます。
ここで、また新しい疑問が出てきます。
復号は
c^d mod nだったはずなのに、
なぜ P、Q、DP、DQ、InverseQ まで必要なのか。
次回は、OpenSSLとC#で本物のRSA鍵を作って、その中身を実際に覗きます。
教科書では (n,d) とだけ書いていた秘密鍵が、実装の世界ではどうなっているのかを追ってみます。