（计算机科学与技术专业论文）基于身份的签名和签密的研究.pdf

摘要 摘要 在传统的公钥密码体制中，利用c a 证书来保证公钥和持有对应私钥的身份 之问的联系，实现公钥的认证。这使得传统公钥密码体制中必须花费大量的时间 和空间来计算和保存这些证书。 1 9 8 4 年s h a m i r 首先提出了基于身份的密码系统概念，公钥可以直接从用户 的唯一可标识的身份信息中获得，比如用户的名字或者e m a i l 地址等，公钥的认 证不再需要证书。这种方案的提出，大大改进了原来基于证书的密码机制的效率。 近年来，各种基于身份的签名和加密方案被相继提出，方案的安全性和效率 被不断的提高。然而这些方案中都存在着一个共同问题，即模型都是建立在用户 必须无条件信任于私钥产生中心( p k g ) 的基础上，由于p k g 拥有用户的私钥， 它可以任意伪造用户对消息进行签名和对消息进行解密，针对这个问题，本论文 的主要工作如下： l 、利用c x f 方案中用户私钥的产生方式，提出了一种新的基于身份的无需 可信中心的数字签名方案z h e n g l ，该方案同时验证系统的主密钥和用户的秘密 信息，与c x f 方案相比，改进后算法的效率大大提高，同时在随机预言模型下证 明其能抵抗适应性选择消息攻击者的存在性伪造攻击。 2 、首次提出了一种无需可信中心的基于身份的数字签密方案z h e n 9 2 ，解决 了传统签密方案中用户必须无条件信任于私钥产生中心的弊端。在随机预言模型 下证明了该方案的安全性等价于6 d h 群上的计算型d i f f i e - h e l l m a n 问题的难解 性。 3 、针对现实网络环境中存在多个私钥产生中心的问题，修改了我们提出的 签密方案z h e n 9 2 ，在保持了g d h 群上计算型d i f f i e h e ll m a n 问题的难解性的条 件下，提出了一种无需可信中心的可跨p k 6 身份签密方案z h e n 9 3 ，使其适应现 实网络存在多p k g 的条件下实现安全通信。 关键词：i d p k i ：身份签名：身份签密：无可信中心 a b s t r a c t a b s t r a c t i nt h et r a d i t i o n a lp u b l i ck e yc r y p t o s y s t e m ，c ac e r t i f i c a t ei su s e dt op r o v i d ea n a s s u r a n c eo ft h er e l a t i o n s h i pb e t w e e nt h ei d e n t i t i t ya n dp u b l i ck e y , w h i c hi s c o r r e s p o n d i n g t oi t s p r i v a t ek e y t h i sm e a n s t h a tt h et r a d i t i o n a l p u b l i ck e y c r y p t o s y s t e mm u s ts p e n dal o to ft i m ea n ds p a c et oc a l c u l a t ea n dp r e s e r v et h e s e c e r t i f i c a t e s i n19 8 4s h a m i rf i r s tp r o p o s e dt h ec o n c e p to fi d - b a s e dc r y p t o g r a p h i cs y s t e m p u b l i ck e yc a nb ed i r e c t l yo b t a i n e df r o mt h eu s e r si d e n t i t yi n f o r m a t i o n ，f o re x a m p l e ， u s e r sn a m e so re m a i la d d r e s s e s s ot h a tt h e r ei sn on e e df o rc e r t i f i c a t ei nt h e a u t h e n t i c a t i o no fp u b l i ck e ya n ym o r e t h ep r o p o s a la d v a n c e st h et r a d i t i o n a l c e r t i f i c a t ep k ial o t i nr e c e n ty e a r s ，v a r i o u si d e n t i t y - b a s e ds i g n a t u r ea n de n c r y p t i o ns c h e m e sh a v eb e e n p r o p o s e d t h es a f e t y a n de f f i c i e n c yh a v eb e e nc o n t i n u o u s l yi m p r o v e d h o w e v e r , t h e r ei sac o i n l i l o np r o b l e mi nt h e s es c h e m e s ，w h i c hi st h em o d e lm u s tb eb a s e do n t h eu n c o n d i t i o n a lt r u s tt ot h ep k g b e c a u s ep k gh a st h ep r i v a t ek e yo fa n yu s e ri ni t s d o m a i n ，i tm a yf o r g eu s e r ss i g n a t u r ea n dd e c r y p ti n f o r m a t i o n t ot h i si s s u e ，t h em a j o r w o r ko ft h i sp a p e ri sa sf o l l o w s ： 1 、a d o p i n gt h ef o r m a t i o no ft h ep r i v a t ek e yg e n e r a t i o no fc x fs c h e m e ，w e p r o p o s e dan e wi d b a s e ds i g n a t u r es c h e m ew i t h o u tt u s t e ap k g ( z h e n g1 ) t h e s c h e m ev e r i f i e st h es y s t e m sm a s t e rk e ya n dt h eu s e r ss e c r e ti n f o r m a t i o na tt h es a m e t i m e c o m p a r e dw i t hc x fs c h e m e ，t h ea l g o r i t h me f f i c i e n c y h a sb e e ng r e a t l y i m p r o v e d ，w h a t sm o r e ，w ep r o v et h a tt h es c h e m ec a nb ea g a i n s tt h ee x i s t e n t i a l f o r g e r yo na d a p t i v e l yc h o s e nm e s s a g ea r a c ku n d e rr a n d o mo r a c l em o d e l 2 、w ef i r s tp r o p o s e da ni d - b a s e ds i g n c r y p t i o nw i t h o u tt u s t e dp k g ( z h e n 9 2 ) i tg e t s r i do ft h ed i s a d v a n t a g e st h a tu s e r sm u s tu n c o n d i t i o n a l l yt r u s tt h ep k gi nt r a d i t i o n a l s i g n c r y p t i o n w ep r o v e dt h a tt h es c h e m e ss e c u r i t yi se q u i v a l e n tt ot h eg d hg r o u p c a l c u l a t i o no ft h ed i f f i e h e l l m a np r o b l e mu n d e rt h er a n d o mo r a c l em o d e l a b s t r a c t 3 、t ot h ei s s u e st h a tt h e r em a yb em a n yp k g si nt h er e a ln e t w o r ke n v i r o n m e n t ，w e i m p r o v e do u rs c h e m e ( z h e n 9 2 ) a n dp r o p o s e da ni d b a s e ds i g n c r y p t i o n ( z h e n 9 3 ) w h i c h c a nc r o s st h ep k g s i tm a i n t a i n e dt h eh a r do fc d h pi nt h eg d h g r o u p ，a n di tc a n r e a l i z es a f ec o m m u n i c a t i o ni nt h er e a ln e t w o r k sw h i c hh a v em a n yp k g s k e y w o r d s ：i d - p k i ；i d - b a s e ds i g n a t u r e ；i d b a s ds i g n c r y p t i o n ；w i t h o u tp k g 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文而产生的权利和责任。 声明人( 签名) ：螂藐 l 训多年岁月。日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打“”) 日期：髟年r 月歹日 日期：一吕年朋i 媚 第一章引高 1 1 信息安全与密码学 第一章引言 随着计算机网络以及信息化的飞速发展，人们之间的信息交流呈现出国际 化、网络化、数字化、智能化、宽带化的趋势，可以说人类已经进入了“信息时 代”。信息时代的主要特征是信息成了社会中最重要的一种资源和财富，信息的 交流和处理手段成了人们生活必不可少的组成部分，过去人们想象不到的许多事 情都已经变成了现实。现在，计算机应用已经渗透到生活中的各个领域。然而现 代信息技术是一把双刃剑，它一方面给人类带来了巨大的好处，另一方面又给人 类带来了前所未有的威胁。由于信息的存储、传递和处理等过程往往是在开放的 通信网络上进行，所以信息容易受到窃听、截取、修改、伪造和重放等各种攻击 手段的威胁。因此，与通信技术的高度发展相对应，信息安全成了信息社会急需 解决的最重要的问题之一。 信息安全的核心内容是保证信息在信息的保密性和真实性。所谓信息的保密 性，是指信息在生成、传递、接收等过程中，不能被非法用户所得到。而信息的 真实性，是指信息在生成、传递、接收等过程中，不会被非法地窜改、删除、和 伪造等。解决信息安全问题是一个庞大的系统工程，需要综合运用数学、计算机、 信息论、编码学、密码学、通信技术、管理技术等各种学科和技术的研究成果， 并且需要在实践中不断提高和不断探索。其中，密码学给解决信息安全问题提供 了许多有效的核心技术，在保护信息的保密性、真实性等方面发挥着关键性的作 用。简单地说，密码学是研究信息系统安全的一l - j 学科。它主要包括两个分支， 即密码编制学和密码分析学。密码编制学是对信息进行编码实现信息隐蔽的一门 学科，其主要县的是寻求保护信息保密性和认证性的方法，密码分析学是研究分 析破译密码的学科，其主要目的是研究加密消息的破译和消息的伪造。密码编制 学和密码分析学既相互对立又相互促进地发展。密码技术的基本思想是对消息做 秘密变换，变换的算法即称为密码算法。而决定秘密变换的秘密参数叫做密钥 ( k e y ) 。在密钥的作用下，把有意义的明文( p l a i n t e x t ) 变换成无意义的密文 桀十身份的签名和签衔的研究 ( c i p h e r t e x t ) 的变换叫做加密算法( e n c r y p t i o n ) ，相应的逆变换叫解密算法 ( d e c r y p t i o n ) 。若在密钥的作用下把消息变换成一种“证据”，用来说明某个实体 对消息内容的认可，则称变换为签名算法( s i g n a t u r e ) ，相应的逆算法称为验证算 法( v e r i f i c a t i o n ) 。根据密钥的特点，通常，将密码系统分为两大类型：类是对 称密码系统，另一类是公钥密码系统。 对称密码系统是一种比较传统的加密方式，其加密运算、解密运算使用的是 同样的密钥。信息的发送者和信息的接收者在进行信息的传输与处理时，必须共 同持有该密码( 称为对称密码) 。因此，通信双方都必须获得这把钥匙，并保持 钥匙的秘密。对称密码系统的安全性依赖于以下两个因素：第一，加密算法必须 是足够强的，仅仅基于密文本身去解密信息在实践上是不可能的；第二，加密方 法的安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确 保算法的秘密性( 事实上，现实中使用的很多单钥密码系统的算法都是公丌的) ， 但是我们一定要保证密钥的秘密性。从对称密码的这些特点我们容易看出它的主 要问题有两点：第一，密钥量问题。在单钥密码系统中，每一对通信者就需要一 对密钥，当用户增加时，必然会带来密钥量的成倍增长，因此在网络通信中，大 量密钥的产生、存放和分配将是一个难以解决的问题。第二，密钥分发问题。对 称密码系统中，加密的安全性完全依赖于对密钥的保护，但是由于通信双方使用 的是相同的密钥，人们又不得不相互交流密钥，所以为了保证安全，人们必须使 用一些另外的安全信道来分发密钥，例如用专门的信使来传送密钥，这种做法的 代价是相当大的，甚至可以说是非常不现实的，尤其在计算机网络环境下，人们 使用网络传送加密的文件，却需要另外的安全信道来分发密钥。 针对对称密码系统的种种问题，1 9 7 6 年d i f f i e 和h e l l m a n 首次提出了公钥密 码学的概念 1 ，它突破性的解决了对称密码系统中的密钥分发的问题。公钥密 码系统与对称密码系统最大的不同在于它的加密和解密使用的是不同的密钥( 人 们常称为非对称密钥) ，这两个密钥之间存在相互依赖关系，即用其中任一个密 钥加密的信息只能用与其对应的另一个密钥进行解密。这使得通信双方无需事先 交换密钥就可进行保密通信。其中加密密钥和算法是对外公开的，人人都可以通 过这个密钥加密文件然后发给收信者，这个加密密钥又称为公钥；而收信者收到 加密文件后，它可以使用他的解密密钥解密，这个密钥是由他自己私人掌管的， 第一章引高 并不需要分发，因此又称为私钥，这就解决了密钥分发的问题。公开密钥密码体 制下，加密密钥不等于解密密钥。加密密钥可对外公开，使任何用户都可将传送 给此用户的信息用公开密钥加密发送，而该用户唯一保存的私人密钥是保密的， 也只有它能将密文复原、解密。虽然解密密钥理论上可由加密密钥推算出来，但 这种算法设计在实际上是不可能的，或者虽然能够推算出，但要花费很长的时问 而成为不可行的。所以将加密密钥公开也不会危害密钥的安全。 1 2 公钥基础设施( p ki ) 的发展 在传统的公钥密码中，用户的公钥采取如下步骤生成：公钥= f ( 私钥) ，其 中f 是一个从私钥空间映射到公钥空间的有效单向函数。由于f 的单向性( 一个 好的混合变换) ，使得由私钥计算所得的公钥随机化，因此需要建立公钥与主体 身份相关的认证机制。传统解决公钥认证问题的方法是采用证书机制，通过发放 公钥证书来证实用户的公钥数据。p k i ( p u b l i ck e yi n f r a s t r u c t u r e ) 技术就是利用 公钥理论和技术建立的提供安全服务的基础设施，p k i 的主要目的就是通过自动 管理密钥和证书，为用户建立一个安全的网络运行环境，使用户可以在多种应用 环境下方便地使用加密和数字签名等技术，从而保证网上数据的机密性、完整性 和有效性。p k i 技术是信息安全技术的核心，也是电子商务的关键和基础技术。 由于通过网络进行的电子商务、电子政务、电子事务等活动缺少物理接触，因此 使得用电子方式验证信任关系变得至关重要。而p k i 技术恰好是一种适合电子商 务、电子政务、电子事务的密码技术，他能够有效地解决电子商务应用中的机密 性、真实性、完整性、不可否认性和存取控制等安全问题。一个实用的p k i 体系 应该是安全的易用的、灵活的和经济的。它必须充分考虑互操作性和可扩展性。 它是认证机构( c a ) 、注册机构( r a ) 、策略管理、密钥( k e y ) 与证书( c e r t i f i c a t e ) 管理、密钥备份与恢复、撤消系统等功能模块的有机结合。但是p k i 的证书管理 存在一些缺点，如证书撤销、保存、发布和验证需要占用较多资源，且管理复杂这 就限制了p k i 在实时和低带宽的环境中的应用，因此，出现了基于身份的公钥密 码体制i d p k c ( i d e n t i t y b a s e dp u b l i ck e yc r y p t o g r a p h y ) ，目的是减少公钥证书管 理开销。 基于身份的密码系统i d p k c 的设想最初由s h a m i r 于1 9 8 4 年提出 2 】，他试 桀十身份的签名和签街的研究 图绕丌基于目录的公钥认证框架的束缚。在基于身份的公钥密码中，用户可以安 全的通信在这种密码系统的密钥产生过程中，公钥直接就是公钥拥有者的身份信 息，因此这种公钥密码系统可以很自然的解决公钥与实体身份的绑定问题。 i d p k c 是解决公钥认证问题的另外一种方法。基于身份的密码系统之所以可直 接将身份信息作为公钥，是因为在其密钥产生过程中，先由实体的身份信息产生 公钥，然后再由公钥产生对应的私钥，当然，由公钥产生对应私钥的过程只为 p k g ( p f i v a t ek e yg e n e r a t i o n ) 所知，对其它实体是保密的。 基于身份的密码和基于证书的密码都是公钥密码体制，它们具有相似的功 能，都可以用来构造进行加密，签名等密码系统，但是基于身份的公钥密码在密 钥生成和密钥管理上有很大的优势。在p k i 中，用户先随机选择一个私钥然后通 过单向函数和私钥来计算公钥，公钥和私钥是同时生成的，他们可以由用户自己 生成，然后把公钥提交给c a 认证，或者他们由c a 产生，然后把私钥通过安全 信道颁发给用户。要想给用户发送秘密消息，则该用户首先要已经生成了自己的 公私钥对。而且由私钥计算所得的公钥总包含一段看似随机的成分，长度比较长， 不利于记忆。而在基于身份的密码系统中，公私钥对生成和p k i 公私钥对的生成 方法不同，公钥和私钥是可以分丌生成的，先由实体的唯一可标识的身份信息产 生公钥，公钥可以由系统中的任何用户来生成，然后再由公钥产生对应的私钥， 由公钥产生对应私钥的过程只为一个第三方信任机构p k g 所知，对其它实体是 保密的。p k g 只需要在生成密钥的时候需要在线，用户可以在收到加密消息后 向p k g 申请私钥，如a 给b 发送加密的邮件时，只需将b 的电子信箱地址信息 作为公钥对邮件加密，b 收到加密邮件后，与可信第三方p k g 联系获得私钥，b 用此私钥及相应的解密算法解密邮件即可读取。在基于证书的p k i 中，用e ，的公 钥和身份信息需要通过数字证书绑定在一起。在p k i 中使用目录服务器来存储用 户的公钥，而且密钥的发生、分发、注销、存储、证书的管理和可信度等问题对 证书机构来说都是极其繁重的负担，因而需要庞大的基础设施来支撑。而在基于 身份的公钥密码系统中，公钥直接从用户的身份信息中获取，因此不需要单独的 目录服务器来存储公钥，也不需要公钥的管理和认证问题，大大减少了系统的复 杂度。由于具有以上的优势，i d p k c 不仅受到广泛的关注与研究，而且丌始取 代传统的基于证书的公钥密码体制在很多领域得到应用，如安全e m a i l 系统， 4 第一章引苦 a d h o c 网络等。因此对i d p k c 及其关键技术进行进一步的研究具有很重要的理 论和实践的深远意义。 1 3 基于身份公钥加密系统的研究现状 s h a m i r 于1 9 8 4 年在文献 2 】中首次提出基于身份的密码系统( i n d e n t i t y - b a s e d e n c r y p t i o ns y s t e m ，以下简称为i b e ) 的同时，还提出了一种建立在大整数因子分 解问题( 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 ：i f p ) 基础上的基于身份签名( i d e n t i t y b a s e d s i g n a t u r e ：i b s ) 。从那以后，基于身份的加密方案提出了许多 3 6 ，但都有这样 那样的缺点，并且它们都没有给出严格的形式化证明来证实机制的安全性。直到 2 0 0 1 年的美洲密码学年会，b o n e h 和f r a n k l i n 7 7 j 提出了第一个可行的基于身份 的加密方案( 以下简称b f 方案) ，并给出了严格的形式化证明，证明该机制是可 抵抗不可区分自适应选择密文攻击的，也因此引起了新的研究i b e 的热潮。不久， c o c k s 8 提出了基于二次剩余的基于身份的加密方案，但是没有给出该方案的形 式化的安全性证明。这是使用二次剩余构造基于身份加密方案的基础性文章。为 了解决基于身份密码机制无法应用于大规模网络环境的问题，h o r w i t z 和l y n n 在文献【9 】中最早提出了层次化基于身份加密的概念，随后g e n t r y 和s i l v e r b e r g 在文献 1 0 中提出了第一个安全且实用的h i b e 方案，该方案扩展了0 1 年b o n e h 和f r a n k l i n 的方案，能够完全抵抗联合攻击。h i b e 机制极大减少了主服务器( p k g ) 的负担，并可被看作一种在分级情况下解决密钥托管问题的方法。0 3 年c a n e t t 、 h a l e v i 和k a t z 1 l 】引入一个叫做“选择身份( s e l e c t i v e i d ) ”的安全性较弱的模型， 并在此模型下提出了一个不需要随机预言模型的基于身份的加密方案。0 4 年， b o n e h 和b o y e n 1 2 在选择身份模型下提出了两种有效的i b e 方案。第一个方案 是在无r a n d o m o r a c l e 模型下基于判定性双线性d h 假设足安全的。第二个方案 基于双线性d h 置换假设，相对于第一个方案更有效。随后，他们又提出另一 种基于判定性b d h 假设的i b e 方案 1 3 ，并在无随机预言模型下证明该方案是 安全的。但是其效率太低仍然不实用。同年，一个基于 1 3 的更有效的i b e 方案 被w a t e r s 1 4 提出，该方案的安全性可以归约到判定性b d h 假设，但是该方案中 的公钥参数太长。s a h a i 和w a t e r s 1 5 】还提出了一个模糊i b e 方案，该方案可以使 用生物信息( 如手纹、声纹等一些模糊身份信息) 作为公钥对数据加密，其安全性 堆十身份的签名和签密的研究 也是建立在选择身份安全模型下的。0 5 年，n a c c a c h e 1 6 对w a t e r s 的签名方案进 行了改进，并在标准模型下证明该方案能抵抗被动攻击。这是第一个完全安全实 用的i b e 方案。b o n e h 、b o y e n 和g o h 1 7 提出了一个h i b e 方案，其中密文仅由 三个群元素组成并且其解密运算与层次无关( 只需进行两个双线性对值的运算即 可) 。该方案在标准模型下是选择i d 安全的，在r a n d o mo r a c l e 模型下是完全安 全的。但其安全性随层次深度指数级降低。0 6 年，a b d a i l a ，c a t a l a n o 等人 1 8 引入了一种带有通配符( w i l d c a r d s ) 的i b e 机制，通过一个固定的字符串序列和通 配符来定义接收密文的用户的身份。 然而，迄今为止，该领域内仍然有许多重要的公丌问题有待解决，例如构造 在标准计算模型下( 而不是r a n d o mo r a c l e 模型下) 选择密文安全的i b e 系统 ( f i t 7 提出) 。 1 4 本文的主要研究成果 针对目前基于身份的密码方案中所面临的安全性和性能需求，本文在前人工 作的基础上，对基于身份的签名和签密方案进行了相关的研究，主要工作如下： 1 、分析了由x i a o f e n g c h e n 等提出的一种无需可信中心的数字签名方案，指 出了该方案在效率上的不足，在其基础上修改了签名生成算法和验证算法，使得 新方案z h e n g l 的效率大大提高，同时给出了新方案的安全性证明。 2 、利用c x f 方案中的用户私钥产生方式，首次提出了一种无需可信中心的 基于身份的数字签密方案z h e n 9 2 ，该方案保持了签密方案的特性，可以在一个 逻辑步骤内实现签名和加密，同时，该方案解决了传统签密方案中用户必须无条 件信任于私钥产生中心的弊端。在随机预言模型下证明了该方案的安全性等价于 g d l l 群上的计算型d i f f i e h e l1 m a n 问题的难解行。 3 、针对现实网络环境中存在多个私钥产生中心的问题，修改了我们提出的 签密方案z h e n 9 2 ，在保持了g d h 群上计算型d i f f i e h e l l m a n 问题的难解性的条 件下，提出了一种无需可信中心的可跨p k g 身份签密方案z h e n 9 3 ，使其适应现 实网络多p k g 的条件下的安全通信。 6 第一章引高 1 5 本文的组织结构 本文的内容结构如下： 第一章首先介绍信息安全与密码学技术，然后介绍p k i 的发展过程，并分析 了i d - p k i 的研究现状。最后介绍了本文的研究成果。 第二章主要介绍本文中用到的基本概率和基础知识，首先介绍与椭圆曲线密 码学相关的数学基础知识。然后介绍了椭圆曲线的基本知识，包括椭圆曲线的概 念，离散对数问题以及对椭圆曲线的攻击现状。最后介绍了标准的有限域上的椭 圆曲线的加密算法。 第三章介绍了基于身份的公钥密码学相关内容，主要分析了几种典型的基于 身份的公钥密码方案。包括了s h a m i r 的数字签名方案以及b o n e hf r a n k l i n 的加 密方案。 第四章主要研究基于身份无需可信中心的签名方案，首先介绍c x f 提出的方 案，接着提出了一种改进方案，给出了方案的算法描述以及安全性证明。最后给 出了2 种方案的性能对比分析。 第五章主要研究基于身份无需可信中心的签密方案，首先介绍基于身份签密 技术的发展与现状。 7 幕十身份的签名和签街的研究 第二章基本概念和基础知识 2 1 数学基础知识 近代密码学是建立在坚实的数学基础之上的，涉及如代数、概率论、组合数 学、信息论等，尤其是数论。当今，有关数论的算法已被广泛使用，部分就是应 为大素数为素材的密码系统的发明。这些系统的可行之处在于我们能够容易的求 出大素数，而系统的可靠性在于大素数的积难以分解。目前可以说，数论与实际 生活结合最紧密的例子就是网络信息安全中的加密和解密问题。本文中所介绍的 签密方案都是运行在群和域上的。 2 1 1 群、环、域 群( g r o u p s ) 是抽象代数学的重要组成部分，是研究椭圆曲线密码体系的重 要基础。 定义2 1 设有一个由任意元素a ，b ，c ，组成的非空集合g ，即g = g ， 。 在g 上由一个针对其中元素进行组合操作的二元运算规则“”，并同时满足下列 四个条件，则g 对于运算“”称为群，并称二元运算“ 为群的运算。 封闭性对于任意的g ，g ，g ，有g ，g ，= 反g 。即g 中任意两个元素在所 定义的群运算“”下，依照次序合成的结果仍是g 中的一个完全确定的元素。 结合律对于任意的g ，g j g i g ，都有( 岛g ) 反= g ，( g ) 单位元存在唯一的元素e g ，使得对于任意的g ，g ，满足e g ，= g io e = g i ， 并称e 为g 的单位元，有时也用1 表示。 逆元素对于任意的g ，g ，都有相应的元素9 7 1 g ，使得g ，g i l = g ，- i g f = e ， 并称百1 为& 的逆元素，简称逆元。 上述四个条件是构成群的充分必要条件，通常成为群的公理，若仅满足条件 和条件，则称为半群；满足条件、和条件，称为幺半群。 第二幸暴本概念和操奉知识 定义2 2 若群g 对运算“”还满足交换律，即对于任何的g ，g ，g ，都 有g ，= g ，吕成立，则称群g 为交换群或阿贝尔群。此时，通常用符号“+ ”来 替代“”，并称群运算“+ 为“加法”，称a + b 为a 与b 的和，称单位元素e 为零元素0 ，称逆元素口- 1 为元素a 的负元素，并记做一a ，相应地称群运算“” 为“乘法”，称a o b 为a 与b 的积，简写为a b 。例如，全体整数的集合在通常的 加法运算下构成一个阿贝尔交换群。 定义2 3 群g 中的元素个数成为群g 的阶( o r d e r ) ，记作# g 或jgj 。 定义2 4 若群g 的阶为有限数，则群g 中的元素个数jgl 有限，则称g 为有 限群；反之，称为无限群。 定义2 5 如果存在一个元素口g ，对任一b g ，都存在一个整数j 0 ，使 得b = 口，则群g 就称为循环群，元素a 称为g 的一个生成元，g 也称为由a 生 成的群。当一个群由a 生成时，记做g = 。 和群一样，坏也是抽象代数学的重要组成部分之一，在椭圆曲线的研究中占 有重要地位，是椭圆曲线密码系统的快速实现和解决计算有限域上的椭圆曲线群 的阶等问题的核心之一。 定义2 6 设有非空集合r ，在r 上定义了两个二元运算，一个是加法运算“+ ”， 另一个是乘法运算“x ”，则定义满足下列三个代数结构 为环： r 上的元素关于加法运算( r ，+ ) 构成阿贝尔群： r 关于乘法运算( r ，x ) 构成半群； 乘法运算对于加法运算满足分配律，即对于任意的a ，b ，c f ，有 ( 口+ 6 ) c = 盘x c + b x c c ( 口+ 6 ) = c x 口+ c x b 若( r ，) 是交换半群，则称r 为交换环；若( r ，) 有单位元，则称r 为含单位元的环。全体整数、全体有理数、全体实数或全体复数在通常的加法 和乘法运算下均构成环，分别称为整数坏、有理数坏、实数环和复数环，又可 统称为数环。 与群和环一样，域也是现代代数学的重要组成部分，是解决椭圆曲线离散对 9 甚。t 二身份的签名和签密的研究 数问题的理论基础之一，在椭圆曲线密码体系的研究中占有及其重要的地位。 定义2 7 设f 是一个至少包含两个元素的集合，在f 上定义了两个二元运算， 一个是加法运算“+ ”，另一个是乘法运算“”，则定义满足下列三个代数结构 为域： f 上的元素关于加法运算“+ ”构成阿贝尔群，设其零元素为o ： f 0 关于乘法运算“”也构成阿贝尔群。设其单位元为e ，在不引起 混乱的情况下可用1 表示； 乘法运算对于加法运算满足分配律，即对于任意的a ，b ，c f ，有 ( 口+ b ) c = a c + b c c ( a + 6 ) = c a + c b 显然，域是环的一种类型，因而也是一种及其重要的代数结构。由于在域内， 方程a + x = b 和a x ：b ( a 0 ) 均有唯一解，故加法和乘法有逆运算，其逆运算分别 为减法和除法，因而域是其内元素可做四则运算的代数结构。 定义2 8 有限域f 是指只含有有限个元素的域，f 的阶为f 中元素的个数。 结构最简单的有限域就是阶为素数的有限域，这种域在密码学中的应用是最广泛 的。 定义2 9 令p 为一个素数，则有限域z p 记为。 定义2 1 0 f p 的非零元在乘法下构成一个一个群，称为的乘法群，以巧表 示。 2 1 2 离散对数问题 简单地说，离散对数问题就是乘方过程的求“逆”，这个问题可以由各种不 同的代数结构构成，最常见的类型有：( 1 ) 有限域上的离散对数问题d l p ；( 2 ) 椭圆曲线离散对数问题e c d l p 。本文中所介绍或提出的方案的安全性都是基于解 决离散对数问题或者d i f f i e h e l l m a n 问题的困难性的。 定义2 8 离散对数问题( d l p ) 设p 是大素数，口是有限域巧= 1 ，2 ，p - l l o 第h 二章皋本概念和梁奉知识 的一个生成元，c ，求满足同余方程口。= f l r o o dp 的整数x ：o x p 一2 。 离散对数问题是个假设为困难的问题，我们可以看出这个问题的困难性取决于问 题的规模，即有限域巧的大小，以及参数口、的选择。当参数选得比较小时， 这个问题并不是困难的，所以精确描述困难性，就要准确描述问题规模和参数的 选择。 定义2 9 一般离散对数问题( g d l p ) 给定个阶为n 的有限循环群g ，g 的一 个生成元g 和一个元素h e g ，求解整数0 x n - 1 ，使得9 1 = h 。 定义2 1 0 复合离散对数问题( c d l p ) 给定( n ，g ，s ，y ) ，其中n 是一个r s a 模，n = p q ( p 、q 为大素数，且p - 1 ，q - 1 都是非平滑的) 。g z ：，且满足 ( 1 ) 1 d 耐2 ( g ) g 2 ，g 1 的生成元p ，则( ( g l ，g 2 ，e ) 上 的c b d h p 为：给定( p ，a p ，b p ，c p ) ，判断h 是否等于e ( 尸，尸) “，h e g 2 。 2 1 4 双线性映射 定义2 1 3 设g 是一个阶为q ( q 是一个大素数) 的循坏群，p 、只、最、q 都是g 的生成元，v 是另一个阶为q 的乘法循环群。 在g 和v 上的离散对数问题构成数学 难题2 个群之间的双线性映射e ：g g v 满足以下条件： ( a ) 双线性，p ( 曩+ 昱，q ) = p ( 鼻，q ) e ( g ，q ) ，j le ( q ，异+ e ) = e ( 片，q ) e ( p 2 ，q ) 或 e ( a p ，b q ) = e ( p ，q ) ”； ( b ) 非退化性，存在p g ，q g ，使得e ( p ，o ) 1 ； ( c ) 可计算性，对于所有的p ，o g 存在高效的算法可计算出e ( p ，q ) 。 我们称e 为双线性配对。 2 2 椭圆曲线基础知识 将椭圆曲线用于公钥密码学的思想是1 9 8 5 年由v i c t o rm il l e r 1 9 及n e a l k o b l i t s 2 0 共同提出的。其理论基础是定义在有限域上的某一椭圆曲线上的有 理点可构成有限交换群。如果该群的阶包含一个较大的素因子，则其上的离散 对数问题是计算上难解的数学问题。也已证明，除了某些特殊的椭圆曲线外， 目前已知的最好的攻击算法也是指数级的。就安全强度而言，密钥长度为1 6 3 比特的椭圆曲线密码体制( e l l i p t i cc u r v ec r y p t o s y s t e m ，e c c ) 相当于1 0 2 4 第二章摹奉概念和暴奉知识 比特的r s a 。即在相同安全强度下，e c c 使用的密钥比r s a 要短约8 4 。这使得 e c c 对存储环境空间、传输带宽、处理器的速度要求较低。 2 2 1 椭圆曲线的概念 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周 长的方程类似。般用韦尔斯特拉( w e i e r s t r a s s ) 方程描述： y 2 + 口i x y + a 3 y - - = x 3 + 口2 x 2 + n 4 x + a 6 ( 2 1 ) 其中口，f ，f 可以是有理数域、复数域，还可以是有限域。满足上面方 程的点( x ，y ) 就构成椭圆曲线。定义中包括一个称为无穷点的元素，记为0 。 密码学中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方 程定义式( 2 1 ) 中，所有系数都是某一有限域c 中的元素，这罩可以选择q = p ， p 是一个大的奇素数：或者q = 2 ”，一个2 的幂。这样，在q = p 的情况下，选择 的域便是f p ，p 是模数：在q = 2 ”的情况下，选择的域便是只脚。其中最为常用 的是由式( 2 2 ) 定义的曲线方程： y 2 兰x 3 + a x + b ( m o dp ) ( 拉，bec ，4 a 3 + 2 7 b 2 ( m o dp ) o ) ( 2 2 ) 令e ( ) 表示基于有限域c 上的椭圆曲线；点p 对应一对坐标( x ，y ) ，其对 称点用一p 表示，常表示为# e ( c ) 。 定义2 1 4 在基于有限域f p 的椭圆曲线上的点构成的群的元素个数称为该 群的阶，常表示为# e ( c ) 。 定义2 1 5 设p 是椭圆曲线e ( c ) _ i z 的- a ，如果存在最小的整数，使得 n p = 0 ，那么称p 点的阶为n 。由群的性质知l q 是椭圆曲线群的阶# e ( ) 的因子。 下面从几何的角度介绍一下椭圆曲线e ( c ) 上的“加法”，如图2 1 所 示：p ( 五，y 。) 和q ( 恐，y ：) 是椭圆曲线e ( c ) 上不同的两个点，连接点p 和q 交曲 线于另一点，过该点作平行于纵坐标轴的直线与曲线相交于点r ( 毛，儿) ，则