1、1,網(wǎng)絡(luò)隱私與安全（01-02）,Introduction to Cryptography -Classical Encryption Techniques,2,故事是這樣開始的,最古老的安全 需求之一： 保密性,加密技術(shù) 理論完善,古典加密技術(shù),對(duì)稱體制-DES,公鑰體制-RSA,隱私與安全 是什么？ 能解決？ 其他問題,消息認(rèn)證碼- MAC/Hash Code,3,問題：通信保密？,Security Requirements； Security Services； Confidentiality (保密性) Integrity (完整性) e.g. love letter 保密性服務(wù)能夠?qū)?/p>

2、現(xiàn)隱私性保護(hù),4,問題：通信保密,問題討論的環(huán)境,Confidentiality，機(jī)密性，保密性,5,古人的智慧,羊皮傳書 藏頭詩(shī) Caesar,6,羊皮傳書,古希臘的斯巴達(dá)人將一條1厘米寬、20厘米左右長(zhǎng)的羊皮帶，以螺旋狀繞在一根特定粗細(xì)的木棍上,7,藏頭詩(shī),明才子唐伯虎： 我愛蘭江水悠悠，愛晚亭上楓葉稠。 秋月溶溶照佛寺，香煙裊裊繞經(jīng)樓。 明朝解縉祝某宰相壽辰進(jìn)詩(shī) ： 真真宰相,老老元臣,烏紗戴頂,龜鶴遐林. 粗看密文”,渾然詩(shī)句,頌揚(yáng)兼祝愿,福祿壽全有;細(xì)究則密語(yǔ)藏頭,挖苦帶諷刺,詛咒真老烏龜”,8,Caesar Cipher,earliest known substitution ci

3、pher by Julius Caesar first attested use in military affairs example: meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB,9,Caesar Cipher Exercise,we are students of fudan university,zh duh vwxghqwv ri ixgdq xqlyhuvlwb,Encrypt?,10,Terminologies,plaintext - the original message ciphertext - the

4、 coded message key - info used in cipher known only to sender/receiver encipher (encrypt) - converting plaintext to ciphertext decipher (decrypt) - recovering plaintext from ciphertext cipher - algorithm for transforming plaintext to ciphertext,11,Symmetric Cipher Model,12,Definition,A cryptosystem

5、is a 5-tuple (E, D, p, K, C), where p is the set of plaintexts, K the set of keys, C is the set of cipher texts, E: MKC is the set of Encryption algorithms, D: CKM is the set of Decryption algorithms.,13,三個(gè)古典系統(tǒng)的再討論,Caesar 羊皮傳書 藏頭詩(shī),14,Caesar Cipher,meet me after the toga party PHHW PH DIWHU WKH WRJD

6、SDUWB p, C, K, E, D?,15,Caesar Cipher,can 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 mathematically give each letter a number a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y Z 13 14

7、15 16 17 18 19 20 21 22 23 24 25 then have Caesar cipher as: C = E(p) = (p + k) mod (26) p = D(C) = (C k) mod (26),16,羊皮傳書,E, D, p, C, K?,17,藏頭詩(shī),真真宰相,老老元臣,烏紗戴頂,龜鶴遐林. E, D, p, C, K? 全詩(shī)為密文”,其密鑰”是每句詩(shī)的首字,可串接成義,作者的真意就隱藏在詩(shī)句的首字串接文(明文”)中. Steganography，隱寫術(shù),18,Rethinking of the Model,encipher,decipher,(plain

8、text in - ciphertext out),ciphertext msg,(ciphertext in - plaintext out),(should understand nothing about the msg),eavesdropper,cmb-cmb,Shared Key,19,Need key exchange,Alice and Bob want to establish a shared secret (key) when other people (eavesdroppers) are listening How to? inbound Vs. outbound,A

9、lice,Bob,20,Discursions on the Model,Q1: Why use a key? Q2: Which parts should be kept secret? which not?,21,Discussion,模型合理嗎？ 什么當(dāng)保密；什么當(dāng)公開？ 19世紀(jì)荷蘭人A.Kerckhoffs就提出了一個(gè)在密碼學(xué)界被公認(rèn)為基礎(chǔ)的假設(shè)，也就是著名的“Kerckhoffs假設(shè)”：秘密必須全寓于密鑰。 Other Models?,22,Discussion,“誰(shuí)是我們的敵人，誰(shuí)是我們的朋友，這個(gè)問題是革命的首要問題”毛選 易用性 秘密全部寓于密鑰算法當(dāng)公開，要看應(yīng)用環(huán)境(商用

10、，軍用，) 開放的系統(tǒng)更安全，?,23,Terminologies (cont.),cryptography - study of encryption principles/methods cryptanalysis (codebreaking) - the study of principles/ methods of deciphering ciphertext without knowing key cryptology - the field of both cryptography and cryptanalysis,24,Cryptography Catalog,The type

11、 of operations used for transforming plaintext to ciphertext Substitution: each element in the plaintext is mapped into another element Transposition: elements in the plaintext are rearranged Product: multiple stages of substitutions and transpositions The number of the keys used Symmetric , single-

12、key, secret-key, conventional encryption: Both sender and receiver use the same key Asymmetric, two-key, or public-key encryption: the sender and receive each uses a different key,25,Cryptography Catalog,The way in which the plaintext is processed Block: processes the input one block of elements at

13、a time, producing an output block for each input block Stream: processes the input elements continuously, producing output one element at a time, as it goes along.,26,Substitution Techniques,Caesar cipher Easy to break!,27,There are only 25 keys to try A maps to A,B,.Z could simply try each in turn

14、a brute force search given ciphertext, just try all shifts of letters The language of Plaintext is known and easily recognizable do need to recognize when have plaintext eg. break ciphertext GCUA VQ DTGCM,Cryptanalysis of Caesar Cipher,28,Improvement on Caesar Cipher Rather than substituting accordi

15、ng to a regular pattern any letter can be substituted for any other letter, as long as each letter has a unique substitute letter, and vice versa.,Monoalphabetic Cipher,29,Monoalphabetic Cipher,K: Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplaceletter

16、s Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA hence key is 26 letters long,30,Monoalphabetic Cipher Security,now have a total of 26! = 4 x 1026 keys with so many keys, might think is secure but would be !WRONG! problem is language characteristics,31,Language Redundancy and Cryptanalysis,human languages are

17、 redundant letters are not equally commonly used in English e is by far the most common letter, then T,R,N,I,O,A,S some letters are fairly rare, eg. Z,J,X,Q tables of single, double & triple letter frequencies,32,Frequency of Letters in English Text,33,Use in Cryptanalysis,key concept - monoalphabet

18、ic substitution ciphers do not change relative letter frequencies discovered by Arabian scientists in 9th century calculate 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 triple troughs a

19、t: JK, X-Z for monoalphabetic must identify each letter tables of common double/triple letters help,34,Example Cryptanalysis,given ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ count relative letter frequencies

20、(see text) guess P & Z are e and t guess ZW is th and hence ZWP is the proceeding with trial and error finally get: it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the vietcong in moscow,35,Cryptanalytic Attacks,對(duì)于對(duì)手而言 最壞情況下，仍有一種攻

21、擊方法可用,Brute Force Search，窮舉法,36,Brute Force Search,always possible to simply try every key most basic attack, proportional to key size assume either know or recognise plaintext,37,Monoalphabetic Cipher Security,now have a total of 26! = 4 x 1026 keys with so many keys, might think is secure but would be !WRONG! problem is language characteristics,38,M