（应用数学专业论文）盲签名研究及其在电子选举中的应用.pdf

盲签名研究及其在电子选举中的应用 摘要 随着计算机网络技术的发展，网络信息安全问题日益突出。作为信息安全核 基础之一的数字签名技术，被广泛应用于军事、通信、电子商务等领域着“电 子签名法”的颁布和实施，这种应用将变得越来越普遍。 首先，本文简单介绍了数字签名、盲签名、哈希函数等基本概念型的盲签名 方案，如r s a 盲签名方案和e 1 g a m a l 盲案，并介绍了盲签名技术电子投票系统 中的应用现状。 其次，在e i g a m a l 盲签名的基础上设计了一种多重盲签名方案，对安全性 理论分析。该方案实现了多人同时对消息的盲签名，并且具有盲性和不可等性质。 基于盲签名技术提出了一种匿名电子投票协议，该协议能够保证身份的匿名性， 并且可以防止一人多票或一票多投现象的发生。 最后，提出了盲签名技术的进一步改进和研究并对未来的发展趋势进行了展 望。 关键词：数字签名；盲签名；代理盲签名；多重盲签名；电子投票 r e s e a r c ho fb l i n ds i g n a t u r e a n da p p l i c a t i o ni ne - v o t es y s t e m a b s t r a c t w i t lt h ed e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g y n e t w o r ki n f o r m a t i o n s e c u r i t yp r o b l e mb e c o m e sm o r ea n dm o r ei m p o r t a n t d i g i t a ls i g n a t u r ea so n eo fk e y t e c h n o l o g yo ft h ei n f o r m a t i o ns e c u r i t yi sw i d e l yu s e di nm i l i t a r y ，c o m m u n i c a t i o n e - c o m m e r c e ，e t c w i t h ”e l e c t r o n i cs i g n a t u r el a w ”b e i n gp u ti n t op r a c t i c e ，t h e a p p l i c a t i o n o f d i g i t a ls i g n a t u r ew i l lb e c o m em o r ea n d m o r ep o p u l a r t h ep a p e rf i r s t l yi n t r o d u c e ss o m eb a s i cc o n c e p f i o n so fc r y p t o g r a p h y , s u c h a s d i g i t a ls i g n a t u r e ，b l i n ds i g n a t u r e ，h a s hf u n c t i o ne t ca n dt y p i c a l b l i n ds i g n a t u r e s c h e m e s ，f o ri n s t a n c e ，r s ab l i n ds i g n a t u r es c h e m ea n de 1 g a m a lb l i n ds i g n a t u r e s c h e m e t h ew i d eu s eo fb l i n ds i g n a t u r et h e o r yi ne - v o t es y s t e m s e c o n d l y , am u l t i p l eb l i n ds i g n a t u r es c h e m eb a s e do ne 1 g a m a lb l i n ds i g n a t u r e s c h e m ei sd e s i g n e dw i t ht h e o r ya n a l y s i st ot h es e c u r i t yo f t h es c h e m e i ti s p o s s i b l ef o r m a n ys i g n e r st os i g na tt h es a m et i m eb yu s i n gt h i ss c h e m ea n dt h i s s c h e m eh a sb o t h p r o p e r t i e so fb l i n da n du n t r a c e a b l e f i n a l l y , t h i sp a p e rp r e s e n t sa n a n o n y m o u s e l e c t r o n i cv o t ep r o t o c o lo nt h eb a s i so fb l i n ds i g n a t u r et e c h n o l o g ya n ds e c u r i t y a n a l y s i so ft h i sp r o t o c o li sp r e s e n t e di nd e t a i l t h ep r o t o c o lc a nr e a l i z e a n o n y m i t yo f v o t e ro f i d e n t i t ya n dp r e v e n tt h a to n ep e o p l eh a v et w ov o t e so rt h es a m e v o t ei s t h r o w nm a n yt i m e s t h e na na n o n y m o u se l e c t r o n i cv o t es y s t e ms c h e m eb a s e d o nt h i s p r o t o c o li sp r o p o s e d t h i sp a p e rp r o v i d e st h ed e s i g no ff u n c t i o nm o d u l e si n d e t a i la n d a p a r to f p r o g r a m m i n gc o d ei sg i v e n i nt h ee n d ，t h i sp a p e rp r e s e n t st h e a s s u m p t i o no ft h ef u r t h e ri m p r o v e m e n ta n d r e s e a r c ho fb l i n ds i g n a t u r et h e o r ya n d l o o k sf o r w a r dt ot h ed e v e l o p m e n tw e n do fb l i n d s i g n a t u r et h e o r yi nt h ef u t u r e k e y w o r d ：d i g i t a ls i g n a t u r e ；b l i n ds i g n a t u r e ；p r o x y b l i n d s i g n a t u r e ；m u l t i p l e b l i n d s i g n a t u r e ；e l e c t r o n i cv o t e 1 1 引言 第1 章绪论 随着计算机和通信网技术的发展和广泛应用，为人们工作、生活带来极大 便利，同时也带来了许多待解决的问题，其中信息的安全性就是一个突出的问题。 信息是一种资源，同时也是一种财富。因各种因素的影响，信息会受到破坏、窃 取、窜改等不同威胁以至信息无法使用。近二十年来发生的一系列威胁信息系统 的事件，如黑客利用分布式拒绝服务方法攻击大型网站，导致网络服务瘫痪、利 用计算机网络进行金融诈骗等等，给国家、社会、团体和个人带来了巨大的无法 挽回的损失，这些都足以让人们高度重视信息系统的安全问题。信息作为国家的 重要战略资源，其安全性显得十分突出，另外，计算机网络也早己被应用于军事 对抗领域。信息系统的安全性问题解决不好，将直接影响到国家安全和社会稳定。 而解决这一问题唯一有效手段就是使用现代密码技术。信息的安全性主要有两方 面：即信息的保密性和信息的认证性。保密的目的是防止敌手破译系统中的机密 信息：认证的目的包括验证信息的发送者是真正的而不是假冒的：验证信息的完 整性，即验证信息在传送或存储过程中未被篡改、重放、延迟等。数字签名是认 证的主要手段之一，也是现代密码学的主要研究内容之一。 密码学的发展历史大致可以分为三个阶段： 第一个阶段：从古代到1 9 4 9 年( 古典密码学阶段) 。这一时期的密码设计不 是通过推理证明，而是更多地依靠设计者的直觉。 第二个阶段：从1 9 4 9 年到1 9 7 5 年( 传统密码学阶段) 。1 9 4 9 年s h a n n o n 发表 的“保密系统的通信理论”的论文，该论文为私钥密码系统建立了理论基础， 从此密码学便成为了一门真正的科学。随后i b m 公司的w t u c h m a n 和c m e y e r 于1 9 7 1 年至1 9 7 2 年，根据h o r s tf e i s t e 在1 9 6 7 年提出的加密算法理论，成功 地设计出了d e s 算法。d e s 的出现改变了过去密码体制的设计者总是设法掩盖密 码算法实现细节的惯例，开创了公开加密算法的先例，从而使密码体制成为一个 工业化数据加密体制成为可能。但d e s 里的所有计算，除去s 盒，全是线性的， 这使得d e s 里的s 盒子只能够防止某些类型的攻击。 这一时期的密码学我们称之为传统密码学。传统密码学具体实现过程是：首 先消息的发送者用这个共享密钥加密消息，然后消息的接收者用这个相同的密钥 解密消息并获取消息。 第三个阶段：从1 9 7 6 年至今。w h i t f i e l dd i f f i e 和m a r t i nh e l l m a n 于1 9 7 6 年在他们的论文“密码学的新方向”中提出了公开密钥密码学的概念，并首次证 明了在发送端和接收端无密钥传输的保密通信是可能的，从而导致了密码学上的 一场革命，开创了公钥密码学的新纪元。采用公开密钥密码体制的每个人都有一 对密钥，公钥和私钥，所有的通信加密都借助于公钥进行，而无需私钥的传输和 共享。公钥密码体制的主要特点就是将加密和解密分开，从而实现多个用户加密 的消息只能由一个用户解密，或由一个用户加密的消息能使多个用户可以解读。 前者用于在网络中实现保密通信，后者用于在认证系统中实现数字签名。保密通 信的具体实现过程是：当a l i c e 想发送一个秘密消息给b o b 时，她查看目录并寻 找b o b 的公钥，然后用公钥加密消息并将加密后的消息发出。这时，b o b 就可以 接收消息并用自己的私钥解密。为了达到公钥密码体制真正安全的目的，要求保 证密钥生成算法不能由任何人根据公钥推出相应的私钥。数字签名的具体实现过 程是：a i i c e 对要发送的消息和她自己的私钥进行一个运算，运算的结果成为数 字签名，然后将数字签名和要发送的消息放到一起进行发送。b o b 接受到消息后， 用a l i c e 的公钥对数字签名进行相应运算，取得消息副本并与随数字签名一起发 送的消息原本进行比较，如果副本与原本相同，则证明接收到的消息为真，否则 就证明签名是伪造的。 1 2 密码学的基本概念和术语 密码学是研究加密和解密变换的- - i 7 科学。它主要包括两个分支，即密码编 码学和密码分析学。密码编码学的目标是使一份消息或记录对非授权的人是不可 理解的；而密码分析学的目的在于研究加密消息的破译和消息的伪造。 1 2 1 密码编码学 采用密码技术可以隐藏和保护需要保密的消息，使未授权者不能提取信息。 被隐藏的消息称为明文，隐藏后的消息称为密文。将明文变换成密文的过程称作 加密，其逆过程，即由密文恢复出原明文的过程称为解密。根据密钥的特点， s i m m o n s 将密码体制分为对称和非对称两种。对称密码体制又称单钥或传统密码 体制：非对称密码体制又称双钥或公钥密码体制。 1 2 2 密码分析学 根据密码分析者破译时己具备的前提条件，通常人们将攻击类型分为四种， 即唯密文攻击、己知明文攻击、选择明文攻击和选择密文攻击。 ( 1 ) 唯密文攻击：密码分析者有一个或更多的用同一个密钥加密的密文，通过 对这些截获的密文进行分析得出明文或密钥。 ( 2 ) 己知明文攻击：除待解的密文外，密码分析者有一些明文和用同一个密钥 加密这些明文所对应的密文。 ( 3 ) 选择明文攻击：密码分析者可得到所需要的任何明文所对应的密文，这些 密文和待解的密文是用同一个密钥加密得来的。 ( 4 ) 选择密文攻击：密码分析者可得到所需要的任何密文所对应的明文，解密 这些密文所使用的密钥与解密待解的密文的密钥是一样的。 1 2 3 密码通信系统和认证系统 一个密码通信系统由以下几个部分组成：明文消息空间p ；密文消息空间c ； 密钥空间k i 和k ，在私钥体s u t ，墨= k 2 = k ，此时密钥k 需经安全的密码信 道由发方传送给收方：加密变换瓦：p 斗c ，南蜀，由加密器完成：解密变 换：q ：p 斗c ，：k 2 ，由解密器实现a 对每一个密钥墨墨， ( 岛确定一个 加密变换e k , ) ，有一个匹配的密钥哎k 2 ( 屯确定一个解密变换) 使得对于一 切m p ，有 包：( 气( m ) ) = m ( 卜1 ) 对于给定的明文消息脚p 和密钥杭k l k j ，加密变换将明文m 变换为密文 c ： c = f m ，毛) = 瓦( ) ，p ( 卜2 ) 接收者利用通过安全信道传送来的密钥岛( 私钥体制下) 或用本地密钥生成 器产生的解密密钥棍哎墨( 公钥体制下) 控制解密操作d 对收到的密文进行变 换以恢复明文消息i n ： m = d 0 ( c ) ，m p ，k 2 k 2 ( 1 3 ) 而密码分析者，则用选定的变换函数h ，对截获的密文c 进行变换，得到的 明文是明文空间中的某个元素r a m = h ( c 、 ( 卜4 ) 一般地m m 令= 气：p _ c i 墨e 墨) ，d = p k ：c j 尸哎k ) ， 则称六元组 ( 尸，c ，k ，k 2 ，s ，d ) 为一保密系统。为了保护信息的机密性，抵抗密码分析，保密 系统应当满足下述要求： ( 1 ) 即使达不到理论上是不可破的p r ( m = m ) = 0 ，也应当是实际上不可破 的。也就是说，从截获的密文或某些已知明文一密文对，要确定密钥或任意明文 在计算上是不可行的。 ( 2 ) 系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。 ( 3 ) 加密和解密算法适用于所有密钥空间中的元素。 ( 4 ) 系统既易于实现又便于使用。 防止消息被篡改、删除、重放和伪造的一种有效的方法是使发送的消息具有 被验证的能力，使接收者或第三方能识别和确认消息的真伪，实现这类功能的密 码系统称作认证系统。一个安全的认证系统应当满足如下基本要求： ( 1 ) 意定的接收者能够检验和证实消息的合法性和真实性。 ( 2 ) 消息的发送者对所发的消息不能抵赖。 ( 3 ) 除了合法的消息发送者外，其它人不能伪造合法的消息。而且在已知合 法密文c 和相应消息m 下，要确定加密密钥或系统地伪造合法密文在计算上是不 可行的。 ( 4 ) 当通信双方( 或多方) 发生争执时，可由称作仲裁者的第三方解决争执。 1 2 4 公钥密码体制 一个公钥密码体制由如下要素组成： 随机参数空间( r ) ； 私钥空间( p 足) ； 公开密钥空间( 只k ) ： 明文空间( p ) ； 密文空间( c ) ： 密钥生成算法( k e y g e n ：r - - 只k 只k ) 加密算法( e n c ：只世p j c ) ； 解密算法( d n c ：只k c _ p ) ； 对任意的，r ，x p k ，y 只k ，m p ，c c ，若( x ，_ y ) = k e y g e n ( r ) ，c = e n c ( y ，m ) ， 则有以下两个条件成立： ( 1 ) 由x 容易计算出y ，但是由y 难以计算出x ： ( 2 ) m = d e c ( x ，e n c ( y ，) ) 如果用户a l i c e 想要让其他人向她发送消息，那么a l i c e 事先随机选择一个 参数r r ，计算出( x ，y ) = k e y g e n ( r ) ，并将y 公开，将x 作为自己的私钥。当 用户b o b 想要给a 1 i c e 秘密地发送消息m p 时，他首先检索到a 1 i c e 的公开密 钥y ，然后用该公开密钥计算出密文c = e n c ( y ，m ) ，发送给a l i c e a l i c e 收到c 后，恢复m 如下：m = d e c ( x ，c ) “窃听者”只能知道密文c 和公开密钥y ，但他 6 不能根据c 和y 得到解密密钥x ，因而不能计算出明文消息m 自1 9 7 6 年提出公开密钥密码学概念以来，已经提出了很多的公开密钥算法 中，有两个算法既适于加密又适于数字签名，即r s a 体制和e l g a m a l 体制。 下面介绍r s a 密码体制： 1 9 7 8 年，m i t 的三位年青数学家r l r i v e s t ，a s h a m i r 和l a d l e m a n 发现了 一种用数论构造双钥的方法，称为m i t 体制，后来被广泛称之为r s a 体制。它的 安全性基于大数分解的难度。 体制：为了产生两个密钥，首先独立地选取两个大素数p 和q ，为了获得更 大程度的安全性，两个数的长度最好一样。计算它们的乘积： 拧= p q ( 卜5 ) 然后随机选取加密密钥e ，使e 和( p 1 ) ( 口一1 ) 互素。最后用欧几里扩展算法 计算解密密钥d ，以满足 e d = 1 m o d ( p 1 ) ( g 一1 ) ( 卜6 ) 则 d = e m o d ( ( p 一1 ) ( g 一1 ) ) ( 卜7 ) 注意，d 和r l 也互素，e 和n 是公钥，d 是私钥，p ，q 保密。 加密：对明文消息m ，首先将它分成比n 小的数据分组加密后的密文c 将由 相同长度的分组c 组成。加密公式简化为： e = m ( m o d n ) ( 1 8 ) 解密：取每一个加密后的分组ec ，并计算： m i = c , a ( m o d n ) ( 卜9 ) 以下介绍e l g a m a 密码体制： 这一体制由e l g a m a l 提出，它是一种基于离散对数问题的双钥密码体制。其 安全性依赖于计算有限域上离散对数的难度。 体制：为了产生一对密钥，首先选择一素数p ，令z 。是一个有p 个元素的有 限域，g 是z ，中的一个本原元，或其生成元( g p ) 。明文集m 为2 ：( z p 中除去0 元素) ，密文集c 为z 三z 二计算 得到公钥( 卢，g ，p ) ，私钥x 口2 9 1 r o o d p ( 1 一1 0 ) 加密：选择随机数女z 。，且( 女，p 1 ) = 1 ，计算 y i = g m o d p ( 随机数k 被加密) y 2 = m m o d p ( 明文被随机数k 和公钥p 加密) ( 卜1 1 ) ( 1 - 1 2 ) 其中m 是发送明文组。密文由上述两部分级联构成，即密文c = y j | i y ， 解密：收到密文c 后，计算 m = y 2 y , = m g “g “m o d p ( 卜1 3 ) 1 2 5 数字签名 数字签名有助于实现大型网络安全通信中的密钥分配，同时也是是实现认证 的重要工具。数字签名应满足如下条件： ( 1 ) 收方能够确认或证实发方的签字，但不能伪造： ( 2 ) 发方发出签字的消息给收方后，就不能否认他所签发的消息： ( 3 ) 收方对己收到的签字消息不能否认，即有收报认证： ( 4 ) 第三者可以确认收发双方的消息传递，但不能伪造这一过程。 数字签名与加密不同：消息的加密和解密可能是一次性的，它要求在解密之 前是安全的：而一个签名的消息可能是一个文件，很可能要在若干年后才验证签 字，且可能需要多次验证。因此，签名的安全性和防伪造的要求更高一些，并且 要求验证速度要快。 一个安全有效的数字签名方案必须满足以下要求： ( 1 ) 要使签名有效，签名必须处于签署人的完全控制之下，即无人能够伪造另 一个签名： ( 2 ) 发方发出签名的消息给对方后，不能否认他所签发的消息： ( 3 ) 收方对己收到的签名消息不能否认： ( 4 ) 与签名联系的信息必须明确： ( 5 ) 第三者可以确认收发双方之间的消息传送，但不能伪造这一过程。 满足上述要求的数字签名能够实现以下功能： ( 1 ) 收方能够证实发方身份；( 2 ) 发方( 收方) 事后不能否认发送( 接收) 的报文； ( 3 ) 收方或非法者不能伪造、篡改报文。 一个数字签名体制通常包含两个组成部分：签名算法和验证算法。对消息m 的签名可以简记为s i g ( m ) = s ，而对s 的证实可以简记为v e r ( s ) = o ，1 ) 。签名算 法和签名密钥是秘密的，只有签名人掌握；证实算法可以公开，以便他人进行验 证。 一个数字签名体制可表示为( m ，s ，k ，v ) ，其中m 是明文空间，s 是签字的集 合，k 是密钥空间，v 是证实函数的值域。 对每一个k k ，有一签名算法： s = s i g t ( m ) s ，其中m c m ( 卜1 4 ) 和一个验证算法： v e r k ( s ，m ) 0 ，1 ( 卜1 5 ) 体制的安全性在于，从m 和签名s 难于推出k ，或伪造一个m 简单介绍一下r s a 数字签名体制： 体制参数：令n = p i p 2 ，p l 和p ：是大素数，令m = s = 乙，选择o ，并计算出 d ，e d = 1 m o d ( ( p l - 1 ) ( p 2 1 ) ) ，公开n 和e 将n 、岛和d 保密。k = ( ，p ，q ，e ，d ) 签名：对消息m e 乙，定义 s = s i g e ( m ) = m 。m o d n ( 卜1 6 ) 为对m 的签字。 验证：对给定的m ，s 可以按下面的式子进行验证 v e q ( m ，s ) = 1 营m ；s 。m o d n ( 卜1 7 ) 体制的安全性依赖于n = a 仍分解的困难性。 e l g a m a 数字签名体制实现过程如下： 9 体制参数 p ：一个大素数，可以使z 。中求借离散对数为困难问题； g ：是z ，中乘群乏的一个生成元或本原元： x ：n p 密n x e z ； i ：消息空间，为； s ：签名空间，为为z x z p 一， 计算 y 5 9 1 m o d p ( 1 1 8 ) 得到公开密钥：( b g ，j ，) ，私钥：x 签名：给定消息r i ，发信用户进行下述工作： ( 1 ) 发送端用户选择秘密随机数女s 乏： ( 2 ) 计算：h ( m ) ，( h 为h a s h 函数) r = g m o d p s = ( ( m ) 一x r ) k m o d ( p i ) ( 卜1 9 ) ( 3 ) 将s i g k ( m ，七) = s = ( r l i5 ) 作为签名，将m ，( r l l j ) 送给对方。 验证：收方收到m ，( r i | s ) ，先计算h ( m ) ，并按下面的式子验证 v e r ( h ( m ) r ，s ) = 1 营y r r 35g “r o o dp ( 卜2 0 ) 这是因为 y 7 r 5 兰g 肼g 畦三g h + 矗m o d p ( 1 2 1 ) 由公式( 卜1 9 ) 有， ( r x + s k ) i h ( m ) m o d ( p 1 1 ( 卜2 2 ) 故有， y 7 r 55g “”m o dp ( 卜2 3 ) 在此方案中，对同一消息m ，由于随机数k 不同而有不同的签名s = ( r | | s ) 1 0 该体制的安全性依赖于解离散对数问题的困难性。 1 2 6 对数字签名的攻击 g o d w a s s e r 在文献 7 中列举了对数字签名的几类攻击： 唯密钥攻击：敌手只知道签名者的公钥。 消息攻击：敌手在攻击签名方案前能够获得对应己知消息或选择消息的签 名。 根据消息的选择方式，消息攻击可分四类： 已知消息攻击：敌手知道各个消息码，聊：，碍对应的签名，但是 ，鸭，不是由敌手选择的。 般选择消息攻击：敌手选择消息弼，辑，可以获得对应消息的签名。 有向选择消息攻击：消息m ，聊：，砚，可能在敌手知道签名者公钥后、在得 到任何签名之前构造。 1 3 盲数字签名 c h a u m 于1 9 8 3 年最早提出了盲签名的概念，下面通过一个具体的协议来更 直观地解释盲签名的概念。设a 1 i c e 为消息拥有者，b o b 为签名人。a l i c e 想让 b o b 签一个文件，但又不想让b o b 知道他在签什么。b o b 不关心文件中说些什么， 他只是证明他在某一时刻公证过这个文件，他愿意这样进行： ( 1 ) a l i c e 取出文件并将它乘以一个随机值，这个随机值称为盲因子； ( 2 ) a 1 i c e 送这份隐蔽好的文件给b o b ； ( 3 ) b o b 在这个隐蔽好的文件上签名； ( 4 ) a l i c e 将其去除盲因子，留下b o b 签过的原始文件。 文献 6 中根据盲签名提供的匿名强度，将其分为四类： 隐签名：签名者不知道所签消息的内容，但是知道签名参数。签名后，通过 比较保留的参数与签名比较，签名者能够识别出自己的签名。 弱盲签名：签名者不知道所签消息的内容，也不知道签名参数，但通过盲化 的签名参数和未盲化的参数问的联系能够识别签名。 交互式盲签名：签名生成过程与弱盲签名相同，通过交互式证明展示签名信 息，签名者不能将盲化的和未盲化的签名参数联系起来。 强盲签名：签名者无法将关于盲消息m 的签名s i g ( m 7 ) 和从s i g ( m ) 转化得到 的关于真实消息m 的签名s i g ( m ) 相联系。 1 4 研究工作概要和论文章节安排 本文主要讨论盲数字签名理论及其在电子选举系统中的应用。文中讨论了盲 签名的形式化定义、基于因子分解问题的盲签名方案、基于离散对数问题的盲签 名方案及其安全性分析：讨论了群盲签名、代理盲签名、门限盲签名、多重盲签 名四类特殊盲签名及相应的方案分析：讨论了基于盲签名技术设计电子选举协 议。本文主要创蓊性工作： 1 设计了一个新的代理盲签名方案并进行了分析； 2 提出了一个新的基于e 1 0 a m a l 体制的多重盲签名方案； 3 基于门限盲签名体制和多重签名方案提出了一个新的电子选举协议并进 行了分析，新的协议满足电子选举协议的七条基本性质。 全文共分六章，各章的内容安排如下： 第一章介绍了信息安全领域的研究背景及意义、数字签名特性及其功能和分 类、对数字签名的攻击：盲签名的分类及应用。 第二章介绍了本文涉及的一些概念和问题，包括数论、代数中的概念、对称 密码体制和非对称密码体制基础、h a s h 函数的概念及安全性、数字签名形式化 定义以及本文的符号约定。 第三章讨论了盲签名的形式化定义、盲r s a 签名及其安全性分析、基于离散 对数问题的盲签名方案及其安全性分析，其中讨论了基本e 1 g a m a l 数字签名、 n e b e r g r u e p p e l 签名、c a m e n i s c h 盲签名方案的设计与分析。 第四章主要讨论了四类特殊盲签名方案的设计与安全性分析，包括群盲签 名、代理盲签名、门限盲签名、多重盲签名。结合m a m b 代理签名方案、c a m e n i s c h 盲签名方案，设计了一个新的代理盲签名方案并进行了分析：讨论了j - l 门限盲 签名方案；讨论了e 1 g a m a l 有序多重数字签名方案。 第五章主要讨论了盲签名在电子选举中的应用。综述了现有电子投票方案， 并进行了比较分析、基于门限盲签名体制和多重签名方案提出了一个新的电子选 举协议并进行了分析。 第六章总结全文并指出了进一步的研究方向。 2 1 数学基础 第2 章预备知识 本节简单介绍论文中用到的数论、代数中的相关基本概念。 定义1 对任意整数y i 和任意整数a 和b ，若”i o 一6 ) ，则称a 和b 模n 同余，记 为口ib ( r n o d n ) 定义2 设a 乙，若存在x z ，使得“= l ( m o d n ) ，则称x 为a 在模n 的乘法 逆元，可记为a ， 定义3 设口乏，若同余式x 2 ；a m o d n 有解，则称a 是模n 的二次剩余，否则， 称a 是模n 的二次非剩余。 定义4 设g 是一个群，如果g 中有一个元素d 使得对于每一个b g ，都存在一 个整数i 使得b = 口7 ，则称g 是一个循环群，a 称为g 的一个生成元。 定义5 设g 是个群，日g ，a 的阶定义为使得a7 = l 的最小正整数t ( 假定这样 的正整数存在的话) 。如果这样的正整数t 不存在，那么a 的阶定义为c 。 定义6 因子分解问题：给定一个正整数n ，找出1 1 的所有素因子。即n = 钟废2 聍， 其中只是互不相同的素数，q 1 定义7r s a 问题：给定一个正整数n ，n = p * q ，p 和q 是两个不同的奇素数，有正 整数e ，使得g c d ( e ，( p 一0 ( q 一1 ) ) = 1 成立，另有整数c ，找出一个整数m ，使得 m 。；c ( m o d n ) 成立。 定义8 离散对数问题( d l p ) ：设有素数p ，z ：的生成元口，z ：，找出一个整数 x ，0 x p 一2 使得g 。；f l ( m o d p ) 成立。 1 4 2 2 密码学基础 密码学是研究密码系统或通信安全的一门科学，包括密码编码学和密码分析 学两个分支。密码编码学主要任务是寻求产生安全性高的有效密码算法和协议， 以满足对消息进行加密或认证的要求：密码分析学研究破译密码或伪造认证信 息，实现破取机密信息或进行诈骗破坏活动。密码技术是信息安全技术的核心。 目前人们把密码理论与技术分成两大类：一类是基于数学的密码理论与技术，包 括公钥密码、分组密码、序列密码、认证码、数字签名、h a s h 函数、身份识别、 密钥管理、p k i 技术、v p n 技术等：另一类是非数学的密码理论与技术，包括信息 隐藏、量子密码、基于生物特征的识别理论与技术等。从目前的密码学体制来分 河分为对称密钥密码和非对称密钥密码体制。前者是指加密和解密都使用相同的 密码，这种体制中最有代表性的算法为d e s 算法：后者是指加密和解密使用不同 的密钥，这种体制中最有代表性的算法为r s a 算法。 2 3h a s h 函数 h a s h 函数就是把任意长的输入消息串转换成固定长度输出串( 叫做h a s h 值、 消息摘要、指纹) 的一种函数。数据的完整性是认证消息、检验数据是否被篡改 的技术，在信息安全中发挥着重要作用，h a s h 函数便是实现这一技术的有效手 段。在一些应用中，仅要求h a s h 函数有单向性是不够的，还需要称之为抗碰撞 的条件：要找出两个随机的消息m 和m7 ，使h a s h ( m ) = h a s h ( m ) 满足很难。单向 h a s h 函数还可以按其是否有密钥控制划分为两大类：一类有密钥控制，以 h a s h ( k ，m ) 表示，为密码h a s h 函数：另一类无密钥控制，为一般h a s h 函数。无密 钥控制的单向h a s h 函数，其h a s h 值只为输入串的函数，任何人都可以计算，因 而不具有身分认证功能，只用于检测接收数据的完整性。而有密钥控制的单向 h a s h 函数，要满足各种安全性要求，其h a s h 值不仅与输入有关，还与密钥有关， 只有持有该密钥的人才能计算出相应的h a s h 值，因而具有身份验证功能。在实 际中，单向h a s h 函数建立在压缩函数的想法上。给定一长度为i 的输入，单向 函数输出长为n 的散列值。压缩函数的输入是消息分组和文本前一分组的输出。 输出是到该点的所有分组的散列。该散列值和下一轮的消息分组一起，作为压缩 函数下一轮的输入。最后一分组的散列就成为整个消息的散列。散列的信息应该 包含整个消息长度的某种二进制表示。这种方法能消除有不同长度的消息可能会 具有相同的散列值所带来的潜在的安全问题，这种技术我们称之为m d 强化技术。 将h a s h 函数用于数字签名中有如下好处： 1 可破坏数字签名方案的某些数学性质，如同态性： 2 通过对消息摘要签名取代对消息签名，可以提高签名的速度： 3 签名可以不包括原信息，增强了保密性： h a s h 函数的安全性是指：在现有的计算资源下，找到一个碰撞是不可能的。 安全的h a s h 函数的存在性依赖于单向函数的存在性。根据h a s h 函数的安全水平， h a s h 函数分为强无碰撞的h a s h 函数和弱无碰撞的h a s h 函数。 下面给出几个定义： 定义9 ( 弱无碰撞) h a s h 函数h 称为是弱无碰撞的是指对给定消息x x ，在计算 上几乎找不到x z ，x x ，使h ( x ) h ( x ) 定义1 0 ( 强无碰撞) h a s h 函数h 被称为是强无碰撞的，是指在计算上几乎不可能 找到相异的x 、x ，使得h ( x ) h ( x ) 定义1 1 ( 单向的) 称h a s h 函数h 为单向的，是指计算h 的逆函数h ，在计算上 不可行。 h a s h 函数主要用于完整性校验和提高数字签名的有效性。一个安全的h a s h 函数应该至少满足以下几个条件：输入长度任意；输出长度固定；对每一个给定 的输入值，计算h a s h 值是容易的；h a s h 函数应该是强无碰撞的。 2 4 数字签名形式化定义 普通数字签名方案包括三个过程：系统初始化、签名产生、签名验证。下面 给出数字签名的形式化定义。 1 系统初始化过程 产生签名方案中的基本参数( m ，s ，k ，s i g ，v e r ) ，其中： m ：消息集合；s ：签名集合；k ：密钥集合，包括私钥和公钥；s i g ：签名算法集 合；v e r ：签名验证算法集合。 1 6 2 签名产生过程 对于密钥集k ，相应的签名算法s i g k ：m 斗s ，对任意的消息m e m ，有 s = s i g k ( 聊) ，则：j s 为消息m 的签名，将( m ，s ) 发送给签名验证者。 3 签名验证过程 对密钥集k ，有签名验证算法v e r r ：m x s 斗 t r u e ，f a l s e ， 吼力= 仁戮i 嚣 签名者收到( m ，s ) 后，计算v e k ( x ，y ) ， v e t k ( x ，y ) = t r u e ，签名有效：否则，签 名无效。 2 5 符号约定 本文中出现的符号： z 是整数集。 乙= o ，l ，n - 1 ) 是整数模n 集。 乙的乘法群乏= 扣乙i g c d ( a ，n ) = 1 ) 。 ( ) = i 乏i 为欧拉函数，即( ”) 定义为不大于l q 且与n 互素的正整数个数。 | i 表示两个( 二进制) 字符串的联结。 a 。a 表示a 从有限集a 中随机选取的元素。 ( o ，1 ) 7 表示长度为l 的所有二进制字符串。 3 1 引言 第3 章普通盲签名 盲数字签名是具有下列两个特性的普通数字签名：( 1 ) 消息的内容对签名者 是盲的。( 2 ) 在签名被接收者泄漏后，签名者不能追踪签名。 参照文献 4 给出的盲签名定义，可以给出盲签名的形式化定义如下： 定义盲签名方案是一个8 元组p = m ，s ，a ，k ，吼，q ，r ，其中： m 是消息( 明文) 空间：s 是签名空间；是随机消息空间；k = k 。x k a 是密钥 空间，其中疋是公钥空问、髟是私钥空间；y 是方案中的签名者；吼是签名请 求者集： q 是多项式时间算法：输入随机字符串x ，构造私钥k ae k a 和相应的 公钥k e 疋； a 是多项式时间盲化算法：输入消息l n m ，随机盲化字符串五、公 钥也k ， ( 5 ) ，h 是单向h a s h 函数，占a ，构造盲消息 m o ( m ， ，k e ， ( 占) ) m ； y 是多项式时间签名算法：输入盲消息m o ( m ，丑，k e ， ( 巧) ) m 、私钥 k a ，随机因子s ，构造盲签名j = y ( m ，巧，占) s ； 是多项式时间脱盲算法：输入盲签名s y ( o ( m ，丑，疋， ( d ) ) ，k a ，巧) s 、随 机盲化字符串旯，提取m 的签名s = 妒( s ，五) ； f ：m x s x 蜒j t r u e ，f a l s e ) 是多项式时间验证算法：输入消息签名对( m ， s ) 、公钥也k ，确定是否是消息m 的有效签名。 3 2 基于因子分解问题的盲签名方案 3 2 1r s a 签名方案 设m = s = z e ，选取两个大素数p 和q ，令r l = p q ，选取e ，使得g c d ( e ，庐( ”) ) = 1 计算d ，以满足e d s l m o d ( ( p 一1 ) ( g 1 ) ) k = ( ”，p ，q ，e ，d ) ，签名者的公钥是( n ，e ) ， 私钥是( 1 3 ，q ，d ) 签名者对明文m 签名：y = s i g ( m ) = r o o d n ，m 乙 接收者用公钥验证签名：v e r ( m ，y ) = t r u e 甘m 2 y 。m o d n 迄今人们尚无法“证明”破解r s a 系统等于因子分解，但一般“相信” r s a 系统的安全性等价于因子分解。即若能分解因子n ，即能攻破r s a 系统：若 能攻破r s a 系统，即能分解因子1 3 3 2 2 盲r s a 签名方案 假定采用3 2 1 节r s a 各参数，a 1 i c e 为了从b o b 处得到关于消息m 的签名， 选择一个随机数r ( 盲因子) 和b o b 的公钥( n ，e ) 对消息m 盲化： 历= m r 。m o d n b o b 收到i l l 后用密钥d 产生签名亨= ( 历) 4 m o d n a l i c e 通过计算 静= ( m r 。) 4 ，= m 4 = s r o o d n 获得b o b 关于i n 的签名s s 有效性可通过 s 。= 聊m o d n 验证。 c h a u m 提出的方案与上述方案类似，只是在盲化消息m 时，不是直对i l l 盲化， 而是对m 的h a s h 值进行盲化，即历= h ( m ) r 8 m o d n ，厅是单向h a s h 函数：验证 阶段：的有效性可通过：s 。；h ( m ) m o d n 来验证 3 3 基于u p 的盲签名方案 设1 3 是素数，g g f ( p ) 是本原元，那么在有限域g f ( p ) 1 - 求解离对数问题 y = g 。m o d p 是数学上的难题。e i g a m a l 签名是1 9 8 5 年e i g a m a l 等人提出的， 它是基于离散对数问题( d l p ) 且主要是为数字签的目的而设计的，是继r s a 之后 最著名的数字签名方案，其修正形式被美国n i s t 作为数字签名标准d s s 3 3 1 基本e i g a m a l 数字签名 系统参数：大素数p ，模p 的本原元g ，使得求离散对数不可能。 私钥：签名者a 任选一整数x ，l x p 一1 。 公钥：a 求出y = g 。m o d p ，y 为其公钥。 签名：对明文m ，l 聊p 一1 ，a 任选一整数k 满足( ( k ，p - 1 ) = 1 接着a 求出签 名( r ，s ) 满足： ，= g m o d p m = x f + k s m o d ( p 一1 1 ( 3 - 1 ) 验证：验证者b 验证下式是否成立： g ”= y ，。m o d p ( 3 - 2 ) 若正确，则( r ，s ) 为r f l 的合法签名，否则为非法签名。 安全性分析及讨论： ( 1 ) 本签名系统的安全性基于求离散对数的困难问题，若能求离散数，则由 y 和g ，可求出b 的密钥x ，本系统就不安全。 ( 2 ) 若敌方欲伪造一合法签名，其任选r 或s ，欲求出s ( 或r ) 满足( 3 2 ) 式， 则面临求离散对数问题。 ( 3 ) 敌方已获得一明文m 及签名( r ，s ) ，欲由( 3 一1 ) 式求出x 。因( 3 - 1 ) 式有两 个未知数x 和k ，此时无法求出x ；但若a 用相同k 签名两次，即m 1 、m ：的签名 为( r ，s 。) 和( ，s ：) ，则敌方可由( 3 一1 ) 式求联立方程组： 州i = x r + k s lm o d ( p 1 ) m 2 = x r + b 2 m o d (