密码学与编码理论

适读人群 ：本书可以作为相关专业本科高年级或者研究生低年级的密码学双语教材。读者可以利用本书中的实例迅速掌握有关算法和协议，也可以通过本书的背景知识和习题对密码学有更深刻的理解。

第三版重新组织了流密码、分组密码、DES和AES等内容，增加了RC4、一次一密的多次使用、完全保密、散列函数的应用、比特币和密码货币、基于对的密码系统等内容。

Contents
目??录

Chapter 1?Overview of Cryptography and Its Applications?密码学及其应用概述
1．1?Secure Communications?安全通信
1．1．1　Possible Attacks?四种主要的攻击
1．1．2　Symmetric and Public Key Algorithms?对称和公钥算法
1．1．3　Key Length?密钥长度
1．2?Cryptographic Applications?密码学应用

Chapter 2?Classical Cryptosystems?传统密码系统
2．1?Shift Ciphers?移位密码
2．2?Affine Ciphers?仿射密码
2．3?The Vigenère Cipher?维吉内尔密码
2．3．1　Finding the Key Length?算出密钥长度
2．3．2　Finding the Key： First Method?算出密钥的第一种方法
2．3．3　Finding the Key： Second Method?算出密钥的第二种方法
2．4?Substitution Ciphers?替换密码
2．5?Sherlock Holmes?夏洛克・福尔摩斯
2．6?The Playfair and ADFGX Ciphers?Playfair和ADFGX密码
2．7?Enigma?Enigma密码机
2．8?Exercises?习题
2．9?Computer Problems?上机练习

Chapter 3?Basic Number Theory?数论简介
3．1?Basic Notions?基本概念
3．1．1　Divisibility?整除性
3．1．2　Prime Numbers?素数
3．1．3　Greatest Common Divisor?最大公因子
3．2?The Extended Euclidean Algorithm?扩展的欧几里得算法
3．3?Congruences?同余式
3．3．1　Division?除法
3．3．2　Working with Fractions?使用分式
3．4?The Chinese Remainder Theorem?中国余数定理
3．5?Modular Exponentiation?模指数
3．6?Fermat’s Theorem and Euler’s Theorem?费马小定理和欧拉定理
3．6．1?Three-Pass Protocol?三轮协议
3．7?Primitive Roots?原根
3．8?Inverting Matrices Mod n?模n求逆矩阵
3．9?Square Roots Mod n?模n平方根
3．10?Legendre and Jacobi Symbols?勒让德和雅可比符号
3．11?Finite Fields?有限域
3．11．1　Division?除法
3．11．2　GF(28)
3．11．3　LFSR Sequences?线性反馈移位寄存器序列
3．12?Continued Fractions?连分数
3．13?Exercises?习题
3．14?Computer Problems?上机练习

Chapter 4?The One-Time Pad?一次一密
4．1?Binary Numbers and ASCII?二进制数和ASCII码
4．2?One-Time Pads?一次一密
4．3?Multiple Use of a One-Time Pad?一次一密的多次使用
4．4?Perfect Secrecy of the One-Time Pad?一次一密的完全保密
4．5?Indistinguishability and Security?不可区分性和安全性
4．6?Exercises?习题

Chapter 5?Stream Ciphers?流密码
5．1?Pseudorandom Bit Generation?伪随机比特生成器
5．2?Linear Feedback Shift Register Sequences?线性反馈移位寄存器序列
5．3?RC4
5．4?Exercises?习题
5．5?Computer Problems?上机练习

Chapter 6?Block Ciphers?分组密码
6．1?Block Ciphers?分组密码简介
6．2?Hill Ciphers?希尔密码
6．3?Modes of Operation?工作模式
6．3．1　Electronic Codebook (ECB)?电子密码本（ECB）
6．3．2　Cipher Block Chaining (CBC)?密码分组链接（CBC）
6．3．3　Cipher Feedback (CFB)?密码反馈（CFB）
6．3．4　Output Feedback (OFB)?输出反馈（OFB）
6．3．5　Counter (CTR)?计数器（CTR）
6．4?Multiple Encryption?多重加密
6．5?Meet-in-the-Middle Attacks?中间相遇攻击
6．6?Exercises?习题
6．7?Computer Problems?上机练习

Chapter 7?The Data Encryption Standard?数据加密标准（DES）
7．1?Introduction?简介
7．2?A Simplied DES-Type Algorithm?DES算法的简化版
7．3?Differential Cryptanalysis?差分密码分析
7．3．1　Differential Cryptanalysis for Three Rounds?三轮差分密码分析
7．3．2　Differential Cryptanalysis for Four Rounds?四轮差分密码分析
7．4?DES?DES算法
7．4．1?DES Is Not a Group?DES算法不是代数群
7．5?Breaking DES?破解DES
7．6?Password Security?口令安全
7．7?Exercises?习题
7．8?Computer Problems?上机练习

Chapter 8?The Advanced Encryption Standard： Rijndael 高级加密标准：Rijndael
8．1?The Basic Algorithm?算法简介
8．2?The Layers?层的描述
8．2．1　The SubBytes Transformation?SubByte变换
8．2．2　The ShiftRows Transformation?ShiftRow变换
8．2．3　The MixColumns Transformation?MixColumn变换
8．2．4　The RoundKey Addition?RoundKey加法
8．2．5　The Key Schedule?密钥扩展方案
8．2．6　The Construction of the S-Box?S盒的结构
8．3?Decryption?解密算法
8．4?Design Considerations?设计中的考虑
8．5?Exercises?习题

Chapter 9?The RSA Algorithm?RSA算法
9．1?The RSA Algorithm?RSA算法简介
9．2?Attacks on RSA?RSA算法的攻击
9．2．1　Low Exponent Attacks?低指数攻击
9．2．2　Short Plaintext?短明文
9．2．3　Timing Attacks?时间攻击
9．3?Primality Testing?素性检测
9．4?Factoring?因子分解
9．4．1　x2≡y2
9．4．2　Using ar≡1? ar≡1的应用
9．5?The RSA Challenge?RSA挑战
9．6?An Application to Treaty Verification?协约验证的应用
9．7?The Public Key Concept?公钥密码系统概念
9．8?Exercises?习题
9．9?Computer Problems?上机练习

Chapter 10?Discrete Logarithms?离散对数
10．1?Discrete Logarithms?离散对数简介
10．2?Computing Discrete Logs?离散对数的计算
10．2．1　The Pohlig-Hellman Algorithm?Pohlig-Hellman算法
10．2．2　Baby Step， Giant Step?小步-大步法
10．2．3　The Index Calculus?指数计算法
10．2．4　Computing Discrete Logs Mod 4?模4离散对数的计算
10．3?Bit Commitment?比特承诺
10．4?Diffie-Hellman Key Exchange?Diffie-Hellman 密钥协商协议
10．5?The ElGamal Public Key Cryptosystem?ElGamal公钥密码系统
10．5．1　Security of ElGamal Ciphertexts?ElGamal密文的安全性
10．6?Exercises?习题
10．7?Computer Problems?上机练习

Chapter 11?Hash Functions?散列函数
11．1?Hash Functions?散列函数简介
11．2?Simple Hash Examples?简单散列示例
11．3?The Merkle-Damg?rd Construction?Merkle-Damg?rd结构
11．4?SHA-2
11．5?SHA-3/Keccak?SHA-3/Keccak算法
11．6?Exercises?习题

Chapter 12?Hash Functions： Attacks and Applications 散列函数：攻击与应用
12．1?Birthday Attacks?生日攻击
12．1．1　A Birthday Attack on Discrete Logarithms?离散对数的生日攻击
12．2?Multicollisions?多元碰撞
12．3?The Random Oracle Model?随机预言模型
12．4?Using Hash Functions to Encrypt?用散列函数加密
12．5?Message Authentication Codes?消息认证码
12．5．1　HMAC
12．5．2　CBC-MAC
12．6?Password Protocols?口令协议
12．6．1　The Secure Remote Password Protocol?安全远程口令协议
12．6．2　Lamport’s Protocol?Lamport协议
12．7?Blockchains?区块链
12．8?Exercises?习题
12．9?Computer Problems?上机练习

Chapter 13?Digital Signatures?数字签名
13．1?RSA Signatures?RSA签名方案
13．2?The ElGamal Signature Scheme?ElGamal签名方案
13．3?Hashing and Signing?散列与签名
13．4?Birthday Attacks on Signatures?签名的生日攻击
13．5?The Digital Signature Algorithm?数字签名算法（DSA）
13．6?Exercises?习题
13．7?Computer Problems?上机练习

Chapter 14?What Can Go Wrong?会出什么问题
14．1?An Enigma“Feature”?Enigma密码机的“特征”
14．2?Choosing Primes for RSA?RSA算法中的素数选取
14．3?WEP
14．3．1　CRC-32
14．4?Exercises?习题

Chapter 15?Security Protocols?安全协议
15．1?Intruders-in-the-Middle and Impostors?中间入侵者和冒名顶替者
15．1．1　Intruder-in-the-Middle Attacks?中间人攻击
15．2?Key Distribution?密钥分配
15．2．1　Key Pre-distribution?密钥预分配
15．2．2　Authenticated Key Distribution?认证的密钥分配
15．3?Kerberos?Kerberos协议
15．4?Public Key Infrastructures (PKI)?公钥基础设施（PKI）
15．5?X．509 Certificates?X．509证书
15．6?Pretty Good Privacy?PGP协议
15．7?SSL and TLS?SSL协议和TLS协议
15．8?Secure Electronic Transaction?SET协议
15．9?Exercises?习题

Chapter 16?Digital Cash?数字现金
16．1?Setting the Stage for Digital Economies?为数字经济创造条件
16．2?A Digital Cash System?数字现金系统
16．2．1　Participants?参与者
16．2．2　Initialization?初始化
16．2．3　The Bank?银行
16．2．4　The Spender?消费者
16．2．5　The Merchant?商家
16．2．6　Creating a Coin?创建硬币
16．2．7　Spending the Coin?消费硬币
16．2．8　The Merchant Deposits the Coin in the Bank?商家将硬币存入银行
16．2．9　Fraud Control?欺诈控制
16．2．10?Anonymity?匿名性
16．3?Bitcoin Overview?比特币简介
16．3．1　Some More Details?更多细节
16．4?Cryptocurrencies?密码货币
16．5?Exercises?习题

Chapter 17?Secret Sharing Schemes?秘密共享方案
17．1?Secret Splitting?秘密分拆
17．2?Threshold Schemes?门限方案
17．3?Exercises?习题
17．4?Computer Problems?上机练习

Chapter 18?Games?游戏
18．1?Flipping Coins over the Telephone?电话掷硬币
18．2?Poker over the Telephone?电话玩牌
18．2．1　How to Cheat?如何欺骗
18．3?Exercises?习题

Chapter 19?Zero-Knowledge Techniques?零知识技术
19．1?The Basic Setup?简介
19．2?The Feige-Fiat-Shamir Identification Scheme Feige-Fiat-Shamir身份识别方案
19．3?Exercises?习题

Chapter 20?Information Theory?信息论
20．1?Probability Review?概率论简介
20．2?Entropy?熵
20．3?Huffman Codes?霍夫曼编码
20．4?Perfect Secrecy?完全保密
20．5?The Entropy of English?英文中的熵
20．5．1　Unicity Distance?唯一性距离
20．6?Exercises?习题

Chapter 21?Elliptic Curves?椭圆曲线
21．1?The Addition Law?加法法则
21．2?Elliptic Curves Mod p?模p椭圆曲线
21．2．1　Number of Points Mod p?模p点的数目
21．2．2　Discrete Logarithms on Elliptic Curves?椭圆曲线上的离散对数
21．2．3　Representing Plaintext?明文表示
21．3?Factoring with Elliptic Curves?椭圆曲线因子分解
21．3．1　Singular Curves?奇异曲线
21．4?Elliptic Curves in Characteristic 2?特征值为2的椭圆曲线
21．5?Elliptic Curve Cryptosystems?椭圆曲线密码系统
21．5．1　An Elliptic Curve ElGamal Cryptosystem?椭圆曲线ElGamal加密方案
21．5．2　Elliptic Curve Diffie-Hellman Key Exchange 椭圆曲线Diffie-Hellman密钥协商协议
21．5．3　ElGamal Digital Signatures?椭圆曲线ElGamal签名方案
21．6?Exercises?习题
21．7?Computer Problems?上机练习

Chapter 22?Pairing-Based Cryptography?基于对的密码系统
22．1?Bilinear Pairings?双线性对
22．2?The MOV Attack?MOV攻击
22．3?Tripartite Diffie-Hellman?三方Diffie-Hellman密钥协商协议
22．4?Identity-Based Encryption?基于身份的加密
22．5?Signatures?签名
22．5．1　BLS Signatures?BLS签名
22．5．2　A Variation?BLS签名的变形
22．5．3　Identity-Based Signatures?基于身份的签名
22．6?Keyword Search?关键词搜索
22．7?Exercises?习题

Chapter 23?Lattice Methods?格方法
23．1?Lattices?格
23．2?Lattice Reduction?格归约
23．2．1　Two-Dimensional Lattices?二维格
23．2．2　The LLL algorithm?LLL算法
23．3?An Attack on RSA?RSA中的攻击
23．4?NTRU
23．4．1　An Attack on NTRU?NTRU中的攻击
23．5?Another Lattice-Based Cryptosystem?另一个基于格的密码系统
23．6?Post-Quantum Cryptography??抗量子密码学
23．7?Exercises?习题

Chapter 24?Error Correcting Codes?纠错码
24．1?Introduction?简介
24．2?Error Correcting Codes?纠错码
24．3?Bounds on General Codes?一般码的限
24．3．1　Upper Bounds?上界
24．3．2　Lower Bounds?下界
24．4?Linear Codes?线性码
24．4．1　Dual Codes?对偶码
24．5?Hamming Codes?汉明码
24．6?Golay Codes?戈莱码
24．6．1　Decoding G24?G24译码
24．7?Cyclic Codes?循环码
24．8?BCH Codes?BCH码
24．8．1　Decoding BCH Codes?BCH译码
24．9?Reed-Solomon Codes?里德-所罗门码
24．10?The McEliece Cryptosystem?McEliece密码系统
24．11?Other Topics?其他问题
24．12?Exercises?习题
24．13?Computer Problems?上机练习

Chapter 25?Quantum Techniques in Cryptography?密码学中的量子技术
25．1?A Quantum Experiment?量子实验
25．2?Quantum Key Distribution?量子密钥分配
25．3?Shor’s Algorithm?Shor算法
25．3．1　Factoring?因子分解
25．3．2　The Discrete Fourier Transform?离散傅里叶变换
25．3．3　Shor’s Algorithm?Shor算法
25．3．4　Final Words?小结
25．4?Exercises?习题

Appendix A?Mathematica Examples?Mathematica实例
Appendix B?Maple Examples?Maple 实例
Appendix C?MATLAB Examples?MATLAB实例
Appendix D?Sage Examples?Sage实例
Appendix E?Answers and Hints for Selected Odd-Numbered Exercises
奇数编号习题的答案与提示
Appendix F?Suggestions for Further Reading?推荐阅读
Bibliography?参考文献

Preface

前??言

本书是密码学课程的教材 ，从1997年开始就将其用于在美国马里兰大学向高年级本科生和一年级研究生讲授密码学，并从2003年开始在美国罗格斯大学用于教学。在设计这门课程时，我们考虑了以下要求：

●?课程内容应该是最新的，并且从数学的观点看它应该涵盖了密码学中的大部分主要专题。

●?课程内容应该能让不熟悉数论和计算机编程但是已选修过本科数学基础课的学生也易于接受。

●?课程内容应该包含足够多的实例，用于展示各种密码算法实际上是怎样运行的。

我们不想把注意力只放在RSA和离散对数上，因为这样会让这门课程变成一门主要关于数论的课。我们也不想把注意力集中在各种协议和如何入侵别人的计算机上，那样会让这门课程的数学性不够强。

密码学中有很多专题可以在一门导论性的课程中介绍。我们尽量把大多数专题包括在本课程内。这些章节在很大程度上代表了我们在不同学期所授课程涉及的主题。当然，这里的材料比大多数一学期的课程都要多。前13章是本书的核心部分，其余章节的选取取决于学生的水平和教师的目标。

除与全书内容都有关联的第3章（数论）外，其余各章内容彼此独立，因此可以按任何合理顺序进行安排。由于学生掌握数论的程度各不相同，我们把基本的数论知识集中放在第3章以便参考，但还是建议按照课程的进度逐步介绍学生所需的数论概念。

信息论、椭圆曲线、格方法、纠错码和量子密码这几章内容比其他章的数学知识更多。纠错码一章是基于几位审稿人的建议而放入本书中的，因为在一门课程中同时介绍密码学和编码理论的做法是非常普遍的。

上机实例

假如你想给出一个RSA算法的例子，可以选择使用两个1位数的素数，模拟使用50位的素数进行运算，或者用你习惯的软件包来实现一个有大素数的实例。或许你正在使用移位密码，试图通过一一尝试密文的26种移位而对一个消息进行解密。不过这个工作应该由计算机来完成。

此外，书末的附录里给出了分别用Mathematica、Maple、MATLAB和Sage等软件编写的上机实例。之所以选择这些软件是因为它们界面友好且不需要有编程经验。虽然密码学课程在不使用计算机的情况下也可以正常授课，但这些上机实例仍然是本书不可分割的一部分,因此应该深入学习。书中不仅包含了关于怎样进行某些计算的数值方面的例子，还阐述了其中的重要思想和相关的问题。

基于上述软件的课后作业（即各章后的上机练习）学生可以独自完成并实现这些实例。当然，有更多编程背景的学生可以自己编写相应的程序。

第三版中新增的内容

密码学是一个迅速发展的领域。本书在第三版中有如下几个方面的变化：

●?重新组织了第二版中的两章（第4章和第5章）内容，并把它们拆分为流密码（包括RC4）、分组密码、DES和AES（分别对应第5章至第8章）。其中，RC4的内容是新增的。

●?散列函数（第二版的第11章）被分成了两章内容：第11章（散列函数）新增了SHA-2和SHA-3的内容，第12章（散列函数：攻击与应用）新增了消息认证码、口令协议和区块链的内容。

●?第二版中与“一次一密”相关的内容被扩展成第4章，新增了一次一密的多次使用、完全保密和密文不可区分性的内容。

●?新增了第14章（会出什么问题），主要讲述了当密码算法被错误使用或设计时会导致什么样的问题。

●?第16章（数字现金）为第二版第11章的扩展，新增了比特币和密码货币的内容。

●?新增的第22章给出了基于对的密码系统的介绍。

●?对全书的注释内容进行了更新，体现了相关领域的最新进展。

●?附录新增了针对各章相关内容采用Mathematica、Maple、MATLAB和Sage语言编写的上机实例。

●?新增了一些习题。

●?本书最后新增了大部分奇数编号习题的参考答案或提示。

致谢

本书在准备过程中得到了许多人的帮助与支持。首先，我们要感谢我们的学生，他们的热情、洞察力和建议都对本书贡献极大。我们特别感谢许多提供修改意见和其他信息的人，尤其是Bill Gasarch，Jeff Adams，Jonathan Rosenberg和Tim Strobell。我们还要感谢Wenyuan Xu，Qing Li和Pandurang Kamat，他们为本书制作了一些图表，并且在第二版的基础上提供了新的反馈意见。我们很愉快地与Pearson的员工们一起工作，尤其是编辑Jeff Weidenaar和Tara Corpuz。

我们要特别感谢本书的审稿人，他们在内容表述和内容组织方面的建议极大地改善了本书的最终面貌。下列标注“*”符号的是指第三版的审稿人。

* Anurag Agarwal, Rochester Institute of Technology

* Pradeep Atrey, University at Albany

Eric Bach, University of Wisconsin

James W. Brewer, Florida Atlantic University

Thomas P. Cahill, NYU

Agnes Chan, Northeastern University

* Nathan Chenette, Rose-Hulman Institute of Technology

* Claude Crépeau, McGill University

* Reza Curtmola, New Jersey Institute of Technology

* Ahmed Desoky, University of Louisville

Anthony Ephremides, University of Maryland, College Park

* David J. Fawcett, Lawrence Tech University

* Jason Gibson, Eastern Kentucky University

* K. Gopalakrishnan, East Carolina University

David Grant, University of Colorado, Boulder

Jugal K. Kalita, University of Colorado, Colorado Springs

* Saroja Kanchi, Kettering University

* Andrew Klapper, University of Kentucky

* Amanda Knecht, Villanova University

Edmund Lamagna, University of Rhode Island

* Aihua Li, Montclair State University

* Spyros S. Magliveras, Florida Atlantic University

* Nathan McNew, Towson University

* Nick Novotny, IUPUI

David M. Pozar, University of Massachusetts, Amherst

* Emma Previato, Boston University

* Hamzeh Roumani, York University

* Bonnie Saunders, University of Illinois, Chicago

* Ravi Shankar, University of Oklahoma

* Ernie Stitzinger, North Carolina State

* Armin Straub, University of South Alabama

J. Felipe Voloch, University of Texas, Austin

Daniel F. Warren, Naval Postgraduate School

* Simon Whitehouse, Alfred State College

Siman Wong, University of Massachusetts, Amherst

* Huapeng Wu, University of Windsor

本书的第一作者要感谢Nisha Gilra提供的鼓励和建议；感谢Sheilagh O’Hare 引导他进入密码学领域；感谢K. J. Ray Liu给予的支持。

本书的第二作者要感谢Susan Zengerle和Patrick Washington在他编写本书时所给予的耐心、帮助和鼓励。

当然，我们欢迎任何的建议和指正，我们的联系方式分别为

Wade Trappe trappe@winlab.rutgers.edu

Lawrence C. Washington lcw@math.umd.edu