Merkle Tree & Merkle Signature Scheme

概念

Merkle Tree 又称 Hash Tree,实现一般为二叉树,当然也可以用多叉树实现,本质是一样的,WiKi 上也有相关介绍,点击这里传送。

树的叶子节点处存放数据的哈希值,其他的非叶子节点通过子节点进行构造,按照下方公式:

nodei=hash(node2i+1||node2i+2)nodei=hash(node2i+1||node2i+2)

其中,节点 ii 是节点 2i+12i+12i+22i+2 的父结点,|||| 表示串接,或者简单的说拼接,比如 a=00012,b=11002a=00012,b=11002
c=a||b=000111002c=a||b=000111002

阅读更多

Hash to Obtain Random Subset (HORS)

HORS(Hash to Obtain Random Subset)属于 FTS, 其生成的公私钥对,可以多次用来签名消息,但是每一次签名之后,系统的安全性会降低,签名能够被伪造的概率上升。论文可见 Better than BiBa: Short One-time Signatures with Fast Signing and Verifying

下面以三元组 (GEN,SIG,VER)(GEN,SIG,VER) 对 HORS 签名系统进行介绍。

密钥生成(GENGEN)

(pk,sk)GEN(1k)(pk,sk)GEN(1k)

首先,我们需要确定参数 kkt=2τt=2τ,哈希函数输出的摘要长度为 n=k×log2t=k×τn=k×log2t=k×τ bits。

阅读更多

Winternitz One Time Signature

1979 年 Ralph C. Merkle 提出了 Winternitz-OTS,其中运用了哈希链(hash chain)的结构,论文见 A Certified Digital Signature ,更加详细的算法描述见 Hash-based Digital Signature Schemes,该算法产生的一对密钥也只能签名一条消息。

下面按照 (GEN,SIG,VER)(GEN,SIG,VER) 三元组描述该算法。

密钥生成(GENGEN)

(pk,sk)GEN(1k)(pk,sk)GEN(1k)

首先,我们需要确定 ww 参数该参数决定哈希私钥多少次构造公钥,此外还需确定哈希之后摘要的长度 nn ,或者可以认为是采用的哈希函数族。

阅读更多

Lamport One Time Signature

Lamport 是第一个 OTS(One Time Signature) 算法,由 Leslie Lamport 于 1979 年提出,论文可见 Constructing Digital Signatures from One Way Function ,一对密钥只能签名一次,不能重复使用。

下面按照 (GEN,SIG,VER)(GEN,SIG,VER) 三元组描述该算法。

密钥生成(GENGEN)

(pk,sk)GEN(1k)(pk,sk)GEN(1k)

首先我们需要确定安全参数 kk,不过实际操作中我们一般只需要确定输出的摘要长度 nn

通过随机数生成器(PRG, Pseudo Random Generator),生成 nn 对随机数,每一对包含两个随机数,每一个随机数 nn bits,总共 2×n×n2×n×n bits,此为私钥。

每一个随机数进行哈希,生成 2×n2×n 个摘要,每一个 nn bits,也是 2×n×n2×n×n bits,此为公钥。

形式化表示为:

sk=(sk0,0,sk0,1,,skn1,0,skn1,1)pk=(pk0,0,pk0,1,,pkn1,0,pkn1,1)sk=(sk0,0,sk0,1,,skn1,0,skn1,1)pk=(pk0,0,pk0,1,,pkn1,0,pkn1,1)

阅读更多

签名算法

定义

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

  • GENGEN: 密钥生成算法
  • SIGSIG: 消息签名算法
  • VERVER: 消息校验算法

定义一个接口表示:

1
2
3
4
5
6
7
8
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
}

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

阅读更多