(计算机软件与理论专业论文)门限密码体制与新型密码体制研究.pdf_第1页
(计算机软件与理论专业论文)门限密码体制与新型密码体制研究.pdf_第2页
(计算机软件与理论专业论文)门限密码体制与新型密码体制研究.pdf_第3页
(计算机软件与理论专业论文)门限密码体制与新型密码体制研究.pdf_第4页
(计算机软件与理论专业论文)门限密码体制与新型密码体制研究.pdf_第5页
已阅读5页,还剩41页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独 立进行研究所取得的成果。除文中已经注明引用的内容外,本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体,均己在文中以明确方式标明。本人完 全意识到本声明的法律责任由本入承担。 论文作者签名:垒亟丛日期 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定,同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版,允许论 文被查阅和借阅:本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索,可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名:j 圭黛垫导师签名期: 当奎盔堂堡主兰垡笙奎 摘要 本文的第部分主要讨论了门限密码体制的有关问题。公钥密码体制允许任 何发送者向一个已知的接收者( 或者接收者的公钥可以被验证) 发送秘密信息。 公钥体制也能用于数字签名。数字签名是手写签名的数字对应物。通过数字签名, 接收方只要知道经过认证的发送方的公钥就可以验证消息的真实性、完整性,并 获得文件签发者对文件内容的承诺。 传统的密码学考虑一个发送者和一个接收者的情况,但是,在互联网得到广 泛应用的今天,大量的与信息安全相关的活动是在组织与个人、组织与组织之间 进行的。如在电子政务中,签署重要文件的权力通常不是掌握在一个人的手里 而是掌握在一个团体手里。签署的文件表达的也不是个人意志,而是某权力机关 的决定:在电子商务中,合同的签署往往代表的是公司利益、是董事会集体意志 的表达。诸如此类的情况就需要组织内部必须制定某种策略,使相关人员分享签 名、解密等权利。门限密码学的目标就是为这种情况提供实用的解决方案。 门限密码体制确保由一组人发送给另一组或一个人的信息的安全性,但不能 显著的增加密钥和或信息的长度。通常情况下人们会知道一个组织和它的公钥, 而没必要去了解谁在这个组织内工作,甚至不需要知道谁有以这个组织的名义签 署文件的权力。为了避免密钥管理的问题一个组织或团体只能有一个被外界所知 的公钥,这个公钥不是组织内部的个人的公钥的总和,它应当以分布的方式分散 给每个相关成员。签名或解密必须按某种安全策略迸行,要考虑到避免滥用职权、 抗( 内部或外部) 攻击、密钥安全、方便可行等多项因素。 特别地,门限签名是门限密码学的个重要分支。“刀) 门限签名体制的签名 密钥由”个人分开掌握,每个人只有密钥的一个碎片,为了产生一个给定消息埘 的签名,至少需要t + 1 个人共同参与,每个人都要产生他们对于这个消息的“部 分签名”,然后合并成州的总签名。- - + m 门限体制产生的签名应该与拥有全部 签名密钥的单个签名者产生的签名看起来是一样的,这个签名可以被任何拥有唯 一对应的公钥的人验证,换句话说,门限签名体制应该是透明的。 山东大学硕士学位论文 门限签名是在如下两个方面的推动下发展起来的:一是在一个组织内部,需 要有一组人同意之后才能签署一个消息或文件,二是为了保护签名密钥免受内部 或外部的人的攻击。随着公钥体制在实际运用中的发展,后者的重要性日益显示 出来。门限签名体制的目标是双重的:既增加了签名代理的可用性,又通过增大 对手获得签名密钥的难度提高了免于伪造攻击的保护程度。门限的方法排除了密 钥由多个人保存,但在签名时由一个人重新恢复的这种简单的解决方案,这样的 协议与任意f ( 或少于,) 个人都不能产生一个新的签名的要求相违背。在门限 体制中,多次签名不会暴露密钥或有明显的密钥重构过程。 本文以d s s 门限体制为载体,研究了门限密码学的安全性、强健性、效率等 多方面的问题,提出了一些新的改进方案。 本文的第二部分讨论了种新型密码体制量子密码体制。量子密码体制 具有突出的安全特性。它提供的密钥交换方式,是不可窃听的,这是现在的公钥 体制所不具备的。量子密码作为新兴的非数学密码,以其独有的特性必将对密码 学的发展产生重大影响。本文对量子密码体制这种新型的密码体制作了较为深入 的研究,对目前影响力较大的所谓“有噪声的b b 8 4 协议”进行了改进,提出了 提高其安全性和效率的新思想、方法。 关键词:门限密码体制,门限签名,d s s 签名,量子密码体制,密钥交换 4 a b s t r a c t t h ef i r s tp a r to ft h i sa r t i c l ei sm a i n l yf o c u so np r o b l e ma b o u tt h r e s h o l d c r y p t o g r a p h y p u b l i ck e ys y s t e m sa l l o w sa n y s e n d e rt os e n dp r i v a t ed a t at o k n o w nr e c e i v e r ( o rt oar e c e i v e rw h o s ep u b l i ck e yi sa n t h e n f i c ) ap u b l i ck e y s y s t e mc a na l s ob eu s e d t od i g i t a l l ys i g nd o c u m e n t s a n yr e c e i v e rw h ok n o w s t h ea u t h e n t i cp u b l i ck e yo ft h es e n d e rc a nc h e c kw h e t h e rd a t ao r i g i n a t e df r o m t h es e n d e r ,o rt h a ti tw a sc r e a t e do rm o d i f i e db ya no u t s i d e r t r a d i t i o n a l l y ,c r y p t o g r a p h yc o n s i d e r st h e c a s ew h e r et h e r ei so n es e n d e r a n do n er e c e i v e r h o w e v e r ,al o to fc o m m u n i c a t i o ni sb e t w e e na ni n d i v i d u a l a n da no r g a n i z a t i o n ,e g ,ac o m p a n y ,ag o v e r n m e n t a la g e n c y o r g a n i z a t i o n s n e e da l s ot oc o m m u n i c a t et oe a c ho t h e r m o r e o v e r , m a n ya n dc e r t a i n l y s e c u r i t yr e l a t e d ,a c t i o n sa r et a k e nb yag r o u po fp e o p l ei n s t e a do fb ya n i n d i v i d u a l f o re x a m p l e ,t h ea u t h o r i t yt os i g nad o c u m e n ti so f t e nn o ti nt h e h a n d so fas i n g l ep e r s o n t h eg o a lo ft h r e s h o l dc r y p t o g r a p h yi st op r e s e n t p r a c t i c a ls c h e m e s t os o l v es u c h p r o b l e m s t h r e s h o l d c r y p t o s y s t e mg u a r a n t e et h ea u t h e n t i c i t yo fm e s s a g e ss e n tb ya g r o u p o fi n d i v i d u a l st oa n o t h e r g r o u p a n dt h i sw i t h o u te n o r m o u s e x p a n s i o n o f k e y sa n d o rm e s s a g e s o n eo f t e nk n o w sa no r g a n i z a t i o na n di t sp u b l i ck e y b u tn o tn e c e s s a r i l yw h ow o r k si nt h i so r g a n i z a t i o no re v e nl e s sw h oh a st h e p o w e r t os i g ni nt h en a m eo f t h e o r g a n i z a t i o n s o ,t oa v o i dak e ym a n a g e m e n t p r o b l e ma n dt oa l l o wd i s t r i b u t i o no fp o w e ra no r g a n i z a t i o ns h o u l dh a v e m a i n l yo n ep u b l i ck e y ,i n s t e a do fr e l y i n go nt h em a n y p u b l i ck e y so ft h e i n d i v i d u a l si n s i d et h a to r g a n i z a t i o n s ot h e o r g a n i z a t i o ns h o u l dh a v eo n e p u b l i ck e y ,t h ep o w e rt os i g no rt od e c d - p ts h o u l dt h e nb es h a r e d t oa v o i d a b u s e u s i n gat h r e s h o l ds i g n a t u r es c h e m e ,d i g i t a ls i g n a t u r e sc a nb ed r o d u c e d 山东大学硕士学位论文 b yag r o u po fp l a y e r sr a t h e rt h a nb yo n ep a r t y i nc o n t r a s tt ot h er e g u l a r s i g n a t u r es c h e m e sw h e r e t h es i g n e ri sas i n g l ee n t i t yw h i c hh o l d st h es e c r e t k e y ,i nt h r e s h o l ds i g n a t u r es c h e m e s t h es e c r e tk e yi ss h a r e db yag r o u po fn p l a y e r s i n o r d e rt o p r o d u c e av a l i d s i g n a t u r e o na g i v e nm e s s a g e m , i n d i v i d u a lp l a y e r sp r o d u c et h e i rp a r t i a ls i g n a t u r e so nt h a tm e s s a g e ,a n dt h e n c o m b i n et h e mi n t oaf u l ls i g n a t u r eo nm 。ad i s t r i b u t e ds i g n a t u r es c h e m e a c h i e v e st h r e s h o l dt h ,i fn oc o a l i t i o no ft ( o rl e s s ) p l a y e r sc a np r o d u c ea n e wv a l i ds i g n a t u r e ,e v e na f t e rt h es y s t e mh a sp r o d u c e dm a n ys i g n a t u r e so n d i f f e r e n tm e s s a g e s a s i g n a t u r er e s u l t i n g f r o mat h r e s h o l ds i g n a t u r es c h e m ei s t h es a m ea si fi tw a sp r o d u c e db yas i n g l es i g n e rp o s s e s s i n gt h ef u l ls e c r e t s i g n a t u r ek e y i np a r t i c u l a r ,t h ev a l i d i t yo ft h i ss i g n a t u r ec a n b ev e r i f i e db y a n y o n ew h oh a st h ec o r r e s p o n d i n gu n i q u ep u b l i cv e r i f i c a t i o nk e y i no t h e r w o r d s ,t h et h r e s h o l ds i g n a t u r ei st r a n s p a r e n t t h r e s h o l ds i g n a t u r e sa r em o t i v a t e db o t hb yt h en e e dt h a ta r i s e si ns o m e o r g a n i z a t i o n st oh a v eag r o u po fe m p l o y e e sa g r e eo nag i v e nm e s s a g eo ra d o c u m e n tb e f o r es i g n i n gi t ,a sw e l la sb yt h en e e dt op r o t e c ts i g n a t u r ek e y s f r o mt h ea t t a c ko fi n t e r n a la n de x t e r n a la d v e r s a r i e s t h el a t t e rb e c o m e s i n c r e a s i n g l yi m p o r t a n tw i t ht h ea c t u a ld e p l o y m e n to fp u b l i ck e ys y s t e m si n p r a c t i c e t h eg o a lo f at h r e s h o l ds i g n a t u r es c h e m ei st w o f o l d :t oi n c r e a s et h e a v a i l a b i l i t yo ft h es i g n i n ga g e n c y ,a n da tt h es a m et i m et oi n c r e a s et h e p r o t e c t i o na g a i n s tf o r g e r yb ym a k i n gi th a r d e rf o rt h ea d v e r s a r yt ol e a r nt h e s e c r e ts i g n a t u r ek e y t h et h r e s h o l da p p r o a c hr u l e so u tt h en a i v es o l u t i o n b a s e do nt r a d i t i o n a ls e c r e ts h a r i n g ,w h e r et h es e c r e tk e yi ss h a r e di nag r o u p b u tr e c o n s t r u c t e d b yas i n g l ep l a y e re a c ht i m et h a t as i g n a t u r ei st ob e p r o d u c e d s u c hp r o t o c o lw o u l d c o n t r a d i c tt h er e q u i r e m e n tt h a tn or ( o rl e s s ) p l a y e r s c a ne v e r p r o d u c e an e wv a l i d s i g n a t u r e i n t h r e s h o l d s c h e m e s , m u l t i p l es i g n a t u r e s a r e p r o d u c e d w i t h o u ta n e x p o s u r e o ra n e x p l i c i t r e c o n s t r u c t i o no ft h es e c r e t k e y 。 t h es e c o n d p a r to f t h i sa r t i c l ed i s c u s s e san e w c r y p t o s y s t e m ,q u a n t u m c r y p t o s y s t e m t h ea p p l i c a t i o no fq u a n t u mm e c h a n i c st oc r y p t o g r a p h yh a s 6 山东大学硕士学位论文 l e dt oan e ws u b j e e t :q u a n t u mc r y p t o g r a p h y 。q u a n t u me r y p t o g r a p h i c s y s t e mi sd i f f e r e n tf r o mp u b l i ck e ys y s t e m i ne x c h a n g i n gs e c r e tk e y ,w h i c h c a nd e t e c te a v e s d r o p p i n gs h o u l di to c c u ra u t o m a t i c a l l yw h i l ep u b l i ck e y s y s t e mc a d ta c c o m p l i s ht h i s t h i sp a p e ri m p r o v e st h eb b 8 4q u a n t u m c r y p t o g r a p h i cp r o t o c o l w i t hn o i s ei n s e c u r i t y a n di n e f f i c i e n c y t h e i m p r o v e m e n tw ep r e s e n tc a nb ea p p l i e dt oo t h e rq u a n t u mc r y p t o g r a p h i e p r o t o c 0 1w i t h n o i s e k e y w o r d s :t h r e s h o l dc r y p t o s y s t e m ,t h r e s h o l d s i g n a t u r e , d s s s i g n a t u r e ,q u a n t u mc r y p t o s y s t e m ,k e ye x c h a n g e 第一章绪论 1 1 引言 传统公钥体制的安全性在于私钥的安全性,我们总是假定这些私钥是不能被 对手得到的。换句话说,整个系统的安全性就在于使对手不能访闽存赭这些私钥 的介质。但是在现实的世界里,被收买的系统管理员,黑客,病毒,意外事故以 及错误的配置都可能导致对手访问到存储私钥的介质。人们采取了多种手段以防 止这种介质访问的攻击,其中非常重要的一种方式就是引入了秘密共享的概念。 通过秘密共享,把一个密钥分布式的存储在多个人手里,每个人只存储密钥的 部分,当需要进行解密或签名时,多个人合作暂时恢复密钥,但是暂时存放密钥 的地点仍然是整个系统的弱点,为了解决这个问题,人们又引入了门限密码体制 的概念。在门限密码体制中,每个人不是送出密钥的一部分,而是一个用他的予 密钥运算之后的部分结果,当收集到足够多的部分结果时,就可以把整个结果恢 复出来。这样门限秘密码体制就显著增强了公钥体制的安全性。在本文中,我们 将主要研究门限签名体制。 s h a m i r 第一个提出门限签名方案,把用于数字签名的整个私钥不是给单个 个人,而是每个人只给密钥的一部分,当需要签名时就要凑够多个人同时参与才 彳亍。他的方案有很多问题,生成签名的机器可以泄漏主密钥,更改被签名的文件, 签署额夕卜的文件,所以必须完全信任生成签名的机器的制造者和操作者,显然这 是很不安全的。现在的门限体制要求在任何时候都不能由单个人掌握整个密钥。 最近人们已经把门限密码学她发展推向多样化,例妇门限零知识证明,门限 伪随机数生成器等。门限秘密学的概念已经扩展成为一股的访问结构,这样经过 授权的“的子集( 参与者的集合) 可以与密码体制结合使用而不必指定门限了。 注意这样的体制的安全行是变化的。有无条件安全的,有可证安全的( 在计算复 杂性的假定下) ,有与原来的体制一样安全的( 可证) ,还有一些体制具有直观的 安全性。最近的研究主要集中予以下几点: 1 可靠性 一 出銮盔堂堡主兰笙鎏塞 一 2 提高安全性,主要有以下几个方面: ( 1 ) 没有可信中心。 ( 2 ) 预动安全性和它的推广。 ( 3 )内部的匿名性。 3效率 4 推广到门限d s s 我们将在第二章详细讨论上述的几点。 1 2 密码体制的基本模式 一个密码系统可以看成是有两个输入的函数的求值,这两个输入一个是密 钥,另一个随着应用的不同而不同,可以是明文,密文或者是要签名的文件,在 本文中我们把这个函数写成密钥作为输入,另一个作为参数,即g 。( k e y ) 。 一些重要的密码体制都具有同态的特性,用函数g 表示就是 g b ( t + k :) = g b 阮) + 忙:) 其中b 就是先前提到的输入,k l 、k 2 属于密钥空间。例如我们考虑e 1 g a m a l 密 码体制首先公钥是( g ,y ,p ) ,其中p 是一个足够大的素数,g 有很大的指数, 而y = g 。m o d p ,此处d 是密钥。密文是“,c 2 ) = 詹m o d p ,m + y m o d p ) ,其中 m e z ,是明文a 现在主要部分是计算g 。0 ) = c ? m o d p 。我们考虑的第二个例子 是r s a 签名和解密,当签名或解密时需要计算矾p ) = b 4 m o d n ,这里6 是要签 名的文件或相应的密文,d 是私钥,珂是公开的模,也就是两个素数的乘积。 s h a m i r 的秘密共享方案满足如下的特性: k e y = m ( c o n t , n ) - ( 5 h a r e ,) ( 1 ) 这里b 是所有参与者的集合4 的子集,并且= f 是门限。如果使用8 h a m i r 的 秘密共享方案并且g 是同态的,则: g i n p u t ( 叻) = g ,f 0 0 l i , b ) ( s h a r e i ) 1 山东大学硕士学位论文 = 丌g ,。( c o 一柚 = n b ,g 枷e ;) p 8 ( 2 ) 在上式中g m p i ( s h a r e ) 可以由子密钥的持有者计算出来,然后随同他的身份( 也就 是i ) 一起发送给可靠的合并者。如果有足够的子秘密持有者响应,知道了他们的 身份的合并者就有了个集合曰7 ,i b i t ,即b 至少有门限的大小。合并者选 择一个集合曰b 使得= ,计算在口中的参与者f 的常数c o 珂柚,然后就可以 计算上式了。 刚开始时,g 。s h a r e ,) 称为部分结果,但现在可以称为部分签名,部分解 密等等视情况而定。 1 3 常用术语 下面我们将介绍本文中用到的一些常用的术语,有些可能在前面已经使用过 了。 参与者:是指参与协议的所有人员,他们每个人都掌握一个密钥,组成 集合爿,有时我们会称之为成员。 处理者:在协议的初始阶段产生所有密镅的入,他还负责把相应的密钥 发送给参与者。 合并者:收集参与者发送给他的部分结果( 如部分签名等) ,当收集到 足够多时他把这些部分结果合并产生最终结果。 子密钥:是指所有参与者个人所掌握的密钥,是整个密钥的一部分,有 时也称为子秘密。 子密钥持有者:由于所有的成员都掌握子密钥,因此有时也称成员为子 密钥持有者。 对手:企图攻破密码体制的人,他可能是参与者,也可能会收买部分参 与者。 还有其他一些术语,我们将在各个章节中在使用的时候再介绍。 1 0 山东大学硕士学位论文 1 4 本文的工作 本文分为两部分。 第一部分以d s s 门限体制为载体,研究了门限密码学的安全性、强健性、 效率等多方面的问题。特别详细研究了r o s a r i og e n n a r o ,s t a n i s l a wj a r e c k i , h u g ok r a w c z y k 和t a lr a b i n 等人提出的方案,在对这些方案分析的基础上, 提出了一些具有更好安全特性的新的改进方案。 本文的第二部分讨论了一种新型密码体制量子密码体制,对这种新型的 密码体制作了较为深入的研究,提出了提高其安全性和效率的新思想、方法。对 目前影响力较大的所谓“有噪声的b b 8 4 协议”进行了改进,得到一个改进的1 3 1 3 8 4 协议。 第二章最近的研究 在这一章中,我们将回顾已有的研究成果。 2 1 安全性 首先讨论安全性方面的问题。在s h a m i r 提出的原始的门限签名方安中合并 者必须是可靠的,否则就必须有容错机制。如果最终的计算结果是公开的( ,q i 如 签名) ,合并者可以泄漏他收到的信息,否则( 例如解密) ,他就不能泄漏他收到 的信息。安全性的目标就是所得到的门限签名算法与原始算法一样安全,而且我 们也应该看到密码分析者有可能会获得如下的额外信息: l 、至多卜1 个子秘密,由至多t 一1 个子秘密持有者泄漏的: 2 、至多,= h 个部分结果,并且每一个g 。( 丝y ) 都会泄漏给密码分析者; 不管密码分析者有没有得到这些额外信息,他要伪造签名或解密的任务都应该是 困难的。要做到这一点,就需要任意卜1 个子秘密都能被模拟( 零知识) ,并且 在给出g 。( 女砂) 的情况下部分结果也能被模拟( 最小知识) 。 s h a m i r 原始地秘密共享方案仅在有限域内有效,而r s a 的密钥属于 z 蛳1 ( + j ,这不是个有限域。如在方程( 2 ) 中所展示的,方程( 1 ) 对于获得门 限密码体制非常合适。s h a m i r 秘密共享的一个改进 4 在阿贝尔群上有效( 把密 钥视为属于扩展的密钥空间) 。那么如下的方程就应该看成是模运算上的标量乘 机而不是指数运算: g ,。c o n 柚s h a r e ,) = g 删0 删,炉” 最后,0 0 ) 必须保持是秘密的,这意味着即使是子秘密的持有者也不能知道 z m 。 现在的门限体制有更高的要求。首先是能处理没有可信的处理者的情况,在 最初的模式中都会用到一个可信的处理者,由他来计算并产生参与者的子密钥。 很明显应当避免使用这样的方法。 1 2 一= 些垒望些掣篁垦= = = = = 一 我们先看一下什么是同态的秘密共享,然后讨论一种不需要可信的处理者秘 密共享方案。 假设( s 一,s ,) 是密钥k 的一个子密钥分配方式,类似的,0 :,s :,s ;) 是 密钥女,的分配方式。又假定我们在子密钥空间和密钥空间上定义一种操作,它以 “q - ”表示,如果“s ,+ s :x b :+ s :) ,0 ;+ j ;) ) 是密钥七+ 的一个可能的子密钥 分配方式,则这个秘密麸享体制就是同态的。s h a m i r 的秘密共享方案就是同态 的。 使用下面的同态的秘密共享方案可以不需要可信的处理者。第一个参与者随 机选择个密钥k ,然后扮演这个密钥的处理者的角色,产生出子密钥 ( s i , i & 。,s 。) 。他通过安全的信道把子密钥j l j ( 1 i - 1 ) 发送给参与者f 。现 在b ( bca ) 中的,个参与者都实施类似的操作( 他们独立的随机的选择密钥) , 然后把子密钥s ,秘密的发送给参与者i 。这样参与者i 就可以计算他的子密钥 t = 。s 。由于这个共享方案是同态的,因此薯就是密钥立= 螂k ,的子密 钥。如果所有的密钥t 都属于一个阿贝尔群,那么卜- 1 个子秘钥持有者不会得到 关于密钥k 的任何信息。 在门限密码体制中第一个使用这个方法的是p e d e r s e n 8 】,他的体制保证了 发布是可验证的,也就是说,每个子密钥持有者收到子密钥之后都会重新计算这 个密钥。他的体制也确保了私钥确实是对应于发布的公钥的。 我们再来看些与预动安全性相关的问题。当一些子密钥丢失或者是被盗 时,或者更严重的是当一个外面的人收集了超过门限的子密钥数时,整个密码体 制就会失效。而改变这个组织的公钥显然不是个好办法,因为那些没有及时更新 他们的公钥数据库的人将会使用错误的公钥,而且在使用新的公钥之前需要多次 的验证。对于这个问题的解决方法就是在不依赖于可信的处理者的情况下能产生 确保正确的子密钥,并且老的公钥存在的时间尽可能的长。应该经常刷新子密钥, 老的子密钥也要被销毁,这样使对手收集到足够数量的子密钥的能力就降低了。 我们下面讨论如何把同态的秘密共享方案运用于门限体制以获得预动安全 的门限密码体制。在这里,我们总是假定秘密共享方案是同态的。 如果h ,j :,s ,) 是密钥女的一个子密钥分配方案,而【q ,s :,j ,) 是密钥 “0 ”的一个随机的子密钥分配方案,那么 ( _ ”,s :”,一 ”) = ( s 。+ s ,s :+ s :,s ,+ s ,) 则是密钥七的另外一种子密钥分配 方案。假定人们信任f 个子密钥持有者,那么这,个参与者( 用歹来代表) 每个人 都按上节的方法发布他们的随机数【j ,j m ,s 川) ,这些子密钥对应于密钥 “0 ”0 如果所有的操作都是在阿贝尔群上进行的,而且秘密共享方是完美的( 将 在后面解释) ,那么最终的子密钥s 。= s ,+ 。s 与原始的子密钥5 ,是完全独 立的,而它们都是密钥k 的子密钥。这样我们就实现了刷新子密钥。 还有种情况就是内部的匿名性。在没有内部人员或合并者的帮助下,一个 外部人员只能看到g 一,( 铆) ,因此他就不能知道谁参与了计算。然而内部人员 和合并者可能能看到g i n t n a ( $ h u r e ) 和i ( 例如在门限签名中) ,这样他们就能知道 谁参与了运算。在有些情况下例如投票,这种情况是不希望发生的而且要确 保内部人员的匿名性。第一个解决方案在【5 】中给出。现在一个相反的问题,追 踪是谁参与了运算的问题在【9 】中有讨论,这有助于解决门限密钥体制的强健性 方面的问题。 2 2 强健性 我们回顾一下方程( 2 ) ,如果一个或多个子秘密持有者送出错误的部分结果, 整个的结果将很可能是错的。如果使用公钥体制的话,人们可以用公钥来验证结 果是不是错的。使用公钥系统,当错误部分结果的数量较少时,通过遍历查找, 最终能确定是谁送出了错误的部分结果。然后就可以重新计算部分结果 g i o p , ( k e y ) ,忽略掉错误的部分结果,这样就至少需要f + e 个部分结果,其中8 是 错误的数目。 为了分析强健性,我们先看一个简单的例子,讨论一下无条件安全的门限密 码体制a 在 9 7 4 年,g i l l b e r t ,m a e w i l l i a m s 和s l o a n e 提出了下面的认证方案。 发送方和接收方都有一个共同的口,b 。6 f ( g ) ,它在矢量空间g f 0 ) g f ( g ) 上描 1 4 坐垄盔兰堡圭兰垡鲨塞一 述了一条秘密的直线,其上坐标为g ,_ y ) 的点满足方程y = d x + b ( 这个体制的 原始描述是在映射空间上,而不是在矢量空间上) 。为了验证一个消息m g f ( q ) , 发送方发送这条直线上的一个点m ,m a c ) ,即消息认证码删c = 口m + 6 ,当接 收方接收到的点( m ,m a c ) 在这条秘密的直线上时,就认为他收到的消息坍通过 了认证。如果这条秘密直线只使用一次的话,那么它被仿冒攻击或替代攻击成功 的概率是l q 。 如果q 是素数,那么可以使用任何的秘密麸享方案把它改造成为门限的认证 体制。出如瑕设s 。是的子秘密,s t 是6 靛子秘密,那么m a c , = m s + s ,就 是m a c 的子秘密,称为m a c 的部分结果。如果使用s h a m i r 的秘密共享方案, 那么这个体制就不具备强健性【1 0 。 把门限体制和错误纠正码结合起来使用,这个体制就具备了强健性,事实上, 可以选择a 的子秘密是0 1 , s 2 ; ,s t ) 和6 的子秘密是f 屯,j :,_ 量1 为g ,b ) 上线 性编码的编码字,如果把它当成一个很好的错误检测码,那么只要有足够多的参 与者计算他们的m a c 的部分结果m a c , 我们就能纠正错误。为了安全性的考虑, 这个体制必须是完美的和合成的 1 1 。完美性的意思是卜1 个子秘密不会给出关 于密钥的任何信息,合成性的意思是说即使泄漏了瓴+ 屯) 的所有子秘密,这里 ( 毛+ :) g f ( q ) ,除了泄漏七+ 七:之外,不会泄漏关于阮,屯) 的任何其他信息。 我们再以门限r s a 体制为例讨论一下如何使一个密码体制具备强健性。从 1 2 】可以看出,s h a m i r 秘密共享方案的推广就意味着r e e d s o l o m o n 码的推广, 因此,似乎只要使用这个一般的r e e d - s o l o m o n 码,就可以使r s a 体制具备强 健性。但是当错误数很多时,目前还没有算法能在一般的r e e d - s o l o m o n 码上找 出错误。很容易证明如果人们能很有效的把b e r l e k a m p m a s s e y 算法 1 3 】推广应 用到一般的r e e d s o l o m o n 码上,那样离散对数问题和因子分解问题就都很容易 了 1 4 。是否存在一个多项式时间的算法能检测到发生错误的位置仍然是个悬而 未决的问题。 获得强健的r s a 体制的一般方法是发送更多的数据,并且依赖r s a 是公钥 出丕丕堂堡主堂焦笙塞 算法这样一个事实。如果f 个参与者中的每一个都能证明他发送的是正确的结果, 那就忽略掉其它所有的部分结果。这样就需要f - t - e 个部分结果,其中e 不正确的 部分结果的数目。 g e n n a r o j a r e c l d k r a w c z y k r a b i n 提出了两个方法可以获得强健的门限 r s a 体制。一个方法是交互的,另一个是非交互的。我们讨论基于 g i l l b e r t m a c w i l l i a m s s l o a n e 认证方案的非交互的方法。 这个方法假定n = p q 是两个安全素数的乘积( 一个素数p 如果可以表示为 2 口+ 1 的形式,这里p 是素数,那么称p 是安全的) 。为了检测一个错误,合并 者需要收到额外的信息d 。和6 。,这里衍表参与者的身份信息,j 是子子秘密a 对于每一个子子秘密j 。,处理者统一的随机的选择一个口。,其中1 口。月4 , 也会这样选择一个b 。,其中1 b 。s “4 一,在这里需要恰当地选取反和占2 1 5 j 。处理者把对应于所有的,子子秘密s 。和整数_ y 。秘密得交给参与者f ,这 里y 。= 岔,s 。,+ 6 。a 处理者也把所有的f 和,的a i d 和6 。秘密的交给合并者。 我们信任合并者不会泄漏这些值,而且会按照下面的方法进行验证,否则就需要 多个合并者。 当需要共同签名时,参与者i 计算所有的消息川的子部分签名盯。子消息验 证码r = m “m 0 0 1 7 ,并把这些值发送给合并者。现在我们来看一下合并者如何 确定正确的部分签名。要验证它是否正确,合并者只需要验证下面的式子是否对 于所有的o - 。都成立: o i , j 卜m i j i y j m o d n 现在合并者就可以使用这些验证成功的部分签名了。但是也要注意正确的部分签 名可能是盯。,这样对于现在已知的所有的门限r s a 体制都有可能需要乘以一1 才得到真正的签名。当合并者知道了e 之后他能很容易的知道是不是需要这样 做。 出銮盔堂堡主堂垡鲨塞 2 3 效率 一 对于无条件安全的门限认证体制和以e 1 g a m a l 体制为基础的门限加密体制 来说,每一个子密钥都与主密钥一样长。而当把扩展的s h a m i r 秘密共享方案用 于门限r s a 体制时有: z4l e n g t h ( k e y ) l e n t h ( s h a r e ,) 2 + ,+ l e n g t h ( k e y ) 这里z 是子秘密持有者的人数。现在出现了比门限r s a 体制效率更高的秘密共享 体制,主要有两个方法:一个肯定有效,而另一个可能有效,在第二个方法中, 可能存在某些特定的参与者的集合,他们的候选人人数大于或等于门限t ,但是 他们却不能完成方程( 2 ) 的门限运算。 对于门限r b a 来说,提出可用于门限密码体制的更有效的秘密共享方案尤 为重要。我们首先讨论t = 2 的体制,然后用在 2 】中给出的k u r o s a w a s f i n s o n 查 值方法对它进行推广。 首先解释f = 2 的情况。 假设,是参与者的人数,茁“) 是一个群而且密钥k k 。我们把参与者的标 号i 定为从0 到卜1 ,对f 我们以二进制方式表示,也就是说i 对应于比特串 o 。i ,( ) j 。 当生成子密钥时,处理者选择厂1 0 9 :( f ) 个独立的,统一的,随机元素k ( 1 c l o g :( f ) ) 。当i 。= 0 时,参与者i 会通过一个安全的信道收到一个 ,= o ,当i 。= l 时,会收到= k - r , 。这样每个参与者f 都会收到厂l o g :( f ) 1 个 值。 现在我们来看一下f 和如何重新构建密钥。如果f ,那么在他们的二迸 制表示中至少有一列c 是不同的,也就是说f c 丘。假设= 0 ,则七= s 。+ j 。 如果群世( + ) 是阿贝尔群,那么这个体制就是同态的,而且不管是否等于0 ,这 个重构过程都能完成。 下面我们解释如何把这个方法用运到门限r s a 中。假定n 是两个等长度的素 数的乘机分发者使用世= z 。( 。) “) 和七= d 按照上面说的方法生成子密钥。又设 山东大学硕士学位论文 m 是经过h a s h 的要处理的消息,当需要共同签名时,每个参与者i 都送出整数i 和对于所有c 的子部分签名 3 - 。= m 吣。假设这一切都是由参与者f 和j 来做的, 有了正确的子秘钥,知道了i g u ,我们就能找出i 。,。的那一列c ,并就此计算 出签名:0 - i ,。+ 盯。= m 毛= m 。如果弭口j 预先知道了将要与谁合作的话,那 么只需要送出一个吼。就可以了,而不是所有的n o g :( f ) 个。 我们把这个方法进行一些推广。_ k n f 匀( 2 ,叭 限体制基于n o g :( f ) 个独立的 ( 2 ,2 ) 共享体制。在 2 提出的体制也满足相同的特性。k u r o s a w a 和s t i n s o n 把这 个特性做了些推广。下面我们来看看。 假设爿和a 都是有限集,b 是爿的一个子集,= h ,= i 刮,而且f 是爿 到a 函数集,我们假定, ,。如果一个函数厂f 当限制到b 上是一对应时, 则函数厂是b 上的一个完美哈希。如果对于所有的势为r 的子集b c a ,在f 中 至少存在一个函数f 是b 上的完美哈希,那么f 是一个完美哈希族( f ,f ,) 。我们 看到二进制表示实际上就是定义了一个从a 到a = o ,1 ) 的一个完美哈希族。 一个完美哈希族能从一个老的秘密共享方案构建一个新的秘密共享方案。假 g n - 。i ( ,) 共享方案和一个完美哈希族( f ,f ,f ) f ,我们就能构建一个( ,f ) 秘密 共享方案。首先看一下如何分配子秘密,对每一个厂f ,处理者用o ,) 秘密共 享方

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论