论文部分内容阅读
摘要：在PKI中，证书路径的构建是非常重要的过程，也许在可信赖的第三方与终端实体之间有多个候选路径，探讨了PKI路径的构建时蚁群算法的应用，并对PKI路径的构建时最短路径问题进行了研究。
关键词：公钥基础设施；蚁群算法；证书路径构建
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)08-1pppp-0c
为了验证一个证书，在证书与可信赖的第三方之间必须建立一条路径，然而在路径之内的每一个证书必须被核实，这一过程就叫做证书路径的处理[1]。通常情况下，证书路径的处理包括两个阶段[2，3]：证书路径的构建和证书路径的确认。
(1)证书路径的构建
有效的路径总是以被可信赖的第三方发行的证书开始。首先，一个核实者应该发现一条从被验证的证书到一个可信赖的第三方的路径，下一步就是核实者需要获得在路径上的每一个证书。
(2)证书路径的确认
核实者需要验证在路径上的每一个证书需要满足下列条件[1]：
a、证书必须包括有效的密码签名，即：证书的核实者必须通过被发行的公钥来确认证书的内容没有被篡改。
b、通过核实证书的有效的生存周期，证书必须是流通中的。
c、证书必须没有被撤销。
因此，当证书路径很长时，证书路径的处理就是一个负担。
创建证书路径的方法有两种：一种是正向搜索，也就是从目标证书开始向信任锚建立证书路径；另一种是逆向搜索，从信任锚开始向目标证书建立路径。一般说来，在层次模型中，一般适用于向前的方向上构建证书。而在向后的方向上构建模型一般来说更适用于在网状模型。而无论哪种模型的构建的都需要满足上面提到的条件。
在本文中，提出利用蚁群算法来实现路径的构建，因为运用了蚁群算法可以使构建的证书路径的最短，从而使证书路径的处理简单化。
1 蚁群算法
蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。[4]首先，要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小。
在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。
蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。
参数说明：
最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。
信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。
错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。
速度半径表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。
记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。
2 蚁群算法用于PKI路径的建立
在PKI的路径构建及验证的过程中，不管是正向搜索还是逆向搜索都需要在需验证的证书与可信赖的第三方之间建立一个路径，而构建路径的过程可以说与蚂蚁寻找食物的过程类似，即在蚂蚁窝与食物之间构建路径。而最短路径的建立过程实际上与在蚂蚁窝与食物之间构建最短路径相类似。
蚁群算法具有以下特征：
各个蚂蚁互相协作，每只蚂蚁在选择路径时总会参照前只蚂蚁留下的信息素，它提供一种正反馈。因为选择某条路径的蚂蚁越多，其他蚂蚁选择这条路径的可能性就越大，因此将蚁群算法用于PKI的路径构建及验证的过程中，方案如下：
（1）初始化：在PKI的路径构建及验证的过程中，我们假设，在某一时刻，证书数量以及可信赖的第三方的数量保持不变，从证书到可信赖的第三方的路线也不变，所以我们先将证书与可信赖的第三方之间的所有路线求出，全部放在数据库中。当某一个用户需要查询某一证书是否可信赖时（即查询在此证书与可信赖的第三方之间是否有路径相连），根据实时信息，先从数据库中选择可行路径，每条路径上附带一个参数，即蚂蚁信息素。开始将所有路线上信息素的值置0。
（2）选择路线：假设当前用户需要查询的证书为i，当前时刻为t，则从证书i到可信赖的第三方j之间的概率为：
图1 路径建立
3 结束语
本文在深入分析传统的证书路径构建算法的基础上，发现传统集中式的证书路径构建算法中，证书路径构建的复杂性，针对此问题，设计了一个基于蚁群算法的证书路径构建算法，来减少证书路径构建的复杂性，从而实现使证书路径最短。
参考文献：
[1]Internet X.509 Public Key Infrastructure Certificate and CRL profile, RFC3280, 2002.4.
[2]C.Adams,S.Lloyd, Understanding Public Key Infrastructure:Concepts,Standards,and Deployment Considerations,MACMILLAN TECHNICAL PUBLISHING,2000.
[3]Steve Lloyd, Understanding Certification Path Construction, PKI Forum,Sep 2002.
[4]Colomi A,Do~igo M，Maniezzo V．Distributed Optimization byAnt Colonies.In:Pro=of the 1st European Conference on ArtificialLife,Pans,Elsevier,1991.
关键词：公钥基础设施；蚁群算法；证书路径构建
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)08-1pppp-0c
为了验证一个证书，在证书与可信赖的第三方之间必须建立一条路径，然而在路径之内的每一个证书必须被核实，这一过程就叫做证书路径的处理[1]。通常情况下，证书路径的处理包括两个阶段[2，3]：证书路径的构建和证书路径的确认。
(1)证书路径的构建
有效的路径总是以被可信赖的第三方发行的证书开始。首先，一个核实者应该发现一条从被验证的证书到一个可信赖的第三方的路径，下一步就是核实者需要获得在路径上的每一个证书。
(2)证书路径的确认
核实者需要验证在路径上的每一个证书需要满足下列条件[1]：
a、证书必须包括有效的密码签名，即：证书的核实者必须通过被发行的公钥来确认证书的内容没有被篡改。
b、通过核实证书的有效的生存周期，证书必须是流通中的。
c、证书必须没有被撤销。
因此，当证书路径很长时，证书路径的处理就是一个负担。
创建证书路径的方法有两种：一种是正向搜索，也就是从目标证书开始向信任锚建立证书路径；另一种是逆向搜索，从信任锚开始向目标证书建立路径。一般说来，在层次模型中，一般适用于向前的方向上构建证书。而在向后的方向上构建模型一般来说更适用于在网状模型。而无论哪种模型的构建的都需要满足上面提到的条件。
在本文中，提出利用蚁群算法来实现路径的构建，因为运用了蚁群算法可以使构建的证书路径的最短，从而使证书路径的处理简单化。
1 蚁群算法
蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。[4]首先，要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小。
在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。
蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。
参数说明：
最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。
信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。
错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。
速度半径表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。
记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。
2 蚁群算法用于PKI路径的建立
在PKI的路径构建及验证的过程中，不管是正向搜索还是逆向搜索都需要在需验证的证书与可信赖的第三方之间建立一个路径，而构建路径的过程可以说与蚂蚁寻找食物的过程类似，即在蚂蚁窝与食物之间构建路径。而最短路径的建立过程实际上与在蚂蚁窝与食物之间构建最短路径相类似。
蚁群算法具有以下特征：
各个蚂蚁互相协作，每只蚂蚁在选择路径时总会参照前只蚂蚁留下的信息素，它提供一种正反馈。因为选择某条路径的蚂蚁越多，其他蚂蚁选择这条路径的可能性就越大，因此将蚁群算法用于PKI的路径构建及验证的过程中，方案如下：
（1）初始化：在PKI的路径构建及验证的过程中，我们假设，在某一时刻，证书数量以及可信赖的第三方的数量保持不变，从证书到可信赖的第三方的路线也不变，所以我们先将证书与可信赖的第三方之间的所有路线求出，全部放在数据库中。当某一个用户需要查询某一证书是否可信赖时（即查询在此证书与可信赖的第三方之间是否有路径相连），根据实时信息，先从数据库中选择可行路径，每条路径上附带一个参数，即蚂蚁信息素。开始将所有路线上信息素的值置0。
（2）选择路线：假设当前用户需要查询的证书为i，当前时刻为t，则从证书i到可信赖的第三方j之间的概率为：
图1 路径建立
3 结束语
本文在深入分析传统的证书路径构建算法的基础上，发现传统集中式的证书路径构建算法中，证书路径构建的复杂性，针对此问题，设计了一个基于蚁群算法的证书路径构建算法，来减少证书路径构建的复杂性，从而实现使证书路径最短。
参考文献：
[1]Internet X.509 Public Key Infrastructure Certificate and CRL profile, RFC3280, 2002.4.
[2]C.Adams,S.Lloyd, Understanding Public Key Infrastructure:Concepts,Standards,and Deployment Considerations,MACMILLAN TECHNICAL PUBLISHING,2000.
[3]Steve Lloyd, Understanding Certification Path Construction, PKI Forum,Sep 2002.
[4]Colomi A,Do~igo M，Maniezzo V．Distributed Optimization byAnt Colonies.In:Pro=of the 1st European Conference on ArtificialLife,Pans,Elsevier,1991.