（计算数学专业论文）盲签名方案研究及其应用.pdf

摘要 盲签名方案研究及其应用 作者简介：程征，男，1 9 7 9 年4 月生，师从成都理工大学魏贵民教授，2 0 0 8 年0 6 月毕业于成都理工大学计算数学专业，获得理学硕士学位。 摘要 随着计算机网络技术和信息技术的迅速发展，信息系统的安全问题变得越来 越重要。数字签名具备消息认证、身份认证、完整性认证、可鉴别和加密等多种 功能的一项信息安全技术在计算机网络安全中占有重要的地位。随着签名技术在 军事、通信、电子商务等领域的深入应用，普通的数字签名己无法满足人们的特 殊需要，于是以数字签名为基础的具有特殊用途的盲签名方案成为本文研究的主 题。 盲签名作为一种特殊类型的数字签名，具有保障签名申请者的匿名性和保护 被签名消息的隐蔽性的功能，所以在电子现金系统和电子选举系统中有着广泛的 应用前景。本文主要围绕和椭圆曲线密码体制相关的盲签名理论研究和应用展 开。作者在阅读大量国内外文献的基础上，以结合盲签名方案和其它数字签名体 制为主要研究方法，在盲签名方案设计及其应用方面作了一些有益的探索和尝 试，主要取得了以下的研究成果： n 1 在分析椭圆曲线的数字签名和现有盲签名方案的基础上，结合两者特性， 构造了一种新的基于椭圆曲线的盲签名方案，并对其进行了理论证明和安全性分 析。该方案是一种强盲签名方案。 ( 2 ) 对赵泽茂提出的基于多元线性变换的代理盲签名方案进行了分析，并将 其平移到椭圆曲线上，得到一个基于椭圆曲线代理盲签名的实现方案。 ( 3 ) 在分析现有部份盲签名方案的基础上，给出一种新的基于椭圆曲线的部 份盲签名方案，并对其进行了理论证明和安全性分析。 ( 4 ) 结合双线性映射构造了一种新的多重部份盲签名方案。新方案能实现多 个签名人同时对盲化的消息实施签名，并且可以同时满足盲性和不可伪造性。并 同时具有多重盲签名和部份盲签名的特性。 a ) 介绍了电子商务的相关知识，并将盲签名方案具体应用到电子现金中， 提出了一个新的电子现金方案，有力地说明了盲签名技术有较大的实际应用价 值。 关键词：盲签名椭圆曲线双线性映射电子现金电子选举 成都理工大学硕士学位论文 r e s e a r c ha n d a p p l i c a t i o no f b l i n ds i g n a t u r e i i i t r o d u c t j o no ft l l ea u t h o f ： c h e n g z h e n 岛m a l e ，w a sb o m i na p 一，1 9 7 9w h o s e t u t o rw a sp r o f c s s o rw c ig i l i - m i l l h e 伊a d u a t e d 舶mc h e n g d uu n i v e r s i t yo f 毗h n o l o g yi nc o m p u t j n g m a t h e m a t i c sm a j o r 觚dw a s 掣a n t e dt h em a s t c rd e g r c ei n j u n e 2 0 0 8 ，k b s t r a c t w i t t lt l l ed e v e l o p m e n to fc o m p u t e rn e t w o r ka n di n f o 加a t i o nt e c h n o l o 舒t h e s e c l l r i t yi s 鲫eo fi i l f o 皿a t i o ns y s t e mb e c o m e sm o r ea n d m o r ei m p o n a n t t h ed i 酉t a l s i 印a t u r e ，w h i c hh 镐t i l ep r o p c n yo fa u t h e n t i c a t i o n ，i n t e 鲥t y ，n o n - r e p u d j a t i o na n d e n c r y p t i 咖w i l hd e e p l y 印p l y i n gi n t om i l i t a 啪c o m m u n j c a t j o na n de 。c o m m e r c e ， n o m a ld i 西t a ls i g a t u r ec a n ts a t i s f ys p e d a lr e q u i r e m e n to fp e o p l e t h e r c f o r e ， s p e c j a lb l j n dd i g i t a ls i g n a t u r cs c h e m e s ，w h j c ha r eo nt h eb a s i so f d i 百t a ls i g n a t u f e a r c t l l ef o c u so ft h i sp a p e r b l i n ds i g l l a t u r cc a ni n s u r es i g i l i n gr e q u e s t c r sa n o n y m i l ya n dp r o t c c tc o 玎c e a lo f s i g n e dm e s s a g c s t 1 l u si th a s aw i d ep r o s p e c ti nt h ee l e c t r o n i cc a s ha n de l e c t f o n i c v o t i n gs y s t 唧s ht h i sp a p e f ，w em a i n l yd i s c l i s sb l i n ds i 舯a t u r e t h c o r yt h a tb a s e d e l l i p i t cc u r v ec r y p t o s y s t e m sa n dj t sa p p l i c a t i o n t 1 l ew r i t e r h a sm a d es o m ep “ g r e s s j l lb l i n ds i 伊a t u r eb yb a s i n go t h e rd i 舀t a ls i 印a t u r ea 】9 0 r i t l l m 粕df c a d i n g1 a r g en u m b e r s o fr c l a t e dl i t c r a t u r 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 hr e s u l t s ： ( 1 ) i nt h es t u d y ，w er e v i e wt h ee l l i p i t cc u r v ed i 舀t a ls i g n a t u r ea l g o r i t t l l n 如dt h e v a r i o u sb l i n ds i 印a t u r es c h e m e s a n dw em a k ead e s c r i p t i o na n d 锄a l y s i so ft h e i r c h 盯a c t e r i s t i c s f u n h e m o r e ，w ep r o p o s ean e ws t m n gb l i n ds i g n a t u r es c h e m eb a s e d 衄e c d s a nh 弱t h cg o o dc h a r a n e r i s t i c sb o t ho f b l i n ds i g n a t u f ca n de l l i p i t cc i l r v e c r y p t o s y s t e m ( 2 ) 1 1 1 m u g l lt h e 锄a l y s i so fz h a oz e m a o sb l j n ds i 印a t u r es c h e m eb a s e do n m u l t i 1 i n e a rt 啪s f o 皿f o n n u l a ，w em o v et h es c h e m ei n t oe l l i p i t cc u f v ea n dg e ta i m p l e m e n t a t i o no fi l ( 3 ) 1 1 l r o u 曲t h ea n a l y s i so fv a r i o u sp a t i a lb l j n ds i 鲫a t u r es c h e m e s ，an c wp a t i a l b l i i l ds i g n a t u r cs c h e m eb a s e do ne l l i p i t cc l l r v ei sp r o p o s e d 1 th a st h ec h a f a c t e r i s t i c s o fb l i n ds i g n a t l i r ca n de a s ya l g o r i t h m ( 4 ) an e wm u l t i b l i n ds i g n a t u r es c h e m ei sp r o p o s e db yu s i n gb i l i n e a rm 印 m 蛆ys i 弘a e 巧c 趾s i 印ab l i n d e dm e s s a g ca ts a m et i m ei nt h i ss c h e m e 姐d t h es i z e o ft h ed j 百t a ls i 印a t u r ci su c h a i l g e a b l e t h es c h e m eh a sf i i n c t i o 璐o fp r o x yb l i n d s i 印a t u r e 柚dm u l t i b l i i l ds j g n a t u r e ( 5 ) 1 卫ep r i m a r yk o w l e d g e s0 ft h ee l e c t r o l l i cc a s h 孤de i e c t m n i cv o t i n ga 砖 i n t r 硼u c c d t 1 l e nt l l eb l i n ds i 印a t u r es c h e m ei sa p p l j e dt 0t h ee l e d m i ce a s h ，舳m w h i c hw ec a i ik n o wt h ea p p l i c a t i o nv a i u eo fb l i n ds i g n a t u r e k e y w o r d s ：b l i n ds i 印a t i l r ee l l i p 雠c u r v e b i l i n e a rm a pe l e c t r o n i cc a s h e l e c t r o n i cv o t i n g l l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得虞壑堡王盍堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：荔乞 扩 加$ 年f 月乃日 学位论文版权使用授权书 本学位论文作者完全了解盛都堡王太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盛壑堡兰太堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 1 ， 学位论文作者签名：屯 侈 学位论文作者导师签名： ；j 蔓苁l ： 卯8 年 厂 月，弓 日 第1 章引言 1 1 信息安全 第1 章引言 随着计算机网络技术和各种信息技术的迅速发展，人类社会已经步入信息时 代，先进的网络信息技术为我们带来了更加便捷、快速的信息交流方式。尤其是 因特网的广泛普及，将人们的日常生活推向了网络，对我们的社会生活产生了革 命性的影响，同时也极大地推动了生产力发展。在此过程中，信息成为最宝贵的 资源，并且可以转换为其它资源。人们可以不受时间和空问的限制，在世界的任 何角落获取想要的信息资源或是与任何个人、组织进行信息交流。同时，极其海 量的信息( 包括政治的，经济的，文化的，军事的等等1 也使我们应接不暇。 信息安全技术在信息化迅速发展的今天己进入了高速发展的新时期，形成了 密码技术、可信计算技术、电磁辐射泄露防护技术、系统入侵检测技术和计算机 病毒检测消除技术等多个安全防护技术门类。所谓信息安全是指信息的五要素， 即信息的保密性( c o n f i d e n t i a l i t y ) 、完整性( i n t e g r i t y ) 、可用性( a v a i l a b i l i t y ) 、可控 性( c o m r o l l a b l i t y ) 与可审查性。保密性就是对抗对手的被动攻击，保证信息不泄 漏给未经授权的人。完整性就是对抗对手主动攻击，防止信息被未经授权的篡改。 可用性就是保证信息及信息系统确实为授权使用者所用。可控性就是对信息及信 息系统实施安全监控。可审查性是指对出现的网络安全问题提供调查的依据和手 段。 在网络和信息技术给我们带来巨大的经济利益和便利的同时，遍布全球的黑 客，利用网络和系统漏洞，肆意攻击各类商业和政府网站，造成巨大的经济损失 和安全问题。机密信息在网络上被泄露、篡改和假冒，计算机病毒和垃圾邮件肆 意传播，不良信息传播给青少年的成长带来负面影响，利用计算机犯罪呈上升趋 势。网络信息安全问题不仅仅是一个技术问题，而且严重威胁到我国政治、军事、 经济、文化等各方面的安全，还将使国家处于信息战和经济金融风险的威胁之中， 网络信息安全已成为亟待解决的影响国家大局和长远利益的关键问题之一。 数字签名作为一种关键的信息安全对抗技术得到了广泛发展和应用。数字签 名具备消息认证、身份认证、完整性认证、可审查性等多种功能。它是实现信息 安全的重要工具之一，也是现代密码学的主要研究内容之一。 成都理工大学硕士学位论文 1 2 数字签名 在传统的商业活动中，书面文件的亲笔签名或印章是用来规定契约性责任 的。签名或印章起到认证、核准、生效的作用。手写签名是可信的，是不能伪造 的和可以鉴定的。根据亲笔签名或印章来证明其真实性，使之能产生法律效力。 但随着社会信息化发展，在网络环境中，信息的发送方和接收方需要存储和传输 大量信息。传统的手写签名受到时间和空间的限制，因而需要电子替代物一数字 签名，在1 9 7 6 年由d i 师e 和h e l l m 锄在著名的密码学的新方向【1 1 一文中第 一次提出了公钥密码体制新思想，基于此的数字签名技术也随之产生。在电子商 务活动中，传送的文件是通过数字签名来证明当事人身份与数据真实性的。数据 加密是保护数据的最基本方法，但也只能防止第三者获得真实数据，它不能保证 通信双方的相互欺骗。数字签名则可以解决伪造、否认、冒充和篡改等问题。实 现了网络身份识别认证、网络资源授权等要求。 数字签名技术的研究与使用，拓宽了密码学的研究范围和领域，在网络通信 身份认证中占有独特的地位。同时数字签名技术已应用到证券、银行、电子商务、 数据库安全、身份认证、电子选举等方面，应用前景广阔。 1 2 1 数字签名的概念 一般的数字签名方案由三部份组成：系统初始化、签名产生、签名验证。首 先，系统初始化过程产生数字签名方案所用到的一切参数；第二，签名产生过程 中，签名者利用签名算法对给定的消息进行签名；最后，签名验证过程中，接收 者利用公开的验证算法对给定消息的签名进行验证，从而判断签名是否有效。下 面给出数字签名的形式化定义【2 】： n 1 系统初始化过程 产生签名方案中的基本参数( m ，s ，k ，s i g ，v l 狼) ，其中： 1 1m 是消息的有限集； s 是签名的有限集； 3 ) k 是密钥的有限集，包括私钥s k 和公钥p k ； 4 ) s i g 是签名算法的有限集； 5 ) v e r 是验证算法的有限集。 ( 2 ) 签名产生过程 对于密钥集合k ，相应的签名算法为s 喀。册，咖；：肘一s 对任意的消 息珊m ，有s s 辔。( m ) ，则s s 为消息m 的签名，将( 】咀，s ) 发送给接收者。 2 第1 章引言 ( 3 ) 签名验证过程 对于密钥集合k ，有签名验证算法 唧：m s - 死阳，肋缸订 吣，- 蒜裟， 接收者收到，s ) 后，计算v b ，k o ，y ) ，若w k ( ) ，) 一n 旭，则签名有效；否 则，签名无效。 1 2 2 数字签名的分类 一个安全有效的数字签名方案应具有以下几个功能：机密性、完整性、身份 认证、防伪造、防抵赖、防重放攻击。根据不同的标准，数字签名可以分为以下 几类： f 1 1 基于数学难题的分类 根据数字签名方案所基于的数学难题，可以将其分为基于整数因子分解问题 ( i n t e g e rf a c t o r i z a t i o np r o b l e m ) 类的数字签名方案；基于离散对数问题( d i s c r c t e l o g a r j t h mp m b l e m ) 类的；基于椭圆曲线离散对数问题( e l l i p t i cc u n 肾d i s c r e t e h g a f i t h mp r o b i 锄) 类的。r s a 数字签名方案是基于整数因子分解问题的，d s a 、 e l g 锄a l 、s c h n o 玎等数字签名方案是基于离散对数问题的，而e c d s a 数字签名 方案是基于椭圆曲线离散对数问题的，还有基于二次剩余问题的签名方案等。 ( 2 ) 基于签名验证方式的分类 根据接收者验证签名的方式可分为真数字签名( 仃u ed i 画t a ls i 鲫t i l r c ) 和仲裁 数字签名( a r b i t m t e dd i 舀t a ls i 印a t u r c ) 【3 】两类。在真数字签名中，签名者直接把签 名消息发送给接收者，接收者无需求助于第三方就能验证签名：而在仲裁数字签 名中，签名者把签名消息经由可信第三方( 仲裁者) 发送给接收者，接收者不能直 接验证签名，签名的合法性是通过仲裁者作为媒介来保证，也就是说接收者要验 证签名必须与仲裁者合作。 ( 3 ) 基于数字签名的特性和功能的分类 根据数字签名的特性和功能，可以将其分为普通数字签名和具有特殊性质的 数字签名【4 】。普通数字签名包括r s a 数字签名、e l g a m a l 数字签名、s c h n o r r 数 字签名、美国的数字签名标准，算法( d s s d s a ) 、椭圆曲线数字签名c d s a ) 、有 限自动机数字签名等。特殊数字签名包括盲签名、代理签名、多重签名、群签名、 环签名等。还有基于前向安全技术和双线性对技术的签名方案等，此外，还有门 限共享、失败一停止签名、不可否认签名、零知识证明等许多分支，都与具体的 3 成都理工大学硕士学位论文 应用环境有着密切的关系。其中，盲签名是本文所要研究论述的主要内容。 1 3 盲签名的研究背景及发展现状 事物的产生都是由时代需求决定的，盲签名作为一类特殊的数字签名，它的 产生和发展是在科技进步和网络技术快速发展的前提下，数字签名要实现功熊多 样化的需求下，迅速发展起来的。它作为一项重要的信息安全技术，基本作用 是在某些特殊情况下，消息的拥有者让签名者对消息进行签名而又不知道消息的 具体内容同时签名者也不想了解所签消息的具体内容，他只是想让人们知道他 曾经签署过这个消息。 1 9 8 2 年，c h a u m 首先提出了盲签名的概念【5 】。在此之后，盲签名便因为其 潜在的应用价值得到了密码学界的极大关注。人们分别基于因子分解问题、离散 对数问题、二次剩余问题、椭圆曲线密码体制等傲了许多努力相继提出了各种性 能良好的盲签名方案，如r s a 盲签名方案、e i g a m a l 盲签名方案、s c h n o r r 盲签 名方案、n y b e r g r u e p p e l 盲签名方案、椭圆曲线盲签名方案等。 盲签名在其发展过程中，大致可以划分为两个阶段： 第一个阶段是1 9 8 2 年9 0 年代初期：盲签名的提出与初步探索阶段。1 9 8 2 年，c h a u m 提出了r s a 盲签名方案，随后又提出了一个无法追踪支付系统中的 盲签名方案。1 9 9 3 年，o k a m o t o 提出了第一个基于离散对数的盲签名方案。1 9 9 4 年c a m e n i s c h 等提出的基于d s a 和n y b c r g - r u e p p e l 盲签名协议。 第二阶段是9 0 年代中期至今，学者们研究的重点主要是在两个方面，第一 是各种特殊场合下面的盲签名协议，如b r a n d s 提出的受限制的盲签名及其设计 的电子货币方案【6 】s t a d l e r 等提出的公平盲签名方案【7 】，f a n 等提出的基于二次 剩余问题的部分盲方案【8 】，以及相关的一些电子货币，电子选举协议的设计。第 二是盲签名协议与其他密码协议或方法的混合，如可证明安全性的引入，基于身 份体系的引入，椭圆曲线算法的引入，群签名与盲签名结合的群盲签名，代理签 名与盲签名结合的代理盲签名等。如2 0 0 1 年，c h i e n 等将部分盲签名应用于r s a 上，提出了一种低计算复杂度的部分盲签名方案。钟鸣等提出了一种基于比特承 诺的盲签名方案，张方国等提出了两种基于椭圆曲线的盲签名方案。另外，在 2 0 0 3 年，h i 和a w a s t h i 【9 】提出了一种代理盲签名方案，改方案比1 趾的方案的 计算更简单。2 0 0 4 年，吴克力【1 0 】提出了一种公平的群盲签名方案，改方案结合 已有的公平盲签名和群盲签名方法，对一种群盲签名增添公平性而得到。 目前，盲签名技术已经被广泛地应用于电子现金、电子选举、电子拍卖等领 域中，本文第五章将重点讨论盲签名在电子现：衾领域的应用。另外，盲签名在匿 名证券交易、口令认证、遗嘱签署、c a 证书的颁发和密钥分配等领域也有重要 4 第1 章引言 的应用。总之，凡是那些要求考虑用户匿名性的应用场所，盲签名技术都将发挥 重要的作用。 1 4 椭圆曲线密码体制的理论研究现状 椭圆曲线( e l l i p t i cq l e ) 是代数几何的一个分支，在过去的1 5 0 多年里得到 了广泛的研究，并形成了成熟完善的理论。将有限域上的椭圆曲线应用于己存在 的d j f ! f i c h e l i m 柚密钥分配体制及e l g 锄a l 体制中，是椭圆曲线密码体制的开端。 椭圆曲线公钥密码是目前己知的公钥密码中，对每一比特所提供加密强度最高、 处理速度最快、开销最低的一种体制，是椭圆曲线理论在密码学上一次全新的应 用。关于椭圆曲线密码的各类研究成果层出不穷，国内外学者提出了许多实现椭 圆曲线密码体制的快速算法，其中具有代表性的有k o b l i t z 、m i l l e r 、m e n e z e s 、 v a n s t o n e 、s i l v c 埘a n 等人，他们提出了许多方法，且仍在研究中。如今椭圆曲线 密码体制的研究日渐成熟，许多标准化组织也在着手制定关于椭圆曲线密码体制 的相关标准。如i e e e 制定的公钥密码标准p 1 3 6 3 ，1 9 9 9 年a n s l 制定的椭圆曲 线数字签名算法( e c d s a ) 标准a n s h 9 6 2 【1 1 】等等。其中，a n s k 9 6 2 标准的发布 成为椭圆曲线密码体制标准化的一个重要里程碑。此外，1 5 叩e c l 4 8 8 8 、l e t f 、 朋m f o m m 、c i n i e o m l o 等标准相继被颁布。电子商务安全协议s e t ( s e c u r c e l e c t r o l l i ct r a l l s a c t i o n s l 的制定者已经把椭圆曲线密码体制作为下一代s e t 协议 中缺省的公钥密码算法。同时，为了鼓励开发基于椭圆曲线密码体制的应用产品， 几个国际标准化组织也把椭圆曲线密码体制作为新的信息安全标准【1 2 】。这将提 高椭圆曲线密码体制在世界范围内的通用性，使椭圆曲线密码体制在全球的广泛 应用成为可能。 国内外学者对椭圆曲线的安全性作了深入的分析研究，一系列基于椭圆曲线 的签名方案被不断提出，如基于椭圆曲线的数字签名方案、基于椭圆曲线的盲签 名方案、基于椭圆曲线的多重盲签名方案、基于椭圆曲线的部分盲签名方案、基 于椭圆曲线的代理签名方案等等。 密码学界普遍认为椭圆曲线密码体制必将成为计算机网络、数据通信、电子 商务，特别是新一代环境受限系统如移动通信系统和智能卡系统的最理想的安全 解决方案。目前，国外已有用椭圆曲线进行加解密和数字签名的产品出现在市场 上。国内也有几家公司和研究机构在做椭圆曲线密码体制的实现，但未发现有比 较成功的产品出现。 5 成都理工大学硕士学位论文 第2 章数学基础和相关密码学知识 2 1 数学基础 盲签名作为一种特殊的数字签名，和数字签名一样要求有较深的数学作为基 础。在理论研究中需要用到许多的数学理论，如数论、近世代数、复杂性理论、 组合论等。本节就论文中所涉及到的相关基础概念做简单介绍。 定义2 1 1 给定一个正整数，如果用m 去除两个整数a 和b 所得的余数 相同，就称a ，b 对模数m 同余，记为口- 6 ( m o d 以) ，并称运算符为咖d 的运算 为模运算。 定理2 1 1 设a 和b 是两个整数( 不同时为零) ，d g c d ，扫) ，则存在整数s 和t 使得口j + 研= d 成立。特殊时，如果a 、b 均为素数，那么存在整数s 和t 使 得口5 + 6 f = 1 。 定理2 1 2 设p 是一个素数，g 是模p 的一个本原元，则有： ( 1 ) 如果n 是整数，那么9 4 。1 m o d p 当且仅当月一o m o d ( p 一1 ) ； ( 2 ) 如果j 和k 都是整数，那么g 一矿( m o d p ) 当且仅当，一七m o d p 一1 ) 。 定义2 1 2 ( 离散对数) 设g = ( g ) 代表由g 生产的q 阶循环群，x 为z ：的元 素，y g 。称满足旷= _ ) ，的最小整数x ，为y g 基于g 的离散对数。 定理2 1 3 ( 整数唯一分解定理) 任一大于1 的整数能表示成素数的乘积， 即对于任一整数日 1 ，有口一a 见以，as p 2s s 只， 其中a ，p 2 巾。是素数。并且若口一鼋】留2 。，口ls 口2s s ， 其中吼，目2 ，目。是素数，则m 一弹，岛= 只o 一1 ，2 ，玎) 。 定义2 1 3 域由个非空集合f 组成，再集合f 中定义了两个二元运算符： “+ ”加法和“，乘法，并满足： ( 1 ) f 关于加法“+ ”是一个交换群，单位元是“o ”，元素a 的逆元是a ； ( 2 ) f 关于乘法“，是一个交换群，单位元是“1 ”，元素a 的逆元是a - 1 ； ( 3 ) ( 分配律) 对任何口，6 ，c ，有口。( 6 + c ) - ( 6 + c ) 口一日6 + 打c ； ( 4 ) ( 无零因子) 对任何4 ，6 ，如果有4 6 = 0 ，则a = 0 或b = o 。 6 第2 章数学基础和相关密码学知识 这样的集合f 称为域，记为 f ，+ ， 。如果f 中只包含有限个元素，则称其 为有限域。 定义2 1 4 单向函数( 0 n e w a y f i l n c t i o n ) 如果一个函数f 满足下面两个条件， 则称之为单向函数： ( 1 ) 对于f 定义域上的x ，可以很容易计算得到f ( x ) ； ( 2 ) 对于f 值域上的y ，要计算得到x ，使之满足f ( x ) = y 现实来说是不可行的。 单向函数计算起来相对容易，但求逆却非常非常困难。陷门单向函数 ( t r 印d o o r e - w a yf u i l c t i o n ) 是有一个秘密陷门的一类特殊的单向函数。拆开手表 是一个很好的陷门单向函数的说明例子。把手表拆成数百个小零件时很容易，反 过来把这些零件重新组装成能够工作的表却非常困难。但通过秘密消息( 表的装 配指令) ，就很容易把表还原。 定义2 1 5 单向散列函数( 0 n e w a yh a s hf i l n c t i o n ) 单向散列函数又可称为压 缩函数、收缩函数、消息摘要、指纹、密码校验和、消息完整性检验( m i c ) 、操 作检验码( m d c ) 。它是密码学中的一类特殊的函数。单向散列函数h ( x ) 作用于一 任意长度的消息m ，返回一固定长度的散列值i l ：| i l = 日( f ) 。它具有下面的性质： ( 1 ) 给定m ，很容易计算h ： ( 2 ) 给定h ，根据h = h ( m ) 求解m 在计算上是不可行的； ( 3 ) 给定m ，要找到另外一消息m ，使得h ( m = 荫m ) 是不可行的。 性质( 2 ) 和( 3 ) 分别被称为单向性和无冲突性。单向散列函数本身不是一个协 议，却是许多协议的一个基本结构模块，是现代密码学的关键技术之一。单向散 列函数的安全性在于它的单向性。正因为这样，单项散列函数广泛应用于密码学 的各个领域：密码协议、密码算法、数字签名等。 现行的单项散列函数主要有：s n e 丘1 l 算法、n h a s h 算法、m d 4 算法、m d 5 、 s h a 算法1 5 1 等。在2 0 0 4 年8 月1 7 同召开的国际密码学会议上，来自山东大学 的王小云教授破解了一直在国际上被广泛应用的两大密码算法m d s 、s h a 1 ， 引起国际密码学领域的极大反响。 在当前的密码体制中，整数因子分解问题和离散对数问题是两个著名的数学 难题，是许多密码协议和密码算法成立的坚实基础，目前还未有能较好解决上述 数学难题的方法。此外，己公认的安全实用的公钥体制还有椭圆曲线离散对数体 制，它所依据的数学难题是椭圆曲线离散对数问( e c d l p ) 的难解性。本文将在第 三章详细讨论椭圆曲线离散对数问题。 总之，这三类数学难题为密码协议尤其是数字签名的算法设计提供了良好的 数学基础和安全保证。如现在广泛使用的r s a 体制签名方案就是基于整数因子 分解问题提出的，并且被认为是安全性最好的方案之一的e i g a m a l 数字签名算法 7 成都理工大学硕士学位论文 则是基于离散对数问题设计的，而椭圆曲线数字签名算法( e c d s a ) 是基于椭圆曲 线离散对数问题设计的。 2 2 密码学基础 密码学缸y p t o l o g y ) 是研究信息系统安全保密的科学，它包括密码编码学和密 码分析学两个方面。密码编码学( c f y p t o 掣a p h y ) 主要研究对信息( 数据) 进行编码， 实现对信息的隐蔽和保密，以防止信息被纂改和非法使用。密码分析学 ( c r y p t a n a i ”i c s ) 主要研究加密消息的破解，对密码算法、协议等进行分析，可以 看作是密码编码学的反向技术。密码技术是实现信息安全的重要技术。从当前的 密码学体制来看，可分为私钥密码体制和公钥密码体制。其中，公钥密码体制是 密码学的重要组成部分。数字签名技术的基础就是公钥密码体制。 1 9 7 6 年d i 伍e 和h e l l m a n 在他们的著名论文密码学的新方向中创造性地 提出了一种新的密码编码方法，提出了公钥密码的思想，其本质区别于之前所有 的密码方法，用这种方法再进行保密通信时不需要传送密钥。我们称之为公钥密 码体制，其安全性基于大整数因子分解的困难性。公钥密码的出现是密码学历史 上的一次革命。第一个比较完善的公钥密码算法是著名的r s a 算法，它由r i v e s l 、 s h a m i r 和a d l e m a n 三人共同提出的，既能用于加密也能用于数字签名。其安全 性基于大数分解的困难度。目前，比较重要的公钥密码算法还有e i g a m a l 算法和 椭圆曲线密码算法，其安全性均是基于离散对数的难解性。公钥密码之所以区别 于以前的古典密码方法：一是以前的密码算法都基于代换与置换操作而公钥密码 使用数学函数进行变换；二是公钥密码体制将加密和解密功能分开，使用个不同 的密钥( 加密密钥和解密密钥) ，而传统密码算法只有一个密钥。 公钥密码体制有两种模型：一种用于保密通信( 如图1 ) ，即接收方b o b 的公 钥作为加密密钥，再以接收方b o b 的私钥作为解密密钥，从而可实现多个用户 加密的消息只能由一个用户解读；另一种用于消息认证r 如图2 ) ，即以发送方i c c 的私钥作为加密密钥，再以发送方a l i c c 的公钥作为解密密钥，从而可实现由一 个用户加密的消息可由多个用户解读。 公钥密码体制有着传统密码体制无法比拟的优越特性。利用公钥密码体制， 无需在不同的用户之间传输密钥，因为用户的公钥公开，这有效地避免了一些密 钥分配和密钥管理的难题。总之，公钥密码体制为解决计算机网络中的安全提供 了新的理论和技术基础1 3 ，1 4 1 。 8 第2 章数学基础和相关密码学知识 明文 明文 a 保密通信 b 消息认证 图2 1 公钥密码加密、认证模式 9 明文 明文 ( c ) 成都理工大学硕士学位论文 第3 章椭圆曲线密码体制 1 9 8 5 年，n e a lk o b l i t z 【1 6 】和v i c t o rm i l l e r 【1 7 】基于椭圆曲线点群上的离散对数 问题( e c d i j p ) 难解性，分别提出了椭圆曲线密码体制( e c c ) ，随后，人们对椭圆 曲线密码的安全性和实现进行了大量研究。椭圆曲线密码体制是建立在由椭圆曲 线上的点构成a b e l 群所构造的离散对数计算困难性的基础之上的，区别于r s a 密码体制或e i g a m a l 密码体制的数学原理。因为椭圆曲线密码体制要达到同样的 安全强度只需更短的密钥长度，而且椭圆曲线所基于的域的运算复杂度远远小于 传统离散对数的复杂度，其在环境资源受限时较容易实现，所以深入研究椭圆曲 线公钥密码有很大的实际意义。 3 1 椭圆曲线 3 1 1 椭圆曲线的概念 椭圆曲线是由韦尔斯特拉斯( w e i e r s t f a s s ) 方程 y 2 + 口1 ) 9 ，+ 拉3 ) ，置x 3 + 口2 2 2 + 4 4 工+ 4 6( 3 1 ) 在域f 上所确定的平面曲线e 。f 可以是有理数域、实数域、复数域或有限 域。其中5 个系数口，( f = 1 2 ，3 ，4 ，6 ) 是域f 中的元素。是e 的判别式且0 。 满足上面的点( x ，y ) 及一个特殊的无穷远点0 就构成椭圆曲线。 在实际的密码学应用中，我们通常在有限域( 伽罗瓦域) 上研究椭圆曲线e ， 特别是大素数域6 f 国) 和特征为2 的有限域矗f ( 2 卅) 。主要研究和应用的椭圆曲 线方程有两种： ( 1 ) 有限域上的椭圆曲线，其特征值不等于2 或3 ，曲线方程为： y 2 _ 工3 + 甜+ 6 ，( 口，6 ，乱3 + 2 7 6 2 0 )( 3 2 ) ( 2 ) 有限域。上的椭圆曲线，其特征值为2 ，曲线方程为： y 2 + 叫l z 3 + 耐2 + 6 ，( 口，6 ，6 一o )( 3 3 ) 这样的曲线称为非超奇异的，且判别式= b 。 1 0 第3 章椭圆曲线密码体制 3 1 2 椭圆曲线的运算方法【1 8 】 设e 是一个定义在域f 上的椭圆曲线。从几何意义上根据弦切运算法则，e 上的两个点相加得到e 上的第三个点。椭圆曲线的点加和倍点运算的几何表示如 图3 1 所示。点集合e ( f ) 及其这种加法运算构成一个a b e l 群，并且。为其无穷 远点。这个交换群的运算法则用来构建椭圆曲线上相应的运算。下面，分别对两 种情况给出对应于式( 3 2 ) 的简化w b i e r s t r a s s 方程的群运算代数公式： 对于域上的椭圆曲线：) ，2 ；x 3 + 甜+ 6 ，域f 的特征值不等于2 或3 1 ) 单位元。对于所有的p e 妒) ，p + d d + p p 。 2 ) 负元素。若p 一0 ，) ，) e 妒) ，则( x ，y ) + 0 ，一y ) ；d 。记点( x ，一y ) 为一p ， 并称其为p 的负。此外一p 也是e ( f ) 上的一个点，一d = 0 。 3 ) 点加。( 如图3 1 所示) 令p = 瓴，咒) e ( f ) ，q = 如，y ：) e 俨) ，p ，l q ， 贝q p + q 0 3 ，y 3 ) 。 其中， 玛；瞄) 2 一五一和y 3 = ( 丝二丝) ( h 一屯) 一咒 4 ) 倍点。( 如图3 2 所示) 令p 一“，m ) e 俨) ，p 一一p ，则2 p 一( 玛，) ，3 ) 。 其中， 毛：( 垄耋马：一现和儿：0 妥竺) “一而) 一m z y lz y l 对于域上的非超奇异椭圆曲线：y 2 + 叫一，+ 删2 + 6 1 ) 单位元。对于所有的p e ( 。) ，p + o o + p p 。 2 ) 负元素。若p 一 ，y ) e ( 0 ) ，则( 砖) ，) + o ，x + y ) 一o 。记点( x ，x + ) ，) 为 一p ，并称其为p 的负。此外一p 也是e ( 只，) 上的一个点，一d = d 。 3 ) 点加。令p “，y 。) e ( ) ，q = 心，y ：) e ( 0 ) ，p t q ，则 p + q 一瓴，儿) 。 其中， 成都理工大学硕士学位论文 而i a 2 + a + + 屯+ 口和乃a “+ 屯) + 玛+ m ， 4 ) 倍点。令p ；“，h ) e 晖) ，尸_ 一p ，则2 p * ，儿) 。其中， 毛“m 4 j 彳嘻和两一x i + 挑 y 尺一亿，： 。 q = 也，y 2 ) 一7 ； 份i - p ；“，咒卜 点加：p + q 一胄 yr ；也，儿) p 一“，) ，) 万 _ - - ： 一a ； n 7 ： 、 倍点：p + p 一月 图3 1 椭圆曲线运算的几何表示 第3 章椭圆曲线密码体制 3 1 3 椭圆曲线的特。陛 椭圆曲线密码体制是己知公钥密码体制中能提供最高比特强度( s t r e n 醇h p c f b i t ) 的一种公钥密码体制。它与其它公钥密码体制相比密钥更短、安全性更高。 具体特性介绍如下： ( 1 ) 安全性更强 对于e c c 而言，1 6 0 b “长的密钥所具有的安全性和r s a 密码体制中1 0 2 4 b i t 长的密钥所具有的安全性相当，而2 1 0 b i t 长的密钥所具有的安全性与2 0 4 8 b i t 长 的密钥所具有的安全性相当。 f 2 ) 处理速度快 在相同资源下，在相同的安全强度下，e c c 中用1 6 0 b i t 长的密钥进行加、 解密或数字签名要比r s a 密码体制中用1 0 2 4 h “长的密钥快大约1 0 倍。 ( 3 ) 存储占用空间小 e c c 的密钥尺寸和系统参数与r s a 密码体制相比要小得多。这对于加密算 法在资源受限环境中( 智能i c 卡) 的应用具有重要意义。在同等的安全强度下， e c c 所需的密钥长度要远低于r s a 密码体制，这就有效地解决了提高密钥长度 来增强安全强度带来的时间开销和实现困难的问题。 ( 4 ) 带宽要求低 当对长消息进行加解密时，e c c 和r s a 密码体制有相同的带宽要求，但应 用于较短消息时e c c 带宽要求却低得多。而公钥加密系统多用于短消息，例如 用于数字签名和对会话密钥的加密传递。 3 2 椭圆曲线离散对数问题及其安全性 3 2 1 椭圆曲线的离散对数问题( e c d l d 椭圆曲线密码体制是建立在椭圆曲线离散对数问题( e c d i j p ：e i p t i cc u e d i s c r c t el d g a r i t h mp m b l e m ) 求解困难性的基础之上的，它比基于乘法群上的密码 体制相同条件下有更高的安全性。 椭圆曲线离散对数问题( e c d i 即是指：设e ( ) 是定义在有限域上的椭圆 曲线，p ，q ( 只) 为曲线上的两点，其中p 为基点。若存在一整数m 使得q = 胛 ( 这里的m 表示数乘，即m 个p 相加) ，则由整数m 和p 计算o 较容易，而由p 和q 计算出m 是不可行的，则称由p 和o 计算出m 的问题为椭圆曲线离散对数 问题【1 9 】。整数m 称为q 的基于p 的离散对数，表示为m l o g ，q 。 成都理工大学硕士学位论文 3 2 2 攻击现状 目前，求解椭圆曲线离散对数问题( e c d l p ) 的方法可以分成两类：指数计算 法和碰撞搜索法。相对来说最有效的方法( 碰撞法) 是p l l a r d r h o 方法和 p o h l j g - h e l l m