（计算机应用技术专业论文）数字签名及其在电子选举中的应用研究.pdf

数字签名及其在电子选举中的应用研究 摘要 网络安全是关系到国家利益、集体利益和用户切身利益的大事，是只能依 靠我国自身力量发展的技术。其中数字签名技术能够确认参与者的身份，防止 恶意的伪造、窜改，在网络通信安全方面起到重要的保护作用，数字签名在实 现诸如电子选举、电子现金等方面有着广泛的使用背景，一直以来倍受关注。 本文的主要研究工作包括： ( 1 ) 介绍了数字签名的基本特性、分类、两类密码体制的数字签名和公钥密 码体制的基本概念。 ( 2 ) 叙述了h a s h 函数和时间戳的基本概念，讨论了h a s h 函数的安全性，h a s h 算法的结构，迭代h a s h 函数的构造方法，单向迭代函数的选择，h a s h 函数的设 计思想。 ( 3 ) 特殊签名技术是电子选举应用的关键技术之一，综合介绍了群签名、盲 签名、收方不可否认的数字签名、代理签名和多重签名等几种有代表性的特殊 签名技术及其发展现状，指出了它们在电子选举中的应用情况。 ( 4 ) 本文介绍了电子选举的国内外研究现状，并分析了一些典型方案，讨 论了其优缺点。并叙述了目前常用的基于盲签名方案的电子选举协议，指出了 其中的不足，并设计了一个新的电子选举协议。此协议是基于e l g a 腿l 签名方 案，重点解决了一般电子选举协议中的可信中心伪造选票和要花费大量时间用 于盲签名的缺陷。该协议不仅满足一个理想的电子选举具有的特征，而且增加 了安全性和灵活性，具有一定的实用价值。最后，在v b6 0 环境下给出了此方 案在计算机上的模拟实现。 关键词：公钥密码体制，数字签名，电子选举，盲签名，群签名 r e s e a r c ho nt h ed i g i t a ls i g n a t u r ea n di t sa p p l i c a t i o ni n e l e c t r o n i cv o 咖g a b s t r a c t 1 ks e c l l r i t yo f n c t w o r ki n f b 砷硝o ni sc l o s e i yr c i a 吲t 0 也ei m m e d i a t ei n t e r s t s o fo u rc o u n t 吼s o c i e 哆a n ds u b s c r i b e r s ，埘c h0 1 1 l yc a i lb ed c v e l o p e db yt e c h n o l o g y p o w e ro fo u ro w n a m o n gt 1 1 e s e ，s i 印a t i l r et e c l h l o l o g y s l l r e sp 枷c i p a t o r s i d e n t i f i c 撕0 na g a j l l s tm a l i c i o u sb u g g i n ga n dd i s t 硎n g ，a n dp l a y sa i li m p o r t a l l tr o l e i np r o t e c t i n gt l l es e c u r i t yo fn e t w o r k i n gc o m m u n i c a t i o n d i g i t a ls i 朗a t i l r ei sav e r ) r i m p o r t a n tm e 廿l o di ne k 咖i l i cv o t i n 舀e k c 臼o i cc 嬲h i tl l a sb e e nt a ：k e ni m om u c h a c c o u n td u et oi t sw i d eu s a g e i nl 量l i sp a p e ro u rw o r ka i m i n gt os l l c hac h a l l e n g ei s 孙f o i l o w s ： ( 1 ) i n t m d l j c t i o nt ot h ec k l r a c t e r i s t i c sa n dc l 硒s f i c a t i o no fd i g i t a ls i g n a t u r e ， d i g i t a ls i 印a n 船s c h e i n e sb a s e do nap r i v a t e k e ys ) r s t e mo rp u b l i c k c ys y s t e m ，a 1 1 d m ec o r cc o n c c p t so f p u b l i c - k e ys y s t e m ( 2 ) d i s c u s s i o no ft h cs e c l l r i t ya 1 1 ds 廿1 l c t u r eo fh 嬲h c t i o n i 忸c o n s 恤l c t i o n m e m o d ，c h o i c eo fo n e w a ym n c d o na n dd e s i g nt l l e o r yi sa l s oi n v o l v e d d i s c 哪s i o n o f d i g i t a lt i m e s t a m p i n gs e n r i c e ( 3 ) s p e c i a ls i 掣删c i l r e sa r ck c yt c c l n o l o g i e so fe l e c 仃o n i cv o t i n g ，s o m et y p i c a l s p e c i a ls i g n a n 鹏s ，s u c ha sg m u ps i g n 船，b 1 i n ds i 印抓l r e ，d i 百t a ls i g n a n 鹏so f r e c e i v c rb e i n gu n d e l l i a b l e ，p r o x ys i g n a n l r e ，强dm u l t i s i 印a n l r e 缸dm e i r 印p l i c a t i o n s i ne l e c 打o n i cv o t i n ga r ei n 仃0 d u c e di nt l l i sp a p e l ( 4 ) i nt h i sa n i c l e ，t l l em a i nr e q u i r e m e n t s 锄dd e v e l o p m e mo f e l e c 舡d n i cv o 血g s c h e m e sa r ei n t r o d u c e d ，s e v e r a lt y p i c a ls c h e m e sa r ea n a l y z e d ，t h e i ra d v 锄t a g e s 锄d d r a w b a c k sa r cd i s c u s d w bd e s c r i b es o m ed e c 订o i l i cv o t i n gs c h e m e sb 4 s e do n b l i n ds i 弘a t l j r ea 1 1 dp o i n to u tt l l e i rs h o r t a g e s ，卸d p r 叩o am w e l e c n d n i cv o t i i l g s c h e m e t h i sp r c 庀0 c o li sb a s e do nt h ee l g 锄a ls i 印确t 埘七p 喇e c t ，i ts o i v e dt h ed e 】融 t h a tt h ea u m e n t i cc e n t e rf o r g eb a l l o ta 1 1 db e e nc o s tm u c ht i l n et o b l i l l ds i g n a t l 】i e t l l i s p r o t o c o lh 勰a l lp r o p e n i e so f a ni d e a lp r o t o c o l 舳da l s 0e 1 1 l l a n c e sm es e c 嘣够a n d n e x i b i l “yi th 船p m c t i c a l 晦l a s tw eh a v e a l i z e di tb 船e do n 6 0i nr n o d e l k e y w o r d s ：p u b l i c - k e yc r y p t o s y s t e m ，d i g i t a ls i g n a n ，e l e c 的1 1 i cv o t i n g ，b l i d s i g n m 雠，g r o u ps i 印a m r e 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学 硕士学位论文质量要求。 答辩委员会签名：( 工作单位、职称) 主席够煽，中g 印伏 委员： 导师： 名够亿 硝 图2 1 图2 2 图3 ，l 图3 2 图3 3 图3 4 图4 1 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图形 清单 数字签名模型6 同时达到秘密通信与数字签名8 使用h a s h 函数的数字签名方案1 5 盲签名过程1 7 有序多重数字签名方案2 5 广播多重数字签名方案2 5 电子选举系统模块结构3 0 电子投票方案框图3 9 系统参数4 3 各选举者的个人密钥4 4 各选举者的签名密钥4 4 各选举者对选票的签名4 5 选举者对签名选票加密4 5 计票中心验证统计选票结果4 6 表格清单 表2 1e l g a m a l 型安全数字签名方案分类1 0 表4 1合法选票列表3 2 表4 2 选票结果3 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得金目b 王些太堂或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签字：辫签字日期：孵r 月柏 学位论文版权使用授权书 本学位论文作者完全了解金月8 王些盍堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金 目b 王些盘堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：缸浑 签字日期：k 年厅少日 名：1 ) ：l 签字日期啊车厂且加 电话：移一伊f 吁 邮编：。雄i 致谢 衷心感谢我的导师候整风教授。我非常荣幸能够成为候老师的学生，我也 非常庆幸在我的学习生涯中能够有机会涉足这个古老、深奥而又充满魅力的神 奇的密码学世界。 本论文是在导师候整风教授的悉心指导下完成的。几年来，候老师在学术 上精益求精的态度、严谨踏实的作风，兢兢业业的精神，给我留下了深刻的印 象。候老师不仅在学业上给我指导和帮助，而且在生活上给我关怀，教给我许 多做人的道理，让我受益终生，在此谨向恩师表示深深地谢意。 感谢计算机学院的胡学钢副院长、王浩副院长以及所有为我们授课的老师， 还要感谢合肥工业大学研究生部的老师们所付出的辛勤工作。 读研期间，我的家人和我的朋友们在学习、生活上给我很多支持，是他们 给了我面对困难和战胜困难的勇气。我前进中的每一步都凝聚着他们无私的爱， 我只能以我加倍的努力来回报他们对我的期望。 感谢我的儿子，是他带给我欢乐，带给我前进的目标! 最后要感谢的是各位评审委员，你们在百忙中抽出时间，评阅我的论文， 并提出了有益的建议。 再次真诚感谢所有给予我关心和帮助我的人们! 作者：蔡庆华 2 0 0 5 年5 月日 1 1 概述 第一章绪论 随着计算机应用的普及和各行业办公自动化、电子化的发展，计算机网络 广泛应用于科研、教育、管理、生产、金融、商业和军事等各个领域，成为信 息社会中重要的基础设施之一。网络提供的快捷信息交流手段和丰富的信息资 源推动各行各业的发展，给人们生产和生活带来极大的方便。尤其近几年来， 全球范围的i n t e r n e t 以惊人的速度增长，公司、企业范围内的i n t r a n e t 也大 幅度迅猛发展，使得网上信息流量和存储量都迅速增长。上网人数的增多和办 公自动化的普及，使得通过网络进行业务处理、信息获得、广告宣传及产品销 售不仅成为可能而且越来越流行。 在i n t e r n e t 迅猛发展的同时，计算机网络的使用也存在巨大的安全隐患。 信息的分布性和流动性特点使其容易遭受攻击和泄漏。计算机网络是计算技术 和通信技术紧密结合的产物，在网络系统中，硬件设备决定了网络的组成和结 构；软件系统决定了网络的功能特性；通信媒体决定了信息传输的方式和质量。 网络系统较单独的计算机硬件设备复杂，异种机间软件多样，任何环节的故障 和泄漏都可能成为攻击的可乘之处。网上的非法用户利用这些弱点窃取在网上 存储和传递的重要信息，或对网上传输的信息予以篡改、伪造、抵赖，严重干 扰了人们对于网络的正常使用；对国防、科研和经济决策机构等国家要害部门 的攻击，从而对国家安全、经济发展和社会安定造成极大的威胁。 随着网络技术的发展，网络安全已经成为当今网络社会的焦点中的焦点， 几乎没有人不在谈论网络上的安全问题，病毒、黑客程序、邮件炸弹、远程侦 听等这一切都无不让人胆战心惊。病毒、黑客的猖撅使身处今日网络社会的人 们感觉到谈网色变，无所适从。 但我们必需清楚地认识到，这一切一切的安全问题，我们不可能一下找到 全部解决方案，况且有的是根本无法找到彻底的解决方案，如病毒程序，因为 任何反病毒程序都只能在新病毒发现之后才能开发出来，目前还没有哪一家反 病毒软件开发商敢承诺他们的软件能查杀所有己知的和未知的病毒，所以我们 不能有“等网络安全了再上网”的念头，因为或许网络不能有这么一日，就象 “矛”与“盾”，网络与病毒、黑客永远是一对共存体。 从诸多事实可以看出，对网络安全和信息安全的研究已经是一个刻不容缓 并且需要先行的重要课题，否则将严重制约网络的进一步发展和广泛应用。针 对当前计算机网络的安全隐患和屡受不法分子攻击的现状，计算机界己经发展 了许多与网络安全相关的技术。例如使用数据加密、存取控制等技术可以对数 据通信时的保密性和完整性予以保证。然而仅仅有这些还是不够的，特别是近 年来，随着电子商务的发展，人们通过通信网络进行迅速的、远距离的贸易， 使得数字或电子签名应运而生并开始用于商业通信系统，诸如在电子选举、电 子邮递、电子转帐、办公自动化系统中。为适应飞速发展的网络环境下的安全 需要，就要根据不同的情况设计出适合特殊要求的安全而有效的签名方案。 1 2 数字签名和电子选举简介 数字签名可用来保证信息传输过程中信息的完整性，提供信息发送者身份 的认证，在电子商务中安全、方便地实现在线支付。而数据传输的安全性、完 整性，身份验证机制以及交易的不可抵赖措施等大多通过安全性认证手段加以 解决。电子签名可以进一步方便企业和消费者在网上做生意，使企业和消费者 双方获利。例如，商业用户无需在纸上签字或为信函往来而等待，足不出户就 能够通过网络获得抵押贷款、购买保险或者与房屋建筑商签定契约等；企业之 间也能通过网上磋商达成有法律效力的协议。同样，数字签名在诸如电子选举、 电子现金等领域也有着广泛的使用前景。 在现代的民主社会中，人们经常进行着各种选举活动，在选举的过程中， 总是使用一个锁着的箱子，该箱子的顶部有一个可以放入选票的小缝，每次选 举的选票是由选举委员会特制的。在选举时，人们将填好的选票一张接一张地 投入选票箱，到了开票时再打开选票箱公开地进行唱票。为了确保选举能够公 正、公平与公开地进行，从制作选票到唱票的整个过程，需要花费大量的人力 与物力，采取各种措施，防止干扰选举正常进行的破坏事件和舞弊行为的发生。 随着计算机技术和通信技术的发展，计算机己普及到了千家万户，其强大 的信息处理能力大大地增强了人们的实践能力，减轻了人们繁重的工作负担 尤其是i n t e r n e t 网的迅猛发展，使得人们足不出户，在电脑屏幕前轻点鼠标便 可邀游世界，尽知天下事，使得人们在家里进行选举成为了可能。 电子选举是密码学的一个应用领域，与实际应用有着密切的联系。它以各 种密码学技术( 尤其是数字签名技术) 为理论基础，通过计算机和网络来完成 选举的整个过程。电子选举作为通常选举的电子化，不仅在组织工作、选票搜 集与统计等方面节省了大量的人力及物力资源，具有很高的效率，而且在一定 程度上保证了选举人的利益和选举结果的公正。 电子选举的目标： ( 1 ) 选举人的利益不受侵犯，即从选票信息中不能得到选举人的信息，实现 选举人的匿名选举。 ( 2 ) 保证选举结果的公正，即不能有伪造选票及有效选票遗漏等作弊现象的 出现。 要使电子选举方式能够安全、可靠地运行，除了必须要保证计算机和网络 功能的完好、不受各种攻击的影响、破坏而能够正常运转之外，最根本和最重 要的一点就是：首先必须在密码学技术的基础上设计出安全的电子选举协议。 所以如何设计一种有效的电子选举协议，以保证数据的准确性和机密数据的保 密性，又具备一般选举所有的安全特性，是本文要解决的问题。 1 3 本文的章节安排 本文共分六部分： 第一章首先对论文所研究的问题作了简单介绍，概述了数字签名和电子 选举的基本概况，并提出了本文的研究思路和内容安排。 第二章介绍了数字签名的基本特性和形式化定义，按照不同标准对数字 签名进行了分类，并给出了相应的方案。 第三章分析了数字签名中经常用到的h a s h 函数和时间戳，介绍了盲签 名、群签名、收方不可否认签名、代理签名和多重签名的基本概念，并给出了 相应的实现方案，为其应用作了铺垫。 第四章分析电子选举方案所应具有的特性，并介绍一应用广泛的电子选 举协议f o o 方案，并分析了其安全特性，指出了其不足。 第五章在分析现有电子选举协议的缺陷之后，为了解决问题，我们提出 了一基于群盲签名方案的电子选举协议，给出了其实现的基本框架和协议信息 流程，并对其安全性进行了分析，说明该协议满足要求，对于该协议还进行了 微机上的模拟实现。 第六章总结与展望，对基于群盲签名协议中存在的问题进行了探讨，提 出了今后研究的方向，并分析了在真正的选举中若采用电子选举协议，还存在 的一些问题：诸如法律问题、网络选举协议的软件安装问题。 第二章数字签名技术 数字签名是由d i f f i e 和h e l l m a n 在他们的著名的论文“n e d i r e c t i o ni n c r y p t o g r a p h y ”中第一次提出来的“1 。之后，它引起了许多人的研究兴趣并且 获得了长足的发展。通俗地讲，数字签名是手写签名的模拟，包含一些数据使 得能够取证签名者就是消息的发出者。另外，数字签名也能够被接收者保存下 来，当出现争执时，可以把数字签名作为证据出示给第三方( 如法院) 来验证 签名的合法性，从而可以用来解决争执。因此，它能够防止下面所示的四类问 题。 1 ) 否认或抵赖：发送( 接收) 者事后不承认已发送( 或接收) 过这样一 份文件。 2 ) 伪造：接收者伪造一份来自发送者的文件。 3 ) 篡改：接收者对接收到的信息进行部分篡改。 4 )冒充：网络中的某一用户冒充另一用户作为发送者或接收者。 数字签名是认证技术中的一种，数字签名可以用来进行下列认证。1 ： 1 ) 实体认证：在报文通信之前，采用鉴别协议来认证通信是否在约定的 通信实体之间进行。 2 ) 报文认证：经实体认证后，双方通信实体便可进行报文通信。为了保 证数据的真实性，应对报文进行认证，即接收实体应能验证报文的来源、时间 与目的地的真实性，通常也采用数字签名等技术来实现。 3 ) 身份认证：用户的身份认证是许多应用系统的第道防线，目的是防 止数据不被非法用户访问。除了口令控制之外，在身份认证环节采用数字签名 技术无疑大大提高了访问控制的力度。 z 1 数字签名的基本特性 长久以来，人们一直使用手写签名来证明文件的原作者，或至少证明签名 者同意文件的内容。签名之所以如此馒人信服是因为它具有如下的特性。1 ； 1 ) 签名是可信的。签名使文件的接收者相信签名者慎重签署了该文件； 2 ) 签名不能伪造的。签名能证明是签名者本人而不是别人签署了该文件： 3 ) 签名是不可重用的。签名是文件一部分，任何人不能将该签名移到别的 文件上； 4 ) 签名后的文件是不能更改的。文件签名以后，不能对文件进行更改； 5 ) 签名是不能否认的。签名及文件是客观存在，签名者不能事后称他没有 签过名。 政治、军事、外交活动中签署文件，商业上签定契约和合同，以及日常生 活中进行书信通信、从银行取款等事务中的签名，传统上采用手写签名或印鉴。 随着信息时代的来临，人们希望通过网络进行迅速的、远距离的贸易合同签名， 如果采用手写签名或者将手写签名扫描下来存储在计算机中，很显然不会具有 上述签名特性。为满足此要求，相应数字或电子签名方法便应运而生。经过专 家的长期研究，现在数字签名技术己经广泛用于电子商务、数据库安全、身份 认证、计算机病毒检测、软件保护以及民主选举“1 等方面。类似于手写签名， 数字签名应满足以下要求： 1 ) 接收方能够确认或证实发送方的签名，但不能伪造。 2 ) 发送方发出签名的消息给接收方后，就不能再否认他所签发的消息。 3 ) 接收方对已经收到的签名消息不能否认，即有接收报文认证。 4 ) 第三者可以确认收发双方之间的消息传送，但不能伪造这一过程。 数字签名与手写签名的区别在于，手写签名是模拟的，且因人而异；数字 签名是o 和1 的数字串，因消息而异。主要差别在于o ： 1 ) 所签文件方面的不同。一个手写签名是所签文件的物理部分：而一个数 字签名并不是所签文件的物理部分，所以所使用的数字签名算法必须设法把签 名“绑”到所签文件上。 2 ) 验证方面的不同。一个手写签名是通过和一个真实的手写签名比较来验 证的，这种方法很不安全，相对而言容易伪造别人的手写签名：而数字签名能 通过一个公开的验证算法来验证，这样“任何人”能验证一个数字签名，安全 的数字签名算法的使用将阻止伪造签名的可能性。 3 ) “拷贝”方面的不同。一个手写签名不易拷贝，因为一个文件的手写签 名的拷贝通常容易与原文件区别开来。而一个数字签名容易拷贝，因为一个文 件的数字签名的拷贝与原文件一样，这个特点要求我们阻止数字签名消息的重 复使用，对此可通过要求消息本身包含的信息如日期来达到阻止重复使用签名 的目的。 2 2 数字签名的形式化定义 数字签名其实是伴随着数字化编码的消息或逻辑上与数字化编码有一定关 联的数据项，借助数字签名可以确定消息的发送方，同时还可以确定消息自发 出后没有被修改过，即保证数据来源的可靠性、数据的完整性和准确性。一般 数字签名方案包括三个过程：系统的初始化过程、签名的产生过程和签名的验 证过程。在系统的初始化过程中要产生数字签名方案中用到的所有参数，包括 公开和秘密的参数。在签名产生的过程中用户利用给定的算法对消息m 产生签 名s i g ( m ) ，这种签名过程可以公开也可以不公开。在签名的验证过程中，验 证者利用公开验证方法对给定消息的签名进行验证，得出签名的有效性。下面 给出数字签名的形式化定义m ，： l 系统的初始化过程 产生签名方案中的基本参数( m ，s ，k ，s i g ，v e r ) ，其中：m ：消息集合， s ：签名集合，k ：密钥集合，包含私钥s k 和公钥p k ；s i g ；签名算法集合，v e r ： 签名验证算法集合。 2 签名产生过程 对于密钥集合k 。相应的签名算法为s i g 。s i g ，s i g 。：m 专s ，对任意的消 息m m ，有s = s i g 。( m ) ，那么，s s 为消息m 的签名，将( m ，s ) 发送到签名 验证者。 3 验证签名过程 对于密钥集合k ，有签名验证算法： v e r x ：m s 专 t r u e ，f a l s e ) 即：v e r k ( m ，s ) = t r u e f a l s e ，s = s i g i ( m ) 。 签名验证者收到( 丑，s ) 后，计算v e h ( m ，s ) ，若v e h ( 1 b ，s ) = t r u e ，则签 名有效；若v e h ( m ，s ) = f a l s e ，则签名无效。 更清楚地，我们可以通过图2 1 来理解签名模型。 m 一( i ) 号 一， 墨工 ( 三) 一国 图2 ，1 数字签名模型 2 3 数字签名的分类 按照不同的分类标准，数字签名有不同的实现方案。 2 3 1 基于数学难题的分类 根据数字签名方案所基于的数学难题，数字签名方案可分为基于离散对数 问题的数字签名方案和基于素因子分解问题的数字签名方案。e l g 锄a l 数字签 名和d s a 数字签名方案都是基于离散对数问题的数字签名方案。而r s a 数字签 名方案是基于素因子分解问题的签名方案。将两者结合起来，又可以产生同时 基于离散对数问题和素因子分解问题的混合数字签名方案。例如h a r n 设计的一 种数字签名方案；l 9 7 年l a i h 和k u o 设计的一种耨的数字签名方案，都是混 合方案。二次剩余问题可以认为是素因子分解问题的特殊情况，因此，基于二 次剩余问题同样可以设计多种数字签名方案，例如，r a b i n 数字签名方案，1 9 9 7 6 年n y a n g 和s o n g 所设计的快速数字签名方案等。 一、基于素因子分解问题的签名方案 设n 是一个合数那么找出n 的所有素因子是一个困难问题，这个困难问题 称为因子分解问题，下面介绍的r s a 数字签名体制基于解决这个问题的困难性。 1 9 7 7 年，由r i v e s t ，s h a j n i r 和a d l e l i l a n 提出了第一个比较完善的公钥密 码算法，这就是著名的r s a 算法，r s a 算法可用于数字签名。 r s a 算法的理论基础是一种特殊的可逆模指数运算，它的安全性是基于分 解大整数的困难性。现在我们来描述r s a 算法圳： 系统选择两个大素数p 和q ，一般要求大于1 0 。计算： n = p + q 和中( n ) = ( p 一1 ) ( q 1 ) ：欧拉函数由( n ) 是与n 互素的整数个 数。 随机选择一个与巾( n ) 互质的整数，记为e ，且要求e n 。 计算满足下列条件d ，即( d e ) m o d 中( n ) = 1 ；m o d 为取余运算。 可得公钥( 即加密密钥) p k = e ，n ) ，其中n 为r s a 算法的模数，e 为加 密指数，私钥( 即解密密钥) s k = d ，d 为解密指数。若用整数m 表示明文， 用整数c 表示密文，则加密变换：c = m 。( m o dn ) ；解密变换：m = c “( m o dn ) 。 l 用r s a 算法实现一般数字签名系统 设a 选择两个大素数p 和q ，并求出其乘积n = p q 。，a 任意选择一个整数 e 使得e 与中( n ) 互素，即g c d ( e ，巾( n ) ) = 1 ，则e 为加密密钥，并求出e 在阶为t 中的乘法逆元d ，即e d = 1m o dt 。根据欧拉定理，指数函数在模n 中所有元素阶的最小公倍数t = g c m ( p 一1 ，q 一1 ) ，为了方便起见，我们均使用 t - ( p 一1 ) ( q 一1 ) = 巾( n ) 。a 将( e ，n ) 公布为其公丌密钥，并将d 保存为 其私有密钥，p ，q 毁去不用。 设发送者a 欲将报文m 签名并发送给接收者b ，则首先a 利用其私有密钥 d 对报文m 进行加密运算得签名文s ，其加密公式为s = d ( m ) = m ( m o dn ) 。 然后发送方a 将签名文s 和明文m 通过网络传送给接收者b ，b 收到( m ，s ) 后，b 利用a 的公开密钥( e ，n ) 对签名文s 进行解密验证。其验证公式为： e ( s ) = s 。“( m o dn ) = ( m “) 。( m o dn ) = m 。 因为除a 外没有别人有解密密钥d ，所以除a 外没有别人能够产生签名文 s = d ( m ) ，这样，报文m 就被签名了。假若a 要抵赖曾经发送报文给b ，b 可将 m 及s = d ( m ) 出示给第三者。第三者很容易用m = e ( s ) 证实a 确实发送了消 息m 给b 。反之，如果是b 将m 伪造成m ，则b 不能在第三者面前出示d ( 用) ， 这样就证明b 伪造了报文。可以看出，上述方法在实现数字签名的同时也实现 了对报文来源的鉴别。 2 用r s a 算法同时达到秘密通信与数字签名“” r s a 是一种指数函数的系统，因此具有乘法性。在r s a 签名系统( ( e ，n ) 为签名者的公开密钥，d 为秘密密钥) 中存在下列缺点： 1 ) 伪造者可任意伪造( 明文，签名文) 对。方法是伪造者任选一签名文s ， 并求出m = s 。m o dn ，则f 【i 及s 为一合法的( 明文，签名文) 对，虽然m 可能并 无任何意义，但签名系统的安全性肯定存在隐患。 2 ) 选择签名文攻击法。伪造者欲伪造一明文m 的签名文s ，则伪造者任选 两数m 及m ：，满足m 。 m ，= m 。接着，伪造者将矾及m 2 送请签名者签名得签名文 s 及s ：。则伪造者可得伪造的合法签名文s = s s ：o dn 。 为了克服上述问题，可将公开密钥密码系统与数字签名系统结合，则可同 时达到秘密通信与数字签名的目的，此结合方式如图2 2 所示： 图2 2同时达到秘密通信与数字签名 设网络用户a 和b 有各自的公开密钥( e ，n ) ( e 。，) 及秘密密钥d ，如 若a 要安全可靠地传送明文m 给b ，则a 首先对明文m 签名得s ，并对签名文s 用b 的公开密钥加密得密文c 。即： 签名：s = d ( ) = m “( m o dn ) 加密：c = e b ( s ) = s “( m o dn b ) b 收到密文c 后，先用其秘密密钥对c 解密得签名文s 。接着利用a 的公开 密钥验证a 的签名，即： 解密：s = d b ( c ) = c “( m o dn b ) 验证：e ( s ) = s ( m o dn 。) = m ( o dn ) r s a 数字签名方案存在下列缺陷。1 ：分解模数n 在理论上未被证明是n p 问 题，目前分解算法和计算能力都得到提高，因此n 要求越来越大；对于活动攻 击和假冒攻击是脆弱的：具有同态性质；签名者每次只能签 1 0 9 ：n 比特长的消 息，获得同样长的签名，速度慢，而且签名文太长。 二、基于离散对数问题的数字签名方案 我们首先简单介绍什么是离散对数问题： 设g 是一个乘法群，a 是g 中任意一个元素，对于给定的b g ，如果存 在个整数x ，使得a x = b ，则称x 是以a 为底b 的离散对数，记作x = l o g 。b 。 在给定a ，b 的情况下，去求x = l o 岛b 的问题称为离散对数问题。 e l g 鲫a l 于1 9 8 5 年基于离散对数问题提出了一个既用于加密又用于数字签 名的密码体制，这个数字签名方案的一个修改方案已被美国国家标准技术研究 所( n i s t ) 采纳为数字签名标准d s a 。e l g a m a i 数字签名方案像e l g a m a l 公钥密 码算法一样是非确定性的，这意味着对任何给定的消息有许多合法的签名。 l e 1 9a f i l a l 加密体制。 设p 是一大个素数并且离散对数问题在z p 上是难求解的，g z p ，是一个 本原元。密钥x ( 1 x ( p 一1 ) 是保密的，相应的公钥y = g 册o dp ，将p ，g ，y 公 开。 发送方加密消息m 时，先选择一随机数k ，使k 与p l 互素。然后计算： a = g 。m o dp 和b = y 。mm o dp ( a 和b 为密文，注意密文的长度是明文的两倍) 。 接收方收到密文a 和b 后，按以下公式计算明文，m = b a m o dp 。其正确 性由下式保证： 因为a 1 = g m o dp ，故有：b a = y m a 。= 矿m a = mm o dp 。 例：假定p = 2 5 7 9 ，g = 2 ，x = 7 6 5 是a 的私钥，则y = g m o dp = 2 7 “m o d2 5 7 9 = 9 4 9 是a 的公钥。现在假定a 想发送消息m = 1 2 9 9 给b 。比如说k = 8 5 3 是a 随机选 择的整数，a 计算以下式子：a = g “m o dp = 2 ”5m o d2 5 7 9 = 4 3 5 ，b = y 。mm o dp = 9 4 9 8 ”1 2 9 9m o d2 5 7 9 = 2 3 6 9 ，然后a 将密文( 4 3 5 ，2 3 6 9 ) 传送给b ，b 收到 密文后，解密计算得：m = b a 1m o dp = 2 3 6 9 4 3 5 7 “m o d2 5 7 9 = 1 2 9 9 。 2e 1 g a m a l 数字签名方案 e l g a l l l a l 数字签名方案是基于离散对数的一种数字签名算法，该算法应用 广泛，在密码学研究中占有重要地位。方案简述如下： ( 1 ) 系统参数 p ：是一大素数： q ：是p l 的大素因子： g ：g z ，且g q 一1 ( m o dp ) ，是p 的本原元； 用户b 的秘密密钥x ：1 x q ； 用户b 的公开密钥y ：y = g ( m o dp ) ； ( 2 ) 签名：对于名文l m p 1 签名方b 先任选一整数k ，要求k b 若满足如下两条件，则f 被称为单向函数。 1 ) 对数x a ，计算y = f ( x ) 是容易的，其中y b 。 2 ) 对于y b ，求x a ，使满足f ( x ) = y 是计算上不可能的。 设a 是f o ，1 ) ，a ：o ，l 符号串构成的集合，设h ：将a 映射为a n ，即将 任意长度的o ，1 符号串映射为固定长度n 的o ，1 符号串。则可将h 称为单向 散列函数。单向散列函数若满足如下特性，则称为安全保密的h a s h 函数。 1 ) 给定x ，要计算h ( x ) 是容易的，使得硬件和软件实现成为实际可行。 注：这里所说的容易以及下面的困难、计算上不可能( c o m p u t a t i o n a l l y i n f e a s i b l e ) 分别是指以现有计算能力( 计算速度、存储空间等) 进行计算时 容易、困难和无法进行计算。 2 ) 己知h ( x ) ，要计算x 是困难的。 这一性质实际上就是所谓的单向性( o n e w a yp r o p e r t y ) ：当己知一消息时 很容易计算其h a s h 值，而当己知h a s h 值时几乎不可能计算出消息，也就是说， 要找到函数h ( ) 的逆运算h 。1 ( ) 几乎是不可能的。 3 ) 对任给定的消息x ，要找到另一个消息x 使得h ( x ) = h ( x ) ，在 计算上是不可能的。 这一性质有时也被称为弱碰撞免疫性( w e a kc o l l i s i o nr e s i s t a n c e ) ，它 其实保证了对于某一给定的消息，是无法找到另一个消息使得两个消息的h a s h 值相等的。这就在根本上防止了任何一方通过替换消息x 或对其进行修改而保 持h ( x ) 不变来进行伪造。 4 ) 要找到任意两个消息x 和x 使得h ( x ) = h ( x ) ，在计算上是不可能的。 这一性质也被称为强碰撞免疫往( s t r o n gc 0 1 1 i s i o n e s i s t a n c e ) ，它其 实度量了h a s h 函数能在多大程度上抗生日攻击( b i r t h d a ya t t a c k ) ，能抗击生 日攻击的h a s h 函数值至少为1 2 8 b i t 。 为了加强弱碰撞自由的h a s h 函数的安全性，人们建议在弱碰撞自由的h a s h 函数中引入随机性。引入随机性的方法主要有三种： 1 ) 用一个好的分组密码和使用一个真正随机的密钥加密消息使消息随机 化。随机密钥也将级联到密文的开头。 2 ) 在对消息进行h a s h 之前，给消息随机选择一个前缀，这样的一个随机 前缀将有效地随机化h a s h 值。 3 ) 从一族h a s h 函数中随机选择h a s h 函数而不是随机化消息本身。 密码学上的h a s h 函数( 也称杂凑函数、杂凑算法) ，是一种将任意长度的消 息压缩到某一固定长度的消息摘要( m e s s a g ed i g e s t ) 的函数。将h a s h 函数应用 到数字签名o ”( 见图3 1 ) 中可带来以下优点。 1 ) 可破坏数字签名方案的某种数学结构，诸如同态结构。 2 ) 可提高数字签名的速度。当签名者想签一个消息x 时，他首先构造一个 消息摘要：z = h ( x ) ( h 是一个h a s h 函数) ，然后计算签名y = s i g 。( z ) 。 图3 i 使用h a s h 函数的数字签名方案 3 ) 无需泄露签名所对应的消息，但可将签名泄露，比如对消息x 的签名是 y = s i g x ( z ) ，其中z = h ( x ) ，可将( z ，y ) 公开，而保密x 。 4 ) 可将签名变换和加密变换分开来，允许用私钥密码体制实现保密，而用 公钥密码体制实现数字签名。在i s o 的公开系统互联参考模型( o p e ns y s t e m i n t e r c o n n e c tr r e f e r e n c em o d e l ) 中，这种分离的一个优点是可在不同层提供 消息的完整性( i n t e g r i t y ) 和机密性( c o n f i d e n t a l i t y ) 。 h a s h 函数除了可用于数字签名方案之外，还可用于其它方面，诸如消息的 完整性检测，消息的起源认证检测等。例如，文件所有者为了保障一个文件的 完整性，即阻止对文件的非法改变，他首先必须获得一个文件的h a s h 值，自己 保存这个文件h a s h 值的一个拷贝，然后将文件存储在可公开的地方。每当他使 用文件时，他计算存储的文件的h a s h 值，然后与他自己保存的拷贝进行比较， 如果相等，文件是完整的，没有被改动，否则文件己被改动。 构造h a s h 函数的方法分为三种，第一种是信息论方法，它以信息论为基础， 提供了无条件安全性，即安全性与敌手的计算能力无关。第二种方法是复杂性 理论方法，这种方法起源于计算的抽象模型，并假定敌手具有有限的计算能力， 它只能提供计算上的安全性。第三种方法是系统论方法，其安全性估计是以所 知道的攻击该系统的最好的算法和必需的计算能力或实现算法的专用硬件的实 际估计为基础的。 目前己有的一些h a s h 函数主要是通过以下几种方法构造而成的： 1 ) 基于一些困难问题诸如离散对数问题、素因子分解问题、背包问题等构 造的h a s h 函数，利用这种方法所构造的h a s h 函数的安全性依赖于解决这些问 题的困难性。 2 ) 基于私钥密码算法的h a s h 函数，这种类型的h a s h 函数已被提出很多， 但它们中的许多己被证明是不安全的( 独立于所使用的基础密码体制的安全 性) 。 3 ) 直接构造法。这种构造方法没有依赖任何假设和密码体制，但是速度很 快，非常实用。 目前常见的三种重要的散列函数是m d 5 、s h a l 和r i p e m d 一1 6 0 。m d 5 报文摘 要算法( r f c1 3 2 1 ) 是由r o nr i v e s t ( r s a 算法中的r ) 在麻省理工学院提出 的，曾是使用最普遍的安全散列算法。s h a 安全散列算法是由美国国家标准和 技术协会n i s t 提出，并作为联邦信息处理标准( f i p sp u b1 8 0 ) 在1 9 9 3 年公 布；1 9 9 5 年又发布一个修订版( f i p sp u b1 8 0 一1 ) ，通常称之为s h a l 。s h a 是 基于m d 4 算法的，并且它的设计在很大程度上是模仿m d 4 的。r i p e m d 1 6 0 报文 摘要算法是在欧洲r a c e 的p i p e 项目中由研究人员开发而成的。 3 2 时间戳服务 使用一个数字签名方案时，可能会遇到一些麻烦问题。诸如，一个签名者 的签名算法和密钥可能被一个敌手偷走，此时，对签名者在敌手偷走签名算法 之前所