11-门限密码学与Proactive+Recovery.pdf

门限密码学与Proactive Recovery 信息安全系统技术原理 林璟锵 本节内容 ? 讲述一些关于门限密码学的基本内容和概念 ? 本课程并非关于密码学的专门课程 ? 门限密码学应用的文献 ? 与其它技术的结合使用 Secret Sharing ? How to Share a Secret ? Adi Shamir ? Communications of the ACM, 1979, 22(11):612-613 Shamir秘密分享方案 ? 要求 ? 已知秘密s，共有n个参与者 ? 基于s，构造n份子秘密 ? 各参与者分别存储 ? 其中的任意f+1个参与者/子秘密，可恢复到s ? 任意f个参与者/子秘密，不能恢复到s ? 其中，f n ? 原理 ? 利用多项式曲线的秘密分享 顺便注意 ? How to Share a Secret ? Share，不同的时候表示不同的意思 ? Alice and Bob share a secret session key ? A和B都知道相同的session key、全部内容 ? Share a secret ? 只是知道secret的部分内容 ? 合起来，才知道secret的全部内容 Shamir秘密分享方案的基本原理 ? 对于f阶多项式曲线 f f-1 ? F(x) = afx + af-1x + … + a0 ? 得到曲线上的f+1个点坐标(x, y)，则可以恢复 出完整的曲线 ? 如果只得到f个点坐标(x, y) ，则可以做出无穷 多条f阶多项式曲线 ? 简单示例 ? 2阶曲线/抛物线 ? 给定3点坐标，可以确定1条抛物线 ? 如果只给定2点坐标，则可以做无数条抛物线 Shamir秘密分享方案的过程 ? 对于秘密s，构造曲线 f f-1 ? F(x) = afx + af-1x + … + s ? 将常数项a0设定为s ? 每一个参与者得到曲线上的不同坐标 ? 如(i, F(i))，1 = i = n ? 也可以使用公开的、互不相等的任意i ? 恢复时，从任意f+1个点坐标，可以 ? 恢复得到完整的曲线 ? 自然也可得到常数项a0=s 实际使用 ? 存在常数项的快速计算公式，如下图 ? LaGrange插值公式 ? 实际使用中，上述过程在素域Fp上进行 ? 计算是mod p等式 ? 子秘密数据定长 秘密分享方案——容错的机密性/可用性 ? 秘密分享方案实现 ? 容错的存储或者传输 ? 攻击者部分的参与者不能危及秘密s ? 也可以将信息分开传输，攻击部分信道，不会危及 秘密s ? 提供机密性 ? 容错的可用性 ? 丢失部分的子秘密，秘密s仍然可恢复 进一步，门限签名/解密 ? 秘密分享到门限计算 ? 在Shamir秘密分享方案中，多个参与者合作 时，“重现”秘密s ? 参与者/攻击者有了窃取s的机会 ? 通常而言，获得秘密数据s，是为了基于该 秘密数据s进行计算（如私钥签名/解密） ? 能否对s进行分享，在不“重新s”的前提下 ? 部分参与者可以合作，利用s进行计算（签名/ 解密） 简单的RSA门限签名方案 ? APSS: proactive secret sharing in asynchronous systems ? Lidong Zhou, Fred B. Schneider, and Robbert Van Renesse ? ACM Transaction on Information and System Security ? A Simplified Approach to Threshold and Proactive RSA ? T. Rabin ? Advances in Cryptology—Crypto’98, 89–104, 1998 RSA算法的私钥签名/解密 ? RSA算法 ? 私钥d，公钥(n, e) ? 加密 ? C = Pe mod n ? 解密 ? P = Cd mod n ? 签名 ? 类