（计算机应用技术专业论文）结构化多重数字签名的研究与应用.pdf

摘要 随着信息技术的迅速发展，我们巳步入信息社会，计算机网络也成为社会赖以 生存的基础当前，计算机网络的安全问题日益突出，信息的安全保密和防伪问题 成为人们关注的重要课题在计算机安全技术的研究中，数字签名是解决信息安全 问题的关键技术，其应用已渗透到电子商务、电子政务等众多领域 数字签名是对传统手写签名的模拟，其概念由d i 伍e 和h e l l m a n 于1 9 7 6 年最 先提出而多重签名是一种面向团体的特殊数字签名，签名过程有多人参与，主要 可分为有序签名方式和广播签名方式目前提出的多重签名方案大都采用这两种方 式之一，缺少两种方式的结合，不能满足实际应用中复杂的签名顺序 近年提出的结构化多重数字签名把有序和广播两种签名方式有效的结合起来， 使得签名顺序结构化，从而允许方案采用更为随意和复杂的顺序进行签名但已有 的结构化多重签名方案较少且都存在一些不足之处，尤其是实际应用中的安全和 效率问题因此，如何设计一个安全高效的结构化多重签名方案在实际应用中有很 大的研究价值 本文从数字签名的基础理论和实现技术出发。研究和分析了数字签名方案基 于的三种主要公钥密码体制和几个典型签名方案，并对多重签名和结构化多重签名 的研究现状进行了介绍随后，本文分析了近年提出的几类结构化多重签名方案， 着重探讨了基于e i g a m a l 体制的结构化多重签名，指出方案中存在的内部成员串 通进行欺诈抵赖的不安全情况，并给出一个改进方案。通过增加时间戳和可信赖的 签名管理中心改善了原方案的安全性，同时，把原方案的两层签名结构扩展为多层 结构，使得改进方案更具通用性，适用于各种复杂的签名结构 考虑到方案的实用性本文还对改进方案涉及的关键算法进行了深入的研究， 探讨了参数的选取规则以及各主要算法的原理和实现( 包括大随机数生成、素数判 定、生成元求解和大整数模运算) ，并分析了各算法的效率 关键词 多重数字签名；有序多重签名；广播多重签名；结构化多重签名； 签名结构 a b s t r a c t w i t h t h er 8 p i d d e v e l o p m e n t o f i n f o r n 扭t i o n t e c h n o l o g y , w e h a v e a l r e a d y s t e p p e d i n t ot h ei n f o r m a t i o ns o c i e t ya n dt h ec o m p u t e rn e t w o r kh a sb e c o m et h ef o u n d a t i o n w el i v eb y b e c a u s eo ft h em o r ea n dm o r es e v e r es e c u r i t yp r o b l e m so fc o m p u t e r n e t w o r k ，h o wt ok e e pi n f o r m a t i o ns e c r e ta n dt oa v o i df o r g e r yi sb e c o m i n gas u b j e c t t h tp e o p l ep a ym u c ha t t e n t i o nt o 。a m o n gt h ec o m p u t e rs e c u r i t yt e c h n o l o g i e s 。 d i g i t a ls i g n a t u r e ，w h i c hh a sb e e na p p l i e dt om a n yf i e l d ss u c ha se l e c t r o n i cb u s i n e s s a n de l e c t r o n i cg o v e r n m e n ta f f a i r s ，i sak e ym e t h o dt os o l v et h ei n f o r m a t i o ns s c u n t y p r o b l e m s d i g i t a ls i g n a t u r e ，f i r s tp r o p o s e db yd i m ea n dh e l l m a ni n1 9 7 6 ，i st h ea n a l o g o ft r a d i t i o n a lh a n d w r i t t e ns i g n a t u r e m u l t i - s i g n a t u r ei sas p e c i a ls i g n a t u r eo r i e n t e d t og r o u p s w h i c hi n v o l v e sm o r et h a no l l ep e r s o ni nt h e8 i g n i n gp r o c e s s t h es i g n i n g o r d e rc a nb ed i v i d e di n t ot w ok i n d s ：s e q u e n t i a la n db r o a d c a s t i n g m o s tp r o p o s e d m u l t i - s i g n a t u r es c h e m e sf o l l o wo n eo ft h ea b o v es i g n i n go r d e r sa n dl a c kt h em l x - t u r eo fb o t ht w o ，w h i c hc a n n o ts a t i s f yt h ec o m p l i c a t e ds i g n i n go r d e ri np r a c t i c a l a p p l i c a t i o n s r e c e n t l yt h es t r u c t u r e dm u l t i - s i g n a t u r eh a sb e e np r o p o s e dt oc o m b i n eb o t h s e q u e n t i a la n db r o a d c a s t i n go r d e r st o g e t h e re f f e c t i v e l y t h es i g n i n go r d e rb e c o m e s s t r u c t u r e ds ot h a ts i g n e r sc a ns i g ni nam o 蕾ef l e x i b l ea n dc o m p l i c a t e do r d e r h o w e v e r ，t h e r ea r ef e ws t r u c t u r e dm u l t i - s i g n a t u r es c h e m e sh a v i n gb e e i lr a 妇e du pa n d t h ee x i s t i n go n e sa l lh a v es o m ed e f t c i e n c y , e s p e c i a l l ys e c u r i t ya n de f f i c i e n c yi np r a c - t i c a la p p l i c a t i o n s s oh o wt od e s i g na k , a e u r ea n de f f i c i e n ts t r u c t u r e dm u l t i - s i g n a t u r e s c h e m ei so fg r e a tv a l u ei nr e s e a r c h b e g i n n i n gw i t ht h eb a s i ct h e o r ya n di m p l e m e n t i n gt e c h n o l o g yo fd i g i t a ls i g - n a t u r e ，t h et h e s i sa n a l y z e st h et h r e ep u b l i c - k e yc r y p t e s y s t e m so i lw h i c hc u g i t a j s i g n a t u r em a i n l yb a s e sa n dd i s c u s s e ss o m et y p i c a ls i g n a t u r es c h e m e s t h es t a t u s q u oo fr e s e a r c h e so nm u l t i - s i g n a t u r ea n ds t r u c t u r e dm u l t i - s i g n a t u r ei 8i n t r o d u c e d s u b s e q u e n t l y s e v e r a ls t r u c t u r e dm u l t i - s i g n a t u r es c h e m e sp r o p o s e dr e c e n t l ya r ea n - a l y z e di nt h et h e s i sa n dt h ed i s c u s s i o ni sf o c u s e do nt h ee l g a m a lb a s e ds c h e m e s t h et h e s i sp o i n t so u tt h ei n s e c u r ec a b e si nt h eo r i g i n a ls c h e m es u c ha sc o n s p i r a c y n o fi n n e rm e m b e r st oc h e a to rd e n ya n dp r e s e n t sa ni m p r o v e ds c h e m et os o l v et h e s e p r o b l e m sb ya d d i n gar e l i a b l es i g n a t u r e - c e n t e ra n dnt i m e - s t a m p b e s i d e s ，t h et w o - l e v e ls i g n i n g8 t m c t u r ei nt h eo r i g i n a ls c h e m ei se x t e n d e dt om u l t i - l e v e ls t r u c t u r es o t h a tt h ei m p r o v e ds c h e m ec a na p p l yt oa l lk i n d so fc o l 曲c a t e d 萄g n j n gs t r u c t u r e s a n db e c o m em o r eg e n e r a l i z e d c o n s i d e r i n gt h ep r a c t i d i 饥t h et h e s i sa l s od i s c u s s e sa n di m p l e m e n t st h et e n - t r a la l g o r i t h m si n v o l v e di nt h ei m p r o v e ds c h e m ei n c l u d i n gc h o o s i n gp a r a m e t e r s ， g e n e r a t i n gb i gr a n d o mn u m b e r s ，d 甙e r m i n i n gp r i m en u m b e r s ，c a l c u l a t i n gp r i m j - r i v ee l e m e n ta n dt h em o d u l eo p e r a t i o n so fb i gi n t e g e r s i na d d i t i o n ，t h ee x e c u t i n g e f f i c i e n c yo ft h ea b o v ea l g o r i f l a m si sm | a l y z a di nt h et h e s i s k e y w o r d s ：d i g i t 蛆m u l t i - s i g n a t u r e ；s e q u e n t i a lm u l t i - s i g n a t u r e ；b r o a d c a s t i n g m u l t i - s i g n a t u r e ；s t r u c t u r e dm u l t i - s i g n a t u r e ；s i g n i n gs t r u c t u r e 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得 的研究成果据我所知，除文中已经注明引用的内容外，本论文不包含 其他个人已经发表或撰写过的研究成果对本文的研究做出重要贡献的 个人和集体，均已在文中作了明确说明并表示谢意 作者签名：硅叠垒日期；竺2 ：! ：兰 学位论文授权使用声明 本人完全了解华东师范大学宥关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和 纸质版有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅有权将学位论文的内容编入有关数据库进行检索有 权将学位论文的标题和摘要汇编出版保密的学位论文在解密后适用本 规定 学位论文作者签名： 墨! 幻奄 导师签名。互皇造 日期； 丝2 ：! ：跫 第一章绪论 1 1本文的研究背景和意义 随着信息技术的迅速发展，我们已步入信息社会，计算机网络也成为社会赖以 生存的基础由于网络的广泛普及，其应用已涉及到政府、军事，文教，商业，金 融等诸多领域，如商业经济信息系统、政府机关信息系统、银行业务系统、证券业 务系统，科研数据传输等，这些系统都涉及到机密信息的传输与存储如何保证这 些机密信息不泄漏。成为网络安全研究需要解决的关键问题 网络安全的目标应当满足：身份真实性，信息机密性和完整性，服务可用性， 不可否认性、系统可控性系统易用性、可审查性等等数字签名技术是维护网络 安全的重要手段之一，它可以保证信息的完整性，鉴别发送者身份的真实性和不可 否认性另外，数字签名本身的基础技术如加密技术，可以保证信息的完整性作 为网络安全领域的研究热点，数字签名在电子商务、电子银行、电子政务等领域有 极其广阔的应用前景 1 1 1信息安全的重要性 所谓信息安全，是指信息的四大要素i l l ，即信息的保密性( c o n f i d e n t i a l i t y ) 、 真实性( a u t h e n t i c i t y ) 可用性( a v a i l a b i l i t y ) 和可控性( c o n t r o l l a b i l i t y ) 保密性 反映了信息与信息系统不可被非授权者所利用；真实性反映了信息与信息系统的行 为不被伪造，篡改、冒充；可用性反映了信息与信息系统可被授权者所正常使用； 可控性反映了信息的流动与信息系统可被控制者所监控 网络安全从本质上来说就是网络上的信息安全，是对信息的保密性、真实性和 可用性的保护；网络信息安全与我国的经济安全，社会安全和国家安全紧密相连， 涉及到个人利益，企业生存金融风险防范社会稳定和国家机密等诸多方面，是 信息化建设进程中具有重大战略意义的问题 目前，由于计算机阿络技术的迅速发展，电子商务，电子政务等应用巳完全渗 透到我们的日常生活之中，影响我们的工作方式、生活方式，管理方式和思想观念， 对生产力的发展也起到了极大的推动作用然而，在网络带给我们巨大经济利益和 便利的同时。网络安全现袄却令人担优，从技术到管理都处于落后、被动的局面， 充斥着安全隐患与危险 计算机网络技术的广泛应用，要求计算机系统具有开放性但计算机网络体系 结构的开放性暴露了许多脆弱，易被攻击的薄弱环节，计算机系统资源的高度共享 性也导致了许多人为故意的未授权窃取篡改、破坏及其敌对性活动。如之近年来 计算机病毒发作猖撅，使得计算机网络的不安全性显得越来越突出 由网络攻击导致的机密信息泄露，轻则引发企业、部门工作陷于瘫痪而造成巨 大的经济损失，重则危及国家，军事安全和社会稳定，因此信息的安全保密和防伪 问题成为人们关注的一个重要课题由于信息资源已经成为代表综合国力的战略资 源，而网络也已渗透到人们日常生活的各个方面，信息安全作为保证国民经济信息 化建设健康有序发展的基础，直接关系到国家的安全，影响重大 1 1 2数字签名在信息安全中的重要作用 数字签名是对传统手写签名的模拟，在实现身份认证、数据完整性、不可抵赖 性等方面都有重要应用，是有效保护计算机信息安全的核心技术之一利用这种技 术，签名的接收者可以确定签名发送者的身份是否真实。同时，发送者不能否认发 送的消息，接收者也不能篡改接收到的消息在现实生活中，数字签名己在越来越 多的产品及协议中得到应用，尤其在电子邮件，电子银行，电子商务和电子政务等 许多领域有重要应用价值，是当前信息化建设中的关键安全机制之一 作为保障网络信息安全的重要手段，数字签名主要有以下特性闭： 1 ) 防伪造其他人不能冒充签名者对消息进行签名，接收方能鉴别发送方所 宣称的身份i 2 ) 防篡改对消息进行签名后，消怠的内容不能更改； 3 ) 防抵赣签名者事后不能声称他没有签过名； 除了具备以上特性，数字签名与传统的手写签名相比也更具优越性，比如签名 因消息而异，即同一个人对不同的消息签名，其结果是不同的i 对消息的修改必然 会导致签名结果的改变，消息与其签名两者不可分割等但是在数字签名中，有效 签名的复制同样是有效的签名，而在传统的手写签名中，签名的复制是无效的因 此，在数字签名的方案设计中要预防签名的非法重放，可以通过在签名报文中添加 流水号、时间戳等技术来抵抗重放攻击 2 在数字签名酶应用中许多应甩环境对其提出了多种特殊的要求显然，普通 数字签名方案难以提供较好的解决方法，因此各种特殊的数字签名方案相继被提 出，形成了数字签名研究中的多个值得关注的方向多重签名就是一种由多人对同 一消息分别进行签名的特殊数字签名，在电子商务，电子政务等领域有着广泛的应 用已有许多学者对多重签名技术进行了研究，提出了有序多重签名、广播多重签 名、结构化多重签名等各种多重签名方案 数字签名技术的研究与使用，拓宽了密码学的研究范围和领域，在网络通信身 份认证中占有独特的地位随着信息时代的到来，网络应用中涉及到伪造、抵赖、 冒充、篡改和身份鉴别的问题，都可以用数字签名技术来解决。作为一种重要有效 的信息安全技术，数字签名技术的应用面将越来越广，需要数字签名技术支撵的应 用系统也将越来越多，数字签名将成为网络信息安全体系的基础与支柱 1 1 3结构化多重数字签名方案的研究意义 多重签名矧“【l 针是面向团体使用的签名技术，即份文件需要多人进行签署， 这在实际应用中极为常见早先的多重签名方案大都假设签名者之间的签名次序是 一种线性( 串行) 的顺序，即有序多重签名，之后出现的广播多重签名方案，采用的 则是一种并行的签名结构目前提出的多重签名方案大都采用这两种方式之一，缺 少两种方式的混合，而实际应用中的签名结构往往结合了有序和广播两种方式图 1 1 给出了串行，并行和串并行混合的三种签名结构， 考警芬嚣誓争 砷厅 一毒 ：塞毒彳 ：鲁毫一0 ：| 谐a 肆l a 图1 1 ：多个签名者问的三种签名结构 在多重签名技术的研究中，近几年才开始提出更一般化的签名者间签名顺序 的问题结构化多重签名 1 6 1 一1 2 0 ) 就是一种可以事先设置复杂签名次序的多重签名 技术它包含了有序多重签名和广播多重签名，能够让签名者之间的签名顺序更为 3 随意由于在现实应用中。不同的签名者往往具有不同的权限和职责，每个签名者 在签名结构中的不同位置( 即每个签名者应该在谁之后才能签名，又必须在谁之前 完成签名) 都会影响签名的有效性因此，签名者间签名顺序的构建至关重要，一 个有效的结构化签名必须严格遵守事先约定的签名结构 b u r r o w e r 等人于2 0 0 0 年提出个e 1 g 锄a 1 型结构化多重签名方案i 堋，但 有研究指出此方案的密钥生成过程存在安全隐患，易为不良成员利用进行欺诈之 后，又有几种结构化多重签名算法被提出，但均存在不足之处，尤其是实际应用中 的安全和效率问题。另一方面，随着时闻的推移和技术的进步，人f 门对数字签名本 身的安全要求不断提高，一些原本被认为是安全的方案和技术也会逐步暴露出其 安全性缺陷因此，如何设计一个安全高效的结构化多重数字签名方案在实际应用 中有很大的研究价值 1 2国内外研究现状 数字签名的概念是1 9 7 6 年由d 瓶e 与h e l l m a n 在他们的开创性论文n e w d i r e 蹦。衄i nc r y p t o f a p h y 弘上1 中首先提出的之后。不同的数字签名方案先后 被提出t1 9 7 8 年v e s t s h a m i r 与a m e m a n 提出了第个实用的基于大整数 分解难题的r s a 公钥加密方案i z 蠲，并由此得到了著名的r s a 签名方案；第个 基于离散对数难题的签名方案是e l g a m a l 在1 9 8 5 年提出的e 1 g a r e a l 方案【z 叫，后 来，美国国家标准与技术研究所( n i s t ) 对该方案进行了改进，并于1 9 9 4 年将其作 为数字签名标准( d s s ) ；1 9 8 5 年，k o b l i t z 和m i n e r 分别提出将椭圆曲线用 于公钥密码体制，1 9 9 2 年v a n s t o n e 首先提出椭圆曲线数字签名算法e c d s a ， 1 9 9 8 年b c d s a 成为i s o 标准 数字签名技术发展到今天。其理论研究和应用开发都得到长足的发展在基础 理论研究方面，许多特殊的数字签名概念被提出，各式各样的数字签名新算法也是 层出不穷，多重签名就是一种特殊的数字签名1 9 8 3 年。i t a k u r a l v j 首次提出多重 数字签名的概念，之后，各种不同的多重数字签名方案被相继提出，其中较流行的 是广播多重数字签名和有序多重数字签名 在基础理论研究的同时，数字签名技术的应用研究也引起了学术界尤其是密码 学界和计算机网络界的广泛重视特别是随着电子通信和计算网络的应用，作为信 4 患安全技术之一的数字签名技术，越来越显出其优越性数字签名的应用开发进入 了新阶段，与数字签名相关的标准和应用系统也日趋完善目前己有很多组织定义 了关于数字签名的标准，如r s ad a t as e c u r i t y 公司的公钥加密标准( p k c s ：p u b l i c k e yc r y p t o g r a p h ys t a n d a r d ) 和美国国家标准与技术研究所( n i s t ) 制定的数字签 名标准( d s s ：d i 出a ls i g n a t u r es t a n d a r d ) ，这些标准清楚地定义了签名和验证的步 骤以及生成的数字签名格式。它们的建立大大促进了数字签名技术的推广与发展 我国研究信息安全基础理论和应用系统的两个重要实验室一一中国科学院软件研 究所信息安全国家重点实验室和中国科学院研究生院信息安全国家重点实验室也 有高水平的研究队伍在从事数字签名技术的研究 然而，随着数字签名技术的发展和应用的普及，对已有签名方案的攻击在不断 升级，密码学中各种算法的安全性正面临着严竣的考验已有研究人员指出著名的 数字签名算法d s a 的随机数生成技术存在重大缺陷因为密钥的有效性依赖于数 字产生的随机度，但d s a 的随机数产生方法上存在偏重某些数字的现象另外， 包括m d 4 ，m d 5 ，n a v a l - 1 2 8 ，r i p e m d 以及s h a - 0 在内的几种搭配数字签名使 用的h a s h 算法也宣告被破解即使是目前认为安全的方案和技术，随着安全要求 的不断提高，其安全性也可能不复存在 另一方面，虽然数字签名的理论研究于很多年前就已经兴起，数字签名的应用 领域也在不断扩大，但对近年才提出的结构化多重数字签名方案，理论研究还楣当 缺乏b u r m e s t e r 等人于2 0 0 0 年提出个e 1 g 8 m a l 型结构化多重签名方案【捌，之 后。h a m 等人又提出了两种结构化多重签名算法【上0 1 ，分别基于r s a 和e 1 g a m a l 体制，l i n 等也提出了一种基于g a pd i f f i e - h e l l m a n ( g d h ) 群的结构化多重签名 方案【1 7 j ，但上述方案在实际应用中还存在一些安全和效率上的缺陷因此，结构 化多重数字签名鹋理论研究与应用仍有很多筒题需要饵决 1 3本文的工作与组织结构 本文的工作主要有以下几方面， 1 ) 介绍了数字签名方案基于的三种主要公钥密码体制和几个典型签名方案 2 ) 分析了多重签名和结构化多重签名的研究现状和最新研究进展； 3 ) 深入研究和分析了基于e i g a m a l 体制的结构化多重签名方案； 5 4 ) 提出了一个改进方案，对原方案进行了扩展并改善了原方案的安全性； 5 ) 探讨了签名方案所涉及的关键算法，包括随机数的生成、素数的判定，生成 元的求解和大整数的模运算等； 6 ) 实现上述关键算法，并进行效率分析 本文组织结构如下t 本章为绪论，主要介绍论文的研究背景，国内外的研究现 状和论文的主要工作以及组织结构；第二章简要介绍了相关的数学基础知识，包括 致论和抽象代数理论；第三章介绍了数字签名的基本概念和几种典型的数字签名方 案，总结了数字签名方案的几种主要体制；第四章介绍多重数字签名技术和几类结 构化多重数字签名方案，通过对e 1 c a m a l 型结构化多重数字签名方案的安全性分 析，提出了个改进方案对原方案进行扩展和安全性改善；第五章探讨了前一章改 进方案所涉及的关键算法，给出算法的实现方法和效率分析；第六章对全文进行总 结，并对未来的研究方向进行展望 6 第二章数学基础理论 近代密码学建立在坚实的数学基础之上，而数字签名作为密码学研究的一个 重要领域，也涉及到大量的数学理论，如数论、抽象代数等知识本章将简要介绍 效论和抽象代数中与数字签名相关的一些基本概念和定理，作为后面章节叙述和论 证的理论基础 2 1数论基础 数论是个相当古老的数学分支，曾度被认为是无实际用途的纯数学学科 如今，数论已成为大多数公钥密码算法的数学基础，被广泛应用于信息安全技术的 加密解密问题上本节将对素数与模运算的基本概念和相关定理1 2 7 】作简单的介 绍 2 1 1素数和唯一分解定理 素数及其相关问题是数论的主要研究内容，在密码学领域起着非常重要的作 用 ( ) 素数的定义 个大于1 的整数，若除了1 和它本身，不能被其他任何整数整除，就称为素 数( 质数) ，否则就称为合数 如果有两个整数4 b ，且。和b 的最大公因数g c d ( a ，b ) = 1 ，则称口和b 互 素 ( 二) 唯分解定理 若不计素因子的次序，任何大于1 的整数仅能用唯一的方法分解成素数的连 乘积，即对任一整数口 1 有 o = a 庇m ，n 翔 其中a ，m ，是素数若 d = 口1 9 2 ，口l 9 2 - 7 其中吼，鼋2 ，是素数，则m = ，l ，g = a ，8 = 1 ，2 ，3 ，哟 2 1 2模运算 密码学中用到了许多模运算，因为模运算可将所有中间结果和最后结果限制在 某个范围内，所以用它进行计算较容易。不会产生巨大的计算结果 ( ) 模运算和同余 如果口是个整数，仃是个正整数，定义口r o o d n 为。除以扎的余数，称运 算符r o o d 的运算为模运算对任意整数o ，可以表示为a = 【口叫n + ( or o o d 哟 如果n 和b 满足e - b = k n ，k 为整数，财称。和b 模n 同余，记为d = b r o o d m 模运算和普通四则运算一样，具有交换律、结合律和分配律，而且，对每个中间 结果都进行模运算，其结果与先进行全部运算，最后进行模运算的结果是一样的 ( 二) 模的乘法逆元和二次剩余 如果d 和。满足凹= 1 m o d n ，则称为口的模礼乘法逆元，记作n 一1 r o o d 亿 一般而论。如果口和n 是互素的，那么存在一个唯一的。模? ；乘法逆元；如果a 和n 不是互素的，那么。的模n 乘法逆元不存在 如果素数p ，有整数口 p ，对护= n r o o d p 有解，那么称a 为模p 的二次剩 余；若没有解，称口为模p 的二次非剩余 2 1 3e u l e r 定理与f o r m a t 定理 e u l e r 定理和f o r m a t 定理在公钥密码体制中有着重要的作用 ( 一) e u l e r 函数和e u l e r 定理 e u l e r 函数，表示小于礼且与n 互索的正整数的个数，记作( n ) 当p 为索 数时，有p ) = p 一1 若p 和q 为互素的两个整数，则有毋( 粥) = 庐p ) 庐( 口) = ( p 一1 ) q 一1 ) e u l e r 定理若p 和口是互素的两个整数，则有a t ( p ) = 1 r o o d p ( _ - - ) f o r m a t 定理 f o r m a t 定理，如果正整数。，p 互素。且p 是素数，则有矿- 1 = 1 r o o d p ，也 8 可表示为口p = 口r o o d p 2 2抽象代数基础 抽象代数不但是数学的一个重要分支，同时在其他学科如量子力学、原子物理 等中都已经成为研究者的有力武器在密码学中，抽象代数也巳扮演重要角色，如 在e i g a m a l 体制和椭圆曲线密码体制中，群和域的相关理论【2 8 j 都是其理论基础 2 2 1有限域和生成元 群是有个二元运算的系统，域上则定义了两个二元运算由于在域中对加减 乘除运算都封闭，因而许多与四则运算有关的问题都涉及域的性质 ( - ) 群的基本概念 设g 为个非空集合，在g 内定义了一种代数运算，若满足下面的条件， ( 1 ) 封闭性对任意口，b g ，有n 6 g ； ( 2 ) 结合律对任意o b ，c g ，有( 口b ) c ；口( 6 c ) ； ( 3 ) 有单位元e 对任意口g ，有e g ，使o e = e 口；口； ( 4 ) 存在逆元对任意o g 有口一1 g ，使口口一1 = 口，1 o = e ，口、a 互 为逆元； 则称g 构成个群在上面的定义中，g 的运算。可以是通常的加法或乘法 群g 中元素的个数称为群的阶，记为lg1 如果群的阶为有限值，称为有限 群，否则为无限群 若群g 中，对任意口，b e 有o b = b 口，则称为a b e l 群( 交换群) 若群g 的非空子集日对于g 中定义的代数运算也构成群，则称日为g 的 子群，记为日g ( 二) 有限域与生成元 非空集合f ，若f 上定义了加法和乘法两种运算，且满足下面条件- ( 1 ) f 关于加法构成a b e l 群，该加法群单位元写为o ； 9 ( 2 ) f 中除去元素o 外，对乘法构成a b e l 群，该乘法群的单位元写为l ； ( 3 ) 加法和乘法间有分配律z n p + c ) = 曲+ ( b + c ) n = b a + 则称f 为域若域中元素的个数是有限的，财称为有限域，一般用g f ( q ) 或e 表 示，口表示其元素的个数( 阶) 若存在个元素g 群g ，对比g 都存在个整数 0 ，使得。= 矿，则 群g 称为循环群，元素g 称为g 的个生成元 2 2 2离散对数问毯 密码学上所说的离散对数问题是个计算困难问题，e 1 g a m a l 数字签名方案 就是建立在这难解问题基础上的 设p 是一个素数，g 是有限域g f ( 力的生成元，g f ( p ) 的元素可以表示为 如下形式； 可= 矿r o o d p 其中0 盘p t ，根据上式可知霉也可以表示为有限域g f ( p ) 上以g 为底的对 数 z = l o g g y , n o d p 其中0 y p 一1 在巳知寥的条件- f $ 鲈是容易的。但在已知y 的条件下，求在有限域g f ) 上的整数解z 是极其困难的在密码学申认为该算法在实现上是不可能的，因为 在资源有限的情况下，当你花费极长时间求解出该变量时，该变量已经失去了保密 意义e 1 g a m a l 算法的安全性就依赖于有限域上离散对数的困难性上 2 2 3l a g r a n g e 定理及其推论 l a g r a n g e 定理，如果g 为有限群，则g 的子群的阶必为g 的阶的因子即 设g 是有限群，而s 是g 的子群，若i g f = n ，i s i = m ，则m ln ( m 整除n ) ， 1 0 定义元紊的阶为t 著j 已= m j n o l = 1 r o o d 力， z ，则记j 乙为元素口的 阶有以下推论；设g 为模p 乘法群，对比g ，元素口的阶玩是j g i = n 的 因子，即凰l n 证明，令s = 扣r o o dp 口2 r o o dp 一r o o dp ，水r o o d 尸，则s 是一个以 。为生成元的模p 乘法群，且为循环群由于g 是群，根据群的封闭性有s 是g 的子群，ls f = 玩根据l a g r a n g e 定理，lsl 是igl 的因子，所以以是ig 的因子 小结 在本章中，我们对本论文所依据的数学基础理论作了简单的介绍，包括数论基 础( 素数、模运算和e u l e r 定理f o r m a t 定理) 和抽象代数基础( 有限域、离散对 数难题和l a g r a n g e 定理) ，便于后面章节的理解和论证 第三章数字签名方案 在数字签名技术出现之前，曾经出现过一种。数字化签名技术，简单的说就 是在手写板上签名，然后将签字的图像传输到电子文档中这种“数字化签名”可以 被剪切。粘贴到任意文档上。非法复制非常容易，所以这种签名方式是不安全的 数字签名与数字化签名是截然不同的两种技术数字签名与用户的姓名和手写签 名形式毫无关系，它使用了信息发送者的私有密钥来变换需传输的信息对于不同 的文档信息，发送者的数字签名是不相同的没有私有密钥，任何人都不能非法复 制签名从这个意义上来说，数字签名是通过一个单向函数对要传送的报文进行处 理得到的，用以认证报文来源并核实报文是否发生变化的字母数字串 数字签名过程一般对数据摘要信息进行处理所谓数据摘要就是散列函数对 消息处理产生的散列值，也称为消息的散列值数据摘要在数字签名中的应用过 程可以概述为首先使用某种散列算法，对要发送的数据进行处理，生成数据摘要 信息；然后采甩公钥密码机制，用私钥加密数据摘要信息加密后的数据摘要信息 就相当于用户的签名，类似于现实生活中的签名和印章接收方可以对接收到的 签名结果进行验证，以判断签名的有效性数字签名体制一般包括两部分，一是 发送方的签名部分，对消息m 签名，可记作s = 8 i g k ( m ) ，签名算法使用的密钥 是秘密的，即签名者的私钥；二是接收方的验证部分。对签名s 的验证可记作 口鲫，8 ) ； t r u e ，f a l s e ，验证算法使用的密钥是公开的，即签名者的公钥 3 1公钥密码体制 密码体制又称为密码系统，可用图3 1 表示根据加密密钥与解密密钥的异 同，可分为单钥密码体制和公钥密码体翻1 2 9 】 单钥密码体制又称为对称密码体制，其加密和解密使用的密钥是相同的，属于 传统密码，具有加密速度快，密钥容易生成等特点但它存在的一个严重缺陷是在 任何密文传输之前，发送者和接收者必须使用一个安全信遭预先传送密钥，而在实 际应用中很难做到这一点 与单钥密码体制不同，公钥密码体制是一种加密密钥与解密密钥不同的密码 体制，又称为非对称密码体制其加密密钥公开，称为公钥；而解密密钥保密，称 墓锡喜嚣荐器；2 ；器 圈3 1 ：密码体制 为私钥由于加密密钥和解密密钥的分离，公钥密码体制解决了利用传统密码体制 进行密钥分发时遇到的问题，私钥无衙传输给任何人，增加了安全性，便于密钥的 分配和管理但在实际应用中，公钥密码体制并没有完全取代单钥密码体制，因为 公锈俸静l 都基于莱一类数学难题，计算非常复杂，速度远比不上单锈俸翩i 表3 1 对单钥密码与公钥密码进行了比较 单钥密码公钥密码 加密和解密使用相同的密钥和算法加密和解密使用相同的算法， 其中公钥用于加密，私钥用于解密 运行条件发送方和接收方必须共享发送方和接收方使用相同的算法； 相同的密钥和算法加密用途时，发送方拥有公钥， 接收方拥有私钥 密钥必须保密两个密钥中只要私钥保密即可 如果不掌握其他信息，要想解密消息如果不掌握其他信息，要想解密消息 安全条件是不可能的，至少是不现实的是不可能的，至少是不现实的 知道所有的算法加上密文的样本，知道所有的算法加上密文的样本和公 还是不可能确定密钥钥，还是不可能确定私钥 衰3 1 ：单钥密码与公钥密码的比较 公钥密码学是现代密码学的一个重要分支，也是数字签名的基础，现有的数字 签名方案大都建立在某个公钥密码体制之上公钥密码【烈】的概念是由d i f f i e 和 h e l l m a n 予1 9 7 6 年提出的，是密码学历史上的一个重大成就构建公钥密码系统 需要设计个单向陷门函数，除非知道某种附加的信息，否则此函数在个方向上 容易计算，而在另外的方向上的计算是不可行的1 9 7 8 年由r i v e s t ，$ h a m i r 和 a d l e m a n 寻找到个基于因子分解难题的单向陷门函数，设计出著名的r s a 公钥 密码系统瞄。1 9 8 5 年，e i g a m a l 找到了基于离散对数问题的单向陷门函数并提 出了相应的e l g a m a i 体翻密码系统 2 3 1 这些公钥密码系统都已成为公钥密码学的 重要基石 公钥密码算法与以前的密码算法有很大区别，一，以前的密码算法都基于代换 与置换操作，而公钥密码使用数字函致进行变换；二、公钥密码体制使用非对称方 式，有两个密钥分别进行加密和解密，而传统密码算法仅使用一个密钥因此，公 钥密码算法具有以下特征 1 ) 加密密钥和解密密钥本质上是不同的，也就是说如果仅知道加密算法和加 密密饲，而要确定解密密钥，在计算上是不可行的； 2 ) 某些公钥密码算法的加密密钥和解密密钥具有互换的性质。如r s a 算法， 若密钥对中的个用于加密，另一个就用于解密 从数学上来讲，公镊密码体翩是一组变换对 霹，d t ) ，l f ，满足条件i z l ： 1 最是明文空问x 到密文空间y 的一一映射，鼠是置的逆映射，t ，； 2 对慨x ，y ，计算最( o ) 和d t ( 口) 都是容易的； 3 由置出发去寻我等价于取的变换在计算上是不可行的； 4 对任何i ，生成变换对最和皿是多项式时间或概率多项式时间的 当该公钥密码体制不用于数字签名时，条件1 可以减弱为， 墨是x 到y 的映射，n 是y 到x 的映射 且对v z x ，n ( 最p ) ) = z ， 在公钥密码体制中，任何一个用户i 都有自己的加密变换置和解密变换取， 并且置对其他用户公开，而d 则对其他用户保密，在实际公钥密码系统中，公 开的就是公钥。而保密的是私钥 公钥密码算法建立在一定的数学难题上，主要有以下三类：大整数素因子分解 难题，有限域上的离散对数难题和椭圆曲线离散对数难题另外还有一些基于其他 数学难题的公钥密码算法，如纠错码理论等，但是不太普及 3 1 1r s a 密码体翩 r s a 密码体制1 2 2 】是公钥密码体制中最负盛名的密码体制，它是以发明人 r j v e 8 t ，s h a m i r 和a d i e m a n 姓名的首字母来命名的，此密码体制既可用于加密解 1 4 密，也可用于数字签名。而且思想简单、易于理解和程序实现，是日前最为广泛采 用的一种密码体制r s a 密码体制描述如下 选取密钥 1 选取两个大素数p ，俄 2 计算n ；p q ，( n ) = 0 一1 ) 妇一1 ) ； 3 随机选取e ，满足1 e 妒唧) 且g e d ( e ，妒 ) ) = 1 ； 4 计算e 模的乘法逆元d ，以= 1 r o o d 伽) 5 销毁p ，口( n ) ，公钥为( e ，帕，私钥为d 加密t 消息m ( n ) ，计算密文c ；m 。r o o d 扎 解密t 密文c ，解密密文得m = 一r o o d 竹 分析密钥选取过程可知，如果能从住正确分解出p 和蟊则不难计算出咖) ， 进一步依据e 和妒( n ) 可解出d 所以如果能有有效的算法对大数进行