（应用数学专业论文）群签名及其在电子现金中的应用研究.pdf

摘要 论文题目：群签名及其在电子现金中的应用研究 学科专业：应用数学 研究生：陈志强 指导教师：王尚平教授 摘要 签名： 签名： 在信息和计算机网络技术快速发展的今天，信息安全问题已经成为国内外计算机和网 络应用研究的热点课题。而数字签名作为认证的重要手段，在网络环境下，为身份认证、 数据完整性、不可否认性等问题提供了技术支持。群签名是数字签名的一个重要分支，可 以提供一些特殊的认证要求。由于群签名自身良好的特性，尤其是其匿名性可以用来很好 地隐藏组织内部结构、保护隐私，使得群签名可以作为工具用来设计一些对匿名性有要求 的协议，例如利用群签名设计电子现金协议、电子选举协议等。本文重点研究了群签名理 论及其在电子现金中的应用，主要工作如下： 1 简单概括了群签名的发展历史和研究现状，并且描述了群签名的定义、安全特性， 对几个群签名的变体作了介绍。 2 提出一个基于身份的成员分类的群签名方案，在该方案中，用户被分为不同的小 群组，每一个小群组有一个管理者，群成员只能代表其所在的群组进行签名。任何一个成 员均不能超越自己的权限代表其他群组进行签名，验证者可以根据公开的群组公钥来验证 签名。这样的的签名方案层次清楚，结构合理，使得管理起来更有效，尤其适合大群组的 签名方案。 3 介绍了电子商务中电子现金系统的基本知识、发展以及存在的问题，基于群签名 构造了一个新的电子现金系统，并分析了电子现金方案的效率。该方案满足多方面的安全 要求，并且具有较高的安全性和效率。 关键词：群签名；双线性对；电子现金；数字签名 本文得到以下资金的资助： 国家自然科学基金( 6 0 2 7 3 0 8 9 ) 陕西省教育厅专项科学研究计划资助项目( 0 6 j k 2 1 3 ) 陕两省科学研究计划批准项目( 2 0 0 5 f 0 2 ) 西安理工大学科技创新基金( 1 0 8 2 1 0 4 0 2 ) 国际合作项目( 日本) 京通株式会社( 1 0 8 2 3 0 5 0 1 ) 企业项目( 西安) 西安瑞日电子发展有限公司( 1 0 8 2 3 0 6 0 8 ) a b s t r a c t t i t l e ：r e s e a r c ho ng r o u ps i g n a t u r e sa n dl t sa p p l i c a t i o n i ne l e c t r o n i cc a s h m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：z h i q i a n gc h e n s u p e r v i s o r ：p r o f s h a n g p i n gw a n g a b s t r a c t s i g n a t u r e s i g n a t u r e i n f o r m a t i o na n dn e t w o r kt e c h n i q u e sa r er a p i d l yd e v e l o p i n gi nn o w a d a y s ；i n f o r m a t i o n s e c u r i t yb e c o m e sar e s e a r c hh o t s p o ti nc o m p u t e ra n dn e t w o r ka p p l i c a t i o no r g a n i z a t i o n sb o t ha t h o m ea n da b r o a d a sam a i nm e t h o do fa u t h e n t i c a t i o n ，d i g i t a ls i g n a t u r ec a ns o l v ep r o b l e m s s u c ha si d e n t i t ya u t h e n t i c a t i o n d a t ai n t e g r i t y , a n du n d e n i a b i l i t y g r o u ps i g n a t u r ei sa ni m p o r t a n t e m b r a n c h m e n to fd i g i t a ls i g n a t u r e ，a n di tc a np r o v i d es o m es p e c i a l a u t h e n t i c a t i o n g r o u p s i g n a t u r e sh a v es o m ef a v o r a b l ep r o p e r t i e s ，e s p e c i a l l y ；t h e i ra n o n y m i t yc a nh i d et h es 仃u c t l l r eo f ag r o u pa n dp r o t e c ti t sp r i v a c y , s ot h e yc a nb eu s e dt od e s i g np r o t o c o l sw h i c hd e m a n d a n o n y m i t y , s u c h 嬲e - c a s ha n de - v o t es c h e m e se t c i nt h i sp a p e rw e s t u d i e dg r o u ps i g n a t u r e a n di t sa p p l i c a t i o n si ne - c a s h t h em a i nw o r k sa r e 嬲f o l l o w s ： 1 t h ed e v e l o p m e n tt r e n da n dt h er e s e a r c hs t a t u so fg r o u ps i g n a t u r ea r es u m m a r i z e d ，t h e c o n c e p ta n ds e c u r i t yp r o p e r t i e so fg r o u ps i g n a t u r ea r ed e s c r i b e d ，a n ds o m ev a r i a n t so fg r o u p s i g n a t u r ea r eb r i e f l yi n t r o d u c e d 2 a ni d b a s e dm e m b e rc l a s s i f i e d g r o u ps i g n a t u r es c h e m ei sp r o p o s e d ，t h et l s c t sa r e c l a s s i f i e di n t os m a l lg r o u p si nt h en e ws c h e m e ，t h e r ei sam a n a g e ri ne v e r ys m a l lg r o u p ，a n da u s e rc a ns i g nam e s s a g eo nb e h a l fo fh i sg r o u p ，b u th ec a n tt r a n s c e n dh i sf i g h ta n ds i g na m e s s a g eo nb e h a l f o fo t h e rg r o u p s ，t h ev e r i f i e r sc a nv e r i f yas i g n a t u r ea c c o r d i n gt ot h eg r o u p s p u b l i ck e y s s u c hs i g n a t u r e sa r ew e l la r r a n g e ds ot h a tt h e yc a t lb ee f f i c i e n tm a n a g e d ，s ot h e y a r es u i t a b l ef o rl a r g eg r o u p se s p e c i a l l y 3 t h eb a s i ck n o w l e d g eo fe c a s ha n di t sd e v e l o p m e n ta r ei n t r o d u c e d ，a n dt h ep r o b l e m si n e - c a s ha r ed i s c u s s e d an e we c a s hs y s t e mb a s e do ng r o u ps i g n a t u r ei s p r o p o s e da n di t s e f f i c i e n c yi sa n a l y z e d t h en e ws c h e m es a t i s f i e sm o s to ft h er e q u i r e m e n t si ne c a s h ；i th a sh i g h s e c u r i t ya n de f f i c i e n c y k e yw o r d s ：g r o u ps i g n a t u r e ；b i l i n e a rm a p ；e l e c t r o n i cc a s h ；d i g i t a ls i g n a t u r e 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名缆颦骂驴符毒月群日 学位论文使用授权声明 本人j 迥在导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为教学和 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) 论文作者签名：落! 盘1 i 虫 导师签名： 口8 年；月沙日 第一章绪论 1 绪论 1 1 引言 i n t e r a c t 和通信技术的广泛应用，使得如今的许多社会活动已经离不开网络，社会对 计算机和网络系统的依赖性越来越大。随着电子邮件、电子商务、电子政务等系统的不断 发展，网络在给人们提供方便的同时，也将使用者暴露给互联网上的一些不法之徒。若计 算机和网络系统的安全受到危害，则会危及国家的安全，引起社会的混乱，从而造成重大 的损失。总之，信息安全与人们的同常生活已经变得密不可分，因此，人们越来越重视信 息的安全性，信息安全成为当今社会急需要解决的技术之一。确保计算机和网络系统的安 全成为世人关注的社会问题，并成为计算机科学技术研究的热点。 信息安全的概念经历了漫长的历史阶段，9 0 年代以来得到了深化，它包括： ( 1 ) 机密信息的保密性：保证机密信息不会泄漏给未经授权的人。 ( 2 ) 信息的完整性：防止信息被未经授权人的篡改。 ( 3 ) 信息的可用性：保证信息和信息系统确实为授权者所用，防止由于计算机病毒或 其它人为因素造成系统的拒绝服务，或者被非法者所用。 ( 4 ) 信息的可控性：对信息和信息系统实施安全监控管理，防止非法利用信息和信息 系统。 一 ( 5 ) 信息的不可否认性：保证信息行为人不能过后否认自己的行为。 要保证在开放的网络中通信的安全性，一个有效的解决办法就是利用密码技术。加密、 数字签名、基于口令的用户认证是实现安全通信的一些最基本的密码技术。越来越复杂的 电子商务、事务处理和服务形式，对在开放的网络中实现安全通信的需求正在迅速增加。 密码学能为保护信息安全提供有效的手段，为信息安全提供关键技术，现代密码学用于解 决信息的保密性、完整性、不可否认性。近年来密码学的研究和发展备受国内外的重视， 因此，密码学得到了长足的发展。 数字签名在身份认证、数据完整性、不可否认性以及匿名性等方面发挥了重要的作用， 因此研究数字签名具有重要的意义。它对于建立人们对网络安全的信任具有不可替代的作 用。为了满足不同应用环境下的需求，人们又提出了许多特殊用途的数字签名方案，例如 群签名、盲签名、代理签名、基于身份的签名等等。 群签名作为数字签名的一个重要分支，它允许签名者代表整个群体签名，并且能提供 签名者的匿名性，即签名者的身份不会暴露给验证者。但是当发生纠纷时，这种匿名性可 以被群主管撤销，从而确定签名者的真实身份，这种特性使得群签名能够应用在实际生活 当中。 电子现金是一种重要的电子支付系统，作为传统现金在网络空f a j 的模拟，具有其它电 子支付方式所不可比拟的优点，从而成为电子商务网络支付的首选技术。电子现金的安全 西安理工大学硕士学位论文 性和可靠性主要是靠密码技术来实现，到目前为止，电子现金系统的安全性和匿名性大都 是基于以公钥密码体制为基础的群数字签名和盲数字签名技术。 1 2 群签名及其发展状况 群签名的概念最早由c h a u m 和h e y s t 于1 9 9 1 年提出。一个群签名方案允许一个群 的成员代表这个群体来对一个消息进行签名。验证者可以使用唯一的群公钥来验证签名， 但是验证者并不能确定签名者的身份；为了防止以后产生的纠纷，群主管可以打开签名， 也就是说他可以断定签名者的身份；而且要断定两个签名是否是同一个成员所发布是困难 的。群签名与一般的数字签名最大的区别在于一般的数字签名只涉及签名者和验证者，而 群签名还要有一个群主管，同时签名要具有匿名性和不可联系性。 自从群签名的概念提出来之后，国内外许多的研究机构都开始研究群签名，从而大量 的群签名方案阳一一1 被提出来。c h e n 和p e d e r s e n 的群签名方案“1 回答了c h a u m 提出的一 些公开问题，同时首次提出了允许群体增加新成员的群签名方案。c a m e n i s c h 对广义群签 名还进行了研究，但是这时候的群签名大都不能高效地增加新成员，要想增加新成员，必 须修改群公钥；而且群公钥和签名的长度随着群成员的增多而线性增长，所以这样的群签 名方案不适合于大群体。 1 9 9 7 年，c a m e n i s c h 和s t a d l e r 提出了第一个效率相对较高且适用于大群体的群签名 方案“1 ，该方案通过引入一个注册过程，使得群组能够灵活地增加新成员，为群签名走向 实用迈进了关键的一步。在这之后人们对群签名的研究异常活跃，也取得了大量的研究成 果。并且开始注重群签名的安全性、高效性和实用性。g a t e n i e s e 等人提出一个可以抗 联合攻击的方案2 1 ，而且效率很高。g a t e n i e s e ，d s o n g 和g t s u d i k 等人提出一些很好 的成员删除方案6 1 ，只是方案中用到了离散对数知识证明，这样便使得开销增加，并且验 证算法的开销也随着删除成员的增加而增加，群成员的删除问题还是没有很好地解决。 2 0 0 2 年，c a m e n i s c h 和l y s y a n s k a y a 提出了一个新的群签名方案1 ，方案中用动态累 加器来解决群成员的删除，并且群公钥长度不变化，此方案是以a t e n i e s e 的方案1 为基 础，加入删除机制，运算开销并没有显著增加，但是，群公钥中包含一个随着成员增加或 减少而不断更新的值，而且在公钥更新之后，群成员需要在本地更新自己的证据值。 近几年来，双线性对即w e i l 对和t a t e 的出现，成为了构造基于身份的密码方案的重 要工具，使得实现先前不切实际的密码学设想成为了可能。随着基于身份密码系统的出现， 密码学者提出了大量的来自于双线性对的基于身份的密码方案8 9 1 0 j “1 2 j 3 1 4 1 y1 9 9 7 年p a r k 、 k i m 和w o n 最先提出基于身份的群签名，只是这个方案的效率非常低，群公钥和签名 的长度是和群的大小成比例的。最近几年，密码工作者们提出了大量的来自于双线性对的 群签名方案n6 1 7 8 一盯，这些方案大多都是基于有限域上的离散对数困难问题的。 2 0 0 3 年，x i a o f e n gc h e n 等人中提出了一个新的来自双线性对的基于身份的群签名方 案钉。该方案解决了密钥托管问题，同时假设只有一个p k g 并且p k g 不再是一个可信 2 第一章绪论 的实体。这个方案中群公钥的大小和签名的长度独立于群成员的个数。该方案的一个缺点 是如果用户想对多条消息签名，相对于每条消息来说，必须生成一个新的密钥对，这限制 了这一方案的实际应用。 到2 0 0 4 年后，利用双线性映射建立群签名得到了深入研究，b o n e h ，b o y e n ，和s h a c h a m 的方案n 7 1 还有c a m e n i s c h 和l y s y a n s k a y a 的方案盯都以双线性映射为基础构造了群签名 方案。这些方案的效率比较高，但是依赖于一些新的数论假设。j a nc a m e n i s c h 和j e n sg r o t h 在他们的方案2 盯中进一步提高了效率，并且满足一些在文献【2 1 】中对群签名的新的安 全性定义。b e l l a r e 构造了动态群签名的新模型 2 2 1 9 并重新定义了匿名性、可追踪性、防 陷害性。 成员的删除问题一直是群签名发展的一个最大障碍，直到2 0 0 1 年，b r e s s o n 和s t e m 给出了一个可撤消的群签名方案12 3 9 群签名的研究才有了突破性的进展。随后，密码工 作者又相继提出了一些可撤销用户的群签名方案。例如，有使用动态累加器设计的方案， 并使用该累加器来实现成员撤销，还有的方案使用互素性来删除群成员。但是这些方案的 效率仍不够理想，有待于进一步探讨。 1 3 电子现金及其发展状况 传统现金( 包括纸币和硬币) 经过千百年的发展，已经在人类社会中发挥着无可替代的 重要作用，但是随着因特网的飞速发展，电子商务的兴起，人们迫切需要寻找一种能够在 网络空间中完全替代传统现金的电子支付方式。自从素有“电子现金之父之称的d c h a u m 博士在1 9 8 3 年提出了电子现金的概念乜4 1 之后，人类的这个梦想正一步一步地走向现实。 通过对电子现金研究的发展历程进行总结，我们认为大致可以将其分为三个阶段：第一个 阶段从1 9 8 3 年至八十年代末，为在线电子现金研究阶段；第二个阶段从九十年代初到1 9 9 3 年，为离线电子现金研究阶段；第三个阶段从1 9 9 3 年以后到现在，为电子现金走向实用化 的研究阶段。 ( 1 ) 在线电子现金协议 第一个阶段为在线电子现金协议研究，这个阶段的标志为1 9 8 3 年c h a u m 提出的匿名电 子现金，为整个电子现金领域的研究奠定了基础。d c h a u m 在文献【2 4 】中首次将盲签名 技术应用于非追踪性支付方案中，提出了匿名电子现金的概念，从此奠定了其在电子现金 领域的权威地位。c h a u m 方案中的电子现金与现实生活中的传统现金相似，由银行发行， 并具有可证明的匿名性：即使银行和商家联手也不能跟踪使用电子现金的用户。为了防止 用户重复使用电子现金，c h a u m 提出了由银行记录己花费的电子现金的方法，由银行在线 检查商家到银行存款的现金中是否有已花费的电子现金，采用这种方案要求银行必须在线 检查，因而这种电子现金称为在线电子现金，这种银行在线检查的方式往往使银行成为通 信中的瓶颈，从而限制了电子现金的实用性。 但是其后的几年内，相关的研究成果比较少，只有d a m g a r d 在1 9 8 8 年利用两方的密码 西安j e _ r - 大学硕士学位论文 协议和零知识证明构造了一个安全性可证明的在线电子现金系统2 钉，他的目的不是为了 开发实际的支付系统，而是为了证明确实存在理论上安全的电子现金，但该方案存在一些 缺陷，后来p f i t z m a n n 和w a i d n e r 对其进行了更正2 ，在假定存在陷f - j 向置换函数的前 提下，给出了构造安全性可证明的离线电子现金方案的方法，为后续的其它安全性可证明 的电子现金系统奠定了基础。 ( 2 ) 离线电子现金协议 第二个阶段为离线电子现金研究阶段，通过分析主要的文献，我们可以发现这个阶段 的研究成果有以下的特点：两种均属于不可证安全性的电子现金方案。为了避免银行进行 在线验证，c h a u m f i a t 并l n a o r 提出了离线匿名电子现金的概念n ，采用“发现”而不是 防止的方法来解决重复花费问题。他们的方案的安全性依赖于一些随机性的假设，且并没 有给出正式的证明，所以不适用于实际的电子现金系统。但是他们在方案中详细论述了如 何构建一个离线电子现金系统，为后来出现的更加安全和高效的电子现金系统打下了基 础。在该方案的提取和支付协议中使用的零知识证明所采用的是首次引入的“分割选择 ( c u t a n d c h o o s e ) 技术”。对于每一次购物，由于必须传送、存储和验证k 个货币，因此 导致了额外的通信、计算和存储开销，所以该方案的效率有待提高。 p f i t z m a n n 和w a i d n e r z e 9 2 年对d a m g a r d 的在线电子现金方案进行了改进，将其变成了 离线方案，但是这两种方案都是基于通用计算协议，因此实现效率不高。f r a n k l i n 和y u n g 在d a m g b r d 方案的基础上提出了一种理论上安全的电子现金方案，它不是基于通用计算协 议，而是基于离散对数假设( d i s c r e t el o g a r i t h ma s s u m p t i o n ，d l a ) 和已存在的相互信任关 系。f r a n k l i n 和y u n g 第一个举例说明了如何基于离散对数假设构造一个离线电子现金方 案，从而构造了一个正式的安全模型。他们的安全模型被后来许多电子现金系统所采用 【2 8 2 9 1 ( 3 ) 实用电子现金系统发展现状 电子现金具有其它电子支付无法比拟的特性，它广阔的应用前景不仅吸引了大量理论 研究者进行不懈的研究，而且也吸引了世界上很多国家进行实用系统的开发和试验。近几 年来，全世界已有几十项电子货币和电子钱包的试验方案。其中最有名的要数英国的 m o n d e x 、美国的d i g i c a s h 试验、c a f e 项目以及美国的v i s a 和n t t 联合试验。 1 4 研究背景及意义 现代通信技术、网络技术、和电子商务的不断发展，互联网广泛的应用，如何完整、 高效、安全地传输信息，成为信息安全工作者研究的热点。数字签名作为认证的主要手段， 在网络身份认证中起着非常重要的作用。人们若要在互联网上进行交易，都需要进行参与 方身份的认证和所传输消息的完整性、真实性认证，以确保交易、通信的安全进行，并提 供有力的法律证明，任何人都不愿意自身的利益受到损失。对数字签名理论和实际应用中 的研究都具有很强的现实意义。 4 第一章绪论 群签名作为一种特殊的数字签名，由于自身良好的特性，尤其是群签名具有匿名性的 特点可以用来很好的隐藏组织内部结构、保护隐私。使得群签名可以作为工具用来设计一 些对匿名性有要求的协议。例如利用群签名设计电子现金协议、电子选举协议等。可以说 群签名在政府领域、军队领域、企业管理领域都存在广阔的应用空间。近年来各国学者利 用群签名设计了一些电子现金协议、电子选举协议、电子拍卖协议等。 随着i n t e m e t 在全球的迅猛发展，电子商务作为2 1 世纪信息时代经济活动全新的技 术手段和方法，已经成为i n t e r n e t 最广泛的应用领域之一。在电子商务环境中，商家可将 商品信息发布在全球信息网，以供顾客在任何时间，任何地点通过互联网下订单，并可由 网上付款机制完成付款手续，因此电子支付具有方便、快捷、高效和经济的优势。用户只 要拥有一台上网的p c 机，便可足不出户，在很短的时间内完成整个支付过程，支付费用 仅相当于传统支付的几十分之一，甚至几百分之一。然而，电子支付方式给我们带来便利 的同时，也给不法分子提供了可乘之机。他们利用电子支付的不完善之处，从中谋取暴利， 侵犯银行及顾客的权益。因此，一个具有安全、高效的电子现金系统对电子商务的发展是 非常重要的。 1 5 本文主要内容及章节安排 本文主要研究了群签名方案的设计与分析，踢及群签名在电子现金中的应用。主要内 容如下： 介绍了一些经典的群签名方案，指出方案的优缺点，讨论了群签名的安全性，几乎所 有早期的群签名方案的安全性都是在随机预言模型下证明的，这样，只能得到启发式的安 全性证明。近来出现了不需要随机预言的群签名方案，但是这些方案的效率是一个尚待解 决的问题。 提出一个基于身份的成员分类的群签名方案，在该方案中，通过将群组中的成员分类， 使得每一类成员只能代表其所在的群组进行签名。任何一个成员均不能超越自己的权限代 表其他群组进行签名，验证者可以根据公开的群组公钥来验证签名。这样的签名方案层次 清楚，结构合理，使得管理起来更有效，尤其适合大群组的签名方案。 电子现金作为一种新的电子支付方式，从一提出便受到了国内外学者及专家的广泛关 注。利用电子现金支付不但可以保护顾客交易隐私，避免信用卡卡号被盗，并且具有交易 成本低和流通性佳的优点。由于以上的原因，我们以电子现金协议的分析与设计作为主要 研究内容。本文设计了一个公平的多银行电子现金系统，由于所基于的群签名具有良好的 性质，因此该系统的安全性好，效率高。 论文的章节安排如下： 第一章介绍了信息安全的重要性，群签名的研究历史、现状以及相关背景。介绍了电 子现金研究发展历程与现状。 第二章研究了密码学中用到的数学知识，简要介绍了与本论文相关的基本知识，包括 西安理工大学硕士学位论文 密码学、公钥密码体制、数字签名、h a s h 函数、零知识证明等。 第三章对群签名作了详细介绍，分析了几个重要的群签名方案的优缺点；设计了一个 成员分类的群签名方案，该方案几乎满足所有的群签名的特性，并在标准模型下分析了它 的安全性。 第四章介绍了电子现金系统，讨论了群签名在电子现金系统中的应用；给出了一个基 于群签名的多银行电子现金方案，并分析了电子现金方案的效率，最后给出了安全性分析。 第五章，总结全文，并展望了将来的工作中需要进一步解决的问题。 1 6 主要符号 a ( t r ) 一表示算法a 以参数口为输入，输出； m o ，1 ) 表示m 为一个k b i t 的0 ，1 信息块； m 0 ，1 表示m 为一个任意有限长的0 ，1 信息块； p r o b a ( ) 表示算法彳成功的概率； ，- 足瓦表示在瓦中随机选择，； z ：表示模素数p 下的乘法群； 1 表示l = ll l ，是自然数k 的一元表示。 丫 6 第二章预备知识和基本工具 2 预备知识和基本工具 大多数的密码体制都是基于一个或几个数论假设。密码学界的工作者一直致力于研究 密码学的理论基础一数论上的安全假设。数字签名是一种相当重要的认证手段，在解决身 份认证、数据完整性、不可否认性问题上起着举足轻重的作用：零知识证明是密码学中一 项非常有用的工具，被广泛应用于各种密码协议中，特别是要求具有匿名性的一类协议。 本章将介绍密码学的一些基础知识，包括密码学假设、公钥密码体制、h a s h 函数、零知 识证明、数字签名等，这些内容是密码学最重要的基础。 2 1 密码学假设 数字签名的安全性大都建立在一个或几个数学难题之上，下面我们介绍几个困难问题 和相应的密码学假设，它们将要在以后章节中陆续用到。 2 1 1 大整数分解问题 在数论中，有整数的唯一分解定理，任何一个大于1 的整数，若不论因子的次序，则 它可以唯一地表示成素数的乘积。在密码学中，有大整数的分解问题。 定义2 1 大数分解问题：给定整数，z ，找出它的素因子，即对刀进行因子分解 以= p ? p p ，其中b 是不同的素数，q 是正整数。 在数论中，大数分解问题是一个古老的问题。分解一个大数理论上并不复杂，但是实 际过程很费时，尽管如此，在这方面现在还是有一些进展。目前最好的大数分解算法是数 域筛选法( n f s ) ，对于大于1 1 0 位的十进制数来说，一般的数域筛选法是目前已知最快的 大数分解算法。还有一些算法如连分数算法、椭圆曲线法( e c m ) 对大数是没有用的，而 二次筛选法( q s ) 对于低于1 1 0 位的十进制数来说，是目前已知的最快算法。 大数分解是一个迅速发展的领域，但大数分解技术的发展未来仍不可知，因为没有人 能预见数学理论的进展。现在广泛应用的基于大数分解问题的r s a 密码体制，被认为是 安全性最好的体制之一。 定义2 2r s a 问题：给定，2 ，使其满足是两个不同大素数p ，q 的乘积。e 和( p - 1 ) ( q - 1 ) 互素，给定满足不等式：1 p ，c 刀一1 的三个大整数”，p ，c ，求整数m ，使得m 。= c m o d n 。 强r s a 问题：令玎是两个不同的大素数p ，q 的乘积，令g 是z ：的循环子群，且它的 阶为 g ，l1 0 9 ；gl = 乞。假定，l ，z g ，强r s ai 口- j 题就是，求“g ，p z 1 ，使其满足 z 三r e ( m o d n ) 。 强r s a 假设：存在一个概率多项式时间算法k ，输入一个安全参数乞，输出一个数 组( 力，z ) 。对所有这样的算法的集合p ，p 能解决强r s a 问题的概率是可以忽略的。 2 1 2 离散对数问题 离散对数问题是公钥密码体制中的一个基本问题，它的安全性决定了很多密码算法和 7 西安理工大学硕士学位论文 方案的安全性，如d i f t i e h e l l m a n 密钥协商、e 1 g a m a l 型签名体制及其变型等。 定义2 3离散对数：设g 是一个有限循环群且g g 是g 的一个生成元，元素a g ， 整数x 满足a = g 。且( 0 x o r d ( g ) ) ，则称x 为c l 的以g 为底的离散对数，用l o g 。a 表示， 即x = l o g 。a 。若g 不是一个生成元，则a 关于g 的离散对数( 若存在) 就推广到寻找最小的 正整数x ，使得a = g 。成立。 离散对数问题有以下的性质： 设g = 是阶为丹有限循环群，口，b ，c g ( 1 ) 1 0 9 9 ( a b ) 兰l o g ga + l o g gb m o d n ； ( 2 ) l o g 。a 。兰x l o g 。a m o d ，z ，v x z ； ( 3 ) 若h 是g 的另一个生成元，则l o g 。a 三l o g a 1 0 9 g 】-