流密码量子密码学讲课

4.2 流密码的原理
1 流密码的基本概念 流密码是将明文划分成字符(如单个字母)，或其编 码的基本单元(如0, 1数字)，字符分别与密钥流作用进 行加密，解密时以同步产生的同样的密钥流实现，其 基本框图如图3-1-1所示。图中，KG为密钥流生成器 密钥流生成器， 密钥流生成器 kI为初始密钥 初始密钥。流密码强度完全依赖于密钥流产生器所 初始密钥 生 成 序 列 的 随 机 性 (Randomness) 和 不 可 预 测 性 (Unpredictability)。其核心问题是密钥流生成器的设计 核心问题是密钥流生成器的设计 。保持收发两端密钥流的精确同步是实现可靠解密的 关键技术。
2. 流密码相对于分组密码有以下优点： 流密码相对于分组密码有以下优点： 在硬件实施上，流密码的速度一般要比 分组密码快，而且不需要有很复杂的硬 件电路； 流密码能较好地隐藏明文的统计特征；
在某些情况下(例如某些电信上的应用)，当缓冲 不足或必须对收到的字符进行逐一处理时，流密 码就显得更加必要和恰当； 流密码的差错传播有限或没有差错传播，使得在 一些容易发生传输误差的环境中使用流密码就更 具优势； 流密码有较理想的数学分析工具，如频谱理论和 技术、代数等； 目前大多数国家的军事和一般外交保密通信似乎 仍主要使用流密码。
A3(1)
(2) A2 A3(2) A1(2)
A1(2) (2) A2 A3(2)
A1(1)
s2 s3 s1
A3(2) A1(2) (2) A2
(1) A2
s1 s2 s3
A3(1) s3 s1 s2
有限状态自动机可用有向图表示，称为转移图。转 移图的顶点对应于自动机的状态，若状态 si 在输入 Ai(1) 时转为状态 s j ，且输出一个字符 A(2)，则在转移图中，从 j 状态 si 到状态 s j 有一条标有的弧线 ( Ai(1) , A (j 2 ) ) ，见下图。

2.1 流密码一般模型
自同步流密码(SSSC)
密钥流生成器是一种有记忆变换器 密钥流与明文符号有关：
i 时刻的密文不仅取决于i 时刻的明文，而且与i 时刻 之前的l个明文符号有关 具有有限的差错传播 具有自同步能力 把明文每个字符扩散在密文多个字符中,强化了抗统 计分析的能力
问：SSSC是如何自同步的？请email回应。
i F ( i1, k ), zi f ( i, k ), ci E (zi,m i). i:密 钥 流 生 成 器 的 内 部 状 态 0 :密 钥 流 生 成 器 的 初 始 状 态 k : 种 子 (初 始 )密 钥 F :状 态 转 移 函 数 f :密 钥 流 生 成 函 数
k
密钥流生成器
11
病原体侵入机体，消弱机体防御机能 ，破坏 机体内 环境的 相对稳 定性， 且在一 定部位 生长繁 殖，引 起不同 程度的 病理生 理过程
2.1 流密码一般模型
二元加法序列密码
明文序列: m= m1 m2 m3 …; 密钥序列: z= z1 z2 z3 …; 密文序列: c= c1 c2 c3 …; 加密变换: ci=zimi (i=1,2,3,…); 解密变换: mi=zici (i=1,2,3,…).
病原体侵入机体，消弱机体防御机能 ，破坏 机体内 环境的 相对稳 定性， 且在一 定部位 生长繁 殖，引 起不同 程度的 病理生 理过程
2.2 线性反馈移位寄存器序列
伪随机序列 考虑二元序列: a={ai}=a0a1a2a3 ….
周期序列
定义2.1 设a= (a0, a1,…,ai,…)是一个二元序列，若 存在正整数N和非负整数m，使得ai+N=ai对于任意i m成立，则称二元序列a是终归周期序列。如果 m=0，则称序列a是严格周期序列，简称周期序列。

33
测量装置无关量子密钥分配
Bell states measurement（BSM）
H.-K. Lo, M. Curty, and B. Qi, Phys. Rev. Lett. 108, 130503 (2012).
34
参考系与测量设备双无关量子密钥分配实验
王超等，Phys. Rev. Lett. 115, 160502 (2015)
16位 1011011001101111; …….
任何一个n位存储器，某时刻可存储2n个数据之一
7
4、量子态与量子比特 Qbit（量子态）----- 0 , 1
（1）光子的偏振
（2）电子的自旋
（3）原子的能级
0
1
……
QByte： 0 1 1 0 1 1 0 0
任何一个n位存储器，某时刻可存储2n个数据！ 8
需要不时地校准对 齐双方的参考系
31
参考系无关量子密钥分配的实验
AT T
实
验
VO VO
A
A
系
统
VO VO
A
A
Short arm
Long arm
梁文烨等，Scientific Reports Vol. 4, 3617(2014)
32
热点2、测量仪器无关量子密钥分配
ALICE x
BOB y
?
?
?
a
b
(4)Bob和Charlie根据公布的L的值来选择基矢进行测量
G.-P. Guo and G.-C. Guo, Physics Letters A 310, 247 (2003).
40
经典消息的秘密共享
2009年，Sarvepalli等人基于CSS码理论提出 QSS方案，并实现接入网功能。

m-C2：只要知道n次本原多项式，m序列极易生成。 m-C3：m序列极不安全，只要泄露2n位连续数字，
就可完全确定出反馈多项式系数。
2021/4/28
4
m序列的破译
已知ki, ki+1,…, ki+2n，由递推关系式可得出下式
ki
ki 1
.
.
. ki n 1
ki 1 ki2
. . . kin
2021/4/28
13
非线性前馈序列
LFSR虽然不能直接作为密钥流用，但可作为驱动源以 其输出推动一个非线性组合函数所决定的电路来产生非 线性序列。这就是所谓非线性前馈序列生成器。
LFSR用来保证密钥流的周期长度、平衡性等 非线性组合函数用来保证密钥流的各种密码性质，以抗
击各种可能的攻击。
2021/4/28
2021/4/28
2
m序列的性质
定理3-5 以f(x)为特征多项式的LFSR的输出序列是m序列的 充要条件为f(x)是本原的。
系 n级LFSR生成的不等价m序列共有(2n－1)/n个。
定理 3-6 m序列满足Golomb的三条伪随机假设。
2021/4/28
3
m序列的性质
m序列否满足密码要求？
m-C1：n级m序列的周期为2n－1，n大，周期指数地 加大，例如n=166时，p=1050(9.353610465 ×1049)。
2021/4/28
12
非线性序列
线性复杂度： 能产生周期序列 {ki}i 0的LFSR的最小级数n。 显然，n级m序列的线性复杂度为n。
线性复杂度是研究和设计密码的重要指标和工具。 一个伪随机序列若其线性复杂度低，就易于由部分序列
综合出生成它的LFSR。一般移存器序列的线性复杂度