第六章密钥分配与密钥管理,第四节,随机数的产生

2013-1-714
随机数的产生
Generation of Random Numbers

2013-1-715
随机数的用途

相互认证

会话密钥的产生


公钥密码算法中的密钥产生

2013-1-716
随机数的要求－随机性

均匀分布

数列中每个数出现的频率相等或近似相等

独立性


数列中任一数不能由其他数推出

经常使用的是伪随机数列
2013-1-717
随机数的要求－不可预测性

对数列中以后的数是不可预测的

对于真随机数，满足独立性，所以不可
预测


伪随机数列需要特别注意满足不可预测
性

2013-1-718
随机数源

真随机数源－物理噪声产生器

离子辐射脉冲检测器

气体放电管


漏电容


数的随机性和精度不够


这些设备很难联入网络
2013-1-719
伪随机数产生器-线性同余法
参数：
模数m (m>0)
乘数a (0≤a增量c (0≤c初值种子X0(0≤X0<0)

mcaXXnnmod)(1


a,c,m的取值是
产生高质量随
机数的关键

目前中的最广泛的

2013-1-720
伪随机数产生器-线性同余法

a=7,c=0,m=32,X
0
=1


{7,17,23,1,7,…}


a=3,c=0,m=32,X
0
=1


{3,9,27,17,19,25,11,1,3,…}


选m尽可能大，使其接近或等于计算机
能表示的最大整数

周期为4
周期为8
2013-1-721

伪随机数产生器-线性同余法

迭代函数应是整周期的，在重复之前应
出现0到m间的所有数


产生的数列看上去应是随机的


迭代函数能有效的利用32为运算实现


如果m为素数，且a为m的本原根，产生
的数列是整周期的。


a=16807,m=2
31
-1,c=0

a=16807 m=2^31 -1 c=0 常用于模拟

2013-1-722
伪随机数产生器-线性同余法

假定敌手知道X
0,X1,X2,X3
,可以确定参数









mcaXXmcaXXmcaXXmod
mod
mod

23
12
01

密码场合用的比较少。
2013-1-74
基于密码算法的随机数产生器

循环加密
C

C+1
加密算法
主密钥K
m

]1[CEX
m
Ki

周期为N的计数器

2013-1-75
基于密码算法的随机数产生器

DES的输出反馈方式(OFB)模式
采用OFB模式能用来产生密钥并用
于流加密。加密算法的输出构成伪
随机序列
2013-1-76

基于密码算法的随机数产生器

ANSIX9.17伪随机数产生器
EDE
EDE
EDE
＋

＋

K1K
2

V
i+1

V
i

R
i

DT
i

]][[]][[1iKiKiiKiKiDTAESRAESVDTAESVAESR



密码强度最高的伪随机数的产生器，并且速度还比较快。用于PGP等，用途很广

2013-1-77
BBS产生器（blum-blum-
shub）


密码强度最强，基于大整数分解困难性
选择p,q,满足p=q=3 mod 4, n=p×q。选
随机数s，s和n互素

X0＝s2mod n
For i=1 to ∞do {
Xi=Xi-12mod n;
Bi=Ximod 2}
Bi为产生的随机数序列

相对前几个这个的密码强度最强。但速度相对比较慢