随机数的用途课件

随机数的用途相互认证对称密码算法中会话密钥的产生公钥密码算法中的密钥产生(RSA)5.1序列的随机性2023/8/301随机数的用途相互认证5.1序列的随机性2023/8/21随机数的要求－随机性均匀分布(周期大)序列中每个数出现的频率相等或近似相等独立性序列中任一数不能由其他数推出经常使用的是伪随机序列2023/8/302随机数的要求－随机性均匀分布(周期大)2023/8/22随机数的要求－不可预测性对序列中以后的数是不可预测的对于真随机数，满足独立性，所以不可预测伪随机序列需要特别注意满足不可预测性2023/8/303随机数的要求－不可预测性对序列中以后的数是不可预测的20231.周期对于序列{xn}，满足对任意i∈Z+,xi=xi+p的最小正整数p2.游程对于序列{xn}，若有xt-1≠xt=xt+1…=xt+l-1≠xt+l,则（xt，xt+1…，xt+l-1）是一个长为l的游程序列随机性衡量参数2023/8/3041.周期对于序列{xn}，满足对任意i∈Z+,xi=xi+p设序列{xn}的周期为p，定义序列随机性衡量参数3.周期自相关函数若p|j,则R（j）为同相自相关函数，此时A=p,D=0,R（j）=1若p∕j,则R（j）为异相自相关函数2023/8/305设序列{xn}的周期为p，定义序列随机性衡量参数3.周期自相(1)若序列的周期为偶数，则在一个周期内，0、1的个数相等，若周期为奇数，则在一个周期内，0、1的个数相差1。（2）在一个周期内，长度为l的游程数占游程总数的1/2l，且对于任意长度，0游程与1游程个数相等。（3）所有异相自相关函数值相等。Golomb随机性假设2023/8/306(1)若序列的周期为偶数，则在一个周期内，0、1的个数相等，随机数源真随机数源－物理噪声产生器离子辐射脉冲检测器气体放电管漏电容数的随机性和精度不够这些设备很难联入网络2023/8/307随机数源真随机数源－物理噪声产生器2023/8/27伪随机数产生器-线性同余法参数：模数m(m>0)乘数a(0≤a<m)增量c(0≤c<m)初值种子X0(0≤X0<m)Xn(0≤Xn<m)a,c,m的取值是产生高质量随机数的关键一般c=0,模数m确定,此时a的取值非常重要,a一般取为模m的本原元素2023/8/308伪随机数产生器-线性同余法参数：a,c,m的取值是产生高质量伪随机数产生器-线性同余法a=7,c=0,m=32,X0=1{7,17,23,1,7,…}a=3,c=0,m=32,X0=1{3,9,27,17,19,25,11,1,3,…}选m尽可能大，使其接近或等于计算机能表示的最大整数周期为4周期为82023/8/309伪随机数产生器-线性同余法a=7,c=0,m=32,X0=1伪随机数产生器-线性同余法迭代函数应是整周期的，在重复之前应出现0到m间的所有数产生的数列看上去应是随机的迭代函数能有效的利用32位运算实现如果m为素数，且a为m的本原根，产生的数列是整周期的。a=16807(本原根),m=231-1,c=0产生数列是整周期的Xn+1=(16807Xn)mod(231-1)已被广泛应用2023/8/3010伪随机数产生器-线性同余法迭代函数应是整周期的，在重复之前应伪随机数产生器-线性同余法假定敌手知道X0,X1,X2,X3,可以确定参数算法运算速度快，序列周期长，但安全性能不佳的弱点始终制约着该算法在密码学领域的应用.2023/8/3011伪随机数产生器-线性同余法假定敌手知道X0,X1,X2,X3基于密码算法的随机数产生器循环加密CC+1加密算法

主密钥Km周期为N的计数器周期为N,序列不可预测2023/8/3012基于密码算法的随机数产生器循环加密CC+1加密算法主密钥K基于密码算法的随机数产生器DES的输出反馈方式(OFB)模式采用OFB模式能用来产生密钥并用于流加密。加密算法的输出构成伪随机序列2023/8/3013基于密码算法的随机数产生器DES的输出反馈方式(OFB)模式DES的输出反馈方式(CBC)模式(2)P1中有一比特错误,将在所有密文中传播.接收者解密时,仅影响相应分组,后续分组可正常解密2023/8/3014DES的输出反馈方式(CBC)模式(2)P1中有一比特错误,基于密码算法的随机数产生器ANSIX9.17伪随机数产生器(PGP中IDEA)EDEEDEEDE＋＋K1K2Vi+1ViRiDTiDTi:当前的日期和时间Vi:是产生第i个随机数时的种子EDEK1K2=EK1DK2EK1随时更新2023/8/3015基于密码算法的随机数产生器ANSIX9.17伪随机数产生器(随机数产生器-BBS产生器密码强度最强，基于大整数分解困难性选择p,q,满足p=q=3mod4,n=p×q。选随机数s，s和n互素X0＝s2modnFori=1to∞do{Xi=Xi-12modn;Bi=Ximod2}Bi为产生的随机数序列2023/8/3016随机数产生器-BBS产生器密码强度最强，基于大整数分解困难性2023/8/30172023/8/2175.3流密码(序列密码)的基本概念明文:密钥:密文:加密变换:解密变换:2023/8/30185.3流密码(序列密码)的基本概念明文:密钥:密文:加密

加法流密码体制模型2023/8/30192023/8/219移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成

。线性反馈移位寄存器2023/8/3020移位寄存器是流密码产生密钥流的一个主要组成部分。线性反GF(2)上的n级反馈移位寄存器存储器存储器存储器存储器2023/8/3021GF(2)上的n级反馈移位寄存器存储器存储器存储器存储在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n维向量(a1,a2,…,an)表示，其中ai是第i级存储器的内容。2023/8/3022在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态初始状态由用户确定反馈函数f(a1,a2,…,an)是n元布尔函数，即函数的自变量和因变量只取0和1这两个可能的值。函数中的运算有逻辑与、逻辑或、逻辑补等运算。2023/8/3023初始状态由用户确定2023/8/223例下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由下表求出。图

一个3级反馈移位寄存器状态（a3,a2,a1)输出101110111011101110

101110一个3级反馈移位寄存器的状态和输出即输出序列为101110111011…，周期为4。2023/8/3024例下图是一个3级反馈移位寄存器，其初始状态为(a1,aGF(2)上的n级线性反馈移位寄存器线性反馈移位寄存器LFSR（linearfeedbackshiftregister）2023/8/3025GF(2)上的n级线性反馈移位寄存器线性反馈移位寄存器LFS输出序列{at}满足：线性反馈移位寄存器：实现简单、速度快、有较为成熟的理论，成为构造密钥流生成器的最重要的部件之一。2023/8/3026输出序列{at}满足：线性反馈移位寄存器：实现简单、速度快、例下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)可求出输出序列为1001101001000010101110110001111100110…周期为31。2023/8/3027例下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a总是假定c1,c2,…,cn中至少

0，否则f(a1,a2,…,an)≡0。总是假定cn=