（基础数学专业论文）一个基于强rsa假设的数字签名方案及其应用.pdf

首都师范大学2 0 0 8 年硕士毕业论文 摘要 2 0 0 0 年c r a m e r 和s h o u p 1 提出了一个不依赖于随机预言机模型的数字签名方案， 该方案在强r s a 假设下可以安全的抵御适应性选择消息攻击而后c r a m e r 和s h o u p 对 其原方案进行了修改并加入了计算离散对数较为困难的假设，从而使得改进方案的签 名长度与方案相比缩短了近一半2 0 0 3 年m a r cf i s c h l i n 3 仅在强r s a 假设下，提出了 与c r a m e r 和s h o u p 改进方案签名长度相同的数字签名方案，并且该方案在执行效率上 要高于仅基于强r s a 假设或计算离散对数困难和强r s a 假设下的签名方案 但是由m a r cf i s c h l i n 设计的签名方案包含了异或运算，因此该方案较难被应用于 可验证签名分享 本文我们改进了m a r cf i s c h l i n 的签名方案并且将改进的方案应用于可验证签名方 案 关键词：强r s a 假设杂凑函数数字签名离散对数可验证签名分享 i i a d i g i t a 1 s i g n a t u r es c h e m eb a s e do nt h es t r o n gr s aa s s u m p t i o na n d i t sa p p l i c a t i o n a b s t r a c t i n2 0 0 0c r a m e ra n ds h o u p 【1 p r e s e n t e das i g n a t u r es c h e m ew h i c hi ss e c u r e a g a i n s ta d a p t i v ec h o s e n - m e s s a g ea t t a c ku n d e rt h es t r o n gr s aa s s u m p t i o na n dw h i c h d o e sn o tr e l yo nt h er a n d o mo r a c l em o d e l c r a m e ra n ds h o u pa d d e dd i s c r e t e - l o ga s - s u m p t i o nt ot h ev a r i a t i o no ft h e i rs c h e m ea n dt h e np r o d u c e ds i g n a t u r e so fr o u g h l y h a l ft h el e n g t h u n d e rt h es t r o n gr s aa s s u m p t i o no n l y ，m a r cf i s c h l i n 3 l a c h i e v e dt h e s a m es i g n a t u r es i z e ，e v e nw i t has n g h t l yi m p r o v e dp e r f o r m a n c et h a ni nt h eo r i g i n a l s t r o n g - r s ao n l yc a s eo rt h ed i s c r e t e - l o ga n ds t r o n g - r s ac a s e b u tt h es c h e m ew h i c hi si n t r o d u c e db ym a r cf i s c h l i ni n c l u d e dx - o ro p e r a t i o n ，s ot h a tt h es c h e m ei sd i f f i c u l tt ob ea p p l i e dt ot h ev e r i f i a b l es i g n a t u r es h a r i n g ( v e s ) i nt h i sp a p e r ，w er e v i s i t e dm a r cf i s c h l i n ss c h e m ea n dt h e na p p l yi tt ot h ev e r - i f i a b l es i g n a t u r es h a r i n g k e y w o r d s ：s t r o n gr s aa s s u m p t i o n ，h a s hf u n c t i o n ，d i g i t a ls i g n a t u r e ，d i s c r e t e - l o g ， v e r i f i a b l es i g n a t u r es h a r i n g 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 怕耽绰 j 日期；孵妨2 忙 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学位 论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容 编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文 在解密后适用本规定。 学位论文作者签名： 日期：c 昭妇妒 首都师范大学2 0 0 8 年硕士毕业论文 1 i n t r o d u c t i o n c r a m e ra n ds h o u p 【1 】h a v ep r e s e n t e das i g n a t u r es c h e m e f o ra1 0 2 4 - b i tr s a m o d u l u sa n da1 6 0 - b i tm e s s a g e ，as i g n a t u r eh a sa b o u t2 2 0 0b i t s t h es c h e m ei ss e c u r e a g a i n s ta d a p t i v ec h o s e n - m e s s a g ea t t a c ku n d e rt h es t r o n gr s aa s s u m p t i o na n d d o e s n o tr e l yo i lr a n d o mo r a c l em o d e l b ys e c u r i t yw em e a ns e c u r i t ya g a i n s ta na d a p t i v e c h o s e nm e s s a g ea t t a c k ，a sd e f i n e db yc o l d w a s s e re ta 1 【2 c r a m e ra n ds h o u pa d d e d d i s c r e t e - l o ga s s u m p t i o nt ot h ev a r i a t i o no ft h e i rs c h e m ea n dt h e np r o d u c e ds i g n a t u r e s o fr o u g h l yh a f tt h el e n g t h ( a b o u t1 3 5 0b i t s ) m a r cf i s c h l i n 3 】r e v i s i t e dt h e i rs c h e m e a n da c h i e v e dt h es a m es i g n a t u r es i z eu n d e rt h es t r o n gr s aa s s u m p t i o no n l y ，e v e n w i t has l i g h t l yi m p r o v e dp e r f o r m a n c et h a ni nt h eo r i g i n a ls t r o n g - r s ao n l yc a s eo r t h ed i s c r e t e - l o ga n ds t r o n g - r s ac a s e b u tt h es c h e m ew h i c hi si n t r o d u c e db ym a r c f i s c h l i ni n c l u d e sx - o ro p e r a t i o n ，s ot h a tt h es c h e m ei sd i f f i c u l tt ob ea p p l i e dt ot h e v e r i f i a b l es i g n a t u r es h a r i n g ( v e s ) i nt h i sp a p e r ，w es h o was c h e m ew h i c hi sam o d i f i e dv e r s i o no fm a r cf i s c h l i n s s c h e m ef r o m 【3 1 3a n di sa l s ou n d e rt h es t r o n gr s aa s s u m p t i o no n l y o u rs o l u t i o n s c h a n g ear a n d o m - b i ts t r i n go a n d - b i th a s hv a l u ei n t oar a n d o m ( z 一1 ) 一b i ts t r i n gq a n d ( z 一1 ) 一b i th a s hv a l u ea n dr e a r r a n g ear e p r e s e n t a t i o n ( - - 0 f ，一( 口oh ( m ) ) ，y ) b ya r e p r e s e n t a t i o n ( 一q ，一( q + 日( m ) ) ，可) t h el e n g t ho fs i g n a t u r ei no u rs c h e m ei ss i m i l a r t ot h em a r cf i s c h l i n sa n dr o u g h l yh a l f o ft h eo r i g i n a lc r a m e r s h o u ps i g n a t u r es c h m e t h ee f f i c i e n to fo u rs c h e m ec o r r e s p o n d st ot h a to fm a r cf i s c h l i n s i nt h ef o l l o w i n g ，w eb r i e f l yo v e r v i e wt h ed i g i t a ls i g n a t u r ea n dt h ev e r i f i a b l es i g - n a t u r es h a r i n g i ns e c t i o n1a n d2 ，w ew i l li n t r o d u c et h es t a n d a r dd e f i n i t i o no ft h e d i g i t a ls i g n a t u r ea n d t h ev e r i f i a b l es i g n a t u r es h a r i n g t h ec o n c e p to fad i g i t a ls i g n a t u r em a yp r o v et ob et h em o s tf u n d a m e n t a la n d u s e f u li n v e n t i o n so fm o d e r nc r y p t o g r a p h y as i g n a t u r es c h e m ep r o v i d e saw a yf o re a c h u s e rt os i g nm e s s a g e s8 0t h a tt h es i g n a t u r e sc a nl a t e rb ev e r i f i e db ya n y o n ee l s e m o r e s p e c i f i c a l l y ，e a c hu s e rc a nc r e a t eam a t c h e dp a i ro fp r i v a t ea n dp u b l i ck e y ss ot h a to n l y h ec a nc r e a t eas i g n a t u r ef o ram e s s a g e ( u s i n gh i sp r i v a t ek e y ) ，b u ta n y o n e c a l lv e r i f y t h es i g n a t u r ef o rt h em e s s a g e ( u s i n gt h es i g n e r sp u b l i ck e y ) t h ev e r i f i e rc a n c o n v i n c e h i m s e l ft h a tt h em e s s a g ec o n t e n t sh a v en o tb e e na l t e r e ds i n c et h em e s s a g ew a ss i g n e d 2a d i g i t a ls i g n a t u r es c h e m eb a s e do nt h es t r o n gr s aa s s u m p t i o na n di t sa p p l i c a t i o n a l s o ，t h es i g n e rc a nn o tl a t e rr e p u d i a t eh a v i n gs i g n e dt h em e s s a g e ，s i n c er i oo n eb u t t h es i g n e rp o s s e s s e sh i sp r i v a t ek e y t h ec o n c e p to fv e r i f i a b l es i g n a t u r es h a r i n g ( v e s ) w a gi n t r o d u c e db yf r a n k l i n a n dr e i t e r 4 v z se n a b l e st h er e c i p i e n to fad i g i t a ls i g n a t u r e ，w h oi sn o tn e c e s s a r i l y t h eo r i g i n a ls i g n e rt os h a r es u c hs i g n a t u r ea m o n g 死p r o x i e ss ot h a tas u b s e to ft h e m c a nl a t e rr e c o n s t r u c ti t av e s p r o t o c o li sd i v i d e di n t oas h a r i n gp h a s ea n dar e c o v e r p h a s e a tt h ee n do ft h es h a r i n gp h a s ee a c hp r o x yc a i lv e r i f yt h a tav a l i ds i g n a t u r e f o rt h eg i v e nd o c u m e n tc a nb er e c o n s t r u c t e d a tt h ee n do ft h er e c o v e rp h a s es u c h s i g n a t u r ei sr e c o n s t r u c t e dn om a t t e rw h a tam a l i c i o u ss u b s e to fp r o x i e sm a yd o a sw ek n o w n ，t h ev e sf o rr s a ，r a b i n ，e 1 g a m a l ，s c h n o r r ，a n dd s sa r ea l ld i s - c u s s e d b u tt h es o l u t i o n sf o rc r a m e r - s h o u ps e e mm o r ee l u s i v e t h er e a s o no fi tm a y b et h ec o m p l e xo p e r a t i o n so fc r a m e r - s h o u p i nt h i sp a p e r ，w er e v i s i tt h es t r u c t u r eo f c r a m e r s h o u pi no r d e rt om a k ei ts i m p l ea n da p p l yi tt ot h ew i d e ra s p e c t s ，e s p e c i a l l y t ov s 1 o u rn e wp r o t o c o lf o rc r a m e r s h o u ps i g n a t u r es c h e m e i nt h i ss e c t i o n w ew i l lg i v es o m ed e f i n i t i o n sa n da s s u m p t i o n st oo u rp r o t o c 0 1 t h ee n do ft h i ss e c t i o n ，w ew i l ld e s c r i b eo u rp r o t o c o la n dp r o o fo fi t ss e c u r i t y 3 1 - 1 t h er s aa n ds t r o n gr s aa s s u m p t i o n s n o ww er e v i e wt h er s aa n ds t r o n gr s aa s s u m p t i o n si ns o m e w h a tm o r ed e t a i l t h er s ap r o b l e mi st h ef o l l o w i n g ：g i v e nar a n d o m l yg e n e r a t e dr s am o d u l u s n ，ae x p o n e n tr ，a n dar a n d o mz 蜀，f i n dy 舀s u c ht h a ty 7 = z t h er s a a s s u m p t i o ni st h i sp r o b l e mi sh a r dt os o l v e t h es t r o n gr s ap r o b l e mi st h ef o l l o w i n g ：g i v e na nr s am o d u l u sna n da r a n d o mz 蜀，f i n dr la n dy 舀，s u c ht h a ty r = 名t h e s t r o n gr s aa s s u m p t i o n i st h i sp r o b l e mi sh a r dt os o l v e n o t et h a tt h e s ea s s u m p t i o n sa r ed i f f e r e n t ，i nt h a tf o rr s aa s s u m p t i o nt h ee x p o - n e n tri sc h o s e ni n d e p e n d e n t l yo fz ：w h e r e a sf o rt h es t r o n gr s aa s s u m p t i o nrm a y b e c h o s e ni naw a yt h a td e p e n d so nz b a r i da n dp f i t z m a n n 5 】i n t r o d u c e dt h es t r o n gr s aa s s u m p t i o n i th a ss u b s e - q u e n t l yb e e nu s e di nt h ea n a l y s i so fs e v e r a lc r y p t o g r a p h i cs c h e m e s 6 】 【7 】) t h i si sa p o t e n t i a l l ys t r o n g e ra s s u m p t i o nt h a nt h er s aa s s u m p t i o n ，b u ta tt h ep r e s e n tt i m e ，t h e o n l yk n o w nm e t h o df o rb r e a k i n ge i t h e ra s s u m p t i o ni st os o l v et h ei n t e g e rf a c t o r i z a t i o n p r o b l e m 1 2 d e f i n i t i o no fd i g i t a ls i g n a t u r es c h e m e w en o wc o n s i d e rt h ed i g i t a ls i g n a t u r e ，t h ee l e c t r o n i cv e r s i o no fh a n d w r i t t e ns i g - n a t u r e sf o rd i g i t a ld o c u m e n t s ：a sd e s c r i b e di ni n t r o d u c t i o n ，au s e r ss i g n a t u r eo na m e s s a g em i sas t r i n gw h i c hd e p e n d so nm ，o np u b i ca n ds e c r e td a t es p e c i f i ct ot h e u s e ra n dp o s s i b l yo nr a n d o m l yc h o s e nd a t a ，i ns u c haw a yt h a ta n y o n ec a nc h e c kt h e v a l i d i t yo ft h es i g n a t u r eb yu s i n gp u b l i cd a t ao n l y t h eu s e r sp u b l i cd a t aa r ec a l l e d t h ep u b l i ck e y ，w h e r e a sh i ss e c r e td a t aa r ec a l l e dt h es e c r e tk e y o b v i o u s l y , w ew o u l d l i k et op r e v e n tt h ef o r g e r yo fl i a r ss i g n a t u r ew i t h o u tk n o w l e d g eo fh i ss e c r e tk e y i n t h i ss e c t i o n ，w eg i v eam o r es t a n d a r dd e f i n i t i o no fd i g i t a ls i g n a t u r ea n do ft h ep o s s i b l e 4ad i g i t a ls i g n a t u r es c h e m eb a s e do nt h es t r o n gr s aa s s u m p t i o na n di t sa p p f i c a t i o n a t t a c k sa g a i n s tt h e m d e f i n i t i o n1 1 ad i g i t a ls i g n a t u r es c h e m ew i t h i nt h ep u b u ck e yf r a m e w o r k i s d e f i n e da sat r i p l eo fa l g o r i t h m s ( 夕，v ) s u c ht h a t 1 k e yg e n e r a t i o na l g o r i t h m 乡i sap r o b a b i l i s t i c ，p o l y n o m i a l t i m ea l g o r i t h mw h i c h o ni n p u tas e c u r i t yp a r a m e t e rl 七，p r o d u c e sp a i r s ( p s ) w h e r epi sc a l l e dap u b l i ck e y a n dsas e c r e tk e y ( w eu s et h en o t a t i o n ( p s ) ( 9 ( 1 七) ) i n d i c a t e st h a tt h ep a i r ( 只s ) i sp r o d u c e db yt h ea l g o r i t h m9 ) 2 s i g n i n ga l g o r i t h m i sap r o b a b i l i s t i c p o l y n o m i a l t i m ea l g o r i t h mw h i c hi sg i v e n as e c u r i t yp a r a m e t e r1 七，as e c r e tk e ysi nr a n g e 乡( 1 知) a n dam e s s a g em o ，1 ) 知a n d p r o d u c e sa so u t p u ts t r i n g8w h i c hw ec a l lt h es i g n a t u r eo fm ( w eu s en o t a t i o n8 z ( i 七，s ，m ) ，i ft h es i g n i n ga l g o r i t h mi sp r o b a b i l i s t i ca n d8 = ( 1 七，s m ) o t h e r w i s e ，a s as h o r t h a n dw h e nt h ec o n t e x ti sc l e a r ，t h es e c r e tk e ym a yb eo m i t t e da n dw ew i l lw r i t e s ( s ，m ) t om e a nm e a n i n gt h a tsi st h es i g n a t u r eo fm e s s a g em ) 3 v e r i f i c a t i o na l g o r i t h my g i v e nas i g n a t u r es am e s s a g ema n dap u b h ck e y p yt e s t sw h e t h e rsi sav a l i ds i g n a t u r eo fmw i t hr e s p e c tt op i ng e n e r a l t h e v e r i f i c a t i o na l g o r i t h mn e e dn o tb ep r o b a b i l i s t i c 1 3 a t t a c k sa g a i n s td i g i t a ls i g n a t u r e at h e o r e t i c a lt r e a t m e n to fd i g i t a ls i g n a t u r e ss e c u r i t yw a si n i t i a t e db yg o l d w a s s e r ， m i c a l i ，a n dy a oi n 【8 】a n df o l l o w e db y f 9 】，【2 】 【1 0 】， 11 ”w en o wd i s t i n g u i s ht h r e eb a s i c k i n d so fa t t a c k s ，l i s t e db e l o wi nt h eo r d e ro fi n c r e a s i n gs e v e r i t y 1 k e y - o n l ya t t a c k ：i nt h i sa t t a c k ，t h ea d v e r s a r yk n o w so n l yt h ep u b i ck e yo f t h es i g n e ra n dt h e r e f o r eo n l yh a st h ec a p a b i l i t yo fc h e c k i n gt h ev a l i d i t yo fs i g n a t u r e s o fm e s s a g e sg i v e nt oh i m 2 k n o w n - s i g n a t u r ea t t a c k s ：t h ea d v e r s a r yk n o w st h ep u b i ck e yo ft h es i g n e r a n dh a sb e e nm e s s a g e s i g n a t u r ep a i r sc h o s e na n dp r o d u c e db yt h ek g a ls i g n e r i n r e a l i t y t h i si st h em i n i m u ma na d v e r s a r yc a nd o 3 c h o s e nm e s s a g ea t t a c k ：t h ea d v e r s a r yi sa l l o w e dt oa s kt h es i g n e rt os i g n an u m b e ro fm e s s a g e so ft h ea d v e r s a r y sc h o i c e t h ec h o i c eo ft h e s em e s s a g e sm a y d e p e n do np r e v i o u s l yo b t a i n e ds i g n a t u r e s t h i sa t t a c kc o n t a i n st h r e es u b c l a s s e s ：t h e 首都师范大学2 0 0 8 年硕士毕业论文 5 g e n e r i cc h o s e n - m e s s a g ea t t a c k s ，t h eo r i e n t e dc h o s e n - m e s s a g ea t t a c ka n d t h ea d a p t i v e l y c h o s e n m e s s a g ea t t a c k t h el a s to n ei st h em o s ts e r i o u sa t t a c k w en o wc l a s s i f yt h ee x p e c t e dr e s u l t so fa na t t a c k ： 一d i s c l o s i n gt h es e c r e tk e yo ft h es i g n e r ：t h ea d v e r s a r yc a nc o m p u t e rt h es i g n e r s s e c r e tk e y i ti st h em o s ts e r i o u sa t t a c k ，w h i c hi st e r m e dt o t a lb r e a k 一c o n s t r u c t i n ga l le f f i d e n ta l g o r i t h m ：t h ea d v e r s a r ys u c c e e d si nf o r 舀n gt h es i g - n a t u r eo fs o m em e s s a g eo fh i sc h o i c e t h i si sc a l l e du n i v e r s a lf o r g e r y p r o v i d i n gan e wm e s s a g es i g n a t u r ep a i r ：t h ea d v e r s a r yi s a b l et of o r g et h e s i g n a t u r eo fo n em a s s a g en o tn e c e s s a r i l yo fh i sc h o i c e t h i si sc a l l e de x i s t e n t i a lf o r g e r y c l e a r l y , d i f f e r e n tl e v e l so fs e c u r i t ym a yb er e q u i r e do fd i f f e r e n ta p p l i c a t i o n s s o m e - t i m e s ，i tm a ys u f f i c et os h o wt h a ta na d v e r s a r yw h oi sc a p a b l eo fak n o w ns i g n a t u r e a t t a c kc a l ln o ts u c c e e di ns e l e c t i v ef o r g e r y , w h i l ef o ro t h e ra p p l i c a t i o n si tm a yb er e - q u i r e dt h a ta na d v e r s a r yc a p a b l eo fa c h o s e ns i g n a t u r ea t t a c kc a nn o ts u c c e e de v e na t e x i s t e n t i a lf o r g e r yw i t hn o n - n e g l i g i b l ep r o b a b i l i t y i nt h i sp a p e r ，w ec a l las i g n a t u r es c h e m ei ss e c u r ei fa l le x i s t e n t i a lf o r g e r yi s c o m p u t a t i o n a l l yi m p o s s i b l e ，e v e nu n d e ra na d a p t i v e l yc h o s e n - m e s s a g ea t t a c k 1 4 o u rr e v i s i t e dp r o t o c o l i nt h i ss e c t i o n ，w er e c a l lt h eo r i g i n a lc r a m e r s h o u ps i g n a t u r es c h e m ea n dt h e f i s c h l i n 8s i g n a t u r es c h e m e a tt h es a m et i m e ，w ei n t r o d u c eo u rm o d i f i c a t i o na n d p r o v ei tt ob es e c u r e t h e s es c h e m e sa r ep a r a m e t e r i z e db yt w os e c u r i t yp a r a m e t e r sla n d1 7 ，w h e r e1 + 1 l t h e ya l lm a k eu s eo fac o l l i s i o n r e s i s t a n th a s hf u n c t i o n 日，w h o s eo u t p u tc a nb e i n t e r p r e t e d 鹤ap o s i t i v ei n t e g e rl e s st h a n2 。ar e a s o n a b l ec h o i c ef o rhm i g h tb es h a - 1 1 1 2 1 f o rap o s i t i v ei n t e g e rn ，w el e tq 鼬d e n o t et h es u b g r o u po f 蜀o fs q u a r e s 1 4 1o r i g i n a lc r a m e r s h o u ps i g n a t u r es c h e m e t h eo r i g i n a lc r a m e r s h o u ps i g n a t u r es c h e m ew o r k sa sf o l l o w s ： 6a d 礤t a ls i g n a t u r es c h e m eb a s e d0 1 1t h es t r o n gr s aa s s u m p t i o na n di t sa p p l i c a t i o n 1 4 2t h ef i s c h l i n ss i g n a t u r es c h e m e a sd e s c r i b e di ni n t r o d u c t i o nu n d e rt h es t r o n gr s aa s s u m p t i o no n l y , m a r cf i s - c h l i nr e v i s i t e dt h es c h e m eo fc r a m e r - s h o u p t h ef o l l o w i n gi st h es c h e m e 1 4 3o u rr e v i s i t e ds i g n a t u r es c h e m e f r o mt h ea b o v es c h e m e s ，w ew i l lf i n df i s c h l i na s s i m i l a t et h et r a p d o o rc o m m i t - m e n tt ot h er e p r e s e n t a t i o np r o b l e ma sp o i n t e do u ti n 【3 】3o n em a y s p l i tt h em e s s a g e i n t oqa n dq + 日( m ) s oi nt h i sp a p e r ，w ew i l lu s et h i si d e aa n da l s ot u r nt h et r a p d o o r c o m m i t m e n tt ot h er e p r e s e n t a t i o np r o b l e m 。b u tt h er e p r e s e n t a t i o no fo u rs c h e m ei s ( 一q ，一( q + 日( 仇) ) ，暑，) ，w h i c hi sd i f f e r e n tf r o mt h er e