（系统分析与集成专业论文）两类在线离线数字签名方案的设计与应用.pdf

s u b j e c t ： t u t o r ： a u t h o r ： i n f o r m a t i o ns e c u r i t yt e c h n o l o g y p r o f z h i b i nl i c h a ol u 2 0 1 0 0 4 华东师范大学学位论文原创性声明 个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均 已在文中作了明确说明并表示谢意。 位期 东师 作者签名：2 丝 日期：纱，口年乡月多矿日 华东师范大学学位论文著作权使用声明 学 垡 并 向主管部门和相关机构如国家图书馆、中信所和”知网”送交学位论文的印刷版和 电子版；允许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校 将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的 标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的”内部”或”涉密”学位论文：c ， 于年月日解密，解密后适用上述授权。 ( 、) 2 不保密，适用上述授权。 导师签名：本人签名：超 奶如年亨只3 ob 宰”涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过 的学位论文( 需附获批的华东师范大学研究生申请学位论文”涉密”审批表方为有 效) ，未经上述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公 开学位论文，均适用上述授权) 。 卢超硕士学位论文答辩委员会成员名单 姓名职称单位备注 顾国庆研究员华东师范大学 主席 王新伟副教授华东师范大学 李明教授华东师范大学 摘要 数字签名是一种重要的网络安全技术，可提供身份认证，数据完整性，不可否 认性等安全服务。移动自组网络中存在多种路由解决方案，例如无线自组网按需平 面距离矢量路由协议a o d v ，以及动态源路由协议d s r 。但这些方案的设计都没 有考虑安全问题，例如网络节点的认证。因此可在路由方案中应用数字签名技术以 提供安全服务，但是数字签名直接应用于移动自组网络时存在以下问题：( 1 ) 普通 签名所需计算量大，但是移动设备计算能力差；( 2 ) 多个节点对同一消息签名时，签 名数量会随着经过节点数目的增加而增加，相应的验证时问也会增加；( 3 ) 网络中 有新节点加入时，现有的其它节点需要更新其公钥列表：由于节点可能会随时地、 频繁地加入，引起公钥列表的更新可能十分频繁，对网络造成较大负担。 针对问题( 1 ) 、( 2 ) ，研究在线离线多签名，它结合了在线离线签名、以及多签 名的特点，使得多个用户对同一个消息，能够快速地生成一个多签名，验证者据此 签名可以确定签名者的身份。签名生成过程中所需的大部分运算都在签名的消息 给出之前进行，即进行预运算；在给出消息之后，只需进行行少量运便可算得出签 名，这样可以解决问题( 1 ) 。有多个用户来签名时，单个多签名取代了佗个签名者生 成的n 个签名，只需进行一次验证，这样可以解决问题( 2 ) 。本文将在g u o 等人给出 的在线，离线签名方案的基础上，运用l u 等人构造多签名的方法，提出一个在线离 线多方案，并在标准模型下，证明该方案的安全性可规约到计算性d i f f i e h e l l m a n 问题。接着讨论动态源路由协议d s r 及其安全需求，并给出方案在动态源路由协 议d s r 上的应用。 第二个方案提出了有助于解决问题( 1 ) 和( 3 ) 的基于身份的在线离线签名，它 结合了基于身份的密码体制和在线离线签名的优点：消除了公钥证书；收到消 息之前进行离线阶段的预运算，消息到来后能够迅速地生成消息的签名。对于新 节点的加入，现有节点不需要更新公钥列表从而解决了问题( 3 ) ；消息到来后签名 的生成也不需要进行大量的运算，解决了问题( 1 ) 。在随机预言机模型下，基于强 d i f f i e h e l l m a n 问题，证明方案的安全性满足在适应性选择消息和身份攻击下的存 在性不可伪造。相对与已有方案，其签名验证算法只需要一次配对运算，因此具备 更高的效率。最后讨论了方案在在无线自组网按需平面距离矢量路由协议a o d v 上的应用。 关键词：签名，基于身份签名，在线离线签名，多签名，双线性配对，强d i f f i e h e l l m a n 问题，c d h 问题 a b s t r a c t a sa ni m p o r t a n tn e t w o r ks e c u r i t yt e c h n o l o g y , t h ed i g i t a ls i g n a t u r ec a np r o v i d es e c u r i t ys e r v i c e s 。s u c ha st h ei d e n t i f i c a t i o n ，t h ei n t e g r i t y , t h en o n r e p u t a t i o n ，a n ds oo n f o rt h er o u t i n gi nm o b i l ea dh o cn e t w o r k s ( m a n e t ) ，t h e r ea l es o m ek i n d so fs o l u t i o n s ， s u c ha sa dh o co n d e m a n dd i s t a n c ev e c t o rr o u t i n g ( a o d v ) ，a n dd y n a m i cs o u r c er o u t i n g ( d s r ) b u tt h ed e s i g n sd o n tt a k et h es e c u r i t yi n t oa c c o u n t ，s u c ha sa u t h e n t i c a t i o n s t h e d i g i t a ls i g n a t u r e sc a n b eu s e di nr o u t i n gp r o t o c o l st op r o v i d es e c u r i t ys e r v i c e s b u tt h e r e a l es o m ep r o b l e m sw h e nt h et e c h n i q u e sa r ea d o p t e db yt h em a n e t ：( 1 ) t h em o b i l ed e v i c e sd o n th a v ee n o u g hc o m p u t a t i o n a la b i l i t y , w h i l ei tn e e d st o om a n yc o m p u t a t i o n st o g e n e r a t eo n es i g n a t u r e ；( 2 ) w h e nm u l t i p l eu s e r ss i g no nt h es a m em e s s a g e ，t h en u m b e ro f s i g n a t u r e sw o u l di n c r e a s ea st h en o d e si n c r e a s e s ，a n dt h ev e r i f y i n gt i m ew o u l di n c r e a s e s a l s o ，( 3 ) w h e nan e wn o d ej o i ni nt h en e t w o r k ，t h eo t h e rn o d e sh a v et ou p d a t et h e i rp u b l i c k e yl i s t s ；t h en e wn o d e sm a yj o i ni nt h en e t w o r ka ta n yt i m ea n df r e q u e n t l y , s ot h eu p d a t e m a y b ef r e q u e n ta n dr e s u l t si nh e a v yb u r d e nf o rt h em a n e t f o rt h ef i r s ta n ds e c o n dp r o b l e m s ，w es t u d yt h eo n l i n e o f f l i n em u l t i s i g n a t u r es c h e m e a st h ec o m b i n a t i o no fo n l i n e o f f l i n es i g n a t u r ea n dm u l t i s i g n a t u r e ，i ta l l o w sm u l t i p l e u s e r st oe f f i c i e n t l ys i g no nac o m m o nm e s s a g ea n dt h e ng e n e r a t eas i n g l em u l t i s i g n a t u r e t h i sm u l t i s i g n a t u r ec o n v i n c e st h ev e r i f i e r sw h oh a v es i g n e do nt h em e s s a g e m o s tc o m - p u t a t i o n sf o rt h em u l t i s i g n a t u r ea l ec o m p u t e db e f o r et h em e s s a g ei sg i v e n a f t e rt h e m e s s a g ei sa v a i l a b l e ，o n l ys m a l lq u a n t i t i e so fc o m p u t a t i o n sa l en e e d e dt og e n e r a t et h e m u l t i - s i g n a t u r e t h i sc o u l ds o l v et h ef i r s tp r o b l e m f o rm u l t i p l eu s e r s ，t h e r ei so n l yo n e m u l t i s i g n a t u r e ，i n s t e a do f 礼s i g n a t u r e sf o r 佗s i g n e r s ，s oo n l yo n ev e r i f i c a t i o ni sn e e d e d t h i sc o u l ds o l v et h es e c o n dp r o b l e m b a s e do nt h eo n l i n e o f f l i n es i g n a t u r ep r o p o s e db y g u o ，w i t ht h em e t h o do fc o n s t r u c t i n gt h em u l t i - s i g n a t u r es c h e m eu s e db yl ue ta 1 ，a c o n c r e t eo n l i n e o f f l i n em u l t i s i g n a t u r ei sp r o p o s e di nt h i sp a p e r i tc a nb ep r o v e ns e c b r e b a s e do nt h ec 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 si nt h es t a n d a r dm o d e l t h e nw ed i s c u s st h ed s rp r o t o c o la n di t ss e c u r i t yr e q u i r e m e n t s ，a n dp r o v i d et h ea p p l i c a t i o ni nt h i s p r o t o c 0 1 n e x t ，t h ei d e n t i t y b a s e do n l i n e o f f l i n es i g n a t u r es c h e m ei sd i s c u s s e d i tc a nb eu s e d t os o l v et h ep r o b l e m s ( 1 ) a n d ( 3 ) i th a sb o t ht h ea d v a n t a g e so ft h ei d e n t i t y - b a s e dc r y p - t o g r a p h ya n dt h eo n l i n e o f f l i n es i g n a t u r es c h e m e s ：t h ek e yc e r t i f i c a t e sa l ee l i m i n a t e d ， a n dm o s tc o m p u t a t i o n sn e e d e df o rt h es i g n a t u r e s g e n e r a t i o na r ec o m p u t e db e f o r et h e m e s s a g e sa r eg i v e n ，s oi tc o u l dg e n e r a t et h es i g n a t u r e se f f i c i e n t l ya f t e rt h em e s s a g e sa l e a v a i l a b l e w h e nt h en e wn o d e s j o i ni nt h em a n e t , o t h e rn o d e sd o n th a v et ou p d a t et h e n p u b l i ck e yl i s t t h a tc o u l ds o l v ep r o b l e m ( 1 ) t h eg e n e r a t i o nf o ras i g n a t u r ed o e s n tn e e d m a n yc o m p u t a t i o n sa f t e rt h em e s s a g ei sg i v e n t h es c h e m e ss e c u r i t yc a nb er e d u c e d t ot h es t r o n gd i f f i e - h e l l m a np r o b l e m si nt h er a n d o mo r a c l em o d e l i t ss e c u r ea g a i n s t t h ee x i s t e n t i a lf o r g e r yu n d e rt h ea d a p t i v ec h o s e n m e s s a g ea n di d e n t i t ya t t a c k c o m p a r e d w i t ht h ee x i s t i n gs c h e m e s ，t h i ss c h e m e sv e r i f i c a t i o na l g o r i t h mo n l yr e q u i r e so n ep a i r i n g o p e r a t i o n ，s oi ti sm o r ee f f i c i e n t a tl a s t ，w ed i s c u s st h ea p p l i c a t i o no ft h i ss c h e m ei nt h e a o d v k e yw o r d s ：s i g n a t u r es c h e m e s ，i d e n t i t y - b a s e ds i g n a t u r e s ，o n l i n e o f f l i n es i g n a - t u r e s ，m u l t i s i g n a t u r e s ，b i l i n e a rp a i r i n g s ，s t r o n gd i f f i e - h e l m m a np r o b l e m s ，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 s 第一章 1 1 1 2 1 3 1 4 第二章 2 1 2 2 2 3 第三章 3 1 3 2 3 3 3 4 3 5 3 6 第四章 4 1 4 2 4 3 4 4 4 5 4 6 目录 引言 信息安全面临的威胁 密码学概述 主要工作 组织结构 基础知识和概念 数学基础 数字签名 在线离线签名 在线离线多签名方案 研究背景 公钥注册模型 在线离线多签名方案的定义与安全模型 在线离线多签名方案的构造和安全性 方案的效率与应用 小结 高效的基于身份的在线，离线签名 研究背景 基于身份在线离线签名方案的定义 基于身份的在线离线方案的构造 基于身份在线离线签名方案的安全性 方案的效率和应用 小结 1 2 5 5 7 7 9 n b掩侈扒笱如 孔孔弱舛弘柏舵 第五章总结与展望 4 3 5 1总结4 3 5 2 展望。4 4 参考文献 4 6 致谢 5 1 在读期间完成的论文目录 5 2 v 第一章引言弟一早jl 曰 1 1 信息安全面临的威胁 随着信息技术的快速发展，我们迎来了信息时代，计算机、网络等信息技术的 应用充斥在日常生活、商业活动和行政事物处理中，如收发电子邮件、即时聊天、 网上购物、银行业务、账单支付等，为社会生产、生活提供了巨大的便利和帮助。 信息技术正在改变着人们的生活和工作方式，推动着社会的发展，在社会生产、生 活中的地位和作用越发重要和显著， 与此同时，信息产业已成为社会新的经济增长点，在国民生产总值中所占的比 重正在逐年增大，社会的信息化正在成为世界发展的潮流和核心。信息，已成为社 会和国家重要的战略资源。 随之而来的信息安全问题也日益为人们所关注，对信息安全的认识经历了一 个由简单到复杂的过程。 上个世纪7 0 年代，是主机为丰的信息时代，信息安全问题主要足面向单机。这 个时期的丰要用户是军方，保密性足这一时期信息安全的主题。 到了8 0 年代，随着个人电脑和通信网络的兴起，可以借助网络在个人电脑问进 行信息传递，用户信息得以共享。这样给信息安全带来了新的问题，使人们逐渐认 识到数据完整性和可用性的重要性。这一时期信息安全的主要内容，主要是安全服 务、安全机制等基本框架。 9 0 年代至今，因特网呈现出爆炸性发展，把我们的社会带进了一个全新的发展 和生存空间。因特网具有高分布性、边界模糊性、层次模糊性、动态演化等特性。 普通用户成为这一时期的主角。这一时期的信息安全问题变得复杂，处理好因特网 这一巨大系统的安全问题成为主要任务。因特网的全球性、开放性、共享性、动态 性等特性，使得任何人都可以自由的介入和交流。其中存在一些恶意行为者，会采 用各种攻击手段进行攻击，对其他个人或者组织的正常活动造成妨碍和破坏。这些 攻击者可能是独立的个人，也有可能足有组织的犯罪团体和国家情报机构。这些攻 击具有无边界性、突发性、蔓延性和隐蔽性等新特点。 在这一时期，信息安全主要包括以下几个方面的服务。 1 2 密码学概述第一章引言 1 保密服务保护数据以防御被动攻击，例如数据被第三方窃听。根据保护范围的 大小，可将保护方式可分多个等级。其中最高级保护用于保护两个用户之间传输的 所有数据在一定的时间范围内都是安全的。低级保护则用于单个消息，或者单个消 息中某个特定域的保护。 2 认证服务用于保证两个用户之间相互通信的真实性。单向通信的情况下，认证 服务的功能是使得接收者相信消息来自于真实的信源。双向通信的情况下，例如邮 件客户端和邮件服务器的连接，开始时的认证服务使得用户相信他自己连接到的 是真实的服务器，而服务器则相信客户端的用户不是假冒的第三人。此外，认证服 务还保证第三方不能介入双方的通信，假冒其中一方进行非授权的消息发送和接 受。 3 完整性服务与保密服务相似，完整性服务也能应用于所有消息，单个消息，或 者一个消息的某个选定域。用于所有消息的完整性服务，旨在保证接收到的消息在 传输途中没有被第三方进行复制、插入、篡改、重排、重放等操作，保证目的端接 收到的消息和源端发送的消息一致；此外，完整性服务还提供对已损坏数据的恢 复。用于单个消息，或者一个消息特定域的完整性服务则仅防止消息的篡改。 4 不可否认服务此服务可保证通信双方中的一方，无法对已发送的消息进行否 认。因此，一方面，在消息发出后，接收者可证明这一消息确实足由发送者发出： 另一方面，在消息接收后，发送者可以证明这一消息确实已经由接收者接收。 5 访问控制访问控制可以用于防止一个用户对一资源的非授权访问。可采用认 证的方式来控制，即检查欲访问某一资源的用户是否具有相应的权限。 信息安全是一个综合、交叉的科学领域，它需要数学、电子、计算机、通信等 学科的长期知识积累以及最新发展成果。它涉及的内容很多，有安全体系结构、安 全协议、密码理论、信息分析等，其核心技术是密码技术。 1 2 密码学概述 密码学是- - i 既古老又年轻的科学。早期出现在古代军事战争中的保密通信 中，例如古中国周朝兵书六韬龙韬中的阴符和阴书便记载了周武王问姜 2 1 2 密码学概述第一章引言 发送者接收者 图1 1 ：私钥密码体制的加解密 子牙关于征战与主将通讯的方式，便足密码学的初始应用。古典密码的一个典型代 表凯撒密码，也是应用于军事将领之间的通信。 古典密码与现代密码的分界线，是1 8 8 3 年荷兰密码学家k e r c h o f f s 提出的保 密原则：系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。现代密 码学中使用大量的数学：包括信息论、计算理论、抽象代数、统计学、组合数学以 及数论。 1 2 1 密码体制分类 现代密码的体制从原理上可以分为两大类，即私钥密码体制和公钥密码体制。 1 私钥密码体制私钥密码体制的特点足加密密钥和解密密钥相同。采用私钥体 制的密码系统，其保密性与算法的保密性无关，主要由密钥的保密性决定。由密文 和加密算法不可能得到明文。即根据k e r c h o f f s 原则，只需要对密钥进行保密，而 对加密算法无需保密。根据私钥密码体制的这种特性，可以使用硬件来实现私钥加 解密算法。 信息发送方和接收方，首先通过一种安全可靠地途径共享密钥。然后发送方对 要发送的明文使用密钥进行加密，生成密文，传送给接收方；接收方收到密文后， 使用相同的密钥，对密文进行解密生成明文。如何产生满足保密要求的密钥，以及 如何将密钥安全可靠地分配给发送方和接收方，是私钥密码体制设计和实现的难 题所在。密钥产生、分配、存储、销毁等问题，统称为密钥管理。这是影响系统安全 的关键因素。若密钥管理问题处理不好，即使密码算法再好，也很难保证系统的安 全性。 私钥密码体制中对明文有两种加密方式：一种是流密码方式，按明文字符逐字 加密；另一种是分组密码方式，将明文消息进行分组，逐组地进行加密。私钥密码 体制可以用于数据加密和消息认证。 3 1 2 密码学概述 第一章引言 用户公私 钥的生成 图1 2 ：公钥密码体制的加解密 2 公钥密码体制公钥密码体制是d i f f i e 和h e l l m a n 在1 9 7 6 年提出的，每个用户 有一对选定的密钥，这两个相关的密钥将加密和解密能力分开：其中一个密钥是公 开的，简称公钥，用于加密；另一个密钥是保密的，简称私钥，用于解密。公钥算法 具有一个重要特性：知道密码算法和加密密钥，求得解密密钥在计算上是不可行 的。 相对于私钥密码体制中的密码算法，例如d e s 和a e s ，公钥密码体制为密码 学的发展提供了新的理论和技术基础，一方面公钥密码算法的基本工具不再是置 换和代换，而是数学函数：另一方面非对称的形式使用两个密钥，对密钥分配、认 证等都有深刻的影响，可以称为密码学上的一次革命。它解决了私钥密码体制中的 两个难题：密钥分配和数字签名。 1 2 2 数字签名 在政治、经济、日常生活中，政府文件、法规、合同、契约、个人信件等，需要 对其签字( 或者盖章) 保证有效性和不可否认性。传统做法是对纸质文件进行手写 签名。随着信息时代到来，日常事务的处理越来越多地依赖于计算机和网络系统， 4 1 3 主要i 作第一章引言 主要以数字方式来处理信息，传统的手写签名方法则不再适用，因此人们逐渐发展 出数字签名技术，作为传统手写签名的模拟，用于对数字信息进行签名，以保证信 息的有效性和不可抵赖性。 数字签名足公钥密码体制的典型应用，其基本过程是：签名者用自己的私钥 对消息，或者压缩过的消息进行处理，生成消息签名；验证者接收到消息及其签名 后，应用签名者的公钥对这两个数据进行处理，检验签名者是否对消息进行了签 名。不同消息生成的签名不同。相对于传统的手写签名提供的有效性和不可抵赖性 服务，数字签名还可以提供信息完整性服务和认证服务。 随着数字签名技术的不断发展，根据实际应用中的不同需要，以及遇到问题的 不同，出现多种类型的数字签名，例如盲签名、群签名、环签名、代理签名、门限签 名、聚集签名、多签名、在线离线签名等等。 1 3 主要工作 ，移动自组网络( m a n e t ) 有多种路由解决方案，例如无线自组网按需平面距离 矢量路由协议( a o d v ) ，动态源路由协议( d s r ) 等等。但这些方案的设计都没有考 虑安全问题，包括节点问的相互认证。数字签名技术可提供认证服务，不过将其应 用于移动自组网络时，存在计算量要求过高，签名数量和验证时间随着经过节点数 的增加而增长，以及公钥列表频繁更新的问题，限制了数字签名的应用。 为了使数字签名技术能够适合移动自组网络路由应用的要求，本文首先研究 在线离线多签名，提出一个方案，可以解决计算量要求过高、签名数量和验证时间 随经过节点数的增加而增长的问题。本文在标准模型下证明了方案的安全性，并讨 论了方案在动态源路由协议上的应用。接着，本文提出一个基于的身份在线离线 签名方案，可以解决签名计算量要求过高、节点的密钥列表更新的问题；并且在随 机预言机模型下，证明了方案的安全性；相对于已有方案，该方案提高了验证阶段 的效率。该方案可用于无线自组网按需平面距离矢量路由协议。 1 4 组织结构 针对数字签名在实际应用中遇到的问题，本文研究了两类在线离线签名方案， 提出一个在线离线多签名方案和一个基于身份的的在线离线签名方案。 第一章介绍了信息安全与密码体制的基本知识，包括密码体制的分类，数字签 名，以及本文的主要工作 第二章介绍了文中讨论的方案所基于的数学基础知识；并对基本的数字签名 5 1 4 组织结构第一章引言 和在线离线签名进行说明。 第三章，首先回顾了g u o 等人提出的优化的在线离线签名方案。然后，在这 个方案的基础上构造一个在线，离线多签名方案，在标准模型下证明了方案的安全 性，并讨论了其在动态源路由协议上的应用。 第四章，介绍基于身份在线离线签名的特点，回顾随机预言机模型以及交叉 引理。随后提出一个具体的在线离线签名方案，并在随机预言机模型下，借助交叉 引理，证明了方案的安全性。方案可应用于无线自组网络按需平面距离矢量路由协 议。 第五章对本文进行总结，并提出本文方案的不足之处及有待改进的地方。 6 第二章基础知识和概念 本章首先给出相关的一些数学知识，包括群、双线性映射、计算性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 问题。然后介绍普通数字签名和在线离线数字 签名。 2 1 数学基础 2 1 1 群 简单的说，一个群就是具有某种操作的集合，下面给出群的定义。 定义2 11 一个集合g ，如果具有运算木，一个特殊的元素e g ，且满足如下条 件： j 对于任意的o ，b g ，口，i cb g 。 2 集合上的运算术满足结合律：对于任意的a ，b ，c g ， n 木( b 木c ) = ( a 木b ) 宰c 3 e 宰a = o ，对于所有的o g 。 4 对于每一个o g ，存在a 7 g ，满足口木n 7 = e 。 就称集合g 为群，表示为( g ，半) ，通常省略运算记为g 。 定义2 12 群中的元素个数如果是有限的，则称为有限群，否则称为无限群 定义2 13 有限群g 的元素个数称为群的阶。 定义2 14 一个群g ，若存在某个元素a g ，满足g = 【a “ r n 为任意的自然数， 那么群g 称为循环群，a 称为群g 的生成元。 7 2 1 数学基础第二章基础知识和概念 2 1 2 双线性映射 g 1 ，g 2 ，g t 同是阶为素数q 的乘法循环群，夕1 为g 1 的生成元，夕2 为g 2 生成 元，如果存在一个映射运算e ：g 1 g 2 一g t ，满足如下条件： 双线性e ( 夕口，缱) = e ( 夕2 ，鳕) = e ( g l ，9 2 ) ，v a ，b z ： 非退化性e ( 夕1 ，9 2 ) 1 可计算性存在一个高效的( 多项式时间的) 算法，计算e ( 9 1 ，夕2 ) 。 称e ：g 1 g 2 _ g t 是双线性映射( b i l i n e a rm a p ) 或者双线性配对( b i l i n e a r p a i r i n g ) 。具有此类映射e 的群g 1 ，g 2 ，g t 被称为双线性群( b i l i n e a rg r o u p ) 。( 更 多的细节，可参考文献【1 8 】，【3 7 ) 定义2 15 一个多项式时间算法9 ，如果输入安全参数8 ，输出一个如上所述的元 组f g ，e ，g 1 ，g 2 ，g t j ，则称这个算法为双线性群生成算法( b i l i n e a r - g r o u p g e n e r a t i o n a l g o r i t h m ) 。 在双线性群g 1 = g 2 的情况下，将这两个群记为g ，双线性群g 上的计算性 d i f f i e h e l l m a n 问题( c o m p u t a t i o n a ld i f f i eh e l l m a nc d h ) 定义如下： 定义2 1 6 给出一个双线性群g ，其双线性映射为e ：g g _ g t ，群g 和群g t 的 阶为素数g 。那么计算 生d i f f i e h e l l m a n 问题为：给出随机的生成, - l g 以及夕口，9 6 ， 其中n ，b z ；，计算 g 曲g 定义2 17 给出一个双线性群生成算法9 ，算法a 相对于夕所具有的c d h 比 势( c d h - a d v a n t a g e ) 为e ，定义为： a d v c a d 日d 一, jp r 限= 夕n 6 i ( 口，e ，g ，g t ) 卫乡；夕墨g ；口，6 墨z ：；九卜一4 ( 口，e ，g ，g r ，g ，g a ，9 6 ) 】e 定义2 18 我们称与9 有关的c d h 问题为化，e ) 困难价，e j h a r d ) ，如果不存在算 法a 在运行时间至多为t 后，其 a d v c _ d 日e 双线性群( g 1 ，g 2 ，g t ) 上的强d i f f i e - h e l l m a n 问题( s t r o n gd i f f i e h e l l m a n ，s d h ) 定 义如下 8 2 2 数字签名第二章基础知识和概念 定义2 19 给出双线j 幽群r g l ，g 2 ，g tj ，那么l - s d h 问题定义为：给出z + 2 个元 素 ( 9 ，9 2 ，鳄，毋2 、，毋2 ) 其中9 1 ，9 2 分别为g 1 ，g 2 的生成元，计算 l ( 夕f + c ，c ) 其中c 可以是z ：中的任何元素。 定义2 1 1 0 某算法4 相对于r g l ，g 2 ，g t ，所具有的i - s d h 优势f ，z s d h a d v a n t a g e ) 为e ，定义为 a d v , _ s d 日d = e fp r m ( 9 产1 ，c ) 卜( 9 。，9 2 ，鳕，毋2 、，毋) 】e 定义2 1 1 1 r g l ，g 2 ，g tj 上的i - s d h 问题是f f t ，( j 一困难的，如果不存在算法a 在 运行时间至多为t 的情况下，其 a d v 芒| s d 日e 2 2 数字签名 数字签名是在公钥密码体系下发展出来的密码技术，是由d i f f i e 和h e l l m a n 在 文献【1 6 】首先提出的概念。在公钥密码体系中，每一个用户有自己的公钥和私钥， 对私钥保密，将公钥公开。用户用自己的私钥对消息生成签名，任何知道公钥的人 可用公钥对签名进行验证。数字签名可以作为消息验证码，提供数据完整性、不可 否认性以及身份认证安全服务。在电子商务应用中，后两项功能尤其重要。 2 2 1 数字签名的定义 一个签名方案由下面三个算法组成( g ，s ，y ) ： 私钥生成算法g ：输入安全参数，输出公私钥对( p k ，s k ) 。私钥s 后称为签名密 钥，公钥砖称为验证密钥。 签名算法s ：以私钥s 七和消息7 n 作为输入，输出签名 简记为七( m ) 。 盯= s ( s k ，m ) 9 2 2 数字签名z z - 章基础知识和概念 验证算法y ：以公钥p 七，消息m 以及待验证的签名仃作为输入，返回一个比特 b = v ( p k ，m ，盯) ， 简记为k 南( m ，盯) 。 在这里要满足的条件是，对于任意选择的公私钥对，等式 k 七( m ，& 七( m ) ) = 1 恒成立。 2 2 2 数字签名的安全模型 数字签名方案的安全性需求是指伪造一个数字签名是非常困难的，即使攻击 者4 能够询问自己所选消息的签名，签名方案仍然满足安全性需求：攻击者a 要 对一个没有被询问过的消息生成一个合法的签名是一件非常困难的事情。对选择 消息攻击过程定义如下： 初始化：运行密钥生成算法g ，输出一个公，私钥对( p k ，s k ) 。将础交给攻击 者a 。 签名询问：攻击者a 能够访问签名预言机s ( s k ，) 。它可以向签名预言机询问任何 消息的签名。询问签名的次数至多为吼。 输出：攻击者输出一个消息签名对( m + ，矿) 。假设q 为攻击者4 对签名预言机的 消息询问集合，如果输出满足以下条件： 1 y p 忌，m + ，盯+ ) = 1 2 m 。芒q 那么我们称攻击者4 攻击成功，记为 a t t a c k ( g ，s ，y ) ( 4 ) = 1 攻击者a 输出了一个消息和这个消息的合法签名，而a 没有向签名预言机询 问过这条消息的签名。 我们给出数字签名的安全性定义。 定义2 21 一个签名方案f g ，s yj ，在选择消息攻击下是r t ，吼，ej 存在性不可伪造 的，如果对于所有的攻击者a 在运行时间至多为t ，询问签名次数至多为9 8 的情况 下， p r a t t a c k ( a ，s y ) ( 4 ) = 1 】 e 1 0 2 3 在线离线签名第二章基础知识和概念 这里安全定义中的“存在性 ，是指任意一个消息的伪造签名；“选择消息 是 指攻击者能够选择任意的消息询问签名预言机，获得消息对应的签名。数字签名的 安全性要强于手写签名的安全性。第一点，手写签名可以被一些专业人士伪造：第 二点，手写签名并不能保证所签署的文档没有被改动过，而数字签名则能够保证。 这些安全性的前提都是私钥得到保密。 2 2 3w a t e r s 签名 这里我们给出数字签名方案的一个具体例子：w a t e r s 签名方案，它足由w a t e r s 在文献【4 6 】中使用双线性群提出的一个签名方案。方案的具体构造如下： 首先运行9 ，得到( q , e ，g l ，g 2 ，鲚) ，这里g 1 = g 2 ，将它们记为g 。接着选取 k + 2 个随机生成元夕，t 7 ，u l ，u k g ，以及一个哈希函数h ： o ，1 ) _ 0 ，1 ) 知。 返回( g ，e ，g ，g t ，夕，“7 ， 8 1 ，日) 作为全局参数p a r a m s 。 密钥生成：对于用户( 以p a r a m s 为输入) ，随机选择q g q ，并且计算a 卜e ( 9 ，夕) 口 作用户的公钥，q 作为用户的私钥。 签名：输入( s k ，m ) ，用户首先计算出m 卜h ( m ) ，m 为比特串( m 1 ，m k ) e o ，1 ) 七。接着签名者选取r 墨窈并计算： 输出的签名为盯= ( 岛，岛) g g 。 验证：输入( p k ，仃，m ) ，验证者首先算得m 卜h ( m ) 并且将盯分析为( ，岛) 。m 为比特串( m l ，m k ) ，公钥p 惫为a ，验证 是否成立；如果成立，表示签名合法，输出1 ，否则签名非法，输出0 。 2 3 在线离线签名 在线离线签名方案由密钥生成算法、签名算法以及验证算法三部分组成。签 名算法分为两个阶段：离线阶段，消息到来之前；在线阶段，消息到来之后。签名 生成所需的大部分的计算在离线阶段进行，并将计算结果存储为离线数据。消息到 来后，只需进行少量的计算，便可生成签名，提高了收到签名请求后的响应速度。 r 9 、l 厂m； u 七n ! l q 9 卜 s a = 一 ，； u 七试 e 、l ，夕 “ 2 3 在线离线签名第二章基础知识和概念 密钥生成：用户u 生成自己的公钥p k 和私钥s k ，并将公钥p k 公开。 签名s i g n ：对用户让来说，签名分为在线阶段和离线阶段。 l 离线阶段：用户以自己的私钥s k 作为输入，计算出离线数据w ，并将 其存储。 2 在线阶段：在用户收到要签名的消息m 后，以消息m 和离线数据w 作 为输入，计算出对消息的签名仃。 用户u 输出( m ，p k ，盯) 。 验证：以消息m ，签名者的公钥p k 以及待验证的签名盯输入，验证盯是否用户 对消息m 生成的签名， v e r i f y ( m ，p k ，盯) 一t o 如果是，输出1 ，否则输出0 。 在线离线签名和普通的数字签名具有相同的安全模型，接下来我们给出在线，离线 签名的安全性定义。 定义2 31 一个在线倩线签名方案，在选择消息攻击下是似，仉，e j 存在性不可伪造 的，如果对于所有的攻击者a 在运行时间至多为t ，询问签名次数至多为q s 的情况 下， p r a t t a c k ( c ，s ，y ) ( 么) = 1 】 密钥生成：用户u 随机选取q z ；，并计算夕口作为私钥s k ，i , - - 算a = e ( 9 ，旷) ，a g t 作为用户的公钥p k 。 签名算法：在消息给出之前，称为离线阶段，在此阶段进行签名所需的大部分计 算，并将结果存储：消息给出之后称为在线阶段，以消息和离线阶段计算的 结果作为输入，经过少量计算得出签名。 离线阶段：用户u 以其私钥s k ，系统参数p a r a m s 作为输入，操作如下： 1 用户“随机选取两个长为礼的向量 ( p l ，舰，p n ) ， 以及 ( 魄，忱，) 所需满足条件为 p l + p 2 + + 鲰= 1 2 1 + 屹+ +