应用密码学原理、分析与Python实现

版权信息

书名：应用密码学：原理、分析与Python实现

ISBN：978-7-115-63571-6

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版　　权

著    刘 卓 赵勇焜 黄领才

责任编辑 佘 洁

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

内容提要

本书主要介绍密码学领域的基本概念、理论和应用，让读者对密码学有全面的了解。本书分为四部分，共计 14 章。第一部分是基础背景知识，该部分主要介绍密码学的应用场景、数学基础，以及密码学理论与实践的区别。第二部分讲述对称密码学，该部分主要介绍古典密码学、流密码和分组密码。第三部分讲述非对称密码学，以 RSA、ElGamal、ECC 和格密码为代表的非对称密码也称公钥密码，是现代密码学的重要分支。第四部分讲述数据完整性，现代密码学也非常注重数据完整性，该部分主要介绍哈希函数、消息验证码及数字签名技术。

作者写作本书的目的是让尽可能多的读者了解和学习密码学，因此，任何希望深入了解密码学及其工作原理的读者都可以阅读本书，同时不会被过于深奥的数学原理所难倒。

前  言

为什么要写这本书

《孙子兵法》中提到，“知彼知已，百战不殆”，意思是在战争中，只有掌握对手的情报，了解对手的动态，才能百战百胜。其实无论是战场还是商场，不管是国家、社会还是团体、个人，在任何较量中，谁能掌握对手的情报，谁就掌握了制胜的关键。在当下，依靠密码学的智慧，以少胜多、以一则情报扭转一场战役的战局已经不再是神话。

进入 21 世纪以来，随着计算机技术的不断发展和互联网的广泛应用，网络信息安全面临着前所未有的危机和挑战。地区冲突和情报战争的不断升级，使得信息安全成为国家安全的重要阵地，不容忽视。

信息安全作为国家安全的重要组成部分，受到国家的高度重视。“没有网络安全就没有国家安全”。2022 年 10 月，中国共产党第二十次全国代表大会更是提出要推进国家安全体系和能力现代化，坚决维护国家安全和社会稳定。当今世界各国之间的网络攻击频仍，在这些看不见硝烟的战争中，信息安全已经成为一把 “达摩克利斯之剑”，悬在各国信息安全的战场之上。而密码学作为信息安全技术的支撑，就成了抵御达摩克利斯之剑的坚固盾牌。

本书作者为我国航空工业的从业人员。航空是国防和民生的重要组成部分，航空数据大部分属于敏感机密信息，一旦泄露，就可能给公众权益、企业利益、政令政策乃至国家安全等造成不同程度的损害。而数据泄露可能会发生在数据采集、传输、存储、使用、共享和销毁的任何环节中。为了防止数据泄露给第三方，在各环节中经常需要使用技术手段对其加以保护。其中最高效的技术手段就是加密。通过对数据进行加密，可以保证其完整性、保密性、可用性这三大安全要素。

过去，密码学只被用于特定的领域，应用范围并不广泛。但在网络信息高度发达的今天，数据已经成为关系各行各业生死存亡的高度机密。从国防单位到民营企业，乃至个人，都需要在网络中频繁使用大量数据，这也使得网络攻击频繁出现，手段日新月异。黑客群体也越来越系统化、专业化，有些甚至掌握了非常尖端的网络攻击技术。因此网络安全，特别是对数据的保护变得尤为重要。2022年，境外针对我国西北工业大学的网络攻击，就是对我国航空工业数据安全发起的一次猛烈冲击，这引起了我国航空工业乃至全社会对数据安全的思考和重视，也让越来越多的人对密码学产生了浓厚的兴趣。

各种新型加密算法层出不穷，使得非密码学专业的初学者理解加密算法变得越来越吃力。为了帮助读者快速了解密码学的工作原理，本书深人浅出地介绍了古典与现代密码学背后的数学原理，包括密码学的底层算法，并对重要的数学知识进行了详细推导和分析，还为读者推荐了相关文献，以加深读者对算法的理解。同时本书提供了大量例题和习题，便于读者进行验证和提高。

与其他密码学图书不同，本书加入了大量的例证和详细推导过程，以帮助读者理解加密算法过程，并着重强调实际使用中需要注意的细节。同时本书也给出了各类密码加密和解密过程的相关 Python/SageMath 代码，以降低读者理解加密算法的难度。还有少部分代码涉及运算技巧，优化了加密算法的速度，提高了效率。读者掌握了相关代码后，就能完全掌握这类密码。

本书介绍的大多数算法只需要读者拥有适当的数学背景，如基础的微积分、线性代数和概率论知识，如果读者有一定的编程经验则更有助于对本书的阅读和理解。对于一些较为专业和晦涩的材料，作者通过详细示例对其进行拆解，并对所涉及的专业数学知识进行简要处理，为读者扫清阅读障碍，将阅读门槛降至无需特殊专业背景即可理解的程度。通过阅读本书，读者将获得对加密算法和密码分析的深刻理解，以及相关的知识、工具和经验，继而自信地探索前沿的密码学主题。

读者对象

● 对密码学感兴趣的读者。作者写作本书的目的是让尽可能多的读者了解和学习密码学，因此，任何希望深入了解密码学及其工作原理的读者都可以阅读本书，而且不会被过于深奥的数学原理所难倒。

● 信息安全/密码学领域的用户和从业人员，包括但不限于关注数据安全的普通用户，在信息的产生、使用、传输过程中接触敏感信息的用户，正在将密码学技术应用于数据保护的信息安全从业人员，以及希望进一步了解数据安全的管理者。

● 高校学生。本书可以作为理科专业的密码学辅助阅读图书，作为对部分细节的补充；也可作为工科专业的密码学阅读图书。读者可以通过书中的示例迅速掌握算法，而无须钻研数学细节。

密码学是一门交叉学科，涉及不同领域的数学知识，包括但不限于数论、抽象代数、线性代数、概率论，同时还与计算机科学有交叉，如优化算法等。推荐大学二年级及以上的学生阅读本书，也非常欢迎对密码学感兴趣的读者将本书作为参考用书。

本书主要内容

本书分为四部分，共 14 章。

第一部分：基础背景知识。该部分主要介绍密码学的应用场景、数学基础以及密码学相关理论与实践。

● 第 1 章　密码学简介，对密码学简史、密码学概念、编码进行介绍。

● 第 2 章　数学基础，主要介绍密码学相关的数学背景知识，以数论和代数为主，以帮助读者理解本书中讨论的一些技术。

● 第 3 章　密码学中的信息理论，主要介绍香农在密码学方面的研究内容，以及信息论在密码学中的应用。

第二部分：对称密码学。该部分主要介绍古典密码学、流密码和分组密码，侧重研究它们的加密过程和分析过程。

● 第 4 章　古典密码学，主要介绍了古典密码学中的一些经典算法，包括凯撒密码、反切码、维吉尼亚密码、仿射密码、希尔密码，以及默克尔-赫尔曼背包密码的加密和解密算法，并详细描述了这些密码的分析方法。

● 第 5 章　流密码，主要介绍了 RC4 加密算法和祖冲之密码的加密和解密过程。

● 第 6 章　分组密码，主要介绍了经典的 DES、AES、SM4 加密算法的加密和解密过程。

第三部分：非对称密码学。非对称密码也称公钥密码，是现代密码学的重要分支。

● 第 7 章　RSA 加密算法，主要介绍了基于大数分解难题的 RSA 加密算法的加密和解密步骤，以及数种针对 RSA 密码系统的分析方法。

● 第 8 章　ElGamal 加密算法，主要介绍了基于离散对数难题的 ElGamal 加密算法的加密和解密步骤，以及数种针对 ElGamal 密码系统的分析方法。

● 第 9 章　椭圆曲线密码，主要介绍了基于离散对数难题的椭圆曲线加密算法，详细描述了它的加密和解密步骤，以及数种针对椭圆曲线密码系统的分析方法。

● 第 10 章　格密码，主要介绍了基于 SVP 和 CVP 的格密码系统，详细描述了它的加密和解密步骤，以及可能的分析方法。

● 第 11 章　全同态加密，全同态加密突破了传统密码算法的限制，让密码学的应用变得更加广泛。本章主要介绍了同态、全同态加密的概念，描述了第二代全同态加密算法的步骤和示例。

第四部分：数据完整性。现代密码学也非常注重数据完整性，该部分主要介绍哈希函数、消息验证码及数字签名技术。

● 第 12 章　哈希函数，主要介绍了 MD2、MD4、SHA 系列哈希函数的加密算法，并简单介绍其发展历史及安全性验证。

● 第 13 章　消息验证码，主要介绍了消息验证码的应用场景与安全性分析。

● 第 14 章　数字签名技术，主要介绍了基于公钥密码学的数字签名应用场景和实例。

对于初学者，建议按照章节顺序阅读本书。对于有一定数学基础的读者，可以跳过介绍数学的有关部分，或者选择感兴趣的章节阅读。

勘误和支持

由于作者水平有限，加之本书内容具有极强的专业性且相关技术发展日新月异，书中难免存在不尽完善之处。如果你对本书有任何宝贵的意见和建议，欢迎通过邮箱 ethanliuzhuo @outlook.com 来信进行交流探讨，作者将不胜感激。

致谢

我要特别感谢我的妻子刘逸云教授和我可爱的女儿们，她们的支持和鼓励促使我完成了本书的写作。特别是我的妻子在写作上给予我许多建议，不仅参与了本书的内容设计和结构安排，还对本书进行了仔细的校对和修改。在此我要向她表示诚挚的谢意。

同时，特别感谢中国航空工业集团有限公司对本书的大力支持。本书的另外两位作者赵勇焜、黄领才在本书的写作过程中做出了巨大的贡献，为本书的顺利完成和最终质量的提高提供了重要的帮助。赵勇焜在本书的初稿阶段就加人了团队，并编写了第 2、3、14 章,使得本书的内容更加系统和严谨。黄领才总师拥有非常丰富的航空从业经验，是本书的技术顾问，为我们提供了大量宝贵的指导和建议，还协助作者团队联系了多位业内专家，为本书提供了不少实用案例和技术支持。在此，我要向两位合作者表示最真挚的感谢和敬意。非常感谢人民邮电出版社的余洁老师及其他参与本书出版工作的编辑老师所做的努力和付出，他们的专业素养和敬业精神让我深感钦佩和感激。在他们的帮助下本书得以顺利出版，而我也从中收获了非常宝贵的经验和知识。特别感谢买尔哈巴・买买提明、彭瑾、陈云天、刘慧以及一众知乎网友指出本书初稿中出现的错误，并对内容深度提出了非常有用的建议。

谨以此书献给我最亲爱的家人，以及众多热爱密码学的朋友。路漫漫其修远兮，吾将上下而求索!

刘　卓

第一部分　基础背景知识

在漫长的人类历史长河中，密码学作为一门古老而神秘的学科，蕴含了人类对保密通信的渴望和破解谜团的挑战。它的起源可以追溯到古代文明，当时人们已经开始使用简单的替换密码来隐藏信息了。古典密码学阶段是密码学历史的重要篇章。在这个时期，人们开始创造各种方法来保护信息。随着时间的推移，密码学越来越复杂且深奥。在文艺复兴时期，人们开始使用更加复杂的密码系统。然而，真正的密码学革命发生在 20 世纪。随着计算机技术的迅猛发展，密码学迎来了一个新的时代。现代密码学的出现与信息论的诞生有着密切的联系。香农的信息论为密码学提供了新的理论基础。信息论引入了熵的概念，提供了衡量密码系统安全性的工具。基于信息论的密码学方法，如对称加密算法和非对称加密算法，极大地推动了密码学的发展。

随着互联网的兴起，密码学的重要性变得更加突出。安全通信和保护个人隐私成为当今数字时代的迫切需求。现代密码学不仅关注加密算法的设计和破解，亦涵盖密码协议、数字签名、身份认证等方面。它为人们的电子交流提供了坚实的保护，保证了信息的机密性和完整性，并能提供认证和不可否认性。

密码学的历史发展见证了人类对于保密通信的追求。从古代的替换密码到现代的复杂加密算法，密码学在保护隐私和信息安全方面发挥着不可或缺的作用。

第 1 章　密码学简介

密码在英文中对应有两个单词，一个是 password，另一个是 cipher。对于大部分人来说，日常生活中所接触的密码是 password，比如手机解锁密码、计算机解锁密码、保险箱密码、网站登录密码、银行卡密码和网络交易密码等，这些是设备用来证明用户可以访问信息或者授权的秘密字符串。它可以是一串数字或一串字母，也可以由一串数字加字母或者其他特殊符号组合而成，甚至可以是人的指纹或者面部，主要用于确认用户的身份，通常还需要与用户名结合起来使用。而密码学研究的密码，通常指的是 cipher，主要是在保密通信中对所传递的信息进行加密，从而确保信息不被发送方和接收方以外的第三方知晓。 cipher 通常是一套复杂的密码系统，通过加密数据来保证数据的安全。

密码学 (Cryptology) 一词源自希腊文 kryptós 及 logos，直译即为“隐藏”及“信息”之意。根据《辞海》的解释，密码主要是指“按特定法则编成，用以对通信双方的信息进行明密变换的符号”。换句话说，密码是通过某种可逆的信息编码的方式，把真实信息转化为一种除通信双方外，第三方无法理解的信息。

密码学是研究以加密形式发送信息的方法，只有掌握此加密技术的特定人群才能破解加密，从而获得有效信息。密码学是一门既古老又年轻的学科，在数千年的发展历史中，经历了古典密码学、近代密码学和现代密码学 3 个阶段。古典密码学主要关注信息的加密过程和传递过程，以及研究对应的破译方法；而近代密码学和现代密码学不只关注信息传输时的保密问题，还涉及信息完整性和信息发布的不可否认性，以及在分布式计算中产生的来源于内部和外部的攻击的所有信息安全问题。

本章将介绍密码学简史，描述密码学最早期的应用场景，以及现代密码学发展的重要节点；同时介绍现代密码学的一些基本概念，并列出密码学的基本要素、基本原则及密码分析方法，帮助读者掌握一定的编码知识，为后续阅读做好充分的准备。

1.1　密码学简史

1.1.1　古代密码学发展

中国古代很早就有使用密码的传统。《孙子兵法》有言：“知彼知已，百战不殆；不知彼而知己，一胜一负；不知彼，不知已，每战必殆。” ^[1]知彼就是了解对手的实力强弱、作战计划、战略方针等信息，情报的数量及准确性甚至可以直接决定战争的胜负。战争历来是使用密码最频繁的地方，比如 “对口令” 就是密码校验的过程。因此中国古代的军队中也拥有不少巧妙、规范和系统的保密通信和身份认证方法。比如作为调遣军队凭证的虎符，就是中国古代非常经典的身份认证方法之一。春秋战国时期，魏国信陵君正是通过窃取魏王的虎符，在通信不发达的当时完成了以密码确认身份信息的过程，从而夺取兵权，率兵大破秦军，解了赵国邯郸之围。

春秋战国时期的兵书《六韬・龙韬・阴符》^[2]中也介绍了中国古代战争中君王与征战在外的将领是如何进行保密通信的。武王问太公，假如军队深入敌后，遇到紧急情况，该如何保持密切联系？太公回答：使用阴符进行秘密联络。阴符共有 8 种。

1）长一尺的符，表示大获全胜，摧毁敌人；

2）长九寸的符，表示攻破敌军，杀敌主将；

3）长八寸的符，表示守城的敌人已投降，我军已占领该城；

4）长七寸的符，表示敌军已败退，远传捷报；

5）长六寸的符，表示我军将誓死坚守城邑；

6）长五寸的符，表示请拨运军粮，增派援军；

7）长四寸的符，表示军队战败，主将阵亡；

8）长三寸的符，表示战事失利，全军伤亡惨重。

若奉命传递阴符的使者延误传递，则处死；若阴符的秘密被泄露，则无论是无意泄密者还是有意，传告者都将被处死。只有国君和主将知道这 8 种阴符的秘密。这就是不会泄露朝廷与军队之间相互联系的内容的秘密通信语言。敌人再聪明也不能识破它。

正是因为阴符的可靠、有效及保密性，后世继续对阴符进行了传承和改进，才有了“符契”和“阴书”等高阶形式。而 “符”在实际使用中，作为凭证，是由竹子做的，并做成两部分，使用时一分为二，验证时合二为一。只有同一“符”的两部分才能完美地合在一起，这就是常用词 “符合”的来历。

后世的军事家对情报传输做了更多的改进。宋朝天章阁待制曾公亮和工部侍郎丁度在编著《武经总要》时，对阴符做了改进。《武经总要》是中国古代著名的军事著作^[3]，是中国第一部由官方主持编修的兵书。在该书前集第 15 卷中有“符契”“信牌”和“字验” 3节，专门介绍了军队中秘密通信和身份验证的方法，如图 1-1 所示。“符契” 源于秦汉时期的调兵虎符，“符”用于朝廷调遣地方军队，“契”为上下两段鱼形，是军队主将向部属调兵的凭证。“符契” 由主将掌握，并且使用 “符契” 后，必须由专人书面记载使用记录，再由专人押递照验。

图1-1　《武经总要》秘密通信方法

“信牌”主要用于两军阵前交战时，传送紧急命令，初期用一分两半的铜钱，后来则用可以写字的木牌。

“字验”是以诗词为载体的军事通信“密码”，类似于现代军队使用密码本进行通信。《武经总要・制度十五・字验》记载了使用方法，即事先将要联络的事项以术语的形式编排好次序，将领们平时均加以熟记，每次作战之前，主将与每个受命出战的副将约定一首无重复的五言律诗为“字验”。若有事报告，就随意写成一封书信，将要报告之事的次序对应该诗中的第几个字，然后在普通书信中的该字旁加一记号即可。

例如，《武经总要・制度十五・字验》记载其规定联络事项的术语及次序是：（1）请弓； （2）请箭；（3）请刀；（4）请甲；（5）请枪旗；（6）请锅幕；（7）请马；（8）请衣赐；（9）请粮料；（10）请草料；（11）请车牛；（12）请船；（13）请攻城守具；（14）请添兵；（15）请移营； （16） 请进军；（17）请退军；（18）请固守；（19）未见贼；（20）见贼讫；（21）贼多；（22）贼少； （23）贼相敌；（24）贼添兵；（25）贼移营；（26）贼进兵；（27）胧退军；（28）贼固守；（29）围得贼城；（30）解围城；（31）被贼围；（32）贼围解；（33）战不胜；（34）战大胜；（35）战大捷； （36）将士投降；（37）将士叛；（38）士卒病；（39）都将病；（40）战小胜。

假设主将与副将规定使用《使至塞上》一诗作为“字验”。《使至塞上》共 40 字，无重复，符合要求。《使至塞上》全文如下：

单车欲问边，属国过居延。

征蓬出汉塞，归雁入胡天。

大漠孤烟直，长河落日圆。

萧关逢候骑，都护在燕然。

假若副将在战争进行中发现敌军增援后，军队被包围了，想把第 24 项和第 31 项军情报告给主将，在报告中就需要设法写进“烟”和“萧”这两个字，并在这两个字旁边做好标记，如点一个黑点或洒一滴水等。主将看到后，想请副将坚守再解围城，那么在回复中，主将也需要设法写进 “入” 和 “圆” 这两个字并做好标记。主副将之间就完成了沟通，即使被敌人截获，因为古代诗词无数，信使也不知道这封信使用了哪首诗，因此无法破译。相比阴符，它所能表达的军事状况更多，更加方便主将做出决策。后来李淑又将五言律诗改为七言绝句，使用了传播范围不那么广的民间绝句，进一步加强了军事情报传递的安全性。

明朝抗倭名将戚继光在战场上使用了反切码作为加密手段。反切是一种注音方法，戚继光利用 “反切注音方法”，编写了密码本。通过该密码本，只有我方的情报人员和将领知道信息的真实含义，传递人员和普通士兵无从知晓。

明末清初著名的军事理论家揭暄所著的《兵经百言》中也详细介绍了军队中的秘密通信方法。《兵经百言》的《术篇・传》下有论述：军队分开行动后，如相互之间不能通信，就要打败仗；如果能通信但不保密，则也要被敌人暗算。所以除了用锣鼓、旌旗、炮声、骑马送信、传令箭、燃火、烽烟等联系手段，两军相遇，还要对暗号。当军队分开有千里之远时，宜用机密信进行通信。机密信分为 3 种形式，即改变字的通常书写或阅读方式；隐写术；不把书信写在常用的纸上，而是写在特殊的、不引人注意的载体上。使用这些通信方式连送信的使者都不知道信中的内容，但收信人却可以接收到信息。由此可见，在中国古代战场上，秘密通信的受重视程度是非常高的。

密码不仅在中国战场上使用频繁，在国外战争中也是如此，著名的凯撒密码就是古罗马时期为了确保在战争中进行有效、可靠的秘密通信而发明的。根据苏维托尼乌斯的《罗马十二帝王传》：如果需要保密，信中便用暗号，也就是改变字母顺序，使局外人无法组成单词。如果想要读懂和理解它们的意思，得用第 4 个字母置换第字母，即以 D 代 A，以此类推。当时的人们还没有办法破解这样的密码，直到公元 9 世纪阿拉伯的阿尔・肯迪才发现可用频率分析来破解凯撒密码，他将方法写在了《破译加密信息手稿》一书中。

大约在公元前 700 年，斯巴达人使用一种叫作“Scytale”的圆木棍进行保密通信，它也被称作密码棒，如图 1-2 所示。它使用起来很简单，把长条带状的羊皮纸缠绕在一根圆木棍上，然后写上想要传达的信息，写完后从圆木棍上解下羊皮纸，上面的字符就被打乱顺序了。只有再以同样的方式将纸缠绕到同样粗细的圆木棍上，才能看明白所写的内容。

图1-2　Scytale

1.1.2　近代密码学发展

1.“齐默尔曼电报”事件

近代密码学主要是指从第一次世界大战到 1976 年这段时期的密码发展阶段。

19 世纪初，电报的发明极大地加速了信息的流通，也使得远距离快速传递信息成为可能。1893 年，尼古拉・特斯拉（Nikola Tesla）在美国密苏里州圣路易斯首次公开展示了无线电通信，标志着人类正式进人无线电时代，使得人们可以远距离进行实时通信。在分秒必争的战争中，军事指挥官可以及时了解前线信息并给出相应及时的部署。

因为无线电不像有线电话线可以专线传输，在一定范围内，无线电是以广播的形式播放的，任何人包括敌人都可以收到无线电信息从而进行应对。因此如何对无线电传送的信息进行加密迫在眉睫。随着第一次世界大战的爆发，对编码和解码人员的需求急剧上升，一场秘密通信的全球战役打响了。第一次世界大战进行到中后期，英国从事密码破译的机构 “40 号办公室” 利用缴获的德国密码本破译了著名的“齐默尔曼电报”(Zimmermann Telegram)，改变了战争进程，如图 1-3 所示。

在第一次世界大战爆发之初，美国采取了中立态度，并没有参加欧洲战事。英国为了让美国加入战争，监听了整个大西洋的海底电缆，其中就截获了包括齐默尔曼电报在内的一系列电报。齐默尔曼电报是由德国外交部长发送给德国驻墨西哥大使的，其内容大致是德国想让墨西哥与自己结盟，一起对抗美国。因为电报传输必须通过大西洋电缆，所以该电报被英国截获。结合之前在战场上获得的密码本，英国在很短的时间内破译了密码信息。看到电报内容的英国人异常兴奋，因为他们一直想把美国卷入战争，但苦于没有机会，现在机会终于来了。于是英国向美国转交了这份电报，该电报激怒了美国，使整个美国相信德国是美国的敌人，就在齐默尔曼电报发送后的 3 个月，美国加入了战争，可以说信息的保密程度直接决定了战争的走向和命运。这次破译也由此被视为密码学历史上一次经典的密码破译案例。

图1-3　齐默尔曼电报

2. Enigma 密码机

失败的德国人痛定思痛，认识到了密码在战争领域的重要性，且之前发明的密码不再安全，因此迫切需要一个安全性更高的密码系统。于是德国人在1919年发明了 Enigma （恩尼格玛）密码机，它的设计结合了机械系统与电子系统，被证明是当时最为可靠的加密系统之一，如图 1-4 所示。作为看似不可破译的密码机器，其密码组合约有 个之多，如此庞大的密码组合使得 “二战” 期间德军的保密通信技术遥遥领先于其他国家。盟军在很长一段时间内无法了解德军的部署，因而在战争初期迅速溃败。德国海军使用该密码系统区分了大西洋运输线上的德国潜艇和他国运输船，通过精准打击切断了盟军的海上运输线，想迫使英国在战争中做出让步。

图1-4　Enigma 密码机

20 世纪计算机科学迅猛发展，电子计算机和现代数学方法为破译者提供了有力的武器。1941 年，英国人阿兰・麦席森・图灵（Alan Mathison Turing）带领200名专业人士发现了 Enigma 密码的漏洞，即明文字母加密后不会是它本身，从而使用计算机破译了德国 Enigma 密码系统。这使英国海军得以提前了解德国潜艇部署，并设下埋伏以吸引德军火力，缓解了运输中可能遇到的压力，扭转了之前的被动局面，逐渐在 “二战”的大西洋航运中占据上风。

3. 太平洋战争情报战

1941 年 12 月 7 日清晨，日军对美国夏威夷珍珠港海军基地进行偷袭，美军官兵伤亡惨重。珍珠港海军基地几乎被摧毁，整个太平洋舰队也完全瘫净。这次偷袭是太平洋战争的导火索，也促成了美国直接参加第二次世界大战，世界反法西斯联盟对德、意、日的联合作战拉开了新的序幕。

美军在珍珠港的惨败在很大程度上是由于美国对日本海军偷袭珍珠港的情报不重视，对情报的破译也很随意，使得日军仅以极微弱的代价就给美国海军造成了不可估量的重创。值得一提的是，日军以极其巧妙的方式对情报进行加密，联合舰队偷袭珍珠港时全程无线电静默，只以民用广播发的古诗作为进攻指令。

在此之后美国开始高度重视日本海军在太平洋的情报传递，并通过密码破译对情报进行分析，进而掌握了日本海军的动向和意图，在随后展开的太平洋海战中取得了一次次改变历史进程的胜利。

4. 雅德利

抗日战争期间，为了迫使中国投降，日本对重庆进行了持续数年的大轰炸，史称“重庆大轰炸”。重庆是有名的雾都，大多数的天气其实是不适合飞机飞行的。然而中国情报部门发现，日本轰炸重庆时都是晴天，绝不会无功而返，因此怀疑有间谍在重庆给日本人通风报信，但苦于找不到间谋。于是中国情报部门邀请美国人雅德利（见图 1-5）来重庆帮助找出间谍。

图1-5　赫伯特・奥斯本・雅德利

雅德利的全名是赫伯特・奥斯本・雅德利（Herbert Osborn Yardley），他是美国密码学之父，出生于印第安纳州沃辛顿。他自小就有着非同寻常的数学天赋， 13 岁就从身为铁路车站站长的父亲那里学会了如何收发电报，从此对电报编码产生了浓厚兴趣。数年后，雅德利通过考试，成了一名美国政府的机要员，专门负责电文的收发、转译等工作，他卓越的工作能力受到了美国政府的赏识。1917年，雅德利牵头组织成立了第一间 “美国黑室”——军情八处，该黑室是美国国家安全局（National Security Agency，NSA）的前身。后来由于美国政府内部重组，新上任的领导对军情八处并不感兴趣，就解散了该处。雅德利在事业上瞬间跌人深谷，并在很长一段时间内靠写小说维持生活。“二战”初期，生活上不得志的雅德利接受了中国的邀请，担任中国情报部门的顾问。

其间，中国情报部门抓捕了包括“独臂大盗”在内的一系列间谍，这些人中不仅有军队系统的，也有情报部门内部的，甚至有政府高层的。不过随着越来越多的间谍被抓获，雅德利的身份也被慢慢公开，待在中国变得不再安全，因此他返回了美国。

返回美国后，雅德利写下了回忆录《中国黑室》，但遭到美国政府的封杀。雅德利于 1958年病逝于美国华盛顿。1999年，其回忆录《中国黑室》终于被公开，雅德利的事迹才在中国慢慢传开。

可以说，密码学的发展直接影响了 “二战”的战局。

5. 密码本密码

密码本密码实际上是一种替换密码，通过用密码本中的字来代替某个信息进行加密。关于密码本密码的应用场景，最为人熟知的就是各个影视剧中所出现的译电员翻译一组数字，写成内容后交给上级的场景。

由于无线电通信的技术瓶颈，无线电发明后很长一段时间内无法直接接收对方的语音信息，只能将语言通过编码形式传给对方，对方再用相同的编码方式翻译回来，这就是译电员的工作。英语是表音文字，很简单，如果不用加密，通过摩斯电码即可传给对方。但作为表意文字的中文就没那么容易了，汉语拼音直到“二战”以后才被发明出来，因此在 “二战”前，人们只能给汉字进行编码，将每个汉字的四角分别用 4 位数字代替，再用摩斯电码发送，这也是中文密码本的来源。这种四角码其实从清朝末期就开始使用了，康熙字典就是使用四角码查阅汉字的。

最早的一本中文电码是法国人编写的《电报新书》，后来在此基础上，中国人编著了《中国电报新编》，作为通用标准开始使用。但是这仅仅被用于不需要加密的民间通信，在外交、军事等信息保密等级较高的领域则完全行不通。于是行业内人员都使用自己的密码本作为加密的材料进行通信。中文密码本如图 1-6 所示。

图1-6　中文密码本

1.1.3　现代密码学发展

密码本是一种特殊的非通用编码本，通信双方秘密约定某本书，按页码、行数、字数将汉字译为数字后发送。它可以是自己写的密码本，也可以是公开发售的某本读物。使用前者的好处是密码本一旦被销毁，就再也不可能破译密文，坏处则是密码本的传输困难，容易在传输过程中被对方情报机构拦截。若选择公开发售的书籍，需要选择同版号同版次印刷的，以保证密码的准确性。这种方式的好处很多，一方只需要告诉另一方是什么书就行，然后在当地获取，不需要进行密码本的传输；坏处则是一旦对方情报机构知道是哪本书，则密码就会被破译，从而将情报彻底地暴露在敌方面前。

密码本在通信量少的情况下，安全性非常高，攻击者很难发现其规律。但是一旦通信量大，攻击者就会根据信息冗余，猜出这本书是哪一类的书籍，进而破译密码。

太平洋战争时期，日军曾先后有两艘潜艇触礁沉没。美军发现后立即派出部队，对这两艘沉没的潜艇进行了彻底搜寻，并在潜艇残骸中找到了日军密码本。正是依靠该密码本，美军情报部门才得以在极短时间内掌握了日本密码编制的方法。前文所列举的日本海军司令山本五十六的行踪被泄露，就是美方情报人员根据该批密码本对日军情报进行破译后得到信息的案例。不过令人意外的是，日军仍然坚信他们的密码本没有外泄，日军方面认为山本五十六所乘飞机被美军击落只不过是偶然事件。

我国关于密码本的历史最早可以追溯到宋朝。北宋时期的《武经总要・字验》是目前可考究的中国最早的军事密码本。

现代密码学的发展与计算机技术、电子通信技术密切相关。在这一阶段，密码理论得到了蓬勃发展，密码系统的设计与分析互相促进，出现了大量的加密算法和各种分析方法。除此之外，对密码的使用扩张到各个领域，出现了许多通用的加密标准，从而促进了网络和技术的发展。

在这里，不得不介绍现代密码学奠基人之一———克劳德・艾尔伍德・香农 (Claude Elwood Shannon）博士。香农毕业于麻省理工学院，是一位非常著名的数学家、电子工程师和密码学家，被誉为信息论的创始人。在 “二战”期间，他为破译敌方密码做出了突出贡献。

香农于1948年发表了一篇著名的论文 “A Mathematical Theory of Communication” （通信的数学理论）^[4]。该文从研究通信系统传输的实质出发，对信息做了科学的定义，并进行了定性和定量的描述，是现代信息论的基础。1949 年，香农又发表了一篇著名论文 “Communication Theory of Secrecy Systems” (保密系统的通信理论) ^[5]，把已有数千年历史的密码学推向了基于信息论的科学轨道，它也是现代密码学的理论基础之一。但论文发表之初并没有被广泛应用，直到数十年后分组密码诞生，才显示出它的价值。

1976 年，惠特菲尔德・迪菲（Whitfield Diffie）和马丁・爱德华・赫尔曼（Martin Edward Hellman）发表论文《密码学的新方向》^[6]，提出了 “公钥密码” 概念，开辟了公钥密码学的新领域。密码学的历史在此刻一分为二，分为对称密码学和非对称（公钥）密码学。在此之前，所有的密码系统都是对称的。可以说，没有对公钥密码学的研究，就没有现代密码学。

1977 年，美国麻省理工学院的 3 位教授提出了 RSA 密码算法^[7]，标志着首个较完善、无明显弱点的公钥密码算法的诞生。这是密码学史上的重要标志性事件。此后，ElGamal、椭圆曲线密码及格密码等公钥密码相继被提出，现代密码学进入一个新的快速发展时期。

1978年，数据加密标准（DES）分组密码被 IBM 公司提出，DES 的出现使密码学得以从政府走向民间。DES 对于分析和掌握分组密码的基本理论与设计原理具有重要参考意义，其设计思路被后续的对称密码算法所参考。基于安全、可靠、速度快等特点，对称密码系统在今天仍然被广泛使用，政府、金融等领域都在使用对称密码算法。

此后，中国、美国、欧盟等国家都加大了对密码学的研究。对称密码学领域相继出现了 SM4、AES 等算法，非对称密码学领域相继出现了 SM2、ECC 等算法，研究人员也开始关注量子密码、格密码等，后量子密码等前沿密码技术逐步成为研究热点。

1.2　密码学概念

1.2.1　密码学的基本要素

1. 机密性 (Confidentiality)

确保数据不会被未经授权的用户查看。加密是实现机密性要求的常用手段，也是密码学提供的最基本的安全服务。

2. 认证 (Authentication)

它有两个子任务。

● 身份认证。确保用户的身份信息是真实可靠的。

● 信息认证。确保信息来源的真实性。

3. 完整性 (Integrity)

确保信息没有以未经授权的方式被更改，其中包括意外事件和故意事件，例如停电造成的网络中断导致数据上传不完整或者攻击者篡改信息。密码学可提供一些方法来检测信息是否被篡改。

4. 不可否认性（Non-repudiation）

确保无论是发送方还是接收方都不能抵赖已传输的信息。换句话说，不可否认性是指确保信息的发送方不能向第三方否认他发送了这些数据。

机密性、认证、完整性和不可否认性这 4 点构成了密码学的基本要素，是密码学的基石。在设计密码及对密码的安全性进行测试时都会把以上基本要素作为考虑的重点，全面地思考所面对的问题，如图 1-7 所示。

1.2.2　密码学的基本原则

随着 Enigma 密码被破译，人们才意识到其实真正保证密码安全的重点往往不是算法，而是密钥管理。即使算法外泄，但只要密钥保密，密码就不会失效。这也称为柯克霍夫原则：即使密码系统的任何细节都已公开，只要密钥未泄露，则该密码系统也应是安全的。

在密码学领域，用于解决复杂问题的步骤通常称为算法（Algorithm）。从明文转密文的方法称为 “加密算法”；从密文转明文的方法，则称为 “解密算法”。加密、解密算法合在一起统称为密码算法。

在了解具体算法之前，首先需要了解一些关于密码学的基本概念。

图1-7　密码学基本要素

● 明文 (Plaintext)：加密前的信息，需要使用某种密码对其进行变换，以隐藏信息。用 表示，该信息只有通信双方能看到。

● 密文 (Ciphertext)：加密后的信息，经过变换后，该信息不能被非授权者所知。用 表示，该信息所有人都能看到。

● 加密 (Encryption)：通过特定的加密技术将明文转化为密文的行为。

● 解密 (Decryption)：由掌握加密技术的特定人群将密文转化为明文的行为。

● 发送方/发件人 (Sender)：例如后文例子中的 Alice。

● 接收方/收信人 (Receiver)：例如后文例子中的 Bob。

● 攻击者/拦截者（Attacker）：例如后文例子中的 Eve。

● 密钥 (Key)：用 表示，密钥通常是一系列数字或符号，发送方采用密钥来加密信息，接收方通过相同或不同的密钥来解密信息。只使用一次的密钥称为一次性密钥。

● 密钥空间 (Key Space)：密钥的所有可能，或解密密钥的可能数量。对于一个安全的密码系统，其密钥空间须能抵御穷举攻击。

Alice 和 Bob 最早出现在1978年 Rivest 等 3 人发表的论文 “A method for obtaining digital signatures and public-key cryptosystems”（一种实现数字签名和公钥密码系统的方法）^[7]中。在此之前，密码学领域一般用 A 表示数据发送方，用 B 表示数据接收方。相对于冰冷的 A 和 B，Alice 和 Bob 更加人性化，因此在密码学界广泛使用，可以说他们是密码学界的 “李雷” 和 “韩梅梅”。不过实际使用过程中，Alice 和 Bob 并不一定是人，在大多数情况下，Alice 是一台计算机，Bob 是一台网络服务器，它们之间互相通信。不过 Eve作为攻击者经常是一个人。Alice 和 Bob 之间互相通信的流程如图 1-8 所示。

图1-8　密码流程

在相关书籍或文献中，还有其他几种身份，如 Mallory、Trent、Victor。Mallory 通常指主动攻击者，它会进行妨碍通信、伪造信息等操作；Trent 则指可信的第三方，进行中继等操作；Victor 指验证者，进行信息验证。

加密的方法主要有两种，分别为替换（Substitution）加密和换位（Transposition）加密。替换加密主要是指将 个字符的明文替换成 个字符的密文；换位加密主要是指将原始信息的字符按照某些特定的模式重新排列。而现代加密方式是以上两种的混合，使得密码更加安全。

加密和解密过程即 Alice 通过密钥加密明文，将明文转变成密文；通过选定途径，发送给 Bob；Bob 通过密钥进行解密，得到明文。一个密码系统，通常由明文 、密钥 、密文 、加密算法 （Encrypt）和解密算法 （Decrypt）这 5 种元素构成，加密算法用公式表示为:

解密算法用公式表示为：

使用密码的场景一般是发送方和接收方之间没有安全的通信通道，所以需要加密信息，以确保不会被第三方知道。信息安全的关键是攻击者不知道加密中使用了何种特定密钥，以及加密方式。攻击者一旦知道密钥及加密方法，密文即被破译。

现代密码学有 3 个基本原则。

(1) 安全的定义

对安全的定义必须是公式化的、表述严格且精确的。一个安全的密码算法应该满足哪些条件？“对于攻击者而言，不能恢复密钥。”这句话是否满足对于安全的定义呢？很显然，不满足。因为有些算法即使不能恢复密钥，也有可能泄露明文。比如 ，没有人可以从密文中猜出密钥，但明文依然被泄露。“对于攻击者而言，不能从密文恢复完整的明文。”这也不满足对于安全的定义。因为不需要恢复完整明文，只要恢复部分明文就可能泄露重要的信息。比如，某个加密算法只加密偶数位的信息，那么奇数位的信息依然会被泄露。“对于攻击者而言，不能从密文恢复任何明文字符。”这也不满足对于安全的定义。因为即使攻击者不能知道明文的任何信息，但只要知道明文之间潜在的关系即可。比如，虽然不知道两架飞机的具体速度，但是知道飞机 A 比飞机 B 快，这也是信息泄露，是不安全的。

正确的定义是：若攻击者无法从密文中计算出任何关于明文的信息，那么该密码是安全的。

（2）精确的假设

若密码学系统的安全性依赖于未被证明的假设，这种假设必须被精确陈述，且假设需要尽可能的少。大部分公钥密码系统通常是基于数学困难问题构造的。现代密码学要求，若一个方案的安全性依赖于假设，则假设必须被精确地陈述。假设是暂无数学证明的，但据推测是正确的命题。一个假设被检查和测试的次数越多，那么它的可信度就越高。

在其他条件相同的情况下，如果有两个基于不同假设的方案都被证明满足某种定义，那么该选哪种方案呢？通常选择假设更弱的那个方案。这是因为假设越弱越好，越弱的假设，其所需要的条件就越少，需要的信息也越少，也就越安全。反过来说，如果某个假设需要很强的条件才可以成立，那么这个假设就会因为条件太多而带来更多的不安全因素。

(3) 严格的安全证明

密码学方案应该有严格的安全证明。一个密码学方案在某些特定的假设下满足给定的定义，是可以严格证明该方案安全的前提。即假设 A 是正确的，则根据 A 给定的定义，所发明的算法 B 就是安全的。假设否定了 A，那么攻击者就能破解算法 B。

1.2.3　密码分析方式

要保证整个密码系统的安全，需要什么呢？只保证加密算法的安全就行了吗？答案是否定的。加密算法的设计需要经严格测试以证明其安全性。比如好不容易设计了一个加密算法，但只能加密前 10 位的字符，后面的不能加密，这很明显不是一个安全的加密算法。一个安全的加密算法应该是无法从密文中计算出任何关于明文的信息，换句话说，不光不能算出具体的明文信息，也不能算出与明文相关的信息。

不过遗憾的是，大多数的密码并不能保证密文中没有明文的任何信息。

在未知密钥的情况下，从截获的密文中分析出明文的过程称为密码分析。试图对密码进行分析的行为称为攻击。

密码分析作为密码学的一部分，通常情况下指的是一种破译密码的方法。绝大多数的密码分析方法都是由学术界赫赫有名的密码学家完成的。它的难度不比设计密码算法小，它的意义在于让人们试图破译密码以验证该密码算法是否安全，如果发现漏洞，需要及时补上，或者更换更安全的密码。

密码分析通常有 3 种方法，如下所述。

1. 经典密码分析

经典密码分析（Classical Cryptanalysis）包括两种，一种是纯暴力破解，穷举所有明文的可能性，找出最合理的一种；另一种则是数学分析方法，包括以下 4 种攻击方式。

● 唯密文攻击 (Ciphertext-Only Attack)：攻击者仅通过分析密文来恢复明文。

● 已知明文攻击 (Known-Plaintext Attack)：攻击者通过分析已知的明文-密文对来恢复全部明文。

● 选择明文攻击 (Chosen-Plaintext Attack)：攻击者知道加密算法，并且有能力选择一些明文一密文对来恢复全部明文。

● 选择密文攻击 (Chosen-Ciphertext Attack)：攻击者可以选择部分密文并获得相应明文，是一种比已知明文攻击更强的攻击方式。

这 4 种攻击的攻击难度依次递减。

2. 实施攻击

实施攻击（Implementation Attack）即不利用密码算法本身，而是通过其他渠道进行密码分析。例如通过测量处理明文的 CPU 功耗，或者测量信号强度来推理出密钥，这些方式也称为侧信道攻击。除此之外还有软硬件攻击、弱点攻击、差分攻击等方式，甚至包括清除访问记录。实施攻击在绝大多数情况下针对的是攻击者可以物理访问的密码系统，因此如果使用远程系统加密，通常不会考虑这种方法。

3. 社会工程学攻击

通过间谍行为，如行贿、窃取、跟踪等方式获得密钥，称为社会工程学攻击（Social Engineering Attack）。它包括但不限于钓鱼、恶意软件传播、身份伪造、诱饵攻击、尾随、假冒权威等攻击方式。有个笑话：某公司被黑客勒索，每 20 分钟断一次网，用技术手段怎么也找不到原因。最后发现是黑客收买了保安，让他每 20 分钟拔一次网线。这种攻击方式也是社会工程学攻击的一种。

密码系统的安全性分析评估一般需要用数据复杂度（明文空间、密文空间、密钥空间）、时间复杂度、空间复杂度和成功概率来衡量。一般来说，密码分析常说的计算复杂度主要是指时间复杂度和空间复杂度。

攻击者 Eve 会寻找密码使用过程中最脆弱的环节，不仅限于算法，还包括密码传输、管理等。换句话说，密码使用者必须使用足够安全的算法，也必须保证可以抵御实施攻击和社会工程学攻击。本书将会重点介绍经典密码分析方法，也会简单介绍实施攻击和社会工程学攻击。

对于任何安全的加密方案，其密钥空间 必须能抵御穷举攻击，且必须满足 ，即明文空间大于密钥空间。若可能的明文比可能的密钥还少，穷举出所有可能的密钥，解密之后会获得比明文空间还大的候选明文集合。

充分大的密钥空间是密码算法安全的必要不充分条件。一个安全的密码算法一定有一个充分大的密钥空间，但充分大的密钥空间不一定能保证密码算法的安全。还有一点值得注意，密钥空间并不等于密钥长度。密钥长度为密钥的二进制位数，比如密钥为 10101010 ，一共 8 位，那么它的密钥长度就是 8 ，其密钥空间为 。如果密钥长度为 16 ，是 8 位密钥长度的两倍，那么它的密钥空间会远远大于后者的密钥空间大小，是其 倍之大。

1.2.4　对称/非对称加密

本书将会讨论对称密码学（Symmetric Cryptography）和非对称密码学（Asymmetric Cryptography），非对称密码学也称公开密钥密码学（Public-Key Cryptography），简称公钥密码学。

在古典密码学中，收发双方都是秘密地选择密钥，密钥绝不能被公开。然后根据选择的密码算法，规定加密和解密过程，并且加密过程和解密过程是相同的。因此如果攻击者知道了密钥和加密算法，就容易解密信息，从而泄露信息。因为加密和解密过程是相同的，所以被称为对称加密算法。

对称加密算法有以下几个特点。

● 加密和解密使用的是同一个密钥。

● 加密和解密的速度比较快。

● 密钥交换的渠道不安全，容易被攻击。可能会产生为了保护密钥不被泄露，而用密码系统加密密钥的无解事件。

● 为了安全，可能需要长密钥来保护信息，这对密钥的管理者提出了非常高的要求，密钥管理起来非常困难。因此在网络通信中，较少使用对称加密算法。

对称加密算法就好比 Alice 和 Bob 都有一串相同的钥匙。Alice 把信息放在一个保险柜里，然后锁上。如果 Bob 想要知道这个信息，就需要用钥匙打开这个保险柜。但是让 Alice 和 Bob 拥有一串相同的钥匙就比较麻烦。当面交换和确认固然是个好办法，但是次数多了就很麻烦。放在保险柜里给对方？但没有钥匙就无法打开保险柜。而且用户一旦不止两个人，需要使用的钥匙对就多了，钥匙分配起来就比较麻烦。并且还有一点，就是拿 Bob 的钥匙开保险柜的人，不能确定就是 Bob 本人，也有可能是 Eve 拿他的钥匙开的，这没办法验证。

当然，利用计算机可以在一定程度上克服这些困难，诸如 DES 和 AES 就是对称密码学的巅峰之作。

为了解决上述难题，人们发明了非对称密码学。非对称密码学使得安全性得到了巨大提高。它将密钥一分为二，拆分成了公钥 (Public Key) 和私钥 (Private Key) 两组密钥。顾名思义，公钥可以被任何人知道，私钥则不能被泄露，只有接收方 Bob 知道。任何人都可以使用公钥加密信息，但只有拥有私钥的 Bob 才能解密信息。这就是非对称加密。比如， Alice 向银行请求公钥，银行将公钥发送给 Alice，Alice 使用公钥对信息加密，那么只有私钥的持有人——银行（Bob）才能对 Alice 的信息解密。与对称加密不同的是，银行不需要将私钥通过网络发送出去，这就解决了密钥交换的问题，因此安全性大大提高。

对称加密算法和公钥加密算法所要求的密钥长度完全不同。对攻击方来说，他极有可能通过穷举找出密钥，因此攻击方肯定对密钥空间的大小感兴趣。大多数密码系统的密钥空间大小是固定的。部分对称算法（如 AES）会根据用户需求来提供相应的模式，每种模式会对应不同的密钥长度。而公钥加密算法（如 RSA）也可以根据需求，提供不同的密钥长度。目前，对于一个只拥有 64 位密钥长度的密码系统，如果靠穷举攻击，在现代计算机的帮助下，几天即可破解。而对于拥有 128 位密钥长度的密码系统，只靠穷举攻击，则需要几十年的时间。破解一个 256 位密钥的加密算法，则需要成千上万年。

1.3　编码

1.3.1　ASCII 编码

因为现代通信的通信量大，时限要求高，所以除了极少部分的文件还是采用线下递送的交换方式，绝大部分信息交换都是通过网络完成的。使用网络就需要使用计算机，计算机底层硬件只能表示 0 和 1 两个数字，即半导体的断开和闭合。为了让计算机读懂人类的语言，IEEE 就设计了 ASCII，ASCII 全称为 American Standard Code for Information Interchange，即美国信息交换标准代码，这是一套基于拉丁字母的计算机编码系统。因为计算机只能处理二进制数，所以 ASCII 表在计算机领域应用甚广，它可以将拉丁字母和阿拉伯数字转化为二进制码。该表是 IEEE 的经典之作，是确立了 IEEE 在今天地位的成果之一。

大部分密码算法都是在计算机上运行的，计算机能处理的数据仅为 0 和 1 。由 0 和 1组成的字符串称为二进制数，比如 1001 0010。

ASCII 表包含二进制、十进制和十六进制，以及对应的字符。表中常用字符共有 96 个，如表 1-1 所示。

可以发现每个字符都对应着二进制（Binary）、十进制（Decimal）和十六进制（Hexadecimal) 数。十进制数和二进制数之间是怎么转化的呢?

十进制整数转换为二进制整数采用“除 2 取余，逆序排列”法。下面举一个例子。

例1.3.1　将十进制数 13 转化为二进制数。

解：

然后逆序排列，得到1101，就是 13 的二进制数了。

二进制数转为十进制数则是从左到右用二进制数的每个数字乘以 2 的相应次方然后相加起来得到的，次方数最高为 ( 为二进制数的长度)，最低为 0 。也举一个例子。

例1.3.2　将二进制数 10010011 转化为十进制数。

解：10010011 一共 8 位数，因此次方项最高为 7 次。

所以 10010011 转成十进制数就是 147 。

表1-1　ASCII 表

十六进制也是计算机比较常用的一种进制方式。它由 和 组成，字母不区分大小写。与十进制的对应关系是： 对应 ； 对应 。

它与十进制的转化方法与二进制类似，只是将底数从 2 换成 16 。比如：2C（十六进制） (十进制 ) ； 90 （十进制） 5A (十六进制)。

除了二进制、十进制和十六进制，还有四进制、八进制、三十二进制。不过这些不常用，有兴趣的读者可以思考它们之间是如何互相转化的。

了解完简单的计算机编码知识后，还需要了解它们的单位。

● 比特（Bit）。也称 “二进制位”，通常简称 “位”，是二进制最小的信息单位，取值只有数字 0 和 1 。

● 字节（Byte）。简称 B，1字节代表 8 位，这 8 位可以构成 256 种组合，是计算机存储容量的基本单位。通常一个英文字母使用 1 字节表示，一个汉字使用 2 字节表示。

● 字（Word）。由两个或两个以上比特组成的比特串，长度不定。在 AES 分组密码中，一个字通常指 32 位或 4 字节。

● 千字节 (Kilobyte)。简称 KB， 。

● 兆字节 (Megabyte)。简称 MB， 。

● 吉字节 (Gigabyte)。简称 GB，1GB=1024MB。

● 万亿字节 (Trillionbyte)。简称 TB，1TB = 1024GB。

当然后面还有更多的单位，但与密码学关系不大。可以发现，计算机存储单位的进率是 1024 而非 1000 ，因为 ，是二进制的。但对于日常的计算机产品，为了方便计算，都是以 1000 为进率的。比如一个 1 TB 的移动硬盘，实际上是 ，即约为标定容量的 。

1.3.2　异或运算

异或运算需要在二进制中进行，如果不是二进制数，就需要将该数字转换成二进制数，再进行计算。下面看看二进制中异或运算的结果：

1　XOR　1=0

0　XOR　0=0

1　XOR　0=1

0　XOR　1=1

为了书写方便，异或运算可以用 表示，即 。为了便于理解，可以想象一下现在有两块磁铁。假设规定磁铁互斥的值是 0 ，互相吸引的值是 1 。磁铁有南北两极，南极表示 1 ，北极表示 0 。两个磁铁的南极和南极放在一起会互斥，所以得到 0 ，北极同理。但是将两个磁铁的南极和北极放在一起，就会吸引，所以是1。

异或运算还有许多有意思的性质。

● 归零律：

● 恒等律：

● 交换律：

● 结合律：

● 自反律：

自反律的证明非常简单， 。自反律的作用非常强大，在某些密码算法中，可以运用自反律来跳过密钥并获得明文。