（基础数学专业论文）几类特殊数字签名的研究.pdf

y8 6 3 7 7 7 中央民族大学硕士学位论文 摘要 数字签名是现代密码学中主要研究内容之一，它是保证数据可靠 性，实现认证的重要工具。数字签名在商业、金融、军事等领域，特 别是在电子贸易、电子支票、电子购物、电子出版以及知识产权保护 等方面都有实际的应用。近几年来随着数字签名研究的深入，产生了 很多特殊的数字签名，如代理签名、群签名、盲签名、多重签名、前 向安全签名等等。这几类签名体制在电子商务、公共资源的管理、军 事命令的签发、金融合同的签署等方面有着广泛的应用前景。 本文在前人成果的基础上，作了以下一些工作： 第一部分，描述了几类特殊数字签名体制：代理签名、群签名、 盲签名、多重签名产生的背景、现状与进展，给出了这几类签名体制 的典型签名方案，指出了这几类签名体制的相互结合和借鉴，并且对 未来的研究方向进行了展望。 第二部分，重点对代理数字签名进行了研究，主要工作有两个： 一是对改进的脚代理签名方案进行了分析与讨论，提出了一种代 理签名方案而国p - j ，新的方案能够抵抗冒充原始签名者攻击与冒充代 理签名者攻击：二是对改进的朋代理签名方案进行了分析，提出 了新的代理签名方案孵2 ，它能够纠正原方案的冒充代理签名者攻 击的漏洞。 第三部分，介绍了椭圆曲线密码体制和前向安全签名的基本概 中央民族大学硕士学位论文 念。将前向安全与与代理签名结合起来，给出了一种基于椭圆曲线密 码体制的前向安全代理签名方案，保证了系统在泄露密钥( 或撤消密 钥) 后以前所做签名的有效性问题，并讨论了该方案的正确性和安全 性。 第四部分，首先引入了密钥隔离签名的概念和模型，利用 剧g 口m 耐签名构造了一个密钥隔离方案，并论证了它的正确性和安全 性。密钥隔离签名虽然增加了用户与系统之间的交互，但是一旦密钥 泄露的话，不仅保障了签名的前向安全也保障了后向安全。接着介绍 了入侵可恢复签名的概念和模型，描述了一个具体的入侵可恢复签名 方案，论证了它的正确性。入侵可恢复签名是前向安全签名和密钥隔 离签名的进一步改进。只要用户和系统的密钥未被同时泄露，这个方 案可以提供前向安全和后向安全，并且即使是用户和系统的密钥同时 泄露的话，它也保证了签名的前向安全。 关键词数字签名，代理签名，前向安全，密钥隔离，入侵可恢复 中央民嗾大学硕士学位论文 t w om a j o rr e s u h s ：f i r s t ，a n a l y z e sa n dd i s c u s s e st h er e v i s e dm u 0 p r o x y s i g n a t u r e s ，p r o p o s e san e wp f o x ys i g n a t u r es c h e m e h h p 一1 t h en e w s c h e m ec a nr e s i s tt w o f o r g e f ya t t a c k s ；s e n d ，a i l a l y z e sa n dd i s c u s s e st h e r e v i s e di 胍p r o x ys i g n a t u r e s ，p r o p o s e san e wp f o x ys i g n a t u r es c b e m e h h p - 2 i tc a nr e s i s tf b r g e r ya t t a c ko ft h ed i s h o n e s to r i g i n a ls i g n e r p a r tl i l ，i n t r o d u c e st h eb a s i cc o n c e p t so ff o r w a r d s e c u r es i g n a t l l r e a n d e l l i p t i c c u e c r y p f o s y s t e m ，p r o p o s e d af b r a r d - s e c u r e p r o x y s i g n a t u r es c h e m eb a s e do nt h ee l l i p t i cc u r v ec r y p t o s y s t e m ，d i s c u s s e si f s s e c u r i t ya n dv a l i d i ty - t h i ss c h e m em a k e ss u r eo ft h ev a l i d i t yo fs i g n a t l l r e o ff o 珊e rp h a s e si ft h ep r i v a t ck e yi nt h es i g n a l u r ei sl e a k e d0 u t ( o r r e v o k e d ) i ns o m ep e r i o do ft i m e p a r ti v ，f i r s t i n t f o d u c e st h ec o n c e p ta l l d 1 0 d e lo fk e y i n s u l a t e d s i g n a t u r e ，c o n s t r u c t sak e y i n s u l a t e ds i g n a t u r es c h e m e b a s e do ne l g a m a l d i g i t a ls i g n a t u r ea n dp r o v e si t sc o r r e c t n e s sa 1 1 ds e c u r i t y 触t h o u g ht h e k e y - i n s u l a t e ds i g n a n l r e s i n c r e a s e s e x c h a n g i n ga n du p d a t i n gp r o c e s s b e t w e e nu s e ra n dm a s t e r ， o n c et h ek e y sa r e1 e a k e do u t ，t h es c h e m e p r o v i d e sn o to n l yt h ef o r w a r ds e c u r i t yb u ta l s ot h eb a c k w a r ds e c u r i t y t h e nt h i sp a p e ri n t r o d u c e st h ec o n c e p ta n dm o d e lo fi n c r u s i o n r e s i l i e n t s i g n a t u r e ，d e s c r i b e sas p e c i f i ci n t r u s i o n r e s i l i e n ts i g n a t u r es c h e m ea n d p r o o f si t sc o r r e c t n e s s 1 n i m s i o n r c s i l i e n ts i g n a t u r ei s f u r t h e ri m p r o v e d b a s e do nf o r w a r d s e c u r es i g n a t u r ea n dk e y i n s u l a t e ds i g n a t u r e a sl o n g a st h ek e y so fu s e ra n dt h ek e y so fh o m eb a s ea r e n tl e a k e do u i 中央民族大学硕士学位论文 s i m u l t a n e o u s l y ， t h es c h e m ec a n p r o v i d e t h ef o n v a r d s e c u r i l y a n d b a c k w a r ds e c u r i t y m o r e o v e r ，t h es c h e m er e t a i n st h ef o 刑a r ds e c u r i t y e v e nw h e na l lt h ek e y sa r el e a k e do u ts i m u l t a n e o u s l y k e yw o r d s d i g i t a ls i g n a t u r e s ，p r o x ys i g n a t u r e ，f o n v a r d - s e c u r e s i g n a t u r e ，k e y - i n s u l a t e ds i g n a t u r e ，i n t m s i o n - r e s i l i e n ts i g n a t u r e 中央民族大学硕士学位论文 第一章绪论 第一节信息系统安全的重要性 计算机技术的快速发展为人类提供了高度的自动化和现代化，随着计算机网 络的不断扩大。人类社会在向着国际化、信息化方向发展，高速、高效、广泛的 信息交流己经渗透到政治、经济、军事、科学文化和家庭生活等社会的各个领域， 社会的生产方式和社会的其他生活方也因此而逐渐改变。但由此衍生出的信息被 监听、截取、伪造、破坏、篡改等等恶意行为就使得信息安全的需求逐年升温， 利用安全技术防范以上行为也到了一个刻不容缓的地步，信息安全得到了人们的 普遍关注。 信息系统安全的中心内容是保证信息在系统中的保密性、认证性和完整性。 传统的密码体制，其主要功能是信息保密，而现代密码体制还应保证信息在系统 的可认证性和完整性，这样可以保证在公开信道上安全地传递信息。为了防止消 息被窜改、删除、重放和伪造，一种有效的方法是使发送的消息具有被验证的能 力，使接收者能够识别和确认消息的真伪，实现这类功能的密码系统称为认证系 统。消息的认证性和消息的保密性不同。保密性是使截获者在不知密钥的情况下 不能解读密文的内容。而认证性是使任何不知密钥的人不可以构造出一个密文， 使意定的接收者脱密成一个可理解的消息( 合法的消息) 。认证理论和技术是最近 2 0 年来随着计算机通信的普遍应用而迅速发展起来，它成为保密学的一个重要 的领域。 认证系统主要有以下几个方面的内容：( 1 ) 消息认证；( 2 ) 身份认证：( 3 ) 数字 签名。曲两者的目的是解决在通信双方利害一致条件下，如何防止第三方伪装和 破坏的问题。而数字签名则解决了当通信双方是竞争对象时，如何远距离迅速地 用电子签名代替传统的手写签名和印签的问题| l l 。 中央民族文学硕士学位论文 第二节数字签名的简介 在人们的日常生活中以及工作中，许多事务需要当事者签名。在传统的以书 面文件为载体的事务处理中，通常采用手写签名、印章、指纹等方式作为书面签 名。书面的签名可以得到司法部门的认可，具有法律意义。在以计算机数据文件 为基础的电子邮件，电子商务等数字通信中，传统的书面签名失去了它的意义， 因为书面签名可以被任意的拷贝。数字签名技术应用而生，它是以密码学的方法 对数据文件产生的一组代表签名者身份与数据完整性的数据信息。数字签名和书 写签名的区别之一在于同一当事者对不同的文件的数字签名是不相同的( 含有文 件的信息摘要) 。这样某一个文件的书面签名可被伪造者复制到不同的文件上， 而任一个文件的数字签名不可能被直接复制到不同的文件上进行伪造签名，数字 签名可用来保护信息的真实性、完整性和信息的来源。 数字签名技术引起了学术界尤其是密码学界和计算机网络界的广泛重视，特 别是随着妞耙，摊甜的飞速发展和电子商务的提出，数字签名技术获得了更加广泛 的研究和应用。各国都己经制定详细研究计划开始着手对数字签名进行研究，都 希望建立自己的数字签名标准。我国近几年也随着信息技术的高速发展在数字签 名方面做出了很多的研究工作，有越来越多的人进行着有关数字签名理论和应用 方面的研究工作。我国也开始了对本国数字签名标准的征集工作。在国外一些国 家不仅提出很多实际可行的数字签名方案，而且相应的还建立了数字签名法案， 使数字签名得到司法机关的认可，具有法律效应。 最早的数字签名算法有只蹦数字签名方案【2 j ，d 鲥数字签名方案、e c d 蹦 数字签名方案，此三种签名方案于2 0 0 0 年2 月1 5 同被美国国家标准技术研究所 ( m s n 在新标准法案h 船j 跖2 中指定为美国的数字签名标准，同时他们也是目 前世界上普遍使用的普通数字签名方案，都已经形成商业的签名软件供商家和个 人使用。其中r 鲋数字签名方案是由兄翱公司提出的基于r 蚋公钥密码体制的 签名方案，其数学基础是大数因子分解的困难性。d - 鲥数字签名方案是基于 提出的剧函m a ，公钥密码体制，其数学基础是在有限域上求解离散对数的嘲难 中央民族大学硕士学位论文 性。c d 翩数字签名方案是基于椭圆曲线密码体制的签名方案，它是将 n 钏签名方案移植到椭圆曲线密码体制中来得到的，它的数学基础是求解椭圆曲 线上离散对数的困难性。目前由于椭圆曲线密码体制较其他公钥密码体制有密钥 短、速度快、安全性高的优点使得椭圆曲线密码体制以及c d s 4 数字签名方案 越来越受到重视。 随着计算机技术和互联网技术的广泛应用，数字签名存在各种各样的应用背 景，在不同的环境下对数字签名提出了更多的要求。面对这样的需求，具有特殊 用途的数字签名方案被提出。形成了数字签名研究的多个值得关注的方向。如： 前向安全数字签名、盲签名、不可否认签名、门限签名、群签名、代理签名、短 签名、环签名等掣扪。 第三节论文的研究内容和章节安排 本论文研究的主要内容是特殊数字签名，笔者的研究重点是代理签名、前向 安全签名、密钥隔离签名和入侵可恢复签名。全文从理论所属范畴上说可以分为 两大部分：第一部分内容是代理签名的研究；第二部分是为减少密钥泄露带来的 损失而进行的签名的研究。笔者对代理签名的主要研究成果有两个：、对改进 的叩代理签名方案进行了分析与讨论，提出了新的代理签名方案并分析了它 的安全性；二、对改进的工斌代理签名方察进行了分析与讨论，提出了新的代 理签名方案并分析了它的安全性。第二部分内容的工作主要有三个：一、笔者将 前向安全思想与代理签名结合起来，在椭圆曲线密码这个相对优化的体制下，设 计了一种前向安全的代理签名；一、介绍了密钥隔离签名的概念和模型，利用 e ，g 口m 口l 签名构造了一个密钥隔离方案：三、引入入侵可恢复签名的概念和模型， 描述了一个具体的入侵可恢复签名方案，论证了它的萨确性。 本论文的章节安排如下： 第二章首先介绍了密码学的基本概念和发展概况。重点是公钥密码学的描 述：接着介绍了数字签名的基本理论，列举了一些典型的普通数字签名方案。 第三章主要是对特殊数字签名进行了归纳、描述。重点是代理签名、卣签名、 中央民族大学硕士学位论文 群签名、多重签名，对每一种体制都给出了具体的方案实施过程，还分别进行了 总结性展望。这是为笔者以后继续研究特殊数字签名作好的知识储备。 第四章是代理签名的研究。首先列举了常见的代理签名协议：在此基础上， 接着分析了两类基本的代理签名及其改进方案的脆弱性，用具体的攻击方法实施 攻击；最后分别提出笔者改进的方案并分析安全性。 第五章研究的是前向安全签名与代理签名的结合。给出了前向安全思想的本 质以及椭圆曲线密码体制的基本理论，将这些知识与代理签名进行了融合，提出 了一种椭圆曲线密码体制下的前向安全代理签名方案，分析了它的安全性。 第六章引入密钥隔离签名与入侵可恢复签名，这两者是前向安全签名的再发 展，它们都是为了减少签名密钥泄露带来的损失而提出的。笔者构造了一种基于 f g 矗卅口l 签名的密钥隔离方案并进行了安全分析；描述了入侵可恢复签名和一个 具体的方案，论证了方案的正确性。 章央民族支学硬士学位论文 第二章密码学基本理论 本章主要分两部分，第一部分主要介绍密码学的基本概念和发展概况；第二 部分介绍数字签名的基本理论与基本的数字签名方案。 第一节密码学概述 一、密码学的发展概况 密码学是一门古老而又年青的科学，它用于保护军事和外交通信可以追溯到 几千年兹。在当今昀信息对代。大量台勺敏感信息如挡案、法庭记录、银行交易等 常常通过公共通信设施或计算机网络来进行交换，而这些信息的秘密性和真实性 是人们迫切需要的。因此，现代密码学的应用已不再局限于军事、政治和外交， 其社会价值甚至商用价值也己得到了充分的发展。 密码学的发展历史大致可以划分为三个阶段： 第一阶段从古代到1 9 4 9 年。这时期可看作为是科学密码学的前夜时期， 】 这段时期的密码技术可以说是种艺术，而不是一种科学，密码学专家常常是凭 直觉和信念来进行密码设计和分析，而不是推理证明。 第二阶段从1 9 4 9 年到1 9 7 5 年。1 9 4 9 年鼬4 聊发表了保密系统的通信 理论 c d m 舢n f f i 动黟巧s e c r 唧s 垮f 绷s ) 鸽著名论文，为私镪密码系统建 立了理论基础，从此密码学成为一门科学。这段时期密码学理论的研究工作进展 不火，公开的密码学文献很少。1 9 6 7 年彪z 砌出版了一本专著破译者，该书 没有任何新的技术思想，只是记述了一段值得注意的完整经历，包括政府仍然认 为是秘密的一些事情，它的意义在于它不仅记述了1 9 6 7 年之前密码学发展的历 史，而且是许多不知道密码学的人了解了密码学。7 0 年代初期，删发表了凡西f e ， 和他的同事们在这个学科方面的几篇技术报告。 第i 个阶段从1 9 7 6 年至今。1 9 7 6 年雕d 自睁和m h 勘z 口n 的密码学的新 方向一文导致密码学上的一场革命。他们首次证明了在发送端和接收端无密钥 中央民族大学硕士学位论文 传输的保密通信是可能的，从而丌创了公钥密码学的新纪元。1 9 7 7 年美国联邦 政府颁布数据加密标准( d e s ) ，这是密码史上的一个创举。d 嬲算法最初由美国 膳m 公司设计，经国家保密局测评，颁发为标准，d 醯开创了向世人公开加密 算法的先例。它设计精巧、安全、方便，是近代密码成功的典范。它成为商用密 码的世界标准，为确保数据安全作出了重大贡献。d 嬲的设计充分体现了册口n n 伽 信息保密理论所阐述的设计密码的思想，标志着密码设计与分析达到了新的水 平。1 9 9 4 年美国联邦政府颁布密钥托管加密标准和数字签名标准( n 蟠) 1 9 9 7 年美国宣布公开征集高级加密标准爿s ，以取代d 醯，经过三轮筛选，最 终在2 0 0 0 年确定使用比利时密码学家j d n _ ，ld 4 绷跏和p 轨c 删f r 盯m 跏提出的一种 密码算法r 咖妇e z 作为a 醯。2 0 0 1 年美国联邦政府正式颁布了高级加密标准 口e s ) 。这些都是密码发展史上一个个重要的里程碑。此外，密码学出现了一些 新方向，先后提出了量子密码学、混沌密码学和生物密码学。量子密码的基本依 据是量子力学的不确定性原理和量子态的不可克隆原理，它是基于菲数学的原理 的密码。混沌是一种复杂的非线性非平衡动力学过程。由于混沌序列是一种具有 良好随机性的非线性序列，有可能构成新的序列密码，因此世界各国的密码学者 对混沌密码寄予了很大的希望。生物信息技术的发展推动着生物芯片、生物计算 机和基于生物信息特征的生物密码的研究。我们相信，量子密码学、混沌密码学、 生物密码学的出现将把我们带入一个新的境界| 4 】。 二、密码学的基本概念 密码学技术是信息安全技术的核心，它主要由密码编码技术和密码分析技术 两个分支组成。密码编码技术的主要任务是寻求产生安全性高的有效密码算法和 协议，以满足对数据和信息进行加密或认证的要求。密码分析技术的主要任务是 破译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏活动。这两个分支 既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发 展。目前人们将密码理论与技术分成两大类，一类是基于数学的密码理论与技术， 包括公钥密码、分组密码、序列密码、认证码、数字签名、散列函数、身份识别、 密钥管理、尸灯技术、阡w 技术等：另一类是非数学的密码理论与技术，包括信 息隐减、量子密码、基于生物特征的识别理论与技术等。 中央民族大学硕士学位论文 第二节公钥密码体制 1 9 7 6 年，加密体制发生了重大变革，美国斯坦福大学数学家和计算机专家 联名发表了密码学中的新方向一文，提出了一种新型的加密体制：公钥密码 体制。公钥密码学的概念是为了解决传统密码学中最困难的两个问题提出来的， 第一个是密钥分配问题；第二个是数字签名和身份认证问题。公钥密码比传统的 密码更能有效的实现数字签名，可以说数字签名是伴随着公钥密码学的进展得到 了长足的发展，现有的数字签名基本上都是利用公钥密码构造的，所以我们将详 细介绍公钥密码的原理及流行的几种公钥密码方案。 用抽象的观点来看，公钥密码体制就是一种陷门单向函数。我们说一个函数 ，如果对它的定义域上的任意工都易于计算厂似，而对于，的值域中的几乎所有 的_ ) r ，即使当，已知时要计算，4 ( y ) 也是不可行的，则称，是单向函数。若当给 定某些辅助信息下易于计算单向函数了的逆，一，则称，是一个单向陷门函数。 公钥密码是将传统密码的密钥k 一分为二，分为加密密钥e 和解密密钥 ，用加密密钥k 。控制加密，用解密密钥髟控制解密，而且由计算复杂性确 保由加密密钥必。在计算上不能推出解密密钥髟。这样，即使是将x 。公开也不 会暴露k 。，也不会损害密码的安全。于是便可将k 。公开，而只是对k 。保密。 可以用下面的图来表示。 单钥密码体制k = l 【d 公钥密码体制k _ l ( d 图2 1 密码体制 中央民族大学硕士学位论文 根据公钥密码的基本思想，可知一个公钥密码应当满足以下三个条件 1 ) 解密算法d 与解密算法e 互逆，即对于所有明文m 都有dr c ，q ，= d 僻 l m ，ke ) ，ka ) = m 。 2 ) 在计算上不能由k 。求出k 。 3 ) 算法和d 都是高效的。 条件1 1 构成密码的基本条件，是传统密码和公开密钥密码都必须具备的起 码条件。 条件是公钥密码的安全条件，是公钥密码的安全基础，而且这一条件是最 难满足的。由于数学水平的限制，目前尚不能从数学证明一个公钥密码完全满足 这一条件，而只能证明它不满足这一条件。这就是这一条件困难性的根本原因。 条件3 ) 是公钥密码的实用条件。因为只有算法和d 都是高效的，密码才 能实际应用。否则，可能只是理论意义，而不能实际应用。满足了以上三个条件， 便可构成一个公钥密码，这个密码可以确保数据的秘密性。进而，如果还要求确 保数据的真实性，则还应满足第四个条件。 q 对于甄奄明文m 都奄e ( d ( m k d ) 。k t ) = m 。 下面将介绍几种常见的公钥密码体制。 一、兄朝密码体制 r 姐密码体制用到了初等数论中的一个重要定理欧拉定理，其安全性依 赖于大整数的因数分解的困难性。r 蜘密码体制描述如下： 1 创建密钥 研印j 随机选择两个素数p 和q ，满足i p h 目l ； s t e p 2 计算n = pq ，咖( n ) = ( p 1 ) ( q 一1 ) ； 印3 随机选择整数岛j p 庐似) 且g c d 心m = j ； & 印4 计算整数d ，满足甜= j 小删妒( n ) ； 印5bg 和妒保密，公钥为( n ，e ) ，私钥为d 。 2 j j 【i 密 中央民族大学硕士学位论文 消息掰( 以) ，计算密文c = j ，l 。珊谢，l 。 3 解密 密文c ，解密密文得明文m = c 。册d d ，l 。 分析密钥建立过程可知，如果能从n 正确分解出p 和口，则不难计算出庐m ) ， 进一步依据e 和庐似) 可解出d 所以如果能有有效的算法对大数进行因子分解，则 兄翻密码体制将被攻破。 二、f g 白，l n f 密码体制 e f g n m 口j 密码体制的安全性依赖于离散对数问题的困难性，许多数字签名方 案是建立在该问题的困难性之上，美国于1 9 9 4 年公布的数字签名标准d 婚 ( d 浮细fs 自即日m 陀s 细l 如嗍就是日6 钮卅4 z 数字签名方案的一个变形。尉g n m 口z 密 码体制描述如下： 1 创建密钥 & 印j 随机选择素数p ，以及z 。的一个生成元g ； & 叩2 随机选取xe z ，为私钥，计算y = 办以p ； e 一公开公钥p ，g ，y ) 。 2 加密 消息( 印) ，随机选取七z 。计算密文 c j = g m o d p ，和c 2 = m y o d p 3 解密 密文( c b c 2 ) ，计算明文m = c 2 ，c 】m o d p 所谓离散对数问题是指对于给定的素数p ，n 是z ，的生成元，元素卢z ，+ ， 寻找满足口1 = 卢m o dp 的x ，这晕o sxsp 一2 。该问题己被广泛认为是可以依赖 桷阻难阍题。与之糨关的另个困难阔题是d 弼e - h e i i m n n 阃题，d 酾e - h e l l m n n 汹 题是指p 为素数，n 是z 。的生成元，依据a4 m o d p 和a 6 m o d p ，找a “m o d p 。 如果对离散对数问题能有有效的多项式时问算法解得x ，则d 咿e m f 枷口n 问题也能获解。对于a ，p ，8 。m o d p 和n 6 m o dp ，可先从4m o dp 中根据离散对 中央民族大学硕士学位论文 数问题的多项式时间算法解出口，再计算( 口6 r = 口“m o d p 。 三、椭圆曲线密码体制 ( 一) 基本理论 1 9 8 5 年劢矗d 5 l 和矿m f 衙l q 第一次提出将椭圆曲线应用到公钥加密算法 中。椭圆曲线密码是建立在有限域上椭圆曲线有理点群的一种密码系统。它的原 理是基于有限域上椭圆曲线离散对数问题( e a 圮_ p ) ，这是一个困难问题。c d l p 比有限域上的离散对数问题要困难得多。目前，分析尼鲥和e 丽朋口? 系统 存在亚指数算法，而分析椭圆曲线密码不存在亚指数算法。因而，对于相同规模 的参数，椭圆曲线密码每一比特密钥的强度要比有限域体制下每一比特密钥强度 大得多；要得到同样强度的密码，椭圆曲线系统的参数规模要小得多。 设坞分别表示具有相同计算复杂性的椭鼹曲线系统和j g 口，眦l 系统 相应的有限域的规模，那么有下面关系： n = 4 9 l n l 。p g ( nl 口g2 ) ) 。3 由这一公式可得到有关竹，对应的一组数据，( 1 7 3 ，1 0 2 4 ) ，( 2 3 0 ，2 0 4 8 ) ，( 3 1 3 ， 4 0 6 9 ) ，即1 7 3 b 豇的椭圆曲线系统相当于1 0 2 拍打的点粥h 小口f 系统或兄妇系统。 可见椭圆曲线系统的参数规模要小得多，因而无论在实现与应用上都具有很大的 优越性。椭圆曲线密码的另一个优点是椭圆曲线的资源极为丰富，个有限域 g 只缈仅有有限的几个乘法子群，却有数量级为鼋的椭圆曲线的嗣构类。因而， 椭圆曲线密码才被看好，也就被认为是新一代公钥密码系统。 本小节以上的说明与后面的定义和定理选自文献 7 】。 定义2 2 3 1 国 咖域k = 6 聃，或表示为，。上的椭圆曲线e 是点的集合 e t k ) ，e t ( i p = x y ) ：毛ye k 。，+ 口硒7 + n 3 y = # + n + 口# 七q d 定理2 2 3 1 坼厶y 曲魄e w ，d 是f 的无穷例勋训点，则e = 佛u er 御构成加法4 抛妇阼群。 可以证明e c 叼满足以下加法规则： 1 ) p o 产o ：b 2 )p 传 y 0 + c 嘧= p 传b y j ) ，对所有p 往b y j ，既( 目 3 ) 仁川的逆元：当g 是素数时，似纠+ 伍圳= d l q 两蘸南碡法；p ( x l y l ) 。q ( x 2 y ) e 秘0 岱1 x 2 。红i y 1 ) + x 2 y z ) = c x 3 ，y ，) i 1 0 中央民族大学硕士学位论文 口是素数时 x 3 = 好一x 1 x 2 ：y 3 = x 旺l x 3 i ：x 暑! 三盐 茗2 一x 1 g = 2 时 工3 = a 2 + a + x l + 工2 ，y j = 九1 + 工3 ) + x 3 + y 1 ； a = 2 三盐 工2 + 石l 镪点( x 3 y 3 ) = 2 ( x 1 y l 6 ) 交换律仁j ，_ ) ，+ 阢，) ，2 ) = 协，y z j + 仁j ，y jj 伊+ q = q + 爿 设p 缸l ，y 珐q 扛2 ，y z j 是e 上任意两点，阢，y 彭是p + q 的值，在图中表示如下： 一冬 二 一一二游 7 ，7 l ： 弘_ - r 、 ，。、 、- ，+ q、。， 、 ， 图2 2 椭圆曲线 定义2 2 0 2 雄，计钮c 印，如果存在最小的整数n ，使得竹p = 0 k ，则n 称 为点p 的阶。 定义2 2 3 3e 阳上有理点的个数称为椭圆曲线的阶，记做托。，则有： 鲫= 口+ j f ，其中( fs2 q ) 。如果秒，则e 称为超奇异的椭圆曲线，否则称 为非超奇异的椭圆曲线。 定理2 2 3 2 设域k 包含q 个元素，则i 挣e 似) 一q j i = 2 g 目前利用鼢d d ，算法计算把可以在多项式时间内得出结果。所以利用椭 圆曲线的阶构造安全曲线在计算上是可行的。 定义2 2 - 3 4 ( 幻是非超奇异加册5 印e 朋跏g “胁，) 椭圆曲线，当口= ? 时，d ； 中央民族大学硕士学位论文 当g 是素数时，口2 3 + 2 7 口6 2 - o 。 ( 二) 椭圆曲线上的e i g 啪a l 密码体制 设消息m 已嵌入到e 上一点q 。 1 创建密钥 s t e p l 选择p & 脚2 随机选取d q 牲伊一为私钥，计算妒( 把伊口) 为曲线上点的个数) 印3 公开公钥舻。 2 加密 随机选取整数七，计算密文 c i = k b 和c 2 = q + k 妤) 。 3 解密 密文 ，c 2 ) ，计算q = c 2 一工c 。，从q 中恢复明文小。 第三节数字签名基本理论 数字签名是现实生活中对文件的手写签名的一种电子模拟。它的主要功能是 实现用户对电子消息的认证。数字签名方案普遍都是基于某个公钥密码体制，签 名者用自己的私钥对消息进行签名，验证者用相应的公钥对签名进行验证。数字 签名与公钥加密一样都是用单向陷门函数确保其安全性。现阶段，大多数的数字 签名依赖的是各种计算困难问题，如大数分解难题、离散对数难题等。 一、数字签名的一般性质 数字签名与传统的签名相比有许多优点：首先，在数字签名中签名与消息是 分丌的，需要一种方法将签名与消息绑定在一起，而在传统的手写签名中，签名 是被签名的消息的一部分；其次，在签名验证的方法上，数字签名利用一种公丌 的方法对签名进行验证，任何人都可以对签名进行验证，而传统手写签名的验证 须山具有专门鉴别知识的人来鉴别；最后，在数字签名中，有效签名的复制同样 是有效的，而传统的手写的签名中，签名的复制是无效的。 数字签名作为保障信息安全的手段之一，可以解决冒充、篡改、重放和抵赖 。中央民族大学硕士学位论文 等问题。数字签名必须具有以下的性质1 2 】： 1 防冒充其他人不能伪造对消息的签名，因为私有密钥只有签名者自己知 道，所以其他人不能伪造出正确的签名结果。要求私钥的持有人保存好自己的私 钥。 2 防篡改对于数字签名，签名和原有文件己经形成一个混合的整体数据， 不能篡改，从而保证了数据的完整性。 3 防重放在数字签名中，如果采用了对签名报文添加流水号、时戳等技术， 可以防止重放攻击。 4 防抵赖数字签名可以鉴别身份，不可能冒充伪造。签名者无法对自己作 过的签名抵赖。要防止接收者的抵赖，在数字签名体制中，要求接收者返回一个 自己签名的表示收到的报文，给对方或者是第三方，或者引入第三方仲裁机制。 这样，双方均不可抵赖。 s 。机密往有了枕密牲的保证，截取攻击就不会成功了，对要签名豹消息进 行适合的加密操作来保证机密性，这些涉及到加密或签密理论。 二、数字签名的形式化定义与分类 数字签名一般包括三个过程：系统的初始化过程，签名过程，验证过程。初 始化过程中要产生方案中用到的参数。签名过程是要利用给定的算法对消息产 生签名s 培伸，。这种签名过程可以公开也可以不公开。签名验证过程中验证者要 利用公开的验证方法对给定的消息的签名进行验证，得出签名的有效性。 以下是形式化定义： 1 系统的初始化 基本参数似s k & g 陋呦肘：消息集合：s ：签名集合：k ：密钥集合；田g ： 签名算法集合；陋r ：验证算法集合。 2 签名产生与验证过程 对于任意七k ，有签署算法s 讯e 研g ，且有对应的验证算法w h 陋r ， 对每一个j 堙 jm 一5 性靠二m s 一( 真，假) 。满足条件：任意! 肼，y 5 ， 签名为j 喀，验证为： ，、f 真，牵钞= s 喀o ) w 7 五圳2 1 假，劫，s 喀o ) 中央民族大学硕士学位论文 数字签名的分类方法有很多种，在这里我们把常见的分类列举出来【3 1 。 从接收者验证签名的方式可将数字签名分为直接数字签名和仲裁数字签名。 在直接数字签名中，签名者直接把签名消息发送给接收者，接收者无需求助于第 三方就能验证签名。而在仲裁签名中，签名者把签名消息经由被称为仲裁者的第 三方发送给接收者，接收者不能直接验证签名，签名的合法性是通过仲裁者作为 中介来保证的，也就是说接收者要验证签名必须与仲裁者合作。 从计算能力上来分，可将数字签名分为无条件安全和计算上安全。现有的数 字签名大部分是计算上安全的。而所谓的计算上安全的数字签名是指伪造数字签 名在计算上是不可行的。无条件安全的数字签名指无论花费多大的时空代价都无 法伪造数字签名。在理论上，无条件安全的数字签名在许多应用中能代替计算上 安全的数字签名，但在实际应用中是不会太有效而不能被应用，这是因为这种数 字签名需要一个复杂的交互式密钥生成协议，而且签名很长。 扶签名者在一个数字签名方案中所能签署的消息的个数来分，可分为一次数 字签名和非一次数字签名。一次数字签名方案只能签署一个消息，若签署两个或 两个以上不同的消息，伪造者就能够伪造签名。一次数字签名方案类似于一次一 密密码方案，往往具有很强的安全性。 根据数字签名方案中的验证方程是隐式还是显式，可将数字签名分为隐式数 字签名和显式数字签名。现有的数字签名方案大部分为显式数字签名。 根据数字签名基于的数学难题，可以分为基于离散对数问题的签名方案和基 于大数分解问题的签名方案。基于离散对数的签名方案是数字签名体制中最为常 见的一类，如e f g 缸m 口f 签名方案，d 钥签名方案，o 肌。幻签名方案。基于大 数分解问题的签名方案有r 蜘签名方案，冗n f 一肋口m 一签名方案， g “f f f d “一q “括印“口把r 签名方案。 近几年来，随着数字签名发展的深入，出现了一些特殊用途的数字签名，习 惯上我们把他们与一般常见的普通数字签名相区别，称为特殊数字签名。本文正 是借鉴普通数字签名，研究一些特殊数字签名，将在第三章专门列出。 三、普通数字签名方案 由于签名的目的不同，出现了很多类型的普通数字签名，并且新的方案层出 不穷，同时也在接受着时间的检验。但是在这些签名方案中，羊些数字签名力+ 案 中央民族大学硕士学位论文 所采用的思想方法与技巧都很经典，常常被其他签名方案所借鉴，本节就列举几 个经典的签名方案。 ( 一) e f g 册m j 数字签名体制 目g 缸拢口j 签名方案【8 l 是在1 9 8 5 年由z z 6 矗槐口j 提出的，它是基于离散对数 问题眦p ) 且主要是为数字签名的目的而设计的，是继足妫之后最著名的数字签 名方案。在其后，有许多对尉6 钮州口j 进行改进和推广的各种方案；如：协m 方 案1 9 1 、爿m y 方案、阮h z e 加方案、g 0 团n 3 4 j d 方案和由美国 牺r 提出的著名 d s s d i d 方案。1 9 9 4 年，胁m 等人对剧g 矗以及其类似的方案进行分析总结， 给出了1 8 个安全可行的方案，称之为“广义e f g h 卅口j 签名方案”。 e f 6 钮州n j 签名方案描述如下： l _ 密钥生成过程 & 印j 选取大素数p 和占z 。的一个生成元，并把a g 公开； & 印2 随机选取整数工口s z p 一动，计算) ，= 矿棚口d p ，y 是公钥，x 是私钥。 2 数字签名生成过程 设m z 。是待签名的消息，秘密随机选取一个整数七但s 七s p - 到，对消息卅 的签名为：蹰俐= f y ，副z ，+ z ，_ l ，其中 y = g 小。d p ，6 = 阻伸) z r j 七7 m 耐p j 为安全散列函数) 。 3 数字签名的验证 对于消息m z ，+ ，r y ，6 ) z p + x z p _ l ，如果_ ) ，7 y6 - g ”小o d p ，则r r ，6 ) 为 消息班的有效签名。 因为6 = 删协砂xrj t 。m 口d 函 ，可得t 6 + z y = h f ，一m 耐p 一 因此如果 ( y ，6 ) z ，z 川是消息卅z ，的正确签名则一定有y7 y6 = g 。7 9 ”卅谢p j j = 占。7 + ，z o d ( p - j j = g h 佃，竹o dp - j j a 在e f g 缸m 口f 签名方案中，签名的过程中需要保密密钥x 和一个秘密的随机数 ，签名的验证只需要公丌的参数。 ( 二) 尼跗数字签名体制 兄朝数字签名体制是由r f v 部f ，肋口卅一和爿d 洲n 月联合提出，是在r l 朔公钥 中央民族大学硕士学位论文 密码系统上建立的一个重要的签名体制。 兄蜘数字签名体制描述如下： l - 密钥生成过程 挚j 随机选取大整数抖警) q ，其中p 和碍是大素数，积) 表示n 的欧拉函 数值，即例= p 一 向- ，甩公开，妒( n ) 保密； & 印2 随机选取正整数j = 2 脚； 却2 随机选择g z ：且g9 爿d d 川； & 簟3 用户的秘密选择密钥为工，j q ( q ： 节彳用户的公开密钥为y ，y = g 。细谢纠 2 数字签名的生成过程 对于待签名的消息朋签名者进行以下步骤： 叩j 选择随机数t ，j t 目，计算出r = g 细谢纠； s t e p 2 计算啦e = h r ，m ) ； s t e p 3 计算出s = xe + k ( m o dq ) 。 以亿叫作为生成的数字签名。 3 数字签名验证过程 数字签名的收方在收到消息m 和数字签名f e ，印后，先计算r kg5 _ y 一川蒯p ， 然后计算h 仃：卅j ，并按下式验证 娩r 也i e s 1 ，m ) = t r u e h t m = e 中央民族大学硕士学位论文 这个签名体制的正确性可以由以下等式证明： r f ig sy 4 2 9 “5 9k 两( m o d p l ( 四) 砌f - 鼬4 埘扣数宇签名体制 1 密钥生成过程 选择玎是两个大素数p 和目的乘积：七是一个固定常数- 产生用户公钥y “) ，2 ， y t 和私镇x 1 。x 2 ，x k ，满跫x t = y 严m o d p ，其中i - i 2 ，k 2 数字签名的生成过程 5 跆p j 用户随机选取一个正整数f 和f 个j 到以之间的随机整数：r ，n ， 计算r = r f 2 m d d 几，其中= j ，2 ，f ； 野印2 计算胁曲单向函数i l 帆硒，飓，黝得到一个位序列，依次取出该序列 的前七x f 个比特值扫m j 6 j 。，6 2 j ，b 。，； t 潮对j j s f ，计算s - o n 曩m 枷牲 以他j j ，b n j b 2 j ，b ，知h ”，k ) ，臼，s j 作为消息m 的数字签名。 3 数字签名验证过程 验证者根据签名先计算 r 1 吣，2 ：i _ ) ，r 甜，l 其中川夕”j 再计算的珥r 。，r ：，r ) ，验证b ，6 m 6 弘如，是否依次是相 应的前七地个比特值。 ( 五) 酝龇一勿姗球g 衙签名体戳 1 密钥生成过程 s 印jn = 朋，其中p 和g 是两个秘密的大素数； & 印2 整数y 满足g c d m p - 向一驯= j ； & 印3 用户的秘密密钥是工ez ：； 日印4 用户的公丌密钥是y z ：，且x = ，卅d d h 。 2 数字签名的生成过程 对于待签名的消息m ，用户进行以下步骤： 中央民族大学硕士学位论文 印j 随机选择一个数七z ：，计算出r = 阳耐州； 印2 计算出散列值p = 豳饥刁，且使j e ( p ；否则，重新进行印j 印3 计算出5 = 屯，州耐，l 。 以向砂作为对m 的数字签名。 3 数字签名的验证过程 数字签名的收方在收到消息，l 和数字签名化一后，用以下步骤来验证 印j 计算出，7 = ，咖d d n ； 印2 计算出7 = 聊巩丁7j ； 舰印验证砌o ；他站州= 胁憎e 7=e 这个签名体制的正确性可以由以下等式证明 t = ，矿，l 。d n = ( k p 矿，l o d n = p w y r m o d n = b m o d n = t 中央民族大学硕士学位论文 第三章特殊数字签名体制 前面已经介绍了数字签名的一些基本知识，我们知道一个常规的数字签名是 手写签名的电子模拟实现，它能对所签名的消息起到防篡改、防抵赖和确认真伪 等作用。