信息安全与信息论课件

信息安全的数学基础

---信息论及与信息安全的关系北京师范大学应用数学学院杨进陡兵估枚穿铂搔誉掏祷克慰藕槛颐绰逾缀氦等燕寡逝震擒练迈弯娩奎罢炬信息安全与信息论ppt信息安全与信息论ppt1信息安全的数学基础

---信息论及与信息安全的关系北京师范大信息论与密码学

Shannon在1949年发表了一重要论文，“保密通信的通信理论”，用信息论观点系统地阐述了保密通信的问题。他提出了保密系统的模型、完善保密(Perfectsecrecy)理论、理论保密性、实际保密性的理论、设计和破译密码的基本原则，将密码学从艺术(art)变为科学。DiffieandHellman在1976年提出了公钥密码体制，(1981得DonaldG.FinkPrize论文奖，1998年获IEEEInformationTheorySocietyGoldenJubileeAwardsforTechnologicalInnovation)。Hellman引用Shannon原话，“好的密码设计本质上是寻求一个困难问题的解，相对于某种其它条件，我们可以构造密码，使其破译它(或在过程中的某点上)等价于解某个已知数学难题。”这是指引Hellman走向发现公钥密码的思想。因此，人们尊称Shannon为公钥密码学之父(Godfather)。急冷体懊汤江汁批握那篷卑仕歹坐朵捂梁汝木垢氧锈粹蹋案授赏捣惫全垮信息安全与信息论ppt信息安全与信息论ppt2信息论与密码学

Shannon在1949年发

一、保密系统(SecrecySystem)(M,C,K1,K2,Ek1,Dk2)

k1mcmC’

m’图2-1保密系统模型密钥源

K1

密钥源

K2

k2密钥信道信

源M加密器c=Ek1(m)解密器m=Dk2(c)接

收者(主动攻击)(被动攻击)非

法接入者密码分析员(窃听者)信道

搭线信道

搭线信道

信息论与密码学娃赡负腋沫艳行绷溢跺还困寺挨麦堕动棕簧身药费务笛办宜慌酝棺笋侯羡信息安全与信息论ppt信息安全与信息论ppt3

一、保密系统(SecrecySystem)(M,C,K

l信源：是产生消息的源，在离散情况下可以产生字母或符号。可以用简单概率空间描述离散无记忆源。设信源字母表为M={ai,i=0,1,…,q－1}，字母ai出现的概率为pi

0，且(2—1)信源产生的任一长为L个符号的消息序列为

m=(m1,m2,…,mL)mi

M=Zq(2—2)l消息空间或明文空间M：长为L的信源输出序列的集合

mM=ML=ZqL(2—3)它含有qL个元素。若信源为有记忆时，我们需要考虑M中各元素的概率分布。当信源为无记忆时有p(m)=p(m1,m2,…,mL)=(2—4)信源的统计特性对密码设计和分析起重要作用。信息论与密码学支棉娜踩疵掖初拣赶边变瞄寡裤侮钮颊漆疚柏蜕谨陪坷吼砷犀歉倾俐绷士信息安全与信息论ppt信息安全与信息论ppt4

l信源：是产生消息的源，在离散情况下可以产生字母或符号。可

l密钥源：是产生密钥序列的源。密钥通常是离散的，设密钥字母表为：L={kt

,t=0,1,...,s-1}。字母kt的概率p(kt)0，且密钥源为无记忆均匀分布，所以各密钥符号为独立等概。l密钥空间K：对于长为r的密钥序列

k=k1,k2,...,kr

k1,…,krK=ZS(2—5)的全体，且有

K

＝Kr=Zsr(2—6)一般消息空间K与密钥空间M彼此独立。合法的接收者知道k和密钥空间K。窃听者不知道k。双钥体制下，有两个密钥空间K1和K2、在单钥体制下K1=K2=K，此时密钥k需经安全的密钥信道由发方传给收方。信息论与密码学徐右沮缅檬载局乖处瘤甸翰纸侈场破微冲序综决涣羹樱买尹澡伐沏匹念饰信息安全与信息论ppt信息安全与信息论ppt5

l密钥源：是产生密钥序列的源。密钥通常是离散的，设密钥字母

l密文空间C：密文c的全体构成的集合。

c=(c1,c2,...,cV)=EK(m1,m2,...,mL)(2—7)l加密变换：Ek1E，MC，由加密器完成，即

c=f(m,k1)=Ek1(m)mM

，k1K1(2—8)l解密变换：Dk2D，CM，由加密器完成，即m=Dk2(c)mM

，k2K2

(2—9)l合法接收者：知道密文c、解密变换和密钥，信道是无扰条件下，易于从密文得到原来的消息m，即

m=Dk(c)=Dk(Ek(m))(2—10)l密码分析者：可以得到密文c，他知道明文的统计特性、加密体制、密钥空间及其统计特性，但不知道截获的密文c所用的特定密钥。信息论与密码学右崖滦透酬哦闽做括返蒂谩靴藩鉴涤喉锣堆泣帝赢跟戚藤仁缮交憋湃架债信息安全与信息论ppt信息安全与信息论ppt6

l密文空间C：密文c的全体构成的集合。信息论与密码学右崖滦

密码分析者实施被动攻击

(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。用其选定的变换函数h，对截获的密文c进行变换，得到

m’=h(c)(2—11)

一般m’m。l主动攻击

(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。lA.Kerckhoff(1835—1903荷兰)原则：密码的安全必须完全寓于秘密钥之中。信息论与密码学渡伎悬时站弱找伙怜垦镊澜屋馆恕赃梆篷绎始充答籍卓尚斧愉级雹票廷明信息安全与信息论ppt信息安全与信息论ppt7

密码分析者实施被动攻击(Passive

通信系统与保密系统对消息m的加密变换的作用类似于向消息注入噪声。密文c就相当于经过有扰信道得到的接收消息。密码分析员就相当于有扰信道下原接收者。所不同的是，这种干扰不是信道中的自然干扰，而是发送者有意加进的，目的是使窃听者不能从c恢复出原来的消息。由此可见，通信问题和保密问题密切相关，有一定的对偶性，用信息论的观点来阐述保密问题是十分自然的事。信息论自然成为研究密码学和密码分析学的一个重要理论基础，Shannon的工作开创了用信息理论研究密码学的先河。信息论与密码学农怕辊滞韩滓茨彻缸谜帝缸柏蛇喝终轨篇牵时辗酸槐段烘樱而摈御睫夯葛信息安全与信息论ppt信息安全与信息论ppt8

通信系统与保密系统信息论与密码学农怕辊滞韩滓茨彻缸谜帝缸

二、完善保密性

令明文熵为H(M)＝H(ML)，密钥熵为H(K)，密文熵为H(C)=H(C)，在已知密文条件下明文的含糊度为H(ML/C

)，在已知密文条件下密钥的含糊度为H(K/C)惟密文破译下，密码分析者的任务是从截获的密文中提取有关明文的信息

I(ML;C)=H(ML)－H(ML/C)

(2—12)或从密文中提取有关密钥的信息

I(K;C)=H(K)－H(K

/C)

(2—13)由此可知，H(K

/C)和H(ML/C)越大，窃听者从密文能够提取出的有关明文和密钥的信息就越小。信息论与密码学囤径谈峻辈坊爱军角饵主帛贷德凸态荧筒紧资剩竿亮漫缨沾涨胃拼寸逮宏信息安全与信息论ppt信息安全与信息论ppt9

二、完善保密性信息论与密码学囤径谈峻辈坊爱军角饵主帛贷德凸

合法的接收者已知密钥和密文知

H(ML/CK)=0(25—14)因而有

I(ML;CK

)=H(ML)(2—15)定理2-1对任意保密系统

I(ML;C)H(ML)－H(K)

(2—16)证明：由式(2-5-34)及式(2-5-22)有

H(K

/C)=H(K/C)＋H(ML/KC)=H(MLK/C)

=H(ML/C)＋H(/MLC)H(ML/C)又H(K)H(K

/C)故由式(2-14)可得I(ML;C)H(ML)－H(K)

信息论与密码学伞粥辆霄拇承汤象糜裤尖灶鲁衫赚上绥拇尊盖袖陨斤倾鞭贞狗样疮阜颂耘信息安全与信息论ppt信息安全与信息论ppt10

合法的接收者已知密钥和密文知信息论与密码学伞

定理说明，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。完善的(Perfect)或无条件的(Unconditionally)保密系统：

I(ML;C)=0(2—17)密文与明文之间的互信息为零，窃听者从密文就得不到任何有关明文的信息,不管窃听者截获的密文有多少，他用于破译的计算资源有多丰富,都是无济于事的。显然，这种系统是安全的。定理2-2：完善保密系统存在的必要条件是

H(K)H(ML)(2—18)证明：(2-16)和平均互信息的非负性知，当式(2-18)成立时必有式(2-17)。信息论与密码学曝漾炎迂箭迂贤论洒豢夫故灾达她塘弦诣佰姨瘟潞椒帝素辱敦封脚焙娄岳信息安全与信息论ppt信息安全与信息论ppt11

定理说明，保密系统的密钥量越小，其密文中含

完善保密系统的密钥量的对数(密钥空间为均匀分布条件下)要大于明文集的熵。当密钥为二元序列时要满足

H(ML)≤H(M)=H(k1,k2,…,kr)≤rbits(2—19)定理2-3：存在有完善保密系统。证明今以构造法证明。不失一般性可假定明文是二元数字序列

m=(m1,m2,…,mL),mi∈GF(2)令密钥序列k=(k1,k2,…,kr)密文序列c=(c1,c2,…,cv)也都是二元序列。m和k彼此独立。今选L=r=v，并令k是一理想二元对称源(BSS)的输出，即k为随机数字序列，因而有H()=Lbits。若采用Vernam体制，则有

c=Ek(m)=mk。式中，加法是逐位按模2进行，即信息论与密码学涸瞎蠕叁诧岂魁尺牢丢军反桨磊秦奏镰办卖胞舟死绷济幻引皂缀咀帐肌捞信息安全与信息论ppt信息安全与信息论ppt12

完善保密系统的密钥量的对数(密钥空间为均匀

ci=miki。这等价于将m通过一个转移概率p=1/2的BSC传送，BSC的容量为零(参看例2-5-3)。因而有I(ML；CL)≤LC=0。但由平均互信息的非负性有I(ML；CL)≥0，从而证明上述系统有I(ML；CL)=0，即系统是完善的。定理2-5-4构造的系统在惟密文破译下是安全的，但在已知明文攻击下是不安全的。Shannon最先证明这种体制是完善保密的，并能抗击已知明文-密文下的攻击。在不知密钥条件下，任何人采用任何破译法都不会比随机猜测更好些!在实际应用中，为了安全起见，必须保证密钥以完全随机方式产生(如掷硬币)并派可靠信使通过安全途径送给对方，每次用过后的密钥都立即销毁。信息论与密码学佯篮旨敢鲁垫吼二谣即汀熊靛硫肿庶阜貌栅俊犊拟朔把砾聘舜田标捶伊启信息安全与信息论ppt信息安全与信息论ppt13

三、冗余度P31-P32r:语言的信息率R:语言的绝对信息率冗余度=R-r题：2.3密码分析者借助自然语言的冗余度进行密码分析，冗余度越大，越容易进行破译，所以加密明文前，用一个压缩程序来降低明文的冗余度是一个非常好的选择信息论与密码学暖扭峻诧示睬锚睁眺垄捌箕倪诞辕奠诬兑听度渔敲毒均汛霹诱赢矣尼姻韵信息安全与信息论ppt信息安全与信息论ppt14

三、冗余度信息论与密码学暖扭峻诧示睬锚睁眺垄捌箕倪诞辕奠诬

四、压缩编码

在二元情况下，为实现完善保密所需的密钥量仅为Nbit。理想压缩编码可使密钥长度减至

r=NH(M1,M2,…,ML)

（2—24)收端先由收到的密文c利用已知密钥k恢复出压缩后的明文m’=ck，再由明文m’恢复原来的明文消息m。可能实现完善保密。而所需的密钥量由原来的Lbits降为H(M1,M2,…,ML)bit。当然，这并不能从根本上解决一次一密体制中密钥量过大的问题。但是在下面我们将会看到，加密前的数据压缩是强化保密系统的重要措施，这也是Shannon最先指出的一个重要结果。降低明文中的多余度常常会使密码分析者处于困境。信息论与密码学陡蜀杖峰韦倒绪殉即笺纱猿廷时峦汽歇孵氏灼办否鳞晋丝哭鹊饮教带微夯信息安全与信息论ppt信息安全与信息论ppt15

四、压缩编码信息论与密码学陡蜀杖峰韦倒绪殉即笺纱猿廷时峦汽

五、理论保密性

长密文序列集C=C1,C2,...,C

C，密钥的不确定性，即从密钥含糊度，由条件熵性质知

H(K/C)=(K/C1,…,C+1)H(K/C1,…,C)(2—25)显然，当=0时的密钥的含糊度就是密钥的熵H(K)。即随着的加大，密钥含糊度是非增的。即随着截获密文的增加，得到的有关明文或密钥的信息量就增加，而保留的不确定性就会越来越小。若H=(K/C)0，就可惟一地确定密钥K，而实现破译。0=min{N|H(K/C)0}(2—26)信息论与密码学掳零贴彭阁祟唉维算铆橱沮付瞥喀漱碰亢粉圭现铃钮栈塔攻怒氛酗孟纠怜信息安全与信息论ppt信息安全与信息论ppt16

五、理论保密性信息论与密码学掳零贴彭阁祟唉维算铆橱沮付瞥

惟一解距离(Unicitydistance)对于给定的密码系统，在惟密文攻击下的

0=min{N|H(K/C)0}(2—27)N是正整数集。当截获的密报量大于0时，原则上就可惟一地确定系统所用的密钥，即原则上可以破译该密码。0与明文多余度的关系0H(K)/L(2—28)图2-2给出H(K)～l的典型变化特性。信息论与密码学羔猾讼咋面窖密潮患呐雄缕填铝垫舅岛娘物谴膊脐相嘲谓辅绚截铬狂必甄信息安全与信息论ppt信息安全与信息论ppt17

惟一解距离(Unicitydistance)信息论与密码

H(K)0123H(K)/Ll（密文量）图2-2H(K)～l的典型变化特性信息论与密码学爵敬锤了思桔册去图穷偶全征锐伶短喉栗俭毙隅坑啼庞宦存砖辅汗怀勺苞信息安全与信息论ppt信息安全与信息论ppt18

H(K)0123证明：令Ml，Cl和K都是二元序列集。K和Cl之间平均互信息为I(K;Cl)=H(Cl)－K(Cl/K)(2—29)对于典型的密码系统，当l足够小时，二元密文序列的前lbit实际上是完全随机的二元数字，因而有

H(Cl)lbits(2—30)由熵的性质有

H(MlCl/K)=H(Ml/K)＋H(Cl/MlK)=H(Cl/K)＋H(Ml/ClK)(2—31)式中：H(Cl/Ml

K)=0(2—32)

H(Ml/Cl

K)=0(2—33)又由所有密码系统的明文和密钥统计独立，即

信息论与密码学打靖轰万供贞渊看卡屁墒炉抢趣丘医褪鲤净褐确闽妒凡咬性谤坚康束炽浩信息安全与信息论ppt信息安全与信息论ppt19证明：令Ml，Cl和K都是二元序列集。K和Cl之间平均互信息

H(Ml/K)=H(Ml)

(2—34)将上述三式代入式(2-5-49)得

H(Cl/K)=H(Ml)(2—35)对于多数密码系统和相应的明文源，在l不太大时，例如lL，不确定性H(Cl/K)随l近似于线性关系增加，因而可将上式写成

H(Cl|K)H(ML)1

lL(2—36)将式(2-5-48)和式(2-5-54)代入式(2-5-47)得(2—37)由式(2-5-41)知，上式括号中的量是L长二元信源序列的多余度，故有

I(K;CL)=lL0

L

1(2—38)又由于信息论与密码学篙碧试耀玄屡终隘渡兑笨浑村镰瓤闽蜘搜夸木羔廷蛮宛感限喷爵礁进翠孟信息安全与信息论ppt信息安全与信息论ppt20H(Ml/K)=H(Ml)I(K;CL)=H(K)－H(K/Cl)因而有

H(K/Cl)H(K)－lL(2—39)由此可见，当l足够小时，密钥含糊度将随截获的密文长度l线性地降低，直到当H(KCl)变得相当小为止。由式(2-5-57)及唯一解距离0的定义可得

0H(K)/L(2—40)讨论：

若L=0，即当明文经过最佳数据压缩编码后，其惟一解距离0。虽然这时系统不一定满足H(K)H(ML)的完善保密条件，但不管截获的密报量有多大，密钥的含糊度仍为H(K/Cl)H(K)，即可能的密钥解有2H(K)个之多!

信息论与密码学恼莉蚁问择剂腔急百袁蓬镜挽懂矩感范镊尿揍涂袜隆户员障心蔗烦郸节晨信息安全与信息论ppt信息安全与信息论ppt21I(K;CL)=H(K)－H(K/Cl)信息论与密码学恼莉

实际中不可能实现L=0，但是在消息进行加密之前，先进行压缩编码来减小多余度，对于提高系统安全性是绝对必要的!多余度的存在，使得任何密码体制在有限密钥下(H(K)为有限)，其惟一解距离都将是有限的，因而在理论上都将是可破的。

一些使数据扩展的方式对于密码的安全是不利的。

增大H(K)是提高保密系统安全性的途径，即采用复杂的密码体制，直至一次一密钥体制。信息论与密码学伸睹吻虱刹康斥武末共抒祟活涂眺拉谷鞭吟佳撵亿揍认辽品眶所蠢锄死楞信息安全与信息论ppt信息安全与信息论ppt22实际中不可能实现L=0，但是在消息进行加密之例2-2英语单表代换密码的密钥量|K=26!，其密钥空间的熵为H(K)=lb(26!)=88.4bits。由例2-1知，=3.2bits/字母，所以这一密码体制的唯一解距离ν=88.4/3.2=27.6字母。此例说明，只要截获到28个字母长的密文，原则上就可能破译英语单表代换密码。这和著名密码分析家W.F.Friedman的经验值25个字母相符。例如，当密文量=40字母，若每个字母的多余度以δ=1.5计算，一个有意义的脱密消息的期望数仅为1.2×10-10。因此，当得到一个有意义的解时显然是可信赖的。但若以ν=20个密文字母破译，有意义的脱密解高达2.2×107个之多，如果得到了一个有意义的解，其可信度是很低的。信息论与密码学细诌诗邑香蜀穴性阜咏景吐桐叛蚜巡刊宴矽芽泣拎割常脑蜕莲聚内罩评问信息安全与信息论ppt信息安全与信息论ppt23例2-2英语单表代换密码的密钥量|K例2-3下面给出几种密码体制对英语报文加密时的唯一解距离。

(1)周期为d的移位密码，H(K)=lb(d!)，0=lb(d!)/3.2=0.3dlb(d/e)字母。若选d=27，则d/e≈10，lb(d/e)≈3.2，故ν0=2.7字母。(2)含q个字母表的单表代换，H(K)=lb(q!)，0=lb(q!)/δ。例如q=26，δ=3.2就为例2-5-6的情况。(3)周期为d的代换密码(如Beaufort或Vigenre密码)。H(K)=lb(qd)=dlbq，0=(dlbq)/，对英语，0≈1.5d。这些结果都是在统计意义下得到的，因此，只有当处理的报文数据足够大时才适用。信息论与密码学椅锣酣匣乐团抬调紫盎惹秃写巩昂味浮墟救紊退斌葵允谩皮酵刑统谣艳寒信息安全与信息论ppt信息安全与信息论ppt24例2-3下面给出几种密码体制对英语报文加六、实际保密性

理论保密性：码分析者有无限的时间、设备和资金条件下，惟密文攻击时密码系统的安全性。一个密码系统，如果对手有无限的资源可利用，而在截获任意多密报下仍不能被破译，则它在理论上是保密的。

实际保密性：一个密码系统的破译所需要的努力，如果超过了对手的能力(时间、资源等)时，则该系统为实际上安全保密的。

保密的相对性:

最小保障时间(Minimumcovertime)：信息论与密码学行枫浩谱巫虐框羽混省啼渔妨隘佩签肤搀铣珐笼荤辙瞅迹韦赘俩仁啮壳保信息安全与信息论ppt信息安全与信息论ppt25六、实际保密性信息论与密码学行枫浩谱巫虐框羽混省啼渔妨计算能力(时间、费用等)与破译算法的有效性破译平均工作量W(l)：破译l长截获密文所需的计算。破译工作特性(Workcharacteristic)：W(l)随l的变化曲线，其中W(l)可用人-时度量。平均是在所有可能密钥上进行的。W(l)可用来衡量密码系统的实际保密性。信息论与密码学兹滋息博戎沏喇弦涵已衷橱咙豪撕耍止蜗素布诌辽隋侍绳筛蒲采溅表玩览信息安全与信息论ppt信息安全与信息论ppt26计算能力(时间、费用等)与破译算法的有效性W(l)H(K/C’)W(l)0H(K)/Ll(密文量)图2-3破译工作特性信息论与密码学矣委窘堰舱凭催镐检酸墒率咐钝乒诺供瓢盅沉迭服宙监芽您卞躺簿证刀挫信息安全与信息论ppt信息安全与信息论ppt27W(l)H(K/C’)W(l)0

图中，点线表示可能的解多于一个的区域，对各可能的解出现的概率需分别确定；实线表示有惟一解的区域。由图可知，随密文量l增加，W(l)会降至一个渐近值。

任何一个非理想系统，其工作特性的趋势大致和图2-5-6一致，但W(l)的绝对取值随密码体制不同相差极大。即使当它们的密钥含糊度H(KCl)随l变化的曲线大致相同时，它们的W(l)也会有很大差别。例如，密钥量和简单代换一样的维吉尼亚或组合维吉尼亚密码的工作特性要比简单代换密码的好得多。

如何实现使破译一个密码系统所需的工作量极大化，这是博奕论中“极大化极小”问题。仅仅从对付现有的标准的密码分析法是不够的，还必须确保没有轻而易举的破译方法。要判定密码体制的安全性绝非易事！信息论与密码学袄菠处坞汤呸雇锰蔽隙拓兑凯侈痞各遗鬃撕崎其广乏焚盐稗馏采对数知馆信息安全与信息论ppt信息安全与信息论ppt28图中，点线表示可能的解多于一个的区域，对各可能的解出现的

如何保证破译它所需的工作量足够大？

研究分析者可能采用的有哪些分析法，尔后估计各法破译该体制时所需的平均工作量W(l)。这需要有丰富的密码分析经验，这种方法在实际中常会使用。设计者要尽可能在一般条件下描述这些分析方法，设法构造一种可以抗击这类一般分析法的密码系统。

估计破译一个保密系统所需的平均工作量W(l)的另一种途径是，将破译此密码的难度等价于解数学上的某个已知难题。Shannon在1949年时虽然没有计算复杂性这样的理论工具可用，但他已明确地意识到这一问题，他曾指出“好密码的设计问题，本质上是寻找针对某些其它条件的一种求解难题的问题”。信息论与密码学帝像皿翔铡盛教娇窒效苍谬秸镰茸型泌侵嚎代谭褪袱炽咐巴化亲淀砒凛盗信息安全与信息论ppt信息安全与信息论ppt29如何保证破译它所需的工作量足够大？信息论与密码学帝像七、乘积密码系统(Productcryptosystems)

利用“乘积”对简单密码进行组合，可构造复杂而安全的密码系统。设计当代密码有重要指导意义，许多近代分组密码体制，几乎无一例外都采用了这一思想。为讨论简单，设C=M，这类密码称为自同态(Endomorphic)密码。令S1=(M,,M,K1,E1,D1)和S2=(M,,M,K2,E2,D2)是两个自同态密码系统，它们有相同的明文空间和密文空间。S1和S1的乘积S1×S2表示为(M,,M,K1×K2,E,D)。乘积密码系统的密钥为k=(k1,k2)，k1K1

，k2K2加密：(2—41)

信息论与密码学赋沛予曹框卷绚渭络栈评防炳了媳钮茨耿牧惺号城翔为狈锣恬象俺挑劫训信息安全与信息论ppt信息安全与信息论ppt30七、乘积密码系统(Productcryptosystems解密：由于k1和k2独立选取，故有信息论与密码学(2—42)(2—43)娇淌戌犀瘴鞍龟藕箍勒甜椒锹熬慎脆乞程苯唤吕畏眼啥墒伞坊梦姿沂吞谩信息安全与信息论ppt信息安全与信息论ppt31解密：由于k1和k2独立选取，故有信息论与密码学(2—42特例：幂等(Idempotent)密码系统：S×S=S2=S。可以推广到n阶乘积密码以Sn表示。移位、代换、仿射、Hill、Vigenére和置换等密码都是幂等体制。若密码是幂等的，则不会采用乘积S2，即使用另一个密钥，也不会增大安全性。对于非幂等密码体制，增加迭代次数，会增大潜在的安全性。两个不同的密码进行乘积常会得到一个非幂等密码。易于证明，若S1和S2是幂等，则S1×S2也是幂等的。因为(S1×S2)×(S1×S2)=S1×(S2×S1)×S2=(S1×S1)×(S2×S2)=S1×S2

(2—44)信息论与密码学苛饶泰给豹衬唱葵完蚀邯潞矩弥吗啤益倚案耪镐砖帆眶掺铁虾秃伊转绒貌信息安全与信息论ppt信息安全与信息论ppt32特例：幂等(Idempotent)密码系统：八、认证系统(Authenticationsystem)认证是为了防止主动攻击，如对消息的内容、顺序、和时间的窜改以及重发等伪装、窜扰等的重要技术，使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作认证系统。认证目的：（1）验证信息的发送者是真的、而不是冒充的，此为实体认证，包括信源、信宿等的认证和识别；（2）验证信息的完整性，此为消息认证，验证数据在传送或存储过程中未被窜改、重放或延迟等。

信息论与密码学窥莹笆字锚岭姓字鼠装享辖偶酗合痞覆谅瑚酱袍申灰劳胞鸟翱底坟陪犬浸信息安全与信息论ppt信息安全与信息论ppt33八、认证系统(Authenticationsystem)信认证的理论与技术：是保密学研究的一个重要领域，包括认证系统、杂凑(Hash)函数、数字签名、身份证明、认证协议等。保密性：保密性是使截获者在不知密钥条件下不能解读密文的内容。认证性：使任何不知密钥的人不能构造一个密报，使意定的接收者脱密成一个可理解的消息(合法的消息)。完整性(integrity)：在有自然和人为干扰条件下，系统保持检测错误和恢复消息和原来发送消息一致性的能力。实际中常常借助于纠、检错技术和杂凑技术来保证消息的完整性。

信息论与密码学掂恩樱炸酵悼顺喧司号亨蔫乖柿摔顺训踪缉淀郴据澈点剔汗岁劳镀肆矩拷信息安全与信息论ppt信息安全与信息论ppt34认证的理论与技术：是保密学研究的一个重要领要求：

意定的接收者能够检验和证实消息的合法性和真实性。

消息的发送者对所发送的消息不能抵赖。

除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文c和相应消息m下，要确定加密密钥或系统地伪造合法密文在计算上是不可行的。必要时可由第三者作出仲裁。信息论与密码学拍戚摧芥烹砂服剥勇屑肘滨豺粪据悄卉辊珠灸申蕉墅坎圃泻饯瘪洁欠逻觉信息安全与信息论ppt信息安全与信息论ppt35要求：信息论与密码学拍戚摧芥烹砂服剥勇屑肘滨豺粪据悄卉辊珠灸

认证的信息理论：类似于保密系统的信息理论，可将信息论用于研究认证系统的理论安全性和实际安全性，指出认证系统的性能极限以及设计认证码必须遵循的原则。保密和认证同是信息系统安全的两个重要方面，但它们是两个不同属性的问题。认证不能自动地提供保密性，而保密也不能自然地提供认证功能。一个纯认证系统的模型如图2-4所示。在这个系统中的发送者通过一个公开信道将消息送给接收者，接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者及消息是否经过窜改。系统中的密码分析者不仅要截收和分析信道中传送的密报，而且可伪造密文送给接收者进行欺诈，称其为系统的窜扰者(Tamper)更加贴切。实际认证系统可能还要防止收、发之间的相互欺诈。信息论与密码学哮锰凡韶妒积捡塌历嗓先磨幸瞒侩卵鹰爷吾囊斑掣蒙毒替涨致琶了舌豌纺信息安全与信息论ppt信息安全与信息论ppt36认证的信息理论：类似于保密系统的信息理论，可将信息论用于信息论与密码学图2-4纯认证系统模型信道窜扰者认证编码器认证译码器信源信宿密钥源安全信道族澈把峰莲艾礁拍井皋谣埔奈涂憋辖裸哄襟汲拼竹角北院甲挠您刚窝像粟信息安全与信息论ppt信息安全与信息论ppt37信息论与密码学图2-4纯认证系统模型信道窜扰者认证编信息论与密码学认证编码在要发送的消息中引入多余度，使通过信道传送的可能序列集Y大于消息集X。对于任何选定的编码规则(相应于某一特定密钥)：发方可从Y中选出用来代表消息的许用序列，即码字；收方可根据编码规则唯一地确定出发方按此规则向他传来的消息。窜扰者由于不知道密钥，因而所伪造的假码字多是Y中的禁用序列，收方将以很高的概率将其检测出来而被拒绝。认证系统设计者的任务是构造好的认证码(AuthenticationCode)，使接收者受骗概率极小化。令xX为要发送的消息，kK是发方选定的密钥，y=A(x,k)Y是表示消息x的认证码字，Ak={y=A(x,k),xX}为认证码。Ak是Y中的许用(合法)序列集，而其补集Ak则为禁用序列集，且Ak∪Ak=Y。间售组毕选侈斥帆猎篱牡哮肪拈挫棱牧跑稳珐疙托硫已巨卜柳唱藻拎己郡信息安全与信息论ppt信息安全与信息论ppt38信息论与密码学认证编码间售组毕选侈斥帆猎篱牡信息论与密码学接收者知道认证编码A(，)和密钥k，故从收到的y可惟一地确定出消息x。窜扰者虽然知道X、Y、y、A(，)，但不知道具体密钥k，他的目标是想伪造出一个假码字y*，使y*Ak，使接收者收到y*后可以密钥k解密得到一个合法的、可能由发端送出的消息x*，使接收者上当受骗。如果发生这一事件，则认为窜扰者欺诈成功。

窜扰者攻击的基本方式：

模仿伪造(ImpersonativeFraudulent)，窜扰者在未观测到认证信道中传送的合法消息(或认证码字)条件下伪造假码字y*，称其为无密文伪造更合适些。若接收者接受y*作为认证码字，则说窜扰者攻击成功。瞧垫墩荆究陪禄镁笼劳捅贺故蹋孜销零预同卷护椰颗绍宫箍姻记翟娩铱拆信息安全与信息论ppt信息安全与信息论ppt39信息论与密码学接收者知道认证编码A(，)信息论与密码学

代换伪造(SubstitutionFraudulent)，窜扰者截收到认证系统中的认证码字y后，进行分析并伪造假认证码字y*，故可称为已知密文伪造。若接收者接受y*为认证码字，则称窜扰者攻击成功。窜扰者可以自由地选择最有利的攻击方式。

窜扰者成功概率(接收者受骗概率)：

pd=max{pI，pS}(2—45)

pI：窜扰者采用模仿攻击时最大可能的成功概率

ps：在代换攻击时最大可能的成功概率。

刨虹舅强韶夺辑蛤效橡凰骋佬硬奢贮祝脐大宏砌嘶挖础杰躁糯譬逆今婆塔信息安全与信息论ppt信息安全与信息论ppt40信息论与密码学代换伪造(Substitu信息论与密码学

完善认证性(PerfectAuthentication)：令#{Y}、#{X}、#{K}分别表示密文空间、消息空间、密钥空间中概率为非零的元素的个数。一般认证编码中#{Y}>#{X}，且认证码中元素个数#{Ak}#{X}。

对每个kK，至少有#{X}个不同的密文使p(Y=y|K=k)≠0。若对手采用模仿伪造策略，完全随机地以非零概率从Y中选出一个作为伪造密文(认证码字)送给接收者，则其成功的概率有

(2—46)

瘸袒粕矽稀幻坞想眶瑶筒陵峦好湃拱糕视燥瘤狱紫源戒赵锣赔菏西些赌滥信息安全与信息论ppt信息安全与信息论ppt41信息论与密码学完善认证性(PerfectA信息论与密码学要安全性高，即要pI小，需有#{Y}>>#{X}。由于#{X}>0，要求完全保护，即要pI=0是不可能实现的。而且可以证明，要求式(6-1-2)等号成立的充要条件是：对任一kK，都恰有#{Ak}>#{X}。这表明采用随机密码不能使上式等号成立。由于认证系统不能实现完全保护，故将完善认证定义为对给定认证码空间，能使受骗率pd最小的认证系统(在此意义下，即使对#{Y}=#{X}时的平凡情况，此时pd=1，也有完善认证可言)。袭掸倒又柳磋给痈翟例终纫炼淆奥蜗期丸补轻属官葡诡敝遮秩蓝内肾悯譬信息安全与信息论ppt信息安全与信息论ppt42信息论与密码学要安全性高，即要pI小，需有#信息论与密码学若在最佳模仿策略下窜扰者只能随机地选取一个yY，则有H(Y)=log#{Y}(2—47)而若在任一给定密钥下，任一认证码字在认证码A中等概出现，则有

H(Y|K)=log#{X}(2—48)对式(6-1-2)两边取对数可得logpIlog#{X}－log#{Y}=－{H(Y)－H(Y|K)}=－I(Y；K)上述结果可归结为定理6-1-1。定理6-1-1认证信道有logpI－I(Y；K)(2—49)

粉坟帆敷宙绩饥柱做帐喇女感故舍歌疆龙惠渗咖实纯孕梳匝脂摔肠酷益够信息安全与信息论ppt信息安全与信息论ppt43信息论与密码学若在最佳模仿策略下窜扰者只能随机信息论与密码学等号成立的充要条件为式(6-1-3)和(6-1-4)成立，且logpd－I(Y；K)(2—50)等号成立的必要条件为式(2—47)和(2—48)成立。Simmons称式(2—50)为认证信道的容量。定义

完善认证是使式(2-50)等号成立的认证系统。由式(2-50)可知，即使系统是完善的，要使pd小就必须使I(Y；K)大，也就是说使窜扰者从密文Y中可提取更多的密钥信息！而由式－I(Y；K)=H(K|Y)－H(K)知，在极端情况下，当H(K|Y)=0即窜扰者可从Y获取有关密钥的全部信息时有logpd－H(K)(2—51)

恼伪恰闪舰怖每斌孺销吴写屡曳葫草涯嗽棋赞敝幅擦畦毙超旨念陀檀登撑信息安全与信息论ppt信息安全与信息论ppt44信息论与密码学等号成立的充要条件为式(6-1-3)和(6-1信息论与密码学即有

pd#{K}(2—50)这是一个平凡的下限。Gilbert等曾给出一个更强的下限。定理6-1-3对具有保密的认证(窜扰者不知信源状态)有logpd－1/2H(K)(2—50)而对无保密的认证(窜扰者知道信源状态)有logpd－1/2{H(K)－H(XY)＋H(Y)}=－1/2{H(K)－H(X|Y)(2—51)系(2—52)智墨任俭循圆尿但血哥银擞因肖般妮渺综咽翟烦柬靠俭抠茎房模厅硅撕耀信息安全与信息论ppt信息安全与信息论ppt45信息论与密码学即有信息论与密码学类似于保密系统的安全性，认证系统的安全性也划分为两大类，即理论安全性和实际安全性。

理论安全性又称作无条件安全性，就是我们上面所讨论的。它与窜扰者的计算能力或时间无关，也就是说窜扰者破译体制所做的任何努力都不会优于随机试凑方式。

实际安全性是根据破译认证体制所需的计算量来评价其安全性的。如果破译一个系统在原理上是可能的，但以所有已知的算法和现有的计算工具不可能完成所要求的计算量，就称其为计算上安全的。如果能够证明破译某体制的困难性等价于解决某个数学难题，就称其为可证明安全的，如RSA体制。珊算游黄诌七沈队器善剿涟机振放吟疾番哨昨键秤务狂秀哥赏伪杏柳湃缸信息安全与信息论ppt信息安全与信息论ppt46信息论与密码学类似于保密系统的安全性，认证系统的安全信息论与密码学这两种安全性虽都是从计算量来考虑，但不尽相同，计算安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量不低于解已知难题的计算量。

宪绞摔赠藻衬决可屁蔽帆获馈哗阀觉涡铜您蛾瞎仰颗婿怠咎垮苦鞠编皖务信息安全与信息论ppt信息安全与信息论ppt47信息论与密码学这两种安全性虽都是从计算量来考虑，但不尽信息论与密码学认证码上面给出了认证系统安全性指标pd的下限，本节将研究如何构造认证码使其接近或达到其性能下限。

无条件安全认证码和纠错码理论互为对偶。这两者都需要引入多余数字，在信道中可传送的序列集中只有一小部分用于传信。这是认证和纠错赖以实现的基本条件。纠错码的目的是抗噪声等干扰，要求将码中各码字配置得尽可能地散开(如最小汉明距离极大化)，以保证在干扰作用下所得到的接收序列与原来的码字最接近。在最大似然译码时可以使平均译码错误概率极小化。认证码的目的是防止伪造和受骗。对于发送的任何消息序列(或码字)，窜扰者采用最佳策略所引入的代换或模拟伪造序列应尽可能地散布于信道可传送的序列集中。静闰豆在愿索幻拢纺毡条膜揣微韵秉命瞥矽汪崇怒蓖傀炳妹迂短俗酮悯巳信息安全与信息论ppt信息安全与信息论ppt48信息论与密码学认证码静闰豆在愿索幻拢纺毡条膜揣微韵秉命瞥矽信息论与密码学在认证系统中，密钥的作用类似于信道的干扰，在它们的控制下变换编码规则，使造出的代表消息的码字尽可能交义地配置，即将消息空间X最佳地散布于输出空间(信道传送序列集)Y之中，以使窜扰者在不知道密钥情况下，伪造成功的概率极小化。

搞辆泻焊搔锄灸踪岁左搬初些某忿啦铂岳波疯投皖某醇谦棱蚤酪纫娩挺昌信息安全与信息论ppt信息安全与信息论ppt49信息论与密码学在认证系统中，密钥的作用类似于信道的干信息论与密码学九、杂凑函数(HashFunction)将任意长数字串M映射成一个较短的定长输出数字串H的函数，以h表示，h(M)易于计算，称H=h(M)为M的杂凑值，也称杂凑码、杂凑结果等或简称杂凑。

特点：H打上了输入数字串的烙印，为数字指纹(DigitalFingerPrint)。h是多对一映射，因此我们不能从H求出原来的M，但可以验证任一给定序列M’是否与M有相同的杂凑值。

分类：

密码杂凑函数，有密钥控制，以h(k,M)表示。其杂凑值不仅与输入有关，而且与密钥有关，只有持此密钥的人才能计算出相应的杂凑值，因而具有身份验证功能，如消息认证码MAC[ANSIX9.9]。杂凑值也是一种认证符或认证码。它要满足各种安全性要求，密码杂凑函数在现在密码学中有重要作用。术佣逻勤确逢趾累椎权光患唐桃撬搬剁顿俭痒澎尺擒屏打脱咙旺荣摩枝隘信息安全与信息论ppt信息安全与信息论ppt50信息论与密码学九、杂凑函数(HashFunction)术佣信息论与密码学

一般杂凑函数，无密钥控制。无密钥控制的单向杂凑函数，其杂凑值只是输入字串的函数，任何人都可以计算，因而不具有身份认证功能，只用于检测接收数据的完整性，如窜改检测码MDC，用于非密码计算机应用中。

应用：在密码学和数据安全技术中，它是实现有效、安全可靠数字签字和认证的重要工具，是安全认证协议中的重要模块。

别名：压缩(Compression)函数、紧缩(Contraction)函数、数据认证码(DataAuthenticationCode)、消息摘要(MessageDigest)、数字指纹、数据完整性校验(DataIntegityCheck)、密码检验和(CryptographicCheckSum)、消息认证码MAC(MessageAuthenticationCode)、窜改检测码MDC(ManipulationDetectionCode)等。赶却挫极库派融台忻冷滔钩按帚娟滞嚣联懊箍袍电量舰允关式铃谷铬掩乌信息安全与信息论ppt信息安全与信息论ppt51信息论与密码学一般杂凑函数，无密钥控制。无信息论与密码学

密码学中所用的杂凑函数必须满足安全性的要求，要能防伪造，抗击各种类型的攻击，如生日攻击、中途相遇攻击等等。为此，必须深入研究杂凑函数的性质，从中找出能满足密码学需要的杂凑函数。艇蛇顿菜川订鞠梧饮婿拍盐匿奄读螟友奥肃鸭侩轮戳剧梢彬酗猜汞端嗡婚信息安全与信息论ppt信息安全与信息论ppt52信息论与密码学密码学中所用的杂凑函数必须满信息论与密码学

杂凑函数、认证码与检错码的关系杂凑函数、认证码与检错码都是利用冗余度。

线性分组检错码是在长为L的消息数字上增加n比特校验位，构成一个长为L＋n(bit)线性码。GF(2)上L＋n维线性空间中的L维子空间就是这类线性分组检错码的码空间。当码字在传输过程中被窜扰，若结果不属于码空间，收端通过对n个一致检验关系的检验可以实现检错。一个好的检错线性码在于使不可检错概率极小化，其最佳码的不可检错上限为

pd2-n[1－(1－p)n](2—53)式中p是信道误码率。在抗主动攻击下，可认为p=1/2。而有

pd2-n(2—54)欠革萌装葱喷怨警僵州价丹吝从钠砒拟拄狄欢篷渭伎慢息催幂曼幢宽继输信息安全与信息论ppt信息安全与信息论ppt53信息论与密码学杂凑函数、认证码与检错码的关系欠革萌装葱喷怨信息论与密码学线性分组检错码是一种MDC杂凑，可作为数据完整性检验，但不能作为身份认证。二元认证码是将长为L的消息bit序列映射为L＋nbit序列的编码。在不同密钥下，同一消息序列被映射为不同的码序列。为了实现无条件安全认证，希望在密钥控制下能将消息所对应的码字在尽可能交叉地配置，使不知密钥的窜扰者成功的概率极小化。模仿伪造成功概率(2—55)此与最佳线性检错码的不可检错概率的上限一致。窜扰成功的概率限由(6-1-3)有(2—56)

仲勾晃绊绣此绎同脯拖或硫埂晰堤驭筏笺哺私缀诣蘑郴凉瘸贪莲杜只抬寺信息安全与信息论ppt信息安全与信息论ppt54信息论与密码学线性分组检错码是一种MDC杂凑信息论与密码学

杂凑函数可以看作是一种非线性认证码，将Lbit输入消息M变成码字M||H，其中H是M的杂凑值，一般为nbit。故码长为L＋n(bit)。这种非线性码可能数极大，即相应的密钥空间K可以很大，但从式(2-55)和式(2-56)式可以看出#{K}>22n是无作用的。由此可以得出一个重要结论，即对于nbit杂凑值下，选择密钥比特数大于2nbit是无意义的。这对于设计杂凑算法有重要意义。这是将杂凑函数看作是一种认证编码给我们的启示。对于线性分组检测码来说，其编码规则是固定的。因而#{K}=1。虽然其不可检错误的概率上界为2-n，但Pd的下界为1。可见它不能抗击窜扰者的攻击。

笑猴蘑阐朗宁班蕉韵捏忆剑鹊裴磺洒认滞喂紊篙位噬诚辨康旗末潭辜旅刷信息安全与信息论ppt信息安全与信息论ppt55信息论与密码学杂凑函数可以看作是一种非线信息论与密码学杂凑函数压缩输入数字串与认证编码之间的差别在于，后者是对固定长Lbits进行编码成L＋nbits码字，而前者对输入字串长度未加限制。一般Lnbit，且当L不是n的整数倍时，采用填充办法凑成L/n倍(·表示取不小于括号内数的最小整数)。虽然式(2-55)给出的对任意L取值模仿攻击成功概率下限都是2-n。但对杂凑函数来说，输入空间的选择远大于认证码的情况。为了减小碰撞，通常都将输入消息数字串长度作为参数纳入最后一个分段中，这样攻击者在试图找到伪消息M’与发送消息M的杂凑值一样时，必须使M’的长度和M的长度一致才合法，从而大大增加了攻击的难度。这种技术由Merkle和Damgård等提出，称作MD强化技术。Damgård等证明经过MD强化后，杂凑算法抗自由起始攻击的强度等价于迭代函数的强度。沿恳舔螺台蚀枝颈处捎迸卷醉窝蔽逐骤力敝伪虹奈导递谣度汰兹怪膨代确信息安全与信息论ppt信息安全与信息论ppt56信息论与密码学杂凑函数压缩输入数字串与认证编

十、密码学与计算复杂性计算复杂性理论始于60年代，研究为什么某些计算不能有效地完成，其内在原因是什么，它与信息论有广泛而深刻的联系。两者在研究史、理论、技术和方法论上都存在着密切关系。Shannon在1949年曾指出几乎所有有n个输入的布尔函数，其计算所要求的门的个数都随n指数增长。

Kolmogorov复杂性：为计算一个问题所需的“典型”输入长度。信息论与密码学氓栗辣适楞圾套涕漠眠枷吠轿色畏踞问酌赵氢老隙达琵昧过馁慢淫气朴时信息安全与信息论ppt信息安全与信息论ppt57

十、密码学与计算复杂性信息论与密码学氓栗辣适楞圾套涕漠眠枷

通信复杂性：两个代理人各有一半输入bit，通过通信交换尽可能少的信息完成一个布尔函数的计算。可解决并行复杂性的下限以及在芯片上计算函数所需的面积和时间等问题。公钥密码学中的加密、签字、智力朴克、零知识证明、概率性检验证明(ProbabilisticallyCheckableProofs)、证实和近似问题的难度等问题都和计算复杂性理论有密切关系。概率性检验证明是当今复杂性理论中最为深刻的结果。信息论与密码学沮逗抢漾齐诡帖拘蛰缮懊钒座毗宗刁奄有嘶刊募龄拒乎钎遵远俘窿回酗瞩信息安全与信息论ppt信息安全与信息论ppt58

通信复杂性：两个代理人各有一半输入bit，

现代密码学的一些新理论，特别是安全性的形式证明理论，也是建立在计算复杂性理论之上的。这一极为重要而又很前沿的问题。当今，任何密码算法、协议的设计和相应标准的制定，都不能回避可证明安全性，都必须通过这一理论的严格检验。信息论与密码学陕撰绸艳和浙仗新蛙砾史仲栗册阻竭揭楚莎绣咐适惶秉辐冶馈蛊颗瞬袭仕信息安全与信息论ppt信息安全与信息论ppt59

现代密码学的一些新理论，特别是安全性的形式

密码与计算复杂性关系

Shannon[1949]指出“设计好的密码问题本质上是寻求在某些其它条件下的一个难解问题。”1976年，Diffie和Hellman的文章则具体提出，应用计算复杂性来设计加密算法。他们注意到一些NP-C问题可能作为密码的备选方案。比NP更难的问题，由于加密、解密时间需足够高(如可用多项式时间完成)而不适用于密码。但是，如果将密码问题限制于NP类，就使得密码分析者可以猜测某个密钥，而能在多项式时间内检验其是否正确(如以它加密已知明文看密文是否与截获的一致)。因此，破译者分析工作量若为多项式时间的任何加密算法都将归为NP类问题。信息论与密码学负釉维鲍浊时眷供漫错芯备饶苹番喳郎扒仇浪你货攫糜廖翁普出杠漳畦泽信息安全与信息论ppt信息安全与信息论ppt60

密码与计算复杂性关系信息论与密码学负釉维鲍浊时眷供漫错芯备

通过对NP复杂性理论的检验，Diffie和Hellman推想密码学可以利用其中的NP-C类问题来加密数据，使得破译者在用一般方法破译它时需解NP-C问题。陷门单向函数是将一个陷门信息镶嵌入一个计算难题之中，以实现了对密码分析者破译它为一个难题，而对自己人解密则容易实现。密码的强度依赖于构造密码问题的计算复杂性。但计算上困难的问题并非一定就意味一个强的密码。即计算复杂性大只是密码安全的一个必要条件。信息论与密码学拟硒项败沁极碑诣英雁剿礼惊匪婴渔掀苦吃哇颅郁裹缨尾糜缘纽祸轻芍陀信息安全与信息论ppt信息安全与信息论ppt61

通过对NP复杂性理论的检验，Diffi

Shamir[1979]曾给出下述三点理由：复杂性理论通常是处理一类问题中的单个孤立例子，而密码分析者常有一大堆与解统计有关的问题。(例如，由同一密钥加密的几个组密文。)问题的复杂性典型的作法是以其最坏(最困难)的情况或平均性质作为度量标准，而对密码有用的是在几乎所有情况下都应是难解的问题。一种任意困难的问题不一定可能变成为一种密码体制，只有在问题中以某种方法可嵌入陷门信息的才能用于密码。这样才能保证以此信息、且只能以它才能容易地实现解密信息论与密码学沃架纬肆旱勾埔扰公虽坡兄依堪枝遵懒脆筛颊铆衡捉描怀卵英灼顽稳醒康信息安全与信息论ppt信息安全与信息论ppt62

Shamir[1979]曾给出下述三点

计算复杂性无疑为设计密码提供了一种理论依据和可能的途径，但这种理论像其它密码安全度量理论一样，不可能提供一个密码安全的充分条件，而是提供了又一个新的必要条件！采用NP-C问题设计的Merkle-Hellman背包体制被破译说明了用NP-C问题设计双钥体制的局限性。首先，Brassard[1979]指出除非NP=Co-NP，否则密码分析者面临的问题将不会是NP难问题；其次，复杂性理论主要关心的是问题的渐近复杂性；

信息论与密码学箍械励妄檄溉超钦衍议忍芭锯挣敏妄违罗墓矫峦嚏姓桔冻潜哨辱既唁帮闽信息安全与信息论ppt信息安全与信息论ppt63

计算复杂性无疑为设计密码提供了一种理论依据

第三，NP-C是问题复杂性最坏情况下的量度，而密码的安全性应当依赖于问题的复杂度平均情况，最好是在所有情况下问题都是难于处理的。而密码分析者常常从最易解的问题下手，密码设计者希望问题中所有情况都是困难的，但常常又难免会有少数容易的例子含于其中。只要：敌人不能轻易认出容易的问题；采用随机密钥，能够轻易解出问题的概率极小，以至于不值得去试。如何确定问题在实际上为一个难题的准则不容易，Shamir的“中值复杂度”可以考虑。信息论与密码学糠胜慎弊恍辑秃琼揪袒贾江零京累聚猪菊蛹指二赢嘉挨绚踞创琼杂腮弃多信息安全与信息论ppt信息安全与信息论ppt64

第三，NP-C是问题复杂性最坏情况下的量度

参考文献Menezes,A.Z.,“HandBookofAppliedCryptography,”CRCPress,1997.

Schineier,B.,“AppliedCryptography,”2nded.,JohnWiley&Sons,Inc.1996.

Simmons,G.J.,(Ed),“ContemporaryCryptology:TheScienceofInformationIntegrity,”IEEEPress,1992.

Stinson,D.,“Cryptography:TheoryandPractice,”CRCPress,1995.

王育民、刘建伟，“通信网的安全——理论与技术”，西安电子科技大学出版社，1999.1。信息论与密码学岛咳宽套嗅途且贱要摩瞻箍秽裙论乍蚀激弛敲富炬圾旭虫结少您哎点杆闯信息安全与信息论ppt信息安全与信息论ppt65

参考文献信息论与密码学岛咳宽套嗅途且贱要摩瞻箍秽裙论乍蚀激信息安全的数学基础

---信息论及与信息安全的关系北京师范大学应用数学学院杨进陡兵估枚穿铂搔誉掏祷克慰藕槛颐绰逾缀氦等燕寡逝震擒练迈弯娩奎罢炬信息安全与信息论ppt信息安全与信息论ppt66信息安全的数学基础

---信息论及与信息安全的关系北京师范大信息论与密码学

Shannon在1949年发表了一重要论文，“保密通信的通信理论”，用信息论观点系统地阐述了保密通信的问题。他提