（计算机应用技术专业论文）基于web+services的adsm的研究及其在网页内容认证中的应用.pdf

冬t j ：汜t i 冀 ： ：。| 一。 n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 一 ip _，一，o：。jil r 本人声明所呈交的学位 i 一一 ；研究成果除加以标注和致谢 0 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：弓友卸 签字日期：乃彩。j 7 一歹 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口 学位论文储签名：芗澎7 签字日期 ：知彩7 一弓 两年。 锄签名：周黼 签字日期：) 瑚1 乡 1 东北大学硕士学位论文摘要 基于w e bs e r v i c e s 的a d s m 的研究及其在网页内容认证中的应用 摘要 随着计算机网络的应用日益深入、广泛，分布式数据系统逐步成为企业级信息系统 的应用模式。越来越多的部门、企业的内部信息呈现出异地存储的特点。例如银行、股 票交易所和政府等重要部门大都通过国内外门户网站提供存款利率、股票报价、新闻消 息等重要信息。在这种情况下，数据的所有者和使用者不再是同一个实体，并且数据往 往是通过不可信的计算实体进行传递的，这就给数据的真实性带来了极大的安全性威 胁。认证数据结构模型( a d s m ) 可以解决分布式环境下数据的查询和认证问题。但是 认证数据结构的实现有个最大的缺点在于：客户端必须访问体积庞大的、私有的接口。 这使得程序开发人员必须具有专门的知识，同时还需要为不同的目标操作系统和程序设 计语言提供独立的工具包，这些工具包都拥有各自独立的通信协议和规范器等等。 为了使a d s m 的客户端平台获得更大的互操作能力，减少代码的重复开发并简化 证明信息的验证过程，本文设计了一个基于w e bs e r v i c e s 的认证数据结构模型，采用 x m l 数字签名实现签名及其验证，提供了数据更新、数据证明、数据认证等w e b 服务 接口，并使用a p a c h et o m c a t 作为服务容器在e c l i p s e 平台上采用j a v a 进行了原型实现。 另外为了解决来自信息中心的数据通过第三方门户网站发布时的认证问题，论文构建了 一个网页内容认证模型，提出了一项新的认证网页内容的f a c 技术，它是一种能够安 全地认证嵌在网页中的关键内容的一种很有效的技术，包括h t m l 标签库的一个扩展 和一项分发和发布认证数据的服务。最后，通过一个浏览器工具栏插件和一个分布式的 网络认证服务给出了网页内容认证模型的原型实现。 关键词：a d s m ；w e bs e r v i c e s ；x m l 数字签名；网页内容认证模型；f a c 技术 一i i 吣1 一1。11。1。 东北大学硕士学位论文 a b s t r a c t - _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ - _ - - - _ _ _ _ - _ _ - _ _ _ _ l - _ _ - _ _ _ _ _ _ i - _ _ _ _ - - - _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ - 。_ _ - _ _ _ _ _ - - _ _ _ - - _ _ - _ _ _ - - _ - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ - - _ _ - _ _ _ _ _ _ - _ - _ _ _ _ - _ _ _ _ _ _ _ 一 r e s e a r c ho na d s mb a s e do nw e bs e r v i c e sa n di t sa p p l i c a t i o ni n a u t h e n t i c a t i n gw e bc o n t e n t a bs t r a c t w i t ht h ei n c r e a s i n gi n - d e p t ha n de x t e n s i v ea p p l i c a t i o no fc o m p u t e rn e t w o r k s ，d i s t r i b u t e d d a t as y s t e m sg r a d u a l l yb e c o m et h ea p p l i c a t i o nm o d eo fe n t e r p r i s ei n f o r m a t i o ns y s t e m m o r e a n dm o r ed e p a r t m e n t sa n de n t e r p r i s e ss t o r et h e i ri n t e r n a li n f o r m a t i o ni nr e m o t ee n t i t i e s f o r i n s t a n c e ，b a n k s ，s t o c ke x c h a n g e sa n dg o v e r n m e n td e p a r t m e n t sm o s t l yp r o v i d ei m p o r t a n t i n f o r m a t i o ns u c ha sd e p o s i ti n t e r e s tr a t e s ，s t o c kq u o t e sa n dn e w st h r o u g hd o m e s t i ca n d i n t e r n a t i o n a lp o r t a l s i nt h i sc a s e ，t h eo w n e r sa n du s e r so ft h ed a t aa r en ol o n g e rt h es a m e e n t i t i e s ，a n dd a t aa r eo f t e nt r a n s m i s s e dt h r o u g hu n r e l i a b l ec a l c u l a t i o ne n t i t i e s ，w h i c hb r i n g s h u g es e c u r i t yt h r e a tt ot h ea u t h e n t i c i t yo f d a t a a u t h e n t i c a t e dd a t as t r u c t u r em o d e l ( a d s m ) c a ns o l v et h eq u e r ya n da u t h e n t i c a t i o ni s s u e so fd a t ai nd i s t r i b u t e de n v i r o n m e n t h o w e v e r , t h es i g n i f i c a n td r a w b a c kw i t ht h er e a l i z a t i o no fa u t h e n t i c a t e dd a t as t r u c t u r ei st h a tt h ec l i e n t s h a v et oa c c e s si tu s i n gab u l k y , p r o p r i e t a r yi n t e r f a c e n o to n l yd i dt h i sr e q u i r es p e c i a l k n o w l e d g eo nt h ep a r to ft h ea p p l i c a t i o nd e v e l o p e r , b u ti ta l s or e q u i r e das e p a r a t et o o l k i tt o b ep r o v i d e df o re a c ht a r g e to p e r a t i n gs y s t e ma n dp r o g r a m m i n gl a n g u a g e a d d i t i o n a l l y , s u c h t o o l k i t su s e dp r o p r i e t a r yc o m m u n i c a t i o n sp r o t o c o l s ，c a n o n i c a l i z e r s ，a n ds oo n i no r d e rt om a k et h ec l i e n tp l a t f o r mo fa d s mh a sg r e a t e ri n t e r o p e r a b i l i t y , r e d u c et h e d u p l i c a t i o no fc o d ea n ds i m p l i f yt h ev e r i f i c a t i o np r o c e s so fc e r t i f i c a t i o ni n f o r m a t i o n ，w e d e s i g n e da na d s mb a s e do nw e bs e r v i c e s ，u s i n gx m ld i g i t a ls i g n a t u r et oa c h i e v eb a s i s s i g n a t u r ea n di t sv e r i f i c a t i o n t h en e wm o d e lp r o v i d e sw e bs e r v i c ei n t e r f a c e ss u c ha sd a t a u p d a t e ，d a t ac e r t i f i c a t i o na n dd a t aa u t h e n t i c a t i o ni n t e r f a c e ，a n dw eu s ea p a c h et o m c a ta sa s e r v i c ec o n t a i n e rt oa c h i e v et h ep r o t o t y p eo ft h en e wm o d e li nj a v ao ne c l i p s ep l a t f o r m i n a d d i t i o n t os o l v et h ea u t h e n t i c a t i o ni s s u e sw h e nd a t af r o mi n f o r m a t i o nc e n t e ra r ei s s u e d t h r o u g ht h et h i r dp a r t yp o r t a l s ，t h ep a p e rc o n s t r u c t saw e bc o n t e n ta u t h e n t i c a t i o nm o d e l ，a n d p r o p o s e s an e ww e bc o n t e n ta u t h e n t i c a t i o nf a ct e c h n o l o g y , w h i c hi sav e r ye f f e c t i v e m a n n e rt h a tc a ns a f e l yv e d f yt h ek e yc o n t e n te m b e d d e di naw e bp a g ea n di n c l u d e sa n e x t e n s i o no ft h eh t m l t a gl i b r a r ya n das e r v i c ef o rp u b l i s h i n ga n dd i s t r i b u t i n ga u t h e n t i c a t e d d a t a f i n a l l y ，w ep r e s e n to u rp r o t o t y p ei m p l e m e n t a t i o nb ym e a n so fab r o w s e rt o o l b a ra n do f ad i s t r i b u t e da u t h e n t i c a t i o nw e bs e r v i c e k e yw o r d s ：a d s m ；w e bs e r v i c e s ；x m ld a t as i g n a t u r e ；w e bc o n t e n ta u t h e n t i c a t i o nm o d e l ； f a c t e c h n o l o g y i i i 、 1 东北大学硕士学位论文目录 目录 独创性声明。i 摘要i i a b s t r a c t i i i 目! 录 第l 章绪论。1 1 1 研究背景。1 1 2 本文研究的主要问题2 1 3 论文的组织结构。4 第2 章相关理论基础及技术。5 2 1 密码学基础及相关技术。5 2 1 1 公钥密码算法5 2 1 2 哈希函数6 2 1 3 消息摘要6 2 1 4 数字签名7 2 2 认证数据结构模型( a d s m ) 7 2 2 1 定义7 2 2 2 设计目标9 2 2 3 实现方法10 2 3 认证跳表数据结构1 0 2 3 1 认证跳表数据结构的定义1 0 2 3 2 认证跳表数据结构的节点值计算方法1 2 2 3 3 认证跳表数据结构的更新操作1 2 2 3 4 认证跳表数据结构的查找操作和验证。1 3 2 4w 曲s e r v i c e s 及其相关技术15 2 4 1w 曲s e r v i c e s 的定义l5 2 4 2w 曲s e r v i c e s 的特点16 2 4 3w e bs e r v i c e s 体系结构模型1 7 2 4 4w e bs e r v i c e s 的关键技术17 2 5 i 、结2 2 第3 章基于w e bs e r v i c e s 的认证数据结构模型2 3 3 1 实体的构成2 4 3 2 实体间通信2 5 东北大学硕士学位论文 目录 3 3 模型设计和分析2 7 3 3 1 服务注册和查询2 7 3 3 2 数据分发和更新2 8 3 - 3 3 数据查询2 9 3 3 4 数据更新服务3 0 3 3 5 数据证明服务3 0 3 3 6 数据认证服务3l 3 4 实体类设计3 3 3 5 原型实现3 6 3 5 1 开发环境3 7 3 5 2a x i s 对象模型3 7 3 5 3 客户端：3 8 3 5 4 响应者端3 8 3 5 5 数据认证服务器3 9 3 5 6x m l 签名、验证签名的实现4 0 3 64 、结4 4 第4 章网页内容认证模型4 5 4 1 系统模型。4 5 4 2 f a c 技术4 7 4 2 1 自定义标签设计4 7 4 2 2 向h t m l 文档中嵌入f a c 标签4 8 4 2 3f a c 查询请求类型4 9 4 3 客户端插件设计5 0 4 4f a c 内容分发验证模型5 0 4 5f a c 内容库设计。5 1 4 61 、l ； i 5 ：! 第5 章基于w e bs e r v i c e s 的a d s m 的网页内容认证系统的实现5 3 5 1 开发环境5 3 5 2w 曲服务器的设计和实现5 3 5 3 客户端的设计和实现5 5 5 3 1 客户端程序的实现5 5 5 3 2 浏览器插件的实现6 0 5 3 3 打包安装程序6 3 5 4 测试结果6 4 5 5 小结一6 5 ，v 东北大学硕士学位论文 第6 章总结与展望。 6 1 总结 6 2 展望 参考文献 致谢 攻读硕士学位期间的论文项目情况 v i 一 东北大学硕士学位论文第1 章绪论 1 1 研究背景 第1 章绪论 近年来，随着计算机网络的应用日益深入、广泛，网络信息系统已经成为国家、企 业、个人不可或缺的重要组成部分，并已经渗透到人们的日常生活、经济、军事、科技 与教育等多个领域。随着网络信息系统的基础性、全局性的地位日益增强，网络信息安 全技术将会有越来越广泛的应用，作为信息安全金三角( c i a ，c o n f i d e n t i a l i t yi n t e g r i t y a v a i l a b i l i t y ) 之一完整性，也就是数据的真实性则是最基本、最重要的安全需求。典型 的解决办法是数据集中化，但是由于数据高度集中，将不可避免的引起“网络延时”和 “拒绝服务攻击，【l 】等问题。而且数据集中方案还需要额外的建立与维护可信数据环境， 而建立和维护可信环境的成本是极其昂贵的；同时也面临着难于升级的问题。基于上述 原因，随着数据吞吐量的增加使得这种集中化的做法变得越来越不可行。 随着w e bs e r v i c e s 和p e r v a s i v e 计算技术的应用【2 3 】，分布式数据系统逐步成为企业 级信息系统的应用模式。越来越多的部门、企业的内部信息呈现出异地存储的特点。例 如银行、股票交易所和政府等重要部门大都通过国内外门户网站提供存款利率、股票报 价、新闻消息等重要信息。每时每刻都有数以万计访问者通过分布在世界范围内的客户 端通过i n t e m e t 访问这些网站，进行大量数据查询和处理。在这种情况下，数据的所有 者和使用者( 发布者) 不再是同一个实体，并且数据往往是通过不可信的计算实体进行 传递的，这就给数据的真实性带来了极大的安全性威胁。因此，如何在不可信数据发布 者或敌手攻击数据发布环境下，保证发布的数据具有真实性成为当前研究的热点问题。 随着这种分布式数据应用的日益增长，建立一种能有效验证分布式数据真实性方法的需 求也更加强烈。 为了解决分布式数据的认证问题，布朗大学的t a m a s s i a 在n a o r 和n i s s i m 提出的认 证字典的基础上，提出了认证数据结构的概念，并给出了认证数据结构模型【4 】 ( a u t h e n t i c a t e dd a t as t r u c t u r em o d e l ，a d s m ) ，它支持分布式数据的高效查询和认证。 这个模型以数据结构和密码学相关技术为研究和实现手段，通过提取整个数据结构特征 值的方法来构建。在a d s m 中，数据的拥有者和使用者( 发布者) 不属于同一个实体， 而且使用者( 发布者) 一般都是不可信的；数据都是按某种特定的数据结构进行存储和 管理，并且每个数据结构都带有经过密码学计算的结构特征，在对数据进行认证时，不 是对单一数据进行认证，而是对数据结构的特征( 摘要值) 进行认证，从而在高效率的 - 1 _ 东北大学硕士学位论文第1 章绪论 情况下实现了数据的认证。 目前在认证数据结构上存在着广泛的研究，所有的实现方法都是增强了数据结构， 让它还带有一个对查询的应答，以及一个能够验证应答真实性的密码学证据。最初的研 究关注于对成员资格查询的认证( 大多数在证书撤销问题的情境中) ，那时m e r k l e 提 出的基于哈希树扩展的众多认证字典被广泛研究【5 ，6 ，7 ，8 ，9 1 0 川。在 1 2 ，1 3 q b 介绍了使用动 态累加器如何实现一个动态认证字典，而在【1 4 】中哈希和累加器的一个有趣的结合被用来 提高一维认证的范围搜索的效率。更多的成员资格查询以外的一般查询也被研究，其中 哈希树的扩展被用来认证各种各样的查询，包括：数据库上的基本操作 1 5 j 6 1 ，直角范围 搜索中的模式匹配【1 1 7 1 ，图中的路径查询和连接性查询，几何对象上的查询( 例如：点位 置查询和线段相交点查询) 【1 8 】，以及x m l 文档上的查询【1 9 】。国内研究工作主要以中科 院软件所卿斯汉为代表，主要研究成果为认证字典在p k i 中的应用4 3 , 4 4 , 4 5 。 1 2 本文研究的主要问题 虽然认证数据结构模型( a d s m ) 可以解决分布式环境下的数据高效查询和认证问 题，但是认证数据结构的实现有个最大的缺点在于：客户端必须访问体积庞大的、私有 的接口。这使得程序开发人员必须具有专门的知识，同时还需要为不同的目标操作系统 和程序设计语言提供独立的工具，这些工具都拥有各自独立的通信协议和规范器等等。 随着i n t e m e t 技术日益广泛的应用，w e bs e r v i c e s 作为一种新颖的系统应用开发与 集成技术得到了越来越多的企业以及开发人员的青睐。w e bs e r v i c e s 描述了一些操作的 接口，通过标准化的x m l 消息传递机制，可以通过网络访问这些操作。该接口隐藏了 服务实现的细节，允许通过独立于服务实现、独立于硬件或软件平台、独立于编写服务 所用的编程语言的方式使用该服务。这使得基于w e bs e r v i c e s 的应用程序具备松散耦 合、面向组件和跨技术实现的特点。 所以为了使a d s m 的客户端平台获得更大的互操作能力( 互用性) ，减少代码的重 复开发并简化证明信息p r o o f 的验证过程，本文设计了一个基于w e bs e r v i c e s 的认证数 据结构模型，提供了数据更新、数据证明、数据认证等w e b 服务接口，并使用a p a c h e t o m c a t 作为服务容器在e c l i p s e 平台上采用j a v a 进行了原型实现。通过实现认证数据结 构模型的w e bs e r v i c e s 接口，可以利用现存的标准得到更高的简便性、互操作性和客户 端的简单性。这个新的接口通过把通信、标准化、串行化操作委托给已存在的实现，来 简化客户端工具的体积。 w e bs e r v i c e s 接口，通过x m l 、s o a p 和h t t p 等标准的互操作技术，提供了一个 2 东北大学硕士学位论文第1 章绪论 标准的远程调用框架。之前的认证数据结构实现通常采用s o c k e t 或者j a v a 的r m i ( r e m o t em e t h o di n v o c a t i o n ，远程方法调用) 技术来实现数据源和响应者之间、客户和 响应者之间的通信协议，如果采用以s o a p 为基础的通信协议就可以与很多不同的程序 设计语言兼容，实现完全的跨平台和语言独立性，还可以避免防火墙问题，在互联网上 配置时拥有更好的可扩展性。 考虑到另外一个严峻的问题，银行、股票交易所、气象局、政府等重要部门的信息， 大都通过国内外门户网站( 第三方发布者) 提供在线交易、市场报价等财经信息。那些 i n t e r a c t 门户站点，从银行等不同的数据源收集信息( 比如，汇率、存款、天气、新闻、 股票行情等) ，然后把这些信息提供给它的客户。现在，是否信任门户站点提供的信息 完全取决于用户的判断力，如果他们相信这个站点，同时也就相信该站点提供的全部信 息，这种情况明显缺乏足够的安全保证。那么就需要通过一个安全和高效的机制，使用 户可以证明从一个w c b 站点获得的信息是否与直接从信息源( 特别重要财经、银行、 军事) 所获得的信息是完全一致的。 先前也有一些方法用来认证网页内容。如传输层安全协议( t r a n s p o r tl a y e rs e c u r i t y p r o t o c o l ，t l s ) 它通过已知的公钥传输系统来交换一个密钥。所有的客户和主机之间 传输的数据都用这个密钥来加密和解密。当技术主要关注于保护通信渠道时，它能用来 保证客户到主机之间端到端的完整性。但是数据的完整性仅仪在终端丰机和客户之间的 通信时才有所保证，但是如果内容通过不可信的第三方传递，这些内容都有可能被篡改。 t l s 对这种不会危及网络服务器到网络浏览器的数据流的攻击抵抗性很弱。 又如公钥基础结构( p u b l i ck e yi n f r a s t r u c t u r e ，p k i ) ，它是在邮件应用中很流行的方 法，它使用公钥对消息进行签名。它需要数据源对所有的请求都要响应( 为了对数据签 名) ，因此给服务器带来了极度的负担，并且数据源很容易受到外界的攻击。虽然数据 源可以复制镜像来解决第一个问题，但是保护这些大量的源镜像服务器从经济上来说却 是不可行的。并且用来验证数字签名过的网络文档的技术现在还处于萌芽期。 再如网络欺骗对策( w e bs p o o f i n gc o u n t e r m e a s u r e s ) ，它通过仅仅让终端用户认识 到存在潜在的不安全因素的元素来阻止对未授权的源数据的修改。y e 和s m i t h 2 0 】开发 了一个方法，把网络内容分隔成信任的和不可信任的部分。任何不是从特定源服务器来 的数据都被划到不可信任的部分中。这个方法在决定是否整个页面被修改过的时候很有 用，但是它不能掌握完美的粒度。另外，它严重依赖于人们对网络欺骗或篡改的检测。 针对上述方法的问题，本文提出了一个新的网页内容认证模型，并提出了一项能够 很有效地认证嵌在网页中的关键内容的f a c ( f l a go fa u t h e n t i c a t e dc o n t e n t ) 技术，它包括 3 东北大学硕士学位论文第1 章绪论 了h t m l 标签库的一个扩展和一项分发和发布认证数据的服务。一个f a c 标签是一个 限定一个h t m l 或x m l 文档一部分的特定的h t m l 标签，网页中关键的数据被称为 f a c 内容；f a c 内容的分发和发布则以基于w e bs e r v i c e s 的a d s m 为基础，采用了 x m l 数字签名这种认证方法。 本文演示了f a c 如何通过提供完整性的加密证据来保护网页内容不受篡改的危 险。最后，本文通过一个浏览器工具栏插件和一个分布式的网络认证服务给出了新的网 页内容认证模型的原型实现。 1 3 论文的组织结构 本文共分为六章，其中第l 章是绪论部分，主要介绍了a d s m 和网页认证的背景和 研究现状、本文研究的主要问题以及给出本文的组织结构。 第2 章介绍认证数据结构的相关理论基础和w e bs e r v i c e s 的相关知识。首先介绍了 认证数据结构中要到的密码学相关知识，其次介绍了认证数据结构的定义和设计，以及 跳表数据结构的定义和基本操作，提出了基于跳表实现认证数据结构的方案。随后介绍 了w e bs e r v i c e s 技术的定义、特点、体系结构模型，最后介绍了w e bs e r v i c e s 的几个关 键技术：x m l 、s o a p 、u d d i 和w s d l 。 第3 章给出了基于w e bs e r v i c e s 的认证数据结构的研究、设计和实现。设计了包含 五方实体的基于w e bs e r v i c e s 的a d s m 。设计了实体间通信的协议、s o a p 消息的格式 设计以及数据更新、数据证明、数据认证等w e b 服务接口。最后，本文使用a p a c h e t o m c a t 作为服务容器在e c l i p s e 平台上实现了w e b 服务接口，和一个w c bs e r v i c e s 客户端。 第4 章构建了一个网页内容认证模型，提出了一项新的认证网页内容的f a c 技术， 自定义了网页中的f a c 基类标签和f a c 引用标签，设计了网页以及标签的设计格式， 最后在客户端设计了一个浏览器工具栏插件用来验证网页中关键内容的真实性。 第5 章在第4 章的基础上实现了基于w e bs e r v i c e s 的a d s m 的网页内容认证系统。 模拟实现了一个w e b 服务器，用i i s 发布天气预报的网页；采用a t l 实现了一个客户 端浏览器插件，并把它打包成一个安装程序，可以很方便地安装或卸载。 第6 章对本文的理论和实践成果做出了总结，同时指出本文所实现的系统的优点和 不足，并对未来的研究工作做以展望。 4 东北大学硕士学位论文第2 章相关理论基础及技术 第2 章相关理论基础及技术 2 1 密码学基础及相关技术 2 1 1 公钥密码算法 公钥密码算法是基于数学函数的、非对称的、使用两个独立密钥的密码算法，其中 一个密钥是私有的，另一个是公有的。 公钥密码体制的应用主要分为三类【2 1 】： ( 1 ) 加密解密：发送方用接收方的公钥对消息加密，接收方用其私钥解密； ( 2 ) 数字签名：发送方用其私钥对消息签名。签名可以通过对整条消息加密或者对 消息的一个小的数据块加密来产生，其中该小数据块是整条消息的函数。 ( 3 ) 密钥交换：通信双方交换会话密钥。 盘 公钥密码算法容易受到穷举攻击，解决攻击的方法是选择长密钥。但是为了便于实 现加密和解密，密钥又必须足够短。在实际中，现已提出的密钥长度确实能抗穷举攻击， 但是它也使加解密速度太慢，所以公钥密码目前仅限于密钥管理和签名中。 d s a ( d i g i t a ls i g n a t u r ea l g o r i t h m ) 是目前很流行的一种公钥密码学算法，它是 s c h n o r r 和e 1 g a m a l 签名算法的变种，被美国n i s t 作为d s s ( d i g i t a ls i g n a t u r es t a n d a r d ) 。 算法中应用了下述参数： ( 1 ) p ：lb i t s 长的素数。l 是6 4 的倍数，范围是5 1 2 到1 0 2 4 ； ( 2 ) q - p 一1 的1 6 0 b i t s 的素因子； ( 3 ) g ：g = h a ( o - 1 ) q ) m o dp ，h 满足h l ； ( 4 ) x ：x q ，x 为私钥； ( 5 ) y ：y = g xm o dp ，( p ，q ，g ，y ) 为公钥； ( 6 ) h ( x ) ：单向哈希函数。 签名过程如下： 产生随机数k ， 满足k q 。计算，= ( g k m o d p ) m o d q ， s = ( k ( 一1 ) ( 日( 棚) + x r ) ) m o d q ，签名结果是( m ，j ) 。 验证过程如下： 计算 w - - - s ( - 1 ) m o d q ，u l = ( 日( 聊) 幸w ) m o d q ，u 2 = ( ，宰w ) m o d q ， v = ( ( g u l * y u 2 ) r o o d p ) r o o d q ，若v = ，则认为签名有效。 一5 _ 东北大学硕士学位论文第2 章相关理论基础及技术 d s a 是基于整数有限域离散对数难题的，其安全性与r s a 相比差不多。d s a 的一 个重要特点是两个素数公开，这样，当使用别人的p 和q 时，即使不知道私钥，你也能 确认它们是否是随机产生的，还是作了手脚。 2 1 2 哈希函数 哈希函数又称数字指纹2 4 1 ，哈希值由下述形式的函数h 生成：h = h ( m ) ，其中，m 是一个变长消息，h ( m ) 是定长的哈希值。消息正确时，将哈希值附于发送方的消息后； 接收方通过重新计算哈希值可认证该消息。 哈希函数的目的就是要产生文件、消息或其他数据块的“指纹”。本文提出的认证数 据结构使用单向可交换哈希函数。单向可交换哈希函数是具有h ( x ，y ) = h ( y ，x ) 性质的二 元哈希函数。例如：h ( x ，y ) = h ( x y ) 。可交换哈希函数日满足： ( 1 ) h 可应用于任意大小的数据块。 ( 2 ) h 产生定长的输出。 ( 3 ) 对任何指定的x ，计算h ( x ) l l 较容易，用硬件和软件均可实现。 ( 4 ) 对任何给定的h a s h 值h ，找到满足h ( x ) - h 的x 在计算上是不可行的，那么称之 为单向性。 ( 5 ) 对任何给定的分组x ，找到满足y c x ，且h ( y ) = h ( x ) 的y 在计算上是不可行的， 那么称之为抗弱碰撞性。 ( 6 ) 找到任何满足h ( x ) = h ( y ) 的偶对( x ，y ) 在计算上是不可行的，那么称之为抗碰撞 性。 本文在认证数据结构实现中使用的哈希算法是安全哈希算法s h a ( s e c u r eh a s h a l g o r i t h m ) ，它是美国国家标准和技术局发布的国家标准f i p sp u b1 8 0 1 ，一般称为 s h a 1 。s h a 1 的基本原理是对长度不超过2 “二迸制位的消息产生1 6 0 位的消息摘要输 出。 2 1 3 消息摘要 消息摘要【2 5 硎由一个单向h a s h 函数对消息作用产生的，该函数可接受任意长度的 消息m ，将其变换为一个固定长度的散列值，这个散列值称为消息摘要( m e s s a g ed i g e s t ) 。 消息摘要是消息m 的所有位的函数，能提供错误检测能力：消息中的任何一位或多位 的变化都将导致该散列值的变化。 一个消息摘要哈希函数应该具备两个特点：( 1 ) 算法是不可预见的，即对于一个给 6 东北大学硕士学位论文第2 章相关理论基础及技术 定的输出值，不能够根据输入数据的一些特点推断出它对应的输入值，也不能够通过试 验还原出它对应的输入值；( 2 ) 对于输入消息的微小改动，都将导致输出散列值的显著 变化。 2 1 4 数字签名 数字签名是非对称密钥技术的一种应用模式，用于保证报文的完整性，不可否认性， 以及提供身份认证信息3 9 1 。数字签名的原理如图2 1 所示。 笈落方靖 嘏文签慧 接受方验 证签名 1 0 1 1 1 嘲口1 露= = =1 0 1 1 1 0 0 0 0 1 口 od 图2 1 ：数字签名的原理图 f i g 2 1p r i n c i p l eg r a p ho fd i g i t a ls i g n a t u r e 发送者在发送报文之前，先选用某种摘要算法为报文生成一个摘要值，并使用自己 的私钥对摘要值加密，然后将加密后的摘要附在报文后面，一同发送给报文的接收者。 接收者收到报文后，从中分离出原始报文和加密后的报文摘要，使用与发送者相同的摘 要算法计算原始报文的摘要值d ，并使用发送者的公共密钥将加密后的报文摘要解密得 到摘要值d ，检查d 与d 是否匹配。 如果匹配，那么由于密钥对的唯一性，所以可以确定报文发送者的身份，而且由于 数据摘要算法的特点，还可以确定原始报文在传输过程中没有被篡改。 2 2 认证数据结构模型( a d s m ) 2 2 1 定义 最早在1 9 9 8 年n a o r 和n i s s i m 提出了认证字典( a u t h e n t i c a t ed i c t i o n a r y ，a d ) 这 一类重要的数据结构，它属于分布式数据的一种类型，在众多研究领域都具有重要的理 7 一 东北大学硕士学位论文第2 章相关理论基础及技术 论和应用价值，诸如科学数据挖掘、地理数据服务器、i n t e m e t 上的第三方数据发布【2 7 】 以及p k i 中的证书撤销2 8 ，2 9 1 等。 认证字典所要解决的基本问题描述如下：设计一个协议，用于在一个不可信的示证 者p 和个验证者矿之间来对集合s 进行隶属关系查询；这里，s 是由某个可信实体 定义的一个有限集合，该集合对于v 是未知的。可信实体控制着用s 来表示的认证字典 所必需的信息。给定一个输入x ，p 可以证明x s 或者工仨s ；同时，可信实体可以动 态地改变集合s 的元素【2 引。 上述问题中，数据集的创建者( 或者拥有者) 和对关于数据集的查询进行应答的实 体不是同一个，更特别的是，数据拥有者并不控制应答一个查询相对应的数据结构。这 个配置环境中，一个中间的、不可信的实体对终端用户发布的关于数据集的查询请求进 行应答。 r o b e r t ot a m a s s i a 4 , 3 8 】正式地定义了这个三方数据查询模型。 【定义1 】三方数据查询模型：一个三方数据查询模型包括一个源s 、一个响应者r 和一个用户u ，其中( i ) s 创建( 拥有) 一个动态数据集s ，这个数据集由用于在s 上的 查询操作q s ：q a s 的查询数据结构d ( g ) 维护。( i i ) 响应者r 通过维护d ( g ) 的一个 拷贝和一些s 的辅助信息来存储s 。( i i i ) 用户u 通过向响应者r 发送查询q q 来向r 发布关于s 的查询；( i v ) 对于u 发布的一个查询q q ，r 计算应答