1、12024-3-192024-3-19112.3.3 单字符多表替换密码单字符多表替换密码技术技术复习：Vernam（弗纳姆）密码技术1917年美国电话电报公司的Gilbert Vernam为电报通信设计了一种十分方便的密码技术。后来称之为Vernam密码技术.它是一种代数密码技术：其加密方法是，将明文和密钥分别表示成二进制序列，再把它们按位进行模2加法。22024-3-192024-3-1922设明文m=m1m2，密钥k=k1k2，其中mi，kiGF(2)，i1，则密文c=c1c2，其中ci=mi ki。这里 为模2加法。由模2加法的性质可知，Vernam密码技术的解密方法和加密方法一样，只
2、是将明文和密文的位置调换一下：mi=ci ki。例2-5：设明文m=01100001，密钥k=01001110，使用Vernam密码加密求密文。解：加密得：c=m k=01100001 01001110=00101111，32024-3-192024-3-1933 为了增强Vernam密码技术的安全性，应该避免密钥的重复使用(?)。假设我们可以做到密钥是真正的随机序列，密钥的长度大于或等于明文的长度，一个密钥只使用一次，那么Vernam密码技术是经得起攻击的考验的。(?)当Vernam密码体制中的密钥序列是随机的“0,1”序列，就是所谓的“一次一密”的密码体制。香农已经证明“一次一密”密码体制
3、在理论上是不可破译的。但由于随机的密钥序列的产生、存储以及分配存在的一定困难，因此Vernam密码体制在当时并没有得到广泛的应用42024-3-192024-3-19444.1 密码学中的密码学中的随机数随机数为什么在密码学中要讨论随机数的产生？很多密码算法都需要使用随机数，因而随机数在密码学中起着重要的作用。DES加密算法中的密钥：DES密钥空间大小为256，如果密钥k是随机产生的，那么对方要尝试256个可能的密钥值。但是如果密钥k这样产生：选取一个16位随机秘密s，然后利用一个复杂但是公开函数 f 将其扩展为56位密钥k，这是对方只要尝试216个可能的密钥值就能找到真正密钥。52024-3
4、-192024-3-19554.1.1 随机数及其随机数及其性质性质序列密码的保密性完全取决于密钥的随机性。如果密钥是真正的随机数，则这种体制在理论上是不可破译的。但这种方式所需的密钥量大得惊人，在实际中是不可行的。-有多惊人？因此，目前一般采用伪随机序列来代替随机序列作为密钥序列，也就是序列存在着一定的循环周期性。这样序列周期的长短就成为保密性的关键。如果周期足够长，就会有比较好的保密性。现在周期小于1010的序列很少被采用，周期长达1050的序列也并不少见。62024-3-192024-3-19661随机数关于随机数，在不同的领域或从不同的角度有许多不同的说法。目前，通常所讲的随机数是指没
5、有规律的数据。72024-3-192024-3-19772随机数的性质（1）随机性随机数在密码学的应用中的无规律性，主要体现在：具有均匀分布、总体良好的随机统计特征，能通过均匀性检验、独立性检验、游程检验等基本的统计特性检验；不能重复产生，即在完全相同的条件下，将得到两个不相关的随机序列。（2）不可预测性不可预测性是指即使给出的产生序列的硬件和所有以前产生序列的全部知识，也不能预测下一个随机位是什么，因而随机序列是非周期的。在实际的双向认证或会话密钥产生等的应用中，不仅要求随机序列具有随机性，还要求对序列中的数是不可预测的。82024-3-192024-3-19884.1.2 随机数的生成随机
6、数的生成方法方法计算机上的随机数产生器并不是随机的，因为计算机一直是具有完全确定性的机器，特别在行为随机性方面表现不尽人意。目前，随机数的生成有以下两类方法。（1）物理方法：是指利用自然界的一些真的随机物理量来生成随机数。比如，放射性衰变、电子设备的噪声、宇宙射线的触发时间等。一般来说，用物理方法得到的随机数具有很好的随机性，但是由于具有的不可重复性，使得统计模拟和验证十分困难。此外，该方法产生随机数的速度和物理随机数发生器的稳定性也使得此方法的应用受到限制。92024-3-192024-3-1999（2）利用计算机来产生随机数，即数学方法。这类方法由一个初始状态（称为“种子”）开始，通过一个
7、确定的算法来生成随机数。一旦给定算法和种子，输出的序列就是确定了的，因而产生的序列具有周期性、规律性和重复性，不是真正的随机数，而是伪随机数（Pseudo Random Numbaer,PRN），产生伪随机数的算法或硬件一般称之为伪随机数生成器（Pseudo Random Numbaer Generator,PRNG）。PRNG是一个生成完全可预料的数列（称为流）的确定性程序。102024-3-192024-3-191010一个编写得很好的 PRNG 可以创建一个序列，而这个序列的属性与许多真正随机数的序列的属性是一样的。例如：PRNG 可以以相同几率在一个范围内生成任何数字；PRNG 可以生
8、成带任何统计分布的流；由 PRNG 生成的数字流不具备可辨别的模。PRNG实现简单、速度快、经济，而且在目前的许多应用中并不一定必须使用真正的随机数，只要产生的伪随机数的随机性能满足应用需求就可以。就目前而言，就目前而言，PRNG 在众多应用都发挥着重要的作用，比如模拟（蒙特在众多应用都发挥着重要的作用，比如模拟（蒙特卡洛方法）卡洛方法）、电子竞技电子竞技和和密码应用密码应用等等。112024-3-192024-3-191111目前应用的随机数都是通过PRNG产生的、满足一定随机性要求的伪随机数。但是在应用中，往往要求伪随机数应尽可能地接近真的随机数的特性，比如具有良好的统计分布特性（能通过基
9、本的被认可的统计检验）、具有足够长的周期等。一般来说，只要产生的伪随机数能够通过足够多的、良好的统计检验，就可以放心地将伪随机数当随机数来使用了。122024-3-192024-3-191212122024-3-192024-3-191212-补充补充 伪随机数（伪随机数（PRNG）生成器算法实现）生成器算法实现（1）C程序实现程序实现132024-3-192024-3-191313132024-3-192024-3-191313-程序（程序（rand01.c）完整地阐述了随机数产生的过程：）完整地阐述了随机数产生的过程：首先，主程序调用random_start()方法 random_star
10、t()方法中”movedata(0 x0040,0 x006c,FP_SEG(temp),FP_OFF(temp),4);”函数用来移动内存数据，其中FP_SEG（far pointer to segment）是取temp数组段地址的函数，FP_OFF（far pointer to offset）是取temp数组相对地址的函数，movedata函数的作用是把位于0040:006CH存储单元中的双字放到数组temp的声明的两个存储单元中。这样可以通过temp数组把0040:006CH处的一个16位的数送给RAND_SEED。紧接着，输出随机数（调用random()方法）Random()是根据随机
11、种子RAND_SEED的值计算得出随机数：RAND_SEED=(RAND_SEED*123+59)%65536;注意：随机数的计算方法在不同的计算机中是不同的，即使在相同的计算机中安装的不同的操作系统中也是不同的。（比如在（比如在linux和和windows下相同的随机种子在这两种下相同的随机种子在这两种操作系统中生成的随机数是不同的，这说明它们的计算方法不同。）操作系统中生成的随机数是不同的，这说明它们的计算方法不同。）142024-3-192024-3-191414142024-3-192024-3-191414 随机种子是从哪儿获得的？随机种子是从哪儿获得的？随机种子为什么是在内存的00
12、40:006CH处取？那么0040:006CH处存放的是什么？学过计算机组成原理课程应该记得在编制ROM BIOS时钟中断服务程序时，会用到Intel 8253定时/计数器，它与Intel 8259中断芯片的通信使得中断服务程序得以运转，主板每秒产生的18.2次中断正是处理器根据定时/记数器值控制中断芯片产生的。在计算机的主机板上都会有这样一个定时/记数器用来计算当前系统时间，每过一个时钟信号周期都会使记数器加一，而这个记数器的值存放在哪儿呢？这个记数器的值就存在内存的0040:006CH处，其实这一段内存空间是这样定义的：TIMER_LOW DW?；地址为 0040:006CH TIMER_
13、HIGH DW?；地址为 0040:006EH TIMER_OFT DB?；地址为 0040:0070H 时钟中断服务程序中，每当TIMER_LOW转满时，此时记数器也会转满，记数器的值归零，即TIMER_LOW处的16位二进制归零，而TIMER_HIGH加1。152024-3-192024-3-191515152024-3-192024-3-191515 在程序rand01.c中的”movedata(0 x0040,0 x006c,FP_SEG(temp),FP_OFF(temp),4);”正是把TIMER_LOW和TIMER_HIGH两个16位二进制数放进temp数组，再送往RAND_SE
14、ED，从而获得了“随机种子”。因此，我们可以确定的是：由此可知，随机数是由随机种子根据一定的计算方法计算出来的数值。所以，只要计算方法一定，随机种子一定，那么产生的随机数就不会变。（2）C+程序实现程序实现1 在相同的平台环境下，编译生成在相同的平台环境下，编译生成exe后，每次运行它，显示的随机数都是一样的。这是后，每次运行它，显示的随机数都是一样的。这是因为在相同的编译平台环境下，因为在相同的编译平台环境下，由随机种子生成随机数的计算方法都是一样的，再加上随由随机种子生成随机数的计算方法都是一样的，再加上随机种子一样，所以产生的随机数就是一样的。机种子一样，所以产生的随机数就是一样的。16
15、2024-3-192024-3-191616162024-3-192024-3-191616（3）C+程序实现程序实现2 本实现中，本实现中，用户和其他程序没有设定随机种子，则使用系统定时用户和其他程序没有设定随机种子，则使用系统定时/计数器的值做为随机计数器的值做为随机种子，种子，所以在相同的平台环境下，编译生成所以在相同的平台环境下，编译生成exe后，每次运行它，显示的随机数会是伪随后，每次运行它，显示的随机数会是伪随机数，即每次运行显示的结果会有不同。机数，即每次运行显示的结果会有不同。（4）生成随机串）生成随机串(C+程序程序)实现实现172024-3-192024-3-1917174
16、.1.3 伪随机数的评价伪随机数的评价标准标准如果一序列产生器是伪随机的，它应有下面的性质：（1）看起来是随机的，表明它可以通过所有随机性统计检验。现在有许多统计测试。它们采用了各种形式，但共同思路是它们全都以统计方式检查来自发生器的数据流，尝试发现数据是否是随机的。确保数据流随机性的最广为人知的测试套件就是 George Marsaglia 的 DIEHARD 软件包（请参阅http:/www.stat.fsu.edu/pub/diehard/）。另一个适合此类测试的合理软件包是 pLab（请参阅http:/random.mat.sbg.ac.at/tests/）。182024-3-1920
17、24-3-191818（2）它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。（3）它不能可靠地重复产生。如果用完全同样的输入对序列产生器操作两次将得到两个不相关的随机序列。（？）192024-3-192024-3-1919194.2 序列密码的序列密码的基本原理基本原理4.2.1 序列密码的概念序列密码的概念 序列密码算法将明文逐位转换成密文，如下图所示。序列密码算法将明文逐位转换成密文，如下图所示。202024-3-192024-3-192020在序列密码中，明文按一定长度分组后表示成一个序列，称为明文流（序列中的每
18、一项称为明文字）。加密时，先由种子密钥（或称为主密钥）通过密钥流产生器产生一个密钥流序列，该序列的每一项和明文字具有相同的比特长度，称为密钥字；然后依次把明文流和密钥流中的对应项做二元加法运算（异或运算），产生相应的密文字，由密文字构成密文流输出。解密过程是将同样的密钥流与密文流中的对应项做二元加法运算，恢复出原来的明文流。212024-3-192024-3-192121假设明文流m=m1,m2,m3,mi,；密钥流k=k1，k2，k3，,ki,序列密码的加密算法为：ci =mi ki 序列密码的解密算法为：mi =ci ki 由于mi ki ki=mi，所以解密算法是正确的。222024-3
19、-192024-3-192222例5-3：假设当前的明文字为01101010，密钥流生成器生成的当前密钥字为10110111，加解密均为按位异或加运算，则得到的密文字为：01101010 10110111=11011101解密时用相同的密钥字为：11011101 10110111=01101010实际的序列密码算法安全性依赖于密钥生成器所产生的密钥流的性质。如果密钥流是无周期的（真正随机的）无限长随机序列，那么此时的序列密码即为“一次一密”的密码体制。232024-3-192024-3-1923234.2.2 序列密码体制的序列密码体制的分类分类 在序列密码中，根据状态函数是否独立于明文或密文
20、，可以将序列密码分为同步序列密码和自同步序列密码两类。1同步序列密码 在同步序列密码中，密钥流独立于消息流产生。242024-3-192024-3-192424同步密钥流生成器模型，它具有以下特点：（1）同步：在一个同步序列中，发送方和接收方必须是同步的，即用同样的密钥且该密钥操作在同样的位置（状态），才能保证正确的解密。（2）无错误传播：在传输期间，一个密文字（或位）被改变（不是删除和插入）只能影响该密文字（或位）的恢复，不会对后续密文字（或位）产生影响。（3）主动攻击破坏同步：按照同步要求，一个主动攻击对密文进行插入、删除或重放操作都会立即破坏其同步，从而可能被解密器检测出来。作为无错误传
21、播的结果，主动攻击者可能有选择地对密文进行改动，并准确地知道这些改动对明文的影响，这时可以采用为数据源提供认证并保证数据完整性的技术。252024-3-192024-3-192525-同步密钥流生成器 举例OFB模式262024-3-192024-3-192626OFB模式的特性：272024-3-192024-3-1927272自同步序列密码 自同步序列密码也称为异步流密码，其密钥流的产生不是独立于明文流和密文流的，与种子密钥和其前面已产生若干密文字有关。282024-3-192024-3-192828-自同步序列密码 举例CFB模式292024-3-192024-3-192929自同步密钥
22、流生成器模型，它具有以下特点：（1）自同步：自同步的实现依赖于密文字被删除或插入，这是因为解密只取决于先前固定数量的密文字。自同步序列密码在同步丢失后能够自动重新建立同步，并正确地解密，只有固定数量的明文字不能解密。（2）有限的错误传播：因为自同步序列的状态取决于t个已有的密文字符，若一个密文字（或位）在传输过程中被修改（插入或删除），则解密时最多只影响到后续 t个密文字的解密，即只发生有限的错误传播。302024-3-192024-3-193030（3）难检测主动攻击：相比于同步，自同步使得主动攻击者发起的对密文字的插入、删除、重放等攻击只会产生非常有限的影响，正确的解密能很快自动重建。因此
23、，主动攻击对自同步序列密码很困难的，可能需要采用为数据源提供认证并保证数据完整性的技术。有限的错误传播特性使得主动攻击者对密文字的任何改动都会引起一些密文字解密出错。（4）密文统计扩散：每个明文字都会影响其后的整个密文，即密文的统计特性被扩散到密文中。所以，自同步序列密码体制在抵抗利用明文冗余度而发起的攻击方面要强于同步序列密码。312024-3-192024-3-193131从从CFB看自同步流密码看自同步流密码 DES是分组长为64bits的分组密码，但利用CFB模式或OFB模式可将DES转换为流密码。流密码不需要对消息填充，而且运行是实时的。因此如果传送字母流，可使用流密码对每个字母直接
24、加密并传送。流密码具有密文和明文一样长这一性质。以后回过头来看322024-3-192024-3-193232CFB模式332024-3-192024-3-193333342024-3-192024-3-193434352024-3-192024-3-1935354.2.3 序列密码与分组密码的序列密码与分组密码的比较比较分组密码和序列密码的不同主要表现在以下两方面：（1）分组密码是以一定的固定长度的分组作为每次处理的基本单元；而序列密码则是以一个元素（一个字符或一个比特位）作为基本处理单元。（2）分组密码使用的是一个不随时间变化的固定变换，具有扩散性好、插入敏感等优势，其缺点是加密处理速度慢
25、，存在错误传播；而序列密码是用的一个随时间变换的加密变换，具有传播速度快、低错误传播和硬件实现电路简单等优势，其缺点是低扩散（意味着混乱不够）、插入及修改不敏感。362024-3-192024-3-193636序列密码体制的安全性取决于密钥流的性能，当密钥流是完全的随机序列时，序列密码是不可破的；随机序列的主要特点表现为无规律性和不可预测性。如果密钥流能做到真正的随机，此时的序列密码就是“一次一密”的密码体制，是绝对安全的。在实际应用中，密钥流都是用有限存储和有限复杂逻辑的电路来产生的，此时的密钥流只有有限个状态。这样的密钥流生成器迟早要回到初始状态而使其呈现出周期性。但如果密钥流周期足够长，
26、且随机性好，其安全强度是可以得到保证的。因此，序列密码的安全强度取决于密钥流生成器的设计。目前，产生密钥流最重要的部件是线性反馈移位寄存器（LFSR，Linear Feedback Shift Register），这是因为LFSR非常适合硬件实现、能产生较大周期和统计特性良好的序列，以及能够用代数方法对产生的序列进行很好的分析。372024-3-192024-3-193737常见的密钥序列产生器常见的密钥序列产生器 目前，最为流行和实用的密钥流产生器大多基于目前，最为流行和实用的密钥流产生器大多基于线性反馈移位寄存器（线性反馈移位寄存器（Linear Feedback Shift Regist
27、er,LSFR）。）。如下图所示，其驱动部分是一个或多个如下图所示，其驱动部分是一个或多个线性反馈移线性反馈移位寄存器位寄存器。LFSRFLFSR1LFSR2LFSRnF FizFiz2024-3-1937382024-3-192024-3-1938384.3 线性反馈移位寄存器线性反馈移位寄存器-定义：定义：反馈移存器的反馈逻辑电路可用一布尔函数反馈移存器的反馈逻辑电路可用一布尔函数f(a1,a2,an)来表示，来表示，若对应的若对应的布尔函数是线性函数，则称该反馈移存器为线性反馈移存器布尔函数是线性函数，则称该反馈移存器为线性反馈移存器LFSR(linear feedback shift
28、register)，否则称为，否则称为非线性反馈移存器非线性反馈移存器。ajaj-2aj-3aj-1图图1 线性反馈移位寄存器线性反馈移位寄存器ajaj-2aj-3图图2 非线性反馈移位寄存器非线性反馈移位寄存器2024-3-1938392024-3-192024-3-193939 此时此时LFSRLFSR函数函数可写为：可写为：f(a1,a2,an)=cna1 cn-1a2 c1an 上图中，常数上图中，常数c ci i=0=0或或1 1，是模是模2 2加法。加法。c ci i=0=0或或1 1可用开关的断开和闭合来实现，这样可用开关的断开和闭合来实现，这样的线性函数共有的线性函数共有2 2
29、n n个。个。输出序列输出序列 at 满足：满足：a1+t=cnat+1 cn-1at+2 c1an+t 其中，其中，t为非负正整数。为非负正整数。如下图所示如下图所示，是一个，是一个LFSR:LFSR:（1 1）线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而）线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一，也成为构造密钥流生成器的最重要的部件之一，也非常适合用硬件实现；非常适合用硬件实现；（2 2）可以产生大周期序列；）可以产生大周期序列；（3 3）可以产生具有良好统计性质的序列；）可以产生具有良好统计性质的序列；（4
30、 4）易于利用代数方法对其进行分析。）易于利用代数方法对其进行分析。n级线性移存器的线性级线性移存器的线性递推式表示递推式表示2024-3-1939402024-3-192024-3-194040假设在假设在j j时刻其内部状态为：时刻其内部状态为：),(21rjjjaaa在在j+1j+1时刻其内部状态变为：时刻其内部状态变为：),(11rjjjaaa其中：其中：),(21rjjjjaaafa此时的输出为此时的输出为j j时刻的最高级：时刻的最高级：rjan n级反馈移位寄存器级反馈移位寄存器 每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位每一存储器称为移位寄存器的一级
31、，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，寄存器的状态，每一状态对应于每一状态对应于GF(2)GF(2)上的一个上的一个n n维向量，共有维向量，共有2 2n n种可能的状态。种可能的状态。移位寄存器是流密码产生密钥流的移位寄存器是流密码产生密钥流的一个主要组成部分。一个主要组成部分。GF(2)GF(2)上一个上一个n n级反级反馈移位寄存器由馈移位寄存器由n n个二元存储器与一个个二元存储器与一个反馈函数反馈函数f(af(a1 1,a,a2 2,a,an n)组成组成，如右图，如右图所示。所示。2024-3-1940412024-3-192024-3-194141ajaj-2aj
32、-1第第7 7时刻时刻 0 0 10 0 1第第0 0时刻时刻 0 0 10 0 1第第1 1时刻时刻 1 0 01 0 0第第2 2时刻时刻 1 1 01 1 0第第3 3时刻时刻 1 1 11 1 1第第4 4时刻时刻 0 1 10 1 1第第5 5时刻时刻 1 0 11 0 1第第6 6时刻时刻 0 1 00 1 0产生序列为：产生序列为：10011101100111012024-3-1941422024-3-192024-3-194242an-1an-2an-3an-4an)4(432naaaannnn一个一个r r级线性移存器的反馈多项式表示为：级线性移存器的反馈多项式表示为：1)(
33、111xcxcxcxfrrrrx1x2x3x41)(234xxxxf通常，用通常，用 来表示一个来表示一个LFSRLFSR。(),f x l2024-3-1942432024-3-192024-3-194343 例：下图是一个例：下图是一个3级反馈移位寄存器，其初始状态为级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由输出可由下表求出。下表求出。即输出序列为即输出序列为101110111011，周期为，周期为4。2024-3-1943442024-3-192024-3-194444在初始状态下在初始状态下,即即0 0时刻时刻在第一个时钟到来时在第一个时钟到来时101
34、f(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-1944452024-3-192024-3-194545 每一时刻的状态可用每一时刻的状态可用n长序列长序列“a1,a2,an”n维向量维向量“(a1,a2,an)”来表示，来表示，其中其中ai是第是第i级存储器的内容级存储器的内容。初始状态由用户确定，当第初始状态由用户确定，当第i个移位时钟脉冲到来时，个移位时钟脉冲到来时，每一级存储器每一级存储器ai都将其内容都将其内容向下一级向
35、下一级ai-1传递，并计算传递，并计算f(a1,a2,an)作为下一时刻的作为下一时刻的an。反馈函数反馈函数f(a1,a2,an)是是n元布尔函数，元布尔函数，即即n个变元个变元a1,a2,an 可以独立地取可以独立地取0和和1两两个可能的值个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或或1。一个一个r r级线性移存器的线性递推式表示为：级线性移存器的线性递推式表示为：)(2211rnacacacarnrnnn2024-3-1945462024-3-192024-3-194646则其输出序列和状态序列
36、如下则其输出序列和状态序列如下:状态序列状态序列:(1,0,1)(0,1,1)(1,1,1)(1,1,0)(1,0,1)(0,1,1).输出序列输出序列:1 0 1 1 1 0 .由上面的结果可以看出，这个反馈移位寄存器的状态序列和输出序列都是周期由上面的结果可以看出，这个反馈移位寄存器的状态序列和输出序列都是周期序列，其周期为序列，其周期为4 4。11f(a1,a2,a3)=a1a2 a3第1级第2级第3级S2=(1,1,1)a1=1,a2=1,a3=01输出0a02024-3-1946472024-3-192024-3-1947472024-3-1947482024-3-192024-3-
37、194848设一个设一个GF(2)上的上的4阶线性反馈移位寄存器如下图所示，其反馈函数为阶线性反馈移位寄存器如下图所示，其反馈函数为f(x1，x2，x3，x4)x1 x2，初始状态为，初始状态为S0（1，0，1，1）容易验证该线性反馈移位寄存器的输出序列为：容易验证该线性反馈移位寄存器的输出序列为：101111000100110 101111000100110 这个线性移位寄存器序列是一个周期序列，周期为这个线性移位寄存器序列是一个周期序列，周期为1515。x4x3x2x1输出序列2024-3-1948492024-3-192024-3-194949 （1）在线性反馈移位寄存器中总是假定）在线
38、性反馈移位寄存器中总是假定c1,c2,cn中至少有一个不为中至少有一个不为0，否则，否则f(a1,a2,an)0，这样的话，在这样的话，在n个脉冲后状态必然是个脉冲后状态必然是000，且这个状态必将一直持，且这个状态必将一直持续下去。续下去。（2 2）若只有一个系数不为）若只有一个系数不为0，设仅有，设仅有cj不为不为0，实际上是一种延迟装置。一般对于，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定级线性反馈移位寄存器，总是假定cn=1。（3）n级线性反馈移位寄存器的状态周期小于等于级线性反馈移位寄存器的状态周期小于等于2n-1。输出序列的周期与状态输出序列的周期与状态周期相等
39、，也小于等于周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值只要选择合适的反馈函数便可使序列的周期达到最大值2n-1。2024-3-1949502024-3-192024-3-195050https:/en.wikipedia.org/wiki/KeeLoq2015 年11 月份，由“神话”行动的一位18岁的安全研究员发现了汽车钥匙芯片Keeloq 算法的漏洞。HCS 滚码芯片和keeloq 算法是目前很多汽车和门禁遥控钥匙采取的软硬件解决方案，车主每次按下钥匙的锁车键、开车键都会触发一次新的信号发出，车辆在收到信号后快速计算，决定是否打开车门。512024-3-
40、192024-3-195151祖冲之算法集（ZUC算法）是由我国学者自主设计的加密和完整性算法，包括祖冲之算法、加密算法128-EEA3和完整性算法128-EIA3，已经被国际组织3GPP推荐为4G无线通信的第三套国际加密和完整性标准的侯选算法。https:/ 密钥序列的伪随机性密钥序列的伪随机性*-（略）（略）4.4 非线性非线性反馈移位寄存器（略）反馈移位寄存器（略）4.5 序列密码算法的破译序列密码算法的破译（略）（略）532024-3-192024-3-195353 已知已知反馈多项式反馈多项式(或线性递推式或线性递推式)及及初始状态初始状态可获得所产生的可获得所产生的序列序列。而。而
41、初始状初始状态态总是可以假定的，故知道了总是可以假定的，故知道了反馈多项式反馈多项式(或线性递推式或线性递推式)也就知道了该也就知道了该反馈多项反馈多项式式(或线性递推式或线性递推式)所产生的序列。那么反过来，已知所产生的序列。那么反过来，已知序列序列能否获得相应的能否获得相应的反馈多反馈多项式项式(或线性递推式或线性递推式)呢？呢？4.5 序列密码算法的破译序列密码算法的破译（略）（略）1.插入攻击插入攻击2.已知明文攻击已知明文攻击542024-3-192024-3-195454 可得到可得到c31，c20，c11，1 23342 34253 451 6k k kckk k kckk k
42、kck321 101001001001ccc 从而得到特征多项式：从而得到特征多项式：p(x)=x3+x+1 比如：比如：若特征多项式若特征多项式p(x)=x3+x+1，初始状态为（初始状态为（101）的移位寄存器产生序列的移位寄存器产生序列为为(101001)。设明文为（设明文为（011010），那么密文为（），那么密文为（110011）。破译者计算）。破译者计算m c得到密钥系列得到密钥系列(101001)，那么可以得到下列矩阵方程式：，那么可以得到下列矩阵方程式：已知序列已知序列a是由是由n 级线性移存器产生的，并且知道级线性移存器产生的，并且知道a的连续的连续2n位，可用解线性方程位，
43、可用解线性方程组的方法得到线性递推式（特征多项式）和组的方法得到线性递推式（特征多项式）和起始状态起始状态。2024-3-1954552024-3-192024-3-195555例：例：设敌手得到密文串设敌手得到密文串101101011110010和相应的明文串和相应的明文串011001111111001，因，因此可计算出相应的密钥流为此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥序列是。进一步假定敌手还知道密钥序列是使用使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和个比特和明
44、文串中的前明文串中的前10个比特建立如下方程：个比特建立如下方程：例题109876123459876587654765436543254321aaaaacccccaaaaaaaaaaaaaaaaaaaaaaaaa2024-3-1955562024-3-192024-3-19565600010001000100110010001010101112345ccccc000100010001001100100010101011112345ccccc2024-3-1956572024-3-192024-3-19575700010011011101010000010011001012345ccccc010
45、0112345ccccc 从而得到特征多项式：从而得到特征多项式：p(x)=x4+x+12024-3-1957582024-3-192024-3-195858 基于基于LFSR的序列密码非常适合于硬件实现，但是不特别适合软件实现。的序列密码非常适合于硬件实现，但是不特别适合软件实现。这这导致出现了一些关于序列密码被计划用于快速软件实现的新建议，因为这些建议导致出现了一些关于序列密码被计划用于快速软件实现的新建议，因为这些建议大部分具有专利，因此这里不讨论它们的技术细节。大部分具有专利，因此这里不讨论它们的技术细节。比较常用的序列密码是比较常用的序列密码是A5、SEAL和和RC4序列密码算法，序
46、列密码算法，A5是典型的基于是典型的基于LFSR的序列密码算法，的序列密码算法，SEAL和和RC4不是基于不是基于LFSR的序列密码算法，而是基于的序列密码算法，而是基于分组密码的输出反馈模式（分组密码的输出反馈模式（OFB）和密码反馈模式（和密码反馈模式（CFB）来实现的来实现的。其他不基其他不基于于LFSR的序列密码生成器的安全性基于数论问题的难解性，这些生成器比基于的序列密码生成器的安全性基于数论问题的难解性，这些生成器比基于LFSR的生成器要慢很多。的生成器要慢很多。592024-3-192024-3-195959SRC4 RC4是美国RSA数据安全公司1987年设计的一种一个可变密钥
47、长度（40至2048比特可变）、面向字节（256个bytes）操作的序列密码。RSA数据安全公司将其收集在加密工具软件BSAFE中。最初并没有公布RC4的算法。人们通过软件进行逆向分析得到了算法；在这种情况下，RSA数据安全公司于1997年公布了RC4密码算法；基本思想：对于n位长的字（RC4是8位长的字），它总共N=2n（RC4是28个）个可能的内部置换状态矢量S表，这些状态是保密的，密钥流K由S中N个元素按照一定方式选出一个元素而生成。密钥流的生成有两个过程：密钥调度算法（KSA）和伪随机数生成算法（PRGA）。KSA主要用于设置数据表S的初始排列(初始化数据表S)；PRGA用于选取随机元
48、素元素并修改S表中的排列顺序。602024-3-192024-3-196060RC4使用了256个字节的S表和两个指针（I和J)，算法步骤为：Step1：初始化：初始化S表表初始化过程如下：（1）对S表进行填充，即令S0=0,S1=1,S2=2,S255=255（2）用密钥k(k0,k1,klen(k)-1)填充另一个256字节的R表。若密钥的长度小于R表的长度，则依次重复填充，直至将R表填满Ri=ki mod len(k)（3）J=0;（4）对于I=0:255，重复以下操作：J=(J+SI+RI)mod 256;交换SI和SJi=0,j=0;while(i=255）i=i+1(mod 256
49、)j=j+S(i)(mod 256)swap(S(i),S(j)t=S(i)+S(j)(mod 256)output k=S(t)612024-3-192024-3-196161Step2：生成密钥序列：生成密钥序列 RC4的下一状态函数定义如下：（1）I=0,J=0;根据明文长度循环执行根据明文长度循环执行（2）I=(I+1)mod 256（3）J=(J+SI)mod 256（4）交换 SI和SJ RC4的输出函数定义如下：（1）h=(SI+SJ)mod 256（2）z=Sh i=0；j=0；while(true）i=（i+1）mod N；j=（j+Si)mod N;swap(Si,Sj);
50、h=(Si+Sj)mod N;output z=Sh;622024-3-192024-3-196262622024-3-192024-3-196262实例2024-3-1962632024-3-192024-3-196363632024-3-192024-3-1963632024-3-1963642024-3-192024-3-196464642024-3-192024-3-1964642024-3-1964652024-3-192024-3-196565652024-3-192024-3-196565RC4算法的优点是：算法简单、高效，特别适合软件实现，RC4是目前应用最广的商密级序列密码（
