（计算机软件与理论专业论文）新型代理签名方案的设计、分析及其实现.pdf

上海交通大学博士学位论文新型代理签名方案的设计、分析及其实现摘要 新型代理签名方案的设计、分析及其实现 摘要 在信息大爆炸的知识经济时代，如何解决数字签名的授权以及数字信息的安全 传递成为当前需要迫切解决的问题，代理签名是解决这类问题的一种最有效和最具 潜力的技术，同时，它又是一个多学科交叉的技术，这给研究工作带来一定的难度 和挑战。斟此，无论在理论上还是应用上，开展代理签名技术的研究，不仅具有重 要的学术价值，而且还对国家安全和信息化建设具有极为重要的意义。 1 9 9 6 年，m a m b o ，u s u d a 和o k a m o t o 提出了代理签名的概念。在这种签名中， 一个被指定的代理签名者能够代表原始签名者生成有效的签名。同时，m a m b o 等 人还给出了代理签名方案应满足不可否认性、可验证性、不可伪造性、可区分性等 六条性质。 由于代理签名在现实中有着重要的应用前景，所以一被提出便受到国内外学者 的广泛关注，并对其进行了深入的探讨与研究。迄今为止，人们已提出了多种类型 的代理签名方案。m a m b o ，u s u d a 和o k a m o t o 把代理签名分为完全代理签名、部 分代理签名和具有授权证书的代理签名三大类。l e e ，k i r n 和k i m 根据不可否认性 把代理签名分为强代理签名和弱代理签名。根据是否指定代理签名者把代理签名分 为指定代理签名和非指定代理签名。他们也考虑了自代理签名，也就是，原始签名 者为自己生成一个代理密钥对，即原始签名者和代理签名者为同一方。伊丽江，白 国强和肖国镇与祁明，h a m 分别提出了代理多重签名类型。h w a n g 和s h i 提出了 多重代理签名类型并设计了一个方案。最近，h w a n g 和c h e n 扩展了代理多重签名 和多重代理签名提出了多重代理多重签名类型并给出了一个具体的方案。 本文对代理签名方案研究的的创新点主要如下： 第一，我们指出h w a n g 和c h e n 提出的多重代理多重签名方案，不能抵抗来自 任何人的伪造攻击。为克服这种缺点，在原方案的基础上，我们提出了一个改进的 方案，并且。 析了其安全性。基于h s u 等人的自验证公钥系统和l i 等人的代理签 名模型，我们提出了一个使用自验证公钥系统的门限代理签名方案。该方案的主要 优点是原始签名者和代理签名者公钥的验证和代理签名的验证能够在一个步骤中 被同时执行。而且，方案能够提供多种安全属性，诸如代理保护、可验证性、强可 识别性、强不可伪造性、强不可否认性、可区分性、可确定实际的代理签名者和代 理签名权的滥用阻止等。就是说，内部攻击、外部攻击、合谋攻击和公钥替换攻击 等能够被有效地抵制。另外，根据所需的计算量和通信量，该方案比以前的使用 s h a m i r 的秘密共享协议和基于证书的公钥系统的门限代理签名方案更有效。 第二，当前，几乎所有的门限代理签名方案都是基于乘法群z ：( 多为大素数) 上的离寸数问题。在所有已提出的方案中，总是存在这样或那样的问题，使得方 案不够安和有效。为了抵制已经发现的弱点，基于乘法群上离散对数问题的门限 上海交通大学博士学位论文新型代理签名方案的设计、分析及其实现摘要 代理签名方案变得越来越复杂，越来越消耗更多的计算量和通信量。双线性对，又 称代数曲线w e i l 对和 f a t e 对，是代数几何研究中一个很重要的工具。它们在密码 学中的应用可以追溯到v i c t o rm i l l e r1 9 8 6 的未出版的论文，特别是 m e n e z e s o k a m o t o v a n s t o n e 和f r e y r i l c k 的研究结果。双线性对有很多优点，如签 名较短等。基于此，我们设计了一个基于双线性对的门限代理签名方案，并对方案 的安全性进行了分析。 第三，基于h s u 等人的自验证公钥系统和h w a n g 等人的代理签名方案，我们 提出了一个基于椭圆曲线群上离散对数问题的门限代理签名方案。该方案的优点是 原始签名者和代理签名者的公钥的验证和代理签名的验证在一个步骤中被同时执 行，并且也提供了很好的安全特性。 第四，针对大多数门限代理签名方案都是基于离散对数问题，h w a n g 等人提 出了一个基于r s a 密码体制的( f ，月) 门限代理签名方案。通过分析，我们发现，他 们的方案不能够提供代理保护、强不可伪造性、强可识别性和确定实际的代理签名 者等属性。为了使方案更安全实用，基于h w a n g 等人的方案，我们提出了一个改 进的方案。改进的方案不仅能够提供代理保护、强不可伪造性、强可识别性和确定 实际的代理签名者等安全属性，而且还保留了原方案的优点。基于s h a o 的方案， 我们建立了一个基于r s a 密码体制的代理签名方案的通用模型，并且分析了其安 全性和执行效率。基于c a o 改进的r s a 密码体制，我们提出了一个普通的代理签 名方案和一个多重代理签名方案，同时，也分析和讨论了其安全性及执行效率。 最后，介绍了公钥基础设施p k i ，提出了代理签名系统模型，根据该模型设计 了代理签名系统并阐述了各个部分的功能，在w i n d o w s2 0 0 0 操作系统下，使用 v i s u a lc + + 在交换式局域网环境下实现了一种门限代理签名方案。 关键词密码学，数字签名，代理签名，双线性对，因子分解，建模 l i 上海交通大学博士学位论文新型代理签名方案的设计、分析及其实现a b s t r a c t d e s i g n 。c r y p 7 r a n a l y s i sa n di 田l e n 姬n t a t i o no f n o v e lp r o x ys i g n a t u r es c h e m e s a b s t r a c t i nt h ee r ao fk n o w l e d g ee c o n o m ya n di n f o i t n a t i o ne x p l o s i o n h o wt od e l e g a t et h e s i g n i n gp o w e ra n ds e c u r e l yt r a n s f e ri n f o r m a t i o ni si ng r e a tn e e do fs o l v i n g t h ep r o x y s i g n a t u r ei so n eo ft h em o s te f f i c i e n ta n dp o t e n t i a lt e c h n i q u e s ，m e a n w h i l e ，i ti so n ek i n d o ft e e h n i q u ew i t hm u l t i p l ek n o w l e d g e ，a sb r i n g ss o m ed i f f i c u l t i e sa n dc h a l l e n g e st o r e s e a r c h e r s t h e r e f o r e ，f r o mt h ev i e wo ft h e o r ya n da p p l i c a t i o n s ，t or e s e a r c ht h ep r o x y s i g n a t u r ei so fg r e a ti m p o r t a n c ea n dp l a y sa ni m p o r t a n tr o l ei nn a t i o n a ls e c u r i t ya n d i n f o r m a t i o nc o n s t r u c t i o n i n19 9 6 ，m a m b o ，u s u d aa n do k a m o t op r o p o s e dt h ec o n c e p to ft h ep r o x ys i g n a t u r e ， i nw h i c had e s i g n a t e dp r o x ys i g n e rc a nc r e a t ev a l i ds i g n a t u r e so nm e s s a g e so ub e h a l lo f t h eo r i g i n a ls i g n e r t og u a r a n t e ei t ss e c u r i t y , t h e ya l s op o i n t e do u tt h a tp r o x ys i g n a t u r e s c h e m e ss h o u l ds a t i s f yt h es e c u r ep r o p e r t i e so f u n d e n i a b i l i t y , v e r i f i a b i l i t y 。u n f o r g e a b i l i t y i n d i s t i n g u i s h a b i l i t ya n ds of o r t h b e c a u s et h ep r o x ys i g n a t u r eh a sm a n yi m p o r t a n ta p p l i c a t i o n si nt h ef u t u r ei nt h er e a l 1 i f e s i n c ei tw a sp r o p o s e d h o m ea n do v e r s e a ss c h o l a r sh a v ep a i dm u c ha t t e n t i o nt oi t a n dc a r r i e do u td e e pr e s e a r c h u n t i ln o w ，m a n yk i r i d so fp r o x ys i g n a t u r es c h e m e sh a v e b e e ni n v e n t e d ，m a m o ，u s u d aa n d0 k a m o t og a v et h r e es o r t so f p r o x ys i g n a t u r es c h e m e s ， i e ，f u l ld e l e g a t i o np r o x ys i g n a t u r e ，p a r t i a ld e l e g a t i o np r o x ys i g n a t u r ea n dp r o x y s i g n a t u r ew i t hw a r r a n t a c c o r d i n gt ou n d e n i a b i l i t y , l e e ，k i ma n dk i mp r o p o s e ds t r o n g p r o x ys i g n a t u r ea n dw e a kp r o x ys i g n a t u r e b a s e d o nw h e t h e rt h ep r o x ys i g n e ri s d e s i g n a t e d ，t h e yg a v ep r o x y - d e s i g n a t e dp r o x ys i g n a t u r ea n dp r o x y u n d e s i g n a t e dp r o x y s i g n a t u r ea l s o ，t h e yt h o u g h ta b o u ts e l f - p r o x yp r o x ys i g n a t u r e ，w h e r et h eo r i g i n a ls i g n e r p r o d u c e sap r o x yk e yp a i rf o rh i m s e l fo rh e r s e l f , i e ，t h eo r i g i n a ls i g n e ra n d t h ep r o x y s i g n e ra r et h es a m ep a r t y y i ，b a ia n dx i a o ，a n dq i a n dh a mp r o p o s e dp r o x y m u l t i s i g n a t u r er e s p e c t i v e l y h w a n ga n ds h ig a v em u l t i p r o x ys i g n a t u r e r e c e n t l y , h w a n ga n d c h e ne x p e n d e dp r o x ym u l t i s i g n a t u r ea n dm u l t i - p r o x ys i g n a t u r ea n d d e s i g n e dam u l t i - p r o x ym u l t i s i g n a t u r es c h e m e t h eo r i g i n a l i t yo f t h ep a d e ri ss t a t e di nt h ef o l l o w i n g ： f i r s t ，b yo b s e r v a t i o n ，w ef o u n dt h a th w a n g e ta 1 ss c h e m ec a r l tr e s i s tt h ef o r g e r y a t t a c kf r o ma n yp a r t y t oo v e r c o m et h ed r a w b a c k ，b a s e do nh w a n ge ta 1 ss c h e m e ，a n i m p r o v e ds c h e m ei sp r o p o s e da n di t ss e c u r i t yi sa n a l y z e d b a s e do nh s ue ta 1 ss o l f c e r t i f i c a t e dp u b l i cs y s t e ma n dl ie ta 1 sp r o x ys i g n a t u r em o d e l ，w ep u tf o r w a r do n e t h r e s h o l dp r o x ys i g n a t u r es c h e m e t h ea d v a n t a g e so ft h es c h e m ea r e t h a tt h e v e r i f i c a t i o no fp u b l i ck e y so fo r i g i n a la n dp r o x ys i g n e r sa n dt h ev e r i f i c a t i o no fp r o x y s i g n a t u r e sc a r lb es i m u l t a n e o u s l yp e r f o r m e di no n es t e p i na d d i t i o n ，t h es c h e m ec a r l 1 1 1 上海交通大学博士学位论文 新型代理签名方案的设计、分析及其实现 a b s t r a c t p r o v i d e l o t so fs e c u r e p r o p e r t i e s s u c ha s p r o x yp r o t e c t i o n ，v e r i f i a b i l i t y , s t r o n g i d e n t i f i a b i l i t y , s t r o n gu n d e n i a b i l i t y , d i s t i n g u i s h a b i l i t y , k n o w np r o x ys i g n e r sa n d p r e v e n t i o no fm i s u s eo fp r o x ys i g n i n gp o w e r , i e i n t e m a la t t a c k s ，e x t e r i o ra t t a c k s c o l l u s i o na t t a c k sa n dp u b l i ck e ys u b s t i t u t i o na t t a c k sc a nb ee f f i c i e n t l yr e s i s t e d b e s i d e s ， a c c o r d i n gt oc o m p u t a t i o nc o s ta n dc o m m u n i c a t i o no v e r h e a d ，t h es c h e m ei sm o r e e 蚯c i e n tt h a nt h o s ew i t hs h a m i r ss e c r e ts h a r ep r o t o c o la n dp u b l i ck e ys y s t e m sw i t h c e r t i f i c a t e s s e c o n d ，c u r r e n t l y , a l lo ft h r e s h o l dp r o x ys i g n a t u r es c h e m e sa r eb a s e do nd i s c r e t e l o g a r i t h mp r o b l e m si nm u l t i p l yg r o u pz ：pi sal a r g ep r i m e ) i na l lo fp r o p o s e d s c h e m e s ，t h e r ea r ea l w a y ss o m ed i s a d v a n t a g e s ，w h i c hm a k es c h e m e si n s e c u r ea n d i d e f f i c i e n t t oe r a s et h ef o u n dw e a k n e s s e s ，d e s i g n e ds c h e m e sb a s e do nd i s c r e t e l o g a r i t h mp r o b l e m si nm u l t i p l yg r o u p sb e c o m em o r ea n dm o r ec o m p l e xa n dc o s tm o r e c o m p u t a t i o na n dc o m m u n i c a t i o no v e r h e a d b i l i n e a rp a i r i n g s ，n a m e l yw e i lp a i r i n g sa n d t a t ep a i r i n g s ，a r eo n er a t h e ri m p o r t a n tt o o li na l g e b r ag e o m e t r y i t sa p p l i c a t i o n si n c r y p t o g r a p h y c a nb a c kt om t i l e r s u n p u b l i s h e dp a p e r i n19 8 6 ，e s p e c i a l l y m e n e z e s o k a m o t o v a n s t o n e sa n df r e y - r n c k sr e s e a r c hr e s u l t s b i l i n e a rp a i r i n g sh a v e l o t so fm e r i t ss u c ha ss h o r ts i g n a t u r e s t h e r e f o r e ，w ed e s i g no n eb i l i n e a r p a i r i n gb a s e d t h r e s h o l dp r o x ys i g n a t u r es c h e m ea n da n a l y z ei t ss e c u r i t y t l l i r d b a s e do nh s ue ta 1 ss e l f - c e n i f i c a t e dp u b l i ck e ys y s t e ma n dh w a n ge ta 1 s p r o x ys i g n a t u r es c h e m e ，o n et h r e s h o l dp r o x ys i g n a t u r es c h e m ew h i c hi s b a s e d0 n d i s t c l e t el o g a r i t h m so v e re l l i p t i c a lc m v eg r o u pi sp r o p o s e d t h em e r i to ft h es c h e m ei s t h a fb o t hv e r i f i c a t i o no fp u b l i ck e y so fo r i g i n a la n dp r o x ys i g n e r sa n dv e r i f i c a t i o no f p r o x ys i g n a t u r e sa r es i m u l t a n e o u s l yp e r f o r m e di no n es t e pa n di tc a np r o v i d eb e t t e r s e c u r i t y f o r t h ，b e c a u s em o s tt h r e s h o l dp r o x ys i g n a t u r es c h e m e sa r eb a s e do nd i s c r e t e l o g a r i t h mp r o b l e m s ，r e c e n t l y , h w a n g e ta 1 d e s i g n e do n e 0 ，n ) t h r e s h o l dp r o x y s i g n a t u r es c h e m eb a s e do nr s a b yo b s e r v a t i o n ，w ef i n dt h a tt h e i rs c h e m ec a nn o t p r o v i d et h ep r o p e r t i e so fp r o x yp r o t e c t i o n ，s 2 0 n gu n f o r g e a b i l i t y , s t r o n gi d e n t i f i a b i l i t y a n dk n o w np r o x ys i g n e r s b a s e do nh w a n ge ta l ，ss c h e m e a ni m p r o v e ds c h e m ei s p r o p o s e d t h ei m p r o v e ds c h e m ei sm o r es e c u r ea n di e t a i n st h ea d v a n t a g e so fh w a n g e t a 1 ss c h e m e b a s e do ns h a o ss c h e m e o n ep r o x ys i g n a t u r em o d e l i sp u tf o r w a r da n d d i s c u s s e do ni t ss e c u r i t ya n de 伍c i e n c y b a s e do nc a o si m p r o v e dr s ac r y p t o s y s t e m ， o n en o r m a lp r o x ys i g n a t u r es c h e m ea n do n em u l t i - p r o x ys i g n a t u r es c h e m ea r eb r o u g h t f o - r w a r da n da n a l y z e dt oi t ss e c u r i t ya n de m c i e n c y f i n a l l y , p u b l i ck e yi n f r a s t r u c t u r e ( p k i ) i si n t r o d u c e da n do n ep r o x ys i g n a t u r em o d e l i sg i v e n o nt h eb a s i so ft h em o d e l ，o n ep r o x ys i g n a t u r es y s t e mi sd e s i g n e da n dd e t a i l e d o nt h ef u n c t i o no fi t sc o m p o n e n t s u n d e rw i n d o w s2 0 0 0 ，o n et h r e s h o l dp r o x ys i g n a t u r e s c h e m ei si m p l e m e n t e du s i n gv i s u a lc + + i ns w i t c hl o c a la r e an e t w o r k s k e yw o r d s ：c r y p t o g r a p h y , d i g i t a ls i g n a t u r e ，p r o x ys i g n a t u r e ，b i l i n e a r p a i r i n g ，f a c t o r i n g ，m o d e l i n g 上海交通大学学位论文答辩决议书 i 申请者i 薛庆水0 所在学科( 专业) j |计算机软件与理论 l l 论文题目新型代理签名方案的设计、分析及其实现 i 答辩日期 2 0 0 5 - 0 6 - 0 6 0 答辩地点 9 上海交通大学2 0 徐0 6 汇校区新建楼l l 答辩委员会成员。 l 担任职务0 姓名i l 职称0 所在工作单位 i l 备注 l l 签名 i 委员0 陈克非l l 教授0 上海交通大学 一 fl 飘4 蚕取 0 ，( g ，m ) = 1 ，如果整数g 对m 的次数为妒伽) ，则g 叫做聊 的一个原根。 定理2 2 模m 存在原根的充分必要条件是m = 2 ，4 ，p 。或2 p ，这里p 是奇素数， 2 上海交通大学博士学位论文新型代理签名方案的设计、分析及其实现第二章密码学基础 联壬正整数。 定理2 - 3 设搠有一个原根g ，则m 恰有妒( 妒( 掰) ) 个对模牌不同余的原根，它们 由集合 s = ( g l l 蔓f q , c m ) ，p ，妒( ，”) ) = 1 ) 中的数给出。 定理2 - 4 设r t 2 ，妒( 研) 的所有不同的素因子是q 】，q 2 ，吼，( g ，m ) = 1 ，则g 是 m 的一个原根的充分必要条件是 趔 g “1 m o d m ( i = 1 , 2 ，5 ) a 定理2 5 设a 对模奇素数p 的次数是d ，d 1 是一个正整数，对于多项式 f c x ) = a n x ”+ a n _ i x ”叫+ + a t x + 口o ，a 。z ( i = o ，1 ，一，以) 如果0 m o d m ，则称f c x ) ；0 m o d m 为n 次同余式。最简单的是一次同余式 鲥e b m o d m ，a 0 m o d m( 2 一1 ) 定理2 - 6 同余式( 2 1 ) 有解的充要条件是( 玎，m ) lb ，并且如果( 2 1 ) 有解，则必有 ( d ，肌) 个解。 由定理2 - 6 知研究同余式( 2 1 ) ，只要研究( 口，m ) = 1 的情形就可以了，所以一次 同余式组不妨设为 x 5 q m o d m ，( i = 1 ，s ；s 1 ) ( 2 2 ) 其中( 肌，m ，) = 1 ( i ，) 定理2 7 ( 孙子定理) 设m l ，一，m ，是s 个两两互素的正整数( 即 ( m ：，朋，) = 1 ，( f 劝，m = m l m ，= m ，m i ( f _ l ，s ) ，则同余式组( 2 - 2 ) 对模掰有唯 一解 x = 叫m l a t + + 帆m , a ，m o d m 其中m ；满足m m ，s l r o o d m ，( i = l ，s ) 。 定义2 5 设信息源的输出符号取值于一离散集合a = “。，d ：，a 。) ，其中口。出 现的概率记为p ( a 。) ( f _ 1 ，n ) ，且p ( d ) = 1 。对v a a ，以，( 口) 记符号口的信息 量，通常定义 ，( 口) = 一l o g p ( d ) 这罩对数的底通常是2 ，相应的信息量的单位是比特( b i t ) 。 定义2 - 6 用随机变量x 表示a 上的信源，用各个符号信息量的平均值 日( x ) = 一p ( a 。) l o g p ( a ，) 上海交通大学博士学位论文新型代理签名方案的设计、分析及其实现第二章密码学基础 来度量信源x 的不确定性，并将h ( x ) 称为该信源的熵，也称h ( x ) 为信源x 的熵函 数。显然，当p ( a ，) 均相等时，h ( x ) 达到最大值，此时p ( q ) = ( i = 1 , 2 ，”) 且 m a x h ( x ) = 一三l o g 二= l o g n j i 肝 力 当某个p ( a ) = 1 时，h ( x ) 达到最小值r a i n h ( x ) = 0 。因此，熵函数满足 0 h ( x 、l o g n 。 定义2 - 7 设随机变量y 取值于一离散集合占= 6 。，6 ：，b 。 ，且呈p ( 包) ：1 。令 p ( x i y ) 表示对于给定y 后，随机变量x 的条件概率，并用p ( x ，y ) 表示对于给定x ，y 后的联合概率。根据概率的乘法原理，有p ( x ，y ) = p ( xfy ) p ( y ) 。h ( x y ) 为给定 y 后x 的条件熵，其定义是 h ( xy ) = 一2 1 ：p ( x ，y ) l o g p ( xy ) j ，y 其中和号y 表示对所有x a ，_ y e b 求和。 ， 定义2 - 8 记z ，y 的联合熵为h ( x ，y ) ，其定义为 h ( x ，y ) = 一p ( x ，y ) l o g p ( x ，_ y ) j ， 则直接验证有 h ( x ，y ) = h ( x ) + h ( y ix ) = h ( y ) 十h ( x l y ) 并且h ( x iy ) 妄h ( x ) ，h ( y lx ) 日( y ) 。 显然，如果x ，y 是互相独立的两个事件，则h ( x ，y ) = h ( x ) + h ( y ) ，如果事件y 完 全被事件x 所确定，则h ( x ，y ) = h ( x ) 。 2 2数据加密系统 根据不同密钥类型将数据加密系统分为两大类：一类是单密钥加密( 又称秘密 钥或对称加密) 系统另一类是双密钥加密( 又称公开密钥或非对称加密) 系统。 2 2 1 单密钥密码系统 在这种系统中，加密和解密均采用同一把秘密钥，而且通信双方都必须获得这 个秘密钥，并且对它保密。 单密钥系统的安全性依赖于两个因素。其一，加密算法必须是足够强的，仅仅 根据密文本身去解密信息在实践上是不可能的：其二，加密方法的安全性依赖于密 钥的保密程度，而不是算法的秘密性，所以，没有必要确保算法的秘密性，需要保 证密钥的秘密性。单密钥系统的算法执行速度极快，从a e s 9 3 - 9 5 1 候选算法的测试 结果看，软件实现的速度都达到了每秒数兆或数十兆比特。单密钥系统的这些特点 使其有着广泛的应用。 4 上海交通大学博士学位论文新型代理签名方案的设计、分析及其实现第二章密码学基础 单密钥系统最大的问题是密钥的分发和管理非常复杂、代价高昂。比如，对于 拥有”个用户的网络，则需要n ( n 一1 坨个密钥。在用户群不是很大的情况下，单 密钥系统是有效的。对于大型网络，当用户群很大，分布很广时，密钥的分配和保 存就成了大问题。单密钥算法另一个缺点是不能实现数字签名。 单密钥系统最著名的是美国数据加密标准d e s 9 、a e s l 9 3 - 9 5 ( 高级加密标准) 和欧洲数据加密标准i d e a t 9 ”。1 9 7 7 年，美国国家标准局正式公布了美国的数据加 密标准d e s ，公开它的加密算法，并批准用于非机密单位和商业上的秘密通信。 之后，d e s 成为全世界使用最广泛的加密标准。在d e s 中，加密与解密的密钥和 流程是完全相同的，区别仅在于加密与解密使用的子密钥序列的施加顺序相反。经 过2 0 多年的使用，已经发现d e s 有很多缺点【3 4 t 9 ，对d e s 的破解方法也日趋有 效。a e s 将会替代d e s 成为新一代单密钥加密标准。 2 2 2 双密钥密码系统 1 9 7 6 年，美国斯坦福大学的d i f i l e 与h e l l m a n 【9 驯在“密码学的新方向文中提 出了公开密钥密码系统p k c ( p u b l i ck e yc r y p t o s y s t e m ) 的新概念，开创了现代密码 学的新领域。d i f f i e 和h e l l m a n 提出的公开密钥密码系统解决了单密钥系统中密钥 的分发和管理非常复杂这一难题，公开密钥加密系统采用的加密密钥( 公钥) 和解密 密钥( 私钥) 是不同的。由于加密密钥是公开的，密钥的分配和管理就比较简单。例 如，对于拥有聆个用户的网络，仅需要2 个密钥。公开密钥加密系统还能够很容 易地实现数字签名。因此，非常适合于电子商务应用需要。图2 1 是一般公钥密码 系统图示，其中加、解密变换e 。，d 。需满足下面三个条件： ( 1 ) d 。是e 。的逆变换，即v m m ( 明文空间) ，均有 d 口0 ) = 玩( 口( 删) ) = m ( 2 ) 在已知b 的公开钥与秘密钥的条件下，e 。与d 。均是多项式时间的确定算 法。 ( 3 ) 对v m m ，找到算法d ；，使得珑( e b ( 坍) ) = m 是非常困难的。这里非常 困难是指在现有的资源与算法下，寻找d ：是不现实的。 满足( 1 ) ，( 3 ) 的定义在正整数集z 、。上的数论函数e 。 x ) 称为陷门单向函数。 图2 - 1 双密钥密码系统 f i g u r e2 - 1d o u b l ek e yc r y p t o s y s t e m 上海交通大学博士学位论文新型代理签名方案的设计、分析及其实现第二章密码学基础 所以，设计p k c 就变成寻找陷门单向函数。通常选择n p 问题或n p c 问题作 为构造p k c 的数学基础。 在实际应用中，双密钥加密系统并没有完全取代对称密钥加密系统，是因为公 开密钥加密系统是基于数学难题，计算非常复杂，它的安全性更高，但在实现速度 上，却远不如单密钥加密系统。在实际应用中，可利用二者的优点，采用单密钥加 密系统加密文件，用双密钥加密系统加密会话密钥，即“加密文件”的密钥，也就是 所谓的混合加密系统，较好地解决了运算速度问题和密钥分配管理问题。所以，双 密钥密码体制通常被用来加密关键性的、核心的机密数据，而单密钥密码体制通常 被用来加密大量的数据。 自从双密钥加密被提出以来，学者们提出了许多种公钥加密方法，它们的安全 性都是基于复杂的数学难题。目前，根据所使用的数学难题来分类，有三类双密钥 系统被认为是安全和有效的，它们是大整数因子分解系统( 如r s a ) 、离散对数系统 ( 如e 1 g a m a l ) _ 手e l 椭园曲线离散对数系统( e c o 。 ( 一) r s a 公钥密码系统 整数分解问题可描述为给定正整数行，如何求其素因子，即如何把1 表示成 n = 聍p 醪，其中既为互素的整数，且p 。1 。整数分解问题是一个著名的n p 问题，求解它的已知较快的确定算法是m o r r i s o n 与b f i l l h a r t l 9 3 】得到的，但仍需要进 行o ( e x p f f l o g n l o g ( 1 0 9 n ) 次算术运算。目前世界上最快的整数分解算法是波拉德 ( j p o l l a r d ) 1 1 岳8 】首创的数域筛法( n f s ) 。数域筛法的计算复杂性为 o ( e x p ( c “8 叫3 ( 1 0 9 l o g n ) “) ) ，其中c 为一实常数且l c 2 。基于大整数分解问题的 最著名的公钥密码体制是19 7 8 年由r i v e s t ，s h a m i r 和a d l e m a n 9 9 1 提出的r s a 体制。 令p 和q 是随机选取的两个大素数( 大约为十进制1 0 0 位或更大) ，h = p q 是公 开的，而p ，口是保密的。如果知道月的分解，就能计算出欧拉函数 ( h ) = ( p 一1 ) ( g 一1 ) 。随机选取一个数p ，e 为小于( n ) 且与它互素的正整数。利用辗 转相除法，可以找到整数d ，使 e d ；l m o d ( n ) ，l d o ( n ) ( 2 - 3 ) 将月，p 公开做加密密钥，而d 严格保密做解密密钥( p ，g ，( 月) 均需保密) 。 设明文空间m = 加i0 坍 n ，则可将聊分成若 干个明文段m ，( i = 1 ，s ) ，使每段m 。 l 时，因为0 m 月及n = p q ，故( m ，”) = p 或q ， 不妨设( 研，h ) = p ，所以，目) = 1 ，因此 c 4 三m 耐= 聊( m q 一1 ) 耐1 9 一三m m o d q 一；m “；m m o d p 由此，可得c 4 ；m ( m o d p q ) ，即f 2 。5 ) 成立。 之后，先后出现了对这一体制在不同范畴的各种模拟，例如，孙琦【m 0 1 ，曹珍 富【1 0 l 】，b u c h m a n n 和w i l l i a m s 10 2 】等人考虑了r s a 在代数整环中的模拟，特别是在 e i s e n s t e i n 环z o 】和一般的二次域中的模拟。这种模拟无疑是对现代密码学的新贡 献。 另一方面，对r s a 的攻击也出现了许多重要工作，特别是小指数的安全性讨 论【1 0 3 】。一种是小私钥指数的攻击，主要是w i e n e r 1 删的攻击及b o n e h 和d u r f e e 1 0 5 j 的改进。另一种是小公钥指数的c o p p e r s m i t h 1 06 】攻击和h a s t a d 1 07 】对广播通信的攻 击。文献 1 0 3 也给出了对抗这些攻击的些措施。b o n e h 和v e n k a t e s a n f ”驯指出破 译小指数r s a 不等价于分解大整数。他们表明从分解到破译小指数r s a 的代数规 约能被转化为有效的分解算法。 近来，曹珍富对r s a 的改进作出了卓有成效的工作。他f 1 0 9 峙旨出有限域尼上 多项式r s a 是不安全的，并给出了r s a 在z 。中的两个新模拟。他 1 ”】给出的r s a 圆锥曲线模拟能对抗小公钥指数攻击。饱【“】提出的多维r s a 特别适合长明文的加 密和签名。并且多维r s a 能有效地对抗小指数攻击，特别是小公钥指数的攻击。 该体制的安全性主要基于大整数分解，它是r s a 体制的一个有力推广和改进。他 u 2 1 还提出了一种安全性等价于大整数分解而密文又没有扩展的公钥密码系统，该 系统可用于数字签名，并且应用到密钥托管中。 r s a 系统是公钥系统中最具有典型意义的方法，大多数使用公钥密码进行加 密和数字签名的产品和标准使用的都是r s a 算法。 r s a 方法的优点主要在于原理简单，易于使用。但是，随着分解大整数方法 的进步及完善、计算机速度的提高以及计算机网络的发展，作为r s a 加解密安全 保障的大整数要求越来越大。为了保证r s a 使用的安全性，其密钥的位数一直在 增加，比如，目前一般认为r s a 需要1 0 2 4 位以上的字长才有安全保障。但是，密 钥长度的增加导致了其加解密的速度大为降低，硬件实现也变得越来越难以忍受， 这对使用r s a 的应用带来了很重的负担，对进行大量安全交易的电子商务更是如 此