電子署名というと、RSA 署名や DSA、ECDSA などが有名ですが、これ以外にも無数の電子署名方式が提案されています。 Schnorr（シュノア）署名もこうした電子署名方式の一つであり、1989年ごろに C.P.Schnorr 氏により発明されました。 しかしながら発明と時を同じくしてアメリカ国立標準技術研究所 (NIST) により DSA が提唱されたことや、 2008年まで Schnorr 自身の取得した特許により保護されており自由に利用できなかったなどの政治的な理由であまり利用されて来ませんでした。 しかしながら理論的側面だけに注目すると他のどの電子署名方式と比較しても計算が単純で分かりやすく、 またセキュリティ的な根拠もしっかりしていることなどから近年注目を集めています。

本記事ではこの Schnorr 署名の動作原理を学び、その仕組みを解説します。 前提知識として、ハッシュ関数といった基礎的な暗号学の知識と、合同式といった初等的な数学の知識を仮定します。

なお、本記事は厳密な定義よりも理解のしやすさを目指して書かれておりますので、数学的に曖昧であったり不十分な箇所があります。 数学的厳密さを求める方は原論文[1]等の議論も併せてご覧ください。

前提知識

合同式

RSA 署名や DSA と同様、Schnorr 署名も合同式を多用します。 そこで本記事では特に断り書きがない限り以下のように省略することにします。

すなわち、q を適当な巨大素数とします。 整数 x, y の掛け算といった場合にはこれは素数 q で割った余り

\[ (x \times y)\ \text{mod}\ q \]

の意味であるとします。 以下では簡単のために「mod q」は省略することにします。 つまり、単に $x \times y$ と書いた場合には掛け算を行った後に q で割った余りを計算するものとします。

指数演算 ($x^y$) なども同様に、特に断り書きがなければ素数 q で割った余りを意味していると思ってください。

離散対数問題

この節では Schnorr 署名のみならず、多くの暗号アルゴリズムの安全性に対して数学的な根拠を与えている「離散対数問題 (Discrete Logarithm Problem; DLP)」について軽く解説します。 この概念に触れるのがはじめての読者にとっては少々抽象的で難しいかもしれませんが、 最初は「ふーん、そうなんだ」ぐらいの気持ちで読んでもらい、以降の記事を読んで詰まりそうになったらこの節に戻ってきてください。 逆に離散対数問題を既にご存じの方はこの節は読み飛ばしてしまって構いません。

簡単な説明

離散対数問題とは何かを一言で表すと、整数 $g, y$ が与えられた場合に「q を法とした時、g を何乗したら y と合同になるか？」という問題のことです。 例えば「11 を法とした時、2 を何乗したら 9 と合同になるか？」を考えてみましょう。 とりあえず 2 を一乗、二乗、……としていくと、 $2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16$ となりますが、 11 を法としますので $2^4 = 5$ としてよく、以降は $2^5 = 10, 2^6 = 9, \cdots$ となります。 これにより答えは「6」だと分かります。

計算の困難性

この例では q = 11 と小さかったため、順番に指数を計算していくことで求めることができましたが q が非常に巨大な数字（例えば 100 桁とか）になった場合にはどうなるでしょうか？ $2^x$ が x に関してほぼランダムだと仮定すると、このように順番に計算していく方法では 100 桁の整数をしらみ潰しに探すのと同じで、これでは日が暮れるどころか、人生が終わってしまいそうですね。 もっと賢い効率的な方法があるのではないかと思うかもしれませんが、実は現時点では劇的に効率化するような方法は一切知られておらず ^[1]、また多くの科学者・数学者からそのような方法はないと信じられています。

逆演算の容易性

一方でこの逆の計算、すなわち $x^y$ を求めるのは非常に高速にできることが知られています。 このことをみるために、例として $2^{1024} = 2^{2^{10}}$ を計算することを考えてみましょう。 上の例でもやったように $2^2=4$, $2^3 = 4 \times 2 = 8$, $2^4 = 8 \times 2 = 16$, $\cdots$ というふうに順番に計算していくのでは掛け算が 1,024 回も必要ですので、 たとえ電卓を使っていいと言われても、ツラいです。 そこで次のように式を変形してみましょう。

\[ 2^{2^{10}} = \left(2^{2^9}\right)^2 = \left(\left(2^{2^8}\right)^2\right)^2 = \cdots = \left(\cdots \left( \left(2^2\right)^2 \right)^2 \cdots \right)^2 \]

この式変形によれば、2 を二乗して、さらにその結果を二乗し、またさらにその結果を二乗して……という操作を 10 回繰り返せばよさそうだと分かります。 これにより、1,024 回の掛け算が必要そうなところを、たったの 10 回の掛け算で済ますことができます。 いまは指数の肩の部分が $2^{10}$ という綺麗な形でしたのでこのように簡単に式変形をすることができましたが、 実は一般の数字に対しても例えば $2^{11451} = 2 \times (2^{5725})^2$ といった具合に変形していくことで任意の指数に対して高速化ができます。 このアルゴリズムは何度も自分自身と乗じることから「繰り返し自乗（二乗）法」という名前で知られています。 繰り返し自乗法は有名なアルゴリズムであり、調べればたくさん情報がありますので、興味のある方はご自分で検索してみてください。

理解度確認テスト「繰り返し自乗法」に簡単な演習問題を設けましたので、こちらも参考にしてください。

まとめ

以上の議論をまとめると、「数字を何乗かするのは簡単だけど、何乗したらその数字になるのかを見つけるのは難しい」と言うことができます。 このように「ある方向への計算は簡単だけど、逆の方向は難しい」という性質を持つ計算というのは暗号にとっては極めて重要となります。 例えば電子署名の場合には「電子署名の検証は簡単で誰にでもできるけど、電子署名を作るのは難しくて特定の人しかできない」という性質が必要だということが言えますので、 なんとなく近しいことはお分かりいただけるのではないでしょうか？

この時点では「確かにそんな感じがするなぁ」くらいに思ってもらうだけで十分です。 この先に読み進めてもらえれば自ずとその意味が分かってくるはずですので、ひとまず深く考えずさらに先に進んでみましょう。

記号の定義

この記事を通し、特に断り書きのない限り以下のように定義します。 各変数の意味は記事内ではじめて登場する際に改めて説明します。

• H(x), H(x; y) …… ハッシュ関数
• q …… 素数。以降、すべての式は最後に q で割った余りを計算していると解釈する
• g …… 整数。ただし $g^i = 1$ となるような i は極めて大きいものとする
• s …… 秘密鍵。整数
• p …… 公開鍵。$p = g^s$
• m …… 署名を行いたいメッセージ（文字列またはバイト列）
• r ……署名に必要な乱数
• y, e …… 電子署名データ

直感的理解

Schnorr 署名の定義に進む前に、なぜ Schnorr 署名が電子署名として動作するのかを直感的に理解しましょう。

Schnorr 署名の動作原理を端的に表すのは以下の式です。

\[ \large e = H(m; g^y p^e) \]

ただし、m は署名対象のメッセージ、p は公開鍵を表す整数、y, e が Schnorr 署名において計算すべき電子署名データ（アルゴリズムの出力値）です。 また $H(x; y)$ はハッシュ関数とします。 引数が二つありますが、これは単純に二つのデータを連結してハッシュ値を計算したものと理解してもいいですし、HMAC をご存じの方はメッセージ認証符号だと理解してもいいです。

この式をよく見ると変数 e が式の両辺に現れており、関数に対する入力が出力にも依存するような「自己言及型」の式となっています。 ハッシュ関数には一方向性がありますので、入力の “e” と出力の “e” がたまたま一致するように選ぶのは一見すると極めて難しそうです。 もし適当に y と e の値をランダムに選んできたとすると、ハッシュ関数の出力値 e’ は e とはほぼ独立に定まるランダムな値であり、 e の値とハッシュ関数の出力値 e’ がたまたま一致するという奇跡が起きない限りこの式を満たすような変数ペア (y, e) を見つけることはでなさそうです。 Bitcoin をご存じの方は Proof-of-Work (PoW) で目的のハッシュ値を見つけることを想像すると、これがいかに困難なのかが分かるのではないでしょうか。

ところが、秘密鍵 s を知っているとこの式をみたすような変数ペア (y, e) を魔法のように見つけることができてしまうのです。 トリックは、公開鍵 p が整数 g と秘密鍵 s を用いて $p = g^s$ と表せることです。 これを用いて上の式の右辺を書き換えると

\[ H(m; g^y (g^s)^e) = H(m; g^{y + se}) \]

と変形することができます。 このように指数部分を共通化することができると何が嬉しいかというと、 r := (y + se) の値は変えずに、y と e の値の配分のみを変えることで e の値を自由に調整できます。 従ってあとはハッシュ関数の出力値と e が一致するように調整を行えば上の方程式をみたす変数ペア y, e を見つけることができます（具体的な計算アルゴリズムは後述）。 正しい (y, e) のペアを見つけられる人は正しい秘密鍵を持っている人だと推測されますので、この (y, e) は電子署名として機能するわけです。

ちなみにこのように、普通の人にとっては非常に難しくても、ある情報を知っていれば簡単に答えが計算できてしまう処理のことを「トラップドア（trapdoor; 落とし戸）関数」といいます。 落とし戸とは忍者屋敷の隠し扉のようなものを指す単語で、隠し扉の位置を知っている人であれば容易に部屋の中に入れますが、 知らない人にとっては入るのは難しいという性質にちなんで名付けられています。

アルゴリズム

以下に Schnorr 署名の電子署名アルゴリズムを示します。 前節の「直感的な理解」も参考にしてください。 なお、ここでは理解を優先することにし、変数の値の範囲などの詳細については敢えて書かないこととします。

署名作成

アルゴリズム1（Schnorr 署名の作成）

q をある巨大な素数とし、g を q と互いに素な整数とする。 また m を署名対象のメッセージ（ビット列）、整数 s を秘密鍵、$H(\cdot; \cdot)$ をハッシュ関数とする。

1. 適当な乱数 r を生成する。
2. $e := H(m; g^r)$ を計算する。
3. 前のステップで求めた e を用いて $y: = r – se$ を計算する。

ここで求めた (y, e) を電子署名として出力する。

署名検証

こうして求められた電子署名は、以下のようなアルゴリズムで検証を行うことができます。

アルゴリズム2（Schnorr 署名の検証）

$p:=g^s$ を公開鍵とし、他の変数の定義については「アルゴリズム1」と同様とする。 与えられた Schnorr 署名 (y, e) を検証するには、 \[ e’ = H(m; g^y p^e) \] を計算し、この e’ が e と一致するかを確認すればよい。（一致すれば正しい）

この検証アルゴリズムの正当性は署名作成時のアルゴリズムにより $r = y + se$ が成り立つことに注意すると、

\[ e’ = H(m; g^y (g^s)^e) = H(m; g^{y+se}) = H(m; g^r) = e \]

により確かめることができます。

セキュリティ

上の説明では特にセキュリティに関する注意はしませんでしたが、巨大素数 q や整数 g を適切に選ばないと簡単に署名を偽造されてしまう可能性があります。 なぜなら冒頭でも説明した離散対数問題が q の桁数の割には簡単^[2]になってしまうケースがあるからです。 秘密鍵を s とすると公開鍵は $p := g^s$ でしたので、秘密鍵は公開鍵に対して g を底とする離散対数の関係になっているため、 離散対数問題が簡単だと秘密鍵がバレてしまいますね。

Schnorr 署名の原論文に書かれている安全な q, g の選び方は以下のとおりです。

• $\tilde{q} | (q-1)$ となるような巨大素数のペア $(q, \tilde{q})$ を見つける。$\tilde{q}$ の桁数が実際の暗号強度となる
• g を $g^{\tilde{q}} = 1$ をみたす整数とする。ただし $g \neq 1$ とする

なぜこのように選びとれば安全なのかといった数学的な議論は少々難しいので詳しくは触れませんが、簡単に言うとこのように選ばないと $g^1, g^2, \cdots$ の取りうる値の種類が q に比べて圧倒的に少なくなってしまうからです。 例えば最も極端な例では g = q-1 とすると、$g^2 = q^2-2q+1 = 1, g^3 = q-1, \cdots$ と q の桁数がどんなに大きくても二通りの値しか取らなくなってしまいます。

発展的話題

歴史的導入

上記の解説では「一見すると解くことは極めて難しそうな自己言及型の方程式であっても秘密鍵に関する知識があれば簡単に解くことができること」を用いて Schnorr 署名を導入しましたが、 実は歴史的にみると Schnorr 署名の原論文[1]ではこのような導入の仕方はされていません。 上記のような導入のされ方は原論文の出版後、多くの論文（例えば[2]の§2.2などが詳しい）でなされていますが、 原論文ではそのような説明は一切なく相互通信が必要な認証方式を改変することで導入しています。

このような導入のされ方は Fiat-Shamir 変換と呼ばれるゼロ知識証明などの分野で多用される重要な考え方ですのでここで[1]の流儀に従った議論を簡単に追いかけてみようと思います。

個人認証アルゴリズム

IC カードを読取機にかざし、個人認証を行うことを考えます。 具体的には IC カードの中にのみ入っている秘密鍵を用いて認証情報を作り、それを読取機に送り返すことで認証を行います。

ここで IC カード内にはランダムに生成された整数 s が秘密鍵として保持されており、 読取機側には公開鍵として $p := g^s$ が記録されているものとします。 利用するユーザが複数人いる場合には、それぞれのユーザに対して異なる秘密鍵の入った IC カードを配布し、読取機側には全ユーザの公開鍵のリストが記録されているものとします。

このとき、以下のような手順で個人認証を行います。

アルゴリズム3（Schnorr 個人認証方式）

1. IC カードは乱数 ｒを生成し、$x := g^r$ を計算し読取機へ送る
2. 読取機は乱数 e を生成し IC カードへ送る
3. IC カードは y := r – se を計算し読取機へ送る
4. 読取機は $x’ := g^y p^e$ を計算し、この結果がステップ 1. で IC カード側から受け取った x と等しいかチェックする。（等しければ認証成功）

このアルゴリズムの正当性は以下のように確かめることができます。

\[ x’ = g^y (g^s)^e = g^{y+se} = g^r = x \]

ここで安全性について考察してみましょう。 IC カードが詐称を行い読取機を騙すためには、

\[ g^r = x = x’ = g^y p^e \Leftrightarrow p^e = g^{r-y} \Leftrightarrow \left(g^s\right)^e = g^{r-y} \]

をみたすような (y, r) のペアを見つけなければいけません。 ところがこの式より $s = (r-y)e^{-1}$ ですから、もしこのような (y, r) が見つかるアルゴリズムが存在するのであれば公開鍵の情報だけから秘密鍵を計算できる （すなわち、離散対数問題が解けてしまう）ことになります。 とてもそのようなアルゴリズムが存在するとは思えませんから、この個人認証アルゴリズムは安全だと分かります。

通信量を減らす

上記の方式ですと、途中で IC カードおよび読取機ともに乱数（それぞれ x および e）を生成し交換する必要があるため少々手順が煩雑です。 そこでやり取りするデータを削減することを考えてみましょう。

ここでまずステップ 1 とステップ 2 の順番を入れ替えることを考えると、IC カードから読取機に変数 x を送る際にランダムに整数 y を生成し $x = g^y p^{-e}$ としてしまえばいくらでも詐称ができてしまうことが分かります。 逆に言うと、変数 e の値をカンニングし変数 x の値を調整するようなことができなければ変数 e を読取機側から渡す必要もありませんし、もっというとランダムである必要もありません。 そこで変数 e をランダムに作る代わりにハッシュ関数 $H(\cdot)$ を用いて x = H(e) としましょう。 ただし e の値をもとに x の値を調整できなければ良いため、ハッシュ関数は一方向性を持つ必要は必ずしもなく、極端な話 e = H(x) = x としてしまっても構いません。

アルゴリズム3’（双方向通信の必要ない Schnorr 個人認証方式）

1. IC カードは乱数 ｒを生成し、$x := g^r$ を計算し、そのハッシュ値を e := H(x) とする
2. IC カードは y := r – se を計算する
3. IC カードは (x, y) を読取機へ送る
4. 読取機は $x’ := g^y p^{H(x)}$ を計算し、この結果が x と等しいかチェックする。（等しければ認証成功）

このようにハッシュ関数を導入しプロトコルを少し変更することで、読取機からデータを一切送信せずとも認証が行えることが分かります。

電子署名とFiat-Shamir変換

ここまでくれば電子署名方式にするのは簡単で、アルゴリズム3’において H(x) を H(m; x) と置換すれば既に解説している Schnorr 署名の処理と全く同じになることが分かります（詳しくはご自身でチェックしてみてください）。

このように相互通信が必要な認証アルゴリズムにハッシュ関数を導入することで、相互通信を必要とせず任意のメッセージに対して電子署名が作成できるアルゴリズムに変換する方法は既に[3]で知られており、 この論文の著者名を冠して「Fiat-Shamir 変換」という名前で呼ばれています。

ハッシュ関数と相互通信のトレードオフ

ここでは個人認証アルゴリズムの改良版のような形で電子署名アルゴリズムを導入しましたが、 必ずしも電子署名アルゴリズムの方が優れているということではなくそれぞれのアルゴリズムにはそれぞれのメリット・デメリットがあります。

電子署名アルゴリズムのメリットは既に述べたように双方向通信が必要ないということですが、逆にデメリットとしてハッシュ関数を利用しないといけないというものがあります。 これの何がデメリットかというと、ハッシュ関数として暗号学的に脆弱なものを利用してしまうと電子署名が簡単に偽造できてしまいますのでハッシュ関数の安全性にも注意を払わないといけなくなってしまうからです。 ハッシュ関数の安全性を数学的にチェックするのは極めて難しく、ある日いきなり脆弱性が発見され利用が推奨されなくなることもあります。 実際かつてよく利用されていた MD5 と呼ばれるハッシュ関数には重大な脆弱性が発見されてしまいましたので、現在ではほとんど利用されることはありません。 現在でもよく使われる SHA-2 に対してもその前のバージョンの SHA-1 に脆弱性が発見されたことなどから安全性が疑問視されており、 スポンジ関数と呼ばれる全く新しい仕組みを用いたハッシュ関数が模索されています（c.f. SHA-3/Keccak）。 このようにハッシュ関数の安全性に関する議論は極めてデリケートであり、脆弱性が発見されることによりアルゴリズムの安全性が破壊される可能性（リスク）が増えてしまうといった意味で、これはデメリットと言えるでしょう。

一方個人認証アルゴリズムではハッシュ関数が必要なかったので、離散対数問題の安全性のみを担保すればよく、こちらのアルゴリズムの方がセキュリティに対するリスクは低いのがメリットと言えます。 しかしながらその代償として、電子署名アルゴリズムのように IC カードから認証データ（電子署名）を一方的に送るような仕組みにはできず、 読取機で乱数を作って送るという操作がどうしても必要となります。 そのため双方向に通信しなければならず、読取機側の送信機構および IC カード側の受信機構が追加で必要となってしまいます。

このように通信を一方向にしたいとハッシュ関数がどうしても必要になり、ハッシュ関数を利用しないとどうしても双方向通信が必要になるという、 どちらか片方を立てるともう片方が立たなくなるという関係は互いに「トレードオフ」であるといいます。 こうした意味で二つの暗号アルゴリズムにはそれぞれ相補的なメリット・デメリットがあると言うことができますので、どちらかのアルゴリズムが優れているという訳ではないことが分かるでしょう。

耐量子コンピュータ電子署名方式

上記ではハッシュ関数の安全性を引き合いに出してハッシュ関数を使う・使わないの議論を行いましたが、 離散対数問題についてもその安全性の数学的な根拠は確固たるものであるとは言い難いです。 離散対数問題の安全性を不安視する根拠として最もよく引き合いに出されるのは「量子コンピュータ」です。 1994年に Shor（ショア）により発見されたアルゴリズム[4]により、量子コンピュータを用いると素因数分解が高速に（多項式時間で）解けることが証明されたことはご存じの方も多いのではないかと思いますが、 実は Shor によるアルゴリズムを少し改変することで離散対数問題も高速に解けることが知られています。 従って少なくとも現実的な量子ビット数を扱える汎用量子コンピュータが完成してしまうと、本記事の Schnorr 署名を含むこれまで考えられてきた数多くの電子署名方式はもはや安全ではなくなってしまいます。

こうした問題点を解決するために研究されているのが、いわゆる「ポスト量子コンピュータ暗号」です。 量子コンピュータ耐性を持った電子署名方式もいくつか提案されており、例えば Lamport 署名[5]などが有名です^[3]。 Lamport 署名は素因数分解や離散対数問題などは一切使っておらず、ハッシュ関数の安全性にのみ依拠していますが、 その代償として同じ鍵ペアを使い回すことができない、公開鍵や電子署名のデータサイズが巨大であるなどの欠点があり、あまり利用されていません。

楕円曲線Schnorr署名

この記事では整数の掛け算を使ったオリジナルの Schnorr 署名方式を紹介しましたが、楕円曲線を利用することもできます。 楕円曲線を利用するとどうしても計算プログラムが複雑になってしまいますが、それを凌駕するようなメリットがあります（概ね DSA と比べた ECDSA のメリットと同様です）。

• 掛け算を使った Schnorr 署名方式と同じ暗号強度を担保するのに、より短い（サイズの小さい）公開鍵や電子署名で十分である。これにより以下のような恩恵を得られる
  • ディスク容量や通信量を削減できる。特に暗号通貨 (Bitcoin) などのデータサイズが致命的となるアプリケーションでの利用効果は大きい（Bitcoin では ECDSA を使っている）
  • 計算桁数が少なくて済むことから、同じ暗号強度で比較すると計算が高速になる傾向がある
• 鍵ペアを生成する際に、安全な素数を探し出す必要がない（任意の整数が秘密鍵となりうる）

楕円曲線バージョンへの書き換えはほぼ自明で、まず署名作成アルゴリズムは以下のようになります。

アルゴリズム1’（楕円曲線 Schnorr 署名の作成）

G を利用する楕円曲線 $\mathcal{C}$ のベースポイントとする。 また m を署名対象のメッセージ（ビット列）、整数 s を秘密鍵、$H(\cdot; \cdot)$ をハッシュ関数とする。

1. 適当な乱数 r を生成する。
2. $e := H(m; rG)$ を計算する。
3. 前のステップで求めた e を用いて $y: = r – se$ を計算する。

ここで求めた (y, e) を電子署名として出力する。

一方、署名の検証アルゴリズムは以下のようになります。

アルゴリズム2’（楕円曲線 Schnorr 署名の検証）

P := sG を公開鍵とし、他の変数の定義については「アルゴリズム1’」と同様とする。 与えられた Schnorr 署名 (y, e) を検証するには、 \[ e’ := H(m; yG + eP) \] を計算し、この e’ が e と一致するかを確認すればよい。（一致すれば正しい）

このアルゴリズムの正当性のチェックは、読者への課題としておきます（理解度確認テスト「楕円曲線 Schnorr 署名の正当性」）。

変数rの決定的計算方法

Schnorr 署名を作成する際には変数 r をランダムに生成する必要があります。 ところが何の不確定さもなく計算を延々と実行していくコンピュータ内で乱数を生成するのは逆に難しく、 しばしば「品質の良くない」乱数を利用することがあります。 しかしながら Schnorr 署名を作成する際に品質の悪い乱数を利用すると、最悪の場合秘密鍵が漏洩してしまいます。

このことをみるために「最悪な」例として、乱数を二回以上使いまわしてしまった場合を考えてみましょう。 二つの電子署名を $(y_1, e_1), (y_2, e_2)$ とし秘密鍵を s とすると、Schnorr 署名のアルゴリズムによりこれらの間には

\[ y_1 = r – s e_1 \] \[ y_2 = r – s e_2 \]

という関係が成り立ちます。 ここでそれぞれの式の左辺および右辺同士を引き算してみると

\[ y_1 – y_2 = -s (e_1 – e_2) \Leftrightarrow s = -(y_1 – y_2) (e_1 – e_2)^{-1} \]

となりますので、（通常は一般に公開され誰でも閲覧できる）電子署名のデータ $y_1, e_1, y_2, e_2$ から秘密鍵 s が計算できてしまい、秘密鍵が漏洩してしまいます！

このように複数の電子署名で乱数を使いまわした場合に秘密鍵が漏洩してしまうことは DSA や ECDSA でも知られており、 最も有名な例として、乱数を使いまわしたことで PlayStation 3 のソフトウェア署名に用いられていた秘密鍵が漏洩してしまったといった事例をあげることができます。

そこでこうした事故を防ぐために、乱数ではなく秘密鍵と署名対象のメッセージから決定的に計算できるようにするという提案がなされております[RFC6979]。 提案自体は極めて新しい（2013年ごろ）ものですが、電子署名が偽造されてしまった場合に被害が極めて大きい暗号通貨（Bitcoin）などのプロジェクトを中心に実装は進んでいるようです。

[RFC6979]自体は DSA および ECDSA での利用を想定したものではありますが、Schnorr 署名でもほぼそのまま利用することができます。 今後 Schnorr 署名を用いるアプリケーション／ライブラリを作成される場合にはこのような決定的手法を利用することを強くおすすめします。

理解度確認テスト

繰り返し自乗法

整数のべき乗がいかに高速に計算できるのかを体感してもらうため、これを安直な計算方法および繰り返し自乗法を利用してそれぞれ実装してみましょう。

実装できましたら、実際に作成したプログラムを動かし、以下の式を計算してみましょう。

\[ 3939^{114514114} \mod 123456789 \]

答えは「31726602」となるはずです。

Python で簡単なコードを書いて実行してみたところ、以下のような計算時間となりました。

• 安直法：13.5秒
• 繰り返し自乗法：0.02秒

後者の方が圧倒的に速い（675倍）ですね。 みなさんのコードはどのくらいの速度差が出たでしょうか？

楕円曲線 Schnorr 署名の正当性

楕円曲線 Schnorr 署名が正しく検証できることを、通常の Schnorr 署名の場合の議論を参考に確かめてみてください。

楕円曲線 Schnorr 個人認証方式

アルゴリズム 3（Schnorr 個人認証方式） に対して整数のべき乗のかわりに楕円曲線を利用することもできます。 どのようなアルゴリズムになるでしょうか？ 本文中の 楕円曲線 Schnorr 署名 を参考にして考えてみましょう。

脆弱な変数r

「変数rの決定的計算方法」で、乱数として生成すべき変数 r を誤って固定値にしてしまった場合にはただちに秘密鍵が漏洩してしまうことを解説しました。 いつも同じ値を使ってしまうのは明らかにダメな実装ですが、もう少しまともな実装としては例えば現在の時刻を種にして乱数を生成するということは頻繁に行われています。 ところが現在時刻などを利用してしまうと、電子署名の作成日などから概ねどの乱数が用いられたのかが推定できてしまいます。 このような場合にはやはり簡単に電子署名から秘密鍵を求めることができてしまいます。

このことをもう少し厳密に議論してみましょう。 乱数として取りうる値が $\{ r_i \}_{i=1}^\kappa$ の $\kappa$ 個のうちのどれかだと分かっているとします。 この時、与えられた二つの相異なる電子署名データ $(y_1, r_1), (y_2, r_2)$ から秘密鍵 s を求めるアルゴリズムを書いてください。 また乱数が固定値だった場合に比べてこのアルゴリズムは $\kappa$ のオーダで何倍の計算時間で実行できるのかを考えてみましょう。

参考文献

[1] C.P.Schnorr, Efficient Identification and Signatures for Smart Cards, CRYPTO ’89, LNCS 435, pp.239-252 (1990)

[2] G.Maxwell and A.Poelstra, Borromean Ring Singatures, draft

[3] A.Fiat and A.Shamir, How To Prove Yourself: Practical Solutions to Identification and Signature Problems, CRYPTO ’86, LNCS 263, pp. 186-194 (1987)

[4] P.W.Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, In Proceeding of 35th IEEE FOCS, pp.124-134 (1994)

[5] L.Lamport, Constructing digital signatures from a one-way function, Technical Report SRI-CSL-98 (1979)

[RFC6979] T.Pornin, Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), RFC6979 (2013)

---