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

ci = pi ⊕ zi pi = ci ⊕ zi
ci和pi分别表示第i比特的密文和明文。
MICKEYMICKEY-128
宣称的安全性
MICKEY-128 2.0 is intended to resist any attack faster than exhaustive key search. The designers have not deliberately inserted any hidden weaknesses in the algorithm.
GrainGrain-128
Grain-128使用了一个线性反馈移位寄存器 (LFSR)来确保很好的统计特性和密钥流周期 的下限值。为了引入非线性特性，它使用了 一个非线性反馈移位寄存器(NFSR)和非线性 滤波器(输出函数)。
GrainGrain-128 LFSR的寄存器内容记为si,si+1,……，si+127 LFSR的反馈多项式表示为f(x),是度数为128 的本原多项式。它定义为:
初始化过程
密钥的比特位定义为ki，0≤i≤127，输入自变 量的比特位定义为IVi，0≤i≤95。 NFSR的寄存器初始化：bi=ki，0≤i≤127； LFSR的寄存器初始化：前96个元素使用IV 比特位载入，si=IVi，0≤i≤95，后面的32比 特由1来填充，si=1，96≤i≤127。 在载入密钥和IV后，钟控256次不输出密钥流 ，密钥初始化过程如下：
bi+128 = si + bi + bi+26 + bi+56 + bi+91 + bi+96 + bi+3bi+67 + bi+11bi+13 + bi+17bi+18 + bi+27bi+59 + bi+40bi+48 + bi+61bi+65 + bi+68bi+84
GrainGrain-128
j∈A
A = {2, 15, 36, 45, 64, 73, 89}.
Grain
加解密方法 加密/解密是将输出比特流与明文/密文进行 异或运算：
ci = pi ⊕ zi pi = ci ⊕ zi
ci和pi分别表示第i比特的密文和明文。
GrainGrain-128
A．线性逼近 对于每个方程a(x)都可以找到一个有偏差的线性逼近方程Aa(x),这意味 着Grain总会产生有偏差的密钥流样本，重要的是选择函数g(x)和 h(x)以确保偏差足够小，没有比穷举攻击更好的攻击手段。 B.代数攻击： 在Grain-128中，NFSR使用h(.)函数引入了非线性特性，使用初始状态 比特流表示输出的函数度一般比较大，而且随时变化，因此它能抵 抗任何代数攻击。 C.时间-存储-数据 权衡攻击： 一般的对于流密码的时间-存储-数据攻击复杂度为O（2n/2）,n指的是 流密码状态的个数。在Grain-128中，两个128位的移位寄存器加起 来状态变量为256，因此时间-存储-数据权衡攻击的复杂度不低于O （2128） D.错误攻击: 对于流密码来说，错误攻击是威胁较大的攻击之一，它们被引入攻击 了很多著名的流密码体制，但是在NFSR中引入缺陷要比在LFSR中 困难。
NFSR 的寄存器内容记为bi,bi+1,…,bi+127 NFSR的非线性反馈多项式g（x）是一个 线性函数和一个非线性函数的和： 32 37 72 102 128 44 60 61 125 g(x) =1+x +x +x +x +x +x x +x x
+x63x67 +x69x101+x80x88 +x110x111+x115x117 为消除歧义，NFSR的修正函数定义为：
CLOCK_R（R, INPUT_BIT_R, CONTROL_BIT_R）: 标记r0,r1,…,r159是钟控前寄存器R的状态，r’0 ,r’1 ,…, r’159 是钟控后寄存器R的状态
FEEDBACK_BIT = r159 ⊕ INPUT_BIT_R 对于1 ≤ i ≤ 159, ri′ = ri -1 ; r0′ = 0 对于0 ≤ i ≤ 159, 若 i ∈ RTAPS , ri′ = ri′⊕ FEEDBACK_BIT 如果CONTROL _ BIT _ R =1 ri′ = ri ⊕ ri′ , 0 ≤ i ≤ 159. :
3. 前钟控 对0≤i≤159:
CLOCK_KG( R, S , MIXING = TRUE , INPUT _ BIT = 0)
MICKEYMICKEY-128 生成密钥流
0≤i≤L-1:
密钥流生成
z i = r0 ⊕ s 0
CLOCK_KG( R, S , MIXING = FALSE , INPUT _ BIT = 0)
zi =
∑
j∈ A
b i + j + h(x) + s i + 93 ,
A = { 2 , 15 , 36 , 45 , 64 , 73 , 89 }.
GrainGrain-128
密钥流生成
加密流程
GrainGrain-128
输出比特zi 为：
zi = ∑ bi + j + h(x) + si +93 ,
GrainGrain-128 算法 MICKEYMICKEY-128 Trivium
3
软件算法
Grain-128
GrainGrain-128
Grain-128的设计者：Martin Hell (Sweden), Thomas Johansson (Sweden) 和 Willi Meier (Switzerland)
GrainGrain-128
g(x) NFSR LFSR f(x)
h(x)
密钥初始化
GrainGrain-128
布尔函数h(x) 定义如下： h( x) = x0 x1 + x2 x3 + x4 x5 + x6 x7 + x0 x4 x8 其中 x0 , x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 分别对应于两个 寄存器b和s 的抽头： bi +12 , si +8 , si +13 , si + 20 , bi +95 , si + 42 , si + 60 , si + 79 , s i +95 反馈比特zi定义为：
软件算法
Trivium
Trivium
Trivium由Belgium密码学家C. De Cannière 和 B. Preneel设计 Trivium从一个80-bit的密钥和一个80-bit的 起始变量中生成多达264比特的密钥流.
Trivium
初始化过程
密钥长度: 80比特, 记为K1 , . . . , K80 IV 大小: 80比特，记为IV1 , . . . , IV80 中间状态大小: 288比特，记为s1,. . . , s93， s94 , . . . , s177， s178 ,. . . , s288。
MICKEYMICKEY-128 寄存器S钟控 寄存器 钟控
四个序列 COMP P 0158 , P1158 ,
FB 0 0...FB 0159 , FB10...FB1159
r
r159⊕
MICKEYMICKEY-128
加解密方法 加密/解密是将输出比特流与明文/密文进行 异或运算：
1. 将80-bit 的密钥和 的密钥和80-bit 的起始变量分别 赋值给内部状态比特s1～s80和s94 ～s173。 赋值给内部状态比特 同时将s 置为1， 同时将 286 , s287和 s288置为 ，剩余所有位 置零。 置零。
MICKEYMICKEY-128
CLOCK_S（S, INPUT_BIT_S, CONTROL_BIT_S）： 标记s0,s1,…,s159是钟控前寄存器R的状态，s’0, s’1, …, s’159是钟控后寄存器R的状态. 采用ŝ0, ŝ1,…, ŝ159 作为中间变量。
寄存器S钟控 寄存器 钟控
FEEDBACK _ BIT = s159 ⊕ INPUT _ BIT _ S ) si = si-1 ⊕ (( si ⊕ COMP0i ) ⋅ ( si+1 ⊕ COMP1i )), 1 ≤ i ≤ 158; ) ) s0 = 0; s159 = s158 .
如果CONTROL _ BIT _ S = 0: ) ′ = si ⊕ (FB0i ⋅ FEEDBAC_BIT ), 0 ≤ i ≤ 159 ; si 如果CONTROL _ BIT _ S = 1： ) ′ = si ⊕ (FB1i ⋅ FEEDBACK_BIT )， ≤ i ≤ 159. si 0
MICKEYMICKEY-128
初始化过程
寄存器R和S初始为全0， 1. 载入IV. 对0≤i≤IVENGTH-1:
CLOCK_KG( R, S , MIXING = TRUE , INPUT _ BIT = ivi )
2. 载入K. 对0≤i≤127:
CLOCK_KG(R, S , MIXING = TRUE , INPUT _ BIT = ki )
f ( x ) = 1 + x 32 + x 47 + x 58 + x 90 + x 121 + x 128
为了消除可能的歧义，定义LFSR对应的修 正（更新）函数：
si +128 = si + si +7 + si +38 + si +70 + si +81 + si +96