用了更优秀复杂的加密手段，同时也拥有更高的加密解密效率。其中最具有代表性的就是图 2-2所示的ENIGMA密码机。 图2-2 ENIGMA密码机 ENIGMA密码机是德国在1919年发明的一种加密电子器，它表面看上去就像常用打字 机，但功能却与打印机有着天壤之别。键盘与电流驱动的转子相连，可以多次改变每次敲击 的数字。相应信息以摩斯密码输出，同时还需要密钥，而密钥每天都会修改。ENIGMA密 码机被证明是有史以来最可靠的加密系统之一，二战期间它开始被德军大量用于铁路、企业 当中，令德军保密通信技术处于领先地位。 这个时期的密码技术，虽然加密设备有了很大的进步，但是密码学的理论却没有多大的 改变，加密的主要手段仍是一一替代和换位，而且实现信息加密的过程过于简单，安全性能 很差。伴随着高性能计算机的出现，古典密码体制逐渐退出了历史舞台。 第二阶段为从1949年到1975年。密码学正式作为一门科学的理论基础应该首推1949 年美国科学家Shannon的一篇文章Communication Theory of Secrecy Systems,Shannon在 研究保密机的基础上，提出将密码建立在解某个己知数学难题的观点，为近代密码学的研究 奠定了理论基础。这一时期有关密码学研究的科技文献难得一见，因为在这一时期，密码学 的研究成果几乎专门服务于军事领域，大量的资源被用来研究如何进行信息保密和破译对方 的保密技术，但是大量研究成果不能公开，导致公开的研究文献近乎空白。 第三阶段为从1976年至今。这一时期，伴随着高性能计算机的出现，使得密码算法进 行高度复杂的运算成为可能。20世纪70年代，以公钥密码体制（非对称密码体制：Asymmetric Cryptography System)的提出和数据加密标准DES的问世为标志，密码学才在真正意义上 取得了重大突破，进入近代密码学阶段。其中，1976年Di伍ie和Hellman发表了研究论文 New Directions in Cryptography,导致了密码学上的一场革命，在这篇论文中，Diie和 Hellman首先证明了在发送端和接受端无密钥传输的保密通讯是可能的，从而开创了公钥密 码学的新纪元。现代密码学改变了古典密码学单一的加密手法，融入了大量的数论、几何、 代数等丰富知识，使密码学得到更蓬勃的发展。 直到现在，世界各国仍然对密码的研究高度重视，密码技术已经发展到了现代密码学时 期。密码学已经成为结合物理、量子力学、电子学、语言学等多个专业的综合科学，出现了 如“量子密码”、“混沌密码”等先进理论随着计算机技术和网络技术的发展，互联网的普 19
19 用了更优秀复杂的加密手段，同时也拥有更高的加密解密效率。其中最具有代表性的就是图 2-2 所示的 ENIGMA 密码机。 图 2-2 ENIGMA 密码机 ENIGMA 密码机是德国在 1919 年发明的一种加密电子器，它表面看上去就像常用打字 机，但功能却与打印机有着天壤之别。键盘与电流驱动的转子相连，可以多次改变每次敲击 的数字。相应信息以摩斯密码输出，同时还需要密钥，而密钥每天都会修改。ENIGMA 密 码机被证明是有史以来最可靠的加密系统之一，二战期间它开始被德军大量用于铁路、企业 当中，令德军保密通信技术处于领先地位。 这个时期的密码技术，虽然加密设备有了很大的进步，但是密码学的理论却没有多大的 改变，加密的主要手段仍是――替代和换位，而且实现信息加密的过程过于简单，安全性能 很差。伴随着高性能计算机的出现，古典密码体制逐渐退出了历史舞台。 第二阶段为从 1949 年到 1975 年。密码学正式作为一门科学的理论基础应该首推 1949 年美国科学家 Shannon 的一篇文章 Communication Theory of Secrecy Systems，Shannon 在 研究保密机的基础上，提出将密码建立在解某个已知数学难题的观点，为近代密码学的研究 奠定了理论基础。这一时期有关密码学研究的科技文献难得一见，因为在这一时期，密码学 的研究成果几乎专门服务于军事领域，大量的资源被用来研究如何进行信息保密和破译对方 的保密技术，但是大量研究成果不能公开，导致公开的研究文献近乎空白。 第三阶段为从 1976 年至今。这一时期，伴随着高性能计算机的出现，使得密码算法进 行高度复杂的运算成为可能。20 世纪 70 年代，以公钥密码体制（非对称密码体制：Asymmetric Cryptography System）的提出和数据加密标准 DES 的问世为标志，密码学才在真正意义上 取得了重大突破，进入近代密码学阶段。其中，1976 年 Diffie 和 Hellman 发表了研究论文 New Directions in Cryptography，导致了密码学上的一场革命，在这篇论文中，Diffie 和 Hellman 首先证明了在发送端和接受端无密钥传输的保密通讯是可能的，从而开创了公钥密 码学的新纪元。现代密码学改变了古典密码学单一的加密手法，融入了大量的数论、几何、 代数等丰富知识，使密码学得到更蓬勃的发展。 直到现在，世界各国仍然对密码的研究高度重视，密码技术已经发展到了现代密码学时 期。密码学已经成为结合物理、量子力学、电子学、语言学等多个专业的综合科学，出现了 如“量子密码”、“混沌密码”等先进理论.随着计算机技术和网络技术的发展，互联网的普
及和网上业务的大量开展，使得人们更加关注密码学，更加依赖密码技术。密码技术在信息 安全中起着十分重要的角色。 2.2基本概念 2.2.1数学基础知识 在介绍密码算法之前，我们先来介绍一些需要用到的数学知识。 (1)带余除法 对于任意的两个正整数a和b，,一定可以找到惟一确定的两个整数k和r,满足 a=b+r且0≤r<b,分别称k和r为a除以b(或者b除a)的商和余数，并称满足这种 规则的运算为带余除法。显然，在带余除法中k=a/b」，其中x表示不大于x的最大整 数，或者称为x的下整数。 若记a除以b的余数为amod b,则带余除法可表示成 a=a/bb+amodb 【例2.1】若a=17,b=5,则a=3b+2,即k=17/5=3,r=17mod5=2。 对于整数a<0,也可以类似地定义带余除法和它的余数，例如：-17mod5=3。 (2)整数同余与模运算 设a,b,n∈Z且n>0,如果a和b除以n的余数相等，即amodn=bmodn,则称a与b 模n同余，并将这种关系记为a=bmodn,n称为模数，amodn相应地也可以被称为a模n 的余数。 【例2.2】17=2mod5,73=27mod23。 显然，如果a与b模n同余，则必然有n(a-b),也可以写成a-b=k或a=k1+b, 其中k∈Z。 由带余除法的定义可知，任何整数a除以正整数n的余数一定在集合{0,1,2，·，n-1中， 结合整数同余的概念，所有整数根据模n同余关系可以分成n个集合，每一个集合中的整数 模n同余，并将这样的集合称为模n同余类或剩余类，且可依次记为 [0ln[ln[2]n,.[n-lln,即[xn={y川VEZAy=xmodn),x∈{01,2，.，n-l}。如果从每 一个模n同余类中取一个数为代表，形成一个集合，此集合称为模n的完全剩余系，以Zn表 示。显然，Zn的最简单表示就是集合{0,1,2，.，-1}，这也是最常用的表示，即 Zn={0,1,2,.,n-1}。 综上可知，amodn将任一整数a映射到Zn={0,1,2,.,n-中惟一的数，这个数就是a 模n的余数，所以可将amodn视作一种运算，并称其为模运算。 模运算具有如下的性质（其中n>1): 如果(a-b),则a=bmodn。 模同余关系是整数间的一种等价关系，它具有等价关系的三个基本性质，即 20
20 及和网上业务的大量开展，使得人们更加关注密码学，更加依赖密码技术。密码技术在信息 安全中起着十分重要的角色。 2.2 基本概念 2.2.1 数学基础知识 在介绍密码算法之前，我们先来介绍一些需要用到的数学知识。 （1）带余除法 对于任意的两个正整数 a 和 b ，一定可以找到惟一确定的两个整数 k 和 r ，满足 a kb r = + 且0 £ <r b ，分别称k 和r 为 a 除以b（或者b 除a ）的商和余数，并称满足这种 规则的运算为带余除法。显然，在带余除法中 k a b = ê ú / ë û ，其中 ê ú xë û 表示不大于 x 的最大整 数，或者称为 x的下整数。 若记a 除以b 的余数为a b mod ，则带余除法可表示成 a a b b a b = + ê ú / mod ë û 【例 2.1】若a =17，b = 5 ，则a b = + 3 2 ，即k = = ê ú 17 / 5 3 ë û ，r = = 17mod5 2 。 对于整数a < 0 ，也可以类似地定义带余除法和它的余数，例如：- = 17mod5 3 。 （2）整数同余与模运算 设 a b n , , ÎZn且n > 0 ，如果a 和b 除以n的余数相等，即a n b n mod mod = ，则称a 与b 模 n同余，并将这种关系记为 a b n º mod ，n称为模数，a n mod 相应地也可以被称为a 模 n 的余数。 【例 2.2】17 2mod5 º ，73 27mod 23 º 。 显然，如果 a 与b 模 n 同余，则必然有 n a b ( ) - ，也可以写成 a b kn - = 或 a kn b = + ， 其中k ÎZ 。 由带余除法的定义可知，任何整数a 除以正整数n的余数一定在集合{0,1,2, , 1 L n - }中， 结合整数同余的概念，所有整数根据模n同余关系可以分成n个集合，每一个集合中的整数 模 n 同 余 ， 并 将 这 样 的 集 合 称 为 模 n 同 余 类 或 剩 余 类 ， 且 可 依 次 记 为 [0 , 1 , 2 , , 1 ] [ ] [ ] [ ] n n n n L n - ，即[ ] { | mod } n x y y y x n = Î Ù º Z y ，x n Î - {0,1,2, , 1 L }。如果从每 一个模n同余类中取一个数为代表，形成一个集合，此集合称为模n的完全剩余系，以Zn 表 示。显然， Zn 的最简单表示就是集合 {0,1,2, , 1 L n - } ，这也是最常用的表示，即 Zn = - {0,1,2, , 1 L n }。 综上可知，a n mod 将任一整数a 映射到Zn = - {0,1,2, , 1 L n }中惟一的数，这个数就是 a 模 n的余数，所以可将a n mod 视作一种运算，并称其为模运算。 模运算具有如下的性质（其中n >1）： 如果n a b ( ) - ，则a b n º mod 。 模 n同余关系是整数间的一种等价关系，它具有等价关系的三个基本性质，即
自反性：对任意整数a,有a=amodn: 对称性：如果a=bmodn,则b=amodn; 传递性：如果a=bmodn且b=cmodn,则a=cmodn。 如果a=bmodn且c=dmodn,则a±c=b±d modn,ac=bdmodn。 模运算具有普通运算的代数性质，可交换、可结合、可分配，如： (amodn±bmodn)modn=(a±b)modn (amodn×bmodn)modn=(a×b)modn (a×b)modn±(a×c)modn)=(a×(b±c)modn 加法消去律：如果(a+b)=(a+c)modn,则b≡cmodn: 乘法消去律：如果ab=acmodn且gcd(a,n)=1,则b≡cmodn。 如果ac=bd modn且c=dmodn及gcd(c,n)=l,则a=bmodn。 上述性质均可由同余和模运算的定义直接证明，请读者自己完成。 【例2.3】已知11mod9=2和17mod9=8,下面是对性质(4)的验证： (11mod9)+(17mod9)mod9=(2+8)mod9=1 (11+17)mod9=1 (11mod9)-(17mod9)mod9=(2-8)mod9=-6mod9=3 (11-17)mod9=-6mod9=3 [(11mod9)×(17mod9)mod9=(2×8)mod9=16mod9=7 (11×17)mod9=187mod9=7 (5×11mod9)+(5×17mod9)mod9=(1+4)mod9=5 (5×(11+17)mod9=140mod9=5 [(5×11mod9)-(5×17mod9)mod9=(1-4)mod9=-3mod9=6 (5×(11-17)mod9=-30mod9=6 由性质(4)还可知，指数模运算可以变成模指数运算，从而使计算得以简化。例如，计算 13mod17可按如下方式进行： 132mod19=17 13mod19=(132×132)mod19=(17×17)mod19=4 138mod19=(13×13)mod19=(4×4)mod19=16 13"mod19=(13×132×138)mod19=(13×17×16)mod19=2 【例2.4】利用同余式演算证明(50-1)是56的倍数。 证明：由于53mod56=125mod56=13,所以5mod56=(53)2mod56=132mod56=1, 于是 50mod56=(5)0mod56=10mod56=1 所以，50=1mod56,即561(50-1)，(50-1)是56的倍数。 21
21 自反性：对任意整数a ，有a a n º mod ； 对称性：如果a b n º mod ，则b a n º mod ； 传递性：如果a b n º mod 且b c n º mod ，则a c n º mod 。 如果a b n º mod 且c d n º mod ，则a c b d n ± º ± mod ，ac bd n º mod 。 模运算具有普通运算的代数性质，可交换、可结合、可分配，如： ( mod mod ) mod ( )mod ( mod mod )mod ( )mod (( ) mod ( )mod ) ( ( )) mod a n b n n a b n a n b n n a b n a b n a c n a b c n ± = ± ´ = ´ ´ ± ´ = ´ ± 加法消去律：如果( ) ( )mod a b a c n + º + ，则b c n º mod ； 乘法消去律：如果ab ac n º mod 且gcd( , ) 1 a n = ，则b c n º mod 。 如果ac bd n º mod 且c d n º mod 及gcd( , ) 1 c n = ，则a b n º mod 。 上述性质均可由同余和模运算的定义直接证明，请读者自己完成。 【例 2.3】已知11mod9 2 = 和17mod9 8 = ，下面是对性质(4)的验证： ((11mod9) (17mod9))mod9 (2 8) mod9 1 (11 17)mod9 1 ì + = + = í î + = ((11mod9) (17mod9))mod9 (2 8)mod9 6mod9 3 (11 17) mod9 6mod9 3 ì - = - = - = í î - = - = ((11mod9) (17mod9))mod9 (2 8) mod9 16mod9 7 (11 17)mod9 187 mod9 7 ì ´ = ´ = = í î ´ = = ((5 11mod9) (5 17 mod9)) mod9 (1 4)mod9 5 (5 (11 17)) mod9 140mod9 5 ì ´ + ´ = + = í î ´ + = = ((5 11mod9) (5 17 mod9))mod9 (1 4)mod9 3mod9 6 (5 (11 17))mod9 30mod9 6 ì ´ - ´ = - = - = í î ´ - = - = 由性质(4)还可知，指数模运算可以变成模指数运算，从而使计算得以简化。例如，计算 11 13 mod17 可按如下方式进行： 2 4 2 2 8 4 4 11 2 8 13 mod19 17 13 mod19 (13 13 )mod19 (17 17)mod19 4 13 mod19 (13 13 )mod19 (4 4)mod19 16 13 mod19 (13 13 13 )mod19 (13 17 16)mod19 2 = = ´ = ´ = = ´ = ´ = = ´ ´ = ´ ´ = 【例 2.4】利用同余式演算证明 60 (5 1) - 是 56 的倍数。 证明：由于 3 5 mod56 125mod56 13 = = ，所以 6 3 2 2 5 mod56 (5 ) mod56 13 mod56 1 = = = ， 于是 60 6 10 10 5 mod56 (5 ) mod56 1 mod56 1 = = = 所以， 60 5 1mod56 º ，即 60 56 | (5 1) - ， 60 (5 1) - 是 56 的倍数
对于性质（⑤），应注意加法的消去律是无条件的，但模运算的乘法消去律是有条件的，比 如，6×3=2mod8和6×7=2mod8,但3与7模8不同余，这就是因为6与8不互素，不 满足乘法消去律的附加条件，两边的6不能被消去。 其实，有一个概念可以作为性质（⑤）的保障，这个概念就是逆元，其定义如下： 设a,neZ且n>1,如果存在beZ使得a+b=0modn,则称a,b互为模n的加法逆元， 也称负元，记为b=-amodn。 同上，a,n∈Z且n>1,如果存在b∈Z使得ab=1modn,则称a,b互为模n的乘法逆 元，记为b=amodn。 显然，对任何整数a,其模n的加法逆元总是存在的，(n-a)就是其中的一个，但不能 保证任何整数都有模n的乘法逆元。请看下面的定理： 定理：设a,n∈Z,如果gcd(a,n)=1,则存在惟一的b∈Z,满足ab=1modn。 证明：任取i,j∈Zn且i≠j,由于gcd(a,n)=1,根据性质(6)可知ai≠a叫modn。因此， az,modn=Z.,即{amod n,2 a mod n,.,(n-1)amod n}={1,2,.,n-1}。所以， l∈az modn,即存在b∈Z,使得ab modn=1∈az,modn。由Z,中数的互异性可知，满 足上面条件的b是惟一的。 2.2.2保密通信的基本模型 保密是密码学的核心目的。密码学的基本目的是面对攻击者Oscar,在被称为Alice和 Bob的通信双方之间应用不安全的信道进行通信时，保证通信安全。 在通信过程中，Alice和Bob也分别被称为信息的发送方和接收方，Alice要发送给Bob 的信息称为明文(Plaintext),为了保证信息不被未经授权的Oscar识别，Alice需要使用密 钥(Key)对明文进行加密(Encryption),加密得到的结果称为密文(Ciphertext),密文一 般是不可理解的，Alice将密文通过不安全的信道发送给Bob,同时通过安全的通信方式将 密钥发送给Bob。Bob在接受到密文和密钥的基础上，可以对密文进行解密(Decryption), 从而获得明文：对于Osca“来说，他可能会窃听到信道中的密文，但由于得不到加密密钥， 所以无法知道相应的明文。图2-3给出了保密通信的基本模型。 明文 密文 明文 加密 解密 不安全信道 安全信道 密钥 图2-3保密通信的基本模型 2.2.3密码学的基本概念 在图2-3给出的保密通信的基本模型中，根据加密和解密过程所采用密钥的特点可以 将加密算法分为两类：对称加密算法（单钥密码算法：Symmetric Cryptography Algorithm) 和非对称密码算法（双钥密码算法：Asymmetric Cryptography Algorithm)。 对称加密算法也称为传统加密算法，是指解密密钥与加密密钥相同或者能够从加密密 钥中直接推算出解密密钥的加密算法。通常在大多数对称加密算法中解密密钥与加密密钥是 相同的，所以这类加密算法要求Alice和Bob在进行保密通信前，通过安全的方式商定一个 密钥。对称加密算法的安全性依赖于密钥的管理。 公开密钥加密算法也称为公钥加密算法，是指用来解密的密钥不同于进行加密的密钥， 也不能够通过加密密钥直接推算出解密密钥。一般情况下，加密密钥是可以公开的，任何人 都可以应用加密密钥来对信息进行加密，但只有拥有解密密钥的人才可以解密出被加密的信 22
22 对于性质(5)，应注意加法的消去律是无条件的，但模运算的乘法消去律是有条件的，比 如，6 3 2mod8 ´ º 和6 7 2mod8 ´ º ，但 3 与 7 模 8 不同余，这就是因为 6 与 8 不互素，不 满足乘法消去律的附加条件，两边的 6 不能被消去。 其实，有一个概念可以作为性质(5)的保障，这个概念就是逆元，其定义如下： 设 a n, ÎZ 且n >1，如果存在bÎZ 使得a b n + º 0mod ，则称 a b, 互为模n的加法逆元， 也称负元，记为b a n º - mod 。 同上， a n, ÎZ 且 n >1，如果存在bÎZ 使得 ab n º1mod ，则称 a b, 互为模 n 的乘法逆 元，记为 1 b a n mod - º 。 显然，对任何整数a ，其模n的加法逆元总是存在的，( ) n a - 就是其中的一个，但不能 保证任何整数都有模n的乘法逆元。请看下面的定理： 定理：设a n, ÎZ ，如果gcd( , ) 1 a n = ，则存在惟一的 n bÎZ ，满足ab n º1mod 。 证明：任取 , n i j ÎZ 且i j ¹ ，由于gcd( , ) 1 a n = ，根据性质(6)可知ai aj n ¹ mod 。因此， mod n n a n Z Z= ， 即 {a n a n n a n n mod ,2 mod , ,( 1) mod 1,2, , 1 L L - = - } { } 。 所 以 ， 1 mod n Îa n Z ，即存在 n bÎZ 使得 mod 1 mod n ab n a n º Î Z 。由 Zn 中数的互异性可知，满 足上面条件的b 是惟一的。 2.2.2 保密通信的基本模型 保密是密码学的核心目的。密码学的基本目的是面对攻击者 Oscar，在被称为 Alice 和 Bob 的通信双方之间应用不安全的信道进行通信时，保证通信安全。 在通信过程中，Alice 和 Bob 也分别被称为信息的发送方和接收方，Alice 要发送给 Bob 的信息称为明文（Plaintext），为了保证信息不被未经授权的 Oscar 识别，Alice 需要使用密 钥（Key）对明文进行加密（Encryption），加密得到的结果称为密文（Ciphertext），密文一 般是不可理解的，Alice 将密文通过不安全的信道发送给 Bob，同时通过安全的通信方式将 密钥发送给 Bob。Bob 在接受到密文和密钥的基础上，可以对密文进行解密（Decryption）， 从而获得明文；对于 Oscar 来说，他可能会窃听到信道中的密文，但由于得不到加密密钥， 所以无法知道相应的明文。图 2-3 给出了保密通信的基本模型。 图 2-3 保密通信的基本模型 2.2.3 密码学的基本概念 在图 2-3 给出的保密通信的基本模型中，根据加密和解密过程所采用密钥的特点可以 将加密算法分为两类：对称加密算法（单钥密码算法：Symmetric Cryptography Algorithm） 和非对称密码算法（双钥密码算法：Asymmetric Cryptography Algorithm）。 对称加密算法也称为传统加密算法，是指解密密钥与加密密钥相同或者能够从加密密 钥中直接推算出解密密钥的加密算法。通常在大多数对称加密算法中解密密钥与加密密钥是 相同的，所以这类加密算法要求 Alice 和 Bob 在进行保密通信前，通过安全的方式商定一个 密钥。对称加密算法的安全性依赖于密钥的管理。 公开密钥加密算法也称为公钥加密算法，是指用来解密的密钥不同于进行加密的密钥， 也不能够通过加密密钥直接推算出解密密钥。一般情况下，加密密钥是可以公开的，任何人 都可以应用加密密钥来对信息进行加密，但只有拥有解密密钥的人才可以解密出被加密的信
息。在以上过程中，加密密钥称为公钥，解密密钥称为私钥。 在图2-3所示的保密通信机制中，为了在接收端能够有效地恢复出明文信息，要求加密 过程必须是可逆的。从上述图示可见，加密方法、解密方法、密钥和消息（明文、密文）是 保密通信中的几个关键要素，它们构成了相应的密码体制(Cipher System)。 定义21密码体制：密码体制的构成包括以下要素： (1)M:明文消息空间，表示所有可能的明文组成的有限集： (2)C:密文消息空间，表示所有可能的密文组成的有限集： (3)K:密钥空间，表示所有可能的密钥组成的有限集： (4)E:加密算法集合； (5)D:解密算法集合。 该密码体制应该满足的基本条件是：对任意的ky∈K,存在一个加密规则ey∈E和 相应的解密规则da∈D，使得对任意的明文x∈M,ee(x)∈C且d(ea(x》=x。 在以上密码体制的定义中，最关键的条件是加密过程e的可逆性，即密码体制不仅能 够对明文消息x应用e进行加密，而且应该可以使用相应的d,对得到的密文进行解密， 从而恢复出明文。 显然，密码体制中的加密函数，必须是一个一一映射。我们要避免出现在加密时 x≠x2,而对应的密文e(x)=e(x2)=y的情况，这时在解密过程无法准确地确定密文y 对应的明文x。 自从有了加密算法，对加密信息的破解技术应运而生。加密算法的对立面称作密码分析， 也就是研究密码算法的破译技术。加密和破译构成了一对矛盾体，密码学的主要目的是保护 通信消息的秘密以防止被攻击。假设攻击者Oscar完全能够截获Alice和Bob之间的通信， 密码分析是指在不知道密钥的情况下恢复出明文的方法。根据密码分析的Kerckhoffs原则： 攻击者知道所用的加密算法的内部机理，不知道的仅仅是加密算法所采用的加密密钥，常用 的密码分析攻击分为以下四类： (I)惟密文攻击(Ciphertext only attack):攻击者有一些消息的密文，这些密文都是 用相同的加密算法进行加密得到的。攻击者的任务就是恢复出尽可能多的明文，或者能够推 算出加密算法采用的密钥，以便可以采用相同的密钥解密出其他被加密的消息。 (2)己知明文攻击(Know plaintext attack):攻击者不仅可以得到一些消息的密文， 而且也知道对应的明文。攻击者的任务就是用加密信息来推算出加密算法采用的密钥或者导 出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。 (3)选择明文攻击(Chosen plaintext attack):攻击者不仅可以得到一些消息的密文和 相应的明文，而且还可以选择被加密的明文，这比已知明文攻击更为有效，因为攻击者能够 选择特定的明文消息进行加密，从而得到更多有关密钥的信息。攻击者的任务是推算出加密 算法采用的密钥或者导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解 密。 (4)选择密文攻击(Chosen ciphertext attack):攻击者能够选择一些不同的被加密的 密文并得到与其对应的明文信息，攻击者的任务是推算出加密密钥。 对于以上任何一种攻击，攻击者的主要目标都是为了确定加密算法采用的密钥。显然这 四种类型的攻击强度依次增大，相应的攻击难度则依次降低。 2.3古典密码技术 古典密码是密码学的渊源，虽然古典密码都比较简单而且容易破译，但研究古典密码的 设计原理和分析方法对于理解、设计以及分析现代密码技术是十分有益的。通常，古典密码 大多是以单个字母为作用对象的加密法，本节介绍几种古典密码体制。 23
23 息。在以上过程中，加密密钥称为公钥，解密密钥称为私钥。 在图 2-3 所示的保密通信机制中，为了在接收端能够有效地恢复出明文信息，要求加密 过程必须是可逆的。从上述图示可见，加密方法、解密方法、密钥和消息（明文、密文）是 保密通信中的几个关键要素，它们构成了相应的密码体制（Cipher System）。 定义 2.1 密码体制：密码体制的构成包括以下要素： （1） M ：明文消息空间，表示所有可能的明文组成的有限集； （2） C ：密文消息空间，表示所有可能的密文组成的有限集； （3） K ：密钥空间，表示所有可能的密钥组成的有限集； （4） E ：加密算法集合； （5） D ：解密算法集合。 该密码体制应该满足的基本条件是：对任意的 key K Î ，存在一个加密规则 key e E Î 和 相应的解密规则 key d DÎ ，使得对任意的明文 x MÎ ， ( ) key e x CÎ 且 ( ( )) key key d e x x = 。 在以上密码体制的定义中，最关键的条件是加密过程 key e 的可逆性，即密码体制不仅能 够对明文消息 x应用 key e 进行加密，而且应该可以使用相应的 key d 对得到的密文进行解密， 从而恢复出明文。 显然，密码体制中的加密函数 key e 必须是一个一一映射。我们要避免出现在加密时 1 2 x x ¹ ，而对应的密文 1 2 ( ) ( ) key key e x e x y = = 的情况，这时在解密过程无法准确地确定密文 y 对应的明文 x。 自从有了加密算法，对加密信息的破解技术应运而生。加密算法的对立面称作密码分析， 也就是研究密码算法的破译技术。加密和破译构成了一对矛盾体，密码学的主要目的是保护 通信消息的秘密以防止被攻击。假设攻击者 Oscar 完全能够截获 Alice 和 Bob 之间的通信， 密码分析是指在不知道密钥的情况下恢复出明文的方法。根据密码分析的 Kerckhoffs 原则： 攻击者知道所用的加密算法的内部机理，不知道的仅仅是加密算法所采用的加密密钥，常用 的密码分析攻击分为以下四类： （1） 惟密文攻击（Ciphertext only attack）：攻击者有一些消息的密文，这些密文都是 用相同的加密算法进行加密得到的。攻击者的任务就是恢复出尽可能多的明文，或者能够推 算出加密算法采用的密钥，以便可以采用相同的密钥解密出其他被加密的消息。 （2） 已知明文攻击（Know plaintext attack）：攻击者不仅可以得到一些消息的密文， 而且也知道对应的明文。攻击者的任务就是用加密信息来推算出加密算法采用的密钥或者导 出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。 （3） 选择明文攻击（Chosen plaintext attack）：攻击者不仅可以得到一些消息的密文和 相应的明文，而且还可以选择被加密的明文，这比已知明文攻击更为有效，因为攻击者能够 选择特定的明文消息进行加密，从而得到更多有关密钥的信息。攻击者的任务是推算出加密 算法采用的密钥或者导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解 密。 （4） 选择密文攻击（Chosen ciphertext attack）：攻击者能够选择一些不同的被加密的 密文并得到与其对应的明文信息，攻击者的任务是推算出加密密钥。 对于以上任何一种攻击，攻击者的主要目标都是为了确定加密算法采用的密钥。显然这 四种类型的攻击强度依次增大，相应的攻击难度则依次降低。 2.3 古典密码技术 古典密码是密码学的渊源，虽然古典密码都比较简单而且容易破译，但研究古典密码的 设计原理和分析方法对于理解、设计以及分析现代密码技术是十分有益的。通常，古典密码 大多是以单个字母为作用对象的加密法，本节介绍几种古典密码体制