第3章密码学概述 密码学是网络信息安全的数学理论基础,密码学常被认为是数学和计算机科学的分 支,和信息论也密切相关。著名的密码学者RonRivest解释道:“ 密码学是关于如何在敌 人存在的环境中通信”。密码学的首要目的是隐藏信息的含义,并不是隐藏信息的存在。 密码学也促进了计算机科学的发展,特别是计算机与网络安全中的技术发展。密码学已 被应用于人们的日常生活,如自动柜员机的芯片卡、电子商务等。目前主要的网络安全技 术也都是以密码学为基础的,使用最广泛的加密机制是对称密码体制和公钥密码体制。 本章首先介绍密码学的起源和发展历程;然后介绍密码学中的基本概念;最后介绍一些传 统的加密技术,虽然这些加密技术不再使用了,但这些加密技术中的一些思想依然在现代 密码学中得到了延伸。 3.密码学起源 1 密码学一词源自希腊语krypto及“理念”两词,意思为“隐藏”及“消息”。它是研究信 息系统安全保密的科学,其目的是为两人在不安全的信道上进行通信而不被破译者获取 通信的内容。相传最早使用密码捆在木棒上方法是公元前5世纪的斯巴达人,公元 前404 年,斯巴达国(今希腊)北路军统帅莱山得在征服雅典之后,本国的信使赶到,献上 了一条皮带,上面有文字,通报了敌将断其归路的企图。莱山得当机立断,率师轻装脱离 了险境。他们使用的是一根叫Sctl如图3. yae的棍子,1所示。送信人先绕棍子卷一张纸 条,然后把要加密的信息写在上面,接着打开纸送给收信人。如果不知道棍子的宽度(这 里作为密钥)是不可能解密里面的内容的。后来,罗马的军队用凯撒密码(三个字母表轮 换)进行通信。 中国周朝兵书《六韬·龙韬》中也记载了密码学的 运用,其中的《阴符》和《阴书》便记载了周武王问姜子牙 关于征战时与主将通信的方式。 太公曰:“ 主与将,有阴符,凡八等。有大胜克敌之 图3.1 Scytale棍子密码符,长一尺。破军擒将之符,长九寸。降城得邑之符,长 八寸。却敌报远之符,长七寸。警众坚守之符,长六寸。 请粮益兵之符,长五寸。败军亡将之符,长四寸。失利亡士之符,长三寸。诸奉使行符,稽 留,若符事闻,泄告者,皆诛之。八符者,主将秘闻,所以阴通言语,不泄中外相知之术。敌 虽圣智,莫之能识。” 武王问太公曰:“…… 符不能明;相去辽远,言语不通。为之奈何?” 太公曰:“ 诸有阴事大虑,当用书,不用符。主以书遗将,将以书问主。书皆一合而再 离,三发而一知。再离者,分书为三部。三发而一知者,言三人,人操一分,相参而不相知 情也。此谓阴书。敌虽圣智,莫之能识。” 阴符是以八等长度的符来表达不同的消息和指令,可算是密码学中的替代法 (substitution),把信息转变成敌人看不懂的符号。至于阴书则运用了移位法,把书一分 为三,分三人传递,要把三份书重新拼合才能获得还原的信息。 在随后的19个世纪中,主要是发明一些更加高明的加密技术,这些技术的安全性通 常依赖于用户赋予它们多大的信任程度。然而密码学文献发展有个很奇妙的过程,由于 战争和各个国家之间的利益,密码学重要的进展很少在公开的文献中出现。密码学的发 展大致可以分为以下三个阶段。 第一阶段是从几千年前到1948年。这一时期密码学还没有成为一门真正的科学,而 是一门艺术。密码学专家常常是凭自己的直觉和信念来进行密码设计,而对密码的分析 也多基于密码分析者(即破译者)的直觉和经验来进行的。第一次世界大战以后,情况开 始变化,完全处于秘密工作状态的美国陆军和海军的机要部门开始在密码学方面取得根 本性的进展。加州奥克兰的EdwardH.Hebern申请了第一个转轮机专利,这种装置在 差不多50年内被指定为美军的主要密码设备。但是由于战争的原因,公开的文件寥寥 无几。 第二阶段是从1949年到1975年。1949年,美国数学家、信息论的创始人Shannon ClaudeElwood发表了《保密系统的信息理论》一文,它标志着密码学阶段的开始。同时 以这篇文章为标志的信息论为对称密钥密码系统建立了理论基础,从此密码学成为一门 科学。由于保密的需要,这时人们基本上看不到关于密码学的文献和资料,平常民众是接 触不到密码的。1967年DavidKahn出版了一本叫作《破译者》(TheCodebreakers)的小 说,它并没有任何新的技术思想,但却对密码学的历史做了相当完整的记述。这部著作的 意义不仅在于它涉及相当广泛的领域,而且在于它使成千上万原本不知道密码学的人了 解了密码学。新的密码学文章慢慢开始源源不断地被编写出来,使人们知道了密码学。 20世纪70年代初期,从而使更多的人了解 IBM公司发表了有关密码学的几篇技术报告, 了密码学的存在。但科学理论的产生并没有使密码学失去艺术的一面,如今,密码学仍是 一门具有艺术性的科学。 第三阶段为1976年至今。1976年,Difie和Helman发表了《密码学的新方向》一 文,他们首次证明了在发送端和接收端不需要传输密钥的保密通信的可能性,从而开创了 公钥密码学的新纪元。该文章也成了区分古典密码和现代密码的标志。1977年,美国的 数据加密标准(DES)公布。这两件事情导致了对密码学的空前研究。从这时候起,开始 对密码在民用方面进行研究,密码才开始充分发挥它的商用价值和社会价值,人们才开始 接触到密码学。密码学发展至今,已有两大类密码系统:第一类为对称密钥密码系统;第 二类为非对称密钥(公开密钥)密码系统。 随着在密码学理论和技术上的探索和实践,人们逐渐认识到认证和保密是两个独立 的密码属性。Simmons系统地研究了认证问题,并建立了一套与Shannon保密理论平行 的认证理论。 41 历史车轮滚滚向前,密码学紧跟科学技术前进的步伐,根据密码学所使用的科学技 术,还可以将其分为如下发展历程:密码学的初级形式———手工阶段,经过中间形式——— 机械阶段,发展到今天的高级形式———电子与计算机阶段。现代密码分析依赖数学方面 的知识,现代密码学离开数学是不可想象的,密码学涉及数学的多个分支,如代数、数论、 概率论、信息论、几何、组合学等。不仅如此,密码学的研究还需要具有其他学科的专业知 识,如物理、电机工程、量子力学、计算机科学、电子学、系统工程、语言学等;反过来,密码 学的研究也促进了上述各学科的发展。 计算机的出现,大大促进了密码学的变革。由于商业应用和大量的计算机网络通信 的需要,民间对数据保护、数据传输的安全性、防止工业谍报活动等课题越来越重视,密码 学的发展从此进入了一个崭新的阶段,与此同时,密码学的研究开始大规模地扩展到 民用。 3.密码的基本概念 2 首先定义一些术语。原始的消息为明文(Plaintext), 而加密后的消息为密文(Cipher)。 从明文到密文的变换过程称为加密(Encryption), 一般用E表示加密过程,从密文到明文 的变换过程称为解密(Decryption), 一般用D表示解密过程。用于加密的各种方案构成 的研究领域称为密码编码学。这样的加密方案称为密码体制或密码。不知道任何加密细 节的条件下解密消息的技术属于密码分析学的范畴,密码分析学即外行所说的“破译”。 密码编码学和密码分析学统称密码学。 3.1 密码编码学 2. 密码编码学的主要任务是研究安全、高效的信息加密算法和信息认证算法的设计理 论与技术,密码系统设计通常的基本要求如下。 (1)知道密钥KAB 时,加密EAB 容易计算。 (2)知道密钥KAB 时,解密DAB 容易计算。 (3)不知道密钥KAB 时,由密文C=EAB( M )不容易推导出明文 M 。 以上三点要求说明密码系统设计的原则是:对合法的通信双方来说,加密和解密变 换是容易的;对密码分析员来说,由密文推导出明文是困难的。衡量一个密码系统的好 坏,当然应当以它能否被攻破和易于被攻破为基本标准。 理论上不可攻破的密码系统是一次一密,密钥只对一个消息进行加解密,之后丢弃不 用,每一条新消息都需要一个与其等长的新密钥。这就是著名的一次一密,它是不可攻破 的。但是在实际应用中,这种系统却受到很大限制。 ①分发和存储这样大的随机密钥序列(它和明文信息等长), 确保密钥的安全是很困 难的。 ②如何生成真正的随机序列也是一个现实问题。因此,人们转而寻求实际上不可攻 42 破的密码系统。 所谓实际上不可攻破的密码系统,是指它们在理论上虽然是可以攻破的,但真正要攻 破它们,所需要的计算资源如计算机时间和存储空间超出了实际上的可能性。例如,破解 某个密码系统需要耗费计算机机时200年,这个密码系统实际上非常安全。 密码编码学系统具有以下三个独立的特征。 (1)转换明文为密文的运算类型。所有的加密算法都基于两个原理:代换和置换, 代换是将明文中的每个元素(如位、字母、位组或字组等)映射成另一个元素;置换是将明 文中的元素重新排列。上述运算的基本要求是不允许有信息丢失(即所有的运算是可逆 的)。大多数密码体制,都使用了多层代换和置换。 (2)所用的密钥数。如果发送方和接收方使用相同的密钥,这种密码就称为对称密 码、单密钥密码、秘密钥密码或传统密码。如果收发双方使用不同的密钥,这种密码就称 为非对称密码、双钥或公钥密码。 (3)处理明文的方法。分组密码每次处理输入的一组元素,相应地输出一组元素。 流密码则是连续地处理输入元素,每次输出一个元素。 3.2 密码分析学 2. 密码分析是指试图找出明文或密钥的工作,通常目标是恢复使用的密钥,而不是仅仅 恢复出单个密文对应的明文,这样可以获得更多有价值的信息。攻击对称密码体制一般 有以下两种方法。 (1)密码分析学:密码分析学攻击通常分析加密算法的性质,利用明文的一般特征 或某些明密文对。破译者使用的策略取决于加密方案的固有性质以及破译者掌握的信 息。这种形式的攻击企图利用算法的特征来推导出特别的明文或使用的密钥。 (2)穷举攻击:攻击者对一条密文尝试所有可能的密钥,直到把它转化为可读的有 意义的明文。平均而言,获得成功至少要尝试所有可能密钥的一半。 如果上述任意一种攻击能成功地推导出密钥,那么影响将是灾难性的,将会危及所有 未来和过去使用该密钥加密的消息的安全。 首先考虑密码分析学,然后讨论穷举攻击。 基于密码分析者知道信息的多少,表3.表中唯密文攻 1概括了密码攻击的几种类型, 击难度最大。有些情况下,攻击者甚至不知道加密算法,但是我们通常假设对手知道。早 在1883年柯克霍夫斯(A.Kerchofs)在其名著《军事密码学》中就建立了一个重要原则: 密码算法即使为密码分析者所知,也应该无助于用来推导出明文和密钥。这一原则已被 人广泛接受,取名为柯克霍夫斯原则,并成为密码系统设计的重要原则之一。 原因是依赖加密算法本身的机密性来防范密码分析者的代价较高,一旦对手知道加 密算法则所有消息不再安全。重新设计加密算法并进行更换的成本也较大,通过密钥保 密而不是加密算法保密来防范密码分析相对容易,可以通过更换密钥加强机密性。与更 换算法的成本相比,更换密钥的成本也要小很多。 使用加密的优势在于,将对众多很长的明文保密转化为对少数的较短的密钥保密,而 后者显然容易得多。 43 表3.密码攻击的类型 1 攻击类型密码分析者已知的信息 唯密文攻击 ciphertextonly . 加密算法 . 要解密的密文 已知明文攻击 knownplaintext . 加密算法 . 要解密的密文 . 用(与待解的密文)同一密钥加密的一个或多个密文对 选择明文攻击 chosenplaintext . 加密算法 . 要解密的密文 . 分析者任意选择的一些明文,以及对应的密文(与待解的密文使用同 一密钥加密) 选择密文攻击 chosenciphertext . 加密算法 . 要解密的密文 . 分析者有目的地选择一些密文,以及对应的明文(与待解的密文使用 同一密钥解密) 选择文本攻击 chosentext . 加密算法 . 要解密的密文 . 分析者任意选择的明文,以及对应的密文(与待解的密文使用同一密 钥加密) . 分析者有目的地选择一些密文,以及对应的明文(与待解的密文使用 同一密钥解密) (1)唯密文攻击。密码分析者有一些消息的密文,这些消息都用同一算法加密。密 码分析者的任务是恢复尽可能多的明文,或者最好能推算出加密消息的密钥,以便可采用 相同的密钥解出其他被加密的消息。 已知 : C1=Ek (M1),C2=Ek (M2),…,Ci=Ek (Mi) 推导出:M1,M2,…,Mi,或者密钥k,或者找出一个算法从Ci+1=Ek (Mi+1)推导出 Mi+1 。唯密文攻击是最容易防范的,因为攻击者拥有的信息量最少。不过在很多情况 下,分析者可以得到更多的信息。分析者可以捕获到一段或更多的明文信息及相应密文, 也可能知道某段明文信息的格式等。例如,按照Postscript格式加密的文件总是以相同 的格式开头,还有,电子金融消息往往有标准化的文件头或者标志等。这些都是已知明文 攻击的例子。拥有这些知识的分析者就可以从分析明文入手来推导出密钥。 (2)已知明文攻击。密码分析者不仅可以得到一些消息的密文,而且也知道这些消 息的明文。分析者的任务是用加密消息推出用来加密的密钥或者推导出一个算法,用此 算法可以对用同一密钥加密的任何新的消息进行解密。 已知: M1,=Ek (M1),M2,Ek (M2),…,Mi,Ek (Mi) 推导出:密钥k,或者从Ci+1=Ek (Mi+1)推导出Mi+1 的算法。 与已知明文攻击紧密相关的是可能词攻击。如果攻击者处理的是一般分散文字信 息,他可能对信息的内容一无所知;如果他处理的是一些特定的信息,他就可能知道其中 C1C2=Ci= 44 的部分内容。例如,对于一个完整的数据库文件,攻击者可能知道放在文件最前面的是某 些关键词。又如,某公司开发的程序源代码可能含有该公司的版权信息,并且放在某个标 准位置。 (3)选择明文攻击。分析者不仅可以得到一些消息的密文和相应的明文,而且他们 也可以选择被加密的明文。也就是说分析者能够通过某种方式,让发送方在发送的信息 中插入一段由他选择的信息,一个例子是差分密码分析。这个比已知明文攻击更有效,因 为密码分析者能选择特定的明文块去加密,那些块可能产生更多关于密钥的信息,分析者 的任务是推出用来加密消息的密钥或者导出一个算法,此算法可以对同一密钥加密的任 何新的消息进行解密。 已知:M1,C1=Ek (M1),M2,C2=Ek (M2),…,Mi,Ci=Ek (Mi), 其中M1,M2,…, Mi 可由密码分析者选择。 推导出:密钥k,或者从Ci+1=Ek (Mi+1)推导出Mi+1 的算法。 一般来说,如果分析者有办法选择明文加密,那么他将特意选取那些最有可能恢复出 密钥的数据。 表3.选择密文攻击和选择文本攻击。它们在 1还列举了另外两种类型的攻击方法: 密码分析技术中很少用到,但是仍然是两种可能的攻击方法。 只有相对较弱的算法才抵挡不住唯密文攻击。一般地,加密算法起码需要经受得住 已知明文攻击。 除了前面介绍的密码分析学,另一种可能的攻击是试遍所有可能密钥的穷举攻击。 如果密钥空间非常大,这种方法就不太实际。因此,攻击者必须依赖于对密文本身的分 析,这一般要运用各种统计方法。使用这种方法,攻击者对可能的明文类型必须有所了 解,比如明文是英文文本或法文文本、可执行文件、Java源代码文件、会计文件等。 在已知密文/明文对时,密钥穷举攻击就是简单地搜索所有可能的密钥;如果没有已 知的密文/明文对时,攻击者必须自己识别明文,这是一个有相当难度的工作。值得说明 的是,穷举攻击并非指的是尝试所有可能的密钥。除非是明文已知的情况下,密码分析者 会尝试所有密钥,以确认所给的明文是否为真正的明文。如果消息仅仅是英文的明文,那 么很容易识别出明文。如果明文在加密前进行了压缩,那识别就很困难了。如果信息是 更一般的数据类型,如二进制文件并进行了压缩,那么识别就更难于自动实现了。因此, 穷举攻击还需要一些辅助信息,这包括对预期明文的某种程度的了解和自动区分明文和 密文的某种手段。 如果一个密码体制满足条件:无论有多少可使用的密文,都不足以唯一地确定密文 所对应的明文,则称该加密体制是无条件安全的。也就是说,无论花多少时间,攻击者都 无法将密文解密,因为他所需的信息不在密文里。除了一次一密(一次一密的具体内容将 会在以后的文中讲到)之外,所有的加密算法都不是无条件安全的。因此,加密算法的使 用者应挑选尽量满足以下标准的算法。 ①破译密码的代价超出密文信息的价值。 ②破译密码的时间超出密文信息的有效生命期。 如果满足了上述两条标准,则加密体制是计算上安全的,因为攻击者成功破译密文所 45 需的工作量是非常巨大的。对称密码体制的所有分析方法都利用了这样一个事实,即明 文的结构和模式在加密之后仍然保存了下来,并且在密文中能找到一些蛛丝马迹。随着 对各种对称密码体制讨论的深入,这一点将会变得很明显。对公钥密码体制的分析是依 据一个完全不同的假设,即密钥对的数学性质使得无法从一个密钥推出另一个密钥,在后 面章节中会详细介绍公钥密码体制。 试遍所有密钥直到有一个可用的密钥能够把密文还原成明文,这就是穷举攻击。我 们可以从这种方法入手,考虑其所需的时间代价。要获得成功一般需要尝试所有可能密 钥中的一半,表3.数据加密标准) 2给出了对于不同密钥空间所耗用的时间。DES( 算法 使用的是56位密钥,3DES使用的是168位密钥,AES(高级加密标准)的最短密钥长度 是128位。表中最后一行还列出了采用26个字母的排列作为密钥的代换密码的一些结 果。假设执行一次解密需要1μs,表中数据说明了对于不同长度密钥执行穷尽搜索所需 的时间。随着大规模并行计算机的应用,处理速度可能会高出若干个数量级。表3. 2最 后一列列举了每微秒执行100万次解密需要的时间。可以看出,DES算法已不再是安全 的算法。 表3.不同密钥空间耗用的时间 2 密钥大小(位) 密钥个数 每微秒执行一次解密 需要的时间 每微秒执行100万次 解密需要的时间 32 232=4.3×109 231μs=35.8min 2.15ms 56 256=7.2×1016 255μs=1142年10.01小时 128 2128=3.4×1038 2127μs=5.4×1024年5.4×1018年 168 2168=3.7×1050 2167μs=5.9×1024年5.9×1024年 26个字符的排列组合26!=4×1026 2×1026μs=6.4×1012年6.4×106 年 3.3 密钥管理学 2. 密码算法对密码系统的安全性有决定性的作用,但很多情况下,一个密码应用系统被 破解往往不是密码算法本身造成的,而是密码系统的密钥管理方案不当造成的。例如,将 密钥与加密算法不加保护地一起存储在计算机中,那么任何侵入该计算机的攻击者都能 得到密码算法和密钥,相应地任何加密消息都可以被破解。 随着互联网的发展,密码学在网络安全中得到了广泛的应用。由于互联网本身是不 可靠的,随时可能被攻击者监听、修改、重放数据,因此通信双方为了能达到安全通信的目 的,需要在互联网本身不安全这个前提下,对安全通信所使用的密钥进行协商和管理。根 据Kerckhofs假设,密码分析者知道所使用的密码体制,拥有除了密钥以外的所有关于 加密函数的全部知识。因此,密码系统的安全性完全取决于所使用的密钥的安全,密钥管 理是密码系统不可缺少的重要组成部分,在密码系统中起着根本的作用。密钥管理相当 复杂,既有技术问题,也有管理策略问题,从某种程度上密钥管理可以说是密码系统中最 重要、最困难的部分,然而密钥管理却往往是人们最容易忽视的地方。 46 密钥管理包括密钥的生产、装入、更换、分配、保护、存储、吊销、销毁等内容,其中分配 和存储是最棘手的问题。密钥管理主要包括以下内容。 (1)密钥生成。密钥生成是密钥管理的首要环节,密钥生成的主要设备是密钥生成 器,密钥生成可分为集中式密钥生成和分布式密钥生成两种模式。对于前者,密钥由可信 的密钥管理中心生成;对于后者,密钥由网络中的多个节点通过协商来生成。 加密算法的安全性依赖于密钥,如果使用了一个弱的密钥产生方法,那么整个加密系 统的安全性都很差。所以需要有一个较好的随机数生成器来生成强壮的密钥。 大部分密钥生成算法采用随机过程或者伪随机过程来生成密钥。随机过程一般采用 一个真随机数发生器,它的输出是一个完全不确定的值。伪随机过程一般采用噪声源技 术,通过噪声源的功能产生二进制的随机序列或与之对应的随机数。 (2)密钥的装入和更换。密钥可通过键盘、密钥注入器、磁卡、智能卡等设备和介质 装入。密钥的生命周期结束,必须更换和销毁密钥。密钥泄露后也必须对其进行销毁和 更新。 (3)密钥分配。密钥分配主要有两种模式:集中式分配和分布式分配。集中式分配 模式由一个可信的密钥管理中心给用户分发密钥,这种模式具有效率高的优点,但管理中 心容易成为攻击者的攻击目标,存在单点失效问题。分布式密钥分配模式,则由多个服务 器通过协商来分配密钥,该模式能极大地提高系统的安全性和密钥的可用性。如果一个 服务器被攻击,其他服务器还可以帮助被攻击的服务器恢复密钥,在灾难恢复方面具有 优势。 (4)密钥保护和存储。所有生成和分配的密钥必须具有保护措施,密钥保护装置必 须绝对安全,密钥存储要保证密钥的保密性,密钥应以密文形式出现。 (5)密钥的吊销。如果密钥丢失或因某种原因不能使用,且发生在密钥有效期内,则 需要将它从正常使用的密钥集中除去,称为密钥吊销。采用证书机制的公钥可以通过吊 销公钥证书实现对公钥的吊销。 (6)密钥的销毁。不再使用的旧密钥必须销毁,否则敌手可用旧密钥解密用该密钥 加密的文件,且利用旧密钥进行分析和破译密码体制。 如果对密钥进行分类,可将密钥分为主机主密钥、密钥加密密钥、会话密钥等类型。 (1)主机主密钥(hostmasterkey)。对密钥加密密钥进行加密的密钥称为主机主密 钥。它一般保存于网络中心、主节点或主处理器中,受到严格的物理保护。 (2)密钥加密密钥(keyencryptionkey)。在传输会话密钥时,用来加密会话密钥的 密钥称为密钥加密密钥,也称为次主密钥(submasterkey)或二级密钥(secondarykey)。 通信网络中各节点的密钥加密密钥应互不相同,在主机和主机之间以及主机和终端之间 传送会话密钥时都需要有相应的密钥加密密钥。 (3)会话密钥(sesionkey)。用于通信双方交换数据时使用的密钥。根据会话密钥 的用途,可分为数据加密密钥、文件密钥等。用于保护传输数据的会话密钥叫作数据加密 密钥;用来保护文件的会话密钥称为文件密钥。会话密钥可以由可信的密钥管理中心分 配,也可由通信方协商获得。通常会话密钥的生存周期很短,一次通信结束后,该密钥就 会被销毁。 47 现有密码系统的设计大都采用了层次化的密钥结构,这种层次化的密钥结构与对系 统的密钥控制关系是对应的。一个常见的三级密钥管理的层次结构如图3. 2所示。 图3.三级密钥管理的层次结构 2 密钥分级大大提高了密钥的安全性。一般来说,越低级的密钥更换越频繁,最低级的 密钥可以做到一次一换。低级密钥具有相对独立性,这样,它的泄露或者破译不会影响上 级密钥的安全,而且它们的生成方式、结构、内容可以根据协议不断变换。于是,对于攻击 者而言,密钥分级系统是一个动态系统,对低级密钥的攻击不会影响高级主密钥。密钥的 分级也方便了密钥的管理,使密钥管理自动化成为可能。 密钥还可以分散管理,如采用物理分散管理,将高层密钥保存在不同的地方,如 K = KR..KI, K 为高层密钥,KR 保存在密码机内,KI保存在密钥载体由用户保留,这样即使 密码机丢失,或用户密钥载体丢失,密码机内的信息仍然由 K 加密保护。这一思想可以 扩展到秘密共享机制,即使用秘密共享来分别保存主密钥。 3.传统密码技术 3 本节讨论的传统密码技术主要是指在计算机出现之前使用的加密方法,本节将对传 统密码学的典型方法进行简要的论述和总结,使读者对密码学的全貌有一个完整的印象。 这些传统的密码技术在现在的密码分析技术面前,可以被轻易地破解,已经没有太多的实 际意义。但传统加密技术使用的代换和置换技术的基本思想在现代密码算法设计中还有 广泛的应用,了解代换和置换技术的基本思想对理解现代密码学产生的背景、为今后研究 和改进现代密码系统提供了基础。 3.1 置换密码 3. 置换密码根据一定的规则重新安排明文字母,使之成为密文。常用的置换密码有两 种:一种是列置换密码;另一种是周期置换密码。下面给出两个例子,分别说明它们的工 48 作情况。 1 假设有一个密钥是type的列置换密码, 密钥type 表3.置换密码 例3.把明文we 3 arltgte如表3. eaoehr写成4列矩阵,3所示 。 按照密钥type所确定的顺序,按列写出该矩阵中的字母 , 3421 就得出密文 : wear rleralgewe tteaoh 顺序eall toge 例3.假设有一个周期是4的置换密码, 1, 2 其密钥是i= ther 2,3,i)=4,1。明文同上例, 4的一个置换f(3,2,加密时先将 明文分组,每组4个字母,然后根据密钥所规定的顺序变换如下: ①明文: M =wearealtogether ②密文:C=arewllae geot erht 置换密码因为有着与原始明文相同的字母频率特征而易被识破。如同列变换所示, 密码分析可以直接从将密文排列成矩阵入手,再来处理列的位置。双字母音节和三字母 分析方法可以派上用场。 多步置换密码相对来讲要安全得多,这种复杂的置换是不容易重构的。 3.代换密码 3.2 代换法是将明文中每一个字符替换成密文中的另一个字符,接收者对密文进行逆替 换就可以恢复出明文。如果把明文看作二进制序列,那么代换就是用密文位串来代换明 文位串。这里介绍两种代换密码,凯撒密码和单表代换密码。 1.凯撒密码 已知最早的代换密码是由JuliusCaesar发明的凯撒(Caesar)密码。它非常简单,就 是对字母表中的每个字母用它之后的第三个字母来代换,例如: .明文:metmeafterthetogaparty .密文:phhwphdiwhuwkhwrjdsduwb 注意到字母表是循环的,即认为紧随z后的是字母a。通过列出所有的可能来定义如 下变换: .明文:abcdefghijklmnopqrstuvwxyz .密文:defghijklmnopqrstuvwxyzabc 如果让每个字母等价于一个数值 : a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25 那么加密算法可以这样表达:对每个明文字母p,代换成密文字母C: 49 C=E(3,p)=(p+3)mod26 移位可以是任意整数k,这样就得到了一般的Caesar算法: C=E(p)p+k)mod26 k,= ( 这里 k 的取值范围为1~25 。解密算法是 : p=D(C-mod26 k,C)=(k) 如果已知某给定的密文是凯撒密码,那么穷举攻击是很容易实现的:只要简单地测 试所有的25 种可能的密钥。 凯撒密码的3个重要特征可以采用穷举攻击分析方法。 ①已知加密算法和解密算法。 ②需测试的密钥只有25 个。 ③明文所用的语言是已知的,且其意义易于识别。 在大多数网络情况下,假设密码算法是已知的。一般来说,密钥空间很大的算法使穷 举攻击分析方法不太可能成功。例如,第4章介绍的3DES 算法,它的密钥长度是168 位,其密钥空间是2168,或者说有大于3.50 种可能的密钥。 7×10 上述第三个特征也是非常重要的,如果明文所用的语言不为所知,那么明文输出就不 可识别。而且,输入可能按某种方式经过缩写或压缩,也就更不可识别了。例如,下面是 经过WINRAR 压缩之后的部分文本文件: 如果这个文件用一种简单的代换密码来加密(将字母集合扩充为不止包含26 个英文 字母), 那么即使用穷举攻击进行密码分析,恢复出来的明文也是很难识别的。 2. 单表代换密码 凯撒密码仅有25 种可能的密钥,远远不够安全。通过允许任意代换,密钥空间将会 急剧增大。回忆凯撒密码的对应:如果密文行是26 个字母的任意置换,那么就有26! 或 大于4×1026 种可能的密钥,这比DES 的密钥空间要大10 个数量级,凭直觉这样的密钥 空间应该可以抵挡穷举攻击了。这种方法称为单表代换密码,这是因为每条消息用一个 字母表(给出从明文字母到密文字母的映射)加密。攻击者尝试所有的4×1026 种可能密 钥的工作量显然太大了,有没有更好的攻击方法呢? 答案是更好的攻击方法仍然存在。如果密码分析者知道明文(例如,未经压缩的英文 文本)的属性,他就可以利用语言的一些规律进行攻击。为了说明分析过程,这里给出一 段文字。需要解密的密文是: PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQ 50 PBQWAQJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFA 首先把字母使用的相对频率统计出来,与英文字母的使用频率分布进行比较,参见 图3.4。3和图3. 图3.常见的英文字母使用频率 3 图3.密文中字母出现的次数 4 如果已知消息足够长,只用这种方法就已经足够了;如果这段消息相对较短,就不能 得到准确的字母匹配。将这种统计规律与图3.可以得出结论:密文字母中的 3比较, F或Q可能相当于明文中的E,但是并不能确定F对应E还是Q对应E。密文中的P、 W、B、H、P、T和X相对频率都比较高,可能与明文中的字母集{A,H,N,R,中 T,I,O,S} 的某一个相对应。相对频率较低的字母(M,R,S,K,U,Y)可能对应着明文字母集{B,J, K,Q,V,X,Z}中的某个元素。 据此我们可以从以下几种方法入手。可以尝试着做一些代换,填入明文,看一下是否 像一个消息的轮廓,更系统一点的方法是寻找其他的规律。例如,明文中有某些词可能是 已知的,或者寻找密文字母中的重复序列,推导它们的等价明文。 3的双 统计双字母组合的频率是一个很有效的工具。由此可以得到一个类似于图3. 51 字母组合的相对频率图。最常用的一个字母组合是TH 。而在密文中,用得最多的双字 母组合是PB,它出现了多次。所以可以估计P对应明文T,而B对应明文H。根据先前 的假设,可以认为F对应E。现在我们意识到密文中的PBF很可能就是THE,这是英语 中最常用的三字母组合,这表明我们的思路是正确的。 3.3 一次一密 3. 一次一密建议使用与消息一样长且无重复的随机密钥来加密消息,另外,密钥只对一 个消息进行加解密,之后丢弃不用。每一条新消息都需要一个与其等长的新密钥。一次 一密是不可攻破的,它产生的随机输出与明文没有任何统计关系。因为密文不包含明文 的任何信息,所以无法攻破。 下面的例子能够说明我们的观点。假设我们使用的是27个字符(第27个字符是空 格)的密码,但是这里使用的一次性密钥和消息一样长,请看下面的密文: ANKYODKYUREPFJBYOJTDSPLREYIUNOFDOIUERFPLUYTS 现在我们用两种不同的密钥解密。 (1)密钥1的解密结果: 密文ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS 密钥1 pxlmvmsydofuyrvzwctnlebnecvgdupahfzlmnyih 明文mrmustardwiththecandlestickinthehal (2)密钥2的解密结果: 密文ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS 密钥2 mfugpmiydgaxgoufhklmhsqrdqogtewbqfgyovuhwt 明文misscarletwiththeknifeinthelibrary 假设密码分析者已设法找到了这两个密钥,于是就产生了两个似是而非的明文。分 析者如何确定正确的解密(即正确的密钥)呢? 如果密钥是在真正随机的方式下产生的, 那么分析者就不能说密钥更有可能是哪一种。因此,没有办法确定正确的密钥,也就是 说,没有办法确定正确的明文。 事实上,给出任何长度与密文一样长的明文,都存在着一个密钥产生这个明文。因 此,用穷举法搜索所有可能的密钥,就会得到大量可读、清楚的明文,但是没有办法确定哪 一个才是真正所需的,因而这种密码是理论上不可攻破的。 一次一密的安全性完全取决于密钥的随机性。如果构成密钥的字符流是真正随机的,那 么构成密文的字符流也是真正随机的。因此,分析者没有任何攻击密文的模式和规则可用。 理论上,对一次一密已经讲得很清楚了。但是在实际中,一次一密提供完全的安全性 存在以下两个基本难点。 (1)产生大规模随机密钥有实际困难。任何经常使用的系统都需要建立在某个规则 基础上的数百万个随机字符,提供这样规模的真正随机字符是相当艰巨的任务。 (2)更令人担忧的是密钥的分配和保护。对每一条发送的消息,需要提供给发送方 52 和接收方等长度的密钥。因此,存在庞大的密钥分配问题。很难分发/存储和明文等长的 随机密钥序列。 (3)若有安全信道可传递每次不同、任意长的密钥序列,为何不直接用来传递明文呢? 因为上述这些困难,一次一密实际很少使用,主要用于安全性要求很高的低带宽信道。 3.4 转轮机 3. 多步置换得到的算法对密码分析有很大的难度,这对代换密码也适用。20 世纪20 年代,人们就发明机械加密设备用来自动处理加密,大多数是基于转轮的概念,机械转轮 用线连起来完成通常的密码代换。 5), 有26 个位 轮转机有一个键盘和一系列转轮(见图3.每个转轮是字母的任意组合, 置,并且完成一种简单代换。例如,一个转轮可能用线连起来以完成用K代换A,用W 代换D,用L代换T等,而且转轮的输出栓连接到相邻的输入栓。 图3.转轮机和其中的机械转轮 5 例如,有一个密码机,有4个转轮,第一个转轮可能用G代换B,第二个转轮可能用N 代换G,第三个转轮可能用S代换N,第四个转轮可能用C代换S,C应该是输出密文。 当转轮移动后,下一次代换将不同。为使机器更加安全,可以把几种转轮和移动的齿轮结 合起来。因为所有的转轮以不同的速度移动, n 个转轮的机器周期为26n。为进一步阻 止密码分析,有些转轮机在每个转轮上还有不同的位置号。 今天转轮机的意义在于它曾经给最为广泛使用的密码———数据加密标准DES 指明 了方向。第4章对DES 进行讨论。 3.5 电码本 3. 电视剧《潜伏》中会出现这样的镜头:当男主角余则成收到密电后,会拿出一本书对 密电进行解密,这本书就是加密解密使用的电码本,如果这本书被敌人知道了,密电中的 机密则会泄露。从字面中意义而言,传统的电码本密码就是像字典一样的书,包含单词和 其相应的码字。表3. 4给出了德国在第一次世界大战期间使用的一部著名电码本密码的 摘录。例如,要加密德文单词Fbur, 码字”4的电码 era整个单词被替换为5位“ 13605 。表3. 本用于加密。相应的还有一个将5位码字按照数字大小顺序排列的电码本,用于解密。 53 电码本密码属于代替密码,但是与简单代替密码有很大的区别,因为这里是对整个单词甚 至短语进行代替。 表3.immermann电报的加密中, 德国外交部 4展示的电码本被用于著名的Z在1917年, 部长ArthurZimmermann给身在墨西哥城的德国大使发送一个加密的电报(见图3.这份 密电文被英国截获,当时英国和法国正在同德国及其同盟国作战,而美国处于中立。 6), 表3.德国电码本摘录 4 Februar 13605 fest 13732 finanziele 13850 folgender 13918 Frieden 17142 Friedenschlus 17149 . . 明文密文 图3.德国Zmmran密电 6 iemn 俄国破译出了德国电码本的部分内容,并将一部分电码本送给英国。经过艰苦的分 析,英国恢复出了足够破译Zimmermann电报的电码本。电报陈述了德国政府计划开展 “无限制潜艇战”,并且预测到这个计划将导致美国卷入战争。因此,Zimmermann决定德 国应该试图拉拢墨西哥加入同盟并与美国作战,如图3.夺 7所示。德国对于墨西哥承诺“ 回其在德克萨斯州、新墨西哥州和亚利桑那州曾经失去的领土”。当解密后的Zimmerman 电报被公布给美国后,美国公众开始敌对德国;随后在Lusitania航线事件后,美国对德国 正式宣战。 最初,英国曾犹豫是否公布Zimmermann电报,因为英国害怕德国发现他们的密码 被破译以后就停止使用该密码。然而,通过在Zimmermann电报发送的同时期对其他电 报进行过滤分析,英国破译者发现还有Zimmermann电报的未加密版本被发送。英国随 后公布了同未加密版本电报内容相似的Zimmermann电报。于是德国就以为他们的电 码本密码没有问题,并在整个第一次世界大战中继续使用其加密敏感信息。 54 图3.用电码本解密的Zn电报 7 immerman 电码本和现代分组密码有一定的相关性,现代分组密码对明文使用复杂的算法产生 密文(反之亦然), 但是从宏观上来看分组密码都可以视为一个电码本密码,这里每个密钥 都确定一部不同的电码本。 习题 1. 假设已知使用凯撒密码,试从下面的密文恢复出明文 : VSRQJHEREVTXDUHSDQWU 2. 如果拥有一台每秒可以尝试240 次密钥的计算机,那么对于密钥空间为2128 进行密 钥的穷举搜索大概需要多长时间(以年为单位)? 3. 请简述密码学在计算机网络安全的重要作用。 4. 密码管理中使用层次化的密钥结构的作用是什么? 5. 设计一个电码本密码的计算机版本。该密码应包含许多可能的电码本,使用密钥 以确定使用哪个电码本对特定消息进行加密或解密。 55