密码学基础知识课件.ppt

《密码学基础知识课件.ppt》由会员分享，可在线阅读，更多相关《密码学基础知识课件.ppt（149页珍藏版）》请在三一办公上搜索。

1、,夫学须静也，才须学也，非学无以广才，非志无以成学。诸葛亮,概述,密码学 密码编码学 密码分析学,作用：机密性 鉴别 完整性 抗抵赖,密码学文献的发展历程：1918年，Friedman重合指数及其在密码学中的应用。1918年，Heberm的转轮机1949年，Shannon保密系统的通信理论1967年，Kahn破译者1971年，Feistel的Lucifer,1975年，Diffie&Hellman提出公开密钥密码学，密码学的新方向1977年，DES成为联邦信息处理标准1978年，MIT的RSA算法。1985年，ElGamal体制（离散对数）；Koblitz&Miller 提出椭圆曲线密码学 1

2、995年，Hoffstein，Pipher，Siverman发明NTRU密码,密码学之前，信息安全的保护主要是通过物理和行政手段实现的。密码学最早多用于外交情报和军事领域。现代密码学家通常是理论数学家。,第一阶段：手工计算第二阶段：机械和电动机械第三阶段：电子和计算机,内容,1.保密与保密系统2.古典密码技术3.密码体制4.密码分析5.加密方式,一、保密与保密系统,保密学：研究信息系统安全保密的科学。,1.保密系统模型图,一个密码体制由五元组（P，C，K，E，D）构成。,Symmetric Cipher Model,Basic Terminology,plaintext-the origina

3、l message ciphertext-the coded message cipher-algorithm for transforming plaintext to ciphertext key-info used in cipher known only to sender/receiver encipher(encrypt)-converting plaintext to ciphertext decipher(decrypt)-recovering ciphertext from plaintextcryptography-study of encryption principle

4、s/methodscryptanalysis(codebreaking)-the study of principles/methods of deciphering ciphertext without knowing keycryptology-the field of both cryptography and cryptanalysis,2.密码设计准则,保密系统抗击密码分析，应满足：1）系统即使达不到理论上是不可破的，也应当为实际上是不可破的。2）Kerckhoff原则。系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。3）加密和解密算法适用于所有密钥空间中的元素。4）系统便

5、于实现和使用方便。,Kerckhoff六项准则,在19世纪对军事密码体制提出六项准则：密码体制即便不是在理论上不可破，也应该是实际上不可破的。体制的泄露不应该给通信者带来麻烦。,3.保密系统的通信理论,明文密码系统的熵惟一解距离UD,Plaintext明文,Entropy:一条信息的信息量通过熵来度量。是对信息或不确定性的数学度量，通过概率分布的函数来计算。语言信息率：r=H(M)/N N相当大时，标准英语的语言信息率在1.0-1.5/字母之间。语言绝对信息率：假定每一个字符串是等可能的，对每个字母编码的最大位数。,英文 R=logL=log26=4.7位/字母Thomas Cover采用随机

6、估算技术得到的信息率为1.3位/字符。自然语言具有高冗余度。D=R-r=3.4位/字母。英语语言是75%冗余。Huffman一条ASCII消息，每字节消息含有与英语相等的1.3位的消息，她的冗余信息为6.7位，相当于每位ASCII文本有0.84位冗余,自然语言的高冗余度为密码分析提供了一个重要工具。它最重要也是最基本的特征：单个字母出现的频率。,密码系统的熵,由密钥空间大小来衡量 H(K)=log K一般来说，熵越大，破译它越困难。密钥：尽量使密钥源为无记忆均匀分布源。,密文的统计特征由明文和密钥的统计特征完全决定。收到的密文越长，分析者找到密钥或明文的可能性越大，为确信分析者可找到唯一的密钥

7、，理论上S至少将要多长。,惟一解距离UD,在给定足够的计算时间下，分析者能唯一计算出密钥所需密文的平均值。惟一解距离Unicity Distance码量：使一个具有无限计算能力的攻击者能够恢复惟一的加密密钥所需要的最小密文量（字符数）。在达到惟一解距离时，密钥暧昧度趋近于零。临界值 S=H(K)/log e-H(m)称为UD。,UD,定义为使得伪密钥的期望值等于零的n的值。当密文字符大于UD时，这种密码就存在一个解，而当密文字符小于UD时，就会出现多个可能的解。它利用信息论描述了被截获的密文量和成功攻击的可能性之间的关系。,UD,Shannon指出：惟一解距离可以保证当其太小时，密码系统是不安

8、全的，但并不保证当其较大时，密码系统就是安全的。惟一解距离不是对密码分析需要多少密文的度量，而是对存在唯一合理的密码分析所需密文数量的指标。惟一解距离与冗余度成反比，当冗余度接近于零时，一个普通的密码系统也可能是不可破的。,UD,一般而言，惟一解距离越长，密码系统越好。无穷大时为理想保密。,密码分析,利用自然语言的冗余度来减少可能的明文数目。语言的冗余度越大，它就越容易被攻击。最重要也是最基本的特征：单个字母出现的频率。一个好的加密算法是一种混合变换，它将有意义的小区域中的有意义的消息相当均匀地分布到在整个消息空间中。,4.密码系统的安全性,是密码学研究的一个重要课题有两种定义“安全性”的方法

9、：基于信息论的方法（经典方法）基于计算复杂性理论的方法（现代方法）,基于信息论的方法：用密文中是否蕴含明文的信息作为标准。基于计算复杂性理论的方法：是考虑信息是否能有效地被提取出来。,现代密码学的基础,传统的密码学和公钥密码学的基础是信息论和计算复杂性理论 信息理论密码学 计算复杂性理论密码学,信息论告诉我们，所有的密码算法（OTP除外）都能被破译。复杂性理论告诉我们，何时能被破译。,信息理论密码学,Shannon用不确定性和惟一解距离度量了密码系统（体制）的安全性。,密码系统的安全性：,理论保密：完全保密 理想保密实际保密：计算安全（可证明安全性）,理论安全,经典方法无条件安全性基于信息论的

10、密码学信息理论密码学：用信息论的观点和方法研究密码系统模型的建立、密码的安全性及破译等，它所研究的安全性准则，假定密码分析者的计算资源，不受限制,完全保密,理论上不可破译的密码体制。必要条件：明文数、密钥数和密文数都相等的密码体制，将每个明文变换成每个密文都恰好有一个密钥，所有的密钥都是等可能的。Shannon从理论上证明：仅当可能的密钥数目至少与可能的消息数目一样多时，完全保密才是有可能的。,完全保密,仅有一次一密（OTP）乱码本的密码系统可获得完全保密。One-Time Pad在要求无条件安全的军事和外交环境中有着很重要的作用。,完全保密：（完善的或无条件的保密系统）给定密文y，明文为x的

11、后验概率等于明文x的先验概率,理想保密,理论上不可译的，它的惟一解距离UD趋向于无穷大的密码体制。意味着语言的多余度趋向于零。当然消除语言中的全部多余度事实上不可能。它是不实用的，但它揭示我们设计密码体制（算法）时，应尽量缩小多余度。明文信息加密前先进行信源编码。,一个完全保密的密码系统必须是一个理想保密的密码系统，但是一个理想保密的密码系统不一定是一个完全保密的密码系统。,实际安全,现代方法有条件安全性基于复杂性理论的密码学复杂性理论密码学：用复杂性理论的观点和方法研究密码系统模型的建立、密码的安全性分析及破译等。假定密码分析者的计算资源是有限的，受到限制,实际安全,实际安全性又称为计算上的

12、安全性。计算安全性：涉及攻破密码体制所做的计算上的努力。可证明安全性：安全性归结为某个经过深入研究的数学难题。,实际安全性,主要考虑：计算能力（基本运算次数、存储量）破译算法的有效性算法：求解某一问题的、一步一步地执行的计算过程。,计算复杂性,问题的计算复杂性 可解问题的最有效算法的计算复杂性算法的计算复杂性 运行它所需的计算能力。常常用两个变量来度量：时间复杂性T和空间复杂性S（或所需存储空间）,“计算上安全”：指利用已有的最好的方法破译该系统所需要的努力超过了敌手的破译能力（时间、空间、资金等）或破译该系统的难度等价于解数学上的某个已知难题（计算复杂性）。,计算复杂性,计算复杂性理论是密码

13、系统安全性定义的理论基础。算法：函数 1（常数）、对数、n（线性函数）、二次函数、三次函数、多项式函数、亚指数、指数函数问题：P、NP、NPC,时间复杂性,一个算法的计算复杂性或有效性可以用执行该算法所需的运行时间和内存空间来度量。时间复杂性有两种定义方法：1。用图灵机表示一个算法 2。该算法的比特运算次数,计算上保密：理论上可破，实际上难破，而不是不可破。,密码体制安全性准则,计算安全性：可证明安全性：无条件安全性：,5.密码编码系统分类：,密码编码系统分类：明文转换为密文操作的类型 替代 置换 密钥数量 单钥 双钥 明文处理方式 分组密码 序列密码,Cryptography,can cha

14、racterize by:type of encryption operations usedsubstitution/transposition/productnumber of keys usedsingle-key or private/two-key or publicway in which plaintext is processedblock/stream,“Purple”紫码,1941.12.7日本偷袭珍珠港1942.1美成功破译JN-251942.4美轰炸日东京、神户等1942.5.7-8巴布亚新几内亚的莫尔兹比港Port Moresby（印尼）1942中途岛之战 4.18“

15、山本五十六”飞机降落时被击落,二、古典密码技术,1.代替密码：单表代替密码、Playfair、Hill、Vigenere、OTP2.置换密码：3.乘积密码：4.转轮机5.隐写术,1.Substitution Ciphers,where letters of plaintext are replaced by other letters or by numbers or symbolsor if plaintext is viewed as a sequence of bits,then substitution involves replacing plaintext bit patterns

16、 with ciphertext bit patterns,代替密码,单表代替密码多名码代替密码多字母代替密码多表代替密码,1）单表代替密码,单表代替密码 例如“凯撒”密码 古罗马军队用 由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 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 Cipher,earliest known substitution cipherby Julius Caesar first attest

17、ed use in military affairsreplaces each letter by 3rd letter onexample:meet me after the toga partyPHHW PH DIWHU WKH WRJD SDUWB,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 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 le

18、tter 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 cipher as:C=E(p)=(p+k)mod(26)p=D(C)=(C k)mod(26),Cryptanalysis of Caesar Cipher,only have 26 possible ciphers A maps to A,B,.Z could simply try each in tu

19、rn a brute force search given ciphertext,just try all shifts of lettersdo need to recognize when have plaintexteg.break ciphertext GCUA VQ DTGCM,Monoalphabetic单表代替 Cipher,rather than just shifting the alphabet could shuffle(jumble)the letters arbitrarily each plaintext letter maps to a different ran

20、dom ciphertext letter hence key is 26 letters long Plain:abcdefghijklmnopqrstuvwxyz Cipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA,Monoalphabetic Cipher Security,now have a total of 26!=4 x 1026 keys with so many keys,might think is secure but

21、would be!WRONG!problem is language characteristics单表代替密码不能掩盖明文语言的所有统计特性。,Language Redundancy and Cryptanalysis,human languages are redundant eg th lrd s m shphrd shll nt wnt letters are not equally commonly used in English e is by far the most common letter then T,R,N,I,O,A,S other letters are fairl

22、y rare cf.Z,J,K,Q,X have tables of single,double&triple letter frequencies,English Letter Frequencies,Use in Cryptanalysis,key concept-monoalphabetic substitution ciphers do not change relative letter frequencies discovered by Arabian scientists in 9th centurycalculate letter frequencies for ciphert

23、extcompare counts/plots against known values if Caesar 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 help,安全性,取决于密文在多大程度上保留了明文语言的语法模式和结构。理想的字母频率分布情况：如果频率分配的信息完全给加密过程给隐藏了

24、，那么密文的频率曲线应该是一条水平的线。减少密文中残留明文语言结构的基本方法：1）对明文中的多个字母一起加密 2）采用多表代替密码,Example Cryptanalysis,given ciphertext:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQcount relative letter frequencies(see text)guess P&Z are e and tguess ZW is

25、 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 politicalrepresentatives of the vietcong in moscow,单表代替密码 移位代替密码E(i)=i+k=j mod q 乘数密码E(i)=ik=j mod q k与q互素 线性同余密码(仿射密码Affine Cipher)E(i)=ik1+k0=

26、j mod q k1与q互素多表代替密码,2）Playfair Cipher,not even the large number of keys in a monoalphabetic cipher provides security one approach to improving security was to encrypt multiple letters the Playfair Cipher is an example invented by Charles Wheatstone in 1854,but named after his friend Baron Playfair,

27、应用：第一次世界大战中英军就使用它作为陆军的标准加密体制，在第二次世界大战中，美军极其他一些盟军用它来进行加密。,Playfair Key Matrix,a 5X5 matrix of letters based on a keyword fill in letters of keyword(sans duplicates)fill rest of matrix with other letterseg.using the keyword MONARCHYMONARCHYBDEFGIKLPQSTUVWXZ,Encrypting and Decrypting,plaintext encrypte

28、d two letters at a time: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

29、 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),Security of the Playfair Cipher,security much improved over monoalphabe

30、ticsince have 26 x 26=676 digrams would need a 676 entry frequency table to analyse(verses 26 for a monoalphabetic)and correspondingly more ciphertext was widely used for many years(eg.US&British military in WW1)it can be broken,given a few hundred letters since still has much of plaintext structure

31、,Polyalphabetic Ciphers,another approach to improving security is to use multiple cipher alphabets called polyalphabetic substitution ciphers 多表代替密码makes cryptanalysis harder with more alphabets to guess and flatter frequency distribution use a key to select which alphabet is used for each letter of

32、 the message use each alphabet in turn repeat from start after end of key is reached,3.Hill 代数法,利用线性变换的方法，但在Z26上进行。代数法（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 x

33、4 y3=5x1+8x2+4x3+9x4 y4=10 x1+6x2+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,Hill的优点：完全隐蔽了单字母频率特性。Hill的矩阵越大，所隐蔽的频率信息越多。Hill密码既不是一种纯换位密码，也不是一种纯代替密码。大多数“现代”密码算法都是将换位密码

34、和代替密码算法有机的结合。Hill密码算法具有线性的缺点。,应用,Hill密码由数学家Lester S Hill 1929年研制。在第二次世界大战中，该密码被用来对无线电呼叫信号进行加密，加密和解密均通过机械设备（而非电子设备）来完成。较易被已知明文破解。,4）Vigenre Cipher,simplest polyalphabetic substitution cipher is the Vigenre Cipher 最简单、最著名effectively multiple caesar ciphers key is multiple letters long K=k1 k2.Kd ith l

35、etter specifies ith alphabet to use use each alphabet in turn repeat from start after d letters in messagedecryption simply works in reverse,代换规则集由26个类似Caesar密码的代换表组成。依赖于密钥词的长度,Example,write the plaintext out write the keyword repeated above ituse each key letter as a caesar cipher key encrypt the c

36、orresponding plaintext lettereg using keyword deceptivekey:deceptivedeceptivedeceptiveplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ,Aids,simple aids can assist with en/decryption a Saint-Cyr Slide is a simple manual aid a slide with repeated alphabet line up plaintext A

37、 with key letter,eg C then read off any mapping for key letter can bend round into a cipher disk or expand into a Vigenre Tableau(see text Table 2.3),Security of Vigenre Ciphers,have multiple ciphertext letters for each plaintext letterhence letter frequencies are obscuredbut not totally loststart w

38、ith letter frequenciessee if look monoalphabetic or notif not,then need to determine number of alphabets,since then can attach each,Kasiski Method,method developed by Babbage/Kasiski repetitions in ciphertext give clues to period so find same plaintext an exact period apart which results in the same

39、 ciphertext of course,could also be random flukeeg repeated“VTW”in previous examplesuggests size of 3 or 9then attack each monoalphabetic cipher individually using same techniques as before,Autokey Cipher,ideally want a key as long as the messageVigenre proposed the autokey cipher with keyword is pr

40、efixed to message as keyknowing keyword can recover the first few letters use these in turn on the rest of the messagebut still have frequency characteristics to attack eg.given key deceptivekey:deceptivewearediscoveredsavplaintext:wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA,5）

41、One-Time Pad(一次一密),if a truly random key as long as the message is used,the cipher will be secure called a One-Time padis unbreakable since ciphertext bears no statistical relationship to the plaintextsince for any plaintext&any ciphertext there exists a key mapping one to othercan only use the key

42、once thoughhave problem of safe distribution of key,一次一密,陆军情报官Mauborgne建议使用与消息一样长且无重复的随机密钥来加密消息一次一密的安全性完全取决于密钥的随机性存在两个难点：产生大规模随机密钥 密钥的分配和保护主要应用于安全性要求很高的低带宽信道。,2.Transposition Ciphers,置换密码now consider classical transposition or permutation ciphers these hide the message by rearranging the letter orde

43、r without altering the actual letters usedcan recognise these since have the same frequency distribution as the original text,移位密码 古希腊的“天书”器械，公元前400年希腊人采用。斯巴达克人塞塔发明的。加密方法 密钥,Row Transposition Ciphers,a more complex scheme栅栏技术write letters of message out in rows over a specified number of columnsthen

44、 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,代替密码Substitution：明文字母被不同的密文字母所代替。置换密码Transposition：Permutation保持明文的所有字母不变，只是利用置换打乱了明文字母的位置和次序。,3.Product Cip

45、hers,ciphers using substitutions or transpositions are not secure because of language characteristicshence consider using several ciphers in succession to make harder,but:two substitutions make a more complex substitution two transpositions make more complex transposition but a substitution followed

46、 by a transposition makes a new much harder cipher this is bridge from classical to modern ciphers,乘积密码：以德军第一次世界大战中所使用的密码为例：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 Y 3 A N DG XF FG VG GA AG XGV 8 O D H 0 2X U 4 I S

47、 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 Machines,before modern ciphers,rotor machines were most common product cipherwere widely used in WW2German Enigma,Allied Hagelin,Japanese Purpleimplemented a

48、 very complex,varying substitution cipherused a series of cylinders,each giving one substitution,which rotated and changed after each letter was encryptedwith 3 cylinders have 263=17576 alphabets,转轮机,转轮机密码系统（多层加密原理）多筒系统中，操作员每按一次输入键，最后一个转轮就旋转一个引脚的位置。转轮机由一系列独立转动的圆柱体组成，每个圆柱体具有26个输入引脚和26个输出引脚，单个圆柱体定义了一个

49、单字母替代。,小结,1.天书 6.One-Time Pad2.caesar 7.置换密码3.仿射 8.乘积密码4.Playfair 9.Hill密码5.Vigenre 10.转轮机,总结,封闭性 唯一性 可逆性,5.信息隐藏Information Hiding,最大的优点也就是它最大的缺点。信息隐藏又称信息伪装。信息隐藏是一门古老的技术。信息隐藏主要分为：隐写术 数字水印,信息隐藏的特点：1.不破坏载体的正常使用。2.载体具有某种冗余性3.隐形性：4.稳健性：信号处理变换5.通用性：图象、视频、音频6.确定性：唯一的鉴别确定,Steganography（隐写术）,an alternative

50、to encryptionhides existence of messageusing only a subset of letters/words in a longer message marked in some wayusing invisible inkhiding in LSB in graphic image or sound filehas drawbackshigh overhead to hide relatively few info bits,藏头诗不可见墨水优点：可以应用于通信双方宁愿他们的秘密信息被发现而不愿其中的重要内容丢失的情况。缺点：它需要大量额外的开销来隐