网络与信息安全02

1、密码学基本概念和传统加密体系 二六Network and Information Security(2)8/2/20221密码学基本概念密码学的演变历史1918, William Friedmans The Index of Coincidence and its Applications in Cryptography Edward Hebern, Rotor Machine for 50 Years.1949, Claude Shannons The Communication Theory of Secrecy System, 成为理论基础19491967，Cryptographic L

2、iterature was barren1974, IBM: Luciffer Cipher, 128位密钥作分组加密1975, Diffie-Hellman, A New Direction in Cryptography, 首次提出适应网络保密通信的公开密钥思想，揭开现代密码学研究的序幕，具有划时代的意义8/2/20222密码学的演变历史(续)19761977，美国国家标准局正式公布实施DES，Data Encryption Standard19771978，Rivest, Shamir, Adelman 第一次提出公开密钥密码系统的实现方法RSA1981，成立International

3、Association for Cryptology Research1985，ElGamal 提出概率密码系统 ElGamal方法19901992，Lai Xuejia and James: IDEA, The International Data Encryption Algorithm2000, AES, Advanced Encryption Standard8/2/20223密码学基本术语 TerminologiesCryptology(保密学)，源自希腊语（Greek）Krypts: hidden; logos:word, 是密码学和密码处理过程的研究。Cryptography:

4、The Science and Study of Secret Writing，密码编码学Cryptanalysis: The Science and Study of Secret Breaking，密码破译学Cipher: A secret method of writing 加密方法Encipher (encipherment), encryption: 将明文转换成密文的过程Decipher (decipherment), decryption: 将密文还原成明文的过程Plaintext (cleartext): 原始的可读数据，明文Ciphertext (Cryptogram): 加

5、密后的不可解读之文件，密文Key: 密钥，对加密与解密过程进行控制的参数E(m): Encryption Transformation 加密变换D(c): Decryption Transformation 解密变换8/2/20224简单加密系统模型什么是密码？简单地说它就是一组含有参数K的变换E。设已知消息m，通过变换Ek得密文C，即，这个过程称为加密，E为加密算法，k不同，密文C亦不同。传统的保密通信机制：EncipherPlaintextCiphertextKeysDecipherC=Ek(m)发方： m收方：mkk（公共信道）加密E解密D（秘密信道）8/2/20225理论安全和实际安全

6、Theoretical Security (or Perfect Security) and Practical Secure (or Computationally Secure)理论安全，或无条件安全： 攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。Shannon用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密，One-time Pad，不实用。实际安全，或计算上安全： 如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系

7、统是计算上不可行（Computationally Infeasible）。 8/2/20226Shannon假定给定一个n位的密文，必有一个最小的工作时间来破解这个系统，这个工作时间为W(n), Work Characteristic. 当n趋于无穷，则W(n)W()；当n大到一定程度，具有有限资源的攻击者在合理的时间内不能破译系统，该系统就被称为是Practical Secure 或Computationally Secure。现在的问题是，W(n)多大系统才安全？例：N1=n5, N2=2n, N3=n! 假定每秒可以计算100万次，即10-6sec/compute n5 2nn!n=10

8、 0.1sec 0.001sec3.6secn=100 104sec2.8h 1030sec1016年10186sec10176年n1000 109sec10年 10286 sec102974世纪 所以，n=100，2n1030sec1016年，W(n) 1030才安全。8/2/20227第二章 常规加密的经典技术加密的基本概念密码体制 加密系统采用的基本工作方式称为密码体制。密码体制的基本要素是密码算法和密钥。密码算法是一些公式、法则或程序；密钥是密码算法中的控制参数。加密系统可以用数学符号来描述：SP, C, K, E, DP：明文空间 C：密文空间K：密钥空间 E：加密变换 D：解密变换

9、 kK，则有CEk(P)，PDk(C)Dk(Ek(P)， 或者DkEk1，且EkDk1。8/2/20228对称密码体制和非对称密码体制对称密码体制(Symmetric System, One-key System, Secret-key System) 加密密钥和解密密钥相同，或者一个密钥可以从另一个导出，能加密就能解密，加密能力和解密能力是结合在一起的，开放性差。非对称密码体制(Asymmetric System, Two-key System, Public-key System) 加密密钥和解密密钥不相同，从一个密钥导出另一个密钥是计算上不可行的，加密能力和解密能力是分开的，开放性好。序

10、列密码体制和分组密码体制如果经过加密所得到的密文仅与给定的密码算法和密钥有关，与被处理的明文数据在整个明文中的位置无关，则称为分组密码体制。通常以大于等于64位的数据块为单位，加密得相同长度的密文。如果密文不仅与最初给定的算法和密钥有关，同时也与明文位置有关(是所处位置的函数)，则称为序列密码体制。加密以明文比特为单位，以伪随机序列与明文序列模2加后，作为密文序列。8/2/20229确定型密码体制和概率密码体制确定型：当明文和密钥确定后，密文也就唯一地确定了。概率型：当明文和密钥确定后，密文通过客观随机因素从一个密文集合中产生，密文形式不确定，称为概率型密码体制。单向函数型密码体制和双向变换型

11、密码体制单向函数型密码体制适用于不需要解密的场合，容易将明文加密成密文，如哈希函数；双向变换型密码体制可以进行可逆的加密、解密变换。加密的应用加密算法的选择公开发表的加密算法、政府指定的加密算法、著名厂家产品、专家推荐的加密算法通信信道的加密链路加密点到点加密高层连接加密端到端加密存储数据的加密硬盘级加密和文件级加密8/2/202210现代密码学的基本原则设计加密系统时，总是假定密码算法是可以公开的，需要保密的是密钥。一个密码系统的安全性不在算法的保密，而在于密钥，即Kerckhoff原则。对加密系统的要求 系统应该是实际上安全的(practical secure)，截获密文或已知明文密文对时

12、，要决定密钥或任意明文在计算上是不可行的。加密解密算法适用于密钥空间中的所有元素。系统易于实现，使用方便。系统的安全性不依赖于对加密体制或加密算法的保密，而依赖于密钥。系统的使用不应使通信网络的效率过分降低。8/2/202211对称加密系统由以下五部分组成:Plaintext：明文Encryption algorithm：加密算法Secret Key：密钥Ciphertext：密文Decryption algorithm：解密算法加密算法必须足够强大，使破译者不能仅根据密文破译消息；Security depends on the secrecy of the key, not the secr

13、ecy of the algorithm.2.1 对称密码的模型8/2/2022128/2/202213Requirementstwo requirements for secure use of symmetric encryption:a strong encryption algorithma secret key known only to sender/receiverY = EK(X)X = DK(Y)assume encryption algorithm is knownimplies a secure channel to distribute key8/2/202214Y =

14、 Ek(X)X = Dk(Y)8/2/202215密码编码学(Cryptography)密码编码系统根据以下三个独立方面进行分类：用于将明文转换为密文操作的类型：替代和置换所使用的密钥的数量：对称密码体制，单钥系统、秘密密钥系统非对称密码体制，双钥系统、公开密钥系统明文处理的方式：分组加密和流加密密码分析学(Cryptanalysis)试图破译密文得到明文或试图获得密钥的过程为密码分析，密码破译的策略取决于加密方法及可供破译者使用的信息。Cryptology 密码学8/2/2022168/2/202217Brute Force Searchalways possible to simply t

15、ry every key most basic attack, proportional to key size assume either know/recognise plaintext8/2/2022182.2 Steganography 隐写术8/2/202219Steganographyan alternative to encryptionhides existence of messageusing only a subset of letters/words in a longer message marked in some wayusing invisible inkhid

16、ing in LSB in graphic image or sound filehas drawbackshigh overhead to hide relatively few info bits8/2/2022208/2/202221More Definitionsunconditional security无条件安全no matter how much computer power is available, the cipher cannot be broken since the ciphertext provides insufficient information to uni

17、quely determine the corresponding plaintext computational security计算上安全given limited computing resources (e.g. time needed for calculations is greater than age of universe), the cipher cannot be broken破译的成本超过该信息的价值破译的时间超过该信息的有用生命周期8/2/202222替代技术(Substitution)改变明文内容的表示形式，保持内容元素之间相对位置不变。单表替换如恺撒密码(Caes

18、ar Cipher)明文字母用密文中对应字母代替，例：明文字母表 Pp0, p1, , pn-1密文字母表 Cc0, c1, , cn-1密钥为正整数k，加密：i+k j (mod n) 解密：j-k i (mod n)Caesar Cipher，加密：C = E(p)=(p+k) mod 26 解密：p = D(C)=(C-k) mod 26, 0A；1B；25Z2.3 经典加密技术8/2/202223置换技术(Transposition or permutation)改变明文内容元素的相对位置，保持内容的表现形式不变。一维变换矩阵转置二维变换图形转置转子加密机(Rotor Machine)

19、DNATSREDNUUOYNAC明文：can you understand密文：codtaueanurnynsd输入输出UUOYNACSREDNNATD密文明文明文：can you understand密文：dnsuaruteodynnac8/2/202224Classical Substitution CiphersWhere letters of plaintext are replaced by other letters or by numbers or symbolsOr if plaintext is viewed as a sequence of bits, then subst

20、itution involves replacing plaintext bit patterns with ciphertext bit patterns8/2/202225Caesar CipherEarliest known substitution cipher by Julius Caesar First attested use in military affairsReplaces each letter by 3rd letter onExample:meet me after the toga partyPHHW PH DIWHU WKH WRJD SDUWB8/2/2022

21、26Caesar CipherCan define transformation as:a b c d e f g h i j k l m n o p q r s t u v w x y zD E F G H I J K L M N O P Q R S T U V W X Y Z A B CMathematically give each letter a numbera b c d e f g h i j k l m0 1 2 3 4 5 6 7 8 9 10 11 12n o p q r s t u v w x y Z13 14 15 16 17 18 19 20 21 22 23 24

22、25Then have Caesar cipher as: C = E(p) = (p + k) mod 26 p = D(C) = (C - k) mod 268/2/202227Cryptanalysis of Caesar Cipher Only have 26 possible ciphers A maps to A,B,.Z Could simply try each in turn by a brute force search Given ciphertext, just try all shifts of lettersDo need to recognize when hav

23、e plaintextE.g. break ciphertext GCUA VQ DTGCM“Fig. 2.4: PHHW PH DIWHU WKH WRJD SDUWB8/2/202228Monoalphabetic Cipher 单一字母替代Rather than just shifting the alphabet, could shuffle (jumble) the letters arbitrarily Each plaintext letter maps to a different random ciphertext letter, hence key is 26 letter

24、s long Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext: ifwewishtoreplacelettersCiphertext: WIRFRWAJUHYFTSDVFSFUUFYA 8/2/202229Monoalphabetic Cipher SecurityNow we have a total of 26! = 4 x 1026 keys more than 400,000,000,000,000,000,000,000,000 With so many keys, you m

25、ight think is secure But would be !WRONG! The problem is language characteristics8/2/202230Language Redundancy and CryptanalysisHuman languages are redundant E.g. th lrd s m shphrd shll nt wnt Letters are not equally commonly used In English E is by far the most common letter, then T, R, N, I, O, A,

26、 S Other letters are fairly rare, e.g.: Z, J, K, Q, X Have tables of single, double & triple letter frequencies 8/2/202231English Letter Frequencies8/2/202232Use in CryptanalysisKey concept - monoalphabetic substitution ciphers do not change relative letter frequencies Discovered by Arabian scientis

27、ts in 9th centuryCalculate letter frequencies for ciphertext, compare counts/plots against known values If Caesar cipher look for common peaks/troughs peaks at: A-E-I triple, NO pair, RST tripletroughs at: JK, X-ZFor monoalphabetic must identify each lettertables of common double/triple letters help

28、8/2/202233Example CryptanalysisGiven ciphertext:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQCount relative letter frequencies (see text)Guess P & Z are e and tGuess ZW is th and hence ZWP is theproceeding with trial and erro

29、r finally get:it was disclosed yesterday that several informal butdirect contacts have been made with politicalrepresentatives of the viet cong in moscow8/2/202234Playfair CipherNot even the large number of keys in a monoalphabetic cipher provides security One approach to improving security was to e

30、ncrypt multiple letters The Playfair Cipher is an example invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair 8/2/202235Playfair Key MatrixA 5X5 matrix of letters based on a keyword Fill in letters of keyword (no duplicates) Fill rest of matrix with other letterse.g. us

31、ing the keyword MONARCHYMONARCHYBDEFGI/JKLPQSTUVWXZ8/2/202236Encrypting and DecryptingPlaintext encrypted two letters at a time: if a pair is a repeated letter, insert a filler like X, eg. balloon encrypts as ba lx lo on If both letters fall in the same row, replace each with letter to right (wrappi

32、ng back to start from end), eg. “ar encrypts as RM If both letters fall in the same column, replace each with the letter below it (again wrapping to top from bottom), eg. “mu encrypts to CM Otherwise each letter is replaced by the one in its row in the column of the other letter of the pair, eg. “hs

33、 encrypts to BP, and “ea to IM or JM (as desired) 8/2/202237Security of the Playfair CipherSecurity much improved over monoalphabetic, since have 26 x 26 = 676 digrams Would need a 676 entry frequency table to analyse (verses 26 for a monoalphabetic), and correspondingly more ciphertext Was widely u

34、sed for many years (eg. US & British military in WW1, WW2) It can be broken, given a few hundred letters, since still has much of plaintext structure 8/2/202238Polyalphabetic Ciphers 多字母密码Another approach to improving security is to use multiple cipher alphabets, called polyalphabetic substitution c

35、iphers It makes cryptanalysis harder with more alphabets to guess and flatter frequency distribution Use a key to select which alphabet is used for each letter of the message Use each alphabet in turn Repeat from start after end of key is reached 8/2/202239Vigenre CipherSimplest polyalphabetic subst

36、itution cipher is the Vigenre Cipher Effectively multiple Caesar Ciphers Key is multiple letters long K = k1 k2 . kd ith letter specifies ith alphabet to use Use each alphabet in turn Repeat from start after d letters in messageDecryption simply works in reverse 8/2/202240ExampleWrite the plaintext

37、out Write the keyword repeated above itUse each key letter as a Caesar Cipher key Encrypt the corresponding plaintext lettere.g. using keyword deceptivekey: deceptivedeceptivedeceptiveplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ8/2/202241AidsSimple aids can assist wit

38、h en/decryption A Saint-Cyr Slide is a simple manual aid a slide with repeated alphabet line up plaintext A with key letter, eg C then read off any mapping for key letter Can bend round into a cipher disk, or expand into a Vigenre Tableau (see text Table 2.4)8/2/2022428/2/202243Security of Vigenre C

39、iphersHave multiple ciphertext letters for each plaintext letter, hence letter frequencies are obscured, but not totally lostStart with letter frequenciessee if look monoalphabetic or notIf not, then need to determine number of alphabets, since then can attach each8/2/202244Kasiski MethodMethod deve

40、loped by Babbage/Kasiski Repetitions in ciphertext give clues to period, so find same plaintext an exact period apart, which results in the same ciphertext Of course, could also be random flukeE.g. repeated “VTW” in previous example, suggests size of 3 or 9, then attack each monoalphabetic cipher in

41、dividually using same techniques as before8/2/202245Autokey CipherIdeally want a key as long as the messageVigenre proposed the autokey cipher, with keyword is prefixed to message as keyKnowing keyword can recover the first few letters Use these in turn on the rest of the message, but still have fre

42、quency characteristics to attack E.g. given key deceptivekey: deceptivewearediscoveredsavplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA8/2/202246One-Time PadIf a truly random key as long as the message is used, the cipher will be secure, called a One-Time padIt is unbre

43、akable since ciphertext bears no statistical relationship to the plaintext, since for any plaintext & any ciphertext there exists a key mapping one to otherCan only use the key once thoughHave problem of safe distribution of key8/2/202247Transposition CiphersConsider classical transposition or permu

44、tation ciphers These hide the message by rearranging the letter order, without altering the actual letters usedCan recognise these since have the same frequency distribution as the original text 8/2/202248Rail Fence CipherWrite message letters out diagonally over a number of rows, then read off cipher row by rowe.g. write message out as:m e m a t r h t g p r y e t e f e t e o a a t giving ciphertextMEMATRHTGPRYETEFETEOAAT8/2/202249Row Transposition CiphersA more complex schemeWrite letters of