生日问题与生日攻击

2020年4月18日22:31:53 发表评论

什么是生日问题?

生日问题是密码学的很多领域中的一个基本问题,它与hash计算特别相关。首先思考如下问题:

假如你和N个人在同一间房里,那么,至少有一个和你生日是同一天的概率是多少?N多大时,和你生日在同一天的概率大于1/2?

首先我们求它的对立事件P,即另外N-1个人没有一个人和你生日是同一天,然后利用1-P即可求解。我们知道一年有365天,因此有个人和你生日不是同一天的概率是364/365,那么N-1都和你不是同一天出生的概率是(364/365)N-1,因此至少有一个人和你生日是同一天的概率是1-(364/365)N-1

第二个问题即解方程1-(364/365)N-1>1/2。我们解得N>253。

上面只是一道开胃小菜,接着我们再看另一个问题。

还是你和N个人在同一间房里,那么,N个人至少有两个人生日相同的概率大于1/2的N值是多少?

同样的求对立事件,即N个人生日不是同一天的概率是:

P=(364/365)*(363/365)*(362/365)*...*(365-N+1)/365

那么根据题目构造不等式:1-P>1/2。我们求得N=23。初看起来这非常不可思议,但仔细想想我们就会发现,N个人进行了N(N-1)/2≈N2,再算算N2>=365解出N=19,所以N=23没那么难以理解了。这个结论是我们想得到的,即如果一个哈希函数的输出位数是N,那么只要不能在一定时间内穷举2N/2,这个哈希函数就是不可攻破的。

生日攻击

如果能在一定时间穷举2N/2,那么就有可能发生碰撞。特别被劫持发送一条“恶意”消息而哈希值刚好碰撞,就会造成可大可小的后果。

PS:今天小侄女生日,祝她生日快乐!

flyingsheep

发表评论