密码学复习笔记（四）

Vigenere密码

  1.特点：

    具有相对较大的密钥空间；

    对称密码；多表代替密码；

    有周期性的弱点：若两个字符出现的间隔是密钥长度的倍数，则它们将以同样的方法加密。

 

  2.加密和解密的原理：    

(1)密钥是一个字符序列：k=(k0,k1,…,km-1)；

    明文x=(x0,x1,…,xN)被分成长度为m的段。

(2)加密函数：Ek(x0,x1,…,xN)=(y0,y1,…, yN)

     yi=(xi+ki%m)%26

    解密函数：Dk(y0,y1,…, yN)=(x0,x1,…,xN)

     xi=(yi-ki%m)%26

       

 3.多轮加密

       若一个明文使用密钥长度为m的维吉尼亚密码加密，得到的密文再用长度为n的密钥加密，其结果与用长度为lcm(m,n)的维吉尼亚密码加密的结果一样。

     若m,n互素，则lcm(m,n)=mxn，密钥长度很大。

4、生日攻击

很多人可能都知道这样一个有趣的事实，那就是一间屋子里只要超过23人，那么其中有两人同一天生日的概率就超过50%了，为什么呢？（先搞一段我也看不怎么懂的数学公式过来）

 

 

这一大段的推导，最终就是要得到上面这个公式，N为选择的空间，比如说365天，n表示当数字超过n时，其中有两个结果相同的概率就大于1/2。

一个比较具体的问题：

---------------------------------

 

某年级有n个人（n≤365），问至少有两个人的生日在同一天的概率有多大？

 

　　试验是对人数为n的年级进行生日调查，试验的基本结果是n个人生日的一种具体分布。由于生日出现的随机性，保证了n个生日种种分布的等可能性。

 

　　基本事件的数学结构--构造性处理：把365天设想为365个"房间"，然后按n个人的生日"对号入座"。这相当于n个可辨指点的每一个都以相同的概率，等可能地被分配到某一"室"内。基本结果总数就是把n个人安排进这365个"房间"的所有可能的不同方法数。基本结果的差异不仅依"人"、依"房"，而且还依"房"内的"人数"相鉴别。因而基本事件总数恰为从365个不同元素中每次取出n个的允许重复的排列种数365^n（乘法原理）。

 

　　所关心的事件A={至少有两人的生日在同一天}={有两人的生日在同一天}∪{有三人的生日在同一天}……。

 

　　这是一个比较复杂的事件，我们宁可从反面去考虑原事件的逆事件A'的结构：

 

　　A'={365个不同元素，每次任取n个依一定的顺序排成一列}。

 

　　由互逆事件的概率关系，即知P（A）=1-[365！/365^n(365-n)!]

 

具体的计算可有下面的结果：

 

(n\P)15\0.25,20\0.41,23\0.51,24\0.54,25\0.57,30\0.71,

40\0.89,50\0.97,55\0.99

 

　　从表中可知，只要人数n≥55，则有2人生日相同的概率已相当接近1了。

--------------------------------------------

生日攻击方法没有利用Hash函数的结构和任何代数弱性质，它只依赖于消息摘要的长度，即Hash值的长度。这种攻击对Hash函数提出了一个必要的安全条件，即消息摘要必须足够长。

这里几句话也说不清，具体内容看：http://wiki.mbalib.com/wiki/生日攻击。