鍵を渡さずに、秘密を送るには
公開鍵暗号とは、公開してよい公開鍵と、自分だけが持つ秘密鍵を、1組にして使う暗号です。公開鍵で暗号にしたデータは、組になった秘密鍵でしか戻せません。
会ったことのない相手にも、鍵を渡す手間なしで秘密を送れます。ウェブサイトへの接続や、メールの暗号化の土台です。
このレッスンのゴール
メモ
公開鍵と秘密鍵が組になって働くしくみを説明することができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 公開鍵 | 誰に見せてもよい鍵。暗号にする側が使う | |
| 秘密鍵 | 持ち主だけが持つ鍵。暗号を戻す側が使う | |
| 鍵ペア | 公開鍵と秘密鍵の組 | |
| 剰余 | 割り算の余り。mod や % で表す | 10 % 3 は 1 |
| 素数 | 1と自分自身でしか割り切れない2以上の数 | 11, 13 |
| RSA | 素数の掛け算の難しさを使った公開鍵暗号の1つ |
学生が入力するセルは、このプレビューでは空白です。
2つの鍵は、役目が分かれている
郵便受けを思い浮かべてください。誰でも手紙を入れられますが、開けて取り出せるのは鍵を持つ持ち主だけです。
公開鍵は「入れる口」、秘密鍵は「開ける鍵」にあたります。公開鍵は配ってかまいません。秘密鍵だけを守ればよいのです。
例: 花子さんが秘密を受け取る
| 場面 | 使う鍵 | 誰の鍵か |
|---|---|---|
| 太郎さんが、花子さん宛てに暗号にする | 花子さんの公開鍵 | 花子さんが公開している |
| 花子さんが、届いた暗号を戻す | 花子さんの秘密鍵 | 花子さんだけが持つ |
| 途中で盗み見る人 | 公開鍵だけ | 戻すことはできない |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
「秘密鍵を相手に送れば、相手も読める」と考える人が多くいます。秘密鍵は決して渡しません。渡すのは公開鍵で、暗号を戻せるのは秘密鍵を持つ人だけです。
小さな数で RSA を手で追う
RSA の鍵は、2つの素数から作ります。ここでは小さな p = 11 と q = 13 を使います。掛けた n = 143 は公開し、(p - 1) × (q - 1) = 120 は秘密にします。
公開鍵は (e = 7, n = 143)、秘密鍵は (d = 103, n = 143) です。7 × 103 = 721 は、120 で割ると余りが1になるように選んであります。
例: 9 を暗号にして戻す
| 手順 | 計算 | 結果 |
|---|---|---|
| 暗号にする | 9 を7乗して143で割った余り | 48 |
| 戻す | 48 を103乗して143で割った余り | 9 |
| 鍵の確認 | 7 × 103 = 721 を120で割った余り | 1 |
学生が入力するセルは、このプレビューでは空白です。
余りが1になることを確かめる
python3 -c "print(721 % 120)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
公開鍵で 9 を暗号にする
python3 -c "print(pow(9, 7, 143))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
秘密鍵で元の 9 に戻す
python3 -c "print(pow(48, 103, 143))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
pow(m, e, n) は何を計算するか
pow(9, 7, 143) は、9を7回掛けた数を143で割った余りです。大きな数を実際に掛けずに、余りだけを手早く求めます。
秘密鍵の d は、公開鍵の情報だけでは簡単に作れません。p と q を知っている人だけが、すぐに求められます。
なぜ小さな数は安全でないか
# n を割り切る最小の数を探します。これが素因数分解です。
n = 143
for p in range(2, n):
if n % p == 0:
print(p, n // p)
break
# n を 221 に変えて、もう一度実行しましょう。
本物の RSA は数百桁の素数を使う
143 のような小さな数は、すぐ素因数分解できて、11 × 13 だと分かります。すると秘密鍵も計算できます。この例は、仕組みを手で追うためだけの玩具です。
本物の鍵は数百桁の素数を使い、掛け算は一瞬ですが、元の2つに戻す計算は現実には終わりません。自分で作らず、検証されたライブラリを使いましょう。
公開鍵暗号は共通鍵を渡すのに使う
公開鍵暗号は、共通鍵暗号よりずっと遅い計算です。そこで、大きなデータは速い共通鍵暗号で暗号にします。
その共通鍵だけを、相手の公開鍵で暗号にして送ります。2つを組み合わせた、この使い方がふつうです。