（应用数学专业论文）数字签密及其在分布式环境中的应用.pdf

数字签密及其在分布式环境中的应用 专业 硕士生 指导老师 摘要 应用数学 曹嘉莉 姚正安教授 常规的书信通信根据亲笔签名或印章来证明内容的真实性，通过信封来防止他人的 非法阅读在计算机通信中，一种谨慎的习惯做法是利用带加密的数字签名，即对消息 先签名后加密带加密的数字签名把公开密钥算法和数字签名结合起来，同时实现通信 的不可伪造性、不可否认性和保密性其缺点是：签名和加密的过程不仅需要耗费计算 资源( 计算时间和存储空间) ，而且扩展了原有消息的长度，不可避免地增加了对通信 带宽的要求这就提出了一个问题：在相同安全参数的前提下，是否能够以较少的计算 时问和通信带宽( 相对于带加密的数字签名而言) 传输任意长度的消息 1 9 9 7 年，z h e n g 首次提出数字签密( s i g n c r y p t i o n ) 的概念数字签密与带加密的数 字签名功能相同，但实现的技术不尽相同：数字签密能够在一个合理的逻辑步骤内同时 实现签名和加密两项功能也就是说，数字签密是公开密钥算法和数字签名在更高层次 上的结合，签名和加密同时进行，不可分割数字签密另一个显著特点是，在相同安全 参数的前提下，数字签密的算法复杂度( 计算时间和通信带宽) 小于带加密的数字签 名数字签密在诸如保密选举、电子拍卖等方面有着广阔的应用前景 本文主要讨论数字签密在分布式环境中的应用： 在m u 分布式签密方案中增加了匿名传送的功能，并在随机预言机模型下讨论了新方 案的安全性和效率所提出的方案以增加一次求逆运算、一次乘法运算、两次指数 运算( 指数长度固定) 为代价，换取在通信带宽上较大的节省，与同样具有匿名传 送功能的k w a k m o o n 分布式签密方案相比效率更高 详细讨论了群签密应该满足的安全性要求，并对m u 群签密方案进行了安全性分析， 指出给定一个有效的密文，接收方中任何一个成员都可以伪装成发送方的成员产生 其它有效的密文，从而证明m u 群签密方案不满足不可伪造性 除此以外，本文还讨论了等级系统内部的访问控制问题，基于r s a 公钥密码系统提 出一个新的访问控制方案该方案有效地解决了交互、在线可信机构等问题，而且每个 用户需要存储的信息的长度都是固定的，适用于用户人数较多的情形并在随机预言机 模型下，证明了该方案是安全的 关键词：数字签密，分布式环境，分布式签密，群签密，访问控制，等级系统 第i 页，共5 5 页 英文摘要 s i g n c r y p t i o na n di t sa p p l i c a t i o n si nd i s t r i b u t e d e n v i r o n m e n t m a j o r ：a p p l j e dm a t h e m a t i c 8 n a m e ：c a oj i a l i s u p e r v i s o r ： p r o 1 y a dz h e n g a n a b s t r a c t s e c u r e 卸da u t h e n t i c a t e dm e s s a g ed e l i v e r yh a sb e e nt h eo b j e c to f1 1 1 u c hs t u d yf o ra 1 0 n gt i m e d u r i n gt h ee x c h a n g eo f i e t t e r 8 ，i ti sac o m m o np m c t i c ef o rt h es e n d e rt os l g n h i sn a m eo nt h el e t t e ra n ds e a li ti na ne n v e l o p e ：t h es i g n a t u r ep r o v i d e 8a u t h e n t i c i t ya n d t h ee n v d o p ek e 印st h ec o n 乞e n ts e c r e tf r o mu n a u t h o n z e dr e a d e r s s i m j l a d y jl i 】t h es c 鲫a r l o o fc o m p u t e rc o m m u n i c a t i o n ，t h ec u r r e n ts t a n d a r dm e t h o di s “s i g n t h e n e n c r y p t ( s t e ) ， w h i c ha c h i e v e st h ef u n c t i o n a h t yo fad i 百t a ls i g n a t u r es c h e m ew i t ht h a to fa na s y m m e t r i c e n c r y p t i o n i tt h e r e f o r eo 行色r st h et h r e es e r v i c e s ：u n f o r g e a b i l i t y ) n o n ，r e p u d i a t l o na n dc o n f i d e n t i a l i t 矿h o w e v e r ，s i g n i n ga n de n c r y p t i n gc o n s u m em a c h i n ec y c l e s ，a n da l s 0i n t r o d u c e “e x p a n d e d ”b i t st ot h eo r i g i n a lm e s s a g e t h ec o s tf o rd e i i v e r i n gas e c u r ea n da u t h e n t i c a 土e d m e s s 8 9 ei sm e a s u r e di nt h ec o m p u t a t i o n a lt i m ea n dt h em e s s a g ee x p a n s i o nr a t ei n v e s t e d b yt h et w oc o m m u n l c a t i o np a r t i 镪，h e r e ，ap r o m e li sa d d r e s s e d ：w l e t h e ri t i sp o s s m l et o t r a n s f e ram e s s a g eo fa r b i t r a r y1 e n g t hi nas e c u r ea n da u t h e n t i c a t e dw a yw i t hac o s tl e s s t h a n 七h a to f “s i g n t h e l l - e n c r yp t j t h es o l u t i o nt ot h i sp r o b l e mi ss i g n c r ) p t l o n ，w h i c hi san e w & i y m m e t r i cc r y p t o g r a p h i c m e t h o dp r o p o s e db yz h e n gi n1 9 9 7 s i g n c r y p t l o np r o v i d e sb o t hm e s s a g ec o n 丘d e n t i a l i t ya n d u n f o r g e a b m t y8 i m u l t a n 印u s l yi nam o r ee 伍c i e n tm a n n e r t h ee 毋c i e n tf e a t u r eo fs i g n c r y p t i o nm a k e si td e s i r a b l ei nm a 删a p p l i c a t i o n s ，s u c ha sv o t i n g ，b i d i n ga n ds oo n i nt h i 8p a p e r ，w ew i l lc o n s t r u c ta ne 币c i e n td j s t r i b u t e ds i g n c r y p t i o ns c h e m ew i t h s e n d e r si dc o n 疗d e n t i a l i t y w 色w i l la i s od e m o i l s t r a t eac o n c r e t ea t t a c kt os h o wt h a tm u s g r o u ps l g n c r y p t i o ns c h e m ef a i l st op r o v i d eu n f o r g e a b m t y 0 u ra t t a e k 枷0 w sad i s h o n e s t r e c e i v e rb o bt of o r g eav a l i dc i p h e r t e x ta si fi tw e r eg e n e r a t e db yt h eg e n u i n es e n d e ra l i c e ， u n d e rt h ea s s u m p t i o nt h a tb o bi 8am e m b e ri nt h er e c e i v i n gg r o u p ，t h i ss e c u r i t yw e a k n e s s 8 e e m st oh a v en o tb e e nm e n t i o n e dj nl l t e r a t u r e s f u r t h e r m o r e ，ew i l lr e v e a ls o m ed r a w b a c k si ng h o d o s i ss c h e m ea n dt r e s e n ta ni m p r a v e dr s a - b a s e da c c e s sc o n t r 0 1s c h e m ef o rh i e r a r c h i c 出g r o u p s t h ep r o p 0 8 e ds c h e m e e n j o y st h ef o l l a w i n gp r o p e r t i e s ： 第i i 页。共5 5 页 t h es i z eo fa ni n d i v i d u a l ss h a r es e q u e n c ei sb o u n d e db yas m a l lc o n s t a n tt i m e st h e s i z eo ft h er s am o d u l u sc o r r e s p o n d i n gt ot h a tg r o u p t h ed e l e g a t i o no fi n f o r m a t i o nf l o wf r o ml l i 曲e 卜l e v e lg r o u p st ol o 、v e r l e v e lg r o u p si s c o m p l e t e l yn o n i n t e r a c t i v e i td o e s n tr e q u i r ea no n l i n et r u s t e da u t h o r i t yt ou p d a t et h es y s t e ma ss o o na sc o m m u n i c a t i o nh a p p e n e d t h ep r o p o s e ds c h e m ei sr e s i s t a n tt oc o n s p i r a c y k e y w o r d s ：8 i g n c r y p t i o n ，d i 8 t r i b u t e de n v i r o n m e n t ，d i s t r i b u t e d8 i g n c r y p t i n ，g r o u ps i g n c r y p t i o n ，a c c e s sc o n t r 0 1 ) h i e r 盯c 1 1 y 第i i i 页，共5 5 页 插图目录 插图目录 4 一lp 0 ，p 1 ，p 2 之间的权限关系 4 2 只，和p 2 之闾的交互过程 4 3 用户之间的权限关系 4 4 t a 为用户类的加密密钥加上冗余g ( 8 ) 第、r i 页共5 5 页 3 7 3 8 4 0 4 1 表格目录 表格目录 1 1 安全性要求 2 1 r s a 加密， 2 2 e l g a m a 仂口密 3 1 数字签名标准的短签名版本， 3 2 k w a k - m o 衄方案与新的匿名传送方案的效率比较 第v i i 页，共5 5 页 2 1 3 1 4 1 7 3 0 符号说明 符号说明 本文未加说明的字母均表示整数以下是全文通用符号，如在个别地方有不同的含 义将明确说明其它符号在所在章节说明 n 1 6 p ，g ，9 7 ，p 1 ，p 2 g c d ( 。加) o j6 ( m o dn ) n 一1 m o d ( 竹) 曲( n ) 川( 凡) n ij 6 o o6 i n i g 兄x o 整除6 ， 素数， 。6 的最大公因子， n 同余于6 模凡， o 对模扎的逆， e u l e r 函数， 礼的不同素因子的个数， 位串。，6 的连接运算， 位串n ，6 的异或运算， 位串a 的长度， 从集合x 中随机选取元素z 第5 2 页，共5 5 页 第一章绪论 本文的主要内容是研究一类具有特殊性质的密码系统数字签密为了使读者对 数字签密有一个大致的了解，我们在本章首先对数字签密的研究背景，如信息安全的重 要性、密码算法、数字签名等进行简单的回顾，给出数字签密的相关概念( 分布式签 密、群签密) ，然后对数字签密的研究现状作简要的介绍，指出目前群签密研究中存在 的一些问题，最后介绍论文的主要工作以及章节安排 1 1 信息安全的重要性 计算机与通信的结合，已经成为当代通信技术发展不可逆转的潮流随着互联网技 术的飞速发展，我们正在经历一种新的经济模式的兴起，它就是电子商务经济电子商 务所包含的内容并不局限于书籍或光盘的在线销售，它既包括企业之间跨越供应渠道或 运用在线采购进行的交易，也涵盖在卫生保健、公共教育、政府服务等众多公用事业领 域极为活跃的在线事务处理我国现有的电子商务系统只是在一般w 曲站点的基础上增 加简单的产品目录和订单这种比较初级的电子商务系统还没有与内部网连接，也就不 会涉及太多的安全问题然而，随着信息化进程的深入，它们即将被新的、真正的电子 商务系统所取代，即w e b 站点与公司的后端数据库系统相连，这样就可以向客户提供有 关产品库存、发货情况以及帐款情况等实时信息，帮助商家实现业务处理的流水化这 种充分集成的电子商务系统将内部网与互联网连接，使得小到本企业的商业机密、商务 活动的正常运转，大至国家的政治、经济机密都面临网上黑客和病毒的严峻考验安全 问题已经成为影响电子商务顺利开展的核心和关键问题：一方面，使用者担心在网络上 传输的个人资料以及信用卡号码等信息被不正当运用：另一方面，特约商店也担心收到 的是被盗用的信用卡号码或者交易不认账等，还有可能因为网络不稳定、应用软件设计 不良导致被黑客入侵造成损失对中国来说，网络产品几乎都是“舶来品”，本身就存 在着不安全隐患，加之受技术、人为等因素的影响，不安全因素更显突出 在计算机网络深入普及的信息时代，信息本身就是时间，就是财富由于信息的存 储、处理、传输等过程通常是在不安全的信道上进行的，信息容易受到窃听、截取、修 第l 贾，共5 5 页 1 2 密码算法 改、重放等各种攻击手段的威胁，信息安全的核心内容就是保护信息，使之免遭偶发的 或有意的非授权泄漏、修改、破坏或处理能力的丧失表l l 列出了常见的七种安全性要 求这些要求在计算机通信过程中至为重要，就像面对面的交流一样某人是否就是 表1 1 安全性要求 术语定义 保密性 认证性 完整性 可访问性 防御性 不可否认性 合法性 保持个人的、专用的和高度敏感数据的机密 确保通信双方的合法身份 保证所有存储和管理的信息不被篡改 保证系统、数据和服务能由合法的人员访问 能够阻挡不希望的信息或黑客 防止通信或交易双方对已进行业务的否认 保证各方的业务符合可适用的法律和法规 他所说的人；某人的身份证明文件( 护照、驾驶执照、学历) 是否有效；声称从某人那 里传来的文件是否确实由那个人发出这些事情都可以归结为上述安全性要求，其中保 密性、完整性和不可否认性最为关键 1 2 密码算法 假设a l i c e 想通过不安全的信道秘密地发送消息给b o b ：她希望窃听者不能阅读发送的 消息，对发送的消息进行加密是行之有效的办法。 在密码学中，消息( m e s s a g e ) 被称为明文( p l a i n t e x t ) ，用m 表示，现实中的消息 可能是文本文件、位图、数字化语音序列或数字化视频图像等等在这里m 是指简单的 二进制数据用某种方法伪装消息以隐藏它的内容的过程称为加密( e n c r y p t i o n ) 被加 密的消息称为密文( c i p h e r t e x t ) ，用c 表示，它也是二进制数据把密文转变为明文的 过程称为解密( d e c r y p t i o n ) 密码算法( a l g o r i t h m ) 也叫密码( c i p h e r ) ，在通常情 况下，它由两个相关的函数组成：一个用作加密，记作e ；另一个用作解密，记作d ， 加密和解密的过程可用数学公式表示如下： e ( m ) = c ， 第2 页，共5 5 页 d ( c ) = m 先加密后解密，恢复原始消息，故下列等式一定成立： d ( e ( m ) ) = m 如果算法的安全性是基于对算法细节的保密，这种算法称为受限制的( r e s t r i c t e d ) 算法受限制的算法具有历史意义，对低密级的应用来说还是很流行的；但按照现在的 标准，其保密性远远不够，不能应用在大的或者经常变换的用户组织中更糟糕的是， 受限制的算法不可能进行质量控制和标准化，每个用户( 组织) 必须自己编写算法并予 以实现 现代密码学用密钥( k e y ) 解决了这个问题，加解密运算都依赖于密钥七： 毋( m ) = c ， d k ( c ) = m ， d k ( z 靠( m ) ) ：m 这种算法的安全性是基于密钥的安全性，而不是算法细节的保密密码算法以及所有可 能的明文、密文和密钥组成了一个密码系统( c r y p t o s y s t e m ) 基于密钥的算法通常有两种：对称算法( s y m i n e t r i ca l g o r i t h m ) 和非对称算法 ( a s y m m e t r i ca l g o r i t h m ) 对称算法的加密密钥能够很容易地从解密密钥中推算出来， 反之也成立在大多数对称算法中，加解密密钥是相同的它要求发送者和接收者在安 全通信之前协商好一个秘密密钥对称算法的安全性依赖于密钥的保密，泄漏密钥就意 味着任何人都能对消息进行加解密只要通信需要保密，密钥就必须保密非对称算法 也叫做公开密钥算法( p u b l i c - k e ya 】g o r i t h m ) ，其加密密钥不同于解密密钥，而且解密 密钥不能根据加密密钥计算出来( 至少在合理假定的长时间内) 加密密钥是公开的， 任何人都可以用来加密消息，但只有用相应的解密密钥才能解密消息，公开密钥算法由 此得名在这些密码系统中，加密密钥叫做公开密钥( p u b l i c _ k e y ，简称公钥) ，解密密 钥叫做私人密钥( p r i v a t ek e y ，简称私钥) 由于对称算法一般比公开密钥算法快一千倍，而且公开密钥密码系统对选择明文攻 击( c h o s e n _ p l a i n t e x ta t t a c k ) 是脆弱的，因此在大多数实际应用中，公开密钥算法用来 保护和分发会话密钥( s e 8 s i o nk e y ) 这些会话密钥用在对称算法中，对通信消息进行保 第3 页，共5 5 页 1 3 数字签名 密有时称这种系统为混合密码系统( h y b r i dc r y p t o s y s t e m ) 本文所涉及的算法，一 般是指公开密钥算法( 特别说明的除外) 1 3 数字签名 长期以来，在文件上手写签名被用来证明作者的身份，或至少表明作者同意文件的 内容在计算机通信中，如果接收者希望确认消息发送者的身份，并且验证消息在传送 过程中是否被篡改，可以借助数字签名实现这些目标与公开密钥算法类似，数字签名 也包含两个相关的部分：签名算法和验证算法发送者利用秘密的签名算法s i g 产生一 段与消息m 相关的位串盯= s 匆( m ) ；给定( m ，接收者可以利用公开的验证算法y e r 确认消息的来源以及完整性 数字签名最早的应用之一是用来对禁止核试验条约的验证美国和前苏联互相允许 把地震测试仪放置在对方境内，以便对核试验进行监控问题是监督国需要确信东道国 没有篡改从地震仪传来的数据；同时，东道国需要确信地震仪只发送规定的需要检测的 数据给监督国传统的鉴别技术能解决第一个问题，但只有数字签名能同时解决两个问 题 1 4 数字签密的提出以及研究现状 常规的书信通信根据亲笔签名或印章来证明内容的真实性，通过信封来防止他人的 非法阅读在计算机通信中，一种谨慎的习惯做法是利用带加密的数字签名，即对消息 先签名后加密如果a 1 i c e 写一封信，她会在信纸中签名，然后把信纸装入信封如果她 把不带签名的信装入信封而在信封上签名，那么收信人b o b 有理由担心这封信已经被替 换如果b 0 b 把a l i c e 的信和信封给c a r o l 看，c 盯0 1 可能因为信没有装对信封而控告b o b 撒 谎因此，加密前签名是很自然的做法带加密的数字签名把公开密钥算法和数字签名 结合起来，同时实现通信的不可伪造性、不可否认性和保密性其缺点是：签名和加密 的过程不仅需要耗费计算资源( 计算时间和存储空间) ，而且扩展了原有消息的长度， 不可避免地增加了对通信带宽的要求这就提出了一个问题：在相同安全参数的前提 下，是否能够以较少的计算时间和通信带宽( 相对于带加密的数字签名而言) 传输任意 长度的消息 第4 页洪5 5 页 第一章绪论 z h e n g 2 】在c r y p t o 9 7 中首次提出了数字签密( s i g n c r y p t i o n ) 的概念，这篇文献在数 字签密发展史上具有里程碑的意义数字签密包含两个相关的算法：签密算法和解签密 算法，它能够在一个合理的逻辑步骤内同时实现签名和加密两项功能，大大降低了消息 保密认证传输所需的时间代价和通信带宽值得注意的是，数字签密与带加密的数字签 名功能相同，但实现的技术不尽相同：数字签密是公开密钥算法和数字签名在更高层次 上的结合，签名与加密同时进行，不可分割 1 9 9 7 年，z h e n g l 2 基于数字签名标准( d i 百t ms i g l l a t u r es t a n d a r d ，简称d s s ) 的 短签名版本( s d s s l 和s d s s 2 ) ，构造了第一个数字签密方案2 0 0 2 年，b k 3 1 建立 了f u o ( f l e x i b l eu n s i g n c r y p t i o n0 r 蹰l e ) 模型，并在该模型下讨论了z h e n g 签密方案 的安全性分析表明，在g 印d i f f i e - h e l l m a n 假设下，该方案作为密码算法可以抵抗 自适应的选择密文攻击( i n d i s t i n g u i s h a b i l i t yu n d e ra d a p t i v ec l l o s e n c i p h e r t e x ta t t a c k ， 简称i n d c c a 2 ) ，作为签名协议可以抵抗选择消息攻击( c h o s 朗一m e s s a g ea t t a c k ，简 称c m a ) 自此，构造c c a 2 一c m a 型的数字签密成为一个研究热点基于有限域上椭 圆曲线和整数分解的数字签密方案在文献 4 ，5 中有记载2 0 0 3 年，m a l o n 争l e e 6 】提出基 于r s a 公钥密码系统的数字签密方案，并在随机预言机( r a n d o mo r a c l e ) 模型下证明了 该方案的安全性l i b e r t 和q u i 8 q u a t e r 在文献7 9 1 中对如何利用椭圆衄线的双线性对以 及g a pd i m e - h e l l m a n 群中的d i m e _ h e l l m a n 问题构造签密方案进行了深入的探讨数字签 密的相关研究可参阅文献f 1 0 ，1 1 1 z h e n g 的开创性工作推动了数字签密研究的蓬勃发展，人们根据各种应用场合的 需要，相继提出了许多不同的数字签密方案例如：在一般情况下，只有接收者才 能验证签名的真实性也就是说，验证签名的过程需要输入接收者的私钥b a o 等 人 1 2 修改了z h e n g 的方案，使得在不泄露接收者私钥的前提下签名可以被公开验 证l m 和l e e 1 3 】以及s h i n 等人( 1 4 1 沿用并进一步发展了b a 0 的思想 再举一个例子在普通的数字签密方案中，通常只有一个指定的接收者文献f 1 5 1 提 出应该将数字签密推广到具有多个指定接收者的情形2 0 0 0 年，m u 等人基于分布式密 码算法 1 6 构造出分布式签密方案 1 7 即组织内每个成员都可以对密文进行解签密他 们还把群签名 1 8 2 0 】引入数字签密的研究，提出了群签密的概念以及构造思路在群 签密方案中，成员可以代表各自所在的组织进行匿名的保密认证传输，出现争议时由 第5 页，共5 5 页 15 论文的主要工作以及章节安排 可信机构( 通常由发送方的群管理员担任) 识别出消息的真正发送者然而m u 等人设 计的方案存在一些缺陷和不足：分布式签密方案不能对发送者实现匿名保护，群签密 的构造思路计算复杂，不适合实际应用2 0 0 3 年，k w a k 和m o o n f 2 1 1 改进了m u 的方案， 提出匿名传送的分布式签密方案，并首次给出群签密方案的完整描述可惜的是，文 献 2 2 忖旨出k w a k m 0 0 n 群签密方案不满足：不可伪造性( u n f o r g e a b i l i t y ) 、抗联合攻击 ( c o a l i t i o m r e s i 8 t a n c e ) 以及可跟踪性( n a c e a b i l i t v ) 对群签密的研究从提出到现在才短短四年多的时间，与群签密有关的的数字签密和 群签名的研究已经取得一些成果，但还不够完善，因此对群签密的研究正处于初级阶 段鉴于现有群签密方案存在的缺陷，以下问题很值得作进一步的探讨： ( 1 ) 给出比较完善的群签密的定义，寻找安全高效的群签密方案到目前为止，还没有一 个可证明安全的群签密方案 ( 2 ) 寻找支持动态成员管理的群签密方案，即系统建立后允许成员的加入或撤销现有 的方案如果增加删除成员或者更改原有成员的私钥，需要重新建立系统，改变群公 钥，效率低 ( 3 ) 设计出适用于大群体的群签密方案，群公钥和密文的长度应独立于成员的人数，并且 签密解签密算法的计算复杂度不依赖于成员的人数 1 5 论文的主要工作以及章节安排 本文主要讨论数字签密在分布式环境中的应用： 在m u 分布式签密方案中增加了匿名传送的功能，并在随机预言机模型下讨论了新方 案的安全性和效率所提出的方案以增加一次求逆运算、一次乘法运算、两次指数 运算( 指数长度固定) 为代价，换取在通信带宽上较大的节省，与同样具有匿名传 送功能的k w a k m o o n 分布式签密方案相比效率更高 详细讨论了群签密应该满足的安全性要求，并对m u 群签密方案进行了安全性分析， 指出给定一个有效的密文，接收方中任何一个成员都可以伪装成发送方的成员产生 其它有效的密文，从而证明m u 群签密方案不满足不可伪造性 第6 页共5 5 页 第一章绪论 除此以外，本文还讨论了等级系统内部的访问控制问题，基于r s a 公钥密码系统提 出一个新的访问控制方案该方案有效地解决了交互、在线可信机构等问题，而且每个 用户需要存储的信息的长度都是固定的，适用于用户人数较多的情形并在随机预言机 模型下，证明了该方案是安全的 本文的余下部分是这样安排的： 第二章简单介绍了与本文相关的背景知识，包括在密码学中常见的困难问题( 大数 分解问题、离散对数问题) ，经典的公开密钥算法，散列函数以及随机预言机模型 第三章详细介绍本文在数字签密方面的工作，包括对m u 分布式签密方案的推广，以 及对m u 群签密方案的安全性分析 第四章讨论了等级系统内部的访问控制问题 第五章总结全文，并提出下一步的工作方向 第7 页，共5 5 页 第二章预备知识 1 9 7 6 年，w d i 伍e 和me h e l l m e n 发表了在密码学领域中具有里程碑意义的文章一 一密码学的新方向，提出了公开密钥密码学( p u b l i 昏k e yc r y p t o s y s t e m ) ，使得密码系 统的安全性常常建立在某个难解的数学问题之上本章首先介绍密码学上常见的困难问 题和经典的公开密钥算法，然后讨论数字签名和认证系统中的重要工具散列函数以 及随机预言机模型 2 1 困难问题 定义2 1若攻击者即使具有无限的计算资源( 计算时间和存储空间) ，也不能破 译密码系统，则称该密码系统是无条件安全的( u n c o n d i t i o n a l l ys e c u r e ) 事实上只有一次一密乱码本( o n e t i m ep a d ) 才是不可破译的，其它密码系统只要简 单地将所有可能的密钥逐一尝试，并检查所得的明文是否有意义就可以被攻破，这种方 法叫做蛮力攻击( b r u t 争f o r c ea t t a c k ) 密码学更关心在计算上不可破译的密码系统 定义2 2若利用最好的算法，至少需要步运算才能破译一个密码系统，这 里是指定的一个非常大的数，则称该密码系统是计算上安全的( c o m p u t a t i o n a u y 8 e c u r e ) 一个密码系统无条件安全是理论上安全，而计算上安全就是实际上安全问题是我 们不知道在这种定义下，如何证明一个实际的密码系统是否安全事实上，当大到一 个不合理的数时，例如：用目前运算速度最快的计算机运行步，需要几千万年甚至宇 宙年龄的计算时间时，就认为该系统是计算上安全的，因而也是实际上安全的另外一 个方法是把证明密码系统是否安全的问题归结到某些著名的数学难题。例如：已知钆是 两个素数的乘积，若n 的分解是困难的，则以礼为模数的r s a 公钥密码系统是安全的 这种方法仅仅对密码系统提供了一种相对于其它问题的安全性证明，而不能绝对证明系 统是否安全 第8 页，共5 5 页 第二章预备知识 下面给出本文所涉及的一些困难问题关于困难问题更详细的介绍，请参 阅【2 3 ，24 】 2 1 1 大数分解问题 在公钥密码系统中，大数分解问题是最常见的困难问题之一，如r s a 公钥密码系 统、r a b i n 公钥密码系统等 定义2 3 大数分解问题( f a c t o r l n g ) ：给定一个正整数礼，找出它的所有素因予， 即找到不同的素数仇和正整数b i 1 ，i = 1 ，2 ，u ( 礼) ，使得n = 硝1 跨p ，其中 u ( 几) 表示他的不同素因子的个数 在数论中，大数分解问题是一个古老的问题分解一个大整数的思想很简单，但是 其计算过程比较费时尽管如此，在这方面的研究还是取得了一些进展目前，最好的 大数分解算法是数域筛选法( n u m b e rf i e l ds i e v e ，简称n f s ) 对二进制位长大于1 1 0 的 数来说，一般的数域筛选法是目前已知的最快的大数分解算法数域筛选法刚被提出时 还不是很实用，但随着过去几年一系列的改进，这一点已经得到改变早期的数域筛选 法曾对第九个费尔马数2 5 1 2 + 1 进行分解 大数分解是个迅速发展的领域推断大数分解技术的发展是很困难的，因为 没有人能够预见数学理论的进展在提出数域筛选法之前，许多人猜测二次筛选法 ( q u a d r a t i cs i e v e ，简称q s ) 接近于任何大数分解算法所能做到的最快( 极限) ，但是 他们错了 r s a 问题是大数分解问题的一个特例 定义2 4 r s a 问题( r s a p ) ：给定正整数n ，e 和整数c ，如果礼是两个素 数mq 的乘积，且g c d ( e ，m ) ) = 1 ，寻找m 磊，使得m 。三c ( m o d 礼) ，其中 ( n ) = ( p 一1 ) ( q 一1 ) 换句话说，r s a 问题就是计算模n 的e 次方根n 和e 的性质保证了对任意的 c 磊，存在唯一的m 磊，使得m 8 兰c ( m o d ) 成立 命题2 1 r s a 问题可多项式归约为大数分解问题 第9 页，共5 5 页 21 田难问题 如果n 是两个素数的乘积，那么计算模n 的平方根在计算上等价于对n 进行因子分 解【25 一般的观点认为，r s a 问题和大数分解问题在计算上是等价的，但尚未得到证 明 关于大数分解问题和r s a 问题，有以下假设 2 4 假设2 1大数分解假设：对任意的多项式q ( ) 以及任意的概率多项式时间算法 a ，存在一个正整数，当 时， p r 阶) 2 p ：p f n 且p 1 ，p n 】 时， p r ，e ，r s a n “圳= 卅 时， p r 撕忍r s ( 圳= 水1 一赤， 其中几风= 礼= p q ：mq 都是素数，p g 且j p i = 川= 七) ，g c d ( e ，咖( n ) ) = 1 ，z z ：r s a 。( 茁) = 矿m 。d 礼 2 1 2 离散对数问题 离散对数问题是公钥密码系统中又一个基本问题，许多密码协议的安全性是基于寻 找离散对数的困难性，如d i m e _ h e l l m a n 密钥协商、e l g a m a l 力口密、e l g a m a l 型签名及其变 型等，因此学者对这个问题进行了广泛而又深入的研究 定义2 5设g 是一个阶为n 的有限循环群，g 是g 的生成元，口g 若整数 z z n ，满足口= 旷，则称。是以g 为底d 的离散对数，用l o 岛a 来表示 第1 0 页，共5 5 面 模指数运算是频繁用于公钥密码系统的一种单向函数不是所有的离散对数问题都 存在解，只有整数才是合法的解发现下面的方程没有解很容易的： 3 。= 7m o d1 3 对1 0 2 4 一比特的数求离散对数更加困难 定义2 6离散对数问题( d i s c r e t el o g 盯i t h mp r o b l e m ，简称d l p ) ：给定素数 p ，召的生成元9 以及召中的元素a ，寻找整数z 昂一1 ，使得0 5g 。( m o dp ) - 定义2 7广义离散对数问题( g e n e r a l i z e dd i s c r e t el o g 盯i t h mp r o b l e m ，简 称g d l p ) ：设g 是一个阶为n 的有限循环群，g 是g 的生成元，a g ，寻找整 数。乙，使得= 矿 密码设计者对下面三个群的离散对数很感兴趣： 素数域的乘法群铭 特征为2 的有限域g f ( 矿) 上的乘法群 有限域f 上的椭圆曲线群e g ( f ) 如果模数p 是素数，那么在z 上寻找离散对数的计算复杂度与对同样尺寸的整数n 进行因子分解的计算复杂度一样，其中礼是两个大致等长的素数的乘积 离散对数的计算与因子分解有着紧密的联系如果可以解决离散对数问题，就能解 决大数分解问题( 逆命题的正确性尚未证明) 目前，在素数域上有三种计算离散对数 的方法：线性筛选法( l i n e 盯s i e v e ) 、高斯整数法( g a u s s i a ni n t e g e rs c h e m e ) 以及数域 筛选法关于离散对数问题的综合性概述可参见 2 5 】 d i 毋e - h e l l i n 粕问题与离散对数问题也是紧密相关的 定义2 8 d i m e _ h e l l m a n 问题( d h p ) ：给定素数p ，邵的生成元口以及召中的元 素g 。( m o dp ) 、g ”( m o dp ) ，计算g 。”( m o d p ) 定义2 9广义d i f 瞻h e l l m a n 问题 ( g e n e r a l i z e dd i m e _ h e l l m a np r o b l e m ， 简 称g d h p ) ：设g 是一个有限循环群，g 是g 的生成元，旷、矿是g 中的元素，计 算g “ 第1 1 页共5 5 页 2 1 困难问题 d i m e h e l l m a n 问题可等价地描述为：给定素数p ，召的生成元9 以及召中的元素 ，p ，计算1 。岛卢m o d p ( = p 1 。g f 。m o dp ) 可以看出，d i m 争h e l l m a n 问题的难度不超过离散对数问题的难度 命题2 2d i 伍e h e l l m a n 问题可多项式归约为离散对数问题，更一般地，广义d i 伍e h e 】1 m a n 问题可多项式归约为广义离散对数问题 对某些有限循环群来说，离散对数问题和d i 毋e - h e l l m a n 问题在计算上是等价 的f 2 6 ，27 定义2 1 0d i 佑e h e u m a n 判定问冠( d e c i s l o n a ld i 伍e h e l l l n a np r o b l e m ， 简称 d d h p ) ：设g 是一个有限循环群，9 是g 的生成元，旷、矿、g 。是g 中的元素，判 断旷与9 。口是否相等 d 1 最e h e l l m a n 判定问题最早出现在文献f 2 8 中，但早期的一些密码系统 2 9 ，3 0 已经隐 含了这个问题 命题23d i 伍e - h e l l m a n 判定问题可多项式归约为d i m e _ h e l l m 舭1 问题 关于离散对数问题和d i f h e - h e n m a n 问题，有以下假设【2 4 ，3 1 假设2 4强离散对数假设( d i s c r e t el o g a r i t h ma s s m u p t i o n ，简称d l a ) ：对任意 的多项式q ( ) 以及任意的概率多项式时间算法a ，存在一个正整数，当 时， p r 【a ( p 禹。) = 嚣：a = 9 。m o d 弘1 。sp l 】 时， 1 p r 凰。) ；。：a = 旷m 。dp ，15z p 一1 k o 时， p 。愚旷，旷) 2g ” o 时， 叫a ( 舢，旷，旷，g ”) = 1 卜p r a ( p ，舢。，矿，9 2 ) = 1 i 赢， 其中素数p 满足p i = 南，9 是z 的生成元，z ，z 磊_ 1 假设2 8 g a pd i m e - h e l l m a n 假设( g d h a ) ：可以在多项式时问内解决d i m e - h e l l m a n 判定问题，但在多项式时间内解决d i 伍e - h e l l m a n 问题在计算上是困难的 g a pd i m e - h e l l m a n 假设的严格定义请参阅【3 3 】 2 2 公开密钥算法 1 9 7 7 年，风v e s t 、s h a m i r 和a d l e m a n f 3 4 1 基于r s a 假设构造了第一个公钥密码系统一 一r s a 公钥密码系统这里的肼口决不可泄露，而且r s a 模数n 不能在一组用户之间共 享 表2 1r s a 加密 公开密钥 私人密钥 加密 解密 n ：素数p 、g 的乘积，称为r s a 模数， e ：满足g c d ( e ，妒( b ) ) = l ，称为加密指数 d = e - 1m o d 咖( n ) ，称为解密指数： c 2 m 8m o dn2 m = c dm o d n 基于离散对数假设的e l g a m a l 加密方案由e l g 锄8 1 【