应用密码学

第
1章

密码学中的基本概念







密码学理论与技术
第1章密码学中的基本概念

本章主要内容是密码学的基本概念，包括密码学的应用、密码算法的基本概念、密码编码学和分析学中的基本概念、密码学的信息论基础、密码学的起源和发展以及密码算法的安全性和复杂性的概念。
密码学在公元前400多年就已经产生了，正如《破译者》一书中所言，人类使用密码的历史几乎与使用文字的时间一样长。
密码学的起源可以追溯到人类刚刚出现，并且尝试去学习如何通信的时候，为了确保相互间通信的机密，开始是有意识地使用一些简单的方法来加密信息，如通过一些（密码）象形文字相互传达信息。接着由于表音和表意文字的出现和使用，确保通信的机密性就成为一种艺术。而随着国家、政权、军事力量的建立，密码学在重要信息的交流传递方面起到了越来越重要的作用。
随着数字化和网络技术不断深入到社会各个方面，人们对信息安全的重要性认识不断提高，而在信息安全中起着举足轻重作用的密码学也就成为信息安全中不可或缺的重要部分。今天密码学已经逐步揭开了神秘的面纱，进入了寻常百姓的日常生活之中。密码学的研究应用前景十分广阔，这个总是秘而不宣的重要角色，在人类的发展中将起到不可估量的作用。
当今世界各主要国家的政府都十分重视密码工作，其中一些国家设立庞大机构，拨出巨额经费，集中数以万计的专家和科技人员，投入大量的高速电子计算机和其他先进设备进行工作。与此同时，各民间企业和学术界也对密码学日益重视，不少数学家、计算机学家和其他有关学科的专家也投身于密码学的研究行列，更加快了密码学的发展。
1.1术语
密码学的英文名称为cryptography，此英文单词为两个古希腊词根的组合： crypto（秘密）和graphein（书写），意为密写，故密码学是一门研究秘密书写的科学，是以认识密码变换的本质、研究密码保密与破译的基本规律为对象的学科。
密码学的另一种定义是一门与信息安全密切相关的数学科学，是信息安全的核心。通俗地讲，密码学将信息表述为不可读的方式，但通过秘密的方法可将信息恢复出来。密码学提供的最基础的服务是使合法通信者进行信息的交互，而其他人员难以获得通信内容。
密码学一般包括两个对立统一的分支学科： 密码编码学和密码分析学。研究密码变化的规律并用之于编制密码以保护秘密信息的学科，称为密码编码学。研究密码变化的规律并用之于分析密码以获取信息情报的学科，称为密码分析学，也叫密码破译学。前者是实现对信息

保密的，后者是实现对信息反保密的，密码编码学与密码分析学相反相成，共处于密码学的统一体中。
现代密码学除了包括密码编码学和密码分析学两个主要学科外，还包括一个新产生的分支——密码密钥学。它是以密码体系最核心部分的密钥作为研究对象的学科。密钥管理是一种规程，它包括密钥的产生、分配、存储、保护、销毁等环节，因而在密码体系中密钥管理至关重要。上述三个分支学科构成了现代密码学的主要学科体系。
1. 发送者和接收者
试图发送消息的一方称为发送者（sender）。
消息的接收对象称为接收者（receiver）。
发送者和接收者都称为用户。经过认可的用户为合法用户，否则为非法用户。
2. 明文和密文
尚未隐藏或未被加密的信息称为明文（plaintext）或消息（message），用P或M表示。明文是未被隐藏的信息，即是发送者准备发送的原文信息。明文的集合称为明文信息空间，用SP表示。
用某种方法伪装消息以隐藏它的内容的过程称为加密（encryption）。
被加密后的消息称为密文（ciphertext），用C表示。所有的密文构成密文信息空间，用SC表示。
3. 密钥
明文到密文的转换往往由一些特殊的函数完成，控制这些函数的参数称为密钥（key），用K表示。所谓密钥，是指由用户事先选定的较短的字符或数字序列，其作用近似于打开保险箱的钥匙。所有密钥的集合构成密钥空间，用SK表示。密钥空间中不相同密钥的个数称为密钥体制的密钥量，它是衡量密码体制安全性的一个重要指标。
密钥是一个数值，它和加密算法一起生成特别的密文。密钥本质上是非常非常大的数。密钥的长度尺寸用比特（bit）来衡量，1024bit密钥代表的数是非常巨大的。在公开密钥加密方法中，密钥的长度越大，密文就越安全。
然而，公开密钥的尺寸和传统加密方法中密钥的尺寸是不相关的。传统80bit密钥的强度等同于1024bit的公钥，传统128bit密钥的强度等同于3000bit的公钥。在同种加密算法中，密钥越大越安全。但是传统方法和公开密钥方法所用的加密算法不一样，因此它们的密钥尺寸不能直接比较。
公钥和私钥是算术相关的，仅凭公钥推算出私钥是非常困难的。然而如果有足够的时间和计算能力，总是可能导出私钥的。这使得选择合适尺寸的密钥变得非常重要。为了安全需要足够大的密钥，而为了速度则要用小的密钥。
4. 加密与解密
加密是在密钥K的作用下，把明文P从明文信息空间SP对应到密文信息空间SC的一种变换，记该变换过程为

EK：SP→SC

则明文和密文的关系可表示为

C＝EK（P）



密文传送到接收者，合法用户利用密钥对

密文C进行与加密变换相反的逆变换，称为解密变换，用DK表示。解密变换是把密文C从密文信息空间SC对应到明文信息空间SP的变换为

DK：SC→SP


逆变换的过程称为解密或译密。解密变换的目的是恢复出明文P：

P=DK（C）＝DK［EK（P）］（11）

上式中的EK和DK为可逆变换对。K不同，EK和DK也不同。可见，信息的保密性完全依赖于密钥K的保密性。
5. 密码体制
一个完整的密码体制（cryptosystem）由5部分组成：
◆明文信息空间SP
◆密文信息空间SC
◆密钥空间SK
◆加密变换族EK
◆解密变换族DK
密码体制应满足以下3个一般性要求：
◆加、解密变换对所有密钥都一致有效。
◆体制必须是简单易行的，应易于找到密钥用于逆变换。
◆体制的安全性仅依赖于密钥的保密性而不能依赖于加、解密算法的强度。
一个好的密码体制则应至少满足以下两个条件：
◆在已知明文P和密钥K时，计算C＝EK（P）容易； 在已知密文C和密钥K时，计算P＝DK（C）容易。
◆在不知密钥K时，不可能由密文C推知明文P。
对于一个密码体制，如果能够根据密文确定明文或密钥，或者能够根据明文及其生成的密文确定密钥，这个密码体制就是可以破译的，反之则为不可破译的。
6. 鉴别、完整性和抗抵赖
除了提供机密性外，密码学在网络时代还有其他作用：
（1） 鉴别
解决身份冒充问题。消息的接收者应该能够确认消息的来源，发送者不可能伪装成他人。同样，发送者也要能够确认接收者是否是自称的，接收者不可能伪装成他人。
（2） 完整性
解决篡改问题。消息的接收者应该能够验证在传送过程中消息没有被修改。
（3） 抗抵赖
发送者或接收者事后不可能虚假地否认他发送或接收到的消息。
这些功能使通过计算机进行的信息交流，就像面对面交流一样安全可靠。某人是否就是他说的人，某人的身份证明文件（驾驶执照、医学学历或者护照）是否有效，声称从某人那里来的文件是否确实是从那个人那里来的，这些事情都是通过鉴别、完整性检验和抗抵赖来实现的。
1.2密码学的应用
由于在很长的时间内，密码仅限于军事、政治和外交的用途，密码学的知识和经验也仅掌握在与军事、政治和外交有关的密码机关手中，再加上通信手段比较落后，所以不论密码理论还是密码技术发展都很缓慢。
随着科学技术的进步，信息交换的手段越来越先进，信息交换的速度越来越快，信息交换的内容越来越广泛，信息交换的形式越来越多样化，信息交换的规模也越来越大。到了20世纪70年代，随着信息的激增，对信息保密的需求也从军事、政治和外交等领域，逐步

扩展到民用和商用领域，从而导致了密码学知识的广泛传播。计算机技术和微电子技术的发展，为密码学理论的研究和实现提供了强有力的手段和工具。进入20世纪80年代以后，随着网络的兴起，对密码理论和技术的研究更是呈爆炸性增长的趋势，密码学在雷达、导航、遥控、遥测等领域占有重要地位。除此之外，密码学正渗透到通信、电力、金融、医疗、卫生、交通等各行业的管理信息系统，甚至到个人和家庭等领域，而且保密的作用也已不再仅仅是保密，还有认证、完整性检验和抗抵赖等新的功能。
对普通的家庭来说，生活中许多地方需要保密，如各种银行密码、信用卡密码、网络账号和密码等。
1.3密码算法的概念及其分类
密码算法（algorithm）也叫密码（cipher），是用于加密和解密的数学函数。通常情况下，有两个相关的函数，一个用作加密，另一个用作解密。
密码算法有多种分类方法。如果算法的保密性是依赖于保持算法的秘密，这种算法称为受限制的算法。受限制的算法具有历史意义，但按现在的标准，它们的保密性已远远不够。大的或人员经常变换的用户组织不能使用它们，因为每有一个用户离开这个组织，其他用户就必须改换另外不同的算法。如果有人无意暴露了这个秘密，所有人都必须改变他们的算法。
不利的是，受限制的密码算法不可能进行质量控制或标准化。每个用户组织必须有他们自己的唯一算法。这样的组织不可能采用流行的硬件或软件产品。由于窃听者可以买到这些流行产品并学习这些算法，于是用户不得不自己编写算法并予以实现，如果这个组织中没有好的密码学家，那么他们就无法知道他们是否拥有安全的算法。
尽管有这些主要缺陷，受限制的算法对低密级的应用来说还是很流行的，用户或者没有认识到或者不在乎他们系统中内在的问题。
如果算法的保密性是依赖于保持密钥的秘密，这种算法称为非受限制的算法，也称基于密钥的算法。在非受限密码算法中，根据密钥的特点，加密算法分为两类： 秘密密钥算法和公开密钥算法。如果没有特殊说明，在本书中，密码算法均指非受限制的算法。
1.3.1对称密码算法
秘密密钥算法通常称之为对称密码算法或传统密码算法，也称单密钥算法。对称密码算法要求发送者和接收者在安全通信之前，商定一个密钥。其算法的安全性依赖于密钥，密钥一旦泄露，整个安全系统都要崩溃。换句话说，在使用对称密码加密算法时，只要通信需要保密，密钥就必须保密。
对称密码算法的加、解密可表示为
加密： EK（P）＝C
解密： P＝DK（C）

式中均使用同一

密钥K。
对称算法可分为两类。一类只对明文中的单个比特（有时对字节）运算的算法称为序列算法（stream algorithm）或序列密码（stream cipher）。另一类算法是对明文的一组比特运行运算，这些比特组称为分组（block），相应的算法称为分组算法（block algorithm）或分组密码（block cipher）。现代计算机密码算法的典型分组长度为64比特——这个长度大到足以防止分析破译，但又小到足以方便使用（在计算机出现前，算法普遍到每次只对明文的一个字符运算，可认为是序列密码对字符序列的运算）。
1.3.2公开密钥算法
公开密钥加密法可以解决密钥发布的问题，公开密钥的概念由Whitfield Diffie和Martin Hellman在1975年提出。现在也有证据表明英国情报机关先于Diffie和Hellman几年发明了这种方法，但是却作为军事秘密不为人知，并且没有什么有价值的成果。
公开密钥算法也叫非对称密码算法或双密钥算法。
公开密钥算法不要求通信双方共享一个密钥，其用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据解密密钥计算出来。用于加密的密钥可向所有使用者公开，使用加密密钥加密后的信息只有用相对应的解密密钥才可解密。
公开加密算法可用下式表示：
加密： EKe（P）＝C
解密： P＝DKd（C）
其中Ke和Kd分别代表加密和解密密钥。
公钥加密法的主要优势在于可以让事先没有安全通道的人安全地交换信息。收、发双方通过安全通道共享密钥的前提条件不存在了，所有的通信中只包含了公钥，私钥是不会传输或共享的。
由于传统的加密方法曾经是传送秘密信息的唯一手段，保持安全通道和发布密钥的高昂费用将其应用范围限制在能够负担得起这些费用的用户中，比如政府或者大银行。公钥加密法是加密技术的革命，它可以为普通人提供较强的加密手段，因而可以说公钥加密法是密码学发展史上的一个里程碑。
1.3.3Hash算法
Hash算法也称为消息摘要或单向函数，是密码学中的一种重要的算法。它是许多安全认证协议的重要组成部分，是实现有效、安全可靠的数字签名和认证的重要工具。
Hash算法是一种将任意长度的输入消息计算产生出一个固定长度的输出的数学变换，即消息m的Hash为h（m）。这类算法具有以下特点：
◆对于任何消息，计算h（m）相对来说较为容易，这意味着要使用该函数，并不需要占用太多的计算时间。
◆给定h（m），寻找一个消息使得其Hash值为h（m）的难度与穷举所有可能的m并计算h（m）的难度相比，不会有明显的差别。
◆虽然理论上存在很多不同数值，其Hash值都是h（m），但是要找到两个Hash结果相同的数值，

从计算的角度来说是很困难的。
要从密码学的角度认为一个Hash函数是安全的，其必备条件如下：
◆找到一个消息，使其消息摘要为一预先给定的消息摘要值，在计算上是不可行的。
◆以现有的计算能力，不可能找到两个具有相同消息摘要的消息。
◆给定一个消息，不可能找到另一个消息与其具有相同的消息摘要。
1.4密码编码学的基本概念
密码编码学的主要目的是确保明文、密钥等秘密信息不被窃听者或攻击者窃听或破译。这里有一个前提假设，即以上非法人员完全能够截获收发者之间的通信。
密码编码学希望能够解决在下述环境下即信息的存储（可能为非授权者接触）、信息的交换（可能被冒用或抵赖）以及信息的传输（可能被截获）过程中，信息的安全保护问题。
密码编码系统应具有以下独立的特征：
（1） 转换明文为密文的运算类型
有的算法的保密性可能依赖于保护算法本身，称为受限制的密码算法； 也有的算法仅依赖于使用算法时所采用的密钥，称为基于密钥的密码算法。本书仅讨论基于密钥的密码算法。
（2） 所用的密钥类型
如果发送方和接收方使用相同的密钥，这种密码称为对称密码、单密钥密码或传统密码。如果发、收双方使用不同的密钥，这种密码就称为非对称密码、双钥密码或公钥密码。
（3） 处理明文的方法
分组密码每次处理一个输入分组，相应地输出一个输出分组。而序列（流）密码是连续地处理输入元素，每次输出一个元素。
1.5密码分析学的基本概念
本书假设破译者是在已知密码体制的前提下来破译使用的密钥。成功的密码分析能恢复出消息的明文或密钥。同时密码分析也是发现密钥体制弱点的途径之一。
对密码进行分析的尝试称为攻击（attack）。一般意义下，攻击密码体制的方法有以下三种：
（1） 穷举攻击
密码分析者对一条密文尝试所有可能的密钥直至破译完成为止。平均而言，要获得成功应至少尝试所有可能密钥的一半。
（2） 统计分析攻击
密码分析者通过分析密文和明文的统计规律来破译密码，主要依赖算法的性质和明文的一般特征或某些明文密文对。如果使用这种方法成功推导出密钥，那么所有未来和过去使用该加密算法的密码都面临威胁。对抗统计分析攻击的方法是设法使明文的统计特性与密文的统计特性不一致。
（3） 解密变换攻击
密码分析者针对加密变换的数学基础，通过数学求解的方法来设法找到相应的解密变换。为对抗这种攻击，应该选用具有坚实数学基础和足够复杂的加密算法。
一般来说，密码攻击的常见类型有以下五种：
◆唯密文攻击（ciph

ertextonly attack）
◆已知明文攻击（knownplaintext attack）
◆选择明文攻击（chosenplaintext attack）
◆选择密文攻击（chosenciphertext attack）
◆选择文本攻击（chosentext attack）
分类的标准根据密码分析者已知的信息来定，表11具体给出了其差别。

表11基于加密信息的攻击类型



攻 击 类 型密码分析者已知的信息

唯密文攻击◆加密算法

◆要分析的密文

已知明文攻击◆加密算法

◆要分析的密文

◆用同一密钥加密的一个或多个明文密文对

选择明文攻击
◆加密算法

◆要分析的密文

◆有目的选择的明文，用同一密钥加密得到的密文
续表


攻 击 类 型密码分析者已知的信息

选择密文攻击◆加密算法

◆要分析的密文

◆有目的选择的密文，用同一密钥解密的对应明文

选择文本攻击◆加密算法

◆要分析的密文

◆任意选择的明文，用同一密钥加密的对应密文

◆有目的选择的密文，用同一密钥解密的对应明文

其中，唯密文攻击的强度最弱，其他攻击强度依次加强。
对于一个密码体制，如果密码分析者无论截获了多少密文以及无论用什么方法进行攻击都不能破译，则称其为绝对不可破译的密码体制。绝对不可破译的密码在理论上是存在的。但是，如果能够利用足够的资源，那么任何实际的密码都是可以破译的。正因如此，更具实际意义的是在计算上不可破译（computationally unbreakable）的密码。所谓计算上不可破译是指密码分析者根据可利用的资源来进行破译所用的时间非常长，或者破译的时间长到使原来的明文失去保密的价值。
应当指出，对任何一种攻击方法，我们都假定密码分析者事先知道所使用的密码体制，这称为Kerckhoff假设，是由Auguste Kerckhoff（1835—1903）提出的。这个假设在密码学领域的重要贡献在于指出了在设计密码体制时，永远不要低估密码分析者的能力。
1.6密码学的信息论基础
1949年，Shannon以其在信息论方面的基本著作为依据，为密码学提供了理论基础。依据已经收到的密文来得到的明文的不确定性，来度量密码在理论上的保密度。如果不论截取了多少密文，对明文仍然一无所知，则此密码达到完全保密。
所有现用密码都会在密文中留下一些有关明文的信息（唯一例外是一次一密）。随着密文长度的增加，明文的不确定性通常会下降，最后到零，此时意味着，有足够的信息来唯一地确定明文，这样，此密码至少在理论上是可破译的。
只要有数百比特长的明文，大多数密码在理论上是可破译的。但这并不意味着这些密码不安全，因为要确定明文在计算上的耗费，可能会超

过可利用的资源。因此，重要的问题不在于密码是否绝对安全，而是计算上是否安全。
图11是一个基本的密码通信系统模型。图中虚线部分为传送密钥的秘密信道。


图11基本的密码通信系统


信息论提出了两个相关问题： 噪声信道问题与保密问题。密码分析者所接收到的密文，可以看成是密码通信系统中的含有信道噪声的明文。
信息论用bit的平均数值来度量消息中的信息量，也称为消息熵。熵是所有消息集合上的概率分布的函数。消息熵用信息的bit数来度量其不确定度，这种信息bit数即使当消息在噪声信道中变了形，或隐蔽于密文中也是一定能获取到的。
如果明文中没有足够的不确定性，那么仅用于保密性的公开算法就经不起唯密文攻击。
1. 条件熵（暧昧度）

给定在集合{Y1，Y2，…，Ym}中的一消息Y，其中∑mi=1p（Yi）=1。令py（X）为在已知消息Y的情况下的条件概率（有时记为p（X|Y）），又令消息Y和X的联合概率为p（X，Y），则

p（X，Y）=Py（X）px（Y）（12）


暧昧度Hy（X）就是在给定Y的情况下X的条件熵

Hy（X）=-∑p（X，Y）log2py（X）px(Y）（13）

2. 唯一解距离
Shannon根据对一给定密文C，密钥K的熵Hc（K）来度量密码的保密度，即对于给定的C，K的不确定度有

Hc（K）=∑cp（C）∑kpc（K）log2（1/（pc（K）））（14）

其中pc（K）是在给定C的条件下，K的概率。如果Hc（K）=0，则没有不确定度，也就是说，只要有足够的资源，密码在理论上是可破译的。
当密文长度N增加时，暧昧度通常下降。
唯一解距离就是使Hc（K）→0的最小N，即要唯一确定密钥所必须要的密文长度。如果对于很长的N，Hc（K）也永不趋于0，则密码就是绝对安全的，Shannon曾用理想保密一词来描述。也就是说，无论截取多少密文，也确定不了密钥。
3. 完全保密
Shannon依据以下3类信息研究了密码体制的信息论特性：
◆以先验概率p（M）出现的明文消息M，其中∑p（M）=1。
◆以概率p（C）出现的密文消息C，其中∑p（C）=1。
◆以先验概率p（K）出现的选择密钥K，其中∑p（K）=1。
令pc（M）为在C已收到，而发送的消息是M的概率，完全保密的条件是

pc（M）=p（M）（15）

令pM（C）为在已知M发送而收到密文C的概率，则pM（C）就是将M加密成C的密钥K的概率p（K）之和，即

pM（C）=∑kp（K），EK（M）=C（16）


一般，对于给定的M和C，至多有一个密钥K使EK（M）=C（有些密码可以用不同的密钥将相同的明文变成相同的密文）。
完全保密的充要条件是

pM（C）=p（C）（17）

这意味着，在已知用某个密钥加密发送M，而收到一特定明文C的概

率，与已知用一部同密钥加密发送另一消息M′，而收到C的概率完全一样。密码分析人员截取了C1、C2、C3、C4中的一个，但无法确定使用了那个密钥，因此也无法知道正确的消息是哪个，如图12所示。


图12完全保密


完全保密要求，密钥的数量必须至少与可能的消息一样多，否则就可能有某个消息M，对于给定的C，没有将C解密成M，即pc（M）=0，密码分析人员据此，就可以排除某些可能的消息，从而增加破译的机会。
4. Shannon的五项准则
Shannon于21世纪40年代提出了关于密码体制的著名五项准则：
◆保密量
◆密钥的规模
◆加解密运算的简易性
◆错误的扩张
◆消息的扩张
5. 最坏情况的条件
在设计密码体制时，需要假定密码分析者拥有尽可能多的知识和情报信息，通过这种假定，设计者才能估计安全的时间。Shannon的最坏情况条件是：
◆密码分析者具有该密码体制的全部知识。
◆密码分析者已得到相当数量的密文。
◆密码分析者知道一定数量的与密文对应的等价明文。
1.7密码学的起源和发展
如前所述，密码学在公元前400多年就早已产生了，密码学的起源的确要追溯到人类刚刚出现，并且尝试去学习如何通信的时候。为了确保通信的机密，最先是有意识地使用一些简单的方法来加密信息，通过一些（密码）象形文字相互传达信息。例如我国古代的烽火就是一种传递军情的方法，再如古代的兵符也是用来传达信息的密令。
接着由于表音和表意文字的出现和使用，确保通信的机密性就成为一种艺术，古代发明了不少加密信息和传达信息的方法。中国古代秘密通信的手段，已有一些近于密码的雏形。宋代曾公亮、丁度等编撰的《武经总要·字验》中记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。
1871年，由上海大北水线电报公司选用6899个汉字，代以四码数字，成为中国最初的商用明码本，同时也设计了由明码本改编为密本及进行加乱的方法。在此基础上，逐步发展为各种比较复杂的密码。
在欧洲，公元前405年，斯巴达的将领来山得使用了原始的错乱密码； 公元前1世纪，古罗马皇帝恺撒曾使用有序的单表代替密码； 之后逐步发展为密本、多表代替及加乱等各种密码体制。这一阶段，称为手工密码时代。
在手工密码阶段，密码学有如下特点：
◆密码学还不是科学，而是艺术。
◆出现一些密码算法。
◆密码算法的基本手段——代替和置换出现，针对的是字符。
◆简单的密码分析手段出现。

密码学真正成为科学是在19世纪末和20世纪初期，特

别是两次世界大战中对军事信息保密传递和破获敌方信息的需求，密码学得到了空前的发展，并广泛用于军事情报部门的决策。
20世纪初，随着技术的进步，产生了最初的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场。这一阶段又称为机械密码时代。
机械密码阶段密码学的主要特点是：
◆密码学逐渐成为科学。
◆密码算法逐步考虑复杂性要求。
◆密钥的使用开始变化。
◆密码分析理论开始形成。
在计算机出现以前，密码算法主要是通过字符之间代替或易位实现的，我们统称这些密码体制为古典密码（classical cryptography）。这些密码算法的使用和分析破译，为今天电子时代尤其是网络时代的密码算法提供了坚实有力的理论基础。因此对古典密码学的学习和研究，是理解、构造和分析现代密码算法的基础。
20世纪60年代后，电子技术的发展，使得基于复杂计算的密码成为可能。这一阶段电子密码机得到较快的发展和广泛的应用，使密码学的发展进入了一个新的阶段。同时充分利用了古典密码留下来的经验，对于算法的设计有了更科学的思路。
电子时代密码学的主要特点有：
◆数据的安全基于密钥而不是算法的保密。
◆高次迭代技术和非线性技术的使用。
◆算法设计需要抵抗各类已知的分析攻击方法。
◆算法分析理论逐步形成。
网络技术的发展，给传统的仅用于防止窃密的密码算法带来前所未有的挑战，保密技术与信息安全技术逐步融合，密码算法不仅要确保机密性，还要用于防抵赖、防冒充、防篡改、防重用等需求。
网络时代的密码学主要特点是：
◆密码算法设计日益复杂，既要考虑理论，又要考虑实现和使用，成为一项工程。
◆单一算法不能完全解决问题，需要一套综合的算法体系。
◆算法的安全性要融入系统的安全性考虑之中。
密码破译是随着密码的使用而逐步产生和发展的。1412年，波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期，欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有了一定的发展。1863年普鲁士人卡西斯基所著《密码和破译技术》和1883年法国人克尔克霍夫所著《军事密码学》等著作，都对密码学的理论和方法做过一些论述和探讨。1949年美国人香农发表了《秘密体制的通信理论》一文，应用信息论的原理分析了密码学中的一些基本问题。
自19世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战线。
1917

年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦三岛和其他许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，这些事例也从反面说明了密码保密的重要地位和意义。
1.8密码算法的安全性和复杂性

1.8.1算法的安全性

密码系统的安全性是至关重要的问题，主要由保密性和可靠性来衡量。
对算法的保密性的要求主要有：
◆在已知与密文相对应的明文的情况下，密码分析者要从截取的密文中系统地确定解密变换，在计算上是不可行的。
◆密码分析者要从截获的密文中确定明文，在计算上是不可行的。
图13给出了保密性要求的示意。


图13保密性的要求


对算法的可靠性要求有：
◆在已知与密文相对应的明文的情况下，密码分析者要有规律地确定加密变换，在计算上是不可行的。
◆密码分析者若想有规律地求出密文C′，使得DK（C′）是m集合中的有效明文，在计算上是不可行的。
图14给出了可靠性要求的示意。


图14可靠性的要求


根据被破译的难易程度，不同的密码算法也具有不同的安全等级。有多种衡量安全性的方法。按照价值大小来衡量，如果破译算法的代价大于加密数据的价值，那么算法可能是安全的； 按照数据有效时间来衡量，如果破译算法所需的时间比加密数据保密的时间更长，那么算法可能是安全的； 按照实际破译所需数据量来衡量，如果用单密钥加密的数据量比破译算法需要的数据量少得多，那么算法可能是安全的。
之所以说“可能”是因为在密码分析中总有新的突破。另一方面，大多数数据随着时间的推移，其价值会越来越小，而数据的价值总是比突破保护它的安全性的代价更小，这点是十分重要的。
Lars Knudsen把破译算法分为不同的类别，安全性的递减顺序为：
◆全部破译。密码分析者找出密钥K，这样DK（C）=P。
◆全盘推导。密码分析者找到一个代替算法A，在不知道密钥K的情况下，等价于DK（C）＝P。
◆实例（或局部）推导。密码分析者从截获的密文中找出明文。
◆信息推导。密码分析者获得一些有关密钥或明文的信息。这些信息可能是密钥的几个比特、有关明文格式的信息等。
如果不论密码分析者有多少密文，都没有足够的信息恢复出明文，那么这个算法就是无条件保密的。事实上，只有一次一密乱码本，才是不可破译的（给出无限多的资源仍然不可破）。所有其他的密码系统

在唯密文攻击中都是可破译的，只要简单地一个接一个地去试每种可能的密钥，并且检查所得明文是否有意义，这种方法叫做强力攻击或穷举攻击。
密码学更关心在计算上不可破译的密码系统。如果一个算法用（现在或将来）可得到的资源都不能破译，这个算法被认为在计算上是安全的（有时叫做强的）。准确地说，“可用资源”就是公开数据的分析整理。
可以用不同方式衡量攻击方法的复杂性：
◆数据复杂性。用作攻击输入所需的数据量。
◆处理复杂性。完成攻击所需要的时间，这个经常叫做工作因素。
◆存储需求。进行攻击所需要的存储量。
作为一种原则，攻击的复杂性取这3个因数的最小值，有些攻击包括这3种复杂性的折中： 存储需求越大，攻击可能越快。
复杂性用数量级来表示。如果算法的处理复杂性是2128，那么破译这个算法也需要2128次运算（这些运算可能是非常复杂和耗时的）。假设有足够的计算速度去完成每秒100万次运算，并且用100万个并行处理器完成这个任务，那么仍需花费1019年以上才能找出密钥，那是宇宙年龄的10亿倍。
当攻击的复杂性是常数时（除非一些密码分析者发现更好的密码分析攻击），就只取决于计算能力了。在过去的半个世纪中，我们已看到计算能力的显著提高，并且没有理由认为这种趋势不会继续。许多密码分析攻击用并行处理机是非常理想的： 这个任务可分成亿万个子任务，且处理之间不需相互作用。一种算法在现有技术条件下不可破译就简单地宣称该算法是安全的，这未免有些冒险。好的密码系统应设计成能抵御未来许多年后计算能力的发展。
1.8.2密码算法中的复杂性概念
无论在实际中采用哪种加密算法，输出序列的每一个比特都可用一个含有若干个变量的方程组来表示。当然，变量是由密钥来确定的。在最坏的情况下，假设密码分析人员知道一段对应的明文和密文序列，这样就得到一组有用的方程。这组方程的解将推导出这次通信中正在使用的密钥。如果这组方程是线性的，而且方程个数并不很多，那么解这组方程就比较容易。因此，实际设计工作一般是运用编制的算法程序在通用或专用电子计算机上进行的，故可以用实现破译所需的计算机资源（即运算时间与存取空间）对破译者所需付出的代价作定量的描述。因此，复杂性理论在密码设计和密码强度分析中占有十分重要的地位。
本节所讨论的“问题”是一个专用术语。问题是指需要回答的一般性提问，通常含有若干个未定参数和自由变量。问题的描述包括：
◆所有自由变量的一般性描述。
◆陈述答案或解必须满足

的性质。
若给定问题的所有自由变量被指定了具体的值，就得到了该问题的一个实例。
算法是指求解某个问题的一系列具体步骤（与密码算法的定义是有区别的）。可以把算法理解为求解某个问题的通用计算程序。如果算法A可以成功地求得问题Q的任何一个实例的解，就称算法A已解问题Q。一个算法的复杂性由该算法所要求的最大时间与存取空间确定。由于算法用于解同一问题的不同规模实例所要求的时间T和空间S往往不同，所以总是将它们表示成问题实例的规模n（描述该实例所需输入数据长度）的函数。
1. 算法的复杂性
算法的时间复杂性函数T（n）反映了该算法对时间的需求，及对每一个实例在规模n＝n1的条件下，要求T（n1）给出该算法解出规模为n1的各个实例的最长时间。一般用算术运算次数作计量单位，以避免使用不同速度的计算机给讨论带来麻烦。
算法的空间复杂性函数S（n）反映了该算法对空间的需求。通常，可实现的算法都自动地引入了对空间复杂性函数S（n）的某种限制，例如，S（n）不超过n的某个低次多项式，所以人们更加注重于对算法时间复杂性T（n）的研究。
如果存在着一个多项式g（n）和常数k（k>0），使得某个算法的时间复杂性函数T（n）恒小于kg（n），即T（n）≤ kg（n），那么就把这个算法称为多项式时间算法。所有的非多项式时间算法统称为指数时间算法。通常算法的时间复杂性也称为O［g（n）］。
一个算法用于解某个问题相同而输入数据长度n不同的实例，其时间需求也可能会有很大差异，所以，有时需要研究其平均时间复杂性函数T′（n），它表示这种算法解该问题规模为n的所有实例的时间需求的平均值。
2. 问题的复杂性
复杂性理论研究，主要基于在图灵机上解决最难的问题实例所需的最低时间、空间开销。图灵机是一种假想的计算机。这种机器能够移动纸带，在小方格内写入或者擦去符号，进行计算以及停机。图灵机虽然简单，但给以足够的时间，它能解最复杂的决定性计算机（决定性计算机是一种其性质由制造者可以实际做到的机器）所能解的一切问题。
能够用多项式时间算法解决的问题，则称其是易解的。由一切易解的问题组成的类记为P，称为多项式时间可解类。在多项式时间内不能解决的问题，则称其是难解的。
关于难解的问题有以下两点需要指出：
◆不应该简单地认为用多项式时间算法可以求解的问题是易解的，而用指数式算法求解的问题是难解的。时间复杂性函数本身是对求解最坏特例所花费的时间的一种度量。如果对某个问题只讨论限定输入数据长度的特例，那么指

数式时间函数有可能是很有效的。说某个问题是难解的，是指该问题至少有一个实例需要指数式时间，解其他的实例所需要的时间可能少得多。在实际工作中，密码设计人员对这一点应该有足够的认识。
◆难解的原因可能不止一个。其中一个明显的原因是问题太难，以致解它必须用指数量级的时间。另一个原因是解本身如此广泛，以致不能用一个受一定输入长度的某个多项式函数所限制的表达式来描述。显然，后一类难解性通常从问题的定义中就显现出来了，而且一开始就可以被识别出来。所以，这里将集中研究前一种难解性。
在研究难解问题过程中，经常会遇到两个概念，即不可判定问题和可判定问题。所谓不可判定问题是能够证明无法构造一个算法去求解它，这样的问题称为不可判定问题。问题的解只能是“是”或者是“非”的这类问题称为可判定问题。
在可判定的问题中，存在如此难解的问题： 即使已有了对问题的解的一个猜测SQ，也无法在多项式时间内验证SQ是否真的是问题的解，即仅仅做解的验证工作就要人们付出难以接受的时间代价。所以，人们自然地把注意力集中于下述的NP类的可判定问题。
在合理的编码方案下可以用非确定型算法在多项式时间内解的判定问题称为NP问题。所谓非确定型算法由猜想和检查两个阶段组成。它首先是对某个问题“猜想出”某个“解”，然后，采用普通的已知算法进行运算，检验猜测的解是否正确。显然任何一个P类问题，自然也是NP类问题。因为，在决定性计算机上用多项式时间算法可解决的问题，在非决定性计算机上用多项式时间算法也可以解决。但是，任何属于NP类的问题就不一定属于P类。实际上，NP类问题在输入数据长度较大时，求解是相当困难的。
在NP类问题中，有一个特别重要的问题，即“可满足性”问题（指确定任何一个给定的逻辑公式是否是可满足的，即是否存在一种对变量“真”、“假”值的配置方法，使公式的结果为真）。对于NP类中任意给定的一个问题，


图15NP类问题与P类和NP

完全问题的关系

都存在一个将它归结为可满足性问题的多项式时间算法。因此，如果找到一个多项式时间算法来解可满足性问题，这就意味着，每一个属于NP类的问题也属于P类。换句话说，若在NP类问题中存在任何难解的问题，那么可满足性问题必定是其中的一个。通常，把属于“可满足性”问题类统称为NP完全问题。显然，NP完全问题是NP问题中最难解的问题。NP类问题与P类和NP完全问题的关系如图15所示。
3. 复杂性理论与密码学的关系
难解问题是密码技术的基础。

将加密算法构筑在难解问题基础之上是密码学发展的一个方向，它迫使破译分析者要破译机密算法必须做大量的工作。特别是最近30年来，依靠复杂性理论，无论是在单钥体制的再认识与改造还是在新的双钥体制的构想、建立和分析方面都取得了长足的进步。例如，在典型的密钥流产生器的设计与分析中，人们对密钥流序列的线性复杂度的认识不断深化，并开始了利用驱动序列与输入密钥流相关性的相关破译与对抗的研究，取得了不少有意义的结果。

许多传统的密码类能够用非确定性的多项式时间算法进行攻击。如果已知密文C，密码分析者简单地猜测一个明文M和一个密钥K，然后在输入明文M和K的基础上，以多项式时间运行加密算法，最后检查结果是否等于C就可以了。这在理论上是重要的，因为它给出了相对NP类的密码而言，密码分析的复杂性的上限。当然，实际上这也是密码分析者在寻找所要的确定性多项式时间算法。
虽然难解性问题可以使构筑在此基础上的密码算法具有较强的抗破译性，但是也必须指出由此造成的一些误解：
◆难解性问题并不能担保不存在比指数时间算法容易的解法，它仅仅指出，比指数时间算法还容易的解法不大可能找到。如果以后能够证明P＝NP，那么破译这种加密算法困难的基础就会起变化。
◆每一个难解性问题都有一个确定的指数时间解法，即与2n成正比的时间内运行的解法。n较小时，2n不是很大，分析者用枚举攻击的工作量也不会太大。如果n很大时，2n便是合适的障碍。
◆硬件的不断进步使越来越大规模的问题都能解开，例如，很多个处理器同时运行的并行处理机已经制造成功。根据猜测程序，两个处理器可以同时从一个猜测点出发运行不同的程序通路，很多处理器一起就可能在多项式时间内以确定性的方式完成某些非确定性程序。但是，也可以选择这样的问题设置，使其n值大到足以要求并行处理器的数目大到不合理的程度才能解。
◆即使一个加密算法是基于难解问题的，但是破译分析者为了破译它不一定总是去解这个难解问题。要用于加密，这些问题必须有一个秘密的容易的解法。破译分析者可能寻找这种容易的解法而不是去解这个难解问题。
上述问题的存在并不说明复杂性理论对于密码学不合适或者不重要，相反，这些矛盾或问题，将进一步促进密码学与复杂性理论的相互结合与发展，同时，也推动了复杂性理论的研究和创新。
习题和思考题
1.1一个完整密码体制的组成和一般要求是什么？如果自己设计一个密码体制，你会提出什么样的要求？
1.2证明完全保密的充要条件的正确性

。
1.3简述攻击密码体制的方法和常见的密码攻击类型。总结每种攻击类型的实施难易度，并做一比较。
1.4安全的密码系统有哪些要求？如何构建一个安全的密码系统？
1.5分别列举两个以上现有的对称密码算法、公开密钥算法和Hash算法。
1.6阐述密码编码学与分析学之间的相互联系及作用。
1.7举例说明近10年密码学的一些新的发展状况。
1.8分析并总结3种密码算法的特点和适用范围。
1.9复杂性理论一般包括哪些方面？
1.10密码算法的复杂性对于安全性研究的意义？




第
2章

手工密码体制







第2章手工密码体制

本章主要内容是手工密码体制，主要思路是针对字符的加密方式，从简到繁，从算法的设计到分析，再到新的抗分析的算法设计。
经典加密技术虽然在当今的密码编码技术中已不太使用，但它们在密码发展史上具有不可磨灭的贡献，许多古典密码思想至今仍被广泛运用，还是密码学发展的基础。
另一方面，密码学是隐蔽战线上富有生气的研究领域，不仅涉及秘密，其本身也隐蔽于秘密中，几乎就是秘密的科学。对古典密码学的研究有助于我们理解今天的对称加密基本方法、预测密码分析攻击的类型。
经典加密体制包括手工密码体制和机械密码体制两类，本章讨论手工密码体制。
2.1手工密码算法类型
在20世纪之前，密码学由基于字符的密码算法构成。不同的密码算法是字符之间互相代替或者互相换位。优秀的密码算法往往是这两种方法的结合，每次进行多次运算。
这两种基本的手工密码算法类型是代替密码（substitution cipher）和换位密码（transposition cipher）。
代替密码就是明文中每一个字符被替代为密文中的另外一个字符，接收者对密文进行逆替换以恢复明文。
在手工密码算法中，有4种类型的代替密码：
◆单表代替密码（monoalphabetic cipher）： 用密文的一个字符简单代替明文的一个字符，从而生成密文。
◆同音代替密码（homophonic substitution cipher）： 与简单代替密码类似，唯一不同的是明文的单个字符可以映射成密文的几个字符之一。
◆多字母组代替密码（polygram substitution cipher）： 字符块被成组加密。
◆多表代替密码（polyalphabetic substitution cipher）： 由多个简单的代替密码构成。
2.2单表密码
前面已介绍，单表密码是一种代替密码，不同的代替密码有不同的代替规律，即使代替规律相同，明文、密文间字母对应关系不同，最终代替出的密码也不相同。
首先以Caesar密码为例，介绍单表密码的生成过程。
Caesar密码被认为是最早的代替密码，由Julius Caesar发明。其原理非常简单，就是对字母中的

每个字母，用其之后的第3个字母替代： 即a用D代替，b用E代替，……，w用Z代替。x其后只有两个字母，则在数完最后一个字母后又接着从头数，即x用A代替。把明文字母和用来代替的密文字母对照写下来就构成了如表21所示的代替关系。

表21密码表



明文字母序号12345678910111213
明文字母表abcdefghijklm
密文字母表DEFGHIJKLMNOP
明文字母序号14151617181920212223242526
明文字母表nopqrstuvwxyz
密文字母表QRSTUVWXYZABC

如果让每个字母和一个数值意一一对应，如表22所示，那么加密算法可用下式表达：

表22字母数字对应表



字母abcdefghijklm

对应数字0123456789101112

字母nopqrstuvwxyz

对应数字13141516171819202122232425


C=E（P）=（P+3）mod（26）（21）


对Caesar密码加以扩展，移位可以是任意的整数k，这样就得到一般的Caesar算法，即

C=E（P）=（P+k）mod（26），1≤k≤25（22）


其解密算法为

P=D（C）=（C-k）mod（26）（23）

2.3同音代替密码
在同音代替中，一个明文字母表中的字母a，可以变换为若干个密文字母f（a），称为同音字母。因此，从明文到密文的映射f的形式是： f： A→2C，其中A，C分别是明文和密文字母表。
一个简单的同音代替密码的示例如下：
①The ②concept ③of ④information ⑤will ⑥be ⑦taken ⑧to ⑨be ⑩an understood quantity. To introduce cryptography，an understanding of issues related to information security in general is necessary. Information security manifests itself in many ways according to the situation and requirement.
在上述的短文中，每个单词的首字母都和一个数字对应。例如字母o与数字3、18对应； 字母i和数字4、14、19、22、24、26、28、31、32对应。加密时可以用与字母对应的任何一个数字代替该字母。比如，明文It is a cow的密文可能是
4114231021834

也可能是
14213129161535
还可能是其他的数字组合等。
2.4任意的单表代替密码

设P=C=Z/（26），k由与英文26个字符符号相对应的数字0，1，…，25的所有可能置换组成。对于任意π ∈k，定义： eπ（x）=π（x）=y，且dπ（y）=π-1（y）=x，其中π-1是π的逆置换。置换π可以表示为

π＝0123…232425

0′1′2′3′…23′24′25′


任意的单表代替密码的特点如下：
◆密钥空间K： |k|=26! ≈ 4×1026，破译者穷举搜索是不行的，但可尝试用统计的方式进行破译。
◆移位密码、乘数密码、仿射密码算法都是这种代替密码的特例。
2.5任意单表代替密码的破译方法
密码破译的原则： 遵循观察与经验。
密码破译的方法： 采用归纳与演绎。
密码破译的步骤： 分析、假设、推测和证实。
用统计学的方法，分析字母的频率和

字母之间的组合关系是破译传统密码的基本方法。表23是单字母频率表，列出了从1000个英文字母取样中，每个字母分别出现的次数，从中可以算出每个字母的相对频率，如A的相对频率是0.073。取样量越大，计算结果就越可靠。表23、表24分别给出了单字母作为单词的首字母和尾字母的频率表，该取样是从一份报纸的文章中顺序取出16410个单词得到的。类似地，还可以得到二字母组频率表，三字母组频率表，等等。