k 安全信道 k
…
…
滚动密钥生成器
滚动密钥生成器
x i
z i
y i
z i
x i
e z i (x i )
图3.20 同步流密码体制模型
e z i (y i )
流密码的结构
• 典型的流密码每次加密一个字节的明文； • 密钥输入到一个伪随机数发生器，产生一串随机 的8比特数； • 发生器的输出称为密钥流； • 11001100 明文 • ⊕01101100 密钥流 • 10100000 密文 • 解密使用相同的伪随机序列： • 10100000 密文 • ⊕01101100 密钥流 • 11001100 明文
S 5 0 1 1 2 2 3 3 4 4 0 5 6 6 7 7
j:=(j+s(i)+k(i)) mod 8;
RC4算法
索引i加1后，j的下一个值为： j=(5+S(1)+K(1)) mod 8=(5+1+6) mod 8=4 即将S数据表的S(1)和S(4)互换：
S 5 0 4 1 2 2 3 3 1 4 0 5 6 6 7 7
第 十 一 讲
流密码技术的发展及分类
• 序列密码是世界各国的军事和外交等领域中使用的主要密码体制之 一 • 2000年Profile 1月欧洲启动的 NESSIE工程中，流密码算法的设计与分析 1 (SW) Profile 2 (HW) 也列上了公开征集评测的日程；6个流密码算法（Leviathan、UIi一 128、BMGL、SOBER—t32、SOBER—tl、SNOW）进入了第二阶 CryptMT (CryptMT Version 3) DECIM (DECIM v2 and DECIM-128) 段评估，但是因为他们都不符合 NESSIE 的征集准则而最终全部落 选 Dragon Edon80 • 2003年3月，日本政府的密码研究与评估委员会（ CRYPTREC）推 荐了三个流密码算法：MUGI、MULTI-S01和RC4-128. HC (HC-128 and HC-256) F-FCSR (F-FCSR-H v2 and F-FCSR-16) • ECRYPT是欧洲FP6下的IST 基金支持的一个为期四年的项目，该项 目启动于2004年2月，STVL （Symmetric techniques virtual lab LEX (LEX-128, LEX-192 and LEX-256) Grain (Grain v1 ）正在进行流密码算法的公开征集评估活动 . and Grain-128) 征集活动到 2005 年4月29 日结束，征集到了 34 个流密码算法 . 2.0) NLS (NLSv2, encryption-only) MICKEY (MICKEY 2.0 and MICKEY-128 2007年4月开始进入第三轮评估，16个算法进入第三轮评估. Rabbit Moustique /stream/phase3list.html Salsa20 Pomaranch (Pomaranch Version 3) 2008年4月8个算法成为推荐算法 . 2008年8月更新为7个推荐算法. Trivium SOSEMANUK
流密码的优缺点
• 和分组密码相比，速度更快，而且需要编写的代 码少； • 对不同的明文需要使用不同的流密钥，否则容易 破解； • 适用于需要对数据流进行加密解密的应用，如通 过一个数据通信信道或网页浏览连接； • 不适用于处理成块的数据：文件传输、电子邮件 和数据库。
流密码与分组密码区别：
流密码几乎总是比分组密码快，通常使用的代 码也比分组密码少得多。如最常用的流密码 RC4，大概比最快的分组密码至少快两倍 。 RC4可以用30行代码写成 ， 而大多数分组密码需要数百行代码。
i=0 j=0 重复下述步骤，直至获得足够长度的密钥流： i=i+1 mod 256 j=j+S[i] mod 256 互换s[i]与s[j] t=S[i]+S[j] mod 256 K=S[t]
RC4算法
假如使用3位（从0到7）的RC4，其操作是对8取模（而 不是对256取模）。数据表S只有8个元素，初始化为：
流密码和RC4
• 流密码的结构 • RC4算法
RC4
• RC4是Ron Rivest为RSA公司在1987年设计的一 种流密码； • 是一个可变密钥长度，面向字节操作的流密码； • 算法以随机置换作为基础，密码的周期大于10100 。 • 每输出一个字节的结果仅需要8条到16条机器操作 指令。 • 可能是应用最广泛的流密码，被应用于SSL/TLS 标准。
第 十 一 讲
种子密钥
密钥流生成器
k1 k2
m2 m1
密文
c2 c1
解密过程
流密码的思想起源
• 设明文为m=m1m2…
mi∈GF(2), i>0 ki∈GF(2), i>0 ci∈GF(2), i>0 i>0 i>0
第 十 一 讲
• 设密钥为k=k1k2… • 设密文为c=c1c2…
• 则加密变换为ci＝ mi + ki (mod 2) • 则解密变换为mi＝ ci+ ki (mod 2)
流密码的思想起源
第 十 一 讲
• 思想起源：20世纪20年代的Vernam体制， 即 “一次一密”密码体制。香农利用信息论证明 随机序列计算机无法实现 “一次一密”密码体制在理论上不可破译 • 由有限的种子密钥生成无限长的随机密钥序列 • 流密码研究内容——设计安全高效的伪随机序列 发生器 评测标准：线性复杂
j=0 对i=0,…,255做 j=j+S[i]+K[i] mod 256 互换s[i]与s[j]
伪随机生成算法（PRGA, Pseudo Random Generation Algorithm）
• 从内部状态中选取一个随机元素作为密钥流中的一个字节， 并修改内部状态以便下一次选择。 • 选取过程取决于索引值i和j，它们的初始值均为0。
应用密码学
计算机科学与技术学院 温蜜
第11讲流密码相关内容
主要内容
第 十 一 讲
• • • • 流密码（序列密码）的思想起源 流密码技术的发展及分类 基于移位寄存器的流密码算法 RC4流密码算法
流密码的思想起源
第 十 三 讲
种子密钥
密钥流生成器
k1 k2
c1 c2
明文
m2 m1
加密过程
流密码的思想起源
S 0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
选取一个密钥，该密钥是由0到7的数以任意顺序组成的。例 如选取5、6和7作为密钥。该密钥如下填入密钥数据表中：
K 5 0
6 1
7 2
5 3
6 4
7 5
5 6
6 7
RC4算法
密钥调度算法KSA
然后利用如下循环构建实际的S数据表： j:=0; for i=0 to 7 do swap(S(i),S(j)); 该循环以j=0和i=0开始。使用更新公式后j为： j=(0+S(0)+K(0)) mod 8=5 S数据表的第一个操作是将S(0)与S(5)互换。
流密码技术的发展及分类
k k
密钥流 生成器 z i E(z ,m ) i i c i 信道 c i
密钥流 生成器 z E(z ,m ) i i
i
m i
• 自同步流密码的优点是即使接收端和发送端不同步，只要 接收端能连续地正确地接受到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的游程个数相等. 例：0110111101中，4个游程长度为1，1个游程长度为2 ，1个游程长度为4
基于移位寄存器的流密码算法
• 初态为100放入寄存器，输出序列情况如下
状态 100 110 111 011 101 010 001 100 输出位 0 0 1 1 1 0 1 0
b3 b2 b1
00111010011101…
f(b1,b2,b3)=b1⊕b3
输出序列的周期为7
目前大多数研究成果都是关于同步流密码的。
RC4算法
• 主要包括两个步骤：
– 密钥调度算法（KSA,Key-Scheduling Algorithm） – 伪随机生成算法（PRGA, Pseudo Random Generation Algorithm）
密钥调度算法（KSA,Key-Scheduling Algorithm）
• 设置内部状态（s[0]，…，s[255]）的随机排列。 • 开始时，内部状态中的元素被初始化为0~255，既 s[i]=i(i=0，…，255)； • 密钥长度可变，设为L个字节（K[0]，…，K[L-1]）； • L一般为5~32之间，用L个字节不断重复填充，直至得到 K[0]，…，K[255]，用于对内部状态S进行随机化。
基于移位寄存器的流密码算法
• 反馈移位寄存器(feedback shift register,FSR)是由n 位的寄存器和反馈函数(feedback function)组成，如 下图所示，n位的寄存器中的初始值称为移位寄存器的 初态. • 工作原理：. 反馈函数f是n个变元(b1,b2,…,bn)的布尔 函数. 移位寄存器根据需要不断地进动m拍，便有m位的 输出，形成输出序列a1,a2,…,am .