（计算机应用技术专业论文）两种前向安全的数字签名研究.pdf

摘要 文章的工作内容主要由两部分构成，第一部分主要是前向安全性在代理签名方 案中的应用算法研究：第二部分主要是前向安全性在聚集签名方案中的应用算法研 究第一部分改进了一般的代理签名方案，提出了前向安全代理，并给出了前向安全 的代理签名方案该方案具有两大优点：保护了被撤销的代理签名人，使被撤销前 的代理签名仍具有可验证性；新的方案具有较高的效率新的方案根据前向安全的 特性把原始签名人的密钥分成若干个时段，每个时段结束都要及时更新代理并通过 安全信道发给相应的代理人攻击者截获当前时段的密钥无法伪造之前时段的代 理，这样保证了之前时段的代理签名具有合法性，即前向安全性它被证明是基于强 r s a 假设安全的 文章第二部分内容主要研究一般的聚集签名方案如何结合前向安全的特性 2 0 0 7 年d im a 首次提出了前向安全的顺序聚集( f s s a g g ) 签名方案，每个时段对一 个大消息产生一个签名f s s a 9 9 签名方案不仅能够提高存储和通讯的利用率，而 且保证消息的完整性本文主要改进了f s s a g g 签名方案，使每个时段能够对多个 消息产生多个签名；同时，改进的方案把签名聚集算法分成了两个独立的算法这 样新的方案能够满足实时性和并发性要求，能够满足一些特殊无线传感器网络的需 求它被证明是基于双线性群上计算c o c d h 问题安全的 关键词：代理签名；前向安全；聚集签名；无线传感器；强r s a ；c o c d h 问题 a b s t r a c t t h i sp a p e ri sc o m p r i s e do ft w om a i ns t u d yi s s u e s t h ef i r s to n ei s s t u d y i n gh o w t o i m p l yf o r w a r ds e c u r i t yi n t on o r m a lp r o x ys i g n a t u r ea l g o r i t h m st oe n h a n c et h es e c u r i t yo f t h ea l g o r i t h m s t h en e ws c h e m ei m p r o v e st h en o r m a lp r o x ys i g n a t u r e s c h e m e ，p r o p o s e s an e wd e l e g a t i o nc a l l e df o r w a r d s e c u r ed e l e g a t i o na n d g i v e saf o r w a r d s e c u r ep r o x ys i g n a t u r es c h e m e i tp r o t e c t st h er e v o k e dp r o x ys i n g e sm a k i n gt h ep r i o rp r o x ys i g n a t u r e s e a s i l yv e r i f i e d t h i sn e ws c h e m ed i v i d e st h ev a l i d i t yt i m eo fak e yp a i ro ft h eo r i g i n a l s i g n e ri n t ot i m ep e r i o d s a tt h ee n do fe a c ht i m ep e r i o d ，t h eo r i g i n a ls i g n e rd e r i v e san e w s e c r e tk e yf r o mt h ec u r r e n to n ei na no n e w a yf a s h i o na n d u p d a t e st h ea c c o r d i n gp r o x i e s s oc o m p r o m i s eo ft h ec u r r e n tk e yd o e sn o te n a b l et h ea d v e r s a r yt of o r g ep r o x i e si nt h e p a s tp e r i o d s t h e r e f o r e ，t h ep r i o rp r o x ys i g n a t u r e sa r ep r o t e c t e d s e c u r i t yo ft h ep r o p o s e d s c h e m er e l i e so nt h es t r o n g r s aa s s u m p t i o n a n o t h e ri s s u ei ss t u d y i n gh o wt oi m p l yf o r w a r d - s e c u r i t yi n t on o r m a la g g r e g a t e s i g - - n a t u r ea l g o r i t h m st os a t i s f ys o m ew i r e l e s ss e n s o rn e t w o r k t h ep r o p e r t yo ff o r w a r ds e - c u r i t ya p p l i e di n t on o r m a la g g r e g a t es i g n a t u r es c h e m e sc a no f f e ro v e r a l li n t e g r i t yo ft h e s i g n e dm e s s a g e s ，w h i l ea g g r e g a t es i g n a t u r e sh a v et h e i ro w na d v a n t a g e so fs t o r a g e c o m m u n i c a t i o ne f f i c i e n c y t h i sn e w l yn o t i o nf i r s ta d v a n c e db yd im ac a l l e df o r w a r ds e c u r e s e q u e n t i a la g g r e g a t e ( f s s a g g ) s i g n a t u r ea n di tc a nw i d e l yu s e di na p p l i c a t i o no fw i r e - l e s ss e n s o rn e t w o r k b u ti tj u s tr e a l i z e ds c h e m e so fs i g n o n e m e s s a g ep e rt i m ep e r i o d ， w h i c hc a n n o ts u f f i c er e a l - t i m er e q u i r e m e n t i nt h i sp a p e hw e p r o p o s e dam o d i f i e ds c h e m e d e r i v e df r o mf s s a g g s i g n a t u r es c h e m ea n dc a l l e di ta sf o r w a r d - - s e c u r ea g g r e g a t i o no fs i g n a t u r e s ( s h o r tf o rf s a ) t h i sn e w l ys c h e m es e p a r a t e st h es i g n a n d a g g r e g a t ea l g o r i t h m i n t ot w od e p e n d e n ta l g o r i t h m sa n ds i g n sm e s s a g e sn o b o u n d a r yp e rt i m ep e r i o d i tc a n b eu s e f u li ns o m es c e n a r i oi nw i r e l e s ss e n s o rn e t w o r k ，s u p p l y i n gr e a l - t i m ea n db e t t e r c o n c u r r e n c y m e a n w h i l e ，i tc a nb ep r o v e ds e c u r eb a s e do nt h ei n t r a c t a b i l i t yo fc o c d h p r o b l e m k e yw o r d s ：p r o x ys i g n a t u r e ；f o r w a r d s e c u r e ； a g g r e g a t es i g n a t u r e ； w i r e l e s s s e n s o r ；s t r o n gr s a ； c o c d h 学位论文独创性声明 本人所呈交的学位论文是在我导师的指导下进行的研究工作及取得的研究成 果据我所知，除文中已经引用的内容外，本论文不包含其他个人已经发表或撰写的 研究成果对本文的研究做出重要贡献的个人和集体，均已在本文中作了明确的说 明并表示谢意 作者签名：雄巍亟 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或指定机构送交论文的电子版和纸质版有权将学位论文 用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文的 内容编入有关数据库进行检索有权将学位论文的标题和摘要出版保密的学位论 文在解密后适用本规定 学位论文作者签名：燃当 导师签名： 学位论文作者签各：槛毖 导师签名： 第一章绪论弟一早珀可匕 1 1 信息安全和密码学 2 1 世纪是信息化的时代，我们的社会也随之进入了一个崭新的时代，传统的 商务活动、事务处理以及政府服务越来越多地通过开放的计算机和通信网，如 i n t e r n e t ，特别是基于万维网的工具来实施和提供目前，通过在线完成的事例已有 很多，如人们日常生活中的银行业务、账单支付、网上购物、股票交易等，还有数 字图书馆、虚拟保密网、选举等等信息化的社会也意味着信息安全己成为人们 在信息化的时代中生存与发展的重要保证条件正如著名未来学家托夫勒曾经说过 的，在信息时代”谁掌握了信息，控制了网络，谁就将拥有世界”因此，近年来，密码 学和信息安全技术越来越受到人们的重视信息安全领域日益成为各国政府和相关 部门、企业关注的重要领域 信息安全作为一门学科，它是一门涉及计算机科学、网络技术、通信技术、密 码学、数论、信息论等多种学科的综合性学科信息的认证性和保密性是信息安全 在信息系统中的两个主要任务文献【4 】详细地解释了这两个任务认证有两个目的： 一方面要验证信息发送者身份的真实性，而不是他人冒充的；另一方面要验证信息 本身的完整性，也就是验证信息在存储或传送过程中未被篡改保密是为了防止攻 击者破译系统中的机密信息在众多信息安全技术中，密码学在保护信息安全的认 证性、机密性，解决信息安全问题等方面起着极为重要的作用 密码学是一门古老又年青的学科，是信息安全的基石它用于保护军事和外交 通信可追溯到几千年前，如著名的古典密码凯撒密码 5 】对当时的军事作出了重大 贡献密码学发展至今，其商用价值和社会价值也已得到了充分的肯定 密码学作为一门学科，它主要包括密码编码学和密码分析学这两个分支 4 文 献 4 】中对他们定义的描述如下：密码编码学是研究对数据进行变换的原理、手段 和方法的技术科学，其目的是隐藏数据的真实内容，以防止数据被无察觉的篡改和 非法使用密码分析学是为了取得秘密的消息，而对密码系统及其流动的数据进行 分析，是对密码原理、手段和方法进行分析、攻击的技术和科学密码编码学和密 码分析学两者之间既存在矛盾，又相互促进发展 1 2 数字签名研究背景第，一章绪论 1 2 数字签名研究背景 政治、军事、外交等活动中签署文件，商业活动中签定契约和合同，以及日常 生活中在书信、从银行中取款等事务中的签字，传统上都采取手写签名或印鉴签 名具有认证、核准和生效等主要功能随着信息时代的到来，人们希望通过现代通 信网进行远距离、迅速的贸易合同的签名，因而数字或者电子签名应运而生，并开 始用于商业通信系统，诸如电子转账、电子邮件、办公室自动化等系统数字签名 是实现签名消息以电子形式存储的一种方法，电子签名消息可以在一个通讯网络中 传输因此，数字签名是现代通信中实现消息认证的一种重要手段数字签名是对传 统手写签名的模拟，在实现身份认证、数据完整性、不可抵赖性等方而有着重要应 用同时，公钥密码体制的诞生为数字签名的研究和应用开辟了一条广阔的道路 近年来，随着数字签名被不断地深入研究，以及电子商务、电子政务这种事务 处理模式的快速发展，数字签名已经从最初的普通签名发展到了多用途、多领域的 特殊签名，这些特殊签名主要集中于基于公钥密码体制的数字签名的研究比较典 型的特殊签名有：前向安全的数字签名、代理签名、门限签名、群签名、盲签名 等数字签名标准和数字签名法的制定也给数字签名的发展创造了优势的条件 1 3国内外研究现状 1 3 1 数字签名的发展 在公钥密码体制中，一个主体可以使用自己的私钥”加密”消息，所得到的”密 文”可以用该主体的公钥”解密”来恢复成原来的消息而且，任何人都可以得到公 钥，可以执行公钥”解密”的验证过程，然而，只有主人才能用相应的私钥得到”密 文”因此，公钥密码可以用来实现数字签名机制1 9 7 6 年d i f f i e 和h e l l m a n 利用公 钥密码学的思想首次提出了数字签名的概念 1 】随后产生了很多数字签名体制，其 中有几个著名的数字签名体制如1 9 7 8 年r i v e s t 、s h a m i r 和a d l e m a n 给出了第一 个r s a 签名方案【6 】，该方案基于大整数分解困难性，同时构造了著名的r s a 公钥 密码方案，因此他们共同获得2 0 0 2 年图灵奖的殊荣1 9 7 9 年r a b i n 提出的以奇整数 为验证指数的r a b i n 签名体制 3 】1 9 8 5 年e 1 g a m a l 设计了一个精巧的数字签名体 f l ；r j 9 e 1 g a m a l 签名体制也是许多其他签名体制的起源，包括最有影响力的两个变 型：s c h n o r r 签名体制【7 ，8 1 和美国数字签名标准( d s s ) 1 0 ，1 1 1 随着对数字签名研究的不断深入，以及电子商务、电子政务这种事务处理模 式快速发展，近十年来密码学领域提出了许多具有特殊性质或特殊功能的数字 签名，在1 9 8 2 年c h a u m 提出并构造了盲签名体制( b l i n ds i g n a t u r e ) 1 2 ；在1 9 8 3 年 2 1 3 国内外研究现状第一章结论 i t a k u r a 首次提出多重数字签名( m u l t i s i g n a t u r e ) 1 4 的概念：在1 9 9 1 年d e s m e d t 和 f r a n k e l 引入了门限签名的概念( t h r e s h o l ds i g n a t u r e ) 1 3 ；在1 9 9 6 年m a m b o ，u s u d a 和o k a m o t 引入了代理签名( p r o x ys i g n a t u r e ) j 3 8 1 3 2 前向安全数字签名的提出和研究现状 一般地，数字签名方案的安全性包括两个方面：签名算法的安全性，通常是指 签名算法能够抵抗各种密码分析方法，就算法本身的逻辑以及其基于的难解问题是 不可攻击的随着数字签名研究的不断发展前进，一些著名的算法已被证明是安全 性、不可攻破的，从来我们可以保证签名方案算法的安全性另一方面是签名密钥 的安全性，通常是指防止签名密钥的泄漏如果签名密钥泄漏了，攻击者就可以使用 被泄漏的密钥来伪造签名，那么即使它的算法是安全的，但这样的数字签名方案还 是不安全的，不可信赖的因此，对于某个既定的数字签名算法，最大的安全隐患就 是签名密钥的泄漏问题因而，如何解决签名密钥的泄漏问题成了当前数字签名 的研究热点之一 一般而言，传统的数字签名总是存在着一个致命的弱点：如果私钥泄漏，则用该 私钥完成的签名，无论该签名是泄漏前产生还是泄漏后产生的，都变得不可信赖由 于私钥的丢失，导致签名人无法向验证者证明，哪些文件是由真正的签名人产生的， 哪些是由攻击者产生的签名基于上述问题，研究如何防止密钥的泄漏，以及如何减 少密钥泄漏带来的损失，显得十分必要通常，我们通过两种方法来解决密钥泄漏的 问题 1 一种广泛应用于解决签名密钥的泄漏问题的方法是分布式密钥共享方案，一 般采用秘密分享的方式实现门限签名算法就是一种利用分布式密钥共享技 术实现的签名算法，提高了系统的安全性和健壮性 2 另一方面，a n d e r s o n 于1 9 9 7 年提出在数字签名里增加前向安全性的属性【1 6 】， 来降低私钥泄漏以后的损失前向安全的主要思想是把密钥对的合法时间分 成若干个时段t ；在每个时段结束时，签名人根据当前的密钥产生下一时段 的密钥，并安全地删除当前时段的密钥因此，当前时段密钥的泄漏不能让攻 击者得到之前时段的密钥，即单向不可逆性自此，前向安全的数字签名成了 另外一种减少密钥泄漏带来的潜在损失的方法 前向安全的概念是在一篇关于密钥交换协议的文献【1 5 】中首次提出的后来， 前向安全被运用于数字签名来减少密钥泄漏带来的潜在风险a n d e r s o n 首次构造 了一个前向安全的数宁签名方案 1 6 】1 9 9 9 年，b e l l a r e 和m i n e r 给出了正式的前向 3 1 4 论文的主要i 作第一章绪论 安全定义和前向安全性的安全模型的形式化定义，并构造了可实施的前向安全数字 签名方案【1 7 】近十年，许多学者对这一领域的快速发展做出了贡献 一方面，比如a b d a l l a 和r e y z i n 提出了一个新的前向安全签名方案【2 0 】，并且 基于o n g s c h n o n 签名体制该方案大大地缩短了b e l l a r e 和m i n e r 签名方案的公 私钥的长度i t k i s 和r e y z i n 则提出了另外一种前向安全的签名方案 1 9 】，主要基 于g u i l l o u q u i s q u a t e r 签名体制该方案的主要优点是的密钥长度比较短。而且签 名和验证算法具有相当高的效率k o z l o v 和r e y z i n 在a b d a l l a 和r e y z i n 构造的方 案 2 0 1 的基础上提出了一个快速密钥更新的方案 2 1 1 ，来提高前向安全数字签名方 案的效率b o y e n 等人则构造了一个在不可信环境下的前向安全方案 2 2 1 ，方案增加 了一个用户密钥作为安全要素，它和当前时段的密钥一起使用才能完成签名算法 因此，该方案的密钥更新算法可以在不可信环境下更新密钥，使得前向安全的数字 签名可以与一些安全软件的构造兼容，如g n up r i v a c yg u a r d ( g p g ) 和s m i m e 另一方面，前向安全性被结合于其他特殊签名方案，提高其他签名方案的健壮 性，如前向安全的代理签名、前向安全的门限签名、前向安全的盲签名等等如： 2 0 0 1 年a b d a u a 、m i n e r 等人构造的前向安全的门限签名【2 5 ，加强防止密钥的丢失 措施，同时使用前向安全性减少密钥丢失后带来的损失2 0 0 3 年d u c 等人构造了基 于强r s a 假设的前向安全的盲签名方案【2 7 】，应用于电子现金和电子支付 1 4 论文的主要工作 随着b e l l a r e 和m i n e r 于1 9 9 9 年首次构造出前向安全签名以及给出其形式化的 安全性证明近几年，前向安全性被运用到各个具有特殊性质的签名方案中，如代理 签名、门限签名、盲签名、聚集签名等本文在前人的基础下，主要研究前向安全 性运用于代理签名方案和聚集签名方案具体工作如下： 1 一般代理签名方案存在一定的安全性隐患，如代理签名权的滥用为解决此 问题，一般代理签名方案都增加了一个代理撤销协议但是这只保护了原始 签名人的权利，代理签名人的一些权利得不到保障，如代理签名人生成的合 法代理签名也因代理人被注销而作废本文把k o z l o v 等人提出的前向安全签 名方案【2 1 】中的方法运用到代理签名方案中产生代理的算法，保障了代理签 名人的部分权利，其次原始签名人也无需因一个恶意的代理签名人而更新其 他代理签名人的公私钥对其前向安全性主要基于强r s a 假设原理，我们通过 p o i n t c h e v a l 和s t e m 提出的交叉引理 2 8 】在随机预言机下证得同时，我们也 证明了方案具有不可伪造性、可验证性、不可否认性、可区分性、代理签名 人的不符合性和可识别性的安全特性最后，我们还对方案作了效率分析 4 1 4 论文的i 要i 作第一章绪论 图1 1 ：s e n s o rn e t w o r k 2 无线传感器网络有着十分广泛的应用前景，如军事、地震监测、水质监测等 等，但由于技术等方面的制约大规模的商业应用还有待时日本文关注信息安 全技术在无线传感器网络的应用，特别是数字签名技术2 0 0 7 年d im a 等人构 造了具有前向安全性的聚集签名( f s s a g g ) 应用于无线传感器网络 4 4 】本文 在此基础上，改造了f s s a g g 签名方案，主要目的是实现s i g n m a n y 的要求，即 每个时段可以对多个消息生成多个签名，不需要等到某个时段的最后一个消 息聚集到大消息时才能执行签名算法，满足了实时性的要求新方案主要基于 b l s b g l s 签名方案，安全性的证明主要基于双线性群上计算c o c d h 困难 另外，我们改造签名算法和聚集算法，使它们和普通的聚集签名方案中一样是 两个独立的算法这样，除了签名人，任何人( 结点) 都可以参与聚集的过程，提 高了并发性因此，我们构造的新方案可以适合一些特殊的传感器的应用背 景如图1 1 ，一个末端传感器节点聚集消息并产生签名，发送给中间传感器节 点a 然后，传感器a 接收到一个签名就执行聚集算法，一旦接收端结点b 请 求通讯时，就把当前聚集的签名发送过去这样就能满足实时性的要求同时， 我们把第一种策略运用到本方案的末端传感器节点，当与传感器a 通讯时， 对当前收集到的所有消息作为一个大消息进行签名，再发送过去消息在本方 案中无论是在同一时段还是不同时段，都是可重复的 5 1 5 本文组织结构第r 一章绪论 1 5 本文组织结构 本文研究了两种具有特殊性质的前向安全数字签名，包括具有前向安全特性的 代理签名和前向安全的聚集签名 第一章简要介绍了数字签名，其次分析了前向安全数字签名的研究背景和研究 现状，最后简要介绍了本文主要研究工作和章节安排 第二章首先介绍了密码学上的一些困难问题，接着介绍了公钥密码体制和数字 签名技术，最后简要地介绍了几种经典的数字签名方案 第三章简要介绍了前向安全特性和前向安全数字签名体制，然后介绍了代理签 名的定义、分类和安全性要求，最后详细介绍了作者提出的一种新的具有前向安全 特性的代理签名方案，包括其研究背景、方案和安全性分析 第四章简要介绍了聚集签名的由来和定义，然后详细地介绍了m a d i 的前向安 全的顺序聚集签名方案，并提出本文作者改进的新方案，给出了新方案的定义和安 全攻击模型，详细地描述了具体的新方案，最后给出了详细的安全性证明 第五章总结全文，并展望了后续的研究前景。 6 第二章基础i i i 知识 弟一早 荃们大u 以 本章将介绍与本论文密切相关的密码学中的困难问题和密码学理论基础，详细 地介绍几种著名的公钥密钥体制接着，简要介绍数字签名的相关概念，并详细地描 述基于著名公钥密钥体制的几个著名的数字签名体制 2 1 常见的困难问题 像大整数分解、素数检测、开方求根等，这类问题的求解运算在现代密码学中 经常遇到这些也是数论中令人感兴趣的课题本节我们学习密码学原理中基于上 述问题的难解性问题 3 3 1 ，如整数分解问题、r s a 问题、离散对数问题等，它们是 现代密码学的重要基础下面详细描述这些困难问题的定义或假设 2 1 1r s a 问题 整数分解问题 定义2 1 1 整数分解问题fi f 问题j 是指在选择适当参数的条件下给定奇合数r 至少有两个素因子上输出素数p 满足p i n 假设2 12 整数分解假设ri f 假设j 是指一个整数分解器是一个尸p 丁算法a 满足概 率e o ? e = p r o b a ( n ) 整除n ，1 0 7e = p r o b m 卜a ( n ，e ，m 8 ( r o o d ) ) 】其中4 的输入由定义2 j 3 确定令g 是整数生 成器，输入1 岛，在k 的多项式时间输出? f 力一个2 后比特的模n = p g ，其中p 和g 是 两个不同的均匀分布的素甄长度均为k 比特? f ，卅e z 一1 ) ( 口一1 ) 我们说对满足 r s a 假设，如果对于所有充分大的k ，对于k 不可忽略的概率e 0 ，不存在由g ( 1 七) 所产生的r s a 问题的求解算法 假设2 1 5 强r s a 问题是指给定一个r s a 模n = p 1 p 2 和一个随机数v z ，计算 z z 和r l ，满足矿三 3 ( m o d ) 假设2 1 6 强r s a 假设最早是由文献1 4 2 , 4 3 提出来的一个p p 丁算法a 即在不知 道因子分解的情况下，计算强r s a 问题是困难的文献口7 7 通过两种方式对这个 假设进行改进假设p 1 和p 2 都是安全素数，即满足p i = 2 吼+ 1 ，其中吼是素数， i = 1 2 2 1 2 离散对数问题 定义2 17 离散对数问题fd l 问题，是指在有限域中给定9 和玩其中d e s c ( f ：) 是一 个对有限域f g ) 的描述，g f ；是翳的一个生成元，he u 最后计算出唯一的整 数a o ? e = p r o b 1 0 9 ：卜4 ( k ) ，g ，乩其中a 的输入由上述定义 确定令g 是一个实例生成器，输入1 七，在k 的多项式时间内运行，输出md e s c ( f q ) ， 其中l g l q = k ，f 训一个生成元g 略，r i i i ) h k 我们说g 满足离散对数纠假 设，如果对所有足够大的对于k 不可忽略的概率e 0 ，不存在由g ( 1 后) 所产生 的d l 问题的求解算法 2 1 3 双线性映射 m e n e a e s ，q k a r n a t o 和v a n s t a n e 2 9 给出了定义在有限域上的一类特殊的椭圆曲 线，存在一个有效算法，将曲线( 在有限域上) 上的两点映射到基域中的一个元素这 类特殊的曲线被称为超奇异曲线w 色i l 对和t a i l 对是典型的超奇异曲线 双线性映射 首先，我们回顾一下双线性对的基本概念令g ，和g 2 分别为阶数为素数q 的 加法循环群和乘法循环群再令p 为g 1 群的生成元假设g 1 和g 2 这两个群中的 离散对数问题都是困难问题双线性对的概念有以下几点构成： 8 2 2 公钥密码体制第二章基础知识 ( 1 ) g 1 和g 2 是两个阶数为素数q 的乘法群； ( 2 ) 夕1 是g 1 群的生成元，夕2 是g 2 群的生成元； ( 3 ) 妒是一个从g 2 群映射到g 1 群的同构算法，即矽( 9 2 ) = g x ； ( 4 ) 双线性映射e ：g 1 g 2 一g r 双线性对满足上述几点概念，对于双线性映射e ：g 1xg 2 _ g t 具有一些特 殊性质： ( 1 ) 双线性性：对于所有的x g 1 ，y g 2 以及a ，b z ，存在等式e ( x 。，y 6 ) = e ( x ，y ) 0 6 ； ( 2 ) 非退化性：e ( g l ，9 2 ) 1 我们可以用超奇异椭圆曲线上的w r e i l 对或经改造的t a t e 对来构造双线性对 在这样的群g 1 上，我们可以定义以下几个密码学问题： 定义2 19 ( g 1 ，g 2 ，e ) 中的计算c o - d i f f i e h e l l m a n ( c o c d h ) 问题是指给定9 2 ，鳄 g 2 ，h g 1 来计算h o g 1 定3 ( 2 1 1 0 ( g 1 ，g o ，e ) 中的判定c o d i f f i e h e l l m a n 问题( c o - d d h i 题) 是指给定 9 2 ，鳢g 2 ，h 2 ，h 2 g 1 ，判定a = b 是否成立 注：当g 1 = g 2 时，上述问题就是标准的c d h 问题和d d h 问题 定义2 1 1 1 间隙c o d i f f i e h e l l m a n 问题是指这样一类问题，在群( g 1 ，g 2 ) 上，给 定渤，鳢，h 2 ， 2 ) ，容易判定a 三bm o dq 是成立的，但是计算h 口是困难的，换句 话说在群( g 1 ，g 2 ) 上，c o d d h 易于解决而c o c d h 难以解决，则称此群为间隙 c o d i f f i e h e l l m a n 群，简记为c o c d h 群 在本文中，我们认为在对映射可以有效计算的”弱”椭圆群中，判定c o d i f f i e h e l l m a n 问题( c o d d h 问题) 是容易的，然而计算c o d i f f i e h e l l m a n 问题( c o c d h 问题) 是困难的 2 2 公钥密码体制 早期的密码( 如著名的凯撒密码) 依赖于对整个加密过程的保密现代密码，像 d e s 和a e s 遵循k e r c h o f s 原则：公开算法的细节验证这些密码的安全性1 9 7 6 年 d i f f i e 和h e l l m a n 首先实现了这一点，并称之为公钥密码学，是密码学的一个重大成 就在公钥密码体制中，加密不用秘密钥，秘密钥仅在解密阶段使用 9 2 2 公钥密码体制第二章基础知识 公钥密码体制必须有两个不相同的密钥，秘密钥被称为私钥，如同对称密码体 制，秘密钥是被秘密保存的另外一个密钥被称为公钥，不言而喻即公开的在公钥 密码体制中，我们知道公钥要确定私钥，这在计算上是不可行的一般地，我们通过 单向陷门函数来实现公钥密码的数学变换 公钥密码体制一般用于实现多个用户的信息只能由一个用户解读，即加密模 型它主要应用于公共网络中实现保密通信，如图2 2 ，存在这样的情况，用户a 发送 消息m 给用户b 加密过程如下： 1 用户b 首先需要产生一对密钥p k b ，s k s ，其中p k b 是公钥，s k s 是私钥 2 a 利用用户b 的公钥p k b 加密消息m ，表示为c = e , k 日( m ) ，其中c 是密文， e 是加密算法 3 用户b 收到密文c 后，用它的私钥s k s 来解密，表示为m = d 。k b ( c ) ，其中d 为解密算法如果不知道s b 则无法对c 进行解密，而私钥s 蛔只有b 知道 明文m 公钥p k b私钥s k b 明文m ab 图2 2 ：加密模型 公钥密码体制的另一种逆向的应用是一个用户加密消息而由多个用户解读，即 认证模型它主要用于认证系统中对消息进行数字签字，如图2 2 ，假定用户b 对用 户a 发送的消息m 进行认证。认证过程有以下几个步骤： 1 用户a 产生一对密钥p k a ，s k a ，其中p k a 表示公钥，s k a 表示私钥。 2 用户a 用自己的私钥s k a 对消息m 加密，表示为c = 忍“( m ) ，将c 发给用户 b 3 用户b 用a 的公钥p k a 对密文c 解密，表示为m = d 砧a ( c ) 。 因为从m 得到的密文c 是通过用户a 的私钥s k a 加密产生的，只有用户a 才 能实现这个过程所以密文c 可以当做a 对消息m 产生的数字签名除此之外，任 何人不能篡改消息m ，除非他能够得到用户a 的私钥s h 因此，以上过程实现了 对消息米源和消息完整性的认证 1 0 2 2 公钥密码体制第二章基础知识 明文m 私钥s k a公钥p k a 明文m ab 图2 3 ：认证模型 下面，我们详细地介绍两个著名的公钥密钥体制，r s a 密码体制和e 1 g a m a l 密 码体制 2 2 1r s a 密码体制 r s a 是最熟悉的公钥密码体制中最负盛名的密码体制，以它的发明人r i v e s t 、 s h a m i r 和a d l e m a n 的名字命名【6 】r s a 是基于d e f i l e 和h e l l m a n 所想像的单向陷 门函数的定义【1 】，给出的第一个公钥密码的实现 r s a 密码体制具体算法的描述如下： 密钥建立 1 随机选择两个大素数p 和口； 2 计算n = p 口； 3 计算( ) = 一1 ) ( 口一1 ) ； 4 随机选择整数e ，1 e 妒( ) ，满足g c d ( e ，( ) ) = 1 ； 5 计算e 模( ) 的乘法逆元d ，即满足ed = 1m o d ( ) ； 6 公开公钥为( e ，) ，安全地销毁p ，q 和( ) ，并保留d 为私钥 加密 消息m ( ) ，计算密文c = m 8m o dn 解密 密文c ，解密密文m = c dm o dn 2 3 数字签g 技术第二章基础知识 2 2 2e l g a m a l 密码体制 e 1 g a m a l 设计了一个巧妙的密码体匍j 3 2 1 ，这个密码体制是d i f f i e h e l l m a n 单向 陷门函数的一个成功应用，把函数转化成公钥加密体制e 1 g a m a l 密码体制在密码 学研究中占有重要地位，是除r s a 体制外另一个目前仍认为安全的、既可用于加 密又可用于数字签名的公钥密码体制基于身份的e 1 g a m a l 加密体制和具有可证 明强安全性的一个变形是e l g a m a l 密码体制的两大关键性的发展。 e 1 g a m a l 密码体制算法的具体描述如下- 密钥建立 1 随机选取一个大素数p ，并且计算乘法群召的某个生成元夕； 2 随机选取z 彩为私钥，计算可= g 茹r o o dp ； 3 公开公钥为，9 ，箩) 加密 消息m ( p ) ，随机选择k 召，计算密文 c 1 = g 知r o o dp c 2 = m 矿m o dp 解密 密文( c l ，吻) ，解密密文m = c 2 赁 2 3 数字签名技术 数字签名技术由公钥密码技术发展演变而来，它在网络安全，包括身份认证、 不可否认性、数据完整性以及匿名性等方面有着非常重要的应用我们将介绍数字 签名的形式化定义和几个著名的数字签名方案 2 3 1 数字签名的形式化定义 一个签名方案至少满足以下三个条件：( i ) 签名者事后不能否认自己的签名； ( i i ) 接收者能验证签名，任何其他人都不能伪造签名；( i i i ) 当双方对签名的真伪发生 1 2 2 3 数字签名技术第二章基础知识 争执时，仲裁者能解决双方之间的争执其中第一个条件称为刁 可否认性，在电子商 务中是必不可少的安全要求签名方案普遍都基于某个公钥密码体制，签名者用私 钥对消息进行签名，验证者用相应的公钥对签名进行验证 数字签名体制的形式化定义【3 3 】是数字签名的一种抽象和概括( 见图2 3 1 ) ，一 般由以下部分组成： 数字签名体制的基本参数( m ，s ，瓦，庀，) ，其中m 为明文消息空间；5 为签名 空间；咒为签名密钥空间和j i c 7 为认证密钥空间 一个有效的密钥生成算法g e n ：n _ 瓦j i c 7 ，其中) l c 和瓦7 分别是私钥和公钥 空间 一个有效的签名算法s i g n ：对任意的s k j i c 和任意的m m ，签名变换为 o r = s i g n 。詹( m ) ，o r 是用密钥s 七生成的m 的签名 一个有效的验证算法v e r i f y ：对于任意的私钥s k j i c ，用础表示与s 七相匹配 的公钥对于m m 和盯es ，必有 、l t r u e ，o r = s i g n s 七( m ) v e r i f y p k ( m ，o r ) = “”7 lf a l s e ， o r s i g n s 知( m ) ， p k 签名者验证者 图2 3 1 ：数字签名体制 t 扎e 压k d s e 2 3 2 几个著名的数字签名方案 下面我们介绍四个著名的数字签名体制，r s a 签名体制、e 1 g a m a l 签名体制、 s c h n o r r 签名体制以及c o c d h 签名体制 r s a 签名体制 r s a 签名方案是d i f f i e 和h e l l m a n 提出数字签名思想后第一个较完善的数字 签名体制 4 】 1 3 2 ，3 数字签名技术第二章基础知识 r s a 签名体制具体算法的描述如下： 1 密钥建立 该过程可参见公钥密码体制r s a 密码系统的密钥建立过程，n = pq ， ( ) = p 一1 ) ( 口一1 ) ，公钥为( e ，) ，私钥为d ，并且满足ed = 1m o d ( ) 2 签名生成： 用私钥d 对消息m 生成签名o r = m dm o dn 3 签名验证 收到消息一签名对( m ，盯) 后，用公钥( e ，n ) 验证m = 盯em o dn 是否成立若 验证等式成立，表示签名有效；否则签名无效 e i g a m a l 签名体制 e i g a m a l 签名体制是许多其他数字签名体制的来源，这些签名体制都属于类 e 1 g a m a l 签名体制族最有影响的两个变型是s c h n o r r 签名体制【7 ，8 】和美国数字签名 标准( d s s ) 1 0 ，1 e 1 g a m a l 签名体制具体算法的描述如下： 1 密钥建立 选择一个大素数p ，g 是乘法群纬的一个生成元，随机选择z 彩为私钥，计 算y = g 茁m o dp ，公钥为三元组( g ，可，p ) 2 签名生成 设m 为待签名的消息，随机选择k z ：，计算 r = g 七m o dp 仃= k - 1 ( m z 木r ) m o d 一1 ) ( r ，口) 为消息m 的签名 3 签名验证 验证者根据公钥( 夕，y ，p ) 和m ，验证等式旷7 口兰g m m o d p 若验证等式成立， 则签名有效；否则签名无效 1 4 2 3 数字签名技术 第二章基础知识 s c h n o r r 签名体制 s c h n o r r 签名体制是e 1 g a m a l 签名体制的一个变型，但它本身具有一个特点： 可以大大地缩短素数域元素的表示，而不降低困难问题的难度这是对公钥密码学 的一个重要贡献这个思想后来发展成为更一般形式有限域的一种新的密码系统： x t r 公钥系统 3 1 】。 s c h n o r r 签名体制具体算法的描述如下： 1 密钥建立 随机选择两个大素数p 和口，满足口i p 一1 ；选择q 阶元素y 缉，设置夕口= 1 m o dp ；建立一个密码杂凑函数h ： o ，1 ) + hz p 随机选择z z ：作为私钥，并计算可= 旷m o dp ，公钥为( p ，口，9 ，可，h ) 2 签名生成 设m 为待签名的消息，随机选取后z ：，并生成一个签名对( e ，) ： r = 矿m o dp e = 忍pi im ) 盯= ( 七+ z 车e ) m o dq ( e ，盯) 为生成的签名 3 签名验证 验证者计算r = y y 8m o dp 和e = 危( r ，| im ) 若e = e 7 成立，表示签名有效， 否则签名无效 c o c d h 签名体制 c o c d h 签名体制是2 0 0 1 年b