（计算机科学与技术专业论文）两类幻方新问题的计算理论初探及猜想.pdf

国防科技大学研究生院学位论文 摘要 缺陷幻方填充、幻方模和分解等问题是幻方研究中发现的具有密码学意义的 新问题。这些幻方新问题在网络身份认证、电子标签、访问控制、密钥管理与分 发、微支付以及数码防伪等领域具有重要的实质性应用价值。对它们进行系统的 理论研究，对于幻方新问题的应用具有直接的指导作用。针对这种需求，本文应 用有限域上的线性代数和计算复杂度理论中的方法对幻方模和分解及缺陷幻方填 充这两个关键问题进行了深入研究，取得的主要成果如下： ( 1 ) 研究了疗2 + l 为素数时幻方模和问题的一些基本性质。证明了 以= 4 , 6 ，1 0 , 1 4 , 1 6 ，2 0 时聆阶幻方模和矩阵可构成( 以2 2 n 一1 ) 维线性空间，并提 出了上述阶数的可分解为多个幻方之模和的幻方模和矩阵判别法，给出了幻 方模和矩阵的初步分解方法。在此基础上提出了满足蚪2 + l 为素数的任意盯 阶幻方模和空间的维数都等于( 一2 2 n 一1 ) 的猜想。 ( 2 ) 研究了低阶缺陷幻方的两种填充算法，并分析了它们存在的不足。针对缺陷 幻方填充问题的n p 完全性证明，提出了一条证明思路。 ( 3 ) 为证明缺陷幻方填充问题的p 完全性，本文提出了完美拉丁方的概念，并 且讨论了它的性质及与幻方之间的联系，特别是证明了5 阶完美幻方与5 阶 正交完美拉丁方对的一一对应关系，有可能给幻方研究提供一种新的研究方 法。 主题词：幻方，缺陷幻方，模运算，线性空间，n p 完全性 第i 页 国防科技大学研究生院学位论文 a b s t r a c t h o wt oc o m p l e t ea l lu n f m i s h e dm a g i cs q u a r ea n dh o wt os e p a r a t et h em o d u l u ss u l n o fm a g i cs q u a r e sa r en e wp r o b l e m sw i t hc r y p t o 掣a p h i c a ls i g n i f i c a n c ei nm a g i cs q u a r e s o m ep r a c t i c a la p p l i c a t i o n so f 也e mc a l lb ew i d e l yf o u n di nt h ef i e l d ss u c ha sn e t w o r k i d e n f i f i c a t i o n , e l e c t r o n i ct a g ，a c c e s sc o n t r o l ，k e ym a n a g e m e n ta n da s s i g n m e n t ， m i c r o - p a y m e n t , d i g i t a la n t i - f a k et e c h n i q u ea n d e t c r e s e a r c h i n go nt h e s en e wp r o b l e m s i nt h e o r yw i l lb ea ni m p o r t a n ta s s i s t a n tt ot h ea p p l i c a t i o n so f t h e m a i m e da tt h i sn e e d , w ed e v e l o po u rw o r ko nt h es t u d yo ft h et w oc r u c i a lp r o b l e m so fs e p a r a t i n gt h e m o d u l u s $ 1 1 mo fm a 毋cs q u a r e sa n dc o m p l e t i n ga nu n f i n i s h e dm a # cs q u a r eu s i n g m e t h o d so fl i n e a ra l g e b r ai nt h ef m i t ef i e l da n dc o m p u t a t i o n a lc o m p l e x i t y t h em a i n c o n t r i b u t i o n so f t h i st h e s i sa r es u l i n a r i z e da sf o l l o w s ( 1 ) t h i sp a p e rf o c u s e so ns o m eb a s i cp r o p e r t i e so f t h ep r o b l e m o f h o wt os e p a r a t et h e m o d u l u ss u l no fm a g i cs q u a r e sa s s o c i a t e dw i t hn 2 + 1b e i n gap r i m en u m b e r a p r o o f i sg i v e nt h a ta l lm a t r i c e so ft h em o d u l u s 羽】mo fm a g i cs q u a r e so fo r d e r 阼 m a k eu po fal i n e a rs p a c ew i t h ( n 2 2 n 一1 ) d i m e n s i o n si fn = 4 , 6 , 1 0 , 1 4 , 16 ，2 0 t h e na p r e t t yt h e o r yi sp r o v e dt od e t e r m i n ew h e t h e ra m a t r i xi sam o d u l u ss 吼o f s o m em a g i cs q u a r e so fo r d e r 撑( n = 4 ，6 , 1 0 , 1 4 ，1 6 ，2 0 ) ，a n dap r i m a r ys o l u t i o ni s p r o p o s e dt os e p a r a t et h em o d u l u s 飘l m o fm a g i cs q u a r e s o nt h eb a s i so ft h i s 。a c o n j e c t u r ei sp r e s e n t e dt h a tt h ed i m e n s i o no f t h el i n e a rs p a c ew h i c hi sm a d eo f b y a l lm a t r i c e so f t h em o d u l u ss u mo f m a g i cs q u a r e so f o r d e rni s 西2 - 2 n - 1 ) i f 2 + li s a p r i m e n u m b e r ( 2 ) 1 1 1 i sp a p e rr e s e a r c h e so nt w oa l g o r i t h m st os o l v et h eu n f i n i s h e dm a g i cs q u a r e w i t hl o wf a n ka n da n a l y s e st h ed e f e c t so ft h e m ap r i m a r ys o l u l i o ni sg i v e nt o p r o v e t h ec o n j e c t u r et h a tc o m p l e t i n ga nu n f i n i s h e dm a g i cs q u a r ei sn p - c o m p l e t e ( 3 ) t op r o v et h a tc o m p l e t i n ga l lu n f i n i s h e dm a g i cs q u a r ei sn p - e o m p l e t e , t h i sp a p e r d e f i n e sp e r f e c tl a t i ns q u a r ea n dd i s c u s s e si t sp r o p e r t i e s t h er e l a t i o nb e t w e e n p e r f e c tl a t i ns q u a r e sa n dm a g i cs q u a r e s , e s p e c i a l l yt h em a p p i n gb e t w e e np e r f e c t l a t i ns q u a r e so fo r d e r5a n dp e r f e c tm a g i cs q u a r e so fo r d e r5w h i c hi sp r o v e di n t h i sp a p e rm a yp o s s i b l yp r o v i d ean e wm e t h o dt os t u d ym a g i cs q u a r e k e yw o r d s ：m a g i cs q u a r e ，u n f i n i s h e dm a g i cs q u a r e ，m o d u l u so p e r a t i o n ， l i n e a rs p a c e ，n p c o m p l e t e n e s s 第n 页 国防科技大学研究生院学位论文 表目录 表4 1 不同时间复杂度函数运算性能的对比 表4 26 阶缺陷幻方的测试结果 2 9 3 7 第1 页 国防科技大学研究生院学位论文 图1 1 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图3 1 图4 1 图4 2 图4 3 图4 4 图4 5 图目录 旅行者1 号、2 号上搭载的4 阶幻方示意图。1 用连续摆数法构造的5 阶幻方 缺陷幻方填充问题 幻方模和原理 幻方加密 缺陷幻方洗牌过程 互补缺陷幻方洗牌恢复过程l o 服务器确认用户m 晚身份的过程 用户a l i c e 确认服务器身份的过程 幻方模和分解问题 缺陷幻方填充问题对应的判定问题。 确定型单带图灵机( d t m ) 示意图 2 8 3 0 非确定型单带图灵机( n d t m ) 示意图3 1 部分拉丁方扩充问题 缺陷完美拉丁方填充问题 。3 8 4 8 第1 v 页 7 8 9 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：匿差绝友堑回塑盟盐簋堡论麴拯区猹塑 学位论文作者签名：立毖盘叁日期：姗年，月，妇 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：煎差堑友堑回基盟进箕垄诠塑握丛筮璺 学位论文作者签名： 作者指导教师签名： b 瓤：劫易辱h 琢| # b 日期：年j 月i f 日 国防科技大学研究生院学位论文 第一章绪论 1 1 幻方的基本概念 幻方是最古老的组合数学问题之一。一个珂阶幻方是由自然数l ，2 , 3 ，栉2 按下 述方法组成的开 方阵：该方阵每行、每列以及每条主对角线的整数之和均等于 常数j = n ( n 2 + 1 ) 2 。这个整数j 叫做平衡数或者幻和( m a g i cs u m ) 。 幻方的历史可追溯至公元前2 2 0 0 年中国的洛书，周易系辞上说“河出图、 洛出书、圣人则之”，“洛书盖取龟象，故其数，戴九履一，左三右七，二四为 肩，六八为足”，这里的洛书用数字列出，就是一个3 阶幻方。幻方自产生之日 起就被蒙上了一层神秘色彩，在很长一段时间里，曾用来作为天文学与占h 术的 重要理论基础，试图以此对哲学、自然现象以及人类行为做出某些似乎合理的解 释。到了现代，幻方除了被认为是一种简单的数学现象外，也被当作人类文明的 一个重大发现。1 9 7 7 年，美国发射了寻求星外文明的宇宙飞船旅行者l 号和旅行 者2 号，搭载物中除了包括绘有男、女人体形态的金属片外，还包括个代表人 类在数学方面的知识和成就的4 阶幻方，如图1 1 所示。 ： 图1 1 旅行者1 号、2 号上搭载的4 阶幻方示意图 在很长一段时间里，幻方的研究进展是非常缓慢的，直到1 7 世纪，人们才开 始对幻方进行系统严肃的分析。1 6 8 8 年法国数学家d el al o u b e r e 研究了幻方构造 的数学理论；十九世纪后半期，数学家将幻方用于概率分析；本世纪，由于计算 机的问世，幻方得到了新的发展。幻方研究人员已经发现各种各样的具有特殊数 学性质的幻方，并试图从理论上探讨其存在性、统一构造方法及其计数问题【l 】。现 在，幻方已经在组合解析学、矩阵理论、图像变换、信息隐藏、组合编码、身份 认证等领域获得了广泛的应用。 1 2 课题的来源及研究目的 第1 页 国防科技大学研究生院学位论文 幻方的数量特别巨大，6 阶幻方的数量已经高达( 1 - 7 7 4 5 士0 0 0 1 6 ) x 1 0 1 9 个已有 的幻方构造方法都属于确定的构造方法，不能任意构造幻方。2 0 0 2 年，国防科技 大学的谢涛老师利用演化计算方法设计了一种随机幻方的快速构造算法 2 1 。该算法 能快速随机地构造任意阶幻方，使得每次随机构造过程中对任一幻方都具有均等 的“命中”概率。基于此算法，他提出了关于幻方新的基本数学问题，即“缺陷幻 方填充问题”、“幻方模和分解问题”及“缺陷幻方洗牌恢复问题”等【3 】，同时申请了 多项发明专利与应用新型专利。 本课题来源于国家自然科学基金项目若干幻方新问题的理论及其应用研 究。缺陷幻方填充、幻方模和分解、幻方洗牌恢复与幻方加密等问题的发现， 是智能计算、组合数学与密码学等多学科之间交叉研究的结果，具有重要的理论 意义。同时，这些幻方新问题在网络身份认证、电子标签、访问控制、密钥管理 与分发、微支付以及数码防伪等领域具有重要的实质性应用价值。对这些幻方新 问题进行理论上的系统分析，以确认或改进已有算法与技术的安全强度，对于推 动幻方研究的发展和幻方新问题的实质性应用具有重要的现实意义。 1 3 本文的主要工作简介及结构安排 本课题主要围绕幻方模和分解和缺陷幻方填充两个关键幻方新问题展开研 究，论文是在谢涛副研究员的具体指导下完成的，主要工作包括： ( 1 ) 总结了幻方研究的现状j 介绍了若干幻方新问题的发现及其潜在应用。 c 2 ) 研究了幻方模和分解问题。首次发现了满足t = 4 , 6 , 1 0 , 1 4 ，1 6 ，2 0 时n 阶幻方模和 矩阵的一些基本性质，证明了行= 4 , 6 ，1 0 , 1 4 , 1 6 , 2 0 时以阶幻方模和矩阵可构成 伽2 2 n 一1 ) 维线性空间，提出了上述阶数的可分解为多个幻方之模和的幻方 模和矩阵判别法，给出了一种幻方模和矩阵的初步分解方法。并在此基础上 提出了满足疗2 + 1 为素数的任意一阶幻方模和空间的维数都等于0 2 2 n 一1 ) 的猜想。 ( 3 ) 深入分析了缺陷幻方填充问题。对低阶缺陷幻方填充算法进行了研究，提出 了两种填充方法。对缺陷幻方填充问题的n p 完全性证明进行了探索，提出了 一条证明思路，并且完成了思路前两步的阶段性工作。 ( 4 ) 为证明缺陷幻方填充问题的p 完全性，提出了完美拉丁方的概念，发现了正 交完美拉丁方与完美幻方的关系，特别是5 阶完美幻方与5 阶正交完美拉丁方 对表现出的一一对应关系，有可能给幻方研究提供一种新的研究方法。 本论文共有5 章，内容具体安排如下： 第一章是绪论，本章概括的介绍了幻方的概念及本课题的来源和研究目的， 第2 页 国防科技大学研究生院学位论文 并简要地介绍了本文的主要工作及结构安排。 第二章介绍了幻方的研究现状，包括幻方在信息技术领域的应用，并着重阐 述了新发现的幻方若干新问题及其在身份认证方面的应用。 第三章分析了幻方模和分解问题，重点探讨了疗2 + 1 为素数时n 阶幻方模和分 解问题所特有的性质，首次将此问题置于素域上的线性空间来讨论，并给出了一 个满足条件的低阶幻方模和矩阵判别法和一个初步分解方法。 第四章分析了缺陷幻方填充问题，一方面对低阶缺陷幻方填充算法进行了研 究，给出了两种填充方法，并分析了两种方法存在的弊端；另一方面对缺陷幻方 填充问题的p 完全性证明进行了探索，提出了一条证明思路，并且介绍了思路前 两步所做的工作。 第五章是对全文工作的总结，概述了本文工作中的主要结果，并对未来的工 作做了简单的展望。 1 4 本章小结 本章是整个论文的绪论部分，着重介绍了课题的来源、研究目的、主要工作 简介以及全文结构安排。 第3 页 国防科技大学研究生院学位论文 第二章幻方研究现状及若干幻方新问题的提出 幻方是一个具有悠久历史的组合数学问题，以往幻方研究工作的重点是试图 发现各式各样的具有特殊数学性质的幻方，并从理论上探讨幻方的存在性、统一 构造方法及其计数问题，有关幻方应用方面的研究尚未大规模涉及。本章将介绍 幻方的研究现状，首先我们将概括介绍幻方的组合学研究方法及结果，然后简单 介绍幻方在信息技术领域的一些应用，最后重点介绍若干幻方新问题。 2 1 幻方的组合学研究方法及结果 幻方是组合学研究的一个组态。组合学研究组态的方法通常是研究组态的存 在性、组态的计数与分类、组态的构造算法及已知组态的性质。因此，传统幻方 研究主要集中在三个方面：其一是研究幻方的存在性及数量；其二是寻找有效算 法构造任意阶的幻方；其三是研究某些特殊形式的幻方【1 1 以及幻方在多维空间的推 广 2 1 1 幻方的数量 除了2 阶幻方不存在外，其他任意自然数阶的幻方都存在。因为1 个幻方通 过方阵旋转与反射，可得到7 种变形，但它们其实都是同构的，因此传统的幻方 计数方法将这8 个同构型幻方计作1 个幻方。按照这种计数方法，3 阶幻方有1 个， 4 阶幻方有8 8 0 个，5 阶幻方个数为2 7 5 ，3 0 5 , 2 2 4 ，幻方的数量随阶数的增加增长很 快，6 阶以上幻方的精确计数问题仍然是一个未曾解决的公开问题，通过m o n t e c a r l o 仿真估计 4 1 ，6 阶幻方的数量高达( 1 7 7 4 5 士0 0 0 1 6 ) x 1 0 1 9 个。 在本论文中，我们更多时候是将幻方看作向量或矩阵，因此在后面的章节中 我们没有沿袭传统的幻方计数方法，而是将8 个同构型各看作一个幻方，这样， 幻方的数量是传统计数方法所得数量的8 倍。 2 1 2 任意阶幻方的构造方法 虽然目前尚无有效的算法可以找出任意阶数的所有幻方，但已有方法可构造 出任意阶的幻方。 、 ， 任意奇数阶的幻方可以按照洛贝利的连续摆数法( c o n t i n u o u sn u m b e r i n g m e t h o d ) 产生。其法则如下【5 】：把l 放在中间一列最上边的方格中，从它开始，按 对角线方向( 比如说按从左下到右上的方向) 顺次把由小到大的各数放入各个方 格中，如果碰到顶，则折到底；如果到达右侧，则转向左侧，如果进行中轮到的 第4 页 国防科技大学研究生院学位论文 方格中已有数或到达右上角，则退至前一格的下方。按照这个法则建立的5 阶幻 方如图2 1 所示。 1 72 4181 5 2 3571 41 6 461 32 02 2 1 01 21 92 l3 1 11 82 529 图2 1 用连续摆数法构造的5 阶幻方 巴赫特的阶梯法( t e r r a c e sm e t h o d ) 也可以构造任意奇数阶幻方。其方法是把 刀阶方阵从四周向外扩展成阶梯状，然后把1 铲个自然数顺阶梯方向先摆放好， 再把方阵以外部分平移到方阵以内其对边部分中去，即构成幻方。此外j h c o n w a y 和v a c c a 分别独立地发明了将奇数集中在方阵中央，而将偶数分布在四角 的方法来构造任意奇数阶幻方p j 。 偶数阶幻方构造问题分为两类。当n 为4 的整数倍时，这样的 阶幻方称为 双偶阶幻方。双偶阶幻方构造比较容易，已有构造方法有对称法、对角线法和比 例放大法等。当栉是2 的整数倍但不是4 的整数倍，这样的打阶幻方称为单偶阶 幻方单偶阶的幻方构造通常比较复杂，如r a l p hs t r a c h e y 首先构造出4 个n 2 阶 的奇数阶幻方，然后通过一个变换矩阵进行必要的行列变换，最终得到一个r 阶 幻方嘲。 文献 6 d p 利用泛系方法提出并证明了递归构造万阶幻方的方法，并给出了利 用m 阶和玎阶幻方构造f i t 阶幻方的公式；文献阴中也给出了一种巧妙构造任意 阶幻方的方法，而且构造的幻方都具有对称的特性。 总之，尽管已经存在统一的幻方构造方法，利用这些方法可以构造任意阶的 幻方，但这些构造方法都属于确定的构造方法，不能任意构造幻方。 2 1 3 特殊形式的幻方 幻方研究的另一个传统方向是幻方向多维情形的推广和寻找某些满足更加苛 刻条件的幻方。 幻方在3 维情形下的推广已经被广泛研究。以阶幻方体( m a g i cc u b ) 是按下述方 式由自然数l ，2 ，3 ，n 3 构造成的一个? i xt x 行的立方体阵列，其在下述每一条直线 上的行个元素的和都等于j = ( 疗4 + n ) 2 ：i ) 平行于立方体一条边的直线；i i ) 每 个截面上的两条对角线；i i i ) 四条空间对角线。已经证明不存在2 阶和3 阶幻方体， 文献【8 给出了一个8 阶幻方体。 第5 页 国防科技大学研究生院学位论文 寻找满足更加苛刻条件的幻方主要表现在对完美幻方( p a n - d i a g o n a lm a g i c s q u a r e ) 的广泛研究中。所谓完美幻方是指幻方中不但两条主对角线上的数字和同 各行、各列上的数字和都相等，而且在任意折对角线上的数字和也都相等。徐桂 芳在文献【9 】中给出了一种阶数为疗= 2 a p 。4 p 。鲰( 其中p ，为大于2 的素数，兄、 吼为非负整数，疗 3 且a 1 ) 的完美幻方的构造方法。胡俊华证明了不存在4 k + 2 阶完美幻方【埘。我们在第四章中将利用到这个结论。 文献【1 】收集了幻方作为组合学研究的组态存在的2 3 个尚未解决的问题和猜 想，以及与这2 3 个问题有关的一些最新结果，基本上反映了幻方在组合学研究中 的进展情况。 2 2 幻方在信息技术领域的一些应用 幻方具有良好的平衡特性，它的这一特性在图像处理、组合编码等方面得到 初步应用。 幻方是一种特殊的数值矩阵，其行、列和对角线上的元素和等于同一个常数， 利用此性质，以幻方为控制网数据矩阵而生成的b e z i e r b e r n s t e i n 曲面，具有单向 积分不变的特性，而其它熟知的逼近方式，如b 样条插值或磨光、l a g r a n g e 插值 等，皆不具备这一性质。幻曲面是幻方从离散到连续的推广，其在图形处理上有 广泛的应用空间【1 1 1 1 1 2 1 。 完美准二进幻方【1 3 1 具有特殊的结构特点，其与二进制非线性等重码具有一定 的映射关系。利用完美偶阶准二进幻方可直接构造一类典型的( 2 k x 2 ，2 kk 2 ) 非 线性等重码。 利用幻方变换对待加密数字图像进行预处理，可提高图像加密和信息隐藏的 安全强度【1 4 】【1 5 1 。 2 3 若干幻方新问题的发现及其应用 已有的幻方构造方法仅能构造单一确定的或极少数的幻方，不能任意构造幻 方。如何用计算机快速随机地构造幻方，使得每次随机构造过程中对任一幻方都 具有均等的“命中”概率? 国防科技大学的谢涛老师利用演化计算方法设计了一 种随机幻方的快速构造算法，能快速产生任意阶幻方，基于此方法，他提出了关 于幻方的新的基本数学问题，即“缺陷幻方填充问题”、“幻方模和分解问题”以及“缺 陷幻方洗牌恢复问题”。在动态身份认证中这三个问题可相互结合、取长补短，形 成一种新的安全高效的双向动态身份认证数学原理，在网络身份认证、电子标签、 访问控制、密钥管理与分发、微支付以及数码防伪等领域具有广泛的应用价值。 第6 页 国防科技大学研究生院学位论文 本节中，我们将详细介绍若干幻方新问题以及它们的一个应用范例，本节内容参 考了文献 2 】【1 6 】。 2 3 1 随机幻方的快速演化构造 随机幻方快速演化构造算法采用演化计算方法可快速随机产生任意阶幻方。 演化计算是一种模拟生物物种进化过程机理的随机自适应学习算法，通过模拟杂 交、变异与适者生存等物种进化机制，演化计算可以求解许多复杂的全局优化与 搜索问题。如果算法中的初始种群是均匀随机设置的，并且各遗传变异算子也是 均匀随机分布的，那么演化算法对于均匀分布的解空间的搜索过程就是一个均匀 随机采样过程。因此，演化算法所产生的具体幻方依赖于初始种子随机数的设置， 不同的初始设置产生不同的幻方，每一次所得到的幻方可视为在整个幻方空间中 作一次均匀随机采样的结果。每次随机幻方的构造过程对幻方空间中任何一个幻 方具有均等的命中概率，但具体每次最终命中哪一个幻方则完全是随机偶然的， 因而根据算法是不可预测的。 2 3 2 缺陷幻方填充问题 将一个随机构造的幻方均匀随机分割为两个互补缺陷幻方，目前理论上还不 存在有效的统一计算方法，使得由仅含一半数字的缺陷幻方恢复出另一半位置的 数字，使之仍然构成一个幻方，反之亦然。我们称该问题为缺陷幻方填充问题。 如图2 2 所示。 1 34 21 654 46 4 9 4 63 642 92 2 03 8 2 43 43 72 32 81 0 1 9 39 4 52 13 24 81 7 4 02 23 11 l2 74 31 4 11 83 03 9 71 52 5 81 41 24 73 53 32 6 缺陷幻方互补缺陷幻方 1 3 1 6 6 3 62 923 8 3 43 72 8 32 l4 81 7 4 02 22 74 3 3 03 92 5 81 43 5 4 2 54 44 9 4 642 0 2 4 2 3 1 01 9 9 4 53 2 3 11 1l 4 1 1 871 5 1 24 73 32 6 图2 2 缺陷幻方填充问题 幻方与拉丁方存在密切联系，部分拉丁方可扩充性问题已证明是n p 完全问 题，种种迹象表明缺陷幻方填充比部分拉丁方扩充更加复杂，此问题极可能是n p 难问题。文献【1 7 】【1 8 】对低阶缺陷幻方填充问题进行了专门研究，提出了一种改进 的条件组合算法，但该算法的复杂性与缺陷数字个数、组合个数、缺陷数字分布 有关，基本还是简单穷举搜索法的改进，不是解决缺陷幻方填充的成熟算法。 第7 页 国防科技大学研究生院学位论文 如果将其中任意一个缺陷幻方作为锁，另一个则可作为相应的钥匙，二者互 为锁与钥匙。由“锁”推不出相应的“钥匙，由“钥匙”推不出相应的“锁”，同时“锁” 可以公开，这就是幻方数字锁原理。 2 3 3 幻方模和分解问题 将两个栉阶随机幻方的元素按位相加取模”2 + l 得到一个模, 2 + l 内自然数的 矩阵j ( 如图2 3 所示) ，在计算上很难将j 分解为两个幻方之模和，判断矩阵s 是 否为两个刀阶随机幻方之模和在计算上也是很难的。一般地，将七2 个随机构造 的珂阶幻方的矩阵元素按位相加再取模疗2 + 1 ，得到一个模, 2 + 1 内自然数的矩阵 j ，在计算上很难将s 分解为七个幻方之模和，判断矩阵s 是否可分解为膏个n 阶随 机幻方之模和在计算上也是很难的。 随机幻方l随机幻方2幻方模和矩阵s 2 34 61 71 03 71 32 9 2 83 54 52 433 3 7 3 483 9 61 44 43 0 1 11 83 84 12 52 22 0 1 52 7l4 2 9 4 93 2 4 33 61 944 0 23 1 2 151 64 84 71 22 6 1 3 1 8 1 71 14 83 33 5 4 32 72 854 9 71 6 4 532 24 13 01 42 0 3 6 4 9 3 924 73 8 6 4 62 32 51 92 43 2 3 14 04 21 01 52 98 l3 73 44 41 22 l2 6 3 61 43 42 l3 54 61 4 2 1 1 22 32 9 24 02 3 2 91 1 1 14 74 4 8 0 4 72 24 73 02 71 98 2 12 32 41 72 82 31 4 2 42 61 11 453 13 9 2 24 2 0 4 2 93 3 2 图2 3 幻方模和原理 。 由幻方模和分解问题可直接得到幻方签名技术。随机构造一个幻方作为不公 开的签名幻方( 相当于签名私钥) ，任一随机幻方与该签名幻方模和之后得到一个签 名矩阵，该签名矩阵与签名幻方的模差必然是一个幻方，以此可以验证签名矩阵 的真伪。通过验证签名矩阵的真伪可以判断被签名的随机幻方是否由己方产生， 而非他方伪造。幻方签名技术也可以称为幻方加密技术。 幻方模和分解问题可应用于密钥管理、身份认证、多方身份认证以及数码防 伪等领域，并且具有安全强度高、验证效率高、易于逻辑芯片实现等优点。 2 3 4 幻方加密 任选一矩阵作为加密密钥，任意随机构成的幻方( 明文) 先与该密钥矩阵进行模 和得到模和矩阵，再将该模和矩阵按某一固定置换表置换，得到该幻方模和置换 矩阵，再经过数轮由矩阵正反对折模和运算与按固定置换表的置换处理组成的变 换过程，最后再与密钥矩阵模和得到输出矩阵，该过程称为幻方加密过程。其中， 由一次矩阵正反对折模和运算后再按固定置换表置换处理组成一轮加密过程。适 第8 页 国防科技大学研究生院学位论文 当选择固定置换表，不论已知多少对随机幻方( 明文) 与其加密结果( 密文) ，在计算 上很难推导出其加密密钥矩阵与置换表。幻方解密过程为加密过程的逆过程，解 密过程仅须将相应加密流程中的模和换成模减运算、正置换换成反置换即可。幻 方加密原理可应用于网络身份认证、访问控制与微支付等领域。如图2 4 所示。 多轮双对折混合变换 矩阵模和 矩阵置换， 。l 双对折模l 一 矩阵置换 矩阵模和 密钥矩阵置换表p 7 l 和变换 i 7 置换表p 密钥矩阵 图2 4 幻方加密 2 3 5 互补缺陷幻方洗牌恢复问题 从一组具有内部数学关系的可校验的h 个有序数字序列中按序随机抽取其中 约一半数字，按先后次序排成一组数字序列，并将该序列置于所剩数字序列之后， 构成一个新的数字序列，称该数字序列重组过程为随机洗牌过程，重组数字序列 称为洗牌结果，其中按序均匀随机抽取数字的方案可由一万元0 - 1 二进制表示，并 称之为洗牌方案。 仅由洗牌结果是不可能恢复原有序可校验数字序列的，洗牌结果仅可由洗牌 方案直接恢复成原有序可校验数字序列，这就是数字序列洗牌原理。 设刀以的随机幻方m 被均匀随机分割为两个互补缺陷幻方m 与鸩，向量矿 的长度为万2 ，v 中各元素初始化为0 ，均匀随机洗牌矩阵口= 眈l ，b oe o ，1 ) ( 该 洗牌矩阵可以转化为一个十进制数) 互补缺陷幻方洗牌转换算法的基本过程是，首先按序将与口中元素1 对应的 m ：中非零数字写入向量矿，然后按序将与b 中元素o 对应的鸩中非零数字输入 向量y ，所得向量y 即为洗牌结果。假设5 x 5 的幻方吖被分割为两部分m 。与鸠， 从左上角元素开始，按自左至右、从上至下的规则直至右下角元素，顺序将与b 中 元素1 对应的m ，中非零数字写入向量y 中；然后按同样次序将与曰中元素0 对应 的m ，中非零数字，紧按当前向量指针输入向量v 中，得到洗牌结果矿如图2 5 所示。 第9 页 国防科技大学研究生院学位论文 1 371 791 9 2 4l l1 4l o6 2 5 81 641 2 l1 83 2 0 2 3 22 11 52 25 缺陷幻方m ， 07oo1 9 2 4o o1 0o 2 581 6o0 lo30 2 3 0oo 2 2 5 o7oo1 9 2 4oo1 0o 2 581 600 lo 3o 2 3 0oo2 25 互补缺陷幻方m 1 301 79o 0l l1 40 6 0oo41 2 o1 8o 2 0 o 2 2 11 500 洗牌矩阵曰 looll 1o10o lo101 0l0lo 0l0l1 洗牌结果向量y 图2 5 缺陷幻方洗牌过程 互补缺陷幻方逆洗牌恢复算法是洗牌转换算法的逆过程，其中m 相当于此逆 运算过程中的“密钥”。逆洗牌恢复算法根据洗牌结果向量矿、洗牌矩阵口以及 互补缺陷幻方m 恢复出原幻方m ，可表示为：矿+ 丑丝l _ m 。逆洗牌恢复的 基本过程是，首先恢复与洗牌矩阵b 中元素l 对应的矩阵数字，从左上角元素开 始，按自左至右、从上而下的规则直至右下角元素，分别考虑与占中元素l 对应 的 以中元素，如果该元素非零，则置恢复幻方肘中相应位置为该数字；否则，置 恢复幻方肘中相应位置为向量y 中当前元素，同时向量y 的指针前进一位，如此 反复直至b 的右下角元素。然后，向量y 从当前指针开始，按同样方式恢复与b 中 元素0 对应的矩阵元素，最后得到原幻方肘如图2 6 所示。 互补缺陷幻方m 1 301 79o o1 11 406 oo041 2 o1 80 2 0 o 22 l 1 5oo 洗牌矩阵曰幻方m looll 10l0o 1olol 0l0l0 ololl 1 371 791 9 2 41 11 4 l o6 2 581 641 2 l1 83 2 0 2 3 22 1 1 52 25 洗牌结果向量矿 图2 6 互补缺陷幻方冼牌恢复过程 第l o 页 国防科技大学研究生院学位论文 互补缺陷矩阵洗牌与逆洗牌算法可用于基于随机幻方的双向动态身份认证技 术【1 9 1 。 2 3 6 幻方的一个应用范例 身份认证是信息安全的重要方面，也是电子商务过程中最薄弱的环节。它是 指通信双方可靠地验证对方的身份。身份认证的本质是示证者有一些信息，除示 证者自己外，任何第三方不能伪造，示证者能够使验证者相信他确实拥有那些信 息，则他的身份就得到了认证。身份认证包括用户向系统出示自己的身份证明和 系统查核用户的身份证明的过程。它们是判明和确定通信双方真实身份的两个重 要环节【2 0 】。身份认证最重要的技术指标就是合法用户的身份是否易于被别人冒充。 同时，要尽可能的方便、可靠，并尽可能地降低成本。 目前使用的身份认证技术从认证原理上可以分为两种类型：静态身份认证和 动态身份认证。动态身份认证就是指用户登录系统验证身份过程中，送入系统的 验证数据是动态变化的。动态身份认证目前主要有时间同步机制身份认证和挑战 应答机制身份认证。这两种身份认证方法都是基于智能令牌实现的，时间同步机 制身份认证基于时间同步令牌实现，挑战应答机制身份认证基于挑战应答令牌 实现。这两种身份认证方法在国外的应用较广，但在国内的应用还不普及，主要 原因是由于国内对令牌技术的发展还不够，并且系统中应用令牌的成本也比较高。 一种比较好的方法是用智能i c 卡和读写设备的功能来替代令牌，也可以达到较好 的效果【2 1 1 。 综合利用缺陷幻方填充、幻方模和分解与互补缺陷幻方洗牌原理，可形成一 种新的网络身份双向动态认证方法【3 j i 。假设用户a l i c e 与认证服务器之间须进行 双向身份认证，a l i c e 的身份信息可由随机产生的幻方m 0 l i c e ) 构成。将m 乜l i c e ) 随机均匀分割为两个互补的缺陷矩阵m 1 ( a l i c e ) - - 与m 2 ( a l i c e ) ，m ，( 4 肋p ) 经过幻方 签名与矩阵置换后作为认证服务器中a l i c e 的注册信息m s i ( 4 船e ) 存入认证服务器 数据库中，m 2 0 f f c e ) 直接作为a l i c e 校验认证服务器真伪的校验信息存入认证卡 中，认证卡则以p i n 码个人身份码) 保护认证服务器的校验芯片设有签名幻方与 矩阵置换表及其相关处理逻辑，认证服务器的校验芯片与认证卡中均设有缺陷幻 方洗牌与逆洗牌算法以及幻方验证逻辑模块，认证服务器与用户终端均设有均匀 随机洗牌矩阵产生模块。双向动态身份认证分为认证服务器确认用户身份与用户 确认认证服务器身份两个过程。 认证服务器确认用户a l i c e 身份的过程如下( 如图2 7 所示) ： 1 ) 用户a l i c e 登录认证服务器； 2 ) 认证服务器产生一均匀随机o 1 矩阵b ( 耽6 ，f ) 并传给用户a l i c e ； 第1 1 页 国防科技大学研究生院学位论文 图2 7 服务器确认用户a l i c e 身份的过程 3 ) 用户a l i c a 将b 耽良f ) 输入认证卡； 4 ) 认证卡以丑( 耽鼠f ) 作为c a m ( 细胞自动机) 的初态，并前向运行数步( 三步 以上) 得到此次洗牌矩阵b + ( w e b , o ；根据洗牌矩阵占( 阡名6 ，f ) 由洗牌算法将缺 陷幻方鸩汹i c e ) 转换成认证向量y o f f c e ，f ) ，爿瞒v ( a t i c e ，f ) 传回用户a l i c e ； 5 ) 用户a f i e e 将向量v ( a l i c e ，f ) 传给认证服务器； 6 ) 认证服务器将蚂0 船p ) 、y o l i c e ，f ) 与相应的洗牌矩阵b 慨6 ，f ) 一起传给校 验芯片； 7 ) 校验芯片首先以占( 耽6 j f ) 作为c a m ( 细胞自动机) 的初态，并前向运行数步 ( 三步以上) 得到此次洗牌矩阵曰( 耽6 ，r ) ；其次，根据置换表与签名幻方解 密m s a o l i c e ) 得到缺陷幻方m 。( a l i c e ) ，并按逆洗牌算法根据m 。( a l i c e ) ， v ( a l i c e ，f ) 与b ( 耽6 j f ) 合成矩阵m ；最后验证矩阵m 的幻方性质是否满足， 并将验证结果传给认证服务器。 用户a l i c e 确认认证服务器身份的过程如下( 如图2 8 所示) ： 图2 8 用户a l i c e 确认服务器身份的过程 第1 2 页 国防科技大学研究生院学位论文 1 ) 认证服务器向用户a l i c e 发送一认证请求信息，即要求用户a l i c e 产生一均匀 随机0 1 矩阵b ( a l i c e , t ) ； 2 ) 用户a l i c e 产生均匀随机o 1 矩阵b 彳，魄，) 并传给认证服务器作为响应； 3 ) 认证服务器将b ( 彳肠p ，f ) 传送至身份校验芯片； 4 ) 身份校验芯片以占z f ) 作为c a m ( 细胞自动机) 的初态，并前向运行数步 ( 三步以上) 得到此次洗牌矩阵b + ( a l i c e , t ) ；然后根据b ( a l i c e , t ) 将解密 峭0 肋口) 后所得缺陷矩阵m 。0 f f c 8 ) 洗牌成y 慨6 ，f ) ，并将v ( w e b ，f ) 送回认 证服务器； 5 ) 认证服务器将v ( w e b ，f ) 发送至用户a h c e ； 6 ) 用户a l i c e 将向量v ( w e b ，f ) 与b 0 慨f ) 输入认证卡； 7 ) 认证卡以口( 4 ，魄f ) 作为c a m ( 细胞自动机) 的初态，并前向运行数步( 三步 以上) 得到此次洗牌矩阵b ( 4 l i c e , t ) ；然后，根据逆洗牌算法将肘：( 址i c c ) 、 矿( 耽6 ，f ) 与b ( a l i c e , t ) 厶成完整矩阵m ；最后，验证该矩阵m 的幻方性质是 否满足，并将验证结果返回用户a l i c e 动态身份认证中的均匀随机洗牌矩阵曰= b l 。可由二维o - l 二状态细胞自动 机或伪随机数发生器产生，其中以 o ，1 ，全局状态中0 与l 的个数基本相等，每 行每列以及两对角线上的0 元素与1 元素个数基本相等，全局状态事实上不重复 也不可预测。细胞自动机具有不可逆性，即不能由后向状态推出其前置状态。因 此，为防止采用预先设计的攻击方法对认证智能卡中的身份特征信息m ，( a l i c e ) j 赴 行攻击，建议在认证智能卡中设计一个细胞自动机，对每一个洗牌矩阵计算三步 以上的后向状态，并以该后向状态作为洗牌矩阵直接对缺陷幻方肘，( 4 胁e ) 进行洗 牌。采用细胞自动机对洗牌矩阵进行转换，攻击者不可能对洗牌矩阵进行随意设 计 幻方验证模块首先验证幻方数字的唯一性，即验证矩阵数字是否由1 至栉2 的 连续自然数组成，如果验证成功，再继续验证每行、每列与两对角线元素的幻和： 否则，该矩阵不满足幻方的基本条件。 这套认证方案是谢涛老师提出的，同项目组的赵彬设计了基于f p g a 的p c i 接口身份认证智能卡，实现了这种基于幻方的双向动态身份认证算法，并在此基 础上设计了相关的协议初步实现了一个身份认证系统。 。 2 4