一种基于线索二叉树的证书撤销管理方案

文中方案使用了排序的二叉树以及散列运算,提出了公钥基础设施中一种改进的证书撤消管理方案——基于线索二叉树搜索树解决方案。该方案不但大大减少了更新撤消列表和查询撤消列表过程中的通信量,改善了撤销列表管理的效率;而且加快撤消列表的更新周期不会引起通信量的快速增

一种基于线索二叉树的证书撤销管理方案

马宏军

北京邮电大学信息工程学院，北京（100876）

E-mail：

摘 要：文中方案使用了排序的二叉树以及散列运算,提出了公钥基础设施中一种改进的证书撤消管理方案——基于线索二叉树搜索树解决方案。该方案不但大大减少了更新撤消列表和查询撤消列表过程中的通信量，改善了撤销列表管理的效率；而且加快撤消列表的更新周期不会引起通信量的快速增加，适合要求撤消列表快速更新的场合，并且实现简单。 关键词：证书撤消，公钥基础设施，二叉树

1. 引言

在身份认证，密钥协商以及数字签名等方面，公开密钥算法有对称密钥算法无可替代的优势。这一类算法越来越多地用来构造各种安全协议，成为安全方案中的关键解决技术。 使用公开密钥算法需要解决用户管理以及密钥绑定的问题，公钥基础设施PKI(Public Key Infrastructure)是解决这一问题的主要途径。

PKI 是一种以公开密钥算法为基础，统一解决密钥发布管理和使用的系统。它不是一个单一的对象或者软件，而是由许多互相联系的组件共同协作来提供一套服务。这些服务使得用户能够简单方便的使用公开密钥系统来解决存在的安全问题。PKI 将用户信息与他的公开密钥绑定为一个整体，然后使用可信的第三方对其进行数字签名，使用者通过验证数字签名来保证公开密钥的有效性。

PKI 中必须要考虑的一个问题是证书撤销。很显然一个当前合法的用户可能在将来的某个时候不再拥有某项权利，所以必须提供一种撤销机制，使得系统能够将已颁发的证书撤销。

证书撤销中主要涉及证书权威、发布服务和证书用户。发布服务是一个数据库,存放CA 发布的有关证书吊销的信息,可使用户高效访问,为用户提供证书有效性查询息。用户访问发布服务查询证书是否被撤销, 发布服务负责回答用户的查询,但发布服务是不被信任的一方,故发布服务回答查询并要给出该回答的有效性的证明,即证明该回答与CA 存放在发布服务中的信息一致,且用户可验证该证明的真实性,故证明中要包含被信任方CA 的签名信息。一旦用户的秘密泄露或怀疑秘密泄露或其他情况,用户可以及时通知CA 吊销其所持有的证书,由CA 通过证书吊销机制,通知其他用户该证书已被吊销。

2. 现有主流证书撤销方案的分析

目前使用最广泛的一种撤销证书的方案是CRL(Certificate Revocation List)，CRL 是X. 509 证书系统中关于证书撤销问题的现行标准解决方案。CRL包含所有被撤销证书的序列号的列表,并含有发行日期、失效日期、CA 的数字签名等信息。CRL由CA 发行更新,更新的CRL 由CA周期性地发送给发布服务, 发布服务在回答一个查询时,将最新的CRL全部传送给查询者,若某个证书的序列号在CRL 中,则查询者确认该证书已被吊销,否则在证书的有效期内该证书有效。CRL 的主要优点是方案简单,但主要问题是用户与发布目录之间繁重的通信量，在大规模的CA中心，由于CA撤销的证书可能很，多用户为了检查一个证书的有效性必须下载整个撤销列表，造成通信的浪费[4]。

为了改善发布服务到查询者的通信代价,Micali 提出了证书撤销系统CRS[3]。其主要思

文中方案使用了排序的二叉树以及散列运算,提出了公钥基础设施中一种改进的证书撤消管理方案——基于线索二叉树搜索树解决方案。该方案不但大大减少了更新撤消列表和查询撤消列表过程中的通信量,改善了撤销列表管理的效率;而且加快撤消列表的更新周期不会引起通信量的快速增

想是CA 周期性地利用单向哈希函数对全部证书状态(即是否有效) 给出一个证明,但对全部证书的周期性证明造成了CA 到发布服务的通信量的增加,且CA 到发布服务的通信成本与更新率成正比,故CRS 方案限制了撤销证书的更新率。

Kocher 提出了CRT方案[2],主要目的是证书验证者能得到一个证书状态(有效还是撤销) 的一个简短证明。CRT是Hash树,其叶子和为一些声明。。CRT 由这样一些声明为叶子的二元哈希树生成。一个证书状态的证明是由其相应的叶子到根结点的路径上所有结点及其子节点的Hash 值构成。

CRT与CRL 相比的主要优点是证明一个证书的状态不需要全部CRT,而只需其中相关路径的部分,且证书拥有者可拥有其证书有效性的简明证明。但其主要缺点是对CRT 的更新计算量过大,被撤销证书的任何一个插入或删除都可能会导致整个CRT的重新计算。

因此本文提出一种改进的线索二叉树的方案，在我们的方案中每一个节点都对应一个撤销证书，所以在相同数量的撤销证书时，树的规模小，并且在更新该树时,不需要对整个树重新计算,仅需计算相关路径，而且由于二叉树的结构更加简单，因此实现更加方便。

3. 基于二叉树的该经的证书撤销方案

本方案基于二叉树，提出了一种改进的证书撤消管理方案,树的节点按照撤消证书的序列号进行排列。树的每一个节点对应于一个撤消的证书,该节点的数据区不仅包含相应证书的序列号,还包括本节点的两个子节点数据区的散列值。如果某一节点缺少一个或两个子节点,则相应的散列值为空。计算一个节点的散列值的参数包括本节点的数据区的证书序列号,以及两个子节点的散列值,如果某一个值为空,则忽略相应的参数。

CA 按照上面的规则建立二叉树后,对二叉树进行签名,其中要包括此二叉树签发的时间以及有效期。签名时首先计算根节点的数据区的散列值,然后使用的私钥对散CA 列值加密。如果对整个二叉树的任意一个节点的数据区进行篡改,都不能通过CA 签名的验证。

为了防止出现畸形的二叉树，树的选择应该使树枝尽量保持平衡。AVL二叉树可以使得各个树叶的深度最多相差1，虽然AVL二叉树的维护要增加一些工作量，但是可以大大提高查询效率，所以本方案采用AVL二叉树[1]。同时为了提高了查找和遍历等操作的效率,本方案决定采用线索二叉树。其典型结构如下：

Lchild Ltag Data Rtag Rchild

图1 典型线索二叉树节点结构

3.1查询撤销证书

用户查询撤消的证书时，首先会向查询目录发送要查询的证书序列号，然后查询目录按照下面两种情况返回查询结果：

1、要查询的证书已经被撤消，即在二叉树中有节点与该证书的序列号相同，查询结果返回该节点，以及从该节点到根节点的路径，以及该路径中的所有节点的数据区内容，和CA对根节点数据区的签名；

2、如果该证书没有被撤消，即二叉树中没有节点与该证书的序列号相同，则不可能在树中找到对应的节点，从根节点开始查询的结果一定是到达某一个节点，而该节点只有一个子节点或本身是一个叶子，如果该节点有左子节点，则该节点对应的序列号小于查询的证书

文中方案使用了排序的二叉树以及散列运算,提出了公钥基础设施中一种改进的证书撤消管理方案——基于线索二叉树搜索树解决方案。该方案不但大大减少了更新撤消列表和查询撤消列表过程中的通信量,改善了撤销列表管理的效率;而且加快撤消列表的更新周期不会引起通信量的快速增

序列号，反之如果该节点有右子节点，则该节点对应的序列号大于查询的证书序列号，查询结果返回该节点，以及从该节点到根节点的路径，该路径中的所有节点的数据区内容和 …… 此处隐藏：5074字，全部文档内容请下载后查看。喜欢就下载吧 ……