沙三廉正

Question

我们曾经用CRCs来检查文件的完整性。为了进行安全性分析，我们可以将检测到大文件中的损坏位的概率联系起来。现在，我们使用RSA签名的SHA-3哈希进行身份验证。

是否有任何方法来计算两个大小相同的文件具有相同的SHA-3散列的概率？我假设概率是1。

如何根据改变的位数或偶数1来关联概率呢？

Answer 1

是否有任何方法来计算两个大小相同的文件具有相同的SHA-3散列的概率？

碰撞阻力通常由生日界绑定，相当于输出大小的一半。因此，找到两个文件(或输入消息)需要使用2^{h / 2}，其中h是(SHA-3)哈希的输出大小。这是假设你有足够的存储空间，这是不可能的。

但是，如果您有两个没有预先选择或预先计算的文件，那么选择两个文件的可能性取决于完整的输出大小:一个在2^{h}中，这是可以忽略不计的。

有关更多信息，您可以尝试了解预像电阻。

我假设概率是1。

如果哈希输出分布良好，对相同哈希的输入的概率为1(对于大小有限的大型文件，则为非常接近1)，这是很有可能的。

如果您有消息，例如，1 1MiB每个和一个256位的散列，那么每个散列值对许多消息都是有效的；这就是鸽子洞原则:如果你尝试把100只鸽子放进10个洞里，你就会得到拥挤的笼子。对于所有可能的1MiB文件，2^{2^{23}}值都分布在2^{256}可能的哈希值上，这意味着关于2^{8388352}消息的平均结果是相同的哈希！

然而，查找此类消息的复杂性在于:加密散列是一种不能逆转的散列方式:除了散列消息之外，没有任何简单的计算可以创建散列到某个值的消息。当然，循环遍历所有的2^{8 \cdot 2^{20}} = 2^{2^{23}}消息(对于所有可能的1MiB大小的文件)是不可行的。

如何根据改变的位数或偶数1来关联概率呢？

找到两个具有相同散列的文件的概率是相同的:可以忽略不计。然而，有一件事要记住:哈希值本身的变化没有被考虑在内。加密散列的设计并不是为了共同抵抗文件和哈希值的更改。在错误仅限于不大于CRC的段或随机错误发生在有限的、可能更大的消息段的情况下，CRC的特性可能更好。

但是，如果散列是签名的一部分，则不能更改。如果您更改签名的位数，则验证将以非常高的确定性失败。因此，验证哈希值作为签名验证的一部分是非常好的。

更深入地挖掘:机会或对手可以在没有签名的情况下翻转散列的任何部分，您需要私钥来生成基于散列的签名。如果您更改了签名的任何位，那么要么在比较哈希(RSA)之前验证失败，要么在比较-现在随机-哈希( ECDSA)时失败(ECDSA间接比较)。

换句话说，签名文件更改和签名验证的可能性是可以忽略不计的。只要哈希保持不变，或者如果散列位都与关于0.5的机会翻转，那么在计算上就不可能找到另一个哈希值为相同值的文件。

所以用签名代替CRC是很好的。另一个文件验证的可能性可以忽略不计。即使是对文件的恶意更改也不会使签名验证，因为有一个安全的哈希函数，如SHA-3。这是一个明显的优势，比儿童权利委员会。

请注意，交换文件连同它们的签名仍然是完全可能的，这是经常被忽视的。签名本身也无助于删除或复制。和往常一样，仅仅应用密码本身并不能保护您的系统安全。

Answer 2

我假设概率是1。

我想你或者你不太明白什么是概率。或者你说的概率1指的是其他的东西。

如果我们使用SHA-3的512位变体，哈希的长度为64字节。这意味着，如果您接受所有可能的大小文件(比如说65个字节)，就会得到保证的冲突，正如@Maarten所解释的那样。如果你指的是这种碰撞的概率，那么肯定是1。但是你需要多少文件才能得到保证的碰撞呢？对于512位散列，需要超过2^512 ~= 10^154文件。即使每秒可以生成1000 000个文件，也需要10^140年才能生成这个数量的文件。这就是为什么您可以创建一个与给定的哈希相同的文件的概率是0，而不是1。

大小相同的两个文件产生相同哈希的概率是多少？SHA-3的分布是均匀的.这意味着两个包含随机数据大小的任意文件产生相同哈希的概率为1/2^512 = 2^(-512) ~= 10^(-154)。在现实中，大多数文件(视频、音频、PDF文档等)有一定的结构和价值，它们的许多部分都不是很随机的。即使考虑到这一点，碰撞的概率也很小，几乎为0。

这就是为什么你关于概率1的说法是不正确的。