绝对安全和香农密码系统

绝对安全和香农密码系统小组成员：

04013002廖孜04013107邓春燕

04013130陈金炜2015-12-28Part1密码系统的基本概念Concealmentsystems

Privacysystems“True”secrecysystems

：信息被“隐藏”在密码里，而不是仅仅被藏起来。即使“敌方”截获也无法获得信息。从一个简单的密码系统讲起：替换密码加密方式/密钥明文密文几个基本概念：冗余度：一段文字在不丢失任何信息的情况下在长度上最多能够省略多少字符比方说，假设英语的冗余度为75%，不是说任意从英语文本中去掉四分之三的字母，还是可以阅读，只是说，对一个充分大的N，可以找到一种编码方式将英文压缩为原来的四分之一。几个基本概念：先验概率：敌方在截获密文前破解密匙的可能性。先验概率由整个随机过程决定，由密码分析者对于情况的先验分析决定后验概率：敌方在截获密文后破解密文的可能性。敌方截获足够长的密文后，可能使得某一消息的概率趋于1而其他消息个概率总和趋于0。英文中26个字母出现文本中的频率统计：两种安全标准：理论保密性：密码分析者在具有无限时间和计算资源的条件下，密码系统的抗破译能力。实际保密性：密码分析者在有限的计算资源以及其他限制条件下，密码系统的抗破译能力。绝对安全（定义）：后验概率等于先验概率，即密文不泄露明文的任何信息

熵：一种对信息的不确定性的信息度量条件熵：设

X和Y是两个随机变量。对于

Y的任何固定值y

，得到一个(条件)概率分布P(X|y)。显然，

定义条件熵

为熵

取遍所有的

的加权平均值：

条件熵度量了由

Y揭示的

X的平均信息量。密钥和密文唯一决定明文，即其中K为密钥，C为密文，P为明文绝对安全系统：条件熵（条件信息量总平均值）在N无穷大的情况下仍不趋近于零。当H(N)趋于0的时候使它倒退到任意大的N。Part2保密系统的数学模型图像的分析：￭译码器：功能形同函数。￭接收端：。（必须存在唯一逆矩阵）￭保密系统：是一个由一定概率且唯一可逆的变换矩阵组成的集合。若组成集合的相同，则此两个保密系统相同。￭为简化处理，假设截取者知道正在使用的系统，即。简单系统的表示（线图）闭系统：对于每个信息（M），若和每个密文（E）之间都有标注密钥（K）的连线，则系统是闭系统。反之则为开系统。E1E2E3E41、维吉尼亚码

密钥：由周期为d的一串字母重复构成。规则：(密钥+信息)(mod26)举例：信息NOWSTHE

密钥GAHAHGA

密文TODSANE

保密系统的例子A:0B:1C:2D:3E:4F:5G:6H:7I:8J:9K:10L:11M:12N:13O:14P:15Q:16R:17E:18T:19U:20V:21W:22X:23Y:24Z:25延伸：使用频率分析法可以破解。最终被称为计算机之父的巴贝奇破解，其设计出世界上第一台计算机。2、矩阵系统（普雷费尔码）密钥：由25个英文字母组成的5×5字母矩阵（J由于很少使用，故省略，若出现用I代替）步骤：编密钥表--整理明文--编写密文举例：

密钥：【信息：wherethereislife,thereishope.】

整理明文：wherethereislifethereishopex密文：tkgy

owokgynlhjofcmyggkmlmbwf

保密系统的例子延伸：使用方便而且可以让频度分析法失效，但在一战中破解。￭若两个保密系统T和R有相同的信息空间，构造加权和，得到新系统：S=pT+qR(p+q=1)更一般地，构造S=p1T+p2R+…+pmU(Σpi=1)￭另一种方法是乘积运算：S=RT。S的密钥由T和R的一部分密钥组成。若：T的m个密钥的概率分别为：

S的n个密钥的概率分别为：则S的mn个密钥的概率分别为：

注意：很多情况下，变化是等效的，因此可以把他们的概率直接加起来。

保密系统的代数学纯密码&混合密码变换集。其中，相当于正在使用的特定密钥。如果所有的密钥都是相当（即：等可能）的，并且对于任意三个，都存在一个，使得，那么是“纯”密码。下面可能用到的公式：

Theorem

1.在纯密码中，将消息空间映射成其自身的操作Ti-1Ti组成一个顺序为m的组。其中，m为不同密钥的个数。证明：假设：存在，使得。故：

因此，得到：

两边取逆：

整理下标，得：Theorem

2.两个纯密码的乘积，交换顺序后是纯密码。证明：

假设：对于每个，都有对应的，使得。

*只有单一的纯密钥的系统，是纯系统。因为：。△的证明：（逆变换）（纯密码性质）△Theorem

3.在一个纯系统中，信息可以被分为剩余类的集合，密文相应地为。有如下性质：①消息剩余类是m重包含的，总共含有所有可能的信息。对于密文的剩余类也一样。②用任一密钥将中的任一信息译码，产生中密文。反过来也成立。③中的信息数，称为，等于中的密文数，也是密钥个数k地一个除数。④中的每一信息可以通过个不同的密钥译码到内的每一密文。￭概念的重要性在于，在一个纯密码中，所有密钥本质上是一样的。对于一个特定的信息，无论用哪个密钥，所有信息的后验概率是一样的。（信息剩余类）（密文剩余类）

由左图可以看出：￭4、2、1均为k=4

的除数。（满足性质③）￭M和E的变换是纯系统。（满足性质②）Theorem

4.在一个纯系统中，不同信息的后验概率和所选的密钥是独立的。密钥的后验概率在数值上是相同的，但存在不同密钥排列选择的过程。￭任意密钥的选择导致了在纯密码中的相同的问题---密码分析的问题。（上一页图）由于不同的密钥可以产生相同剩余类中的密文，意味着：相同剩余类中的密文在分析上是等效的。￭从维吉尼亚码举例：密文被写在长度为d的连续块中，当d=5时：

￭5栏被分别切开，且重组构成有意义的信息。

￭当列被切开，唯一的剩余信息是密文的剩余类Theorem5.如果是纯系统，那么。其中，是的任意两个变换。反过来，如果上述等式在系统中成立，那么是纯系统。证明：①前半部分的证明由纯系统的定义易证。②后半部分：

左边：右边：同理，可以得到：Ti、Tj等效，成立。

（②得证）△△Part3密码系统的理论安全性密码体制的组成通常情况下，一个密码体制由五元组{SL，Cn，Br，Ek，Dk}五个部分组成：·明文信息空间SL，它是全体明文s的集合；·密文信息空间Cn，它是全体密文c的集合；·密钥空间Br，它是全体密钥b的集合；·加密算法Ek:它是一族由SL到Cn的加密变换，即SL→Cn;·解密空间Dk，它是一族由Cn到SL的解密变换，即Cn→SL密码分析的类型唯密文破译：仅能对截获的密文进行分析，得出明文或密钥；已知明文破译：分析破译部分已知的明文－密文对；选择明文破译：可以选择任何明文-密文对；选择密文破译：可以选择任何密文-明文对。显然，唯密文破译是对系统的密码破解威胁最弱的一类攻击。利用信息论的语言来表述保密系统：明文熵：H(SL)=H(S1S2‥SL)密钥熵：H(Br)=H(B1B2‥Br)密文熵：H(Cn)=H(C1C2‥Cn)已知密文，关于明文的疑义度为H(SL/Cn)明文和密文之间的互信息：I(SL;Cn)=H(SL)－H(SL/Cn)①从密文中提取有关密钥的信息：I(Br;Cn)＝H(Br)－H(Br/Cn)②完全保密性对合法接收者：H(SL/CnBr)＝0所以：I(SL;CnBr)＝H(SL)－H(SL/CnBr)

＝H(SL)显然，I(SL;Cn)＝0时，为完全保密系统，或无条件保密系统，破译者无法破译。完全保密性保密系统的三个基本结论定理1：

I(SL;Cn)≥H(SL)－H(Br)说明：必须使密钥量尽可能大，才能使互信息为0。定理2：完全保密系统的必要条件：

H(Br)≥H(SL)也就是说密钥熵大于明文熵。一般明文存在剩余度，所以密钥量可以下降。定理3：存在完全的保密系统。对合法接收者：H(SL/CnBr)＝0所以：I(SL;CnBr)＝H(SL)－H(SL/CnBr)

＝H(SL)显然，I(SL;Cn)＝0时，为完全保密系统，或无条件保密系统，破译者无法破译。完全保密性问题：在唯密条件下，破译时需要处理至少多少密文量？2015-12-28已知：H(Br/Cn)＝H(Br/C1C2‥Cn）

≤H(Br/C1C2‥