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

ΓВ安全协议与标准[e-mail]2007,11ΓВ高级密码协议与应用•密码协议和数学难解问题↓•D-H、RSA、ECC↓•秘密分享、门限密码↓•比特承诺和网络棋牌游戏↓•安全多方计算↓•ECC↓•量子计算与密码学↓•侧信道攻击↓ΓВ协议•（算法）•协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。（1）协议中的每人都必须了解协议，并且预先知道所要完成的所有步骤。（2）协议中的每人都必须同意遵循它。（3）协议必须是无歧意的，每一步必须明确定义，并且不会引起误解。（4）协议必须是完整的，对每种可能的情况必须规定具体的动作。ΓВ密码学算法和协议的背景：某些数学难解问题•大数分解难题–IFP-Integerfactorizationproblem•离散对数难题–DLP-Discretelogarithmproblem–ECDLP•ΓВ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,2eNiscoprimetoφ(N),and0=CN.•开e次方–e=3，65537ΓВDiffie-Hellman密钥交换协议•DH76，Diffie-Hellman–基于DLP问题•步骤–选取大素数q和它的一个生成元g，这些参数公开–A选择随机数Xa，B选择随机数Xb–A计算Ya＝g^Xamodq，B计算Yb＝g^Xbmodq–交换Ya，Yb–A计算K＝Yb^Xamodq，B计算K'＝Ya^Xbmodq–事实上，K＝K'ΓВDiffie-Hellmanproblem•Givenanelementgandthevaluesofgxandgy,whatisthevalueofgxy?•ComputationalDiffie-Hellmanassumption–ItisanopenproblemtodeterminewhetherthediscretelogassumptionisequivalenttoCDH,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，xq–公钥y，y＝g^xmodp•签名，对报文M–产生随机数k–r＝(g^kmodp)modq–s=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/AES•ECDSA，基于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＋bmodp–A有自己的私钥Na，并产生公钥Pa＝Na×G–B有自己的私钥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•UsingtheECDSAforXMLDigitalSignaturesrfc4050-UsingtheECDSAforXMLDigitalSignatures.txtΓВECCSTD•PKCS#13proposal•ECCCryptographyTutorial–•ANSIX9.42($100)•ANSIX9.62/FIPS186-2•IEEEP1363:StandardSpecificationsForPublicKeyCryptography–•ECC-EllipticCurveCryptography––~dpj/elliptic.html–•ISO/IEC15946ΓВ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-Hellmankeyagreementallowinguptotwokeypairsfromeachparty–Menezes-Qu-Vanstonekeyagreement,whichrequirestwokeypairsfromeachparty–DSASignatures,withSHA-1andRIPEMD-160ashashfunctions–Nyberg-RueppelSignatureswithappendix,withSHA-1/RIPE-160ashashfunctions•FortheECfamily,thestandardwillmirrortheDLfamily;•FortheIFfamily,thestandard:–RSAencryptionwithOptimalAsymmetricEncryptionPadding(OAEP)–RSAsignaturewithappendixusingahashfunctionandANSIX9.31padding–Rabin-Williams(evenexponent)equivalentsoftheaboveRSAsignatures•ΓВP1363.1•IEEEP1363.1willspecifycryptographictechniquesbasedonhardproblemsoverlattices.–ItisalsointendedthatP1363.1provideasecond-generationframeworkforthedescriptionofcryptographictechniques,ascomparedtotheinitialframeworkprovidedin1363-2000an