【基于哈希的密码体系】Hash to Obtain Random Subset

本篇文章，我们接着来聊，基于哈希的密码体系，在上一篇文章当中，利用组合的思想[1]，将私钥的大小缩减为了原来的一半，但是，这个方案的选择函数，虽然是可以保证不同的消息，对应的私钥不可能相等，但是这个选择函数执行起来的效率是不够高的，本篇文章呢，我们来看一个Leonid Reyzin 和 Natan Reyzin 提出新的方案HORS[2]，为了提高效率，采用了哈希函数来替换S, 接下来，我们就来看一下这个的具体做法。

前置知识

我们考虑下之前讲过的S函数，我们的目标实际上是找到一个对应的映射，实际上，我们可以弱化一下这个要求，也就是我们只需要对于两个不同的消息我们找到两个子集是困难的就足够了，至于为啥需要这样呢，举一个例子，假设私钥集合是，然后，我们选中了之后，因为我们只要求集合的元素不超过目标数就可以了，因此攻击者可以伪造这些消息，这还是用到之前讲过的组合学的知识，这个也少，直接自己数一下就可以了。

然后，这里，可以进一步的扩展，如果我们已经签署了个消息，我们要签署新的消息，我们只需要满足就可以签署新的消息。

算法过程

接下来，我们来看一下，具体的算法过程，和其他的一样，也分为密钥生成，签名以及验证函数。

密钥生成

• 输入: 给定参数，l, t, k。

生成t个随机的l比特的字符串, 原始论文写的字符串(strings)，这里，其实是相当于直接存字节数组就好，不一定是字符串。

计算其中

• 输出: 公钥，私钥

签名算法

• 输入: 需要签名的消息m, 以及私钥

计算，注意，这里哈希函数输出的长度是，因为，后面要按照这个进行分组，我们将h分成k个子串()，这里每个子串的长度是比特。

将，每个子串，转换成为对应的整数这里

• 输出签名:

验签算法

• 输入: 需要验签的消息m, 以及签名，公钥

计算, 按照签名算法相同的规则分割h为并将其转换为对应的整数其中

• 验证: 计算对于所有的是否成立，如果全成立，验签通过，否则验签失败。

这里，哈希函数可以任意取，论文给的是SHA-1或者RIPEMD-160, 但是，理论上用任何的安全的哈希函数问题都不大，目前SHA-1应该是不太安全了，注意论文的时间。

代码实现

这里，还是简单的写一个代码的实现，这里，我们固定哈希函数是SHA-1吧，主要是论文当中，也建议用了它(虽然现在不安全了，但是不影响学习)。这里，简单用Python来实现一下，这个实现，这里我直接用了列表，因为Python的集合是无序的，这里，懒得搞个有序的，不过，不影响算法，或者，直接看成多重集合就可以了。

from hashlib import sha1
import random

from Crypto.Util.number import long_to_bytes


def key_gen():
    l, k, t = 64, 20, 256
    s = [random.randint(0, 2 ** l) for _ in range(t)]
    v = [sha1(long_to_bytes(s[i])).hexdigest() for i in range(t)]
    return k, s, v


def sign(m, s):
    h = sha1(m).digest()
    sigma = []
    for item in h:
        sigma.append(s[item])
    return sigma


def verify(m, sigma, v):
    h = sha1(m).digest()
    for i in range(len(h)):
        v_prime = sha1(long_to_bytes(list(sigma)[i])).hexdigest()
        if v_prime != v[h[i]]:
            return False
    return True


if __name__ == '__main__':
    _, sk, pk = key_gen()
    m = b'LittleQ'
    sigma = sign(m, sk)
    print(verify(m, sigma, pk))

这里，因为我们选定了哈希，比如SHA-1固定输出是160比特，因此，我们的K自然就取20了。

总结

本文，主要是介绍了HORS的基于哈希函数的签名方案，这个方案，相比于上一篇文章所讲的，不仅仅是简化了选择函数的执行过程，并且，现在，我们是可以签名多个消息了，我们只需要保证新的消息就可以实现新的消息的签名，从此，我们就可以用同一个私钥来签署多个不同的消息了，但是，这个方案，其实也是有一些问题的，他总体能签名的消息数量是有限制的，而且不太大，最多最多，就只能签署k个消息，因为根据鸽巢原理，如果有k+1个消息，我们是没有办法找到符合成立的子集的。其次呢，这个方案，对应的公钥的体积其实是蛮大的，比如，我们t取一个字节的大小，比如256，然后，如果我们正常l取64，也就是8个字节的话，我们的公钥的体积就是比特，也就是16k，后面的文章当中，我们就来看下前辈的大佬们，是如何处理这些问题的。好了，快乐的时光总过得特别快，又到了和大家说再见的时候了，我们下次再见。

参考资料

1. https://link.springer.com/content/pdf/10.1007/3-540-48071-4_1.pdf

• https://link.springer.com/content/pdf/10.1007/978-3-540-72738-5_3.pdf
• https://eprint.iacr.org/2017/909.pdf