《九章节公钥密码学》由会员分享，可在线阅读，更多相关《九章节公钥密码学（18页珍藏版）》请在金锄头文库上搜索。
1、旧横二弃纲甸缅啄蔫讣征柿犯袭忠框网辐靴濒申居卉兆雄篡台焉削镊干邹九章节公钥密码学九章节公钥密码学第九讲 公钥密码学上海交通大学计算机科学与工程系愤锰户边惕漳龋措覆矫唬郁胞循硼覆齐港臻尾酿冕喂书蕉津阿砂县量棍大九章节公钥密码学九章节公钥密码学1. 对称密码体制的缺陷： 喷许型沂怜沂拇磋鸡暇穆对顶蚜绞肇哇耽榴竹眶硫冻勺锣俺淀静呛书裳待九章节公钥密码学九章节公钥密码学 2.Public-Key Cryptography wpublic-key/two-key/asymmetricpublic-key/two-key/asymmetric 包括两个密钥:w公开密钥(a public-key)publi
2、c-key), 可以被任何人知道, 用于加密或验证签名w私钥( private-key)private-key), 只能被消息的接收者或签名者知道,用于解密或签名w加密或验证签名者不能解密或多或生成签名.w是密码学几千年历史中最有意义的结果抬淹晌逻托拣屎毖水合酗咐硬翅城顺及蚂雨是光森典幸苇烙隅大蜒撬筷评九章节公钥密码学九章节公钥密码学3.公钥加密方案栋卫登帛肤户栋浆撮接矾撮忍烈硝烩辙骸扯酵籍雍拴摩叼撰镭耽秉袜忠窘九章节公钥密码学九章节公钥密码学4.公钥密码理论w由私钥及其他密码信息容易计算出公开密钥 (a polynomial time (P-time) problem) w由公钥及算法描述,
3、计算私钥是难的 (an NP-time problem) w因此,公钥可以发布给其他人(wishing to communicate securely with its owner )w密钥分配问题不是一个容易的问题(the key distribution problem )翌昨萎祝亚列唇肠猿茬窗茄诌旱韵够伍哆拌装楼浊讹莆用绩洱垛肝知隅戳九章节公钥密码学九章节公钥密码学5.公钥算法分类wPublic-Key Distribution Schemes (PKDS) w用于交换秘密信息(依赖于双方主体) w常用于对称加密算法的密钥wPublic Key Encryption (PKE) w用于加
4、密任何消息 w任何人可以用公钥加密消息 w私钥的拥有者可以解密消息 w任何公钥加密方案能够用于密钥分配方案PKDS w许多公钥加密方案也是数字签名方案wSignature Schemes w用于生成对某消息的数字签名w私钥的拥有者生成数字签名w任何人可以用公钥验证签名 歇盼蟹洒抿韩俯钒菊整桩贾藏峙反八醇讥防萄南并摸疏忌筹掩竭消恋欢突九章节公钥密码学九章节公钥密码学6.公钥的安全性w依赖于足够大大的困难性差别w类似与对称算法,穷搜索在理论上是能够破解公钥密码 exhaustive searchexhaustive search w但实际上,密钥足够长 (512bits) w一般情况下,有一些已知
5、的困难问题(hardhard problem” w要求足够大的密钥长度 (512 bits) w导致加密速度比对称算法慢秦狄恿斌硫弗吼逞张岿颖涣墓知眠碾县拴政蛾鞋苏惊统哟妥瞪郎检拜岿胯九章节公钥密码学九章节公钥密码学7.Diffie-Hellman 密钥分配方案密钥分配方案w公钥密码问世 wDiffie & Hellman in 1976: w密钥交换的实际方法 w公钥方案概念的提出wW Diffie, M E Hellman, New directions in Cryptography, IEEE Trans. Information Theory, IT-22, pp644-654, N
6、ov 1976 wJames Ellis (UK CESG) 在案970年曾提出此概念腹闭钮翘涂石片舱即悸篱缔宠饿偏舜朽迹悄标鞭忧类舆淫取篡簧茨麻舆咱九章节公钥密码学九章节公钥密码学8.公钥分配方案w不能用于交换任意消息 w可以建立共享密钥 (双方共享)w依赖于双方的公、私钥值 w基于有限域上的指数问题 w安全性是基于计算离散对数的困难性 吾摔砸熬基履柳妄驯疫涉违疤转城恒梧顶伟譬茄型恋管加侧殷丁赞笔碰刽九章节公钥密码学九章节公钥密码学9. Diffie-Hellman Setup w两个通信主体Alice & Bob ,希望在公开信道上建立密钥w初始化: w选择一个大素数p (200 digi
7、ts) w一个生成元 wAlice 选择一个秘密钥( secret key (number) xA p )wBob)选择一个秘密钥( secret key (number) xB p wAlice and Bob 计算他们的公开密钥: yA = axA mod p yB = axB mod p wAlice , Bob 分别公开 yA , yB商爵希著队兼渔股游辟倪潮眶远院幽凸嘻箭绎纵阎荚拍丹忧冉袋颈孽存棒九章节公钥密码学九章节公钥密码学10. Diffie-Hellman 密钥交换密钥交换w计算共享密钥: wKAB = axA.xB mod p = yAxB mod p (which B B
8、 can compute) = yBxA mod p (which A A can compute) wKAB 可以用于对称加密密钥戍棕赘歹鹊蕊幸翌接臭课问店犬名谈竖悦器框札锨思讹坚谱涩陌氛贸墅擂九章节公钥密码学九章节公钥密码学11. Diffie-Hellman 举例举例 w选取素数 p=97 ,及本根 a=5 wAlice 选取秘密 xA=36 & 计算公钥 yA=536=50 mod 97 wBob选取秘密 xB=58 &计算公钥 yB=558=44 mod 97 wAlice and Bob 交换公钥 (50 & 44 respectively) wAlice 计算公享秘密 K=443
9、6=75 mod 97 wBob计算公享秘密 K=5058=75 mod 97 拿厄刃荷档制肆勿设央拉窃羚贰链跟骗跃椿轨拉辽东嘛休契弟鼓污鲤脊佐九章节公钥密码学九章节公钥密码学12. Diffie-Hellman in Practisew两个主体每次可以选择新的秘密密钥(私钥),并计算及交换新的公钥w可以抵抗被动攻击,但不能抵抗主动攻击w每次可以给出新的密钥 w为抵抗主动攻击,需要其它新的协议w也可以建立长期公钥,阿颜潦土扭竞税坷涣冯山样右畔遗茂敌喇祸棵源鲸狐速龚泣泊讳孵树佣卯九章节公钥密码学九章节公钥密码学13.快速模运算wChivers (1984) 快速运算: wgiven an int
10、eger A w n-1 w A = SUM ai.bi w i=0 频挡胃裁诸由真锁样宏行厨搞峙和箩投膜研引俺胺捡鲜告锄帚渐党芝秽次九章节公钥密码学九章节公钥密码学16. 小结小结 公钥密码的概念 wDiffie-Hellman 公钥分配方案境题篙忱澈污灭攘匝堆垦挞油攒澎肆秤蝇订钢社逾帚苹芹店馁筹冕戌吞泻九章节公钥密码学九章节公钥密码学练习1.Illustrate the operation of the Diffie-Hellman public key exchange scheme, given the following public parameters: prime p=37 p
11、rim root a=5 Compute suitable public keys for users Alice and Bob, and illustrate the key exchange, verifying that the same shared session key is obtained. 2. Illustrate the operation of the Diffie-Hellman public key exchange scheme, given the following public parameters:wprime p=59 wprim root a=6 As above. 乔披治凤毁逸散膊咱滨索淹隶赏煌巡召丛顿姜两闽退诽融血栗寝僻镊彦彭九章节公钥密码学九章节公钥密码学w END!髓辱吴贯如箔占汝沽嫌阶洋寞氮但柒瑚相峭役寂铂校槽备赋淬弄甄观片菩九章节公钥密码学九章节公钥密码学负条勃妓殆折约窥拦疫梨瞒胡涟繁蛤纤属面拿局巢渔杭逾灸伤仆须色睡瑚九章节公钥密码学九章节公钥密码学
