14
关于LCG和LFSR
LCG和LFSR • 具有很好的统计特性 • 但是是可以预测的:根据以往的输出可以预测出新 的输出 可预测性可以用来对加密过程进行选择明文攻击
Mihir Bellare and Phillip Rogaway, Introduction to Modern Cryptography课件
procedure Inialize
$ $ {0,1}s ; b {0,1} St
procedure Next( m ) ( X1[1] X 1[m ], St ) G ( St , m )
$ {0,1}nm X 0 [1] X 0 [m ]
procedure Finalize(b ') return( b b ')
状态发生器的符号表示
( X [1] X [ m ], St ) G ( St , m )
表示： 运行G ，其初始状态是 St ，运行 m 步 X [1] X [ m ]表示输出序列 St 表示修改后的状态
Mihir Bellare and Phillip Rogaway, Introduction to Modern Cryptography课件
return X b [1] X b [m ]
攻击者 A 的和随机数不可区分的优势为： indr A AdvG ( A) 2 Pr INDR G true 1
17
通过分组密码构建流密码/伪随机数发生器
令 E :{0,1}k {0,1}n {0,1}n 表示一个分组密码，定义算法：
18
CTR模式的PRG的安全性
Fact：如果E是一个安全的 PRF(伪随机函数)， 那么G是一个INDR安全的 PRG.
Mihir Bellare and Phillip Rogaway, Introduction to Modern Cryptography课件
19
ANSI X9.17 PRG
3
用于加密
Alice 维护状态 St A ，Bob 维护状态 St B 初始时： St A = St B ，为一随机的种子。
( M [1] M [m ])
( X [1] X [m ], St A ) G ( St A , m ) ( X [1] X [m ], St B ) G ( St B , m ) for i 1,, m do C [i ] X [i ] M [i ] for i 1,, m do M [i ] X [i ] C [i ]
令 E :{0,1}k {0,1}n {0,1}n 表示一个分组密码，定义算法：
algorithm G ( St ) ( K , S ) St X EK ( S ) ; S EK ( X ) return ( X ,( K , S ))
状态为 ( K , S ) ， K 是加密的密钥， S {0,1}n
维基百科
10
16-bit Fibonacci LFSR
A 16-bit Fibonacci LFSR. The feedback tap numbers in white correspond to a primitive polynomial in the table so the register cycles through the maximum number of 65535 states excluding the all-zeroes state. The state shown, 0xACE1 (hexadecimal) will be followed by 0x5670
X 0 , 0 X 0 m ：为种子
多数编译器的库中使用了该理论实现其伪随机数发生器 rand()
Mihir Bellare and Phillip Rogaway, Introduction to Modern Cryptography课件
7
线性同余发生器
Hyperplanes of a linear congruential generator in three dimensions
15
理论上的安全需求
和随机数的不可区分 INDR (Indistinguishability from random) 选一个随机的种子 St ( X 1[1] X 1[ m ], St ) G ( St , m ) 随机地选取 X 0 [1] X 0 [ m ] 随即的选取位 b
X b [1] X b [ m ]
(C [1]C [m ])
注意： Alice 和 Bob 的状态必须同步。
Mihir Bellare and Phillip Rogaway, Introduction to Modern Cryptography课件
4
用于伪随机位生成器
状态发生器的输出可以用于需要随机位的场合 • 密钥 • 分组密码的IV • Nonces • 仿真
Mihir Bellare and Phillip Rogaway, Introduction to Modern Cryptography课件
5
状态发生器
• 线性同余发生器
– LCGs (Linear Congruential Generatots)
• 线性反馈移位寄存器
– LFSRs (Linear Feedback Shift Registers)
Mihir Bellare and Phillip Rogaway, Introduction to Modern C全性?
令 E :{0,1}k {0,1}n {0,1}n 表示一个分组密码，定义算法：
algorithm G ( St ) ( K , i ) St X E K ( i 1) return ( X ,( K , i 1))
Mihir Bellare and Phillip Rogaway, Introduction to Modern Cryptography课件
21
前向安全性
假设攻击者得到了 St[ 2]，那么： 1、它可以计算出 X [3] X [ 4] 2、当时他能否计算出 X [1] X [ 2]? 前向安全性要求第 2 个问题的答案为 No. 前向安全的目的是为了保证系统在受到恶意软件攻击的情况下 的安全性。
A
b'
A要计算出 b 如果 A的优势是可以忽略不计的，G 是安全的。
Mihir Bellare and Phillip Rogaway, Introduction to Modern Cryptography课件 16
正式定义
令G 表示状态生成器， 其种子的长度为 s ， 输出的分组的长度为 n Game INDR G
algorithm G ( St ) ( K , i ) St X E K ( i 1) return ( X ,( K , i 1))
状态为 ( K , i ) ， K 是加密的密钥， i 为 n 位的整数 ( 0 i 2n ) ；
$ 初始状态为 ( K , 0) ，其中 K {0,1}k
$ $ 初始状态为 ( K , S ) ，其中 K {0,1}k , S {0,1}n
20
其他标准
• FIPS-186定义了基于DES和SHA-1的PRGs • NIST SP 8000-90定义了基于hash、HMAC、 CTR、ECC的生成器 • ANSI X9.31和ANSI X9.62 • OpenSSl定义了基于SHA-1的PRG
维基百科
12
基于LFSR的流密码：A5/1
The operation of the keystream generator in A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations.
13
RC4
The lookup stage of RC4. The output byte is selected by looking up the values of S(i) and S(j), adding them together modulo 256, and then using the sum as an index into S; S(S(i) + S(j)) is used as a byte of the key stream, K.
维基百科 8
线性反馈移位寄存器
• 4-bit Fibonacci LFSR • 16-bit Fibonacci LFSR • 16-bit Galois LFSR.
9
4-bit Fibonacci LFSR
A 4-bit Fibonacci LFSR with its state diagram. The XOR gate provides feedback to the register that shifts bits from left to right. The maximal sequence consists of every possible state except the "0000" state.
维基百科 11
16-bit Galois LFSR
A 16-bit Galois LFSR. The register numbers in white correspond to the same primitive polynomial as the Fibonacci example but are counted in reverse to the shifting direction. This register also cycles through the maximal number of 65535 states excluding the allzeroes state. The state ACE1 hex shown will be followed by E270 hex.