拓扑图形密码导出文本密码的一种技术.pdf
《拓扑图形密码导出文本密码的一种技术.pdf》由会员分享,可在线阅读,更多相关《拓扑图形密码导出文本密码的一种技术.pdf(8页珍藏版)》请在咨信网上搜索。
1、 第5 9卷2 0 2 3年第5期 西 北 师 范 大 学 学 报(自然科学版)V o l.5 9 2 0 2 3 N o.5 J o u r n a l o f N o r t h w e s t N o r m a l U n i v e r s i t y(N a t u r a l S c i e n c e)D O I:1 0.1 6 7 8 3/j.c n k i.n w n u z.2 0 2 3.0 5.0 0 8收稿日期:2 0 2 2 0 3 1 4;修改稿收到日期:2 0 2 3 0 5 3 1基金项目:国家自然科学基金资助项目(6 1 1 6 3 0 5 4,6 1 1
2、 6 3 0 3 7,6 1 3 6 3 0 6 0)作者简介:孙宜蓉(1 9 7 8),女,山东济宁人,讲师,硕士.主要研究方向为拓扑图形密码.E m a i l:s u n y r n w n u.e d u.c n*通信联系人,男,教授.主要研究方向为复杂网络、网络加密及拓扑图形密码.E m a i l:y y b b 9 1 81 6 3.c o m拓扑图形密码导出文本密码的一种技术孙宜蓉,姚 兵*(西北师范大学 数学与统计学院,甘肃 兰州 7 3 0 0 7 0)摘要:拓扑图形密码是一种新型的图形密码,它具有计算机存储小、运行快、容易产生文本密码等优点.本文针对一种特殊拓扑结构(毛毛
3、虫树)下的奇优美标号进行算法构造,证明了算法的多项式性.为深入研究拓扑图形密码的多样性和广泛性,本文给出了探讨性的例证和问题.关键词:文本密码;多项式算法;拓扑图形密码;毛毛虫树;奇优美标号中图分类号:O 1 5 7.5 文献标志码:A 文章编号:1 0 0 1-9 8 8(2 0 2 3)0 5-0 0 3 9-0 8A t e c h n i q u e f o r p r o d u c i n g t e x t-b a s e d p a s s w o r d s f r o mt o p o l o g i c a l g r a p h i c p a s s w o r d
4、sS UN Y i-r o n g,YAO B i n g(C o l l e g e o f M a t h e m a t i c s a n d S t a t i s t i c s,N o r t h w e s t N o r m a l U n i v e r s i t y,L a n z h o u 7 3 0 0 7 0,G a n s u,C h i n a)A b s t r a c t:T o p o l o g i c a l g r a p h i c p a s s w o r d i s a n e w t y p e o f g r a p h i c a
5、l p a s s w o r d s,w h i c h d i f f e r s f r o m t h e e x i s t i n g g r a p h i c a l p a s s w o r d s,o c c u p i e s l e s s s p a c e o f c o m p u t e r,a n d r u n s q u i c k l y,a s w e l l a s p r o d u c e s t e x t-b a s e d p a s s w o r d s.A n a l g o r i t h m i c i s c o n s t
6、r u c t e d f o r t h e o d d-g r a c e f u l l a b e l l i n g o f p a r t i c u l a r t o p o l o g i c a l s t r u c t u r e s,c a l l e d c a t e r p i l l a r s,a n d o u r m e t h o d i s p o l y n o m i a l.F o r f u r t h e r r e s e a r c h i n g g e n e r a l i z a t i o n a n d v a r i e
7、t y o f t o p o l o g i c a l g r a p h i c p a s s w o r d s,s o m e e x a m p l e s a n d p r o b l e m s a r e a l s o g i v e n.K e y w o r d s:t e x t-b a s e d p a s s w o r d;p o l y n o m i a l a l g o r i t h m;t o p o l o g i c a l g r a p h i c p a s s w o r d;c a t e r p i l l a r;o d d-
8、g r a c e f u l l a b e l l i n g0 引言随着互联网的迅猛发展和网民数量的日益增多,密码认证成为人们在互联网应用和现实生活中常用的安全手段.图形密码是一种全新的身份认证技术.与传统的文本密码不同,图形密码使用图形作为认证媒介,通过用户对图形的点击、识别、重现,或者用户与图形系统的互动进行认证.然而,图形密码需要占用大量计算机的存储单元,造成运行缓慢;并且用户不能自己随意更换图片,或者自己设计图形密码.近来,W a n g等1-2提出了一种新的图形密码,叫做拓扑图形密码,它与现存的图形密码(比如二维码)有所不同,是通过代数矩阵存储在计算机中的.拓扑图形密码的一个优
9、点是它可以通过拓扑图产生一个很长的文本密码.文献3 介绍了从拓扑图形密码生成文本密码的一些方法,这些方法是基于图的拓扑结构和图标号产生的,其中一些方法还可以转换成多项式算法.文献3 还介绍了产生文本密码D(a)的“路-邻居”方法,此方法对以毛毛虫树为拓扑结构的图形密码极为有效.但是,没有给出具体的算法来得到奇优美毛毛虫树.本文给出一个快速的多项式算法来解决这个问题,并给出顶点剖分方法下的一个奇优美毛毛虫树算法.93西 北 师 范 大 学 学 报(自然科学版)第5 9卷 J o u r n a l o f N o r t h w e s t N o r m a l U n i v e r s i
10、 t y(N a t u r a l S c i e n c e)V o l.5 9 文中有关图论的标准术语和记号可参见文献4,5,且所提及的图均为有限、无向、简单图.为叙述简洁,当m和n均为整数且0mn时,记号m,n 表示集合m,m+1,n;当s和t均为奇数且1st时,记号s,to表示奇数集合s,s+2,t;当s和t均为偶数且0st时,用记号s,te表示偶数集合s,s+2,t.若图G中任两个顶点x,y之间都能用唯一的一条路P(x,y)=x u1u2umy连接,则称图G是一棵树,树中的一度顶点称为树的叶子.如果把树中的所有叶子都删掉后,仅剩路P,则称树为毛毛虫树;如果把树中的所有叶子都删掉后,
11、仅剩毛毛虫树,则称树为龙虾树;若图G中有p个顶点q条边,则称图G是(p,q)-图.定义13 设图G是(p,q)-图,给定映射h:V(G)0,2q-1,且对任何不同的顶点u,vV(G),总有h(u)h(v);每条边u vE(G)的标号定义为:h(u v)=h(u)-h(v).当图G的边标号集合满足h(E(G)=h(u v):u vE(G)=1,2q-1o时,称h是图G的一个奇优美标号;若图G是一个具有二部划分(X,Y)的偶图,且m a xh(u):uXm i nh(v):vY(简记为hm a x(X)hm i n(Y),则称h是图G的一个集有序的奇优美标号.1 毛毛虫树图形密码的两个算法1.1
12、奇优美毛毛虫树算法设毛毛虫树H中的一条路为P=u1u2un,记每个顶点ui的叶子集合为L(ui)=vi,j:j1,mi ,其中mi是整数,mi0且i1,n,则V(H)=V(P)L(u1)L(u2)L(un).毛毛虫树的结构如图1所示.图1 毛毛虫树F i g 1 A s c h e m e o f a c a t e r p i l l a r 由于图H是二部图,所以它的顶点集二部划分(X,Y)为:当n为偶数时,X=u2i-1:i 1,n2 n/2i=1L(u2i),Y=u2i:i 1,n2 n/2i=1L(u2i-1);(1)当n为奇数时,X=u2i-1:i 1,n+12 (n-1)/2i=
13、1L(u2i),Y=u2i:i 1,n-12 (n+1)/2i=1L(u2i-1).(2)奇优美毛毛毛虫树算法初始化.令h是毛毛虫树H的一个标号.先对X中顶点进行标号.令h(u1)=0,h(v2,j)=h(u1)+2j,j1,m2;h(u3)=h(v2,m2)+2=2(m2+1),h(v4,j)=h(u3)+2j=2(m2+1+j),j1,m4;h(u5)=h(v4,m4)+2=2(m2+m4+2),h(v6,j)=h(u5)+2j=2(m2+m4+2+j),j1,m6.步骤1.n为偶数.当2in/2时,令h(u2i-1)=h(v2i-2,m2i-2)+2=2i-1+i-1k=1m2k ,h(
14、v2i,j)=h(u2i-1)+2j=2i-1+j+i-1k=1m2k ,其中j1,m2i.再对Y中顶点进行标号.因为h(vn,mn)=2n2-1+mn+n/2-1k=1m2k =2n2-1+n/2k=1m2k ,所以令04 2 0 2 3年第5期 孙宜蓉等:拓扑图形密码导出文本密码的一种技术 2 0 2 3 N o.5A t e c h n i q u e f o r p r o d u c i n g t e x t-b a s e d p a s s w o r d s f r o m t o p o l o g i c a l g r a p h i c p a s s w o r d
15、 sh(un)=h(vn,mn)+1=2n2+n/2k=1m2k -1,它是奇数.再令h(vn-1,j)=h(un)+2j=2n2+j+n/2k=1m2k -1,其中j1,mn-1.则h(un)-h(vn,mn)=1,h(un-2)=h(vn-1,mn-1)+2,h(vn-3,j)=h(un-2)+2j,其中j1,mn-3.当1in/2-1时,令h(un-2i)=h(vn-2i+1,mn-2i+1)+2=2n2+n/2k=1m2k+ii=1mn-(2l-1)+(2i-1),h(vn-(2i+1),j)=h(un-2i)+2j=2n2+n/2k=1m2k+ii=1mn-(2l-1)+j +(2i
16、-1),其中j1,mn-(2i+1).由以上标号可得hm a x(X)=h(vn,mn)=2n2-1+n/2k=1m2k ,hm i n(Y)=h(un)=2n2+n/2k=1m2k -1,所以hm a x(X)hm i n(Y).现计算边标号:当j1,mn 时,有h(unvn,j)=h(un)-h(vn,j)=2n2+n/2k=1m2k -1-2n2-1+j+n/2-1k=1m2k =2mn-2j+1.因为 当j=mn时h(unvn,mn)=1,当j=1时h(unvn,1)=2mn-1,所 以,当j1,mn 时,h(unvn,j)1,2mn-1o,且h(un-1un)=h(un-1)-h(u
17、n)=2n2+n/2k=1m2k -1-2n2-1+n/2-1k=1m2k =2mn+1.当i1,n-1o时,有h(un-iun-(i-1)=h(un-1)-h(un-(i-1)=2n2+n/2k=1m2k+(i-1)/2l=1mn-(2l-1)+(i-2)-2n2-i+12+(n-i-1)/2k=1m2k =2 n/2k=1m2k+(i-1)/2l=1mn-(2l-1)-(n-i-1)/2k=1m2k+(2i-1)=2i-1l=0mn-l+(2i-1).(3)又当i2,n-2e时,有h(un-iun-(i-1)=h(un-i)-h(un-(i-1)=2n2+n/2k=1m2k+i/2l=1m
18、n-(2l-1)+(i-1)-2n2-i2-(n-i)/2k=1m2k =2 n/2k=1m2k+i/2l=1mn-(2l-1)-(n-i)/2k=1m2k+(2i-1)=2i-1l=0mn-l+(2i-1).(4)综上所述,当i1,n-1 时,有h(un-iun-(i-1)=2i-1l=0mn-l+(2i-1);当i1,n-1o时,有h(un-ivn-i,j)=h(un-i)-h(vn-i,j)=2n2+n/2k=1m2k+(i-1)/2i=1mn-(2l-1)+j +(i-2)-2(n-i-1)/2k=1m2k-n+i+1=2n/2k=1m2k+(i-1)/2l=1mn-(2l-1)-(n
19、-i-1)/2k=1m2k +2j+(2i-1)=2i-1l=0mn-l+2j+(2i-1),j1,mn-i.(5)所以h(un-ivn-i,j)2i-1l=0mn-l+(2i+1),2il=0mn-l+(2i-1)o.又当i2,n-1e时,有h(un-ivn-i,j)=h(un-i)-h(vn-i,j)=2n2+n/2k=1m2k+i/2l=1mn-(2l-1)+14西 北 师 范 大 学 学 报(自然科学版)第5 9卷 J o u r n a l o f N o r t h w e s t N o r m a l U n i v e r s i t y(N a t u r a l S c
20、i e n c e)V o l.5 9 (i-1)-2(n-i-2)/2k=1m2k+n-i2+j-1 =2 n/2k=1m2k+i/2l=1mn-(2l-1)-(n-i-2)/2k=1m2k-2j+(2i+1)=2il=0mn-l-2j+(2i+1),j1,mn-i,(6)所以h(un-ivn-i,j)2i-1l=0mn-l+(2i+1),2il=0mn-l+(2i-1)o.综上所述,当i1,n-1 时,有h(un-ivn-i,j)2i-1l=0mn-l+(2i+1),2il=0mn-l+(2i-1)o.以上证明可以断言h(E(H)=h(unvn,j)n-1i=1h(un-iun-(i-1)
21、h(un-ivn-i,j)=1,2mn-1o2mn+1 2mn+3,2mn+2mn-1+1o 2mn+2mn-1+3 2i-1l=0mn-l+(2i-1)2i-1l=0mn-l+(2i+1),2il=0mn-l+(2i-1)o 2n-2l=0mn-l+(2n-3)2n-2l=0mn-l+(2n-1),2n-1l=0mn-l+(2n-3)o=1,2n-1l=0mn-l+(2n-3)o.(7)因 为 毛 毛 虫 树H的 边 数 为q=n-1l=0mn-l+(n-1),所以h(E(H)=1,2q-1o.又因为hm a x(X)hm i n(Y),从而h是毛毛虫树H的一个集有序奇优美标号.步骤2.n为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 拓扑 图形 密码 导出 文本 一种 技术
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。