（应用数学专业论文）多接收者签密方案研究.pdf

摘要 论文题目：多接收者签密方案研究 学科专业：应用数学 研究生：娄建军 指导教师：王尚平教授 摘要 签密是在一个逻辑步骤内同时完成数字签名和加密两种功能，其所需的代价一般低于 “先签名后加密”，因而是一种实现既保密又认证的消息传输及存储的理想方法。在许多 情况下，对同一个消息的签密需要同时发送给多个接收者，签密者要求他的签密仅能由他 所指定多个接收者验证真伪，并且每一个接收者都能够独立验证签密的有效性，无需相互 协作，而任何无关的其他人在没有得到签密者或者接收者的帮助下都无法验证签密。 签密在当今社会信息安全技术领域有着广泛的应用背景，例如在电子现金支付系统、 电子拍卖和电子投票等领域。 本文对签密理论作了研究，主要的成果有： ( 1 ) 提出了一个能同时满足保密性，可认证性和不可否认性的一种基于双线性对的 多接收者签密方案，并给出了安全性分析。 ( 2 ) 分析探讨了代理签名的相关技术，并引入签密的基本思想，提出了一个具有多 接收者的代理签密方案。在该方案中每一个接收者都能够独立验证签密的有效性，同时并 分析了该方案的安全性。 关键词：数字签名；签密；基于身份；代理签名 本研究得到以下基金资助 国家自然科学基金( 6 0 2 7 3 0 8 9 ) 陕西省自然科学研究计划资助项目( 2 0 0 5 f 0 2 ) 陕西省教育厅自然科学研究计划资助项目( 0 3 j k l 6 5 ) 西安理工大学科技创新基金( 1 0 8 2 1 0 4 0 2 ) 陕西省教育厅专项科学研究计划资助项目( 0 6 j k 2 1 3 ) t i t i e ：r e s e a r c ho nm u - r e c e i v e i t ss i g n c r y m o n s c h e m e s m a j o r ：a p p l i e dm a t h e m a t i c s a u t h o r ：j a 面n i ll o u s u p e r v i s o r ：p r o f s h a n g p i n gw a n g s i g n c r y p t i o nc a l la c h i e v eb o t ht h es i g n a t u r ea n de n c r y p t i o nf u n c t i o ni nat o g i cs t e pa n di s w i t ht h ec o s tl o w e rt h a nc o h m q o uw a y ”f i r s ts i g n a t u r ea n dt h e ne n c r y p t i o n ”，t h u si sa r ti d e a lw a y t oa c h i e v ei n f o r m a t i o ns t o r a g ea n dt r a n s m i t t e ds e c r e t l ya n dv e r i f i a b l y i ns o m es i t u a t i o na m e s s a g eh e e d st ob es e n tt om o r et h a no n el e g a lr e c i p i e n ta tt h es a r t a et i m e as i g n e re x p e c t sh i s s i g n a t u r et ob ev a l i d a t e do n l yb yt h e s ea p p o i n t e dr e c i p i e n t s e v e r yr e c e i v e ra l s oh o p e sh ec a n e a s i l yv e r i f yt h es i g n c r y p t i o nr e s p e c t i v e l yw i t h o u ta n yo t h e r s h e l p ，b u tt h o s ei r r e l e v a n to n a s 啪n o tw i t h o u tt h es i g n e r so rh i sc o o p e r a t i o n s i g n c r y p t i o nh a sm a n ya p p l i c a t i o n s ，s u c ha si ne l e c t r o n i c a lf u n d st r a n s f e rs y s t e m s ， e l e c t r o n i c a la u c t i o na n de l e c t r o n i c a lv o t i n ge t c t h e f o l l o w i n ga r et h er e s u l t so ft h et h e s i s ： ( 1 ) as i g n c r y p t i o ns c h e m ef r o mb i l i n e a rp a i r i n g si sp r o p o s e d ，w h i c h 啪s a t i s f ys e c u r i t y , v e r i f i a b i l i t ya n dn o n d e n i a b l ea tt h es a m et i m e t h es e c u r i t ya n a l y s i so ft h es c h e m ei sa l s o a n a l y z e d ( 2 ) t h er e l a t e dt e c h n o l o g yo fp r o x ys i g n a t u r ei sa n a l y z e d f i n a l l y , b yi n t r o d u c i n gt h ei d e a o fs i g n c r y p t i o n , w ep r o p o s eap r o x ys i g n c r y p f i o ns c h e m ea n da n a l y z et h es e c u r i t yo ft h e s c h e m e ，i nt h es c h e m e 。e v e r yr e c e i v e r 锄v e r i f yt h es i g n c r y p t i o nr e p e c t i v e l y k e yw o r d s ：d i g i t as i g n a t u r e ；s i g n c r y p t i o n ；i d - b a s e d ；p r o x ys i g n a t u r e 独创性声明 秉敢祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名，垄墼豳磷万月钿 学位论文使用授权声明 本八。= 垄篷l 三在导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为教学和 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) 论文作者签名， 壅盛导师签名： 障弱 峰 第一章绪论 1 绪论 1 1 引言 随着i n t e r a c t 的迅速发展，计算机和通信网络已经广泛应用于社会的各个领域，它已 成为推动人类与社会发展的最强大的动力，是人类最宝贵的财富之一然而，信息网络越 是重要，它就越容易成为攻击的目标。因此。信息安全已成为当今社会十分关注的问题。 信息安全问题是一个复杂的系统工程，它涉及的内容十分广泛。它包括： 保密性：对抗敌手的被动攻击，保证信息不被泄漏给未经授权的用户： 完整性：对抗敌手的主动攻击。防止信息被未经授权的用户篡改； 可用性：保证信息及信息系统确实为授权用户所使用； 可控性：能够对信息及信息系统实施安全监控； 不可否认性：保证信息行为人不能过后否认自己的行为。 因此，信息安全的主要目的之一就是能够保证数字信息的有效性。为了实现数字信息 的保密性使用密码学算法对其进行加密是最有效的办法，为了实现信息的完整性对信息进 行完整性校验，对用户进行身份认证，使用数字签名技术，是当前最实际可行的办法由 此可见，密码学是信息安全的核心技术 密码学的发展为人们提供了保障网络信息安全的核心技术，不仅可以利用密码来保密 所传达的信息，以便只有我们所希望的接收者才能真正获取信息，而且通过密码技术的使 用，使得现实世界的许多事情，诸如签字、订合同、发送收据等都可以通过数字信号来完 成。 密码学的基本思想就是将一种形式的消息交换成另外一种形式的消息，使得非授权方 无法解读真实的消息内容。我们称密码学中用到的各种变换为密码算法，简单的说，如果 一个变换能够将一个有意义的消息( 称为明文) 变换成无意义的信息( 称为密文) ，从而使非 授权人难以从密文读取明文的内容，那么称这个变换为加密算法。如果一个变换能将一个 消息变换成一种。证据一用来证明某个实体对消息内容的认可，那么称这个变换为一个 数字签名算法。数字签名作为密码学和信息安全领域中的重要组成部分，是当前信息安全 研究的热点，在社会生活的各个领域中具有广阔的应用前景。 1 2 数字签名的介绍 在现实生活中，长期以来文件上的手写签名一直被用作签名者身份的证明。这是因为： 签名是可信的；签名是不可伪造的：签名是不可重用的；签名的文件是不可改变的；签名 是不可抵赖的。在未来社会的生活中，电子文档将逐步代替纸质的文件成为信息交流的主 西安理工大学硕士学位论文 体。证明某一个电子文件是某作者所作的有效办法是模拟普通的手写签名在电子文档上进 行电子签名，即在电子化文件添加可以标明自己的一段特征数据来实现签名，使作者可以 通过数字签名表明自己的身份，读者也可以通过数字签名验证作者的身份。 数字签名是对手写签名的模拟，具有以下几个特点： ( 1 ) 不可否认性：签名者事后不能否认签过名； ( 2 ) 不可伪造性：其他人不能伪造签名； ( 3 ) 签名不可重用：签名是文件的一部分，敌手不可能将签名移到其他的文件上。 ( 4 ) 不可抵赖的：签名者事后不能声称他没有签过名。 ( 5 ) 签名文件不可改变：文件签名后，文件不可改变。 1 3 研究背景 近几年来，特别是互联网迅速的发展，为人们提供了更为快捷和方便的交流方式。数 字信息被广泛的在互联网中使用和交流，由于数字信息的存储、处理、传输等过程往往是 在开放的通信网络上进行，所以信息很容易遭受窃听、截取、修改、伪造、重放等来自各 方的各种攻击手段的威胁。因此，与信息技术的高度发展相对应，在信息处理和传输过程 中对其提供相应的安全保护也正成为信息技术发展所必须面对和解决的问题，如何对在网 络上公开传递的各类数据信息进行安全保护，使得数据能够安全的、完整的、可认证的到 达接收方。这使得我们面临严重挑战，同时也因为这些挑战，使得信息安全成为信息社会 急需解决的最重要的问题之一 密码学是信息安全的核心，它能为信息安全提供关键的理论和技术。加密技术是密码 技术中最重要的组成部分之一 ( 1 ) 消息和加密 消息被称为明文。用某种方法伪装消息以隐藏它的内容的过程称为加密。加了密的消 息称为密文，而把密文转变为明文的过程称为解密。图1 - 1 表明了这个过程。 圈1 - 1 加密和解密 ( f i g u r e1 - 1e u c r y p t i o na n dd e c r y p f l o n ) 通常个加密方案涉及到两方，一方是发送方，一方是接收方。当发送方想传输一个 消息时( 或称作明文) ，他首先将它进行加密，形成密文，再将密文送给接收方。当收到 2 第一章绪论 密文后，解密者运用解密算法将原始的明文从密文中恢复出来。加密的目的是使发送方和 接收方在不安全的信道上秘密地通信，这种信道可能是在攻击者的控制之下。该攻击者可 能是通过偷听。甚至是在改变发送方和接收方之间所通信的内容。为了保证攻击者不能获 得密文中的明文信息，需要发送方和接收方拥有攻击者所不知的一些信息。图1 2 说明了 这个过程。 圈1 - 2 密码体制 ( f t 印雌1 - 2o 铘，t o 盯5 t 锄) c 2 ) 算法和密钥 密码算法一般包括加密和解密两个数学函数。( 通常情况下，有两个相关的函数：一 个用作加密，另一个用作解密) 在以下的算法中，设k 表示密钥，置可以是很多数值里的任意值。密钥足的可能值 的范围叫做密钥空间。加密和解密运算都使用这个密钥( 即运算都依赖于密钥，并用k 作 为下标表示) ，这样，加解密函数现在变成： k ( m ) 一c 圾( c ) - m 这些函数具有下面的特性( 见图1 - 3 ) ： 巩峨( 肼) ) - m 图l o 使用一个密钥的加廨密 ( h 弘砷l oe n a 唰i o n o r d e c r t p 吐o n o t m j n g as e c r e t k ，) 西安理工大学硕士学位论文 但是有些算法使用不同的加密密钥和解密密钥( 见图1 - 4 ) ，也就是说加密密钥k 与相 应的解密密钥屹不同，在这种情况下： k 似) - c ( c ) 一m p k ( 似) ) 一m 图l - 4 使用两个密钥的加，解密 嘶n 1 - 4 f , n c r y p t i o no fd e c r 即t i o no f u s i n st w os e c r e ti | y | ) 现在广泛使用的方法是隐藏加解密算法的部分输入。这个输入在通常情形下是密钥， 密钥在每个加密方案中一般是不变的。根据密钥是用加密还是解密，又可以分为加密密钥 和解密密钥。解密密钥是需要保密的，通常又叫私钥( 或秘密密钥) 。而加密密钥可能是 公开的，也可能是保密的，在私钥加密系统( 或称为对称密钥系统) 中，加密密钥通常是 保密的。而在公钥密码系统( 或称非对称密钥系统) 中，加密密钥是公开的。 加密的方式有许多种，其中对秘密加密传输是保证信息安全的一种理想的方式。但要 单纯的采用效率较高的对称密码体制加密来保护秘密信息，一方面，需要通信双方协商产 生共享密钥，另一方面，既需要验证消息的可信性又需要验证通信双方的身份，而且以网 络为公开的信息传输基础的社会中通信双方有时根本是互不相识的，因此通信前进行安 全地共享( 传递) 秘密密钥是做不到的，故此时对称密码体制是无法解决问题的。为此， 国内外的学者和研究人员提出了“先签名后加密”的方法，但它所需的代价是签名和加密 所需的代价之和，因而效率不高。在此背景下，z h e n g 于1 9 9 7 年首次提出了签密 ( s i g n c r y p t i o n ) 的概念及方案，较好的解决了这一问题，其基本思想是在同一个逻辑步 骤内同时完成数字签名和加密两项功能，而且加解密仍可采用效率较高的对称密码算法， 因而其代价要远远低于。先签名后加密”，并且同时可实现加解密密钥的安全传输，所以 是实现对秘密信息既保密又认证的安全传输的较为理想的方法。 信息安全主要依靠密码技术来保证信息的安全性，其主要目的是防止信息的非授权泄 漏。加密方法多种多样，使得在实际生活中具有广泛的实际用途。在信息网络中一般是利 用信息变换规则把可知的信息变成不可知的信息。加密可以有效地对抗截收、非法访问等 威胁。它通常分为两大类：“对称式”和“非对称式”。 ( 1 ) 对称算法 4 第一章绪论 基于密钥的算法通常有两类：对称算法和公开密钥算法。 对称算法有时又叫传统密码算法，就是加密密钥能够从解密密钥中推算出来，对称密 钥加密技术是使用相同的密钥对数据进行加密和解密，发送者和接收者用相同的密钥。对 称加密算法是传统常用的算法，其中最有影响的是1 9 7 7 年美国国家标准局颁布的d e s 算 法( 数据加密标准算法) 和后来推出的a e s 算法。o e s 属于分组加密，它用密钥对6 4 位二 进制信息进行加密，将6 4 位明文加密成6 4 位密文。在实际运算过程中，d e s 设计的6 4 位密钥只有5 6 位用于加密过程，其它8 位用于奇偶校验位。d e s 加解密只是简单比特位 处理的组合，因此速度快，密钥生成容易。其主要缺点：一是密钥长度太短，随着硬件技 术的飞速发展。采用对所有密钥的遍历搜索，搜索的时间会进一步缩短，d e s 的安全性受 到严重的威胁：二是当用户数刀增大时，通信密钥数按n t n 一1 ) 2 的几何级数增加，从而给 密钥分配与管理带来困难；三是由于d e s 算法公开，其安全性完全依赖于对密钥的保护。 因此，必须使用秘密的方式交换密钥。所以d e s 不适合在计算机中单独使用。 a e s 是由n i s t 筹划，旨在取代d e s ，以保护2 1 世纪敏感政府信息的新型加密标准。 a e s 是一个非保密的、公开披露算法的、全球免费使用的分组密码。其算法采用对称密 钥密码实现，支持1 2 8 b i 坞，1 9 2 b i 坞，2 5 6 b i t s 密钥 在大多数对称算法中，加，解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥 算法，它要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性依赖于 密钥，泄漏密钥就意味着任何人都能对消息进行加解密。只要通信需要保密，密钥就必 须保密。 对称算法的加密和解密表示为： & ( 肼) 一c 巩( c ) - m 对称密码术的优点是：有很强的保密强度，且经受住时间的检验和攻击，加密处理简 单，加密解密速度快。 尽管对称密码术有一些很好的特性，但它也存在着明显的缺陷，包括： 进行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情况下是可行 的，但在某些情况下会非常困难，甚至无法实现。 规模复杂。 ( 2 ) 公开密钥算法 公开密钥算法( 也叫非对称算法) 非对称密钥加密体制非对称密钥加密系统，又 称公钥和私钥系统。公钥密码的优点是可以适应网络的开放性要求，且密钥管理问题也较 为简单，解决了密钥管理问题。 它是这样设计的：用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加 密密钥计算出来( 至少在合理假定的长时间内) 。之所以叫做公开密钥算法，是因为加密 密钥能够公开，即陌生者能用加密密钥加密信息，但只有用相应的解密密钥才能解密信息 5 西安理工欠学硕士学位论文 在这些系统中，加密密钥叫做公开密钥( 简称公钥) ，解密密钥叫做私人密钥( 简称私钥) 。 私人密钥有时也叫秘密密钥。为了避免与对称算法混淆，此处不用秘密密钥这个名字。 用公开密钥k 加密表示为 取) 一c 虽然公开密钥和私人密钥是不同的，但用相应的私人密钥解密可表示为： 圾( c ) - m 有时消息用私人密钥加密而用公开密钥解密，尽管可能产生混淆，但这些运算可分别 表示为： e x ) - c 巩( c ) 一m 从以上可以看出，与对称密码技术相比较，利用非对称密码技术进行安全通信，有以 下优点： 通信双方事先不需要通过保密信道交换密钥。 密钥持有量大大减少。在一个用户的团体中进行通信，每一用户只需要持有自己 的私钥，而公钥可放置在公共数据库上，供其他用户取用。这样，整个团体仅需n 对密钥， 就可以满足相互之间进行安全通信的需求。 非对称密码技术还提供了对称密码技术无法或很难提供的服务：如与哈希函数联 合运用可组成数字签名，可证明的安全伪随机数发生器的构造，零知识证明等。 而非对称密码技术的主要缺点是：加解密速度慢、耗用资源大。一般来说，实用的 加解密方案都综合运用了对称密码技术和非对称密码技术 1 4 本文的研究重点 本文研究重点是多接收者的签密方案。签密理论自提出来以后己经给出了很多方案， 但通过对这些己知签密方案的研究，发现他们的方案大多只有一个几个接收者。然而，在 许多时候，签密的合法接收者往往不止一个人，签密具有多重性，同一个消息需要发送给 多个指定接收者，并且每一个对应的接收者都希望能够独立验证签名的有效性，无需相互 协作，任何无关的其他人若没有签密者或接收者的都无法验证签名真伪。这种情况在现实 生活中十分常见，例如，国家政府、安全和情报部门签署的机密文件，需要同时发送给些 特定的机构或具有一定级别的官员；又如，a 公司开展某个项目的过程中，有厅个固定合 作公司，项目进行期间，a 公司需要经常给所有合作公司发送有关项目进展的文件，但他 并不希望任何非合作公司能够掌握这些文件的内容，即这种签密仅能由合法的n 名合法的 接收者单独验证。 所以，针对现阶段缺乏对多接收者签密技术的系统性研究分析，以及这个领域中存在 6 第一章绪论 的一些不成熟性，有必要开展对此类方案的研究，构建出一些设计简单、实现方便、快速 高效、抗攻击性好的多接收者签密方案，为需要多名合法接收者的签密问题提供更好更多 的解决途径。 1 5 主要研究内容 ( 1 ) 介绍了数字签名，给出数字签名的定义及其理论基础( 困难性及假设) ，同时还 分析环签名、代理签名、盲签名等。 ( 2 ) 第三章介绍了签密的概念，性质及研究现状，并基于己有的签密方案构造了一 个多接收者的签密方案。 ( 3 ) 第四章介绍了代理签名的概念，安全性的性质以及代理签名方案的基本定义， 并构造了一个具有多接收者的代理签密方案 7 西安理工走擘硕士学位论文 2 基本概念和基本理论 现代密码学为信息安全技术提供了有效的技术保证。基于公开密钥密码学发展起来的 数字签名为抵抗攻击者对信息系统进行主动攻击提供了强有力的防护手段，在日常生活中 扮演着越来越重要的角色。本章主要介绍数字签名理论，从数字签名的定义、数字签名的 理论基础、数字签名的算法等几个方面进行了讨论，并对相关签名技术进行了简要的分析。 2 1 椭圆曲线的理论基础 2 1 1 群、环和域的概念 ( 1 ) 群 定义设g 是一个非空集合，若在g 上定义一个加法运算满足下列条件，称g 构成了 一个群。 封f j j 性对于任何的4 ，b e g ，有口+ b e g ； 结合律对于任何的口，b ，c e g ，有( 4 + 6 ) + c 一4 + p + c ) ； 存在单位元e e g ，使得对于任何的a e g ，有4 + o - e + 4 - 口； 对于任何的e e g ，存在逆元a e g ，使得4 + 4 一- a 4 + 口e 成立。 ( 2 ) 环 定义设f 是一个非空集合，若在f 中定义一个加法和乘法运算两种运算，其中加法 记为。+ ”，乘法记为“”，如果满足下列条件，称f 构成了一个环。 ( f ，+ ) 是可交换群； f 中的全体非零元素对乘法构成交换群； 乘法在加法上是可分配的，对任何的a , b ，c e g ，有 f l p + c ) n b + 口cp + c ) 口一b a + c a ( 3 ) 域 定义设r 是一个非空集合，若在r 中定义一个加法和乘法运算两种运算，其中加法 记为“+ ”，乘法记为“”，如果满足下列条件，称露构成了一个域 俾，+ ) 是可交换群，加法的单位元是零元素； r 中的全体非零元素对乘法构成交换群： 乘法在加法上是可分配的，对任何的f l ，b ，c g ，有 a ( 6 + c ) - a b + 4 。c( 6 + c ) a _ 6 口+ c 。a b 第二章基本概念和基本理论 2 1 2 椭圆曲线 椭圆曲线的相关研究起源于1 9 世纪，它是代数、几何、数论等多个数学分支的一个 交叉点。1 9 8 5 年，n c i l k o b l i t z “1 和v i c t o r m i l l e “等人将椭圆曲线应用到密码学中w e l l ， 以椭圆曲线上的有理点构成的a b e l 群为背景结构提出了椭圆曲线上的密码体制e c c 。 椭圆曲线密码体制与基于有限域上乘法群的离散对数的密码体制( 如e i c r a m a l ， d i 向e h d l m a n 等) 及r s a 相比，有以下优点： ( 1 ) 在安全性相当的前提下，椭圆曲线密码体制的密钥短、签名短： ( 2 ) 椭圆曲线密码体制建立在椭圆曲线离散对数的数学难题之上，没有亚指数攻击 算法； ( 3 ) 椭圆曲线密码体制资源丰富，椭圆曲线上可以提供无数的有限a b e l 并且这种群 的结构丰富、易于实际计算。 所谓椭圆曲线是指亏格为1 的平面代数曲线，一般地，可以用w c i c r s t r a s s 方程描述： y 2 + a r t y + a 3 - ，+ a z x 2 + a 4 x + 气 其中a l e f ，f 1 ，6 ，f 是一个域可以是有理数域、复数域，还可以是有限域。 满足上面方程的点就构成椭圆曲线。 目前，在密码学中都是基于某个有限域讨论椭圆曲线，例如基于z ，p 为素数。只 有在有限域基础上，才可能在信息变挟中进行精确计算，为了提高计算速度，通常还有基 于有限域f _ 讨论椭圆曲线。 设是特征值大于3 的有限素整数域，则在放射坐标平面上，定义在有限域上的 椭圆曲线【艺) 是由满足下式 y 2 - ，+ 戤4 - b 其中a 。b e f o r 多夕 k - 圈2 - 1 椭圈曲线群的运算 a n g i l 难2 - 1t h e o p e r a t i o n o f e l l i p t i c c u r v e ) 9 西安理工大学硕士学位论文 及判别式4 口2 + 2 7 b 3 ，0 的点及无穷远点0 所组成的在e 上非空集合。这些点在下面的加 法运算下构成一个a b e l 群，群运算的恒等元是0 。 在此仿射坐标平面上，定义在有限域e 上椭圆曲线任意两点p ，q ，通过该两点的直 线l 若与椭圆曲线有第三个交点记为r ；该点一只的关于工轴的对称点r 也在该椭圆 曲线上。定义“加法”p + q r 。 如果直线l 通过点r 及其对称点一r 与曲线没有第三个交点，那么规定r + ( 一哟0 ， 称为零点，表示此时直线l 在无穷远处与曲线有交点，d 也就等价于加法群中的单位元一 零元。这样，在实数域下，椭圆曲线上所有的点，加上一个无穷远点零点，构成一 个加法群。 定理：如果p ，q 是椭圆曲线e 上的任意两点，p 和q 的连线l 与曲线e 相交于另外一 点尺，d 表示无穷远点。则 ( 1 ) ( p + q ) + r 1 0 ； ( 2 ) p + 0 i p ： ( 3 ) p + q - q + p ； ( 4 ) 对于任意一点p e e ，存在一点一p ，使得p + ( - p ) 1 0 ； ( 5 ) 对于p ，q ，r e e ，则( p + q ) + 尺一p + ( q + 尺) 。 这些性质表明在加法运算下，椭圆曲线土的点构成a b e l 群。另外，根据点构成的倍 数公式，有p + 尸2 p ，p + + p m p 。 2 1 3 双线性映射的基本概念 在椭圆曲线中，有一类被称为超奇异曲线的椭圆曲线，该类曲线被认为是。弱”椭圆 曲线。m e n e z e s ，o k a m o t a 和v a n s t o n e s 的工作d 1 指出了这些椭圆曲线上利用椭圆曲线离 散对数问题构建密码体制较标准的离散对数问题可使用较小的有限域的优势将消失。把超 奇异椭圆曲线排除在密码应用之外己成为一个普遍接收的约定。 j o u x 在文献 4 1 中首先利用椭圆曲线中的w e i l 配对构造了一个一轮三方密钥交换 协议，b o n c h 和f r a n k l i n 用w n 配对构造了一个基于身份的加密体制“1 ，成为近年来的 一个研究热点。 双线性对内容的简要介绍如下： 设g 1 是阶为q 的加法循环群，且q 是一个大素数。p 是g 1 的一个生成元。口，b e z ：是 两个随机数。假设g 和g 2 这两个群中的离散对数问题都是困难问题。 定义称g 1 和g 2 之间的映射e ：g 1 xg 1 一g 2 为一个双线性对，如果e 满足以下条件： 双线性性( b i l i n e a r ) ：对所有p , q eg l ，有e ( a p ，b q ) - e ( p , q 严。 非退化性( n o n d e g e n e r a t e ) ：存在p ，q g 1 ，使得e ( p q ) _ 1 。 可计算性( c o m p u t a b l e ) ：存在一个有效的算法对所有p ，q g 1 ，能够快速计算 第二幸基本概念和基本理论 e ( p ，q ) 我们可以用超奇异椭圆曲线上的w e i1 对或经改造的t a t e 对来构造双线性对。 设求逆和乘法运算在g 1 中都能够有效计算。那么在这样的群g 1 上，可以定义以下几 个密码学问题： 离散对数( d l ) 问题：给定p , q - g 1 ，找出一个整数厅，使得q - n p 成立，若这样的n 存在 计算性d i f f i e h e l h n a n f 司题( c d h p ) ：任给a p , b p e g l ( 口，b e z ) ，计算a b p 判定性d i f f i e - h e l l 啪问题( d d h p ) ：任给4 尸b p , c p ( a , b 。c e 乏) ，判断是否 c a b m o d q ，若等式成立，称( 只a p , b p , c p ) 为一个有效的d i f f i e - h e l h n a n 四元组。 如果在群( g 1 上。d d h 问题是在多项式时间内可解的，而不存在任何多项式时间算 法使得d l p 问题和c d h 问题能够以不可忽略的概率被求解，那么我们称g 1 为g a p d i f f i e - h e l h n a n 群( g a pd i f f i e - h e l h n a ng r o u p ，简称g d h 群) 。即在多项式时间内能够解决 c d h p 和d l p 问题的概率可以忽略不计。g d h 群通常存在于有限域中的超椭圆曲线或超奇 异椭圆曲线中，双线性对一般可以由w e l l 或t a t e 对得到。有关具体的细节可参见文献 【5 ，6 。7 】。 2 1 4 有限域上椭圆瞳线的阶 对于椭圆曲线e ) 的阶的计算，有以下几个定理： h a s s e 定理哪：设置e ，e 为椭圆曲线。则 i # e ( k ) 一l p l z 4 p 如果挣e - p ，则椭圆曲线e 是一类特殊的椭圆曲线，成为。畸形”曲线。其准确 的阶的计算如下： 定理n 1 ：对于椭圆曲线e ( 目，则e ：y 2 - 工3 + a x + b ( 其中口，b e 只) ，那么 托孵) 1 1 + ( 1 + 掣) ( z 聃其中守表示勒让德( 州哟符号，即 f 1 s 是p 的平方剩余 南 o ，p 肛 p j 一1 ，环是p 的平方剩余 其中s 是整数，g c d ( s ，p ) - 1 。 1 1 西安理工大学硕士学位论文 2 2 数字签名 2 2 1 数字签名的基本理论 1 9 7 6 年，d i 任i c 和h e l l m a n “1 首次提出了数字签名的概念，使得数字签名获得了广泛 的研究和发展。数字签名是信息完整性、真实性的理论基础，是信息安全的关键技术之一。 目前，数字签名是建立在公开密钥体制基础上，它是公开密钥加密技术的另一类延伸 应用。它以加密技术为基础，核心是采用加密技术的加，解密算法体制来实现对消息的数 字签名。其一般工作流程是：消息的发送方首先通过运行一个哈希函数，对要发送的消息 生成消息摘要，然后用自己的私钥对这个消息摘要生成数字签名，将这个数字签名作为消 息的附件和消息一起发送给接收方：消息的接收方首先从接收到的原始消息中计算出消息 摘要，接着再用发送方的公钥对消息附加的数字签名进行解密。如果两个散列值相同、那 么接收方就能确认该数字签名是发送方的。通过数字签名能够实现对原始消息的鉴别和不 可抵赖性。 其基本过程如下： + 。强送方+ 一接收方+ 图2 - 2 工作流程图 f i g u r e2 - 2w o r ki l o w e h a r t ) 数字签名是现实生活中对文件的手写签名的一种电子模拟。一个签名算法通常应满足 以下几个条件： 不可伪造性：要使签名有效，签名必须处于签名者的完全控制之下，即任何其他 人都不能伪造签名，接收者能验证签名： 不可否认性：签名者发出签名的消息后不能否认自己的签名； 可仲裁性：当签名者与接收者对签名的真伪发生争执时，仲裁方能解决双方之间 的争执 第二章基本概念和基本理论 上述的数字签名能够实现以下功能： 接收者能够证实签名者身份； 签名者事后不能否认签名的消息； 接收者或非法者不能伪造、窜改消息。 自从d i f l i e 和h c l l m a n 提出公钥密码体制的观点之后，它使密码学发生了一场变革。 1 9 7 7 年，由r i v e s t 、s h a m i r 和a d l e r m a n “提出了第一个比较完善的公钥密码算法，公钥 密码算法是使用一对互相匹配的密钥进行加密、解密。每个用户拥有一把仅为本人所掌握 的私有密钥s k ( 私钥) ，用它进行解密和签名：同时拥有一把公开密钥p k ( 公钥) 并可 以对外公开，用于加密和验证签名。因此，这种体制又称为双钥或非对称密钥密码体制。 当发送一份保密文件时，发送方使用接收方的公钥对数据加密，而接收方则使用自己的私 钥解密这样，信息就可以安全无误地到达目的地了，即使被第三方截获，由于没有相应 的私钥，也无法进行解密。或者用户也可以采用自己的私钥对信息加以处理，由于密钥仅 为本入所有，这样就产生了别人无法生成的文件，也就形成了数字签名。 公开密钥加密的基本思想是：每个用户拥有两个密钥，一个是公开密钥p k 它类似于 电话本上的号码，对任何其他用户都公开；另一个是私有密钥s k ，仅为自己拥有。加密 算法e 和解密算法d 都是公开的，虽然是s k 由p k 决定的，但却不能根据p k 计算出s k ( 1 ) 用加密密钥p k 对明文z 加密后，用解密密钥s k 即可恢复出明文，即 d 饵o ) ) ix ；另外加密和解密的运行可以对调，即e ( d 0 ) ) a l ez ； 2 ) 加密密钥不能用来解密，即d 馁o ) ) - x ； ( 3 ) 在计算机上可以容易地产生成对的p k 和s k ； ( 4 ) 从己知的p k 推导出s k 在计算上是不可能的。 2 2 2 数字签名的困难问题 数字签名方案普遍都是基于某个公钥密码体制，签名者用自己的私钥对消息进行签 名，验证人用相应的公钥对签名进行验证。从表面上看，数字签名与公钥加密使用密钥的 顺序不同。实际上，数字签名与公钥加密一样也是用单向陷门函数确保其安全性。本质上， 大数分解困难问题和离散对数困难问题等各种计算困难问题的存在是安全的数字签名方 案存在的根本。 按照数学难题分类：数字签名可分为基于离散对数问题的签名和基于素因子分解问题 的签名。e 1 g a m a l 和d s a 签名基于离散对数问题；而r s a 数字签名则基于素因子分解 问题。将离散对数和因子分解结合起来，又可以产生同时基于离散对数和素因子分解问题 的数字签名，即只有离散对数和素因子分解同时可解时，这种数字签名才不安全，因此， 该种签名具有较高的安全性。 下面给出在公钥密码体制中经常用到的一些困难性问题： 西安理工大学项士学位论文 从数论的角度来看，任何公钥密码系统的安全性都是基于求解某个数学难题或者说是 建立在一个n p 问题之上，即对于特定的问题我们无法找到一个多项式时间的算法求解该 问题，一般求解此类问题的算法都是在指数时间内是无法解决的，现有的所有的手段不适 于求解此类问题。 这些数学难题可以分为三大类： 大整数因数问题：两个大素数p 和q 相乘得到乘积n 比较容易计算，但从它们的乘积 万分解为两个大素数p 和q 则十分困难。如果 足够大，那么在多项式时间内不可能找到 有效的算法解决此问题。 有限域乘法群上的离散对数问题( d l p ) ：设a ，b 为有限域乘法群z 上的两个元素， 找出x e z ，使得矿- b 的运算称为有限域乘法群z 。上的离散对数。 椭圆曲线上的离散对数问题( e c d l p ) ：设( e ) 是定义在有限域e 上的椭圆曲线， 给定曲线上任一点p ，e 的阶为弗，p 的阶为n 。椭圆曲线离散对数问题是指给定曲线上 阶为n 的点尸，己知点q 一对( p 生成的循环群) ，求正整数m ，使q - m p ，这是椭圆 曲线上的离散对数问题。 根据所依赖的数字难题把公钥密码体系分为三类： 基于整数因式分解的公钥密码体制：其中主要包括r s a 体制和r a b i n 体制。r s a 是 r i v e s t ，s h a m i r 和a d e m a l l 于1 9 7 7 年提出来的，可用于加密，又可用于数字签名。r s a 的安全性是依赖于作为公钥的大数忍的位数长度的。为保证足够的安全性，一般需要较长 的比特长度，随着密钥的长度增加而增强。但是，密钥越长，其加解密所耗的时间也越长， 增大模长带来了实现上的难度。 基于有限域乘法群上离散对数问题的公钥密码体制：其中主要包括i a 签名方案， d i 蚯e - h e l l m a n 密钥交换方案，e i g a m a l 加密体制和s c h n o r r 签名方案。 椭圆曲线密码体制与其它两类体制比较，有以下优点： ( 1 ) 椭圆曲线密码体制的安全性高。加密算法的安全性能一般通过该算法的抗攻击 强度来反映。e c c 和其他另外几种公钥系统相比，其抗攻击性具有绝对的优势。椭圆曲线 的离散对数问题( e c d l p ) 计算困难性在计算复杂程度上目前是完全指数级的，而蚴 是亚指数级的。这体现了e c c 比r s a 的每比特安全性高。 ( 2 ) 计算量小和处理速度快。在相同的计算资源条件下，在处理私钥的速度上( 签 名和解密) ，e c c 远比r s a 和d s a 快得多。 ( 3 ) 占用的存储空间小。e c c 的密钥尺寸和系统参数与r s a ，1 0 2 4 位r s a , d s a 具有相同的安全强度，d s a 相比要小得多。1 6 0 位e c c 小得多。这对于加密算法在资源 受限环境上要的意义。 ( 4 ) 在同样的基域下，椭圆曲线密码具有更多的可选择性。 ( 5 ) 椭圆曲线密码体制的安全强度参数和私钥的个数少。 通过对三种公钥密码体系几个方面的比较，可以看出e c c 是当今比较好的一种公钥 1 4 第二章基本概念和基本理论 密码体系 2 2 3 两个典型的签名体制 公钥密码学是现代密码学的一个主要分支，也是数字签名的重要基础。目前，己有的 数字签名方案大都建立在某个公钥密码体制之上。1 9 7 6 年，d i f f i e 和h e l l m a n 首次提出 了公钥密码的思想，标志着公钥密码学的诞生构建公钥密码系统需要一种被称为单向陷门 函数的特殊数学函数。1 9 7 7 年，由r i v e s t 、s h a m i r 和a d l e m a n 发明了著名的r s a 体制； 1 9 8 5 年，e l g a m a l “找到了基于离散对数问题的单向陷门函数并提出了相应的密码系统， 这些公钥密码系统己成为公钥密码学的重要基石。 ( 1 ) r s 密码体制 设是两个不同的大素数p ，q 2 _ 积，即- 朋，且畎) 表示 r 的欧拉函数值，即 甲( ) - o - 1 x q - 1 ) 密钥建立： 1 随机选取两个大素数p ，鼋； 、 2 计算n - p q ，缈) - ( p 一1 ) ( 霉一1 ) ； 3 随机选取整数e ，满足1 t e 9 ( ) ，g c d ( e , m ( n ) ) 一1 ； 4 计算整数d ，满足耐- l m o o 矿( n ) ； 5 。p ，窖和妒( ) 保密，私钥为d 。 r s a 数字签名算法：对于密钥对( ，岛d ) ，定义消息肼乙的签名算法为： s s i g j 伽) m 4m o d n 贝i j s 称为对消息n l 的签名。定义签名验证算法为： v e t 伽，s ) 真m - ，m o d n ( 2 ) e t g e m a l 密码体制 密钥建立： 1 随机选取大素数p ，计算z ：的一个随机乘法生成元g 2 随机选取彳j z ：，计算y - g 。m o d p 3 公开公钥( p ，g ，y ) 。 e l g a m a l 签名算法：对于每一个密钥k - o ，g ，工，y ) ，定义其加密算法为 $ i g k ( 肼，七) ( r ，s ) ，历z ： 其中随机选取的七。z ：，和s 满足以下条件 西安理工大学硕士学位论文 ，- g m o d p ，s 一( ，h 一玎) 七一m o d o , 一1 ) 定义签名验证算法： v e r ( m ，r ，s ) 真。y 7 ，- g 。m o d p ，册，r e 乙，s e z 川 2 2 4 数字签名的基本算法及安全性定义 ( 1 ) 数字签名的基本算法 一般数字签名方