签名算法

定义

任意的签名算法都可以用一个三元组表示: ($GEN, SIG, VER$)，可以说是组成签名系统的三个算法。

• $GEN$: 密钥生成算法
• $SIG$: 消息签名算法
• $VER$: 消息校验算法

定义一个接口表示：

type Signature interface {
	// GenerateKey generates secret key and public key
	GenerateKey() (sk []byte, pk []byte)
	// Sign computes signature of message using secret key
	Sign(message []byte, sk []byte) []byte
	// Verify check if the signature is valid
	Verify(message []byte, pk []byte, signature []byte) bool
}

下面详细说说这三个算法。

密钥生成算法

形式化表示为：

$$(pk, sk) \leftarrow GEN(1^k)$$

其中，$k$ 是安全参数，wiki 上给出了详细的说明：

In cryptography, the security parameter is a variable that measures the input size of the computational problem. Both the resource requirements of the cryptographic algorithm or protocol as well as the adversary’s probability of breaking security are expressed in terms of the security parameter.

也就是相当于说，安全性参数可以表示出破坏该签名安全性的概率和需要的资源等。

不过在实际中，我们可能会固定 $k$，比如为 256 等等。

指定安全参数之后，调用该方法，系统可以生成一对密钥，其中包括一个私钥和公钥，公钥可以公布，但是私钥必须安全保存。

消息签名算法

形式化表示为：
$$ \sigma(M) \leftarrow SIG(M, sk)$$

输入需要签名的消息，以及生成的私钥，该算法可以输出消息的签名。

消息校验算法

形式化表示为：
$$ false/true \leftarrow VER(M, \sigma(M), pk) $$

输出消息，和对应需要校验的签名，然后输入公钥，该算法可以确定消息是否完整，并可以校验发布者的身份，因为只用该发布者私钥签名的数据，才能成功通过该公钥解密。

满足

一个签名算法必须满足两个性质：

1. 不可伪造性：其他用户不可能伪造签发者对数据进行签名。
2. 正确性：通过上述三个步骤进行计算，输出结果一定为 $true$。

Hash-based 签名方案分类

One Time Signature (OTS)

$OTS$ 的每一个密钥对，只能用来签名一条消息，因为在签名完第一次消息之后，该密钥对不再安全，攻击方可以 100% 伪造签名。

比如：Lamport OTS, WOTS.

Few Times Signature (FTS)

$FTS$ 的每一个密钥对，可以用来签名多个消息，但是随着签名的次数增加，安全性会急剧下降。

比如：HORS.