加密解密中变形魔方阵的应用

近年来，人们对魔方阵的探讨，不再局限于趣味数学上的议题，不少学者纷纷将魔方阵的应用融入信息安全之中。那么我们今天就来探讨一下加密解密中变形魔方阵是如何应用的？

一、魔方阵变形之分析

1、魔方阵的由来

根据文献记载，最古老的魔方阵是一个三阶魔方阵，出自中国古代的洛书，相传大禹在黄河及洛水治理水患时，于洛河发现一只乌龟背上刻着奇特图案，即一个标准的三阶魔方阵。魔方阵又被称为九宫算，是因为三阶魔方阵共有九个方格，又被称为纵横图的原因可能是直行与横列的和相等的缘故。在日本，魔方阵又称为幻方。

2、魔方阵的定义

若一个方阵是由n横列与n个直行所构成，共有扩个小方格，则称这个方阵是一个n阶方阵；若每一列，每一行及每一个对角线数字相加的总合相等，则称为正规魔方阵（Normal MagicSquare），或是标准魔方阵(Standard Magic Square)。检验一个魔方阵是否为一个正规型态，可判定任一列、一行或是对角线之和是否为(n的三次方+n)/2，其中n为魔方阵的阶数。

例如：以3阶魔方阵为例，其每一列之和为15。

3、魔方阵的变形

常见的魔方阵变形有几种：刚性变形法、加值变形法、互补变形法、井字对换变形法、田字变形法、拓朴变形法及、旋转变形法等多种方法嘲o对于奇数或是偶数的魔方阵变形，又有不同的方法；本文以合成法举例说明9*9阶及12*12阶魔方阵之构造方法。

（1）奇数九阶魔方阵合成法

九阶魔方阵可以分解成数个三阶魔方阵。一个阶数为n之魔方阵，当n≥3时，若n为两个整数p，q之乘积时，则这个魔方阵可由p阶及g阶魔方阵合成。例如九阶魔方阵可以分解成三阶魔方阵。

3*3型态合成法

步骤1：将9*9的矩阵平均切割成三等份，总共分成9大区块。这里称之为井字型切割法。

步骤2：将9大区块分别按照3*3魔方阵的区块位置标上l到9的顺序编号。

步骤3：9*9共有81个小方格，第一区块依顺序将1-9数字对应3*3魔方阵的相对位置，填入小方格内。

步骤4：反复步骤3的工作，直到81个小方格全部填满数字。

步骤5：检查各行各列及对角线的数字总和是否相等，若相等就结束工作；不相等则跳至步骤3重新开始。

（2）偶数十二阶魔方阵合成法

几阶为12的魔方阵可以分解成n=4*3或是n=3*4两种型态，即每一个基本方块可以切割成三等份或是四等份。如图4及图5所示。

4*3型态合成法

步骤1：将12*12的矩阵平均切割成四等份，总共分成16大区块。

步骤2：将16大区块分别按照4*4魔方阵的区块位置标上1到16的顺序编号。

步骤3：12*12共有144个小方格，第一区块依顺序将1-16数字对应4*4魔方阵的相对位置，填入小方格内。

步骤4：反复步骤3的工作，直到144个小方格全部填满数字。

步骤5：检查各行各列及对角线的数字总和是否相等，若相等就结束工作；不相等则跳至步骤3重新开始。

3*4型态合成法

步骤1：将12*12的矩阵平均切割成三等份，总共分成9大区块。还是用井字型切割法。

步骤2：将9大区块分别按照3*3魔方阵的区块位置标上1到9的顺序编号。

步骤3：12*12共有144个小方格，第一区块依顺序将1-9数字对应3*3魔方阵的相对位置，填入小方格内。

步骤4：反复步骤3的工作，直到144个小方格全部填满数字。

步骤5：检查各行各列及对角线的数字总和是否相等，若相等就结束工作；不相等则跳至步骤3重新开始。

（3）合成法注意事项

已知最小魔方阵为一个三阶魔方阵，因此若用合成法或是切割法来构造一个9阶以上的魔方阵，最小的要求是三阶。为什么不用二阶？因为二阶魔方阵不存在。

假设：设有一个二阶魔方阵，如图6所示，其中a，b，c，d依序为不相同的正整数。

证明：假设图6为一个二阶魔方阵，所以a+b=b+d=a+c=b+d=a+d=b+c。

得a=b=c=d，然魔方阵之假设为a≠b≠c≠d之条件，故图6与假设矛盾。

所以二阶魔方阵不存在。

证毕。

二、加密解密原理及其认证机制

1、魔方阵的特性一“大于1法则”

三阶魔方阵特性：以3*3为例，两个对角的和分别是(8+2)=10，(6+4)=10；因3*3=9，而10比9大1。

四阶魔方阵特性：以4*4为例，两个对角的和分别是(16+1)=17，(13+4)=17；因4*4=16，而17比16大1。

五阶魔方阵特性：以5*5为例，两个对角的和分别是(17+9)=26，因(15+11)=26，而26比25大1。

六阶魔方阵特性：以6*6为例，两个对角的和分别是(6+31)=37，(1+36)=37；因6*6，而37比36大1。

七阶魔方阵特性：以7*7为例，两个对角的和分别是(30+20)=50，(28+22)-50;因7*7，而50比49大1。

八阶魔方阵特性：以8*8为例，两个对角的和分别是(64+1)=65，(57+8)=64；因8*8=64，而65比64大1。

2、用魔方阵的特性当验证机制

当传送者( Sender)将明文(plaintext)加密之后，他最少要传密文(ciphertext)及密钥(key)这两样信息给接收者( Receiver)，接收者根据密钥（或密码）将密文解密成明文。这是最基本的情况。如果加密密钥与解密密钥是一样的，属于对称式密码系统；如果不一样，则是非对称式密码系统。如果要让接收者对传送者进行身份的认证及鉴别，传送者至少还要提供明文、密钥及密文等三种信息给对方，接收者可以把密文解密后，与原来的明文比对看看是否一致。

如果传送者在一般的网络上传送密文给接收者，另外在安全信道(Secure Channel)或是虚拟网（Virtual Private Network，VPN）上传送种子(seed)给接收者，这个种子就是魔方阵阶的大小及四个角落的值，当接收者收到传送者所传送的密文及种子时，接收者可以自行产生一个魔方阵；此时，产生的这个魔方阵就是一个加密矩阵，利用这个矩阵把密文进行解密，就会得到明文。

例如：传送者经由安全信道传送种子为(7，30，28,22，20)及密文给接收者时，接收者收到后，接收者知道要产生7*7的魔方阵，且四个角落值一定是(30，28，22，20)，若不是，接收者就无法正确的将密文解密成明文。

3、安全性分析

一个3*3魔方阵只有1种，4*4魔方阵有880种，5*5魔方阵有275305224种，6*6魔方阵约1.775399- 109种组合，而10*10则约有2.4149·10110种组合。这样排列与组合的证明已经有专家及学者证明出来了。

开放性问题：我们现在有下列开放性问题需要探讨及研究。

1．大于一的法则，显然只是对大多数的魔方阵适用，到底有多少个例外的魔方阵不适用于此法则，目前没有论述。

2．如何快速产生一个奇数的魔方阵，已有文献探讨，而快速地产生偶数的魔方阵，现有文献甚少提及。

3．魔方阵是否有更广泛的应用，应用在哪里，仍是一个尚待研究的议题。

将魔方阵应用于加密解密，为分组密码提供一个新的研究思维。另一方面，现在密码体制中，传送者仍然免不了需要将明文密文对提供给接收者，以利接收者对传送者身份的识别。本文的方法，传送者无需传送明文，大大地节省传输过程所消耗的资源，也避免攻击者利用明文攻击。传送者只需传送微量的信息（例如种子参数）给接收者，接收者可自行产生解密矩阵，在传输过程并没有密钥，因此密钥不会有泄漏的疑虑。