共通鍵暗号と公開鍵暗号を図解する

この記事は riku-kobayashi.jpに掲載した記事の転載です。

暗号化と一口に言っても、実は仕組みが全く違う2つの方式があります。暗号化と復号に同じ鍵を使うか、別々の鍵を使うか、という違いです。

この記事ではこの2方式を整理します。TLSのハンドシェイクや証明書チェーンの仕組みは、この2つの組み合わせが前提になっています。

共通鍵暗号（対称鍵暗号）

暗号化する側と復号する側が、同じ鍵を使う方式です。

代表的なアルゴリズムはAESです。計算がシンプルなぶん高速で、大量のデータを暗号化するのに向いています。

弱点は、この鍵Kをどうやって送信者・受信者の両方が安全に持てるようにするかです。

事前に会って手渡しできるなら簡単ですが、ネットワーク越しにやり取りする場合、鍵そのものを平文で送れば盗聴されて終わりです。

これを鍵配送問題と呼びます。

公開鍵暗号（非対称鍵暗号）

鍵配送問題を解決するために考えられたのが公開鍵暗号です。

鍵が2つ1組の鍵ペア（公開鍵・秘密鍵）になっていて、片方で暗号化したものはもう片方でしか復号できません。

公開鍵は誰に見られてもよく、秘密鍵は本人だけが持ちます。この鍵ペアには2通りの使い方があります。

使い方1: 暗号化

相手の公開鍵で暗号化すると、相手の秘密鍵でしか復号できません。

公開鍵は誰に見られても構わないので、事前に安全な経路で共有しておく必要がありません。鍵配送問題が起きないのはこのためです。

暗号化・復号の仕組み

なぜ片方の鍵で暗号化したデータが、もう片方の鍵でしか復号できないのか。

これはある計算は簡単にできるが、その逆算は現実的な時間では終わらないという数学的な性質を利用しています（一方向性関数、鍵を知っていれば逆算できることからトラップドア関数とも呼ばれます）。

小さい数で計算量の非対称さを比べてみます。

61 × 53 = 3233 は一瞬で計算できますが、逆に3233だけを渡されて2つの素数の積に分解するとすると、2から順に割り切れるか試していくしかありません。

実際のRSAでは300桁を超える数を使うため、この総当たりが現実的な時間では終わらなくなります。

実際に暗号化・復号でやっている計算は、mod演算を使った累乗（ある数を何乗かした結果を、別の数で割った余りを求める計算）です。

同じ p=61, q=53 の例で、鍵を作るところから暗号化・復号まで実際にやってみます。

鍵を作る

1. N = p × q = 61 × 53 = 3233 → 公開鍵に入る数
2. φ(N) = (p−1) × (q−1) = 60 × 52 = 3120 → p, q を知っている人だけが計算できる数
3. e を1つ選ぶ（例: e = 17）→ 公開鍵は (N, e) = (3233, 17)
4. e × d を φ(N) で割った余りが1になるような d を計算する（例: d = 2753）→ 秘密鍵は d = 2753

暗号化・復号する

メッセージを m = 65 とすると（実際には文字列を数値に変換してから使います）:

• 暗号化: c = m^e mod N = 65¹⁷ mod 3233 = 2790
• 復号: m = c^d mod N = 2790²⁷⁵³ mod 3233 = 65（元に戻った）

なぜ元に戻るのか。

復号の式 m = c^d mod N に、暗号化の式 c = m^e mod N をそのまま代入してみます。

m = c^d mod N

= (m^e mod N)^d mod N

= m^e×d mod N

なぜ (m^e mod N)^d mod N = m^e×d mod N と言えるのか

小さい数で確認してみます。a = 7, N = 5, d = 3 とすると、7 mod 5 = 2 です。

7×7×7 の中の「7」を、余りの「2」に1つずつ置き換えていってみます。

7×7×7

≡ 2×7×7 （1つ目の7を2に置き換え）

≡ 2×2×7 （2つ目の7を2に置き換え）

≡ 2×2×2 （3つ目の7を2に置き換え）

（すべて mod 5 で考える）

実際に計算すると 343 → 98 → 28 → 8 と値そのものは変わっていきますが、5で割った余りはどの段階でも3のまま変わりません（343, 98, 28, 8 はすべて5で割ると3余ります）。

なぜ置き換えても余りが変わらないかというと、7と2の差は5（Nの倍数）なので、どこか1箇所を7から2に置き換えると、全体の値はちょうど5の倍数ぶんだけ変わるからです（例: 7×7×7 − 2×7×7 = (7−2)×7×7 = 5×7×7、5の倍数）。

5の倍数だけ増減しても、5で割った余りは変わりません。これを3箇所とも置き換え終わると、7³ mod 5 = 2³ mod 5 が成り立ちます。

これと同じことを c = m^e mod N に当てはめると、(m^e mod N)^d mod N と (m^e)^d mod N は同じ値になります。

だから c^d mod N は m^e×d mod N と置き換えられます。

つまり暗号化してから復号するという一連の操作は、まとめると m^e×d mod N を計算していることと同じです。

実際にこの式を計算してみると、次のようになります。

m^e×d mod N

= 65⁴⁶⁸⁰¹ mod 3233

= 65^{(15×3120 + 1)} mod 3233　（d の定義より）

= (65³¹²⁰)¹⁵ × 65 mod 3233

= 1¹⁵ × 65 mod 3233　（オイラーの定理より 65³¹²⁰ ≡ 1 mod 3233）

= 65

なぜこのように変形できるのか、順を追って見ていきます。

d は、e × d を φ(N) で割った余りが1になるように選んだ数でした（鍵を作る手順の4番目）。

だから e × d = 17 × 2753 = 46801 は必ず X × 3120 + 1 の形になり（実際に計算すると X = 15）、φ(N)=3120 で割ると余りが1になります。

つまり m を (e×d) 乗するのは、m を φ(N) 乗する操作を15回繰り返してから、最後にもう1回 m をかけるのと同じです。

ここでm を φ(N) 乗すると mod N で 1 に戻るという数論の性質（オイラーの定理）を使います。これは m と N が互いに素（1以外に共通の約数を持たない）なときに成り立つ性質です。

今回の例では m=65=5×13, N=3233=61×53 で、共通の素因数がないので条件を満たしています（RSAでは m は N=p×q より小さい値として扱われ、実用上ほとんどの m でこの条件は成立します）。

この性質自体の証明はここでは省きます（初等的な証明はこちら）。

ポイントは、d を計算するには φ(N) が必要で、φ(N) を計算するには p, q が必要という点です。

N だけから p, q を求めようとすると、上で見た素因数分解と同じ壁にぶつかります。公開鍵から理論上は秘密鍵（d）を計算できてしまうのですが、素因数分解に何百年、何千年とかかるため事実上不可能、という前提の上に成り立っています。

使い方2: 署名

逆に、自分の秘密鍵で署名すると、誰でも自分の公開鍵でその署名を検証できます。

秘密鍵を持っている本人にしか署名は作れませんが、検証は公開鍵さえあれば誰でもできます。

このデータは確かに本人が作ったことを第三者が確認できる、という性質です。これはTLSの証明書の仕組みで使われています。

署名検証の仕組み

実際の署名は、データそのものを丸ごと暗号化しているわけではありません。

公開鍵暗号は計算コストが高いため、データが大きいとそのまま暗号化するのは非効率です。代わりに次の手順を踏みます。

1. 署名者はデータをハッシュ関数（SHA-256など）にかけ、固定長の要約値（ハッシュ値）を作る
2. そのハッシュ値を自分の秘密鍵で暗号化したものが署名になる
3. 検証者は受け取ったデータを同じハッシュ関数にかけて、自分でもハッシュ値を計算する
4. 受け取った署名を署名者の公開鍵で復号し、中身のハッシュ値を取り出す
5. 3と4のハッシュ値が一致すれば、データは改ざんされておらず、確かに秘密鍵の持ち主が署名したとわかる

ハッシュ値だけを暗号化すればよいので、データ本体が大きくても署名・検証の計算コストは一定に抑えられます。

公開鍵暗号の弱点

代表的なアルゴリズムはRSAや楕円曲線暗号（ECC）です。鍵配送問題を解決できる代わりに、暗号化・復号の計算コストが共通鍵暗号より2〜3桁重く¹、大量のデータをやり取りする通信には不向きです。

2つを組み合わせるハイブリッド暗号

共通鍵暗号は速いが鍵配送問題があり、公開鍵暗号は鍵配送問題がないが遅い。

TLSはこの両方の長所を組み合わせています。

最初の鍵交換の部分だけ公開鍵暗号（または鍵交換の仕組み）を使い、以降のデータ通信は共通鍵暗号に切り替える。

TLSのハンドシェイクは、この最初の共通鍵を安全に作るための手続きです。

まとめ

	共通鍵暗号	公開鍵暗号
鍵の数	1つ（両者で共有）	2つ（公開鍵・秘密鍵のペア）
速度	速い	遅い
得意なこと	大量データの暗号化	鍵配送・署名
弱点	鍵配送問題	計算コストが高い
代表例	AES	RSA、ECC

TLSがどうやってこの2つを組み合わせているかは、次の記事でハンドシェイクの流れとして図解します。

参照

• Cloudflare — What is encryption?
• Cloudflare — What is public key encryption?
• NIST — Advanced Encryption Standard (AES), FIPS 197

1. 具体的な倍率はアルゴリズムや鍵長、実装によって変わりますが、公開鍵暗号（RSAなど）は共通鍵暗号（AESなど）に比べて2〜3桁遅いとされます。 ↩