（运筹学与控制论专业论文）短的强指定认证人签名.pdf

摘要 指定认证人的签名首先是由j s k o b s s o n ，s a k o 和i m p s g l a z z o 在1 9 9 6 年欧洲密码学会议上提 出的。同年c h a u m 也在他的专利中提出了和指定认证人的签名相似的概念一一私有签名。指定 认证人的签名是指签名者把对消息的签名发送给一个指定的验证人，只有这个指定的认证人才 能相信签名的有效性。指定认证人不能够让任何第三方相信签名是真实有效的，因为认证人自 己可以产生一个与原始签名不可区分的有效签名。指定认证人的签名在实际中有很多应用场 合，如招标、电子投票和电子拍卖。 本文讨论了指定认证人签名的加强形式：强指定认证人的签名。给定两个可能签名人的公 钥以及一个强指定认证人的签名攻击者无法判断谁是真实的签名人。在已有的强指定认证人 的签名方案中，签名的代价较高，签名的长度也较长。在介绍了一些( 强) 指定认证人签名的 相关知识后，本文给出了两个短的强指定认证人签名方案。这两个方案分别基于不同的密码体 制：传统的公钥密码体制和基于身份的公钥密码体制。 本文提出的方案的优点之一是具有比较短的签名长度，只有f z ：| 签名长度是所有已知的 方案中最短的，具有较低的通讯代价，在低带宽的网络环境中更加适用。同时，和已有的方案 相比，本文提出的方案具有最小的计算代价。在传统公钥密码体制下，产生和验证签名只需 要2 个指数运算。而在基于身份的公钥密码体制下，产生和验证签名只需要2 个p a i r i l l g 运算。计 算代价有了很大程度上的减少，因而更加适合在一些只有有限计算资源的网络环境中使用。 本文所提出的短的强指定认证人签名方案在满足所有强指定认证人签名的属性的同时，签 名的长度非常的短。而且在d i f 丑e - h e l l m s n 问题的假设下，本文所提出的方案是安全的，并且给 出了安全性的形式化证明。 美鼍词；指定认证人的签名，强指定认证人的签名，短签名基于身份的密码体制。d i f r e - h e l l m e n 问愿 v a b s t r a c t t h ec o n c e p to fd e s i g n a t e dv e r i f i e rs i g n a t u r e ( d v sf o rs h o r t ) w a sf i r s tp r e - s e n t e db yj a k o b s s o n ，s a k oa n di m p a g l i a z z oa te u r o p c r y p t 9 6a n di n d e - p e n d e n t l yb yc h a u mi nh i sp a t e n t ，u n d e rt h en a m ep r i v a t es i g n a t u r e s d e s i g n a t e dv e r i f i e rs i g n a t u r ei si n t e n d e dt oas p e c i f i ca n du n i q u ed e s i g - n a t e dv e r i f i e r ，w h oi st h eo n l yo n et h a ti sa b l et ob e l i e v et h es i g n a t u r e s v a l i d i t y t h i sd e s i g n a t e dv e r i f i e rc a n n o tc o n v i n c ea n yt h i r dp a r t yt h a tt h e s i g n a t u r ei sa c t u a l l yv a l i d ，e s p e c i a l l yb e c a u s et h ed e s i g n a t e dv e r i f i e rc a n a l s og e n e r a t eas i g n a t u r ew h i c hi si n d i s t i n g u i s h a b l ef r o mt h eo r i g i n a lo n e t h i sk i n do fs i g n a t u r eh a sw i d ea p p l i c a t i o n si nm a n ya r e a s ，s u c ha sc a l l f o rt e n d e r s ，e l e c t r o n i cv o t i n ga n de l e c t r o n i ca u c t i o n t 1 1 i sm a s t e rt h e s i sc o n s i d e r sas t r o n g e rn o t i o no ft h ed e s i g n a t e dv e r i t i e rs i g n a t u r e ：s t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r e ( s d v sf o rs h o r t ) t h i s k i n do fs i g n a t u r eh a st h ep r o p e r t yt h a tg i v e nt w op o t e n t i a ls i g n i n gp u b - l i ck e y sw i t has t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r e ，i ti s c o m p u t a t i o n a l l y i n f e a s i b l ef o ra ne a v e s d r o p p e rt od e t e r m i n eu n d e rw h i c ho ft h et w os e c r e t k e y st h es i g n a t u r ew a sp e r f o r m e d t h e r ea r es e v e r a ls t r o n gd e s i g n a t e d v e r i f i e rs i g n a t u r es c h e m e si nt h el i t e r a t u r e h o w e v e rt h e ya l ls u f f e rf r o m h i g hc o m p u t a t i o n a lc o s ta n dl o n gs i g n a t u r el e n g t h a f t e ri n t r o d u c i n gt h e b a s i c so ft h ec r y p t o l o g ya n d ( s t r o n g ) d e s i g n a t e dv e r i f i e rs i g n a t u r e ，t w o s h o r ts t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r es c h e m e sa r ep r o p o s e ：o n ei n t r a d i t i o n a lp u b l i ck e ys y s t e ma n dt h eo t h e ri ni d e n t 渺b a s e dp u b l i ck e y s y s t e m o n eo ft h ea d v a n t a g e so ft h ep r o p o s e ds c h e m e si st h es h o r tl e n g t ho f t h es i g n a t u r e t h es i g n a t u r el e n g t hi so n l yl z 孔w h i c hi st h es h o r t e s tc o i n - u l p a r e dw i t h “lt h ee x i s t i n gs d v s s c h e m e s t h e r e f o r et h ep r o p o s e ds c h e m e s h a v el o wc o m m u n i c a t i o nc o s ta n dm o r ea p p l i c a b l ei nt h en e t w o r k sw i t hl o w b a n d w i d t h a n o t h e ra d v a n t a g ei st h a tt h ep r o p o s e ds c h e m e sh a v et h el e a s t c o m p u t a t i o n a lc o s ta m o n g a l lk n o w ns d v ss c h e m e s c o n c r e t e l y , g e n e r a t i n ga n dv e r i f y i n gas i g n a t u r eo n l yn e e d st w oe x p o n e n t i a t i o n si nt r a d i t i o n a l p u b l i ck e ys y s t e ma n dr e q u i r e so n l yt w op a i r i n g si ni d e n t i t y - b a s e dp u b l i c k e ys y s t e m t h ec o m p u t a t i o n a lc o s ti sr e d u c e dd r a m a t i c a l l ya n dt h en e w s c h e m e sa r em o r ea p p l i c a b l ei nt h es y s t e m sw i t hl i m i t e dc o m p u t a t i o n a l r e s o u r c e b o t ht h et w os c h e m e ss a t i s f ya 1 1t h ep r o p e r t i e so fs t r o n gd e s i g n a t e dv e r - i f i e rs i g n a t u r ea n da r ep r o v a b l ys e c u r eu n d e rt h ed i f f i e - h e l l m a na s s u m p - t i o n s m a t sm o r e t h ef o r m a lp r o o f so ft h e i rs e c u r i t ya x ep r e s e n t e d k e y w o r d s ：d e s i g n a t e dv e r i f i e rs i g n a t u r e ，s t r o n gd e s i g n a t e dv e r i f i e rs i g - n a t u r e ，s h o r ts i g n a t u r e ，i d e n t i t y - b a s e dc r y p t o g r a p h y , d i f i t e - h e l l m a np r o b - l e m s l v 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取褥的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所傲的贡献均已在论文中作了声明并表示 了谢意。 作者签名： 日期； 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅：有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后运用本规定 作者签名： 日 期： a c k n o w l e d g e iw o u l dl i k et ot h a n kp r o f e s s o rr u s u ns o n g m ys u p e r v i s o r f o rh i sm a n y s u g g e s t i o n sa n dc o n s t a n ts u p p o r td u r i n gt h i sr e s e a r c h ia ma l s ot h a n k f u lt op r o l e s s o rf u t a iz h a n gf o r h i si n t r o d u c t i o no ft h eb a s i c sa b o u tt h e c r y p t o g r a i ) h ya n de a r n e s td i s c u s s i o n s i ti 8m yh o n o rt h a tih a p p e n e dt ok n o wd ry im ua n dd rw i l l ys u s i l o f r o mu n i v e r s i t yo fw o l l o n g o n gi na c o n f e r e n c e t h e yh a v eb e e nw e l lk n o w n i nt h ec r y p t o g r a p h yr e s e a r c hc i r c l e d u r i n gt h el a s taf e wm o n t h s ，t h e ) h a v eg i v e nm ee n o r m o u sa d v i c ea n dh e l p ih a dt h ep l e a s u r eo fm e e t i n gd rg e n l i nj i d rh u m g a n g d rp i n g j i a n g ，m rq i n g b a oz h u ，m rq i n g s h e n gc h u ，d rw e i g u a n gq u ，d ry o n g g a o c h e n ，d rz h i r e ns u n t h e ya r ew o n d e r f i l lp e o p l ea n dt h e i rc o u r s e sa n d h e l pm a k er e s e a r c hl i k et h i sp o s s i b l e is h o u l da l s ot h a n ko t h e r t e a c h e r s t h a th a v eg i v e nm eh e l pd u r i n gm y u n d e r g r a d u a t ea n dg r a d u a t es t u d i e si n n a n j i n gn o r m a lu n i v e r s i t y , o fc o u r s e ，i 啪g r a t e f u lt om yp a r e n t s m yu n c l ea n da u n tf o rt h e i r p a t i e n c ea n df o 口e w i t h o u tt h e mt h i sw o r kw o u l dn e v e rh a v ec o m ei n t o e x i s t e n c e f i n a l l y ，1w i s ht ot h a n kt h ef o l l o w i n g ：a i p i n gq i a 0 ，j i ez h a o ，l i n q i a n g l i u q i a o z h ix ua n do t h e r si no u rc o m p u t e rr o o m ( s i n c ew ea l w a y sd i s c u s s p r o b l e m s ) ；p e i q ih u a n g ，y o n gf a n ，s h i c a oc h e n ，y i j u nz h a n ga n do t h e r s i nt h en o 3d o r m i t o wb u i l d i n g ( f o ra l lt h eg o o da n db a dt i m e sw eh a d t o g e t h e r ) ；w e i 、；h ( s h ek n o w sw h y la n dm yl i t t l es i s t e r ( b e c a u s es h ea s k e d m et o ) v 1 a b b r e v i a ti o n b d hb i l i n e a rd i 甩e - h e l l m a n c ac e r t i f i c a t i o na u t h o r i t y c d hc o m p u t a t i o n a ld i f i 日e h e l l m a a d v sd e s i g n a t e dv e r i f i e rs i g - n a m r e i d - b a s e di d e n t i t y - b a s e d i d s d v si d e n t i t y b a s e ds t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r e i d s s d v si d e n t i t y b a s e ds h o r ts t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r e p k cp u b l i ck e yc r y p t o g r a p h y p k gp r i v a t ek e yg e n e r a t o r p k ip u b l i ck e yi n f r a s t r u c t u r e v 1 1 s d v ss t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r e s s d v ss h o r ts t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r e u f - s d v s c m a u n f o r g e a b i l i t yo fa ns d v ss c h e m eu n d e rac h o s e n m e s s a g ea t t a c k u f - s s d v s c n i au n f o r g e a b i l i t yo fa ns s d v ss c h e m eu n d e rac h o s e n m e s s a g ea t t a c k u f - i d s s d v s c m au n f o r g e a b i l i t yo fa ni d s s d v ss c h e m eu n d e ra c h o s e nm e s s a g ea t t a c k v 1 1 1 n o t a t i o n ：b i l i n e a rp a i r i n g g 1 g 2 ：t w oc y c l i ca d d i t i v eg r o u p s g j ：c y c l i cm u l t i p l i c a t i v eg r o u p p 厄u ：p u b l i ck e yo ft h eu s e r “ s k ：。：s e c r e tk e yo f t h eu s e r “ 上且g ：zi sr a n d o m l yc h o s e nf r o mt h es e tg 7 p ：r i n go fi n t e g e r sm o d u l op 7 p ：m u l t i p l i c a t i v eg r o u p o f7 7 p e ：n e g l i g i b l ev a l u e g i ：b i tl e n g t ho f t h ee l e m e n ti nt h es e tg 0 ，1 ) + ：p o s s i b l em e s s a g es p a c e p r e f a c e i nt h ee l e c t r o n i cw o r l d ，o n ec a nf i n dm a n ye x a m p l e so ft h ed i g i t a l s i g n a t u r e s c h e m e s i nt h e s es y s t e m s au s e ra l i c es i g n e dc e r t a i ns t a t e m e n ta n dg e t t h ed i g i t a ls i g n a t u r eo ft h es t a t e m e n t ，t y p i c a l t y ，t h es i g n e ds t a t e m e n tc a n a s s u r et h et r u t ho ft h es t a t e m e n ta n d1 i n kt h ei d e n t i t yo ft h es i g n e rw i t h t h e s i g n a t u r e ，a l i c ec a r tp r e s e n th i ss t a t e m e n tw i t ht h ed i g i t a ls i g n a t u r et oa n y v e r i f i e rb o b ，w h oc a ni nt u r nv e r i 移t h es i g n a t u r ea n db e c o m ec o n v i n c e d o ft h et r u t ho ft h es t a t e m e n t t h ee a s eo fc o p y i n ga n dt r a n s m i t t i n gd i g i t a ls i g n a t u r ei so fg r e a tc o n - v e n i e n c et ou s e r s ：a l i c ec a ns i m p l ys e n dac o p yo ft h es i g n a t u r eo ft h e s t a t e m e n tt oa n yv e r i f i e rb o b o nt h eo t h e rh a n d ，t h i ss a l n ee a s eo ft h e d i s t r i b u t i o na p p l i e st ob o ba 8w e l l ，w h oc a ne a s i l yd i s s e m i n a t ea l i c e ss i g n a t u r ea n dc o n v i n c ea nu n l i m i t e dn u m b e ro ft h et h i r d p a r t yv e r i f i e r sa b o u t t h et r u t ho ft h es t a t e m e n t t h i sp o s s i b i l i t yp o s e sas e r i o u st h r e a tt oa l i c e s 口m v a c y o n c ea l i c es e n d so u tt h es i g n a t u r eo ft h es t a t e m e n tt ob o b ) s h e n o1 0 n g e rh a sa n yc o n t r o lo v e rt h en u m b e ro fe n t i t i e sb e s i d e sb o b w h oc a n n o to n l yl e a r nt h es t a t e m e n tb u ta l s ob e c o m ec o n v i n c e da b o u tt h et r u t h o ft h es t a t e m e n t d e s i g n a t e dv e r i f l e rs i g n a t u r e ( d v s ) i ss u c ha k i n do fs i g n a t u r ew h i c hi s i n t e n d e dt oas p e c i f i ca n du n i q u ed e s i g n a t e dv e r i f i e r ，w h oi st h eo n l yo n e c a nb e l i e v et h ev a l i d i t yo ft h es i g n a t u r e u s i n gd 粥，t h ev e r i f i e rb o bc a n n o tc o n v i n c ea n o t h e rp a r t yt h a tt h es i g - n a t u r ei sa c t u a l l yv a l i d ，e s p e c i a l l y b e c a u s eb o bc a na l s oo u t p u tav a l i ds i g n a t u r eo nb e h a l fo ft h eo r i g i n a l s i g n e ra l i c e i fb o bp r e s e n t s t h es i g n a t u r ea n dt h es t a t e m e n tt os o m e o t h e rt h i r d p a r t y ，t h i st h i r d p a r t yc a nn o tb e l i e v et h es t a t e m e n ti ss e n tb y a l i c ee v e nt h es i g n a t u r ei sv a l i db e c a u s eb o bc a f lg e tav a l i ds i g n a t u r eo f a n ys t a t e m e n tb yh i m s e l f v c h yb o bc a nb e l i e v et h ev a l i d 研o ft h ed y sa n db e l i e v et h ec o r r e s p o n d i n gs t a t e m e n ti sm a d eb ya l i c e ? i ti s d u et ot h ef a c tt h a to n l yt w o u s e r s t h es i g n e ra n dt h ed e s i g n a t e dv e r i f i e r ，c a no u t p u tav a l i ds i g n a t u r e a f t e rr e c e i v i n gav a l i ddv ss i g n a t u r eo ft h es t a t e m e n t ，b o bk n o w sh i m s e l f d o e sn o ts i g nt h i ss t a t e m e n ts ob o bb e l i e v e st h a tt h es i g n e ra l i c ed o e sd o i ta n db e l i e v e st h es t a t e m e n ti sm a d eb ya l i c e 。u m i l eo t h e ru s e r sc a b n o t b e l i e v eb e c a u s et h e yc a n n o ts u r ew h o a l i c eo rb o b ，s i g n e dt h es i g n a t u r e t h ec o n c e p to fd e s i g n a t e dv e 州i e rs i g n a t u r e ( dv s ) w a sf i r s tp r e s e n t e d b yj a k o b s s o n ，s a k oa n di m p a g l i a z z oa te u r o p c r y p t 9 6a n di n d e p e n d e n t l y b vc h a u mi nt h ep a t e n t 、u n d e rt h en a m ep r i v a t es i g n a t u r e s t h i sk i n d o fs i g n a t u r eh a sw i d ea p p l i c a t i o n si nm a n ya r e a s s u c ha sc a l l f o rt e n d e r s ，e l e c t r o n i cv o t i n ga n de l e c t r o n i ca u c t i o n t h i sm a s t e rt h e s i sc o n s i d e r s as t r o n g e rn o t i o no ft h ed e s i g n a t e dv e r i f i e rs i g n a t u r e ：s t r o n gd e s i g n a t e d 阮幔厅e rs i g n a t u r e g i v e nt w op o t e n t i a ls i g n i n gp u b l i ck e y sw i t has t r o n g d e s i g n a t e dv e r i f i e rs i g n a t u r e ，i ti sc o m p u t a t i o n a l l yi n f e a s i b l ef o ra ne a v e s d r o p p e rt od e t e r m i n eu n d e rw h i c ho ft h et w os e c r e tk e y st h es i g n a t u r ew a s p e r f o r m e d 。t h e r e 疆es e v e r a ls t r o n gd e s i g n a t e dv e r i f i e rs i g n a t u r es c h e m e s i nt h e1 i t e r a t u r e h o w e v e rt h e ya l ls u f f e rf r o mh i g hc o m p u t a t i o n a lc o s ta n d l o n gs i g n a t u r el e n g t h a f t e ri n t r o d u c i n gt h eb a s i c so ft h ec r y p t o l o g ya n d ( s t r o n 曲d e s i g n a t e dv e r i f i e rs i g n a t u r e t w os h o r ts t r o n gd e s i g n a t e dv e r i f i e r s i g n a t u r es c h e m e sa r ep r o p o s e d o n ei nt r a d i t i o n a lp u b l i ck e ys y s t e ma n d t h eo t h e ri ni d e n t i t y b a s e dp u b l i ck e ys v s t e m ，b o t ht h et w os c h e m e sh a v e t h es h o r t e s tl e n g t ho ft h es i g n a t u r ea n dt h ef e a s tc o m p u t a t i o n a lc o s t t h eo r g a n i z a t i o no ft h i sm a s t e rt h e s i si sa sf o l l o w i n g s ：c h a p t e r1 i n t r o d u c e ss o m eb a s i c sk n o w l e d g eo ft h em o d e r nc r y p t o g r a p h y t h ef o r m a l d e f i n i t i o n sa n dt h er e l a t e dw o r ko ft h edv s & r ep r e s e n t e di nc h a p t e r2 w es h o wt h et w om a i nr e s u l t so ft h i st h e s i si nc h a p t e r3a n dc h a p t e r4 r e s p e c t i v e l y a t1 a s tw ec o n c l u d et h i st h e s i s 2 c h a p t e r1 i n t r o d u c t i o n i nt h i sc h a p t e r w es h o ws o m eb a s i c so ft h em o d e r nc r y p t o l o g yw h i c h i su s e f u lt ou n d e r s t a n dt h ew h o l ep a p e r f o rm o r ei n f o r m a t i o na b o u t m o d e r nc r y p t o g r a p h y , o n ec a nr e a dc h eb o o kf 1 1 t h er e s to ft h i sc h a p t e r i s o r g a n i z e da sf o l l o w s ：w ei n t r o d u c et h et w oa s p e c t so f t h ec r y p t o g r a p h y e n c r y p t i o na n ds i g n a t u r ei ns e c t i o n1 1a n dl ，2 s e c t i o n1 3b r i e l ys h o w s h o wd o e st h ec r y p t o g r a p h yw o r k i nt h el a s tt w os e c t i o n1 4 a n d1 5 ， w ei n t r o d u c et h et w om a i nc r p t o s y s t e m s ：c o n v e n t i o n a lc r y p t o g r a p h ya n d p u b l i ck e yc r y p t o g r a p h y 1 1 e n c r y p t i o n d a t at h a tc a nb e r e a da n du n d e r s t o o dw i t h o u ta n ys p e c i a lm e a s u r e si s c a l l e dp l a i n t e x to rc l e a r t e x t t h em e t h o do fd i s g u i s i n gp l a i n t e x ti ns u c h aw a ya st oh i d ei t ss u b s t a n c ei sc a l l e de n c r y p t i o n e n c r y p t i n gp l a i n t e x t r e s u l t si nu n r e a d a b l eg i b b e r i s hw h i c hi sc a l l e dc i p h e r t e x t o n eu s e se n c r y p t i o nt om a k es u r et h a ti n f o r m a t i o ni sh i d d e nf r o ma n y o n ef o rw h o mi t i sn o ti n t e n d e d ie v e nt h o s ew h oc a ns e et h ee n c r y p t e dd a t a t h ep r o c e s so f r e v e r t i n gc i p h e r t e x tt oi t so r i g i n a lp l a i n t e x ti sc a l l e dd e c r y p t i o n g e n e r a l l y s p e a k i n g ，t h ep u r p o s eo ft h ee n c r y p t i o ni st op r o t e c tt h ep r i v a c yo ft h e m e s s a g e 1 2 d i g i t a ls i g n a t u r e d i g i t a ls i g n a t u r e sl e tt h er e c i p i e n to fi n f o r m a t i o nv e r i f yt h ea u t h e n t i c i t y o ft h ei n f o r m a t i o n so r i g i n 。a n da l s ov e r i f yt h a tt h ei n f o r m a t i o nw a sn o t a l t e r e dw h i l ei nt r a n s i t t h u s ，d i g i t a ls i g n a t u r e sp r o v i d ea u t h e n t i c a t i o na n d d a t ai n t e g r i t y t h e s ef e a t u r e s & r ee v e r yb i ta sf u n d a m e n t a lt oc r y p t o g r a p h y a sp r i v a c y ) i fn o tm o r e ad i g i t a ls i g n a t u r es e r v e st h es a m ep u r p o s ea sas e a lo nad o c u m e n t o rah a n d w r i t t e ns i g n a t u r e h o w e v e r b e c a u s eo ft h ew a yi ti sc r e a t e d ，i t i s s u p e r i o rt oas e a lo rs i g n a t u r ei na ni m p o r t a n tw a y ad i g i t a ls i g n a t u r e n o to n l ya t t e s t st ot h ei d e n t i t vo ft h es i g n e r b u ti ta l s os h o w st h a tt h e c o n t e n t so ft h ei n f o r m a t i o ns i g n e dh a sn o tb e e nm o d i f i e d ap h ) 7 s i c a ls e a l o rh a n d w r i t t e ns i g - n a t u r ec a n n