基于自動機理論的密碼匹配方法

姜克鑫， 趙亞慧， 崔榮一

(延邊大學(xué) 工學(xué)院，吉林 延吉 133002)

0 引言

密碼匹配問題實質(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)，并通過算法分析驗證了該自動機的有效性.

1 有限狀態(tài)自動機

在自動機理論中，自動機都是指抽象的自動機，即是一種能變化和處理信息的離散動態(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)

2 狀態(tài)數(shù)目可變自動機(VNS-DFA)的構(gòu)造

為提高用戶密碼的安全性，本文設(shè)計了如下用戶注冊和用戶登錄的流程：用戶注冊時首先設(shè)置密碼，然后系統(tǒng)對密碼進(jìn)行同態(tài)映射加密;用戶登錄系統(tǒng)時，為防止密碼被偷窺，將密碼隱藏在所輸入的字符串中.為了接受這些隱藏在字符串中的密碼，本文構(gòu)造了一種VNS-DFA自動機，只要用戶輸入的密碼被該自動機正確識別即可成功登錄.密碼設(shè)置和VNS-DFA自動機識別的過程如圖2所示.

圖2 密碼設(shè)置和識別的過程

2.1 密碼加密的過程

f-1(w)={x|f(x)=w且x∈Σ*}.

(3)

由式(3)可知，若w是經(jīng)過加密之后的密碼，則w的原始密碼應(yīng)包含在它的同態(tài)原像中.

2.2 自動機的構(gòu)造及識別

本文設(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)原像.

3 算法分析

3.1 算法的有效性證明

對于任意一個輸入串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)自動機

3.2 算法的復(fù)雜度分析

自動機算法的復(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ù)雜度

4 結(jié)論

研究表明，本文構(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)存空間.