對密碼安全性的研究

姚明　姚兵

摘? 要：利用新定義與標(biāo)號理論，找到使得不同的圖模塊在一定條件下可相互轉(zhuǎn)換的關(guān)鍵點(diǎn)，給出圖模塊之間基于這一點(diǎn)變換所需要的可算法化的算法，得到圖模塊由點(diǎn)連結(jié)變成由邊連結(jié)的方法，為快速大規(guī)模構(gòu)造圖形結(jié)構(gòu)和方便實(shí)際應(yīng)用在理論上有了依據(jù)。

關(guān)鍵詞：優(yōu)美標(biāo)號;全優(yōu)美空間;邊有序全優(yōu)美標(biāo)號;邊有序全優(yōu)美空間

中圖分類號：TN918.4;O157.5? ? ? ?文獻(xiàn)標(biāo)識碼：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? 引? 言

基于一點(diǎn)的可算法化的結(jié)果能讓圖形結(jié)構(gòu)方便實(shí)際應(yīng)用，破譯困難，尤其是圖結(jié)構(gòu)的靈活多變，能組合各種所需圖結(jié)構(gòu)，為快速大規(guī)模構(gòu)造圖形結(jié)構(gòu)在理論上提供了保證;因需要基于一點(diǎn)變換而衍生的算法使密碼的安全性得到加強(qiáng)。邊有序全優(yōu)美標(biāo)號（edge-ordered total graceful labellings）、邊有序全優(yōu)美空間的定義使得研究的結(jié)果指向優(yōu)美樹猜想，這有助于探索優(yōu)美樹問題，而優(yōu)美樹的分解猜想成立則取決于猜想能夠被證明[1，2]，諸多的研究成果表明解決它仍很困難[3]，算法可為研究優(yōu)美樹問題提供數(shù)理支撐。

1? 預(yù)備知識

若無特別聲明，文中論及的圖均指有限、無向、簡單連通圖，未定義的術(shù)語和符號可參見文獻(xiàn)[4]。為方便敘述，規(guī)定記號[m，n]={m，m+1，…，n}。

其中：整數(shù)n>m≥0。

F（G）為G的二部分圖空間[5]，設(shè)樹T∈F（G）有集合Ф（T）={g|g為T的正常標(biāo)號}，一個(gè)正常標(biāo)號g對任意的x，y∈V（T），有g(shù)（x）≠g（y）;

此外：∏（T）={g|g：V（T）∪E（T）→[m，n]}，且對任意的x，y∈V（T）∪E（T），有g(shù)（x）≠g（y），則g為圖T的一個(gè)正常的全標(biāo)號。

設(shè)有圖T、H、E、K∈F（G），K圖的邊集合是由2個(gè)邊不交的邊子集E（H），E（T）的并所構(gòu)成的邊集合，即：E（K）=E（H）∪E（T）（如圖1所示）;

E圖是用一條邊連接頂點(diǎn)u∈V（T）與頂點(diǎn)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]：

設(shè)集合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的任何一個(gè)優(yōu)美標(biāo)號滿足f∈L（G）;

則稱L（G）為G的優(yōu)美空間（graceful space），記為LGS（G）。

定義2[9，10]：

設(shè)圖G∈F有集合L（G）={g|g∈∏（G）}。

若：

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

（2）圖G的任何一個(gè)全優(yōu)美標(biāo)號滿足f∈L（G）;

則稱L（G）為G的全優(yōu)美空間（total graceful space），記為LTGS（G）。

定義3：

設(shè)圖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的任何一個(gè)標(biāo)號滿足f∈Λ（G）;

則稱f邊有序全優(yōu)美標(biāo)號，圖G為邊有序全優(yōu)美圖，且記ΛEOTGL（G）={f|f為邊有序全優(yōu)美標(biāo)號}。

定義4：

設(shè)圖G有集合δ（G）={G|G∈F，G為邊有序全優(yōu)美圖}。

若：

（1）對任意的圖F，T∈δ（G），總有F∪T∈δ（G）;

（2）任何一個(gè)圖G滿足G∈δ（G）;

則稱δ（G）為G的邊有序全優(yōu)美圖空間（edge-ordered total graceful graphs space），記為δEOTGGS（G）。

2? 主要結(jié)果及證明

定理1：

設(shè)圖K∈F（G）有標(biāo)號g∈∏（G），E（K）=E（H）∪E（T），H為（p，q）-圖;若對于u∈V（T），有點(diǎn)p+ q=M∈V（K），使得g（u）-g（M）=q，則g∈ΛEOTGL（K）。

證明：

設(shè)（p，q）-圖H有標(biāo)號f∈LTGS（H），頂點(diǎn)集U={vi|i∈[1，s1]}，U ′={uj|j∈[1，t1]}，f（vi）>f（uj），f（vt1）=p+q;圖T有頂點(diǎn)n=p-1，頂點(diǎn)集為X={xi|i∈[1，s2]}，Y={yj|j∈[1，t2]}。

（1）令標(biāo)號h∈∏（T）滿足：h（yj）=p+j，h（xi）=q-1+i;

不失一般性，可設(shè)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有頂點(diǎn)n=p-1;

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

（2）由于圖H有標(biāo)號f∈LTGS（H），f（vs1）=p+q;

不失一般性，設(shè)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）設(shè)圖K∈F（G）有標(biāo)號g∈∏（G）：

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

由（2）有g(shù)（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(shù)（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;

不失一般性，可設(shè)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）設(shè)M∈V（K），令g（M）=p+3;

由上述（3），總有點(diǎn)u∈V（T），g（u）=p+2;

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

因此有g(shù)（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(shù)（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(shù)∈ΛEOTGL（G）。

定理2：

設(shè)圖K∈δEOTGGS（G），g∈ΛEOTGL（K），圖E有標(biāo)號f∈∏（G）;若存點(diǎn)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;

不失一般性，可設(shè)：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];

由上所述，存在點(diǎn)M∈V（T），且f（M）=p+2q;U∈V（H），f（U）=p+q，

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

因此用一條邊將兩點(diǎn)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? 結(jié)? 論

由基本的圖模塊利用標(biāo)號理論基于創(chuàng)新的可算法化的算法從中發(fā)現(xiàn)類似于網(wǎng)絡(luò)中節(jié)點(diǎn)的點(diǎn)是連結(jié)滿足一定條件下圖模塊的關(guān)鍵點(diǎn)，由可算法化過程看出此點(diǎn)能夠使得圖結(jié)構(gòu)模塊化，基于一點(diǎn)變換而衍生的算法因密碼破譯困難使得安全性得到加強(qiáng)。由點(diǎn)連結(jié)演變成由邊連結(jié)使得圖模塊結(jié)構(gòu)靈活多變，能組合各種所需圖結(jié)構(gòu)，為快速大規(guī)模構(gòu)造圖形結(jié)構(gòu)和方便實(shí)際應(yīng)用在理論上提供了保證。邊有序全優(yōu)美標(biāo)號與邊有序全優(yōu)美空間的新定義、模塊化的組合與分解使得研究痕跡指向優(yōu)美樹猜想，這有助于探索優(yōu)美樹問題，希望下一步的研究在此方面有所收獲。

參考文獻(xiàn)：

[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] 姚明，趙振學(xué)，姚兵.關(guān)于樹（圖）的單點(diǎn)空間 [J].甘肅科學(xué)學(xué)報(bào)，2016，28（5）：15-18+78.

[6] 姚明，姚兵，謝建民.關(guān)于圖k-魔幻標(biāo)號的若干結(jié)果 [J].甘肅科學(xué)學(xué)報(bào)，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-），男，漢族，江蘇揚(yáng)州人，教授，本科，研究方向：圖著色和標(biāo)號及計(jì)算優(yōu)化。