2010-5-14 1
第六章 密钥分配与密钥管理
Key Distribution and Key
Management
2010-5-14 2
内容提要
? 单钥加密体制的密钥分配
? 公钥加密体制的密钥管理
? 密钥托管
? 随机数的产生
? 秘密分割
2010-5-14 3
随机数的产生
Generation of Random Numbers
2010-5-14 4
基于密码算法的随机数产生器
? 循环加密
C
C+1
加密算法
主密钥 Km
]1[ ?? CEX mKi
周期为 N的计数器
2010-5-14 5
基于密码算法的随机数产生器
? DES的输出反馈方式 (OFB)模式
采用 OFB模式能用来产生密钥并用
于流加密。加密算法的输出构成伪
随机序列
2010-5-14 6
基于密码算法的随机数产生器
? ANSIX9.17伪随机数产生器
EDE
EDE
EDE＋
＋
K1K2
Vi+1
Vi
Ri
DTi
]][[
]][[
1 iKiKi
iKiKi
DTA E SRA E SV
DTA E SVA E SR
??
??
?
2010-5-14 7
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为产生的随机数序列
2010-5-14 8
秘密分割
Secrete Sharing
2010-5-14 9
秘密分割门限方案
? 导弹控制发射，重要场所通行检验，通
常需要多人同时参与才能生效，需要将
秘密分为多人掌管，并且由一定掌管秘
密的人数同时到场才能恢复秘密 。
2010-5-14 10
门限方案的一般概念
? 秘密 s被分为 n个部分,每个部分称为 shadow,由一个
参与者持有，使得
? 由 k个或多于 k个参与者所持有的部分信息可重构 s。
? 由少于 k个参与者所持有的部分信息则无法重构 s。
? 称为 (k,n)秘密分割门限方案,k称为门限值。
? 少于 k个参与者所持有的部分信息得不到 s的任何信
息称该门限方案是完善的。
2010-5-14 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
2010-5-14 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-1xk-1
? N个参与者 P1,…,Pn,Pi的 Shadow为 f(i)。任意 k个参与
者得到秘密，可使用 {(il,f(il))|l=1,…,k}构造方程组
?
?
?
?
?
????
????
?
?
?
?
)()()(
)()()(
1
110
1
1
11110
k
k
kkk
k
k
ifiaiaa
ifiaiaa
?
?
?
2010-5-14 13
Shamir门限方案
? 由 Lagrange插值公式
)( m od
)(
)()(
1 1
q
ii
ix
ifxf
k
j
k
jl
l lj
l
j? ?
?
?
? ?
?
?
)( m od)()1(
1 1
1 q
ii
i
ifs
k
j
k
jl
l lj
l
j
k ? ?
?
?
?
?
?
??
2010-5-14 14
Shamir门限方案
? 如果 k-1个参与者想获得 s，可构造 k-1个方
程，有 k个未知量。对任一 s0,设 f(0)= s0.
这样可以得到第 k个方程，得到 f(x)。对
每个 s0都有唯一的多项式满足，所有由 k-
1个 shadow得不到任何 s的信息。因此此
方案是完善的。
2010-5-14 15
Shamir门限方案
? 例 k=3,n=5,q=19,s=11。随机选 a1=2,a2=7
f(x)=7x2+2x＋ 11 mod 19。
计算 f(1)=1,f(2)=5,f(3)=4,f(4)=17,f(5)=6
已知 f(2),f(3),f(5),重构
1127
)35)(25(
)3)(2(
6
)53)(23(
)5)(2(
4
)52)(32(
)5)(3(
5)(
2 ???
??
??
?
??
??
?
??
??
?
xx
xxxxxx
xf
2010-5-14 16
Asmuth-Bloom门限方案
? 首先选取大素数 q，正整数 s(秘密数据 )，
以及 n个严格递增的 m1,m2,…,mn,满足
1,q>s
2,(mi,mj)=1(对所有 i≠j)
3,(q,mi)=1(对所有 i)
4.
??
?
?
??
?
??
1
1
1
1
k
i
in
k
i
i mqmN
N/q大于任取的 k-1和不
同的 mi的乘积
选随机的 A,满足 0≤A ≤[N/q] -1，公布 q和 A
2010-5-14 17
Asmuth-Bloom门限方案
? 求 y=s+Aq(y<N),yi=y(mod mi) (i=1,…,N).
（ mi,yi）为一子密钥,集合 {(mi,yi)}(i=1…,n)构成
(k,n)门限方案
? 当 k个参与者提供子密钥时，可建立方程组
? 由中国剩余定理可以求得 y=y’mod N‘,N’为 k个
m的乘积，大于等于 N,所以 y=y’是唯一的，再由 y-
Aq得到 s
?
?
?
?
?
?
?
ymy
ymy
kk ii
ii
)(m o d
)(m o d
11
?
2010-5-14 18
Asmuth-Bloom门限方案
? 如果仅有 k－ 1个参与者，只能求得 y’’=y mod
N’’，而 N’’<N/q,无法确定 y。
? 例 k=2,n=3,q=7,s=4,m1=9,m2=11,m3=13
N=m1m2=99>91=7*13=qm3
在 [0,[99/7]-1]=[0,13]中随机取 A=10，求 y＝
s+Aq=4+10× 7=74.
y1＝ y mod m1=2
y2＝ y mod m2=8
y3＝ y mod m3=9
(9,2),(11,8),(13,9)构
成（ 2,3）门限方案
2010-5-14 19
Asmuth-Bloom门限方案
? 若已知 (9,2),(11,8)，可建立方程组
? 解得 y=(11× 5× 2＋ 9× 5× 8) mod
99=74
? S=y-Aq=74-10× 7＝ 4
?
?
?
?
?
?
?
y
y
)11( m o d8
)9( m o d2
第六章 密钥分配与密钥管理
Key Distribution and Key
Management
2010-5-14 2
内容提要
? 单钥加密体制的密钥分配
? 公钥加密体制的密钥管理
? 密钥托管
? 随机数的产生
? 秘密分割
2010-5-14 3
随机数的产生
Generation of Random Numbers
2010-5-14 4
基于密码算法的随机数产生器
? 循环加密
C
C+1
加密算法
主密钥 Km
]1[ ?? CEX mKi
周期为 N的计数器
2010-5-14 5
基于密码算法的随机数产生器
? DES的输出反馈方式 (OFB)模式
采用 OFB模式能用来产生密钥并用
于流加密。加密算法的输出构成伪
随机序列
2010-5-14 6
基于密码算法的随机数产生器
? ANSIX9.17伪随机数产生器
EDE
EDE
EDE＋
＋
K1K2
Vi+1
Vi
Ri
DTi
]][[
]][[
1 iKiKi
iKiKi
DTA E SRA E SV
DTA E SVA E SR
??
??
?
2010-5-14 7
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为产生的随机数序列
2010-5-14 8
秘密分割
Secrete Sharing
2010-5-14 9
秘密分割门限方案
? 导弹控制发射，重要场所通行检验，通
常需要多人同时参与才能生效，需要将
秘密分为多人掌管，并且由一定掌管秘
密的人数同时到场才能恢复秘密 。
2010-5-14 10
门限方案的一般概念
? 秘密 s被分为 n个部分,每个部分称为 shadow,由一个
参与者持有，使得
? 由 k个或多于 k个参与者所持有的部分信息可重构 s。
? 由少于 k个参与者所持有的部分信息则无法重构 s。
? 称为 (k,n)秘密分割门限方案,k称为门限值。
? 少于 k个参与者所持有的部分信息得不到 s的任何信
息称该门限方案是完善的。
2010-5-14 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
2010-5-14 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-1xk-1
? N个参与者 P1,…,Pn,Pi的 Shadow为 f(i)。任意 k个参与
者得到秘密，可使用 {(il,f(il))|l=1,…,k}构造方程组
?
?
?
?
?
????
????
?
?
?
?
)()()(
)()()(
1
110
1
1
11110
k
k
kkk
k
k
ifiaiaa
ifiaiaa
?
?
?
2010-5-14 13
Shamir门限方案
? 由 Lagrange插值公式
)( m od
)(
)()(
1 1
q
ii
ix
ifxf
k
j
k
jl
l lj
l
j? ?
?
?
? ?
?
?
)( m od)()1(
1 1
1 q
ii
i
ifs
k
j
k
jl
l lj
l
j
k ? ?
?
?
?
?
?
??
2010-5-14 14
Shamir门限方案
? 如果 k-1个参与者想获得 s，可构造 k-1个方
程，有 k个未知量。对任一 s0,设 f(0)= s0.
这样可以得到第 k个方程，得到 f(x)。对
每个 s0都有唯一的多项式满足，所有由 k-
1个 shadow得不到任何 s的信息。因此此
方案是完善的。
2010-5-14 15
Shamir门限方案
? 例 k=3,n=5,q=19,s=11。随机选 a1=2,a2=7
f(x)=7x2+2x＋ 11 mod 19。
计算 f(1)=1,f(2)=5,f(3)=4,f(4)=17,f(5)=6
已知 f(2),f(3),f(5),重构
1127
)35)(25(
)3)(2(
6
)53)(23(
)5)(2(
4
)52)(32(
)5)(3(
5)(
2 ???
??
??
?
??
??
?
??
??
?
xx
xxxxxx
xf
2010-5-14 16
Asmuth-Bloom门限方案
? 首先选取大素数 q，正整数 s(秘密数据 )，
以及 n个严格递增的 m1,m2,…,mn,满足
1,q>s
2,(mi,mj)=1(对所有 i≠j)
3,(q,mi)=1(对所有 i)
4.
??
?
?
??
?
??
1
1
1
1
k
i
in
k
i
i mqmN
N/q大于任取的 k-1和不
同的 mi的乘积
选随机的 A,满足 0≤A ≤[N/q] -1，公布 q和 A
2010-5-14 17
Asmuth-Bloom门限方案
? 求 y=s+Aq(y<N),yi=y(mod mi) (i=1,…,N).
（ mi,yi）为一子密钥,集合 {(mi,yi)}(i=1…,n)构成
(k,n)门限方案
? 当 k个参与者提供子密钥时，可建立方程组
? 由中国剩余定理可以求得 y=y’mod N‘,N’为 k个
m的乘积，大于等于 N,所以 y=y’是唯一的，再由 y-
Aq得到 s
?
?
?
?
?
?
?
ymy
ymy
kk ii
ii
)(m o d
)(m o d
11
?
2010-5-14 18
Asmuth-Bloom门限方案
? 如果仅有 k－ 1个参与者，只能求得 y’’=y mod
N’’，而 N’’<N/q,无法确定 y。
? 例 k=2,n=3,q=7,s=4,m1=9,m2=11,m3=13
N=m1m2=99>91=7*13=qm3
在 [0,[99/7]-1]=[0,13]中随机取 A=10，求 y＝
s+Aq=4+10× 7=74.
y1＝ y mod m1=2
y2＝ y mod m2=8
y3＝ y mod m3=9
(9,2),(11,8),(13,9)构
成（ 2,3）门限方案
2010-5-14 19
Asmuth-Bloom门限方案
? 若已知 (9,2),(11,8)，可建立方程组
? 解得 y=(11× 5× 2＋ 9× 5× 8) mod
99=74
? S=y-Aq=74-10× 7＝ 4
?
?
?
?
?
?
?
y
y
)11( m o d8
)9( m o d2
