《第19讲公钥密码概述》由会员分享,可在线阅读,更多相关《第19讲公钥密码概述(28页珍藏版)》请在金锄头文库上搜索。
1、公钥密码体制,量子密码研究室 王 滨 2005.4.12,上课安排,公钥密码体制的概念、思想和工作方式 Diffie-Hellman密钥交换算法 RSA 算法 EIgamal公钥算法 ECC算法,背景,在拥有大量用户的通信网络,若想让两两用户都能进行保密通信,即要求 (1)任意一对用户共享一个会话密钥 (2)不同的用户对共享的会话密钥不相同 对于分配中心,N个用户则需要分配CN2个会话密钥,大量的数据存储和分配是一件很麻烦的事,在计算机网络环境下显的尤为突出。另外传统密码不易实现数字签名,也进一步限制了其发展。,公开密钥算法的提出,公钥密码学是1976年由Diffie和Hellman在其“密码
2、学新方向”一文中提出的,见文献: W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654,公开密钥算法,公开密钥算法是非对称算法,即密钥分为公钥和私钥,因此称双密钥体制 双钥体制的公钥可以公开,因此也称公钥算法 公钥算法的出现,给密码的发展开辟了新的方向。公钥算法虽然已经历了20多年的发展,但仍具有强劲的发展势头,在鉴别系统和密钥交换等安全技术领域起着关键的作用,加密与解密由不同的密钥
3、完成 加密: 解密: 知道加密算法,从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以作为加密而另一个用作解密(不是必须的),公开密钥算法的基本要求,基于公开密钥的加密过程,用公钥密码实现保密,用户拥有自己的密钥对(KU,KR) 公钥 KU公开,私钥KR保密,基于公开密钥的鉴别过程,用公钥密码实现鉴别,条件:两个密钥中任何一个都可以用作加密而另外一个用作解密 鉴别: 鉴别保密,公开密钥算法,公钥算法的种类很多,具有代表性的三种密码: 基于整数分解难题(IFP)的算法体制 基于离散对数难题(DLP)算法体制 基于椭圆曲线离散对数难题(ECDLP)的算法体制,Diffie-Hell
4、man密钥交换算法,Diffie-Hellman公钥技术,Diffie-Hellman公钥密码技术又称为Diffie-Hellman密码交换协议,它是Whitefield Diffie和Martin Hellman在1976年提出的,是至今仍然流行的一种公 钥技术.(见教材P143),D-H密钥交换协议背景密钥分配,人工手动分配密钥: 问题 效率低 成本高 每个用户要存储与所有用户通信的密钥 安全性差 机器自动分配密钥: 要求 任何两个用户能独立计算他们之间的秘密密钥 传输量小 存储量小 任何一个(或多个)用户不能计算出其他用户之间的秘密密钥,单向陷门函数函数,满足下列条件的函数f: (1)
5、给定x,计算y=f(x)是容易的 (2) 给定y, 计算x使y=f(x)是困难的 (3) 存在z,已知z 时, 对给定的任何y,若相应的x存在,则计算x使y=f(x)是容易的 所谓计算x= f-1(Y)困难是指计算上相当复杂,已无实际意义,单向陷门函数说明,仅满足(1)、(2)两条的称为单向函数;第(3)条称为陷门性,z 称为陷门信息 当用陷门函数f作为加密函数时,可将f公开,这相当于公开加密密钥,此时加密密钥便称为公开密钥,记为Pk f函数的设计者将z保密,用作解密密钥,此时z称为秘密钥匙,记为Sk。由于设计者拥有Sk,他自然可以解出x=f-1(y) 单向陷门函数的第(2)条性质表明窃听者由
6、截获的密文y=f(x)推测x是不可行的,Diffie-Hellman密钥交换算法,Diffie和Hellman在其里程碑意义的文章中,虽然给出了密码的思想,但是没有给出真正意义上的公钥密码实例,也既没能找出一个真正带陷门的单向函数 然而,他们给出单向函数的实例,并且基于此提出Diffie-Hellman密钥交换算法,Diffie-Hellman密钥交换算法的原理,基于有限域中计算离散对数的困难性问题之上:设F为有限域,gF是F的乘法群 F*=F0=,并且对任意正整数x,计算gx是容易的;但是已知g和y求x使y= gx,是计算上几乎不可能的,Diffie-Hellman密钥交换协议描述,Alic
7、e和Bob协商好一个大素数p,和大的整数g,1 p和g无须保密,可为网络上的所有用户共享,Diffie-Hellman密钥交换协议描述,当Alice和Bob要进行保密通信时,他们可以按如下步骤来做: (1) Alice选取大的随机数x,并计算 X = gx (mod P) (2) Bob选取大的随机数y,并计算 Y = gy (mod P) (3) Alice将X传送给Bob;Bob将Y传送给Alice (4) Alice计算K= (Y)x(mod P); Bob计算K =(X) y(mod P), 易见,K = K =g xy (mod P) 由(4)知,Alice和Bob已获得了相同的秘密
8、值K 双方以K作为加解密钥以传统对称密钥算法进行保密通信,DH协议分析,优点: (1) 任何两个人都可协商出会话密钥,不需事先拥有对方的公开或秘密的信息. (2) 每次密钥交换后不必再保留秘密信息,减少了保密的负担. 前提条件: 必须进行身份认证,确保不是与假冒的用户进行密钥交换,否则不能抵抗中间人攻击.,中间人攻击,-攻击者W在信道中间,假冒U与V进行密钥交换,同时假冒V与U进行密钥交换.致使看似U与V交换的密钥,实际上都是与攻击者交换的密钥.,具体攻击,具体方法,攻击者W在信道上截获 和 后,不将它们送给用户V和用户U,而是随机选取整数 ,并计算出 将它明传给用户U,同时暂时保留 ;同时随机选取整数 ,并计算出 后,将明传给用户V,同时暂时保留 .,具体方法,用户U计算出 用户V计算出 攻击者W分别计算出 分别作为解密用户U发给用户V的密钥和解密用户V发给用户U的密钥.,具体方法,攻击者截获用户U发给V的密文后,不传给用户V,而是解读出明文后再将明文用W与V的密钥加密后传给V. 备注: 中间人攻击中可选择xw1=xw2. 对付中间人攻击的方法: 中间人攻击利用了D-H协议中与双方的身份信息无关这个缺点,因而必须利用对方的身份信息进行对之进行身份认证.,中间攻击基本模式,U,V,xU,w1,W,w2,xV,STS(Station To Station)协议,