图形密码中一类特殊图的几种标号

顾彦波, 李敬文, 王露露

(兰州交通大学 电子与信息工程学院, 兰州 730070)

1 引言与预备知识

目前人们经常使用的密码一般是文本密码[1], 用户设置密码时要符合强口令的要求, 还要经常更换, 增加了记忆负担, 且实际生活中用户记下密码或者在不同场景中使用相同的密码, 都会给系统安全带来隐患. 图形密码是利用人们对图形记忆优于对文本记忆的特点而设计的一种新型密码[2-3], 用户不用记忆冗长的字符串, 而是通过识别或记住图形进行身份验证. 如果可能的图形数量足够大, 图形密码的密钥空间可以远超过文本密码, 即可以更好地抵抗暴力破解和字典攻击等. 利用拓扑图加数论等技术产生的图形密码, 具有动态性强、 智商高、 组合方式无穷多、 存储量多、 运算快等优点, 可达到使用者易记忆、 进攻者难破译的基本要求[4-5]. 目前, 关于各类图各种标号的研究已取得了很大进展[6-15]. 本文研究由层次级联图叠加构成孪生顶点重叠图以及圈加层次级联图构成的单圈图, 以提供新型的图形密码.

本文用[m,n]表示整数集合{m,m+1,…,n}； 用[s,t]o表示奇数集合{s,s+2,…,t}, 其中s,t是奇数； 用[a,b]e表示偶数集合{a,a+2,…,b}, 其中a,b是偶数. 集合X的元素个数记为|X|. 具有p个顶点、q条边的图称为(p,q)-图.

定义1[4-6]若(p,q)-图G有一个映射f:V(G)→[0,2q-1], 使得任何两个不同顶点u,v∈V(G)的标号满足f(u)≠f(v), 且边标号集合为

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

则称f为图G的一个奇优雅标号, 图G为奇优雅图. 如果G是二部图, (X,Y)是其顶点集合的二分类, 且有max{f(x):x∈X}

定义2[4-6]若(p,q)-图G有一个映射f:V(G)→[0,2q-1], 使得不同顶点u,v∈V(G)的标号满足f(u)≠f(v), 且边标号集合为

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

则称f为图G的一个奇优美标号. 如果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, 称其为顶点重叠图. 进一步, 如果q=2|E(K)|=2|E(L)|, 则称G为一致顶点重叠(p,q)-图.

设一致顶点重叠(p,q)-图G=K◇L有一个映射f:V(G)→[0,q], 使得:

(i) 每对顶点x,y∈V(G)都满足f(x)≠f(y);

(ii)f是子图K的一个奇优美标号；

(iii) 边标号集合f(E(G))={f(xy)=|f(x)-f(y)|:xy∈E(G)}=[1,q-1]o.

则称G是一个孪生奇优美顶点重叠(p,q)-图, 称f是图G的一个孪生奇优美标号, 称K为源图, 称L为源图K的一个伴随图.

下面给出本文的研究对象. 设当n=1时, 层次级联图的总个数为p1=5； 一层的层次级联图H1顶点的序列号分为两部分, 分别为X1={x1,x2,x3}和Y1={y1,y2}； 顶点之间的边为E(H1)={x1y1,x2y2,y2x3,y2x1}. 设当n=2时, 层次级联图的总个数为p2=11； 二层的层次级联图H2顶点的序列号分为两部分, 分别为X2=X1∪{x4,x5,x6}和Y2=Y1∪{y3,y4,y5}； 顶点之间的边为

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

依次当n=k时, 层次级联图的总个数为pk=(k+2)(k+1)-1；k层的层次级联图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)

层次级联图顶点的序号如图1所示.

图1 层次级联图的顶点序号

图2 单圈图Cn⊕Hk的顶点序号

把圈Cn上一个顶点与层次级联图Hk上一个顶点用一条边粘接起来而形成的图称为单圈图Cn⊕Hk, 如图2所示. 记圈Cn的顶点序号为ui(i=1,2,…)和vi(i=1,2,…); 层次级联图Hk的顶点序号为xi(i=1,2,…,(k+2)(k+1)/2)和yi(i=1,2,…,(k+2)(k+1)/2-1).

2 主要结果

定理1由圈C4m上一个顶点与层次级联图Hk的x(k+2)(k+1)/2顶点用一条边连接构成的单圈图C4m⊕Hk是集有序奇优雅图, 其中：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].

其次证所有边标号互不相同.

1) 圈C4m的顶点标号为

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.

当i=1,2,…,m时, 边标号

当m取值很小时会出现负值, 其中如果出现负数则对应加2q表示其对应的边标号. 当i=m+1,m+2,…,2m时, 边标号

当i=1,2,…,m时, 边标号

当m取值很小时会出现负值, 其中如果出现负数则对应加2q表示其对应的边标号. 当i=m+1,m+2,…,2m-1时, 边标号

边标号

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

即圈上所有的边标号互不相同,f(E(uv))=[4m-2t+1,8m+2t+3]o, 当m取值很小时会出现负值, 其中如果出现负数则对应加2q表示其对应的边标号.

2) 粘连边的边标号为

当m取值很小时会出现负值, 其中如果出现负数则对应加2q表示其对应的边标号.

3) 用数学归纳法证明： 当n=1时, 层次级联图的总个数为p1=5, 则t=3； 第一层的层次级联图H1顶点序列号分为两部分, 分别为X1={x1,x2,x3}和Y1={y1,y2}； 且顶点之间的边为E(H1)={x1y1,x2y2,y2x3,y2x1}； 则H1的顶点标号和边标号分别为

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}

成立； 假设当n=k时, 层次级联图的总个数为pk=(k+2)(k+1)-1=2t-1； 第k层的层次级联图Hk顶点的序列号分为两部分, 分别为式(1), 且顶点之间的边为式(2); 则Hk的顶点标号和边标号分别为

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],

当m取值很小时会出现负值, 其中如果出现负数则对应加2q表示其对应的边标号, 结论成立； 当n=k+1时, 层次级联图的总个数为pk+1=(k+3)(k+2)-1；k+1层的层次级联图Hk+1顶点的序列号分为两部分, 分别为

(3)

且顶点之间的边为

则Hk+1的顶点标号和边标号分别为

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],

结论成立, 证明了所有边标号互不相同, 即f(E(H))=[4m-2t+5,4m+2t-1]o, 当m取值很小时会出现负值, 其中如果出现负数则对应加2q表示其对应的边标号.

综上证明了单圈图C4m⊕Hk的顶点标号满足[0,8m+4t-3], 且fmax(X)

图3为定理1的一个实例.

图3 单圈图C4⊕H2与C8⊕H2的集有序奇优雅标号

定理2由圈C4m+2上一个顶点与层次级联图Hk的x(k+2)(k+1)/2顶点用一条边粘连构成的单圈图C4m+2⊕Hk是奇优美图, 其中: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), 即所有的顶点标号各不相同. 首先证明单圈图C4m+2⊕Hk是奇优美标号. 由上述标号知, 顶点的最大标号为f(y1)=8m+4t+1, 顶点的最小标号为f(x1)=0. 又有

所以

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

其次证所有边标号互不相同.

1) 圈C4m+2的顶点标号为

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.

则边标号

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};

边标号

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};

边标号

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};

边标号

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

边标号

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};

边标号

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

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

即圈上所有的边标号互不相同,f(E(uv))=[1,8m+3]o.

2) 粘连边的边标号为

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

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

3) 用数学归纳法证明： 当n=1时, 层次级联图的总个数为p1=5, 则t=3, 第一层的层次级联图H1顶点的序列号分为两部分, 分别为X1={x1,x2,x3}和Y1={y1,y2}； 且顶点之间的边为E(H1)={x1y1,x2y2,y2x3,y2x1}； 则H1的顶点标号和边标号分别为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}

成立； 假设当n=k时, 层次级联图的总个数为pk=(k+2)(k+1)-1=2t-1； 第k层的层次级联图Hk顶点的序列号分为两部分, 分别为式(1), 且顶点之间的边为式(2); 则Hk的顶点标号和边标号分别为

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,

结论成立； 当n=k+1时, 层次级联图的总个数为pk+1=(k+3)(k+2)-1； 第k+1层的层次级联图Hk+1顶点的序列号分为两部分, 分别为式(3)； 且顶点之间的边为式(4); 则Hk+1的顶点标号和边标号分别为

结论成立. 从而证明了层次级联图Hk的所有边标号互不相同, 即f(E(H))=[8m+7,8m+4t+1]o.

综上证明了单圈图C4m+2⊕Hk的顶点标号满足[0,8m+4t+1], 边标号满足[1,8m+4t+1]o, 故单圈图C4m+2⊕Hk是奇优美图. 证毕.

图4为定理2的一个实例.

图4 单圈图C6⊕H2和C10⊕H2的奇优美标号

定理3以层次级联图作为源图H和伴随图L的集有序奇优美标号, 则孪生奇优美顶点重叠图K=H◇L对应集有序奇优美标号.

证明： 根据层次级联图的定义, 将p个点的层次级联图H二分为(X,Y), 令X的点数为m个,Y的点数为n个, 且m+n=p, 则X={xi:i∈[1,m]},Y={yj:j∈[1,n]}. 定义一个标号f1满足：1)f1(xi)=2i-1,i∈[1,m]； 2)f1(yj)=2(p-j),j∈[1,n]. 对于任意边xiyj∈E(H), 边标号为f1(xiyj)=f1(xi)-f1(yj), 有f1(V(H))=[1,2m-1]o∪[2m,2p-2]e, 从而得f1(E(H))=[1,2p-3]o.

孪生奇优美重叠树Ki+1=Ki◇Li中的伴随图为有p个顶点的层次级联图L. 伴随图L的顶点二分为(U,Z), 其中:U={ui:i∈[1,m]};Z={vj:j∈[1,n]}. 定义一个标号f2满足： 1)f2(ui)=2(i-1),i∈[1,m]； 2)f2(vj)=2(p-j)-1,j∈[1,n]. 对于任意边uivj∈E(L), 边标号为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.

由上述推导可得f1(xm)=f2(vn), 把源图H中的顶点xm与伴随图L中的顶点vn合成一个顶点, 记为w, 所得到的图是一个孪生奇优美重叠图K=H◇L, 标号定义为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)}

说明所有的顶点标号互不相同, 即

因为合成的w顶点标号不变, 所以对于任意边xiyj∈E(K), 边标号为f(xiyj)=f(xi)-f(yj)和对于任意边uivj∈E(K), 边标号为f(uivj)=f(vi)-f(uj), 说明所有的边标号互不相同, 即f(E(K))=[1,4p-5]o.

综上证明了孪生顶点重叠图K的顶点标号满足[1,2p-3]o∪[2p-2,4p-4]e, 且f(V(A))<{f(w)}

图5为定理3的一个实例.

图5 孪生奇优美顶点重叠图K1的集有序奇优美标号形成过程

综上所述, 本文主要提出了用层次级联图作为基础图, 先通过加圈构成一种单圈图, 再把层次级联图作为源图和伴随图, 将其中的一个顶点重叠构成孪生顶点重叠图, 且这种单圈图和孪生顶点重叠图具有集有序奇优雅标号、 奇优美标号、 集有序奇优美标号. 把单圈图和峦生顶点重叠图作为图形密码库, 由于其具有多种不同的标号, 可以为图形密码提供多样性, 从而提高密码的安全性.