现代密码学第五讲(一)：流密码

10001100„
输出序列的周期为5
基于移位寄存器的流密码算法

n级LFSR输出的序列的最大周期是2n 1
为什么？


LFSR的寄存器状态遍历2n 1个非零状态 初始状态为全零，则输出序列为0的循环
定义 当LFSR的寄存器状态遍历2n 1个非零状 态时，序列的周期达到最大2n 1，这种序 列被称为m序列。
《现代密码学》第五讲
流密码（一）
1
上讲内容回顾

分组密码定义（分组 填充） 分组密码的发展历史（Shannon DES AES。。。） 保密系统的安全性分析及分组密码的攻击 数据加密标准（DES）算法介绍 高级加密标准（AES）算法介绍 中国无限局域网标准（SMS4）算法介绍 分组密码算法的运行模式
i>0 i>0
则加密变换为ci＝ mi + ki (mod 2) 则解密变换为mi＝ ci+ ki (mod 2)
流密码的思想起源



思想起源：20世纪20年代的Vernam体制， 即“一次一密”密码体制。香农利用信息论 随机序列计算机无法 实现 证明“一次一密”密码体制在理论上不可破 译 由有限的种子密钥生成无限长的随机密钥序 列 流密码研究内容——设计安全高效的伪随机 评测标准：线性复杂 序列发生器 度高；周期大

流密码技术的发展及分类
k 密钥流 生成器 zi E(zi,mi) mi

k 密钥流 生成器 zi E(zi,mi) mi
ci
信道
ci
自同步流密码的优点是即使接收端和发送端不同 步，只要接收端能连续地正确地接受到n个密文符 号，就能重新建立同步。因此自同步流密码具有 有限的差错传播 ，且分析较同步流密码的分析困 难得多
rn rn-1 … r2 r1
bn bn-1 … b2 b1
输出位o i
反馈函数f
基于移位寄存器的流密码算法


线性反馈移位寄存器LFSR(linear feedback shift register）的反馈函数为线性函数 作为密钥流的序列{ai}的周期一定要大 否则密钥流的空间太小，利用穷举搜索可 以得到密钥流{ai} n级LFSR输出的序列的周期r不依赖于寄存器 的初始值，而依赖于特征多项式p(x)
流密码技术的发展及分类
思考：假设j=n/4,n为分组长度 对于DES，n=64, j=16；对AES，n=128,j=32
CFB模式为（ OFB模式为（ CTR模式为（
）流密码？ ）流密码？ ）流密码？
自同步、同步、同步
基于移位寄存器的流密码算法
rn bn

rn-1 … bn-1 …
r2 b2
r1 b1

挪威政府的首席密码学家Ernst Selmer 于1965年提出了移 位寄存器理论，它是序列密码中研究随机密钥流的主要数 学工具. 移位寄存器是指有n个寄存器（称为n-级移位寄存器） r1,r2,…,rn从右到左排列，每个寄存器中能存放1位二进制数 ，所有寄存器中的数可以统一向右（或向左）移动1位， 称为进动1拍. 即r1的值(b1)右移1位后输出，然后r2的值 (b2)送r1 , r3的值(b3)送r2,……最后， rn的值(bn)送rn-1.
从而可确定该线性反馈移位寄存器接下来的 状态，也就能够得到余下的密钥序列。
基于移位寄存器的流密码算法
例： 5级线性反馈移位寄存器产生的密钥序列 加密得到的明文串为011001111111001， 对应的密文串为101101011110011。求该 LFSR的反馈函数。 解：由明密文得相应的密钥序列为 110100100001010； 利用前10个密钥序列比特建立如下方程：
基于移位寄存器的流密码算法
定义 若n次不可约多项式f(x)的阶为2n-1，则 称f(x)为n次本原多项式。
定理 {ai}是周期为2n 1的m-序列的充要条件 是其特征多项式f(x)为n阶本原多项式
基于移位寄存器的流密码算法

一个3-级的反馈移位寄存器，反馈函数 f(x)= b3⊕b1 ，初态为100，输出序列？

流密码技术的发展及分类
k 密钥流 生成器 k 密钥流 生成器 zi ci 信道 ci
zi
E(zi,mi)
E(zi,mi)
mi

mi
在同步流密码中，密（明）文符号是独立的，一个错误传 输只会影响一个符号，不影响后面的符号。 缺点：一旦接收端和发送端的种子密钥和内部状态不同步 ，解密就会失败，两者必须立即借助外界手段重新建立同 步。
c2 c1
明文
m1 m2
加密过程
流密码的思想起源
种子密钥 密钥流生成器 k2 k1
m2 m1
密文
c1 c2
解密过程
流密码的思想起源

设明文为m=m1m2… 设密钥为k=k1k2…
mi∈GF(2), i>0 ki∈GF(2), i>0
设密文为c=c1c2…
ci∈GF(2), i>0
例：0110111101中，4个游程长度为1，1个游程长度为2，1个 游程长度为4
流密码的思想起源
异相自相关函数是一个常数. 设一个周期为r的序列 a1, a2,…, ar, ar+1, ar+2,… ， 将序列平移T位得到另外一个序列 aT, aT+1,… ar+T, ar+T+1,…， 若ai= ai+T, 则称对应第i位相等。 设两个序列相同位的个数为n，不同位的个数为d， 则R(T)=(n-d)/r为自相关函数

基于移位寄存器的流密码算法
定义 设n级LFSR的输出序列{ai}满足递推关系
an k cn an k 1 cn1an k 2 c1ak (k 1).
这种递推关系可用一个一元高次多项式
f ( x) cn x cn1x
n
n1
c1x 1
表示，称这个多项式为LFSR的特征多项式。
状态 100 110 111 011 101 010 001 100 输出位 0 0 1 1 1 0 1 0 f(b1,b2,b3)=b1⊕b3
b3 b2 b1
00111010011101…
输出序列的周期为7
基于移位寄存器的流密码算法
流密码的攻击 攻击目的：确定整个密钥流{ki} 攻击手段： 惟密文 已知明文 选择明/密文 自适应选择明/密文
基于移位寄存器的流密码算法
定义 设 f ( x)是 GF (2)上的多项式，使 f ( x)|( xn 1) 的最小的n称为 f ( x) 的周期或者阶。
f ( x) x4 x3 x2 x 1 为 GF (2) 上多项式， 例： 以它为特征多项式的LFSR 的输出序列周期。 ( x5 1) ( x4 x3 x2 x 1)( x 1) f ( x)( x 1)
基于移位寄存器的流密码算法
kn 1 k1bn k2bn 1 knb1 k k b k b k b n2 2 n 3 n 1 n 1 1 k2 n knbn kn 1bn1 k2 n1b1
n个线性方程包含n个未知数：b1,b2,...,bn，所 以可惟一解出bi (i=0，1，…，n)
密钥流生成、存储和分 发困难
流密码的思想起源
Golomb伪随机性测试 周期为r的0－1序列的随机性公设如下： r是奇数，则0－1序列{si}的一个周期内0的个数 比1的个数多一个或少一个；若r是偶数，则0的个 数与1的个数相等. 在长度为r的周期内，长为1的游程的个数为游程 总数的1/2，长为2的游程的个数占游程总数的 1/22,„, 长为c的游程的个数占总游程的1/2c.而 且对于任意长度，0的游程个数和1的游程个数相 等.
（主动/被动 唯密文/已知明（密）文/选择明（密）文/自适应选择明（ 密）文）
来自百度文库
本章主要内容



流密码（序列密码）的思想起源 流密码技术的发展及分类 基于移位寄存器的流密码算法 其它流密码算法 Estream推荐流密码算法

软件算法 硬件算法
3
流密码的思想起源
种子密钥 密钥流生成器 k2 k1

流密码技术的发展及分类
Profile 1 (SW) Profile 2 (HW) 序列密码是世界各国的军事和外交等领域中使用的主要密码体制之 一 CryptMT (CryptMT Version 3) DECIM (DECIM v2 and DECIM-128) 2000年1月欧洲启动的NESSIE工程中，流密码算法的设计与分析也 列上了公开征集评测的日程；6个流密码算法（Leviathan、UIi一128 、BMGL、SOBER—t32、SOBER—tl、SNOW）进入了第二阶段评估 Dragon Edon80 ，但是因为他们都不符合NESSIE的征集准则而最终全部落选 HC 2003年3月，日本政府的密码研究与评估委员会（CRYPTREC）推荐 (HC-128 and HC-256) F-FCSR (F-FCSR-H v2 and F-FCSR-16) 了三个流密码算法：MUGI、MULTI-S01和RC4-128. LEX (LEX-128, LEX-192 and LEX-256) Grain (Grain v1 and Grain-128) ECRYPT是欧洲FP6下的IST 基金支持的一个为期四年的项目，该项 目启动于2004年2月，STVL （Symmetric techniques virtual lab）正 NLS (NLSv2, encryption-only) MICKEY 在进行流密码算法的公开征集评估活动.(MICKEY 2.0 and MICKEY-128 2.0) 征集活动到2005 年4月29 日结束，征集到了34个流密码算法. Rabbit Moustique 2007年4月开始进入第三轮评估，16个算法进入第三轮评估. Salsa20 Pomaranch (Pomaranch Version 3) http://www.ecrypt.eu.org/stream/phase3list.html SOSEMANUK Trivium 2008年4月8个算法成为推荐算法. 2008年8月更新为7个推荐算法.

基于移位寄存器的流密码算法
1 若LFSR的反馈函数已知，破译者已知连续n位明密 文对 {m1 , m2 ,, mn } 和 {c1 , c2 ,, cn } 则可以推导出 n比特密钥流 {k1 , k2 ,, kn }，i mi ci 继而由反馈 k 函数得到整个密钥流{ki} 2 已知明文攻击下，假设破译者已知了2n位明密文 对 M {m1 , m2 ,, m2n } C {c1, c2 ,, c2n} ，则可确定 ， 一段2n位长的密钥序列 K {k1, k2 ,, k2n} ，由此可 以完全确定n级反馈多项式的系数。
基于移位寄存器的流密码算法


反馈移位寄存器(feedback shift register,FSR)是由n位的寄 存器和反馈函数(feedback function)组成，如下图所示，n 位的寄存器中的初始值称为移位寄存器的初态. 工作原理：移位寄存器中所有位的值右移1位，最右边的 一个寄存器移出的值是输出位，最左边一个寄存器的值由 反馈函数的输出值填充，此过程称为进动1拍. 反馈函数f是 n个变元(b1,b2,…,bn)的布尔函数. 移位寄存器根据需要不断 地进动m拍，便有m位的输出，形成输出序列a1,a2,…,am .
f ( x) | x 1,
n
n5
所以f(x)的周期为5
基于移位寄存器的流密码算法
解：对应的n级LFSR的反馈函数为
状态 0001 1000 1100 0110 0011 0001 1000 1100 输出位 1 0 0 0 1 1 0 0 f(b1 ,b2 ,b3 ,b4)
b4 b3 b2 b1
f ( x) x3 x 1
生成多项式为
( x7 1) ( x4 x2 x 1)( x3 x 1) ( x4 x2 x 1)f ( x)
f ( x) | x 1,
n
n7
所以f(x)的周期为7
基于移位寄存器的流密码算法

初态为100放入寄存器，输出序列情况如下