（应用数学专业论文）数字签名的公平交换.pdf

中山= _ = 学硕士学位论文数字签名的公平交换 论文题目：数字签名的公平交换 专业：应用数学 硕士生：林群 指导教师：王燕呜教授 摘要 本文首先阐述了电子商务在信息社会的重要性，以及公平交换协 议对于电子商务的意义，然后介绍了密码学、数字签名与密码协议的 基本概念和基本理论。公平交换协议是一种很重要的密码协议，它的 目的是为了使互不信任的双方能够实现电子数据的公平交换，使得交 换的结果要么双方都如愿以偿，要么双方都一无所获。正因为公平交 换在电子商务中扮演着极其重要的角色，所以近年来一直是研究的热 点。在本文中，我们系统地统一了当前各种优化公平交换协议的思想， 提出了优化公平交换协议的基本模型，并运用此模型来分析各种协议 思想的特点。并且，我们还构造了一个基于身份签名的公平交换协议。 最后，我们对各种思想方案进行了比较。公平交换协议可以应用在电 子商务和电子政务等，具有极其重要的应用价值。 关键词：公平交换：基于身份；可验证加密的签名； 双重签名；指定确认者签名 中山大学硕士学位论文数字签名的公平交换 t i t l c =f a j r e x c h a n g eo fd i g i t a ls i 印a t u n s m a j o r ： a p p l j e dm a t h e m a n c s n a m e ： l i n q u n s u p e r v i r ：p m 蛔s o rw 蛾gy a n - l i i i n g a b s t r a c t 1 1 1 i sp a p e rf i 巧td e a l sw i mt h ei i n p o n 粕c co fe - c c 曲m e r c ci ni n f o 加a t i o ns o c i e t y 锄dn l e s i g l l i f i c a n c c o ff a i fe x c h a n g e p i o 眩斌i ne c o m m e f c e s e c o n d l y ，w e i n 埘砌u c ct h eb a s i cc o n p t s 柚dl h c o f i e so fc f y p t o g 珀p h y ，d 培i t a ls i g l l a t u r ea n d c r y p t i cp m t o c 0 1 f a i rc x c h 柚g cp r o t o c o li ss u c h 姐i i n p o n a n tp m t o c o l ，w h i c hi s u s e dt oa l l o wt w op o t c n t i a l l ym i s t 邢s t i n gp a n 主e st oe x c h a n g ee l c c 咖i j cd a t aj naf a i r w a y s ot l l a te i t h c re a c hp a n yg c 协t h eo t h c r sd a t a ，o fn c i t l l e fo ft h e md o c s b b c a u s c f a i re x c h 柚g ep 曲l c mp l a y s 锄c h 柚i i n p o r 切m tr o l c i ne c 【哪m e r c c ，i th a sa t l r a c t e d m u c hr e s e a r c ha t t e n t i o n i nt h i sp a p e f w eg c n c f a l i z ea nk i l l d so fi d e 8 si no p t i m i s t i c f a i fe x c h a n g cp m t o l ，柚dp r o p 0 ab a s i c 珊o d e l u s i n gi h i s 珊0 d e l ，w e 孤a l y z et h e c l l a r t e r0 fe a 曲i d 髓m o 删v c f ，w ep u tf 0 州盯daf 妇e x c h a n g ep r o t 蚴io fa n i d - b a s e ds i g n a t u r e 1 n 也el a s t ，w ec d m p 鲥ee a c hs c h 锄e f a i re x c h a n g cp m t o c o li s v a l u a b i e ，柚di t nb cu di ne c o 咖e r c e 拥de p o l i 如se t c k e ) w o r d s ： f a i fe x c h a n g e ； i d 山鹞e d ； v c f i 矗a b l y 朋c f y p l e ds i 弘a t u r e t w o 。p a r t ym u l t i s i g n a t l i r c ；d c s i g n a t e dc o l l f 至珊c rs i g i l a t u r e 中山大学硕士学位论文 数字签名的公平交换 第1 章前言 1 1 研究背景 随着信息科学的蓬勃发展，社会已进入信息时代。计算机和通信网络的广泛 应用，为人们的生活和工作提供了很大的方便，同时也产生了许多新的经济活动 形式。其中，电子商务就是现代经济活动的主要形式之一。与传统贸易相比，电 子商务的主要特征是在网上传播商品和服务信息，以及完成商品交易；它能够降 低运营成本、提高经济效益和增加贸易机会。作为信息技术的产物和网络经济的 主要形式，电子商务已被越来越多的消费者、商家和政府职能部门接受和认同。 随着全球经济一体化进程的加快，电子商务正在对社会和经济生活产生更加巨大 的影响，并在全球范围内日益普及。大力发展电子商务，对于国家以信息化带动 工业化的战略，实现跨越式发展，增强国家竞争力，具有十分重要的战略意义。 电子商务活动在i n t e m e t 上进行，大量的数据需要在网上传输，其中包括定 单、合同和身份证明等敏感信息。这些传统上基于纸面的，常常需要签名或盖章 的重要凭证被转化为数字文件在i n t 啪e l 上出现，以电子数据形式被交易对象们 广泛地使用。为了保护电子交易数据的安全，需要采用密码技术，以确保电子商 务系统中数据的保密性、真实性、完整性。 然而，尽管人们承认电子商务有着形式方便、获取商品信息快捷、节省时间 等方面的优势，但他们对其还持有很多怀疑态度。究竟是什么原因使得他们对电 子商务如此没有信心呢? 网络安全问题固然是其中一个重要因素。除此之外，网 络诚信问题也是一个重要因素。买家付款后不能及时得到商品、卖家卖出商品不 能保证收到货款、商品质景不合格等各种违法违规行为屡屡发生，造成了电子商 务交易的信用危机。尽管经济领域出现了网络化，但法律体系的发展却相对滞后。 消费者在网络上的权益得不到保障，阻碍了电子商务的健康发展。业内人士普遍 认为；电子商务发展瓶颈不是技术问题，而是网络诚信。诚信问题已成为电子商 务发展的主要障碍。 中山大学硕士学位论文 数字签名的公平交挠 据悉，我国的电子签名法已于2 0 0 5 年4 月1 日起实施，这加强了电子 商务的诚信建设，但它并不能完全解决电子商务中的信用危机，电子商务的诚信 建设还有待进一步加强。 1 2 相关工作 电子商务所面临的两大问题就是网络安全与网络诚信。网络安全的本质就是 信息安全，它是对通信信息的完整性、保密性、真实性、不可否认性的保护。对 信息安全系统的研究已经有几十年的历史。随着我国公钥基础设施的应用和信息 技术的发展，网络安全已经有了一定的保障。然而，网络诚信问题却不容乐观。 尽管电子签名法的颁布，赋予了电子签名和数据电文法律效力，在一定程度 上提高了诚信度；但仍然无法完全解决诚信问题，从而影响人们的消费心理，阻 碍了电子商务的健康发展。 为了能够在缺乏诫信的网络环境下完成各种交易，就必须有协议。所谓协议 指的是双方或多方通过一系列规定的有序步骤来完成某项任务。两密码协议就是 指应用密码技术构造的协议。随着网络应用普及到各个领域，密码协议显示出其 重要的应用价值，已成为密码学研究的热门课题之一。目前已有各种各样的用于 不同目的的密码协议，如身份鉴别协议【1 ，2 ，3 】、零知识证明协议【4 ，5 】、公平交换 协议f 6 7 8 j 等。 设计公平交换协议，目的是使任意两个互不信任的主体之间能够以一种高效 公平的方式来交换电子数据。由于此类协议在电子商务中处于举足轻重的地位， 所以一直备受重视。关于它的研究也经历了一系列的发展过程，从“逐步秘密交 换”1 9 ，1 啡到“使用在线的可信第三方”n 1 ，1 2 】，再到“使用离线的可信第三方” 【1 3 ，1 4 】。因为使用离线可信第三方的协议具有高效性，所以又被称为优化公平交 换协议，它是目前公平交换协议研究的热点。 设计优化公平交换协议主要有三种思想：基于可验证加密的签名【1 3 】，基于 双重签名f 1 5 ，1 6 j ，基于可转化的指定确认者签名【1 7 】。它们各有千秋。以往的文 献都专注于用其中菜一种思想来设计协议，而忽略了它们之间的联系与各自的特 点。 2 中山大学硕士学位论文数字签名的公平交换 1 3 本文安排 在本文中，我们系统地统一了当前各种优化公平交换协议的思想，提出了优 化公平交换协议的基本模型，并运用此模型来分析各种协议思想的特点，以及对 各种思想方案进行了比较，阐明了它们的应用背景。 本文共分为4 章，具体安排如下： 第1 章叙述了电子商务的重要性，并阐明了电子商务所面临的问题。 第2 章介绍了密码学体制、数字签名和密码协议的基本概念和基本理论。 第3 章提出了优化公平交换协议的基本模型，并运用此模型来分析各种协议 思想的特点，以及对它们进行比较。另外，我们还构造了一个基于身份签名的公 平交换协议，并分析了它的安全性。 第4 章对本文进行了总结。 其中，第3 章是本文的重点。 中l n 大学硕士学位论文 数字签名的公平变换 第2 章预备知识 2 1 密码学基础 2 1 1 概述 密码学是一门既古老又年轻的学科，其历史可以追溯到几千年以前。长期以 来，它主要应用于政治、军事以及外交等领域。但是，在1 9 4 9 年之前，密码技 术基本上是一门技巧性很强的艺术，而不是一门科学。在这一时期，密码专家常 常是凭借直觉和信念来进行密码设计和分析，而不是推理证明f 2 】。 在1 9 4 9 年，s h 锄叫发表了“保密系统的通信理论( o o m m 岫i c a t j o nt h e o r vo f s e c r c c ys y s t e m s ) ”一文【1 8 】，为密码学奠定了坚实的理论基础，使密码学成为一 门真正的科学。但从1 9 4 9 年至1 9 7 5 年，密码学的理论研究工作进展不大。 l 卵6 年，d i 铂e 和i 毛e l l m a n 发表了“密码学中的新方向( n e wd i r e c t - o s m c r y p t o g r a p h y ) ”一文f 1 9 】，提出了适应网络上保密通信的公钥密码思想，开创了 公钥密码学的新纪元。从此，密码学的研究进入了一个崭新的时代。公钥密码学 也经历了从基于公钥证书的密码体制发展到至今方兴未艾的基于身份的密码体 制。如今。密码学理论和技术已成为信息科学和技术中的一个重要研究领域。随 着近年来电子商务的兴起，现代密码学的应用已不仅仅局限于政治、军事以及外 交等领域，其商用价值和社会价值得到了充分的肯定。 通常，我们将没有加密的信息称为明文，加密后的信息称为密文：从明文到 密文的变换称为加密，从密文到明文的变换称为解密。在加密和解密过程中，控 制加密变换的密钥称为加密密钥k ，控制解密变换的密钥称为解密密钥j 匕。目 前，根据密钥性质不同，可分为对称密码体制和公钥密码体制两大类。在对称密 码体制中，加密密钥x 。与解密密钥蜀是相同的，统称为k 。而在公钥密码体制 中，加密密钥丘与解密密钥黑。是不同的，其中足。公开，且不会影响是。的安全 性：但是它必须满足对任意朋，有d 局但丘) = 肌 4 中山大学硕士学位论文 数字签名的公平交换 下面给出的是一个密码体制的模型：( 图2 1 ) 望回奎茎，困堡塑望马 发送者 口 通信通道 口 接收者 加密密钥解密密钥 图2 1 密码体制模型 一个好的密码体制至少应该满足下述两个条件【2 】： ( 1 ) 在已知明文m 和加密密钥e 时，计算密文c = 咖) 容易。在已知密文c 和解密密钥岛时，计算明文埘= d 岛( c ) 容易。 ( 2 ) 在不知解密密钥蜀时，不可能由密文c 推知明文m 密码分析者通常可以在下述四种情况下对密码体制进行攻击【2 】： ( 1 ) 唯密文攻击：密码分析者仅知道一些密文。 ( 2 ) 已知明文攻击：密码分析者知道一些明文和相应的密文。 ( 3 ) 选择明文攻击：密码分析者可以选择些明文，并得到相应的密文。 ( 4 ) 选择密文攻击：密码分析者可以选择一些密文，并得到相应的明文。 其中唯密文攻击的强度最弱，其他情况下的攻击强度依次增加。 2 1 2 对称密码体制 对称密码体制的特点是加密和解密共用一把密钥，即x 。= j 0 ，所以又称 “单密钥体制”。它历史悠久，据说恺撒大帝就曾经在战争中使用过。在对称密 码体制中，密码按加密方式不同可以分为分组密码与序列密码。分组密码是按字 符块加密的；而序列密码是逐个字符加密的。关于它们的详细介绍，可参见【5 】。 值得注意的是，对称加密的算法是公开的，交换信息的双方不必交换加密算 法，面是采用相同的加密算法，他们只需要交换加密密钥。 对称密码体制存在的弊端： ( 1 ) 必须提供一条安全的渠道。使得通信双方在首次通信时协商一个共同的密钥。 5 中山大学硕士学位论文 数字签名的公平交换 ( 2 ) 对于不同的接受者要使用不同的密钥，使得密钥的数目往往很大，难以管理。 ( 3 ) 密钥的管理和分发工作很繁琐，而且具有潜在危险。 因此，需要找到一种加密体制，能够解决以上弊端。 2 1 3 公钥密码体制 1 9 7 6 年，美国学者d j 舾e 和h e l l m a n 提出了公钥密码学的思想【1 9 】，从 而引起密码学的一场革命。在公钥密码体制中，加密密钥和解密密钥是不同 的。用户的加密密钥可以公开，登记在网络的密钥数据库中，就像把自己的 电话号码公开在电话号码簿上一样。任何人打算跟某个用户u 通信，只要在 公开的密钥数据库中查得用户u 的加密密钥，并用它把明文加密成密文传送 给用户u 。用户u 可以用仅有自己知道的解密密钥对收到的密文进行解密， 恢复出明文，从而完成保密通信。 公钥密码体制从根本上解决了密钥分配和消息认证等问题，特别适合于 计算机网络系统的应用。它的缺点是运算速度较慢。因此，它比较适合于对 少量数据的加密。 公钥密码体制的理论基础是求解某些数学难题的困难性。至今，学者们 提出了许多种公钥加密方法。根据所基于的数学难题来分类，以下两类系统 目前被认为是安全有效的：( 1 ) 大整数因子分解系统( 代表性的有r s a 加密) ， ( 2 ) 离散对数系统( 代表性的有e l g a m a l 加密) 。 ( 1 ) r s a 公钥密码 当今应用最广泛的公钥系统r s a 是由麻省理工学院的础v c s t ，s h 跏i r a d e l m 蛆于1 9 7 8 年提出的【2 0 】，它的安全性是基于大整数因子分解的困难性。 此密码体制如下： ( 1 ) 选取两个不同的大素数p ，口，将其保密。 ( 2 ) 计算n = 朋，刀公开；垂o ) = ( p 一1 ) 国一1 ) ，垂m ) 保密。 ( 3 ) 随机选取正按数p ( 1 ，o ) ) ，使其满足g c d 0 ，中0 ) ) = 1 ，e 即为公开 的加密密钥。 6 中山大学硕士学位论文 数字签名的公平交换 ( 4 ) 计算d ，满足如；1 m o d 中0 ) ，d 即为保密的解密密钥。 ( 5 ) 加密变换：对明文m z 。，生成密文c = m 。m o d n ( 6 ) 解密变换：对密文c z 。，恢复明文埘= c 。m o d n 利用e u l e r 定理f 4 】，容易证明解密变换是加密变换的逆变换。 r s a 公钥密码体制原理简单，易于使用。随着计算机速度的不断提高， 目前，一般认为r s a 的密钥要求具有1 0 2 4 位以上的字长才能保障其安全。 关于r s a 体制安全性的讨论，可参见f 5 】。 ( 2 ) e l g 姗a l 公钥密码 e l g a m a l 公钥密码体制是由t e l g 锄a l 于1 9 8 5 年提出的【2 1 】，它是一种 基于离散对数的公钥密码系统。有限域z 。上的离散对数问题是这样描述的： 设p 是一个素数，a z ；，口是一个本原元，z ；，已知口和，求满足 口。= m o d p 的唯一整数d ，d 【0 ，p 一2 】，称为有限域上的离散对数问题。 此密码体制如下： ( 1 ) 选取大素数p ，口z ：是一个本原元，p 和盯公开。 ( 2 ) 随机选取整数d ，d n p 一2 1 ，计算卢= 口。m o d p 即为公开的加密密钥，d 即为保密的解密密钥。 ( 3 ) 加密变换：对明文m z ；，随机选取一个秘密整数七，七【1 ，p 一2 】， 生成密文为c = ( c l ，c 2 ) ，其中c 1 = 口m o d p ，c 2 = 朋m o d p ( 4 ) 解密变换：对密文c = ( c 。，c ：) ，恢复明文卅= c ：( c 。4 ) 1m o d p 容易证明解密变换能正确地从密文恢复相应的明文。 在e l g 蛐l a l 公钥密码体制中，密文依赖于明文肘和秘密选取的随机 整数七 因此，明文空问中的一个明文可以对应密文空间中的许多不同的密 文。在此体制中，= 口。m o d p ，从公开的口和，求保密的解密密钥d ， 7 中山大学硬士学位论文数字签名的公平交换 就是求解一个离散对数。截至目前，还没有找到一个非常有效的多项式 时间算法来计算有限域上的离散对数。因此，e l g 锄a l 公钥密码体制的安 全性主要是基于有限域z ，上离散对数问题的难解性。 2 1 4 混合密码体制 尽管公钥密码体制能够克服对称密码体制的缺陷，但其加解密运算 实现速度比对称密码体制慢得多。所以，在现实生活中，两种密码体制 往往结合使用。例如，利用公钥密码体制来传递会话密钥，这样，会话 密钥在网络中就能比较容易地分配和传输了。 2 2 数字签名 2 2 1 概述 数字签名，顾名思义，就是日常生活中手写签名的电子对应物，它主要 用于对数字消息进行签名，以实现用户对数字消息的认证。它与传统的手写 签名有如下区别1 2 】： 首先，手写签名是被签署文件的物理组成部分，雨数字签名不是，所以 所使用的数字签名方案必须设法使签名“绑”到所签名的文件上。 第二，手写签名不易拷贝，而数字签名正好相反，因此必须阻止一个数 字签名消息被重复使用，一般通过要求消息本身带有诸如日期等信息来达到 阻止签名被重复使用的目的。 第三，手写签名是通过与一个真实的手写签名比较来进行验证，而数字 签名是通过一个公开的验证算法来验证，数字签名是由0 和1 组成的数字串， 它因消息而异，当出现争端时，它能够为仲裁者提供足够的证据来进行裁决， 因此，其安全性远远高于手写签名此外，数字签名依托于计算机网络，其 时效性也远远大于手写签名。 数字签名具有如下特性【2 】： ( 1 ) 签名是可信的：任何人都可以验证签名的有效性。 8 中山大学硕士学位论文 数字签名的公平交换 ( 2 ) 签名是无法伪造的：除了合法的签名人之外，其他任何人伪造其签名困 难的。 ( 3 ) 签名是不可重复使用的：对一个消息的签名不能通过复制变为另一个消 息的签名。否则，任何人都可以发现消息与签名之间的不一致性，从而可 以拒绝签名的消息这可以防止签名滥用。 ( 4 ) 签名的消息是不可改变的：经签名的消息不能被篡改。否则，任何人可 以发现消息与签名之间的不一致性。 ( 5 ) 签名具有不可否认性：签名人事后不能否认自己的签名。 随着计算机信息网络的迅速发展，特别是电子商务的兴起，数字签名的 使用越来越普遍数字签名是防止信息欺诈行为的重要保障 2 2 2h a s h 函数 h 弱h 函数是一种将任意长度的消息压缩为某一固定长度的消息摘要的 函数。一个密码学上安全的h a s h 函数日应具备以下性质1 5 】： ( 1 ) 单向性：给定消息x ，计算日g ) 是容易的：但给定何 ) ，计算x 却 是困难的。 ( 2 ) 抗碰撞性；寻找两个不同的消息x 和r 使得日d = 日o ) 是计算上 困难的。 h a s h 丽数常常用于数字签名，这样可以提高签名的速度，并有利于防止 伪造签名。 2 2 3 数字签名方案 公钥密码体制的提出，不仅解决了密钥分配的困难，两且可以用来设计 数字签名方案。下面给出的是基于公钥密码的一般数字签名方案的签名和验 证过程1 2 】。假设a 要发送签名给b 。 ( 1 、a 用其保密的私钥对消息坍加密密文5 就是a 对消息m 的签名 ( 2 ) a 将签名的消息 ，s ) 传送给b ( 3 ) b 用a 的公钥对s 进行解密，得到小若州= m ，则确认对j 是a 对 9 中山大学硕士学位论文数字签名的公平交换 消息脚的有效签名：否则为无效签名。 在上述的签名方案中，a 使用公钥密码的解密变换来对消息进行签名。由于 解密变换是保密的，只有a 自己知道，所以只有a 能对任意消息进行正确签名。 另一方面，由于加密变换是公开的，所以任何人都可以验证签名的有效性。 但是，并不是每一个公钥密码体制都可以按照上述方式来设计数字签名方 案，只有满足e ( 以。o ) ) = z 的公钥密码体制才可按上述方式来设计数字签名方 案。 一般数字签名方案包括3 个过程：系统的初始化过程、签名的产生过程 以及验证过程【2 2 】。 系统的初始化过程产生该方案所用到的参数；签名的产生过程中，签名 者a 利用其私钥对消息产生签名；签名验证过程中，验证者b 利用相应的 公钥验证签名的有效性。下面，我们将描述两种不同的签名方案： ( 1 ) r s a 签名体制 ( 1 ) 初始化 n = 朋，p 和q 是秘密的大素数，中0 ) = q 一1 ) 臼一1 ) ； 整数e 满足g c d 以西o ) ) = 1 ：整数d 满足出；1 m o d o ) ： a 的私钥为( d ，零o ”，公钥为和，n ) ，抒为单向h 笛h 函数。 ( 2 ) 生成签名 对于待签名的消息埘，a 先计算h ) ， 然后计算5 = h 伽，m o d ， 得出生成的签名即为s ( 3 ) 验证签名 收到签名( m ，s ) 后，b 计算日如) ， 判断) = ，是否成立； 若成立，则s 即为a 对m 的有效签名。 关于r s a 签名的安全性讨论可参见【5 】。 中山大学硕士学位论文数字签名的公平交换 ( 2 ) s c h n o f r 签名体制 ( 1 ) 初始化 p ，目为大素数，且日陋一1 ) ；g z ；，且9 9 = 1 m o d p ； a 的私钥并n q ) ，公钥_ ) ，= 9 1 m o d p ，日为单向h 鹤h 函数。 ( 2 ) 生成签名 对于待签名的消息m ，a 先选择随机数七仉口) ， 计算e = 日( r ，m ) ，然后计算5 = 和+ m o d 鼋， 得出生成的签名即为忙，5 ) ( 3 ) 验证签名 收到签名( m ，e ，s ) 后，b 先计算，= g y 1m o d p ， 然后计算( ，埘) ，判断h ( r ，州) = e 是否成立。 若成立，则0 ，5 ) 即为a 对m 的有效签名。 关于s c h l l o 玎签名的安全性证明可参见【2 3 ，2 4 】。 2 3 基于身份的密码体制 2 3 1 概述 1 9 “年，s h a m i r 首次提出基于身份的密码体制思想【2 5 】，其目的是为了简化 p 的密钥管理以及取消公钥证书的使用。它将用户的个人身份信息( 如姓名、 身份证号、b m a j l 地址等) 作为他本人的公钥。根据身份信息，只有p k g ( 可 信中心) 能够计算出每个人的私钥。在这种体划下，用户不再需要公钥证书，从 而提高了管理的效率及系统的安全性。这种密码体制是通过椭圆曲线上的双线性 对来实现的。 双线性对是于1 9 9 3 年由m e n e z 胬【2 6 】等引入到密码学研究当中，其目的是 用来攻击超奇异椭圆曲线上的离散对数问题。当时，双线性对的存在被视为起消 极作用。2 0 0 0 年，s a l 【a i 【”1 等人和j o u x 【2 8 1 分别独立发现双线性对可以用来构建 1 1 中山大学硕士学位论文 数字签名的公平交换 新的密码方案。在这以后，利用双线性对构建的密码方案接二连三地涌现，如基 于身份的加密方案【2 9 ，3 0 ，3 1 】，短签名方案【3 2 ，3 3 】，基于身份的签名方案 【3 4 3 5 ，3 6 】，三方密钥协商方案f 2 8 】等等。 下面，我们将简要介绍双线性对的基础知识。 设g 1 和g ：是两个阶为目的循环群，q 为大素数。定义双线性映射 e ：g l g l g 2 满足以下性质： ( 1 ) 双线性：e ( 口p ，6 q ) = p ( p q ) ”，对v p ，q g l ，6 z 。成立； ( 2 ) 非退化性：j p ，q g ，使e ( p ，q ) 1 ； ( 3 ) 可计算性：存在一个有效算法计算8 ( p q ) ，对、q g ， 下面我们描述椭圆曲线上的数学闯题： ( 1 ) 离散对数问题( d l p ) 给定g ，中的两个元素p ，q ，计算整数斗，使q = 廿 ( 2 ) 确定离散对数问题( d d h p ) 对口，6 ，c z ：，给定g l 中元素p ，口p ，卯，c p ，判断是否c ；曲m o d g ( 3 ) 计算离散对数问题( h p ) 对口，6 z ：，给定g l 中元素p ，口p 护，计算口6 p 当某个群g 上的d d h p 是容易的，而c d h p 是困难的时，我们称群g 为 间隙群。这样的群可以在有限域上的超奇异椭圆曲线上找到。 2 3 2 基于身份的签名方案 双线性对可以用来构建基于身份的签名体制。这种体制由以下四个算法组成： ( 1 ) 初始化：p k g ( 可信中心) 随机选择整数s z ：，计算j k = 妒，5 称为主 密钥，由p k g 保密，并将p ，厶等系统参数公之于众。 ( 2 ) 私钥获取：用户给出身份信息，由p k g 计算并返回用户的私钥。 ( 3 ) 签名：用户利用其私钥及系统参数，计算出对消息的签名。 ( 4 ) 验证：验证者利用系统参数以及用户公钥，判断出消息的签名是否有效。 中山大学硕士学位论文 数字签名的公平交换 下面，我们将描述一个基于身份的签名方案，此方案由c h a 和c h e o n 给出 【3 4 】，它由以下四个算法组成： ( 1 ) 初始化：p k g ( 可信中心) 随机选择整数s z ：，计算= 妒，5 称为主 密钥，由p k g 保密，并公布系统参数j 口r m ： g 。，g ：，岛g ，只f k ，日，h 。) ，其中 g l ，g 2 为口阶循环群，e ：g l g 1 斗g 2 ，h ： 0 ，q 一g l ，h l ： 0 甜g l 寸z 。 ( 2 ) 私钥获取：用户给出身份信息i d ，p k g 计算q = h ( ) ，并返回用户的私 镇d i d = s q m ( 3 ) 签名：要对消息m 签名，用户任选随机数，z 。，计算u = ，c = h ，( ，) ， 矿= ( ，+ c 矽。；签名即为仃= 缈，y ) ( 4 ) 验证：接收到消息m 和签名盯= ，y ) 后，验证者检验等式 e ( p ，y ) = e ( ，k ，+ c q 。) 是否成立，其中c = 日。伽，u ) ，当且仅当该等式成立 时接受签名。 该方案在r a n d o mo r a c l e 模型下【3 7 】可证明是安全的。 2 3 3 短签名 双线性对除了可以用来构建基于身份的签名方案，还可以用来构建短签名方 案。短签名的特点是：在同样安全的级别下，它的字节数比普通签名要小得多， 所以特别适用于带宽较小的通讯环境里，以节约信息通讯的成本。 短签名方案由以下四个算法组成： ( 1 ) 初始化：设置系统参数，并公之于众。 ( 2 ) 密钥生成：用户随机选择整数s z ：作为私钥，其对应的公钥厶。= 妲 ( 3 ) 签名：用户利用其私钥及系统参数，计算出对消息的签名。 f 4 ) 验证：验证者利用系统参数以及用户公钥，判断出消息的签名是否有效。 下面，我们将描述两种短签名方案，它们均可以在任意一个间隙群中实现。 方案( 一) ：此方案是由b 彻e h ，l y 越和s h a c h 锄提出【3 2 】，它由以下四个算法组 中山大学硕士学位论文 数字签名的公平交换 成： ( 1 ) 初始化：设置并公布系统参数n 阳埘5 ： g | ，g ：，e ，口，尸， ，其中g 1 ，g ：为口阶 循环群，e ：g l g 1 一g 2 ，尸g l 为任一生成元，疗： o 册斗g 1 ( 2 ) 密钥生成：用户任选整数5 z ：作为私钥，其对应的公钥p 柚= 铲 ( 3 ) 签名：要对消息历签名，用户计算盯= 讲( m ) ，盯即为m 的签名。 ( 4 ) 验证：接收到消息m 和签名d 后，验证者检验等式p ( p ，仃) = 8 ( p 劬，h 沏) ) 是 否成立，当且仅当该等式成立时接受签名。 该方案在r a n d o mo r a c l e 模型下可证明是安全的【3 2 】。 方案( 二) ：此方案是由f z h a n ge ta 1 1 3 3 】提出，它由以下四个算法组成： ( 1 ) 初始化：设置并公布系统参数n ，口肌s ： g 。，g 2 ，8 ，吼p ，日) ，其中g 。，g ：为q 阶 循环群，p ：g 1 g l _ g 2 ，p g 1 + 为任一生成元，日为单向h a s h 函数。 ( 2 ) 密钥生成：用户任选整数s z ：作为私钥，其对应的公钥j k = s p ( 3 ) 签名：要对消息m 签名，用户计算盯2 赤p ，盯即为朋的签名a ( 4 ) 验证：接收到消息聊和签名仃后，验证者检验等式 e ( p p ) = e ( 尸0 + 日( m ) 只盯) 是否成立，当且仅当该等式成立时接受签名。 该方案在r a n d o m0 r l c 模型下可证明是安全的，而且比方案( 一) 更加有效f 3 3 】。 2 4密码协议 2 4 。1 基本概念 协议是指两个或两个以上的参与者为完成某项任务所采取的一系列步骤。这 些步骤是有序的，必须依次执行，在前一步骤完成之前，后面的步骤不能执行。 协议至少需要两个参与者。一个人也可以通过执行一系列步骤来完成某项任务， 但它不构成协议。另外，通过执行协议必须能够完成某项任务，达到某种目的。 1 4 中山大学硕士学位论文 数字签名的公平交换 协议具有以下特点【2 】： ( 1 ) 协议的每个参与者都必须了解协议，事先知道所要完成的所有步骤。 ( 2 ) 协议的每个参与者都必须同意并遵循协议。 ( 3 ) 协议必须是清楚的，也就是说，每一步骤必须明确定义，不会引起误解。 ( 4 ) 协议必须是完整的，对每种可能的情况都要规定具体的操作。 所谓密码协议就是应用密码技术构造的协议。参与密码协议的各方可能 相互信赖，也可能互不信任。密码协议的目的就是在完成某项任务的同时， 不仅能够避免敏感信息被窃听者窃取或篡改，还要能够发现或防止协议参与 者彼此之间的欺骗行为。 密码协议在网络通信中有着重要的应用价值。目前已有各种各样的用于 不同目的的密码协议。近年来，随着电子商务的兴起，密码协议越来越受到 人们的重视。对于电子商务中不同的交易模式需要建立不同的密码协议。 2 4 2 零知识证明 零知识证明是现代密码学中的个十分引人入胜的问题。假设p 是某些 秘密信息的拥有者，p 想向v 证明自己掌握这些秘密信息。v 是验证者，v 验证p 是否真的掌握这些秘密信息。所谓零知识证明就是指p 设法使v 相 信自己掌握这些秘密信息，同时又不向v 泄露这些秘密信息【2 】。 零知识证明常用来设计身份鉴别等协议。关于它的详细介绍，可参考有 关书籍【1 ，4 】，这里不再赘述。 中山大学硕士学位论文 数字签名的公平交换 第3 章公平交换协议 3 1 概述 随着社会信息化的发展，网络成了人们工作与生活不可缺少的平台，电子商 务因其方便快捷日益受到人们的喜爱，已成为现代经济活动的主要形式之一。然 而，尽管人们看好电子商务的发展前景，但对电子商务大规模、大范围的使用却 顾虑重重。顾虑的根源就在于电子商务诚信度不够。消费者所关心的是：你手上 有我要的东西，我付了钱之后能不能收到我要的东西? 如果收不到，我找谁要回 我的钱? 由于存在这样的疑惑，许多消费者对网上购物持怀疑态度。因此，如何 在任意两个互不信任的主体之间以一种高效、公平的方式来交换电子数据，是基 于信息技术的商务活动的主要阀题。公平性和高效性成为这类电子商务协议的基 本要求。公平交换协议应该使得参与交换的双方以公平的方式交换信息。这里的 公平是指：要么任何一方都可以得到对方的信息，要么双方都得不到对方的信息。 正由于公平交换协议在应用领域的重要性，所以一直得到研究人员的广泛关 注，也提出了各种各样的方案。现有的公平交换协议大致可以分为以下三种类型： ( 1 ) 逐步秘密交换：这种方案是由o k 咖。幻等人提出f 9 】，其思想如下： 假设a 和b 分别拥有一位秘密信息x 。和巩，他们双方打算交换秘密。另 外，事先已定义两个单向函数，o ) ，g o ) 。交换过程是这样进行的： 首先a b ：，( x 。) 且b a ：g ( 邑) 然后a 与b 逐位交换x 。和五的每一位信息，直到以位信息交换完毕。 此协议必须满足以下性质： ( 1 ) 交换的每一位信息都必须能够让接受者检验，以确信此位信息是有效的。 ( 2 ) 双方必须拥有同等的计算资源，否则拥有优越资源的一方可以作弊而从 中获利。 此协议的弊端是显而易见的： 中山大学硕士学位论文数字签名的公平交换 ( 1 ) 双方需要交互多次，通讯成本很大。 ( 2 ) 双方拥有的计算资源通常是不相等的，这使得公平性难以得到保证。 ( 2 ) 使用在线的可信第三方( 即t 坤) ：这种方案是由j z h o u 等人提出 【1 1 】，其思想是这样的：a 和b 各自把自己的秘密信息发给r r p ，由 下r p 验证信息的有效性。如果信息均有效，则r r p 分别将信息转发 给对方。显然，这样的协议能够保护交易双方的公平性，而且很容易 设计。然而，此协议存在一个很大的弊端：即使双方诚实地进行合作， r 冲也不得不参与交换活动。这样无论在计算上还是在通信上，f 曙 都会成为一个瓶颈，使得这类协议的效率不会很高。 ( 3 ) 使用离线的r r p ：这种方案首先是由a s o k 抽等人提出【6 】，在此协议 中，r r p 只有在交易的某一方有欺诈行为时才介入交换活动。然而， 此协议还不具有完全的公平性。当一方被对方欺骗时，t r p 只能开证 明来说明某一方在交易过程中蒙受损失。第一个具有完全公平性的协 议是由f c n g b a o 等【1 3 1 提出来的，它具有预防损失的特性。也就是说， 无论哪一方采取任何不当行为，都不会给对方造成损失。因而交易的 结果是双方要么都如愿以偿，要么都一无所获。具有完全公平性的协 议又称为优化公平交换协议。 优化公平交换协议效率较高，所以是当前公平交换协议研究的热点。 在本文中，我们指出，优化公平交换协议可以由以下基本模型来构造，记为 协议( 3 1 ) 。假设a 与b 欲交换各自的签名s 。，瓦，在一般情况下，协议( 3 - 1 ) 由三步交互组成( 为了简化，假定通信渠道是安全的) 。 协议( 3 - 1 ) ： a b ：z 岱。) b a ：s 5 a 斗b ：s 。 1 7 中山大学硕士学位论文数字签名的公平交换 说明：( 1 ) r 岱。) 是对签名s 。的一种变换，协议的关键就在于构建丁 。) ， 使得只有t t p ( 或a ) 能够将r 。) 恢复出5 。，b 不能恢复出s 。，但b 能够检 验丁p 。) 的有效性。t 。) 有效则意味着r 仲一定能够将其逆变换得出s 。 ( 2 ) 无论在哪一步( a 或b ) 找r r p 解决目题时，都必须将自己的签名提 交给t r p ，由t 1 p 保存以备用，以免哪一方使诈骗取r r p 帮助而不履行自 己的义务。 ( 3 ) 协议在双方诚实地交易时只需三步就可完成；只有在出现不诚实行 为时，r r p 才参与处理交易，使得协议十分简洁、高效。 此协议的安全性要求如下： ( 1 ) a 若企图生成r ( s 。) 通过验证，且让r r p 无法将r 。) 逆变换恢复 s 。，这应该是计算上不可行的。 ( 2 ) b 若没有r r p 的帮助，自己企图将r 岱。) 逆变换恢复s 。，这应该是 计算上不可行的。 ( 3 ) t r p 若没有得到r 岱。) ，自己企图生成s 。，这也应该是计算上不可 行的。 要设计优化公平交换协议，关键就在于如何构建t 。) 。构建岱。) 目 前主要有三种思想，我们将在下文中分别叙述。 3 2 基于可验证加密酶签名 3 2 1 在公钥证书体制下的实现 这种思想是由f e n gb 等人于1 9 9 8 年提出来的【1 3 】。意思是指r 。) 是 使用可验证加密的签名来构建。也就是说，第一步a 发送给b 的不是a 的 签名s 。，而是对s 。加密后的密文r 。) ( 用t r p 的公钥来加密) 。b 能够验 证r ( s 。) 的有效性，r 。) 有效，则说明t r p 能够将指r $ 。) 恢复出s 。这 中山大学硕士学位论文数字签名的公平交换 种思想的特点是：r p 。) 意味着签名s 。不可见。 在【1 3 】一文中，f e n gb a o 引入了c e m b s 的概念，血m b s 是c c r t i f i c a t e o f e n c r y p t c d m e 鼯a g c b e i i l ga s i g n a t u r c 的缩写。它是一种证书，目的是证明 被加密的内容是指定方对一已知文件的签名，但不泄露此签名。它的构建原 理如下【1 3 】： 假定蹦，和豚，分别为r r p 的公钥与私钥，p 七。和娃。分别为a 的公钥 与私钥，s 。= s 螂( 话。，用) 是a 对已知文件肌的签名，c r = ( 麒，s 。) 是 对签名s 。用p 酶加密所产生的密文。a 产生c ，后，也产生c e m b s ，用c 打r 表示，其目的是证明g 是对签名s 。的加密同时又不泄露s 。存在一种公众 可验证算法娩，f ，在输入c 打f ，c r ，肌，p k ，p 七。，输出“1 ”( 有效) 或者o ” ( 无效) ，即删( c 打f ，c r ，小，p 七 ) = 1o f 0 若输出值为“l ”j g = 酶，s 。) 且s 。( 加。，s 。，m ) = 1 则此时若用腻，来对c ，进行解密，得到的结果就是a 对m 的签名s 。 所以，根据这种思想，设计公平交换协议如下【1 3 】： a _ + b ：c ，r f b 呻a ：咒 a b ：s 。 f e n g b 指出，c e m b s 可以在e l g 啪a l 加密体制【2 1 】与d s a 签名体制 【3 8 1 实现，也可以在e l g 锄l 加密体制与g 0 签名体制【3 9 】实现。a t e n i e s c 迸一步给出c e m b s 在各种普通常见的签名体制的实现f 4 0 】这样就使得此 公平交换协议可以获得广泛的应用。下面，我们将描述江m b s 在g q 签 名体制与e l g 皿a l 加密体制的实现，这是a t e n i c 分析f c n gb a 0 的方案【1 3 】 后给出的一种改进的方案【4 0 卜 首先，我们描述g - q 签名体制【3 9 】。 1 9 中山大学硕士学位论文 数字签名的公平交换 ( 1 ) 初始过程 n = 朋，其中p = 2 p + 1 ，留= 2 口+ 1 ，p ，g ，p l ，矿均是大素数， v 是系统参数；a 的秘钥呔z 。，公钥j z 。+ ，且( 政) ”j = 1 m o d 咒 h ： o 册一 o ，廿m ； 公开参数：肛，v ，j ，日； 秘密参数：p ，g ，如。 ( 2 ) 生成签名 a 随机选择r z 。，计算r = ，”m o d n ； 计算d = h 仰，r ) ，d = r ( 睹 ) 4 m o d ，i ， 则 ，d ) 即为a 生成的数字签名。 ( 3 ) 验证签名 计算了= 日似，d 0 4 ) 判断万= d 是否成立： 若成立，则q ，d ) 就是a 对卅的数字签名。 系统使用在( z + ，g ) 上的e l g 蛐a l 加密体制，有 p ：e l g 锄a l 系统在( z 。，g ) ，其中g q ，d ( g ) = p 鼋i ； 1 r i 甲的s k r 【1 ，鼋一1 】。p r = g g rm o d 件； 用尸墨对签名s 加密，有( ，s ) = ( 职矿) ； 其中形= g m o d ，y = s 俨b ) m o d 甩，七z 。+ ， 记( 矽，y ) 为g ，解密过程为s = 吉m 。d 弹 a 产生a i m b s