安全协议与标准12-高级密码协议与应用

1、 安全协议与标准2007, 11 高级密码协议与应用 密码协议和数学难解问题 D-H、RSA、ECC 秘密分享、门限密码 比特承诺和网络棋牌游戏 安全多方计算 ECC 量子计算与密码学 侧信道攻击 协议 （算法） 协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。 （1）协议中的每人都必须了解协议，并且预先知道所要完成的所有步骤。（2）协议中的每人都必须同意遵循它。（3）协议必须是无歧意的，每一步必须明确定义，并且不会引起误解。（4）协议必须是完整的，对每种可能的情况必须规定具体的动作。 密码学算法和协议的背景：某些数学难解问题 大数分解难题 IFP - Integer fac

2、torization problem 离散对数难题 DLP - Discrete logarithm problem ECDLP RSA算法 找素数，选取两个512bit的随机素数p,q 计算模n pq，Euler函数(n) =(p-1)(q-1) 找ed1 mod (n) 选取数e，用扩展Euclid算法求数d 发布公钥(e,n)，保密私钥(d, n) 加密明文分组m(视为整数须小于n)c=me mod n 解密m=cd mod n RSA problem RSA问题The RSA problem is to find integer P such that P e C (mod N), g

3、iven integers N, e and C such that N is the product of two large primes, 2 e N is coprime to (N), and 0 = C N. 开e次方 e=3，65537 Diffie-Hellman密钥交换协议 DH76，Diffie-Hellman 基于DLP问题 步骤 选取大素数q和它的一个生成元g，这些参数公开 A选择随机数Xa，B选择随机数Xb A计算YagXa mod q，B计算YbgXb mod q 交换Ya，Yb A计算KYbXa mod q，B计算KYaXb mod q 事实上，KK Diffie

4、-Hellman problem Given an element g and the values of gx and gy, what is the value of gxy ? Computational Diffie-Hellman assumption It is an open problem to determine whether the discrete log assumption is equivalent to CDH, though in certain special cases this can be shown to be the case. Decisiona

5、l Diffie-Hellman assumption (ga, gb, gab) ? (ga, gb, gc) ElGamal加密 准备 素数p，Zp*中本原元g，公开参数 私钥a，公钥b=ga mod p 加密 对明文1=m=p-1，选随机数k 密文(c1, c2)c1=gk mod p, c2=mbk mod p 解密 mc2 (c1a)-1mbk (gk)a)-1 m(ga)k (g-ka) m mod p ElGamal签名方案 Zp满足离散对数问题难解，是生成元设P Zp* ，A Zp*Zp-1 K (p, a,), =a (mod p) 私钥是a 签名时，取秘密随机数kZp-1*

6、，定义sig(x,k) = (,), (k mod p, (x-a)k-1 mod (p-1) 验证 ver(x, (,)： ? ?x mod p 验证正确性证明 如果 (x,)是真实签名aka+k而 (x-a) k-1 mod (p)即 ax-k mod (p)故 n(p)+x-k+k n(p)+x n(p)x x mod p 其实就是签名时从 kax解出来得 DSS/DSA 准备 素数p，约512比特； 素数q，约160比特，要求是p-1的因子 选择gh(p-1/q) mod p 密钥 用户私钥x，x=b，无记号则ba 比较是否相等 a. 比较两个大文件是否等同 比如网络文件共享或同步，避

7、免传输而比较两个大文件内容是否一致(BT/eMule) 方法是比较两个文件的Hash值 (如果不想泄露自己大文件的Hash值，归为b) b. 比较两个小文件(短消息) 不能公布内容，也不能公布Hash值 如果公布其Hash值，则容易受到枚举攻击 参见 应用密码学6.2 保密的多方计算-协议#3”保密的多方计算约会服务（Secure Multiparty Computation Dating Service） ” 求和/平均值 一群人怎样才能计算出他们的平均薪水，而又不让任何人知道其他人的薪水呢？ Alice在她的薪水上加一个秘密随机数，然后把它送给Bob Bob把他的薪水加上，并把它送给Car

8、ol。 Carol把她的薪水相加，并把它送给Dave。 Dave把他的薪水相加，并把它送给Alice。 Alice减去那个随机数以恢复每个人薪水之总和。 Alice把这个结果除以人数(4)，并宣布结果。 to check if they love each other Alice有保密输入a，Bob有保密输入b:a := 1 若A喜欢B / 否则0b := 1 若B喜欢A / 否则0 目标(在尽可能保护隐私的前提下)计算f(a,b) := a b 保护隐私的效果如果f(a,b)=1，则没有隐私如果f(a,b)=0，则如果对方是0则其不知道自己是否是1，即保护了自己的隐私。 SMPC问题定义 参

9、与者Pi持有输入Xi计算函数(Y1,Y2,Yi,)=F(X1,X2,Xi,)参与者Pi得到输出Yi Pi不知道Xi/Yi之外的其他值 假设各方输入时是诚实的。 如果有可信第三方，则可以让它来帮助计算。 但是安全多方计算考虑不用可信第三方时的情况，并考虑抵抗部分成员合谋试图知道其他人的输入。 所有密码协议都是多方安全计算的特例门限签名/解密、群密钥协商、身份鉴别、传输加密等。电子商务中的问题，比如拍卖、投票、电子现金等。在互联网上保护隐私方面。 对密文查询 比如Gmail可以存放3G的邮件，Google公司显然企图从中搜集用户喜好和动向（他们叫数据挖掘），从而发送定向广告。为了挫败Gmail的企

10、图以及其他的安全考虑，使用PGP处理邮件。 问题是如何查询？ 查找某封信，只记得该信内容是讨论如何做“酸菜鱼”的。 标签label 如何保护用户隐私 Google可能会记录用户的查询关键字历史，从而服务于。 如何保护自己的查询关键字不被记录。 Private Information Retrieval (PIR) 查询数据库，而不暴露查询的具体项 另一种形式 允许查询数据库，而不暴露数据库 CED：DLP Alice想让Bob帮忙计算e，而不泄露x和e x ge mod p A计算x x*gr mod p B求e x ge mod p A计算e = (e-r) mod p-1 因为 x ge

11、mod p x*gr ge mod p x g(e-r) mod p 一般思路 借助别人的计算能力，计算自己的函数，而不泄漏某些相关的信息。 自己计算F(X)X-F(X)-YX-F(X)-Y 如果借助另外的帮助X-g(X)X-g(X) h(Y h(Y)-Y)-Y| | | |X X-F-F(X(X)-Y)-Y RSA提速 利用外部计算能力加密C=Me 解密M=Cd M=1For each bit of D=dkd2d1if di=1 then M=M*C % NC=C2 % NEnd For 量子技术 量子 量子比特(qubit) 量子通信 量子密码学 量子计算机 1994年，彼得秀尔（Pet

12、er Shor）提出量子质因子分解算法 1994年，贝尔实验室的专家彼得修尔（Peter Shor）证明量子电脑能做出对数运算 纠缠 Quantum entanglement 光子有一奇异的特性“混杂”特性，即从同一个光 源分出的光束具有相同的物理性质，尤如“双胞胎”一样。 1982年，法国奥赛光学研究所的科学家就在实验室实现了光子“混杂”，1997年，他们又使用光纤再次完成了这一实验。 瑞士研究人员在近期也进行了类似的实验，他们将聚集在一个非线性晶体上的激光束分成两束，第一束被导向一个实验室，另一束则通过一个2公里长的光纤、被导向另一个实验室，两个实验室相距55米。研究人员在一个实验室内将第三束光与“双胞胎”光束中的一束相互作用，他们观察到在另一个实验室的另一束光也发生着这种变化。这一实验证实了光子的“混杂”特性：一个唯一、相同的物体同时处于两个不同的地方，使得在一个地方对光子的操作可以反射到处于另一个地方的“双胞胎”光子上并表现出来。实验的成功，使光子“混杂”特性从实验室研究走向实际应用迈出了新的一步，使量子远距离输运变成可能。 测不准 海森堡测不准原理 在一个量子力学系统中，一个粒子的位置和它的动量不可被同时确定。（测量手段必然引入干扰） 量子密钥分发协议 BB84 B92 一次一密(one-time pad) vs. 量子计算 按照