（计算机软件与理论专业论文）可分电子现金及其实现技术研究.pdf

摘要 电子现金因其具有离线交易、用户匿名、方便灵活、能有效防止拒付和恶意透 支等特性而成为电子商务最重要的支付方式之一，并且已经成为未来电子货币的发 展趋势。可分性是任何形式货币的一个最基本、最自然的属性，可分电子现金不仅 能作为一个整体使用，还可以被分为更小的部分多次使用，可以减少用户的取款次 数，网络通信量因此显著降低，系统执行效率明显提高。因此，电子现金的可分性 一直以来都是该领域的研究重点和热点。 可分电子现金要真正走向实际应用还有很多工作要做。重复支付、超额支付的 检测使得可分电子现金协议变得复杂化，导致协议的计算复杂度增高，执行效率下 降；引入可信第三方追踪违法用户可以避免协议的复杂化，但是不能保证用户的匿 名性，并且可信第三方的引入也会增加系统额外的开销；同一电子现金的不同部分 往往存在相关性( 不完全无连接性) ，存在泄露用户隐私的潜在威胁。本文致力于 探索新的思路。运用新的技术手段来构建性能更加优良、效率更加高效的可分电子 现金方案。 首先，总结分析了实现电子现金的关键技术，包括实现电子现金的可分性的各 种技术，分析了相关技术的优劣。 其次，在传统的二叉树技术基础上，积极探索好的思路和新的技术改进，提出 了两个新的可分电子现金方案：第一个方案，通过构造高效的交互式零知识证明， 实现了电子现金的完全无连接性，也就是说用户在使用同一电子现金进行不同交易 时不会泄露用户的任何机密信息，也不会泄露任何与所支付的电子现金相关节点的 信息，该方案同时克服了可信第三方的存在性；第二个方案是试图提高可分电子现 金方案执行效率的有益尝试。方案在取款阶段引入概率算法，结合单向累加器的有 界性来进行身份验证，避免了传统的分割选择算法，有效提高了执行效率，方案克 服了可信第三方的存在性、实现了电子现金无连接性。 最后，指出了可分电子现金存在的问题并对进一步的研究工作做了展望。 关键词：可分电子现金；零知识证明；单向累加器；无连接性；- - y 极t t h er e s e a r c ho i ld i v i s i b l ee - c a s hs y s t e ma n di t si m p l e m e n t a t i o nt e c h n i q u e a b s t r a c t b e c a u s eo fi t se x c e l l e n tp r o p e r t i e so fo f f - l i n et r a n s a c t i o n , k e e p i n gu s e ra n o n y m o u s ， c o n v e n i e n c ea n df l e x i b i l i t y , a n db e i n ga b l et oe f f e c t i v e l yp r e v e n tr e p u d i a t i o no fp a y m e n t a n do v e r d r a w i n gw i t he v i li n t e n t i o n s ，e - c a s hh a sb e c o m eo n eo ft h em o s ti m p o r t a n t e l e c t r o n i cp a y m e n tm o d e s a n di ta l r e a d yh a sb e c o m et h ef u t u r et r e n do fd e v e l o p m e n to f e l e c t r o n i cm o n e y d i v i s i b i l i t yi so n eo ft h em o s tb a s i ca n dn a t u r a lp r o p e r t i e so fc u r r e n c y o fa n yk i n d ad i v i s i b l ee c a s h 啪e i t h e rb eu s e da sa l le n t i r e t yo rb ed i v i d e di n t o s m a l l e rp a r t s 砸sw a y , t h eu s e r sc o u l dr e d u c et h en u m b e r so fw i t h d r a w 协a t sm o r e ， n o to n l yt h en e t w o r kt r a f f i cw i l lb el i g h t e r , b u ta l s ot h es y s t e mw i l lb em o r ee f f i c i e n c y t h e r e f o r e ，t h ed i v i s i b i l i t yo ft h ee - c a s hh a sa l w a y sb e e na ni m p o r t a n ta n dh o tp o m 0 f t h i sf i e l d t h e r ei sal o n gw a yt og of o re - c a s ht ob e i n gp u t t e di n t op r a c t i c e n ed e t e c t i o no f d u p l i c a t i o no fp a y m e n t sa n do v e rp a i d ，w i l lm a d et h ep r o t o c o l so fe - c a s hc o m p l i c a t e d , t h e c o m p u t a t i o n a lc o m p l e x i t yo f t h e p r o t o c o l si n c r e a s e d ，a n d t h ee f f i c i e n c yo f i m p l e m e n t a t i o nd e c l i n e d w ec a nu s et h et r u s t e dt h i r dp a r t yo 耶) t ot r a c kt h ei l l e g a l u s e r st oa v o i dm a k i n gt h ep r o t o c o lc o m p l i c a t e d ；h o w e v e gt h em p o s e sat h r e a tt ot h e u s e r sa n o n y m i t y , a n dw i l l l c a dt oa d d i t i o n a lc o s t so ft h es y s t e m u s u a l l y , d i f f e r e n tp a r t s o fad i v i s i b l ee - c a s hh a v er e l e v a n c ew h i c hi sap o t e n t i a lt h r e a to fl e a k i n gt h eu s e r s p r i v a c y t h i sp a p e rc o m m i t si t s e l ft oc o n s t r u c td i v i s i b l ee c a s hs y s t e m sw i t he x c e l l e n t p r o p e r t i e sa n dh i g he f f i c i e n c y , a n de x p l o r et h en c wc l u eo ft h o u g h t so fd i v i s i b l ee - c a s h s y s t e m f i r s t l y , w ea n a l y z e da n ds u m m a r i z e dt h ek e yi m p l e m e n t a t i o nt e c h n i q u e so fe - c a s h s y s t e m s ，i n c l u d i n gt h et e c h n i q u e so fd i v i s i b l ee - c a s hs y s t e m s , a n dc o m p a r e dt h er e l a t e d t e c h n i q u e s s e c o n d l y , w ed oal o tt oe x p l o r eg o o dc l u eo ft h o u g h t sa n dn e wa d v a n c e si n t e c h n o l o g yo fd i v i s i b l ee - c a s hs y s t e m ，a n dp r o p o s et w od i v i s i b l ee - c a s hs c h e m e s n c f i r s to n eh a st h e f u l l u n l i n k a b i l i t yp r o p e r t yb yr e a s o n o fu s i n gm a n ye f f e c t i v e z c r o - k n o w l e d g ep r o o f s i na n o t h e rw o r d s ，au s e rc a n n o tl e a ka n yo fh i sp r i v a c y , i n c l u d i n g t h en o d e si n f o r m a t i o no ft h ec a s hh ew a su s i n g m e a n w h i l e ，t h e r ei sn oa1 曙i nt h e s c h e m e n es e c o n do n ei sau s e f u la n dv a l i da t t e m p tt oi m p r o v et h ee - c a s hs y s t e m e f f i c i e n c y i n t h i ss c h e m e ，w et a k ea d v a n t a g eo fp r o b a b i l i s t i ca l g o r i t h ma n dt h e b o u n d e d n e s so ft h eo n e w a ya c c u m u l a t o ri n s t e a do ft h et r a d i t i o n a lc u t - c h o o s ea l g o r i t h m a sar e s u l t , t h es c h e m ei sp r o v e nm o r ee f f i c i e n t ，n or r ea n du n l i n k a b i l i t y f i n a l l y , w ep o i n ts o m eo p e np r o b l e m so fe l e c t r o n i cc a s ha n dp r o s p e c tt h ef u t u r e r e s e a r c ho fe - c a s h k e yw o r d s ：d i v i s i b l ee - c a s h ；z e r o - k n o w l e d g ep r o o f ；o n e - w a ya c c u m u l a t o r ； f u l l - u n l i n k a b i l i t y ；b i n a r yt r e e 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人己用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名与小波 嗍榔年t 胪日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 ， 不保密酬 ( 请在以上方框内打二”) 。 论文作者签名：9 小1 支 刊币鹳：编争 f ! j t f j ：砘。坼厂月o f f j u i ：为哆 i if jj pt l ( 小j h 叫的版卡义9i i i ，人。所，f r ，术绛y ：l , f ，f f ：f i , f 币化及f h , , j 个人小f ! j 啊1 7 i 他川) 第一章绪论 1 1 引言 第一章绪论 电子商务以因特网( i n t e m e t ) 为载体，是因特网最主要的应用之一，i n t e r n e t 本 身所具有的开放性、合作性、共享性、低成本、高效率的特点，也将成为电子商务 的潜在特点。电子商务必将对整个社会的经济运行和经济结构产生深远影响。目前 来看，电子商务发展面临体制、模式、法律、技术等诸多方面的制约，但最突出的 问题在于怎样有效保障电子商务过程中交易的安全性，交易的安全性是电子商务的 基础和保障，同时也是电子商务技术的难点。 在电子商务过程中，客户、商家和银行以互联网络为平台完成电子支付过程， 进而完成整个交易。因此，电子支付是电子商务活动中最为核心和关键的环节，从 某种意义上讲，保障了电子支付的安全性，也就保障了整个交易的安全性。电子支 付方式通常可以分为基于账号的支付和基于代币的支付。我们常见的电子信用卡、 电子支票属于前者；电子现金是一种基于代币的支付方式。其中，电子信用卡不支 持离线支付，支付过程中，客户、商家、银行和发卡机构必须同时在线，共同完成 多方认证和数据的传送，代价较大，而且不具备匿名性。电子支票转账支付，是网 络银行的初级形式，其原理和普通支票类似，可以有效的减少银行的纸张的使用、 降低交易成本。电子支票虽支持离线支付，但对于用户的拒绝支付和透支行为却不 能有效地预防和制止。另外，因为交易的办理必须通过银行，电子支票无法保证用 户的匿名性。电子现金则能较好地克服上述支付方式的缺陷，它既能用于大额支付， 也适合于小额支付、支持离线支付，并且可以有效地保护用户隐私和交易的隐蔽性， 还能够防止拒绝支付和透支行为。电子现金必将成为电子支付的最主要的手段。表 1 1 给出了电子支付方式的分类和不同支付方式特性的比较。 表1 - 1 ：支付方式分类和比较 青岛大学硕士学位论文 1 2 电子现金的概念和基本模型 1 2 1 什么是电子现金 电子现金或称数字现金【( e l e c t r o n i cc a s h ，d i g j 【t a ld a s h ，e - c a s h ，e t c ) 是一种 以电子数据形式流通的、能被客户和商家普遍接受的、通过i n t e r n e t 购买商品或服务 时使用的数字化货币。电子现金是一种隐性货币，表现为由现金数值转换而来的一 系列电子加密序列数，通过这些加密序列数来表示现实中各种金额的币值。简单来 看，一份电子现金就是一个数组( x ，s i g n s ( x ) ) ，其中x 是现金拥有者的公钥，其对应 的私钥只有用户知道( 这里的公钥、私钥并非一般意义上用来加、解密的密钥，而 是指用户公开的和私密的能表明用户身份的信息) 。s i g n s ( x ) 是由发行电子现金的银 行对该公钥的数字签名( 通常是一个盲签名) 。在支付过程中用户将电子现金( x s i g n s ( x ) 1 传递给商家，商家通过银行的公钥验证电子现金是否由该银行发行。电子 现金作为纸币的电子等价物已完全可能具备货币的五种基本功能，即价值量度、流 通手段、储蓄手段、支付手段和世界货币，它可通过网络系统和公共信息平台实现 流通、存取、支付，因而更受商家和用户的青睐，正成为电子支付研究的热点。 1 2 2 电子现金的基本模型和特性 从1 9 8 2 年c h a u m 【2 】提出电子现金的概念以来，电子现金研究已经经历近3 0 年的发 展，大量优秀的学术文章被发表在美国密码会议、欧洲密码会议等高级别会议中。 o k a m o t o ，m o t iy u n g ，y i a n n i st s i o u n i s 以及j a nc a m e n i s c h ! 1 7 1 等人都在其论文中对电 子现金进行了深入的研究和分析。本节将介绍电子现金方案的基本模型，该模型满 足电子现金的基本安全性要求，用于说明电子现金的概念。 电子现金在其生存周期中一般要经过提取( w i t h d r a w ) 、支付( p a y m e n t ) 和存 款( d e p o s i t ) 三个过程，在其流通过程中涉及用户u ( u s e r ) 、商家m ( m e r c h a n t ) 和银行b ( b a n k ) 三方。一个完整的电子现金方案包括以下几个部分： 1 ) 取款协议( w i t h d r a w a lp r o t o c 0 1 ) ：用户从银行提取电子现金。用户在匿名的前 提下与银行交互执行盲签名协议，获得带有银行签名的合法电子现金，该电子现金 上包含有用户身份信息。取款协议一般分为如下两个协议： a ) 开户协议。银行向用户提供包含其身份信息的电子执照，计算量较大。 b ) 取款协议。该协议本质上是盲签名过程，用户从其帐户中提取电子现金。 2 ) 支付协议( s p e n dp r o t o c 0 1 ) ：用户向商家证明其电子现金的合法性，并消费一 定数量的电子现金，获取其所需要的货物或服务。支付协议也分为两个协议： a ) 现金验证：验证电子现金上银行的签名，确认电子现金合法性。 2 第一章绪论 b ) 知识泄露：用户向商家泄露部分有关自己身份的信息，用于防止用户违 法使用电子现金。 3 ) 存款协议( d e p o s i tp r o t o c 0 1 ) ：商家将电子现金连同其与用户交互过程中所产生 的“证据 交给银行。银行将检查存入的电子现金是否被合法使用，如果发现有非 法使用的情况发生，银行将使用重用检测协议追踪到踪非法用户的身份。 一个完整的电子现金解决方案通常还要包括初始化过程、重复消费检测过程， 即在商家提交证据时，银行必须检测用户是否重复消费了一个电子现金，或者商家 重复提交了同一个电子现金。电子现金的基本支付模型如图1 - 1 所示。 开户银行 5 商家发送货物 表示物理资金流 表示电子现金流 图1 1 电子现金一股模型 电子商务活动中，各参与方从各自角度考虑，对电子现金有不同的要求，如安 全、可靠、实用等等。因此在设计电子现金系统时应尽量满足以下一般性要求： 1 ) 独立性( i n d e p e n d e n c e ) ：电子现金安全性不能仅依赖于物理上的安全， 必须通过电子现金本身使用的密码学技术来保证电子现金的安全。 2 ) 不可重复使用( n od o u b l e s p e n d i n g ) ：电子现金只能使用一次，重复使用应该 能够被容易的检查到。 3 ) 不可伪造性( u n f o r g e a b i l i t y ) - 包括两种情况，一是用户不能凭空或是根据已 有的电子现金和支付信息伪造有效的电子现金；二是商家和银行不能够伪造 合法用户的不存在的支付信息。 3 青岛大学硕士学位论文 4 ) 匿名性( a n o n y m o u s ) ：合法用户的隐私受保护，即便是银行和商家勾结也不 能跟踪电子现金的使用。 5 ) 可传递性( t r a n s i t i v i t y ) ：电子现金可以方便地从一个用户传给另一个用户，且 不能被跟踪。 6 ) 可分性( d i v i s i b i l i t y ) ：电子现金不仅能作为整体使用，还应能被分为更小的 部分多次使用，但各部分的面额之和与原电子现金面额必须相等。 1 3 电子现金的应用现状 在实际应用中，国际上比较流行的电子现金系统主要包括以下几种： 1 ) e - c a s h 5 j 系统 这是一种已经实现了的电子现金系统，由荷兰阿姆斯特丹d i 百c a s h 公司 ( w w w d i g i c a s h c o r n ) 开发，1 9 9 6 年3 月在美国密苏里的m a r kt w a i n 银行发行使用。 目前使用该系统发布e c a s h 的银行有十多家，包括m a r kt w a i n ，e u n e t ，d e u t s c h e ， a d v a n c e ，m e r i t a 等世界著名银行。e - c a s h 使用公钥加密( 7 6 8 位r s a 密钥的3 d e s ) 和 数字签名确保安全，电子现金账号系统可以续存，并且移动电话、掌上电脑和其他 信息工具也都将支持e - c a s h 支付。在使用e c a s h 时，买方和卖方必须在发放e c a s h 的银行建立一个账户，银行向他们提供客户端软件( c y b e r w a l l e t ) ，负责到银行的 存、取款，以及支付或接收商家的货币，支付者的身份是不公开的。e c a s h 可以实 时转账，商家和银行之间不需要第三方服务机构介入。 2 ) m o n d e x 系统1 3 j m o n d e x ( w w w m o n d e x c o r n ) 是由英国最大的西敏寺( w e s tm i n s t e r ) 银行和 m i d l a n d 银行为主开发和倡议的以智能卡为存储介质的电子现金系统，它属于预付 式电子现金系统的一种，类似智能卡的应用模式。m o n d e x 于1 9 9 5 年7 月在英国斯温 顿市正式开始使用，可以说是全球惟一国际性的电子现金系统，也是现今最先进最 完整的智能卡系统。日本1 9 9 7 年引入m o n d e x ，澳大利亚四家银行、新西兰六家银 行都准备推广m o n d e x ，香港汇丰和恒生银行已经发行4 0 0 0 0 余张m o n d e x 智能卡。 3 ) c y b e r c a s h 系统1 4 j 1 9 9 4 年8 月，c y b e r c a s h ( w w w c y b e r c a s h c o r n ) 开始提供一种用于处理小额电子 现金事务。目的是为商家与金融机构在i n t e r a c t 上提供一种新的支付途径。客户可以 从c y b e r c a s h 服务器上下载c y b e r c o i n 软件，用于建立一个到c y b e r c a s h 的连接 通路。c y b e r c a s h 可以处理客户的各种需求：如建立客户身份、将信用卡中的信息与 个人情况联系起来，记录客户交易情况、提供管理与软件升级服务等工作。c y b e r c a s h 系统采用m d 5 与数字签名提供认证，采用d e s 与公钥算法进行加密，密钥长度为7 6 8 比特。 4 第一章绪论 4 ) n e t c a s h 系统【5 】 n e t c a s h 是由美国南加里福尼亚大学信息科学研究所( w w w i s i e d u ) 设计的电 子现金系统，仅是软件的解决办法，不要特殊硬件，利用对称和非对称加密算法， 具有高可靠性和匿名性，且能安全地防止伪造。系统中的电子现金是经过银行签字 的具有顺序号的比特串。其主要特点是通过设置分级货币服务器来验证和管理数字 现金，比较安全。n e t c a s h 产生的电子现金由如下字段组成：货币服务器名称( 负责 产生这个现金的银行名称及i p 地址) 、截止日期( 电子现金停止使用的日期，到期后， 银行将使其顺序号不再流通，同时银行还将记录未兑现账单数据库的余额) 、顺序号 ( 银行记录尚未兑现的有效账单的顺序号) 、币值( 电子现金的数量及货币类型) 。 尽管存在种种问题，电子现金的使用仍呈现增长势头。电子现金能否会像商家 和银行界预言的那样，成为未来网上贸易方便的交易手段，关键在于能否进一步提 出和完善安全、高效、可行的电子现金方案。 1 4 研究的主要内容 论文的主要工作： 1 ) 可分电子现金概述 总结了十多年来可分电子现金的研究历程，重点分析了可分电子现金的实现技 术，指出了目前可分电子现金研究存在的问题和可分电子现金进一步的研究方向。 2 ) 电子现金的可分性研究 电子现金必须能够实现精确花费。在实现电子现金的精确花费的同时必须有效 地保障户的隐私，防止重复花费、有效地追踪违法用户，并要尽可能的提升可分电 子现金系统的执行效率。 3 ) 可分电子现金的无连接性研究 目前绝大多数的可分电子现金方案，在实现了对违法用户的有效防范的同时， 牺牲了对用户隐私的绝对保护，在同一电子现金不同支付过程往往会泄露用户的支 付信息。本文在第四章提出的可分电子现金方案中，实现了电子现金的完全无连接 性，用户在支付过程中不会泄露任何威胁用户隐私的信息，包括用户所使用的电子 现金节点的位置信息。 4 ) 可分电子现金的效率和公平性研究 通过引入单向累加器，结合概率算法，在第五章提出了一个效率较高的可分电 子现金方案，方案无需可信第三方的参与，实现了电子现金的公平性。 5 青岛大学硕士学位论文 1 5 论文结构安排 本论文共6 苹，结构安排如下： 第一章绪论。着重介绍电子现金的基本概念和电子现金的研究及应用状况； 第二章电子现金关键技术分析。介绍公钥密码体制、单向散列函数、数字签名 技术和身份认证技术。 第三章可分电子现金概述。简要介绍了电子现金和可分电子现金的研究发展历 程，总结分析了可分电子现金的实现技术。 第四章具有完全无连接性的可分电子现金方案。基于二叉树、比特承诺、零知 识证明等技术提出了一种具有完全无连接性，无需可信第三方参与的、公平的可分 电子现金方案。 第五章基于单向累加器的高效可分电子现金方案。基于单向累加器理论和二叉 树技术，提出了一个同时具有用户匿名性和交易无连接性的离线可分电子现金方案， 方案无需可信第三方参与；加入了概率验证算法，明显降低了协议的时间复杂度， 提高了系统的执行效率。 第六章总结与展望。指出了可分电子现金存在的问题并对进一步的研究工作做 了展望 6 第二章电子现金关键技术分析 第二章电子现金关键技术分析 电子现金技术是以数学为基础的现代密码学的最重要应用之一，基于数学的现 代密码学体系主要包括双( 公) 钥密码体系、分组密码体系、序列密码体系三大体 系，以及三大体系延伸分支或应用，包括数字签名、h a s h 函数、身份识别、密钥管 理、p k i 技术、v p n 技术等。本章只讨论与电子现金相关的公钥密码、h a s h 函数、 数字签名、与身份证明( 零知识证明) 等理论和技术。 2 1 电子现金技术中的公钥密码体制 1 9 7 6 生1 z w d i f f i e _ ；f e l m h e u m a n 【6 】发表了论文“n e wd i r e c t i o n si nc r y p t o g r a p h y 一 ( 密码学的新方向) ，提出了公钥密码体制的新思想，证明在发方与收方之间不 需要传送密钥的保密通信是可能的。为了适应计算机通信和电子商务迅速发展的需 要，密码学的研究领域逐渐从消息加密扩大到数字签名、消息认证、身份识别、抗 欺骗协议等新课题，而这些技术恰是电子现金技术的基础。 2 1 1 单向函数和陷门单向函数 单向函数( o n e - w a yf u n c t i o n ) 和陷门单向函数( o n e - w a yt r a p d o o rf u n c t i o n ) 的概 念是公钥密码学的核心，用抽象的观点来看，公钥密码体制的设计就是陷门单向函数 的设计。 定义2 - 1 8 】( 可逆的函数) 一个函数厂：彳_ 丑，若对于任意气x 2 ，毛，x 2 e a ， 有，( 毛) - ，( 屯) ，则称f 为单射，或卜l i 剃 - j ，或可逆的函数。 定义2 - 2 8 】( 单向函数)一个可逆函数，：彳一b 被称为单向的如果它满足以下两 个条件： a ) 反容易计算：即给定输心，易于计算厂g ) 。 b ) 反向计算是困难的：即对“几乎所有的x e a 町瓤是“极为困难的 以至于实际上做不到，则称厂为单向函数。 定义中的“极为困难 是对现有的计算资源和算法而言。m a s s e ，7 l 称此为视在困 难性( a p p a r e n td i f f i c u l t y ) ，相应函数称为视在单向函数，以此来与本质上 ( e s s e n t i a l l y ) 的困难性相区分 7 1 。 7 青岛大学硕士学位论文 需要说明的是，不能将单向函数的概念与数学意义上的不可逆函数的概念混同， 因为单向函数可能是一个数学意义上可逆或者一对一的函数，而一个不可逆函数却 不一定是单向函数。 目前，还没有入能够从理论上证明单向函数是存在的。单向函数存在性的证明 将意味着计算机科学中一个最具挑战性的猜想p = n f ，即n p 完全问题的解决，而关 于n p 完全性的理论却不足以证明单向函数的存在。有幸的是，现实中却存在几个单 向函数的“候选 ( 3 0 0 位大素数相乘，固定基数和模数的模指数运算) 。说他们是“候 选，是因为他们表现出了单向函数的性质，但还没有办法从理论上证明它们一定 是单向函数。 显然，单向函数不能直接用作密码体制，因为如果用单向函数对明文进行加密， 即使是合法的接收者也不能还原出明文了，因为单向函数的逆运算是困难的。与密 码体制关系更为密切的概念是陷门单向函数。 定义2 - 3 8 l ( 陷门单向函数)陷门单向函数是一类满足下述条件的单向函数： 正：4 呻芝，z z ，z 是陷门信息集。 1 ) 于所有的z z ，在给定z 下容易找到一对算法e ：和砬使对所有x _ 彳 易于计算正及其逆，即： 无( 工) 一t ( 石) ，砬( 无( x ) ) 一石 而且当给定z 之后容易找到一种算法只，称之为可用消息鉴别函数，对于所有x e a ， 易于验证是否x e a ，4c a ，4 是可用明文集。 2 ) 对“几乎 所有z e z ，当只给定e ：和e ，对“几乎所有x e 彳：，“很 难，意即“实际上不可能 从y c ( x ) 算出x 。 3 ) 对任一z ，集丘必须是保密系统中明文集中的一个“方便 集。即便于 实现明文到它的映射。 陷门函数的定义并未给出这类函数是否存在，但是他们指出“一个单钥密码体 制，如果能抗击选择明文攻击，就可以规定一个陷门单向函数。以其密钥作为陷 门信息，则相应的加密函数就是这类函数，这是构造双钥体制的途径。多项式求根 问题、离散对数( d l ，d i s c r e t el o g a r i t h m ) 问题、大整数分解( f a c ，f a c t o r i z a t i o n p r o b l e m s ) 、二次剩余问题( q r ，q u a d r a t i cr e s i d u e ) 以及模n 平方根问题( s q r o o t ) 都是我们常见的单向函数的例子，目前多数的公钥密码体制都是基于这些问题构造 8 第二章电子现金关键技术分析 的。 目前比较流行的公钥密码体制主要有两类：一类是基于大整数因子分解问题的， 其中最典型的代表是r s a 体制。另一类是基于离散对数问题的，比较有影响的是 e 1 g a m a l 公钥密码体制，此外还有影响比较大的椭圆曲线公钥密码体制等。 2 1 2r s a 公钥密码体制【9 1 d i f f i e 和h e l l m a n l 6 1 首次提出公钥密码体制的思想的两年之后，m i t ( m a s s a c h u s e t t s i n s t i t u t eo ft e c h n o l o g y ) 三位青年数学家r i v e s tr l ，s h a m i ra 和a d l e m a nl m 在1 9 7 8 年在其论文“am e t h o df o ro b t a i n i n gd i g i t a ls i g n a t u r e sa n dp u b l i c k e yc r y p t o s y s t e m s 一 ( ：实现数字签名和公钥密码体制的一种方法) 中最先提出了一种可行的实现方 法，这就是我们现在广泛使用的r s a 体制。r s a 体制的提出真正使得互不相识的通 信双方在一个不安全的信道上进行安全通信最终成为可能。r s a 算法的安全性基于 数论中的大整数分解的困难性。下面给出r s a 密码体制详细介绍。 方案：独立的选取两个大素数a ，改( 超过1 0 0 位的十进制数字) ，计算： n 。p lx 见 和其欧拉函数值： 妒( 咒) 一( 见- 1 ) ( p u 一1 ) 随机选择一个整数e ，1 ：e r p ( n ) r ( r p ( n ) ，e ) - i 。因而在模妒( 咒) 下，e 有逆元： d - e 。1 m o d q ，( n ) 取公钥为咒* 0 e ，私钥为d ( p t ，p 2 不再需要，可以销毁) 。 加密：将明文分组，各组在m o d n 下可唯一表示。可用明文集 4 - 工：1 s 石 甩，( 五万) 一1 ) x 4 的概率 型! 鱼二! 丛堡二! ! 1 一三一上+ 上呻1 矗pip2 1 1 p 2p i p 2 密文 ) ，一rm o d n 9 青岛大学硕士学位论文 解密： x y m o d n 证明：y d - ( z 厂一一，因为d e = l m o d 妒( 忍) ，所以如- q 驴( 刀) + 1 。由欧拉定理 ( 工，厅) a 1 ，x 小) = l m o d n ，所以有： y | - ( r ) 一一一一x 叫帕+ 1 _ 石z 神t z 1 = x m o d n 陷门函数：z 一( a ，p ：，d ) 。 理论上，r s a 的安全性取决于模1 1 分解的困难性，但数学上至今还未证明分解模 就是攻击r s a 的最佳方法，也未证明分解大整数就是n p 问题，可能有尚未发现的多 项式时间分解算法。质因数分解的处理时间如表2 1 所示。 表2 - 1 质因数分解所需时间( 每微秒运算一次) 因此，即使考虑到将来计算机技术进步的因素，当n 达到2 0 0 憧时，使用 2 1 3e 1 g a m a l 公钥密码体制【1 0 】 本文给出的两个电子现金方案当中并未直接应用到e 1 g 锄a l 公钥密码体制，但是 由于e i g a m a l 公钥密码体制及其广泛的应用于数字签名技术，而数字签名技术是绝大 多数数字现金方案都要用到的最重要的技术之一，因此在这做一下介绍。 方案：令z ，是一个有p 个元素的有限域，p 是一个素数，令g 是z ，( z ，中出去o 元素) 中的一个生成元。明文集m 为z ，密文集中是z p xz ，。选定g ( g 以) 以及厂me , + m m o d p ，并输出签名盯- ( m ，y ，岛厂) 3 ) 验证算法v e r ：对于口i 伽，y ，e ，r ) 验证等式9 7 一i y m o d p 和p - h ( 优，i ，) ，) 是 否成立。若成立则输出1 ，否则输出0 。 以目前的计算能力来看，当g 的位数1 6 0 b i t ，p 的位数为1 0 2 4 b i t 时可以保 证该数字签名方案的安全性。 2 3 4 盲签名【2 】 一般的数字签名中，总是要先知道了文件内容后才签署，但有时需要对一个文 件签字，而且不想让签名者知道文件的内容，称这样的签名为盲签名( b l i n d s i g n a t u r e ) 。利用盲变换可以实现盲签名。 图2 - 1 盲签字框图 1 9 8 2 年，d c h a u m 2 1 在提出盲签名的同时，给出了盲签名的第一个实现方案：盲 r s a 签名方案，主要是为了防止银行将电子现金和客户的身份联系起来破坏客户的 1 4 第二章电子现金关键技术分析 匿名性。该方案从r s a 公开密钥算法演变而来。 银行选择两个大素数p 和g ，以及一个单向函数厂，并随即选择一个e ，使得 g c d ( e ，驴o ”一l ，其中n p q ，驴o ) - ( p 一1 ) ( q 一1 ) 。由e d 一1 m o d 9 0 ) 求出 d e 。1 m o d q ，( n ) 。b 公开刀，e 和厂，保密p ，q 和d 。设待签名的消息为x ，按如下步 骤用户u 可以得到银行b 的盲签名。 1 ) u 随机选取：，z 口，计算m r f ( x ) m o d n ，并将m 传递给b 。 2 ) b 收到膨进行签名得s m 4m o d n ，然后将s 传递给u 。 3 ) u 计算c - m d r m o d n 一厂d ( x ) m o d nc 即为m 的盲签名。 u 容易验证：c 一( f 4 0 ) ) 。m o d n - f ( x ) m o d n 。 由此可以看出，b 对消息的签名合法，且b 不能将所签的消息与实际的消息联系。此 外，b 为了验证u 传送给他的待签消息x 的合法性，可借助分割选择技术。 盲签名可以让签名者在不知道所签文件内容的情况下签名，而文件拥有者将该 签名去盲后能够得到签名者关于真实文件的签名。在电子现金系统中目前常用的盲 签名方案有r s a 盲签名、s c h n o r r 盲签名、d s a 盲签名、o k a m o t o 盲签名、 n y b e r g - r u e p p e l 盲签名等。这些盲签名均从相应的普通数字签名协议中变换而来。 此外，一些其他的特殊数字签名技术也在电子现金方案中有重要应用，比如群 签名、代理签名等等。 2 4 身份证明技术 电子现金在使用过程中，用户从银行提取电子现金、用户向商家支付电子现金 都不可避免的需要进行合法身份的证明。我们更关心的是用户如何既能证明自己的 合法身份而又不泄露自己的身份信息，即保持交易的匿名性。这就需要用到零知识 证明技术。 2 4 1 零知识证明协议 零知识证明最初是由g o l d w a s s e r t l l l 等人在8 0 年代提出的。在这类协议中证明者 可以向验证者证明某命题的正确性却不泄漏关于命题的任何有用信息。 假设p ，v 表示在协议交互中正确履行协议的证明者( 又称示证者) 和验证者， f ，表示在协议交互中不按照协议执行的证明者和验证者。一个零知识身份证明系 1 5 青岛大学硕士学位论文 统必须满足以下三个条件： 1 ) 完备性( c o m p l e t e n e s s ) ：如果，则验证者v 将以极大的概率接受证明 者p 的命题； 2 ) 合理性( s o u n d n e s s ) ：如果，譬，则验证者v 将以极大的概率拒绝恶意证 明者p 的命题； 3 ) 零知识性( z e r o k n o w l e d g e ) ：恶意验证者将以小到可以忽略不计的概率获 得证明者p 的任何有用的秘密信息。 根据以相同的命题，为输入p 和某概率多项式时间图灵机与v 交互后输出结果 概率分布的不同可以将零知识证明划分为：完美的零知识证明、计算的零知识证明 和统计的零知识证明。这里不再赘述具体的定义。 o u i s q u a t e r 等人1 9 8 9 年在论文“h o wt oe x p l a i nz e r o k n o w l e d g ep r o t o c o l st oy o u r c h i l d r e n ( 零知识证明协议的通俗解释) 中给出了一个解释零知识证明的通俗 例子： 有一个洞，如图2 所示。假设p ( 示证者) 知道某个咒语，可以打开c 、d 之间的 暗门，现在我们来看p 如何向v ( 验证者) 出示证明使其相信他知道这个咒语，但又 不告诉v 这个咒语的内容。 图2 - 2 零知识证明图解 基本协议： 1 ) v 站在a 点； p 进入洞内任意一点c 或d ； 3 1 当p 进入洞内之后，v 走到b 点； 4 ) v 发指令给p ：( a ) 从左边出来，或( b ) 从右边出来； 5 )