压缩签名

Question

假设我有一方创建的64字节签名(来自ed25519).该方必须进一步压缩签名,使其在基础2048中为4-8位.然后,第二方必须能够从数据重新创建签名.

以下是小数签名的示例: 5670805304946899675614751184947294808143702505785021095830828785725573127924144977212837580418240432902375737987653828318622222068237988634991262293689098

如何在2048基础上将此签名压缩为大约4位数？这可能使用数独压缩吗？

Answer 1

我认为这是不可能的.至少你说" 第二方必须能够从数据中重新创建签名 "的部分

这背后的简单原因是熵,或每个签名中包含的信息量.首先,让我们看看您描述的每种"格式"中最多可以存储多少信息.

• ed25519签名:64字节,即512位(因此2 ^ 512种可能性,大约1.34e154)
• 基数2048中的4位数,即2048 ^ 4种可能性,log2((2 ^ 11)^ 4)= 44
• 8位数(因为你说4-8),相同的推理,88位

因此,基于2048的数字已经少了很多(最大可能)信息.对于你的函数存在,这意味着在2 ^ 512种可能性中,有足够的冗余信息(即如果你知道位a和b,你很有可能知道位c,或者可能是某些值的配置是完全不可能的,等等,你可以用44(或88)位表征所有可能的输出.

让我们看一下Shannon的源编码定理:

每个具有熵H(X)的随机变量可以压缩成N(X)以上的比特,信息丢失的风险可以忽略不计,如N→∞; 但相反,如果它们被压缩成少于N H(X)位,则几乎可以肯定信息将丢失.

这里的随机变量是ed25519签名.你问两件事

1. 如果H(<random ed25519 signature>)可以是44或88.
2. 如果使用N = 1而不是N→∞可以达到此限制,因为您希望每个签名都使用44或88位进行编码,而不是N个签名的平均位数低于44或88.这是一个更强烈的要求.

ed25519签名中的熵肯定比44或88位中的熵更多.从网站Ed25519简介:

安全性高.该系统具有2 ^ 128安全目标; 打破它有类似的难度打破NIST P-256,RSA与~3000位密钥,强大的128位分组密码等.已知的最佳攻击实际上平均花费超过2 ^ 140位操作,并成功降低二次性位操作数下降的概率.

但是如果你的功能存在,它可能会容易得多,因为你只需要2 ^ 44(或2 ^ 88)次尝试,每次应用"反向"功能,就可以详尽地找到所有碰撞.当然,我们不知道假设的反向函数需要多少位操作,但至少它会给你一个想法.另外,如果你使用生日攻击进行暴力攻击,你只需要这个尝试次数的平方根(因此2 ^ 22或2 ^ 44).

相反,如果你用平均2 ^ 140次操作阅读执行此攻击的论文,每次执行2 ^ i次迭代(因此i + o = 140),您可能希望找到合理枚举的格式所有可能的64字节签名,2*i位.但是,这只适用于您的第一个问题,因为攻击可以利用属性,例如某些签名值比其他签名值更频繁地发生.然后,通过编码某些值,这些值通常用比经常发生的值更少的位来编码,而不是每个值都可以达到2*i的最佳存储长度.

除此之外,我们读到:

小签名.签名适合64个字节.这些签名实际上是较长签名的压缩版本; 压缩和减压的时间包括在上面报告的循环计数中.

这意味着即使较大的密钥中存在一些冗余,它们也已经进行了额外的压缩传递,并且我们可以合理地假设在较小的密钥中应该存在相同的信息密度.也就是说,发现裁员的可能性更小.

因此,这意味着如果您将签名转换应用于44-88位,您将丢失信息,几乎占用了 64字节的哈希值.由于无法重新创建从其校验和下载的文件,因此无法从您计算的哈希重新创建ed25519签名.