随机数的用途课件.ppt

1、第第5 5章章 序列密码序列密码2022-3-221随机数的用途随机数的用途n相互认证相互认证n对称密码算法中会话密钥的产生对称密码算法中会话密钥的产生n公钥密码算法中的密钥产生公钥密码算法中的密钥产生(RSA)5.1 5.1 序列的随机性序列的随机性第第5 5章章 序列密码序列密码2022-3-222随机数的要求随机性随机数的要求随机性n均匀分布均匀分布(周期大周期大)n序列中每个数出现的频率相等或近似相等序列中每个数出现的频率相等或近似相等n独立性独立性n序列中任一数不能由其他数推出序列中任一数不能由其他数推出n经常使用的是伪随机序列经常使用的是伪随机序列第第5 5章章 序列密码序列密码2

2、022-3-223随机数的要求随机数的要求n对序列中以后的数是不可预测的对序列中以后的数是不可预测的n对于真随机数，满足独立性，所以不可对于真随机数，满足独立性，所以不可预测预测n伪随机序列需要伪随机序列需要特别特别注意满足不可预测注意满足不可预测性性第第5 5章章 序列密码序列密码2022-3-2241.1.周期周期对于序列对于序列xxn n ，满足对任意，满足对任意i iZZ+ +,x,xi i=x=xi+pi+p的最小正整数的最小正整数p p2.2.游程游程对于序列对于序列xxn n ，若有，若有x xt-1t-1x xt t= =x xt+1t+1= =x xt+l-1t+l-1x x

3、t+lt+l, ,则（则（x xt t，x xt+1t+1，x xt+l-1t+l-1）是一个长为）是一个长为l l的游程的游程序列随机性衡量参数序列随机性衡量参数第第5 5章章 序列密码序列密码2022-3-225n设序列设序列xxn n 的周期为的周期为p p，定义，定义序列随机性衡量参数序列随机性衡量参数3.3.周期自相关函数周期自相关函数;0d,;0A, 2 , 1,)(jiijiixxpixxpijpDAjR其中若若p|j,p|j,则则R R（j j）为同相自相关函数，此时）为同相自相关函数，此时A=p,D=0,RA=p,D=0,R（j j）=1=1若若p pj,j,则则R R（j

4、j）为异相自相关函数）为异相自相关函数第第5 5章章 序列密码序列密码2022-3-226(1)(1)若序列的周期为偶数，则在一个周期内，若序列的周期为偶数，则在一个周期内，0 0、1 1的的个数相等，若周期为奇数，则在一个周期内，个数相等，若周期为奇数，则在一个周期内，0 0、1 1 的个数相差的个数相差1 1。（2 2）在一个周期内，长度为）在一个周期内，长度为l l的游程数占游程总数的的游程数占游程总数的1/21/2l l，且对于任意长度，且对于任意长度，0 0游程与游程与1 1游程个数相等。游程个数相等。（3 3）所有异相自相关函数值相等。）所有异相自相关函数值相等。GolombGol

5、omb随机性假设随机性假设第第5 5章章 序列密码序列密码2022-3-227随机数源随机数源n真随机数源物理噪声产生器真随机数源物理噪声产生器n离子辐射脉冲检测器离子辐射脉冲检测器n气体放电管气体放电管n漏电容漏电容n数的随机性和精度不够数的随机性和精度不够n这些设备很难联入网络这些设备很难联入网络第第5 5章章 序列密码序列密码2022-3-228伪随机数产生器伪随机数产生器- -线性同余法线性同余法参数：参数：模数模数m (m0)m (m0)乘数乘数a (0am)a (0am)增量增量c (0cm)c (0cm)初值种子初值种子X X0 0(0X(0X0 0m)m)X Xn n(0X(0

6、Xn nm)m)mcaXXnnmod)(1a a,c,m,c,m的取值是的取值是产生高质量随产生高质量随机数的关键机数的关键一般一般c=0,c=0,模数模数m m 确定确定, ,此时此时a a的取值非常重要的取值非常重要, ,a a一般取为模一般取为模m m的本原元素的本原元素第第5 5章章 序列密码序列密码2022-3-229伪随机数产生器伪随机数产生器-线性同余法线性同余法na=7,c=0,m=32,Xa=7,c=0,m=32,X0 0=1=1n7,17,23,1,7,7,17,23,1,7, na=3,c=0,m=32,Xa=3,c=0,m=32,X0 0=1 =1 n3,9,27,17

7、,19,25,11,1,3,3,9,27,17,19,25,11,1,3, n选选mm尽可能大，使其接近或等于计算机尽可能大，使其接近或等于计算机能表示的最大整数能表示的最大整数周期为周期为4 4周期为周期为8 8第第5 5章章 序列密码序列密码2022-3-2210伪随机数产生器伪随机数产生器-线性同余法线性同余法n迭代函数应是整周期的，在重复之前应出现迭代函数应是整周期的，在重复之前应出现0 0到到m m间的所有数间的所有数n产生的数列看上去应是随机的产生的数列看上去应是随机的n迭代函数能有效的利用迭代函数能有效的利用3232位运算实现位运算实现n如果如果m m为素数，且为素数，且a a为

8、为m m的本原根，产生的数列的本原根，产生的数列是整周期的。是整周期的。na=16807(a=16807(本原根本原根),m=2),m=23131-1,c=0-1,c=0产生数列是整周产生数列是整周期的期的nXn+1=(1680716807Xn)mod (231-1)已被广泛应用已被广泛应用第第5 5章章 序列密码序列密码2022-3-2211伪随机数产生器伪随机数产生器-线性同余法线性同余法n假定敌手知道假定敌手知道X X0 0,X,X1 1,X,X2 2,X,X3 3, ,可以确定参数可以确定参数mcaXXmcaXXmcaXXmodmodmod231201算法运算速度快，序列周期长，但安全

9、性能不佳算法运算速度快，序列周期长，但安全性能不佳的弱点始终制约着该算法在密码学领域的应用的弱点始终制约着该算法在密码学领域的应用. .第第5 5章章 序列密码序列密码2022-3-2212基于密码算法的随机数产生器基于密码算法的随机数产生器n循环加密循环加密CC+1加密算法加密算法 主密钥主密钥Km1CEXmKi周期为周期为N的计数器的计数器周期为周期为N,序列不可预测序列不可预测第第5 5章章 序列密码序列密码2022-3-2213基于密码算法的随机数产生器基于密码算法的随机数产生器nDESDES的输出反馈方式的输出反馈方式(OFB)(OFB)模式模式采用采用OFBOFB模式能用来产生密钥

10、并用于流加密。加密算模式能用来产生密钥并用于流加密。加密算法的输出构成伪随机序列法的输出构成伪随机序列nDES的输出反馈方式的输出反馈方式(CBC)模式模式)()(212122CDCPCPECKK(2)P1中有一比特错误中有一比特错误,将在所有密文中传播将在所有密文中传播.接收者解密时接收者解密时,仅影响相仅影响相应分组应分组,后续分组可正常后续分组可正常解密解密第第5 5章章 序列密码序列密码2022-3-2215基于密码算法的随机数产生器基于密码算法的随机数产生器nANSIX9.17ANSIX9.17伪随机数产生器伪随机数产生器(PGP(PGP中中IDEA)IDEA)EDEEDEEDEK1

11、K2Vi+1ViRiDTi12121212,1,iK KiK KiiK KiK KiREDEVEDEDTVEDEREDEDTDTi:DTi:当前的日期和时间当前的日期和时间Vi:Vi:是产生第是产生第i i个随机数时的种子个随机数时的种子EDEK1K2=EK1DK2EK1随时更新随时更新第第5 5章章 序列密码序列密码2022-3-2216随机数产生器随机数产生器-BBS产生器产生器n密码强度最强，基于大整数分解困难性密码强度最强，基于大整数分解困难性选择选择p,q,p,q,满足满足p=q=3 mod 4, n=pp=q=3 mod 4, n=pq q。选随机数选随机数s s，s s和和n n

12、互素互素X X0 0s s2 2 mod n mod nFor i=1 to do For i=1 to do X Xi i=X=Xi-1i-12 2 mod n; mod n; B Bi i=X=Xi i mod 2 mod 2B Bi i为产生的随机数序列为产生的随机数序列第第5 5章章 序列密码序列密码2022-3-2217第第5 5章章 序列密码序列密码2022-3-22185.35.3 流密码流密码( (序列密码序列密码) )的基本概念的基本概念明文明文:210 xxxx 密钥密钥:210zzzz 密文密文:210yyyy )2(GFxi )2(GFzi )2(GFyi 加密变换加密

13、变换:iiizxy 解密变换解密变换:iiizyx 第第5 5章章 序列密码序列密码2022-3-2219 加法流密码体制模型加法流密码体制模型第第5 5章章 序列密码序列密码2022-3-2220移位寄存器是流密码产生密钥流的一个主要移位寄存器是流密码产生密钥流的一个主要组成部分。组成部分。GF(2)上一个上一个n级反馈移位寄存器由级反馈移位寄存器由n个二元个二元存储器存储器与一个与一个反馈函数反馈函数f(a1,a2,an)组成组成 。 线性反馈移位寄存器线性反馈移位寄存器第第5 5章章 序列密码序列密码2022-3-2221 GF(2)上的上的n级反馈移位寄存器级反馈移位寄存器存储器存储器

14、存储器存储器存储器存储器存储器存储器第第5 5章章 序列密码序列密码2022-3-2222在任一时刻，这些级的内容构成该反馈移位寄在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于存器的状态，每一状态对应于GF(2)上的一个上的一个n维向量，共有维向量，共有2n种可能的状态。种可能的状态。每一时刻的状态可用每一时刻的状态可用n维向量维向量(a1,a2,an)表示，其中表示，其中ai是第是第i级存储器的内容。级存储器的内容。第第5 5章章 序列密码序列密码2022-3-2223初始状态初始状态由用户确定由用户确定 反馈函数反馈函数f(a1,a2,an)是是n元布尔函数，即函元布尔

15、函数，即函数的自变量和因变量只取数的自变量和因变量只取0和和1这两个可能的这两个可能的值。值。函数中的运算有函数中的运算有逻辑与、逻辑或、逻辑补等逻辑与、逻辑或、逻辑补等运运算。算。第第5 5章章 序列密码序列密码2022-3-2224例例 下图下图 是一个是一个3 3级反馈移位寄存器，其级反馈移位寄存器，其初始初始状态为状态为( (a a1 1,a,a2 2,a,a3 3)=(1,0,1)=(1,0,1)，输出可由下表求输出可由下表求出。出。图图 一个一个3级反馈移位寄存器级反馈移位寄存器状态（状态（a3,a2,a1)输出输出1 0 11 1 01 1 10 1 11 0 11 1 0 10

16、1110 一个一个3级反馈移位寄存级反馈移位寄存器的状态和输出器的状态和输出即输出序列为即输出序列为101110111011，周期为，周期为4。第第5 5章章 序列密码序列密码2022-3-2225GF(2)上的上的n级线性反馈移位寄存器级线性反馈移位寄存器nnnnacacacaaaf121121),( 线性反馈移位寄存器线性反馈移位寄存器LFSRLFSR（linear feedback shift linear feedback shift registerregister）第第5 5章章 序列密码序列密码2022-3-2226输出序列at满足：nnnnacacacaaaf121121),(

17、 11312212111 nnnnnnnnacacacaacacaca线性反馈移位寄存器：线性反馈移位寄存器：实现简单、速度快、有较为成熟的理论，实现简单、速度快、有较为成熟的理论，成为构造成为构造密钥流生成器的最重要的部件之一密钥流生成器的最重要的部件之一。, 2 , 1,1111 tacacacatntntntn第第5 5章章 序列密码序列密码2022-3-2227例 下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)可求出输出序列为可求出输出序列为1001101001000010101110110001111100110周期为周期为31。第第5 5章章 序列密码序列密码2022-3-2228总是假定c1,c2,cn中至少0，否则 f(a1,a2,an)0。 总是假定cn=1。LFSR输出序列的性质：输出序列的性质：完全由其反馈函数决定。完全由其反馈函数决定。n级级LFSR状态数：状态数：最多有最多有2n个。个。n级级LFSR的状态周期：的状态周期： 2n-1。输出序列的周期输出序列的周期=状态周期状态周期， 2n-1。选择合适的反馈函数可使序列的周期达到最大值选择合适的反馈函数可使序列的周期达到最大值2n-1，周期达到最大值的序列称为周期达到最大值的序列称为m序列序列。