JIANG Kexin,ZHAO Yahui*,CUI Rongyi.Password matching method based on automata theory[J].Journal of Yanbian University,2021,47(02):141-145.
基于自动机理论的密码匹配方法
- Title:
- Password matching method based on automata theory
- 文章编号:
- 1004-4353(2021)02-0141-05
- Keywords:
- automata theory; password match; password encryption; homomorphic mapping; homomorphic preimage
- 分类号:
- TP391.41
- 文献标志码:
- A
- 摘要:
- 针对用户安全登录问题,提出了一种基于自动机的密码匹配模型.首先,对于用户任意输入的密码进行同态映射加密; 其次,构造出可接受加密密码的自动机——状态数目可变自动机(VNS - DFA),该自动机不仅能够匹配加密密码,同时还可以输出加密密码的同态原像以及匹配成功的次数; 最后,在状态数目可变的自动机上对用户输入的密码进行实验验证表明,用户建立的密码经过同态映射后可全部被该自动机接受,且该自动机的时间复杂度优于传统的DFA以及改进的DFA.
- Abstract:
- For users to log in safely, a password matching model based on automata was proposed. Firstly, we perform homomorphic mapping encryption for any entered password; Then, we construct an automaton that accepts encrypted passwords, namely variable number of states automata(VNS - DFA), the automat a can not only match the encrypted password, but also can output the homomorphic image of the encrypted password and the number of successful matches. Finally, the experiments on the automata with variable number of states show that the user's password can be accepted by the automata after homomorphic mapping, and the time complexity of the automata is better than that of the traditional DFA and the DFA which was improved.
参考文献/References:
[1] 敬茂华.一种新的自动机构造理论(PFA)[D].沈阳:东北大学,2016.
[2] 黄鸿华.基于Visual C++的装箱问题的BF算法[J].电脑知识与技术,2018,14(36):258-259.
[3] 蔡恒,张帅.基于BF算法改进的字符串模式匹配算法[J].电脑编程技巧与维护,2014(22):14-15.
[4] RAHIM R, ZULKARNAIN I, JAYA H. A Review: search visualization with Knuth Morris Pratt algorithm[C]//IOP Conference Series: Materials Science and Engineering. Medan: IOP, 2017,237(1):012026.
[5] 李先祥,陈思琪,肖红军,等.基于SGBM算法与BM算法的三维重建分析[J].自动化与信息工程,2019,40(5):6-12.
[6] 王茁.基于有限状态自动机的公交车到站时间预测模型[D].哈尔滨:哈尔滨工业大学,2012.
[7] 程晓锦,徐秀花.有限状态自动机及在字符串搜索中的应用[J].北京印刷学院学报,2014,22(4):45-48.
[8] 熊仁都,杨嘉佳,朱广宇,等.PARA -AC:一种基于AC自动机的高性能匹配算法[J].电子技术应用,2020,46(11):87-90.
[9] 赵庚兵.基于自动机理论的软件项目进度监控方法研究[D].广州:广东工业大学,2016.
[10] KNAST R. Finite -state probabilistic languages[J]. Information & Control, 1972,21(2):148-170.
[11] BLANCO A, DELGADO M, PEGALAJAR M C. Fuzzy automaton induction using neural network[J]. International Journal of Approximate Reasoning, 2001,27(1):1-26.
[12] DAS S, GILES C L, SUN G Z. Using prior knowledge in an NNPDA to learn context -free languages[J]. Advances in Neural Information Processing Systems, 1993,5:65-72.
[13] 宋文,牟行军.计算的模型:图灵机与Petri网[J].西华大学学报(自然科学版),2012,31(3):1-6.
[14] 罗智勇,杨旭,孙广路,等.基于马尔可夫的有限自动机入侵容忍系统模型[J].通信学报,2019,40(10):79-89.
[15] 敬茂华,杨义先,汪韬,等.新颖的正则NFA引擎构造方法[J].通信学报,2014,35(10):98-106.
[16] 蒋宗礼,姜守旭.形式语言与自动机理论[M].北京:清华大学出版社,2002:89-91.
[17] THOMAS H C, CHARLES E L, RONALD L R, et al.算法导论[M].殷建平等,译.3版.北京:机械工业出版社,2013:583-588.WALTER S. Turning machine: US 2,389,556[P], 1945-11-20.
相似文献/References:
[1]刘帆,赵亚慧,崔荣一.基于自动机的用户名合法性检测方法[J].延边大学学报(自然科学版),2022,(02):169.
LIU Fan,ZHAO Yahui,CUI Rongyi.Username validity detection method based on automata[J].Journal of Yanbian University,2022,(02):169.
备注/Memo
收稿日期: 2020-11-05 基金项目: 延边大学外国语言文学一流学科建设项目(18YLPY13)
*通信作者: 赵亚慧(1974—),女,教授,研究方向为模式识别、智能计算、自然语言处理.