密碼學與網路安全 第2章 古典加密技術.

Presentation on theme: "密碼學與網路安全 第2章 古典加密技術."— Presentation transcript:

1 密碼學與網路安全 第2章 古典加密技術

2 對稱式加密Symmetric Encryption
也稱為傳統加密、私密金鑰加密或單金鑰加密 傳送端(加密)和接收端(解密)共用相同的金鑰 所有古典加密演算法都是私密金鑰 是1970年代公開金鑰加密發展出來之前的唯一加密方式 而且是最常用的加密方式 Symmetric encryption, also referred to as conventional encryption or single-key encryption, was the only type of encryption in use prior to the development of public-key encryption in the 1970s. It remains by far the most widely used of the two types of encryption. All traditional schemes are symmetric / single key / private-key encryption algorithms, with a single key, used for both encryption and decryption. Since both sender and receiver are equivalent, either can encrypt or decrypt messages using that common key.

3 基本術語 明文 plaintext － 原始可理解的訊息或資料
密文 ciphertext － 是由加密演算法根據明文和秘密金鑰所產生的輸出結果，內容是雜亂無章的訊息 密碼 cipher 加密法 encipher (encrypt) － 將明文轉換成密文的演算法 解密法 decipher (decrypt) － 將密文還原成明文的演算法 金鑰 key － 用在加密演算法的資訊，而且只有傳送端和接收端知道 密碼學 cryptography － 研究加密原則、方法的學科 密碼解析 cryptanalysis (codebreaking) － 研究不需金鑰而能解密的學科 密碼技術 cryptology － 研究密碼學和密碼解析的學科

4 對稱式加密模型 Detail the five ingredients of the symmetric cipher model, shown in Stallings Figure 2.1: plaintext - original message encryption algorithm – performs substitutions/transformations on plaintext secret key – control exact substitutions/transformations used in encryption algorithm ciphertext - scrambled message decryption algorithm – inverse of encryption algorithm

5 必要條件 若要安全使用傳統加密法，有兩個必要的條件： 以數學公式表示： 我們不需要保護演算法，但我們需要保管好金鑰 強固的加密演算法
只有傳送端與接收端能得知秘密金鑰 以數學公式表示： Y = EK(X) X = DK(Y) 我們不需要保護演算法，但我們需要保管好金鑰 We assume that it is impractical to decrypt a message on the basis of the cipher- text plus knowledge of the encryption/decryption algorithm, and do not need to keep the algorithm secret; rather we only need to keep the key secret. This feature of symmetric encryption is what makes it feasible for widespread use. It allows easy distribution of s/w and h/w implementations. Can take a closer look at the essential elements of a symmetric encryption scheme: mathematically it can be considered a pair of functions with: plaintext X, ciphertext Y, key K, encryption algorithm EK, decryption algorithm DK.

6 密碼學Cryptography 密碼學系統可以根據三種不同的觀點來描述： 將明文轉為密文所用的運作方式 金鑰的使用數量 處理明文的方式
替代 ／ 置換 ／ 重複的替代與置換 substitution / transposition / product 金鑰的使用數量 單金鑰或私密金鑰／ 雙金鑰或公開金鑰 處理明文的方式 區塊加密 ／ 串流加密block / stream

7 密碼解析 目的是還原金鑰，而非只還原訊息 一般的方法： 密碼解析攻擊cryptanalytic attack
暴力破解法brute-force attack Typically objective is to recover the key in use rather then simply to recover the plaintext of a single ciphertext. There are two general approaches: Cryptanalytic attacks rely on the nature of the algorithm plus perhaps some knowledge of the general characteristics of the plaintext or even some sample plaintext-ciphertext pairs. Brute-force attacks try every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained. On average,half of all possible keys must be tried to achieve success.

8 密碼解析攻擊 僅知密文 已知明文 選定明文 選定密文 選定內文 只知道演算法和密文(得知道明文是exe檔、或英文…)
除密文外，尚有一或多組 明文/密文組 選定明文 選取明文使用加密器獲得密文 選定密文 選取密文用解密器獲得明文 選定內文 選取明文或密文來加密或解密 Stallings Table 2.1 summarizes the various types of cryptanalytic attacks, based on the amount of information known to the cryptanalyst, from least to most. The most difficult problem is presented when all that is available is the ciphertext only. In some cases, not even the encryption algorithm is known, but in general we can assume that the opponent does know the algorithm used for encryption. Then with increasing information have the other attacks. Generally, an encryption algorithm is designed to withstand a known-plaintext attack.

9 密碼解析攻擊 絕對安全unconditional security 計算安全性computational security
不論攻擊者取得多少密文，如果他無法從其中的資訊解出相對應的明文，我們就說這個加密機制是絕對安全。也就是說，不論攻擊者花多少時間都不可能破解密文，因為解開密文所需的資訊不在其中 計算安全性computational security 破解加密法所需的成本超過加密訊息本身的價值，或者破解加密法所需的時間超過訊息的有效壽命，加密法就視為計算安全性 Two more definitions are worthy of note. An encryption scheme is unconditionally secure if the ciphertext generated by the scheme does not contain enough information to determine uniquely the corresponding plaintext, no matter how much ciphertext is available. An encryption scheme is said to be computationally secure if either the cost of breaking the cipher exceeds the value of the encrypted information, or the time required to break the cipher exceeds the useful lifetime of the information. Unconditional security would be nice, but the only known such cipher is the one-time pad (later). For all reasonable encryption algorithms, we have to assume computational security where it either takes too long, or is too expensive, to bother breaking the cipher.

10 暴力破解 嘗試所有可能的金鑰 平均來說，必須嘗試的金鑰數量，大約是可能的金鑰總數的一半 下表列出不同的金鑰數量所需要的時間 金鑰長度
（位元） 可能的金鑰總數 每微秒加密一次所需的時間 每微秒加密l06次所需的時間 32 232 = 4.3  109 231 µs = 35.8 秒 2.15 毫秒 56 256 = 7.2  1016 255 µs = 1142 年 10.01 小時 128 2128 = 3.4  1038 2127 µs = 5.4  1024 年 5.4  1018 年 168 2168 = 3.7  1050 2167 µs = 5.9  1036 年 5.9  1030 年 26 字元（任 意排列） 26! = 4  1026 2  1026 µs = 6.4  1012 年 6.4  106 年

11 替代加密法 以其它的字元或符號來替代將明文裡的字元 如果將明文視為連續的字元，那麼替代就是將明文的字元樣式換成密文的字元樣式
In this section and the next, we examine a sampling of what might be called classical encryption techniques. A study of these techniques enables us to illustrate the basic approaches to symmetric encryption used today and the types of cryptanalytic attacks that must be anticipated. The two basic building blocks of all encryption technique are substitution and transposition. We examine these in the next two sections. Finally, we discuss a system that combine both substitution and transposition.

12 凱撒加密法Caesar Cipher 目前所知道最早且最簡單的替代加密法 羅馬的凱撒將軍（Julius Caesar）所發明
將每個字母用其後的第三個字母來替代 例如: meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB Substitution ciphers form the first of the fundamental building blocks. The core idea is to replace one basic unit (letter/byte) with another. Whilst the early Greeks described several substitution ciphers, the first attested use in military affairs of one was by Julius Caesar, described by him in Gallic Wars (cf. Kahn pp83-84). Still call any cipher using a simple letter shift a caesar cipher, not just those with shift 3.

13 凱撒加密法 字元的順序可繞回頭： 為每個字母指定一個數值： 便能以下列方式表示這個演算法，也就是每個明文字元p會換成密文字元C：
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 為每個字母指定一個數值： 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 便能以下列方式表示這個演算法，也就是每個明文字元p會換成密文字元C： c = E(p) = (p + k) mod (26) p = D(c) = (c – k) mod (26) This mathematical description uses modulo (clock) arithmetic. Here, when you reach Z you go back to A and start again. Mod 26 implies that when you reach 26, you use 0 instead (ie the letter after Z, or goes to A or 0). Example: howdy (7,14,22,3,24) encrypted using key f (ie a shift of 5) is MTBID

14 凱撒加密法的密碼解析 只有26種可能的加密方式 如果知道密文是由凱撒加密法產生，暴力法便很容易破解，因為：
對映至從A到Z的 如果知道密文是由凱撒加密法產生，暴力法便很容易破解，因為： 已知加密/解密演算法 只要一一測試這26種對映方式 已知明文所用的語言 例如破解密文：GCUA VQ DTGCM With a caesar cipher, there are only 26 possible keys, of which only 25 are of any use, since mapping A to A etc doesn't really obscure the message! Note this basic rule of cryptanalysis "check to ensure the cipher operator hasn't goofed and sent a plaintext message by mistake"! Can try each of the keys (shifts) in turn, until can recognise the original message. See Stallings Fig 2.3 for example of search. Note: as mentioned before, do need to be able to recognise when have an original message (ie is it English or whatever). Usually easy for humans, hard for computers. Though if using say compressed data could be much harder. Example "GCUA VQ DTGCM" when broken gives "easy to break", with a shift of 2 (key C).

15 單套字母加密法 Monoalphabetic Cipher
不只字母移位，也任意排列字母 每個明文字母對映到不同的隨機密文字母 因此金鑰長達26個字母 Plain ：abcdefghijklmnopqrstuvwxyz cipher：DKVQFIBJWPESCXHTMYAUOLRGZN 明文：ifwewishtoreplaceletters 密文：WIRFRWAJUHYFTSDVFSFUUFYA With only 25 possible keys, the Caesar cipher is far from secure. A dramatic increase in the key space can be achieved by allowing an arbitrary substitution, where the translation alphabet can be any permutation of the 26 alphabetic characters. See example translation alphabet, and an encrypted message using it.

16 單套字母加密法的安全性 總共有26!種可能的金鑰，也就是4 x 1026 金鑰數量龐大，應該就很安全 但是，錯！ 問題是在語言的特性
Note that even given the very large number of keys, being 10 orders of magnitude greater than the key space for DES, the monoalphabetic substitution cipher is not secure, because it does not sufficiently obscure the underlying language characteristics.

17 字元相對出現頻率 不是所有字元的出現頻率都相同 英文裡的字母E是最常用的字母，其次是T、R、N、I、O、A、S
其他如Z、J、K、Q、X的使用頻率並不高 各種語言皆有常用字、詞的頻率統計，有助於密碼解析 As the example shows, we don't actually need all the letters in order to understand written English text. Here vowels were removed, but they're not the only redundancy. cf written Hebrew has no vowels for same reason. Are usually familiar with "party conversations", can hear one person speaking out of hubbub of many, again because of redundancy in aural language also. This redundancy is also the reason we can compress text files, the computer can derive a more compact encoding without losing any information. Basic idea is to count the relative frequencies of letters, and note the resulting pattern.

18 字元相對出現頻率 Note that all human languages have varying letter frequencies, though the number of letters and their frequencies varies. Stallings Figure 2.5 shows English letter frequencies. Seberry & Pieprzyk, "Cryptography - An Introduction to Computer Security", Prentice-Hall 1989, Appendix A has letter frequency graphs for 20 languages (most European & Japanese & Malay).

19 單套字母加密法的密碼解析 重要概念 – 單套字母替代加密不會改變字元出現的頻率 補救措施是讓一個字元有好幾種替代方式，亦即同音字
如果按照字元出現頻率來決定其密文符號的多寡，就能完全消除單一字元的頻率資訊

20 密碼解析範例 要破解的密文是： 首先找出字元的相對出現頻率，並比較標準的英文字母頻率分佈 推測密文裡的P和Z是e和t
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ 首先找出字元的相對出現頻率，並比較標準的英文字母頻率分佈 推測密文裡的P和Z是e和t 推測密文裡的ZW是th，因此ZWP是the 繼續反覆試驗，最後可得： it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow

21 普雷費爾Playfair加密法 普雷費爾是最知名的多字元加密法 這個方法將雙字元的明文視為單一元素，再將其轉成雙字元的密文
這是由英國科學家惠斯頓Charles Wheatstone爵士於1854年發明，但是他以其朋友Baron Playfair命名 Consider ways to reduce the "spikyness" of natural language text, since if just map one letter always to another, the frequency distribution is just shuffled. One approach is to encrypt more than one letter at once. The Playfair cipher is an example of doing this.

22 普雷費爾金鑰矩陣 普雷費爾演算法使用由關鍵字組成的5 × 5字元矩陣 矩陣的建構方式 例如以MONARCHY當作關鍵字
先將關鍵字字元由左至右、由上至下填入矩陣，並刪除重複字元 將26個字母剩餘的字元依序填入，而且將I跟J視為同一個字元 例如以MONARCHY當作關鍵字 M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z The best-known multiple-letter encryption cipher is the Playfair, which treats digrams in the plaintext as single units and translates these units into ciphertext digrams. The Playfair algorithm is based on the use of a 5x5 matrix of letters constructed using a keyword. The rules for filling in this 5x5 matrix are: L to R, top to bottom, first with keyword after duplicate letters have been removed, and then with the remain letters, with I/J used as a single letter. This example comes from Dorothy Sayer's book "Have His Carcase", in which Lord Peter Wimsey solves it, and describes the use of a probably word attack.

23 普雷費爾加密法的加密與解密 一次針對明文的兩個字元來加密： 若是相同字元的雙字元，就插入填充字元，例如x
如果這兩個字元位於矩陣同一列，就把第一個字元當成最後一個字元的右邊字元（繞回頭），並用它們右邊的字元來替代它們 eg. “ar" encrypts as "RM 如果這兩個字元位於矩陣同一行，就把第一個字元當成是最後一個字元的下方字元（繞回頭），並且用它們下方的字元來替代它們 否則(即兩字不同行又不同列)，則每個字元都換成與它自己同一列、但與另一個字元同一行的字元eg. “hs" encrypts to "BP", and “ea" to "IM" or "JM" Plaintext is encrypted two letters at a time,according to the rules as shown. Note how you wrap from right side back to left, or from bottom back to top. 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 (wrapping 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" encrypts to "BP", and “ea" to "IM" or "JM" (as desired) Decrypting of course works exactly in reverse. Can see this by working the example pairs shown, backwards.

24 普雷費爾加密法的安全性 安全性優於單套字母加密法 因為有26個字母，但雙字元有26 × 26 = 676 種組合，因此不易辨識雙字元
再者，單一字元的相對出現頻率變化範圍比雙字元大很多，也讓雙字元頻率分析變得更加困難 有很長一段時間此法廣被使用 例如此法是英國陸軍一次世界大戰的標準系統，且直到二次世界大戰，美國陸軍與某些聯軍仍廣泛使用 雖然普雷費爾加密法具備了相當程度的安全性，但還是很容易破解。因為它原封不動的留下很多明文語言的結構。 基本上要破解普雷費爾加密法，只要幾百個密文字元就夠了 The Playfair cipher is a great advance over simple monoalphabetic ciphers, since there are 26*26=676 digrams (vs 26 letters), so that identification of individual digrams is more difficult. Also,the relative frequencies of individual letters exhibit a much greater range than that of digrams, making frequency analysis much more difficult. The Playfair cipher was for a long time considered unbreakable. It was used as the standard field system by the British Army in World War I and still enjoyed considerable use by the U.S.Army and other Allied forces during World War II. Despite this level of confidence in its security,the Playfair cipher is relatively easy to break because it still leaves much of the structure of the plaintext language intact

25 多套字母加密法 Polyalphabetic Ciphers
改進單套字母加密，以多套字母加密替代而提高安全性 以一組相關的單套字母作為替代的規則 以金鑰決定在轉換時要使用哪種替代規則 One approach to reducing the "spikyness" of natural language text is used the Playfair cipher which encrypts more than one letter at once. We now consider the other alternative, using multiple cipher alphabets in turn. This gives the attacker more work, since many alphabets need to be guessed, and because the frequency distribution is more complex, since the same plaintext letter could be replaced by several ciphertext letters, depending on which alphabet is used. The general name for this approach is a polyalphabetic substitution cipher. All these techniques have the following features in common: A set of related monoalphabetic substitution rules is used. 2. A key determines which particular rule is chosen for a given transformation.

26 維吉尼亞加密法 Vigenère Cipher
最簡單的多套字母替代加密法 以位移量0到25的26個凱撒加密法來組成相關的多套字母加密的替代規則 維吉尼亞表(表2.3)有助於瞭解及使用這種方法 The best known, and one of the simplest, such algorithms is referred to as the Vigenère cipher, where the set of related monoalphabetic substitution rules consists of the 26 Caesar ciphers, with shifts of 0 through 25. Each cipher is denoted by a key letter, which is the ciphertext letter that substitutes for the plaintext letter ‘a’, and which are each used in turn, as shown next.

27

28 維吉尼亞加密法範例 加密需要與訊息一樣長的金鑰 金鑰通常是某個重複的關鍵字 例如關鍵字是deceptive的以下加密範例：
金鑰：deceptivedeceptivedeceptive 明文：wearediscoveredsaveyourself 密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ

29 維吉尼亞加密的安全性 維吉尼亞加密法的強度在於一個明文字元可以對應到好幾個密文字元
每個密文字元是由關鍵字裡的字母決定，因此能隱藏字元出現的頻率資訊 維吉尼亞加密法並沒有隱藏所有的明文結構 雖然優於普雷費爾加密法，但還是殘存著相當程度的頻率資訊

30 維吉尼亞加密的破解之道 若使用單套字母加密法，密文的字元統計資訊會與明文趨於一致
若懷疑使用的是維吉尼亞加密法，破解的過程會由如何求出關鍵字長度而定 關鍵字長度：若兩個相同順序(sequence序列)的明文字串距離，剛好是關鍵字長度的整數倍，就會產生相同的密文字串 破解這個加密法的重點在於，如果關鍵字長度是N，這個加密法實際上就是由N個單套字母加密法所組成

31 自動金鑰系統 長度與訊息相同的關鍵字能消除關鍵字會定期出現的特性 維吉尼亞加密法提出了自動金鑰系統 這個系統會將明文接在關鍵字之後而形成金鑰
例如關鍵字deceptive的範例： 金鑰：deceptivewearediscoveredsav 明文：wearediscoveredsaveyourself 密文：ZICVTWQNGKZEIIGASXSTSLVVWLA 但還是會因為金鑰與明文的字元頻率分佈相同，而能以統計的技巧破解

32 單次金鑰加密法One-Time Pad 使用與訊息等長的隨機金鑰，能不需重覆使用金鑰而達到相當程度的安全
且這把金鑰用在加密、解密單一訊息之後，就丟棄不用 因此每個新的訊息都需要與訊息等長的新金鑰 此法所產生的隨機密文與原始明文並無統計的關聯性 單次金鑰加密法的密文並無明文的任何訊息，因此無從破解 問題：key的產生和安全的發送與保護 The One-Time Pad is an evolution of the Vernham cipher, which was invented by Gilbert Vernham in 1918, and used a long tape of random letters to encrypt the message. An Army Signal Corp officer, Joseph Mauborgne, proposed an improvement using a random key that was truly as long as the message, with no repetitions, which thus totally obscures the original message. It produces random output that bears no statistical relationship to the plaintext. Because the ciphertext contains no information whatsoever about the plaintext, there is simply no way to break the code, since any plaintext can be mapped to any ciphertext given some key. The one-time pad offers complete security but, in practice, has two fundamental difficulties: There is the practical problem of making large quantities of random keys. 2. And the problem of key distribution and protection, where for every message to be sent, a key of equal length is needed by both sender and receiver. Because of these difficulties, the one-time pad is of limited utility, and is useful primarily for low-bandwidth channels requiring very high security.

33 置換加密法 Transposition Ciphers
目前所提，都是將明文符號換成另一個密文符號 另一種完全不同的對映方式，是以某種形式重新排列明文字元 這種技巧稱為置換加密法

34 柵欄加密法Rail Fence cipher
最簡單的置換加密方法 將明文排成一連串的對角線形式，然後再一列一列讀出 例如： 明文：meet me after the toga party 密文：m e m a t r h t g p r y e t e f e t e o a a t 單純的置換加密方式很容易被識破 因為密文和原始明文的字元頻率分佈都相同

35 列置換加密法 Row Transposition Ciphers
比較複雜的方法是將訊息一列一列排成矩形，再一行一行讀出來 但還要交換行與行之間的順序 「行的順序」就變成這個演算法的金鑰 例如： 金鑰： 明文：a t t a c k p o s t p o n e d u n t i l t w o a m x y z 密文：TTNAAPTMTSUOAODWCOIXKNLYPETZ

36 回轉機Rotor Machines 回轉機是現代加密法出現之前，最常見的複雜加密方式 廣泛用於二次大戰： 實作了非常複雜且多樣的替代加密法
德軍Enigma、聯軍Hagelin、日軍Purple 實作了非常複雜且多樣的替代加密法 是由一組獨立、且能讓電流脈衝流過的回轉柱所組成 3柱回轉機有263=17576種不同的字母替代方式 The next major advance in ciphers required use of mechanical cipher machines which enabled to use of complex varying substitutions. A rotor machine consists of a set of independently rotating cylinders through which electrical pulses can flow. Each cylinder has 26 input pins and 26 output pins, with internal wiring that connects each input pin to a unique output pin. If we associate each input and output pin with a letter of the alphabet, then a single cylinder defines a monoalphabetic substitution. After each input key is depressed, the cylinder rotates one position, so that the internal connections are shifted accordingly. The power of the rotor machine is in the use of multiple cylinders, in which the output pins of one cylinder are connected to the input pins of the next, and with the cylinders rotating like an “odometer”, leading to a very large number of substitution alphabets being used, eg with 3 cylinders have 263=17576 alphabets used. They were extensively used in world war 2, and the history of their use and analysis is one of the great stories from WW2.

37 聯軍所用的Hagelin回轉機

38 資訊藏密法Steganography 加密之外的另一種選擇 隱藏了訊息存在的事實： 缺點：成本高、費時 字元標記 看不見的墨水 針孔
打字機修正色帶 光碟利用資料頁框裡的最低位元隱藏資訊 缺點：成本高、費時

39 總結 古典加密技術與術語 單套字母加密法 字元出現頻率的密碼解析技巧 普雷費爾加密法 多套字母加密法 置換加密法 回轉機 資訊藏密法