（应用数学专业论文）在线离线方案及应用.pdf

摘要 本文首先分析了信息安全的重要性，阐述了数字签名在信息安全中的重要地 位论文接着介绍了有关密码学、数字签名和在线腐线签名的基本概念和基本理 论数字签名是手写签名的电子模拟，是密码学的重要问题之一在线离线签名 是一种旨在提高签名速度的一种签名解决方法在线离线签名和在线离线加密 由于其在实际应用中的重要作用，它们的优化以及它们的实现引起我们的关注 目前，在线，离线签名方案还没有应用到实际中，而加密方案还没有论文提出可 行方案本文提出一个新的在线，离线短签名方案，它满足安全性质要求，然后我 们把它用程序实现出来：而对在线，离线加密方案，本文分析并设计了一种在线 离线加密方案，它是基于对称密码和非对称密码两种体制的特点构造出来的 关键词：数字签名：单向陷门哈希函数；短签名；双线性对：基于身份的 签名；在线离线签名；在线离线加密 a b s t r a c t t h i s p a p e rf i r s t 壮a l y s e st h ei m p o r t 弛c e o fi n f o 珊a t i o ns e c i l r 主t y 如dt h e s i 弘i f i 啪c eo fd i 百t a ls i 肛a t i l r e i ni n f 0 姗a t j s e c u r j t y a n dt h e n ，t l l i sp 印c r i n 呐d u c c st h eb a s i cc o n c 印ta n dt h eb a s i ct h e o r yo fc r ”t o l o g y ，d i g i t a ls i g 舱t _ e 姐d o n l i i l c 0 f e l j n e s i g n a t l l r c d i 百t a ls i 班a t u r cs c h e m ei s 姐e l c c t m n i cs i m u l a t i o no f h a l l d - w r i t t e n s i 弘a t u m a n di s锄 i m p o n 锄tr e s e 眦ht o p i c i n c r y p t o 舯p h y o n l i n e 0 m j i l e s i g n a t u 陀 i sa s i g n a t i l f e s o l u t i o nt oi n c r e 硒e s i g n a t u r es p e e d o 王l l i i i e 0 m i cs i g n a t u 咒a n do n l i n c 0 f e l i n ee r l c r y p t i o na r es h o w nt ob ev e r yu s e f i l li n m 姐ya p p l i c a t i o n s ，s ot h e j ro p t i m i z ca i l dt l l e i rr c a l i z a t i l l a v ec a u g l l tm u c ha t t e n t i o n o fu s kt h e s ed a y s ，o n l i n c ，o f f l i n es i 萨a t u r cs c h e m eh 豁n e v e r b e e nr e a l i z e d 锄dt l l a t o n l i n e ，o e l i n e c c r y p n o nh 猫n os c h e m e si np 印e rb c f o r c w ep m p o s e an e w 1 i n e 0 m i n es h o ns i 印a t u 坞s c h 锄c ，w h i c hs a t i s f i e ss e c u r i t yr e q u i r e m e n t s ，t h e nw e p m g r a mt op 酬f b m li t ；龃dt l l e nf o ro n l i n e o m i i l e 曲c r y p t i o n ，、ea n a l y z e 锄dd e s i 弘a o n l i n e o f f l i i i ee n 口y p t i o n ，i tb a s 船t h ec h 缸a c t e r i s t i co fs y m m e t r i cc r y p t o 脚h ya l l d a s y m m e 仃i cc r y p t o 乎a p h y 1 【e yw o r d s ：【h g i “s i 印a t l l t e ；0 n ew a yt m p d 0 0 r h 髂hf l l n c t i o n s ；s h o ns i g m t u r e ； b i l i n e 缸p a i r i n g s ； m - b 船e d s i 驴a t u r e ；o n l i n e ，o m i 耻s i 肿t u r e ； o n l i n “o m i n e e n c r ) 乍t i o n i i ( ) s 。( ) v 础( ) 记号 签名验证者 需要签名的消息( 或需要加密的消息) 两个大素数，口5 1 2 位，满足g l ( p 一1 ) 模栉的非零剩余类 z ：中的一个元素，阶数为譬，即旷。1 m o d p 安全的单向哈希函数 用户“的密钥对，j 为私钥，保密；j ，为公钥，公开；满 足y g 。m o d p 任取 带密钥为曲的签名算法 带密钥为5 的签名算法 带公钥为p 膏的验证算法 y 矗( )带公钥为户的验证算法 v 一 口 = 矿 m 川 z 占 0 瓴 h 中山大学硕士学位论文 在线，离线方案及应用 1 1 研究背景 第1 章前言 随着计算机网络的不断发展，信息化已成为人类发展的大趋势人们在享受 信息共享带来的巨大优越性的同时，也被信息安全问题所困扰信息安全的目的 就是保证数据信息在确定的时间内，在确定的地点，条件下只能被确定的人所使 用比如，有时信息接收者需要证明信息的确是期望的发出者发出的，或者信息 发出者希望信息只能由期望的接收者接收并阅读，收发双方都希望信息确切可靠 安全，即未被伪造或篡改 计算机安全涉及众多的课题病毒、抵制窃听、未授权的访问、对数据的 篡改、数据加密、认证、非否认等等本文将考虑如下领域；数字签名 1 2 相关工作 很难对计算机安全下一个定义大部分情况下，安全主要与对资源的访问控 制相关如果你发现自己要解决如下问题，你就在考虑计算机安全了： 如何传输敏感信息，如信用卡号码； 如何存储敏感信息； 如何确保代码的来源是可靠的； 如何保证只有经过授权的用户才能访问系统 还有很多其它问题，但它们都是围绕如何对信息和资源进行保护 中山大学硕士学位论文在线离线方案及应用 网络安全的本质就是网络上的信息安全信息安全是对信息的完整性、保密 性、真实性、不可抵赖性和个人隐私的保护 信息安全技术包括：密码技术、认证及抗抵赖技术、访问控制技术、防火墙、 安全审计技术等等在理论上，信息安全是建立在密码学以及安全协议的基础上 的密码学是信息安全的核心，利用密码技术对信息进行加密传输、加密存储、 数据完整性鉴别、用户身份鉴别等，比传统意义上简单的存取控制和授权等技术 更可靠 数字签名【1 ，2 ，3 】是密码学研究的热门课题之一，是当前信息化建设中的关键 安全机制之一它在密钥分配、电子商务、电子银行和电子政务等许多领域都有 重要的应用，利用数字签名，可以实现身份认证、不可抵赖性、保障数据完整性， 可以解决伪造、抵赖、冒充和篡改等问题特别是其身份鉴别、不可抵赖性在电 子商务、电子政务等领域都有着重要的作用数字签名是保障网络信息安全的有 力手段 数字签名是手写签名的电子模拟，比手写签名更具有可靠性数字签名的实 现基础是公钥密码学，使用公钥加密算法和哈希函数，来达到手写签名的功能 在计算机网络中，要使数字签名代替手写签名，就要求数字签名具有相应的法律 效力，这就要求在法律上规定数字签名的有关条款目前，美国、加拿大等很多 国家都已经颁布了相关的法律条文，我国的数字签名法律的制订工作也正在抓紧 进行 常用的数字签名方案有r s a 【4 ，5 】、e c d s a 【6 ，7 】、e l g 锄a l 嘲、s c l l l l o 【9 ，1 0 ，1 1 】 签名方案等；另外还出现一些具有特殊用途的数字签名，如，盲签名【1 2 ，1 3 】、群 签名【1 4 ，1 5 ，1 6 3 1 ，3 2 ，3 3 3 4 】、代理签名【4 9 ，5 l ，5 2 ，5 3 ，5 4 ，5 5 ，5 6 ，5 7 】、不可否认签名 【1 7 ，1 8 ，1 9 】、环签名【2 0 ，2 1 ，2 2 】、短签名【5 9 】 在线离线签名【5 9 】是把数字签名分成两个阶段的签名方式，它是为了提高签 名方案的效率而提出来的一种解决方案两个阶段第一阶段是离线阶段，在未知 签名的信息的情况下做的工作由于此阶段有足够的时间，因而离线阶段算法复 中山大学硕士学位论文 在线离线方案及应用 杂一些并不影响到信息签名的速度；第二阶段是在线阶段，这是在信息出现后开 始的，由于有离线阶段做了准备工作，所以此阶段速度会非常快由于在线离 线签名的在实际应用中有重要意义，因此如果有一种签名长度短、算法有效且安 全的在线离线签名方案，那么在现实中将会得到很广泛的应用，例如i c 卡之类 目前已出现的在线离线签名方案【5 9 】在线离线签名方案的主要特点在于在线 阶段的运算过程需要很快速，这样才能体现在线离线签名方案的好处 1 3 本文研究内容及组成 数字签名是实现电子交易安全的核心技术，是保证交易过程中数据安全( 包 括信息的保密性、真实性、完整性和不可抵赖性等) 的有效手段在线离线签名 是一种重要的、具有实际意义的数字签名本文主要研究安全有效的在线离线签 名方案，并根据现实中的应用，提出在线，离线短签名方案。 本文共分为6 章，具体组织如下： 第1 章分析了计算机安全的重要性，阐述了数字签名在信息中的重要地位 第2 章介绍了有关密码学、数字签名特别是代理签名的基本概念和基本理 论，给出著名的s d m o r r 签名方案【1 1 】、基于身份的签名方案、单向陷门哈希函 数和短签名方案用到的双线性对 第3 章给出一个典型的在线离线签名方案，详细讨论了在线离线签名方案 和它的安全性要求在大多数的签名方案中，都可以很自然地把签名过程分成在 线阶段和离线阶段两个过程，但是因为每一个签名方案都有自己特殊的形式所以 也就会形成各式各样的在线，离线签名方案怎么样构造一种方案使得在线，离线 签名过程都有一个统一的形式，这就是第一篇关于在线离线方案提出来并且解 决了的问题 第4 章我们设计了一种在线离线短签名方案在以前的在线离线签名方 3 中山大学硕士学位论文在线离线方案及应用 案中，签名产生后，为安全考虑，签名的长度都会比较长，这样本文就结合基于 身份的短签名方法，实现了一种新的在线离线短签名方案，并且给出一个应用 程序 第5 章我们讨论并提出了一种在线离线加密方案本文就结合对称加密方 法和非对称加密方法的特点，实现了一种在线，7 葛线加密方案 第6 章对本文进行了总结，并提出了展望 其中，第3 章、第4 章和第5 章是本文的重点 4 中山大学硕士学位论文 在线，离线方案及应用 2 1 密码学基础 第2 章预备知识 密码学( c r y p t o 舯p h y ) 一词来源于古希腊的o y p t 0 和g r 印h e i n ，意思是密写 密码学是一门既古老又年轻的学科，其历史可以追溯到几千年以前古代的 行帮暗语和一些文字猜谜游戏等，实际上就是对信息的加密这种加密方法通过 原始的约定，把需要表达的信息限定在一定的范围内流通古典密码学主要应用 于政治、军事和外交等领域f 3 5 】而现代密码学也是从战争中发展起来的，1 9 4 9 年，信息论仓q 始人数学家香农( c e s h a n n o n ) 在贝尔系统技术杂志( b e l l s y s t e mt c c h i c a lj o 啪a 1 ) 上发表了经典论文保密系统的通信理论( n e c o m m u n i c a t i 1 1 l e o r y o f s e c r e c y s y s t e m s ) 【3 6 】，这篇文章在第二次世界大战结 束后即被解密正是这篇文章，开启了现代密码学的发展，使密码学成为一门科 学 密码学主要包括两个方面：密码编码学 卯t o 铲a p h y ) ，简称为“编密学”和 密码分析学( c r y p t 柚a l y s i s ) 研究密码变化的规律并用之于编制密码以保护秘密 信息的科学，称为密码编码学，从事此行的叫密码编码者( c r y p t o 舭p h e r ) 研究密 码变化的规律并用之于密码以获取信息情报的科学，称为密码分析学，也叫密码 破译学，从事密码分析的专业人员称为密码分析者( c r y p t 栅l y s t ) 前者是实现对 信息保密的，后者是实现对信息反保密的，密码编码学与密码分析学相辅相成， 共处于密码学的统一体中，密码学即是二者的矛盾统一体 下面给出的是一个密码体制的模型( 图2 1 ) 中山大学硕士学位论文 在线离线方案及应用 塑回童茎，囡墼 发送者 口 通信通道 0 接收者 uu 加密密钥解密密钥 图2 1 密码体制模型 假设发送者( s d e r ) 想发送消息给接收者( r e c e i v c r ) ，且想要安全的发送信息： 他想确信窃听者不能阅读发送的消息 没有加密的信息( m e 髂a g e ) 称为明文( p l a i m e x t ) 用某种方法伪装消息以 隐藏它的内容的过程称为加密( e n 口y p t i ) ，加密后的信息称为密文( c i p h e n e x t ) ， 而把密文转变为明文的过程称为解密( d e c r y p t i ) 【5 8 】 明文用小表示，它可能是位序列、文本文件、位图、数字化的语音序列或数 字化的视频图像等等对于计算机，m 指简单的二进制数据密文用c 表示，它 也是二进制数据加密的过程实质是由明文m 到密文c 的函数，我们称之为加 密函数e ，用数学公式表示：e ( m ) - c 相反地，解密的过程实质是由密文c 到明文珊的函数，我们称之为解密函数 d ，解密函数的数学公式为：d ( c ) - 朋 在一个密码体制中，要求解密变换是加密变换的逆变换，故下面的等式必须 成立：d ( e ( m ) ) - m 密码算法( a 1 9 0 r i t h m ) 也叫密码( c i p h e f ) ，是用于加密和解密的两个数学函数 ( 通常有两个相关的函数：一个用于加密，另一个用于解密) 如果算法的保密 性是基于保持算法的秘密，这种算法称为受限制( r e s t 五c t e d ) 的密码算法受限制 的密码算法虽然具有历史意义，但按现在的标准，它们的保密性远远不够因为 如果有人无意泄露了算法的秘密，所有人都必须改变他们的算法，而且受限制密 码算法还有更大的坏处就是密码算法不能进行质量控制或标准化，存在管理上的 许多不便 6 中山大学硕士学位论文 在线，离线方案及应用 现代密码学用密钥体e y ) 解决这个问题密钥用七表示，七可以是很多数值里 的任意值密钥后的可能的取值范围叫做密钥空间o y s p a c c ) ，引入密钥七后的加 解密函数可以写成如下形式，为了不失般性，我们设加密密钥为七。，解密密钥 为k ，足。和k 可能相同也可能不同 加密：& 劬) 一c 解密：巩( c ) - 胁 其中e 。是由加密密钥七。确定的加密变换，d 是由解密密钥t 。确定的解密变换 并有b 。( & 似) ) - m 成立 如果一个密码体制的加密密钥与解密密钥相同，即k = ，则称为对称密 码体制( s y 姗e t r i ck e yc r y p t y s t 锄) 或单密钥密码体制、秘密密钥密码体制由 于加解密的密钥相同，对称密码体制的安全性取决于对密钥的保密，它要求发送 者和接收者在安全通信前，商定一个密钥其安全性依赖于密钥的安全性 对称密码的代表有1 9 7 7 年美国国家标准局( n b sn a t 如n a lb u r e a uo f s t a n d a f d s ) 公布的数据加密标准d e s ( d a t ae n p t i o ns 鼬d a r d ) 【3 7 】，1 9 9 2 年 出现的国际数据加密算法删b a ( i n t e m a t i o n a ld a t ae n 甜y p t i 彻a l g 鲥t l m ) f 3 8 ，3 9 】， 2 0 0 1 年美国国家标准技术研究所n i s t ( n “o n a lh s t i t u t eo fs t a i l d a r d 缸d t e c h n 0 1 0 9 y ) 正式公布的高级加密标准a e s ( a d v 锄c e de n c 唧t i o ns t a n d a r d ) 【4 0 】 等 对称密码体制具有很高的保密强度，可以达到经受较高级破译力量的分析和 攻击，加解密速度快但对称密钥体制加解密使用的是相同的密钥，所以在一个 大范围的网络上，密钥的分发和管理是一件很困难的事情，使它难以满足系统的 开放性要求，无法解决消息确认问题 若加密和解密分别用两个不同的密钥实现，即七。- 屯，称其为非对称密码 体制或公钥密码体制在一个非对称密码体制中，由加密密钥t 。计算解密密钥 7 中山大学硕士学位论文 在线，离线方案及应用 是困难的，公开t 不会损害k 的安全性，则可以将k 。公开，这样的密码体制称 为公钥密码体制( p u b l i c k c yc r y p t o s y s t e m ) ，其中七。和k 是成对出现的，七。叫做 公开密钥( p u b l i c k c y ，简称公钥) ，k 叫做私人密钥( p r i v a t ek e y ，简称私钥) 公钥密码体制思想的提出来自w d i f f i e 和m e h e l l n l a l l 在1 9 7 6 年发表的 密码学的新方向( n e wd i 咒c t i 衄i nc r y p t o 舯p h y ) 一文其第一个算法是由 r m e r k l e 和m h e l l m 锄开发的背包算法【4 1 ，4 2 】迄今为止最著名、使用最广泛 的是由r r i v t 、a s h 锄i r 和l a d l e m a l l 三位教授于1 9 7 7 年提出的r s a 公钥 密码体制【4 ，5 】另外比较著名的还有e l g a m a l 公钥密码体制【8 】，r a b i n 方案【4 3 ，“】 等 公钥密码体制能适应开放性的使用环境，密钥管理相对简单，能抵抗选择明 文攻击，非常适合数字签名，安全性好但是算法一般比较复杂，加解密速度慢 2 2 数字签名基础 2 2 1 数字签名基本概念 在日常生活中，经常需要人们签署各种信件和文书，传统上都是用手写签名 或印鉴签名的作用是认证、核准和生效，签名是用来确定需要对该文件负责的 某个人 随着信息时代的来l i 缶，人们希望对越来越多的电子文件进行迅速的、远距离 的签名，这就是数字签名【1 ，2 ，3 】数字签名( d i g i t a ls i 弘a t l l r c ) 是手写签名的电 子模拟，主要用于对数字消息( d i g i t a lm e 鹞a g c ) 进行签名，以防消息的冒名伪 造或篡改，亦可用于通信双方的身份鉴别数字签名以电子形式存储消息签名， 因此，签名之后的消息能通过计算机网络传输 8 中山大学硕士学位论文 在线，离线方案及应用 数字签名与传统的手写签名有很大的差别【4 5 ，4 6 】 首先，手写签名是被签署文件的物理组成部分，而数字签名不是，所以所使 用的数字签名方案必须设法使签名“绑”到所签名的文件上 第二，手写签名不易拷贝，而数字签名正好相反，因此必须阻止一个数字签 名消息被重复使用，一般通过要求消息本身带有诸如日期等信息来达到阻止签名 被重复使用的目的 第三，手写签名是通过与一个真实的手写签名比较来进行验证，而数字签名 是通过一个公开的验证算法来验证，数字签名是由0 和1 组成的数字串，它因消 息而异，当出现争端时，它能够仲裁者提供足够的证据来进行裁决，因此，其安 全性远远高于手写签名此外，数字签名依托于计算机网络，其时效性也远远大 于手写签名 数字签名有下面几个元素 5 9 ： ( 1 ) 一个安全参数( 由用户在密钥对生成时选取) 这个参数决定密钥的 长度( 当然也决定了安全性) 、签名运行时间复杂度、验证运行时间复杂度 和需要签名的消息( 摘要) 数量 ( 2 ) 一个消息空间这是签名算法作用( 未经哈希) 的消息空间 ( 3 ) 一个概率多项式时间密钥产生算法可以被任何用户用来产生密钥对 ( 公钥，和私钥册的算法 ( 4 ) 一个概率多项式时间签名算法给定一个消息册和个私钥s r 产生 一个对给定消息历的签名 ( 5 ) 一个多项式时间验证算法对给定的签名仃、消息历和公钥朋验证 签名仃是否是皿的相对于公钥所的有效签名 数字签名应具有以下特性【3 5 】： 9 中山大学硕士学位论文 在线，离线方案及应用 ( 1 ) 签名是可信的任何人都可以验证签名的有效性 ( 2 ) 签名是无法伪造的除了合法的签名者之外，其他任何人伪造其签名 是困难的 ( 3 ) 签名是不可重复使用的对一个消息的签名不能通过复制变为另一个 消息的签名否则，任何人都可以发现消息与签名之间的不一致性，从而 可以拒绝签名的消息 ( 4 ) 签名的消息是不可改变的经签名的消息不能被篡改否则，任何人 可以发现消息与签名之间的不一致性 ( 5 ) 签名具有不可否认性签名者事后不能否认自己的签名 随着计算机信息网络的迅速发展，特别是电子商务的兴起，数字签名的使用 越来越普遍数字签名是防止信息欺诈行为的重要保障 2 2 2 基于公钥密码的数字签名方案 数字签名方案可以用对称算法实现，也可以用公钥算法实现，但前者除了 文件签名者和文件接受者双方，还需要第三方认证，较麻烦，仅讨论基于公钥密 码体制的数字签名方案 下面给出基于公钥密码的一般数字签名方案的签名产生阶段和签名验证阶 段假设d 要发送文件给p ： ( 1 ) 0 用其保密的私钥对消息m 加密，密文a 就是0 对消息的签名 ( 2 ) 0 将签名的消息沏，盯) 传送给p ( 3 ) p 用d 的公钥对盯进行解密，得到槐若挪- 掰，则确认盯是消息规 的有效签名否则为无效签名 因为私钥是保密的，只有。自己知道，所以只有0 能对任何消息进行正确签 1 0 中山大学硕士学位论文在线离线方案及应用 名另一方面，由于公钥是公开的，所以任何人都可以验证签名的有效性如果 d 否认签名的事实，则p 可将d 产生的密文出示给仲裁者，仲裁者用0 的公钥去 证实其签名的确实性；反之，若p 将收到的密文消息进行伪造篡改，则其不能用 。的公开密钥进行加密，仲裁者很容易证明是伪造的 但是，并不是每一个公钥密码体制都可以按照上述方式来设计数字签名方 案，只有满足& ( d 0 伽) ) 一川的公钥密码体制才可按上述方式来设计数字签名方 案 基于公钥密码的数字签名方案，著名的有r s a 数字签名方案【4 ，5 】、e i g 锄a l 签名方案【8 】和s d m o 盯签名方案【9 ，1 0 ，1 1 】等 2 2 3s c h n o r r 签名方案【1 1 】 s c h j l o r r 签名方案是由c s c h r f 于1 9 8 9 年提出的，是一个比较著名的 e i g 锄a l 签名方案的变种形式 设p ，q 为两个大素数，口i ( p 一1 ) ，g 是z ；中的一个元素，阶数为g ，i l ( ) 是 个安全的单向哈希函数 签名人。要对消息m 进行签名，d 随机选取。与z ：，计算r 0 一g b m o d p 和 一j l ，0 ) + k m o d g 则( r d ，) 即为对消息m 的签名0 将( r 。，) 发送给 验证者矿 验证人检验等式占。一) ，州饧m o d p 是否成立，若成立，则说明( ，d ，如) 是有 效的签名图2 2 3 简单描述了s c h o r r 签名的过程 d 计算： 七d 与z ：，- g 。m o d p 中山大学硕士学位论文 在线，离线方案及应用 i x d _ i l o ，尘，r d ) + 良om o d q o y ：( m ，r o ，s d ) ? y 检验： g 。；) 善”，。r om o d p 图2 2 3 ：s c h n o i r 签名方案 2 2 4 基于身份( i d - b a s e d ) 的签名方案 基于身份的密码学是由a d is h 硼i r 于1 9 8 4 年提出的其主要观点是，系统中 不需要证书，可以使用用户的标识如姓名、i p 地址、电子邮件地址等作为公钥用 户的私钥通过一个被称作私钥生成器p k g ( p r i v a t ek e yg e n e r a t o r ) 的可信任第三 方进行计算得到基于身份的数字签名方案在1 9 8 4 年s h 锄i r 就已得到然而，直 到2 0 0 1 年，b o n e h 等人利用椭圆曲线的双线性对才得到s h 锄i r 意义上的基于身份 的加密体制( i b e ，i d b 8 s e de n c r y p t i o n ) 在此之前，一个基于身份的更加传统 的加密方案曾被c o c k s 提出，但效率极低目前，基于身份的方案包括基于身份 的加密体制、可鉴别身份的加密和签密体制、签名体制、密钥协商体制、鉴别体 制、门限密码体制、层次密码体制等 下面的签名方案是j c c h a 和j h c h e 【6 3 1 中的一个基于身份的签名方 g 是对d d h p ( 决策d i f f i e h e l l m a n 问题，d e c i s i o n a l p r o b l e m ) 问题在多项式时间内可以被解决的阶为素数的群 1 初始化( s e t u p ) 选取g 的一个生成元尸取一个随机数占2 力，令，k = s 只再选用于密码学 的哈希函数日，：f o ，1 g 一功和h ： o ，1 ) 一g 系统参数是( 只 1 2 中山大学硕士学位论文在线离线方案及应用 ，日。，日：) 主密钥是& 2 解释( e x t r a c t ) 给定一个身份i d ，计算p ，d = 占h ：( i d ) 并把它做为与身份i d 相对应的密钥， 我们注意q 。= 日：( i d ) 相当于非对称密钥体制中的公钥 3 签名( s i g n ) 给定一个私钥_ d 。和一个消息肺取一个随机数，e z 以输出一个签名口= ( 以 ”其中胆r q d ，力= 日1 ( 玛功，毕( 一妨d ： 4 验证( v e r i f y ) 要验证与身份i d 相关的一个消息椭签名盯2 ( 以妁，只须检验( 只j k ， 坍西q ，玢是否是一个有效的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 元组是指给定( 只a 只配c 辟，决定在z l 内是否有萨a 6 ， 如果成立则( 只矗只织c 疗就称为一个有效的d i f f i e - h e l l i i l a n 元组) 很容易证明如下：如果仃= ( d 是对消息皿白一个有效的签名，那么泸，q 。， 睁( 一肋d ，d 其中，乃口，力t 日1 ( 忍功 所以( 只厶- ，坍由q 。， = ( 只j k ，( r 肋q 。，( r 曲d 五d ) 2 3 短签名方案简介 2 ( 只s 只( ，+ q _ | d ，s ( 一q ) 数字签名一直是密码学领域研究的热门问题之一随着数字信息化的发展 中山太学硕士学位论文 在线，离线方案及应用 数字签名技术得到了越来越多的应用许多具有特殊性质的数字签名方案被提 了出来，譬如：盲签名( b l i i l ds i 印a t u r e ) 【1 2 ，1 3 】、不可否认签名( 1 l n d e n i a b l e s i g n a t i l r e ) 【1 7 ，1 8 ，1 9 】、防失败签名( f a i l - s t o ps i 弘a t u r c ) 【4 7 ，4 8 】以及群签名( 印u p s i 印a t u r e ) 【1 4 ，1 5 ，1 6 】和环签名( r i n gs i g n a t u r c ) 【2 0 ，2 1 ，2 2 】等 而现在介绍的短签名方案，它在一些带宽限制环境下是非常好用的例如， 产品注册系统通常会要求用户键入c d 盘标签上提供的签名当要求一个人输入 个数字签名时，当然是提供最短的可能的签名是最受欢迎的类似地，当空间 受到限制时，短签名也将受欢迎 构造短签名的问题在很早以前就提出来了而且已经有几种方案提出在安全 性类似的情况下，怎样缩短d s a 签名长度了( 例如d n a c c a c h e 和j s t e m 【6 4 】) 在签名中，两种常用的签名方案，r s a 和d s a ，产生与安全性需求相关的相 当长度的签名例如，当用1 0 2 4 比特( b i t ) 做模时，r s a 签名长度就是1 0 2 4 比 特：类似地，当用1 0 2 4 比特做模时，标准的d s a 签名长度是3 2 0 比特椭圆曲 线形式的d s a ，签名长度也同样是3 2 0 比特而用d b o n e h ，b l y n n ，和h s h a c h 锄 6 5 的方案，签名长度总是1 6 0 比特 2 3 1 短签名方案用到的双线性映射 双线性对在密码学中有很多不同的用途 2 3 ，2 4 ，2 5 ，2 6 ，2 7 ，2 8 ，2 9 ，6 5 ， 并且可以用它来构造新的密码方案 令g 1 为由p 生成的阶为素数口的循环加群，g ：为循环乘群并与g 1 有相同 的阶函且有映射p ：g l g ，一g ：，有如下性质： 1 ) 双线性性：e ( 妒6 功2 日( 只妨“，对任意的慝g 1 ，p g ， a 、b z 口 1 4 中山大学硕士学位论文 在线，离线方案及应用 2 ) 非退化性：存在尸g 1 ，口g 1 使得p ( 只功1 3 ) 可计算性：对尸g l ，口g l 存在有效的算法计算p ( 只妨 离散对数问题( d l p ) ：给定两个群元素尸g ，口g 1 ，要找出一个整数刀 z ：使得驴艘 决策d i f f i e h e l l m a n 问题( 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 ，d d h p ) ： 对丑，& c z ：，给定只a 只c p 判定是否有萨a 6 ( m o d0 计算d i f f i e h e l l 砸a n 问题( c o m p u t a t i o nd i f f i e h e l l m a np r o b l e m ，c d h p ) ： 对a j 6 ，c z ：，给定只以胪计算a 6 只 我们上面提到的基于身份的签名方案正是基于“间隙d i f f i e h e l l m a n 群” ( g a pd i f f i e h e l l 帕ng r o u p ，g d hg r o u p ) 的，所谓的“间隙d i f f i e h e l l 哪n 群”就是对于“决策d i f f i e h e l l m a n 问题”容易，而“计算d i f f i e h e u m a n 问题”困难的一类群 2 3 2 单向陷门哈希函数( h a s hf u n c t i o n ) k r a w c z y k 和r a b i n 6 6 和文献 3 0 里提到单向陷门h a s h 函数，在k r a w c z y k 和r a b i n 6 6 的文献中，单向陷门h a s h 函数即是“交色龙哈希函数( c h a i l l e l e o n h a s hf u n c t i o n ) ”单向陷门h a s h 函数是一种特殊的h a s h 函数，它有一个公钥 h k 和一个私钥t k ，单向陷门h a s h 函数具有两个输入，日( m ；y ) ，给出公钥h k 之后，任何人都可以计算h 8 s h 值日。锄；y ) ，但只有拥有私钥的用户才可以找 到这个h a s h 函数的“碰撞”值 中山大学硕士学位论文 在线腐线方案及应用 “c h 锄e l e o n ”表示陷门信息的所有者有能力去把函数输入改变成任意他想 要的选择的值面不改变输出结果 c h a m e l e o nh a s h 函数是与用户u t 联系在一起的，u ；发布公开哈希密钥h 并 保存相应的私钥( 例如寻找碰撞的陷门) ，记为公开( 哈希) 密钥h 。，定 义c h 锄e l e o n 哈希函数，记为c h a 虬h a s h 巩( ，) ，该函数如果给定值日仉则可 以有效地计算出来 文献 6 6 中列出c h 心h a s h u ，( ，) 的性质如下： 一输入信息m 和一个随机字符串r ，c h a m - h a s h 。( m ，r ) 产生哈希值h c h a m h a s h n ( ，r ) 有如下性质： 抗碰撞；不存在有效的算法使得输入公钥日。就找得到一对 ( m 1 ， ) 和( m 2 ，r 2 ) ，其中小l m 2 ，使得c h 舢h a s h “( 胁1 ，1 ) 2 c h a m h a s h ( j ，l ：，r 2 ) ，这个概率是可忽略的。 陷门碰撞：给定一个秘密陷门信息和( 册，r 1 ) ，存在一个有效 算法可以找到任意信息m 2 ，使得c 眦虬眦s hn ( 州。，1 ) 2 c h a m _ h a s h n ( 州：，r 2 ) ，这个概率是1 一致性：对随机选取的r ，所有的信息m 在c h a m _ h a s h 。( 皿，r ) 产生同样的概率分布 具体的c h 锄e l e o n 哈希函数例子可以在文献 6 6 中得到下面给出 6 6 中构 造的一个基于强离散对数的c h a m e l e o n 哈希函数 1 6 中山大学硕士学位论文在线，离线方案及应用 在初始阶段，用户阢产生两个大素数p 和q ，使得q p 一1 ，其中q 是一个足 够大的素数因子然后元素g 从z ；选取，满足d 耐，( g ) 2 q 公钥日珥是 y 2 9 。( m o d 脚可以看出公钥部分隐含p 、q 和g c h 删h a s h 。( m ，r ) 定义如下， 给定信息m z ：，选取随机值r z ：，并令c h a n h a s h 仉( m ，r ) 3g ”y7 ( m o dp ) 可以看出，上面的c h 锄e l e o n 哈希函数对u u 。是抗碰撞的u 。总是可以 找得到，； m ，并计算相应的，使函数得到同一个哈希值，因为他知道x 所以 他可以非常容易解m + xr = 痨+ x ，( 雨o d 。 2 4 本章小结 这一章，我们介绍了一些必要的基础知识，包括密码学、数字签名基本概念、 基于身份的签名简介、双线性对和单向陷门哈希函数等我们特别给出了著名的 s c l l l l o n 签名方案和一个基于身份的签名方案 1 7 中山大学硕士学位论文 在线，离线方案及应用 第3 章在线离线签名方案 在线离线签名【5 9 】是把数字签名分成两个阶段的签名方式两个阶段的第 一阶段是离线阶段，在未知签名的信息的情况下做的工作第二阶段是在线阶 段，这是在信息出现后开始的，由于有离线阶段做了准备工作并且选择了快速签 名方案，所以此阶段速度会非常快 3 l 具体的在线离线签名方案( p a n i c m a ro n - h n e 0 m l i n es i g 岫t l l m s c h e m e ) 对于大部分的签名方案，签名过程都可以很自然地分成两个阶段我们来看 一个具体的签名方案，e l g a 豫l 签名方案 3 1 1e l g a 咖l 签名方案转换成在线，j 骞线签名方案 对消息m 签名时，首先选择一个随机数向七与矿l 互素然后计算 口= g m o dp 利用扩展欧几里德算法从下式中求出6 ： m _ ( z 4 + 肋) m o d ( 矿1 ) 签名为一对数：口和扛随机数值七必须保密 中山大学硕士学位论文 在线，离线方案及应用 要验证签名时，只要验证 这是因为： 因此有： y 4 口6 m o dp ：g m o dp ，= g 。m o dp 4 = g 。m o dp y 4 口6m o dp = 占蚪g 抽m o dp g 盯+ 赫m o dp g mm o dp 成立表3 一l 就是e 1 g 锄l 签名示意图 1 9 中山大学硕士学位论文在线，离线方案及应用 表3 1e l g 锄l 签名 从上面e l g a l 签名方案我们可以把它转换成在线离线签名方案首先在 信息m 还没出现的之前做为离线阶段，有( 表3 2 ) ： 表3 2e l g 锄a l 离线签名阶段 而在线阶段就是在信息m 出现之后，有( 表3 3 ) ： 表3 3e l g a m a l 在线签名阶段 我们可以看到，其实每一种已知的签名方案都可以很自然地转换为在线离 线签名方案但是，也因此有个弊端，就是对每一种签名方案，我们都得费心费 力去把它转换成在线离线签名方案而且，即使每一种签名方案都可以转换成在 线离线签名方案，但也不意味着转换后的在线离线签名方案就是可以应用的 中山大学硕士学位论文 在线，离线方案及应用 因为我们之所以要把普通签名方案转换成在线，离线签名方案，目的在于有些实 际应用场合要求在信息出现的时候要在很短的时间内签名完成，所以就要求在线 离线签名方案的在线阶段所用到的算法需要是非常快速的 这就回答了，即使我们看到任何签名算法都可以转换为在线离线签名算法， 但却不符合我们应用中的算法所以我们还必须另外寻找一种方法，使普通签名 算法可以转换为可以实际应用的在线离线签名算法 另外一个要求是用一种普遍适用的方法，使任何一种签名算法都可以通过它 转换成在线离线签名算法，而不必每一种签名算法都有自己特有的在线，离线签 名算法 3 1 2 文献【5 9 】中在线，离线签名算法思想 在线离线签名方案的三个主要因素： ( 1 ) 一个( 普通) 签名方案； ( 2 ) 一个快速一次性( 0 n et i n l e ) 签名方案； ( 3 ) 一个快速的单向哈希方案 s h i m o ne v e n ，o d e dg o l d r e i c h 和s i l v i om i c a l i 5 9 中提到的这个算法的 本质是在离线阶段用普通签名方案对一次性签名要用到的随机构造的信息进行 一次普通签名，然后在线阶段利用一次性签名方案对消息进行签名具体如下； 记为单向哈希函数，把任意长度信息映射成门比特( b i t ) 长的字符串记 ( es 为普通签名方案( g 为密钥产生( k e y g e n e r a t i o n ) 算法，s 是签名算法， 矿是验证算法) 记( gs 订表示一次性签名方案过程如表3 4 ： 中山大学硕士学位论文 在线离线方案及应用 密钥产生： 表3 4 文献 5 9 中在线离线签名算法 签名者运行口产生( ，磁5 胁公钥户是公开的，而耐是“签名密钥”，须 保密 离线计算： 在选择信息之前，签名者先运行算法毋以随机选择一次性公钥p 七和与础 相对应的一次性私钥她( 这个一次性密钥对不太可能会再次用到) 然后再 用普通签名方案对础进行签名 。( 肚) ， 并保存，和一对一次性密钥( 础鲥 在线签名： 对信息m ，进行签名，签名者取出先计算好的签名和密钥对( 砒鳓利 用髓对信息研进行哈希，把信息历映射到长度为刀的字符串，表示为以痂然 生生盔堂堡主堂丝堡苎 一苎垡! 塑垡查墨墨壁旦 后再计算一次性签名 仃= ( 从痂) 信息皿的签名就是础和盯的串联( 础，盯) 验证： 对( 戚，盯) 验证是否是信息皿关于公钥用的真实签名，验证者首 先利用验证算法矿和公钥彤检查是础的真实签名其次，他计算忙麒劫 并运行算法n 检查口是矗相对于一次性公钥p 是的真实签名即验证过程楣当 于求证下面两个式子的正确性 安全性： ( 础) v 时( 麒功，仃) 该方案可以证明抗适应性选择明文攻击 有效性： 上面算法的离线阶段计算本质上就是对一个字符串进行普通签名计算由 于在线阶段用了非常快速的哈希函数和一次性签名方案，所以相