非均匀分布下生日问题的模拟研究  

Simulation study on birthday problem in non-uniform distribution

作　　者：刘天昕[1] 耿凤杰[2] 赵俊芳[2] 

机构地区：[1]北京科技大学计算机与通信工程学院,北京100083 [2]中国地质大学(北京)数理学院,北京100083

出　　处：《计算机应用》2015年第A02期38-40,共3页journal of Computer Applications

基　　金：国家自然科学基金资助项目(11202192);中央高校基本业务经费资助项目(2652012141)

摘　　要：生日问题的解是在均匀分布的假设下给出的,其原理用于密码学中的生日攻击。实际生日分布是非均匀的,有必要研究与均匀分布下生日概率解的定量差别。利用蒙特卡罗模拟方法研究了非均匀生日分布下的生日概率问题。在生日分布为余弦变化的模型下模拟计算了生日概率,并将结果与均匀分布的解析解作了对比分析。模拟结果表明,即使在20%和10%的非均匀度下,二者与均匀分布的结果仍然非常接近,最大差别分别小于0.008和0.003;但在100%极端非均匀度下,最大差别可达0.15。该模拟算法可推广应用于复杂概率问题的数值计算,利用计算机模拟可以给出较为精确的结果。The birthday problem is solved under the assumption of uniform distribution,and its principle is used as the birthday attack in cryptography. It is necessary to quantitatively compare the solutions when real birthday distribution is not uniform. The birthday problem in non-uniform distribution was studied using the Monte Carlo simulation. In a postulated cosine-distributed model, the birthday probabilities were computed and compared to the analytical solution in uniform distribution. The simulation results show that even at the levels of 20% and 10% non-uniformity,the probabilities are still very close to the uniform situation and the maximum deviations are 0. 008 and 0. 003,respectively; At the special case of100% non-uniformity,the maximum deviation reaches 0. 15. The simulation algorithm can be used in the numerical calculations of complicated probability problems,and results with high precision can be obtained using computer simulation.

关 键 词：生日问题 生日攻击 模拟计算 非均匀分布 概率计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]