第八章密钥分配与密钥管理:8.1随机数的产生 813伪随机数产生器 ●最为广泛使用的伪随机数产生器是线性同余算法 ●线性同余算法有4个参数: ●模数m(m>0), 乘数a(0≤a<m), ●增量c(0≤c<m), ●初值即种子X(0≤X0m); 由以下送代公式得到随机数数列{X}: Xn+1=aXn+c mod 如果m,a,c,X都为整数则产生的随机数序列{Xn}也都是整数, 且0≤X<m 历忠毛孑技*字
8.1.3 伪随机数产生器 最为广泛使用的伪随机数产生器是线性同余算法 线性同余算法有4个参数： ⚫ 模数m (m>0)， ⚫ 乘数a (0a<m)， ⚫ 增量c (0c<m)， ⚫ 初值即种子X0 (0X0<m)； 由以下迭代公式得到随机数数列{ Xn }： ⚫ Xn＋1＝aXn+c mod m ⚫ 如果m，a，c，X0都为整数则产生的随机数序列{ Xn }也都是整数， 且0X0<m 7/ 第八章 密钥分配与密钥管理：8.1 随机数的产生
第八章密钥分配与密钥管理:8.1随机数的产生 813伪随机数产生器 ●评价线性同余算法的性能有以下3个标准: ①迭代函数应是整周期的,即数列中的数在重复之前应产生出0到 m之间的所有数 ②产生的数列看上去应是随机的。因为数列是确定性产生的,因此 不可能是随机的,但可用各种统计检测来评价数列具有多少随机性 ③迭代函数能有效地利用32位运算实现 ●a,c和m的取值是产生高质量随机数的关键,通过精心选取 a,c和m,可使以上3个标准得以满足 为使随机数数列的周期尽可能大,m应尽可能大,普遍原则是选m 接近等于计算机能表示的最大整数,为了方便32位运算地实现, 可取为231-1,这满足上述的第③条要求 历忠毛孑技*字
8.1.3 伪随机数产生器 评价线性同余算法的性能有以下3个标准： ⚫ ①迭代函数应是整周期的，即数列中的数在重复之前应产生出0到 m之间的所有数 ⚫ ②产生的数列看上去应是随机的。因为数列是确定性产生的，因此 不可能是随机的，但可用各种统计检测来评价数列具有多少随机性 ⚫ ③迭代函数能有效地利用32位运算实现 a, c和m的取值是产生高质量随机数的关键，通过精心选取 a, c和m，可使以上3个标准得以满足 ⚫ 为使随机数数列的周期尽可能大，m应尽可能大，普遍原则是选m 接近等于计算机能表示的最大整数，为了方便32位运算地实现，m 可取为2 31 -1，这满足上述的第③条要求 8/ 第八章 密钥分配与密钥管理：8.1 随机数的产生
第八章密钥分配与密钥管理:8.1随机数的产生 813伪随机数产生器 对第①条来说,一种典型的选取方式是,m为素数(231-1即 为素数)、c=0、a是m的一个本原根 这时c=0,序列的最大可能周期为g(m),还与初始值有关,但达不 到整周期,因为至少0不在序列中 a,c和m的取值尤其重要,如果m7,c=0,m=32,X=1,则产生的 数列为{7,17,23,1,7,…},在32个可能值中只有4个出现,数 列的周期为4,因此结果仍不能令人满意 a=75=16807即为m=231-1的一个本原根,由此得到的随机数产生器 Xn+1=(aX)mod(23-1已被广泛应用,而且与其它产生器相比, 经历过更多的检验,这种产生器常用于统计和模拟工作 历忠毛孑技*字
8.1.3 伪随机数产生器 对第①条来说，一种典型的选取方式是，m为素数(231 -1即 为素数)、c=0、a是m的一个本原根 ⚫ 这时c=0 ，序列的最大可能周期为(m)，还与初始值有关，但达不 到整周期，因为至少0不在序列中 ⚫ a, c和m的取值尤其重要，如果a=7，c=0，m=32，X0＝1，则产生的 数列为{7，17，23，1，7，…}，在32个可能值中只有4个出现，数 列的周期为4，因此结果仍不能令人满意 ⚫ a=75=16807即为m=231－1的一个本原根，由此得到的随机数产生器 Xn＋1＝(aXn ) mod (231－1)已被广泛应用，而且与其它产生器相比， 经历过更多的检验，这种产生器常用于统计和模拟工作 9/ 第八章 密钥分配与密钥管理：8.1 随机数的产生
第八章密钥分配与密钥管理:8.1随机数的产生 81.3伪随机数产生器 ● Knuth给出了使迭代函数达到整周期的充要条件 X=aX+c mod m ●定理5-1线性同余算法达到整周期的充要条件是: ①gcd(c,m)=1 ②对所有满足pm的素数p,有a=1modp ③若m满足4m,则a满足a=1mod4 通常,可取m=2,a=2+1,c=1,其中r是一整数,i<r 也是一整数即可满足定理5-1的条件 ●线性同余算法的强度在于如果将乘数和模数选择得好,则 产生的数列和从1,2,…,m-1中随机选取的数列是不可 区分的 历忠毛孑技*字 10
8.1.3 伪随机数产生器 Knuth给出了使迭代函数达到整周期的充要条件 ⚫ Xn＋1＝aXn+c mod m 定理5-1 线性同余算法达到整周期的充要条件是： ⚫ ① gcd(c,m)=1 ⚫ ② 对所有满足p|m的素数p，有a＝1 mod p ⚫ ③ 若m满足4|m，则a满足a＝1mod 4 通常，可取m＝2 r ，a＝2 i＋1，c＝1，其中r是一整数，i<r 也是一整数即可满足定理5-1的条件 线性同余算法的强度在于如果将乘数和模数选择得好，则 产生的数列和从1，2，…，m-1中随机选取的数列是不可 区分的 10/ 第八章 密钥分配与密钥管理：8.1 随机数的产生
第八章密钥分配与密钥管理:8.1随机数的产生 81.3伪随机数产生器 ●线性同余算法的密码分析 给定参数,则线性同余算法由初始值X确定 如果敌手知道正在使用线性同余算法,并知道算法的参数,则一且 获得数列中的一个数,就可得到以后的所有数 甚至如果敌手只知道正在使用线性同余算法以及产生的数列中极少 部分,就足以确定出算法的参数。假定敌手能确定X,Ⅺ1,X2, X3,就可通过以下方程组解出a,c和m e X=(axo+c)mod m ●X2=(X1+c)modm X3=(ax,+c)mod m 改进的方法是利用系统时钟修改随机数数列 每当产生N个数后,就利用当前的时钟值模m后作为种子 直接将当前的时钟值加到每个随机数上(模m加) 历毛子技大
8.1.3 伪随机数产生器 线性同余算法的密码分析 ⚫ 给定参数，则线性同余算法由初始值X0确定 ⚫ 如果敌手知道正在使用线性同余算法，并知道算法的参数，则一旦 获得数列中的一个数，就可得到以后的所有数 ⚫ 甚至如果敌手只知道正在使用线性同余算法以及产生的数列中极少 一部分，就足以确定出算法的参数。假定敌手能确定X0，X1，X2， X3，就可通过以下方程组解出a，c和m。 ⚫ X1＝(aX0+c) mod m ⚫ X2＝(aX1+c) mod m ⚫ X3＝(aX2+c) mod m 改进的方法是利用系统时钟修改随机数数列 ⚫ 一：每当产生N个数后，就利用当前的时钟值模m后作为种子 ⚫ 二：直接将当前的时钟值加到每个随机数上(模m加) 11/ 第八章 密钥分配与密钥管理：8.1 随机数的产生