（这篇文章本该有图的，实际却没有，因为画图太累惹……LFSR的部分对着图看效果会好很多，但我懒得画，同学们请自己脑补吧~）

何谓序列密码

上一章中我们了解了对称密码的一类炒鸡简单的情形：替换密码，这一章我们继续讲对称密码学。

通过对现有加密算法类型的归纳，我们发现对称密码主要可分为序列密码（Stream Ciphers）还有分组密码两大类。其差异是较大的：序列密码对每位加密，而分组密码将原文分成若干块进行加密。

序列密码相较分组密码使用较为不广泛一些，但它适合在计算资源受限的设备上运作（因为小而快？）。在效率上，二者的所差实际不多。

本章我们主要讨论序列密码，因为这是一个大话题。

序列密码分同步序列密码与异步序列密码两类。前者是在线的：实际使用的密钥由预设的密钥与原文一并生成；而后者是离线的，所设的密钥就是加密的密钥。容易看出，前者的安全性更高一些，但是所耗时间更久（因为不能并行计算了）。但实际生活中，还是同步序列密码用的更多一些。

至于序列密码的加解密，非常简单：加密是$y_i = e_{s_i}(x_i) = x_i + s_i \ mod \ 2$。解密是其反函数也便是其本身。

为什么序列密码的加密解密可以这么简单呢？因为在模二加法等价于异或，而已知$x_i, y_i, s_i$的一个元素无法求出剩下两个元素。只要$s_i$有良好的随机属性，那么已知原文的部分片段及密文是无法解出其他原文的。书上说，异或运算具有可逆性，是完全均衡的（输出有多原像且它们出现的概率均等）。这二者保证了序列密码是一种良好的对称密码。

从上文的表述我们容易发现：序列密码的安全性完全取决于密钥序列。故而密钥序列的生成是序列密码的关键。密钥序列必须有良好的统计属性，足够“随机”，这样才能提升安全性。故而，我们需要了解随机数相关的知识。

（序列密码也被称为Vernam加密，因为它最早在1917年由Gilbert Vernam发明）

随机数生成器

在讲随机数生成器之前，我们就不讲随机数了。顾名思义，随机数是数列中的概念，表明这一数列足够“随机”。至于“随机”，这是一个玄学词汇。我们往往会依据数据的各项统计属性刻画它的“随机性”，或，可预测性。在计算机中，我们会使用三类（其实是两类）随机数生成器（Random Number Generator）。

其一，TRNG（T for True），真随机数生成器，即通过各式物理过程生成随机数。这样做的好处在于输出几乎具有不可复制性。

其二，PRNG（P for Pseudo），伪随机数生成器，是可以计算出来的，但具有良好的统计属性（至于是什么属性，就别问啦）。比如ANSI C中的rand()函数，就是通过一个初始的种子还有一个运算实现的。

其三，CSPRNG（Cryptographically Secure Pseudo-Random Number Generator），密码学安全的伪随机数生成器。它是PRNG的一种特例，具有更多的属性：它不可预测（当然，这是不可能的，毕竟是伪随机数。这里不可预测指给定部分密钥，计算出前继位/后续位在计算上是不可行的，即不存在时间复杂度为多项式的算法能够确定前继位/后续位）。

我们先不管随机数生成器的实现细节，假设我们有了足够标准的上述三类随机数生成器作为我们的密钥流生成器，那么我们要怎么得到一个完美的序列密码的密钥呢？在此之前，我们需要看这个“完美”要如何定义：密码体制若在无限计算资源的情况下也无法破译，则其为无条件安全的，或信息理论上安全的。

很明显，这个定义和计算安全不一样，它更强一些。那么是否存在无条件安全的密码呢？一次一密（OTP，One-Time Password）便是这样一种无条件安全的密码。它有三个条件：①通过TRNG生成密钥序列；②有且仅有合法通信方知道密钥序列；③每一密钥序列位$s_i$仅被使用一次。

很明显，这样的OTP是无条件安全的。我们把等式系统写出来，容易发现这样一个等式系统是不可解的，知晓$s_i$与知晓$x_i$完全等价。这里用到了第一个条件：随机数是通过TRNG生成的。如不然，各位间存在这样那样的函数关系，即使求解很困难，这样的等式系统在理论上仍是可解的（因为它们彼此不独立），已知部分明文的话。

这样的OTP虽然理论上似乎很理想，但它的使用并不广泛，条件一首先是一个限制，但主要的问题在条件二与条件三，尤其是条件三。条件二要求信道绝对安全，但这并不容易满足。而条件三要求一段密钥只能用于一篇原文且密钥需与原文登长。这里，密钥只能使用一次的限制要求通信双方频频交换密钥，而密钥与原文等长的条件则大大提高了交换密钥的成本（想象一下，你在传输1GB的机密视频前要先交换1GB的密钥……）。

因为这些原因，实际生活中我们很少使用OTP。但它启迪了我们，只要密钥足够随机，攻击者便无法通过破解得到原文。所以问题在于如何设计随机数生成的算法使得得到的随机数足够随机，这是一个被研究了很久的话题，而我们不妨看看现实生活中的序列密码是生成随机数的，具体是如何运作的，它们与OTP存在怎样的不同。

需要说明的是，实际的序列密码均不是无条件安全的，我们期望它们是计算安全的，即采用最好的算法的操作数的下界也在我们的期望之上。但这一定义里存在许多问题，其中一个便是：“最好的算法”如何确定？

为了避免OTP多次交换密钥的麻烦，我们采取新的模式：通信双方交换一次短密钥，通过密钥序列生成器来依据初始密钥（它很像是种子）生成实际使用的密钥。

那么这个密钥生成器要如何设置呢？我们能否通过线性同余发生器（比如ANSI C中的rand()），一种PRNG得到密钥序列呢？很明显，不能。因为简单的已知明文攻击足够帮助攻击者计算出整个密钥。

所以，我们需要CSPRNG。利用反馈移位寄存器可以得到CSPRNG的一种可能。那么我们就来学学吧。

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

本节所述“移位寄存器“均为线性反馈移位寄存器（LFSR，Linear Feedback Shift Register）。它由若干时钟存储元件（触发器）还有一个反馈路径组成。触发器的个数称LFSR的度。LFSR通过反馈网络计算一些触发器的异或和，将其作为上一触发器的输入，重复此过程，这便是LFSR的基本运作模式。

书上给出了一种度为3的简单的LFSR模型，我们能够通过它对LFSR的运作模式产生一些感性的印象。于是，我们可以抽象出LFSR的数学描述。我们注意到，触发器输出后的开关决定了该输出是否参与反馈，故我们可以$p_j$，反馈系数刻画某一输出对整一反馈路径的贡献。而本次输出与且仅与反馈系数、此前的输出（输入也算在输出里了）存在关联。简单归纳后我们不难得到：

$s_{i+m} = \sum\limits_{j = 0}^{m-1} p_j \cdot s_{i+j} \ mod \ 2, s_i, p_i \in \{ 1, 2 \}, i = 0, 1, 2, \dots$。

显然，本次输出是此前输出的一些线性组合，故LFSR也被称为线性递归（为啥不叫递推呢）。

很自然，LFSR中可能的状态共$2^m$种，其中全0的下一个状态还是全0。至于其他状态，它必然绘在若干步之后陷入某个循环之中。故度为m的LFSR可产生的最大序列长度为$2^m - 1$。

我们如何确定LFSR的循环节，换言之，我们如何确定$(s_i, s_{i+1}, \dots, s_{i+m-1})$在给定的递推条件下多少步后会走进一个循环里呢？我们考虑这一LFSR的特征多项式$P(x) = x^m + p_{m-1}x^{m-1} + \dots + p_1 x + p_0$。那么当此多项式为本原多项式时输出序列的周期能取到$2^m - 1$。证明？我不懂哦。

至于LFSR的安全性，其实它是堪忧的。如果LFSR被作为序列密码使用，那么密钥k便是反馈系数向量$(p_{m-1}, \dots, p_1, p_0)$。假设攻击者知道一些明文，一些密文，他还知道LFSR的度m，那么他便可以展开攻击了：把$s_m = \dots, s_{m+1} = \dots$写出来，只要m个方程就够了。然后我们发现这是一个由m个方程组成的m元一次异或方程组，跑个高消就能解出密钥了。这足以说明LFSR的密码学属性之差了。这也反映LFSR是一个具有良好统计属性但密码学属性的PRNG实例。

然而，LFSR并未丧失其所有密码属性，我们可以把多个LFSR垒在一起得到一个健壮的密码体系。比如Trivium就是这么来的。至于为什么垒在一起就更安全了呢……这我就不懂了。

书中介绍的Trivium是一种较新（新？2005年呀）的序列密码，它是否安全还是有待时间检验的（好像是有不少攻击，网上能搜得到，虽说并未细看）。它是把三个移位寄存器垒在一块，然后它的独特之处在于放了个AND操作，这样Trivium的数学描述便不完全是线性的了。这Trivium的设计初看也挺复杂，就不分析了。

事实上，序列密码非常非常容易受选择明文攻击。因此，我们需要在输入参数里加入一个nouce，它是随机生成的，并不需要保密，只是用于让同一密钥每次生成的密钥序列都不相同，以抵御选择明文攻击。

Trivium的加密分三个阶段：初始化，热身，加密。初始化阶段用于读入nonce还有清空寄存器；热身阶段计时4×288=1152次，用于充分随机化密码；加密阶段从第1153周期开始，每位吐出的位便是密钥序列位。

Trivium的一大特点在于它的紧凑性（硬件实现上的紧凑）。Trivium由288位长的移位寄存器组成，其所占面积约为4000个门，大致可以16位/时钟周期的速率计算密钥序列（为什么是这样的呀）。来做一下简单的计算，假设硬件设计的主频是125MHz。那么加密速率为16位×125MHz=2G位/秒。（当然，没有比较，我们并无法知晓这快在哪里）

要点回顾

1.在绝大多数领域，分组密码的使用要广泛于序列密码，当然也有例外的情形，尤其是计算资源受限的情况之下。

2.在对随机数的要求少，很多时候PRNG就够了。但在密码学这一块，我们需要CSPRNG或是TRNG。

3.OTP是无条件安全的，但是它的应用比较受限，因为它苛刻的条件。

4.LFSR虽具有良好的统计属性，但它并非很好的序列密码，除非我们把多个LFSR组合起来。

习题

2.1是个人应该都会吧。顺便，Kaspar Hauser我个人并不是很喜欢。

2.2中提了一些概念：密钥的生命周期，生命周期内与外密钥的存储，密钥的生成与分发。要求我们以OTP为例解释这些概念。

1
2
3
4
5
6
一次一密系统在实际生活中的意义：在需要近乎绝对安全且对资源消耗几乎没有限制的场景下
密钥的生命周期：使用前无限期，使用后作废
在生命周期内密钥的存储：安全地存储
在生命周期后密钥的存储：无需存储
密钥的分发：通过安全的信道
密钥的生成：物理手段

2.3是找出多次使用的假OTP（不满足第三条件）的vulnerability。很明显，它易受已知明文攻击或者选择明文攻击。

2.4没意思。2.5让手工模拟LFSR的计算过程。

2.6已知明文攻击即可，解50个异或方程组即可。复杂度为$50 \times (200^3) = 4e8$，标准PC可以一跑。

2.7不懂。表2-3里没有m=8的本原多项式。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Understanding Cryptography exercise 2.8
// code by Ness
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
const int LEN = 4;
int feedback[LEN+1];
int seq[(1<<LEN)+5];
set<int> hash_pool;
int encode(int begin)
{
	int ans = 0;
	for(int i = 0;i < LEN;i++)
	{
		ans *= 2;
		ans += seq[begin + i];
	}
	return ans;
}
int calc(int begin)
{
	int ans = 0;
	for(int i = 0;i < LEN;i++)
		ans ^= (feedback[i] * seq[begin + i]);
	return ans;
}
void load_feedback(int id)
{
	feedback[4] = 1;
	if(id == 1) feedback[0] = feedback[1] = 1; // x^4 + x + 1
	if(id == 2) feedback[0] = feedback[2] = 1; // x^4 + x^2 + 1
	if(id == 3) feedback[0] = feedback[1] = feedback[2] = feedback[3] = 1; // x^4 + x^3 + x^2 + x + 1
}
int main()
{
	load_feedback(3);
	for(int seq_encode = 1;seq_encode < (1 << LEN);seq_encode++)
	{
		hash_pool.clear();
		int seq_encode_copy = seq_encode;
		for(int i = 0;i < 4;i++)
		{
			seq[i] = seq_encode_copy % 2;
			seq_encode_copy /= 2;
		}
		hash_pool.insert(encode(0));
		for(int step = 0;;step++)
		{
			seq[step + LEN] = calc(step);
			int hash_val = encode(step+1);
			if(hash_pool.count(hash_val))
			{
				for(int i = 0;i <= step + LEN;i++)
					printf("%d", seq[i]);

				printf(" %d\n", step+1);
				break;
			}
			else
				hash_pool.insert(hash_val);
		}
	}
	return 0;
}

（当然，2.8背后的数学原理我一点也不懂不要问我）

2.10也不知道什么情况就有点不想做……这本书的印刷是怎么回事？

2.11就一综合题，要求我们把之前所有的口胡都转化为实践，有点烦的……（还是口胡舒服啊）懒得跑高消，就手解方程组了。

2.12手工模拟即可，因为寄存器里的1很少（良心出题人），关于当下的1什么时候会转移到会有影响的位置就好了。算出来只有第2、3、68、69位是1。从这个例子我们可以看出来，Trivium的周期是较大的，某一位要经过较多shift操作之后才能影响到全局。