第02章-3网络信息安全理论基础

1网络信息安全

第2章网络信息安全理论基础

2第2章网络信息安全理论基础

本章主要内容：2.1前言2.2密码学的基本概念2.3密码系统模型和密码体制2.4密码分析2.5古典密码32.1前言基础数论在密码学中的作用

基础数论作为一门古老的数学学科，在整个数学学科中占有非常重要的位置。数论中许多基本内容，如同余理论、中国剩余定理（CRT）、高次剩余理论等，在新型密码体制、密钥分配与管理、数字签名、身份认证等方面有直接的应用。

现代密码与近代数学形影不离近代数学在现代密码研究中比比皆是：群论，有限域上椭圆曲线理论，多项式理论与迹函数理论，陷门单向函数等。42.2密码学的基本概念

密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支。密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问密码分析学(Cryptanalytics)，研究分析破译密码的学问。5

2.2密码学的基本概念

明文(消息)(Plaintext)：被隐蔽消息。

密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。

加密(Encryption)：将明文变换为密文的过程。

解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。

加密员或密码员(Cryptographer)：对明文进行加密操作的人员。6

2.2密码学的基本概念

加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。72.2密码学的基本概念

密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。

密码分析员(Cryptanalyst)：从事密码分析的人。

被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。

主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。82.3密码系统模型和密码体制Shannon的保密系统模型9

2.3密码系统模型和密码体制现代密码系统模型102.3密码系统模型和密码体制密码体制(Cryptosystem)——六元组(M,C,K1,K2,E,D)明文空间:M，mM称为明文(plaintext)密文空间:C，cC称为密文(ciphertext)加密密钥空间:K1，

k1K1

称为加密密钥(encryptionkey)解密密钥空间:K2k2K2

称为解密密钥(decryption

key)

密钥(key):k=(k1,k2)11密码体制(Cryptosystem)——六元组(M,C,K1,K2,E,D)加密变换簇:E解密变换簇:D

2.3密码系统模型和密码体制12密码体制(Cryptosystem)加密变换与解密变换的关系mMCc

2.3密码系统模型和密码体制13

保密系统应当满足的要求

系统即使达不到理论上是不可破的，即pr{m’=m}=0，也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。加密和解密算法适用于所有密钥空间中的元素。系统便于实现和使用。14认证与认证系统认证系统(Authenticationsystem)

防止消息被窜改、删除、重放和伪造的一种有效方法,使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作认证系统保密性

保密性是使截获者在不知密钥条件下不能解读密文的内容。认证性使任何不知密钥的人不能构造一个密报，使意定的接收者解密成一个可理解的消息(合法的消息)。15安全认证系统应满足下述条件意定的接收者能够检验和证实消息的合法性和真实性。消息的发送者对所发送的消息不能抵赖。除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文c和相应消息m下，要确定加密密钥或系统地伪造合法密文在计算上是不可行的。必要时可由第三者作出仲裁。16密码体制系统的分类对称密码体制(symmetriccryptosystem)

k=k1=k2或k1

k2

单钥、私钥(one-key,privatekey)密码体制

2.3密码系统模型和密码体制17单钥体制(One-keysystem)：

加密密钥和解密密钥相同，即能简单的由加（解）密密钥求得解（加）密密钥。注意：一个保密系统的加密密钥和解密密钥相同，或者虽然不同，但由其中的任意一个很容易的求得另外一个，即使用的是对称密钥密码体制，那么某个实体有能力加密，也就有能力解密。18密码体制系统的分类对称密码体制(symmetriccryptosystem)分组密码(blockcipher)

将明文消息分为包含若干个符号的组，在选定密钥后使用固定的加密变换对明文分组逐组地进行加密。例如，DES(1977),AES(2001)流密码(streamcipher)

明文：m=m1m2m3…..

密钥：k=k1k2k3….

加密：c1=Ek1(m1),c2=Ek2(m2),c3=Ek3(m3),….

密文：c=c1c2c3….

例如，GSM移动台（手机）到基站BS之间无线传输中使用的加密算法A5/1是一种流密码

2.3密码系统模型和密码体制19非对称密码体制(asymmetriccryptosystem)

双钥、公钥(two-key,publickey)密码体制

k1k2或k1不能k2

公钥:k1=pk；私钥:k2=sk

2.3密码系统模型和密码体制20双钥体制(Twokeysystem)：加密密钥和解密密钥不同。一个保密系统把加密和解密分开，加密和解密分别用两个不同的密钥实现，并且由加密密钥推导出解密密钥是计算是不可行的，则该系统使用的是非对称密钥密码体制（公钥密码体制）如：RSA、EIGaMal、椭圆曲线密码体制等是非对称密码体制的典型代表。使用公钥密码体制的每个用户都有一对选定的密钥，其中一个是可以公开的，称为公钥，另外一个是用户自己秘密保存。

思考：用于加密的还是解密的秘钥保存？212.3密码系统模型和密码体制密码系统的设计原则设计加密函数与解密函数的学科称为密码编码学(Cryptography)、密码学或保密学。具有某种安全性理论上不可破实际上不可破Kerckhoff假设：系统的保密性不依赖于对加密体制或加（解）密算法的保密，而仅依赖于密钥的保密。加密和解密算法适用于密钥空间的全部元素系统便于实现和使用方便22

2.3密码系统模型和密码体制密码学发展简史密码学发展史简图远古1949年1976年1977年1949年现代密码古典密码1976年私钥密码公钥密码1977年商用密码23密码学发展简史古典密码时期(—1949)特定应用领域：军事、政治、外交神秘性艺术性现代密码学(1949—)：密码技术成为一门学科

著名论文:

Communicationtheoryofsecrecysystems,BellSyst.Tech.J.,Volume28,656-715,1949.

仙农(C.D.Shannon:1916-2001)

2.3密码系统模型和密码体制24密码学发展简史公钥密码学(1976—)计算机网络环境中的应用W.Diffie和M.E.Hellman提出公钥密码的思想(1976)著名论文：W.DiffieandM.E.Hellman,Newdirectionincryptography,IEEETran.OnInformationTheory,IT-22,(6),644-654,1976.密码学的商业应用(1977—)1977：美国国家标准局(NationalBureauofStandards)颁布数据加密标准DES(DataEncryptionStandard)1994：美国政府颁布数字签名标准DSS(DataSignatureStandard)2001：美国政府颁布高级加密标准AES(AdvancedEncryptionStandard)

2.3密码系统模型和密码体制252.4密码分析

截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。262.4密码分析

密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别

密码设计是利用数学来构造密码密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力……，有时还靠点运气。27利用密文推断出明文或解密密钥的学科称为密码分析学(Cryptanalysis)

分析(analysis)=破译(break)=攻击(attacks)攻击方式主动攻击(activeattack)

窜改通信中的数据流，或在通信中产生虚假数据流被动攻击(passiveattack)

窃听或监视通信过程，从中获得信息2.4密码分析28攻击方法

2.4密码分析29穷举破译法(exhaustiveattackmethod)方法：对截获的密文依次用各种可能的密钥试译，直到获得有意义的明文；或者利用对手已注入密钥的加密机（比如缴获得到），对所有可能的明文依次加密直到得出与截获的密文一致的密文。对策：将密钥空间和明文空间设计得足够大。确定性分析法方法：利用密文或者明文—密文对等已知量以数学关系式表示出所求未知量（如密钥等），然后计算出未知量。对策：设计具有坚实数学基础和足够复杂的加密函数统计分析法方法：密码破译者对截获的密文进行统计分析，找出其统计规律或特征，并与明文空间的统计特征进行对照比较，从中提取出密文与明文间的对应关系，最终确定密钥或明文。对策：扰乱密文的语言统计规律

攻击方法30物理破译方法(Kocher,1996)

利用加密执行时的物理现象来确定密钥的密码分析方法，也被称为“边信道攻击”（side-channelattack）。所利用的物理现象有密码算法执行器件（加密芯片）的功耗，各算法步执行时间度量，甚至主机执行加密任务时主板上电容器发出的声音等等。

攻击方法31攻击类型唯密文攻击(ciphertext-onlyattack)

密码分析者仅知道有限数量用同一个密钥加密的密文已知明文攻击(knownplaintextattack)

密码分析者除了拥有有限数量的密文外，还有数量限定的一些已知“明文—密文”对选择明文攻击(chosenplaintextattack)

密码分析者除了拥有有限数量的密文外，还有机会使用注入了未知密钥的加密机，通过自由选择明文来获取所希望的“明文—密文”对

选择密文攻击(chosenciphertextattack)

密码分析者除了拥有有限数量的密文外，还有机会使用注入了未知密钥的解密机，通过自由选择密文来获取所希望的“密文—明文”对32无条件安全和计算安全

无条件安全

如果算法产生的密文不能给出唯一决定相应明文的足够信息，无论截获多少密文，花费所少时间都不能解密密文。

Shannon指出，仅当密钥至少和明文一样长时达到无条件安全（即一次一密）

计算安全

破译密文的代价超过被加密信息的价值破译密文所花时间超过信息的有效期331）代替密码（替换密码）

可分为单表密码、多表密码单表密码：将明文中的字母或符号用另一种字母或符号来代替，这种代替是一一对应的。明文与密文之间只有一种对应关系。多表密码：代替不是一一对应的。代替规律不同，密码体制也不同。代替规律相同，明密文间字母对应关系不同，代替出的密码也不同。e.g.同余密码（加同余、乘同余、线性同余）随机替代、密钥词组、多表组合2.4古典密码34*

一般单码替换密码♦简单的方法给出密钥♦写出密钥（删除重复字母）♦在其下面依次写出剩余字母（以横、纵行）♦按列读取字母得到密文。2.4古典密码35

一般单码替换密码举例♦给定密钥字"STARWARS"♦去掉重复字母得到"STARW"♦填写剩余字母：STARWBCDEFGHIJKLMNOPQUVXYZ♦按列读取字母得到密文♦Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZ♦

Cipher:SBGLQZTCHMUADINVREJOXWFKPY♦可以用这个密钥加密、解密♦例如Plaintext:IKNOWONLYTHATIKNOWNOTHING♦Ciphertext:HUINFNIAPOCSOHUINFINOCHIT36

一般单码替换密码的密码分析♦根据频率统计进行分析♦确定每个字母被映射到什么字母♦如果知道单词之间的间隙知道,则破译会很容易.♦单个字母出现的可能是A或I♦一般来说3个字母出现的可能是THE或AND♦还可以用其他通常出现的双字母或三字母组合)♦还可以应用其它很少应用的字母37同余密码

(1)加同余码：一种移位密码，如凯撤(Cacsar)密码：以查码表方式进行一对一替换。收发双方采用同一码表。凯撤密码加密变换：C=P+3(mod26)

凯撤密码解密变换：P=C-3(mod26)密钥：338

若明文m=Casearcipherisashiftsubstitution则密文C=E(m)=FDVHDUFLSHULVDVKLIWVXEVWLWXWLRQ明文abcdefghijklm密文DEFGHIJKLMNOP明文nopqrstuvwxyz密文QRSTUVWXYZABC39凯撤密码扩展：C=P+n(mod26)P=C-n(mod26)

密钥：n密码分析（１）加解密算法已知（２）可能尝试的密钥只有２6个通过强力攻击得到明文40

(2)乘同余码：移位或等间隔抽取码，明密文之间没有一一对应关系。（容易产生多义性）。变换按照同余乘法进行：加密变换：C=Pk(mod26)

解密变换：P=Ck(mod26)

密钥：k

41

(3)线性同余：加同余与乘同余密码的结合。正常字母顺序替换，解码容易42随机替换密码随机改变字母替换顺序，改变单一字母组合，增加字符或者专用符号替换，从而增加了密钥数量，使密码破译困难，但用户自己记忆也困难。通常以码表查阅实现。密钥词组密码解决密钥记忆困难问题，任选一词组作为密钥。加解密均也采用查表方式。上述密码均是字母、符号的排列和组合，用计算机可以对上述密码进行破译。43多表密码

利用多码表组合形成的加解密机制，打乱明文统计规律，提高保密强度。多表代换密码是以一系列(两个以上)代换表依次对明文消息的字母进行代换的加密方法

e.g.维吉尼亚密码、博福特密码等441．维吉尼亚密码一种以移位代换为基础的周期代换密码，为1858年法国密码学家维吉尼亚提出。首先构造一个维吉尼亚方阵：它的基本阵列是26行26列的方阵.方阵的第一行是按正常顺序排列的字母表,第二行是第一行左移循环1位得到的,依此类推,得到其余各行.然后在基本方阵的最上方附加一行,最左侧附加一列,分别依序写上a到z26个字母,表的第一行与与附加列上的的字母a相对应,表的第二行与附加列上的字母b相对应..最后一行与附加列上的字母z相对应.如果把上面的附加行看作是明文序列，则下面的26行就分别构成了左移0位，1位，2位…，25位的26个单表代换加同余密码的密文序列。加密时，按照密钥字的指示，决定采用哪一个单表。45ABCDEFGHIJ...YZAABCDEFGHIJ...YZBBCDEFGHIJK...ZACCDEFGHIJKL...ABDDEFGHIJKLM...BCEEFGHIJKLMNCDFFGHIJKLMNODEGGHIJKLMNOPEFHHIJKLMNOPQFGZZABCDEFGHI...XY46维吉尼亚密码密钥字encryptionencryptione明文：publickeydistribution密文：thdcgrdmmqmfvrgqnbwbr由于密钥字比明文短，所以要重复书写密钥字，以得与明文等长的密钥序列。47Vigenérecipher-破译依然保留了字符频率某些统计信息重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大。482）置换密码

也称换位密码或转置密码。

加密方式与密文形式不同于代替密码体制。

不改变组成明文消息的符号本身，只对符号进行重新排列。可以分类为：倒序密码：颠倒明文书写顺序。栅栏密码：明文交替书写排列。行列转置：明文行列转置书写。49变换密码的关键思想◆按一定规则写出明文，按另一规则读出密文。◆密钥：用于读密文的方法和写明文的方法50例、行变换密码-（Rowtranspositionciphers）按行写出字母以密钥给出的顺序按行读出密文（总是有一个密钥对）51行变换密码(续1)1)Plain:THESIMPLESTPOSSIBLETRANSPOSITIONSXXKey(R): 25413Key(W): 41532 THESI STIEH MPLES EMSLP TPOSS STSOP IBLET EITLB RANSP SRPNA OSITI TOIIS ONSXX XOXSNCipher:STIEHEMSLPSTSOPEITLBSRPNATOIISXOXSN523）代码密码

可以对明文字母、符号、词组和短语等进行替换，甚至对明文句子进行替换。不考虑明文的结构，代码替换可以是等长的，也可以是不等长的。短码替换使明文长度缩短，实现明文压缩。长码替换使明文长度增长，实现明文扩展。e.g.以各种编码实现替换：二进制码、八或16进制码、五中出二码、格雷码等。53一次一密密码一次一密密码，由AT&T公司的GilbertVernam在1917年提出。发方和收方各保存一份一次一密乱码本，它是一个大的不重复的真随机密钥字母集。发方用乱码本中的某一页密钥加密明文。加密方法：明文字符和乱码本密钥字符的模26加法。每个密钥仅对一个消息使用一次。发方对所发的消息加密，然后销毁乱码本中用过的一页。收方有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每个字符，然后销毁乱码本中用过的一页。54语言的统计规律性C.E.Shannon1949年第一次透彻地阐明了密码分析的真谛，指出密码能够被破译的最根本原因是于明文空间非均匀的统计特性英文字母频率表

初等密码分析实例字母概率字母概率字母概率字母概率ABCDEFG0.081670.014920.027820.042530.127020.022280.02015HIJKLMN0.060940.069660.001530.0080.0400.0240.067OPQRSTU0.0750.0190.0010.0600.0630.0910.028VWXYZ0.0100.0230.0010.0200.00155单表代换密码分析

给定密文：EJMHAFJPDPBKRNMQJANONPSMNBQOAFJPDNIWQRGGSOQANFHMWNNIJSWRQJYNQNMOQHQBOQBPHFHIHFXOBOQRNAFJPDFNIWQRJEYNOGHXANQRNORJMQNOQJIN

首先求出密文字母的频度分布表密文字母ABCDEFGHIJKLMNOPQRSTUVWXYZ

频数6503283751010617

10614730004220先猜测Ek:eN,，再利用英文高频度的双字母知识，比对密文中出现的双字母（词）及次高频度字母集{t,a,o,i,n,s,h,r}，猜测Ek:tQ,oJ,

得到部分试译结果：

EoMHbFoPDPBKReMtobeOePSMeBtObFoPDFeIWtRGGSOtbeFHMWeeIoSWRtoYeteMOtHtBOtBPHFHIHFXOBOtRebFoPDFeIWtRoEYeOGHXbetReORoMteOtoIe56利用三字母组合和元音辅音拼写知识，猜测单词tRe为the，即

Ek:hR.在余下的次高频度字母集{a,i,n,s,r}中选择适当的辅音字母作为密文O的原像,即Ek:sO.利用构词分析