（应用数学专业论文）群签名方案研究.pdf

群签名方案研究 司光东 摘要自从1 9 7 6 年d i m e h e l l m a n 在“密码学的新方向”中提出了公钥密码 学的概念并设计出了一个在公开信道上进行密钥交换的协议以来，公钥密码学得 到了飞速的发展。而数字签名作为公钥密码学中非常重要的一个分支也取得了很 快的发展。在当今计算机通信迅速发展的时代，由于数字签名在认证、数据完整 性、不可否认性和匿名性等方面发挥着非常重要的作用而受到了人们广泛的关 注。 群签名是数字签名中非常重要的一种类型，是由d 。c h a u m 和e v a nh e y s t 于 1 9 9 1 年首次提出来的。它允许群成员代表群进行签名而不泄露群成员的任何信 息。正是由于群签名方案中对群成员的匿名性，使之在电子选举、电予投标和离 线电子货币等方面有着潜在的应用价值。 群签名中，知识证明起着非常重要的作用，它使群签名方案具备了以前方案 所没有的抵抗某些攻击的能力，但目前提出的方案还不能很高效地删除群成员， 这将严重制约群签名的发展。可以自由增删群成员的动态群签名方案正是在这种 基础上提出来的，目前该方案的难点是寻找一些高效的可删除群成员算法，使之 在删除群成员时不以牺牲群签名整体的效率为代价。本文在这一方面进行了些 有益的探索，提出了一个基于网络认证的可删除群成员的动态群签名方案，该方 案中删除部分的效率较高且可移植于其它类型的群签名方案之中。 本文主要研究结果如下： 1 分析了三个基于离散对数的群签名方案证明了方案 c z 2 0 0 0 不具有防陷 害性和防伪造性，证明了方案 w f 2 0 0 3 不具有防伪造性，证明了方案 t j 9 9 不能 抵抗联合攻击、广义伪造攻击和不具有不可链接性。 2 基于r s a 算法和离散对数提出了一个利用i d 验证的群签名方案并对该 方案进行安全性分析，作者曾用各种常用方法尝试对其攻击，目前为止没有成功。 3 提出了一个基于网络认证的动态群签名方案。利用模块化设计原则对群 签名进行设计。方案包括认证和签名两个模块，这是群签名方案的一个独特构想 在签名模块中和用e i g a m a l 加密算法和知识签名等来构造群签名方案。 4 总结了群签名的发展历程并提出了一些可供参考的研究方向。 关键词：数字签名群签名动态群签名网络认证 r e s e a r c ho fg r o u ps i g n a t u r es c h e m e s s ig u a n g d o n g a b s t r a o ti nt h e i rs e m i n a l1 9 7 6p a p e r n e wd i r e c t i o n si nc r y p t o g r a p h y ，d i f f i ea n d h e l l m a nd e v i s e dt h ec o n c e p to f p u b l i ck e yc r y p t o g r a p h ya n dp r o p o s e dap r o t o c o lt h a t a l l o w st w oe n t i t i e st od e r i v eac o m m o ns e c r e tk e yo n l yb ye x c h a n g i n gi np u b l i c f r o m t h e no n ，p u b l i ck e yc r y p t o g r a p h yd e v e l o p e dq u c k l y ，s od i dd i g i t a ls i g n a t u r e s ，p a r t so f p u b l i ck e yc r y p t o g r a p h y w i t ht h eq u i c kd e v e l o p m e n to f c o m m u n i c a t i o ni nc o m p u t e r s ， d i g i t a ls i g n a t u r e sh a v ep l a y e da l li m p o r t a n tr o l ei nt h ea s p e c t so fa u t h e n t i c a t i o n ，d a t a i n t e g r i t y , n o n - r e p u d i a t i o n ，a n o n y m i t ya n ds oo n g r o u ps i g n a t u r ew h i c hi sas o r to fi m p o r t a n td i g i t a ls i g n a t u r e s ，f i r s ti n t r o d u c e db yd c h a u ma n de v a nh e y s ti n19 9 1 ，a l l o w e di n d i v i d u a lm e m b e r so fag r o u pt om a k e s i g n a t u r e so nb e h a l f o ft h eg r o u pw h i l ep r o v i d i n gt h es i g n e r sa n o n y m i 锣o w i n gt oi t s a n o n y m i t y , g r o u ps i g n a t u r ec a nb ea p p l i e di nt h ea c t i v i t yo fe l e c t r o n i cp o l i t i e sa n d e l e c t r o n i cc o m m e r c es u c ha se l e c t r o n i cv o t i n g ，e l e c t r o n i cb i d d i n ga n do f f - l i n e e l e c t r o n i cc a s ha n ds oo n s i g n a t u r eo f k n o w l e d g ep l a y sa ni m p o r t a n tr o l ei nt h eg r o u ps i g n a t u r eb e c a u s ei tc a n a v o i ds o m ea t t a c k sc o m p a r e dw i t he a r l yo n e s h o w e v e r , t h ee f f i c i e n c yo fm a n y r e v o c a t i v eg r o u ps i g n a t u r e sp r o p o s e da tp r e s e n ti sp o o ra n di th a so b s t r u c t e dt h e d e v e l o p m e n to fg r o u ps i g n a t u r e t h i si so n eo fr e a s o n st h a td y n a m i cg r o u ps i g n a t u r e w h i c hc a nd e l e t eg r o u pm e m b e r se f f i c i e n t l yi sp r o p o s e d a tp r e s e n t ，t h ed i f f i c u l t i e se rad y n a m i cg r o u ps i g n a t u r ea r et os e a r c hs o m ee f f i c i e n t a l g o r i t h r nt od e l e t eg r o u pm e m b e r sb u t n o tc u td o w nt h ee f f i c i e n c yo fg r o u ps i g n a t u r e w ee x p l o r e si tb e n e f i c i a l l yi nt h i sd i s s e r t a t i o n b a s e do nn e t w o r ka u t h e n t i c a t i o n ，w e p r o p o s e da ne f f i c i e n td y n a m i cg r o u ps i g n a t u r es c h e m et od e l e t eg r o u pm e m b e r s t l l i s r e v o c a t i v es c h e m ec a nb et r a n s p l a n t e dt oo t h e rg r o u ps i g n a t u r es c h e m e s t h ef o l l o w i n ga r et h em a i nr e s e a r c h i n gr e s u l t s ： 1 t h es e c u r i t i e so f t h r e eg r o u ps i g n a t u r es c h e m e sa r ea n a l y z e d w ep r o v et h a tt h e s c h e m e c z 2 0 0 0 i s n ts a t i s f i e dw i t he x c u l p a b i l i t ya n du n f o r g e a b i l i t y , t h es c h e m e 【w f 2 0 0 3 】i s n ts a t i s f i e dw i t hu n f o r g e a b i l i t y , t h es c h e m e 【t j 9 9 】i s n ts a t i s f i e dw i t h c o a l i t i o n r e s i s t a n c ea n du n i v e r s a lu n f o r g e a b i l i t ya n du n l i n k a b i l i t y 2 b a s e do nr s aa l g o r i t h ma n dd i s c r e t el o g a r i t h m ，ag r o u ps i g n a t u r es c h e m ew i t h i dv e r i f i c a t i o ni sp r o p o s e da n da n a l y z e d w ee v e na t t a c k e di tb yal o to fm e a n sa n d f a i l e d 3 b a s e d 0 1 1n e t w o r ka u t h e n t i c a t i o n ，a d y n a m i cg r o u ps i g n a t u r e w i t h m o d u l a r i z a t i o ni sp r o p o s e d t h i si sas p e c i a lc o n c e p t i o n0 1 1g r o u ps i g n a t u r e 4 w es u m m a r i z et h ed e v e l o p i n gp r o c e s so fg r o u ps i g n a t u r ea n dp o i n to u ts o m e o r i e n t a t i o n st or e s e a r c h k e y w o r d s ：d i g i t a ls i g n a t u r eg r o u ps i g n a t u r e d y n a m i cg r o u ps i g n a t u r e n e t w o r ka u t h e n t i c a t i o n 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人 已经发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均 已在文中作了明确说明并表示谢意。 一， 少l 一 作者签名；盔i 堑：生：日期。继! 留 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西 师范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文 的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆、院系资料室被查阅：有权将学位论文的内容编入有关数据库进 行检索 有权将学位论文的标题和摘要汇编出版。 名；批 第一章绪言 自古以来，通信安全保密在国家的军事和经济等方面占有重要的位置。同时， 随着计算机和电子通信技术的普及与发展数据的认证在现实社会占有愈来愈重 要的位簧。在我国，由于信息高速发展，信息技术与信息产业日益受到重视，在 信息的传输与处理的过程中，如何保护信息使之不被非法窃取或窜改，成为人们 关注的十分重要的问题。 自从1 9 7 6 年w d i f r i e 与m e h e l l m a n 发表了“密码学的新方向”p 叫以来，在 密码学领域中爆发了一场重要的变革。从那时起，密码学理论与技术逐渐从军事 独有向民用及经济领域渗透，并且取得了长足的发展。 毫无疑问，数字签名是这场革命中的一项重要成就，它是保证数据完整性和 实现网络认证以及开展现代电子商务的重要工具之一。它类似于传统的手写签名 或印章，以便于在法律上能认证、核准、生效。同时，又具有手写签名远不可及 的在网络上实现快速、远距离传输和认证的特点。在我国，随着电子签名法 于2 0 0 4 年8 月正式颁布实行，可以预见，数字签名将会在未来社会上发挥越来越 重要的作用。 自从数字签名的概念提出以来，数字签名技术得到了很大的发展。同时，与 数字签名相关的签名算法也在不断发展中。为了使多人签名得以应用，d e s m e d t 于1 9 8 7 年提出了群向密码系统( g r o u p - o r i e n t e dc r y p t o s y s t e m ) 。他指出，社会上 除了以个人为单位的实体之外，也存在许多由众多个人所组成的团体，如贸易公 司，学校和国家机关等等。当我们发送电文给这些团体时，都是直接写上这些团 体的名字，当电文到这些团体后，团体内部有一套处理规则。团体式密码体制把 数字签名的发展推向了更高一个层次。目前人们已提出了许多数字签名方案，如 不可否认签名、代理签名、门限签名、盲签名等。而群签名( g r o u ps i g n a t u r e ) 正是 这些数字签名中非常重要的一种。 1 1 群签名方案的发展背景及现实意义 群签名是由d c h a u m 和e v a nh e y s t 于1 9 9 1 年首先提出来的，他们通过下 面的例子1 ”j 加蛆说明： 一个公司有数台计算机，每台都连在局域网上。公司的每个部门都有自己的 打印机( 也连在局域网上) ，并且只有本部门的人员力被允许使用他们部门的打印 机。因此，打印时必须使打印机确信用户在哪个部门工作。同时，公司想保密， 不可以暴露用户的身份。如果在当天结束时发现打印机使用得爪频繁，丰管者必 须能够指 谁滥用了邢台打印机，并给他。个账啦。 对这个问题的解决方案称为群签名方案。也就是说，一个群签名方案应该具 有以下的三条性质： ( 1 ) 只有该群体内的成员才能够对消息进行签名。 ( 2 ) 签名的接收者能够证实签名是该群体内的个有效签名，但他不能发现 该签名是由哪一个具体的成员所签。 ( 3 ) 如果出现争议，该签名可以被“打开”以揭示签名者的身份( 可能有群 成员的参与) 。 一个公司可以利用群签名来认证帐单或数字合同，顾客仅需知道该公司的公 开密钥就可以验证签名的正确性。同时，公司不但对外隐藏了它的内部组织结构 而且在必要时公司仍然可以追查出签署某个文件的雇员。 由于群签名方案中的这种匿名性，使其在现实生活中具有广泛的应用前景， 它可以被应用于管理、军事、政治及经济等多个方面【2 ，1 5 , ml 。如电子商务【2 】、电 子现金( e l e c t r o n i cc a s h ) 、电子投标( b j e c u o n i cb i d d i n g ) 3 4 】及智能卡( s 如矾c a t d s ) 4 6 1 等中的应用。正是由于群签名这么多的应用范围，它引起了众多学者们非常浓厚 的兴趣，同时也取得了丰硕的成果。 d c h a u m 和e v i l l i h e y s t 在首次提出群签名方案的概念时，也提出了四个群 签名方案，尽管其中三个方案在打开签名时需要群成员协助，以及两个方案在系 统建立后不能增加新成员，但这并不妨碍它为群签名发展奠定的坚实基础。为了 使群签名能更加完善，l c h e n 和t p p e d e r s e n 于1 9 9 4 9 5 年提出了两个新的群签 名方案【3 5 ，3 6 l ，这两个方案分别提供了理论上和计算上的安全性，且可以自由地加 入新成员。此后学者们又提出了一些基于离散对数的群签名方案 4 7 , 5 4 - 5 7 】，可是许 多的离散对数方案已被证明是不安全的 7 , 8 , 2 1 , 4 0 , 5 9 】。1 9 9 7 年，j c a m e n i s h 和m s t a d l e r 首次提出适用于大的群体的群签名方案【25 1 ，可以称得上是群签名方案发展 史上的里程碑。该方案利用零知识证明思想来构造群签名方案，使群签名方案不 再像以前一样易受各种攻击。从此以后提出的许多方案d ，1 4 j 8 3 7 1 都借助于这种思 想。 当群签名方案的成员更新时，会引发许多问题而在前面的大多数方案中都 不能删除群成员或者删除群成员时效率不高。于是能高效地删除群成员的动态 群签名( d y n a m i c g r o u ps i g n a t u r e ) 6 3 1 就成为目前人们关注的焦点。现在已经提出了 一些可删除群成员的动态群签名方案 1 3 , 1 7 , 2 0 , 5 8 。 1 2 论文的章节安排与研究结果 本篇论文主要突m 作者在这三年r p 埘群签名研究所得到的一些成果和心得体 会同时对近十多年来群签名的发展状况进行分析、概括和总结，展现已提出的 群签名方案的优秀成果。 1 , 2 1 论文的章节安排 本篇论文共分为四部分，分别以绪言、背景知识、群签名的发展状况与安全 性分析以及群签名方案这四块加以讨论。 第二章：本章主要是引用了前人所做的优秀成果，这些成果对后面作者自己 和他人的成果起着基础性作用。第一节中的代数与数论又是其它几节的基础，介 绍了有限群、离散对数和大数分解等问题，并且也给出了它们的计算复杂度。第 二节介绍了一些加密算法和数字签名算法，主要以r s a 算法和e l g a m a l 算法为主， 这些著名的算法是后面提出的方案成立的基础。后两节分别介绍了数论假设和知 识签名，这些也是群签名方案成立的必要保证。 第三章，主要介绍了群签名的发展状况和对一些群签名方案的安全性分析。 在群签名的发展状况中以群签名的发展脉络为主线，同时也讨论了群签名方案以 后的主要研究方向。在第二节对一些群签名方案的安全性分析中主要讨论了三种 群签名方案 6 1 , 5 5 , 6 7 】，通过分析发现这三个方案都是不安全的。同时得出了这些方 案不安全的原因所在基于离散对数设置群签名方案时，引入的参数过多而验 证等式只有少数几个，也就相当于方程组中未知量远多于方程的个数一样，这样 就容易受到伪造等攻击。 第四章：介绍群签名方案。第一节中首先给出了一个利用i d 验证的群签名 方案，此方案在群管理员预计算下效率较高。在此方案中，作者把r s a 算法和离 散对数结合在一起来构造群签名方案。第二节中主要讨论了目前群签名方案的删 除成员算法。先对目前具有代表性的两个删除方案进行评述，然后作者提出了一 个基于网络认证的动态群签名方案，该方案采用模块化设计方法把动态群签名方 案分为两个模块进行设计，在几乎没有增加计算量的情况下实现了删除成员的目 的。 1 2 2 主要研究结果 作者在群签名方面主要取得了以下研究结果： 1 对三个群签名方案进行分析，证明了方案 6 】不具有防陷害性和防伪造 性，证明了方案 6 7 1 不具有防伪造性，证明了方案【5 5 】刁i 能抵抗联合攻击、，“义伪 造攻击和不具有不可链接性。 2 基于r s a 算法和离散射数提出了个利用i d 验汪的群签名方案并对该方 案进行安全性分析，作者曾用各种常用方法尝试对其攻击，目前为止没有成功。 3 提出了一个基于网络认证的动态群签名方案，利用模块化设计原则对群签 名进行设计。这是群签名方案的一个独特的构想，在签名模块中利用e 1 g a m a l 加 密算法和知识签名来构造群签名方案。 4 对群签名的发展历程进行了总结并提出了一些可供参考的研究方向。 l ，2 3 论文中的记号 z ：表示由所有小于掰且与聊互素的正整数组成的集合。 妒沏) 为欧拉函数。 口。a 表示a 是集合a 的随机选取的唯一元素。 a a ) 表示集合a 一 a ) = x a ix 口) 。 对于元素g g ( g 是群) ，o r d ( g ) 表示g 在g 中的阶。 j aj 表示口的二进制比特长度。 c j 】是二进制串c 的第比特。 h ： o ，1 ) 一 o ，1 ) + 表示强抗碰撞h a s h 函数。 i i 表示两个二进制比特串的链接。 知识签名s p k ( s i g n a t u r e b a s e do na z e r o - k n o w l e d g e p r o o f o f k n o w l e d g e ) 记为 s p k ( u j ，口2 ，口。) ：p r e d i c a t e 。 第二章基础知识 密码学是一门涉及非常广泛的的学科，它需要多个数学领域的知识，包括数 论、群论、环论、域论、线性代数、概率论以及信息论。同时，还应该熟悉计算 复杂性、算法和n p 完全性理论等知识。 2 1 代数与数论 代数与数论在密码学中扮演着非常重要的角色，它是密码学中非对称加密算 法的蒸础。许多算法的困难性都基于计算某一数学难题的困难性，比如，著名的 r s a 算法和e l g a m a l 算法就是基于计算大数分解的困难性和有限循环群中离散对 数的困难性。 2 1 1 群( g r o u p ) 定义2 1 1 6 s 1 设g 是非空集合，在g 中定义了一种代数运算，称为乘法， 记为“一。即对于g 中任意两个元素a ，b 都唯一确定g 中一个元素口b ，称为巩b 的乘积。如果g 对这种运算满足下面几个条件： 1 ) 结合律：对g 中任意3 个元素口，b ，c 都有 ( 口6 ) 口= a ( 6 + c ) 2 ) 单位元素的存在：g 中存在个元素e ，对予g 中任意元素a ，都有 f 口盘口已= 口 3 ) 逆元素的存在：对g 中任一元素o ，都可找到g 中一个元素a ，使得 a 一1 口；a 口一= e 那么g 就称为一个群。e 称为g 的单位元，a 。称为a 的逆元。 如果i g l 有限，则称g 为有限群，g 中元素的个数i g l 称为g 的阶。 z ，表示整数模m 的剩余类所构成的集合，在模肌加法下构成一个阶为朋的 阿贝尔群。 z ：在普通乘法模卅下构成一个乘群，阶为妒) ，其中p ( 研) 为欧拉函数。 定义2 1 2 欧拉函数陋4 】t 设h 是一个币整数，伊( h ) 的值等于序列i ，2 ，”一l 中与疗互素的整数的个数： 妒( 疗) = f 女f l s k - n 一1 ，g c d ( k ，疗) = 1 ) f 若整数分解为h = 兀p ，“，其中p ，表示不同的素数，则伊o ) = ”兀( 1 一) f = l卢ip 1 特别地妒( p ) = p l ，p 为素数。 群z 。对加法是。个循环群。 群z ：对乘法是循环群当且仅当n = 2 , 4 ，p ”( p 为奇素数) 。 2 1 2 数论问题 许多加密体制依赖于解决某个数论难题的不可行性，这里的不可行性是指在 合理有限的资源范围内找不到一个可行的算法来解决这个问题。在现实情况下是 指用运算速度最快的计算机和目前最优的算法在数年( 或几个世纪、宇宙时间) 内不能计算出这个问题。 离散对数问题是本篇论文中最根本的理论依据，它是密码学中的重要基础。 定义2 1 3 离散对数【2 5 1 ：设g 是个有限循环群且ge g 是g 的一个生成元。 元素口g 的离散对数是指唯一的整数x ，( o x l g l ) ，使得a = g 。成立。记为 x = l o g ga 若g 不是生成元，口基于g 的离散对数( 若存在) 是指最小的正整数x ，使口= g 。 成立。 离散对数具有以下性质： 设g = 是阶为 的有限循环群，口，b ，c g 1 ) l o g g ( a b ) ；l o g g ( a ) + l o g g ( b ) r o o d 疗 2 ) l o g f ( 口1 ) 童x l o g f ( a ) m o d 盯，v je z 3 ) 若h 是g 的另一个生成元，则l o g 。( 口) zl o g ( a ) 1 0 9 ( g ) 】“m o d n 当a = h 时，l o g 。( 向) ； 1 0 9 ( g ) 】“m o d 雄 定义2 1 4 离散对数问题( d l p ) 1 2 5 1 ：对于一个有限循环群g = 和元素 日g ，寻找整数矗( o 曼x 0 。肘z ：最高效的算法足数域筛法( n u m b e rf i e l ds i e v e ) 。 需要o fe x p ( 1 9 2 + o ( 1 ) ) ( 1 np ) ( i ni np ) 巧1 的计算复杂度。 定义2 1 5 离散对数代表1 2 6 j ：设g 是阶为泞的有限循环群，9 1 ，掌2 ，g 。是 g 的川个不同的生成元。元素a g ，若m 维数组 ( _ ，x 2 ，x 。) ，0 膏，h 一1 , 1 s i m 使d = 兀g j 成立。称 i - i ( x i ，工2 ，x ，) 0 x 打一1 ，l i 茎m 为元素a 的代表。也叫指数组。 元素ae g 关于生成元g 。，g ：，g 有玎”个m 维代表a 定义2 1 6 代表问题( t h er e p r e s e n t a t i o np r o b l e m ) 1 2 6 】：对于有限循环群g 和生成元组g 。，g ：，g ，以及元素a g ，寻找整数组 ( x 1 ，x 2 ，x _ ) ，o 冬x i h 一1 ，l i m 使口= 兀酽成立。 j l - 离散对数的代表问题是离散对数问题( d l p ) 的推广。如果随机地选择生成 元g l , g ：，g 。，也就是说若生成元之间的离散对数是未知的这两个问题的困 难性是等价的。 定义2 1 7 d i f f i e h e l l m a n 问题【6 8 】：对于一个有限循环群g 和它的生成元g 以及两个元素g ”和暑，寻找对应的元素g “。 若d l p 在多项式时间内可解，则d i f f i e h e l l m a n 问题在多项式时间内也可解。 这是由于先可计算“= 1 0 9 。( g ”) ，然后计算( g ”) ”即可。反之是否成立，到目前为 止还没有解决，不过在某些群中，这两个问题的计算量是相当的 m w 9 6 晡”。 定义2 1 8判定性d i f f i e - h e l l m a n 问题吲( t h ed e c i s i o nd i f f i e - h e l l m a n p r o b l e m ) ：对于有限循环群g 和它的一个生成元g 以及三个元素g ”，g ”，g ”，判 定z ”与g ”是否相等。 下面介绍大接数分解，它的困难性问题是r s a 公钥加密体制的基础。 定义2 1 9 整数因子分解问题( t h ei n t e g e rf a c t o r i z a t i o np r o b l e m ) 【2 6 】：给定 整数 ，对”进行因子分解 = p ；。p ；2 p p ，是不同的素数，e 是正整数。 整数分解的算法复杂度可分为以下两种情况讨论。 1 ) 普通算法。算法复杂度与n 的大小有关，比如应用二次筛法和普通数域筛 法。因子分解最显而易见的算法是试除法，当然最糟的情况就是把小于 的整 数- 试除来分解月。p 0 1 7 5 是较高教的算法，其运行时洲为o ( 们。 2 ) 特殊算法。其运行时间依赖于”的特性，比如最大素因子的尺寸大小。 若疗有小素因子，用椭圆曲线方法f 2 6 1 的运行时间为 o e x p ( 1 + 0 0 ) 4 2 i n p i n i n p ) j 。 通过上述可以看出，到目前为止，对于大数分解的算法复杂度是多项式时间 的，随着大整数的比特长度增长而变得越来越困难。 定义2 1 1 0 e 次方根1 2 5 】：设g 是个群，整数e i g i 。对于元素a , b 仨g 。 若b = a 成立，我们把b 叫做元素口的e 次方根。 当g c d 似妒( g f ) ) = l 时，元素口的e 次方根存在且唯一，若 g i 已知时，可以 通过以下方法计算口的e 次方根，在z | 中先计算e 一，然后再计算b = a “即可。 定义2 i i ie 次方根问题：群g 的阶是未知的，对于正整数e l g i 和元素 口g ，寻找元素b g ，使b 。= 口。 若g = z ：，”= p q ，p ，q 是两个不同的素数，而当b z 。时，这个问题就是r s a 问题。若押可以被分解时，则易知j g j - 矿( ，) = ( p 1 ) ( g 1 ) ，此时可容易地求解e 次根问题。也就是说，如果大数分解问题易解时，则容易求解r s a 问题。 定义2 1 1 2 【6 4 】设 是两个素数p ，口的乘积，且ae z 。，若存在整数w ，使 w 2 = a r o o d 玎成立，则称口是模刀的二次剩余( 平方剩余) 。游不存在整数w 使 w2 = a m o d n 成立，则称a 是模刀的二次非剩余。所有模”的= 次剩余和二次非剩 余的集合分别记为 舛。和q n r 。 若n 的因子分解已知，容易判定一个元素是否是模 的二次剩余。而当n 的因 子分解未知时，判定一个元素是否是模，f 的二次剩余是一个困难性问题。 定义2 1 1 3 二次剩余问题( t h eq u a d r a t i cr e s i d u o s i t y p r o b l e m ) ：给定整数玎和 吼( 0 蔓口 0 o t h e r w i s e 2 。2 3e l g a m a l 签名方案 生成算法：取有限循环群g 中元素g ，且i g | _ q ，其余的参数与其加密方案 相同。 签名算法：设消息为m ，签名者任选随机数，z 。，计算 “= g r , s = ，。( h ( m ) 一x u ) m o d q ，则( “，s ) 就是消息m 的签名。 验证算法：g “1 = y 。掰5 2 2 4s c h n o r r 签名方案 生成算法：同上。 签名算法：设消息为m ，签名者任选随机数r 乙，计算 c = h ( m | | g ) ，j = r c x ( m o d q ) 。 验证算法：c = h ( m | | 9 5 y 。) 2 3 数论假设 数论假设( n u m b e r - t h e o r e t i ca s s u m p t i o n ) 是密码学中非常重要的理论基础， 它也是本篇论文成立的理论根据。因为在密码学中许多的困难性问题还不能在理 论上证明是安全的，或有一些问题在理论上是可解的。但在计算上是不可行的， 即许多问题都是计算安全的。 假设1 ( r s a 假设) 对于所有的多项式尸( x ) 与任意充分大的，存在一个 概率算法，使得对于所有的概率多项式时间算法a ( p r o b a b i l i s t i ep o l y n o m i a l t i m e a l g o r i t h m s ) ，均有 p r 肠剐8 j ( g ) ：钉( 1 ) 引刊( g 一一) 】 斋 成立。 假设2 ( 强r s a 假设) 对于任意的多项式尸( x ) ，与所有充分大的，。，使得对 于所有的概率多项式时问算法a ，存在一个概率算法7 ，均有 1 阶 ”“。”州旧亦玎( r q ( 郴) 车邸，圳 】 1 为系统的一个安全特征，称满足c = h ( g | | y | l g 。y 。i f m ) 的数对( c ，j ) o ，1 。 - 2 0 。，2 “o “ 是消息m o ，1 ) + 关于y 基于g 的离散对数 的知识签名。记作s p k a ：y = g 。 ( m ) 。 如果知道满足x = l o g y 的秘密密钥x o ，l “，则可以通过如下方法计算消息 m 0 1 1 的签名。 1 ) 选择，r ( o ，1 ) 巩“1 ，并计算，= g 2 ) c = h ( g l j y j j ，| l m ) 3 ) j = r c x ( i n ，z 1 若上述指数运算全在z ：上，则可以选择，e 。z ：，= g7 m o d p ，( 聆i p 1 ) ，然后 计算f = h ( g f f 川圳凹) 与j = ，- c x ( m o d n ) 。 定义2 4 4 9 1 设0 l 为系统的一个安全特征称满足 c = h ( g i | h0y l | jy 20g y