树与单圈图优雅标号算法的新型图形密码研究

doi:10.16180/j.cnki.issn1007-7820.2019.03.016

摘要/Abstract

摘要：

为解决传统身份验证方法中密码易记忆性与安全性问题,文中提出了一种针对树图与单圈图的优雅标号算法,并将其应用于构建基于优雅标号的新型图形密码。该算法把图结构和数论相结合,递归遍历指定优雅解空间,直到对应邻接矩阵满足优雅目标函数或对应优雅空间遍历完成时结束。文中给出了算法设计步骤,并进行了算法测试分析。结果表明,16个点范围内所有树图与单圈图几乎都是优雅的,只有个别图是非优雅的。据此得到2个定理和一个猜想,为构建基于优雅标号的新型图形密码提供了基础数据。

关键词: 图形密码, 树与单圈图, 优雅图, 优雅标号, 非优雅图, 优雅标号算法

Abstract:

In order to solve the problem of easy memory and security of passwords in traditional authentication methods, an elegant labeling algorithm for tree and unicyclic graphs was proposed, which was further used to construct a new type of graphical password based on elegant labeling. The algorithm combined graph structure and number theory, iteratively traversed the specified elegant solution space until the corresponding adjacency matrix satisfied the elegant objective function or finished when the corresponding elegant space traversal was completed. This paper presented the algorithm design steps and carried out the algorithm test and analysis. The results showed that almost all the tree and unicyclic graphs within the 16-point range were elegant. Only some of the graphs were non-elegant. According to the results, two theorems and one conjecture were obtained, which provided a basic data set based on elegant labeling for the new graphical password.

Key words: graphical password, tree and unicyclic graphs, elegant graph, elegant labeling, non-elegant graph, algorithm of elegant labeling

中图分类号:

TP301

黄泽. 树与单圈图优雅标号算法的新型图形密码研究[J]. 电子科技, 2019, 32(3): 77-81.

HUANG Ze. New Type of Graphical Password Study Based on the Elegant Label Algorithm of Tree and Unicyclic Graph[J]. Electronic Science and Technology, 2019, 32(3): 77-81.

图/表 9

表1

表2

表3

图1

图2

表4

表5

表6

表7

参考文献 16

[1]	胡卫, 吴晓平, 张昌宏 , 等. 图形密码身份认证方案设计及其安全性分析[J]. 计算机工程与设计, 2009,30(14):3284-3287.
	Hu Wei, Wu Xiaoping, Zhang Changhong , et al. Graphical password authentication scheme design and security analysis[J]. Computer Engineering and Design, 2009,30(14):3284-3287.
[2]	Standing L, Conezio J, Haber R N . Perception and memory for pictures:Single-trial learning of 2500 visual stimuli[J]. Psychonomic Science, 1970,19(2):73-74. doi: 10.3758/BF03337426
[3]	Chiasson S, Van Oorschot P C, Biddle R . Graphical password authentication using cued click points [C]. Berlin:European Symposium on Research in Computer Security, Springer, 2007.
[4]	Belk M, Germanakos P, Fidas C, et al. Studying the effect of human cognition on user authentication tasks [C]. Berlin:International Conference on User Modeling, Adaptation, and Personalization. Springer, 2013.
[5]	Tao H, Adams C . Pass-Go:a proposal to improve the usability of graphical passwords[J]. International Journal of Network Security, 2008,7(2):273-292.
[6]	Brostoff S, Sasse M A . Are passfaces more usable than passwords? a field trial investigation[M]. London:Springer, 2000.
[7]	Davis D, Monrose F, Reiter M K. On user choice in graphical password schemes [C].San Diego:Conference on Usenix Security Symposium,USENIX Association, 2004.
[8]	Wang H, Xu J, Yao B. Exploring new cryptographical construction of complex network data [C].Changsha:IEEE International Conference on Data Science in Cyberspace (DSC),IEEE, 2016.
[9]	Wang H Y, Jin X U, Yao B . New labellings based on the idea of graphical construction plus number theory for designing cryptographs[J].Research Gate, 2017(smce):114-120.
[10]	Mc Kay B D .Nauty software program, version 2.2[DB/OL].( 2013- 02- 20)[2018-03-01] .
[11]	Bondy J A , Murty U S R .Graph theory with applications[M]. London:Macmillan, 1976.
[12]	Balakrishnan R, Selvam A, Yegnanarayanan V . Some results on elegant graphs[J]. Indian Journal of Pure & Applied Mathematics, 1997,28(7):98-107.
[13]	Skupień, Zdzis A W, Andrzej A K . Rainbow regular order of graphs[J]. Australasian Journal of Combinatorics, 2008,42(42):115-127.
[14]	Zhou X, Yao B, Chen X . Every lobster is odd-elegant[J]. Information Processing Letters, 2013,113(1-2):30-33. doi: 10.1016/j.ipl.2012.09.008
[15]	马德山, 刘林忠 . 1—树图的邻强边染色[J]. 数学研究与评论, 2000,20(2):299-305.
	Ma Deshan, Liu Linzhong . Adjacent strong edge staining of 1-tree graphs[J]. Journal of Mathematical Research and Exposition, 2000,20(2):299-305.
[16]	辛利斌, 张振国, 王顺平 , 等. 自动指纹识别系统算法的优化改良[J]. 电子科技, 2016,29(12):41-43.
	Xin Libin, Zhang Zhenguo, Wang Shunping , et al. Optimization of automatic fingerprint identification system algorithms[J]. Electronic Science and Technology, 2016,29(12):41-43.

(p,p-1)	优雅图数	非优雅图	图总数	总耗时数	平均耗时/ms
(3,2)	1	0	1	0:0:0	0.000 1
(4,3)	1	1	2	0:0:0	5.5
(5,4)	3	0	3	0:0:0	0.013 2
(6,5)	5	1	6	0:0:0	4.166 666 666 666 67
(7,6)	11	0	11	0:0:0	0.363 636 363 636 37
(8,7)	20	3	23	0:0:0	5.347 826 086 956 52
(9,8)	47	0	47	0:0:0	2.765 957 444 535 41
(10,9)	104	2	106	0:0:1	10.896 226 415 094 3
(11,10)	235	0	235	0:0:2	11.697 872 340 425 5
(12,11)	548	3	551	0:05:45	626.522 686 025 408
(13,12)	1 301	0	1 301	0:11:58	552.537 279 016 141
(14,13)	3 157	2	3 159	1:36:38	1 835.549 224 438 11
(15,14)	7 741	0	7 741	106:00:31	4 930.003 229 556 9
(16,15)	19 317	3	19 320	3个非优雅图总耗时180 h

(p,p)	优雅图数	非优雅图	图总数	总耗时数	平均耗时/ms
(3,3)	1	0	1	0:0:0	0.09
(4,4)	2	0	2	0:0:0	0.314 5
(5,5)	4	1	4	0:0:0	4.2
(6,6)	13	0	13	0:0:0	0.307 692 307 692 308
(7,7)	33	0	33	0:0:0	0.212 121 212 121 212
(8,8)	89	0	89	0:0:0	0.752 808 988 764 045
(9,9)	239	1	240	0:0:0	1.733 333 333 333 33
(10,10)	657	0	657	0:0:0	1.471 841 704 718 42
(11,11)	1 806	0	1 806	0:0:2	1.516 057 585 825 03
(12,12)	5 026	0	5 026	0:0:48	9.661 360 923 199 36
(13,13)	13 998	1	13 999	4:34:8	114.286 449 032 074
(14,14)	39 260	0	39 260	1:00:47	92.911 156 393 275 6
(15,15)	110 381	0	110 381	4:31:45	147.719 364 455 84
(16,16)	311 465	0	311 465	106:09:45	1 227.059 066 026 68