第5章 密钥分配与密钥管理.ppt

如果一个参与者或一组未经授权的参与者在猜测秘密s时，并不比局外人猜秘密时有优势，即： ③由少于k个参与者所持有的部分信息得不到秘密s的任何信息。 则称这个方案是完善的，即(k, n)-秘密分割门限方案是完善的。 下面介绍最具代表性的两个秘密分割门限方案。 5.5.2 Shamir门限方案 Shamir门限方案是基于多项式的Lagrange插值公式的。 设{(x1,y1),…,(xk,yk)}是平面上k个点构成的点集，其中xi(i=1,…,k)均不相同，那么在平面上存在一个唯一的k-1次多项式f(x)通过这k个点。 若把密钥s取作f(0), n个子密钥取作f(xi) (i=1, 2 ,…, n)，那么利用其中的任意k个子密钥可重构f(x)，从而可得密钥s。 这种门限方案也可按如下更一般的方式来构造。 设GF(q)是一有限域，其中q是一大素数，满足q≥n+1, 秘密s是在GF(q)\{0}上均匀选取的一个随机数，表示为s∈RGF(q) \{0}。k-1个系数a1,a2,…,ak-1的选取也满足ai∈RGF(q) \{0}(i=1,2,…,k-1)。 在GF(q)上构造一个k-1次多项式 f(x)=a0+a1x+…+ak-1 xk-1。 n个参与者记为P1, P2 ,…, Pn, Pi分配到的子密钥为f(i)。如果任意k个参与者 要想得到秘密s，可使用{(il, f(il))|l=1,…,k}构造如下的线性方程组： (5.1) 因为il(1≤l≤k)均不相同，所以可由Lagrange插值公式构造如下的多项式： 从而可得秘密s=f(0)。 然而参与者仅需知道f(x)的常数项f(0)而无需知道整个多项式f(x)，所以仅需以下表达式就可求出s： 如果k-1个参与者想获得秘密s, 他们可构造出由k-1个方程构成的线性方程组, 其中有k个未知量。对GF(q)中的任一值s0，可设f(0)=s0，这样可得第k个方程，并由Lagrange插值公式得出f(x)。 因此对每一s0∈GF(q)都有一个惟一的多项式满足式（5.1），所以已知k-1个子密钥得不到关于秘密s的任何信息，因此这个方案是完善的。 例5.1 设k=3, n=5, q=19, s=11，随机选取a1=2, a2=7，得多项式为 f(x)=(7x2+2x+11) mod 19 分别计算 f(1)=(7+2+11) mod 19=20 mod 19=1 f(2)=(28+4+11) mod 19=43 mod 19=5 f(3)=(63+6+11) mod 19=80 mod 19=4 f(4)=(112+8+11) mod 19=131 mod 19=17 f(5)=(175+10+11) mod 19=196 mod 19=6 得5个子密钥。 如果知道其中的3个子密钥 f(2) = 5, f(3)=4, f(5)=6，就可按以下方式重构f(x)： 所以 从而得秘密为s=11。 5.5.3 基于中国剩余定理的门限方案 The end! Thanks Modern Cryptography * Modern Cryptography * 第5章 密钥分配与密钥管理 单钥加密体制的密钥分配 公钥加密体制的密钥管理 密钥托管 随机数的产生 秘密分割 5.4 随机数的产生 随机数在密码学中起着重要的作用。这一节首先介绍随机数在密码学中的作用，然后介绍产生随机数的一些方法。 5.4.1 随机数的使用 很多密码算法都需使用随机数，例如： 相互认证。在密钥分配中需使用一次性随机数来防止重放攻击。 会话密钥的产生。 公钥密码算法中密钥的产生，用随机数作为公钥密码算法中的密钥，或以随机数来产生公钥密码算法中的密钥。 在随机数的上述应用中，都要求随机数序列满足随机性和不可预测性。 1. 随机性 以下两个准则常用来保障数列的随机性： ① 均匀分布: 数列中每个数出现的频率应相等或近似相等。 ② 独立性: 数列中任意一数都不能由其他数推出。 数列是否满足均匀分布可通过检测得出，而是否满足独立性则无法检测。 有很多检测方法能证明数列不满足独立性，因此通常检测数列是否满足独立性的方法是在对数列进行了足够多次检测后都不能证明不满足独立性，就可比较有把握地相信该数列满足独立性。 在设计密码算法时，经常使用似乎是随机的数列，称为伪随机数列，例如RSA算法中素