姜克鑫, 趙亞慧, 崔榮一
(延邊大學(xué) 工學(xué)院,吉林 延吉 133002)
密碼匹配問題實質(zhì)上是字符串的匹配問題[1].傳統(tǒng)的匹配算法主要有基于字符暴力匹配的BF算法[2-3]和通過消除主串指針回溯的KMP算法[4],其中KMP算法的時間復(fù)雜度雖然低于BF算法,但KMP算法中因存在著相同字符的重復(fù)比較,因此其匹配效率仍相對較低.2019年,李先祥等[5]提出了BM算法.由于BM算法的速度比KMP算法快3~5倍,因此其受到學(xué)者的廣泛關(guān)注.
1956年,Moore等首次提出了有限狀態(tài)自動機的概念[6].隨后,學(xué)者們利用有限狀態(tài)自動機對字符串匹配的問題進(jìn)行了研究.例如:文獻(xiàn)[7]給出了一種高效的有限狀態(tài)自動機的存儲表示方法,并基于這種存儲表示方法建立了一種效率高于KMP算法的模式匹配算法;文獻(xiàn)[8]提出了一種基于自動機的多模式匹配算法(AC算法),該算法在匹配失敗時能夠高效跳轉(zhuǎn),因此其匹配效率較好.但目前相關(guān)研究中所提出的自動機狀態(tài)數(shù)目都是固定不變的,即僅能匹配特定的輸入字符串,因此具有很大的局限性.為此,本文提出了一種新的有限自動機——狀態(tài)數(shù)目可變自動機(variable number of states automata,VNS-DFA),并通過算法分析驗證了該自動機的有效性.
在自動機理論中,自動機都是指抽象的自動機,即是一種能變化和處理信息的離散動態(tài)數(shù)學(xué)模型.自動機可通過形式化語言、狀態(tài)轉(zhuǎn)移圖以及狀態(tài)轉(zhuǎn)移表3種方式進(jìn)行描述[9].目前,自動機主要包括確定型有限狀態(tài)自動機、非確定型有限狀態(tài)自動機、有窮概率自動機[10]、模糊有窮自動機[11]、下推自動機[12]、圖靈機[13]等.其中確定型有限狀態(tài)自動機是一種控制狀態(tài)和符號集都有限的自動機,它能夠?qū)γ總€輸入的字符做出識別,并保證所輸入的字符串都能夠到達(dá)最終的狀態(tài)和路徑[14].由于確定型有限狀態(tài)自動機實現(xiàn)簡單,且能應(yīng)用于字符串匹配中,因此本文選用確定型有限狀態(tài)自動機.
1)有限狀態(tài)自動機.有限狀態(tài)自動機M可表示為一個五元組的形式[15]:
M=(Q,Σ,δ,q0,F).
(1)
其中:Q為狀態(tài)的非空有窮集合;q稱為M的一個狀態(tài);Σ為輸入字母表,輸入字符串都是Σ上的字符串;δ為狀態(tài)轉(zhuǎn)移函數(shù),δ∶Q×Σ→Q,對?(q,a)∈Q×E,δ(q,a)=p,表示M在狀態(tài)q時讀入字母表的字符a,將狀態(tài)q變成p,并處理下一個字符;q0為M的開始狀態(tài),q0∈Q;F為M的終止?fàn)顟B(tài),F(xiàn)?Q.
假設(shè)公式(1)中的Q={q0,q1},Σ={0,1},q0為開始狀態(tài),F(xiàn)={q1}為終止?fàn)顟B(tài),且δ(q0,0)=q0,δ(q0,1)=q1,δ(q1,0)=q0,δ(q1,1)=q1,此時自動機M的狀態(tài)轉(zhuǎn)移圖如圖1所示,其狀態(tài)轉(zhuǎn)移表如表1所示.在圖1中,一個圓圈代表一個狀態(tài),帶標(biāo)簽的箭弧表示轉(zhuǎn)移函數(shù),無標(biāo)簽的箭弧指向的圓圈表示初始狀態(tài),雙圓圈表示終態(tài).在表1中,表的各行對應(yīng)M的狀態(tài),表的各列對應(yīng)輸入事件,其中有箭頭標(biāo)注的狀態(tài)是初始狀態(tài),有*標(biāo)注的狀態(tài)是終態(tài).
圖1 M的狀態(tài)轉(zhuǎn)移圖
表1 M的狀態(tài)轉(zhuǎn)移表
由式(1)可知,上述定義的有限狀態(tài)自動機M只能判別輸入的字符串是否被自動機接受,但無法給出必要的中間結(jié)果和確定自動機M所接受的字符串是什么內(nèi)容.對此,本文在公式(1)中增加了一個輸出字母表Δ以及輸出函數(shù)g∶Q→Δ,且當(dāng)q∈Q時,g(q)=a表示M在q狀態(tài)下輸出a.
2)有限狀態(tài)自動機接受的語言.自動機接受的所有字符串的集合稱為自動機所接受的語言.設(shè)M=(Q,Σ,δ,q0,F)是一個自動機,對于?x∈Σ*,如果δ(q0,x)∈F,則稱x被M接受;如果δ(q0,x)?F,則稱x不被M接受.有限狀態(tài)自動機所接受的語言可表示為:
L(M)={x|x∈Σ*且δ(q0,x)∈F}.
(2)
為提高用戶密碼的安全性,本文設(shè)計了如下用戶注冊和用戶登錄的流程:用戶注冊時首先設(shè)置密碼,然后系統(tǒng)對密碼進(jìn)行同態(tài)映射加密;用戶登錄系統(tǒng)時,為防止密碼被偷窺,將密碼隱藏在所輸入的字符串中.為了接受這些隱藏在字符串中的密碼,本文構(gòu)造了一種VNS-DFA自動機,只要用戶輸入的密碼被該自動機正確識別即可成功登錄.密碼設(shè)置和VNS-DFA自動機識別的過程如圖2所示.
圖2 密碼設(shè)置和識別的過程
f-1(w)={x|f(x)=w且x∈Σ*}.
(3)
由式(3)可知,若w是經(jīng)過加密之后的密碼,則w的原始密碼應(yīng)包含在它的同態(tài)原像中.
本文設(shè)計的狀態(tài)數(shù)目可變自動機(VNS-DFA)可用如下的七元組表示:
M=(Q,Σ,Δ,δ,q0,F,g).
(4)
其中:Q,δ,q0,F的含義與DFA中的含義相同;g為輸出函數(shù),?q∈Q,a∈Σ,g(q)=a, 即在滿足條件的狀態(tài)q下輸出原始字符a;Σ為輸出字母表;Δ為Σ經(jīng)過同態(tài)映射之后的輸入字母表.
根據(jù)自動機的結(jié)構(gòu)及原理,本文構(gòu)造的VNS-DFA算法(算法1)的具體步驟如下所示:
輸入:原始串s,驗證串t.
輸出:加密串在驗證串中出現(xiàn)的次數(shù).
Step 1 將串s進(jìn)行加密,得到串s1.
Step 2 初始化自動機狀態(tài)轉(zhuǎn)移矩陣A,并對其元素全部賦值為0.
Step 3 修改矩陣A,其中m為s1的長度, 0為初態(tài),n為終態(tài).具體修改規(guī)則如下:
A[0][s1[0]]=1;
A[n][s1[0]]=n+1;
A[n+1][s1[1]]=2;
ifs1[0]= =s1[m-1];
A[n][s1[1]]=2;
A[i][s1[0]]=n+1,A[i][s1[i]]=i+1,i=1,…,m-1.
Step 4 初始狀態(tài)k=0,匹配成功次數(shù)count=0,待匹配字符位置i=0.
Step 5 如果i= =n回到Step 6;否則,跳轉(zhuǎn)至新的狀態(tài)j=A[k][s1[i]],并將j賦值給k;
ifj= =特定狀態(tài),輸出相應(yīng)數(shù)字,回到Step 5;
ifj= =n-1匹配成功,count+1,回到Step 5;
i=i+1.
Step 6 結(jié)束.
算法1中:輸入是原始密碼s和用戶驗證登錄密碼t,輸出是t在s中是否出現(xiàn)及其出現(xiàn)的次數(shù),矩陣A為自動機的狀態(tài)轉(zhuǎn)移矩陣,m為原始密碼經(jīng)過同態(tài)映射后的密碼長度,0為初始狀態(tài),n為終止?fàn)顟B(tài).
Step 3為算法1的核心.在由Step 3建立好的自動機中輸入某個字符時,若自動機成功匹配,則跳轉(zhuǎn)至下一狀態(tài),否則跳轉(zhuǎn)至初始狀態(tài).Step 5為算法1的匹配過程,當(dāng)且僅當(dāng)狀態(tài)跳轉(zhuǎn)為終態(tài)時,輸入的字符串才能被自動機所接受,同時輸出其同態(tài)原像.
對于任意一個輸入串a(chǎn)1a2…an,根據(jù)文獻(xiàn)[16]中的定理1(對于任意的q∈Q,w∈Σ*,a∈Σ,都有δ(q,wa)=δ(δ(q,w),a))可以得到如下式子:
δ(0,a1a2…an)=δ(δ(0,a1a2…an-1),an)=δ(δ…(δ(0,a1)…),an).
(5)
根據(jù)算法1的轉(zhuǎn)移規(guī)則(δ(0,a1)=1,…,δ(n-1,an)=n),可將式(5)轉(zhuǎn)變?yōu)椋?/p>
δ(δ…(δ(0,a1)…),an)=δ(δ…(δ(1,a2)…),an)=δ(n-1,an)=n.
(6)
由式(6)可得
δ(0,a1a2…an)=δ(δ…(δ(1,a2)…),an)=δ(n-1,an)=n.
(7)
由式(7)可知,自動機在初態(tài)時可接受字符串a(chǎn)1a2…an,并且最后可到達(dá)終態(tài).根據(jù)本文提出的算法所構(gòu)造的識別串a(chǎn)1a2…an的有限狀態(tài)自動機如圖3所示.
圖3 識別a1a2…an的有限狀態(tài)自動機
本文以輸入密碼s為例驗證本文構(gòu)造的自動機能夠接受該密碼.假設(shè)s= ′12′,且s對應(yīng)的同態(tài)映射為f(1)= ′one′,f(2)= ′two′.在該假設(shè)下匹配該密碼的自動機如圖4所示.由圖4可知:當(dāng)輸入的字符串中只要包含′onetwo′,該自動機就可接受該字符串;當(dāng)自動機匹配到′one′時,自動機輸出′one′對應(yīng)的同態(tài)原像′1′;當(dāng)自動機匹配到′two′時,自動機輸出′onetwo′對應(yīng)的同態(tài)原像′12′.由以上可知,本文提出的自動機能夠匹配包含加密密碼的字符串,并能夠輸出用戶輸入的原始密碼,因此本文構(gòu)造的自動機是有效的.
圖4 識別原始串′12′的有限狀態(tài)自動機
自動機算法的復(fù)雜度通常包括建立算法的時間復(fù)雜度和匹配字符的時間復(fù)雜度.為了驗證VNS-DFA算法的有效性,本文將VNS-DFA算法的時間復(fù)雜度、空間復(fù)雜度與傳統(tǒng)的DFA和改進(jìn)后的DFA的時間復(fù)雜度、空間復(fù)雜度進(jìn)行了對比,結(jié)果如表1所示.實驗中,將待匹配串的長度設(shè)置為m, 輸入串的長度設(shè)置為n, 字母長設(shè)置為|Δ|.
由表2可知:在時間復(fù)雜度上,在輸入規(guī)模相同的情況下3種算法在字符匹配的過程中的時間復(fù)雜度均為Θ(n),但VNS-DFA算法的建立時間最短(復(fù)雜度為O(m));在空間復(fù)雜度上,在輸入規(guī)模相同的情況下其差別不大.這是因為3種算法都可用二維數(shù)組表示狀態(tài)轉(zhuǎn)移矩陣,因此其大小取決于自動機的狀態(tài)個數(shù)以及輸入字母表的長度.
表2 3種不同算法的復(fù)雜度
研究表明,本文構(gòu)造的VNS-DFA能夠匹配任意輸入的字符串,且其匹配速率優(yōu)于傳統(tǒng)的DFA及改進(jìn)的DFA,因此本文方法可以用于密碼的識別.在本文的算法中,當(dāng)待匹配的字符串長度較大時,會因自動機的狀態(tài)數(shù)目增多而導(dǎo)致耗費更多的內(nèi)存空間.因此在今后的研究中,我們將對自動機的狀態(tài)數(shù)目進(jìn)行改進(jìn),以節(jié)約內(nèi)存空間.