利用蟻群算法來解決ＰＫＩ中最短路徑問題

摘要：在PKI中，證書路徑的構(gòu)建是非常重要的過程，也許在可信賴的第三方與終端實(shí)體之間有多個(gè)候選路徑，探討了PKI路徑的構(gòu)建時(shí)蟻群算法的應(yīng)用，并對(duì)PKI路徑的構(gòu)建時(shí)最短路徑問題進(jìn)行了研究。

關(guān)鍵詞：公鑰基礎(chǔ)設(shè)施；蟻群算法；證書路徑構(gòu)建

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)08-1pppp-0c

為了驗(yàn)證一個(gè)證書，在證書與可信賴的第三方之間必須建立一條路徑，然而在路徑之內(nèi)的每一個(gè)證書必須被核實(shí)，這一過程就叫做證書路徑的處理[1]。通常情況下，證書路徑的處理包括兩個(gè)階段[2，3]：證書路徑的構(gòu)建和證書路徑的確認(rèn)。

(1)證書路徑的構(gòu)建

有效的路徑總是以被可信賴的第三方發(fā)行的證書開始。首先，一個(gè)核實(shí)者應(yīng)該發(fā)現(xiàn)一條從被驗(yàn)證的證書到一個(gè)可信賴的第三方的路徑，下一步就是核實(shí)者需要獲得在路徑上的每一個(gè)證書。

(2)證書路徑的確認(rèn)

核實(shí)者需要驗(yàn)證在路徑上的每一個(gè)證書需要滿足下列條件[1]：

a、證書必須包括有效的密碼簽名，即：證書的核實(shí)者必須通過被發(fā)行的公鑰來確認(rèn)證書的內(nèi)容沒有被篡改。

b、通過核實(shí)證書的有效的生存周期，證書必須是流通中的。

c、證書必須沒有被撤銷。

因此，當(dāng)證書路徑很長(zhǎng)時(shí)，證書路徑的處理就是一個(gè)負(fù)擔(dān)。

創(chuàng)建證書路徑的方法有兩種：一種是正向搜索，也就是從目標(biāo)證書開始向信任錨建立證書路徑；另一種是逆向搜索，從信任錨開始向目標(biāo)證書建立路徑。一般說來，在層次模型中，一般適用于向前的方向上構(gòu)建證書。而在向后的方向上構(gòu)建模型一般來說更適用于在網(wǎng)狀模型。而無(wú)論哪種模型的構(gòu)建的都需要滿足上面提到的條件。

在本文中，提出利用蟻群算法來實(shí)現(xiàn)路徑的構(gòu)建，因?yàn)檫\(yùn)用了蟻群算法可以使構(gòu)建的證書路徑的最短，從而使證書路徑的處理簡(jiǎn)單化。

1 蟻群算法

蟻群算法(ant colony optimization， ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。[4]首先，要讓螞蟻能夠避開障礙物，就必須根據(jù)適當(dāng)?shù)牡匦谓o它編進(jìn)指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點(diǎn)；再次，如果要讓螞蟻找到最短的路徑，那么需要計(jì)算所有可能的路徑并且比較它們的大小。

在沒有螞蟻找到食物的時(shí)候，環(huán)境沒有有用的信息素，那么螞蟻為什么會(huì)相對(duì)有效的找到食物呢？這要?dú)w功于螞蟻的移動(dòng)規(guī)則，尤其是在沒有信息素時(shí)候的移動(dòng)規(guī)則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動(dòng)（開始，這個(gè)前方是隨機(jī)固定的一個(gè)方向），而不是原地?zé)o謂的打轉(zhuǎn)或者震動(dòng)；其次，螞蟻要有一定的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運(yùn)動(dòng)下去，而是有一個(gè)隨機(jī)的干擾。這樣就使得螞蟻運(yùn)動(dòng)起來具有了一定的目的性，盡量保持原來的方向，但又有新的試探，尤其當(dāng)碰到障礙物的時(shí)候它會(huì)立即改變方向，這可以看成一種選擇的過程，也就是環(huán)境的障礙物讓螞蟻的某個(gè)方向正確，而其他方向則不對(duì)。這就解釋了為什么單個(gè)螞蟻在復(fù)雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。當(dāng)然，在有一只螞蟻找到了食物的時(shí)候，其他螞蟻會(huì)沿著信息素很快找到食物的。

螞蟻如何找到最短路徑的？這一是要?dú)w功于信息素，另外要?dú)w功于環(huán)境，具體說是計(jì)算機(jī)時(shí)鐘。信息素多的地方顯然經(jīng)過這里的螞蟻會(huì)多，因而會(huì)有更多的螞蟻聚集過來。假設(shè)有兩條路從窩通向食物，開始的時(shí)候，走這兩條路的螞蟻數(shù)量同樣多。當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來，這樣，短的路螞蟻來回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會(huì)多，自然會(huì)有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長(zhǎng)的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。

參數(shù)說明：

最大信息素：螞蟻在一開始擁有的信息素總量，越大表示程序在較長(zhǎng)一段時(shí)間能夠存在信息素。

信息素消減的速度：隨著時(shí)間的流逝，已經(jīng)存在于世界上的信息素會(huì)消減，這個(gè)數(shù)值越大，那么消減的越快。

錯(cuò)誤概率表示這個(gè)螞蟻不往信息素最大的區(qū)域走的概率，越大則表示這個(gè)螞蟻越有創(chuàng)新性。

速度半徑表示螞蟻一次能走的最大長(zhǎng)度，也表示這個(gè)螞蟻的感知范圍。

記憶能力表示螞蟻能記住多少個(gè)剛剛走過點(diǎn)的坐標(biāo)，這個(gè)值避免了螞蟻在本地打轉(zhuǎn)，停滯不前。而這個(gè)值越大那么整個(gè)系統(tǒng)運(yùn)行速度就慢，越小則螞蟻越容易原地轉(zhuǎn)圈。

2 蟻群算法用于PKI路徑的建立

在PKI的路徑構(gòu)建及驗(yàn)證的過程中，不管是正向搜索還是逆向搜索都需要在需驗(yàn)證的證書與可信賴的第三方之間建立一個(gè)路徑，而構(gòu)建路徑的過程可以說與螞蟻尋找食物的過程類似，即在螞蟻窩與食物之間構(gòu)建路徑。而最短路徑的建立過程實(shí)際上與在螞蟻窩與食物之間構(gòu)建最短路徑相類似。

蟻群算法具有以下特征：

各個(gè)螞蟻互相協(xié)作，每只螞蟻在選擇路徑時(shí)總會(huì)參照前只螞蟻留下的信息素，它提供一種正反饋。因?yàn)檫x擇某條路徑的螞蟻越多，其他螞蟻選擇這條路徑的可能性就越大，因此將蟻群算法用于PKI的路徑構(gòu)建及驗(yàn)證的過程中，方案如下：

（1）初始化：在PKI的路徑構(gòu)建及驗(yàn)證的過程中，我們假設(shè)，在某一時(shí)刻，證書數(shù)量以及可信賴的第三方的數(shù)量保持不變，從證書到可信賴的第三方的路線也不變，所以我們先將證書與可信賴的第三方之間的所有路線求出，全部放在數(shù)據(jù)庫(kù)中。當(dāng)某一個(gè)用戶需要查詢某一證書是否可信賴時(shí)（即查詢?cè)诖俗C書與可信賴的第三方之間是否有路徑相連），根據(jù)實(shí)時(shí)信息，先從數(shù)據(jù)庫(kù)中選擇可行路徑，每條路徑上附帶一個(gè)參數(shù)，即螞蟻信息素。開始將所有路線上信息素的值置0。

（2）選擇路線：假設(shè)當(dāng)前用戶需要查詢的證書為i，當(dāng)前時(shí)刻為t，則從證書i到可信賴的第三方j(luò)之間的概率為：

Candidate為需查詢的證書i與可信賴的第三方之間的候選集，Rij(t)為弧（i，j）在t時(shí)刻的信息強(qiáng)度，代表以前的信息；Sij為需查詢的證書i與可信賴的第三方之間的路徑的經(jīng)過的方便程度，代表實(shí)時(shí)信息；a為以前信息的重要性（a≥0）；b代表當(dāng)前信息的重要性（b≥0）。

（3）每次選擇完路徑后要根據(jù)實(shí)際情況重新確定信息素的值，

R_ij（new）=m＊R_ij(old)+ΔR_ij，

式中，m為信息的持久性，（0≤m≤1），也可以將1-m理解為信息的衰減度，

R_ij為螞蟻所留信息量的一個(gè)常數(shù)。

選擇某路徑的次數(shù)越多，說明此路徑是比較短的路徑，其信息素的值也越大，為以后選擇路徑提供必要的信息。

從文獻(xiàn)3的一個(gè)簡(jiǎn)單的圖中（即圖1），我們也會(huì)發(fā)現(xiàn)在一個(gè)可信賴的第三方與目標(biāo)證書之間有多個(gè)候選路徑。例如，在圖1中交叉證書的例子，在用戶3的可信賴的第三方與用戶2的證書之間有2個(gè)候選路徑(如：CA7->CA5->CA0->CA2->CA4->User2 和 CA7->CA6->CA5->CA0->CA2->CA4->User2)。對(duì)于多個(gè)候選證書可能都一樣符合證書的評(píng)價(jià)標(biāo)準(zhǔn)。

如果采用了蟻群算法后，更趨向于采用前一路徑，因?yàn)橄伻核惴梢哉业阶疃搪窂剑疚囊彩蔷投鄠€(gè)路徑均可成為候選路徑時(shí)，采用蟻群算法獲取最短路徑。

圖1 路徑建立

3 結(jié)束語(yǔ)

本文在深入分析傳統(tǒng)的證書路徑構(gòu)建算法的基礎(chǔ)上，發(fā)現(xiàn)傳統(tǒng)集中式的證書路徑構(gòu)建算法中，證書路徑構(gòu)建的復(fù)雜性，針對(duì)此問題，設(shè)計(jì)了一個(gè)基于蟻群算法的證書路徑構(gòu)建算法，來減少證書路徑構(gòu)建的復(fù)雜性，從而實(shí)現(xiàn)使證書路徑最短。

參考文獻(xiàn)：

[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.