所有产品

Furein交易所:根据哈希函数的签名 Part-2

  Furein交易所上述的小窍门能够将公钥调集的巨细折半,Furein交易所并以相同量级减缩签名的巨细。Furein交易所认为这样做很棒,但称不上什么立异之举。密钥和签名依然长达数千个位元。

  咱们采用的终究优化手法,是由 Robert Winternitz 根据上述 Merkle 办法所提出的更进一步晋级。在实践运用中,这个办法减缩了 4~8 倍的签名和公钥巨细价值是添加了签名和验证的时刻。

  Winternitz 的主见源自一项技能:时空权衡(time-space tradeoff)。这类处理方案使得空间需求减小,价值是添加核算时刻(反之亦然)。以下几个考虑能协助我i们更好的了解 Winternitz 办法:

  假如咱们今天不要签名音讯的每一位元(0 或 1),而是将它们视为更大的音讯编码,那会怎么样呢?比方咱们每 4 个位元签名一次,或是每八个位元(1 字节)签名一次?

  在开端的 Lamport 办法中,咱们有两列字符串作为签名密钥(和公钥)的一部分。一列是签署 0 位元用的,另一列签署 1 位元。

  现在假定咱们想直接对字节签名,而不是每个位元做签名。最直接的做法是将密钥(和公钥)列表从本来的两个添加到 256 个组成一张大表,包括音讯中每一个或许的字节。这样签名者就能从一张巨大的密钥表中选取适宜的值,每次针对整个字节作签名。

  不幸的是,这个主见烂透了。尽管它将签名的巨细减少了 8 倍,付出价值却是将公钥和密钥巨细添加 256倍 。假如这份巨大的密钥表能够用于屡次签名那也就算了但它不能。当密钥表发作重用时,这种“签整个字节版别”的 Lamport 办法也会遇到和原始 Lamport 办法相同的约束。

  存储和分发 256 个随机密钥列本钱十分昂扬,假如咱们只在需求签名的时分,以编程的手法生成需求的密钥呢?

  这么做的优点是咱们只需求贮存一列密钥,当需求签名时再运用哈希运算生成其他密钥即可。

  具体来说,Winternitz 提出能够对终究一列密钥再次进行哈希散列运算,生成一列公钥: pk 。(在实践运用中,咱们只需求 255 列密钥,由于终究一列密钥咱们能够直接视为公钥。)这个办法的高雅之处在于,任何一个给定的密钥值都能经过公钥查看;只需持续进行哈希散列运算,然后查看是否得到终究公钥即可。

  留意:要对字节进行签名,咱们只需求 255 个密钥列,而不是 256 个。由于终究一个密钥列等同于公钥。

  要对音讯的第一个字节进行签名,咱们需求从适宜的列中选取一个值。举例来说,假如是字节 “0” ,咱们将从 sk0 中输出一个值作为咱们的签名;假如是字节 “20” ,咱们将从 sk20 中输出一个值作为咱们的签名。关于终究一个字节 “255” ,咱们尽管没有对应的密钥列,但也没关系!咱们能够输出空字串或是输出 pk 中的元素。

  要留意,实践上咱们不需求保存每一个密钥列。经过核算推演,咱们能从初始列得到所需密钥。验证者只需求拿好公钥并直接进行恰当次数(视音讯字节数状况而定)的哈希运算,就能够验证核算结果是否等同于正确的公钥元素。

  好像前面章节评论的 Merkle 优化办法,到现在为止所描绘的 Winternitz 办法也有着显着的缝隙。由于密钥列互相相关(即 sk1 = H(sk0)),任何人看到字节“0”及其签名,都能够容易的将音讯的字节改为 “1”,然后更新签名匹配篡改(同理可类推)。事实上,无论什么字节进犯者都能够添加到音讯中。假如没有查看机制,这会导致十分严峻的假造进犯危险。

  处理这个问题的办法正如前面所说到的,假如要防止进犯者修正签名,签名者有必要核算原始音讯字节的校验和,并对校验和也进行签名。校验和的规划使得进犯者添加任何字节,都会使校验和失效。这儿不做过多评论,具体请参阅这儿。

  毫无疑问,校验和正确与否是至关重要的;只需有任何一点疏忽,都会为你带来很欠好的影响。假如在出产环境中布置这样的签名,会形成严峻的结果。

  拿下面这个有点粗糙的图阐明,对一条 4 字节的音讯运用 Winternitz 签名办法:

  留意:示例中的音讯由字节 byte 组成而不是 bit 。尽管我很确认正确地核算了校验和,但由于是手算的,有时分或许会有点小疏忽。

  通篇评论中,咱们主要在讲根据哈希散列的签名怎么运作的,而没有谈到为什么挑选它。现在就让咱们阐明一下这种结构的签名特色是什么。

  前期支撑散列签名的观念以为,这种办法十分快速并且简略,由于这种办法只需求评价适宜的哈希函数,并进行一些数据复制即可。朴实从核算本钱视点考虑,哈希散列签名肯定有才能和 ECDSA 、RSA 等一较高下,一起关于轻量级设备十分友爱。当然,这种功率在很大程度上是以献身带宽为价值的。

  不过(最近)关于哈希散列签名的鼓起有着更杂乱的原因:一切的公钥加密行将被破解。

  更具体地说:行将面世的量子核算机,简直会对一切现在运用的签名办法的安全性形成巨大的冲击,包括 RSA、ECDSA 等等。由于 Shor 算法(以及它的变体)让咱们能在多项式时刻内,处理离散对数和因式分解问题的办法,这使得绝大多数签名办法不再安全可靠。

  大部分哈希散列签名不容易遭到 Shor 算法影响。当然,咱们不是说哈希散列签名能够彻底反抗量子核算进犯;对哈希运算最有用的量子进犯称作 Grover 算法,它会大大下降哈希运算的安全性 。不过这种程度的安全性影响,远小于 Shor 算法带来的影响(破解时刻层级差别在平方到立方之间),因而能够简略经过添加哈希函数的运算内容和输出巨细,来保证签名的安全性。像是 SHA3 系列哈希函数开发意图很清晰,它能处理更大的输入,并有更好的才能对立量子核算进犯。

  至少从理论上来讲,哈希散列签名风趣之处在于它留给咱们一线时机,抵挡未来的量子核算进犯或许就只能挣扎一下,谁知道呢。

  提示一下,现在咱们议论的哈希散列签名都是“古玩级”的,上述一切的哈希散列签名办法都发明于 1970 年或是早于 1980 年,这好像不适用于今时今天。

  我写完这篇文章初稿后,有许多人要我多讲讲这个范畴近几年的开展。我无法给出翔实的列表,不过我能够略微描绘近几年呈现的一些点子(感谢 Zooko 和 Claudio Orlandi)。

  无状况签名。上述一切办法共通的一个限制在于,它们要求签名者在签名之间坚持状况。关于一次性签名咱们能够很直观的了解:咱们有必要防止重复运用任何密钥;而在 Merkle 屡次签名中,咱们有必要记住正在运用的叶节点公钥,防止重复运用。更糟的是,Merkle 办法要求签名者先构建一切或许用上的密钥对,所以签名的数量是有限的。

  在 1980 年,Oded Goldreich 指出有一种手法能够树立无需坚持状况的签名 。主见如下:不预先生成一切密钥,而是生成一个简略的一次性公钥的“验证树”。每一个密钥的都能够在树的底层签署额定的一次性公钥,并以此类推。假如运用单个种子生成一切私钥,则表明完好的 Merkle 树不需求在密钥生成时存在,而能够在生成新密钥时按需求构建。每个签名都包括签名和公钥的“验证链”;从根节点开端,一直到叶节点真实用于签名的密钥对。

  这项技能让咱们能在十分“深”的 Merkle 树构建很多(指数级)的密钥。这答应咱们结构十分多的一次性公钥,只需求咱们随机地(或伪随机地)挑选签名密钥,则发作密钥重用的或许性极低。当然,这是直觉主见。有关这个主见的更多优化和具体示例,请参阅 Bernstein 等人的 SPHINCS 提案;SPHINCS-256 实例供给巨细约为 41KB 的签名。

  Picnic:后量子零常识签名(post-quantum zero-knowledge based signatures)。Picnic 是彻底不同的主见,它根据一项全新的非交互式零常识证明体系(non-interactive zero-knowledge proof system) 技能,称为 ZKBoo。ZKBoo 是一种新的 ZK 证明体系,它根据一种称为“头脑中的 MPC”的技能,让证明者运用多方核算来进行自证 。这现已过于杂乱,无法具体解说;但终究的结果是,人们能够持续运用哈希函数来验证杂乱的句子。

  简而言之,Picnic 和 ZK 证明体系供给除了哈希函数签名之外的第二种考虑方向。这些签名的本钱依然很高 高达几百千字节,可是技能演进能够大大减缩签名的量级。

  假如你略微回想一下本文,咱们费了番功夫描绘一些哈希函数的安全特性。这可不只是简略展现罢了!你能够看到,哈希散列签名的安全性,彻底取决于咱们所挑选的哈希函数。

  (再暗示一下,哈希散列签名不安全的当地,便是进犯者现已在设法攻破的哈希函数)

  大多数评论哈希散列签名的根底的文章,一般会在哈希函数的抗原像进犯上提出安全疑虑。以 Lamport 签名为例,咱们能够很直观的了解。给定一个公钥,假如进犯者能够核算出哈希运算的输入,那她就能够容易假造一个有用签名。这种进犯使得签名不再安全。

  不过,这是进犯者只看到了公钥,却还未看到任何一个有用签名的状况。在下面状况中,进犯者能够取得更多音讯。假定她现在有了公钥和一部分的密钥 pk01 = H(sk01) 和 sk01。假如进犯者能够找到公钥 pk01 的次原像,尽管她还不能对不同的音讯进行签名假造,但实践上她现已生成了一个新的签名。关于签名安全要求特别特别严厉的场景(SUF-CMA),这就能够被视为一次有用的进犯了。因而 SUF-CMA 在抗 次原像进犯上有很高的规范。