《应用密码学》课件第4章 序列密码

2.3.3单字符多表替换密码技术复习：Vernam（弗纳姆）密码技术1917年美国电话电报公司的GilbertVernam为电报通信设计了一种十分方便的密码技术。后来称之为Vernam密码技术.它是一种代数密码技术：其加密方法是，将明文和密钥分别表示成二进制序列，再把它们按位进行模2加法。设明文m=m1m2…，密钥k=k1k2…，其中mi，ki∈GF(2)，i≥1，则密文c=c1c2…，其中ci=mi

⊕ki。这里

⊕为模2加法。由模2加法的性质可知，Vernam密码技术的解密方法和加密方法一样，只是将明文和密文的位置调换一下：mi=ci

⊕ki。[例2-5]：设明文m=01100001，密钥k=01001110，使用Vernam密码加密求密文。解：加密得：c=m⊕k=01100001⊕01001110=00101111，

为了增强Vernam密码技术的安全性，应该避免密钥的重复使用(?)。假设我们可以做到密钥是真正的随机序列，密钥的长度大于或等于明文的长度，一个密钥只使用一次，那么Vernam密码技术是经得起攻击的考验的。(?)当Vernam密码体制中的密钥序列是随机的“0,1”序列，就是所谓的“一次一密”的密码体制。香农已经证明“一次一密”密码体制在理论上是不可破译的。但由于随机的密钥序列的产生、存储以及分配存在的一定困难，因此Vernam密码体制在当时并没有得到广泛的应用4.1密码学中的随机数为什么在密码学中要讨论随机数的产生？很多密码算法都需要使用随机数，因而随机数在密码学中起着重要的作用。DES加密算法中的密钥：DES密钥空间大小为256，如果密钥k是随机产生的，那么对方要尝试256个可能的密钥值。但是如果密钥k这样产生：选取一个16位随机秘密s，然后利用一个复杂但是公开函数f将其扩展为56位密钥k，这是对方只要尝试216个可能的密钥值就能找到真正密钥。4.1.1随机数及其性质序列密码的保密性完全取决于密钥的随机性。如果密钥是真正的随机数，则这种体制在理论上是不可破译的。但这种方式所需的密钥量大得惊人，在实际中是不可行的。---有多惊人？因此，目前一般采用伪随机序列来代替随机序列作为密钥序列，也就是序列存在着一定的循环周期性。这样序列周期的长短就成为保密性的关键。如果周期足够长，就会有比较好的保密性。现在周期小于1010的序列很少被采用，周期长达1050的序列也并不少见。1．随机数关于随机数，在不同的领域或从不同的角度有许多不同的说法。目前，通常所讲的随机数是指没有规律的数据。2．随机数的性质（1）随机性随机数在密码学的应用中的无规律性，主要体现在：①具有均匀分布、总体良好的随机统计特征，能通过均匀性检验、独立性检验、游程检验等基本的统计特性检验；②不能重复产生，即在完全相同的条件下，将得到两个不相关的随机序列。（2）不可预测性不可预测性是指即使给出的产生序列的硬件和所有以前产生序列的全部知识，也不能预测下一个随机位是什么，因而随机序列是非周期的。在实际的双向认证或会话密钥产生等的应用中，不仅要求随机序列具有随机性，还要求对序列中的数是不可预测的。4.1.2随机数的生成方法计算机上的随机数产生器并不是随机的，因为计算机一直是具有完全确定性的机器，特别在行为随机性方面表现不尽人意。目前，随机数的生成有以下两类方法。（1）物理方法：是指利用自然界的一些真的随机物理量来生成随机数。比如，放射性衰变、电子设备的噪声、宇宙射线的触发时间等。一般来说，用物理方法得到的随机数具有很好的随机性，但是由于具有的不可重复性，使得统计模拟和验证十分困难。此外，该方法产生随机数的速度和物理随机数发生器的稳定性也使得此方法的应用受到限制。（2）利用计算机来产生随机数，即数学方法。这类方法由一个初始状态（称为“种子”）开始，通过一个确定的算法来生成随机数。一旦给定算法和种子，输出的序列就是确定了的，因而产生的序列具有周期性、规律性和重复性，不是真正的随机数，而是伪随机数

（PseudoRandomNumbaer,PRN），产生伪随机数的算法或硬件一般称之为伪随机数生成器（PseudoRandomNumbaerGenerator,PRNG）。PRNG是一个生成完全可预料的数列（称为流）的确定性程序。一个编写得很好的

PRNG可以创建一个序列，而这个序列的属性与许多真正随机数的序列的属性是一样的。例如：PRNG可以以相同几率在一个范围内生成任何数字；PRNG可以生成带任何统计分布的流；由PRNG生成的数字流不具备可辨别的模。PRNG实现简单、速度快、经济，而且在目前的许多应用中并不一定必须使用真正的随机数，只要产生的伪随机数的随机性能满足应用需求就可以。

就目前而言，PRNG在众多应用都发挥着重要的作用，比如模拟（蒙特卡洛方法）、电子竞技和密码应用等。目前应用的随机数都是通过PRNG产生的、满足一定随机性要求的伪随机数。但是在应用中，往往要求伪随机数应尽可能地接近真的随机数的特性，比如具有良好的统计分布特性（能通过基本的被认可的统计检验）、具有足够长的周期等。一般来说，只要产生的伪随机数能够通过足够多的、良好的统计检验，就可以放心地将伪随机数当随机数来使用了。-[补充]

伪随机数（PRNG）生成器算法实现（1）C程序实现-程序（rand01.c）完整地阐述了随机数产生的过程：

首先，主程序调用random_start()方法

random_start()方法中”movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);”函数用来移动内存数据，其中FP_SEG（farpointertosegment）是取temp数组段地址的函数，FP_OFF（farpointertooffset）是取temp数组相对地址的函数，movedata函数的作用是把位于0040:006CH存储单元中的双字放到数组temp的声明的两个存储单元中。这样可以通过temp数组把0040:006CH处的一个16位的数送给RAND_SEED。

紧接着，输出随机数（调用random()方法）

Random()是根据随机种子RAND_SEED的值计算得出随机数：RAND_SEED=(RAND_SEED*123+59)%65536;注意：随机数的计算方法在不同的计算机中是不同的，即使在相同的计算机中安装的不同的操作系统中也是不同的。（比如在linux和windows下相同的随机种子在这两种操作系统中生成的随机数是不同的，这说明它们的计算方法不同。）

随机种子是从哪儿获得的？

随机种子为什么是在内存的0040:006CH处取？那么0040:006CH处存放的是什么？

学过《计算机组成原理》课程应该记得在编制ROMBIOS时钟中断服务程序时，会用到Intel8253定时/计数器，它与Intel8259中断芯片的通信使得中断服务程序得以运转，主板每秒产生的18.2次中断正是处理器根据定时/记数器值控制中断芯片产生的。在计算机的主机板上都会有这样一个定时/记数器用来计算当前系统时间，每过一个时钟信号周期都会使记数器加一，而这个记数器的值存放在哪儿呢？

这个记数器的值就存在内存的0040:006CH处，其实这一段内存空间是这样定义的：

TIMER_LOWDW?；地址为0040:006CHTIMER_HIGHDW?；地址为0040:006EHTIMER_OFTDB?；地址为0040:0070H

时钟中断服务程序中，每当TIMER_LOW转满时，此时记数器也会转满，记数器的值归零，即TIMER_LOW处的16位二进制归零，而TIMER_HIGH加1。

在程序rand01.c中的”movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);”正是把TIMER_LOW和TIMER_HIGH两个16位二进制数放进temp数组，再送往RAND_SEED，从而获得了“随机种子”。因此，我们可以确定的是：随机种子来自系统时钟，确切地说，是来自计算机主板上的定时/计数器在内存中的记数值。

由此可知，随机数是由随机种子根据一定的计算方法计算出来的数值。所以，只要计算方法一定，随机种子一定，那么产生的随机数就不会变。（2）C++程序实现1

在相同的平台环境下，编译生成exe后，每次运行它，显示的随机数都是一样的。这是因为在相同的编译平台环境下，由随机种子生成随机数的计算方法都是一样的，再加上随机种子一样，所以产生的随机数就是一样的。（3）C++程序实现2

本实现中，用户和其他程序没有设定随机种子，则使用系统定时/计数器的值做为随机种子，所以在相同的平台环境下，编译生成exe后，每次运行它，显示的随机数会是伪随机数，即每次运行显示的结果会有不同。（4）生成随机串(C++程序)实现4.1.3伪随机数的评价标准如果一序列产生器是伪随机的，它应有下面的性质：（1）看起来是随机的，表明它可以通过所有随机性统计检验。现在有许多统计测试。它们采用了各种形式，但共同思路是它们全都以统计方式检查来自发生器的数据流，尝试发现数据是否是随机的。确保数据流随机性的最广为人知的测试套件就是GeorgeMarsaglia的DIEHARD软件包（请参阅/pub/diehard/）。另一个适合此类测试的合理软件包是pLab（请参阅http://random.mat.sbg.ac.at/tests/）。（2）它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。（3）它不能可靠地重复产生。如果用完全同样的输入对序列产生器操作两次将得到两个不相关的随机序列。（？）4.2序列密码的基本原理4.2.1序列密码的概念序列密码算法将明文逐位转换成密文，如下图所示。在序列密码中，明文按一定长度分组后表示成一个序列，称为明文流（序列中的每一项称为明文字）。加密时，先由种子密钥（或称为主密钥）通过密钥流产生器产生一个密钥流序列，该序列的每一项和明文字具有相同的比特长度，称为密钥字；然后依次把明文流和密钥流中的对应项做二元加法运算（异或运算），产生相应的密文字，由密文字构成密文流输出。解密过程是将同样的密钥流与密文流中的对应项做二元加法运算，恢复出原来的明文流。假设明文流m=m1,m2,m3,…,mi,…；密钥流k=k1，k2，k3，…,ki,…序列密码的加密算法为：ci

=mi⊕ki序列密码的解密算法为：mi

=ci⊕ki由于mi⊕ki⊕ki=mi，所以解密算法是正确的。[例5-3]：假设当前的明文字为01101010，密钥流生成器生成的当前密钥字为10110111，加解密均为按位异或加运算，则得到的密文字为：01101010⊕10110111=11011101解密时用相同的密钥字为：11011101⊕10110111=01101010实际的序列密码算法安全性依赖于密钥生成器所产生的密钥流的性质。如果密钥流是无周期的（真正随机的）无限长随机序列，那么此时的序列密码即为“一次一密”的密码体制。4.2.2序列密码体制的分类

在序列密码中，根据状态函数是否独立于明文或密文，可以将序列密码分为同步序列密码和自同步序列密码两类。1．同步序列密码在同步序列密码中，密钥流独立于消息流产生。同步密钥流生成器模型，它具有以下特点：（1）同步：在一个同步序列中，发送方和接收方必须是同步的，即用同样的密钥且该密钥操作在同样的位置（状态），才能保证正确的解密。（2）无错误传播：在传输期间，一个密文字（或位）被改变（不是删除和插入）只能影响该密文字（或位）的恢复，不会对后续密文字（或位）产生影响。（3）主动攻击破坏同步：按照同步要求，一个主动攻击对密文进行插入、删除或重放操作都会立即破坏其同步，从而可能被解密器检测出来。作为无错误传播的结果，主动攻击者可能有选择地对密文进行改动，并准确地知道这些改动对明文的影响，这时可以采用为数据源提供认证并保证数据完整性的技术。-同步密钥流生成器

举例OFB模式OFB模式的特性：

2．自同步序列密码自同步序列密码也称为异步流密码，其密钥流的产生不是独立于明文流和密文流的，与种子密钥和其前面已产生若干密文字有关。-自同步序列密码

举例CFB模式自同步密钥流生成器模型，它具有以下特点：（1）自同步：自同步的实现依赖于密文字被删除或插入，这是因为解密只取决于先前固定数量的密文字。自同步序列密码在同步丢失后能够自动重新建立同步，并正确地解密，只有固定数量的明文字不能解密。（2）有限的错误传播：因为自同步序列的状态取决于t个已有的密文字符，若一个密文字（或位）在传输过程中被修改（插入或删除），则解密时最多只影响到后续

t个密文字的解密，即只发生有限的错误传播。（3）难检测主动攻击：相比于同步，自同步使得主动攻击者发起的对密文字的插入、删除、重放等攻击只会产生非常有限的影响，正确的解密能很快自动重建。因此，主动攻击对自同步序列密码很困难的，可能需要采用为数据源提供认证并保证数据完整性的技术。有限的错误传播特性使得主动攻击者对密文字的任何改动都会引起一些密文字解密出错。（4）密文统计扩散：每个明文字都会影响其后的整个密文，即密文的统计特性被扩散到密文中。所以，自同步序列密码体制在抵抗利用明文冗余度而发起的攻击方面要强于同步序列密码。从CFB看自同步流密码DES是分组长为64bits的分组密码，但利用CFB模式或OFB模式可将DES转换为流密码。流密码不需要对消息填充，而且运行是实时的。因此如果传送字母流，可使用流密码对每个字母直接加密并传送。流密码具有密文和明文一样长这一性质。——以后回过头来看CFB模式

4.2.3序列密码与分组密码的比较分组密码和序列密码的不同主要表现在以下两方面：（1）分组密码是以一定的固定长度的分组作为每次处理的基本单元；而序列密码则是以一个元素（一个字符或一个比特位）作为基本处理单元。（2）分组密码使用的是一个不随时间变化的固定变换，具有扩散性好、插入敏感等优势，其缺点是加密处理速度慢，存在错误传播；而序列密码是用的一个随时间变换的加密变换，具有传播速度快、低错误传播和硬件实现电路简单等优势，其缺点是低扩散（意味着混乱不够）、插入及修改不敏感。序列密码体制的安全性取决于密钥流的性能，当密钥流是完全的随机序列时，序列密码是不可破的；随机序列的主要特点表现为无规律性和不可预测性。如果密钥流能做到真正的随机，此时的序列密码就是“一次一密”的密码体制，是绝对安全的。在实际应用中，密钥流都是用有限存储和有限复杂逻辑的电路来产生的，此时的密钥流只有有限个状态。这样的密钥流生成器迟早要回到初始状态而使其呈现出周期性。但如果密钥流周期足够长，且随机性好，其安全强度是可以得到保证的。因此，序列密码的安全强度取决于密钥流生成器的设计。目前，产生密钥流最重要的部件是线性反馈移位寄存器（LFSR，LinearFeedbackShiftRegister），这是因为LFSR非常适合硬件实现、能产生较大周期和统计特性良好的序列，以及能够用代数方法对产生的序列进行很好的分析。常见的密钥序列产生器目前，最为流行和实用的密钥流产生器大多基于线性反馈移位寄存器（LinearFeedbackShiftRegister,LSFR）。如下图所示，其驱动部分是一个或多个线性反馈移位寄存器。LFSR………FLFSR1LFSR2LFSRn……FFF2024/3/19374.3线性反馈移位寄存器

-定义：反馈移存器的反馈逻辑电路可用一布尔函数f(a1,a2,…,an)来表示，若对应的布尔函数是线性函数，则称该反馈移存器为线性反馈移存器LFSR(linearfeedbackshiftregister)，否则称为非线性反馈移存器。ajaj-2aj-3aj-1图1线性反馈移位寄存器ajaj-2aj-3图2非线性反馈移位寄存器2024/3/1938此时LFSR函数可写为：f(a1,a2,…,an)=cna1

cn-1a2

…

c1an上图中，常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，这样的线性函数共有2n个。输出序列{at}满足：a1+t=cnat+1

cn-1at+2

…

c1an+t其中，t为非负正整数。如下图所示，是一个LFSR:（1）线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一，也非常适合用硬件实现；（2）可以产生大周期序列；（3）可以产生具有良好统计性质的序列；（4）易于利用代数方法对其进行分析。n级线性移存器的线性递推式表示-优势：2024/3/1939-工作原理(如下图)假设在j时刻其内部状态为：在j+1时刻其内部状态变为：其中：此时的输出为j时刻的最高级：n级反馈移位寄存器

每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成，如右图所示。2024/3/1940ajaj-2aj-1第7时刻001第0时刻001第1时刻100第2时刻110第3时刻111第4时刻011第5时刻101第6时刻010产生序列为：10011101……比如：2024/3/1941an-1an-2an-3an-4an2、反馈多项式表示一个r级线性移存器的反馈多项式表示为：x1x2x3x4通常，用来表示一个LFSR。2024/3/1942例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由下表求出。即输出序列为101110111011…，周期为4。2024/3/1943-具体来说：在初始状态下,即0时刻在第一个时钟到来时101f(a1,a2,a3)=a1a2⊕a3第1级第2级第3级S0=(1,0,1)输出10f(a1,a2,a3)=a1a2⊕a3第1级第2级第3级S1=(0,1,1)a1=1,a2=0,a3=11输出1a02024/3/1944每一时刻的状态可用n长序列“a1,a2,…,an

”n维向量“(a1,a2,…,an)”来表示，其中ai是第i级存储器的内容。初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并计算f(a1,a2,…,an)作为下一时刻的an。反馈函数f(a1,a2,…,an)是n元布尔函数，即n个变元a1,a2,…,an

可以独立地取0和1两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。-表示方法1、线性递推式表示一个r级线性移存器的线性递推式表示为：2024/3/1945则其输出序列和状态序列如下:

状态序列:(1,0,1)(0,1,1)(1,1,1)(1,1,0)(1,0,1)(0,1,1)….

输出序列:101110….

由上面的结果可以看出，这个反馈移位寄存器的状态序列和输出序列都是周期序列，其周期为4。在第二个时钟到来时11f(a1,a2,a3)=a1a2⊕a3第1级第2级第3级S2=(1,1,1)a1=1,a2=1,a3=01输出0a02024/3/19462024/3/1947例：一个5级线性反馈移位寄存器设一个GF(2)上的4阶线性反馈移位寄存器如下图所示，其反馈函数为f(x1，x2，x3，x4)＝x1⊕x2，初始状态为S0＝（1，0，1，1）容易验证该线性反馈移位寄存器的输出序列为：

101111000100110101111000100110……

这个线性移位寄存器序列是一个周期序列，周期为15。x4x3x2x1＋输出序列2024/3/1948（1）在线性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。

注：（2）若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定cn=1。（3）n级线性反馈移位寄存器的状态周期小于等于2n-1。输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1。

2024/3/1949/wiki/KeeLoq2015年11月份，由“神话”行动的一位18岁的安全研究员发现了汽车钥匙芯片Keeloq算法的漏洞。HCS滚码芯片和keeloq算法是目前很多汽车和门禁遥控钥匙采取的软硬件解决方案，车主每次按下钥匙的锁车键、开车键都会触发一次新的信号发出，车辆在收到信号后快速计算，决定是否打开车门。祖冲之算法集（ZUC算法）是由我国学者自主设计的加密和完整性算法（序列密码），包括祖冲之算法、加密算法128-EEA3和完整性算法128-EIA3，已经被国际组织3GPP推荐为4G无线通信的第三套国际加密和完整性标准的侯选算法。/item/祖冲之算法集/7177910?fr=aladdin4.3.2密钥序列的伪随机性*-（略）4.4非线性反馈移位寄存器（略）4.5序列密码算法的破译（略）

已知反馈多项式(或线性递推式)及初始状态可获得所产生的序列。而初始状态总是可以假定的，故知道了反馈多项式(或线性递推式)也就知道了该反馈多项式(或线性递推式)所产生的序列。那么反过来，已知序列能否获得相应的反馈多项式(或线性递推式)呢？答案是肯定的。4.5序列密码算法的破译（略）1.插入攻击2.已知明文攻击可得到c3＝1，c2＝0，c1＝1，从而得到特征多项式：p(x)=x3+x+1比如：若特征多项式p(x)=x3+x+1，初始状态为（101）的移位寄存器产生序列为(101001)。设明文为（011010），那么密文为（110011）。破译者计算mc得到密钥系列(101001)，那么可以得到下列矩阵方程式：

已知序列a是由n级线性移存器产生的，并且知道a的连续2n位，可用解线性方程组的方法得到线性递推式（特征多项式）和起始状态。2024/3/1954例：设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥序列是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程：例题2024/3/1955即：2024/3/1956从而得到：所以：

从而得到特征多项式：p(x)=x4+x+12024/3/19574.6常用的序列密码算法

基于LFSR的序列密码非常适合于硬件实现，但是不特别适合软件实现。这导致出现了一些关于序列密码被计划用于快速软件实现的新建议，因为这些建议大部分具有专利，因此这里不讨论它们的技术细节。比较常用的序列密码是A5、SEAL和RC4序列密码算法，A5是典型的基于LFSR的序列密码算法，SEAL和RC4不是基于LFSR的序列密码算法，而是基于分组密码的输出反馈模式（OFB）和密码反馈模式（CFB）来实现的。其他不基于LFSR的序列密码生成器的安全性基于数论问题的难解性，这些生成器比基于LFSR的生成器要慢很多。4.6.1A5序列密码算法*（略）4.6.2

SEAL序列密码算法*

（略）4.6.3

RC4序列密码算法RC4是美国RSA数据安全公司1987年设计的一种一个可变密钥长度（40至2048比特可变）、面向字节（256个bytes

）操作的序列密码。RSA数据安全公司将其收集在加密工具软件BSAFE中。最初并没有公布RC4的算法。人们通过软件进行逆向分析得到了算法；在这种情况下，RSA数据安全公司于1997年公布了RC4密码算法；

基本思想：对于n位长的字（RC4是8位长的字），它总共N=2n（RC4是28个）个可能的内部置换状态矢