（计算机软件与理论专业论文）群组密钥协商协议的设计与分析.pdf

摘罂 摘要 信息作为一种资源，它的普遍性、共享性、增值性、可处理性和多效用性， 使其对于人类具有特别重要的意义。信息安全的实质就是要保护信息系统或信 息网络中的信息资源免受各种类型的威胁、二f 扰和破坏，即保证信息的安全性。 信息安全是任何国家、政府、部门、行业都必须十分蘑视的问题，是一个不容忽 视的国家安全战略。 密码技术是信息安全中的关键技术。密码技术包括加密解密技术，认证技 术等；通过密码技术的应用，可以为人们提供信息保密性，数据完整性，身份认 证，消息认证，数字签名，以及不可否认性等多种安全特性。只有密码学得到了 很好的发展，掌握了这些前沿的密码技术才能很好的保证信息的真止安全。而 在密码学里而，密码系统的安全都是依赖于密钥的安全保密性，因此如何安全有 效的协商出共同的会话密钥是一个非常重要的问题。有了安全的密钥协商机制， 才可能将加密方案或者数字签名方案应用到实际中去。 由于密钥协商的重要性，密钥协商的研究吸引了很多人的关注，是密码学 理论研究中的一个热点。本文的前半部分主要介绍了密钥协商的一些基本概念， 包括其所需要的安全要求和数学基础：同时还对密钥协商方面的研究进展进行 了调研，介绍了人们在这些方面的研究成果。 随着计算机网络中面向群组的应用的兴起，人们也很关注与之密切相关的 群组密钥协商的研究。e l 前，群组密钥协商的研究已经从最初的静态群组的非 认证密钥协商发展到了动态群组的认证密钥协商。这里其1 1 1个重要的分支是 移动网中的群组密钥卧商。在移动网中，成员用户所拥有的资源和计算处理能 力干差万别，有的处理能力很强，有的则仅拥有有限的一些资源。考虑到这些特 点，本文在借鉴前人研究的基础上，利用双线性对，提出了一个认证的动态群组 密钥协商方案。在此方案中，系统的主要处理任务由处理能力强的用户来负责， 而其它用户仅需要处理少量的计算和通信任务。此外，我们还对该方案的效率 和安全性进行了分析，得出我们的方案足安全有效的结论。因此，我们的方案适 用于移动网这种应用环境。 此外，我们还研究了与密钥协商协议效率密切相关的椭圆曲线的标量乘法。 摘要 在借鉴之前的标量乘法窗口算法和侧信道原子块方法的基础上，我们提出了一 个抗侧信道攻击的标量乘法窗口算法，并在此基础上，提出了一个新的并行标量 算法。新的并行算法可以抵抗侧信道攻击，而且其效率也优于之前的并行标量 算法。 关键词：动态群组密钥咖商 双线，i 生x 1基下身份的密码系统 椭 圆曲线密码学 i l a b s t r a c t a b s t r a c t i n f o r m a t i o n ，a sak i n do fv a l u a b l er e s o u r c e ，i sv e r yi m p o r t a n tt oh u m a nb e i n g a n dw eh a v et ot a k em e a s u r e st op r o t e c ti t ，t oa s s u r et h es e c u r i t yo fi n f o r m a t i o n i n - d e e d ，i n f o r m a t i o ns e c u r i t yi st op r o t e c ti n f o r m a t i o nf r o mb e i n gt h r e a t e n e d ，d i s t u r b e d ， a n dd e s t r o y e di n f o r m a t i o ns e c u r i t yi ss oi m p o r t a n tt h a ta l ls t a t e s ，g o v e r n m e n t s ，a n d e n t e r p r i s e sh a v et oc o n s i d e ri ts e r i o u s l y t h ek e yt e c h n i q u eo fi n f o r m a t i o ns e c u r i t yi sc r y p t o g r a p h y i tc a np r o v i d es e r - v i c e so fc o n f i d e n t i a l i t y e n t i t ya u t h e n t i c a t i o n ，m e s s a g ea u t h e n t i c a t i o n ，s i g n a t u r e ，n o n r e p u d i a t i o n ，e t c a sw ek n o w , i nm o d e r nc r y p t o g r a p h y , t h es e c u r i t yo fac r y p t o s y s t e m d e p e n d so nt h es e c r e c yo ft h ek e ys oi ti so fg r e a ti m p o r t a n c et od e s i g nk e ya g r e e m e n t p r o t o c o l sb o t he f f i c i e n ta n ds e c u r eo n l yi ft h e r ee x i s t ss e c u l ek e ya g r e e m e n tp r o t o c o l s ，c a ny o up u to t h e rc r y p t o s y s t e m s ( e ，g e n c r y p t i o ns c h e m e s ，o rd i g i t a ls i g n a t u r e s c h e m e s ) i n t op r a c t i c es e c u r e l y d u et ot h ei m p o r t a n c eo fk e ya g r e e m e n t ，t h er e s e a r c ho fk e ya g r e e m e n th a sg a i n e d q u i t eal o to ff o c u s s i nt h ef i r s tp a r to ft i f f st h e s i s ，w ep r e s e n ta ni n t r o d u c t i o n t o k e ya g r e e m e n t ，i n c l u d i n gt h eb a s i cc o n c e p t sa b o u tt h es e c u r i t yr e q u i r e m e n t sa n dm a t h f o u n d a t i o n s ；w ea l s op r e s e n tas u r v e yo ft h er e c e n td e v e l o p m e n to fk e ya g r e e m e n t p r o t o c o l s w i t ht h ep o p u l a r i t yo fg r o u p o r i e n t e da p p l i c a t i o ni nc o m p u t e rn e t w o r k s ，t h er e s e a r c ho ft h er e l a t e dg r o u pk e ya g r e e m e n th a sb e c o m eah o ts p o t c u r r e n t l y ，t h er e s e a r c hf o c u so fg r o u pk e ya g r e e m e n th a ss h i f t e df r o mt h eo r i g i n a lu n a u t h e n t i c a t e ds t a t i cg r o u pk e ya g r e e m e n tt oa u t h e n t i c a t e dd y n a m i cg r o u pk e ya g r e e m e n tt h e r ei so n e i m p o r t a n tr e s e a r c hb r a n c ho fg r o u pk e ya g r e e m e n t ：g r o u pk e ya g r e e m e n tf o rm o b i l e n e t w o r k s t h e r ei sa no b v i o u sv a r i e t yo ft h ec o m p u t a t i o na b i l i t yi nm o b i l en e t w o r k s ： s o m eu s e r sh a v es t r o n gh a n d l i n ga b i l i t y ，w h i l et h eo t h e r so n l yh a v el i m i t e dh a n d l i n g a b i l i t y d u et ot h i sv a r i e t y ，b a s e do nt h ef o r m e rr e s e a r c h e s ，u t i l i z i n gb i l i n e a rp a i r i n g s ， w ep r o p o s e da na u t h e n t i c a t e dd y n a m i cg r o u pk e ya g r e e m e n tf o rm o b i l en e t w o r k s i n t h i sk e ya g r e e m e n ts c h e m e ，ag r o u pu s e rw h oh a ds t r o n ga b i l i t yi sr e s p o n s i b l ef o rt h e i l i a b s t la c t h a n d l i n go fm o s tc o m p u t a t i o na n dc o m m u n i c a t i o n ；t h eo t h e ru s e r so n l yn e e dt oc a r r y o u taf e wc o m p u t a t i o n s o u rs c h e m ei se t s c i e n t ，a n di tm e e t st h er e q u i r e m e n t so fk e y a g r e e m e n t s oo u rp r o t o c o li sp r a c t i c a li nm o b i l en e t w o r k s k e yw o r d s ：d y n a m i cg r o u pk e ya g r e e m e n t b i l i n e a rp a i r i n g s i d e n t i t y 。 b a s e dc r y p t o s y s t e m e l l i p t i cc u r v ec r y p t o s y s t e m 主要符哮对照表 b d h c d h c a d d h d s a e c c k g c p i n p k g s e t 主要符号对照表 双线性d i f f i e h e l l m a n 计算性d i f f i e h e l l m a n 认证中心 判断性d i f f i e h e l l m a n 数字签名算法 椭圆曲线密码系统 密钥生成中心 个人身份标识号码 密钥生成器 安全电子交易 v i i 关于学位论文使用授权的说明 本人完全了解中国科学技术大学有关保鐾、使用学位论文的规 定，即： 中国科学技术大学稀有在著作权法规定范围内学位论文酌使用 权，其中包括：( 1 ) 已获学位瓣礤究生必须接学校援定提交学位论文， 学校可以采用影印、缩印或其他复制手段保存研究生上交的学位论 文；( 2 ) 为教学和科研目的，学校可以将公开的学位论文作为资料在 图书馆、资料室等场所供校内爆生阕读，蠛在校嚣嚣上供校内舜，圭敦l 览部分内容。 本人保证遵守上述规定。 ( 保密的论文在解密后应遵守此规定) 储虢埠 器麓：边旌! 叁羔缝 名 鬻 签导 西 声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行 研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论 文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明 确方式标明。 签名：纽篮日期：泣墨： 第】章绪| 仑 第1 章绪论 信息安全技术是一门综合的学科，它涉及信息论、计算机科! 学和密码学等多 方面知识，它的主要任务是研究计算机系统和通信网络内信启、的保护方法以实 现系统内信息的安全、保密、真实和完整。其中，信息安全的核心是密码技术。 随着计算机网络不断渗透到各个领域，密码学的应用也随之扩大。数字签 名、身份鉴别等都是由密码学派生出来的新技术和应用。当前的密码学研究内 容主要包括数据加密，数字签名和密钥协商等。 1 1 数据加密 在计算机上实现的数据加密，其加密或解密变换是由密钥控制实现的。密 钥是用户按照一种密码体制随机选取，它通常是一随机字符串，是控制明文和密 文变换的唯一参数。 根据密钥类型不同将现代密码技术分为两类：一类是对称加密( 秘密钥匙 加密) 系统，另一类是公开密钥加密( 非对称加密) 系统。 对称钥匙加密系统是加密和解密均采用相同的密铡，而日通信取方都必须 获得这一密钥，升保持密钳的秘密性。对称密码系统的安全性依赖j j 以下两个 因素。第一，加密算法必须是足够强的，仅仅基于密文本身去解密信息在实践一l 是不可能的；第二，加密方法的安全性依赖于密钥的秘密性，而不是算法的秘密 性，因此，我们没有必要确保算法的秘密性，而需要保证密钥的秘密性。对称加 密系统的算法实现速度快，其软件实现的速度都达到了每秒数兆或数十兆比特。 对称密码系统的这些特点使其有着广泛的应用。因为算法不需要保密，所以制 造商n j 以开发出低成本的芯片以实现数据加密。这些芯片有着广泛的应用，适 合于大规模生产。 对称加密系统最大的问题是密钥的分发和管理非常复杂、代价高昂。比如 对于具有n 个用户的网络，需要n f n 一1 ) 2 个密钥，在用户群不是很大的情况 下，对称加密系统是有效的。但是对于大型网络，当用户群很大，分布很广时， 密钥的分配和保存就成了大问题。对称加密算法另一个缺点是不能实现数字签 第1 章绪论 名。 公开密钥加密系统采用的加密密钥( 公钥) 和解密密钥( 私钥) 是不同的。 由于加密钥匙是公开的，密钥的分配和管理就很简单，比如对于具有n 个用户的 网络，仅需要2 月个密钥。公开密钥加密系统还能够很容易地实现数字签名。因 此，最适合于电子商务应用需要。 在实际应用中，公开密钥加密系统并没有完全取代对称密钥加密系统，这是 因为公开密钥加密系统是基于复杂的数学难题，比如大整数因子分解系统( 代表 性的有r s a ) 、椭园曲线离散对数系统( e c c ) 年h 离散对数系统( 代表性的有d s a ) ， 其计算非常复杂，它的安全性更高，但它实现速度却远赶不上对称密钥加密系 统。 l2 数字签名 密码技术除了提供信息的加密解密外，还提供对信息来源的鉴别、保证信 息的完整和不可否认等功能，而这三种功能都是通过数字签名实现。 数字签名的一般步骤： 被发送文件采用哈希算法对原始报文进行运算，得到一个固定长度的数 字串，称为报文摘要( m e s s a g ed i g e s t ) ，不同的报文所得到的报文摘要各异， 但对相同的报文它的报文摘要却是唯一的。 2 发送方生成报文的报文摘要，用自己的私钥对摘要进行加密来形成发送方 的数字签名。 3 这个数字签名将作为报文的附件和报文一起发送给接收方。 4 接收方首先从接收到的原始报文中用同样的算法计算出新的报文摘要，再 用发送方的公钥对报文附件的数字签名进行解密，比较两个报文摘要，如 果值相同，接收方就能确认该数字签名是发送方的。 这样的签名方法是符合可靠性原则的。即：签字是可以被确认的，签字是无 法被伪造的，签字是无法重复使用的，文件被签字以后是无法被篡改的，签字具 有不可否认性。 2 第l 章绪沦 实现数字签名有很多方法，目前数字签名采用较多的是公钥加 密技术，如基 ：r s ad a t as e c u r i t y 公司的p k c s ( p u b l i ck e yc r y p t o g r a p h y s t a n d a r d s ) 、d s a ( d i g i t a ls i g n a t u r ea l g o r i t h m ) 、x 5 0 9 、p g p ( p r e t t yg o o dp r i v a c y ) 。1 9 9 4 - 年- 美国标准与技术协会公布了数字签名标准( d s s ) 而使公钥加密技 术广泛应用。 1 3 密钥协商 正如前面所述，对称密码系统执行速度快，而公钥密码系统安全性能好但是 速度慢，所以可以综合利用这两者的各自特点，以构建安全有效的密码系统：用 公钥密码系统来协商出一个共同的会话密钥做为对称密码系统的密钥，然后用 对称密码系统对大量数据进行加密。这个协商会话密钥的过程，便是密钥协商 协议的执行过程。 密钥协商协泌也称密钥交换协 义，它包括一系列的步骤，通过这些步骤， 两个或者多个用户可以协商出一个共同的会话密钥，用于之后的保密通信。有 了密钥协商协议，人们便可以在不安全的网络媒介上方便而安全的共享会话密 钥。假定a l i c e 和b o b 想利用一个私钥密码系统来实现保密通信，他们必须首先 决定选用一个共享的密钥。如果是通过打电话米讨论选用密钥，那么窃听者就可 以通过偷听来的密钥来获取他们之后的通信内容。而通过采用密钥协商协议， a l i c e 和b o b 就可以在不安全的环境中安全地交换密钥。 密钥协商协议是密码学中一个重要的基本构件，它是加密算法和数字签名 算法之后的又一个基本密码学工具，有了它才4 能构建安全、复杂的上层协议和 虑用。否则，如果用户之间不能够安全的协商出秘密的共同密钥，即使有非常优 秀的加密算法或者签名算法，也同样无法得到个安全有效的应用。 在保密认征通信中，密钥协商有着非常广泛的应用。很多网络通信协议都 包含有密钥协商，比如应用广泛的s s l ，i p s e c ，w c d m a 等网络通信防议。 1 4 本文结构 在接下来的第二章中，我们介缁密钥协商相关的基础知识，包括数学基础知 识和难题假设等；同时，还介绍密钥协商的发展现状。第三章介绍的是我们提出 第1 章绪论 的一个新的基于身份的动态群组密钥协商方案，而第四章则是对新方案进行复 杂性和安全性两方而进行分析。第五章我们提出了一个新的椭圆曲线并行标量 算法，有了快速的标量算法的实现，我们可以更加有效的实现基于椭圆曲线的密 码系统，比如基于椭圆曲线的密钥协商方案。最后一章是沦文的结论。 4 第2 章密铡协商介绍 第2 章密钥协商介绍 如前所述，密钥协商的目标是在不安全的网络环境下实现安全有效的密钥 交换。这里就包括两方面的含义：好的安全性以及算法执行的高效率。效率的考 虑主要是算法的执行轮数以及交换的数据信息量；而刑于安全性来说，人们 般认为密钥协商需要满足下列的些要求( 1 0 2 。 2 1密钥协商的安全要求 隐式密钥j a i i e ( 1 m p l i c i tk e ya u t h e n t i c a t i o n ) ：如果一个密钥协商协议具有 了隐式密钥认证的特性，则它可以保证除了协议参与者之外的其它人都不 能够获知所协商出来的会话密钥。 显式密钥认i i e ( e x p l i c i tk e ya u t h e n t i c a t i o n ) ：一个密钥协商协议如果同时 具有隐式密钥认证和密钥确认的特性，则称此协议是提供显式密钥认证 的。而密钥确认是指该特性可以使得协议参与者确认其它用户最后计算出 来的是相同一致的会话密钥。 己知会话密钥安全( k n o w ns e s s i o nk e ys e c u r i t y ) ：如果密钥协商协议具 有了已知会话密钥安全的特性，则一次会话密钥的泄漏不会影响到别的轮 次所枷商出来的会话密钥，也就是要求经过密钥协商方案协商出来的不同 会话密钥之间是相瓦独立的。 向前安全性( f o r w a r ds e c r e c y ) ：是指西议参与者的长期私钥的泄漏不会 影响到在这之前所协商的密钥的安全性。如果是所有协l 义参与者的长期私 钥都被破解之后，仍然不会影响到其之前所得到的会话密钥的安全性，则 称该协议具有完全向前安全性；否则，称该协议具有部分向前安全性。 密钥泄漏的伪装攻击安全( k e y - c o m p r o m i s ei m p e r s o n a t i o nr e s i l i e n c e ) ： 是指敌手破解用户a 的长期私钥后，可以伪装成a 去欺骗其它人：但是不能 够伪装成别人，比如伪装称b ，来欺骗该被破解的用户a 。 第2 章崭钏协商介绍 未知密钥协商攻击安全( u n k n o w nk e y s h a r er e s i l i e n c e ) ：是指用户不能 被欺骗去和未知的第三者协商密钥，也就是不能发生下而的情况：a l i c e 本 想和b o b 协商密钥，而实际上被欺骗成与m a l i c e 协商密钥。 2 2 密钥协商所采用的认证技术 现代的密钥协商协议中，认证是一个基本的安全要求；目前，一般有以下两 种身份认证的技术：基于公钥证书的身份认证和基于身份标识的身份认证。 2 2 1基于公钥证书的密钥协商 在基于证书的协议中，我们假定每个协议参与者均拥有一个静态( 长期) 的 d i f f i e h e l l m a n 公私密钥对，并且每个用户都知道其它用户的公钥。静态公钥是 通过个认证中心( c a ) 所签发的证书来认证的，该证书中的公钥绑定了用户 的标识。当两个用户想在他们之间建立一个临时会话密钥时，他们要交换一对 临时( 短期) d i f f e h e l h n a n 公铡，这些临时的公铡用来和长期密钥一起构建所 耍叻、商的会活密钥：而长期符钊的认证性便是通过c a 签署的“f 书来提供的。 在一个基于证书的系统中，参与者在使用一个用户的公钥之前必须首先验 证该公钥证书。这样，系统就需要大量的刊算时间和存储空问。 2 2 ，2 基于身份的密钥协商 在1 9 8 4 年，s h a m i r l 8 8 提出了一个基于身份的密码系统的思想，在这种系统 中用户的公钥是关于用户标识的函数，比如用户的公钥可以是用户的公丌电子 邮件地址；而私钥的生成则需要一个可信的第三方，这个第三方一般称为p k g ( p r i v a t ek e yg e n e r a t o r ) 或者k g c ( k e yg e n e r a t i o nc e n t e r ) ，它负责用户对应私 钥的生成。s h a m i r 当时就给出了一个可行的基于身份的数字签名方案，而第一 个可行的基于身份的加密方案是在2 0 0 1 年由b o n e h 和f r a n k l i n 1 7 1 提出的。b f 加 密方案是基于双线性对的，在该方案中，用户的公钥是用户的标识( 比如，司。以 是他的e m a i l ) 。受b f 方案的启发，在很短的时间内，人们利用双线性对的特点， 提出了很多基于身份的密码协议方案。 第2 章密钏曲，商介绍 2 3 密钥协商的数学基础 2 3 1 椭圆曲线 椭圆曲线密码体制( e l l i p t i cc u r v ec r y p t o s y s t e m ，e c c ) 是由m i l l e r 7 7 和 k o b l i t z 6 7 分别独立引入的密码学工具，它是当前学界和业界的研究热点。椭恻 曲线密码体制相比于其它公钥密码体制( 比如r s a 密码系统) 有着以下的有点： 安全性能更高加密算法的安全性能一般通过该算法的抗攻击强度来反 映。e c c 和其他j l 种公钥系统相比，其抗攻击性具有绝对的优势。如1 6 0 1 ：l 特位e c c 与1 0 2 4 比特位r s a 、d s a 有相同的安全强度。而2 i o i ：- l 特位e c c 则与2 0 4 8 比特位r s a 、d s a 具有相同的安全强度。 计算量小，处理速度快虽然在r s a 中可以通过选取较小的公钥( 可以小 到3 ) 的方法提高公铡处理速度，即提高加密和签名验证的速度，使其在加 密和签名验证速度匕与e c c 有可比性，但在私钥的处理速度卜( 解密和签 名) ，e c c 远比r s a 、d s a 快得多。因此e c c 总的速度比r s a 、d s a 要快 得多。 存储空间占用小e c c 的密钥尺寸和系统参数与r s a 、d s a 相比要小得 多，意味着它所占的存贮窀问要小得多。这对于加密算法在i c 卡上的应用 具有特别重要的意义。 带宽要求低当对长消息进行加解密时，三类密码系统有相同的带宽要求， 但应用于短消息时e c c 带宽要求却低得多。而公钥加密系统多用于短消 息，例如用于数字签名和用于对对称系统的会话密钥传递。带宽要求低使 e c c 在无线网络领域具有广泛的应用前景。 e c c 的这些特点使它必将取代r s a ，成为通用的公钥加密算法。比如s e t 协议 的制定者已把它作为下一代s e t 协议中缺省的公钥密码算法。 2 3 1 1 r 上的椭圆曲线 p 是一个大于3 的奇素数，整数d ，b 昂，他们满足4 a 3 + 2 7 b 2 o ( m o d p ) 。 则定义于有限域昂上的以n ，b 为参数的椭圆曲线，其上面的点包括一个称 第2 章带钏协商介绍 为无穷远点矽，以及满足下而的等式的点p = 0 ，y ) ，y e ， 对于给定一个点p = ( x p ，卯) ，x p 称为p 的z 坐标，y p 成为p 的y 坐标。 定义在集合e ( 昂) 上的加法操作+ 使得( e ( 昂) ，+ ) 构成了一个阿贝i f , 群( a b e l i a ng r o u p ) ，其中扩是零点。正是这个阿贝尔群，使得我们可以构造出 椭圆曲线密码系统。 e ( b ) 中的加法操作定义为： 对于所有p e ( 昂) 有：尸+ 护= 汐+ p = p 。 2 如果p = ( z ，y ) e ( b ) ，n ( x ，y ) + ( z ，一y ) = 护点( x ，一y ) f ( 昂) 记为一p 。 3 p = ( x l ，y 1 ) e ( 昂) ，q = ，y 2 ) ( 昂) ，其中尸o l j p + q = ( 玛，y 3 ) ( 点 加操作) ： z 3 = 九2 一z i x 2 ，y 3 = 3 , ( x l x 3 ) 一y 4 ，p = ( x l ：y i ) e ( f p ) ，j j p + p = 2 p = ( x 3 ，y 3 ) ( 此操作也称为点倍操作) 铲九2 2 x l , y 3 = 扛i 咱) - - y l , z - - 百3 x 2 + a 从上面的规则中可以看出，e ( f 口) 上的两个不同椭圆曲线点的加法操作需要 下列的一些算术运算( r 有限域中) ：一次求逆运算、两次乘法、一次平方和六 次加法。类似的，e ( r ) 上的点倍操作需要一次求逆运算、两次乘法、两次平方 i u t , 次加法。般来说，r 中的求逆运算是一个比较费时的运算，所以计算两个 椭圆点之和的一个替代方法是利用影射坐标。此时，次求逆运算被替换为乘 法运算和其它不那么费时的有限域运算。更详细的信息可以参考文献 7 2 。 第2 章崭铡协商介绍 2 , 3 1 2 f 2 m 上的椭圆曲线 有限域如m 上由参数日，b f 2 m ，b 0 定义的非奇异椭圆曲线，它包括了一 个特殊的无穷远点矽和满足下面式子的所有点p = 扛，y ) ，x , y f 2 一 与f i , 上的椭圆曲线类似，( f 2 m ) 上的椭圆点集合也可以构造出个阿贝尔群结 构。其加法操作的定义如f ： 1 对于所有p e ( f 2 0 ) 有：尸+ 扩= 扩+ p = p 。 2 如果尸= ( ，y ) e ( f 2 m ) ，n ( x ，y ) + ( x ，一y ) = 扩。点( ，- y ) e ( 兄m ) 也称为 点尸的负，记为p 。 第2 章密钊协商介绍 3 p = ( xl ，y t ) e ( f 2 一，) ：q = ( x 2 ，y 2 ) e ( v 2 ，n ) ，其中尸q ，i ) i j p + q = ( x 3 ，y 3 ) 妒舻+ 九- b x l + 托舻撕l + 犯) 怕十y l ，扣鬻 4 p = ( z i ，yj ) e ( 而m ) ，j j p + p = 2 p = ( x 3 ， ) ： = a 2 + 兄+ 口，”= 撕+ 妁) + 均+ y j ，a = 工l + 元x i 从上面的规则中可以看出，e ( 尼m ) 上的两个不同椭圆曲线点的加法操作需 要f 列的一些算术运算( f 2 一有限域中) ：一次求逆运算、两次乘法、一次平方和 八次加法。类似的，e ( 而，) 上的点倍操作需要一次求逆运算、两次乘法、两次平 方和六次加法。同样，而，。中的求逆运算也是一个比较费时的运算，所以计算两 个椭圆点之和的i 乜可以利用影射坐标法来得到更快的实现。更详细的信息町以 参考文献 7 2 1 。 o 第2 章拼钏协商介绍 2 , 3 1 3 枰肓圆曲线离散对数问题 已知e 的点q 是p 的倍数，求k z 使得q = k p ，这便是椭圆曲线的离散 对数问题( e c d l p ) 。可以证明由k 和p 计算q 比较容易，而南q 和p 计算k 则比较困难。e c d l p 是比整数因子分解问题i f p 和离散对数问题d l p 难得多的 数学难题。 e c c 既可以用于数据加密，也可以用于数字签名。 2 3 2 双线性对 在介绍双线性对之前，先介绍d d h i k ， 题；f d c d h 问题。 2 3 21d d h 问题和c d h 问题 g 是一个有着素数阶q 和生成元g 的循环群，n ，自，c 是z ：中的随机数。 d d h 问题( d e c i s i o n a ld i f f i e h e l l m a np r o b l e m ) g 中d d h 问题的概率多项式时间求解函数的输入是两个元组 ， ，结果是要区分这两个元组： a d v 嬲= p r 够( ， ) = 1 妊g ；a ，b ，c 尺z 圳 如果成功区分元组的概率a d v 是不可忽略的，则称d d h 问题是容易的，否则称 d d h 是困难的。 对于一般的有限域，由于n ，b ，c 的随机性，元组 和 是相互独立的，因此成功区分两个分组的概率是可忽略的，此 时d d h 问题是困难的。而在椭圆曲线中，由于下面将要介绍的双线性对所具有 的特殊性质，使得其中的d d h 问题是容易的( 见2 ，3 2 2 ) 。 c d h 问题( c o m p u t a t i o n a ld i f f i e h e l l m a np r o b l e m ) g 的( t ，) 一c d h 攻击者是一个概率函数算法，其运行时间是了1 ，输入为 ( g ，g a ，g b ) ，并至少以概率输出g ”。g 中c d h 问题的概率多项式时间求解函数 定义为： a “v c d ，g h = l p r g 曲_ ( g ，g ，g “，9 6 ) 1 9 g ；a ，6 rz 圳 如果g 中不存在( t ，) 攻击者，则c d h 问题是( t ，e ) 难解的。现在，人们 第2 章崧例协商介绍 普通认为c d h 问题是难解问题。 2 3 2 2 双线性对定义 假设g i 和g 2 是两个阶为q ( q 是一个大素数) 的群，则这个两个群上的双线 性对映射p ：g l g l g 2 必须满足下列性质： 双线性：我们称一个映射f ：g 1 g i g 2 具有双线性性质，如果对于所有 只q g l 和所有n ，b z ，它都满足等式e ( a p ，b q ) = e ( 只q ) ”。 非退化性：该映射不会把g lxg i 中所有的所有对都映射到g 2 的生成元 上去。实际上，由于g l ，g 2 的阶都是素数，从而使得如果p 是g l 的生成 元，则p ( 只p ) 就是g 2 的生成元。 可计算性：对于任意只q g l ，存在一个有效的算法可以计算出e ( 只q ) 的 值。 满足上述性质的群是真实存在的。比如，可以取群gn 为椭圆曲线e 昂上 的点形成的加法群的子群，而群g 2 取为有限域瓦z 上的乘法群的子群。往后， 可以将g 看称加法群，g 2 看成乘法群。 映射p ：g 1 g l g 2 的存在致导其d d h l l _ 3 题易解性：g 】中的d d h 问题就 是耍区分 和 ，其中a ：b ，c 是z q 中的随机数，p 也是随机在g l 中选取的。j o u x 和n g u y e n 5 8 】指出了d d h 问题在g j 中是易解 的。因为，给定只a p , b p , c p g i ，我们可以得到 c = a b m o d q 铮p ( 只c p ) = e ( a p , b p ) 4 i 过，g l 中的c d h 问题仍然是难解的。g l 中的c d h 问题就是，给定随机 的元组 ，耍计算出d 扫p 的值。j o u x 和n g u y e n 在文献嗍中给出了一 个映射e ：g 1 g l g 2 ，其中gj 的c d h 问题彼认为是难解的，虽然其d d h 问 题是易解的。 2 3 2 3b d h 假设 由于g l 中的d d h 问题是易解的，我们不能利用g 】中d d h 来建立密码系 统。但是，可以利用c d h 假设的一个变种：b d h 假设，来建立密码系统 1 2 星! 茎堂型塑：塑坌塑 b d t l 问题( b i i i b e a rd i 伯e - h e r m a np r o b l e m ) 令g l ，g 2 是两个阶为素数q 的群，e ：g l g l g 2 是。个双线性映刺，而 p 是g 1 的生成元。元组 中的b d h 问题是：给定 ， 其中日，b ，c 瑶，要计算的是w = g p ) 曲。g 2 。 一个算法被认为以优势求解出 中的b d h 问翘，如粜它 满足式子： p r ( p , a p , b p , c p ) = e ( 只p ) “如】 其概率是基于琶中d ，b ，c 的随机选择，g i 中p 的随机选择t 以及t 的随机比 特位的选择。 b d h 参数生成器 一个概率算法0 要成为一个b d h 参数生成器，则它需要满足： ( 1 ) 0 接受一个安全参数t z + ， f 2 ) 0 的运行时间为k 的多项式时间 ( 3 ) 0 输出一个素数q ，两个阶为q 的群g 1 ，g 2 的捕述t 双线性映射8 g l g l g 2 的描述。 我们记0 的输出为0 ( 1 ) = 。安全参数用来决定口的犬小， 比如，可以取日为一个随机的k 一位素数。对于i = 1 ，2 ，我们假定群g i 的描述包 括了的多项式时间算法用以计算g i 中的群动作，以及包括g ，的生成元。g i 的 生成元使得我们可以成生g i 中的随机元素。类似的，我们假定映射p 的描述包 括了一个计算e 的多项式时间算法。 b d h 难题假设 令0 是一个b d h 参数生成器，我们称一个算法以优势s 求解出b d h 问题( 对于足够大的女) ，如果算法满足： r a d 。，：p ，i ( q ，g 。，g 2 ，。，只。只b 只。_ p ) ：。( 只p ) “雠 p 。勺i 2s ) j p 。q ，4 ，自，。弓 j 第2 章密纠协商介绍 如果对于任意概率k 多项式时间算法，a d v 。( ) 都是可忽略的函数，我 们就称哆满足b d h 假发。而当0 满足b d h 假i 5 ； 时，我们就可以说由0 生成的 群组其b d h 问题是难解的。 b d h 的困难性 b d h 难题和密码学中的其它难题之间有着怎样的关系尼? 目前，我们可以 确定的是 中的b d h 问题不会比g i 或者g 2 中的c d h 问题更加难 解。换句话院，如果一个算法可以求解出g 1 或者g 2 中的c d h 问题，那么该算 法必然可以求解出 中的b d h 问题。这个命题的反命题现在仍然是 一个公开问题：即是否存在一个可以求解出b d h 问题的算法，此算法也可以求 解g i 或者g 2 中的c d h 问题? 2 4 密钥协商的发展现状 密钥协商得到了很大的发展。 2 4 1 双方密钥协商 第一个双方密钥协商协议是由d i f l i e 和h e l l m a n 4 1 】于1 9 7 6 年提出的，即著名 的d i f f i e - - h e l l m a n 协议。这个协议的提出开创了一个崭新的研究方向，促成了 后来众多的密钥协商叻、议的研究。由于该踟议没有提供认证性，从而会受到诸 如中间人攻击等攻击，于是围绕着提供认证性和其它方面的性质，人们提出了很 多的改进方案，不过大多数到后来都发现存在错误。 在前期提出的d i f i i e - - h e l l m a n 防议改进方案都是基于公钥证书的，其中比 较有名的是由m a t s u m o t o ，t a k a s h i m a 和i m a i ( 7 3 1 提出的m t i 方案，他们设计出了 三类无穷族的密钥 力、商协议，用来为传统的d i f f i e - - h e l l m a n 协议提供认证特性： 不过，他们的针对主动攻击的安全性分析是启发式的。l a w 【6 9 等人指出了m t i 方案中的一个错误，并提出了一个高效的认证密铡叻- 商铷议，即有名的m q v 踟 议，其针对于主动攻击的安全性分析也是启发式的。 后来，随着基于身份密码系统思想的提出，以及双线性对研究方面的进展， 人们利用双线性对提出了很多基于身份的密钥咖商机制。 借嚣于j o u x f 5 7 的三方d i f f i e - - h e l l m a n 胁议思想阱及b o n e h 和f r a n k l i n 在 1 4 第2 章耕引协商介绍 文献【1 7 中的思想，s m a r t 9 4 】提出了另外一个基于身份的认汪密钥协商方案。 该方案用到了w e f t 对，并要求所有的用户都是属于同个p k g 的范围之内。 该协议可必实现基于身份的高效密钥托管服务。在s m a r t 的基础上，c h e n 和 k u d l a 3 3 提出了一个效率更好的基于身份的密钥协商方案。他们提出一个机制 用于去除密钥托管，因为这在个人通信中由于更好的保密性而更受用户欢迎。他 们还提出了一利r 改进以保证当用户属于不同p k g 范围时电司以进行密钥协商。 然而，w a n g 1 0 i l 指出s m a r t 协议以及c h e r t k u d l a 协 义都有安全缺陷：s m a r t 协 议不能抵抗密钥显露攻击( k e yr e v e a l i n ga t t a c k s ) ，而且也不具备完全向前安全 性质：c h e n k u d l a 协议电不具备完全向前安全性质，而且其形式化安全性分析 有错误，协议也不能抵抗密钥显露攻击。 s c o t t l 8 7 在文献中提出了一个基于身份的密钥协商协议，其中每个用户选择 他自己的个人身份标识号码( p i n ) ，以及一个可信的第三方p k g 负责通过秘密 信道给每个用户发送各自的秘密。根据各自的秘密和p i n 数码计算出个数值， 并将此数值内置成为一个硬件令牌。这样，各自的秘密可以由他们自己的p i n 数码，身份标识和令牌重构出来。不过w a n g 在文献 1 0 1 中指出了在b r e s s o n 安 全模型下，s c o t t 协议是不安全的。 s h i m 8 9 也提出了一个基于身份的密钥协商j o l 匍j ，不过s u n 和h e i s h i o o l 指 出了s h i m 协泌是不安全的，冈为它不能抵抗中间人攻击。 m c c u l l a g h 和b a r r e t o ( 7 4 1 提出了另外一个高效的基于身份的认证密钥协商 协议。他们的协议可以工作在密钥托管模式下，也可以工作在非密钥托管模 式下，而且还可以实现不同p k g 范畴的用户的密钥协商。在不进行预计算的 条件下，这个方案的效聋墨是c h e n 和k u d l a 3 3 的方案的效；缸的两倍。不过很 快x i e 【1 0 3 指出该协议对于密钥泄漏攻击( k e yc o m p r o m i s ea t t a c k s ) 是不安全 的；c h o o