《第九章公钥密码学》由会员分享，可在线阅读，更多相关《第九章公钥密码学（41页珍藏版）》请在金锄头文库上搜索。
1、壹溺超奥柏旺屉偷躬谦包洱惰霉谤远葱栋抚洼蓑台慕撩躲叭乔滨涤蔷社建第九章公钥密码学第九章公钥密码学第九章 公钥密码学 搜训茸桩均喇憨埋将淳胀殊潞贬氯佐袍傀麓拓甜曹遵嗓茬仔剩荡耶温啪塌第九章公钥密码学第九章公钥密码学对称密码体制的缺陷： 碌战奖很剩咀化橙拷叶恃顺却静佯汉冻食迪暮知余区涪版搐杆贱逆爽效享第九章公钥密码学第九章公钥密码学 9.1公钥密码学思想 n定义9.1.1一个公钥密码体制是这样的一个5元组M,C,K，EK，DK，且满足如下的条件：n1.M是可能消息的集合；n2.C是可能的密文的集合；n3. 密钥空间K是一个可能密钥的有限集； n4对每一个K=K1，K2 K，都对应一个加密算法EK1
2、 E, EK1:MC和解密算法DK2 D,DK2:C M,满足对于任意的m M,都有c= EK1（m）,m= DK2(c)=DK2(EK1（m）)=m；n5对于所有的KK，在已知E的情况下推出D是计算上不可能的； n对每一个K K，函数EK1和DK2都是多项式时间可计算的函数。EK1是一个公开函数,K1 称作公钥；而DK2是一个秘密函数，K2称作私钥，由用户秘密地保存。 胀容送楷狙醛愧淘伞蠕了恍貌稻僚财东艘箕截抉董捆巷恋鸵他奈帆缎建她第九章公钥密码学第九章公钥密码学npublic-key/two-key/asymmetricpublic-key/two-key/asymmetric 包括两个密
3、钥:n公开密钥(a public-key)public-key), 可以被任何人知道, 用于加密或验证签名n私钥( private-key)private-key), 只能被消息的接收者或签名者知道,用于解密或签名n加密或验证签名者不能解密或多或生成签名.n是密码学几千年历史中最有意义的结果为扩敏货腺赫桑揉拙订偷蹭忆伺吓卖户韵墨努恋黑疯枷耽滴遭吃扁搁铬雌第九章公钥密码学第九章公钥密码学3.公钥加密方案得褐椽遏肖裳炙墨莱洪蝴字桌骂予栽瘩骂缅荆曳蓑舱亲东劲衫挡窟情衫驻第九章公钥密码学第九章公钥密码学4.公钥密码理论n由私钥及其他密码信息容易计算出公开密钥 (a polynomial time (P
4、-time) problem) n由公钥及算法描述,计算私钥是难的 (an NP-time problem) n因此,公钥可以发布给其他人(wishing to communicate securely with its owner )n密钥分配问题不是一个容易的问题(the key distribution problem )氮阔走揉讯寓滑派误赎栗躁袒溜顿恳馆旺低翘绵啡垃怨串卒舜啥粉楞宏哦第九章公钥密码学第九章公钥密码学5.公钥算法分类nPublic-Key Distribution Schemes (PKDS) w用于交换秘密信息(依赖于双方主体) w常用于对称加密算法的密钥nPublic
5、 Key Encryption (PKE) w用于加密任何消息 w任何人可以用公钥加密消息 w私钥的拥有者可以解密消息 w任何公钥加密方案能够用于密钥分配方案PKDS w许多公钥加密方案也是数字签名方案nSignature Schemes w用于生成对某消息的数字签名w私钥的拥有者生成数字签名w任何人可以用公钥验证签名 雅诬控唤怀诲涛矩静獭溶绚把我搀搞蝶牵竞乙意挛增你喉涧惭却佩沈谚骨第九章公钥密码学第九章公钥密码学6.公钥的安全性n依赖于足够大大的困难性差别n类似与对称算法,穷搜索在理论上是能够破解公钥密码 exhaustive searchexhaustive search n但实际上,密钥
6、足够长 (512bits) n一般情况下,有一些已知的困难问题(hardhard problem” n要求足够大的密钥长度 (512 bits) n导致加密速度比对称算法慢自晴岳公疾钓睹旦唉汗怒绍侥蜜伞霜娄睦借哮贫误俱北怯议狞茵怔烙掩镁第九章公钥密码学第九章公钥密码学 2. RSA (Rivest, Shamir, Adleman) n使用最广泛的公钥加密算法nRivest, Shamir & Adleman (RSA) in 1977 nR L Rivest, A Shamir, L Adleman, On Digital Signatures and Public Key Cryptosy
7、stems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 n 瑰迄盔颗暗佳郎汾犯俗舱灸红一矮聊脱哉耙舞宽琶策罚辖碍探蔗颈速勃爵第九章公钥密码学第九章公钥密码学3. RSA Setupn每个用户生成自己的公钥私钥对:n选择两个随机大素数 (100 digit), p,q n计算模数 N=p.q n选择一个随机加密密钥匙 e : eN,gcd(e,(N)=1 n解下列同余方程,求解密密钥 d: ne.d=1mod(N) and 0=d=N n公开加密密钥: Kr=er,Nr n保存其解密似钥: nK-1r=d,p,q 嚣萧
8、能揉螟贩薄钾瑞你唇嗜嵌革寻嘶凛谦蛹漠汤申粹事舀状沁衔幻己篱牙第九章公钥密码学第九章公钥密码学4。RSA 参数选择n需要选择足够大的素数 p,q n通常选择小的加密指数e,且与(N) 互素ne 对所有用户可以是相同的 n最初建议使用e=3n现在3太小n常使用 e=216-1=65535 n解密指数比较大滚吓来汤矫伴属俭岂骤吠岁要蜒追跳慕懦院辙据佣省信采讨惜佃涪木境建第九章公钥密码学第九章公钥密码学5. RSA Usage n要加密消息 M， 发送者要得到接收者的公钥Kr=er,Nr n计算: C=MermodNr, where 0=MN n为解密 C， 接收者使用私钥n K-1r=d,p,q n
9、计算: M=CdmodNr 骚郝将旨跃吭翘瘩皇抡暖凳峨瞩哇槐豁秦吞铲缕晌速疯舆傍碗盼疹吩胆偶第九章公钥密码学第九章公钥密码学6. RSA理论理论nRSA 基于Fermats Theorem: nif N=pq where p, q are primes, then:X(N)=1modN nfor all x not divisible by p or q, ie gcd(x,(N)=1 nwhere (N)=(p-1)(q-1) n但在 RSA 中，e & d 是特殊选择的nie e.d=1mod(N) 或e.d=1+R(N) nhence have:M=Cd=Me.d=M1+R(N)=M1.
10、(M(N)R=M1.(1)R=M1modN n 按硅矣搭恳串妮握却皑嚷列华肾盒夏伊绿救恿糯糯伺缀曹狰蔡诉捂麻拥朋第九章公钥密码学第九章公钥密码学8。RSA举例例子：例子：1. 选素数选素数p=47和和q71，得，得n=3337, (n)=46703220；2. 选择选择e=79，求得私钥，求得私钥d=e -1 1019(mod 3220）。）。3. 公开公开n=3337和和e=79.4. 现要发送明文现要发送明文688，计算：，计算：68879(mod 3337)=15705.收到密文收到密文1570后，用私钥后，用私钥d1019进行解密：进行解密： 15701019（mod 3337)=68
11、8弯化芳覆睫牌蟹婿绰演岂寂熟疼斋驴枢命愁撮黎惹占乙灾室觉简丽哪秦沟第九章公钥密码学第九章公钥密码学9。RSA 安全性安全性 nRSA 安全性基于计算 (N)的困难性 n要求分解模N 返铜务薪龚鬼忽旅毡棠馒骤沮撇煎讹呐搞其夕温患氏认镰寥域魏糊萎慧紫第九章公钥密码学第九章公钥密码学10. RSA的实现问题的实现问题n需要计算模 300 digits (or 1024+ bits) 的乘法n计算机不能直接处理这么大的数n（计算速度很慢）n需要考虑其它技术，加速RSA的实现耘或嚏卸枯泉蛇瞅拽筒荤洲声轮哲苇捐炕哥镶酱倍罐蓉吁荡与汞淋硅环昏第九章公钥密码学第九章公钥密码学11. RSA 的快速实现的快速实
12、现n加密很快，指数小n解密比较慢，指数较大n利用中国剩余定理CRT，nCRT 对RSA解密算法生成两个解密方程 （利用M=CdmodR ）n即: M1=Mmodp=(Cmodp)dmod(p-1)nM2=Mmodq=(Cmodq)dmod(q-1)n解方程 M=M1modpnM=M2modqn具有唯一解（利用CRT）：n:M=(M2+q-M1)umodqp+M1n其中p.umodq=1酉汪混史互药体傈简衰谜棺哦炎膜咯院剧斟缉辊诊窄零腹辽品壕汞渐蜘谈第九章公钥密码学第九章公钥密码学9.2.3概率素性检测概率素性检测 n定义9.2.3：如果P是素数，且a小于p,如果至少存在一个x 1，p-1满足x
13、2a(modp)，则我们称a是模p的二次剩余（quadratic residue）。n定义9.2.4：设p是一奇素数，对任何a0,我们定义勒让德符号（Legendre symbol）L(a,p)为 0 如果a 0(modp) L(a,p)= 1 如果a是模p的二次剩余 -1 如果a是p的非二次剩余n定理9.2.1（欧拉准则）：设p是素数，那么x是模p的二次剩余当且仅当 x(P-1)/2 1(modp) 疏端具必曝胸扇善檄竟屈裴挨拈抗诞粪繁铸秸葛饮类孙您侯退梳肝量逗讣第九章公钥密码学第九章公钥密码学n推论9.2.1：假设p是素数，那么L(a,p) a(P-1)/2(modp) n定义9.2.5：
14、雅可比符号（Jacobi symbol）,记作J(a,n),是勒让德符号的一般化表示，它定义在任意正整数a和奇整数n上。设n的素数因子分解式为pe1pek,则J(a，n)=L(a，p1)e1 L(a，p)ek 锣利顾另响茬持豪距荷敖厘跋治泞岿勺溺轰铅氖兵栗寝斧窒伴话亨甄鸣婚第九章公钥密码学第九章公钥密码学 对一个奇整数n的Solovay-strassen素性测试 1. 选择一随机整数a，满足a 1,n-12.如果J(a,n)=a(n-1)/2modn 则回答“n是素数”否则 回答“n是合数”阔囱惨曹炒灾何浆越簧滨振涣秘橡谱逗幕惜轻崩漓义躁筋殉署脱饭逛蓖曳第九章公钥密码学第九章公钥密码学7.Di
15、ffie-Hellman 密钥分配方案密钥分配方案n公钥密码问世 nDiffie & Hellman in 1976: n密钥交换的实际方法 n公钥方案概念的提出nW Diffie, M E Hellman, New directions in Cryptography, IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976 nJames Ellis (UK CESG) 在案970年曾提出此概念氓陋译胃豪司块很骄暴调俏忿滥竟雏问靠葫柬污陌恢炉碎敢悄纷曼猿颗誉第九章公钥密码学第九章公钥密码学12。El Gamal 公钥加密方案公钥加
16、密方案nDiffie-Hellman key distribution scheme 的变形n能够用于安全交换密钥npublished in 1985 by ElGamal: nT. ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985. n安全性是基于离散对数 n缺点：增加了消息长度（2倍） 衫魁芝斤套夸矛子菱果琢钥拧骋洋手帽兑谨薪芒猫垄哀
17、恨涣刽够括龙枕钻第九章公钥密码学第九章公钥密码学13 密钥建立n密钥生成：密钥生成：n选取一个大素数p及本原元amod pn接收者 Bob有一个密秘钥 xB n计算 yB=axBmodp n 疹咕滞挂寅命绎乙祝翰染截阵锤买洁边弟箱措犁潞拦乐各主澎观幂卡浸病第九章公钥密码学第九章公钥密码学14. El Gamal 加密加密n为加密 M n发送者选择随机数k, 0=k=p-1 n计算消息密钥 K : nK=yBkmodp n计算密文对: C=C1,C2 nC1=akmodp nC2=K.Mmodp n发送到接收者nk 需要永久保密 褥沾硕魏酝勿学哆略闭陨刀烈董剑寥烫授即育垛哀蹦锨勉褥窒潮抒媳槽蒸第
18、九章公钥密码学第九章公钥密码学15. El Gamal 解密解密n首先计算 message key K nK=C1xBmodp=ak.xB modp n计算明文: nM=C2.K-1 modp 绷赌空靖圣砍捆甫顽受儡麓鞠遮零栽潍编骨镑久钓歹挖匿辆纸闷御磅孺邀第九章公钥密码学第九章公钥密码学16. El Gamal Examplen选择 p=97 及本原根 a=5 nrecipient Bob 选择 秘密钥xB=58 & 计算并发布公钥yB=558=44mod97 nAlice 要加密 M=3 to Bob n首先得到 Bob的公开密钥 yB=44 n选择随机 k=36 计算:K=4436=75
19、mod97 n计算密文对: nC1=536=50mod97 nC2=75.3mod97=31mod97 n发送 50,31 to Bob nBob 恢复 message key K=5058=75mod97 nBob 计算 K-1=22mod97 nBob 恢复明文 M=31.22=3mod97 叼辆耙牙湾氦脑刺屠淬毁峭奢匣楷稼疟细律驱萤欠笔永延祷涩艘胡嗣驮遮第九章公钥密码学第九章公钥密码学9.3.1离散对数问题算法离散对数问题算法 肋目务准同胁傲帘翁榴驻秩酶孜投毫迭忻罩讫棚叛嘉镍男裙穿赡栓幸椅菩第九章公钥密码学第九章公钥密码学姨堡抹共运籍盟储挺胺三功剿蓑亭处氦蜀镣郎簧据蜗佣组享每泽庚抬烂硫第
20、九章公钥密码学第九章公钥密码学9.4 基于纠错码的公钥密码体制基于纠错码的公钥密码体制n纠错码理论中的NPC问题。 n问题1 陪集重量问题 n问题2 重量分布问题 n问题3 最小距离问题 n当前关于建立基于纠错码的密码体制很多是基于传统的Hamming距离的。 纽翻婚汞隘算多破牛霄学牢一燕城串憋揪奴槛闪绽婿隐绝秘阶猛赦骸照糙第九章公钥密码学第九章公钥密码学礁犹懈乒首直少火扑峪咕区甸商卫滨滋佳惹铃褂鄂惧冠蓑您眯龋戍剑泉镁第九章公钥密码学第九章公钥密码学9.5椭圆曲线公钥体制 1椭圆曲线 n定义9.5.1：设p是一个大于3的素数，在Zp上的椭圆曲线y2=x3+ax+b 由一个基于同余式y2=x3+
21、ax+b modp的解集（x，y）Zp*Zp和一个称为无穷远点的特定点O组成，这里的a,b Zp是二个满足4a+27b0 modp 的常数。 痹示脊胰恬何胆墅鲤化匝型倔蜀丫专嚎缓拐双敞犹肌街苯迁瑚萄统质恰婆第九章公钥密码学第九章公钥密码学椭圆曲线上的运算n设P=(x1,y1) E, Q=(x2,y2) E, 若 x1=x2且y1=-y2 ,那么 P+Q=O;否则P+Q=(x3,y3) ,这里的x3=2-x1-x2,y3= (x1-x3)-y1. x3=也胳吓恬侗差闪堵弄性迢辛乳钮嵌抹男乾嫌陷擎渊音优壁韵罚塌掘贰疫葫第九章公钥密码学第九章公钥密码学2椭圆曲线密码体制 定理9.5.1（Hasse定
22、理）：如果E是定义在域GF(q)上的椭圆曲线，N是E上的点(x,y) GF(q)的数目，则漱辑韦掐急贮版面盈褒迹游休枉疥削名莉氰绳宾贰层哲舅粹苫熔稠极惠视第九章公钥密码学第九章公钥密码学骏氓架冬模涨音垃爽契施撼届舞卵饲狠娶铬兼弧钝敬未坎辣崇蛹谓萄移省第九章公钥密码学第九章公钥密码学椭圆曲线密码体制有如下的一些特点 ：n1.在安全性相当的前提下, 可使用较短的密钥. n2.椭圆曲线密码体制是建立在一个不同于大整数分解及素域乘法群离散对数问题的数学难题之上. n 3 椭圆曲线资源丰富, 同一个有限域上存在着大量不同的椭圆曲线, 这为安全性增加了额外的保证。 n4. 在执行速度方面,椭圆曲线密码体制
23、较对应的离散对数体制要快, 且在签名和解密方面较RSA 快, 但在签名验证和加密方面较RSA 慢. n5椭圆曲线密码体制的安全性分析成果并不丰硕. 也许这可视为椭圆曲线密码体制具有高强度的一种证据,因此, 大多数密码学家对这种密码体制的前景持乐观态度. 揭洞呵噪许容赞循闭竞骋夹慰滚冯郁桨活仓正卉净刀楷伦媒迸皂篙六二牵第九章公钥密码学第九章公钥密码学9.6其他公开密钥密码体制其他公开密钥密码体制 9.6.1Goldwasser-Micali概率公开密钥概率公开密钥密码系统密码系统 斟肩劲蔡赡资钉居脂纶蛔寅何扇逮鸭绷角折问膜兽朗拾忽驻琵吐伊皿哭杰第九章公钥密码学第九章公钥密码学赔另塌瓤尽垂猿祁烟档
24、诅挺叁抛掉豺摔粹梆戮歼擞彝锣线谗默设帜封溃诽第九章公钥密码学第九章公钥密码学Goldwasser-Micali概率公开密钥密码系统概率公开密钥密码系统的安全性分析与讨论的安全性分析与讨论 n对于攻击者来说，当他截获到密文(C1,C2,Ck)时，他能求出J(Ci,n) ，但当mi=0，J(Ci,n)= J(xi2,n)=1，当mi=1, J(yxi2,n)= J(y,n)J(xi2,n)=1,攻击者无法获得其它的任何信息，而对A来说，因为他拥有私有密钥p和q ，可求出J(Ci,p)，J(Ci,q) , 从而得到明文。 n从传输效率来看，由于明文对应至1,n-1之间，故其效率为，|n|为n的长度。
25、效率非常差 。辗乞绸旋钻钥炒樊膨衔循咀苛哇砷院玫擒宰蛆学脏妇舒伐对光身育骆闯蕉第九章公钥密码学第九章公钥密码学9.6.2Merkle-Hellman背包公背包公钥密码体制钥密码体制 蛰洋稍果吼砷羔京恕镭攘标情枉瘩衍题驼玛崔谐黄柴瘸饶勃乡茸圈获芯讶第九章公钥密码学第九章公钥密码学9.6.3有限自动机公开密钥密码有限自动机公开密钥密码体制体制 n此类体制是基于分解两个有限自动机的合成也是困难的而构造的，尤其是当其中的一个或两个为非线性时，难度就会更大。 啊毖枕弱娱先槽湾对兼襄尹朝涨墓研抉骏楔闺委浮殖宁皆烁砖群定岭业寇第九章公钥密码学第九章公钥密码学小结n公钥密码学是现代密码学的很重要的组成部分，本章主要介绍了公钥密码的思想和几种基于计算复杂性的公钥密码体制。n公钥密码的思想nRSA体制n基于纠错码的公钥密码体制n基于椭圆曲线的公钥密码体制。 栈泊灌冤家踪酿罪生产瀑墓宫渝商砸巫斥到无少胀待谓痴调邓怖戊知铣琉第九章公钥密码学第九章公钥密码学
