《01-02+密码学初探.ppt》由会员分享，可在线阅读，更多相关《01-02+密码学初探.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、LiJT网络隐私与安全（网络隐私与安全（01-02）Introduction to Cryptography-Classical Encryption Techniques1LiJT故事是这样开始的故事是这样开始的最古老的安全最古老的安全需求之一：需求之一：保密性保密性加密技术加密技术理论完善理论完善古典加密技术古典加密技术对称体制对称体制-DES公钥体制公钥体制-RSA隐私与安全隐私与安全是什么？是什么？能解决？能解决？其他问题其他问题消息认证码消息认证码-MAC/Hash Code2LiJT问题：通信保密？问题：通信保密？Security Requirements；Security Ser
2、vices；Confidentiality(保密性保密性)Integrity(完整性完整性)e.g.love letter保密性服务能够实现隐私性保护保密性服务能够实现隐私性保护3LiJT问题：通信保密问题：通信保密问题讨论的环境 Confidentiality，机密性，保密性，机密性，保密性 4LiJT古人的智慧古人的智慧羊皮传书羊皮传书藏头诗藏头诗Caesar5LiJT羊皮传书羊皮传书古希腊的斯巴达人将一条1厘米宽、20厘米左右长的羊皮带，以螺旋状绕在一根特定粗细的木棍上6LiJT藏头诗藏头诗明才子唐伯虎：明才子唐伯虎：我爱兰江水悠悠，爱晚亭上枫叶稠。我爱兰江水悠悠，爱晚亭上枫叶稠。秋月溶
3、溶照佛寺，香烟袅袅绕经楼。秋月溶溶照佛寺，香烟袅袅绕经楼。明朝解缙祝某宰相寿辰进诗明朝解缙祝某宰相寿辰进诗：真真宰相真真宰相,老老元臣老老元臣,乌纱戴顶乌纱戴顶,龟鹤遐林龟鹤遐林.粗看粗看密文密文”,浑然诗句浑然诗句,颂扬兼祝愿颂扬兼祝愿,福禄寿全福禄寿全有有;细究则密语藏头细究则密语藏头,挖苦带讽刺挖苦带讽刺,诅咒诅咒真老乌真老乌龟龟”7LiJTCaesar Cipherearliest known substitution cipher by Julius Caesar first attested use in military affairsexample:meet me after
4、the toga partyPHHW PH DIWHU WKH WRJD SDUWB8LiJTCaesar Cipher Exercisewearestudentsoffudanuniversitywearestudentsoffudanuniversityzhzhduhduhvwxghqwvvwxghqwv riri ixgdqixgdq xqlyhuvlwbxqlyhuvlwbEncrypt?9LiJTTerminologiesplaintext-the original message ciphertext-the coded message key-info used in ciphe
5、r known only to sender/receiver encipher(encrypt)-converting plaintext to ciphertext decipher(decrypt)-recovering plaintext from ciphertextcipher-algorithm for transforming plaintext to ciphertext 10LiJTSymmetric Cipher Model11LiJTDefinitionA cryptosystem is a 5-tuple(E,D,p,K,C),wherep is the set of
6、 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.12LiJT三个古典系统的再讨论三个古典系统的再讨论Caesar羊皮传书羊皮传书藏头诗藏头诗13LiJTCaesar Cipher meet me after the toga partyPHHW PH DIWHU WKH WRJD SDUWBp,C,K,E,D?14LiJTCaesar Cipher can d
7、efine 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 25then have Caesar c
8、ipher as:C=E(p)=(p+k)mod(26)p=D(C)=(C k)mod(26)15LiJT羊皮传书羊皮传书E,D,p,C,K?16LiJT藏头诗藏头诗真真宰相真真宰相,老老元臣老老元臣,乌纱戴顶乌纱戴顶,龟鹤遐林龟鹤遐林.E,D,p,C,K?全诗为全诗为密文密文”,其其密钥密钥”是每句诗的首字是每句诗的首字,可串接成义可串接成义,作者的真意就隐藏在诗句的首作者的真意就隐藏在诗句的首字串接文字串接文(明文明文”)中中.Steganography，隐写术隐写术17LiJTRethinking of the Modelencipherdecipher(plaintext in-cip
9、hertext out)ciphertext ciphertext msg msg(ciphertext in -plaintext out)(should understand nothingnothing about the msg)eavesdropperbla-blacmb-cmbcmb-cmbbla-blaShared Key18LiJTNeed key exchangeAlice and Bob want to establish a shared secret(key)when other people(eavesdroppers)are listeningHow to?inbo
10、und Vs.outboundAliceAliceBobBob19LiJTDiscursions on the ModelQ1:Why use a key?Q2:Which parts should be kept secret?which not?20LiJTDiscussion模型合理吗？模型合理吗？什么当保密；什么当公开？什么当保密；什么当公开？19世纪荷兰人世纪荷兰人A.Kerckhoffs就提出了一个在密就提出了一个在密码学界被公认为基础的假设，也就是著名的码学界被公认为基础的假设，也就是著名的“Kerckhoffs假设假设”：秘密必须全寓于密钥。：秘密必须全寓于密钥。Other M
11、odels?21LiJTDiscussion“谁是我们的敌人，谁是我们的朋友，这谁是我们的敌人，谁是我们的朋友，这个问题是革命的首要问题个问题是革命的首要问题”毛选毛选易用性易用性秘密全部寓于密钥秘密全部寓于密钥算法当公开，要看应用算法当公开，要看应用环境环境(商用，军用，商用，军用，)开放的系统更安全，开放的系统更安全，?22LiJTTerminologies(cont.)cryptography-study of encryption principles/methodscryptanalysis(codebreaking)-the study of principles/methods
12、of deciphering ciphertext without knowing keycryptology-the field of both cryptography and cryptanalysis23LiJTCryptography CatalogThe type of operations used for transforming plaintext to ciphertextSubstitution:each element in the plaintext is mapped into another elementTransposition:elements in the
13、 plaintext are rearrangedProduct:multiple stages of substitutions and transpositionsThe number of the keys usedSymmetric,single-key,secret-key,conventional encryption:Both sender and receiver use the same keyAsymmetric,two-key,or public-key encryption:the sender and receive each uses a different key
14、24LiJTCryptography CatalogThe way in which the plaintext is processedBlock:processes the input one block of elements at a time,producing an output block for each input blockStream:processes the input elements continuously,producing output one element at a time,as it goes along.25LiJTSubstitution Tec
15、hniquesCaesar cipherEasy to break!26LiJTThere are only 25 keys to tryA maps to A,B,.Z could simply try each in turn a brute force search given ciphertext,just try all shifts of lettersThe language of Plaintext is known and easily recognizabledo need to recognize when have plaintext eg.break cipherte
16、xt GCUA VQ DTGCMCryptanalysis of Caesar Cipher 27LiJTImprovement on Caesar CipherRather than substituting according 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 Cipher28LiJTMonoalphabetic C
17、ipherK:Plain:abcdefghijklmnopqrstuvwxyz Cipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA hence key is 26 letters long29LiJTMonoalphabetic Cipher Securitynow have a total of 26!=4 x 1026 keys with so many keys,might think is secure but would be!WR
18、ONG!problem is language characteristics30LiJTLanguage Redundancy and Cryptanalysishuman languages are 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,Qtables of single,double&triple letter frequenc
19、ies31LiJTFrequency of Letters in English Text32LiJTUse in Cryptanalysiskey concept-monoalphabetic substitution ciphers do not change relative letter frequencies discovered by Arabian scientists in 9th centurycalculate letter frequencies for ciphertextcompare counts/plots against known values if Caes
20、ar 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 help33LiJTExample Cryptanalysisgiven ciphertext:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQ
21、UZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQcount relative letter frequencies(see text)guess P&Z are e and tguess ZW is th and hence ZWP is theproceeding with trial and error finally get:it was disclosed yesterday that several informal butdirect contacts have been made with politicalrepresentati
22、ves of the vietcong in moscow34LiJTCryptanalytic Attacks对于对手而言对于对手而言最坏情况下，仍有一种攻击方法可用最坏情况下，仍有一种攻击方法可用Brute Force Search，穷举法，穷举法35LiJTBrute Force Searchalways possible to simply try every key most basic attack,proportional to key size assume either know or recognise plaintext36LiJTMonoalphabetic Ciphe
23、r Securitynow have a total of 26!=4 x 1026 keys with so many keys,might think is secure but would be!WRONG!problem is language characteristics37LiJTMore Definitionsunconditional security no matter how much computer power is available,the cipher cannot be broken since the ciphertext provides insuffic
24、ient information to uniquely determine the corresponding plaintext computational security given limited computing resources(eg.time needed for calculations is greater than age of universe),the cipher cannot be broken Unconditional security would be nice,but the only known such cipher is the one-time pad(later).For all reasonable encryption algorithms,have to assume computational security where it either takes too long,or is too expensive,to bother breaking the cipher.38LiJThomework请你设计一种好的加密方法，并简单分析你给出方法在抗词频分析攻击方面的性能。对单字母表的加密方法你有何种改进建议？39