现代密码学第5章课件.ppt

* * 通信和法律实施存取过程 * * 密钥托管密码体制的组成成分 用户安全成分（USC） 密钥托管成分（KEC） 数据恢复成分（DRC） * * 随机数的产生 Generation of Random Numbers * * 随机数的用途 相互认证 会话密钥的产生 公钥密码算法中的密钥产生 * * 随机数的要求－随机性 均匀分布 数列中每个数出现的频率相等或近似相等 独立性 数列中任一数不能由其他数推出 经常使用的是伪随机数列 * * 随机数的要求－不可预测性 对数列中以后的数是不可预测的 对于真随机数，满足独立性，所以不可预测 伪随机数列需要特别注意满足不可预测性 * * 随机数源 真随机数源－物理噪声产生器 离子辐射脉冲检测器 气体放电管 漏电容 数的随机性和精度不够 这些设备很难联入网络 * * 伪随机数产生器-线性同余法 参数： 模数m (m0) 乘数a (0≤am) 增量c (0≤cm) 初值种子X0(0≤X00) 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 周期为8 * * 伪随机数产生器-线性同余法 迭代函数应是整周期的，在重复之前应出现0到m间的所有数 产生的数列看上去应是随机的 迭代函数能有效的利用32位运算实现 如果m为素数，且a为m的本原根，产生的数列是整周期的。 a=16807,m=231-1,c=0 * * 伪随机数产生器-线性同余法 假定敌手知道X0,X1,X2,X3,可以确定参数 * * 基于密码算法的随机数产生器 循环加密 C C+1 加密算法 主密钥Km 周期为N的计数器 * * 基于密码算法的随机数产生器 DES的输出反馈方式(OFB)模式 采用OFB模式能用来产生密钥并用 于流加密。加密算法的输出构成伪 随机序列 * * 基于密码算法的随机数产生器 ANSIX9.17伪随机数产生器 EDE EDE EDE ＋ ＋ K1K2 Vi+1 Vi Ri DTi * * BBS （blum-blum-shub）产生器 密码强度最强，基于大整数分解困难性 选择p,q,满足p=q=3 mod 4, n=p×q。选随机数s，s和n互素 X0＝s2 mod n For i=1 to ∞ do { Xi=Xi-12 mod n; Bi=Xi mod 2} Bi为产生的随机数序列 * * 秘密分割 Secrete Sharing * * 秘密分割门限方案 导弹控制发射，重要场所通行检验，通常需要多人同时参与才能生效，需要将秘密分为多人掌管，并且由一定掌管秘密的人数同时到场才能恢复秘密。 * * 门限方案的一般概念 秘密s被分为n个部分,每个部分称为shadow,由一个参与者持有，使得 由k个或多于k个参与者所持有的部分信息可重构s。 由少于k个参与者所持有的部分信息则无法重构s。 称为(k,n)秘密分割门限方案，k称为门限值。 少于k个参与者所持有的部分信息得不到s的任何信息称该门限方案是完善的。 * * Shamir门限方案 基于多项式Lagrange插值公式 设{(x1,y1),…,(xk,yk)}是平面上k个点构成的点集，其中xi(i=1,…k,)各不相同，那么在平面上存在唯一的k-1次多项式f(x)通过这k个点.若把秘密s取做f(0)，n个shadow取做f(xi)(i=1,…n),那么利用其中任意k个shadow可以重构f(x)，从而可以得到秘密s * * Shamir门限方案 有限域GF(q),q为大素数，q≥n+1。秘密s是GF(q)\{0}上均匀选取的随机数，表示为s∈RGF(q)\{0}.k-1个系数a1,a2,…ak-1选取ai ∈RGF(q)\{0}.在GF(q)上构造一个k-1次多项式f(x)=a0+a1x+…+ak-1xk-1 N个参与者P1,…,Pn,Pi的Shadow为f(i)。任意k个参与者得到秘密，可使用{(il,f(il))|l=1,…,k}构造方程组 * * Shamir门限方案 由Lagrange插值公式 * * Shamir门限方案 如果k-1个参与者想获得s，可构造k-1个方程，有k个未知量。对任一s0,设f(0)= s0.这样可以得到第k个方程，得到f(x)。对每个s0都有唯一的多项式满足，所有由k-1个shadow得不到任何s的信息。因此此方案是完善的。 * * Shamir门限方案 例k=3,n=5,q=19,s=11。随机选a1=2,a2=7 f(x)=7x2+2x＋11 mod