（应用数学专业论文）代理签名方案设计与分析.pdf

代理签名方案设计与分析 王天银 摘要随着计算机通信网的迅速发展，人们希望通过电子设备实现快速、远距 离的交易，数字签名应运而生，并开始应用于现实社会中。数字签名已经在信息 安全、身份认证、数据完整性、不可否认性以及匿名性等方面发挥了重要作用。 代理数字签名作为一种特殊的数字签名体制，可以实现普通数字签名无法解决的 代理问题。代理数字签名的这种特殊性质使得它可以广泛应用于电子选举、移动 通信、移动代理、电子商务等领域。自从1 9 9 6 年m a m b o 、u s u d a 和o k a m o t o 首次 提出代理数字签名橛念以来，人们己提出了多种代理数字签名方案，如代理多重 数字签名方案、门限代理数字签名方案以及盲代理数字签名方案等，代理数字签 名的研究取得了丰硕的成果。然而，已提出的大多数代理数字签名方案在安全性、 效率以及可行性等方面仍不够理想。因此设计安全、高效、可行的代理数字签名 方案具有重要的现实意义。本文在这方面进行了一些有益的尝试和探索。 本文第一章为绪论，首先对代理数字签名的产生背景、现实意义和发展状况进 行了介绍，第二章介绍了一些必要的相关数学和密码学知识，最后三章为本文核 心部分，对已提出的几种典型的代理数字签名方案进行了分析，并提出了一些新 的代理数字签名方案。 本文所取得的主要研究成果如下： 1 对两个门限代理数字签名方案进行了分析。证明了q c z 方案不能抵抗 伪造攻击和公钥替换攻击，r 一日一y 方案不能抵抗原始签名人的伪造攻击，并分 别对这两个方案进行了改进，改进后的方案可以抵抗所提出的攻击。提出了一种 新的具有已知签名者的不可否认门限代理数字签名方案，新方案具有计算量小、 通信量低、安全性高等优点。 2 对两个代理盲数字签名方案进行了分析，证明了r l 一丁方案和l a 方案 不能抵抗伪造攻击和不具有不可链接性。提出了两种新的代理盲数字签名方案， 新方案满足代理盲数字签名方案的安全性要求。 3 对一个前向安全的强代理数字签名方案进行了分析，证明了丁一l 方案不具 有前向安全性。并分别基于g u i l l o u a u 括q u t e r 签名体制和s c h n o r r 签名体制，提出 了两种新的前向安全的代理数字签名方案。 关键词：数字签名；代理数字签名：门限代理数字签名；代理盲数字签名；前 向安全 d e s i g n a n d a n a l y s i s o f p r o x ys i g n a t u r e s c h e m e w a n gt i a n y i n a b s t r a c tw i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rc o m m u n i c a t i o nn e t w o r k ，i ti s d e e p l yh o p e d t h a tp e o p l ec a nf i n i s ht h e i rt r a d i n ga c t i v i t i e sq u i c k l yi nt h ed i s t a n c eb yt h e m e a n so fe l e c t r o n i ca p p a r a t u s a sar e s u l t ，d i g i t a ls i g n a t u r ec a m ei n t ob e i n gw h i c hi s w i d e l yu s e di ns o c i e t y d i g i t a ls i g n a t u r eh a sb e e np l a y i n gav e r yi m p o r t a n tr o l ei nt h e f i e l d so fi n f o r m a t i o ns e c u r i t y , i d e n t i t ya u t h e n t i c a t i o n ，d a t ai n t o ；鲥t y , n o n r e p u d i a t i o na n d a n o n y m i t y , e t c a sas p e c i a ld i g i t a ls i g n a t u r es c h e m e ，p r o x yd i g i t a ls i g n a t u r ec a ns e t t l e s o m ep r o x yp r o b l e m sw h i c ho t h e rn o r m a l d i g i t a is i g n a t u r e s c h e m e sc a l u l ts o l v e b e c a u s eo ft h i s p a r t i c u l a r i t y , p r o x yd i g i t a ls i g n a t u r e c a l lb ew i d e l ya p p l i e dt om a n y f i e l d s ，s u c ha se - e l e c t i o n ，m o b i l ec o m m u n i c a t i o n ，m o b i l ea g e n t ，e - c o m m e r c ea c t i v i t i e s a n ds oo n s i n c et h ey e a ro f1 9 9 6w h e nm a m b o ，u s u d aa n do k a m o t o f i r s t l ya d v a n c e d t h ec o n c e p to f p r o x ys i g n a t u r e ，m a n yp r o x ys i g n a t u r es c h e m e s h a v e b e e nr a i s e d ，s u c ha s 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 r e s h o l dp r o x ys i g n a t u r es c h e m e a n d p r o x y b l i n dd i g i t a l s i g n a t u r es c h e m e a n dp l e n t i f u la c h i e v e m e n t sh a v eb e e nm a d ei nt h es t u d i e so fp r o x y d i g i t a ls i g n a t u r e h o w e v e r , m a n yp r o x ys i g n a t u r es c h e m e s h a v es o m ed e f e c t si ns e c u r i t y , e f f i c i e n c ya n df e a s i b i l i t y s oi t i so fg r e a ts i g n i f i c a n c et od e s i g ns e c u r e ，e f f i c i e n ta n d f e a s i b l ep r o x ys i g n a t u r es c h e m e s t h i sp a p e rm a d es o m em e a n i n g f u la t t e m p t si nt h e f i c l d sm e n t i o n e da b o r e c h a p t e r l ，i n t r o d u c t i o no fb a c k g r o u n d si nw h i c hp r o x yd i g i t a ls i g n a t u r ee m e r g e d ， m e a n i n g i nr e a l i t ya n dd e v e l o p m e n t c h a p t e r 2 ，i n t r o d u c t i o no f s o m er e l a t i v em a t h e m a t i c sa n d c r y p t o l o g y t h ef o l l o w i n gt h r e ec h a p t e r s ，t h em a i np a r to ft h i sp a p e r , i nt h i sp a r t ，t h ea u t h o r a n a l y z e ds e v e r a la l r e a d y - p r o p o s e dc l a s s i c a lp r o x ys i g n a t u r es c h e m e sa n dr a i s e ds o m e n e w p r o x ys i g n a t u r es c h e m e s t h em a i nc o n t r i b u t i o n so ft h i sp a p e r ： 1 t h r o u g ht h ea n a l y s i so ft w ot 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 s ，w ep r o v e dt h a t q _ c - xs c h e m ec a n tr e s i s tf o r g e r ya t t a c ka n dp u b l i ck e ys u b s t i t u t ea t t a c k a n dt - h y s c h e m ec a n ts t a n du pt of o r g e r ya t t a c kf r o mo r i g i n a ls i g n e r a n ds o m ea m e n d m e n t s h a v eb e e nm a d et ob o t hs c h e m e s a f t e rt h ea m e n d m e n t s ，b o t hs c h e m e sc a nr e s i s ta t t a c k s m e n t i o n e da b o v e m o r e o v e r , an e wn o n r e p u d i a b l 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 e w i t hk n o w n s i g n e r sw a sa d v a n c e dw h i c hh a sf e a t u r e so fl e s sc a l c u l a t i n ga m o u n t ，h i g h e r i j s e c u r i t ya n d l o w e rc o m m u n i c a t i n ga m o u n t - 2 t h r o u g ht h ea n a l y s i s o ft w op r o x yb l i n ds i g n a t u r es c h e m e s ，w ep r o v e dt h a t n e i t h e rt l ts c h e m en o rl - as c h e m ec a l lr e s i s tf o r g e r ya t t a c ka n d b o t hh a v el i n k a b i l i t y a n dt w on e wp r o x yb l i n dd i g i t a ls i g n a t u r es c h e m e sw e r ep r o p o s e dw h i c hw i l ls a t i s f y t h ed e m a n d sf o rs e c u r h yo fp r o x yb l i n ds i g n a t u r es c h e m e 3 t h r o u i g h t h e a n a l y s i s o faf o r w a r d s e c u r e s t r o n gp r o x yd i g i t a l s i g n a t u r e s c h e m e ，w ep r o v e dt h a ti t h a sn of o r w a r ds e c u r i t ya ta 1 1 a n dw ep r o p o s e dt w on e w f o r w a r d - s e c u r e p r o x ys i g n a t u r e s c h e m e sb a s e do ng u i l l o u q u i s q u a t e ra n ds c h n o r r s c h e m e r e s p e c t i v e l y k e y w o r d s ：d i g i t a ls i g n a t u r e ；p r o x yd i g i t a ls i g n a t u r e ；t h r e s h o l dp r o x yd i g i t a l s i g n a t u r e ；p r o x yb l i n dd i g i t a ls i g n a t u r e ；f o r w a r ds e c u r i t y 玎i 学位论文独创性声明 本人声明所星交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人 已经发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均 已在文中作了明确说明并表示谢意。 作者签名：耋i i i 叁：日期；兰塑! ! 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西 师范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文 的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆、院系资料室被查阅l 有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。 作者签名：互丞丛 第一章绪论 政治、军事、外交的文件、命令和条约，商业中的契约以及个人之间的书信等， 传统上采用手书签名或印章，以便在法律上能够认证、核准、生效。随着计算机 和电子通信技术的普及与发展，数字化、电子化的趋势已经波及社会生活的几乎 所有方面，人与人之间的许多交往活动，包括商业贸易、金融贸易以及其它一些 经济活动，不少都是以数字信息的方式通过开放的计算机网络来完成。因此，如 何保护信息使其不受非法的篡改、删除、重放和伪造等攻击，成为人们亟待解决 的重要现实问题“1 。于是，数字签名应运而生，它是实现信息认证的重要工具，数 字签名已经在信息安全、身份认证、数据完整性、不可否认性以及匿名性等方面 发挥了重要作用。 自从1 9 7 6 年d i f f i e 和h e l l m a n 在他们的著名论文密码学的新方向。1 中 首次提出数字签名概念以来，为了满足电子商务、电子政务、移动通信、移动代 理等各种实际情况下对数字签名的需要，人们提出了各种各样的数字签名方案。 如群签名、盲签名、代理签名、多重签名、指定接收者的签名哺”等等。本文对 种具有特殊性质的数字签名代理数字签名进行研究。 1 ：1 代理签名的发展背景 本节主要介绍代理数字签名的发展背景及其在社会中的重要意义，尤其在电子 商务中的一些实际应用。 我们先从一些实例来说明代理数字签名在社会中的应用。考虑如下问题： ( 1 ) 某个公司的经理在某一段时间内，由于健康或其它原因而不能行使数字签 名权，那么，该经理不得不委托他的秘书代表他在这段时间内行使他的数字签名 权。 ( 2 ) 某一软件公司为了向客户证实它出品的程序的可靠性，需要以公司的名义 对所有这些程序进李亍数字签名。由于程序太多公司经理无法亲自检测每个程序， 并在这些程序上签名。一个比较实际的做法是：公司经理将代表公司生成数字签 名的权力委托给每个程序员，让他们各自以公司的名义为他们创作的程序生成数 字签名。 ( 3 ) 某一总行授予所属支行签发电子货币的权力，让他们以总行的名义签发电 子货币，但又不让他们获得总行的签发密钥，以免其滥发行电子货币。 类似以上这种数字签名权力的委托问题在现实社会中是很常见的，是信息化社 会必然遇到的一种现象。要解决以上这种数字签名权力的委托问题，人们必须解 决如下问题。 安全性：一般来说，一个人将数字签名权力委托给代理人的时候，希望代理人 只能代表他在特定的时间、特定的文件进行签名，而不希望代理人滥用他的数字 签名权力，并且不希望其他任何人能因此伪造出有效的数字签名。 可行性：人们希望委托数字签名权力的方法方便、快捷、容易实现。 效率：人们希望委托数字签名权力的方法具有较高的速度和较小的计算量和通 信量等。 普通的数字签名体制不能解决以上问题。因此，设计一种新的特殊的数字签名 体制以解决上述问题成为一个亟待解决的现实问题。这就是代理数字签名产生的 现实背景。 1 2 代理签名及其分类 本节主要介绍代理签名的概念、分类、安全性要求及其研究现状。 1 2 1 代理签名概念 1 9 9 6 年，m a m b o 、u s u d a 和o k a m o t o 5 , 6 1 首先提出了代理数字签名的概念，给 出了解决数字签名权力委托问题的方法。利用代理数字签名体制，一个被称为原 始签名人的用户将他的数字签名权委托给一个被称为代理签名人的用户，代理签 名人代表原始签名人生成的数字签名，称为代理数字签名。 代理数字签名的严格定义如下： 定义1 i 设a ，b 是某个数字签名体制( m ，s ，k ，s i g ，p e r ) 的两个用户，他们的 私钥和公钥对分别是 。，y ) ，0 。，y 。) ，若以下条件满足： ( 1 ) a 利用他的秘密密钥z 。计算出一个数盯，并且将盯交给b ； ( 2 ) 任何人( 包括b ) 在试图求工。时，盯不会对他有任何帮助i ( 3 ) b 可以利用盯和算。生成一个新的签名密钥g r a 。： ( 4 ) 存在一个公开的验证算法w 。，使得任何5 5 和m e m ，都有 v e o ，b ( y 4 ，s ，m ) 一t r u e + s = s i g ( c r j 口，m ) i ( 5 ) 任何人在试图求出n ，盯或盯。时，任何数字签名s i g ( t y a 目，m ) 都不会 对他产生帮助。 那么我们就称用户爿将他的( 部分) 数字签名权利委托给了用户口，并且称爿 为b 的原始签名人，称曰为a 的代理签名人，称1 3 为委托密钥，称g 。为代理签 名密钥，称以吼。作为签名密钥对消息研e m 生成的数字签名s i g ( a 。，m ) 为a 的代理数字签名。 定义1 2 能够生成代理数字签名的数字签名体制被称为代理数字签名体制。 一个代理数字签名体制p s 一( p f ，职，p s ，b y ) 一般由以下四个算法组成： ( 1 ) 系统参数生成算法i p f ：该算法的输入是1 ，其中k 为安全参数：输出为 系统所需的参数，如原始签名人a 和代理签名人占的公私钥对0 。，y 。) 、 。，y b ) 、 安全无碰撞h a s h 函数等。p f 是一个概率算法，系统的安全性评估依赖于k ( 2 ) 代理密钥生成算法p k ：该算法的输入为原始签名人和和代理签名人的私 钥以及一些系统参数，输出为代理密钥仃。豚一般为概率算法。 ( 3 ) 代理数字签名生成算法愿：输入给定消息脚和代理密钥仃。，输出代理 签名s s i g p 。，m ) p s 一般为概率算法。 ( 4 ) 代理签名验证算法p v ：输入签名s 、消息所、以及验证公钥y 。，y 。输出 为代理数字签名s 是否合法的结果1 或0 p v 是个确定性算法。 有时，为了确定代理签名人，还有一个附加的代理签名人身份识别算法肼。 输入个有效的代理数字签名s ，将会输出代理签名人的身份仍。 1 2 2 代理签名安全性要求 文献【5 ，6 】指出代理数字签名应该满足以下六条性质： ( 1 ) 不可伪造性( u n f o r g e a b l i t y ) ：除了原始签名人，只有指定的代理签名人能够 代表原始签名人产生有效的代理数字签名。 ( 2 ) 可验证性( v e r i f i a b l i t y ) ：从代理数字签名中，验证者能够相信原始签名人认 同了这份签名消息。 ( 3 ) 不可否认性( u n d e n i a b l i t y ) ：一旦代理签名人代替原始签名人产生了有效的 代理数字签名，他就不能向原始签名人否认他所签的有效代理数字签名。 ( 4 ) 可区分性( d i s t i n g u i s h a b i l i t y ) ：任何入都可区分代理数字签名和正常的原始 签名人的数字签名。 ( 5 ) 代理签名人的不符合性( p r o x ys i g n e r sd e v i a t i o n ) ：代理签名人必须创建一 个能检测到是代理签名的有效代理签名。 ( 6 ) 可识别性( i d e n t i f i a b l i t y ) ：原始签名人能够从代理数字签名中确定代理签名 人的身份。 为了体现对原始签名人和代理签名人的公平性，l e e 、k j mm l 等对其中的一些 性质给出了更强的定义。 ( 7 ) 强不可伪造性( s t r o n gu n f o r g e a b l i t y ) ：只有指定的代理签名人能够产生有效 代理签名，原始签名人和没有被指定为代理签名人的第三方都不能产生有效代理 签名。 ( 8 ) 强可识别性( s t r o n gi d e n t i f i a b l i o ；) ：任何人都能够从代理数字签名中确定代 理签名人的身份。 ( 9 ) 强不可否认性( s t r o n gu n d e n i a b l i t y ) ：一旦代理签名人代替原始签名人产生 了有效的代理数字签名，他就不能向任何人否认他所签的有效代理数字签名。 防止滥用( p r e v e n t i o no fm i s u s e ) ：应该确保代理密钥对不能被用于其它目 的。为了防止滥用，代理签名人的责任应当被具体确定。 另外，文献【9 】指出代理数字签名还应该满足可撤销性( 原始签名人可以随时撤 销他委托给代理签名人的签名权力) 。 本文认为一个良好的代理数字签名方案应该满足性质( z ) 、( 4 ) 、( 7 ) 、( 8 ) 、( 9 ) 、a 0 ) 以及可撤销性的要求，并且本文设计的代理签名方案都满足这七条安全要求。 1 2 3 代理签名分类 根据不同的标准，代理数字签名有不同的分类方法。 ( _ ) 根据数字签名权力委托过程的不同方式，代理数字签名可以分为三种基本 类型：完全代理型、部分代理型和具有授权书的代理型。 1 完全代理型：原始签名人a 直接把自己的签名密钥x 。通过安全信道发送给 代理签名人口，使得代理签名人口拥有他的全部数字签名权力。 2 部分代理型：原始签名人a 用自己的签名密钥z 。产生委托密钥盯，并把仃以 安全方式发送给代理签名人b ，代理签名人口利用口和其私钥x 。生成代理签名密钥 吼_ 。，利用。，代理签名人b 可以生成有效代理签名。 3 具有授权书的代理型：这种代理签名使用一个称为授权书t n 。的文件来实现 数字签名权力的委托，这种类型又可分为两种子类型。 ( 1 ) 授权代理型：原始签名人a 用他的签名密钥x 。使用普通的签名算法对授权 书m 。，进行签名，然后把m 。，和对m 。，的签名传给代理签名人口。代理签名人口用他 的私钥x 。直接对消息m 进行签名，一个有效的代理数字签名由代理人口的数字签 名、授权书n 。和原始人a 对m 。，的签名组成。 ( 2 ) 持票代理型：在持票代理签名中，证书m 。是由消息部分和原始签名人爿对 新产生的公钥的签名组成。原始签名人4 把新产生的公钥所对应的私钥以安全的 方式传给代理签名人口。代理签名人口用原始签名人a 给他的私钥和他自己的私 钥x 。生成代理数字签名。 上述三种类型的代理数字签名娄型，各有优点和不足。完全代理型的优点是简 单方便，容易实现，缺点是原始签名人a 向代理签名人口暴露了他的私钥x 。代 理签名人口所产生的签名与原始签名人a 所产生的签名是相同的，所阻完全代理 签名不具有可区分性、强不可伪造性、强可识别性和强不可否认性。因此完全代 理型不适用于商业应用；部分代理型的优点可以保护原始签名人a 的私钥z 。，代 理数字签名的长度、生成和验证代理数字签名所需计算量和普通数字签名几乎一 样，缺点是许多部分代理型签名方案不满足强不可伪造性和强不可否认性：具有 授权书的代理型的优点是可以保护原始签名入a 的私钥工。和对代理人口的代理权 进行限制，缺点是计算量稍大、签名长度约是普通签名长度的二倍。 o 根据代理数字签名方案所基于的数学难题，代理数字签名方案可分为基于 离散对数问题的代理数字签名方案和基于素因子分解问题的代理数字签名方案。 根据代理数字签名方案所具有的特殊性质，代理签名方案可分为代理多重 数字签名方案、盲代理数字签名方案、门限代理数字签名方案等等。 卿根据原始签名人能否产生代理数字签名，代理数字签名又可分为代理保护 型和代理非保护型。 1 2 4 代理签名研究现状 由于代理数字签名在移动通信、移动代理、电子商务、电子选举、电子拍卖【n 1 6 1 等方面有着重要的应用，所以一提出便受到广泛关注。国内外学者对其进行了深 入的探讨与研究，并取得了丰硕的研究成果，迄今为止，人们已经提出了多种代 理数字签名方案。如门限代理数字签名方案 协2 2 l 、代理盲数字签名方案 2 3 省】、代 理多重数字签名方案【2 们9 1 、具有跟踪接收者的代理数字签名方案【地3 1 肄等。然而， 仍然存在如下问题尚需进一步研究和解决： ( 1 ) 安全性问题：目前很多代理数字签名方案存在安全隐患。例如，不能抵抗 伪造攻击、公钥替换攻击等。 ( z ) 执行效率问题：目前的代理数字签名方案，尤其是门限代理数字签名方案 和代理多重数字签名方案计算复杂性离、通信量大、执行效率低。 ( 3 ) 如何利用盲签名、定向签名、零知识签名等特殊签名方案来实现代理数字 签名? ( 4 ) 如何利用前向安全思想设计具有不可否认性的前向安全代理数字签名方 案? 1 3 论文的蕈节安排和主要研究成果 本节给出本文的章节安排和主要研究成果。 1 3 1 论文的章节安排 本文共分为五部分，分别以绪论、预备知识、门限代理签名体制、代理盲签名 体制、前向安全的代理签名体制五部分进行论述。 第一章：主要介绍代理数字签名的产生背景、现实意义、发展现状以及代理数 字签名的概念、安全性要求、分类等。 第二章：主要介绍了一些必要的数学、密码学相关知识和一些必要的假设，这 些是以后各章的基础。 第三章：主要介绍了门限代理签名的发展状况和对些典型门限代理签名方案 的安全性分析及改进，并提出了一种新的具有已知签名者的不可否认门限代理签 名方案。 第四章：主要介绍了代理盲签名的发展状况和对一些典型代理盲签名方案的安 全性分析及改进，并提出了两种新的代理盲签名方案。 第五章：主要介绍了前向安全的概念和对一个前向安全的强代理签名方案的安 全性分析，并提出了两种新的前向安全的代理签名方案。 1 3 2 主要研究成果 作者在代理签名方面主要取得了以下研究成果： 1 对两个典型门限代理签名方案进行了分析，证明了q c z 方案【3 2 】不能抵 抗伪造攻击和公钥替换攻击，r h y 方案 3 3 】不能抵抗原始签名人的伪造攻击。 并分别对这两个方案进行了改进。提出了一种新的具有己知签名者的不可否认门 限代理签名方案，新方案具有计算量小、通信量低、安全性高等优点。 2 对两个典型代理盲签名方案进行了分析，证明了r 一己一r 方案f 2 3 j 和l 一彳方 案【2 5 】都不能抵抗伪造攻击和都不具有不可链接性。提出了两种新的代理盲签名方 案，新方案满足代理盲签名方案的安全性要求。 3 对r 一前向安全的强代理签名方案【3 4 】进行了分析，证明了f 一方案不具有 前向安全性。并分别基于g u i l l o u q u i s q u t e r 签名体制【3 5 】和s c h n o r r 签名体制【3 6 】， 提出了两种新的前向安全的代理数字签名方案。 第二章预备知识 本章将介绍一些必要的背景知识，主要是数论、代数学知识以及一些必要的密 码学知识。这些知识是以后各章的基础。 2 1 相关数学知识 数学尤其是代数学和数论在密码学中具有非常重要的地位，目前所使用的公钥 密码体制的安全性基础主要是数学中的困难问题。基本有两大类：一类是基于大 数因子分解问题的，比如，r s a 体制和r a b i n 体制；另一类是基于离散对数问题的， 如d s a 体制和e l g a m a l 体制。 下面对后面将要用到的一些数论与代数学知识进行必要的简单介绍。 定义2 1 1 整数因子分解问题( t h ei n t e g e rf a c t o r i z a t i o np r o b l e m ) ：给定整数 n ，对n 迸行因子分解 = p p p ；2 p 其中p 是不同的素数，e ，是正整数【3 7 】。 到目前为止，对于大数分解的算法复杂度是多项式时间的，随羞大整数的比特 长度增长而变得越来越困难。 定义2 1 2 欧拉函数妒( ) ：设n 是个正整数，妒( 珂) 的值等于序列1 , 2 ，n 一1 中 与n 互素的整数的个数： 妒( 珂) = i 七1 1 七 n - l ，g e d ( k ，打) = 1 ) i 若n 的因子分解已知，则很容易计算伊0 ) ，但当，l 很大时，着n 的因子分解未 知，则很难计算9 伽) 定义2 1 3 离散对数( d 舭他倌l o g r i t h m ) 设g 是一个有限循环群且g g 是g 的一个生成元。元素y g 的离散对数是指唯一的整数x ，( o x i g i ) ，使得y = g 。 成立。记为： x = l o g f y 若g 不是生成元，y 基于g 的离散对数( 若存在) 是指最小的正整数x ，使得 _ y = g 成立。 定义2 1 4 离散对数问题( d i s c r e t el o g r i t h mp r o b l e m ) ：对于一个有限循环群 g ；cg ，和元素y g ，寻找整数x ( o xt l g l ) ，使得y t g 。成立3 8 1 。 定义2 1 5 计算d 够p 一胁l l m a n ( c d h ) 问题：对于一个有限循环群g 和它的生 成元g ，以及两个元素g 。和g6 ，寻找对应的元素g ”。 定义2 1 6 决策d 彬e h e l l m a n ( d d h ) 问题：对于一个有限循环群g 和它的 生成元占，以及三元组( g 。，g6 ，g ) ，判断g = g “是否成立盼删。 定义2 1 7g a pd i 舻e h e l l m a n ( g d h ) 问题：这是一类c d h 问题困难而d d h 问题容易的问题。 定义2 1 8g a pd i f f i e h e l l m a n ( g d h ) 群：这是一种c d h 问题困难而d d h 问 题容易的群。 这样的g d h 群可以在超奇异椭圆曲线或超椭圆曲线上找到。 定义2 1 9 双线性对e ：令g 和g ，分别为阶数为素数牙的加群和乘群，p 为群 q 的生成元，假定g 1 和岛这两个群中的离散对数问题是困难问题，则跌射e ： g tx g l 一职称为双线性对“1 、4 。本文后面所用到的双线性对e 是满足下列三条性 质的双线性对： ( 1 ) 双线性：e ( a p , b p ) 一e ( p ，p ) ”，对任意p p 。e g i 和a ，b z 。 ( 2 ) 非退化性：若对任意的p 1 g 1 ，总有e ( v ，p 。) = 1 ，则p ；0 ( 3 ) 可计算性：对任意p ，p g ，存在有效算法可以计算e ( p ，p ) 我们可以用超奇异椭圆曲线上的w e i l 对或经改造的t a t e 对来构造这样的双线 性对。 定义2 1 1 0 二次剩余( 妫eq u a d r a t i cr e s i d u o s i t y ) ：设h 是两个素数p ，q 的乘积， 且y z 。，若存在整数x ，使得z 2 一y m o d n 成立，则称y 是模 的二次剩余( 平方 剩余) ；若不存在整数石，使得石2 - y m o d n 成立，贝称y 是模的二次非剩余。所 有模r l 的二次剩余和二次非剩余的集合分别记为q 贾。和q n r 。 若n 的园子分解已知，容易判定一个数是否是模n 的二次剩余，而当月的因子 分解未知时，判定一个数是否是模”的二次剩余是一个困难性问题。 定义2 , 1 1 1 二次剩余问题( t h eq u a d r a t i cr e s i d u o s i t yp r o b l e m ) ：给定整数和 y ，( osyc ) ，判定是否存在整数x ( os x n ) ，使得z 2 。y r o o d n 成立。 2 2 相关密码学知识 本节对后面各章将要用到的相关密码学知识进行一些必要的介绍。 2 2 1 公钥密码体制 公钥密码技术是由d i f f i e 和h e l l m a n 于1 9 7 6 年首次提出的一种密码技术。与对 称密码体制相比，公钥密码体制有两个不同的密钥，它可将加密功能和解密功能 分于1 2 1 4 4 。一个密钥被称作私钥，像在对称密码体制中一样，该密钥被秘密保存。 另一个密钥称作公钥，不需要保密，绘定公钥，要确定私钥在计算上是不可行的。 公钥密码体制有两种基本类型，一种是加密模型如图2 1 ，另一种是认证模型，如 图2 2 。 明文 明文 图2 1 加密模型 a 的私钥a 的公钥 明文 明文 图2 2 认证模型 因为加密与解密的密钥不同，所以又称为非对称密码系统。它的缺点是速度慢， 与对称密码系统相比，大概慢了百倍至千倍。但由于对称密码体制不适舍直接应 用于大规模的网络上。因为仅密钥的分发、认证就是一大难题，所以一般对称密 码体制配合公钥密码体制一起应用，结合两种体制的长处，来对信息进行保护。 2 2 2 数字签名方案 一般数字签名方案d s 包括三个过程【4 1 ：系统初始化过程、签名产生过程和签 名验证过程。 l 、系统初始化过程 产生数字签名方案中的基本参数( m ，s ，k ，s i g ，v e l ) ，其中：吖消息集合， s 一签名集合，k 密钥集合，包含私钥和公钥，s i c 签名算法集合，p e r 签名验证算法集合。 2 、签名产生过程 对于密钥集合k ，相应的签名算法为s i g 。e s l g ，s 喀k ：m s ，对任意的 消息e m ，有s = s i g k 沏) ，则s s 为消息的签名。 3 ) 签名验证过程 对于密钥集合定，有签名验证算法： v e k ：m s - t r u e ，向l s e 签名验证者收到咖，s ) 后，计算v e r r ( m ，5 ) ，若v e r k ( 卅，s ) ；t r u e ，签名有效；否则， 签名无效。 数字签名必须满足以下三点： ( 1 ) 签名是发送者用自己的私钥进行签署的，接收者在验证签名正确后，能识 别发送者的身份。 ( 2 ) 发送者事后不能否认对消息的签名。 ( 3 ) 经过签名的文件若经过任何修改，则无法通过验证，确保文件的完整性。 一般认为数字签名方案还应该满足自适应选择消息攻击下的安全性。自从数字 签名的概念提出之后，人们提出了许多不同的数字签名体制，比较著名的数字签 名体制有：s c h ，l o f f1 4 4 j 、r s a 矧、e i g a m a l 【4 “、d s s1 3 4 1 、f i a t s h a m i r 【4 7 1 等。 2 2 3 基于配对的短签名体制 基于配对的短签名体制是b o n e h 等人首先提出的“，方案如下： 设群g ，和g ：的阶数都为素数孽，p 为g d h 群g 1 的生成元，e ：g 1 x g l g 。 为一安全双线性对，h ( ) ： o ，1 一g 1 为一强无碰撞安全单向h a s h 函数。签名者 随机选择s k s z ；作为私钥，对应的公钥为p k a s k p ，要对消息r n 进行签名，签名 者计算；s k h 咖) ，接收者收到签名咖，盯) 后，验证e ( p ，盯) t e o k ，h ( m ) ) ，若成 立，则签名有效；否则无效。 若假定c d h 问题是困难的，则该体制在随机预言( o r a c l e ) 模式下被证明对抗 任意选择明文攻击是安全的。 2 2 4 单向h a s h 函数 单向h a s h 函数就是把任意长度的明文比特映射为固定长度k 比特的函数。 即( ) ： o ，l 一 o ，1 f 记消息为胁，散列值h = h ) ，一个安全的单向h a s h 函数应该至少满足以下 要求： 1 输入长度是任意的； 2 输出长度是固定的： 3 ，给定m ，很容易计算h ； 1 0 4 给定h ，根据h = h m ) 计算m 很难，即求逆不可行： 5 给定脚，要找到另一消息肌。，并满足灯沏) = 汀铆) 在计算上是不可行的。 6 给定抒( ) ，要找两个不同鹩槐。和l t l ：，使得打( 礅，) = h ( m 2 ) 在计算上是不 可行的。 满足前五条性质的单向h a s h 函数称为弱单向h a s h 函数，满足以上六条性质的 单向h a s h 函数称为强h a s h 函数。单向h a s h 函数的安全性依赖于输出的比特长 度，一般要求输出长度至少为k = 1 6 0 比特。比较流行的单向h a s h 函数有：s h a l 、 m d 2 、肋4 、m d 5 等。 2 1 3 数论假设及参数设置 本节给出一些必要的数论假设，这些是以后各章的代理签名方案的安全性基 础。 2 3 ，1 数论假设 假设1 ( 强r s a 假设) ：已知n ( n 为两个大素数p ，q 的乘积，且不知道p ，g ) 和c z 二，则找出一组数r ( r ，1 ) ，口z ：，且满足口7 一c m o d n 是一个非常困难的问 题【4 9 】。 假设2 ( 离散对数锻设) ：对于一个阶数很大的有限循环群gt cg ，和元素 y g ，寻找整数工( o 王zc 蚓) ，使y 。g 。成立在计算上是不可行的。 假设3 ( d i f f i e h e l l m a n 假设) ：在g a pd i f f i e h e l l m a n 群上c d h 问题是个 非常困难的问题。 2 3 2 参数设置 在本文以后的各章中，如无特别说明，所用参数律同下：i i 表示字符串的连 接，庐( ，) 为欧拉函数，j d ，q 为安全大素数，g ，g ：为阶为q 的群，群g ，为g d h 群， 且在群g 1 ，g ：上计算离散对数是困难的问题，p ：g 1 g 1 一g ：为一安全的双线性 对，( ) ： o ，1 ) 一 o ，1 r ，h ，( ) ： 0 ，1 ) x g l 一z ：，h ，( ) ： o 妒一g 1 为三个强无碰撞 安全单向h a s h 函数，q _ r 为模n 的平方剩余集合，m 。为授权书( 详细描述了代理 签名的诸多事宜，如原始签名人和代理签名人的身份、代理权限、有效期等) 。 第三章门限代理签名体制 本章将介绍门限代理签名的基本概念和门限代理签名体制的发展状况，并对两 个典型的门限代理签名方案进行了分析，最后本章提出了一种新的具有已知签名 者的不可否认门限代理签名方案，并与已提出的门限代理签名方案在安全性及效 率等方面进行了比较。 3 1 基本概念及发展状况 随着代理签名的发展，门限代理签名受到了广泛关注。o ， ) 门限代理签名是代 理签名的一种变形，它是由门限签名体制和代理签名体制结合而产生的一种新的 签名体制。门限代理签名体制的代理签名密钥由打个代理签名人分享保管，只有t 个或更多的代理签名人代表原始签名人运用各自的代理签名密钥碎片才能产生对 消息m 的签名，少于t 个则不能。 z h a n g1 1 以和k i ml l g 等分别独立的提出了门限代理签名体制。s u n 、l e e 和 h w a n g1 1 8 l 指出z h a n g 和k i m 、p a r k 和w o n 的门限代理签名方案是不安全的，并给 出了一个改进方案。文献 2 0 j 差- - 步指出s u n 、l e e 和h w a n g 方案不自抵抗公钥替 换攻击，并给出了一个更安全的不可否认门限代理签名方