对密码安全性的研究

姚明　姚兵

摘  要：利用新定义与标号理论，找到使得不同的图模块在一定条件下可相互转换的关键点，给出图模块之间基于这一点变换所需要的可算法化的算法，得到图模块由点连结变成由边连结的方法，为快速大规模构造图形结构和方便实际应用在理论上有了依据。

关键词：优美标号;全优美空间;边有序全优美标号;边有序全优美空间

中图分类号：TN918.4;O157.5       文献标识码：A 文章编号：2096-4706（2019）23-0136-04

Research on the Security of Password

YAO Ming1，YAO Bing2，3

（1. Lanzhou Petrochemical Polytechnic，Lanzhou  730060，China;

2.College of Mathematics and Information Science，Northwest Normal University，Lanzhou  730070，China;

3.School of Electronics and Information Engineering，Lanzhou Jiaotong University，Lanzhou  730070，China）

Abstract：By using the new definition and labelling theories，we find the key points that make different graph modules can be converted to each other under certain conditions，and give the algorithmic algorithm needed by the transformation between graph modules based on this point，and get the method that the graph module changes from point connection to edge connection，which provides a theoretical basis for fast and large-scale construction of graph structure and convenient practical application.

Keywords：graceful space;total graceful space;edge-ordered total graceful labellings;edge-ordered total graceful graphs space

0  引  言

基于一点的可算法化的结果能让图形结构方便实际应用，破译困难，尤其是图结构的灵活多变，能组合各种所需图结构，为快速大规模构造图形结构在理论上提供了保证;因需要基于一点变换而衍生的算法使密码的安全性得到加强。边有序全优美标号（edge-ordered total graceful labellings）、边有序全优美空间的定义使得研究的结果指向优美树猜想，这有助于探索优美树问题，而优美树的分解猜想成立则取决于猜想能够被证明[1，2]，诸多的研究成果表明解決它仍很困难[3]，算法可为研究优美树问题提供数理支撑。

1  预备知识

若无特别声明，文中论及的图均指有限、无向、简单连通图，未定义的术语和符号可参见文献[4]。为方便叙述，规定记号[m，n]={m，m+1，…，n}。

其中：整数n>m≥0。

F（G）为G的二部分图空间[5]，设树T∈F（G）有集合Ф（T）={g|g为T的正常标号}，一个正常标号g对任意的x，y∈V（T），有g（x）≠g（y）;

此外：∏（T）={g|g：V（T）∪E（T）→[m，n]}，且对任意的x，y∈V（T）∪E（T），有g（x）≠g（y），则g为图T的一个正常的全标号。

设有图T、H、E、K∈F（G），K图的边集合是由2个边不交的边子集E（H），E（T）的并所构成的边集合，即：E（K）=E（H）∪E（T）（如图1所示）;

E图是用一条边连接顶点u∈V（T）与顶点v∈V（H）后所得到的图;

且记：f（V（E））={f（x）|x∈V（E）}，f（E（E））={f（xy）|xy∈E（E）}。

（a）T-图

（b）H-图

定义1[6-8]：

设集合L（G）={f|f：V（G）→[0，p-1]，f∈Ф（G），G∈F}。

若：

（1）对任意的f∈L（G），使得uv∈E（G），满足{f（uv）|uv∈E（G）}=[1，q];

（2）图G的任何一个优美标号满足f∈L（G）;

则称L（G）为G的优美空间（graceful space），记为LGS（G）。

定义2[9，10]：

设图G∈F有集合L（G）={g|g∈∏（G）}。

若：

（1）对任意的g∈L（G），使得uv∈E（G），满足{f（uv）|uv∈E（G）}=[1，q];

（2）图G的任何一个全优美标号满足f∈L（G）;

则称L（G）为G的全优美空间（total graceful space），记为LTGS（G）。

定义3：

设图G∈F有f∈Λ（G）={f|f∈LTGS（G）};边集合E（G）=E（H）∪E（T），E（H）∩E（T）=∅。

若：

（1）对任意的（p，q）-图H及图T，使得uv∈E（H），xy∈E（T），满足{f（xy）|xy∈E（T）}=[1，q]，{f（uv）|uv∈E（H）}=[q+1，2q];

（2）图G的任何一个标号满足f∈Λ（G）;

则称f边有序全优美标号，图G为边有序全优美图，且记ΛEOTGL（G）={f|f为边有序全优美标号}。

定义4：

设图G有集合δ（G）={G|G∈F，G为边有序全优美图}。

若：

（1）对任意的图F，T∈δ（G），总有F∪T∈δ（G）;

（2）任何一个图G满足G∈δ（G）;

则称δ（G）为G的边有序全优美图空间（edge-ordered total graceful graphs space），记为δEOTGGS（G）。

2  主要结果及证明

定理1：

设图K∈F（G）有标号g∈∏（G），E（K）=E（H）∪E（T），H为（p，q）-图;若对于u∈V（T），有点p+ q=M∈V（K），使得g（u）-g（M）=q，则g∈ΛEOTGL（K）。

证明：

设（p，q）-图H有标号f∈LTGS（H），顶点集U={vi|i∈[1，s1]}，U ′={uj|j∈[1，t1]}，f（vi）>f（uj），f（vt1）=p+q;图T有顶点n=p-1，顶点集为X={xi|i∈[1，s2]}，Y={yj|j∈[1，t2]}。

（1）令标号h∈∏（T）满足：h（yj）=p+j，h（xi）=q-1+i;

不失一般性，可设h（yt1）=h（x1）+q-1;

由此推得：h（yt2-1）=h（x1）=q-2，h（yt2-2）=h（x1）+q-3，…，h（y1）=p+1;

注意到h（x1）=p，h（x2）=p-1;

因此h（yt2）=p+q-2，h（yt2-1）=p+q-3，h（yt2-2）= p+q-4，…，h（y1）=p+1;

此處h（yj）>h（xi）;

因此有h（E（T））={h（yj）-h（x1）|yj，x1∈V（T），j∈ [1，t2-1]}∪{h（yt2）-h（x2）}={1，2，…，q-1};

又，图T有顶点n=p-1;

综上所述，h（E（T））=[1，q-1]，h∈LTGS（T）。

（2）由于图H有标号f∈LTGS（H），f（vs1）=p+q;

不失一般性，设f（vs1-1）=p+q-1，…，f（v1）=p+;

f（u1）=p，f（u2）=p+1，…，f（ut1）=q+;

因此有f（E（H））=f（E（H1））∪f（E（H2））∪{f（v1）-f（u1）};

其中f（E（H1））={f（vi）-f（u1）|u1，vi∈V（H），i∈[2，s1]}，f（E（H2））={f（uj）-f（v1）|uj，v1∈V（H），j∈[2，t1]};

即：f（E（H））={f（uv）|uv∈E（H）}=[1，q]

（3）设图K∈F（G）有标号g∈∏（G）：

1）对于图H，令g（vi）=f（vi）+p+q，g（uj）=f（uj）+p;

由（2）有g（vs1）=f（vs1）+p+q=2（p+q），g（vs1 -1）=

f（vs1-1）+p+q=f（vs1）-1+p+q=2（p+q）-1，…，g（v1）=f（v1）+p+q=p++p+q=p+q;g（u1）=f（u1）+p=2p， g（u2）=f（u2）+p=f（u1）+1+p=2p+1，…，g（ut1）=f（ut1）+p=f（u1）+s1-1+p=2p-1+s1;

因此g（v2）-g（u1）=p+q+1-2p=+q+1，g（v3） -g（u1）=p+q+2-2p=+q+2，…，g（vs1）-g（u1）=2（p+q）-2p=2q;g（v1）-g（u2）=p+q-2p-1=+q-1，…，g（v1）-g（ut1）=p+q-q-p=p;

又有g（v1）-g（u1）=p+q-2p=+q;g（E（H））={g（vi）-g（u1）|vi，u1∈V（H）}∪{g（v1）-g（uj）|v1，uj∈V（H）}∪{g（v1）-g（u1）};

其中{g（vi）-g（ui）|vi，u1∈V（H）}={1+q+，…，2q}，{g（v1）-g（uj）|v1，uj∈V（H）}={p，…，+q-1}，g（v1）-g（u1）=p+q-2p=p+q;

即：g（E（H））=[p，2p]。

2）对于图T，令g（yj）=h（yj）+p+1，g（xi）=h（xi）+p+1;

不失一般性，可设g（yt2）=h（yt2）+p+1=g（x1）+ q-2;

由此推得：g（yt2-1）=h（yt2-1）+p+1=g（x1）+q-3，…，g（y1）=g（x1）+1;

令g（x1）=p+1，g（x2）=p;

因此有{g（yj）-g（x1）|x1，yj∈V（T）}={1，2，…，q-3};

注意到{g（yt2-1）-g（x2）}={q-2}，{g（yt2）-g（x2）}={q-1};

从而g（E（T））={g（yj）-g（x1）|x1，yj∈V（T）}∪{g（yt2-1）-g（x2）}∪{g（yt2）-g（x2）};

即：g（E（T））=[1，q-1];

（4）设M∈V（K），令g（M）=p+3;

由上述（3），总有点u∈V（T），g（u）=p+2;

使得：g（u）-g（M）=q;

因此有g（E（T））∪{q}={1，2，…，q-1}∪{q}=[1，q];

从而g（E（T））∪{q}∪g（E（H））={1，2，…，q-1}∪{q}∪{p，2q}=[1，2q];

综上，有g（E（T））∪g（E（H））={1，2，…，q-1，q}∪{p，2q}=[1，2q];

即：g∈LTGS（G）;

又（E（K））={g（uv）|uv∈E（G）}=[1，2q];

由定义3，有g∈ΛEOTGL（G）。

定理2：

设图K∈δEOTGGS（G），g∈ΛEOTGL（K），图E有标号f∈∏（G）;若存点M∈V（T），U∈V（H），使得f（M）- f（U）=q，则f∈LTGS（G）。

证明：

由定理1，有：

（1）对于图H，令f（vi）=g（vi）-1，f（uj）=g（uj）- 1;

有f（vs1）=g（vs1）-1=2（p+q）-1，f（vs1-1）=g（vs1-1）-1=g（vs1）-1-1=2（p+q）-2，…，f（v1）=g（v1）-1= p++p+q-1=p+q-1;f（u1）=g（u1）-1=2p-1，f（u2）=g（u2）-1=g（u1）+1-1=2p，…，f（ut1）=g（ut1）-1=g（u1）+t1-1-1=2q-2+t1;

因此有f（v2）-f（u1）=p+q-2p+1=+q+1，f（v3）- f（u1）=p+q+1-2p+1=+q+2，…，f（vs1）-f（u1）= 2（p+q）-1-2p+1=2q;f（v1）-f（u2）=p+q-1-2p= +q-1，…，f（v1）-f（ut1）=p+q-1-q-p+1=p;f（E（H））={f（vi）-f（u1）|vi，u1∈V（H）}∪{f（v1）- f（uj）|v1，uj∈V（H）}∪{f（v1）-f（u1）};

其中{f（vi）-f（u1）|vi，u1∈V（H）}={1+q+，…2q}，{f（v1）-f（uj）|v1，uj∈V（H）}={p，…，+q-1};

又f（v1）-f（u1）=p+q-1-2p+1=+q;

即：f（E（H））=[p，2q]。

（2）对于图T，令f（yj）=g（yj）-1，f（xi）=g（xi）-1;

不失一般性，可设：f（yt2）=g（yt2）-1=g（x1）+q-3;

由此推得：f（yt2-1）=g（yt2-1）=g（x1）+q-4，…，f（y1）=g（x1）;

令f（x1）=p，f（x2）=p-1;

因此有{f（yj）-f（x1）|x1，yj∈V（T），j∈[1，t2-1]}={1，2，…，q-3};

注意到{f（yt2-1）-f（x2）}={q-2}，{f（yt2）-f（x2）}={q-1};

从而f（E（T））={f（yj）-f（x1）|x1，yj∈V（T），j∈[1，t2-1]}∪{f（yt2-1）-f（x2）}∪{f（yt2）-f（x2）};

即：f（E（T））=[1，q-1];

由上所述，存在点M∈V（T），且f（M）=p+2q;U∈V（H），f（U）=p+q，

使得f（M）-f（U）=q;

因此用一条边将两点U，M连接得到图E，且f（E（E））=f（E（H））∪{f（U）-f（u1）}∪f（E（T））;

其中{f（U）-f（u1）}=g（x1）+1-2p+1}=p+2-2p+ 1}={q}，f（E（H））=[p，2q]，f（E（T））=[1，q-1];

即：f（E（E））=f（E（H））∪{f（U）-f（u1）}∪f（E（T））=[1，q-1]∪{q}∪[p，2q];

综上所述，有f∈LTGS（G）。

3  结  论

由基本的图模块利用标号理论基于創新的可算法化的算法从中发现类似于网络中节点的点是连结满足一定条件下图模块的关键点，由可算法化过程看出此点能够使得图结构模块化，基于一点变换而衍生的算法因密码破译困难使得安全性得到加强。由点连结演变成由边连结使得图模块结构灵活多变，能组合各种所需图结构，为快速大规模构造图形结构和方便实际应用在理论上提供了保证。边有序全优美标号与边有序全优美空间的新定义、模块化的组合与分解使得研究痕迹指向优美树猜想，这有助于探索优美树问题，希望下一步的研究在此方面有所收获。

参考文献：

[1] ROSA A. On certain valuations of the vertices of a graph [J]. Theory of Graphs，1967：349-355.

[2] GALLIAN J A. A Dynamic survey of graph labeling [J]. The Electronic Journal of Combinatorics，2012，18：1-7.

[3] EDWARDS M，HOWARD L. A survey of graceful trees [J]. Atlantic Electronic Journal of Mathematics，2006， 1（1）：5-30.

[4] BONDY J A，MURTY U.S.R. Graph theory with application [M]. New York：MaCmillan，1976.

[5] 姚明，赵振学，姚兵.关于树（图）的单点空间 [J].甘肃科学学报，2016，28（5）：15-18+78.

[6] 姚明，姚兵，谢建民.关于图k-魔幻标号的若干结果 [J].甘肃科学学报，2010，22（1）：1-6.

[7] WILLIAM A，RAJAN B，RAJASINGH I，et al. Nor Super Edge Magic Total Labelling [C]//The Proceeding of the 4th International Workshop in Graph Labeling，Harbin Engineering University and University of Ballarat，Australia，2008：5-8.

[8] YAO B，ZHANG Z，YAO M，et al. A New Type of Magical Coloring [J].Advances in Mathematics，2008（5）：571-583.

[9] SUBBIAB S P. Super total graceful graphs and a tree conjeucture [J].Electronic Notes in Discrete Mathmatics，2015，48：301-304.

[10] GRAF A. A new graceful labeling for pendant graphs [J].Aequationes mathematicae，2014，87（1-2）：135-145.

作者简介：姚明（1962-），男，汉族，江苏扬州人，教授，本科，研究方向：图着色和标号及计算优化。