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

安全协议与标准 linfb 2007 11 高级密码协议与应用 密码协议和数学难解问题 D H RSA ECC 秘密分享 门限密码 比特承诺和网络棋牌游戏 安全多方计算 ECC 量子计算与密码学 侧信道攻击 协议 算法 协议是一系列步骤 它包括两方或多方 设计它的目的是要完成一项任务 1 协议中的每人都必须了解协议 并且预先知道所要完成的所有步骤 2 协议中的每人都必须同意遵循它 3 协议必须是无歧意的 每一步必须明确定义 并且不会引起误解 4 协议必须是完整的 对每种可能的情况必须规定具体的动作 密码学算法和协议的背景 某些数学难解问题 大数分解难题IFP Integerfactorizationproblem离散对数难题DLP DiscretelogarithmproblemECDLP RSA算法 找素数 选取两个512bit的随机素数p q计算模n pq Euler函数 n p 1 q 1 找ed 1mod n 选取数e 用扩展Euclid算法求数d发布公钥 e n 保密私钥 d n 加密明文分组m 视为整数须小于n c memodn解密m cdmodn RSAproblem RSA问题TheRSAproblemistofindintegerPsuchthatPe C modN givenintegersN eandCsuchthatNistheproductoftwolargeprimes 2 e Niscoprimeto N and0 C N 开e次方e 3 65537 Diffie Hellman密钥交换协议 DH76 Diffie Hellman基于DLP问题步骤选取大素数q和它的一个生成元g 这些参数公开A选择随机数Xa B选择随机数XbA计算Ya g Xamodq B计算Yb g Xbmodq交换Ya YbA计算K Yb Xamodq B计算K Ya Xbmodq事实上 K K Diffie Hellmanproblem Givenanelementgandthevaluesofgxandgy whatisthevalueofgxy ComputationalDiffie HellmanassumptionItisanopenproblemtodeterminewhetherthediscretelogassumptionisequivalenttoCDH thoughincertainspecialcasesthiscanbeshowntobethecase DecisionalDiffie Hellmanassumption ga gb gab ga gb gc ElGamal加密 准备素数p Zp 中本原元g 公开参数私钥a 公钥b gamodp加密对明文1 m p 1 选随机数k密文 c1 c2 c1 gkmodp c2 mbkmodp解密m c2 c1a 1 mbk gk a 1 m ga k g ka mmodp ElGamal签名方案 Zp满足离散对数问题难解 是生成元设P Zp A Zp Zp 1K p a a modp 私钥是a签名时 取秘密随机数k Zp 1 定义sig x k kmodp x a k 1mod p 1 验证ver x xmodp 验证正确性证明 如果 x 是真实签名 a k a k 而 x a k 1mod p 即a x k mod p 故 n p x k k n p x n p x xmodp其实 就是签名时从k a x解出来得 DSS DSA 准备素数p 约512 比特 素数q 约160比特 要求是p 1的因子选择g h p 1 q modp密钥用户私钥x x q公钥y y g xmodp签名 对报文M产生随机数kr g kmodp modqs k 1 H M xr modq r s 即是签名 连同明文的M验证 测试是否v r 其中v g u1 y u2modpmodqu1 H M s 1modqu2 r s 1modq 椭圆曲线EllipticCurve 背景RSA安全依赖因子分解的难度 为了增加安全性就得增加位数 从而导致计算速度变慢 Zp 上的DLP问题有亚指数复杂度的算法 至今未发现解决ECDLP的普适性亚指数算法ECC可以用较小的密钥长度达到较高的计算难度 即安全性循环群 从Zp 到EC点加群 椭圆曲线EC EllipticCurvey2 axy by x3 cx2 dx e其中a b c d e是满足某个简单条件的实数Anyellipticcurvecanbewrittenasaplanealgebraiccurvedefinedbyanequationoftheform y2 x3 ax b EC P Q R EC上点加法 定义为无穷点 零点为O点点加法P Q R定义为过P Q和椭圆曲线相交的第三点的X轴对称点R 素域上的EC 在有限域Zp上的简化ECy2 x3 ax bmodp其中4a3 27b2modp 0 这是一个离散点的集合 举例y2 x3 18x 15mod23y2 x3 17x 15mod23 EC 1 DLP ECDLP 在D H密钥交换中 群Zp 中 使用了y gxmodp中x的计算困难性在EC点加法群中Q kP中的k计算也是极其困难的 kP表示k个P相加 P P EC上的离散对数问题 ECDLP Q k P中的k计算也是极其困难的k P表示k个P相加 P P P在DH密钥交换中使用了y gxmodp中x的计算困难性同样在ECC中将使用Q kP中计算k的困难性有两个应用密钥交换加密解密 DSA ECDSA DSA DSS 基于DLP问题的签名算法 标准Lucifer DES Rijndael AESECDSA 基于ECDLP问题的DSA算法 使用EC的密钥交换 D H 步骤y2 x3 ax bmodp选择素数p 得约160 比特 和参数a b选择一个生成点G x1 y1 p a b和点G是公开的A 选取秘密的数Na 计算Pa Na GB 选取秘密的数Nb 计算Pb Nb G交换Pa PbA 计算K Na Pb Na Nb GB 计算K Nb Pa Nb Na G分析攻击者得求Na和Nb 就是P G中的 用EC的加解密 准备曲线参数p a b G y2 x3 ax bmodpA有自己的私钥Na 并产生公钥Pa Na GB有自己的私钥Nb 并产生公钥Pb Nb G加密 A要给B发送消息 对明文m的编码点Pm 选择随机数k 密文C C1 C2 k G Pm k Pb 解密 编码点Pm C2 Nb C1 因为 Pm k Pb Nb k G Pm k Nb G Nb k G Pm 用EC的加解密 原理先是通过k Pb掩盖Pm 即m 又通过k G掩盖k知道陷门Nb则可以轻松恢复之分析攻击者解C1 k G中的k困难性 关于速度 速度在密钥长度相等的情况下 RSA和ECC的速度相当 但是在相同的安全强度要求下 ECC可以使用较少的位数就可以 故ECC较好适合嵌入式设备中 ECCvs RSA RFC4050 UsingtheECDSAforXMLDigitalSignatures ECCSTD PKCS 13proposalECCCryptographyTutorial P1363 IEEEP1363isanIEEEstandardizationprojectforpublic keycryptography Itincludesspecificationsfor Traditionalpublic keycryptography IEEEStd1363 2000and1363a 2004 Lattice basedpublic keycryptography P1363 1 Password basedpublic keycryptography P1363 2 Identity basedpublic keycryptographyusingpairings P1363 3 1363 a theunderlyingcomputationallydifficultproblem discretelogarithminthegroupofremaindersmoduloaprime DL discretelogarithminthegroupofpointsonanellipticcurveoverafinitefield EC integerfactorization IF FortheDLfamily thestandardwillinclude Diffie HellmankeyagreementallowinguptotwokeypairsfromeachpartyMenezes Qu Vanstonekeyagreement whichrequirestwokeypairsfromeachpartyDSASignatures withSHA 1andRIPEMD 160ashashfunctionsNyberg RueppelSignatureswithappendix withSHA 1 RIPE 160ashashfunctionsFortheECfamily thestandardwillmirrortheDLfamily FortheIFfamily thestandard RSAencryptionwithOptimalAsymmetricEncryptionPadding OAEP RSAsignaturewithappendixusingahashfunctionandANSIX9 31paddingRabin Williams evenexponent equivalentsoftheaboveRSAsignatures P1363 1 IEEEP1363 1willspecifycryptographictechniquesbasedonhardproblemsoverlattices ItisalsointendedthatP1363 1provideasecond generationframeworkforthedescriptionofcryptographictechniques ascomparedtotheinitialframeworkprovidedin1363 2000anddraftP1363a Itisnotthepurposeofthisprojecttomandateanyparticularsetofpublic keytechniquesorsecurityrequirements includingkeysizes forthisoranyfamily Rather thepurposeistoprovide areferenceforspecificationofavarietyoftechniquesfromwhichapplicationsmayselect therelevantnumber theoreticbackground andextensivediscussionofsecurityandimplementationconsiderationssothatasolutionprovidercanchooseappropriatesecurityrequirementsforitself P1363 2 Memorizedsecretsareanimportantfactorinhumanauthentication P1363 2willspecifypublic keycryptographictechniquesspecificallydesignedtosecurelyperformpassword basedauthenticationandkeyexchange Thesetechniquesprovideawaytoauthenticatepeopleanddistributehigh qualitycryptographickeysforpeople whilepreventingoff linebrute forceattacksassociatedwithpasswords Rather thepurposeistoprovide 1 areferenceforspecificationofavarietyoftechniquesfromwhichapplicationsmayselect 2 theappropriatetheoreticbackground and 3 extensivediscussionofsecurityandimplementationconsiderationssothatasolutionprovidercanchooseappropriatesecurityrequirements P1363 3 IEEEP1363 3willspecifyIdentity BasedCryptographictechniquesbasedonPairings TheseofferadvantagesoverclassicpublickeytechniquesspecifiedinIEEE1363 Examplesarethelackofarequirementtoexchangeorlookuppublickeysofarecipientandthesimplifieduseofshort livedkeys Itisnotthepurposeofthisprojecttomandateanyparticularsetofidentity basedpublic keytechniques orparticularattributesofpublic keytechniquessuchaskeysizes Rather thepurposeistoprovideareferenceforspecificationsofavarietyoftechniquesfromwhichapplicationsmayselect Certicom CerticomCorp isacryptographycompanyfoundedin1985byGordonAgnew TheCerticomintellectualpropertyportfolioincludesover350patentsandpatentspendingworldwidethatcoverkeyaspectsofellipticcurvecryptography ECC softwareoptimizations efficienthardwareimplementations methodstoenhancethesecurity andvariouscryptographicprotocols TheNationalSecurityAgency NSA haslicensed26ofCerticom sECCpatentsasawayofclearingthewayfortheimplementationofellipticcurvestoprotectUSandalliedgovernmentinformation whuecc Lattice based 秘密 密钥 分割 秘密分割 多人共同持有秘密 0 秘密K需要t个人联合打开1 产生随机数R1 R2 Rt 1 Rt K R1 R2 Rt 12 t个人分别持有Ri3 恢复秘密K R1 R2 Rt 1 Rt 秘密的门限共享 m n 门限方案秘密的恢复需要n个人中的m个参与即可Lagrange插值方案以 3 n 门限方案为例 取多项式f x ax2 bx K a b是随机数 K是秘密对于成员i 1 n 给予f xi axi2 bxi K 一般取xi i恢复秘密时只需n中的三个 x y 点即重构f x 门限密码学 ThresholdCryptography 一组人用门限方法共同持有一个私钥 要对某个消息签名 1 可以恢复私钥 然后签名 这样私钥就公开暴露在组人面前 以后就不能用了 2 不恢复私钥而签名 这样私钥可以继续使用 时间戳服务 在很多情况中 人们需要证明某个文件在某个时期存在 版权或专利争端即是谁有产生争议的工作的最早的副本 谁就将赢得官司 对于纸上的文件 公证人可以对文件签名 律师可以保护副本 如果产生了争端 公证人或律师可以证明某封信产生于某个时间 在数字世界中 事情要复杂得多 没有办法检查窜改签名的数字文件 他们可以无止境地复制和修改而无人发现 在计算机文件上改变日期标记是轻而易举的事 没有人在看到数字文件后说 是的 这个文件是在1952年12月4日以前创建的 AppliedCryptography SecondEdition权威机构 CA 公证处 inPGPfmt 实验 时间戳服务 联合信任 公司的时间戳服务 盲签名BlindSignature A持有消息m B持有私钥d 计算s mdmodn 但是不泄露各自的输入 A让B签署经随机盲化掩饰后的消息m m remodnB计算s m dmodnA从而仍可得到B对m的签名s s reverse r m re d r 1 md red 1 mdmodn 信息隐藏学 隐写术Steganography 演示软件DstegoGoogle Dstego 能把秘密藏到声音 图像 甚至可执行文件中阈下信道Subliminalchannel数字水印Digitalwatermarking 网络游戏 棋类游戏很容易网络化牌类游戏则需要处理额外问题如何洗牌 发牌 一个简单的操作 掷色子更简单的 抛硬币 抛硬币 Alice和Bob想抛掷一个公平的硬币 但又没有实际的物理硬币可抛 Alice提出一个用思维来抛掷公平硬币的简单方法 首先 你想一个随机比特 然后我再想一个随机比特 我们将这两个比特进行异或 Alice建议道 好的思路 首先 Bob确定一个比特 但这次他不立即宣布 只是将它写在纸上 并装入信封中 接下来 Alice公布她选的比特 最后 Alice和Bob从信封中取出Bob的比特并计算随机比特 只要至少一方诚实地执行协议 这个比特的确是真正随机的 信封 加密这种技术叫比特承诺 BitCommitment 投币入井协议 FlippingCoinsintoaWell 金簪子掉进井里 采用单向函数的抛币协议 如果Alice和Bob对使用一个单向函数达成一致意见 协议非常简单 1 Alice选择一个随机数x 她计算y f x 这里f x 是单向函数 2 Alice将y送给Bob 3 Bob猜测x是偶数或奇数 并将猜测结果发给Alice 4 如果Bob的猜测正确 抛币结果为正面 如果Bob的猜测错误 则抛币的结果为反面 Alice公布此次抛币的结果 并将x发送给 ob 5 Bob确信y f x 三方智力扑克 Alice Bob和Carol都产生一个公钥 私钥密钥对 加密可交换性质 即mk1 k2 mk2 k1Alice产生52个消息 可验证的唯一的随机串 每个代表一副牌中的一张牌 Alice用她的公钥加密所有这些消息 并将它们发送给Bob Bob 由于不能阅读任何消息 他随机地选择5张牌 他用他的公钥加密 并把它们回送给Alice Bob将余下的47张牌送给Carol Carol 由于不能阅读任何消息 也随机选5个消息 她用她的公钥加密 并把它们送给Alice Alice也不能阅读回送给她的消息 她用她的私钥对它们解密 然后送给Bob或Carol 依据来自谁而定 Bob和Carol用他们的密钥解密并获得他们的牌 Carol从余下的42张牌中随机取5张 把它们发送给Alice Alice用她的私钥解密消息获得她的牌 在游戏结束时 Alice Bob和Carol都出示他们的牌以及他们的密钥 以便每人都确信没有人作弊 百万富翁问题 百万富翁问题两个百万富翁想知道谁更富有 但不想泄露有关财富多少的任何信息 如果不借助于第三方 他们自己能做到吗 Twomillionaireswishtoknowwhoisricher however theydonotwanttofindoutinadvertentlyanyadditionalinformationabouteachother swealth Howcantheycarryoutsuchaconversation Yao82 网络游戏问题 从 Gold87 演绎 军棋 暗棋 普通军棋需要第三人为裁判网络军棋使用服务器 可信第三方 为裁判 能否避免使用第三方 专利 自裁判军棋 自裁判军棋此军棋可实现不用裁判即可下暗棋的功能 能达到与网络军棋相同的效果 年龄比较 概念假设A B年龄a b 且无意于撒谎准备适当多的 比如100个 信封顺序排好B回避 A把前a个信封中做记号A回避 B把第b个信封取出 把其余信封收起来A和B共同打开此信封 有记号则说明a b 无记号则b a 比较是否相等 a 比较两个大文件是否等同比如网络文件共享或同步 避免传输而比较两个大文件内容是否一致 BT eMule 方法是比较两个文件的Hash值 如果不想泄露自己大文件的Hash值 归为b b 比较两个小文件 短消息 不能公布内容 也不能公布Hash值如果公布其Hash值 则容易受到枚举攻击参见 应用密码学 6 2保密的多方计算 协议 3 保密的多方计算约会服务 SecureMultipartyComputationDatingService 求和 平均值 一群人怎样才能计算出他们的平均薪水 而又不让任何人知道其他人的薪水呢 Alice在她的薪水上加一个秘密随机数 然后把它送给BobBob把他的薪水加上 并把它送给Carol Carol把她的薪水相加 并把它送给Dave Dave把他的薪水相加 并把它送给Alice Alice减去那个随机数以恢复每个人薪水之总和 Alice把这个结果除以人数 4 并宣布结果 tocheckiftheyloveeachother 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问题定义 参与者Pi持有输入Xi计算函数 Y1 Y2 Yi F X1 X2 Xi 参与者Pi得到输出YiPi不知道Xi Yi之外的其他值假设各方输入时是诚实的 如果有可信第三方 则可以让它来帮助计算 但是安全多方计算考虑不用可信第三方时的情况 并考虑抵抗部分成员合谋试图知道其他人的输入 所有密码协议都是多方安全计算的特例 门限签名 解密 群密钥协商 身份鉴别 传输加密等 电子商务中的问题 比如拍卖 投票 电子现金等 在互联网上保护隐私方面 对密文查询 比如Gmail可以存放3G的邮件 Google公司显然企图从中搜集用户喜好和动向 他们叫数据挖掘 从而发送定向广告 为了挫败Gmail的企图以及其他的安全考虑 使用PGP处理邮件 问题是如何查询 查找某封信 只记得该信内容是讨论如何做 酸菜鱼 的 标签label 如何保护用户隐私 Google可能会记录用户的查询关键字历史 从而服务于 如何保护自己的查询关键字不被记录 PrivateInformationRetrieval PIR 查询数据库 而不暴露查询的具