机数的产生 Generation of random numbers 2021/2/21
2021/2/21 3 随机数的产生 Generation of Random Numbers
基于密码算法的随机数产生器 ■循环加密 周期为N的计数器 C+1 主密钥Km 加密算法 X:=EK IC+I 2021/2/21
2021/2/21 4 基于密码算法的随机数产生器 ◼ 循环加密 C C+1 加密算法 主密钥Km X = E [C +1] i Km 周期为N的计数器
基于密码算法的随机数产生器 ■DES的輪出反馈方式(OFB)棋式 采用OFB棋式能用来产生蜜钥并用 于流加密。如密算法的輪出构成伪 随机序列 2021/2/21 5
2021/2/21 5 基于密码算法的随机数产生器 ◼ DES的输出反馈方式(OFB)模式 采用OFB模式能用来产生密钥并用 于流加密。加密算法的输出构成伪 随机序列
基于密码算法的随机数产生器 ANSX9.17伪随机数产生器 KiK DT1一 EDE EDE i+1 EDE R2=AESkⅣ由AES[DT V+1=AESk[ ROAES[D7】 2021/2/21 6
2021/2/21 6 基于密码算法的随机数产生器 ◼ ANSIX9.17伪随机数产生器 EDE EDE ＋ EDE ＋ K1K2 Vi+1 Vi Ri DTi [ [ ]] [ [ ]] i 1 K i K i i K i K i V AES R AES DT R AES V AES DT = = +
BBS产生景(bum-bum- shub) ■密码强度最强,基于大整数分解困难性 选择pq,满足p=q=3mod4,n甲pXq。选 随机数s,s和n互素 Xo=s2 mod n For i=1 to oo do t X=X -12mod n; B X, mod 2] B为产生的随机数序列 2021/2/21
2021/2/21 7 BBS产生器（blum-blumshub） ◼ 密码强度最强，基于大整数分解困难性 选择p,q,满足p=q=3 mod 4, n=p×q。选 随机数s，s和n互素 X0＝s 2 mod n For i=1 to ∞ do { Xi=Xi-1 2 mod n; Bi=Xi mod 2} Bi为产生的随机数序列
秘密分割 Secrete Sharing 2021/2/21
2021/2/21 8 秘密分割 Secrete Sharing
秘密分门限方案 导弹控制发狲,重要场所通行检验,通 常需要多人同肘参与才能生效,需要将 秘密分为多人拿管,并且由一定拿管秘 密的人数同时到场才能快复秘密。 2021/2/21
2021/2/21 9 秘密分割门限方案 ◼ 导弹控制发射，重要场所通行检验，通 常需要多人同时参与才能生效，需要将 秘密分为多人掌管，并且由一定掌管秘 密的人数同时到场才能恢复秘密
门限方亲的一般概念 ■秘密S被分为冂个部分,每个部分称为 hadow,由一个 参与者持有,使得 ■由k个或多于k个参与者所持有的部分信息可重构S ■由少于k个参与者所持有的部分信息则无法重构5。 称为(k,n秘密分剖门限方素,k称为门限值。 少于k个参与者所持有的部分信息得不到S的任何信 息称该门限方索是完暮的。 2021/2/21
2021/2/21 10 门限方案的一般概念 ◼ 秘密s被分为n个部分,每个部分称为shadow,由一个 参与者持有，使得 ◼ 由k个或多于k个参与者所持有的部分信息可重构s。 ◼ 由少于k个参与者所持有的部分信息则无法重构s。 ◼ 称为(k,n)秘密分割门限方案，k称为门限值。 ◼ 少于k个参与者所持有的部分信息得不到s的任何信 息称该门限方案是完善的
Shamir门限方案 基于多项式 Lagrange插值公式 设{(x1y),,(×k,y}是平面上k个点构成的点集, 其中(=1,k,)各不相同,那么在平面上存在准 一的k-1次多项式f(x)通过这k个点若把秘密S取做 f(o),n个 shadow取做f((i=1,n,那么利用其 中任意k个 shadow可以重构f(刈),从而可以得到 秘密S 2021/2/21
2021/2/21 11 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≥n+1。秘密S是GF(q)NO} 上均勺选取的随机数,表示为5∈GF(q\O}k1个条 k-1次多项式b+ax+时国(q)上构造一个 数a1,a2,ak选取a1∈RGF(q){O}在G N个参与者P1,…,Pn,P1的$ hadow为f()。任意k个参与 者得到秘密,可使用{(,f()l=1,]构造方程组 +a1(1)+…+a-(i)-=f(Gi) a+a1(i)+…+a1()=f(i) 2021/2/21
2021/2/21 12 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-1x k-1 ◼ N个参与者P1 ,…,Pn ,Pi的Shadow为f(i)。任意k个参与 者得到秘密，可使用{(il ,f(il ))|l=1,…,k}构造方程组 + + + = + + + = − − − − ( ) ( ) ( ) ( ) ( ) ( ) 1 0 1 1 1 1 0 1 1 1 1 k k k k k k k a a i a i f i a a i a i f i