压缩签名
Compressing signature
假设我有一个一方创建的 64 字节签名（来自 ed25519）。此方必须进一步压缩签名，使其以 2048 为基数为 4-8 位数字。然后，第二方必须能够从数据中重新创建签名。
这是十进制签名的示例：
5670805304946899675614751184947294808143702505785021095830828785725573127924144977212837580418240432902375737987653828318622222068237988634991262293689098
如何将此签名压缩为 2048 基数的大约 4 位数字？这可能使用 Sudoku compression?
签名为 64 字节，因此有 256^64 或 2^512 种可能的签名。仅当使用 2^512 个可能的签名中最多 2048^8 = 2^88 个时，才有可能实现此压缩量。 Ed25519 似乎不太可能出现这种情况。
编辑：修改并澄清了问题，询问此处是否可以进行数独压缩。有 6670903752021072936960 = 2^72.49... 方式来填充数独网格，比 9^81 = 2^256.7... 标记每个单元格的方式小得多。但签名算法不应该是这种情况，所以这种压缩在信息理论上是不可能的。
我认为这是不可能的。至少你说“第二方必须能够从数据中重新创建签名”的部分
这背后的简单原因是 熵，或每个签名中包含的信息量。首先，让我们看看你描述的每个"formats"中最多可以存储多少信息。
- ed25519 签名：64 字节，即 512 位（因此有 2^512 种可能性，大约 1.34e154）
- 4位以2048为基数，即2048^4种可能，log2((2^11)^4) = 44
- 8位（因为你说的是4-8），同理，88位
因此，基于 2048 位的数字已经少了很多（最大可能）信息。对于你的函数存在，这意味着在 2^512 种可能性中，有足够的冗余信息（即如果你知道位 a 和 b，你很可能知道位 c，或者可能是一些值的配置是完全不可能的，等等），你可以用 44（或 88）位来表征所有可能的输出。
让我们来看看 Shannon's source coding theorem :
N i.i.d. random variables each with entropy H(X) can be compressed into more than N H(X) bits with negligible risk of information loss, as N → ∞; but conversely, if they are compressed into fewer than N H(X) bits it is virtually certain that information will be lost.
这里的随机变量是ed25519签名。你在问两件事
- 如果 H(
) 可以是 44 或 88。
- 如果N=1可以达到这个限制，而不是N→∞，因为你希望每个签名用44或88位编码，而不是N个签名的平均位数低于44或88. 这个要求强多了
ed25519 签名中的熵肯定比以 44 或 88 位存储的更多。来自网站 Introduction to Ed25519 :
High security level. This system has a 2^128 security target; breaking it has similar difficulty to breaking NIST P-256, RSA with ~3000-bit keys, strong 128-bit block ciphers, etc. The best attacks known actually cost more than 2^140 bit operations on average, and degrade quadratically in success probability as the number of bit operations drops.
但是如果你的函数存在，它可能会更容易，因为你有足够的 2^44（或 2^88）次尝试，每次应用 "reverse" 函数，穷尽地找到所有碰撞.当然，我们不知道假设的反向函数需要多少位操作，但至少它给了你一个想法。另外，如果您使用 the birthday attack 进行这种暴力攻击，您将只需要此尝试次数的平方根（因此 2^22 或 2^44）。
相反，如果您阅读了使用平均 2^140 次操作执行此攻击的论文，每次迭代 2^i 次，每次 2^o 次操作（因此 i+o=140），您可能希望找到一种用 2*i 位合理枚举所有可能的 64 字节签名的格式。但是，这仅适用于您的第一个问题，因为攻击可能会利用一些属性，例如某些签名值比其他签名值更频繁地发生。然后你的最佳存储长度 2*i 只能平均达到，而不是每个值，通过编码一些更经常发生的值而不是更经常发生的值。
除此之外，我们读到：
Small signatures. Signatures fit into 64 bytes. These signatures are actually compressed versions of longer signatures; the times for compression and decompression are included in the cycle counts reported above.
这意味着即使较大的密钥中存在一些冗余，他们已经进行了额外的压缩，我们可以合理地假设较小的密钥中的信息即使不是更高密度也应该是相同的.也就是说，找到冗余的机会更小。
因此这意味着，如果您应用从签名到 44-88 位的转换，您将丢失信息，几乎占用了 64 字节的 a hash。由于不可能从校验和中重新创建您下载的文件，因此无法从您计算的哈希中重新创建 ed25519 签名。
假设我有一个一方创建的 64 字节签名（来自 ed25519）。此方必须进一步压缩签名，使其以 2048 为基数为 4-8 位数字。然后，第二方必须能够从数据中重新创建签名。
这是十进制签名的示例：
5670805304946899675614751184947294808143702505785021095830828785725573127924144977212837580418240432902375737987653828318622222068237988634991262293689098
如何将此签名压缩为 2048 基数的大约 4 位数字？这可能使用 Sudoku compression?
签名为 64 字节，因此有 256^64 或 2^512 种可能的签名。仅当使用 2^512 个可能的签名中最多 2048^8 = 2^88 个时，才有可能实现此压缩量。 Ed25519 似乎不太可能出现这种情况。
编辑：修改并澄清了问题，询问此处是否可以进行数独压缩。有 6670903752021072936960 = 2^72.49... 方式来填充数独网格，比 9^81 = 2^256.7... 标记每个单元格的方式小得多。但签名算法不应该是这种情况，所以这种压缩在信息理论上是不可能的。
我认为这是不可能的。至少你说“第二方必须能够从数据中重新创建签名”的部分
这背后的简单原因是 熵，或每个签名中包含的信息量。首先，让我们看看你描述的每个"formats"中最多可以存储多少信息。
- ed25519 签名：64 字节，即 512 位（因此有 2^512 种可能性，大约 1.34e154）
- 4位以2048为基数，即2048^4种可能，log2((2^11)^4) = 44
- 8位（因为你说的是4-8），同理，88位
因此，基于 2048 位的数字已经少了很多（最大可能）信息。对于你的函数存在，这意味着在 2^512 种可能性中，有足够的冗余信息（即如果你知道位 a 和 b，你很可能知道位 c，或者可能是一些值的配置是完全不可能的，等等），你可以用 44（或 88）位来表征所有可能的输出。
让我们来看看 Shannon's source coding theorem :
N i.i.d. random variables each with entropy H(X) can be compressed into more than N H(X) bits with negligible risk of information loss, as N → ∞; but conversely, if they are compressed into fewer than N H(X) bits it is virtually certain that information will be lost.
这里的随机变量是ed25519签名。你在问两件事
- 如果 H(
) 可以是 44 或 88。 - 如果N=1可以达到这个限制，而不是N→∞，因为你希望每个签名用44或88位编码，而不是N个签名的平均位数低于44或88. 这个要求强多了
ed25519 签名中的熵肯定比以 44 或 88 位存储的更多。来自网站 Introduction to Ed25519 :
High security level. This system has a 2^128 security target; breaking it has similar difficulty to breaking NIST P-256, RSA with ~3000-bit keys, strong 128-bit block ciphers, etc. The best attacks known actually cost more than 2^140 bit operations on average, and degrade quadratically in success probability as the number of bit operations drops.
但是如果你的函数存在，它可能会更容易，因为你有足够的 2^44（或 2^88）次尝试，每次应用 "reverse" 函数，穷尽地找到所有碰撞.当然，我们不知道假设的反向函数需要多少位操作，但至少它给了你一个想法。另外，如果您使用 the birthday attack 进行这种暴力攻击，您将只需要此尝试次数的平方根（因此 2^22 或 2^44）。
相反，如果您阅读了使用平均 2^140 次操作执行此攻击的论文，每次迭代 2^i 次，每次 2^o 次操作（因此 i+o=140），您可能希望找到一种用 2*i 位合理枚举所有可能的 64 字节签名的格式。但是，这仅适用于您的第一个问题，因为攻击可能会利用一些属性，例如某些签名值比其他签名值更频繁地发生。然后你的最佳存储长度 2*i 只能平均达到，而不是每个值，通过编码一些更经常发生的值而不是更经常发生的值。
除此之外，我们读到：
Small signatures. Signatures fit into 64 bytes. These signatures are actually compressed versions of longer signatures; the times for compression and decompression are included in the cycle counts reported above.
这意味着即使较大的密钥中存在一些冗余，他们已经进行了额外的压缩，我们可以合理地假设较小的密钥中的信息即使不是更高密度也应该是相同的.也就是说，找到冗余的机会更小。
因此这意味着，如果您应用从签名到 44-88 位的转换，您将丢失信息，几乎占用了 64 字节的 a hash。由于不可能从校验和中重新创建您下载的文件，因此无法从您计算的哈希中重新创建 ed25519 签名。