（计算机系统结构专业论文）数字指纹协议的研究与应用.pdf

上海交通大学硕士学位论文 摘要 随着电子商务的发展，以无形的数字格式作为多媒体产品的发布 l 形式将成为i n t e r n e t 上的主流方式。与此同时，就带来了知识产权的 保护问题。由于软件产品的易拷贝性，对软件产品( 如j p e g 、g i f 图像，应用程序，各种文趟皇至2 瑚盗版就变得异常容易，因此会大大 x 勺 打击发布商的积极性0 数字指纹协议的研究就是为了从密码学的角度 提出能够有效的追查非法拷贝源的方法，在一定的前提下可以应用于 各种类型的软件产品( 图像、文档等) 。其基本思想是类似人类手指 指纹的作用，在分发给每个软件产品购买者的产品拷贝中加入唯一的 “指纹”，当产品生产者发现侵权行为后，通过这一“指纹”来跟踪 产品非法拷贝的源头，对盗版者进行指控，从而达到版权保护和威慑 的作用。本文将简要介绍数字指纹协议的发展历史，简述和分析主要 的一些数字指纹协议体系，并对数字指纹协议未来的研究发展方向和 应用前景进行展望。 关键字 数字指纹协议、可视密码、版权保护、安全两方计算、比特承诺、公 一一k 。、_ j 一一 钥 塾主! ! 竺塑：堡塑塑塞兰壁旦一 a b s t r a c t w i t ht h ed e v e l o p m e n to fe c o m m e r c e ，d i g i t a lp r o d u c th a sb e e nt h em a i n f o r m a to fm u l t i m e d i ap r o d u c to nt h ei n t e m e t a tt h es a m et i m e ，t h e p r o b l e mo fc o p y r i g h tp r o t e c t i o nh a sg a i n e dm u c h a t t e n t i o n b e c a u s eo f t h ec h a r a c t e rt ob ec o p i e de a s i l y , t h es o f t w a r ep r o d u c ts u c ha sj p e go r g i fi m a g e s ，a p p l i c a t i o n sa n dd o c u m e n t sa r eb e i n gc o p i e di l l e g a l l ye v e r y d a y t h i s d o e sh a r mt ot h em e r c h a n t s b e n e f i t t h eg o a lo fd i g i t a l f i n g e r p r i n t i n gp r o t o c o l i st o s t u d yam e t h o db a s e do nc r y p t o g r a p h yt o t r a c et h es o u r c eo f i l l e g a lc o p y ，w h i c h i nc e r t a i nc o n d i t i o n sc a nb ea p p l i e d i na l lk i n d so fs o f t w a r ep r o d u c t t h eb a s i ci d e ao fd i g i t a lf i n g e r p r i n t i n g ； l i k et h ef i n g e r p r i n to fh u m a n b e i n g ，i st oe m b e d a nu n i q u e ”f i n g e r p r i n t ” i n t oe a c hc o p yo ft h ep r o d u c ts e n tt ot h eb u y e r w h e nf i n d i n gt h ei l l e g a l c o p nt h em e r c h a n tc a nt r a c et h es o u r c eo fi t ，w h om a y b e i sad i s h o n e s t b u y e rc a l l e dt r a i t o r , a c c u s et h et r a i t o r s o t h em e r c h a n tc a np r o t e c th i s c o p y r i g h t t h i sp a p e r w i l li n t r o d u c et h eh i s t o r yo fd i g i t a lf i n g e r p r i n t i n g p r o t o c o la n d d i s c u s ss o m eo f t h ei m p o r t a n t p r o t o c o ls c h e m e s k e y w o r d s f i n g e r p r i n t i n gp r o t o c o l ，v i s u a lc r y p t o g r a p h y , c o p y r i g h tp r o t e c t i o n ， s e c u r e2 - p a r t yc o m p u t a t i o n ，b i tc o m m i t m e n t ，p u b l i ck e y h 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密囱。 ( 请在以上方框内打“”) 学位论文作者签名：数浩 日期：州嘭年土月盯日 指剥撇：璐川) 日期：i ) ；年3 月zf 日 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：友硅 日期：炒，年2 月矽日 上海交通大学硕士学位论文 第一章绪论 随着电子商务的发展，以无形的数字格式作为多媒体产品的发布形式将成为 i n t e m e t 上的主流方式。与此同时，就带来了知识产权的保护问题。由于软件产 品的易拷贝性，对软件产品( 如j p e g 、g i f 图像，应用程序，各种文档等) 的 盗版就变得异常容易，因此会大大打击发布商的积极性。从目前的技术研究来说， 在开放环境下要严格防止非法使用者的侵权拷贝是不太可行的。主要的研究方向 集中在如何有效的追查非法拷贝源，即当有人在购买了正版的软件产品后主动向 其他人非法提供产品，在这一拷贝被发布商发现时，发布商能够追查到这一份产 品拷贝的原始购买者以向这个非法盗版者提起诉讼( 正版购买者应保护自己的产 品拷贝不被其他人盗取) 。这一类相关技术中比较主要的有数字水印技术、指纹 协议体系等。 1 1 、数字指纹协议的定义 数字水印技术研究主要关注如何一个算法在数字产品( 主要针对数字图像) 中嵌入一串信息( 水印) 并能够完整的检测恢复。这一信息可以是发布商的名称， 也可以是任意的有特定意义的b i t 串。水印嵌入的要求是不可见性、鲁棒性，还 要求能抵抗一定的主动攻击。 仅有水印嵌入检测算法是不足以实现版权的保护，我们需要一个完整的保护 协议来规范商家和购买者之间的交易行为。既要保护商家的版权不受侵害，也要 保护诚实的购买者的合法权益，因此，人们提出了指纹协议的概念。 指纹协议有比较大的适应性，在一定的前提下可以应用于各种类型的软件产 品( 图像、文档等) 。其基本思想是类似人类手指指纹的作用，在分发给每个软 件产品购买者的产品拷贝中加入唯一的“指纹”，当产品生产者发现侵权行为后， 通过这“指纹”来跟踪产品非法拷贝的源头，对盗版者进行指控，从而达到版 权保护和威慑的作用。用指纹协议来进行版权保护的思想最早是由n e a jr w a g n e r 在1 9 8 3 年 w 8 3 所提出的，后人在此基础上从不同的方面提出了各种实 际的方案，如基于数字水印的指纹协议，基于密钥分发安全的t r a i t o r - t r a c i n g 协 议等等，本文将对这些协议体系作详细的介绍。 1 2 、数字指纹协议的发展历程 用数字指纹来保护数字产品的思想最早是由n e a lr w a g n e r 于1 9 8 3 年提出 的a 1 9 9 4 年，c h o r 等 c f n 9 4 提出了第一个具体的用于广播加密( b r o a d c a s t i n g e n c r y p t i o n ) 的协议，其中的思想成为后来的些新的协议和改进的协议的基础。 1 9 9 5 年，b o n e h 和s h a w 【b s 9 5 提出了基于标记假设( m a r k i n g a s s u m p t i o n ) 的指 数字指纹协议的研究与应用 纹协议或称之为基于数字水印的指纹协议，其目的是使指纹协议可以应用到更一 般的数字媒体形式中去。之后p f i t z m a n n 等人 p s 9 6 、p w 9 7 a 提出了非对称的概 念，从公平性的角度对以前的协议做了改进。而后又有人提出了门限指纹协议 【n p 9 8 、动态指纹协议 f t 9 9 】、匿名指纹协议 p w 9 7 b 、p s 9 9 、c o o 、d 9 9 等一系 列从不同角度改进的协议变体。在1 9 9 9 年，b o n e h 等人在【b f 9 9 一文中提出了 用公钥体系实现的指纹协议，使针对广播加密的指纹协议从概率可检测性进步到 了确定型可检测性，这是指纹协议研究发展中的又一大重要里程碑。 1 3 、数字指纹协议与现代密码学 数字指纹协议中用到了大量的现代密码学原理，从t r a c t o rt r a c i n g 协议中的 对称加密、概率性检测出盗版者，到非对称指纹协议中用到的数字签名、零知识 证明、比特承诺，再到公钥t r a c t o rt r a c i n g 协议中的公钥体系、d e c i s i o n d e f f i e h e l l m a n 问题，以及所有指纹协议中都涉及到的编码理论。可以说，整个 指纹协议的发展过程包含了现代密码学中的一大部分内容，许多密码学原理的最 新进展都作为了指纹协议提高安全性和有效性的基础。 1 4 、本文章节安排 第二章我们较系统的介绍了现代密码学的基础概念和原理，先介绍了作为密 码学基础的现代代数学和数论问题，其中简要说明了在本文中需要用到的离散对 数问题、表示问题和d i f i l e h e l l m a n 问题。随后介绍加密算法、数字签名，最后 阐述密码学协议中经常使用的两项技术一比特承诺和零知识证明。 第三章我们系统地来介绍基本的数字指纹协议。从早期的对称型针对广播加 密体系的t r a i t o r t r a c i n g 协议开始，然后介绍更公平的非对称t r a i t o r t r a c i n g 协议， 之后提出更一般性的适用于普遍多媒体环境的基于数字水印的指纹协议，最后我 们简要介绍一下近几年来对基本数字指纹协议的一些扩展研究，包括门限t r a i t o r t r a c i n g 协议、动态t r a i t o rt r a c i n g 协议、指纹协议的编码属性研究和匿名指纹协 议。 第四章我们来描述确定型检测而非概率型检测的基于公钥体系的数字指纹 协议，我们将从该协议的加密解密方法和检测方法分别进行介绍。 第五章我们将讨论可视密码中的指纹跟踪算法，首先将简要叙述一下可视密 码的基本原理，之后来详细介绍我们构造的具有跟踪能力的可视密码方案。 第六章对全文作了总结和归纳，同时对数字世界中的指纹跟踪这一领域研究 作我们的展望。 上海交通大学硕士学位论文 2 1 、现代代数学 第二章相关的密码学基础 很长时间以来，代数学与数论被认为是纯理论科学。但是，现在它在现代 密码学中有相当重要的地位，很多公开密钥密码体制的安全性的基础是一些数论 问题。本节将回顾现代密码学中重要的代数和数论结论。 2 1 1 、群 设s 是非空集合，+ 是从s s 到s 的二元运算，a + b 表示将+ 作用于元素 口b s 的结果。如果对任意口，b s 都有口+ b = b + d ，则是可交换的。如果对 任意d ，b s 都有( 口+ b ) c = a ( 6 + c ) ，则+ 是可结合的。如果元素e s 对任意 a s 都有e 女口= a e = a ，则e 是单位元。假设p 是单位元，如果元素口，b s 满 足b 十a = a b = e ，则口和b 互为逆元。 定义2 1 1 如果二元运算+ 在集合g 上是可结合的，并且g 包含+ 的单位元， g 中的每含元素都有+ 下的逆元，则称g 关于+ 构成了称为群的代数结构，记为 ( g q ( 简记为g ) 。如果，是可交换的，则这个群是阿贝尔群。如果l g f 是有限 的则g 称为有限群。有限群的元素个数称为群的阶。 定义2 1 2 设( g ，t ) ，( g ，+ ) 是两个群，厂是g g 的映射，如果 ( x ，y g ) ：= ( ，( 工+ y ) = 厂( 石) + ( y ) ) 则称，厂是( g ，+ ) 到( g ，+ ) 的同态，若是双射，则称是( g ，) 到( g7 ，+ ) 的同构。 2 1 2 、数论问题 很多密码体制的安全性依赖于解决些数论闯题( 如大数分解) 的困难性。 如果不存在能够利用有限资源( 时间和存储空间) 解出问题的算法，那么该问题 是难解的。一般，不能证明这样的算法不存在，但是由于没有人找到这样的算法 而可以假设它不存在。较著名的困难问题包括离散对数问题、大整数分解问题及 二次剩余问题等。下面简单介绍候下文要用到的离散对数问题、表示问题和 d i f i l e h e l l m a n 问题。 塑! 塑堡垫鲨盟竺壅兰! ! 望 一 2 1 2 1 、离散对数问题 定义2 1 3 令g 是有限循环群，g 是g 的生成元。元素a g 的离散对数是 一个整数x ( 0 x i g i ) ，并满足口= g 。记为l o g 。口。 离散对数也称为a 的指数。如果g 不是g 的生成元，那么若存在a 对g 的离 散对数，它是满足4 = g 。的最小整数x 。普通对数的一些结论在离散对数中也成 立。假设g = k ) 是阶为n 的循环群，口、b 和c 是g 的元素。则有 l o g ga b l o g ga + 1 0 9 9 b ( m o d n ) 并对任意整数x ，有 l o g pa 。ix l o g ga ( r o o d n ) 如果h 也是g 的生成元，那么， l o g 。h 三( 1 0 9 g ) - 1 ( m o d n ) ，l o g fa 三l o g a ( 1 0 9 g ) 叫( r o o d n ) 定义2 1 4 ( 离散对数问题) 给定有限循环群g ，生成元g 和一个元素a 找至整数x ，0 x 1 g ) 一1 ，滴j f f a = g 。 2 1 2 2 、表示问题 定义2 1 5 令g 是阶为n 的有限循环群，g g 。g 是其不同的生成元。元 素口g 的一个表示是肌元组g l ，一，) ，对所有1 i m ，0 n - 1 ，满足 口= 兀g ? 表示问题是离散对数问题的推广。如果生成元g ，g 。是随机选择的，则找 到同元素的两个不同表示是和离散对数问题一样困难的。 2 1 2 2 、d i 怖e h e l l m a n 问题 定义2 1 6 ( d i f f i e i t e l l m a n 计算问题) 给定有限循环群g ，g 的生成元g ， 两个元素g ”和g ”，找到元素g ”。 d i f f i e h e l l m a n 计算问题和离散对数问题的关系相当密切。如果离散对数问 题可以在多项式时间内解出，则首先计算 4 上海交姬丈学碾士学位论文 “= l o g g g “ 然后计算( g ”) “即可解出d i f f i e h c l l m a n 问题。在某些群内，离散对数问题和 d i f f i e h e l l m a n 问题是计算相当的。 定义2 1 7 ( d i f f i e h a l l m a n 确定问题) 给定有限循环群g ，g 的生成元g ， 三个元素g “、g ”和g ”，确定元素g ”和g ”是否相等。 显然，如果能够解决d i f f i e h e l l m a n 计算问题，d i f f i e h e l l m a n 确定问题也能 解决。一般，假设d i f f i e h e l l m a n 确定问题是难解的。 s h o u p 证明了解决这两个问题的通用算法的复杂度最小是q ( p ) ，其中，对 d i f f i e h e l l m a n 计算问题p 表示群的阶数的最大素因子，对d i f f i e h e l l m a n 确定问 题p 表示群的阶数的最小素因子，但是在这个模型下离散对数问题和 d i f f i e h e l l m a n 问题不是计算相等的。 2 2 、公钥密码 公开密钥加密的概念在1 9 7 6 年d i f f i e 和h e l l m a n 的一篇文章“秘密学的新方 向”【d h 7 6 中才首次提出。他们提出了陷门单向函数的概念，我们知道单向函数 的逆计算是非常困难的，但对于陷门单向函数如果知道了函数的陷门，那么就可 以很容易地进行单向函数的逆计算。例如给定函数f ：a 一b ，该函数可作为 公钥，其陷门( 私钥) 秘密b 可以通过6 = t ( a ) 计算并秘密保存。对消息m a 的 加密就是( m ) ，解密即为厂“沏) ) = 巩。 陷门单向函数不仅用于加密，也用于实现数字签名。例如，对消息m b 的 数字签名为s = f 。( 聊) ，任何人都可用公钥验f f m = ，( s ) 是否成立来检验签名。 2 2 1 、r s a 加密 这里我们简介r s a 密码体制 r s a 7 8 j ，其陷门单向函数基于计算以合数即为 模数的e 次方根的困难性，即r s a 问题的难解性。 加密算法如下：设p 和q 是两个大素数，p 一1 和q l 至少有一个大的素因子， 塑! 塑墼塑堡堕竺窒兰生望 一 ”= p q ，整数p 满足g c d ( 8 ，p ( ) ) = 1 。接收者b o b 的公钥是( n ，0 ，私钥是( p ，q ，d ) 其中d 满足d e ；1 ( m o d o ( n ) ) 。 假设发送者a l i c e 要将消息m 0 ，”一l 秘密发送给b o b ，a l i c e 首先计算 c = m 。( m o d n ) 并将密文c 发送给b o b ，b o b 计算= c 4 ( r o o d n ) 进行解密。 由于d e = 1 ( m o d 妒( n ) ) ，因此c 4 = ( m 8 ) 4 ；m ( m o d n ) ，这就说明b o b 能够解密得 到明文。该方案的安全性基于r s a 问题的难解性，但是系统并不总是安全的。 例如，e 比较小的情况下攻击是可能的。所以实际使用时应注意使p 和q 为强素 数，各自足够大，差足够大，p 一1 和q l 的最大公因子要小，e 与d 足够大。 2 2 2 、e i g a m a l 加密 e 1 g a m a l 提出的加密方案可以看作d i f f i e h e l l m a n 密钥交换协议的另一种应 用。设g 是有限循环群，其阶为q ，g g 是g 的生成元，在g 中计算离散对 数是困难的。在原方案中，p 是大素数， g = z ：， 因而g 的阶为p l 。接受者b o b 的私钥是x ，公钥是y = g 。假设发送者a l i c e 要将消息m g 秘密发送绘b o b 。首先a l i c e 随机选取 a e z 4 ， 计算( 爿，b ) = ( g 。，y 4 m ) 并将密文( 爿，占) 发送给b o b 。接受者b o b 计算 旦：虚：也：m a 。 g “g “ 进行解密。 e 1 g a m a l 加密算法的安全性基于d i f f i e h e l l m a n 问题的难解性。该算法是概 率加密算法。如果每次加密时选取口是随机的，那么确定( a ，b ) 是( 彳，b ) 两个密 文是否对应于同一个明文m 和解决d i f f i e h e l l m a n 确定问题相同。 6 上海交通大学硕士学位论文 2 3 、签名算法 数字签名的思想由d i f f i e 和h e l l m a n 在中提出。数字签名是以电子形式签名 一个消息的方法，和传统签名有一些相似之处。一个数字签名是一个将签名者公 钥和签名消息联系起来的二进制串。任何人都可以用签名者的公钥验证签名，另 一方面，只有知道私钥的人才能产生正确的签名。签名方案的正式定义如下所示。 定义2 3 1 一个签名方案是一个算法的3 元组( g e n ，s 喀，v e r ) ，其中g e n 是概率 型算法，s 辔通常是概率型算法，v e r 是确定型算法。g e n 输入系统参数，输出签 名者s 的私钥z ，和公钥儿，s i g 输入消息m 和x 。，输出m 的签名，v e r 输入消 息坍、签名仃和s 的公钥y 。，输出t r u e 或f a l s e ，并满足 ，、f t r u ei f p r o b ( c r = s 培( 肌，t ) ) 0 w r ( 卅，盯，虬) = jf a l s eo t h e n i s e 而且，任何人不知道私钥就不能产生正确的签名，即签名是不可伪造的。 2 3 1 、r s a 签名 r s a 签名方案直接从r s a 加密方案得到，安全性基于计算模数为合数的e 次 方根的困难性。 设p 和g 是两个大素数，p l 和q l 至少有一个大的素因子，疗= p q ，整数 e 满足g c d ( e ，矿( h ) ) = 1 。签名者的公钥是( n ，e ) ，私钥是( p ，q ，d ) ，其中d 满足 d e i l ( m o d ( p ( n ) ) 。散列函数h ： 0 ，1 ) 寸z 。 定义2 3 2 对消息m 0 ，1 的公钥为( ”，e ) 的r g a 签名是s z 。，满足 s 8i h ( m ) ( m o d n ) 。 签名者产生签名时只要计算j ；( h ) ) 。( m o d n ) 。由于出；1 ( m o d e ( n ) ) ，因 此s 。= ( h ( m ) ) “；h ( m ) ( m o d n ) ，这就说明签名是正确的。 如果不用散列函数，那么两个签名的乘积是消息乘积的签名，而且攻击者可 以选择s ，计算m = s 8 ( m o d n ) ，从而伪造签名。i s 0 i e c 9 7 9 6 标准提出了解决这 墼主塑丝垫坚塑旦窒皇些旦 一 个问题的签名过程。 2 3 2 、e i g a m a l 签名 e i g a m a l 在还提出了一个签名算法。设g 是有限循环群，其阶为q ，g g 是 g 的生成元，在g 中计算离散对数是困难的。签名者的私钥是工，公钥是y = g 。 散列函数h ： o ，1 + jz 。 定义2 3 3 对消息m o ，1 ) + 的公钥为y = g 。的e 1 g a m a l 签名是( “，s ) g z 。 满足g “”= y u 5 。 在上面的定义中，为了计算y “，首先将“表示为z 中的整数“，然后计算 “”= “( r o o d q ) ，最后计算y ”得到y “。在下文中，群元素、整数和字符串之间的 转换依此类推。 持有私钥x 的签名者产生对消息m 的签名( “，s ) 的过程如下： 首先选 ，rz ：， 然后计算 “：g 哪s ：塑业( m o d g ) 。 ， 由于y u u5 = g “g ”= g = g “，因此签名( “，j ) 能够通过验证。显然，如 果离散对数问题被解决，就可以伪造签名。如果两次签名产生时选择的，相同， 则可以计算出私钥。数据签名算法( d i g i t a ls i g n a t u r ea l g o r i t h m ，简称d s a ) 是 e 1 g a m a l 签名的一个变形。 数字签名作为手写签名的电子化，具有更大的安全性和更高的效率；它更容 易验证，更加难以伪造，同时也更加难以抵赖。 上海交通大学硕士学位论文 2 4 、比特承诺和零知识证明 2 4 1 、比特承诺 安全的多方计算协议将用到零知识证明，而g o l d r e i c h 等 g m w 9 1 证明了只 要存在承诺方案，对任何n p - 语言都存在( 黑盒) 零知识证明。因此尽管比特承 诺本身的实际用途不大，但作为密码学协议的原语有着非常重要的意义。比特承 诺可分为承诺阶段和打开阶段，在承诺阶段承诺者向接收者发送一对未来事件的 预测( 承诺) ，但不揭示该预铡，在打开阶段承诺者揭示预测且接收者相信揭示 值就是承诺值，形式化地说： 定义2 4 1 ( 比特承诺方案) 是 统计性隐藏的，如果在承诺阶段后( 打开阶段前) 接收者得到的关于被承诺 比特x 0 , 1 的信息v 为i ( x ly ) 2 - “，其中2 o ，n 为安全参数 j 约束的，对0 n ) 3 1 4 3 、会话发送子协议 m e r c h a n t 广播( 发布) i t e m 中每个会话数据块，每个会话数据块中c i p h e r b l o c k 使用这个块对应的s e s s i o n k e y 加密。s e s s i o n k e y 被等长的分成l 段s 1 s 卜s l ， 其中第i 段使用第i 个密钥桶中的b 个密钥进行加密( i - - 1 l ) 。这l * b 个加密值 按次序排列构成这个会话数据块的e n a b l i n gb l o c k ，随加密块一起发送。每个 b u y e r 收到一个会话数据块后，使用自己的p e r s o n a lk e y 从e n a b l i n gb l o c k 中解密 出对应的s 1 ) s l ，组成完整的s e s s i o n k e ys ，从而解密出对应加密块中的有效数 据。 3 1 4 4 、盗版跟踪子协议 对一组c o i ls i z e 个共谋t r a i t o r s 来说，为了使一个p i r a t e u s e r 可以成功解密所 有s e s s i o nb l o c k 中的数据，他们必须提供一个有效的p e r s o n a lk e y 。首先他们不 会提供其中单个人的p e r s o n a lk e y ，否则m e r c h a n t 直接从检测出的这个p e r s o n a l k e y 查到t r a i t o r ，那么他们就要对l 段中每个s j ，从他们的c o l l 个_sizep e r s o n a lk e y 中对应的c o i ls i z e 个k e y i 。i 中选择一个作为解密s i 的密钥，使最终共谋产生的 p e r s o n a lk e y 是有效的，但是和t r a i t o r s 中的任意一个p e r s o n a lk e y 都不同，来阻 止追查。但是，该协议通过如下算法使m e r c h a n t 仍能确定其中的一个t r a i t o r ：当 事后查到了一个p i r a t eu s e r ，m e r c h a n t 可以得到一个该p i r a t eu s e r 使用的p e r s o n a l k e y k ( 实际是每个密钥桶中对应一个k e y i j ) 。对于这个k 中l 个k e y i j ( i = 1 l ) ， m e r c h a n t 对每个其p e r s o n a lk e y 中对应位置等于k e y i j 的b u y e r 作次标记，如 k = k e y l ，7 ，k e y 2 ，3 ，k e y 3 ，4 i k e y l ，9 ，某个 b u y e r的p e r s o n a l k e y = k e y l , 7 , k e y 2 ，8 ，k e y 3 ，4 ，k e y l ，6 ) ( 假设位置中的对应k e y 都不相同) ，则这个 b u y e r 被标记两次( 第1 、3 两个密钥桶) 。最后被标记次数最多的b u y e r 就被认 为是t r a i t o r s 之一。( 实际上这个b u y e r 至少被标记l c o l ls i z e 次，并且共谋所伪 造的p e r s o n a l k e y 等于一个合法b u y e r 的p e r s o n a l k e y 的概率根据参数设置是可忽 略的，以保证共谋不能陷害一个诚实的b u y e r ，这个算法的证明以及共谋不可陷 害的证明在c f n 9 4 中进行了详细的证明) 3 2 、非对称型t r a i t o rt r a c i n g 协议 p f i t z m a n n 等将非对称的概念应用于t r a i t t r a c i n g 协议 p s 9 6 】，以改善协议的 安全性和公平性。简单来说，在基本的t r a i t t r a c i n g 协议中，m e r c h a n t 和b u y e r 都知道卖给b u y e r 的个人密钥( p e r s o n a lk e y ) ，那么在发现盗版提起诉讼时，b u y e r 完全可以声称m e r c h a n t 发现的p e r s o n a lk e y 是m e r c h a n t 的一个不诚实的员工所 数字指纹协议的研究与应用 流传出去的，从而使仲裁无法确认谁是t r a i t o r ( 所谓对称性) 。 非对称的概念就是要使标识b u y e r 的“指纹”只有b u y e r 自己知道( 自己选 择生成其个人密钥的c o d e w o r d ) ，而m e r c h a n t 在商品交易时不知道，但可以确 认( 通过零知识证明) 。在t r a c i n g 时m e r c h a n t 可以得到足够的证据( p r o o f ) 来 指认相关的t r a i t o r 。 非对称的概念也被用于后一章说讲的基于数字水印的指纹协议中。 非对称t r a i t o r - t r a c i n g 协议的基础仍基于上文简述的对称型的t r a i t o r - t r a c i n g 协议，包括参与的角色和对象。为了实现非对称性，我们需要增加三个密码学体 系：一个公钥签名模式、个承诺模式和个安全2 - p a r t y 计算。在这里我们不 讨论这些模式的概念和实现，假设都已存在。 3 , 2 i 、协议参数 o ：一个适当的概率参数以表示安全的系数 c o l ls i z e ：协议可以保证安全的最大的共谋者的个数 l ：会话密钥的分段个数，个人密钥的集合大小( 这里我们选定 l = 6 4 + c o l l _ s i z e + ( c + l 0 9 2 ( n ) ) 、 b ：一个任意字母表的大小，如字母表为 1 ，2 ，3 ，b ( 这里我们选定 b = 4 8 + c o i l s i z e ) n ：b u y e r 的最大数量 3 2 2 、协议过程 协议分成六个子协议 3 2 2 1 、b u y e r 的签名密钥生成： 每个购买者( b u y e r ) 生成一对签名模式使用的公私钥( s k b ，p k b ) 并公布其 公钥p k b 。 3 2 2 2 、密钥初始化子协议 和基本( 对称) 协议中的对应子协议相同，m e r c h a n t 选择l 个密钥桶( b u c k e t ) 每个桶有b 个对称密钥。 1 4 上海交通大学硕士学位论文 3 2 2 3 、密钥指纹子协议 b u y e r 选择一个长为l 的码字w o r d s ( 这一步在基本协议中是由m e r c h a n t 完 成的) 。 b u y e r 对w o r d s 生成一个承诺c o m b ，并把这个承诺发送给m e r c h a n t 。用来揭 示承诺的信息称为o p e n s 。 b u y e r 使用自己的签名私钥s k a 对如下消息进行签名：m s g b = ( t e x t ，c o r n s ) ，生 成s i g s 。其中t e x t 是一个字符串，只要足以说明签名消息的含义。 m e r c h a n t 使用p k b 验证s i g s 是对m s g b 的一个有效的签名。 接下来执行安全2 - p a r t y 计算： 输入： b u y e r ：w o d s 干廿o p 肋8 m e r c h a n t ：在密钥初始化子协议中生成的l * b 个对称密钥，一个随机选择的 大小为l 2 的集合s e t b ( 1 ，l ) 的子集) ，c o r n b 计算： 验证o p e n b 可以打开承诺c o m b ，否则协议失败 验证s e t b 的大小最多为l 2 个元素 w o r d b 中符号对应集合s e t s 中元素的位置组成的有序符号集称为 h a l f w o r d _ t r a c e b ，其余部分称为h a l f w o r d _ _ e v i d b ( 见图3 2 ) 输出： b u y e r ：由w o r d s 对应生成的个人密钥( p e r s o n a lk e y ) m e r c h a n t ：h a l f w o r d _ t r a c e b ( 这样m e r c h a n t 只知道w o r d b 中的一半符号而不 能猜出整个w o r d b ，仍符合我们的非对称性) 这样在执行完安全2 - p a r t y 计算) 舌m e r c h a n t 得到的交易记录r e c o r d m = ( i d a ，t e x t , c o m b ，s i g s ，s e t b ，h a l f w o r d _ t r a c e s ) ，b u y e r 得到的交易记录r e c o r d b = ( t e x t ，w o r d b ， o p e n s ) 。 3 2 2 4 、会话发送子协议： 和基本协议中对应的子协议相同。 3 2 2 5 、盗版跟踪子协议 如同基本协议中一样，m e r c h a n t 发现个p i r a t eu s e r ，得到个个人密钥， 也就相当于找到一个长为l 的码字w o r d f o 。d ，他搜索所有交易记录中的( s e t s 。 h a l f w o r d _ t r a c e a ) ，找到一个记录，其h a l f w o r d _ t r a c e s 和w o r d f o u n d 至少有 l ( 4 4 c o i l s i z e ) 个对应位置上符号是相同的。他取出m s g a = ( t e x t , o o m b ) ns i g a 准备 数字指纹协议的研究与应用 向仲裁者控告此b u y e r 。 3 2 2 6 、仲裁子协议 m e r c h a n t 组成的证据为p r o o f = - ( m s g b ，s i g b ，w o r d a c 。e ) ，其中w o r d “。为长l 的码字，码字中对应s e t b 中元素的位置上由h a l f w o r dt r a c e b 中的对应符号组成， 码字中其他位置的符号由w o r d f o u n d 中的对应位置符号组成。 b u y e r 提供o p e n b 。 仲裁者首先验证s 蟾b 签名的有效性和承诺的有效性( 揭示w o r d b ) 。 然后验证w o r d a c 。和w o r d b 是否至少在l 2 + l ( 1 6 + c o i l s i z e ) 个对应位置上的 符号相同，成立则指控成功，否则b u y e r 即可否认指控。 为了使w o r d b 始终对m e r c h a n t 保密，可以用零知识证明来给出w o r d b 。 f i g u r e3 2d e c r i p t i o no f a s y m m e t i c a lt r a i t o rt r a c i n gp r o t o c o l 图3 2 非对称t r a i t o r u r a e i n g 协议描述 圭生奎塑查兰堡主兰焦丝苎 3 2 3 、安全性 3 2 3 _ 1 、b u y e r 的安全性 因为m e r c h a n t 从h a l f w o r d _ t r a c e b 中知道w o r d b 中的l 2 个位置的符号，如果 m e r c h a n t 要陷害一个b u y e r ，他需要再猜对这个w o m b 中的另外至少 l ( 1 6 c o i ls i z e ) 个位置的符号。 考虑m e r c h a n t 猜测出w o r d b 中至少l ( 1 6 + c o l l s i z e ) 个位置符号的概率，设s 为一个随机变量，表示猜对符号的个数。对任意一个位置( 1 l ) ，随机猜测猜 对的概率为p = l b 。我们使用一个概率限定公式c h e m o f f b o u n d 判断概率： 厂1 j、厂。口一i 、川 对任意p 1 有p r f x ，彦f 【7 f ( 为0 - l 随即变量) 所以p “s p p l ) 3 l b ) 2 。m 根据我们先前设定的l = 6 4 + c o l l _ s i z e + ( o + 1 0 9 2 ) ) 和b = 4 8 + c o i l _ s i z e 得到p r ( s l ( 1 6 c 0 1 1 s i z e ) ) 2 ，适当选取。可以认为m e r c h a n t 猜对 l ( 1 6 t c o l l s i z e ) 个符号的概率可忽略，从而保证了b u y e r 的安全性。 3 2 3 2 、m e r c h a n t 的安全性 计算m e r c h a n t 能够检测出个t r a i t o r 的概率： 因为协议约定最多有c o l ls i z e 个共谋者，所以对于一个长为l 的共谋得到的 码字w o r d f 0 。d ( 或者说是p e r s o n a l k e y ，这是对应的) ，至少有一个共谋者需要提 供至少l c o i ls i z e 个符号( 或者说是密钥桶中的对称密钥) 。假设这个共谋者为 t ，我们来计算s e t - r 中至少含有w o r d 嘶。d 和w o r d t 交集中l ( 4 c o l l s i z e ) 个符号的 概率。 由于s e t x 是随机选择的，我们来证明这随机选择的l 2 个符号包含了至少 l ( 4 c o l ls i z e ) 个t 所提供的l c o i ls i z e 个符号。 这个概率可以等同于如下的概率模型：在个大小为l 的球池中，至少有 r = l e o us i z e 个红球，从池中随机选出l 2 个球( 不放回) 作为样本，样本中至 少有r 十= l ( 4 c o l l 个红球的概率r 幸) 。( 一并且)size)=r4p ( r e d r 2 r l 2 首先，样本中有f 个红球的概率为p ( r e d = ，) = 所以 r y 三一r ，火三2 一 ( 0 2 ，l 数字指纹协议的五j f 究与应用 p ( r e 。d 。= r 、- 1 ) ：= p ( r e d = ，、 = 南错警竿南= ：q u o t r ( q u o t r ( r ，。瓦了石万e 百3 瓦了石 因为r r ，也就是q u o t r ( r ) n ir 的递减也递减，因此 p ( r e d = r - x ) ( 西南jp ( r 甜一) ，垤9 、 进而得到 p ( r e d _ 一6 4 c o l l _ s i z e + o 得到 尸( r e d _ r 4 ，( 羔 r i $ 尸c r e d 1 时，完全c 一安全的码是不存在的。因此我 们必须弱化我们的指纹要求，允许分发者用随机的方法来生