Key generation

Choose a private signing key, {\displaystyle x} , from the allowed set.
The public verification key is {\displaystyle y=g^{x}} $y=g^{x}$ # 公钥、 .私钥

Signing

To sign a message,{\displaystyle M}: # 原始消息

Choose a random {\displaystyle k} from the allowed set.
Let {\displaystyle r=g^{k}} $r=g^{k}$ # 一次性公钥、 .私钥
Let {\displaystyle e=H(r\parallel M)} $e=H$r\parallel M$$ , where{\displaystyle \parallel } $\parallel$ denotes concatenation and {\displaystyle r} is represented as a bit string. # 加密结果
Let {\displaystyle s=k-xe} $s=k-xe$ # 签名结果

The signature is the pair,{\displaystyle (s,e)} $$s,e$$ . # 最终签名

原始数据为 M

需要私钥 x, 一次性私钥 k

两个大的步骤：

加密（动词）
签名（动词）

结果由上述个步骤组两部分(加密结果, 签名结果)，称之为“签名（名词）”

Verifying

Let {\displaystyle r_{v}=g^{s}y^{e}} $r\_{v}=g^{s}y^{e}$
Let {\displaystyle e_{v}=H(r_{v}\parallel M)} $e\_{v}=H$r\_{v}\parallel M$$

If{\displaystyle e_{v}=e} $e\_{v}=e$ then the signature is verified.

验证：根据公钥、最终签名、原始消息能够重新计算出加密结果。

Proof of correctness

It is relatively easy to see that{\displaystyle e_{v}=e} $e\_{v}=e$ if the signed message equals the verified message:

{\displaystyle r_{v}=g^{s}y^{e}=g^{k-xe}g^{xe}=g^{k}=r} $r\_{v}=g^{s}y^{e}=g^NaNg^=g^{k}=r$ , and hence{\displaystyle e_{v}=H(r_{v}\parallel M)=H(r\parallel M)=e} $e\_{v}=H$r\_{v}\parallel M$=H$r\parallel M$=e$ .

Public elements:{\displaystyle G},{\displaystyle g},{\displaystyle q},{\displaystyle y},{\displaystyle s},{\displaystyle e},{\displaystyle r}. Private elements:{\displaystyle k},{\displaystyle x}.