（应用数学专业论文）数字签名及其在信息与通信安全中的应用.pdf

摘要 数字签名及其在信息与通信安全中的应用 专业：应用数学 博士生：高崇志 导师：李磊、姚正安 摘要 数字签名的概念，是由r i v e s t 、s h a m i r 和a d l e m a n 提出的。当一方( “签名 者”) 对某段消息签名以后，数字签名协议可以确保其他方( “验证者”) 能够确 认这个事实。数字签名不仅是密码学中一个非常重要的概念，它也是许多安全协议 的重要组成构件。 本论文研究了几种特殊的数字签名以及它们在信息及通信安全中的应用。首 先，我们研究了两种多用户间的签名一环签名和多重签名。对环签名，我们统一 了计算模数，使其能不经预处理就能在同一个域上进行运算。对于多重签名，为了 满足各成员间不同的安全性要求，论文引入了带不同安全级别的方案。 第四章则讨论了签名系统的同态性。可以看到，现有定义中同态签名系统的不 可分辨性在大多数情况下是不必要的。因此，论文引入了严格同态与广义同态两个 概念。在广义同态的定义中，剔除了针对同态签名系统的不可分辨性要求。m i c a l i 和r i v e s t 在2 0 0 2 年提出了一种特殊的同态签名系统一传递性签名。传递性签名能 够对传递性图的边进行签名。但是，m i c a l i 和r i v e s t 以及后来对传递性签名的研究 均只给出了针对无向图的传递性签名。怎样构造针对有向图的签名却作为公开问题 遗留了下来。在第四章中，针对有向图，我们给出了满足广义同态性质的传递性签 名系统。 保证数据完整性是数字签名的个重要应用。在第五章中，我们首先研究怎么 用单向陷门h a s h 函数构造在线离线签名。现有的在线离线签名在离线阶段均需 要进行普通的签名运算。在新方案中，我们不仅提高了签名安全性，而且还去除了 进行普通签名运算的要求。从而使签名效率提高了约一倍。基于新的在线n 线签 名方案，我们构造了对实时数据流的认证协议，以确保数据流的完整性。 关键词：数字签名，环签名，多重签名，同态签名系统，传递性签名，在 线离线签名，数据流的认证。 第i 页共9 7 页 d i g i t a ls i g n a t u r e s a n da p p l i c a t i o n st oi n f o r m a t i o na n d c o m m u n i c a t i o ns e c u r i t y m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：c a o c h o n g - z h i s u p e r v i s o r ：l il e ia n dy a oz h e n g a n a b s t r a c t d i 西t a ls i g n a t u r e s ，i n t r o d u c e db yr i v e s t ，s h a m i ra n da d l e m a n ，a r eb a s i ct o o l s w h i c he n a b l eo n ep a r t y n ，满足 v ( n ) 1 尸( 礼) ， 则称函数v ：n r 是可忽略的。 定义2 3 我们说一个问题p 是困难的，是指对任意的多项式时间算法f ， 它能够成功解决问题p 的概率a d v ( f , p ) 是可忽略的。我们通常也会说求解出 问题p 是“不可行”的。 第1 1 页，共9 7 页 2 2 对称密码系统和公钥密码糸境 定义2 4应答机( o r a c l e ) 这个概念，是相对于一个提问者a 来说的。 我们说d 是一个应答机，是指提问者a 可以对应答机提问，而应答机则把正 确答案告诉给提问者。如果一个提问者可以提问并得到正确答案，则我们称这 个提问者可以访问应答机。对于提问者来说，应答机相当于是一个黑匣子，它 将提问作为输入，而将正确的答案作为输出。提问者除了得到答案外对应答 机的内部构造或内部算法一无所知。 例如，设w 是一个固定的整数值，0 是判断一个整数是否等于w 的应答 机。那么，每当提问者a ( 她预先对数值w 一无所知) 提供一个数值z 让。 回答时，d 就回答1 或0 来分别代表”等于”或“不等于”。提问者4 除了得 到这些答案外，她对。的内部构造( 在这里，实际上就是对数值叫的认知) 本身是一无所知的。 如果a 是一个算法，当算法4 可以访问应答机p 时，我们就把算法a 记 做a o 。 注：有些资料也将o r a c l e 直译为“预言规”。 2 2 对称密码系统和公钥密码系统 2 2 1 对称密码系统 在对称密码系统( s y m m e t r i cc r y p t o s y s t e m ，也称p r i v a t e k e yc r y p t o s y s t e m ) 中，通信的两方或者多方之间拥有共同的密钥。从而达到对信息进行保密的目 的。经典的对称密码算法有t w o f i s h s c h 9 8 、d e s f i p 7 6 、a e s h u b 9 8 等。 定义2 5 一个对称密码系统是一个由算法构成的三元组( g ，e ，d ) ，其 中， 一密钥生成算法g 是一个生成密钥的概率算法。它在多项式时间内，输出密 钥。 一加密算法_ e 是一个对信息进行加密的概率算法。它在多项式时间内，以密 钥k 和明文m 为输入，输出个密文c 。对明文m 进行加密的过程用符 号c 卫e ( m ) 来表示。 解密算法d 是一个确定性算法，它对一个密文进行解密。解密算法以密钥k 和密文c 为输入，输出相对应的明文m 。这个过程用符号m d 席( c ) 来表 示。 第1 2 页洪9 7 页 第二章密码学的背景知识 一个对称密码系统有一个明文空间：m 。它是所有定长的字符串所组成的集 合。也就是说，存在有一个正整数k ，使得2 , 4 = o ，1 ，。一个对称密码系统 还必须使得对v m m ，有d k ( e k ( m ) ) = m 。 塾墅窒堡垂丝笪窒全丝： 设( g ，e ，d ) 是一个对称加密系统，k 是一个选定的密钥。令0 。和o 、是 两个应答机。其中，应答机瓯如下工作：当送给它消息m 时，它随机选择一 个和m 相同长度的字串x ，运行加密算法得到e = e k ( x 1 ，最后输出c 作 为答案。而应答机0 1 如下工作：当送给它消息m 时，它直接运行加密算法得 到g e k ( m ) ，最后输出a 作为答案。我们称0 0 为随机应答机，而称o 。为 真实应答机。 定义2 6 设5 = ( g ，e ，d ) 是一个对称加密系统，令a 是一个分析算 法。算法a 能够访问应答机d o 或者o 。之一，它的输出是“0 ”或者“l ”。令 s u c c r e a l ( 5 ，a ) = p r a 。1 _ 1ik 墨g ) s u c c r 。d ( s ，a ) = p r a 。= 1 | k 墨g ) 称上述两式之间的差为分析算法a 的“优势”( a d v a n t a g e ) ： a d v ( 5 e ，a ) d = e fs u c c r e a l ( s e ，a ) 一s u c c d ( s e ，a ) 当算法a 最多运行时间t ，最多对应答机提q 个问，并且所提问题( 即消 息m ) 最多只有卢个不同的长度的情况下，我们把a 的“优势”记作： i n s e c ( 8 ；t ，g ，p ) d = e fm a x a a d v ( s e ，a ) ) 变量a d v ( s ，a ) 代表什么意思呢? 直观意义上来说，它就代表算法a 能够对加密系统5 分析成功的可能性。当a d v ( s 占，a ) 等于1 时( 也就 是s u c c a 。l ( 酣，a ) = 1 ，并且s u c c r a 丑d ( s e ，a ) = 0 ) ，即代表算法a 能够正确 地判断哪一个应答机是真实应答机( 也即判断出哪一个是真正的加密算法) 。 而当数值a d v ( s 3 ，a ) 越小甚至接近于。时，即代表分析算法a 无法判断哪一 个应答机是真正的加密算法。 定义2 7 如果说一个对称加密系统& ! = ( g ，e ，d ) 是安全的，是指对任 意一个分析算法a ，以及多项式长度的t ，口，肛，i n s e c ( $ $ ；t ，g ，) 是可忽略的。 第1 3 页、共9 7 页 2 2 对称密码系统和佥钥密码系统 附注：我们可以看到，如果说一个对称加密系统s 占= ( g ，e ，d ) 是安全 的，那么加密算法e 一定是一个概率算法。但是，以上我们所提的基本的对 称加密算法t w o f i s h 、d e s 、a e s 也被称作是安全的，这是因为这些算法在 使用时，总是和某些技术相结合使用的。这些技术包括使用安全的运算模式 ( s e c u r em o d e so fo p e r a t i o n ) 或者在确定性算法中加入“状态”这一参数， 使之成为概率性算法等等。 2 2 2 公钥密码系统 公钥密码系统( p u b l i ck e yc r y p t o s y s t e m ) 的思想是由w h i t f i e dd i f f e 和m a r t i n h e l l m a n 在1 9 7 6 年首次提出的p h 7 6 b 。不同于对穗密码系统的是，公钥密码系 统将加密密钥和解密密钥区分开来。从而使一个人在具有加密的能力的同时， 却不一定具有解密的能力。1 9 7 8 年，r i v e s t 、s h a m i r 和a d l e m a n 提出了第一个 单向陷门函数o n e - w a yt r a p d o o rf u n c t i o n l ，构造了r s a 公钥密码系统。公钥密 码系统的思想及核心是利用单向陷门函数。我们说一个函数i ( x 1 是单向陷门 函数，是指它满足如下要求： 1 函数i ( z 1 有个陷门丁。 2 若知道白变量z ，则计算，( z ) 是容易的； 3 若知道陷门r 和函数值，( z ) ，则计算出z 的值是容易的。 4 若不知道陷门r ，则由函数值i ( x ) 计算出z 是不可行的。 坌堑窒堡垂丝笪室竖： 我们在这里严格给出公钥密码系统的定义，更详细的讨论，请参 见i b o o l l 。 定义2 8 一个公钥密码系统是一个由算法构成的三元组( g ，e ，d ) ，其中 密钥生成算法g 是一个生成密钥的概率算法。它在多项式时间内，以安全参 数1 为输入，输出密钥对( e ，d ) 。其中e 叫做公钥，d 叫做私钥。( 我们用符 号( e ，d ) g ( 1 。) 来表示密钥对( e ，d ) 由算法g 产生。) 加密算法e 是一个对消息进行加密的概率算法。它在多项式时间内，以安 全参数l 、公钥e ( 由a ( i ) 产生) 和消息m 卧 r s a ( z ) = z 8r o o dn r s a 假设：v 概率多项式算法a ，| 一个可忽略的函数e ，s t p r a ( r s a ”，( z ) ) = 。lp ，口墨 o ，1 ) 。，e 墨z ；( 。) ，。墨z ：) e ( ) 命题2 1 当r s a 假设成立时，7 醛a 是一个单向陷门函数族。 基于r s a 假设，则可以利用冗5 4 单向陷门函数族构造r s a 公钥系统： 指标集，定义同上，i = n = p q ；l p l = 吲) 。我们先计算出满 足方程e d = 1 m o d 妒( n ) 的数d ，则对应于指标为 的函数，陷门就 为k ，= d 。加密函数为： r s a 。，。) ( t ) = z 。r o o dn 解密函数为： r s a ：d ( c ) = c 4 m o dn 除了r s a 公钥密码系统外，还有其他类型的公钥密码系统，如e 1 g a m a l 公 g a m s 5 】和m c e l e c e 公钥系统 m c e 8 7 等。 直观上，我们要求一个公钥密码方案有如下安全性 ( 1 ) 分析者由公钥不能得到私钥，这是最基本的一个要求。 ( 2 ) 分析者由密文及其他公开的信息( 如公钥等) ，不能得到明文。 ( 3 ) 更进一步地，分析者不能从密文得到任何有用的信息，哪怕只是明文的一 小部分。 第1 6 页，共9 7 页 第二章密码学的背景知识 f 4 1 从已有的通信记录中，分析者不能得到任何有用的信息。例如，即使发送 方发送的两段密文代表的是相同的明文信息，分析者也能够判断出两段信 息的内容相同。进一步地，我们希望即使以前加密的内容被公布分析者 破译出当前密文的概率也不会增加。 因此，我f f 期望达到这样的效果：明文就像一张写有信息的信纸。加密的 过程如同将信纸封在了不透光的信封内。每个人都可以将信纸封在信封内，但 是只有合法的收信者才可以打开指定的信封。下面是用严格的数学语言来描述 这样一个模型，其它等价的安全性定义请参见f b g o l l 。 公钥密码系统的安全性：多项式时间的不可分辨性。 定义2 9 我们说一个公钥系统( g ，e ，d ) 是多项式时间内不可分辨的，是 指对任意的多项式时间的算法a 、任意的多项式q ，以及足够大的， p r a ( 1 k , e ，m o ，m l ，c ) = ml ( e ，d ) 墨g ( 1 ) ；7 n 置( m o ，? t z l ) ；c 旦e ( e ，m ) 1 2 + 1 q ( k ) 也就是说，不存在这样一个算法，它能够找到两个信息m 。、m 1 ，对于c e ( e ，m o ) ue ( e ，m 1 ) ，这个算法能够在多项式时间内判断出c e ( e ，m o ) 还 是c e ( e ，m 1 ) 。 从直观上，一个加密算法具有多项式时间内的不可分辨性，就是指在多项式时 间内，分析者找不到这样的两个信息，它们的密文形式能够被分析者分辨出 来。对上面的信纸信封模型来说，就是当两张信纸被信封分别装上以后，分 析者无法在多项式时间内分辨出两个信封之间的差别。 附注： 1 如果加密算法e 是确定性算法，我们立即可以看到e 不满足以上的安 全性定义。因为对给定的，m o ，m 1 和c ，( m o ) ，( m 1 ) ，a q 很容易验 证c = ，( m o ) 还是c = ，( m 1 ) 。所以，跟对称加密算法样，人们在应用公钥 密码基本算法( 例如，r s a 公钥密码系统) 的时候，总是和某些技术( 使 用安全的运算模式、将确定性算法转化为概率算法等) 相结合起来一起使 用的。 2 文献 b g o i 使用单向陷门函数和困难核( h a r d c o r ep r e d i c a t e s ) 构造了一种安 全的概率加密算法，并且严格证明了，它满足不可分辨性安全。 第1 7 贾，共9 7 页 2 , 3 数字签名 2 3 数字签名 2 3 1 背景 数字签名( 也称电子签名) ，顾名思义，是以数字的形式实现我们传统意义 上的签名所能达到的功能。我们的政治、军事、外交等的文件、命令和条约； 商业中的契约以及个人之间的书信都需要进行签名，以便在法律上认证、核 准、生效。随着电子计算机及互联网的出现，人们的文件已经数字化，不再是 写在纸上的文字。文件传输方式也由传统方式改变为直接拷贝，网上传输的方 式。因此，我们需要将签名也数字化，以确保信息的完整性和不可抵赖性。 一个签名算法至少应该实现以下目的： 假设a 和b 是由用户构成的集合( 集合内可以仅是一个人，也可以是多 人) 。签名算法应该满足： 1 集合a 内的用户可以对所发的消息附加上一段信息，以让人确信消息是他 所发。我们把这个行为称为“签名”。仅有集合a 内的用户可以用团体a 的名义签名。我们称集合a 为签名者团体，集合a 内任一用户的签名为团 体a 的签名。 2 集合且内的用户可以由签名确认消息是由团体a 内的成员发送的。我们把 这个行为称为对团体a 的签名进行“验证”。仅有b 内的用户可以验证。 我们称集合b 为验证者团体。 实际生活中的手写签名，签名者团体a 内只含一个人，即：只有自己才能 以自己的身份进行签名。这是由每个人都有自己的笔迹特征所决定的。验证者 团体则不只含一个人，它由任何有能力验证签名的人( 如公安机关，笔迹专家 等等) 组成。另外，a 和b 也可以是同一个实体。例如，军方内部需要进行 通信，但是要对通信内容加上附加信息以保证信息确实是军方自己发出的。这 时，签名者团体a 和验证者团体b 均只含一个实体，即军方本身。 签名算法可以由对称加密或公钥加密算法来实现。基于对称加密的签名算 法，如果发送方和接受方共同拥有密钥s ，则发送方可以用c = e ( m ) 作为消 息m 的签名。接受方则验证风( m ) 是否等于m 即可。值得注意的是，这种体 制只是用在一个团体内部成员( 成员都拥有共同的密钥s ) 之间的通信。目的 是让接收者确信消息确实是由团体成员发送的。但是却不能让第三方确信消息 是由合法发送者发送的( 而不是接收者自己产生的) 第1 8 页，共9 7 页 第二章密码学的背景知识 所以，人们通常把注意力集中在满足以下条件的数字签名。它可以由公钥 加密算法实现，我们称之为公钥体制下的签名。 1 只有签名者自身才可以得到合法的签名。 这个条件就蕴含了签名的不可伪造性和不可抵赖性。 2 签名具有可验证性。 出具了消息m 以及对之的签名s 以后，接收者可以向第三方证明签名确实 是由签名者产生的。 附注： l 某些签名定义要求必须能证实签名的时期和时l 司 s t a 9 9 】。这不是基本签名算 法的本质要求。故我们这里没有列出这条性质。 2 某些签名定义要求接受方对已收到的签名信息不能否认，即具有收报认证 功能。这也不是基本签名算法的本质要求，故而也不列出。 数字签名在信息安全，包括身份认证、数据完整性、不可否认性以及匿名 性等方面具有重要应用，特别是在大型网络安全通信中的密钥分配、认证以及 电子商务系统中具有重要作用。 2 3 2 数字签名的概念 我们现在讨论在公钥系统框架下的数字签名。 定义2 1 0 一个数字签名协议是一个由算法构成的三元组( g ，s i g ，w y ) ， 其中 密钥生成算法g 是个生成密钥的概率算法。它在多项式时间内，以安全 参数1 为输入，输出密钥对( p ，s ) 。其中尸是公钥，s 为私钥。( 我们用符 号( p s ) a ( 1 。) 来表示密钥对( p ) s ) 由算法g 产生。) 签名算法s 峙是一个产生签名的概率算法。它在多项式时间内，以安全参 数1 、私钥s ( 由v ( 1 。) 产生) 和消息m o ，1 ) 。为输入，输出一个信 息8 ，我们称s 为消息m 的签名。( 我们用符号ses i g ( 1 。，m ，s ) 表示签名算 第1 9 y i ，共9 7 页 2 3 数字签名 法是一个概率算法，而用s = s i g ( 1 ，m ，s ) 表示签名算法是一个确定性算 法。为简便起见，在不致引起歧义的情况下，我们直接用s s i g ( m ，s ) 或 者s = s i g ( m ，s ) 表示s 是消息m 的签名。) 验证算法v r f y 是一个对签名进行验证的算法。它在多项式时间内，以公钥p 、 一个信息m 以及它的签名s 为输入，输出t r u e 或i a l s e ，分别代表签名是有 效还是无效的。 一个签名协议应该满足v 啼( m ，s ，p ) = t r u e 当且仅当s s i g ( m ，s ) 。( 为简便 起见，我们将直接用v r f y ( m ，s ) 代表验证m 的签名s 。) 一安全性。一个签名协议，它对一个多项式时间的概率攻击算法来说，必须是 安全的。 安全定义有许多种，并且存在不同级别的安全定义，我们将在随后及第3 章 和第4 章详细讨论这个问题。 2 3 3 数字签名的安全性 在本节中，本文给出数字签名的安全性描述。有关数字签名安全性的 严格定义是i 妇o o l d w a s s e r 、m l c a h 和1 虬o 【g m y 8 3 】开始的，其后有进一步的发 展 g m r s 8 a ，b m 9 2 ，n y 8 9 b ，r o m 9 0 ，d n 9 4 】。 对数字签名的攻击类型： i 唯密钥攻击：在这种形式的攻击中，分析者只知道签名者的公钥。也就是 说，他可以验证消息的签名是否有效。 2 已知签名攻击：在这种形式的攻击中，分析者除了知道签名者的公钥外， 还知道一些有效的消息一签名对。在现实应用中，分析者一般都能做到这种 程度的攻击。 3 选择消息攻击：在这种形式的攻击中，分析者可以选择对他有利的消息， 并且让签名者对这些消息进行签名。这种选择可以是基于他以前所获得的 知识( 例如已知的消息，签名对等等) 第2 0 页，共9 7 页 第二章密码学的背景知识 对攻击类型更为详细的描述可以参见【g m r 8 8 b 】- 对数字签名的攻击程度： 我们由低到高地列出对一个签名算法的攻击程度，他们代表了一个分析者 对签名算法的攻击是否成功。 1 存在性伪造：分析者至少可以对一个消息进行签名，而不管这个消息是否 是他自己选择的。 2 选择性伪造：分析者至少可以对他所选择的一个消息进行签名。 3 全局性伪造：分析者虽然无法获知签名者的私钥，但他可以对任何一个消 息进行签名。 4 彻底攻破：分析者可以计算出签名者的私钥。 不同的应用需要不同的安全性定义。有时，人们要求能进行己知签名攻击 的分析者不能进行选择性伪造。而在另一些应用里( 例如签名者为公众服务 者，如公证者) ，则要求能进行选择消息攻击的分析者不能进行存在性伪造。 作为例子，我们对后一种安全性进行阐述。 星全蛙塞竖圭= ；蠢选捶堕童至至自l 进i 重壅壅丝鱼遣 一个数字签名协议是安全的( 分析者在选择攻击下不能进行存在性伪造这 个意义上) ，是指当分析者将签名算法s ；g ( - ) 作为应答机时，他不能在多项式 时间内伪造出他不曾提问过的消息的签名。 严格来说，令b 表示将消息m 映到有效签名s 的一个应答机。令f 是一个 伪造程序。它以签名者的公钥p 作为输入，并且可以访问应答机日。我们将 之记为f 口( p ) 。f 首先进行选择消息攻击，将访问b 而得到的消息一签名对作 为进一步的输入，进而输出一个新的消息签名对。如果这个新的消息是f 从 未对日请求过的，我们则称f 是成功的。 我们要求如果一个签名协议是安全的，则对任意的伪造攻击程序f ，对任 意的多项式q 和足够大的t ， p r ( v r f y ( m ，s ，p ) = t r u e ( p , s ) 兰g ( 1 ) ；( m ，s ) 昌f 8 ( p ) ) 1 q ( k ) 第2 1 页，共9 7 页 24 本章小结 其中，概率的取值依赖于( p s ) g ( i ) ，伪造程序f 内的随机变量以及b 内 的随机变量。 上述安全性定义是针对分析者在选择攻击下不能进行存在性伪造这个意义 上来说的。我们把这个安全性简称为签名协议的“e c 安全性”。 定义2 i i 设= ( g ，s i g ，v r f y ) 是一个签名协议。如果v ( p s ) 一 g ( 1 ) ，v 。一 o 1 ) ，有s i g ( x ，s ) = gjv r f y ( z ，y ，p ) = t r u e ，那么则称签名 协议是完全的( c o m p l e t e ) 。如果签名协议对于某个安全性定义来说是安全 的，那么则称在这个安全性定义下是合理的( s o u n d l 。 2 3 4 r s a 基本签名算法及其安全性分析 在这个小节中，我们来看看基于r s a 密码系统的签名算法，它在e c 安全 性定义下是否安全。 假设r s a 密钥系统的公钥为( n ，e ) ，n 为两个大素数的乘积，e 是与妒( n ) 互素的一个数。私钥d 是满足方程e d = 1r o o d 妒( n ) 的数。对m 签名就是计 算仃d = e fs i g ( m ) = m 8 r o o d 札，验证签名口就是验证矿兰m ( r o o dn ) 。 定理2 1 r s a 签名系统在选择消息攻击下是全局性可伪造的。( 或者： 在已知签名的攻击下，是可存在性伪造的) 。 证明 如果t , 1 和2 是两个消息，则已知它们的签名就可以推出“l m ：的 签名。利用这个事实，我们来构造对r s a 签名系统的攻击。 为了得到消息m 的签名，我们随机选一个数r z ：。m l 和m 2 构造如 下：m 1 磐m rr o o dn ：m 2 d = e fr - 1m o d n 。当我们对r s a 签名系统请求了m 1 和m 2 的签名后，我们就可以得到消息m 的签名。因为m l m 2 = ( m r ) r l = 7 7 a 一 附注：我们似乎已经得到结论，基于r s a 的签名算法是不安全的。但是，请 注意，我们会在第四章重新讨论这个问题。详细请参见部分4 4 的引理4 3 和 引理4 4 。读者请注意，不同的签名协议或者是相同的签名协议用在不同的场 合，其安全性要求是可能完全不相同的。 2 4 本章小结 为使本论文自成体系，在本章中，我们给出了密码学领域内的一些基础 知识；包括对称密码系统、公钥密码系统以及数字签名协议。读者可以参 第2 2 页，共9 7 页 第二章密码学盼背景知识 见 s t i 9 5 ，b c 0 1 等以获得更迸一步的知识。对于基础的有关数论知识，本论文 就不再涉及。感兴趣的读者可以参考n e a lk o b l i t z 所编著的“a l g e b r a i ca s p e c t s o fc r y p t o g r a p h y ”【k o b 9 8 】。 第2 3 页，共9 7 页 第三章多用户的簦名协议一环签名和多重签名 第三章多用户的签名协议一环签名和多重签 名 在一般的签名协议中，签名时只需要签名者a 的私钥鼠，而在验证程序 中则只需对应的公钥r 即可。但是，在某些应用中，签名是需要多个用户共 同参与的 a c j t 0 0 ，s o n 0 1 ，a c j t 0 0 ，a s t 0 2 1 。这种多用户的参与可以分为显式的 参与与隐式的参与。显示的参与意味着在签名过程中，需要用到多个用户的私 钥和多个用户的公钥b o y 9 1 1 。隐式的参与意味着在签名的过程中，需要多人的 公钥，但只需要使用到一个人的私钥 a c j t 0 0 ，r s t 0 1 ，b s s 0 2 1 。例如，在一份 文件需要多个人共同签署才能生效的情况下，就需要利用到多个人显式参与的 签名协议。我们将这类需要多个用户共同参与的签名协议简称为多用户的签名 协议。 本章中讨论两种多用户的签名协议一环签名( r i n gs i g n a t u r e ) 和多重签名 ( m u l t i s i g n a t u r e ) 。 环签名协议( r i n gs i g n a t u r es c h e m e s ) 是一种规定了潜在签名者的范围，但 不揭示出签名者真正身份的签名协议。它是一种隐式的多用户签名协议。也就 是说，签名者只有一个，但签名者在签名的时候除了用到他自身的密钥外，还 要用到其他签名者的公钥。多重签名( m u l t i s i g n a t u r e s ) 是一种多个用户必须 一齐合作才能进行的签名协议。它适用于某些文件需要多个人共同签署才能生 效的情况。多重签名协议是一种显式的多用户签名协议。也就是说，在签名的 时候，需要用到多个用户的私钥。 在本章的第一节中，我们讨论环签名协议。以往的环签名协议中，各个用 户运算使用的模数是不同的，因而在签名的时候，需要进行初始化工作统一计 算模数。同时，每个签名者都必须自己搜索素数以构造自身的密钥。我们将讨 论如何解决这些问题。在本章的第二节中，我们讨论多重签名协议。多重签名 需要多个用户共同签署一个文件。这些用户之间的重要性可能不同( 比如说， 一个公司的法律部会比人事部更重要，因而，法律部的签名就需要有更高的安 全性) 。但是，现有的多重签名方案都假设各签名者同等重要。本文在第二节 中将提出一种带不同安全级别的多重签名方案。 第2 5 页，共9 7 页 3 1 环签名 环签名是一种特殊的群签名( g r o u ps i g n a t u r e ) 。群签名方案由c h a u m 和 v a nh e y s t 在1 9 9 1 年 c h 9 1 首次提出。群签名允许团体的一个成员以团体的名义 进行签名。签名以后，签名者的身份是保密的。除团成员外，还存在有个角 色，称为团体管理者。在必要的时候，团体管理者可以揭示出真正签名者的身 份。群签名具有广泛的应用 c a m 9 8 ，c l 0 1 1 ，例如，一个公司有多个部门，这些 部门都有以公司名义独立签署文件的权利。当一个文件的签署没有必要指明具 体的签署部门的时候，就可以应用群签名的方案。同时，在签名出了问题的时 候，团体管理者可以追查到原始的签署者。因此，群签名可以应用于电子货币 系统、电子选举系统等 l r 0 8 ，c p 9 2 ，c l 0 1 1 。 环签名规定了潜在签名者的范围，但任何人都不能揭示出签名者的真正 身份。环签名的概念是由p d v e s t 、s h a m i r 和t a u m a n r s t 0 1 1 在2 0 0 1 年首次提 出的。它的雏形可以在讨论群签名的相关文献 c h 9 1 ，c a m 9 7 1 中找到。在2 0 0 2 年，b r e s s o n 、s t e r n 和s z y d l o b s s 0 2 提出了带门限方案的环签名。 3 1 1 定义 定义3 1 ( 环签名) 环签名协议里面有一个团体，里面的每个成员都 是可能的签名者。我们把这样的一个团体叫做一个环( r i n g ) ，并把环里面的 第个成员记做a 。每个成员a 对应有一个基本的签名算法s 谵k 以及签名验 证密钥对( 最，鼠) 。其中5 i g k 、r 公开，乳由成员a 女私有。 一个环签名方案由如下的两个子程序构成( 针对成员个数为r 的环) ： r i n g s i g n ( m ，尸1 ，恳，耳，s ，只) ( 签名子程序) 签名子程序以消息m 、所有成员的公钥p 1 ，尸2 ，只以及成员a 。的私钥舅 为输入，输出对消息m 的签名o - 。( 这时，s 为真正签名者的序号。) r i n g v e r i f y ( m ，o ) ( 验证子程序) 验证子程序以消息m 以及对消息m 的签名口为输入，输出t r u e 或者是血括e ， 以判断签名c r 是否为环内成员所签。 一个环签名方案必须满足签名方案的两个基本性质：合理性和完全性。除 此之外，环签名还必须满足匿名性：任何人不能以大于1 r 的概率成功判断出 第2 6 页共9 7 页 第三章多用尸的鍪名1 存议一环签名和多重簦名 真正的签名者。他唯一能做的就是确定签名者是否是环中的成员。 3l2 相关工作 r i v e s t 、s h a m i r 和t a u m a n i r s t 0 1 提出的环签名方案是一种绝对匿名性的环 签名方案。也就是说，即使个分析者拥有无限的计算能力，他也不能揭示出 签名者的真正身份。在此，我们简要介绍一下r i v e s t 、s h a m i r 和t a u m a n 的工 作。 在构造环签名的时候，文献 r s t 0 1 用到了两种技术：构造合并函数 ( c o m b i n i n gf u n c t i o n s ) 和做预处理以统一单向陷门函数族的模数。 盒莛鱼垫堡! 堡b i 坠i 錾坠坠笪q 墅2 ： 一个合并函数g ，。( g l ，y r ) 是这样的一个函数，它以密钥、初始值。为参 数，以 0 ，1 ) 6 中的r 个值y l ，y 2 ，y r 为输入。输出一个值z o ，1 6 。当参数k 和u 取固定值时，一个合并函数应该具有如下性质： 性质31 对于单独的一个输入值来说，合并函数是一个一一映射。 对任意一个s ( 1 s r ) ，如果给定r 一1 个值：y l ，y 。扎玑+ 1 1 ，玑， 则函数晚，。是从输入值玑到输出值。的一一映射。 性质3 2 合并函数针对一个单独的输入是可解的。 对于s 1 ，r ) ， 如果给定了2 ( o ，1 6 以及r 一1 个 值： y 1 ，y s 一1 ，+ _ ，* - 则可以快速地计算出玑 o ，1 b ，使 得晚，。( 1 ，y r ) = z 。 性质3 , 3 如果没有某个单向陷门函数的陷门信息，方程( 3 1 ) 是不可 解的。 g ，。( 9 1 ( z 1 ) ，g r ( x ，) ) = z ，f 3 - 1 ) 其中肌( z ) 是单向陷门函数。 给定方程( 8 - 1 ) 中的k 、”和。，如果一个分析者对某一个g l 不能求逆， 则分析者不能从方程( 3 一1 ) 中求解出z 1 ，z ，。 例如，5 勰 r s t 0 1 给出了一个合并函数： q ，”( y l ，y r ) = 取渤。最一1 0 最( o 风( 9 1 0 “) ) ) 第2 7 页，共9 7 页 这里毋是以k 为密钥的基本对称加密函数。可以证得，q 。满足以上三个条 件，并且可以由如下式子得到玑： y 。= 巧1 ( 9 州o 巧1 ( 计。巧1 ( z ) ) ) o 既( 蜘一1o 风( g lo 口) ) 在文献 r s t 0 1 1 中的环签名中，每个成员都拥有各自的单向陷门函数。这就引 出了一个问题：这些单向陷门函数都是在不同的域( 或者说是模数) 上运算 的。我们来看文献 r s t 0 1 是如何把不同的单向函数统一到一个域上的。 文献 r s t 0 1 1 中提供了两种环签名的方案一r s a 版本的环签名方案和r a b i n 版本的环签名方案。以下以r s a 版本的环签名为例，看是如何把r s a 单向陷 门函数族统一于同一个域上的： 成员a ( 1 tsr ) 生成他的r s a 密钥= ( 啦，p 。，q i ，龟，d i ) 。其中，只= ( n ，e t ) 是他的公钥，s 一慨，吼，哦) 是他的私钥。 在域琢。上的单向陷门函数五定义如下： ( 。) = z “( r o o d n 。) 而 的逆， _ 1 在已知私钥的时候可以计算： ， 1 ( y ) = y 畦= x ( m o d 吼) ， 这些r s a 单向陷门函数在不同的域z 。，上。取6 使得2 b 大于所有的吼，然 后可以将 扩展成吼，使得m ( 1si r ) 在共同的域( o ，1 ) 6 上。 吼： o ，1 ) 6 一 o ，1 ) 5 如下定义： 对m 0 ，1 ) 6 ，选取非负整数t t 、r i 使得m = 屯m + n 并且0sn m 。 it ；吼+ ， ( r i ) i f ( t ，+ 1 ) r k 2 6 ， 9 1 ( m ) = 【。 幽。， 这样，就将 扩展到了共同的域上。 圣簦名查塞笪垦s 蝰奎： 给定待签的消息m ，签名者的私钥最，以及环中所有成员的公 钥p 1 ，p 2 ，只。签名者按如下方式计算环签名： 第2 8 页，共9 7 页 第三章多用户的签名协议一环签名和多重签名 1 签名者计算h ( m ) ，并将之作为对称密钥k ： k = ( m ) ， 其中 ( ) 是一个h a s h 函数。 2 签名者在 o ，l ，6 中随机选取一个初始值“e 3 签名者独立地为其他环的成员选取r ( 0 ，1 ) 6 ( 1 i r 算 玑= 吼( 飘) 4 。签名者求解关于未知量讥的方程： q 。( 1 ，y 2 ，蚧) = u ， 由合并函数的定义，当给出了合并函数其他的输入时， 了，并且可以被快速地解出。 5 签名者由陷门信息冀求得函数吼的逆： 岛= 酊1 ( y 2 6 对消息m 的签名即为如下的( 2 r + 1 ) 元组： ( p 1 ，p 2 ，只；口；z l ，x 2 ，) i s ) ，并且计 玑的值就被确定 如果要验证消息m 的签名 ( p l ，最，只；口；o b z 2 ，z ，) 验证者计算c h ( 毗。( f l ( x 1 ) ，2 ( 她) ， ( z ，) ) 。如果计算值等于u ，则接受，否则 拒绝。 文献 r s t 0 1 i 还提出了环签名的另外种方案一r a b i n 版本的环签名方案。 与r s a 版本不同的是，它的单向陷门函数是基于r a b i n 公钥系统 r a b 7 9 b 1 。 在2 0 0 2 年，b r e s s o n 、s t e r a 录l s z y d o b s s 0 2 提出了门限方案的环签名方案。 在以上方案中，为达到真正的匿名性，每个环成员都必须自己独立生成密 钥对。也就是说，不存在一个可信任中心做诸如生成密钥和分发密钥的工作。 例如，在r s a 版本的环签名方案中，每个环成员都需要搜索出两个大素数而 生成m ( 从而使n ，是这两个大素数的乘积) 。然后，再根据t t 。生成他她的私 钥与公钥。显然，这些初始工作需要大量的计算。并且为使模数相同，每个签 名者在签名的时候，都需要做额外的准备工作。类似的情况也会出现在r a b i n 版本的环签名方案中。 第2 9 页，共9 7 页 3l 环签名 为了使环签名一开始就基于相同的模数，并且使环中的各成员不必自己搜 索素数，我们提出了基于离散对数的环签名方案。 3 1 3 基于n y b e r g - r u e p p e l 签名方案的环签名 为达到在一个共同的域上计算的目的，我们注意到r s a 公钥系统不能满足 这样的要求。我们也注意到，利用一般的基本签名算法来构造单向陷门函数也 是不可行的。例如，我们不能用e i g a m a l 签名方案 g a i n 8 5 来构造单向陷门函 数。为达到这个目的，我们必须利用有这样性质的基本签名方案：任何人都可 以生成可以被验证程序接受的”假”签名，而只有拥有私钥的用户才可以针对他 自己选择的消息计算出”真”的签名。 考虑n y b e r g - r u e p p e l 签名协议 n r 9 3 b ，我们可以看到它满足以上要求。凶 而可以被用为构造单向陷门函数。进而应用于环签名方案中。以下我们就来描 述n y b e r g r u e