圖形密碼中一類特殊圖的幾種標(biāo)號

顧彥波, 李敬文, 王露露

(蘭州交通大學(xué) 電子與信息工程學(xué)院, 蘭州 730070)

1 引言與預(yù)備知識

目前人們經(jīng)常使用的密碼一般是文本密碼[1], 用戶設(shè)置密碼時要符合強口令的要求, 還要經(jīng)常更換, 增加了記憶負(fù)擔(dān), 且實際生活中用戶記下密碼或者在不同場景中使用相同的密碼, 都會給系統(tǒng)安全帶來隱患. 圖形密碼是利用人們對圖形記憶優(yōu)于對文本記憶的特點而設(shè)計的一種新型密碼[2-3], 用戶不用記憶冗長的字符串, 而是通過識別或記住圖形進(jìn)行身份驗證. 如果可能的圖形數(shù)量足夠大, 圖形密碼的密鑰空間可以遠(yuǎn)超過文本密碼, 即可以更好地抵抗暴力破解和字典攻擊等. 利用拓?fù)鋱D加數(shù)論等技術(shù)產(chǎn)生的圖形密碼, 具有動態(tài)性強、 智商高、 組合方式無窮多、 存儲量多、 運算快等優(yōu)點, 可達(dá)到使用者易記憶、 進(jìn)攻者難破譯的基本要求[4-5]. 目前, 關(guān)于各類圖各種標(biāo)號的研究已取得了很大進(jìn)展[6-15]. 本文研究由層次級聯(lián)圖疊加構(gòu)成孿生頂點重疊圖以及圈加層次級聯(lián)圖構(gòu)成的單圈圖, 以提供新型的圖形密碼.

本文用[m,n]表示整數(shù)集合{m,m+1,…,n}； 用[s,t]o表示奇數(shù)集合{s,s+2,…,t}, 其中s,t是奇數(shù)； 用[a,b]e表示偶數(shù)集合{a,a+2,…,b}, 其中a,b是偶數(shù). 集合X的元素個數(shù)記為|X|. 具有p個頂點、q條邊的圖稱為(p,q)-圖.

定義1[4-6]若(p,q)-圖G有一個映射f:V(G)→[0,2q-1], 使得任何兩個不同頂點u,v∈V(G)的標(biāo)號滿足f(u)≠f(v), 且邊標(biāo)號集合為

f(E(G))={f(uv)=[f(u)+f(v)](mod 2q):uv∈E(G)}=[1,2q-1]o,

則稱f為圖G的一個奇優(yōu)雅標(biāo)號, 圖G為奇優(yōu)雅圖. 如果G是二部圖, (X,Y)是其頂點集合的二分類, 且有max{f(x):x∈X}

定義2[4-6]若(p,q)-圖G有一個映射f:V(G)→[0,2q-1], 使得不同頂點u,v∈V(G)的標(biāo)號滿足f(u)≠f(v), 且邊標(biāo)號集合為

f(E(G))={|f(u)-f(v)|:uv∈E(G)}=[1,2q-1]o,

則稱f為圖G的一個奇優(yōu)美標(biāo)號. 如果G是二部分圖, (X,Y)是其頂點集合的二部分劃分, 且有max{f(x):x∈X}

定義3[7]若一個(p,q)-圖G有兩個子圖K和L, 使得V(K)∩V(L)=w,E(G)=E(K)∪E(L), 則將G寫作G=K◇L, 稱其為頂點重疊圖. 進(jìn)一步, 如果q=2|E(K)|=2|E(L)|, 則稱G為一致頂點重疊(p,q)-圖.

設(shè)一致頂點重疊(p,q)-圖G=K◇L有一個映射f:V(G)→[0,q], 使得:

(i) 每對頂點x,y∈V(G)都滿足f(x)≠f(y);

(ii)f是子圖K的一個奇優(yōu)美標(biāo)號；

(iii) 邊標(biāo)號集合f(E(G))={f(xy)=|f(x)-f(y)|:xy∈E(G)}=[1,q-1]o.

則稱G是一個孿生奇優(yōu)美頂點重疊(p,q)-圖, 稱f是圖G的一個孿生奇優(yōu)美標(biāo)號, 稱K為源圖, 稱L為源圖K的一個伴隨圖.

下面給出本文的研究對象. 設(shè)當(dāng)n=1時, 層次級聯(lián)圖的總個數(shù)為p1=5； 一層的層次級聯(lián)圖H1頂點的序列號分為兩部分, 分別為X1={x1,x2,x3}和Y1={y1,y2}； 頂點之間的邊為E(H1)={x1y1,x2y2,y2x3,y2x1}. 設(shè)當(dāng)n=2時, 層次級聯(lián)圖的總個數(shù)為p2=11； 二層的層次級聯(lián)圖H2頂點的序列號分為兩部分, 分別為X2=X1∪{x4,x5,x6}和Y2=Y1∪{y3,y4,y5}； 頂點之間的邊為

E(H2)=E(H1)∪{x3y3,x5y5,y3x4,y4x5,y5x6,y5x3}.

依次當(dāng)n=k時, 層次級聯(lián)圖的總個數(shù)為pk=(k+2)(k+1)-1；k層的層次級聯(lián)圖Hk頂點的序列號分為兩部分, 分別為

(1)

頂點之間的邊為

E(Hk)=E(Hk-1)∪{x(k+1)k/2y(k+1)k/2,…,y(k+1)k/2x(k+1)k/2+1,…,y(k+2)(k+1)/2x(k+1)k/2}.

(2)

層次級聯(lián)圖頂點的序號如圖1所示.

圖1 層次級聯(lián)圖的頂點序號

圖2 單圈圖Cn⊕Hk的頂點序號

把圈Cn上一個頂點與層次級聯(lián)圖Hk上一個頂點用一條邊粘接起來而形成的圖稱為單圈圖Cn⊕Hk, 如圖2所示. 記圈Cn的頂點序號為ui(i=1,2,…)和vi(i=1,2,…); 層次級聯(lián)圖Hk的頂點序號為xi(i=1,2,…,(k+2)(k+1)/2)和yi(i=1,2,…,(k+2)(k+1)/2-1).

2 主要結(jié)果

定理1由圈C4m上一個頂點與層次級聯(lián)圖Hk的x(k+2)(k+1)/2頂點用一條邊連接構(gòu)成的單圈圖C4m⊕Hk是集有序奇優(yōu)雅圖, 其中：m=1,2,…;k=1,2,….

1)f(v2m)=2t+2i=2t+4m,i=2m；

2)f(xi)=f(v2m)-2i+2=2t+4m-2i+2,i=1,2,…,t；

3)f(yi)=8m+4t-2i-1,i=1,2,…,t-1；

4)f(ui)=8m+2t-2i+1,i=1,2,…,2m；

5)f(vi)=f(v2m)-2t-2i+2=2t+4m-2t-2i+2=4m-2i+2,i=1,2,…,m；

6)f(vi)=f(v2m)-2t-2i=2t+4m-2t-2i=4m-2i,i=m+1,m+2,…,2m.

記f(X)=[4m+2,4m+2t],f(Y)=[8m+2t+1,8m+4t-3],f(U)=[4m+2t+1,8m+2t-1],f(V)=[0,2m-2]∪[2m+2,4m]. 易見fmax(X)

所以

f(V(C4m⊕Hk))=f(X∪Y∪U∪V)=[0,8m+4t-3].

其次證所有邊標(biāo)號互不相同.

1) 圈C4m的頂點標(biāo)號為

f(v2m)=2t+2i=2t+4m,i=2m;

f(ui)=8m+2t-2i+1,i=1,2,…,2m;

f(vi)=f(v2m)-2t-2i+2=2t+4m-2t-2i+2=4m-2i+2,i=1,2,…,m;

f(vi)=f(v2m)-2t-2i=2t+4m-2t-2i=4m-2i,i=m+1,m+2,…,2m.

當(dāng)i=1,2,…,m時, 邊標(biāo)號

當(dāng)m取值很小時會出現(xiàn)負(fù)值, 其中如果出現(xiàn)負(fù)數(shù)則對應(yīng)加2q表示其對應(yīng)的邊標(biāo)號. 當(dāng)i=m+1,m+2,…,2m時, 邊標(biāo)號

當(dāng)i=1,2,…,m時, 邊標(biāo)號

當(dāng)m取值很小時會出現(xiàn)負(fù)值, 其中如果出現(xiàn)負(fù)數(shù)則對應(yīng)加2q表示其對應(yīng)的邊標(biāo)號. 當(dāng)i=m+1,m+2,…,2m-1時, 邊標(biāo)號

邊標(biāo)號

f(E(u1v2m))=[f(u1)+f(v2m)](mod 2q)=[(8m+2t-2+1)+0](mod 2q)={8m+2t-1}.

即圈上所有的邊標(biāo)號互不相同,f(E(uv))=[4m-2t+1,8m+2t+3]o, 當(dāng)m取值很小時會出現(xiàn)負(fù)值, 其中如果出現(xiàn)負(fù)數(shù)則對應(yīng)加2q表示其對應(yīng)的邊標(biāo)號.

2) 粘連邊的邊標(biāo)號為

當(dāng)m取值很小時會出現(xiàn)負(fù)值, 其中如果出現(xiàn)負(fù)數(shù)則對應(yīng)加2q表示其對應(yīng)的邊標(biāo)號.

3) 用數(shù)學(xué)歸納法證明： 當(dāng)n=1時, 層次級聯(lián)圖的總個數(shù)為p1=5, 則t=3； 第一層的層次級聯(lián)圖H1頂點序列號分為兩部分, 分別為X1={x1,x2,x3}和Y1={y1,y2}； 且頂點之間的邊為E(H1)={x1y1,x2y2,y2x3,y2x1}； 則H1的頂點標(biāo)號和邊標(biāo)號分別為

f(X1)={4m+6,4m+4,4m+2},f(Y1)={8m+9,8m+7},

f(E(H1))=[f(X1)+f(Y1)](mod 2q)={4m+5,4m+3,4m+1,4m-1}

成立； 假設(shè)當(dāng)n=k時, 層次級聯(lián)圖的總個數(shù)為pk=(k+2)(k+1)-1=2t-1； 第k層的層次級聯(lián)圖Hk頂點的序列號分為兩部分, 分別為式(1), 且頂點之間的邊為式(2); 則Hk的頂點標(biāo)號和邊標(biāo)號分別為

f(Xk)=[4m+2,4m+2t],f(Yk)=[8m+2t+1,8m+4t-3],

f(E(Hk))=[f(Xk)+f(Yk)](mod 2q)=[4m-2t+5,4m+2t-1],

當(dāng)m取值很小時會出現(xiàn)負(fù)值, 其中如果出現(xiàn)負(fù)數(shù)則對應(yīng)加2q表示其對應(yīng)的邊標(biāo)號, 結(jié)論成立； 當(dāng)n=k+1時, 層次級聯(lián)圖的總個數(shù)為pk+1=(k+3)(k+2)-1；k+1層的層次級聯(lián)圖Hk+1頂點的序列號分為兩部分, 分別為

(3)

且頂點之間的邊為

則Hk+1的頂點標(biāo)號和邊標(biāo)號分別為

f(Xk+1)=[4m+2,4m+(k+2)(k+3)],

f(Yk+1)=[8m+(k+2)(k+3)+1,8m+2(k+2)(k+3)-3],

結(jié)論成立, 證明了所有邊標(biāo)號互不相同, 即f(E(H))=[4m-2t+5,4m+2t-1]o, 當(dāng)m取值很小時會出現(xiàn)負(fù)值, 其中如果出現(xiàn)負(fù)數(shù)則對應(yīng)加2q表示其對應(yīng)的邊標(biāo)號.

綜上證明了單圈圖C4m⊕Hk的頂點標(biāo)號滿足[0,8m+4t-3], 且fmax(X)

圖3為定理1的一個實例.

圖3 單圈圖C4⊕H2與C8⊕H2的集有序奇優(yōu)雅標(biāo)號

定理2由圈C4m+2上一個頂點與層次級聯(lián)圖Hk的x(k+2)(k+1)/2頂點用一條邊粘連構(gòu)成的單圈圖C4m+2⊕Hk是奇優(yōu)美圖, 其中:m=1,2,…;k=1,2,….

1)f(xi)=2i-2,i=1,2,…,t；

2)f(yi)=8m+4t-2i+3,i=1,2,…,t-1；

3)f(ui)=8m+2t-2i+5,i=1,2,…,m+1；

4)f(ui)=8m+2t-2i+3,i=m+2,m+3,…,2m+1；

5)f(vi)=2t+2i-2,i=1,2,…,2m；

6)f(v4m+2)=4m+2t+2.

記f(X)=[0,2t-2]e,f(Y)=[8m+2t+5,8m+4t+1]o,f(U)=[4m+2t+1,6m+2t-1]o∪[6m+2t+3,8m+2t+3]o,f(V)=[2t,4m+2t-2]e∪{4m+2t+2}. 易見f(X)≠f(Y)≠f(U)≠f(V), 即所有的頂點標(biāo)號各不相同. 首先證明單圈圖C4m+2⊕Hk是奇優(yōu)美標(biāo)號. 由上述標(biāo)號知, 頂點的最大標(biāo)號為f(y1)=8m+4t+1, 頂點的最小標(biāo)號為f(x1)=0. 又有

所以

f(V(C4m+2⊕Hk))=f(X∪Y∪U∪V)=[0,8m+4t+1].

其次證所有邊標(biāo)號互不相同.

1) 圈C4m+2的頂點標(biāo)號為

f(ui)=8m+2t-2i+5,i=1,2,…,m+1；

f(ui)=8m+2t-2i+3,i=m+2,m+3,…,2m+1；

f(vi)=2t+2i-2,i=1,2,…,2m；f(v4m+2)=4m+2t+2.

則邊標(biāo)號

f(uivi)=|f(ui)-f(vi)|=|(8m+2t-2i+5)-(2t+2i-2)|=8m-4i+7,i=1,2,…,m+1,

f(E(uivi))={4m+3,4m+7,…,8m+3};

邊標(biāo)號

f(uivi)=|f(ui)-f(vi)|=|(8m+2t-2i+3)-(2t+2i-2)|=8m-4i+5,i=m+2,…,2m,

f(E(uivi))={5,9,…,4m-3};

邊標(biāo)號

f(ui+1vi)=|f(ui+1)-f(vi)|=|[8m+2t-2(i+1)+5]-(2t+2i-2)|=8m-4i+5,i=1,2,…,m,

f(E(ui+1vi))={4m+5,4m+9,…,8m+1};

邊標(biāo)號

f(E(ui+1vi))={3,7,…,4m-1};

邊標(biāo)號

f(u2m+1v2m+1)=|f(u2m+1)-f(v2m+1)|=|[8m+2t-2(2m+1)+3]-(2t+4m+2)|=1,

f(E(u2m+1v2m+1))={1};

邊標(biāo)號

f(u1v2m+1)=|f(u1)-f(v2m+1)|=|(8m+2t-2+5)-(2t+4m+2)|=4m+1,

f(E(u1v2m+1))={4m+1}.

即圈上所有的邊標(biāo)號互不相同,f(E(uv))=[1,8m+3]o.

2) 粘連邊的邊標(biāo)號為

f(u1x2t-1)=|f(u1)-f(x2t-1)|=|(8m+2t-2+5)-(2t-2)|=8m+5,

f(E(u1v2t-1))={8m+5}.

3) 用數(shù)學(xué)歸納法證明： 當(dāng)n=1時, 層次級聯(lián)圖的總個數(shù)為p1=5, 則t=3, 第一層的層次級聯(lián)圖H1頂點的序列號分為兩部分, 分別為X1={x1,x2,x3}和Y1={y1,y2}； 且頂點之間的邊為E(H1)={x1y1,x2y2,y2x3,y2x1}； 則H1的頂點標(biāo)號和邊標(biāo)號分別為f(X1)={0,2,4},f(Y1)={8m+11,8m+13},

f(E(H1))=|f(X1)-f(Y1)|={8m+7,8m+9,8m+11,8m+13}

成立； 假設(shè)當(dāng)n=k時, 層次級聯(lián)圖的總個數(shù)為pk=(k+2)(k+1)-1=2t-1； 第k層的層次級聯(lián)圖Hk頂點的序列號分為兩部分, 分別為式(1), 且頂點之間的邊為式(2); 則Hk的頂點標(biāo)號和邊標(biāo)號分別為

f(Xk)=[0,2t-2]e,f(Yk)=[8m+2t+5,8m+4t+1]o,

f(E(Hk))=|f(Xk)-f(Yk)|=[8m+7,8m+4t+1]o,

結(jié)論成立； 當(dāng)n=k+1時, 層次級聯(lián)圖的總個數(shù)為pk+1=(k+3)(k+2)-1； 第k+1層的層次級聯(lián)圖Hk+1頂點的序列號分為兩部分, 分別為式(3)； 且頂點之間的邊為式(4); 則Hk+1的頂點標(biāo)號和邊標(biāo)號分別為

結(jié)論成立. 從而證明了層次級聯(lián)圖Hk的所有邊標(biāo)號互不相同, 即f(E(H))=[8m+7,8m+4t+1]o.

綜上證明了單圈圖C4m+2⊕Hk的頂點標(biāo)號滿足[0,8m+4t+1], 邊標(biāo)號滿足[1,8m+4t+1]o, 故單圈圖C4m+2⊕Hk是奇優(yōu)美圖. 證畢.

圖4為定理2的一個實例.

圖4 單圈圖C6⊕H2和C10⊕H2的奇優(yōu)美標(biāo)號

定理3以層次級聯(lián)圖作為源圖H和伴隨圖L的集有序奇優(yōu)美標(biāo)號, 則孿生奇優(yōu)美頂點重疊圖K=H◇L對應(yīng)集有序奇優(yōu)美標(biāo)號.

證明： 根據(jù)層次級聯(lián)圖的定義, 將p個點的層次級聯(lián)圖H二分為(X,Y), 令X的點數(shù)為m個,Y的點數(shù)為n個, 且m+n=p, 則X={xi:i∈[1,m]},Y={yj:j∈[1,n]}. 定義一個標(biāo)號f1滿足：1)f1(xi)=2i-1,i∈[1,m]； 2)f1(yj)=2(p-j),j∈[1,n]. 對于任意邊xiyj∈E(H), 邊標(biāo)號為f1(xiyj)=f1(xi)-f1(yj), 有f1(V(H))=[1,2m-1]o∪[2m,2p-2]e, 從而得f1(E(H))=[1,2p-3]o.

孿生奇優(yōu)美重疊樹Ki+1=Ki◇Li中的伴隨圖為有p個頂點的層次級聯(lián)圖L. 伴隨圖L的頂點二分為(U,Z), 其中:U={ui:i∈[1,m]};Z={vj:j∈[1,n]}. 定義一個標(biāo)號f2滿足： 1)f2(ui)=2(i-1),i∈[1,m]； 2)f2(vj)=2(p-j)-1,j∈[1,n]. 對于任意邊uivj∈E(L), 邊標(biāo)號為f2(uivj)=f2(vi)-f2(uj), 有f2(V(L))=[2m-1,2p-3]o∪[0,2m-2]e, 從而得f2(E(L))=[1,2p-3]o.

由上述推導(dǎo)可得f1(xm)=f2(vn), 把源圖H中的頂點xm與伴隨圖L中的頂點vn合成一個頂點, 記為w, 所得到的圖是一個孿生奇優(yōu)美重疊圖K=H◇L, 標(biāo)號定義為f, 滿足：f(a)=f1(a),a∈V(H(X)){xm}；f(b)=f2(b),b∈V(L(Z)){vn}；f(w)=2m-1；f(y)=f1(y)+2p-2,y∈V(H(Y))；f(u)=f1(u)+2p-2,u∈V(L(U)). 從而有

f(V(A))=[1,2m-3]o,f(V(B))=[2m+1,2p-3]o,

f(V(Y))=[2m+2p-2,4p-4]e,f(V(U))=[2p-2,2p+2m-4]e.

易見

f(V(A))<{f(w)}

說明所有的頂點標(biāo)號互不相同, 即

因為合成的w頂點標(biāo)號不變, 所以對于任意邊xiyj∈E(K), 邊標(biāo)號為f(xiyj)=f(xi)-f(yj)和對于任意邊uivj∈E(K), 邊標(biāo)號為f(uivj)=f(vi)-f(uj), 說明所有的邊標(biāo)號互不相同, 即f(E(K))=[1,4p-5]o.

綜上證明了孿生頂點重疊圖K的頂點標(biāo)號滿足[1,2p-3]o∪[2p-2,4p-4]e, 且f(V(A))<{f(w)}

圖5為定理3的一個實例.

圖5 孿生奇優(yōu)美頂點重疊圖K1的集有序奇優(yōu)美標(biāo)號形成過程

綜上所述, 本文主要提出了用層次級聯(lián)圖作為基礎(chǔ)圖, 先通過加圈構(gòu)成一種單圈圖, 再把層次級聯(lián)圖作為源圖和伴隨圖, 將其中的一個頂點重疊構(gòu)成孿生頂點重疊圖, 且這種單圈圖和孿生頂點重疊圖具有集有序奇優(yōu)雅標(biāo)號、 奇優(yōu)美標(biāo)號、 集有序奇優(yōu)美標(biāo)號. 把單圈圖和巒生頂點重疊圖作為圖形密碼庫, 由于其具有多種不同的標(biāo)號, 可以為圖形密碼提供多樣性, 從而提高密碼的安全性.