（应用数学专业论文）对英式电子拍卖协议的研究.pdf

对英式电子拍卖协议的研究 专业：应用数学 硕士生：黄中杰 导师：王燕鸣教授 摘要 随着互联网的迅速发展，网上电子拍卖商务活动的日益增多，电子拍卖 交易也迅速的发展起来。到目前，已经有很多有关电子拍卖系统和协议的 论文发表。电子拍卖主要有两种方式，一种是封闭式电子拍卖s e a l e d - - b i d a u c t i o n ，这种拍卖的投标的内容是不公开的；另一种是英式电子拍卖，这 种拍卖的投标的内容是公开的。本文主要研究英式电子拍卖协议。在英式 电子拍卖中，所有的投标标值都会即时在公告板上张贴出来，每个竞拍者 都能从公告板上看到投标的暂时最高值，并以此为根据调整个人的投标策 略，选择投出更高的投标，或是放弃竞逐。首先，本文会先回顾以前的几 个协议，对这些协议进行分析，指出其中的问题。在2 0 0 0 年，k 。n g u y e n 和j t r a o r 6 基于群签名方案提出了一个英式电子拍卖1 1 0 ，但是，群签名本 身运算量太大，而且群经理本身能打开群成员的签名，这样，投标人的匿 名性得不到实现。2 0 0 1 年，k a z l l m a s ao m o t o 和a t s u k om i y a j i 【1 6 】基于 e l g a m a l 公开密钥系统，引入电子公告板，提出了一个只需一次注册的英 式电子拍卖方案。由于引入了公告板，拍卖过程中能轻易的撤销一个无效 的投标和身份，但是该方案在宣布获胜者阶段时，r m 只是秘密的将获胜者 的信息送给卖方，其它竞拍人不能公开验证该获胜者的身份。如此，没人 知道r m 是否正确地将获胜者身份传送给卖方，或者是否真的有人投出了 比自己高的投标。为解决以上问题，本文在e l g a m a l 公钥系统基础上， 引入可信第三方，运用知识证明签名等知识，基于离散对数的困难性提出 一个新的电子拍卖协议，该协议满足所有电子拍卖协议的要求，并且最后 可以公开验证获胜者的身份。 关键词：英式电子拍卖协议，e l g a m a l 公钥系统，可信第三方，知识 证明签名，离散对数的困难性，可公开验证获胜者身份 s o m er e s e a r c h e so ne l e c t r o n i c e n g l i s ha u c t i o np r o t o c o l m a j o r ：a p p h e dm a t h e m a t i c s n a m e ：h u a n gz h o n 萄i e s u p e r v i s o r ：w a n gy a n m i n g a b s t r a c t e l e c t r o n i ca u c t i o nc o m m e r c eh a sm a d eg r e a tp r o g r e s si nr e c e n ty e a r se x d t e d b yt h ef a s t m o v i n go ft h ei n t e m e ta n da c t i v a t e db yt h ef a s tm o v e m e n to ft h e e l e c t r o n i cc o m m e r c e u pt on o w ，t h e r eh a v eb e e nm a n ye l e c t r o n i ca u c t i o n r e l a t e ds y s t e m sa n dp r o t o c o l s t h e r ea r et w of o r m so fe l e c t r o n i ca u c t i o n o n ei s s e a l e d - b i da u c t i o no fw h i c ht h eb i di n f o r m a t i o ni ss e a l e d ，a n dt h eo t h e ri s e n g l i s hp u b l i ca u c t i o no fw h i c ht h eb i di n f o r m a t i o ni so p e n i nt h i sp a p e r , w e f o c u so nt h ee l e c t r o n i ce n g l i s ha u c t i o n i nt h i sp u b l i ca u c t i o n ，a rt h eb i dv a l u e s a r e p u b l i s h e do na b u l l e t i nb o a r d ；a l lt h eb i d d e r sc a nr e a dt h ei n t e r i mh i 曲e s tb i d t h e r e f o r e ，t h e yc a nm a k eu pt h e i rn e x tb i d sa c c o r d i n gt ot h i sh i g h e s tb i d a t f i r s t ，w ew i l ll o o kd e e pi n t os o m ep r e v i o u ss c h e m e sa n dt h e np o i n to u ts o m e t h e i rp r o b l e m s i n2 0 0 0 ，k n g u y e n 和j t r a o r dp r o p o s e das c h e m e 【1 0 】u s i n ga m o d i f i e dg r o u ps i g n a t u r e ，h o w e v e r ，i ts u f f e r sf r o mt h ei n e f f i c i e n c yo ft h eg r o u p s i g n a t u r e m o r e o v e r , t h eg r o u pm a n a g e rc a no p e nt h es i g n a t u r eo fm e m b e r so f t h e g r o u p ，s o t h i ss c h e m ec a nn o t r e a l l ys a t i s f y t h e a n o n y m i t y i n 2 0 0 1 。k a z u m a s ao m o t o 和a t s u k om i y a j ii n t r o d u c e db u u e t i nb o a r dt op r o p o s e a n o t h e rs c h e m e 【1 6 】w i t ho n et i m er e g i s t r a t i o nw h i c hi sv e r ye a s yt or e v o k ea i n v a l i db i da n di d e n t i t y a n dt h ep r o b l e mo ft h i ss c h e m ei st h a ti fab i d d e ri s v e r i f i e dt ob eaw i n n e r , h i si d e n t i t yc a nn o tb ep u b l i s h e d h i si d e n t i t yi st ob e s e n tt ov e n d o rs e c r e t l y i ti su n f a i rb e c a u s eo t h e rb i d d e r sc a nn o tv e r i f yt h a tt h i s i d e n t i t yi sa sa u t h o r i z e do n e s ot h e yc a l ln o tb es u r eo ft h ev a l i d i t yo fa u c t i o n i nt h i s p a p e r ，an e wp u b l i ca u c t i o ns c h e m ew h i c h i sb a s e do nd i s c r e t e l o g a r i t h mp r o b l e m a n du s e ss o m ec r y p t o g r a p h i c a lt o o l ss u c ha se l g a m a lp u b l i c k e ys y s t e m ，a n ds i g n a t u r eo fk n o w l e d g e ， i sp r o p o s e d i nt h i ss c h e m e ，a t r u s t e dc e n t e ri si n t r o d u c e d t h i ss c h e m es a t i s f i e st h er e q u i r e m e n t so ft h e s t a n d a r do ft h ee n g l i s hp r o t o c o la n dc a np u b l i c l yv e r i f yt h ei d e n t i t yo ft h e w i n n e r k e y w o r d s ：e n g l i s hp u b l i ca u c t i o n ，d i s c r e t el o g a r i t h mp r o b l e m ，e l g a m a l p u b l i ck e ys y s t e m ，s i g n a t u r eo fk n o w l e d g e ，t r u s t e dc e n t e r ， v e r i f yt h ei d e n t i t yo fw i n n e r 中山大学硕士学位论文 第1 章引言 拍卖是一种特殊的商品交易形式，现实生活中些没有固定价格的，但却有非 同一般的意义或价值的东西，都可以成为拍卖场上的商品，如一些古董珍品，某 名人用过的东西等。随着互联网的迅速发展，网上电子商务活动的日益增多，电 子拍卖交易也在i n t e r n e t 网上快速地开展起来，也出现了许多网上电子拍卖系统。 网上拍卖只不过将传统的拍卖过程放在网上进行，然而，网上拍卖明显具有传统 拍卖方式不具备的许多优势，例如，网上拍卖可以用多媒体( 照片、录像资料等) 手段为潜在客户展示拍卖货物的方方面面；拍卖物在交易完成前没有必要像传统 拍卖那样做物理上的转移；交易双方也没有必要都到一个拍卖场地去验视货物和 参与实物运作过程。除此之外，网上拍卖在服务功能上并不比传统拍卖市场逊色 多少。网上拍卖还通常提供与拍卖过程相配套的一系列服务，比如达成交易、支 付货款，以及办理运输等等。对于拍卖者和竞买者来说，网上拍卖的好处是高效 率以及时间的节省，网上潜在客户遍及全球，还大大增加了拍卖成功的可能性。 由于网上拍卖的成本很低，许多低价值的小玩意儿，或者是二手货都可以拿出来 拍，这样对于拍卖品提供者来说，好处是更加充分的利用了手中的资源取得了收 入，减少了不需要的东西，而且交易的成本很低；对于竞买者来说，他们用很低 的价格和交易费用买到了自己喜欢或者需要的东西，而且省时省力。目前电子拍 卖主要有以下两种形式：( 1 ) s e a l e d b i da u c t i o n 秘密拍卖，卖方首先公开 待拍物品的资料，买主在竞拍开始后将自己的所属意的价格写在标书上，并以密 封形式投标，在卖家宣布投标结束后打开标书，由出价虽高者或第二高者成交。 ( 2 ) e n g l i s ha u c t i o n 英式公开拍卖，是最普遍的一种交易形式。用户一个接一 个地投出他们投标( 每一个投标都要比它前一个投标的值高) ，交易期限一到， 交易也同时停止，物品将卖给出价最高者。两种拍卖各有其优缺点。s e a l e d - - b i d a u c t i o n 比较简单，安全性也高，只要传递投标的媒介是安全的，就可以得到相对 中山大学硕士学位论文 安全的拍卖系统，同时也比英式拍卖有相对更高的公平性。但是这种拍卖方式存 在两个非常明显的缺点：在买者中间没有一个有效完善的竞争机制。买方最 后付出的价格很可能会比商品实际的价格要高得多。如果考虑了这两个因素后， 那么英国式的拍卖方式就比s e a l e d - - b i d 拍卖方式要来得“有效”。由于英国式 的拍卖方式采取公开的方式，那么，买方之间就存在“直接”的竞争，并且由于 这种公开性，买方之间可以通过对方的反应来估计商品的潜在的价格，避免s e a l e d b i d 拍卖中可能出现的付出价格远超出原来价格的问题。本文主要研究英式电子 拍卖协议的安全问题，给出一个安全的电子拍卖的协议。 1 1 拍卖的特点和要求： 1 1 1 拍卖的类型： 本文着重于对英式拍卖的特点和服务的研究：标书的详情要在拍卖过程中公开， 而投标者都试图投出对自己最有利的投标，而每次投标的标值必须是全场的最高 值。 大体上，拍卖的类型主要由以下的不同的特征所决定。投标的秘密等级和投标 能否被取消大致上决定了该拍卖模型的类型。 投标的秘密等级： ( 1 ) 公开的：任何人在拍卖过程中都可以验证每个投标者的出价。 ( 2 ) 秘密的：拍卖者只能在拍卖结束后才可以知道其余投标的价钱。 投标的取消制度 ( 1 ) 可以取消。 2 中山大学硕士学位论文 ( 2 ) 不能取消。 1 1 2 模型的要求 拍卖模型一般都需要满足以下一些基本要求。 ( 1 ) 标书的完整性。 只有有效注册的用户才能投标，任何未经授权的人都不能伪造标书。投出的标 书不能修改，伪造。 ( 2 ) 公平性 每一个合法的投标者都能随自己意愿自由的投出超过已有标书标价的标书。拍 卖方不能随自己意愿自由改变标书的状态。投标只能在规定的时间内投出。 ( 3 ) 不可复制 任何人都不能复制出一份已经存在的标书。 ( 4 ) 不可否认 拍卖方不能否认收到已经收到的投标，另一方面，投标人不能否认已经投出的 合法投标。 ( 5 ) 可验证 任何人都可以验证投标者和投标的合法性。 1 2 电子拍卖协议的基本模型 1 2 1 - 电子拍卖系统的要求 3 中山大学硕士学位论文 运行在公开的不安全的网络上的电子拍卖与一般拍卖不同的地方在于，在电子 拍卖过程前后要保护竞拍者的匿名性及竞拍者投标的重要信息，任何人包括拍卖 方都无法获得竞拍者的身份及其投标的重要信息。拍卖结束后只公开赢家的证书 及最高出价，保护拍卖者的身份秘密，任何人都能验证拍卖结果的有效性。每一 个好的拍卖系统都应该满足以下要求： ( 1 ) 竞拍者的匿名性 任何人除了竞拍者本人外，在任何时候都不能从投标上的签名来辨认出竞拍者 的身份。i n t e r n e t 是一个公开的环境，在i n t e r n e t 上传输的数据都具有可以随意 复制的特性，如果竞拍者的身份公开了，那么，所有得到这些身份信息的人都可 以通过某些简单的手段复制出这个身份，由于电子拍卖当中没有面对面的直接确 认，拍卖方很难确认哪一个才是合法的用户。所以，能否保障到竞拍者身份的匿 名性在电子拍卖过程中就显得尤为重要。 ( 2 ) 可验证 任何人都可以公开验证获胜者的身份标识是合法的。 ( 3 ) 可追踪性 当a m 确定该轮拍卖的获胜者时，这个获胜者不能否认他的投标。 ( 4 ) 不可伪造 任何人都不能伪造出一个有效的投标。 ( 5 ) 不可欺骗性 任何人都不能伪装成某个已注册的竞拍者进行竞价。 ( 6 ) 同一拍卖过程中投标的可联系性 4 中山大学硕士学位论文 任何人都能清楚的知道哪几个投标来源于哪个投标者，以及某个投标者在这一 轮里总共投出的投标数。 ( 7 ) 异步拍卖过程中身份的不可联系性 任何人除了投标人本人外都不能从以前的拍卖进程的数据中，确认某个拍卖过 程中该投标者的投标。 ( 8 ) 一次注册 任何投标者都只需要向注册机构注册一次，就可以参与多轮拍卖。 ( 9 ) 容易撤销 注册方能够轻易撤销投标者的投标权力。 1 2 2 电子拍卖协议 ( 1 ) 初始化 拍卖主持人( 简称a m ) 选择系统参数并在公告板上公布这些参数及有关拍卖品的 信息( 如拍卖品编号、拍卖时间等) ； ( 2 ) 注册 每一个希望参与拍卖的人都向某一可信机构注册，得到他个人参与到拍卖中的 个人身份标识。同时，可信机构应把所有个人的身份标识在公告板上张贴出来， 使得a i 能够根据这些信息计算每一张的拍卖票据。 ( 3 ) 拍卖 5 中山大学硕士学位论文 竞拍者计算他的拍卖密钥并且在公告板上投标出价，所有合法用户都能从公告 板上辨认出投标的情况，根据投标的信息可以验证投标的有效性。 ( 4 ) 拍卖结束 公开获胜竞拍者，a m 将赢家的身份标识公开，任何人都能公开地验证赢家的投 标出价，证明该投标的身份标识是合法的。但不能从中得到赢家的身份。 可见，电子拍卖当中，一个非常重要的任务就是保证竞拍者身份的不泄露，这 与密码学研究的目的之一以及许多密码学协议的功能相吻合，于是，出现了许多 基于不同的密码学协议的电子拍卖系统 1 0 1 l 儿1 2 1 6 。 i 3密码学简介 i 3 1 密码学 密码学作为一种技术源远流长，可以追溯到非常遥远的过去，距今已有4 0 0 0 年。 据说，历史上第一套密码系统“s c y t a l e ”是来源于希腊。而历史上恺撒大帝曾使 用密码系统向他军队的将领传递秘密消息。自古以来，中国民间都留有一些典故， 一些聪明的人为了把自己真正想表达的意思隐藏起来，就把某些文字巧妙的转换 为一些意思完全不同的诗词，使人不能简单直接的领悟其含义。但密码学成为一 门学科，则是近3 0 年的事，由于计算机科学的蓬勃发展，使得密码学应用的领域 迅速从军事上扩展到许多民用的领域。现在，如何保护信息的安全已经不仅仅是 军事和政府部门感兴趣的问题，而各事业单位也越感兴趣。在网络化的今天，计 算机犯罪每年造成的损失数额巨大，难以计算。密码是有效而且可行的保护信息 安全的办法，有效是指密码能做到使信息不被非法窃取，不被篡改或破坏，可行 是说它实现的代价是能够接受的。 6 中山大学硕士学位论文 1 3 2 我们能用密码学干什么 作为社会生活的一种重要的需求，秘密通讯主要包括的功能有三方面。 ( 1 ) 如何秘密的传输消息，以防止未经授权的人私自查阅消息里面的信息。 ( 2 ) 如何保证消息的发送者把自己的消息发送到特定的用户手上，而不是别的用 户。 ( 3 ) 接受者如何能确认消息确实来自特定的发送者。 传统来说，主要有两种方式。一种是通过不可感知的联系，把相关的消息转化为 毫无意义或其余的存在，掩饰原来真正的意义。另一种就是依靠一个安全秘密的 渠道来传递，这可能是一个人，或是其它别的东西。密码学一个重要任务是研究 如何达成第一种方式的目的学科。它保证秘密数据的秘密，在不安全的渠道上安 全传输交流数据。当现实生活中某方面需要以上第一种方式的需求时，那么，密 码学就派上了用场。计算机科学的飞速发展，也使得密码学的应用平台更为广阔， 许多政治，商业上的组织行为也可以系统的在网络上基于基本的密码学协议实现。 如选举投票，现金支付，拍卖活动等，相应出现了电子现金，电子拍卖等在线交 易活动。 1 3 3 传统的密码学系统 1 3 3 1 对称密钥系统 密码学的最开始的目的是保留隐私：两方( 发送者s 和接收者r ) 希望秘密的交 换信息，这样，不怀好意的人就不能获知他们所要传递的信息。早期最为标准的 密码学上提供的解决方法是对称密码系统。这种系统提供了面向多于一个用户的 安全交流方式，他最大的特点在于，加密的密钥能根据解密的密钥和其它附带的 信息推算出来，在大多数情况下，加密密钥跟解密密钥是相同的，这种情况下， 也称作单密钥系统。系统要求发送者和接受者预先通过安全渠道协商定一个密钥， 中山大学硕士学位论文 所以整个系统的安全性就在于密钥上，如果密钥的组成方式泄漏了，那么任何人 都可以加密和解密，只要密钥安全，那么所有的信息都能保密。 对称密钥系统包括以下方面： ( 1 ) 明文空间以及所有可能明文p ( 2 ) 密文空间以及所有可能密文c ( 3 ) 密钥空间k 和每个k 决定的加密算法和解密算法 ( 4 ) 满足o k ( e 。( p ) = p 。 采用这种系统传输信息时，就无需担心消息受到窃听，因为窃听者没有密钥的 信息，他不能解密消息。但这种系统却存在以下的问题： ( 1 ) 谁也不能保证密钥能正确的传输到正确的人手里。如果你能正确的做到以上 这一步，理论上，对称密钥系统也没有存在的必要。 ( 2 ) 如果发送者和接收者之间出现矛盾，第三方难以确认谁真正发送了消息。因 为双方共享同一密钥，都能够产生对自己有利的密文。 ( 3 ) 更为主要的问题在于密钥的管理，两个用户要准备一个密钥，那么n 个用户 就需要n ( n 1 ) 2 个不同的密钥。 1 3 。3 。2 公钥系统 为了解决对称密钥系统的问题，上世纪7 0 年代，w h i t e f i e l dd i f f i e 和m a r t i n h e l l m a n 提出了一种新型的系统，称之为公钥系统。这种系统可以公开加密算法， 但却不会泄露解密算法，因此和对称算法相比，任何人都可以通过公开渠道( 网 络或密钥管理中心) 得到他人的加密密钥，把明文加密以后传送给接收者，只有 拥有解密密钥的人才能够对密文解密。公开密钥算法可以运用到现实生活中的方 方面面，如数字签名，电子现金，电子选举，电子拍卖等。 公钥系统包括加密b 和解密以，对每一个k ，有以下特性。 ( 1 ) b 是喀的逆运算，即有q ( 反( p ) ) = p 。 ( 2 ) 以和d 。是非常容易计算的。 中山大学硕士学位论文 ( 3 ) 任意密钥k ，要从绣推算出最在计算上是不可能的。 ( 4 ) 任意密钥k ，要从k 推算出臣和d 。是计算上不可能的。 由于第三个特性，那么加密的密钥就可以向公众公开，而不必担心自己的加密 的秘密泄露出去。因而，公钥系统分为两个部分，一组是加密过程，一组是解密 过程，两组是独立的，即从其中一种不能推算出另外一种的运算规则和运算结果。 在这一种公开的系统里面，我们不再需要找一个安全的渠道来传送个人的密钥。 每一个用户只需保存好自己的解密用的私钥q ，而把加密用公钥巨公开，他可以 根据自己的密钥构造出公钥，但别人却不能根据公钥计算出用户的私钥。表面上 看来，这种系统是很难实现的，但其实，许多这样的系统已经存在，典型的有r s a 公钥系统和e l g a m a l 加密系统。如果a 想使用这个系统，他只要做以下几步： ( 1 ) a 找到b 的公钥，用公钥加密数据，并把加密后的信息发给b ( 2 ) b 收到信息后，用私钥解密数据，得到明文p ( 3 ) 其余别的人，由于没有私钥，单从公钥不能得到私钥，所以不能解密信息。 公钥系统还有一些值得注意的优点： ( 1 ) 通信双方不需要互相秘密传递密钥。 ( 2 ) 每个用户只需保存自己的私钥。 ( 3 ) 任何新的用户加入都不会造成旧用户密钥的变更。 更为重要的是，公钥系统的提出为密码学应用上的许多难题，提供了解决的方 法。我们可以用公钥系统，设计出许多数学和计算机的模型，解决我们所面对的 难题。随着计算机科学和电子商务的蓬勃发展，公钥秘密系统的应用更为广泛， 出现了很多以公钥系统建立的电子商务模型，其中不乏很多在线的网上拍卖模型， 以下部分简略介绍已有的几种电子拍卖方案。 相关电子拍卖方案： 电子拍卖系统所要求的服务和特性，与群签名的特点有很大程度上的吻合。 k n g u y e n 和j t r a o r 6 在他们的论文 1 0 把改进的群签名方案应用于协议当中，实 现了一种英式电子拍卖协议 n t o o ，但是这种方案具有某些缺陷，首先群签名是 一个复杂签名生成和签名验证的过程，需要大量运算，拍卖过程经常需要生成签 中山大学硕士学位论文 名、验证签名和验证投标书的有效性，这是效率问题。其次，群经理拥有能验证 所有人真实身份的特权。再次，在拍卖过程中很难撤消一个竞拍者，拍卖初始化 时竞拍者的成员证书已经被分发，而在拍卖过程中撤消竞拍者是较频繁的，如竞 拍者想要撤出拍卖或拍卖管理者想要取消某个竞拍者的竞拍资格，那么所有竞拍 者的证书不得不重新分发，这将严重影响拍卖的进行。k a z u m a s ao m o t o 和a t s u k o m i y a j i 1 6 引入了两个实体( 一个为注册实体r m ，一个是拍卖实体a m ，前者处 理参与拍卖的人的注册问题，后者执行拍卖过程) 和公告板，基于e l g a m a l 公钥系 统提出了一个只需一次注册的拍卖协议。协议里。拍卖的注册非常之有效，并且 r m 非常容易地取消参与者的投标，但是这种协议存在一个问题，那就是如何公开 证明一个竞拍者为最终的拍卖胜利者。为了解决这个问题，本文提出以下一个新 的协议，实现只需一次注册，并可公开验证获胜者身份的安全有效的电子拍卖方 案。重点是引入可信第三方，c a 为每一个曰i 生成一个随机数月i ，以该随机数生成 竞拍者的身份标识i ，a m 在公告板上得到该身份标识后，为每一个垦牛成拍卖 票据。这样，c a 和a h i 每轮的拍卖过程中共同牛成可验证竞拍者身份的特殊信息， 他们单独一个人不能验证参与拍卖的人的身份。最后，获胜者的身份的特殊信息 能在该轮的拍卖过程后公布，公布过程前后，获胜者的身份都保证不会被泄露。 该方案有着简单的拍卖过程和验证过程，并能公开验证获胜者。 最后，给出本文的结构：第2 章简要介绍数学和密码学方面的背景：第3 章简 略介绍已有英式电子拍卖的基本协议和其问题；第4 章引入可信中心c a ，设计一 个可以公开验证获胜者身份的电子拍卖协议，满足拍卖的基本特性，并在宣布获 胜者阶段时，所有人都能公开验证获胜者；第5 章分析了方案的安全性和有效性； 第6 章为本文的结论部分。 1 0 中山大学硕士学位论文 2 1 离散对数问题 第2 章预备知识 给定大素数p ，有限域z ，的生成元g ，已知y ，b z ，给定6 ，石，计 算出y 2 扩十分容易，但如果给出y ，b ，求整数j 2 i o 氍y ，使得扩2 ym o d p ， 这就是求离散对数问题，这是一个难题。不是所有的离散对数都有解，只有整数 才是合法的解。 2 2 单向散列函数( h a s h 函数) 单向散列函数作用于某一任意长度消息，然后返回固定长度的值h ，长度为。 其主要的特性有： ( 1 ) 给定m ，很容易计算其散列值h ( m ) 。 ( 2 ) 给定h ，根据h ( m ) = 计算出m 在计算上是不可能的。 ( 3 ) 给定m ，找出p ，使得h ( m ) = h p ) 在计算上是不可能的。 单向散列函数的作用就在于为消息生成唯一的标识，使得相关的各方都可以验 证该消息的合法性。 2 3 公开密钥算法 2 3 1l i s a 公开密钥算法。 中山大学硕士学位论文 选取两个大素数，p 和覃。计算乘积n = pq 。选取e 与( p i ) ( q 一1 ) 互 素。最后利用欧基里德扩展算法计算解密密钥d ，以满足ed = 1m o d ( p - - 1 ) ( q 一1 ) ，注意到d 和，l 也瓦素。e 和n 是公开密钥，d 是私人密钥。它的安全性依赖 于大数因子分解的困难性。整个过程如下： 表2 1 该算法既可用于数字签名又可用于加密，其安全性依赖于计算有限域上离散对 数的难度。首先产生一对密钥对，选择素数p ，两个随机数占和x ，g 和x 都小于 p ，然后计算：公开密钥y = g r o o d p ，p ，私钥是z 。 a e l g a m a l 签名 对消息m 签名时，选择一个随机数k ，k 与p 一1 互素。然后计算 a 2 9 m o d p 利用欧基里德算法从下式中求出b ： m = 伽+ k b ) m o d ( p 一1 ) 签名为一对数：( a ，b ) 随机数k 必须保密。 中山大学硕士学位论文 验证签名时，只要验证： y 。9 6m o d p = g ”m o d p 每一个e l g a m a l 加密都需要一个新的k 值，该值必须随机选取。假如a 恢复过 b 使用过的一个k ，她就能恢复b 的私人密钥x 。假如a 曾用同样的k 得到过签 名或加密的两个消息，甚至他不知道消息是什么，他也可恢复石。 b e l g a m a l 加密 表2 2 只需修改一下以上方案就可以用来加密消息。要加密消息，首先选择随机数k ， k 和p l 互素，计算 f 1 2 9 m o d p b = y mm o d p 解密时，计算m = b a 。m o d p 1 3 中山大学硕士学位论文 表2 3 2 4d i f f i e - h e l l m a n 密钥交换协议 如果a 和b 想共享一个密钥或某些信息，他们只需按照d i f f i e - - h e l l m a n 协议 执行以下步骤。 2 5 群签名 表2 4 群签名方案允许群里的成员以整个群的身份去签署一份消息。别人可以用群的 公开密钥验证这个签名，但是他们不能从这个签名得到与签名者有关的任何私人 信息，他们也不能确认其中的两个签名是否由群中的同一个成员签署。另一方面， 中山大学硕士学位论文 群里存在一个负责人，他可以打开群中成员签署的消息，得知签名者的身份。这 种签名方案最早由c h a u m 和v a nh e y s t 提出，但最初的方案的计算量非常大，难 以实现一个具有大量成员的群的群签名。此后，c a m e n i s c h 和s t a d l e r 提出了一个 有效的群签名方案，解决了以上问题，同时，使得群签名可以应用到电子拍卖当 中。详细情况可参见 8 。 2 6 知识证明签名 试设想如下的情况，两方发生交易，但双方并不能在感官方面接触对方，也就 是说至少有一方不能确认对方的身份，那么，交易刚开始时候要做的是确认对方 的身份，此时，对于买方来说，当他确认自己身份的时候，不可避免要泄露自己 的某些特定的信息，相对于卖方，买方不能保证自己的匿名性。这样，我们就需 要构造一种特殊的协议，买方在不泄露自己的秘密时，同时能够公开证明自己的 合法性。c a m e n i s h 和s t a d l e r 在文章 8 中提出了一种有效的知识证明签名，这 种方案的安全性基于离散对数的难解性。下面是该问题的描述：a 如何在不泄露x 的情况下，向b 证明他确实知道y 关于底g 的离散对数( 即x = l o g 。y ) 的知识。他 可以随机选取re z 。，计算t = g r o o d p ，c = h ( m | | g | | y | | g ) 和求出s ， s = r c 工m o d p ，传送( c ，5 ) 给验证者。验证者：检验c = h ( ml ig | | yi ig 5y ) 。如果等式成立，就验证了签名的有效性。这种知识证 明签名我们记为s k d ：y = g 。 ( 肌) ，用k 来表示。 中山大学硕士学位论文 第3 章以前的方案 3 1 基于群签名的方案 该方案由k n g u y e n 和j t r a o r 6 所提出，他们通过引入一个修改过的群签名方案 n t 0 0 来构造出一个英式电子拍卖协议 1 0 。协议主要思想如下： 系统的建立阶段： 拍卖主持a u c t i o nm a n a g e m e n t ( a m ) 引入r s a 系统，选择一个大的数，为 两个大素数p ，q 的乘积，r s a 密钥对为( e ，d ) ，z 。域上的 阶循环群g ，生 成元为g ，a z ：，r m ( r e v o c a t i o nm a n a g e m e n t ) 选择h g ，计算e l g a m a l 密 钥对( p ，2 h 9 ，于是拍卖的公钥就为r2 ( n ，p ，g ，g ，n ，h ，k ) 。 注册阶段 参与拍卖的人皿，随机生成密钥x ，计算值z 2 9 ，y = a 。m o d n ，把这两值经 过安全的渠道送给a m ；a m 收到z ，y 后，计算证书p2 ( y + 6 ) 4 r o o d n ，并发给皿 拍卖阶段： e 如果要投标，他先计算以下值( d 。，d ：，k ，屹) g l = g ，z 1 = g l ，z 。，d l = 瑶9 7 ，d 2 = 矗“ f o rm z # 1 6 中山大学硬士学位论文 k = s k 【( y ，芦) ：z 1 = g ：ad 2 = h 6 ad l = k ? g7 】( m ) ； ：s k 【( ) ：，：g ? ) ( k ) ； 匕= s k 【( a ) ：z 。g ? = g ? 】( k ) 投标者e 的签名包括一组数据( d ，d ：，k ，蚝) 如果，吃，嵋是有效的，任何人都能证实( d 。，d ：) 是用e l g a m a l 加密方案 对z 加密的，用r m 的公钥k 加密的数据，而e 握有自己的私n x 和a m 给他的身 份证明v 。 公布中标者 r m 用他自己的私钥p 解密( d 。，d ：) ，由于每一个旦对应于一个z ，r m 能证 实每一个e 的身份。当一个b i 投出最高的标书时，肼可以确认他的身份。 这个协议有三个突出的问题 ( 1 ) 由于将群签名应用到该协议上，这样在每一次投标时都产生一次签名和签名验 证。然而，每一个群签名过程的产生和验证都需要复杂和大量的运算。 ( 2 ) 由于拍卖当中要求投标人的身份对于拍卖主持人来说，都应该是秘密的，但 是，群签名方案中，群经理知道每一个群成员的身份，这样投标人身份的匿名性 就不能满足。 ( 3 ) 在英式拍卖中，如果一个投标者由于某种原因，常常会从某次拍卖中退出， 拍卖主持人应该能够很轻易的令到该用户安全的退出。所以，取消机制不能够太 过复杂。然而，在上面的协议中，想去取消一个用户，是比较困难的，因为每一 中山大学硬士学位论文 个用户都得到一份成员证书，同时，每一个用户都不希望自己的密钥在撤销过程 中泄露，所咀不希望自己的密钥会在公告板上张贴出来。 3 2 只需一次注册的方案 这个由o m o t e 和m i y a j i 提出的公开拍卖系统 1 6 是一个非常有效的系统模型 o m 0 1 。每一个参与拍卖的人都可以只通过一次注册就能参与随后多轮的拍卖。 在这个方案中，有两个拍卖负责人，注册负责人秘密掌握住所有参与注册的人的 密钥与这人身份的联系。拍卖负责人主持拍卖，同时在每一轮的拍卖中生成拍卖 的票据。 以下简述该协议。p 和q 是两个大素数，满足g 整除p l 。g 是一个q 阶循环 群z ：的生成元。a m 自己的私钥吒，和公钥砭= g r o o d p 。投标者e 的私钥t 和 公钥y 。= g r o o d p 协议如下 投标者的注册阶段 e 依照下列步骤向r m ( r e g i s t r a t i o nm a n a g e r m e n t ) 登记自己的身份。他选 择一个随机数t ；，将( _ ) 。，t 。) ，连同能够证明他知道私钥工i 的信息( y 。在底g 上 的离散对数) 传给p d d 。如果i m 接受了证明的有效性，他就会在公布板上张贴出( y i ， t ，) ，同时秘密地保存能证明垦身份的信息。 a m 建立系统： 假定a m 主持第轮的拍卖，他从公告板上得到每一个参与者皿的( y ；，t j ) ， 然后，他用d i f f i e - - h e l l m a n 密钥交换协议为每一个且计算他们之间共享的密钥 中山大学硕士学位论文 弦。他帮助每一个e 生成一个随机数，然后安全地保留好，接着，他为曩计算 以下的拍卖密钥。 互= ( e n c ( y 产，t f ) ，_ ) ，? ，g ) 这里，e n c 。( 弦，t i ) = e n c ( _ ) ，e n c “1 ( y 产，t i ) ) ，使用同一个共享密钥弦m o d p 对f ；加密七次后得到的。然后，他将t i 的顺序打乱，贴在他的公告板上。 投标拍卖阶段： 每一个投标者如果想参与到第k 轮拍卖中去，他很轻易的就能从a m 的公告板 上找到自己的拍卖密钥王，他只需预先通过公式y ，= 弦计算e h c ( ) t ，t ，) 。 当他投出自己的投标时，他传送以下的投标信息给a m 。 ( m j ，y ? ，9 1 ，) m i ( m i = a u c t i o n l d il b i d v a l u e ) ，坩，9 1 由a m 张贴出来，k 证明b i 确实 知道使得y ? = ( g ) “m o d p 成立的口。 决定获胜者和宣布获胜者 假定m ，是一个获胜投标。a m 向r m 传送，：1 ，证明加在获胜投标历，上的公开信息 y 7r o o d p 所关联的公开密钥y j 。然后，r m 在决定了获胜者之后，秘密通知卖主。 该方案所面临的问题： 只从非常简单的投标和验证过程，以及每一个投标者都只需要通过一次注册就 可以参与到多轮的拍卖中去的方面来看，这个方案是一个非常有效的方案。但是， 该方案有一个问题，就是在最后宣布获胜者时，r m 只能秘密地向卖主证明，而不 能公开地验证。a m 向r m 证明谁是获胜者的过程以及r m 的秘密证实谁为获胜者这 1 9 中山大学硕士学位论文 两个步骤，并没有向公众公开。在宣布获胜者的阶段，每一个投标人都只能辨别 出哪一个投标的值最高，但他们没有能力证明两个丰持人是否正确履行其职责以 及谁是真正的获胜者，他们只能去相信两位主持是诚实的。而在a m 的角度上来看， 他将，i 1 送给r m ，他不能确定究竟r m 有没有向卖方给出正确合适的获胜者的身份 证明。 获胜者的身份不能公开的原因主要在于：如果身份公开了，那么在今后的几轮 拍卖里，a m 知道获胜者的身份，那么，拍卖者对a m 的匿名性就不能再保持下去。 由于a m 使用同样的密钥信g y ；，他就可以很轻易的在随后的几轮拍卖过程中验证 出投标人的身份。 中山大学硬士学位论文 第4 章本文的协议 本文引入可信第三方，基于知识证明签名提出个新的协议，满足可公开验证 获胜者的电子拍卖方案。在该方案中，每个竟拍者首先与c a 交换信息，得到c a 为他生成的身份标识证书，然后c a 使用e l g a m a l 公钥系统生成证书的副本，并把 证书的副本张贴在公告板上，任何人都不能由副本的信息得到证书，但在c a 和a m 的共同帮助下可以验证副本与正本的联系。a m 从公告板上得到证书的副本，通过 d i f f i e - - h e l l m a n 协议生成拍卖票据，然后生成验证拍卖票据有效性的随机数，用 这个随机数生成验证票据有效性的信息。每一个竞拍者可以通过d i f f i e - - h e l i m a n 协议计算出自己的票据，然后生成拍卖投标( 该投标包括标值，一个身份的知识 证明签名，以及票据) ，把投标张贴上投标公告板。最后，当个用户投出了最 高投标后，c a 和a m 共同公开张贴出所有的验证信息，任何人可以通过这些信息验 证获胜者的身份，验证过程中，获胜者的身份始终没有泄漏出去。协议中，包括 两个负责人，一个是负责登记投标者的可信中心c a ，拍卖主持人a i ，以及参与投 标的投标人口；。他们主要执行的步骤和意义如下： 他主要负责处理想参与拍卖的投标人的注册，同时秘密保存这些用户的身份信 息。 他帮助用户生成参与到拍卖的身份标识，该标识与投标者的身份联系在一齐， 埘不能通过该标识得到有关投标者的信息，而拍卖者通过该标识参与到拍卖中去。 c a 将这些用户标识顺序打乱，张贴出来。 2 1 中山大学硬士学位论文 在最后阶段，他宣布获胜者的身份标识，将标识张贴出来，并且生成一个知识 证明签名证明该标识的有效性。任何人都可以通过验证知识证明签名来验证获胜 者的身份。 他为每一个已经注册的用户生成每一轮的拍卖票据，票据包括一个随机数和拍 卖者的注册标识。他将所有的票据顺序打乱，并张贴出来，同时秘密保存随机数。 这样，注册的用户只需通过简单的计算，就可以轻易地找到自己的票据，而其它 别的人，甚至c a 都不能在这阶段通过该票据得到拍卖者的身份。 在拍卖结束阶段，他将把能证明获胜者的信息张贴出来。 投标人b i 投标人必须向c a 申请注册，才能参与到拍卖中去。 然后，他与a m 经过一系列协议，得到他的拍卖票据，并用这些票据参与到每一 轮的拍卖中去。 还有一些值得注意的地方，在宣布获胜者时，a m 和c a 都必须将有关用户的信息 张贴出来，同时这些信息之前应该是保密的，所以，我们必须首先做出以下两个 假设： ( 1 ) c a 能够真正秘密保存到注册用户的信息。 ( 2 ) a m 在每一轮使用完随机数来生成拍卖票据时，都必须将随机数完好的秘密保 存下来。 可公开验证的拍卖协议： 中山大学硕士学位论文 该方案主要有5 步，由注册阶段开始，到宣布获胜者阶段结束。首先，先注明一 些符号的定义。 符号所代表的意义如下 p ，q ：大素数，r q i ( p 一1 ) e ： 参与拍卖的投标者 y ，：b i 的公钥( n 满足y 。= g m o d p ，这里公开密钥是参与拍卖者用来注册 的密钥，但却不会泄露鼠的身份。) 一：e 的私钥 e 向c a 证明他拥有密钥工i 的知识证明签名。 r ： c a 为每一个b 生成的随机数r 乙 i d i ：l d | 2g r i d i e z q x ：i - ( y i ) 皿 x 。： a h i 的私钥 匕：a m 的公开密钥( l = g r o o