信息安全基础2(密码编码学与网络安全).ppt

Chapter 2 Cryptography,2012,Foundation of Information Security,1,2,3,4,Overview,Overview of Cryptography,Classical Ciphers,Block Ciphers,5,6,1 Overview of Cryptography,1.1 History of Cryptography,1.2 Cryptosystem,1.3 Cryptanalysis,1.4 Cryptography,Before 1949 Classical Encryption古典加密 Before computer was invented, cryptography was art more than science. There were some cipher algorithms, encryption machines & simple cryptanalysis密码分析 ways. The main encryption objects are alphabet character. The security of data is based on the secrecy of algorithms.,1.1 History of Cryptography密码学历史,The Phaistos (1700 BC),Encryption Machines in Early 20th Century,19491976 Shannon published “The Communication Theory of Secret Systems” in 1949, which indicated cryptography became a formal subject. The development of computer enabled ciphers on complex computing. The security of data is based on the secrecy of secret key instead of cipher algorithm.,History of Cryptography (cont d),After 1976 Diffie & Hellman published “New Directions in Cryptography” in 1976, in which put forward asymmetric cryptography不对称密码体制. Rivest, Shamir & Adleman bring forward RSA public key algorithm. Public key cryptography enables secret communication without key transmission between sender & receiver which is well fit for digital signature 数字签名.,History of Cryptography (cont d),Diffie & Hellman published “New Directions in Cryptography” in 1976 Government of the United States enacted 颁布“Data Encryption Standard”-DES in 1977 Government of the United States enacted new encryption standard-EES in 1993 Doctor from the Bell Lab broke EES in 1995 DES was broken in 1997 Government of the United States recruited 征集 new standard for computer encryption-AES all over the world in 1997 AES was enacted in 2001 after strict selection,Memorabilia大事记 of Modern Cryptography,Hypothesize that attacker knows the cipher algorithm used Security of a cryptosystem should rely on the secrecy of the key instead of the cipher algorithm As a result, the design of cryptosystem should follow the public principle,Kerckhoffs Principle (1883),Definition Cryptography密码编制学 study of encryption principles/methods Cryptanalysis密码分析学 study of principles/ methods of deciphering ciphertext密文 without knowing key Cryptology密码学 the field of both cryptography and cryptanalysis Principle Camouflaging伪装 message, preventing unauthorized user from knowing what it means,1.2 Cryptosystem密码体制,Plaintext(Message)明文 - the original message Ciphertext密文 - the coded message Key密钥 - info used in encryption & decryption, known only to sender/receiver, which should be kept secret K= Encipher加密算法 (encrypt) - converting plaintext to ciphertext CE(M，Ke) Decipher解密算法 (decrypt) - recovering plaintext from ciphertext MD(C，Kd),Component of Cryptosystem,Two requirements for secure use of symmetric encryption对称加密: - a strong encryption algorithm - a secret key known only to sender / receiver Assume encryption algorithm is known Exist a secure channel to distribute key,Requirements,CiphertextC xlcm,CiphertextC xlcm,cryptanalyst,Source,Destination,encryption key,decryption key,Plaintext M love,secure channel,Ke,Kd,Key,Encryption,PlaintextM love,channel,Decryption,Contents of keep secret - Restricted algorithm: secrecy of algorithmClassical Cipher - Key-based algorithm: secrecy of keyModern Cipher Number of keys used - Hash functions: no key - Secret key cryptography: one key (Symmetric Cipher对称密码/ Conventional Cipher传统密码/ Single-Key Cipher单钥密码) - Public key cryptography: two keys - public, private (Asymmetric Cipher非对称密码/ Public-Key Cipher公钥密码/ Two-Key Cipher双钥密码) Way in which plaintext is processed - Block分组密码: process input & output as block - Stream流密码/序列密码: process input & output as bit or character,Classification of Cryptography,Symmetric Cipher Ke=Kd Asymmetric Cipher KeKd Ke Kd So, make Ke public, keep Kd secret,Symmetric Cipher & Asymmetric Cipher,Conventional Cipher - Block Cipher DES IDEA EES AES - Stream Cipher RC4 Public Key Cipher - RSA ElGamal ECC,Examples of Modern Cipher Type,Advantages of Conventional Cipher - speedy for encryption & decryption Disadvantages of Conventional Cipher - hard to distribute & manage key, realize digital signature Advantages of Public Key Cipher - easy to distribute & manage key, realize digital signature Disadvantages of Public Key Cipher - hard to generate key, slow for encryption & decryption,Advantages & Disadvantages,Definition The process of attempting to discover M or K or both is known as cryptanalysis. Brute Force Attack 暴力破解攻击(穷举攻击) Statistics Analyse Attack 统计分析攻击 Mathematics Analyse Attack 数学分析攻击,1.3 Cryptanalysis,Decrypt ciphertext by trying every possible key according to the length of key space, until getting possible right plaintext Can break any cryptosystem by theory On average, half of all possible keys must be tried to achieve success,Brute Force Attack,Brute Force Attack (cont d),Most basic attack, proportional to key number & time of one decryption Assume either know / recognise plaintext Average Time Required for Exhaustive无遗漏的 Key Search,Compare & analyze the statistical character of plaintext & ciphertext Can break almost all classical ciphers,Statistics Analyse Attack,Analyze according to the mathematical theory Main way to break public key cipher,Mathematics Analyse Attack,Ciphertext only 惟密文 - only know algorithm / ciphertext, statistical, can identify plaintext Known plaintext 已知明文 - know/suspect corresponding pairs of plaintext & ciphertext to attack cipher Chosen plaintext 选择明文 - select plaintext and obtain ciphertext to attack cipher Chosen ciphertext 选择密文 - select ciphertext and obtain plaintext to attack cipher Chosen text 选择文本 - select either plaintext or ciphertext to en/decrypt to attack cipher,Classify by Resources Cryptanalyst Gets,Unconditional security 绝对安全 - No matter how much computer power is available, the cipher cannot be broken - Only one-time pad scheme (Shannon) qualifies合格 One-time pad 一次一密(absolutely unbreakable永不可破) - Use a random key which is as long as the message, with no repetitions - Plaintext and ciphertext are statistically independent - Key generation & distribution is of difficulty,Unconditional vs. Computational Security,Computational security 计算上的安全 - The cost of breaking the cipher exceeds the value of the encrypted info 代价 - The time required to break the cipher exceeds the useful lifetime of the info (M or K) 时间,Unconditional vs. Computational Security (cont d),Diffusion 扩散 dissipates statistical structure of plaintext & key over bulk of ciphertext Confusion 混淆 makes relationship between ciphertext and key as complex as possible Iteration of product 乘积迭代 - Uses diffusion & confusion in succession连续,1.4 Cryptography密码编制学,2 Classical Ciphers,4.11/25.15.21/9//25.15.21/ try to decipher it,Cryptography & the World War II,The Pearl Harbor Incident was on December 7, 1941,Countermining of USA 美国将计就计,Japanese Purple 紫密 American Magic 魔码,Midway Naval Battles 中途岛战役 - the Turning Point of WWII,Japanese Navys JN25 were broken by American Military in 1942 Isoroku Yamamoto山本五十六 died of information decoding in 1943 The success of decipher cut the war length as 8 years at least,Substitution & Permutation/Transposition代换和置换,Substitution Letters of plaintext are replaced by other letters or by numbers or symbols Plaintext is viewed as a sequence of bits, then substitution replaces plaintext bit patterns with ciphertext bit patterns,Modified Hieroglyphics 象形文字 1900 B.C. Egypt,Substitution & Permutation/Transposition (cont d),Permutation/Transposition Hide the message by rearranging the letter order without altering the actual letters used,Spartan Scytale 斯巴达棍 500 B.C.,Classification of Classical Cipher,Substitution Cipher 代换密码 Single-letter substitution 单字母代换 Monoalphabetic substitution 单表 Shift Cipher 移位密码（加法密码） Multiplicative Cipher 乘法密码 Affine Cipher 仿射密码 Homophone 同音字 Polyalphabetic substitution 多表 Vigenere Cipher 维吉尼亚密码 Vernam Cipher 弗纳姆密码 Rotor Machine 转轮机 Multiple-letter substitution 多字母代换 Playfair Hill Permutation/Transposition Cipher 置换密码 Rail Fence cipher 栅栏密码 Columnar Transposition Cipher 列置换密码,2.1 Substitution Cipher,2.2 Permutation Cipher,2.1 Substitution Cipher,2.1.1 Definition,2.1.2 Shift Cipher,2.1.3 Homophone,2.1.4 Vigenere Cipher,2.1.5 Vernam Cipher,2.1.6 Playfair,2.1.7 Rotor Machine,2.1.1 Definition,Single-letter substitution 单字母代换 Mapping of a plaintext letter to a corresponding ciphertext letter independently Monoalphabetic substitution 单表代换 Unique mapping of a plaintext alphabet to a ciphertext alphabet Polyalphabetic substitution 多表代换 Mapping of a plaintext alphabet to several ciphertext alphabets Multiple-letter substitution 多字母代换 Letter mapping is dependent on its position on the context, which may be managed in groups.,2.1.2 Shift Cipher 移位密码,Caesar Cipher 凯撒密码 2000 years ago, earliest known monoalphabetic substitution cipher, by Julius Caesar Replace each letter by the following 3rd letter Example meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB,Caesar Cipher (cont d),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 z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C C: LQIRUPDWLRQ VHFXULWB P: ? Mathematically give each letter a sequence number 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 z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Define Universal Caesar Cipher as C = E(m) = (m + k) mod 26 p = D(C) = (C k) mod 26 K = 125,Caesar Cipher (cont d),Only have 26 possible ciphers (25 useful) A maps to B,Z (key space=25) Given ciphertext, just try all shifts of letters A brute force search of 25 possibilities to attack universal Caesar cipher,Brute-Force Cryptanalysis,Ciphertext only attack Characteristics for success The encryption and decryption algorithms are known There are only 25 keys to try The language of the plaintext is known or easily recognizable,Shuffling Cipher 置乱密码,Rather than shifting the alphabet, shuffle 打乱 the letters arbitrarily, each plaintext letter maps to a different random ciphertext letter Message & ciphertext English alphabet AZ Keythe relevant relationship between the message alphabet & the ciphertext alphabet Example,Message: DANGERHELPME,Ciphertext: ZBWUOEAOCQRO,Key size = 26 Key space = 26! 4x1026 For a long time thought secure, but easily breakable by frequency analysis attack 频率分析攻击 (Arabian scientists in 9th century) Why? Language characteristics Letters of human language are not equally commonly used,Statistics Analyse Cryptanalysis on Shuffling Cipher,Relative Frequency of Letters in English Text,Frequency Statistics of Language,In addition to the frequency info of single letters, the frequency info of two-letter (digram 双字母) or three-letter (trigram 三字母) combinations can be used for the cryptanalysis Most frequent digrams TH, HE, IN, ER, AN, RE, ED, ON, ES, ST, EN, AT, TO, NT, HA, ND, OU, EA, NG, AS, OR, TI, IS, ET, IT, AR, TE, SE, HI, OF Most frequent trigrams THE, ING, AND, HER, ERE, ENT, THA, NTH, WAS, ETH, FOR, DTH,Example (P2526),Given ciphertext UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESX UDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPD TSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MB ZWP FUPZHMDJ UD TMOHMQ Count relative letter frequencies,THE,TH,T,E,A,O,IT,Example (P2526),Proceeding with try and error finally get: UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESX UDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPD TSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MB ZWP FUPZHMDJ UD TMOHMQ,HA_E,_EEN,B_T,_O_ITI_A_,V F,B A,P Y,U I,L X,C H,V,B,U,P L C L,Example (P2526),Ciphertext UZ QSO VUOHXMOPV GPOZPEVSG ZWSZ OPFPESX UDBMETSX AIZ VUEPHZ HMDZSHZO WSFP APPD TSVP QUZW YMXUZUHSX EPYEPOPDZSZUFPO MB ZWP FUPZHMDJ UD TMOHMQ Message it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the vietcong 越共 in moscow 情报内容 据悉昨天在莫斯科有一些非正式但是直接与越南共产党的政治代表的接触,2.1.3 Homophone 同音词,Invented by Mathematician Gauss A type of monoalphabetic substitution Mapping of a plaintext letter to several corresponding ciphertext letters, the amount of cipher letters for one plaintext letter is proportional to the frequency of the plaintext letter used If the amount of corresponding ciphertext letter is more than one, different letter should be chosen for every encryption,Example,A 3 16 29 94 31 47 68 52 B 87 71 C 80 26 7 D 11 40 62 93 E 2 15 28 37 54 41 60 73 89 90 21 57 76 F 9 70 G 34 82 H 99 43 51 24 0 17 I 4 19 27 81 33 46 66 J 100 K 39 L 1 45 14 96 M 10 88 N 13 5 20 36 69 50 49 O 6 18 95 74 59 48 23 30 P 91 53 Q 101 R 92 79 42 58 12 38 S 35 44 61 56 85 77 T 8 25 63 55 72 64 86 97 98 U 32 65 83 V 78 W 67 75 X 102 Y 22 84 Z 103 P: information security C: ?,Shortcoming of Homophone,A plaintext letter only affects one or several ciphertext letters fixedly Digram & trigram frequencies still survive in the ciphertext Two approaches for this problem - Use multiple alphabets Polyalphabetic substitution - Encrypt multiple letters Multiple-letter substitution,2.1.4 Vignere Cipher(1553),Best-known polyalphabetic substitution ciphers Each key letter determines one of 26 Caesar (shift) ciphers Repeat from start after end of key is reached Makes cryptanalysis harder with more alphabets to guess and flat frequency distribution,Vignere Cipher (cont d),Multiple(26) Caesar ciphers Keyword is repeated to make a key as long as the plaintext Ci = (pi + ki) mod 26 ki=az Example: The length of key is m, key space is 26m,Key: deceptivedeceptivedeceptive Plaintext: wearediscoveredsaveyourself Cipheretxt: ZICVTWQNGRZGVTWAVZHCQYGLMGJ,Vignere Cipher (cont d),Kasiski Test (synchronization同步),Have 26 possible ciphertext letters for each plaintext letter Hence letter frequencies are obscured 不明显 But not totally lost for the short length & repeating using of key Given a sufficient amount of ciphertext, common sequences are repeated, exposing the period (keyword length) One target of the cryptanalysis,Key: deceptivedeceptivedeceptive Plaintext: wearediscoveredsaveyourself Cipheretxt: ZICVTWQNGRZGVTWAVZHCQYGLMGJ,Kasiski Test (contd),Repetitions in ciphertext give clues to key period If the distance of two same plaintext sequences is the multiples of key length, well get two same ciphertext sequences eg repeated “VTW” in previous example Suggests key size of 3 or 9,Kasiski Test (contd),Key size is short Brute force attack, key space=26n Key size is long Assume that keyword length is n, then Vigenre cipher, in effect, consists of n monoalphabetic substitution ciphers Analyze each of the ciphers separately by single-letter frequency analysis attack for n times to get n keys 1, 2, n-1, n 1+n, 2+n, 2n-1,2n 1+2n,2+2n, 3n-1,3n 1+3n,2+3n, 4n-1,4n k1 k2 kn-1 kn,Autokey Cipher 密钥自动生成系统,Vigenre autokey system: after key is exhausted, use plaintext for running key (to eliminate the periodic 周期性 nature) A minor error caused by decryption may lead to consequential decryption errors at fix-length intervals间隔 over a wide area,Key: deceptivewearediscoveredsav Plaintext: wearediscoveredsaveyourself Cipheretxt: ZICVTWQNGKZEIIGASXSTSLVVWLA,Autokey Cipher (contd),Key and plaintext share the same frequency distribution of letters, so statistical technique can be used for the cryptanalysis e.g., e enciphered with e would occur with a frequency of (0.1275)2 0.0163, t enciphered with t would occur with a frequency of (0.0925)2 0.0086 Take the commonly used trigram “the” as a part of plaintext & key, shifting it to get more clues for cryptanalysis (ref. for autokey cipher),2.1.5 Vernam Cipher,Invented by Gilbert Vernam in 1918 Stream Cipheron bit, not on letter Ci=piki pi=Ciki Security resides on the randomicity 随机性 of key,Common cryptanalysis is based on the fact that the same short key is used repeatedly (easy for the storage & distribution) Brute Force Attack on Vigenere Cipher,Cipheretxt: Trying Key: Message:,Why Do We Need One-time Pad?,Key length=3,abd,abd,eam,heq,NO,Common cryptanalysis is based on the fact that the same short key is used repeatedly (easy for the storage & distribution) Brute Force Attack on Vigenere Cipher,Cipheretxt: Trying Key: Message:,Why Do We Need one-time Pad?,The 4-group message & ciphertext show the common relevance,Key length=3,bbc,bbc,dan,ger,bbc,bbc,hel,pme,YES,Key space = 263 = 17576,How Can Key Be Safer?,Assume that Key is as long as the message Cipheretxt: ZICVTWQN ZICVTWQN Possible Key: RXOAPYCT RBCCPYCT Message: ILOVEYOU IHATEYOU Which one is true key? Analysis Hard to judge because M & C are not relevant Given any meaningful message of equal length to the ciphertext, there must exist a key to produce that message.,I save you I kill you Calm down Spirit up,One-time Pad,Joseph Mauborgne introduced the idea and Shannon proved the correctness Key is as long as the message, with no repetitions Plaintext and ciphertext are statistically independent Unconditionally secure (Unbreakable) Only used in military use for the difficulty of key generation & distribution,2.1.6 Playfair,Invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair Best-known multiple-letter substitution (encrypt multiple letters at one time) Digram cipher (digram to digram, i.e., E(pipi+1) = cici+1 through keyword-based 5x5 transformation table),Playfair Matrix,A 5X5 matrix of letters based on a keyword Fill in letters of keyword Fill rest of matrix with other letters eg. using the keyword MONARCHY,Keyword = monarchy Plaintext: H S E A A R M U Ciphertext: B P I M R M C M J M,Encrypting,Encrypt two letters at a time: 1.If a pair is a repeated letter, insert a filler like X, Z eg. “balloon“ encrypts as “ba lx lo on“ 2.If both letters fall in the same row, replace each with letter to right (wrapping back to start from end) eg. “ar“ encrypts as “RM“ 3.If bot