鍵を送らずにログインする
Schnorr プロトコルは、公開鍵の裏にある秘密の数を知っていることを示すゼロ知識証明です。3つの短いメッセージで示し、秘密は手元から一度も出ません。
これは Schnorr 署名の土台で、今も実際のシステムで使われています。
このレッスンのゴール
メモ
小さな数で Schnorr プロトコルを実行し、検証できる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 秘密鍵 | 証明者だけが知る数 x | |
| 公開鍵 | G の x 乗を P で割った余り、y | |
| ナンス | 1回の証明だけに使うランダムな数 | k |
| レスポンス | チャレンジへの証明者の答え | s = k + c * x mod Q |
| シミュレーター | 秘密なしで、やり取りの記録をにせて作るプログラム |
学生が入力するセルは、このプレビューでは空白です。
Schnorr は3つの手順
証明者は x を知っていて、y = G の x 乗 (P で割った余り) は誰もが知っています。
- コミット: 証明者はランダムな k を選び、t = G の k 乗を送ります。
- チャレンジ: 検証者はランダムな c を送ります。
- レスポンス: 証明者は s = k + c × x (Q で割った余り) を送ります。
検証者は、G の s 乗が t × y の c 乗と等しいかを、P で割った余りで確かめます。どちらも G の k + c x 乗になります。
Schnorr の証明を1回実行する
docker exec jupyter python3 steps/schnorr.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
例: ラボの表示
| 手順 | 誰が | 値 |
|---|---|---|
| 秘密と公開鍵 | 証明者 | x = 65、y = 227 |
| コミット | 証明者が送る | t = 504 |
| チャレンジ | 検証者が送る | c = 77 |
| レスポンス | 証明者が送る | s = 38 |
| 確認 | 検証者 | True |
学生が入力するセルは、このプレビューでは空白です。
試そう: 秘密11で証明する
P = 1019
Q = 509
G = 4
x = 11 # 秘密
y = pow(G, x, P) # 公開鍵
print("公開鍵 y =", y)
k = 30 # 証明者のランダムな数。1回だけ使います
t = pow(G, k, P)
c = 5 # 検証者のチャレンジ
s = (k + c * x) % Q
print("t =", t, "c =", c, "s =", s)
left = pow(G, s, P)
right = t * pow(y, c, P) % P
print("G ** s =", left)
print("t * y ** c =", right)
# s を s + 1 に変えて、もう一度実行しましょう。確認は通るでしょうか。
チャレンジが最後でなければならない理由
もし証明者が、t を送る前に c を知っていたとします。好きな s を選び、t = G の s 乗 ÷ y の c 乗とすれば、確認は通ります。x は一度も要りません。
これがシミュレーターのしていることです。ラボのシミュレーターは先に c = 77 と s = 300 を選び、t = 880 を作り、確認は通りました。だから記録は、チャレンジを選んでいない人には何の証明にもなりません。何も漏らさないのは、このためです。
秘密なしで記録をにせて作る
docker exec jupyter python3 steps/simulate.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
2回使ったナンスは秘密を漏らす
次にラボは、同じ k で2つ目のチャレンジに答えました。2つのチャレンジ c と c2 への2つの答え s と s2 から、x = (s − s2) ÷ (c − c2) を Q で割った余りで求められます。表示は65でした。
これはおもちゃだけの話ではありません。実際の署名の仕組みでも、ランダムな数が繰り返されて鍵が漏れたことがあります。ナンスは1回使ったら捨てます。
よくある間違い
注意
「ランダムな k は、ランダムに見えればよい」と考える人がいます。k は決して繰り返してはいけません。同じ k で2つの別のチャレンジに答えると、2つの記録を持つ人は、1回の割り算で秘密鍵を求められます。
すべての数を試して秘密を見つける
docker exec jupyter python3 steps/bruteforce.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。