（应用数学专业论文）基于双线性对的数字签名研究.pdf

陆怡基丁双线性对的数字签名研究 摘要 在现代高速发展的信息社会中，数字签名作为一种保证数据安全的重要工具 正日益受到人们的重视。类似于以往的手写签名，数字签名不但要求签名者身份 的准确性，而且要求签名方便于信道的传输。一般的数字签名需要具有以下四个 性质：保密性，认证性，完整性和不可否认性。随着数字签名理论的不断发展， 人们对他的使用性也不断提出更高的要求：数字签名需要更强的安全性，需要更 少的存储空间，需要更短的密钥 基于此，b o n e h 和f r a n k l i n 于2 0 0 1 年提出了基于双线性对的短签名，它所具 有的优越的性质使我们认识到双线性对这一数学工具在密码学中的重要性。 本文首先介绍数字签名中一些相关的基本概念，然后介绍双线性对及其重要 性质。最后，结合双线性对的这些性质，我们提出了基于双线性对的两个数字签 名方案和一个数字签密方案，并分析这三个方案的安全性及优越性： 在群签名方案中，我们结合群签名和尉g 口所以，公钥体制的思想，提出了基于 椭圆曲线上目g a 朋口，公钥体制的群签名方案。该方案可以防止群管理员和群成员 的联合伪造攻击，计算简单，而且需传输的数据量少，方案比较有效； 在卡梅隆签名方案中，我们知道：卡梅隆签名是一种非交互式的数字签名， 使用的h 嬲办函数是一种特殊的陷门单向月弧乃函数卡梅隆胁砌。卡梅隆数字 签名具有不可传递性，不可否认性等优点。本方案应用双线性对，提出了一个基 于身份的卡梅隆数字签名方案； 在签密方案中，我们提出了一个基于访问结构的多代理签密方案，实现了多 代理签密中既认证又保密的要求，并且是第一个基于访问结构的多代理签密方案。 通过分析表明，本方案是正确，安全的。 关键词：数字签名：双线性对：e ，g 口聊口，公钥体制：椭圆曲线 a b s t r a c t i nt h em o d e m d e v e l o p e di n f o r m a t i o ns o c i e 够，t h ed i g i t a ls i g n a t l l r e ，a sa 1 1i m p o n a i l t m e t h o dt op r o t e c td a t ei n f o m a t i o n ，h a sb e e nd r a w i n gt h ea t t e n t i o no fm o r ea 1 1 dm o r e r e s e a r c h e r s a sw h a tt h eh a j l d w r i t i n gs i g n a t u r ed o e s ，t h ed i g i t a ls i g n a t u r en o to n l yn e e d t ob e e n s u r e dt h e i d e n t i t y o ft h e s i g n e r，b u ta l s o t h ec o n v e i l i e n to fc h a n n e l t r a n s m i t t i n g g e n e r a ls p e a k i n g ，t h ed i g i t a ls i g n a t u r ec a l l r e a l i z et h ef o l l o w i n gf o u r s e c u r i t ya i m s ：s e c u r i t y ，a u t h e n t i c a t i o n ，i n t e g r a l i t ) ，a n du n d e n i a b l e w i t ht h eg r 0 训| ho f t h ed i g i t a ls i g n a t u r e ，m o r ea 1 1 dm o r er e q u i r e sa r eb r o u g h tf o n a r d ，s u c ha sh o wt om a l ( e t h es i g n a t u r em o r es e c u r i t y ，t om a k em es i g n 硼l r eo c c u p yt h el e s ss t o r er e s o u r c ea n dt h e s e c r e tk e ya ss h o r ta si tc a nb eu n d e rt h ee n s u r i n gs e c u r i t yc o n d i t i o n l o t so fr e s e a r c h e r sh a v ed o n ea b u l l d a n t 、v o r ki nt h i sw a y s i n c eb 0 n e ha n df r a n l ( 1 i n p r e s e n t t h es h o r t s i g n a t u r e s c h e m ef r o mb i l i n e a r p a i r i n g si n 2 0 01 t h eb i l i n e a r p a i r i n g s ，b e c a u s eo f i t sv i r t u e ，c o m et ob ea j li m p o r t a mt o o li nt h ec r ) r p t o g r a p h y t h er e s e a r c ho ft h i st h e s i sf o c u s e so nt h ed i g i t a ls i g n a t u r ew h i c hi sb a s e do nt h e b i l i n e a rp a i r i n g s f i r s t l yt h et h e s i si n t r o d u c e ss o m eb a s i cc o n c e p t sa 1 1 dt o o l sw h i c ha r e u s e db yt h es i g n a t u r e ；s e c o n d l yw ei n t r o d u c et h eb i l i n e a rp a i r i n g sa n dp r i n c i p l e s ；a tt h e e n d ，w ep r o p o s a l t w os i g n a t u r es c h e m e sa n das i g n c r y p t i o ns c h e m ew h i c ha r eb a s e do n t h eb i l i n e a u rp a i r i n g s ，t h e nw ea n a l y s i st h es e c u r i t ya n dt h es u p e r i o r i t yo ft 1 1 e m i i lt h eg r o u ps i g n a t u r es c h e m e ，a c c o r d i n gt oe l g 锄a lp u b l i ck e yc r y p t o s y s t e ma n d g r o u ps i g n a t u r e ，t h i ss c h e m eg i v e r sag r o u ps i g n a t u r es c h e m eb a s e do ne l g a l l l a lp u b l i c k e yc r y p t o s y s t e mo v e re l l i p t i cc u r v e i tc a na v o i dt h ec o m m o nf o 培e 巧a t t a c ko ft h e 掣o u pm e m b e ra n dt h eg r o u pm a n a g e r t h es c h e m eh a sr e l a t i v e l ys m a l lc o m p u t a t i o n a l c o m p l e x i 够，a j l dt h e 锄o u n to fd a t an e e dt ob et r m s f e l l r e di sv e r ) ，s m a h ，s ot h i s l o g a r i t h ni sr e l a t i v e l ye m c i e n t ； i nt h ec h 锄e l e o n s i g n a t u r es c h e m e，w e k n o wt h a tc h 锄e l e o ns i g l l a t u r ea r e n o n - i n t e r a c t i v es i g n a t u r e s ，i t sb u i l d i n gb l o c ki sc h a m e l e o nh a s hf u n c t i o n ，at r a p d o o r o n e - w a yh a s hm n c t i o n t h ed i s t i n g u i s h i n gc h a r a c t e r i s t i co fc h a m e l e o ns i g na t l 盱ei s n o n t r a n s f e r a b l ea n dn o n - r e p u d i a t i o n t h i ss c h e m ep r o p o s e sai d b 塔e dc h 锄e l e o n d i g i t a ls i g n a t u r ef r o mb i l i n e a rp a i r i n g s ； i nt h es i g n c 巧p t i o ns c h e m e ，w eg i v eam u l t i p r o x ys i g n c r y p t i o ns c h e m eb a s e do nm e 陆怡基于双线性对的数字签名研究 a c c e s ss t l l l c t u r ew h i c hp r o v i d e si n c e n t i v et o c o o p e r a t e w i t ha u t h e n t i c a t i o na 1 1 d c o n f i d e n t i a l i t y t h es c h e m ei st h ef i r s tm u l t i - p r o x ys i g n c r y p t i o ns c h e m eb a s e do n 也e a c c e s ss t m c t u r e i ti sa n a l y z e dt h a tt h i ss c h e m ei sc o r r e c ta 1 1 ds e c u r e k e y w o r d s ：d 珥t a ls i g na t u r e ；b i l i n e a rp a i m g ；e 1 g 锄a lc r ) ，p t o s y s t e m ；e l l i p t i cc u n ，e 陆愉基于双线性对的数字签名研究 5 3 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 学位论文作者签名：辟1 咯 签字日期： 一2d 谚年占月，2 日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 学位论文作者签名：陆恬 签字日期：夕啷年月肜日 翩签名：奄抛 签字日期：五功庐厶月i q 日 陆怡基于双线性对的数字签名研究 第一章引言弟一早亏i 画 1 1 密码学简介 密码学是一门古老而又年轻的科学，它在军事和外交通信上的应用可以追溯到 几千年以前。在当今的信息化时代，大量的敏感信息如病历，法庭记录，资金转 移，私人财产等常常通过计算机网络和公共通信设施来进行数据传输，而这些信 息的秘密性和真实性是人们迫切需要得到证实的。因此，现代密码学的应用已经 不再仅仅囿于军事，政治和外交，其商用价值和社会价值也已经得到充分的肯定。 密码学的发展历史大致可以分为以下三个阶段 4 2 ，4 3 ，4 4 ，4 5 ： 第一阶段为从古代到l949 年。这一时期可以看作是科学密码学的朦胧时 期。这段时期的密码技术只可以称之为是一种技术，而非是一门科学，密码学专 家也只是凭借自己的直觉和信念来进行密码设计和分析，而不是通过精确的计算 和理论推导。 第二阶段为从1949 年到1975 年。1949 年s h a n n o n 发表的保密系 统的信息理论一文为私钥密码系统的建立打下了深刻的理论基础，从此密码学 成为了一门真正的科学。可以这么认为，现在的密码学是艺术和科学的完美结合， 是一门具有艺术性的科学。这段时间关于密码学理论的研究进展工作不大，公开 的密码学文献也很少。19 67 年k a h n 出版了一本关于密码学的专著破译者， 该书没有任何新的技术思想，只是记载了一段值得注意的完整经历，包括政府在 内仍然认为是一些秘密的事件。它的意义不仅在于它记载了1967 年之前密码 学发展的经历，而且使很多大众认识了真正的密码学。70 年代初，i b m 发表了 f e i s t e l 等人在这一领域的一些工作。 第三阶段为1976 年至今。1976 年斯坦福大学的赫尔曼( m e h e l l m a n ) ， 迪菲( w d i f f i e ) 和默克尔( r m e r k l e ) 联合发表了密码学的新方向一文， 首次提出了公开密钥体制的思想。这一思想导致了密码学上的一场技术革命。他 们首次证明了在信道发送端和接收端无密钥传输的保密通信是可能的，从而开创 了公钥密码学的新纪元。公钥密码在加密与解密时使用不同的密钥，把加密过程 2 扬州人学硕+ 学位论文 和解密过程设计成不同的途径。当算法公开时，在计算上不可能由加密密钥求解 解密密钥，因而加密密钥可以公开，只需秘密保存解密密钥。如图 1 所示： 隧匿酬i 篱豢鳃熹溶! 陋围虽酬鞠赠蕊卜固 匮蟹圈匝基童圈 图l 1 在使用公钥密码体制进行通信时，明文脚用加密密钥疋进行加密，而收方则 用与加密密钥不同的解密密钥髟进行解密。因为加密密钥e 和解密密钥k ，是一 一对应的，所以使用加密密钥加密的密文只能用解密密钥进行解密。并且想 从解密密钥k 推出加密密钥妫在实际上是不可能的。若以髟作为加密密钥，疋 作为解密密钥，则可实现一个用户加密的信息可由多个用户解密，即数字签名。 密码学是一门研究密码系统和通信安全的科学。它主要包括两个方面：密码编 码学和密码分析学。密码编码学主要致力于寻求保证信息保密性和认证性的方法， 密码分析学主要致力于加密信息的破译和防止伪造的方法。密码编码学和密码分 析学相互促进，相互发展，它们共同推进了密码学的发展。采用密码技术可以隐 蔽和保护需要保密的信息，使未授权者没有能力提取信息。被隐蔽的信息称为明 文，隐蔽后的信息称为密文。将明文变换成密文的过程称为加密，反之，将密文 破译成明文的过程称为解密。对明文进行加密操作的人员称为加密员。密码员对 明文进行加密时所进行的一组操作称为加密算法，传输信息的预定对象称为接收 者，他对密文进行的一组解密操作称为解密算法。加密算法和解密算法都在一组 相关密钥的控制下运行，所对应的密钥分别称为加密密钥和解密密钥。 根据密钥的特点，我们可以将密码体制分为对称密码体制和非对称密码体制。 对称密码体制又称为私钥密码体制，非对称密码体制又称为公钥密码体制。在私 钥密码体制中，加密密钥和解密密钥是一样的或者是容易互相确定的，而在公钥 密码体制中，加密密钥和解密密钥是不同的或者不容易互相确定。在私钥密码体 陆怡基于双线性对的数字签名研究 3 制中，按照加密方式又可以分为流密码和分组密码。在流密码中，明文信息按照 字符逐位进行加密；在分组密码中，将明文信息进行分组，然后按组进行加密。 在公钥密码体制中，加密密钥和解密密钥是不同的，或者说很难从一个密钥推出 另一个密钥。现在的公钥密码体制大多采用分组密码，而概率加密体制一般采用 流密码。 在信息传输和系统处理中，除了预定的接受者，还有非授权者，他们通过搭线 窃听，电磁窃听，声音窃听等多种窃听方式来获取机密信息，我们称其为截收者。 他们虽然不知道系统采用的密钥，但是他们有可能从截获的密文中推断出明文， 这一过程称之为密钥分析。从事上述分析工作的人员称为密码分析员。密码系统 所遭受的另一类攻击称为主动攻击：非法入侵者主动窜扰系统的正常工作，采用 删除，增改，重填，伪造等手段向系统注入假信息，以达到损人利己的目的。所 谓一个密码是可破的是指：从明文可以迅速的确定密文或者所采用的密钥，或通 过明文一密文对迅速确定出密钥。通常假设密码分析者是知道所采用的密码系统 的，这个假设称为k e r c k h o f f 假设。当然，如果密码分析者不知道所采用的密码 系统，那么将大大加大他破译密码的困难度。但是我们一般不假设密码分析员不 知道所采用的密码系统。因此，在设计一个密码系统时，我们一般要求在k e r c k h o f f 假设下达到安全性。 破译密码的方法有穷举破译法和分析法两种。所谓穷举法又称为强力法，是指 对所截获的密文依次采用各种可能的密钥试译，直到得到有意义的明文为止，或 者在密钥不变的情况下，对所有可能的明文进行加密，直到得到与所截取的密文 一致为止。只要有足够的计算时间和存储空间，穷举法在理论上是可行的。但在 实际操作中，时间和空间上都是受限的，所以穷举法又是不可行的。分析破译法 又分为确定性分析法和统计分析法两类。确定性分析法是利用一个或几个已知量 用数学关系式表达出未知量。统计分析法是利用明文的一些已知的统计规律来破 译的方法，密码分析者对所截获的密文进行统计，并与明文的统计规律进行比较， 从中提取出明文和密文的对应信息。密码分析者之所以能成功的破译密码，关键 原因是明文中信息的冗余度。 4 扬州大学硕+ 学位论文 根据密码分析者破译时所具有的前提条件，人们将攻击类型分为四种类型：唯 密文攻击，己知明文攻击，选择明文攻击和选择密文攻击： ( 1 ) 唯密文攻击：密码分析员有一个或更多的用同一密钥加密的密文，通过对这 些截获的密文进行分析得到明文或密钥； ( 2 ) 已知明文攻击：除了待解的密文外，密码分析员有一些明文和用同一密钥加 密的对应密文； ( 3 ) 选择明文攻击：密码分析员可以得到任何明文所对应的密文，这些密文与待 解的密文是用同一密钥加密得到的； ( 4 ) 选择密文攻击：密码分析员可以得到任何密文所对应的明文，解密这些密文 所需要的密钥和待解的密钥是一样的。 上述四种攻击类型的强度按序递增，唯密文攻击是最弱的一种攻击，选择密文 攻击是最强的一种攻击。选择密文攻击可以用于分析公钥密钥体制。如果一个系 统可以抵抗选择明文攻击，那么他可以抵抗唯密文攻击和已知明文攻击。 为了保护信息的机密性，抵抗密钥分析，保密系统应该满足以下性质： ( 1 ) 系统即使达不到理论上是不可破的，也需要达到实际上是不可破的。即从截 取的明文一密文对，要确定密钥或者是明文在计算上是不可行的； ( 2 ) 系统的保密性不依赖于加密体制的保密( 即k e r c k h o f f 假设) ，而依赖于密 钥的保密； ( 3 ) 加密算法和解密算法适用于密钥空间中所有的元素； ( 4 ) 系统易于实现又便于使用。 防止消息被篡改，删除，重放和伪造的一种有效的方法是使发送的信息具有被 验证的能力，使接受者有能力识别和确认消息的真伪，实现这类功能的密码系统 称为认证系统。信息的认证性和信息的保密性不同：保密性是指截获者在不知道 密钥的情况下无法解读密文的内容，而认证性是任何不知道密钥的人不能构造出 一个密报，而只有选定的接收者才能解密出j 下确的密文。认证理论和技术是最近 2 0 年随着计算机通信的普遍应用而迅速发展起来的一个重要的密码学研究领域。 如传统的手写签名正在被更迅速，安全和可靠的数字签名所取代。一个安全的认 陆怡基于双线性对的数字签名研究 证系统应该满足下述的基本要求： ( 1 ) 意定的接收者可以检验和证实消息的合法性和真实性； ( 2 ) 消息的发送者对所发送的消息不能抵赖； ( 3 ) 除了合法的消息发送者外，其他人不能伪造出合法的消息。而在已知合法密 文和相应消息下，要确定加密密钥或系统的伪造合法密文在计算上是不可行的； ( 4 ) 当通信双方发生争执时，可由称为仲裁者的公正的第三方解决争执。 一般而言，在密码学术语中，“体系”，“方案 和“算法”本质上是一回事。 1 2 数字签名简介 政治，军事和外交等活动中签署文件，商业上签定契约和合同，以及日常生活 中写书信，在银行取款等事物中的签字，传统上都采用手写签名和印章。签名起 到认证，核准和生效的作用。随着信息时代的来临，人们希望通过数字通信网络 进行迅速，远距离的贸易合同签名，因此，数字签名应运而生，开始应用于商业 通信系统，诸如电子邮件，电子转帐和办公室自动化系统等。 数字签名和手写签名的主要区别在于以下几点 4 1 ： ( 1 ) 在签署文件方面，一个手写签名是所签文件的物理部分，而数字签名不是所 签文件的物理部分，所以所签的数字签名必须想办法绑定到所对应的文件上； ( 2 ) 在验证方面，一个手写签名是通过和一个真实签名相比对来验证的；而数字 签名是能通过一个公开的数字签名验证算法来验证的，任何人都能验证签名的真 伪。所以安全的数字签名能有效的阻止伪造签名的可能性； ( 3 ) 在复制方面，一个手写签名是不太容易复制的；而一个数字签名的复制是非 常容易的。这一特点要求我们必须阻止数字签名的重复使用，可以考虑使用同期 时截等方法来达到防止重复使用的要求。 一个数字签名方案至少应该具备以下几个要求： ( 1 ) 签名者事后不能否认自己的签名； ( 2 ) 接收者能验证签名，其他任何人都不能伪造签名； 6 扬州人学硕士学位论文 ( 3 ) 当双方关于签名发生争执时，需要一个公j 下的第三方进行解决争执。 手写签名基本符合上面的条件，而数字签名是以电子形式进行存储的信息的 一种，并且需要在网络通信中进行传输。基于公钥密码体制和私钥密码体制都可 以进行数字签名，目前主要集中于比较实用的公钥密码体制的数字签名的研究。 根据接受者的不同数字签名可以分为真数字签名和仲裁数字签名两类。在真数 字签名中，签名者直接把消息发送给接受者，接收者无须求助于第三方就可直接 验证签名；而在仲裁签名中，签名者把消息通过可信任的仲裁第三方发送给接受 者，而接收者不能独立的验证签名，需要与仲裁第三方合作才能验证签名。 在计算能力上，数字签名可以分为无条件安全的数字签名和计算上安全的数字 签名。现有的数字签名大多是计算上安全的数字签名，如：r s a 数字签名，e l g a m a l 数字签名等。所谓计算上安全的数字签名是指任何伪造者伪造的数字签名在计算 上是不可行的。 从签名者在一个数字签名中所签消息的次数可以分为一次数字签名和多次数 字签名。一次数字签名只能签一个消息，如果签多个消息，伪造者就可能伪造出 真的签名。另外，一次签名具有很强的安全性。 数字签名还可以按照其他形式进行划分，我们以上只是简略的概述一下。 1 3 本文的组织结构 第二章主要介绍公钥密码算法，椭圆曲线密码学，几种常见的数字签名算法， h a s h 函数以及秘密共享的一些基本概念，为以下提出的三个数字签名算法做理论 上的准备； 第三章主要介绍了双线性对的概念和一些性质，并且介绍了一种特殊的双线性 对t a t e 对。利用它的性质，我们可以构造出更符合现代要求的数字签名方案。 第四章我们结合双线性对，构造出了三个安全，实用的数字签名方案：基于双 线性对的群签名方案，基于双线性对的卡梅隆签名方案，基于双线性对的访问结 构多代理签密方案。 陆怡基丁双线性对的数字签名研究 7 第五章我们依次分析了这三个数字签名的安全性及优越性，体现了双线性对在 密码学中的实用性。 第六章是本文的总结和展望。 扬州大学硕士学位论文 第二章基本概念 帚一早昼今僦忍 2 1 公钥密码算法 在私钥密码系统中，加密密钥和解密密钥是相同的或者解密密钥很容易从加密 密钥中推出。因此，加密密钥的泄露将使密码系统变的不安全。私钥密码系统的 另一个缺点是需要一个绝对安全的信道预先传送密钥，这一点在实际操作中将占 用很多资源。 公钥密码系统解决了这些问题。在公钥密码系统中，加密密钥和解密密钥是不 同的，或者说从加密密钥很难推出解密密钥；并且，通信双方不必要预先传送密 钥。 1 9 7 6 年斯坦福大学的赫尔曼( m e h e l l m a n ) ，迪菲( w d i f f i e ) 和默克尔 ( r m e r k l e ) 联合发表了密码学的新方向一文，首次提出了公开密钥体制的 思想。这一原创性的思想给密码学带来了重大的变革。 1 9 7 7 年马萨诸塞理工学院里夫斯特( r l - r i v e s t ) ，沙米尔( a s h a m i r ) ，艾 德勒曼( l a d l e m a n ) 研究出的一种利用素因数分解的困难性而设计的一种公钥密 码算法。他们的研究成果在1 9 7 7 年4 月以“数字签名和公开密钥密码体制”为题 公开发表，并受到高度评价。这就是著名的r s a 密码算法。 随后，密码学家基于类似的非多项式计算问题，提出了大批的公钥密码算法： e 1 g a m a l 算法，r a b i n 算法，m e r k e h e l l m a n 背包算法，m c e li e c e 算法，二次剩余 算法和椭圆曲线算法等。 2 1 1 公钥密码算法的观点 d i f f i e 和h e l l m a n 建议利用n p 问题设计加密算法。他们推测如果把信息通过 编码加密在一个n p 问题中，那么破译这个问题等同于n p 问题。那么，这类算法 不可能在多项式时间算法内得到解决。为了构造这样的密码，秘密的陷门信息必 须被嵌入在一个涉及单向函数求逆的计算难问题上。一个函数厂，如果对它的定 义域上的任意z 都易于计算厂( x ) ，而对于厂的值域中的几乎所有的y ，即使当厂已 陆怡基于双线性对的数字签名研究 9 知时，要计算厂1 ( x ) 也是不可行的，我们称这样的( x ) 是单向函数。这一辅助信 息就是秘密的解密密钥。这就是设计公钥密码体制的基本原理。这类密码的强度 取决于它所依据的问题的计算复杂度。然而，计算上的困难性问题不一定会产生 一个强密码系统。这是因为：1 复杂性理论处理的一般是一个问题的独立情况， 而密码分析常常处理大量的有联系的问题；2 复杂性一般是用最坏情况或平均 情况来度量，而一个密码算法要求几乎在所有情况下都是难解的；3 要保证密 码难破解，得保证只有通过陷门信息才能对单向函数反向求值。 需要注意的是： ( 1 ) 公钥密码系统的安全性是计算安全的，而不是无条件安全的；因为它基于n p 问题并不是不可解的，而是难解的； ( 2 ) 单向函数在密码学中很重要，但是目前使用的单向函数都未能被证明是单向 的，只是被广泛认为是单向的。 2 1 2 r s a 算法 r s a 算法的理论基础是一种特殊的可逆模指数运算，它的安全性基于大数分解 的困难性。r s a 算法描述如下： 系统参数：取两个大素数p 和g ，z = p g ，缈( 刀) = ( p 1 ) ( g 一1 ) ，随机选择整 数p ，轲茸足g c d ( p ，妒( ”) ) = 1 ，p d 兰1 ( m o d 妒( 以) ) 。 公开密钥：刀，d 。 私有密钥：p ，g ，p 。 加密算法：对于待签消息所，其对应的密文为c = e ( 聊) 三聊。( m o d 刀) 。 解密算法：d ( c ) 三c d ( m o d 刀) 。 使用r s a 密码时应注意如下的事项： ( 1 ) 不能使用共同的模刀。如果使用相同的模玎，可能会出现以下主要问题： 如果相同的明文m 分别送给两个不同的使用者，则此系统可能变得不安全： 拥有一对加解密密钥就能分解因数；拥有一对加解密密钥，就能在不必 分解的情况下，求出另一对加解密密钥。 1 0 扬州大学硕士学位论文 ( 2 ) 明文的熵应尽可能地大。如果所需加密的明文的熵非常小，利用确定式 的公开密钥加密系统，它的安全性将无法抵抗低熵攻击法。因此p 硒s f 1 建议 在使用公钥加密时，至少应插入8 个字节的随机数，以抵抗低熵攻击。 以上注意事项，均直接或间接关系到r 删公钥体制的安全性。若参数参数选择 不当，则以这些参数构成的尺删密码在理论上将不安全；若使用不当，即使安 全的r 删系统也会使得密码协议不安全。 r s a 应注意的相关参数选择可归纳如下： ( 1 ) 素数p 和g 应选择为强素数 素数p 是强素数，意指它满足下面两个条件： ( 2 ) 存在两个大素数a 及仍，使得易ip 一1 ，仍ip + 1 ； ( 3 ) 存在四个大素数，吃，毛和，使得la l ，置ia + 1 ，吃ip 2 1 ， s 2p 2 + 1 。 这里，称，吃，墨和j ：为3 级素数，称p 。及仍为2 级素数，称p 为1 级素数。 r s a 的安全性基于因子分解，故门的质因子p 和g 必须选择适当，以确保因子 分解在计算上( 有效时间内) 不可能实现。若p 和g 不是强素数，则可通过下 面的方法求出因子分解。 七 假设p 一1 有七个质因子，且可写成p 一1 = 兀钟，其中q 为非负整数，只为素 _ l 数，扛1 ，2 ，后。因为p 一1 的质因子a ，p 2 ，仇均很小，不妨设只 b ( b 为 七 已知小整数) 。令正整数a ，尺满足：口q ，r = 兀开，p 一1r 。因为p 为 ，= 1 素数，任取小于p 的f 整数f ，不妨设f = 2 ，由费马定理知，2 尺兰1 ( m o dp ) 。 计算出2 凡在模数刀中的约化数x ( x 三2 rm o d 玎) ，若x = 1 ，则令f = 3 ，计算 x ，直到x 1 ，则g c d ( x 一1 ，刀) = p ，即分解，z 成功。对于g 有类似的情况。 因此，若p 和g 不为强素数则可在有限时间内分解。 ( 4 ) 素数p 和q 的位数差不能太小 陆怡 基于双线性对的数字签名研究 1 l 若p 和g 的位数相差的不大，则可通过下面的方法分解，z 。设f = 旦# ， z ：旦，由于( p g ) 2 ：( p + g ) 2 4 p g ，则f 2 一办2 ：刀。由于办比较小，故可 z 从大于石的整数依次尝试f ，并通过f = 旦# ，乃：而计算p 和g 。 z ( 5 ) 素数p 和g 的位数差不能太大 p 和g 的位数又不能相差很大。若很大，则可通过尝试法从小的素数依次实验 的办法分解，z 。因此p 和g 的位数相差不能大，也不能小，一般是几比特。 ( 6 ) 数p 一1 和9 1 的最大公因数应很小 如果p 一1 和g 一1 的最大公因数很小，则研聊聊d ，2 s 和d 括证明了r 删可能在 不需要分解因数，2 的情况下被破解。可以考虑下面的破解法( 密文攻击法) ： 设破密者获得密文c = m 8m o d 刀。破密者令c 1 = c ，然后计算下列各式： c 2 = g m o d = ( m 8 ) 2 = m 矿m o d ，c j = 1 = m m o d 若e = 1 m o d ( 刀) ，则e = m m o d 且p “1 = p m o d 矽( 刀) ，c f + 1 = c 1 = c m o d 。 如果f 很小，利用此攻击法可以获得明文m 。由欧拉定理知 扛( ( p 一1 ) ( g 一1 ) ) ，若p g 和g 一1 的最大公因数很小，则可以避免此攻击法。 ( 7 ) 素数p 和g 应大到使得分解因数咒在计算上不可能 很明显，如果能分解因数，? ，则r 删即能被破解，因此p 和g 的长度必须大到 分解因数为计算上不可能。数学家估计分解z + 1 0 位数的困难程度大约是分 解x 位数的1 0 倍。以现在一般商业上应用而言，选择为5 1 2 位或1 0 2 4 位。 ( 8 ) 解密密钥d 的选择 为了提高解密效率应尽可能选择小的d ，但是若d 太小也有安全隐患。比如已 知明文聊，加密后得密文c = 所。m o d 刀，我们可通过穷举d 依次检验 l c d = 聊i n o d ，z 是否成立。因此d 不应选得太小，一般为d 刀4 。 ( 9 ) 加密密钥p 的选择 p 应满足它的阶尽可能大，并且本身不能太小。对于明文聊，密文c = 聊8m o d ，2 ， 1 2 扬州人学硕士学位论文 若p 选得较小，且，2 8 ，z ，可直接将c 开p 次方得到明文聊。一般情况下，选 择p 为1 6 位的素数，既可以加快加密运算，又能避免低指数攻击。 另外，p 应选择使其在矽( 刀) 中的序为最大，即p 。= 1 m o d 矽( 胛) 中最小的f 为 ( p 一1 ) ( g 一1 ) 2 。 ( 1 0 ) 模数，z 的使用限制 对于给定的模数刀，满足p j 谚= 1 ( m o d 船) 的加，解密密钥对( p ，4 ) 很多，因此有 人建议在通信中用一个参数，z 以节约存储空间。但可证明这对于系统来说是有 安全隐患的。实际上，假设密钥对( q ，谚) ，( 巳，嘭) 是同一参数，? 的两个不同参 数对，当( 口，p ，) = 1 时，对于同一明文胧分别加密得密文q = 朋白m o d 刀， 巳= 肌勺m o d ，z 。由欧几里德算法知，必然存在整数f 和s ，满足，q + s 勺= 1 ， 因此有0 c ；= 朋“”巳兰聊m o d 刀。 2 1 3 eig a m ai 算法和离散对数问题 e 1 g a m a l 加密算法的安全性是基于有限域的乘法群上的离散对数问题的难 解性。 随机选取一大素数p ( 2 0 0 位十进制数) ，选一个数g ( 模p 的本原根， 1 g p 一1 ) ，把p ，g 对每个用户公开。 密钥生成：随机选取一整数x ( 1 x p 一1 ) 作为用户的私钥，记为d = ( x ) ； 计算y = g 。n l o d p ；将e = ( y ) 公开，作为用户的公开密钥。 加密过程：要加密信息m ，首先在公开密钥数据库中查得用户的公开密钥： e = ( y ) ； 随机地取一整数尼( 1 七 3 ，所是一正整数，c 是特征为p 的有限域， 域上的非奇异耽耙瑙舭珊方程y 2 + q 砂+ 吗y = x 3 + 口2 x 2 + 以4 x + 吼，口f 的所有 解( x ，y ) ，再加上无穷远点d 就可以生成上的椭圆曲线e ( 乞) 。 令e ( f ) 为有限域，上的一条椭圆曲线，点p e ( f ) ，若存在最小正整数，2 ， 使得卯= d ( o 是椭圆曲线上的无穷远点) ，则称胛是点尸的阶。对于给定的点 q e ( f ) ，e ( f ) 上的离散对数问题( 删尸) 即求整数x ，使得卯= q 。 将明文脚嵌入到椭圆曲线e 上的已点，选一点b e ，b 的阶为g ，g 是素数， 上的离散对数问题是难解的，每个用户都选择一个数口，o 口 曰，口保密， 口b 公开，欲向么发送明文聊，选取一随机整数七，且( o 后 g ) ，将数偶 ( 船，巴+ 尼( b ) ) 发送给彳，是么的私钥，么可以从柚得到柚，通过求 己= 巴+ 尼( b ) 一船，可以恢复乞，从而恢复明文聊。 2 3 数字签名 陆恰基于双线性对的数字签名研究 1 7 在文件上手写签名长期以来被用作作者身份的证明，或表明签名者同意文件的 内容。实际上，签名体现了以下几个方面的保证： ( 1 ) 签名是可信的。签名使文件的接收者相信签名者是慎重地在文件上签名的。 ( 2 ) 签名是不可伪造的。签名证明是签字者而不是其他的人在文件上签字。 ( 3 ) 签名不可重用。签名是文件的一部分，不可能将签名移动到不同的文件上。 ( 4 ) 签名后的文件是不可变的。在文件签名以后，文件就不能改变。 ( 5 ) 签名是不可抵赖的。签名和文件是不可分离的，签名者事后不能声称他没有 签过这个文件。 而在计算机上进行数字签名并使这些保证能够继续有效则还存在一些问题。 首先，计算机文件易于复制，即使某人的签名难以伪造，但是将有效的签名 从一个文件剪辑和粘贴到另一个文件是很容易的。这就使这种签名失去了意义。 其次，文件在签名后也易于修改，并且不会留下任何修改的痕迹。 有几种公开密钥算法都能用作数字签名，这些公开密钥算法的特点是不仅用 公开密钥加密的消息可以用私钥解密和，而且反过来用私人密钥加密的消息也可 以用公开密钥解密。其基本协议很简单： ( 1 ) a l i c e 用她的私钥对文件加密，从而对文件签名； ( 2 ) a l i c e 将签名后的文件传给b o b ； ( 3 ) b o b 用a l i c e 的公钥解密文件，从而验证签名。 在实际过程中，这种做法的准备效率太低了。从节省时间，数字签名协议常 常与单向散列函数一起使用。a l i c e 并不对整个文件签名，而是只对文件的散列值 签名。 在下面的协议中，单向散列函数和数字签名算法是事先协商好的： ( 4 ) a l i c e 产生文件的单向散列值； ( 5 ) a l i c e 用她的私人密钥对散列加密，以此表示对文件的签名； ( 6 ) a li c e 将文件和散列签名送给b o b ； ( 7 ) b o b 用a 1 i c e 发送的文件产生文件的单向散列值，同时用a l i c e 的公钥 对签名的散列解密。如果签名的散列值与自己产生的散列值匹配，签名是有效 1 8扬州大学硕士学位论文 的。 2 3 1 r s a 数字签名方案 r s a 数字签名方案基于r s a 公钥密码算法。关于r s a 数字签名方案的描述如下： ( 1 ) 选择大素数p ，g ，令胛= p g ，则缈( 玎) = ( g 一1 ) ( p 一1 ) ； ( 2 ) 选择口 o ，缈( 疗) 一1 】，求6 o ，缈( 刀) 一1 】，使得a 6 = 1m o d 缈( ，z ) ； ( 3 ) 公开 刀，6 ) ，保密 p ，g ，口) ； ( 4 ) 签名算法豫( 石) 为y = x 4m o d 刀，x o ，z 一1 ； ( 5 ) 验证算法玩，( x ，y ) 为真营x = y 6m 0 h d 船。 前面对r s a 算法的分析，可以保证只有持有口的人才能产生签名，任何人都能 验证签名。r s a 签名算法有几个要点需要注意： ( 1 ) 通过计算x = y 6 ，任何人都可以伪造对信息x 作了签名y ； ( 2 ) 由于r s a 数字签名方案的同态性，如果知道了五，娩的签名y l ，y 2 ，那 么而而的签名就是乃y 2 ； r s a 数字签名方案还有一个不足就是每次只能签【l o g ：】长比特的信息，并且产 生的签名也是 1 0 醛】长的；如果将长信息分组签名，则签名速度慢，并且签名 也太长了。 对上面的问题的解决办法是签名前先对信息做h a s h 变换，然后在进行签名。 2 3 2 eig a m ai 型数字签名方案 基于e l g a m a l 算法可以得到一类e l g a m a l 型数字签名方案。e 1 g a m a l 型数字签 名方案： ( 1 ) 选择大素数p ，g ，其中g 是p 一1 的一个大素数因子或者g = p ； ( 2 ) 如果g p ，选择阶为g 的元素口z ：，如果g = p ，选择阶为p 一1 的元 = 日 系口z n5 陆怡基于双线性对的数字签名研究 1 9 ( 3 ) 计算= 口4m o d p ； ( 4 ) 公开 p ，9 ，口，历，保密以； ( 5 ) 选择并公开函数 ，g ，乃) ； ( 6 ) 随机选择七( g p ) 或七z ：一。( g = p ) ，签名跚( x ，忌) = ( 厂，万) ，其中 7 = ( 口。m o d p ) m o d g ； 当g p 时，万满足：矿( 7 ，x ，万) + 谚g ( y ，x ，万) + 办( y ，x ，万) = o m o d g ； 当g = p 时，万满足：矿( 厂，x ，万) + 曙( 厂，x ，万) + 办( 7 ，x ，艿) = o m o d p 一1 ； ( 7 ) 验证耽厂( y ，x ，万) 为真营( ( y ”占口昭” 艿口6 m j ) = 1 m o d p ) m o d g ； 如果签名是正确的 ，则 ： ， 每g 7 占口6 7 j i i l o dg = ( 口矿7 占口口g 7 占口6 7 占m o dp ) m o d g ； 当厂，g ，办取不同的函数时，就可以得到不同的数字签名，统称为e 1 g a m a l 型数 字签方案； 两个典型的例子是： 取g = p ，厂( y ，x ，万) = 万，g ( y ，x ，万) = 7 ，办( y ，x ，万) =