给定哈希长度的通用生日计算 [英] Generalised Birthday Calculation Given Hash Length
问题描述
让我们假设我们得到以下信息:
Let us assume that we are given the following:
- 哈希的长度
- 获得碰撞的机会
现在,了解了以上内容,我们如何获得获得给定机会百分比所需的样本"数量?
Now, knowing the above, how can we obtain the number of "samples" needed to obtain the given chance percentage?
推荐答案
当我们将Simplified formula
用作生日悖论时,我们得到:
When we take the Simplified formula
for the birthday paradox we get:
probability = k^2/2N
所以:
sqr(probability*2*n) = k
我们知道n = 2 ^ lenghtHash
Where we know that n = 2^lenghtHash
一个小测试: 哈希= 16位:N = 65536 概率= 50%= 0.5
A small test: Hash = 16 bit : N= 65536 probability = 50% = 0.5
sqr(0.5 * 2 * 65536)= 256 samples
sqr(0.5*2*65536) = 256 samples
这不是100%正确,因为我们从简化公式开始,但是对于大哈希和更大样本集,它变得非常接近.
This is not 100% correct as we started of with the Simplified formula, but for big hashes and lager sample sets it gets very close.
有关公式的链接,您可以此处.
for a link on the formula you can look here.
这篇关于给定哈希长度的通用生日计算的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!