《密码学基础知识课件.ppt》由会员分享，可在线阅读，更多相关《密码学基础知识课件.ppt（149页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 夫学须静也，才须学也，非学无以广才，非志无以成学。 诸葛亮 概述n密码学 密码编码学 密码分析学 n作用： 机密性 鉴别 完整性 抗抵赖 密码学文献的发展历程：n1918年，Friedman重合指数及其在密码学中的应用。n1918年，Heberm的转轮机n1949年，Shannon保密系统的通信理论n1967年，Kahn破译者n1971年，Feistel的Lucifer n1975年，Diffie & Hellman提出公开密钥密码学，密码学的新方向n1977年，DES成为联邦信息处理标准n1978年，MIT的RSA算法。n1985年，ElGamal体制（离散对数）； Koblitz & M
2、iller 提出椭圆曲线密码学 1995年，Hoffstein，Pipher，Siverman发明NTRU密码 n密码学之前，信息安全的保护主要是通过物理和行政手段实现的。n密码学最早多用于外交情报和军事领域。n现代密码学家通常是理论数学家。 n第一阶段： 手工计算n第二阶段： 机械和电动机械n第三阶段： 电子和计算机内容n1. 保密与保密系统n2. 古典密码技术n3. 密码体制n4. 密码分析n5. 加密方式一、保密与保密系统保密学：研究信息系统安全保密的科学。 1.保密系统模型图一个密码体制由五元组（P，C，K，E，D）构成。Symmetric Cipher ModelBasic Term
3、inologynplaintext - the original message nciphertext - the coded message ncipher - algorithm for transforming plaintext to ciphertext nkey - info used in cipher known only to sender/receiver nencipher (encrypt) - converting plaintext to ciphertext ndecipher (decrypt) - recovering ciphertext from pla
4、intextncryptography - study of encryption principles/methodsncryptanalysis (codebreaking) - the study of principles/ methods of deciphering ciphertext without knowing keyncryptology - the field of both cryptography and cryptanalysis 2.密码设计准则n保密系统抗击密码分析，应满足： 1）系统即使达不到理论上是不可破的，也应当为实际上是不可破的。 2）Kerckhof
5、f原则。系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。 3）加密和解密算法适用于所有密钥空间中的元素。 4）系统便于实现和使用方便。 Kerckhoff六项准则在19世纪对军事密码体制提出六项准则：n密码体制即便不是在理论上不可破，也应该是实际上不可破的。n体制的泄露不应该给通信者带来麻烦。n3.保密系统的通信理论n明文n密码系统的熵n惟一解距离UDPlaintext明文明文nEntropy:一条信息的信息量通过熵来度量。是对信息或不确定性的数学度量，通过概率分布的函数来计算。n语言信息率：r=H(M)/N N相当大时，标准英语的语言信息率在1.0-1.5/字母之间。n语言绝对信息
6、率：假定每一个字符串是等可能的，对每个字母编码的最大位数。 n英文 R=logL=log26=4.7位/字母nThomas Cover采用随机估算技术得到的信息率为1.3位/字符。n自然语言具有高冗余度。D=R-r=3.4位/字母。英语语言是75%冗余。Huffmann一条ASCII消息，每字节消息含有与英语相等的1.3位的消息，她的冗余信息为6.7位，相当于每位ASCII文本有0.84位冗余 n自然语言的高冗余度为密码分析提供了一个重要工具。n它最重要也是最基本的特征：单个字母出现的频率。密码系统的熵n由密钥空间大小来衡量 H(K)=log K一般来说，熵越大，破译它越困难。密钥：尽量使密钥
7、源为无记忆均匀分布源。 n密文的统计特征由明文和密钥的统计特征完全决定。n收到的密文越长，分析者找到密钥或明文的可能性越大，为确信分析者可找到唯一的密钥，理论上S至少将要多长。惟一解距离UDn在给定足够的计算时间下，分析者能唯一计算出密钥所需密文的平均值。n惟一解距离Unicity Distance码量：使一个具有无限计算能力的攻击者能够恢复惟一的加密密钥所需要的最小密文量（字符数）。在达到惟一解距离时，密钥暧昧度趋近于零。n 临界值 S=H(K)/log e-H(m) 称为UD。UDn定义为使得伪密钥的期望值等于零的n的值。n当密文字符大于UD时，这种密码就存在一个解，而当密文字符小于UD时
8、，就会出现多个可能的解。n它利用信息论描述了被截获的密文量和成功攻击的可能性之间的关系。UDnShannon指出：惟一解距离可以保证当其太小时，密码系统是不安全的，但并不保证当其较大时，密码系统就是安全的。惟一解距离不是对密码分析需要多少密文的度量，而是对存在唯一合理的密码分析所需密文数量的指标。n惟一解距离与冗余度成反比，当冗余度接近于零时，一个普通的密码系统也可能是不可破的。UDn一般而言，惟一解距离越长，密码系统越好。无穷大时为理想保密。密码分析n利用自然语言的冗余度来减少可能的明文数目。n语言的冗余度越大，它就越容易被攻击。n最重要也是最基本的特征：单个字母出现的频率。n一个好的加密算
9、法是一种混合变换，它将有意义的小区域中的有意义的消息相当均匀地分布到在整个消息空间中。4.密码系统的安全性n是密码学研究的一个重要课题n有两种定义“安全性”的方法： 基于信息论的方法（经典方法） 基于计算复杂性理论的方法（现代方法） 基于信息论的方法：用密文中是否蕴含明文的信息作为标准。 基于计算复杂性理论的方法：是考虑信息是否能有效地被提取出来。现代密码学的基础 传统的密码学和公钥密码学的基础是信息论和计算复杂性理论 信息理论密码学 计算复杂性理论密码学 n信息论告诉我们，所有的密码算法（OTP除外）都能被破译。n复杂性理论告诉我们，何时能被破译。信息理论密码学nShannon用不确定性和惟
10、一解距离度量了密码系统（体制）的安全性。密码系统的安全性： n理论保密：完全保密 理想保密n实际保密：计算安全 （可证明安全性）理论安全n经典方法n无条件安全性n基于信息论的密码学n信息理论密码学：用信息论的观点和方法研究密码系统模型的建立、密码的安全性及破译等，它所研究的安全性准则，假定密码分析者的计算资源，不受限制 完全保密n理论上不可破译的密码体制。必要条件：明文数、密钥数和密文数都相等的密码体制，将每个明文变换成每个密文都恰好有一个密钥，所有的密钥都是等可能的。nShannon从理论上证明：仅当可能的密钥数目至少与可能的消息数目一样多时，完全保密才是有可能的。完全保密n仅有一次一密（O
11、TP）乱码本的密码系统可获得完全保密。nOne-Time Pad在要求无条件安全的军事和外交环境中有着很重要的作用。 完全保密：（完善的或无条件的保密系统）n给定密文y，明文为x的后验概率等于明文x的先验概率理想保密n理论上不可译的，它的惟一解距离UD趋向于无穷大的密码体制。n意味着语言的多余度趋向于零。当然消除语言中的全部多余度事实上不可能。n它是不实用的，但它揭示我们设计密码体制（算法）时，应尽量缩小多余度。n明文信息加密前先进行信源编码。 n一个完全保密的密码系统必须是一个理想保密的密码系统，但是一个理想保密的密码系统不一定是一个完全保密的密码系统。实际安全n现代方法n有条件安全性n基于
12、复杂性理论的密码学n复杂性理论密码学：用复杂性理论的观点和方法研究密码系统模型的建立、密码的安全性分析及破译等。假定密码分析者的计算资源是有限的，受到限制实际安全n实际安全性又称为计算上的安全性。n计算安全性：涉及攻破密码体制所做的计算上的努力。n可证明安全性：安全性归结为某个经过深入研究的数学难题。实际安全性主要考虑：n计算能力（基本运算次数、存储量）n破译算法的有效性算法：求解某一问题的、一步一步地执行的计算过程。计算复杂性n问题的计算复杂性 可解问题的最有效算法的计算复杂性n算法的计算复杂性 运行它所需的计算能力。常常用两个变量来度量：时间复杂性T和空间复杂性S（或所需存储空间） n“计
13、算上安全”：指利用已有的最好的方法破译该系统所需要的努力超过了敌手的破译能力（时间、空间、资金等）或破译该系统的难度等价于解数学上的某个已知难题（计算复杂性）。计算复杂性n计算复杂性理论是密码系统安全性定义的理论基础。n算法：函数 1（常数）、对数、n（线性函数）、二次函数、三次函数、多项式函数、亚指数、指数函数n问题：P、NP、NPC 时间复杂性n一个算法的计算复杂性或有效性可以用执行该算法所需的运行时间和内存空间来度量。n时间复杂性有两种定义方法： 1。用图灵机表示一个算法 2。该算法的比特运算次数 n计算上保密： 理论上可破，实际上难破，而不是不可破。密码体制安全性准则n计算安全性：n可
14、证明安全性：n无条件安全性：5.密码编码系统分类： n密码编码系统分类： 明文转换为密文操作的类型 替代 置换 密钥数量 单钥 双钥 明文处理方式 分组密码 序列密码Cryptographyncan characterize by:ntype of encryption operations usednsubstitution / transposition / productnnumber of keys usednsingle-key or private / two-key or publicnway in which plaintext is processednblock / str
15、eam“Purple”紫码n1941.12.7日本偷袭珍珠港n1942.1美成功破译JN-25n1942.4美轰炸日东京、神户等n1942.5.7-8巴布亚新几内亚的莫尔兹比港Port Moresby（印尼）n1942中途岛之战n 4.18“山本五十六”飞机降落时被击落二、古典密码技术n1. 代替密码：单表代替密码、 Playfair、Hill、Vigenere、OTPn2. 置换密码：n3. 乘积密码：n4. 转轮机n5. 隐写术1. Substitution Ciphersnwhere letters of plaintext are replaced by other letters o
16、r by numbers or symbolsnor if plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns 代替密码n单表代替密码n多名码代替密码n多字母代替密码n多表代替密码1）单表代替密码n单表代替密码 例如“凯撒”密码 古罗马军队用 由Julius Caesar发明明文字母 A B C D E F G H I K L M N O P Q R S T V X Y Z密文字母 D
17、 E F G H I K L M N O P Q R S T V X Y Z A B C注：拉丁文不用J，U，W Caesar Ciphernearliest known substitution ciphernby Julius Caesar nfirst attested use in military affairsnreplaces each letter by 3rd letter onnexample:meet me after the toga partyPHHW PH DIWHU WKH WRJD SDUWBCaesar Cipherncan define transforma
18、tion 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 Cnmathematically 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 25nthen have Caesar cipher as:C = E
19、(p) = (p + k) mod (26)p = D(C) = (C k) mod (26)Cryptanalysis of Caesar Ciphernonly have 26 possible ciphers nA maps to A,B,.Z ncould simply try each in turn na brute force search ngiven ciphertext, just try all shifts of lettersndo need to recognize when have plaintextneg. break ciphertext GCUA VQ D
20、TGCMMonoalphabetic单表代替 Ciphernrather than just shifting the alphabet ncould shuffle (jumble) the letters arbitrarily neach plaintext letter maps to a different random ciphertext letter nhence key is 26 letters long Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext: ifwewi
21、shtoreplacelettersCiphertext: WIRFRWAJUHYFTSDVFSFUUFYAMonoalphabetic Cipher Securitynnow have a total of 26! = 4 x 1026 keys nwith so many keys, might think is secure nbut would be !WRONG! nproblem is language characteristicsn单表代替密码不能掩盖明文语言的所有统计特性。Language Redundancy and Cryptanalysisnhuman language
22、s are redundant neg th lrd s m shphrd shll nt wnt nletters are not equally commonly used nin English e is by far the most common letter nthen T,R,N,I,O,A,S nother letters are fairly rare ncf. Z,J,K,Q,X nhave tables of single, double & triple letter frequencies English Letter FrequenciesUse in Crypta
23、nalysisnkey concept - monoalphabetic substitution ciphers do not change relative letter frequencies ndiscovered by Arabian scientists in 9th centuryncalculate letter frequencies for ciphertextncompare counts/plots against known values nif Caesar cipher look for common peaks/troughs npeaks at: A-E-I
24、triple, NO pair, RST triplentroughs at: JK, X-Znfor monoalphabetic must identify each letterntables of common double/triple letters help安全性n取决于密文在多大程度上保留了明文语言的语法模式和结构。n理想的字母频率分布情况：如果频率分配的信息完全给加密过程给隐藏了，那么密文的频率曲线应该是一条水平的线。n减少密文中残留明文语言结构的基本方法：1）对明文中的多个字母一起加密 2）采用多表代替密码Example Cryptanalysisngiven cipher
25、text:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQncount relative letter frequencies (see text)nguess P & Z are e and tnguess ZW is th and hence ZWP is thenproceeding with trial and error finally get:it was disclosed yesterda
26、y that several informal butdirect contacts have been made with politicalrepresentatives of the vietcong in moscow n单表代替密码 移位代替密码E(i)=i+k=j mod q 乘数密码E(i)=ik=j mod q k与q互素 线性同余密码(仿射密码Affine Cipher) E(i)=ik1+k0=j mod q k1与q互素n多表代替密码 2）Playfair Ciphernnot even the large number of keys in a monoalphabet
27、ic cipher provides security none approach to improving security was to encrypt multiple letters nthe Playfair Cipher is an example ninvented by Charles Wheatstone in 1854, but named after his friend Baron Playfair n应用： 第一次世界大战中英军就使用它作为陆军的标准加密体制，在第二次世界大战中，美军极其他一些盟军用它来进行加密。Playfair Key Matrixna 5X5 ma
28、trix of letters based on a keyword nfill in letters of keyword (sans duplicates) nfill rest of matrix with other lettersneg. using the keyword MONARCHYMONARCHYBDEFGIKLPQSTUVWXZEncrypting and Decryptingnplaintext encrypted two letters at a time: 1.if a pair is a repeated letter, insert a filler like
29、X, 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 both letters fall in the same column, replace each with the letter below it (again wrapping to top from bottom), eg. “mu enc
30、rypts to CM 4.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) Security of the Playfair Ciphernsecurity much improved over monoalphabeticnsince have 26 x 26 = 676 digrams nwould need a 676
31、entry frequency table to analyse (verses 26 for a monoalphabetic) nand correspondingly more ciphertext nwas widely used for many years (eg. US & British military in WW1) nit can be broken, given a few hundred letters nsince still has much of plaintext structure Polyalphabetic Ciphersnanother approac
32、h to improving security is to use multiple cipher alphabets ncalled polyalphabetic substitution ciphers 多表代替密码nmakes cryptanalysis harder with more alphabets to guess and flatter frequency distribution nuse a key to select which alphabet is used for each letter of the message nuse each alphabet in t
33、urn nrepeat from start after end of key is reached3.Hill 代数法n利用线性变换的方法，但在Z26上进行。n代数法（Hill密码） A B C D E F G H I J K L M 4 8 25 2 9 20 16 5 17 3 0 22 13 N O P Q R S T U V W X Y Z 24 6 21 15 23 19 12 7 11 18 1 14 10 A-Z 取值 0-25。 加密：y1=8x1+6x2+9x3+5x4 y2=6x1+9x2+5x3+10 x4 y3=5x1+8x2+4x3+9x4 y4=10 x1+6x2
34、+11x3+4x4e.g. HELP x1=H=5 x2=E=9 x3=L=22 x4=P=21 加密后y1=397mod26=7 y2=15 y3=10 y4=14 密文为UQZY 解密：x1=23y1+20y2+5y3+1y4 x2=2y1+11y2+18y3+1y4 x3=2y1+20y2+6y3+25y4 x4=25y1+2y2+22y3+25y4 nHill的优点：完全隐蔽了单字母频率特性。Hill的矩阵越大，所隐蔽的频率信息越多。nHill密码既不是一种纯换位密码，也不是一种纯代替密码。大多数“现代”密码算法都是将换位密码和代替密码算法有机的结合 。nHill密码算法具有线性的缺点
35、。 应用nHill密码由数学家Lester S Hill 1929年研制。n在第二次世界大战中，该密码被用来对无线电呼叫信号进行加密，加密和解密均通过机械设备（而非电子设备）来完成。n较易被已知明文破解。4）Vigenre Ciphernsimplest polyalphabetic substitution cipher is the Vigenre Cipher 最简单、最著名neffectively multiple caesar ciphers nkey is multiple letters long K = k1 k2 . Kd nith letter specifies ith
36、alphabet to use nuse each alphabet in turn nrepeat from start after d letters in messagendecryption simply works in reverse n代换规则集由26个类似Caesar密码的代换表组成。n依赖于密钥词的长度Examplenwrite the plaintext out nwrite the keyword repeated above itnuse each key letter as a caesar cipher key nencrypt the corresponding
37、plaintext letterneg using keyword deceptivekey: deceptivedeceptivedeceptiveplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJAidsnsimple aids can assist with en/decryption na Saint-Cyr Slide is a simple manual aid na slide with repeated alphabet nline up plaintext A with ke
38、y letter, eg C nthen read off any mapping for key letter ncan bend round into a cipher disk nor expand into a Vigenre Tableau (see text Table 2.3)Security of Vigenre Ciphersnhave multiple ciphertext letters for each plaintext letternhence letter frequencies are obscurednbut not totally lostnstart wi
39、th letter frequenciesnsee if look monoalphabetic or notnif not, then need to determine number of alphabets, since then can attach eachKasiski Methodnmethod developed by Babbage / Kasiski nrepetitions in ciphertext give clues to period nso find same plaintext an exact period apart nwhich results in t
40、he same ciphertext nof course, could also be random flukeneg repeated “VTW” in previous examplensuggests size of 3 or 9nthen attack each monoalphabetic cipher individually using same techniques as beforeAutokey Ciphernideally want a key as long as the messagenVigenre proposed the autokey cipher nwit
41、h keyword is prefixed to message as keynknowing keyword can recover the first few letters nuse these in turn on the rest of the messagenbut still have frequency characteristics to attack neg. given key deceptivekey: deceptivewearediscoveredsavplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQN
42、GKZEIIGASXSTSLVVWLA5）One-Time Pad(一次一密)nif a truly random key as long as the message is used, the cipher will be secure ncalled a One-Time padnis unbreakable since ciphertext bears no statistical relationship to the plaintextnsince for any plaintext & any ciphertext there exists a key mapping one to
43、 otherncan only use the key once thoughnhave problem of safe distribution of key 一次一密n陆军情报官Mauborgne建议使用与消息一样长且无重复的随机密钥来加密消息n一次一密的安全性完全取决于密钥的随机性n存在两个难点： 产生大规模随机密钥 密钥的分配和保护主要应用于安全性要求很高的低带宽信道。2.Transposition Ciphers n置换密码nnow consider classical transposition or permutation ciphers nthese hide the mess
44、age by rearranging the letter order nwithout altering the actual letters usedncan recognise these since have the same frequency distribution as the original text n移位密码 古希腊的“天书”器械，公元前400年希腊人采用。斯巴达克人塞塔发明的。 加密方法 密钥Row Transposition Ciphersna more complex scheme栅栏技术nwrite letters of message out in rows
45、over a specified number of columnsnthen reorder the columns according to some key before reading off the rowsKey: 4 3 1 2 5 6 7Plaintext: 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 zCiphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ n代替密码Substitution：明文字母被不同的密文字母所代替。n置换密码Transposition：Permutation保持
46、明文的所有字母不变，只是利用置换打乱了明文字母的位置和次序。3.Product Ciphersciphers using substitutions or transpositions are not secure because of language characteristicsnhence consider using several ciphers in succession to make harder, but: ntwo substitutions make a more complex substitution ntwo transpositions make more co
47、mplex transposition nbut a substitution followed by a transposition makes a new much harder cipher nthis is bridge from classical to modern ciphers n乘积密码： 以德军第一次世界大战中所使用的密码为例：ADFGVX乘积密码 A D F G V X 明文：P R O D U C TA K Z W R 1 F C I P H E R SD 9 B 6 C L 5 中间报文：F Q 7 J P G X FG AG VD VF XA DG XV G E V
48、 Y 3 A N DG XF FG VG GA AG XGV 8 O D H 0 2X U 4 I S T M D E U T S C H 密钥 2 3 7 6 5 1 4 排列顺序 F G A G V D V 密文： F X A D G X V DXGX FFDG GXGG D G X F F G V VVVG VGFG GDFA G G A A G X G AAXA 4. Rotor Machinesnbefore modern ciphers, rotor machines were most common product ciphernwere widely used in WW2nG
49、erman Enigma, Allied Hagelin, Japanese Purplenimplemented a very complex, varying substitution ciphernused a series of cylinders, each giving one substitution, which rotated and changed after each letter was encryptednwith 3 cylinders have 263=17576 alphabets转轮机n转轮机密码系统（多层加密原理）n多筒系统中，操作员每按一次输入键，最后一个
50、转轮就旋转一个引脚的位置。n转轮机由一系列独立转动的圆柱体组成，每个圆柱体具有26个输入引脚和26个输出引脚，单个圆柱体定义了一个单字母替代。小结n1. 天书 6. One-Time Padn2. caesar 7. 置换密码n3. 仿射 8. 乘积密码n4. Playfair 9. Hill密码n5. Vigenre 10. 转轮机总结n 封闭性n 唯一性n 可逆性5. 信息隐藏Information Hidingn最大的优点也就是它最大的缺点。n信息隐藏又称信息伪装。n信息隐藏是一门古老的技术。n信息隐藏主要分为： 隐写术 数字水印 信息隐藏的特点：1. 不破坏载体的正常使用。2. 载体具