クリーム色の背景、色付き表示、高コントラスト、大きな文字のほうが読みやすいですか?配色と文字を選ぶと、すべてのページに一度で反映されます。

無料レッスン

Schnorr プロトコル: 鍵を知っている証明

このレッスンのあとで: 小さな数で Schnorr プロトコルを実行し、検証できる。

65分のレッスンコマンド3件ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

鍵を送らずにログインする

Schnorr プロトコルは、公開鍵の裏にある秘密の数を知っていることを示すゼロ知識証明です。3つの短いメッセージで示し、秘密は手元から一度も出ません。

これは Schnorr 署名の土台で、今も実際のシステムで使われています。

このレッスンのゴール

メモ

小さな数で Schnorr プロトコルを実行し、検証できる。

キーワード

ことばいみれい
秘密鍵証明者だけが知る数 x
公開鍵G の x 乗を P で割った余り、y
ナンス1回の証明だけに使うランダムな数k
レスポンスチャレンジへの証明者の答えs = k + c * x mod Q
シミュレーター秘密なしで、やり取りの記録をにせて作るプログラム

学生が入力するセルは、このプレビューでは空白です。

Schnorr は3つの手順

証明者は x を知っていて、y = G の x 乗 (P で割った余り) は誰もが知っています。

  1. コミット: 証明者はランダムな k を選び、t = G の k 乗を送ります。
  2. チャレンジ: 検証者はランダムな c を送ります。
  3. レスポンス: 証明者は 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で証明する

コード: python
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

ここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。

このラボとソースについて: ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

授業で使いますか?このモジュールを学生に割り当てると、教員用ガイド、自動採点つきの課題、学生ごとのラボを使えます。