第1章 密码学和数据安全导论

1.1 密码学及本书内容概述

1.密码学（cryptology）：密码编码学（cryptography）和密码分析学（破译密码）。

2.密码使用学的三个主要分支：对称算法（Symmetric Algorithm），非对称算法（Asymmetric Algorithm）或公钥算法（Public-Key Algorithm），密码协议（Cryptographic Protocol）。

1.2 对称密码学

1.基本概念：明文，密文，密钥，密钥空间（所有可能密钥组成的集合），安全信道（用于在通信双方间安全地分配密钥）。

2.安全地传输消息地问题最后可以归结为安全地传输和存储密钥地问题。

3.简单对称加密：替换密码

例如，A被k替换，B被d替换。

替换表是这种密码体制地关键，需要在Alice和Bob之间安全传输。

第一个攻击：蛮力攻击或穷尽密钥搜索。x(明文)，y(密文)，K={k1,k2,...,kk}，攻击将检查每个ki，判断是否等于。

第二种攻击：字母频率分析。密文中某个出现频率最高地字母可能是英文语言中最常用的一个字母的替换字母。

（1）确定每个密文字母的频率；（2）连续的两个，三个或四个等密文字母的频率；（3）高频的短单词。

好的密码应该隐藏被加密文本的统计属性，仅仅密钥空间大是不够的。

1.3 密码分析

1.破译密码体制的一般思路

①经典密码分析：从密文y中恢复明文x，或从密文y中恢复密钥k。

密码分析可分为两类：一类是发现加密方法内部结构的分析攻击；另一类是将加密算法看作是黑盒，试图测试所有可能密钥。

②实施攻击：旁道分析。

③社会工程攻击：强迫某个人说出密钥，骗取密钥。

2.可靠的密码体制必须遵守Auguste Kerckhoffs在1883年提出的Kerckhoffs原理。

Kerckhoffs原理：即使除密钥外的整个系统的一切都是公开的，这个密码体制也必须是安全的。尤其是即使攻击者知道系统的加密算法和机密算法，此系统也必须是安全的。

3.关于密钥长度的讨论

只有在蛮力攻击是最好的攻击方法时，讨论对称加密算法中密钥长度的问题才有意义。

在安全性相当的情况下，对称算法和非对称算法所要求的密钥长度完全不同。

使用蛮力攻击成功破解不同长度密钥的对称算法预计时间：56~64位——短期几小时或几天，112~128位——长期几十年，256位——量子计算机几十年。

1.4 模运算与多种古典密码

1.模运算

定义：假设a,r,mZ(所有整数的集合)，如果m除a的余数为r，则可记作ar mod m，m为模数，r为余数。

计算余数：r = a - q*m

等价类：余数不唯一。模数9存在9个等价类：

{...,-27,-18,-9,0,9,18,27,...}，{...,-26,-17,-8,1,10,19,28,...}，...，{...,-19,-10,-1,8,17,26,35,...}

等价类中所有成员的行为等价：对于一个给定模数m，选择同一个等价类中任何一个元素用于计算的结果都是一样的。

例如：

通常选择余数为

2.整数环

，其中任意两个数的加法和乘法运算模m的结果仍属于

加法逆元始终存在：

乘法逆元不一定存在：，当且仅当时，即a和m的最大公约数为1时，a存在乘法逆元。

思考：为什么a和m互质时，a存在乘法逆元？

3.经典替换密码

凯撒密码：将明文中的每个字母在字母表中移动固定长度的位置。

仿射密码：将铭文乘以密钥的一部分，然后再加上密钥的剩余部分。

缺点：密钥空间小，易穷举破解；明文和密文之间的映射关系是固定的，易用频率分析方法破解。

第二章 序列密码

2.1 引言

1.对称密码可以分为序列密码和分组密码。

序列密码：单独加密每个位，将密钥序列中对应的一位与明文的一位相加后模2。

分组密码：每次使用相同的密钥加密整个明文位分组。

2.序列密码中加密和解密使用相同的函数。

可以证明解密函数的确可以得到明文位，即将代入到解密函数中，能得到明文。

这得益于的值总是0。

3.为什么可使用简单的模2加法来进行加密？

模2加法与XOR（异或）运算是等价的。

对于一位明文无论是0或1，如果密钥位完全随机，密文为0或1的概率完全相等。

4.密钥序列位的本质是什么？

密钥序列（即所有)是序列密码安全性的核心问题。序列密码的安全性完全取决于密钥序列。

密钥序列位的核心要求是对攻击者而言它必须看上去是随机的。

2.2 随机数与牢不可破的分组密码

1.随机性对于序列密码的安全性十分重要，三种随机数生成器（RNG）：

真随机数生成器（TRNG）：输出不可复制，基于物理过程（例如抛硬币，掷色子等）生成序列。

伪随机数生成器（PRNG）：从一个初始种子值开始通过各种计算得到序列。一个广泛使用的例子是ANSI C中的rand()函数，它的参数为：对PRNG的一个一般要求是，它必须拥有良好的统计属性，意味着它的输出近乎与真随机数序列相同。

加密安全的伪随机数生成器：是PRNG的一个特例，具有不可预测性。即给定密钥序列中的n个连续位，不存在一个时间复杂度为多项式的算法使得成功预测下一位概率超过50%。之前的任何一位也是不可计算的。

2.无条件安全

如果一个密码体制在无限计算资源的情况下也不能被破译，则说明它是无条件安全的或信息理论上安全的。

2.一次一密：一个简单的无条件安全的密码

通过真随机数生成器得到密钥序列；只有合法的通信方才知道密钥序列；每个密钥序列位仅使用一次。

缺点1：密钥长度必须和明文长度一样。

缺点2：密钥只能使用一次，传输代价高。

3. 实际使用的序列密码

使用伪随机数生成器替换真随机密钥序列位，其中密钥k是种子。

是计算安全，而非无条件安全。

4.计算安全

如果为破解一个密码体制，最好的已知算法需要至少t个操作，则说明此密码体制是计算安全的。

5.利用PRNG构建密码流

PRNG可以用来生成密钥流，但是对序列密码而言是不够的，因为对手攻击也很聪明。

假设一个基于线性同于发生器的PRNG，其密钥包含值（A，B）。假如攻击者知道明文的前300位，由于模数m是公开已知的，在密文的基础上，可以推出密钥序列的前300位，进而推出A和B（的多个解）。如果得到已知明文的第四片信息，就可以唯一的检测出密钥。

也就是说，如果已知一些明文片段，我们可以计算出密钥并解密整个密文。

6.利用CSPRNG构建密钥序列

相当一部分在密码学之外使用的伪随机数生成器都不是密码学安全的。

实际中的序列密码有三种：①针对软件实现优化的密码，计算一个密钥序列为通常需要更少的CPU指令；②针对硬件实现优化的密码，一个典型的例子是反馈移位寄存器；③将分组密码作为基本块来实现序列密码。

2.3 基于移位寄存器的序列密码

一种得到长伪随机序列的简单方法就是使用线性反馈移位器寄存器（LFSR），典型的LFSR是A5/1密码和A5/2密码，它们作为标准被用于GSM手机网络中手机与基站之间的语音加密。

1. 线性反馈移位寄存器（LFSR）

由若干时钟存储元件（触发器）和一个反馈路径组成。

一个拥有m个触发器的LFSR可以称为“度为m”。

反馈路径计算一位寄存器中某些触发器的XOR和，并将其作为上一个触发器的输入。

某条反馈路径是否活跃则取决于反馈系数，将触发器的输出与它对应的系数相乘 ,表示反馈是活跃的，对应触发器的输出均为0。

LFSR有时也称为线性递归。

度为的LFSR可以产生的最大序列长度为。

在针对单个LFSR的已知明文攻击中，一旦敌手知道了反馈系数，就可以构建LFSR，并加载他已经知道的任意个连续的输出位。

2. Trivium

是一个较新的序列密码，它的密钥长度位80位，是基于三个移位寄存器的组合。

这三个寄存器的长度分别为93、84和111位，总长度288。

每个寄存器的输出都与另一个寄存器的输入相连，寄存器以一种类似环的形式排列。

使用Trivium加密时需要两个输入参数（密钥和初始向量），主要目的是即使在密钥不改变的情况下，此密码产生的两个密钥序列也必须不同。如果不适用变化的，序列密码也是高度确定的。

与绝大多数的分组密码（比如AES）相比，这个硬件实现相对较小但却非常快。

3. eSTREAM项目

为推动序列密码设计为项目目标。

分为两种配置，分别是针对要求高吞吐量的软件应用程序而设计的密码和针对资源有限（比如有限存储、有限门数量或有限功耗）的硬件应用程序而设计的密码。

在收到的34个候选密码中，满足希望属性的由4个面向软件（配置1）的密码和3个面向硬件（配置2）的密码。

面向软件：HC-128、Rabbit、Salsa/12和SOSEMANUK。

面向硬件：Grain V1、MICKEY V2和Trivium。

4. 真随机数的生成

所有TRNG都需要利用一些熵源，即一些真正随机的过程。

大致分为两类：一类是使用专门设计的硬件作为熵源的方法，例如半导体噪音、不相关的振荡器；另一类是利用外部随机源的TRNG，例如在网络接口中计算触键间隔或包的到达时间的计算机系统。

第三章 数据加密标准与替换算法

在过去30年的大多数时间里，数据加密标准（Data Encryption Standard， DES）是最主流的分组密码。

3.1 DES简介

1. 起源

1972，美国标准局（NBS）号召在美国实行标准密码。

1974，NBS从IBM的一个密码研究小组提供的方法中找到一个基于Lucifer密码的加密算法DES。

1977，NBS发布了修订后的IBM密码的所有规范，将其命名为数据加密标准（FIPS PUB 46），此时DES的有效期设置为1987年。

1987，NIST重新声明对DES的使用推迟至1999年。

1999，DES最终被高级加密标准（AES）所取代。

2. 基本操作

混淆（Confusion）：一种使密钥与密文之间的关系尽可能模糊的加密操作。常用的方式是替换。

扩散（Diffusion）：一种为了隐藏明文的统计属性而将一个明文符号的影响扩散到多个密文符号的加密操作。最简单的方式是位置换。

乘积密码（Product cipher）：将扩撒操作串联起来建立的更为强壮的密码。

扩散属性：意味着修改明文中的1位将会导致平均一半的输出位发生改变，即第二位密文看上去与第一位密文完全没有关系。例如：明文和采用分组密码扩散之后得到的密文分别是和。

3.2 DES算法概述

1. DES是一种使用56位密钥对64位长分组进行加密的密码。

2. DES的整体设计

DES是一种对称密码，其加密过程和解密过程使用相同的密钥。

DES是一种迭代算法，每个分组的加密过程都包含16轮，每轮的操作完全相同。

DES使用的是Feistel网络，其结构主要包括对明文进行初始置换、进行16轮操作、逆初始置换得到密文。

在每一轮操作中，明文会被分为和两部分，会被送入函数中，的输出将与进行异或，最后左右两部分进行交换进入下一轮。每轮中的轮密钥均来自56位的主密钥，生成过程是通过密钥编排（key schedule）实现的。函数内部实现扩散和混淆。

3. DES的内部结构

初始置换和逆初始置换：均是按位置换，可以看作是简单的交叉连接，即将第58位放在第1位，将第50位放在第2位等，存在一个初始置换表和逆初始置换表，两个表互逆。

函数：将输入分成位的分组，然后将其扩展为位（E-盒），然后再将每组位数放入S-盒中进行置换成位。扩展的方法是将某一位插入到不同的分组中，存在一张扩展表。所有S-盒中的置换表都不相同，作用是将位值映射为位，表格的读取方式是将最高位和最低位组合起来选择行，中间4位选择列。例如，S-盒的输入，行为，列为，查表得到08，即。S-盒是DES中最重要的元素，因为S-盒在密码中引入了非线性，即。S-盒 可以抵抗各种高级的数学攻击，尤其是差分密码分析，而差分密码分析直到1990年的一次学术论坛上才第一次被公开，当时IBM小组宣称设计者早在16年前就已经直到此攻击的存在，并说明DES就是专门为了抵抗差分密码分析而设计的。

密钥编排：从原始的56位密钥中得到16个轮密钥，轮密钥又称子密钥。56位密钥首先及逆行一次置换选择，然后分为和两部分，然后分别对每一部分进行循环移位，每循环移位一次得到56位密钥，进行一次置换选择后输出为一个子密钥。

3.4 解密

DES的优势之一是其解密过程与加密过程在本质上是完全相同的。解密过程中轮密钥采用密钥编排逆转生成。解密函数的每轮操作都是DES加密中对应轮的逆。第一轮解密后得到的结果实际上与最后一轮加密前的结果相等。

3.5 DES的安全性

1. 密码攻击可以分为穷尽密钥搜索攻击（或蛮力攻击）与分析攻击。

2. 在DES提出后不久，针对DES密码强度的批评主要围绕以下两个方面：(1) 密钥空间太小；（2）可能存在利用S-盒数学属性的分析攻击。利用穷尽密钥搜索攻击就可以较容易地破解单重DES，但至今还没发现能高效破解多重DES地攻击方式。

3. DES穷尽密钥搜索

输入：至少一个明文密文对

输出：满足的

攻击：测试所有个可能的密钥，直到以下条件成立：

（找到错误密钥的可能性只有，错误密钥指的是只能正确解密一个密文而不能正确解密后续密文的密钥。）

普通计算机并不适合用来执行次密钥测试，但可以选择专门用来搜索密钥的机器。

（1）1993 CRYPTO，Michael Wiener提出了一种非常高效的密钥搜索机器设计方案，该方案使用的是管道技术。

（2）1988年，EFF构建了一个硬件机器，叫Deep Crack，它使用蛮力攻击可以在56个小时内破解DES。

（3）2006年，来自德国波鸿大学和基尔大学一个研究学者小组基于商业集成电路构建了COPACOBANA机器破解DES的搜索时间平均不到7天。

56位的密钥大小已经不足以保证当今机密数据的安全性。

4. 分析攻击

1990，Eli Biham和Adi Shamir发现了所谓的差分密码分析（DC）理论上可以破解任何分组密码，但DES的S-盒可以很好地抵抗这种攻击。

1993，公布了线性分析攻击（LC）。

DC和LC成功地发动一次攻击分别需要知道和个明文-密文对，这些数字看上去非常不切实际，因为：（1）攻击者需要知道相当多的明文；（2）搜集和存储这样大地数据量需要花费相当长地时间，也需要相当大地内存资源；（3）攻击只能恢复一个密钥。

3.6 软件实现与硬件实现

软件实现是指在桌面CPU或类似智能卡或手机地嵌入式微处理器上运行DES。硬件实现是指在诸如专用集成电路（ASIC）或现场可编程门阵列（FPGA）的IC上运行DES实现。

1. 软件实现：最常见的思路是使用一些表，这些表里的数据来自于一些DES操作预计算的值，例如一些S-盒预计算的值盒置换预计算的值。DES中使用的小型S-盒在硬件实现上非常高效，但在现代CPU上的效率一般。加快DES软件实现的一个值得注意的方法是位分片（bitslicing）。

2. 硬件实现：DES的一个设计标准就是硬件实现的效率，类似E置换、P置换、IP置换和IP^-1置换的置换操作非常易于用硬件实现，因为它们只需要布线而不需要逻辑，通常使用布尔逻辑实现，即逻辑门。

3.7 DES的替换算法

1. AES（Advanced Encryption Standard，高级加密标准）：密钥长度有128位、192位和256位三种，目前没有出现成功破译AES的分析攻击。

2. 3DES与DESX：三重DES，即由三个连续的DES加密组成，可以表示为，其中是三个不同的密钥。3DES在硬件实现上非常高效，但在软件实现上却不那么高效。增强DES的另一种方法是使用密钥漂白，做法为在DES算法之前和之后将明文和密文分别与另外两个64位密钥和进行异或操作，可以表示为。

3. 轻量级密码PRESENT：轻量级是指实现复杂度非常低的算法，尤其指硬件实现方面。PRESENT是一个替换-置换网络，由31轮组成。

第四章 高级加密标准

高级加密标准（AES）是目前使用最为广泛的一种对称密码。

1. AES的发展历程

3DES的软件实现并不高效，其分组大小相对较小，如果要防止量子计算机攻击DES，密钥长度最好应该接近256位。

1997年，NIST提出向社会征集新的高级密码标准（AES）。

2001年，NIST宣布分组密码Rijndael成为新的AES，它由比利时的两位年轻密码学家Joan Daemen和Vincent Rijmen设计。

2. AES算法概述

AES的输入、密钥、输出均为128位。明文在AES中的每一次迭代都成为一种状态。

AES由三种类型的层组成，分别由10轮的字节代换层、扩散层和密钥加法层组成。

字节代换层（S-盒）：状态中的每个元素都使用具有特殊数学属性的查找表进行线性变换。

扩散层：包括ShiftRow（行移位变化）层盒MixColumn（列混淆变换）层。

密钥加法层：128位轮密钥（又称子密钥）来自于密码编排中的主密钥，它在该层与状态进行异或操作。

3. AES的内部结构

16字节的输入按字节输入到S-盒中，16字节的输出先在ShiftRows层按字节进行置换，然后由MixColumn变换进行混淆。最后将128位的子密钥与中间结果进行异或计算。

AES是一个面向字节的密码，DES使用了大量的位置换，可以看作是拥有面向位的结构。

AES的16个字节按照4字节乘4字节的矩阵排列。

字节代换层的S-盒代换是一个双向映射，即个可能的输入元素都与一个输出元素一一对应。S-盒通常使用一个拥有固定项的、256位乘8位的查找表实现。字节代换层的操作可以表示为，不存在的输入值。

扩散层由两个子层组成，分别为ShiftRow变换和MixColumn变换。ShiftRow变换循环往复地将状态矩阵地第二行向右移动三个字节，将第三行向右移动两个字节，将第四行向右移动一个字节。MixColumn步骤是一个线性变换，它混淆了状态矩阵地每一列。长度为4字节地每列都可以看作是一个向量（向量的每个元素是一个字节），该向量与一个固定的的矩阵相乘，此矩阵包含常量的项。

密钥加法层的两个输入分别是16字节的当前状态矩阵和长度为16字节的子密钥，这两个输入是通过按位异或操作组合在一起。

密钥编排将原始输入密钥（128位、192位或256位）作为输入，得到AES每轮使用的子密钥。子密钥的个数等于轮数加一，这是因为第一个密钥加法层进行密钥漂白时也需要密钥。AES子密钥的计算是递归的，即为了得到子密钥，子密钥必须是已知的。AES的密钥编排是面向单词的，其中1个单词=32位，子密钥存储在一个由单词组成的扩散密钥数组中。

128位密钥AES的密钥编排：11个子密钥存储在元素为的扩散密钥数组中，其中对应。11个密钥可以预先被计算出来，然后再对明文进行加密或对密文进行解密。也可以在对明文（密文）进行加密（解密）的过程中，每轮都会产生一个新的子密钥。