数学实验试验14密码.ppt

1、实验十四: 密码 (Cryptogram, Cypher),密码学(Cryptology)是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学(Cryptography)；应用于破译密码以获取通信情报的，称为破译学(Cryptanalysis) ，总称密码学。,密码学的演变历史,1918, William Friedmans The Index of Coincidence and its Applications in Cryptography Edward Hebern, Rotor Machine for 50 Years. 1949,

2、Claude Shannons The Communication Theory of Secrecy System, 成为理论基础 1949-1967，Cryptographic Literature was barren 1971, IBM: Luciffer Cipher, 128位密钥作分组加密 by team led by Horst Feistel used 64-bit data blocks with 128-bit key,1975, Diffie-Hellman, A New Direction in Cryptography, 首次提出适应网络保密通信的公开密钥思想，揭开

3、现代密码学研究的序幕，具有划时代的意义 1976-1977，美国国家标准局正式公布实施DES，Data Encryption Standard 19771978，Rivest, Shamir, Adelman 第一次提出公开密钥密码系统的实现方法RSA 1981，成立International Association for Cryptology Research,1985，ElGamal 提出概率密码系统 ElGamal方法 19901992，Lai Xuejia and James: IDEA, The International Data Encryption Algorithm 200

4、0, AES, Advanced Encryption Standard,密码学基本术语 Terminologies,Cryptology(保密学)，源自希腊语(Greek) Krypts: hidden; logos: word, 是密码学和密码处理过程的研究。 Cryptography: The Science and Study of Secret Writing，密码编码学 Cryptanalysis: The Science and Study of Secret Breaking，密码破译学 Cipher: A secret method of writing 加密方法,Encip

5、her (encipherment), encryption: 将明文转换成密文的过程 Decipher (decipherment), decryption: 将密文还原成明文的过程 Plaintext (cleartext): 原始的可读数据，明文 Ciphertext (Cryptogram): 加密后的不可解读之文件，密文 Key: 密钥，对加密与解密过程进行控制的参数 E(m): Encryption Transformation 加密变换 D(c): Decryption Transformation 解密变换,14.1 单表密码(Monoalphabetic Cipher ):

6、按照秘密的替换方案, 将明文中的每个字母换成指定字母. Each plaintext letter maps to a different random ciphertext letter Hence key is 26 letters long Plain: abcdefghijklmnopqrstuvwxyz Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplaceletters Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA,Now have a total of 26! = 4 x 1026

7、 keys more than 400,000,000,000,000,000,000,000,000 4x1026 = 400万亿亿 With so many keys, might think is secure But would be !WRONG! Problem is language characteristics Human languages are redundant E.g. th lrd s m shphrd shll nt wnt,Letters are not equally commonly used In English e is by far the most

8、 common letter, then T, R, N, I, O, A, S Other letters are fairly rare c.f.(比较) 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 f

9、requencies 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 at: JK, X-Z For monoalphabetic must identify each letter

10、 tables of common double/triple letters help,Example Cryptanalysis,Given ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ Count relative letter frequencies (see text) Guess P & Z are e and t Guess ZW is th and henc

11、e 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,14.2 多表密码(Polyalphabetic Ciphers),几张替换表轮流使用. 破译轮换周期 p: 将密文向后移动 k 位之后与原来比较,统计重码率v. kp时v约为0.038，k=p时约0.

12、065,Vigenre Cipher,Simplest polyalphabetic substitution cipher is the Vigenre Cipher, which is effectively multiple caesar ciphers Key is multiple letters long K = k1 k2 . kd ith letter specifies ith alphabet to use Use each alphabet in turn Repeat from start after d letters in message Decryption si

13、mply works in reverse,Example,Write the plaintext out Write the keyword repeated above it Use each key letter as a caesar cipher key Encrypt the corresponding plaintext letter e.g. using keyword deceptive key: deceptivedeceptivedeceptive plaintext: wearediscoveredsaveyourself ciphertext: ZICVTWQNGRZ

14、GVTWAVZHCQYGLMGJ,14. 序列密码(sequence cipher),移位寄存器序列(shift register sequence) ： s k+n = f(s k, s k+1,s k+n-1). 周期 p 不超过 2n . M序列和m序列 本原多项式 若一个n次多项式满足如下条件： （1）f(x)是既约的 （2）f(x)可整除xm+1，m=2n-1 （3）f(x)除不尽xq，qm 则称为本原多项式。 由本原多项式产生的序列一定是m序列。,随机性检验 频数检验：在m序列的一个周期中，“0”“1”的数目基本相等； 序列检验：序列中相邻两项组成的元素组，四种可能应当各出现1/4

15、； 扑克检验：序列中相邻5项组成的元素组，25种可能应出现的频率大体相等； 自相关检验：对每个自然数p,序列中ai=ai+p的频率k(p)应当与p无关； 游程检验：长度为1的游程占总游程数的一半；长度为2的游程占总游程的1/4，长度为k的游程占总游程数的1/2k,14.4 RSA公钥体制,1977年，美国的里维斯特(Ronald Rivest)、沙米尔(Adi Shamir)和阿德勒曼(Len Adleman)提出第一个较完善的公钥密码体制RSA体制，这是一种建立在大数因子分解基础上的算法。,秘密:大素数p,q,解密密钥d 公开：n(=pq),加密密钥h. 加密：密文x（整数n）, xh 除以

16、n求余数得明文y. 解密: yd除以n求余数得x.,解密密钥d的求法：,hd 除以 (p-1)(q-1) 余1 保密性：不易由大数n分解求出p,q. 从而求不出d. 实验：加密和解密练习,1985年，英国牛津大学物理学家戴维多伊奇(David Deutsch)提出量子计算机的初步设想，这种计算机一旦造出来，可在30秒钟内完成传统计算机要花上100亿年才能完成的大数因子分解，从而破解RSA运用这个大数产生公钥来加密的信息。同一年，美国的贝内特(Bennet)根据他关于量子密码术的协议，在实验室第一次实现了量子密码加密信息的通信。尽管通信距离只有30厘米，但它证明了量子密码术的实用性。 与一次性便笺密