安全协议与标准linfbsdu.edu.cn2007, 11 高级密码协议密码协议和数学难解问题D-H、RSA、秘密分享、门限密码比特承诺和网络棋牌游戏安全多方计算ECC量子计算与密码学侧信道攻击 协议（算法）协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。 （1）协议中的每人都必须了解协议，并且预先知道所要完成的所有步骤。（2）协议中的每人都必须同意遵循它。（3）协议必须是无歧意的，每一步必须明确定义，并且不会引起误解。（4）协议必须是完整的，对每种可能的情况必须规定具体的动作。 密码学算法和协议的背景：某些数学难解问题大数分解难题IFP - Integer factorization problem离散对数难题DLP - Discrete logarithm problemECDLP Diffie-Hellman密钥交换协议 DH76，Diffie-Hellman基于DLP问题步骤选取大素数q和它的一个生成元g，这些参数公开A选择随机数Xa，B选择随机数Xb A计算YagXa mod q，B计算YbgXb mod q 交换Ya，YbA计算KYbXa mod q，B计算KYaXb mod q 事实上，KK 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 problemRSA问题The RSA problem is to find integer P such that P e C (mod N), given 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 =b，无记号则ba 比较是否相等a. 比较两个大文件是否等同比如网络文件共享或同步，避免传输而比较两个大文件内容是否一致(BT/eMule)方法是比较两个文件的Hash值(如果不想泄露自己大文件的Hash值，归为b)b. 比较两个小文件(短消息)不能公布内容，也不能公布Hash值如果公布其Hash值，则容易受到枚举攻击参见 应用密码学6.2 保密的多方计算-协议#3”保密的多方计算约会服务（Secure Multiparty Computation Dating Service） ” 求和/平均值一群人怎样才能计算出他们的平均薪水，而又不让任何人知道其他人的薪水呢？Alice在她的薪水上加一个秘密随机数，然后把它送给BobBob把他的薪水加上，并把它送给Carol。Carol把她的薪水相加，并把它送给Dave。Dave把他的薪水相加，并把它送给Alice。Alice减去那个随机数以恢复每个人薪水之总和。Alice把这个结果除以人数(4)，并宣布结果。 to check if they love each otherAlice有保密输入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问题定义参与者Pi持有输入Xi计算函数(Y1,Y2,Yi,)=F(X1,X2,Xi,)参与者Pi得到输出YiPi不知道Xi/Yi之外的其他值假设各方输入时是诚实的。如果有可信第三方，则可以让它来帮助计算。但是安全多方计算考虑不用可信第三方时的情况，并考虑抵抗部分成员合谋试图知道其他人的输入。 所有密码协议都是多方安全计算的特例门限签名/解密、群密钥协商、身份鉴别、传输加密等。电子商务中的问题，比如拍卖、投票、电子现金等。在互联网上保护隐私方面。 对密文查询比如Gmail可以存放3G的邮件，Google公司显然企图从中搜集用户喜好和动向（他们叫数据挖掘），从而发送定向广告。为了挫败Gmail的企图以及其他的安全考虑，使用PGP处理邮件。问题是如何查询？查找某封信，只记得该信内容是讨论如何做“酸菜鱼”的。标签label 如何保护用户隐私Google可能会记录用户的查询关键字历史，从而服务于。如何保护自己的查询关键字不被记录。Private Information Retrieval (PIR)查询数据库，而不暴露查询的具体项另一种形式允许查询数据库，而不暴露数据库 CED：DLPAlice想让Bob帮忙计算e，而不泄露x和e x ge mod pA计算x x*gr mod pB求e x ge mod pA计算e = (e-r) mod p-1因为 x ge mod p x*gr ge mod p x g(e-r) mod p 一般思路借助别人的计算能力，计算自己的函数，而不泄漏某些相关的信息。自己计算F(X)X-F(X)-YX-F(X)-Y如果借助另外的帮助X-X-g(Xg(X) ) h(Yh(Y)-)-YY| | | |X X-F-F(X(X)-Y)-Y RSA提速利用外部计算能力加密C=Me解密M=CdM=1For each bit of D=dkd2d1if di=1 then M=M*C % NC=C2 % NEnd For 椭圆曲线* 寻找离散对数问题的背景群：从Zp*到ECElliptic Curvey2axybyx3cx2dxe其中a、b、c、d、e是满足某个简单条件的实数另有O点被定义为无穷点/零点点加法，PQR定义为过P、Q和椭圆曲线相交的第三点的X轴对称点R EC图示P+Q=RO点累加P+P=2PP+P+P=3PP+P=kP 素域上的EC在有限域Zp上的简化ECy2x3axb mod p 其中4a327b2 mod p 0这是一个离散点的集合* 直观解释把开放二维平面折叠到pp的方框内，并且只考虑整数点 y2x318x15 mod 23 ECDLP在D-H密钥交换中(群Zp*中)使用了ygx mod p中x的计算困难性在EC点加法群中QkP中的k计算也是极其困难的(kP表示k个P相加：P + + P) ECDSADSA/DSS，基于DLP问题的签名算法/标准Lucifer/DES，Rijndael/AESECDSA，基于ECDLP问题的DSA算法 P1363IEEE P1363 is an IEEE standardization project for public-key cryptography. It includes specifications for:* Traditional public-key cryptography (IEEE Std 1363-2000 and 1363a-2004)* Lattice-based public-key cryptography (P1363.1)* Password-based public-key cryptography (P1363.2)* Identity-based public-key cryptography using pairings (P1363.3) 1363/athe underlying computationally difficult problem: discrete logarithm in the group of remainders modulo a prime (DL) discrete logarithm in the group of points on an elliptic curve over a finite field (EC) integer factorization (IF) For the DL family, the standard will include: Diffie-Hellman key agreement allowing up to two key pairs from each party Menezes-Qu-Vanstone key agreement, which requires two key pairs from each party DSA Signatures, with SHA-1 and RIPEMD-160 as hash functions Nyberg-Rueppel Signatures with appendix, with SHA-1/ RIPE-160 as hash functions For the EC family, the standard will mirror the DL family; For the IF family, the standard: RSA encryption with Optimal Asymmetric Encryption Padding (OAEP) RSA signature with appendix using a hash function and ANSI X9.31 padding Rabin-Williams (even exponent) equivalents of the above RSA signatures P1363.1IEEE P1363.1 will specify cryptographic techniques based on hard problems over lattices. It is also intended that P1363.1 provide a second-generation framework for the description of cryptographic techniques, as compared to the initial framework provided in 1363-2000 and draft P1363a. It is not the purpose of this project to mandate any particular set of public-key techniques or security requirements (including key sizes) for this or any family. Rather, the purpose is to provide:(1)a reference for specification of a variety of techniques from which applications may select, (2)the relevant number-theoretic background, and(3)extensive discussion of security and implementation considerations so that a solution provider can choose appropriate security requirements for itself. P1363.2Memorized secrets are an important factor in human authentication. P1363.2 will specify public-key cryptographic techniques specifically designed to securely perform password-based authentication and key exchange. These techniques provide a way to authenticate people and distribute high-quality cryptographic keys for people, while preventing off-line brute-force attacks associated with passwords. Rather, the purpose is to provide: (1) a reference for specification of a variety of techniques from which applications may select,(2) the appropriate theoretic background, and(3) extensive discussion of security and implementation considerations so that a solution provider can choose appropriate security requirements. P1363.3IEEE P1363.3 will specify Identity-Based Cryptographic techniques based on Pairings. These offer advantages over classic public key techniques specified in IEEE 1363. Examples are the lack of a requirement to exchange or look up public keys of a recipient and the simplified use of short-lived keys. It is not the purpose of this project to mandate any particular set of identity-based public-key techniques, or particular attributes of public-key techniques such as key sizes. Rather, the purpose is to provide a reference for specifications of a variety of techniques from which applications may select. CerticomCerticom Corp. is a cryptography company founded in 1985 by Gordon Agnew.The Certicom intellectual property portfolio includes over 350 patents and patents pending worldwide that cover key aspects of elliptic curve cryptography (ECC): software optimizations, efficient hardware implementations, methods to enhance the security, and various cryptographic protocols.The National Security Agency (NSA) has licensed 26 of Certicoms ECC patents as a way of clearing the way for the implementation of elliptic curves to protect US and allied government information.whuecc Lattice-based phDLattice-based 量子技术量子量子比特(qubit)量子通信量子密码学量子计算机1994年，彼得秀尔（Peter Shor）提出量子质因子分解算法1994年，贝尔实验室的专家彼得修尔（Peter Shor）证明量子电脑能做出对数运算 纠缠 Quantum entanglement光子有一奇异的特性“混杂”特性，即从同一个光 源分出的光束具有相同的物理性质，尤如“双胞胎”一样。1982年，法国奥赛光学研究所的科学家就在实验室实现了光子“混杂”，1997年，他们又使用光纤再次完成了这一实验。 瑞士研究人员在近期也进行了类似的实验，他们将聚集在一个非线性晶体上的激光束分成两束，第一束被导向一个实验室，另一束则通过一个2公里长的光纤、被导向另一个实验室，两个实验室相距55米。研究人员在一个实验室内将第三束光与“双胞胎”光束中的一束相互作用，他们观察到在另一个实验室的另一束光也发生着这种变化。这一实验证实了光子的“混杂”特性：一个唯一、相同的物体同时处于两个不同的地方，使得在一个地方对光子的操作可以反射到处于另一个地方的“双胞胎”光子上并表现出来。实验的成功，使光子“混杂”特性从实验室研究走向实际应用迈出了新的一步，使量子远距离输运变成可能。 测不准海森堡测不准原理在一个量子力学系统中，一个粒子的位置和它的动量不可被同时确定。（测量手段必然引入干扰） 量子密钥分发协议BB84B92 一次一密(one-time pad) vs. 量子计算按照信息论观点，one-time pad能抵抗量子计算 TODO：量子计算量子计算机For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time.量子密码学“海森堡测不准”“单量子不可复制”实验室阶段 侧信道攻击TODO Q & A