第七章信息加密技术

1、第七章第七章 信息加密技术信息加密技术 加密，就是对一般人都能看懂的消息，施加某种变换，变加密，就是对一般人都能看懂的消息，施加某种变换，变换后的这种信息称为密码。换后的这种信息称为密码。 4040年代末，香农使密码学置于坚实的数学基础上，有理论年代末，香农使密码学置于坚实的数学基础上，有理论支撑，有系统变换方法，成为系统科学学科。支撑，有系统变换方法，成为系统科学学科。 7070年代末，数据加密标准和公钥密码体制的问世，树立起年代末，数据加密标准和公钥密码体制的问世，树立起近代密码学的两大里程碑。数据加密标准近代密码学的两大里程碑。数据加密标准(DES)(DES)是针对计算机是针对计算机发展

2、中出现的数据保密问题而组织研究的非线性算法，主要用发展中出现的数据保密问题而组织研究的非线性算法，主要用于商用和非军事应用；公钥密码体制是将加、解密密钥甚至加、于商用和非军事应用；公钥密码体制是将加、解密密钥甚至加、解密函数分开，用户只保留解密密钥，而将加密密钥和加密函解密函数分开，用户只保留解密密钥，而将加密密钥和加密函数一起公之于众。数一起公之于众。7.1 概述概述一个一个密码体制密码体制是一个六元组：是一个六元组：（M, C, KM, C, K1, K, K2, E, D ), E, D )其中，其中，M M -明文空间明文空间C C -密文空间密文空间K K1 -加密密钥空间加密密钥空

3、间K K2 -解密密钥空间解密密钥空间E E - -加密变换空间加密变换空间D D - -解密变换空间解密变换空间基本概念：基本概念：密钥（密钥（key)是用于加解密变换的关键信息，是用于加解密变换的关键信息，由用户由用户(或或系统系统)事先选定的较短的秘密的字符或数字序列，事先选定的较短的秘密的字符或数字序列，视其视其用于加解密而分别称为加密密钥与解密密钥；用于加解密而分别称为加密密钥与解密密钥；7.2 7.2 密码通信的基本模型密码通信的基本模型 加密变换获得密文加密变换获得密文C C：C CE Ek k(P)(P) 明文明文P P从明文信息空间从明文信息空间S SP P变换到密文信息空间

4、变换到密文信息空间S SC C，E Ek k就是实现这种带有参数就是实现这种带有参数k k的加密变换函数，的加密变换函数，k k为密钥为密钥 加密变换Ek解密变换Dk破译分析发送者接收者C明文P密钥传送通道k 密钥窃听者( )kDcP( )kCEP 相反得解密相反得解密: : D Dk k(C)(C)P P E Ek k D Dk k 为单参数的可逆变换对为单参数的可逆变换对 系统保密性依赖于密钥系统保密性依赖于密钥 k k 如果合作接收方能区分如果合作接收方能区分C C和和CC，我们就说这类通信是安全的，我们就说这类通信是安全的加密变换解密变换密码分析发送者接收者CCPP( )D CP( )

5、kE PC7.3 7.3 对密码体制的基本要求对密码体制的基本要求 香农提出的五项准则：香农提出的五项准则： 1.1.所提供的保密强度所提供的保密强度 2.2.密钥的规模密钥的规模 3.3.加密和解密运算的简易性加密和解密运算的简易性 4.4.错误的扩散程度错误的扩散程度 5.5.信息的扩散程度信息的扩散程度 同余：同余：给定任意整数给定任意整数a和和q， a除以除以q，余数是，余数是r，则可以表示为，则可以表示为a=sq+r,0rq，其中，其中s=a/q,表示小于表示小于a/q的最大整数。定义的最大整数。定义r为为a mod q的剩余，记为的剩余，记为ra mod q.若整数若整数a和和b有

6、有(a mod q)=(b mod q)，则称，则称a与与b在在mod q下同余。下同余。对于满足对于满足r=a|a=sq+r,sZ的整数集称为同余类。的整数集称为同余类。模运算有下述性质：模运算有下述性质：（1）若）若q|(a-b)，则，则ab mod q（2）(a mod q)=(b mod q)意味意味ab mod q（3） ab mod q等价于等价于ba mod q（4）若）若ab mod q且且bc mod q ，则，则ac mod q模算术模算术:（Modular Arithmatic)在在mod q的的q个剩余类集个剩余类集0，1，2，,q-1上可以定义加上可以定义加法和乘法运

7、算如下法和乘法运算如下:加法加法: (a mod q)+ (b mod q)= (a+b) mod q乘法乘法:(a mod q) (b mod q)= (a b)mod q7.4 7.4 单表密码单表密码 所谓单表密码，是一种代换密码，就是把明文中的字母用另一个字母或符所谓单表密码，是一种代换密码，就是把明文中的字母用另一个字母或符号来代替，把可懂明文变成不可懂明文。号来代替，把可懂明文变成不可懂明文。密码种类：密码种类：单表密码单表密码加法（移位）密码、乘法密码、仿射密码、随机代换密码加法（移位）密码、乘法密码、仿射密码、随机代换密码密钥词组密码密钥词组密码 多表密码多表密码维吉尼亚（维吉

8、尼亚（Vigenere)密码密码 换位密码换位密码 倒序密码、栅栏密码、图形密码、列转置密码倒序密码、栅栏密码、图形密码、列转置密码 线性反馈移位寄存器密码线性反馈移位寄存器密码一一. .加法密码加法密码 最早使用实例是公元前最早使用实例是公元前100100年恺撒密码，如下表，正常顺序为明文字母年恺撒密码，如下表，正常顺序为明文字母( (小小写写) )，循环左移三个字母为密文字母，循环左移三个字母为密文字母( (大写大写) )，对明文消息加密，就是将明文中，对明文消息加密，就是将明文中的每个字母用它的下面相应的字母代换的每个字母用它的下面相应的字母代换明文字母序号123456789101112

9、13明文字母表abcdefghijklm密文字母表DEFGHIJKLMNOP明文字母序号12345678910111213明文字母表nopqrstuvwxyz密文字母表QRSTUVWXYZABC明文：明文：c r y p t o s y s t e m s密文：密文：F U B S W R V B V W H P V 如采用如采用1 12626代替代替a az z，则恺撒密码的加密变换的数学模型为：，则恺撒密码的加密变换的数学模型为： C P + 3 (mod 26)C P + 3 (mod 26) 同理，解密变换的数学模型为：同理，解密变换的数学模型为： P C P C 3 (mod 26)

10、3 (mod 26) 从上两式可知，可以把从上两式可知，可以把3 3看作式这种体制的密钥看作式这种体制的密钥 推广得推广得 C P + (mod 26)C P + (mod 26) P C - (mod 26) P C - (mod 26) 密钥就是密钥就是，26|26|时，明文和密文相同（恒等变换）时，明文和密文相同（恒等变换） 所以，加密密码要求所以，加密密码要求26 26 ，即，即不能是不能是2626的整数倍，最多只有的整数倍，最多只有2525种变化种变化| 例：明文例：明文 mathodmathod C C1 1 13 + 3 16 P 13 + 3 16 P C C2 2 1 + 3

11、 4 D 1 + 3 4 D C C3 3 20 + 3 23 W 20 + 3 23 W C C4 4 8 + 3 11 K 8 + 3 11 K C C5 5 15 + 3 18 R 15 + 3 18 R C C6 6 4 + 3 7 G 4 + 3 7 G 密文为：密文为：PDWKRGPDWKRG二二. .乘法密码乘法密码 乘法密码是对正常字母表的等间隔抽取获得，其加密变换的数学模型为：乘法密码是对正常字母表的等间隔抽取获得，其加密变换的数学模型为： C C P (mod 26)P (mod 26) 式中式中满足（满足（ ，2626）1 1，即，即必须是和必须是和2626互素的任意整数

12、即只有互素的任意整数即只有1 1，3 3，5 5，7 7，9 9，1111，1515，1717，1919，2121，2323，2525共共1212个数个数, ,除去除去1 1，乘法密码只有，乘法密码只有1111种种变化。变化。密钥就是密钥就是 其解密变换的数学模型为：其解密变换的数学模型为： P C P C (mod 26) (mod 26)下表为下表为3 3时的乘法密码表时的乘法密码表三三. .仿射密码仿射密码 仿射密码就是加法密码和乘法密码相结合，加密变换的数学模型为：仿射密码就是加法密码和乘法密码相结合，加密变换的数学模型为： C C P + (mod 26)P + (mod 26) 实

13、际上也是等间隔实际上也是等间隔抽取和移位抽取和移位的结合的结合 明 文 ： abcdefghijklm密 文 ： CFILORUXADGJM明 文 ： nopqrstuvwxyz密 文 ： PSVYBEHKNQTWZ当当1 1时，为加法密码；当时，为加法密码；当0 0时，为乘法密码时，为乘法密码 （1212）（）（2626）312312，除去恒等，共有，除去恒等，共有311311种变化种变化 其解密变化的数学模型为：其解密变化的数学模型为： P P （C C ） (mod 26) (mod 26) 下表为下表为3 3，4 4时的仿射密码表（时的仿射密码表（即先将正常字母表向左移即先将正常字母表

14、向左移4 4位，然后再位，然后再以以3 3的间隔进行抽取！的间隔进行抽取！）明 文 ： abcdefghijklm密 文 ： GJMPSVYBEHKNQ明 文 ： nopqrstuvwxyz密 文 ： TWZCFILORUXAD例：假设仿射密码参数是例：假设仿射密码参数是，1111，22，译解，译解VMWZVMWZ 解：先写出四个密文字母对应的数字符号解：先写出四个密文字母对应的数字符号 V V2222， M M1313， W W2323， Z Z2626 然后根据公式求解然后根据公式求解 C C P + (mod 26)P + (mod 26) P P （C C ） (mod 26) (mo

15、d 26) 或或 P P （C C +26K+26K） K K0,1,20,1,2 先求密文先求密文V V对应的明文对应的明文 P P （22 22 2 + 26K2 + 26K）1111 P P （22 22 2 + 262 + 266 6）11 16 p11 16 p 密文密文M M对应的明文对应的明文 P P （13 13 2 + 26K2 + 26K）1111 P P （13 13 2 + 262 + 260 0）11 1 a11 1 a 密文密文W W对应的明文对应的明文 P P （23 23 2 + 26K2 + 26K）1111 P P （23 23 2 + 262 + 263

16、3）11 9 i11 9 i 密文密文Z Z对应的明文对应的明文 P P （26 26 2 + 26K2 + 26K）1111 P P （26 26 2 + 262 + 265 5）11 14 n11 14 n 所以明文为所以明文为 pain pain四四. .随机代换密码随机代换密码 将代换字母由将代换字母由2626个字母随机抽取排列而成，总共有个字母随机抽取排列而成，总共有2626！不同种排列，！不同种排列，2626！ 4 410102626 保密性有所提高，但必须妥善保护密钥保密性有所提高，但必须妥善保护密钥五五. .密钥词组密码密钥词组密码 首先写出正常顺序的明文字母表，然后从特定字母

17、下开始写出密钥词组，但首先写出正常顺序的明文字母表，然后从特定字母下开始写出密钥词组，但要删除密钥词组中的重复字母，把未出现在密钥词组中的其它字母，依照字母要删除密钥词组中的重复字母，把未出现在密钥词组中的其它字母，依照字母顺序，依次填写顺序，依次填写 。 例如，选择例如，选择 monoal phabetic cipher monoal phabetic cipher 作为密钥词组，删去重复字母得到作为密钥词组，删去重复字母得到 monal phbeticrmonal phbeticr，选择字母，选择字母e e作为开始书写密钥词组的特定字母，有作为开始书写密钥词组的特定字母，有明 文 ： ab

18、cdefghijklm密 文 ：MONALPHBE明 文 ： nopqrstuvwxyz密 文 ： TICR 把未出现在密钥词组中的其他字母，依照字母顺序，依次填写在密钥词组之把未出现在密钥词组中的其他字母，依照字母顺序，依次填写在密钥词组之后，当在后，当在Z Z字母下面填写了字母后，再接着填到字母下面填写了字母后，再接着填到A A下面，最后完成包含密钥词组下面，最后完成包含密钥词组的代替字母表的代替字母表7.5 7.5 多表密码多表密码 它是利用了多个单表代替密码而构成的密码体制，最著名的是法国密码学家它是利用了多个单表代替密码而构成的密码体制，最著名的是法国密码学家提出的维吉利亚密码，基本

19、方阵提出的维吉利亚密码，基本方阵26262626 多表密码和单表密码相似，加密可以用同余方程表示多表密码和单表密码相似，加密可以用同余方程表示 C Ci P Pi + k + ki (mod 26) i (mod 26) i1 1，2 2， 第第i i个明文字母个明文字母P Pi加上密钥加上密钥k ki进行模进行模2626运算可得相应的第运算可得相应的第i i个密文字母个密文字母C Ci（注：（注：用用0 02525代替代替a az z）明 文 ： abcdefghijklm密 文 ： WXYZMONALPHBE明 文 ： nopqrstuvwxyz密 文 ： TICRDFGJKQSUV AB

20、CDEFGHIJKLMNOPQRSTUVWXYZBCDEFGHIJKLMNOPQRSTUVWXYZACDEFGHIJKLMNOPQRSTUVWXYZABDEFGHIJKLMNOPQRSTUVWXYZABCEFGHIJKLMNOPQRSTUVWXYZABCDFGHIJKLMNOPQRSTUVWXYZABCDEGHIJKLMNOPQRSTUVWXYZABCDEFHIJKLMNOPQRSTUVWXYZABCDEFGIJKLMNOPQRSTUVWXYZABCDEFGHJKLMNOPQRSTUVWXYZABCDEFGHIKLMNOPQRSTUVWXYZABCDEFGHIJLMNOPQRSTUVWXYZA

21、BCDEFGHIJKMNOPQRSTUVWXYZABCDEFGHIJKLNOPQRSTUVWXYZABCDEFGHIJKLMOPQRSTUVWXYZABCDEFGHIJKLMNPQRSTUVWXYZABCDEFGHIJKLMNOQRSTUVWXYZABCDEFGHIJKLMNOPRSTUVWXYZABCDEFGHIJKLMNOPQSTUVWXYZABCDEFGHIJKLMNOPQRTUVWXYZABCDEFGHIJKLMNOPQRSUVWXYZABCDEFGHIJKLMNOPQRSTVWXYZABCDEFGHIJKLMNOPQRSTUWXYZABCDEFGHIJKLMNOPQRSTUVXYZA

22、BCDEFGHIJKLMNOPQRSTUVWYZABCDEFGHIJKLMNOPQRSTUVWXZABCDEFGHIJKLMNOPQRSTUVWXYa 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密钥abcdefghijklmnopqrstuvwxyz例：设选用的密钥字为例：设选用的密钥字为 CipherCipher， 而要加密的消息为而要加密的消息为 Polyalphabetic cipherPolyalphabetic cipher 解密变换数学模型为：解密变换数学模型为： P Pi C Ci k ki (mod 26) i (mod

23、26) i1 1，2 2，密 钥 字 ： c i p h e r c i p h e r c i p h e r c i 明 文 ： p o l y a l p h a b e t i c c i p h e r 密 文 ： R W A F E C R P P I I K K K R P T Y G Z 7.6 7.6 换位密码（换位密码（又称为转置密码！又称为转置密码！）一一. .倒序密码倒序密码 如：如： 明文明文 transposition ciphertransposition cipher 密文密文 REHPI CNOIT ISOPS NARTREHPI CNOIT ISOPS NA

24、RT二二. .栅栏密码栅栏密码 将明文字母交替写在两行上，然后按行读出即得密文将明文字母交替写在两行上，然后按行读出即得密文 密文密文 TASOI INIHR RNPST OCPETASOI INIHR RNPST OCPE三三. .图形密码图形密码 密文密文 TONCI RATIP INSSH REOPTONCI RATIP INSSH REOPt a s o i i n i h rt a s o i i n i h rr n p s t o c p er n p s t o c p et r a n s pt r a n s po i t i s oo i t i s on c i p h

25、 en c i p h e r r四四. .列转置密码列转置密码 把明文消息逐行写到一个事先规定了宽度把明文消息逐行写到一个事先规定了宽度( (列数列数) )矩形内，再按列（从小的编号开始）矩形内，再按列（从小的编号开始）读出，即构成密文读出，即构成密文例如：明文例如：明文 Laser beams can be modulated to carry more Laser beams can be modulated to carry more intelligence than radio wave intelligence than radio wave 假设选取得密钥字为假设选取得密钥字为

26、 SORCERYSORCERY。它含有。它含有7 7个字母，即明文被书写到具有个字母，即明文被书写到具有7 7列的矩形内。列的矩形内。对这对这7 7个密钥字母按它们在字母表中出现得先后顺序依次编号，遇有相同字母，则从左个密钥字母按它们在字母表中出现得先后顺序依次编号，遇有相同字母，则从左至右依序编号至右依序编号, ,得得 S O R C E R YS O R C E R Y6 3 4 1 2 5 76 3 4 1 2 5 7l a s e r b el a s e r b ea m s c a n ba m s c a n be m o d u l ae m o d u l at e d t

27、o c at e d t o c ar r y m o r er r y m o r ei n t e l l i i n t e l l i g e n c e t hg e n c e t ha n r a d i oa n r a d i ow a v e sw a v e s 密文密文 ECDTM ECAER AUOOL EDSAM MERNE NASSO DYTNR VBNLCECDTM ECAER AUOOL EDSAM MERNE NASSO DYTNR VBNLC RLTIL AETRI GAWEB AAEIH O RLTIL AETRI GAWEB AAEIH O 密文共有密

28、文共有6161个字母，密钥字长度为个字母，密钥字长度为7 7。6161除以除以7 7，得商为，得商为8 8，余数为，余数为5 5，这就是，这就是说解密图形中有说解密图形中有7 7列，列，9 9行，但第行，但第9 9行只有前行只有前5 5列才有字母列才有字母SEVAWOIDARNAHTECNEGILLETNIEROMYRRACOTDETALUDOMEBNACSMAEBRESALS O R C E R YS O R C E R Y6 3 4 1 2 5 76 3 4 1 2 5 7rnrn1r1+tntn-1t1密钥序列7.7 7.7 线性反馈移位寄存器密码线性反馈移位寄存器密码 它是由一个它是由一个n n级移位寄存器级移位寄存器 R R( (rn，rn-1，r1) )和一个和一个“抽头抽头”序列序列 T T( (tn，tn-1，t1) )组成组成 令令 R(rn ，rn-1 ，r1 )表示寄存器表示寄存器 R R的下一状态的下一状态 因为因为 ri ri+1 rn TR (mod 2) (mod 2) t1r1 t2r2 tnrn 所以所以 R HR (mod 2) 式中式中H H为为n nn n矩阵，第一行为抽头序列矩阵，第一行为抽头序列T T( (t tn，t tn-1，t t1) )，主对角线