Schnorr Signatures
いろいろな場面で解説が必要になりそうなので独立させてみました。
はじめに
まずは、原文の解説を簡単にします。
原文からいくつもの論文が出ているので、知っているものといくつか異なる点があるかもしれませんが、
概念は一緒だと思います。
それから、楕円曲線（elliptic curve : EC）でSchnorr Signaturesを構成します。
原文
「Efficient Identification and Signatures for Smart Cards」とあるように
元々、ICカードでの署名で考えられたもののようです。
簡単な説明だけします。
詳しく知りたい方は、参考文献などを参照ください。
準備
以下を準備します。
\begin{align*}
g &\text{ : 生成元(generator)}\\
x &\text{ : 秘密鍵(private key)}\\
y =g^x &\text{ : 公開鍵(public key)}\\
H(\cdot) &\text{ : ハッシュ関数(hash function)}\\
M &\text{ : メッセージ(message)}\\
\end{align*}
※：秘密鍵は、署名者のみが知っている情報です。
※：それ以外の項目については、署名者も検証者も知っています。
署名（Sign）
署名は、乱数k（毎回異なる値）から、sを求めます。
途中で生成したハッシュ値（数値）eを合わせて署名値となります。
\begin{align*}
& k \text{ : 乱数(random number)}\\
& r =g^k \\
& e = H(r\ ||\ M)\\
& s = k - xe \\
& (s, e) \text{ : 署名値(signature value)}\\
\end{align*}
※：乱数kが同じ値の場合、x（秘密鍵）が計算出来てしまいます。
検証（Verify）
検証ですが、署名値(s,e)と準備の秘密鍵x以外は知る事が出来ます。
最後の等式が成り立てば、署名が正当となります。
\begin{align*}
&r_v = g^sy^e \\
&e_v = H(r_v\ ||\ M)\\
& e \overset{?}{=} e_v
\end{align*}
証明（Proof）
r_vとrが同じであれば、この署名と検証が成り立ちます。
\begin{align*}
r_v &= g^sy^e \\
&= g^{k - xe}g^{xe}\\
&= g^k\\
&=r\\
\end{align*}
まとめ
単純な式でやりましたが、実際コンピュータの世界では循環群などを使ってある程度の長さにします。
また、逆算が出来てしまうように思えるかもしれませんが、離散対数問題により
大きな群であれば、解くことが困難である、という事が言えるそうです。
最初の論文(1990)では512bits程度でも大丈夫でしたが、コンピュータの性能が上がってきている為
現在では、2,048bits以上ないとセキュリティが担保されないそうです。
Schnorr Signaturesの楕円曲線（EC）化
先ほどのSchnorr Signaturesは、冪乗の演算を用いていましたが、これを楕円曲線（EC）に置き換えてみます。
楕円曲線（EC）も離散対数問題の特性を持っていて、冪乗よりも少ないデータ量で扱う事が出来ます。
準備
以下を準備します。
\begin{align*}
G &\text{ : 生成元(generator/EC point)}\\
x &\text{ : 秘密鍵(private key/scalar)}\\
X=xG &\text{ : 公開鍵(public key/EC point)}\\
H(\cdot) &\text{ : ハッシュ関数(hash function/return scalar)}\\
m &\text{ : メッセージ(message)}\\
\end{align*}
※：秘密鍵は、署名者のみが知っている情報です。
※：それ以外の項目については、署名者も検証者も知っています。
署名（Sign）
署名は、乱数r（毎回異なる値）から、Rを求めます。
乱数r,Rと秘密鍵xなどから、署名sを求めます。
\begin{align*}
r &\text{ : 乱数(random number/scalar)}\\
R =rG &\text{ : (EC point)}\\
s = r + H(R\ ||\ m)x &\text{ : 署名(scalar)}\\
(R,s) &\text{ : 署名値(signature value)}\\
\end{align*}
※：乱数rが同じ値の場合、x（秘密鍵）が計算出来てしまいます。
検証（Verify）
検証ですが、署名値(R,s)と、準備の秘密鍵x以外は知る事が出来ます。
次の等式が成り立てば、署名が正当となります。
\begin{align*}
&sG \overset{?}{=} R + H(R\ ||\ m)X \\
\end{align*}
証明（Proof）
署名の計算式に生成元Gを積算することで、署名と検証が成り立ちます。
\begin{align*}
s &= r + H(R\ ||\ m)x \\
&\text{両辺に}G\text{を積算}\\
sG &= rG+H(R\ ||\ m)xG\\
sG &=R+H(R\ ||\ m)X\\
\end{align*}
まとめ
原文の「Schnorr Signatures」といくつか異なる点があります、
署名値とするのがハッシュ値ではなく乱数の楕円曲線上の点（EC Point）ですが、
内容はほとんど変わってない事がわかります。
また、実装によって異なる点に注意する必要があります。
\begin{align*}
sG &=R+H(\cdot)X\\
sG &=R-H(\cdot)X\\
\end{align*}
ハッシュ値を+とするのか、-とするのかの違いがあります。
原文を踏襲するのであれば、-となるのでしょうがどちらでも構いません。
解説では、+を採用しています。
コンピュータ演算の場合、-より+の方が手順がひとついらなくなる為、
+で実装している場合があります。
各実装によってハッシュ関数が異なります。
ハッシュ関数に入れるパラメータは実装により異なります。
（少なくとも、Rとmは必須で、一部実装ではXを入れる場合があります。）
また、剰余（modul)より大きいハッシュ関数が必要になります。
原文の「Schnorr Signatures」では、2,048bits以上ないとセキュリティ的に弱いと書きました。
下記のPaperによれば、Bitcoinで使われている、secp256k1だと、3,072bits相当の強度があるようです。
http://www.secg.org/SEC2-Ver-1.0.pdf
実際には、署名値で33+32byte（520bits）なので、データ量が少ない事がわかります。
参考文献
Schnorr署名 ―― 30年の時を超えて注目を集める電子署名
原文も参考にしましたが、Wikipediaのリンクは切れています。
「Efficient Identification and Signatures for Smart Cards」でGoogle検索すると出てきます。
Key Aggregation for Schnorr Signatures