对合

第３１卷第１期

２０１４年１月

计算机应用研究

Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ

Ｖｏ１．３１ Ｎｏ．１

Ｊａｎ．２０１４

Ｍ ＤＳ矩阵和对合Ｍ ＤＳ矩阵的新构造方法水

郭磊 ，郑浩然 ，傅增强 ，王月

（１．解放军信息工程大学三院，郑州４５０００４；２．空军西安飞行学院，西安７１０３００）

摘要：首先对Ｌａｃａｎ等人给出的由Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ码的方法进行了研究，指出了其中存在的问

题，给出了由两个Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵的充要条件；然后利用矩阵乘的方法，给出了由标量乘

Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵的充要条件；最后在Ｓａｊａｄｉｅｈ等人给出的由两个Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造对合

ＭＤＳ矩阵方法的基础之上，给出了标量乘Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造对合ＭＤＳ矩阵的方法。对标量乘矩阵来讲，可

以通过调控标量中分量的大小来调整标量乘矩阵元素大小和元素重量大小来满足其软、硬件实现性能，因此该

构造ＭＤＳ矩阵及对合ＭＤｓ矩阵的方法具有实用价值。

关键词：分组密码；扩散结构；分支数；ＭＤＳ矩阵；Ｖａｎｄｅｒｍｏｎｄｅ矩阵

中图分类号：ＴＰ３０９．７ 文献标志码：Ａ 文章编号：１００１—３６９５（２０１４）ｏ１—０２２２－０４

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－３６９５．２０１４．０１．０５２

Ｎｅｗ ｃｏｎｓｔｒｕｃｔｉｏｎ ｍｅｔｈｏｄｓ ｆｏｒ ＭＤＳ ｍａｔｒｉｃｅｓ ａｎｄ ｉｎｖｏｌｕｔｉｏｎ ＭＤＳ ｍａｔｒｉｃｅｓ

ＧＵＯ Ｌｅｉ ，ＺＨＥＮＧ Ｈａｐ—ｒａｎ ，ＦＵ Ｚｅｎｇ—ｑｉａｎｇ ，ＷＡＮＧ Ｙｕｅ

（１．Ｉｎｓｔｉｔｕｔｉｏｎ Ｎｏ．３，Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５０００４，Ｃｈｉｎａ；２．Ｔｈｅ Ａｉｒ Ｆｏｒｃｅ Ｘｉ’ａｎ Ｆｌ ｈｔ Ａｃａｄｅｍｙ，Ｘｉ’ａｎ

７１０３００． ｉｎａ１

Ａｂｓｔｒａｃｔ：Ｆｉｒｓｔｌｙ ｔｈｉｓ ｐａｐｅｒ ｓｔｕｄｉｅｄ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ＭＤＳ ｃｏｄｅｓ ｂｙ Ｖａｎｄｅｒｍｏｎｄｅ ｍａｔｒｉｃｅｓ ｐｒｏｐｏｓｅｄ ｂｙ Ｌａｅａｎ ｅｔ ａｌ

ａｎｄ ｐｏｉｎｔ ｏｕｔ ｔｈｅ ｐｒｏｂｌｅｍｓ ｅｘｉｓｔｉｎｇ ｉｎ ｔｈｉｓ ｍｅｔｈｏｄ，ａｎｄ ｐｒｏｐｏｓｅｄ ｔｈｅ ｎｅｃｅｓｓａｒｙ ａｎｄ ｓｕｆｆｉｃｉｅｎｔ ｃｏｎｄｉｔｉｏｎｓ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ＭＤＳ

ｍａｔｒｉｃｅｓ ｂｙ ｔｗｏ Ｖａｎｄｅｒｍｏｎｄｅ ｍａｔｒｉｃｅｓ．Ｔｈｅｎ，ｕｓｉｎｇ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｍａｔｒｉｘ ｍｕｈｉｐｌｉｃａｔｉｏｎ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ｔｈｅ ｎｅｃｅｓｓａｒｙ

ａｎｄ ｓｕｆｆｉｅｉｅｎｔ ｃｏｎｄｉｔｉｏｎｓ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ＭＤＳ ｍａｔｒｉｃｅｓ ｂｙ ｓｃａｌａｒ ｍｕｈｉｐｌｉｃａｔｉｏｎ Ｖａｎｄｅｒｍｏｎｄｅ ｍａｔｒｉｃｅｓ．Ｆｉｎａｌｌｙ，ｂａｓｅｄ ｏｎ ｔｈｅ

ｍｅｔｈｏｄ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ｉｎｖｏｌｕｔｉｏｎ ＭＤＳ ｍａｔｒｉｃｅｓ ｆｒｏｍ ｔｗｏ Ｖａｎｄｅｒｍｏｎｄｅ ｍａｔｒｉｃｅｓ ｐｒｏｐｏｓｅｄ ｂｙ Ｓａｊａｄｉｅｈ ｅｔ ａｌ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏ—

ｐｏｓｅｄ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ｉｎｖｏｌｕｔｉｏｎ ＭＤＳ ｍａｔｒｉｃｅｓ ｂｙ ｓｃａｌａｒ ｍｕｈｉｐｌｉｃａｔｉｏｎ Ｖａｎｄｅｒｍｏｎｄｅ ｍａｔｒｉｃｅｓ．Ｆｏｒ ｓｃａｌａｒ ｍｕｈｉｐｌｉ—

ｃａｔｉｏｎ ｍａｔｒｉｃｅｓ，ｉｔ ｃｏｕｌｄ ａｄｊｕｓｔ ｅｌｅｍｅｎｔｓ ｓｉｚｅ ａｎｄ ｗｅ：【ｇｈｔ ｉｎ ｓｃａｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ ｍａｔｒｉｃｅｓ ｔｈｒｏｕｇｈ ｒｅｇｕｌａｔｉｎｇ ｔｈｅ ｓｉｚｅ ｏｆ ｓｃａｌａｒ

ｃｏｍｐｏｎｅｎｔｓ ｔｏ ｍｅｅｔ ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｓｏｆｔｗａｒｅ ａｎｄ ｈａｒｄｗａｒｅ．Ｓｏ ｔｈｅ ｍｅｔｈｏｄｓ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ＭＤＳ ｍａｔｒｉｃｅｓ

ａｎｄ ｉｎｖｏｌｕｔｉｏｎ ＭＤＳ ｍａｔｒｉｃｅｓ ｈａｖｅ ｐｒａｃｔｉｃａｌ ｖａｌｕｅ．

Ｋｅｙ ｗｏｒｄｓ：ｂｌｏｃｋ ｃｉｐｈｅｒ；ｄｉｆｆｕｓｉｏｎ ｓｔｒｕｃｔｕｒｅ；ｂｒａｎｃｈ ｎｕｍｂｅｒ；ＭＤＳ（ｍａｘｉｍｕｍ ｄｉｓｔａｎｃｅ ｓｅｐａｒａｂｌｅ）ｍａｔｒｉｃｅｓ；Ｖａｎｄｅｒ—

ｍｏｎｄｅ ｍａｔｒｉｃｅｓ

０ 引言

混乱原则和扩散原则是保证分组密码安全性的两个基本

设计原则。在分组密码中，其扩散特性往往是通过特定的扩散

结构来实现的，扩散结构的设计非常重要，直接关系到分组密

码的安全性能和实现性能…。分支数理论是分组密码扩散结

构设计的一个重要理论，设计者可以根据分支数的大小从理论

上给出最大差分特征概率和最佳线性逼迫优势的界，从而保证

分组密码对差分密码分析和线性密码分析是实际安全的 。

以分支数尽可能大的线性变换为分组密码算法的扩散结构是

设计分组密码的一种重要方法，线性变换的构造可通过可逆矩

阵的构造完成。由于ＭＤＳ矩阵的分支数达到了最大，使得

ＭＤＳ矩阵在分组密码扩散结构的设计中得到广泛应用，如

ＡＥＳｌ４ Ｊ

、Ｋｈａｚａｄ＿５ 和Ｓｈａｒｋ等分组密码算法等。此外，为了保证

加脱密结构的一致性，ＭＤＳ矩阵最好是对合矩阵，因此，如何

构造对合型ＭＤＳ矩阵显得尤为重要。

常见的ＭＤＳ矩阵构造方法主要有三种：ａ）利用纠错码理

论，从ＭＤＳ码中提取ＭＤＳ矩阵，如ＡＥＳ、Ｋｈａｚａｄ、Ｓｈａｒｋ等分组

密码就是通过分组码理论来构造它们扩散层中使用的ＭＤＳ矩

阵。文献［６］给出了一种利用两个Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造

ＭＤＳ码的方法，但在其Ｖａｎｄｅｒｍｏｎｄｅ矩阵的定义下，文献中的

构造方法是有缺陷的；文献［７］给出了从线性分组码中搜索

ＭＤＳ矩阵的三种方法。ｂ）随机生成ＭＤＳ矩阵，如：文献［８］指

出可以从循环矩阵、Ｈａｄａｍａｒｄ矩阵以及Ｃａｕｃｈｙ矩阵中搜索便

于实现的ＭＤＳ矩阵；文献［９］通过限制条件在Ｃａｕｃｈｙ矩阵中

搜索出了１６ Ｘ １６的对合ＭＤＳ矩阵。Ｃ）利用数学方法构造

ＭＤＳ矩阵，如：文献［１０］利用代数方法，给出了一种构造对合

Ｃａｕｃｈｙ—Ｈａｄａｍａｒｄ型ＭＤＳ矩阵的方法；文献［１１］给出了利用两

个Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造对合ＭＤＳ矩阵。

一般来说，由于已知的ＭＤＳ码不多，并且利用方法ａ）构

造出的ＭＤＳ矩阵，其软、硬件实现性能未必能满足要求；利用

方法ｂ）构造出的ＭＤＳ矩阵，当矩阵的阶数和ｎ（矩阵中的元素

属于有限域ＧＦ（２ ））较大时，直接进行随机搜索显得不太现

实，此时，密码上一般在具有特定结构的矩阵中进行搜索，但是

当矩阵的阶数和ｎ较大时，直接搜索也变得异常困难；利用方

收稿日期：２０１３—０３．３０；修回日期：２０１３—０４．２８ 基金项目：国家自然科学基金资助项目（６１２７０４１）

作者简介：郭磊（１９８６：），男，甘肃兰州人，硕士，主要研究方向为密码学（ｇｌ２００６４４＠１６３．ＣＯＩｎ）；郑浩然（１９６８一），男，教授，博士，主要研究方向为

密码学、信息安全；傅增强（１９７９．），男，助理工程师，主要研究方向为信息安全；王月（１９８６－），男，硕士研究生，主要研究方向为密码学．

第１期 郭磊，等：ＭＤＳ矩阵和对合ＭＤＳ矩阵的新构造方法 ・２２３・

法ｃ）构造出的ＭＤＳ矩阵往往具有特定的数学结构，其软、硬

件实现性能也未必能满足要求。

本文对文献［６］中存在的问题进行了纠正，给出了正确的

利用两个Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵的方法；考虑到利

用该方法构造出的ＭＤＳ矩阵的软、硬件实现性能，对标量乘

Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵进行了研究，给出了由标量乘

Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵的充要条件；在文献［１１］给

出的构造对合ＭＤＳ矩阵方法的基础之上，给出了特征为２的

域上标量乘Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造对合ＭＤＳ矩阵的方法。

１ 基础知识

本文从矩阵角度来介绍差分分支数与线性分支数。

定义１［１２］ 设 ＝（ 一， ）∈ＧＦ（２ ） ，则称 －－，

中非零元的个数为ｘ的汉明重量，简称为重量，记为ｗ（ ）。

定义２ｌ１２ ３ 令０：ＧＦ（２ ） 一 （２ ） （ｘ）＝Ａ×ｘ是

一个变换，ｘ＝（ －－， ） ∈ＧＦ（２ ） ，矩阵Ａ＝（ａ ） ，

ａ ∈ＧＦ（２ ），则称

８（ ）＝ｍｉｎ｛ｗ（ｘ）＋ｗ（Ａ×ｘ）｝

ｘ＃Ｏ

为 的分支数。

定义３［１２］ 令０：ＧＦ（２ ） 一 （２ ） （ｘ）＝Ａ×ｘ是

一个变换，．）ｆ＝（ －．， ） ∈ＧＦ（２ ） ，＿）ｆ ＝（ ，…， ） Ｅ

ＧＦ（２ ） ，矩阵Ａ＝（ａ ） 一ａ∈ＧＦ（２ ），则称

Ｂ （ ）：ｍｉｎ｛ （ｘ①ｘ ）＋ （Ａ×ｘ① （Ａ ｘｘ ））｝

ｘ ≠

为Ａ的差分分支数。

定义４【ｉｚｌ 令０：ＧＦ（２ ） 一 （２ ） （ｘ）＝Ａ×ｘ是

一个变换，．）（＝（ ．．， ） ∈ＧＦ（２ ） ，ｐ＝（卢 一，卢ｍ） ∈ＧＦ

（２ ） ，矩阵Ａ＝（ａ ） ，ａ ＧＦ（２ ），则称

Ｂｆ（Ａ）＝ｍｉｎ｛ｗ（ｐ）＋ （Ａ ｘｐ）｝，

ｂ Ｕ

为Ａ的线性分支数（Ａ 表示矩阵Ａ的转置矩阵）。

对任意矩阵Ａ，由于Ａｘａ①Ａ ｘｂ＝Ａ ｘ（ａ①ｂ），因此差分

分支数与分支数是一致的，而线性分支数与分支数不一定相等。

但对于ＭＤＳ矩阵来讲，其差分分支数与线性分支数是相等的。

由于密码学中应用的ＭＤＳ矩阵与分组码理论中的ＭＤＳ

码是相对应的，因此本文简要介绍有关分组码的基础知识：有

限域ＧＦ（ｑ）上的一个［ｎ，ｋ，ｄ］一线性码是向量空间ＧＦ（ｑ） 一

个ｋ维子空间，两个ｎ维向量的最小汉明距离即两个码字的最

小汉明距离为ｄ。一个［ｎ，ｋ，ｄ］一线性码Ｃ的生成矩阵Ｇ是一

个由Ｃ的一组基作为矩阵的行而形成的一个 ×ｎ矩阵。若一

个［ｎ，ｋ，ｄ］一线性码的生成矩阵Ｇ＝［ Ｉ Ａ］，其中， 为

ｋ× 的单位矩阵， 是一ｋ ｘ（ｎ—ｋ）矩阵，那么生成矩阵Ｇ称

为［ｎ，ｋ，ｄ］一线性码的标准生成矩阵。［ｎ，ｋ，ｄ］一线性码遵循

Ｓｉｎｇｌｅｔｏｎ界，ｄ≤ｎ—ｋ＋１，本文把ｄ＝ｎ—ｋ＋１的［ｎ，ｋ，ｄ］一线性

码称为极大最小距离可分码（ｍａｘｉｍｕｍ ｄｉｓｔａｎｃｅ ｓｅｐａｒａｂｌｅ

ｃｏｄｅｓ，ＭＤＳ） 。分组密码设计中应用的ＭＤＳ矩阵即为ＭＤＳ

码的标准生成矩阵Ｇ＝［ ＩＡ］中的矩阵Ａ，一般取ｎ＝２ｋ，因

此有关ＭＤＳ码的相关结论直接应用到ＭＤＳ矩阵的证明中。

引理１“ 设Ａ为有限域ＧＦ（ｑ）上的ｎ阶方阵，以下三个

条件是等价的：ａ）Ａ是ＭＤＳ矩阵Ｉｂ）矩阵［ ＩＡ］中任意的ｎ列

是线性无关的；ｃ）矩阵［一Ａ ＩＥ］中任意的ｎ列是线性无关的。

引理２ １３］有限域ＧＦ（ｑ）上的ｎ阶方阵Ａ是ＭＤＳ矩阵的

充要条件是矩阵月的任意阶子方阵都是非奇异的。

定义５ １３］设ａ ∈ＧＦ（ｑ），ｉ＝１，…，ｍ，ｑ为素数或素数的

方幂，则由ＣＦ（ｑ） 中的向量（ａ 一，ａ ）决定的Ｖａｎｄｅｒｍｏｎｄｅ

方阵

ｆ １ １ … １ １

。 一，。 ）：（ 一－） ： ＝１ … 。 Ｉ。

【ｎ 一 ｎ 一 … ｎ：一 Ｊ

ＶａｎｄｅＦｉｎ。ｎｄｅ方阵的ｚ…－１０式ｄｅｔ（ （口 。。，。 ））

（ａｊ—ａ ），其中ｍ≥２。

若可逆矩阵

显然矩阵

Ｂ＝（ ）ｍ ：ｌ＝

ｂｌ ・

ｂ２ ・

：

●

ｂ ・

中存在奇异的ｍ阶子方阵，如其前ｍ一１列和第ｍ＋１构成的

ｍ阶子方阵

ａ１ ‘‘

ａ２ ‘

●

：

口ｍ 一

就是奇异的。那么矩阵Ａ （Ａｌ Ｂ）＝（Ｅｌ Ａ Ｂ）中存在奇异

的ｍ阶子方阵，根据引理１知矩阵Ａ Ｂ非ＭＤＳ矩阵，进而根

据引理２知矩阵Ａ Ｂ中存在奇异的子方阵。而文献［６］中的

Ｖａｎｄｅｒｍｏｎｄｅ矩阵的定义即为

Ｖ（。 一，０ ）＝（ ） ｍＪ：１＝

０ｌ 。。

ａ２ ’

●

：

０ｍ 一

这种形式，因此文献［６］中的定理１、２是有问题的。

定理１［６ Ｊ 记Ｖ（ａｌ，…，ａ ）为Ｖａｎｄｅｒｍｏｎｄｅ矩阵

（ ）ｍ ： ，则对（Ｆｑ） 上的任意两个向量（。。，…，ｏ，）和

（ｂ 一，ｂ，），若ａ ，ｂｊ是２ｒ个互不相同的元，那么矩阵

ａ 一，ａ ） ｂ 一，ｂ ）

中的任意一个子方阵都是非奇异的。

定理２ 记 ａ －．， ）为 ×ｋ的非奇异Ｖａｎｄｅｒｍｏｎｄｅ

矩阵， ｂ 一，ｂ 一 ）为ｋ ｘ（ｎ—ｋ）矩阵（ ） ： 一 ，则由生

成矩阵Ｇ＝［Ｅ Ｉ ｏ 一 ）＾１ （ｂ 一，ｂ 一 ）］定义的码为ＭＤＳ

码的充要条件为ａ ．是ｎ个互不相同的元。

２ 由Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵

下面给出正确的由两个Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵

的充要条件：

定理３设有限域ＧＦ（ｑ）上的Ｖａｎｄｅｒｍｏｎｄｅ方阵

ｏ 一，ｎ ）＝（ｎ； ）０： ， ｂ 一，ｂ ）＝（ ） 。，则矩阵

。 一，ｏ ） ｂ 一，ｂ ）是ＭＤＳ矩阵的充要条件是。 ，６

为ＧＦ（ ）中２ｍ互不相同的元。

证明必要性。证明若ＧＦ（ｑ）上的矩阵Ｖ（ａ 一，ａ ）Ｉ１

一 一 一 ＿ 一 一 ；

以 眈

、●●●●●●ｒｆｔ●●●●●●●Ｊ

一 一

．．．

＿ ＂

一 一 一

；

吼

；．．１

，，

≈

一 一 一

；

・２２４・ 计算机应用研究 第３１卷

ｂ 一，ｂ ）是ＭＤＳ矩阵，那么Ⅱ 、ｂｊ为ＧＦ（ｑ）中２ｍ互不相

同的元。

根据引理１可知，若 ａ 一，ａ ） Ｖ（ｂ 一，ｂ ）是ＭＤＳ

矩阵，那么矩阵【Ｅｌ ａ 一，。 ） ｂ 一，ｂ ）］中任意的ｍ

阶子方阵是非奇异的，而矩阵

ａｌ，…，ａ ）［ＥＩ ａ 一，ａ ） ｂ１，…，ｂ ））＝

［ ａ１，…，ａ ）ｌ （ｂ 一，ｂ ）］

因此矩阵［ ａ 一，。 ）Ｉ ｂ 一，ｂ ）］中任意的ｍ阶子方阵

也是非奇异的，而矩阵［Ｖ（ａ －－，ａ ）ｌ Ｖ（ｂ 一，ｂ ）］中任意

的ｍ阶子方阵正好也是一个Ｖａｎｄｅｒｍｏｎｄｅ方阵，由Ｖａｎｄｅｒ—

ｍｏｎｄｅ方阵的行列式知Ｖａｎｄｅｒｍｏｎｄｅ方阵的行列式不等于零

当且仅当Ｖａｎｄｅｒｍｏｎｄｅ方阵的生成向量中的元互不相等，因此

ａ 、６

，为ＧＦ（ｑ）中２ｍ互不相同的元。

充分性。即证明若。 、ｂｊ为ＧＦ（ｑ）中２ｍ互不相同的元，

那么矩阵 ａ －－，ａ ） ｂ 一，ｂ ）是ＭＤＳ矩阵。

显然矩阵［ ａ －－，ａ ）ｌ ｂ ，…，ｂ ）］中任意的ｍ阶子

方阵仍为一个Ｖａｎｄｅｒｍｏｎｄｅ方阵，由ａ 、ｂ 为ＧＦ（ｑ）中２ｍ互不

相同的元知［ 。 一，ｎ ）ｌ Ｉ／（ｂ －－，ｂ ）］中任意的ｍ阶子方

阵都是非奇异，则矩阵

ａ 一，ａ ） ［ ａｌ，…，ａ ）Ｉ ｂｌ，…，ｂ ）］＝

［Ｅｌ ｎ 一，ａ ） ｂ 一，ｂ ）］

中任意的ｍ阶子方阵也是非奇异的，根据引理１知矩阵 ａ。，

…

，ａ ） ｂ 一，ｂ ）为ＭＤＳ矩阵。证毕。

由定理ｌ和文献［６］中的定理２知：

若ＧＦ（ｇ）上的矩阵 ｏ ．－，ｎ ）＝（ｏｊ ） ｍ ，Ｖ（ｂ 一，

ｂ ）＝（ ） ｍ 。，则矩阵 。 一，。 ） ｂ 一，ｂ ）为ＭＤＳ

矩阵充要条件是ａ 、６ 为ＧＦ（ｑ）中２ｍ互不相同的元；

若ＧＦ（ｑ）上的矩阵 ｏ。，…，ｏ ）：（ ）ｍ ．川，

Ｖ（ｂ ，…，

ｂ ）＝（ ） ，则矩阵Ｖ（。 一，０ ）Ｖ（ｂ 一，ｂ ） 为ＭＤＳ

矩阵充要条件是。 、ｂｊ为ＧＦ（ｑ）中２ｍ互不相同的元。

３ 标量乘Ｖａｎｄｅｒｍ ｏｎｄｅ矩阵构造ＭＤＳ矩阵

在有限域ＧＦ（ｑ）上，记

ｆ ｏＬ１ａＩ，ｌ… ａ１， １ ４‘ ｔ ｍ ｌ ． ， … ， ｊ

为标量（ 一，ｏｔ ）乘矩阵

ｆ ａ１，１… １ Ａ

＝（ｎ ）ｍ［１Ｊ：１＝Ｉ： ｌ

【ａｍ，１…。 ， Ｊ

的标量乘矩阵，记

ｆ ａｌ。ｌＩ１…０／１ ０，ｌ，ｍ １

Ａ（ ， ：ｌ ： ｆ

Ｉ 。 ，， … 。 ， ｊ

为了研究标量乘Ｖａｎｄｅｒｍｏｎｄｅ方阵构造ＭＤＳ矩阵的方法，下

面首先分别由定理１给出标量乘矩阵逆的结构特点，由定理２给

出两个矩阵相乘与它们的标量乘矩阵相乘的关系，再由定理４给

出由两个标量乘Ｖａｎｄｅｒｍｏｎｄｅ方阵构造ＭＤＳ的充要条件。

定理４（Ａ‘ … ）～：（Ａ一 ）‘“ｒ ， 。

证明设Ａ。。＝Ｔ＝（ｔ ） ｍ： ，由

ｆ ｌ’１…ｔｉ， １ｆ ０１．１…ａＩ． １

Ａ Ａ＝【 ； ｌｌ； ； ｌ＝Ｅ

ｌ ｔｍ，１ 。一ｔｍ，ｍ Ｊｌ ａｍ，１ … ａｍ，ｍ Ｊ

［ ’ ：：： 。１ ｔｌ，ｍ ］ｊ（１ Ｏｔｌ ａ ｌ， ：：：： 二］＝Ｅ

＝

ａｌ

，

Ｅ

ａ １ ａ ｔ １ ｔ

ＡＡ～＝ ｌｌ；

，

…

ｍ，ｍ Ｊｌ ｍ， ‘一 ， Ｊ

＿ ｍａｍ，ｍ Ｏｔｍｌｔ ｍ ，篓

ｆ Ｉ’】… １

ｌ ａ ￡ …ｎ ￡ ． 』

定理５若Ａ＝（ａｉ

，ｊ

） ： ，Ｂ＝（ｂｉ

，

ｊ） ｍ。，则

证明设Ａ～：Ｔ：（ｔ ） ： ，则由定理１知

矩阵（Ａ一’）‘ ，一 Ｂ‘Ｂ１．“ 中第ｉ行第 列的元为主

ａ －１ｔ ６

Ｊ。

显然肖－１ Ｂ中第ｉ行第 列的元为 ｍ ｂ ，那么（（肖Ｉ１

８）‘ ｒ ・， ）‘ｐ１，＇ｐｍ’中第 行第 列的元为 ｉ’￣Ｊ

ｋ ＝ｌ

６ ，

这与矩阵（ 一 （ａｌ－ｌ，．．．，ａｎ７Ｉ）Ｔ Ｂ‘ ｍ 中第ｉ行第 列的元砉

１ｔ

，

６

，

相等，即与（Ａ‘ ） Ｂ‘ 第ｉ行第 列的

元 －１￡ 岛６ 相等，由 、 的任意性知（４‘ 。。 ）

Ｂ‘ ， ＝（（Ａ一 Ｂ）‘叮 ，， ）‘ ”ｔ 。证毕。

。 ）＝（ ） ：。， （ｂ ，…，ｂ ）＝（ Ｉ１） ｍ：。，贝０矩阵（ （ｎ。，・－－，

ｎ 、６，为ＧＦ（ｑ）中２ｍ互不相同的元且ｏ／ 都为非零元。

证明根据引理２知矩阵（Ｖ（０ ，…，ａ ）（ａｌ＇＇ ） Ｖ

（ｂ 一，ｂ ） ’， 是ＭＤＳ矩阵的充要条件是其任意阶子方

（（ 。Ｉ，…， ｍ）一 （６ｌ，…，ｂｍ））‘ 广 ， ， Ｔ）‘ ｌ， ， ｍ

为了证明方便不妨记矩阵Ｖ（Ⅱ 一，ａ ） Ｖ（ｂ 一，ｂ ）

中任意的ｋ阶子方阵为了－＝（￡ ）

，

，那么矩阵（ （。 一，

。 ）‘ … ） ｂ 一，ｂ ）‘ ，ｔ ｍ’中任意的ｋ阶子式即为

ｌ

ｔｉｌ ｌ ｏ￣ｉ－

］ 岛２ｔｉ１，，２…（ｘｉ－￣ 岛 ｔｉｌ，¨Ｊ

１ ａ １￡ 』ｌ ａ ￡ ２ …ａ 岛 ｆ ２ｍ ５

； ｌ

￡

ｌ

￡ 也 … ａ －。

ｋ ｆ‰“ ｊ

第１期 郭磊，等：ＭＤＳ矩阵和对合ＭＤＳ矩阵的新构造方法 ・２２５・

而

根据行列式的性质知

ａ 岛ｌｔ １Ｊ１ 【１Ｉ圯 … ｄ 。 ｆｆ１Ｊ

ｌ

。

１

ｔ ２Ｊｌ ｏｔｌ２ ￡ｆ２

，

』２…ｄ ｔ ２

，ｎ

ｉ ；

ｄ ‘咄Ｊｌ Ｉ￣ｊ２ｔ 以…Ｏｔｉ—ｋ。 ｆ

¨

Ｏ／ｉｉ … ｔ ８ｎ。－‘Ｂ｜ｋ

Ｏｔｉ

、

… ｔ 、９ｎ…ｐｉｋ

ｔｉｌＪ１

ｔｉ２Ｊｌ

：

●

ｔｉ Ｊ１

ｔｉ１√ｌ

ｔ‘２Ｊｌ

：

●

ｆ √１

当且仅当 是非零元 ，ｌ＝１，…， ，且

根据引理２知

ｔｉｌ

，』１

２ ｌ

●

：

ｔｉｋ

，ｊｌ

ｔｉｌＪ１

ｔｉ２

，ｊ１

●

：

ｔｉ Ｊｌ

≠０

≠０

≠０

当且仅当 ａ 一，ａ ） ｂ 一，ｂ ）是ＭＤＳ矩阵，再根据定理１

知矩阵 ａ “，ａ ） ｂ 一，ｂ ）是ＭＤＳ矩阵的充要条件为

ａ 、 为ＧＦ（ｑ）中２ 互不相同的元。因此（Ｖ（ａ。，…，

ａ ）‘ … ） ｂ －．，ｂ ）‘ ， ｍ 是ＭＤＳ矩阵的充要条件是

，

为ＧＦ（ｑ）中２ｍ互不相同的元且 、 都为非零元。证毕。

４ 标量乘Ｖａｎｄｅｒｍ ｏｎｄｅ矩阵构造对合ＭＤＳ矩阵

本章在文献［１１］给出的由两个Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造对

合ＭＤＳ矩阵方法的基础之上，给出有限域ＧＦ（２ ）上由两个标

量乘Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造对合ＭＤＳ矩阵的方法。

引理３［ｉｉ 设有限域ＧＦ（２ ）上的Ｖａｎｄｅｒｍｏｎｄｅ方阵

。 一，口 ）＝（ｎ； ）【’Ｊｍ：ｌ， ｂ 一，ｂ ）＝（ ）ｆ．ｍ

若ｂ ＝ａ ＋△，则矩阵Ｖ（ａ 一，ａ ） Ｖ（ｂ 一，ｂ ）为对合矩

阵。

引理４ ｕｌ设有限域 （２ ）上的Ｖａｎｄｅｒｍｏｎｄｅ方阵

。 一，ｎ ）：（Ⅱ； ） ｍ：ｌ， ｂ ．－，ｂ ）＝（ ）Ⅵｍ：ｌ

若ｂ ＝０ ＋△，且０ ，ｂｊ为ｃＦ（２ ）中２ｍ互不相同的元，则矩阵

ａ 一，ａ ） ｂ 一，ｂ ）为对合ＭＤＳ矩阵。

定理７设有限域ＧＦ（２ ）上的Ｖａｎｄｅｒｍｏｎｄｅ方阵

ａ１，…，ａ ）＝（ ） ｍ １， ｂｌ，…，ｂ ）＝（６ｊ ） ｍ ｌ，（Ｏｔ１，

…

， ）∈ＧＦ（２ ） ，若ｂ ＝ａ ＋△且ａ ，６ 为 （２“）中２ｍ互

不相同的元，ｏｔ ≠０，则矩阵（Ｖ（ａ ，…，ａ ） －・… ｍ ） Ｖ（ｂ ，

…

，ｂ ） … 为对合ＭＤＳ矩阵。

证明 根据定理６知矩阵（Ａ ・’… ） ８ －’“ ｍ’为ＭＤＳ

矩阵，下面证明其对合性质。

根据引理３知 ａ ．－，ａ ） ｂ 一，ｂ ）为对合矩阵，

不妨设 。 一，ｎ ） ｂ 一，ｂ ）：Ｔ＝（ｔｌ

，

ｊ） ｍ：ｌ，则

（ ａ１，…，ａ ） １’’ ｍ ）Ｉ１ ｂ１，…，ｂ ） ’’ ｍ ＝

（（ 口Ｉ，…，口ｍ）一 ｖ（ｂＩ，－一，ｂ ））‘ａｒ ，…，ａ ）Ｔ）（。ｌ，…， ｍ）＝

（ａ ａｊｔｌ，ｊ） ｍ ：１，

那么矩阵（ｅｌｉ－ ａｊｔ ） ： 的第ｉ行乘第 列后得到的元为

ｍ

～

＝

ｍ

ｌ

ｔｉ

，

ｋｔｋ

，

ｊ＝｛

因此矩阵（ 口 ”，ａｍ）‘ “，“ｍ ） ｂ 一，ｂ ）‘ …， 为对

合矩阵。

综上所述，若ｂ ＝ａ ＋△且ａ 、ｂｊ为ＧＦ（２ ）中２ｍ互不相

同的元， ≠０，则矩阵（Ｖ（。 ”，。 ） … ）Ｉ１ Ｖ（ｂ 一，

ｂ ） ，’’ ’为对合ＭＤＳ矩阵。证毕。

５ 结束语

本文对Ｌａｃａｎ等人给出的由Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ

码的方法进行了研究，指出了其中存在的问题，给出了由两个

Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵的充要条件。进而对标量乘

Ｖａｎｄｅｒｍｏｎｄｅ矩阵的结构特点进行了研究，给出了由标量乘

Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造ＭＤＳ矩阵的充要条件。最后在Ｓａｊａｄｉｅｈ

等人给出的由两个Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造对合ＭＤＳ矩阵方法

的基础之上，给出了标量乘Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造对合ＭＤＳ

矩阵的方法。对由标量乘Ｖａｎｄｅｒｍｏｎｄｅ矩阵构造的ＭＤＳ矩阵

及对合ＭＤＳ矩阵来讲，可以通过调控标量中分量的大小来调

整构造出来的ＭＤＳ矩阵及对合ＭＤＳ矩阵元素大小和元素重

量大小来满足其软、硬件实现性能，因此本文给出的构造ＭＤＳ

矩阵及对合ＭＤＳ矩阵的方法具有实用价值。

参考文献：

［１］ＤＡＥＭＥＮ Ｊ，ＲＵＭＥＮ Ｖ．１１Ｉ１ｅ ｗｉｄｅ ｔｒａｉｌ ｄｅｓｉｇｎ ｓｔｒａｔｅｇｙ［Ｃ］／／Ｐｒｏｃ ｏｆ

ｔｈｅ ８ｔｈ ＩＡＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ Ｃｉｒｅｎｃｅｓｔｅｒ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—

Ｖｅｒｌａｇ，２ｏｏｌ：２２２－２３８．

［２］ＲＩＪＭＥＮ Ｖ，ＤＡＥＭＥＮ Ｊ，ＰＲＥＮＥＥＬ Ｂ，ｅｔ ａ１．Ｔｈｅ ｃｉｐｈｅｒ ＳＨＡＲＫ

［Ｃ］／／Ｐｒｏｃ ｏｆ Ｆａｓｔ Ｓｏｆｔｗａｒｅ Ｅｎｅｒｙｐｔｉｏｎ・ＦＳＥ．［ｓ．１．］：Ｓｐｒｉｎｇｅｒ－Ｖｅｒ－

ｌａｇ，１９９６：９９－ｌ１１．

［３］Ｊｕ ｓ Ｋ，ＳＥＯＫＨＩＥ Ｈ，ＳＡＮＧＪＩＮ Ｌ，ｅｔ ａ１．Ｐｒａｃｔｉｃａｌ ａｎｄ ｐｒｏ．￣ａｂｌｅ ｓｅ．

ｃｕｒｉｔｙ ａｇａｉｎｓｔ ｄｉｆｆｅｒｅｎｔｉａｌ ａｎｄ ｌｉｎｅａｒ ｅｒｙｐｔａｎａｌｙｓｉｓ ｆｏｒ ｓｕｂｓｔｉｔｕｔｉｏｎ．ｐｅｒ－

ｍｕｔａｔｉｏｎ ｎｅｔｗｏｒｋｓ［Ｊ］．ＥＴＲｌ Ｊｏｕｍａｌ，２００１，２３（４）：１５８．１６７．

［４］ＤＡＥＭＥＮ Ｊ，ＲＩＪＭＥＮ Ｖ．Ｔｈｅ ｄｅｓｉｇｎ ｏｆ Ｒｉｊｎｄａｅｌ：ＡＥＳ—ｔｈｅ ａｄｖａｎｃｅｄ

ｅｎｅｒｙｐｔｉｏｎ ｓｔａｎｄａｒｄ［Ｍ］．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００２．

［５］ ＢＡＲＲＥＴＯ Ｐ，。ＲＵＭＥＮ Ｖ．Ｔｈｅ Ｋｈａｚａｄ ｌｅｇａｃｙ—ｌｅｖｅｌ ｂｌｏｃｋ ｃｉｐｈｅｒ

［ＥＢ／ＯＬ］．（２０００）［２００６－１２－０３］．ｈｔｔｐ：／／ｗｗｗ．ｃｒｙｐｔｏｎｅｓｓｉｅ．０强

［６］ ＪＥＲＯＭＥ Ｌ，ＪＥＲＯＭＥ Ｆ．Ｓｙｓｔｅｍａｔｉｃ ＭＤＳ ｅｒａｓｕｒｅ ｃｏｄｅｓ ｂａｓｅｄ ｏｎ

ｖａｎｄｅｒｍｏｎｄｅ ｍａｔｒｉｃｅｓ［Ｊ］．ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｌｅｔｔｅｒｓ，２００４，

８（９）：５７０－５７２．

［７］ＭＡＴＨＵＲ Ｃ—Ｎ，ＮＡＲＡＹＮＡ Ｋ，ＳＵＢＢＡＬＡＫＳＨＭＩ Ｋ Ｐ．Ｈｉｇｈ ｄｉｆｕｓｉｏｎ

ｃｉｐｈｅｒ：ｅｎｃｒｙｐｔｉｏｎ ａｎｄ ｅｒｒｏｒ ｃｏｒｒｅｃｔｉｏｎ ｉｎ ａ ｓｉｎｇｌｅ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｐｎ‘ｍｉ－

ｔｉｖｅ［Ｃ］／／ＬＮＣＳ，ｖｏｌ ３９８９．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００６：３０９—３２４．

［８］ＸＩＡＯ Ｌ，ＨＥＹＳ Ｈ Ｍ．Ｈａｒｄｗａｒｅ ｄｅｓｉｇｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆｂｌｏｃｋ ｃｉｐｈｅｒ ｃｏｍ－

ｐｏｎｅｎｔｓ１ Ｃｌ／／Ｐｒｏｃ ｏｆｔｈｅ ５ｔｈＩｎｔｅｍａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎＩｎｆｏｒｍａｔｉｏｎ Ｓｅ－

ｃｕｆｆｔｙ ａｎｄ Ｃｒｙｐｔｏｌｏｇｙ－ＩＣＩＳＣ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２０Ｏ３：１６４・１８１．

［９］ＪＯＲＧＥ Ｎ Ｊ，６ＬＣＩＯ Ａ．Ａ ｎｅｗ ｉｎｖｏｌｕｔｏｒｙ ＭＤＳ ｍａｔｒｉｘ ｆｏｒ ｔｈｅ ＡＥＳ『Ｊ］．

Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｎｅｔ Ｗｏｒｋ Ｓｅｃｕｒｉｔｙ，２００９．９（２）：１０９－１１６．

［１Ｏ］崔霆，金展辉．对合Ｃａｕｃｈｙ＇Ｈａｄａｍａｒｄ型ＭＤＳ矩阵的构造［Ｊ］．电

子与信息学报，２０１０，３２（２）：５００－５０３．

【ｌ１ Ｊ ＳＡＪＡＤＩＥＨ Ｍ，ＤＡＫＨＩＬＡｕＡＮ Ｍ，ＭＡＬＡ Ｈ．ｅｔ ａ１．Ｏｎ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ

ｉｎｖｏｌｕｔｏｒｙ ＭＤＳ ｍａｔｒｉｃｅｓ ｆｒｏｍ Ｖａｎｄｅｒｍｏｎｄｅ Ｍａｔｒｉｃｅｓ ｉｎ ＣＦ（２ｑ）［Ｊ］．

Ｄｅｓｉｇｎｓ，Ｃｏｄｅｓ ａｎｄ Ｃｒｙｐｔｏｇｒａｐｈｙ，２０１２，６４（３）：２８７—３０８．

［１２］昊文玲，冯登国，张文涛．分组密码的设计与分析［Ｍ］．２版．北

京：清华大学出版社．２００９．

［１３］ＭｃｗＩＬＬＩＡＭＳ Ｆ Ｊ，ＳＬＯＡＮＥ Ｎ Ｊ Ａ．Ｔｈｅ ｔｈｅｏｒｙ ｏｆ ｅｒｒｏｒ—ｃｏｒｒｅｃｔｉｎｇ

ｃｏｄｅｓｌ Ｍ １．Ｔｈｅ Ｎｅｔｈｅｒｌａｎｄｓ：Ｎｏｒｔｈ Ｈｏｌｌａｎｄ，１９７７．

：

：

￡

：

：

儿

￡ ｔ ￡

三＝

；

圯 彪

；