生日悖论与生日分析

《生日悖论与生日分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《概率论》案例分析题目生日悖论与生日攻击班级:学号:姓名:—、问题分析生日悖论：如果一个房间里有23个或23个以上的人，那么至少有两个人的生H相同的概率要大于50%o这就意味着在一个典型的标准小学班级(30人)中，存在两人生日相同的可能性更高。对丁-60或者更多的人，这种概率要大于99%。从引起逻辑孑盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉和抵触的意义上，它才称得上是一个悖论。大多数人会认为,23人中有2人生□相同的概率应该远远小于50%。在《著名的生□悖论》屮说道：23个人里有两个生日相同的人的儿率有多大呢？居然有50%o悖论定义：悖论是指一种导致矛

2、盾的命题。悖论(paradox)來自希腊语"para+dokein",意思是“多想一想”。如果承认它是真的，经过一系列正确的推理，却又得岀它是假的；如果承认它是假的，经过一系列正确的推理，却乂得出它是真的。生日攻击：生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即Hash值的长度。这种攻击对Hash函数提出了一个必要的安全条件，即消息摘要必须足够长。生日攻击这个术语来自于所谓的生日问题，在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率不小于1/2?这个问题的答案为23o二、问题求解不计特殊的年月，如闰二月。先计算房间

3、里所有人的生口都不相同的概率，那么第一个人的生日是365选365第二个人的生日是365选364第三个人的生EI是365选363第n个人的生EI是365选365-(n-1)所以所有人生H都不相同的概率是：(365/365)X(364/365)X(363/365)X(362/365)X...X[(365-n+l)/365]那么，n个人中有至少两个人生日相同的概率就是：1-(365/365)X(364/365)X(363/365)X(362/365)X...X[(365-n+l)/365]所以当n二23的时候，概率为0.507,约等于0.51。当n二100的时候，概率为0.99

4、99996,趋近于1。三、结果分析可见，我们的感觉有时候往往会欺骗我们。经过客观的推理运算，可以得到在23个人的一个团体屮，至少有两人生日相同的概率大于50%,而当这个人数增大到100时，至少有两人生日相同的概率竟然接近于lo四、总结与心得体会通过这次的概率论论文写作，我们在实际生活中发现问题，然后用概率论的知识去解决他们。一方面，增强了我们发现问题的能力，另一方面，也增强了我们运用平时所学的理论知识去解决实际问题的能力。如果，我们只是一味的学习课木上的知识，依旧是没有任何用处的。只有把这些知识，融会贯通，才能遇题解题。除此Z外，我们在学习概率论的过程屮发现了很多类似的悖

5、论，比如说谎者悖论，理发师悖论，上帝悖论等，我们判断一件事悄不能只根据平时的经验，那些所谓的经验可能会对你的判断形成误导，只有，经过仔细的推敲,运算所得到的东西才是符合实际的，才是经得起实际检验的。五、问题发展生日悖论与生口攻击。所以生口悖论的本质就是，随着元素增多，出现重复元素的概率会以惊人速度增长，而我们低估了它的速度。下图中，q(n)表示的是我们幻想中随着人数的增长至少两个人生H相同的可能性，而p(n)则表示的是实际屮随着人数的增长至少対个人生日相同的可能性，很明显能够看出来，当p(n)等于50的时候，至少两个人生口相同的概率已经趋近于lo注：p(n)这条线是我们运

6、用上面生日悖论的求解方法计算得出的。1.00.8这个问题不容忽视，因为它意味着，在密码学中，我们低估了散列值出现碰撞的概率。这一结论应用于对散列函数的攻击屮，称为“生日攻击(BirthdayAttack)”。我们先把这个问题与生日脱钩，写成一般形式。从离散均匀分布的区间[l,d]中取岀n个整数，至少两个数字相同的概率⑵(1_FIZTi1(1一沽nsdP(d^n)=I1?n>d下面考虑一个64位散列函数，它有2钳种可能的散列值，更想100%地找到一纟0.碰撞，就需要2^4-11019次攻击。但是基于生日攻击的原理，我们只需要232109次攻击，就有约50%的概率能够攻击成

7、功。下面给出一种证明(符号沿用上面公式的):p=1—n;=(i—》n(n—1)>—2t//n(l—P)n>y/—2ln(l—P)/d^当P=0.5时n>1.17/d〜fd在V^=232次攻击中，就有约50%的概率发牛碰撞，收益降低一半，成本却开了根号，对于这些人数字来说，开根号是件不得了的事。为了提高碰撞率，我们以愛个散列作为一组，用独立的10组分别进行攻击，则一共需要约IO】。次攻击，出现碰撞的概率高于99.9%——这是一个非常理想的成功率，需要的攻击