第３８卷第１期２００８年１月
东南大学学报（自然科学版）
ＪＯＵＲＮＡＬＯＦ
ＳＯＵＴＨＥＡＳＴ
ＶｏＬ３８
Ｅｄｉｔｉｏｎ）
Ｎｏ．１
ＵＮＩＶＥＲＳＩＴＹ（Ｎａｎｎ＿ａｌ
Ｓｃｉｅｎｃｅ
Ｊａｎ．２００８
置换密钥矩阵加密算法的改进
叶峰
袁家斌
（南京航空航天大学信息科学与技术学院，南京２１００１６）
摘要：提出了对分组加密算法（ＲＫＭ）的改进，主要包括密钥进化算法、特征因子子矩阵和密钥
的分发与更新算法．密钥进化算法是特征因子子矩阵生成算法和密钥分发与更新算法的基本组
件，由一个１６字节的单字节数组（称为进化指针）和一个密钥矩阵计算一个新的密钥矩阵．特征因子子矩阵是把１２８ｂｉｔ矩阵特征因子作为进化指针代入密钥进化算法计算而得．在引入特征因子子矩阵的基础上对算法流程进行了改进，使算法的加、解密完全对称．在不降低算法安全性的基础上减少了４轮异或运算，从而降低了运算量．在密钥进化算法的基础上设计了密钥的分发与更新算法，使算法无需每次传输密钥矩阵就能共享．
关键词：加密算法；置换密钥矩阵；密钥进化算法；特征因子子矩阵
中圈分类号：ＴＰ３０９．７
文献标识码：Ａ
文章编号：１００１—０５０５（２００８）０１．００１１－０５
Ｅｎｈａｎｃｅｍｅｎｔｏｆｒｅｐｌａｃｉｎｇｋｅｙｍａｔｒｉｘｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍ
ＹｅＦｅｎｇ
ＹｕａｎＪｉａｂｉｎ
ｏｆ
（ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＮａａｊｉｎｇＵｎｉｖｅｒｓｉｔｙ
Ａｅｒｏｎａｕｔｉｃｓａｎｄ
Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ２１００１６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｅｅｎｈａｎｃｅｍｅｎｔｏｆｔｈｅｎｏｖｅｌｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍｒｅｐｌａｃｉｎｇｋｅｙｔｅｄ．Ｔｈｅ
ｍａｔｒｉｘ（ＲＫＭ）ｉｓ
ｐｒｅｓｅｎ—
ｅｎｈａｎｃｅｍｅｎｔｃｏｍｐｒｉｓｅｓ：ｋｅｙ
ａｎｄ
ｅｖｏｌｕｔｉｏｎａｌｇｏｒｉｔｈｍ，ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｆａｃｔｏｒｍａｔｒｉｘ，ａｎｄｔｈｅ
ｋｅｙｄｉｓｔｒｉｂｕｔｉｏｎｕｐｄａｍａｌｇｏｒｉｔｈｍ．Ｋｅｙｅｖｏｌｕｔｉｏｎａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｉｓｔｈｅｂａｓｉｃｍｏｄｕｌｅｏｆｔｈｅ
ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｆａｃｔｏｒｃａｌｃｕｌａｔｅｓ
ａ
ｎｅｗｋｅｙ
ｏｎ
ｍａｔｒｉｘ—ｃａｌｃｕｌａｔｉｎｇａｌｇｏｒｉｔｈｍａｎｄｔｈｅｋｅｙｄｉｓｔｒｉｂｕｔｉｏｎａｎｄｕｐｄａｔｅｍａｔｒｉｘｆｒｏｍ１６－ｂｙｔｅａｒｒａｙ（ＳＯ－ｃａｌｌｅｄ“ｅｖｏｌｕｔｉｏｎｐｏｉｎｔｅｒ”）ａｎｄ
ａ
ａｌｇｏｒｉｔｈｍ，
ａｎ
ｏｌｄｋｅｙ
ｍａｔｒｉｘ．Ｂａｓｅｄ
ｔｈｅｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｆａｃｔｏｒｍａｔｒｉｘ，ｗｈｉｃｈｉｓｃａｌｃｕｌａｔｅｄｆｒｏｍｔｈｅ１２８ｂｉｔｋｅｙｍａｔｒｉｘ
ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｆａｃｔｏｒ，ｔｈｅｅｎｈａｎｃｅｍｅｎｔｏｆｔｈｅｅｎｃｒｙｐｔｉｏｎｐｒｏｃｅｓｓｉｓｄｅｃｒｙｐｔｉｏｎｐｒｏｃｅｓｓｏｆｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｉｓａｂｓｏｌｕｔｅｌｙｔｈｅ
ｍａｄｅ．Ｔｈｅ
ｅｎｃｒｙｐｆｉｏｎ
ａｎｄ
ｔｈｅ
ｓａｍｅ．Ｔｈｅ
ｎｅｗａｌｇｏｒｉｔｈｍｏｍｉｔｓ４ｒｏｕｎｄｓ
ＸＯＲｏｐｅｒａｔｉｏｎｓｗｉｔｈｏｕｔｈａｒｍｉｎｇｔｈｅｓｅｃｕｒｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ｕｓｉｎｇｔｈｅｋｅｙｄｉｓｔｒｉｂｕｔｉｏｎａｌｇｏｒｉｔｈｍ．ｔｈｅｒｅｉｓ
ｎｏ
ａｎｄ
ｕｐｄａｔｅ
ｎｅｅｄｔｏｎａｎｓｆｅｒｔｈｅｋｅｙｍａｔｒｉｘｅｖｅｒｙｔｉｍｅ．
Ｋｅｙｗｏｒｄｓ：ｅｎｃｒｙｐｆｉｏｎａｌｇｏｒｉｔｈｍ；ｒｅｐｌａｃｉｎｇｋｅｙｍａｔｒｉｘ；ｋｅｙｅｖｏｌｕｔｉｏｎａｌｇｏｒｉｔｈｍ；ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ
ｆａｃｔｏｒｍａｔｒｉｘ
对称分组加密算法（如Ｂｌｏｗｆｉｓｈｕ吲，ＲＣ５ＨＪ，
ＡＥＳ［４］，ＡＣ”１等）是信息安全的基础部件，具有安全性高、加解密速度快、软硬件实现标准化等优点，自主研究设计高安全性对称分组加密算法是十分必要的．置换密钥矩阵加密算法【６０（ｒｅｐｌａｃｉｎｇ
ｋｅｙ
缺点是：它的解密算法和加密算法是不相同的，这一点与Ｆｅｉｓｔｅｌ型密码＂１有明显的不同．Ｆｅｉｓｔｅｌ型密码的巧妙之处在于，除了子密钥输入顺序之外，其加密和解密的步骤完全相同，这就使得在制作芯片时易于做到标准化和通用化．本文对ＲＫＭ算法进行改进（ＲＫＭ・ＩＩ），统一了算法的加、解密流程，有利于用硬件实现ＲＫＭ一Ⅱ算法．ＲＫＭ－Ⅱ算法用特征因子子矩阵的查表运算，替代了与矩阵特征因子的异或运算，
ｍａｔｒｉｘ，ＲＫＭ）是一种新的基于置换密钥矩阵的非
线性多米诺查表加密算法，它既不同于ＡＥＳＭｌ的固定Ｓ盒，也不同于Ｂｌｏｗｆｉｓｈ【１刮的密钥相关Ｓ盒，它的密钥就是一个随机Ｓ盒．但ＲＫＭ算法的一个
收稿日期：２００７旬７—１０．作者简介：叶峰（１９７４一），男，博士生，ｙｅｆｅｎｇ．ｎｕａａ＠ｈｏｔｍａｉｌ．ｃｏｍ．
引文格式：叶峰，袁家斌．置换密钥矩阵加密算法的改进［Ｊ］．东南大学学报：自然科学版，２００８，３８（１）：ｌｌ—１５
万方数据
１２
东南大学学报（自然科学版）
第３８卷
在不降低安全性的前提下减少了运算量．
在密码算法的实际应用中，密钥的建立、分发与管理哺’１训是密码系统的重要组成部分．ＲＫＭ算法的密钥矩阵过大，不利于密钥的分发与管理．本文设计了一个密钥进化算法，并在密钥进化算法的基础上研究了ＲＫＭ一Ⅱ算法的密钥分发与更新问题．１
ＲＫＭ－ＩＩ算法流程
文献［６］给出了ＲＫＭ算法的详细描述．ＲＫＭ
算法的加密流程包括３个部分：初始变换、中间变换和结束变换．初始变换是２轮与特征因子的异或运算加上多米诺查表运算和字节换位运算的组合．中间变换是４轮多米诺查表运算和字节换位运算的组合．结束变换同样是２轮与特征因子的异或运算加上多米诺查表运算和字节换位运算的组合，总共进行８轮运算．ＲＫＭ算法的加、解密过程是不对称的，它的解密过程是加密过程的反演．图１为ＲＫＭ—ＩＩ算法流程，该算法与Ｆｅｉｓｔｅｌ型密码一样，是一种加、解密流程完全对称的分组加密算法，也就是说，其解密算法和加密算法的计算流程相同．
ＲＫＭ．ＩＩ加密算法对１２８位明文进行加密时，以字节为最小单位进行，整个算法计算过程同样有８轮，但与ＲＫＭ算法不同，ＲＫＭ一１１算法不分初始变换、中间变换与结束变换．算法主要计算过程是多米诺查表∞１和字节换位．多米诺查表的目的有２
个：①为了制造混乱；②为了增加雪崩效应．通过多
米诺查表可以将明文和密钥通过非线性的方式结合在一起．在ＲＫＭ．ＩＩ算法中用到的查表同ＲＫＭ算法一样是一个随机密钥矩阵Ｍ］．在多米诺查表之后要进行字节换位，方法是将１６个单字节数逆序排列，其目的是进一步增强扩散的效果．
ＲＫＭ—ＩＩ加密算法除了最后一轮，每一轮都是一次多米诺查表加字节换位，最后一轮多米诺查表之后不进行字节换位．８轮多米诺查表使用的矩阵是对称的：首先是主密钥矩阵，接着是横向特征因子子矩阵和纵向特征因子子矩阵，然后再跟一个主密钥矩阵；后４轮是前４轮的逆过程，首先是主密钥矩阵，接着是纵向特征因子子矩阵和横向特征因子子矩阵，最后再跟一个主密钥矩阵．明文经过以上８轮计算之后就得到密文．
ＲＫＭ—１１算法在对１２８位密文进行解密时，其解密过程和加密过程完全一样，但是输入的密钥矩阵不同．加密使用某个密钥矩阵，解密时就使用其逆矩阵哺］．ＲＫＭ．ＩＩ算法之所以加、解密对称，是因
万
方数据输入（１６字节）
１２３４５６７８９１０１１１２１３１４１５１６●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
ｔ
多米诺查表（主密钥矩阵）＋字节换位●
●
●
ｔ●●●●●●●●●
●●●
多米诺查表（横向特征因子子矩阵）＋字节换位●
●●●●●●●●●●●●●●
●
多米诺查表（纵向特征因子子矩阵）＋字节换位
●●●●●●●●●●●●●●●●
多米诺查表（主密钥矩阵）＋字节换位
●●●●●●●●●●●●ｔ
●
●
●
多米诺查表（主密钥矩阵）＋字节换位●●
●●●●●●●●●●●
●●●多米诺查表（纵向特征因子子矩阵）＋字节换位●
●●＋●●●●●●●●●●●●
多米诺查表（横向特征因子子矩阵）＋字节换位
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
多米诺查表（主密钥矩阵）
●●●●
●●●●●●●●
●●●●
输出（１６字节）图１
ＲＫＭ．ＩＩ算法流程
ＲＫＭ—ＩＩ算法提供２种分组长度选择：１２８位和２５６位．上述为１２８位ＲＫＭ—ＩＩ算法流程，当输ＲＫＭ算法的特点之一是引入了矩阵特征因子．置换密钥矩阵特征因子Ｍ１是置换密钥矩阵经在一定程度上反映该置换密钥矩阵的元素序列特征．置换密钥矩阵特征因子包括置换密钥矩阵横向特征因子和置换密钥矩阵纵向特征因子，它们是置
换密钥矩阵从横向和纵向２个不同的方向运算得
到的．引入特征因子的目的是尽可能将置换密钥矩阵的特征映射到密文上，提高算法的安全性．在ＲＫＭ算法中，特征因子和明文数据的作用方式是异或运算．
为了增强混乱和扩散效果，在ＲＫＭ—ＩＩ算法中设计了特征因子子矩阵．所谓特征因子子矩阵就是将横向特征因子作为进化指针，和密钥矩阵一起代人密钥进化算法中，得到的新矩阵称为横向特征因子子矩阵；同样，将纵向特征因子作为进化指针，和密钥矩阵一起代入密钥进化算法中，得到的新矩阵称为纵向特征因子子矩阵（见图２）．这样，在实际加密运算过程中，就将有３个密钥矩阵参加运算．
为它的每一步都是自反的，包括多米诺查表和字节换位．
入是２５６位明文，也就是３２个字节时，加、解密算法和１２８位基本相同，只是在多米诺查表和字节换位时运算长度增加一倍．
２特征因子子矩阵
２．１特征因子子矩阵的计算
过特征因子算法而得到的一组值，这一组数值能够
第１期
叶峰，等：置换密钥矩阵加密算法的改进
置换密钥矩阵计算其特征因子代入密钥进化算法特征因子子矩阵
１３
变的ｋ了，因为特征因子仅仅是主密钥矩阵的函
Ｕ
数，而与输人明文无关．所以说特征因子子矩阵的引入相当于引入一个随明文改变的子密钥ｋ．
由前文分析可知，ＲＫＭ—ＩＩ算法的特征因子子矩阵查表运算相当于ＲＫＭ算法的主密钥矩阵查表运算加上与特征因子的异或运算相结合的效果，这样使算法省去了４轮异或步骤而不降低安全性．
图２特征因子子矩阵计算
２．２特征因子子矩阵的安全性
在ＲＫＭ算法中，是用特征因子跟明文进行按位异或运算怕Ｊ．明文按分组进行加密，每个分组有１２８位，而特征因子的长度也正好是１２８位，所以可以先用明文跟横向特征因子进行异或运算，再跟纵向特征因子进行异或运算，这部分运算为初始替换．同样，在结束替换中，先用明文跟纵向特征因子进行异或运算，再跟横向特征因子进行异或运算．
在ＲＫＭ－ＩＩ算法中，将算法的初始变换和结束变换从与横向、纵向特征因子的异或改成查横向、纵向特征因子子矩阵．横向特征因子子矩阵和纵向特征因子子矩阵是分别利用横向特征因子和纵向特征因子经过密钥进化算法进化而来的，它们包含了横向特征因子和纵向特征因子的信息．经过改进，不但特征因子的计算是非线性的，而且特征因子和明文数据的组合计算也是非线性的，增加了密码分析的难度从而增加了算法的安全性．而且，算法将只保留查表和字节换位２种运算，从而算法更加对称了．
不仅如此，特征因子子矩阵的引入还相当于引进了随明文变化而变化的密钥的作用．这个效果可以从图３看出．设明文ｍ经过主密钥矩阵查表得
经过改进后，算法更加简单、对称，也更加高效，算
法也更容易用软件和硬件来实现；另外，复杂的子矩阵生成过程也增加了穷举攻击的代价．３
ＲＫＭ－Ⅱ算法的密钥建立与分发
ＲＫＭ算法是基于置换密钥矩阵的，置换密钥
矩阵旧１既是算法的密钥，又是算法的运算函数，这是ＲＫＭ算法区别于其他对称加密算法的主要特征．置换密钥矩阵是一个８ｂｉｔ输入８ｂｉｔ输出的随机Ｓ盒，随机选择的Ｓ盒对于抵抗已知的攻击方法如线性攻击和差分攻击也许不是最优的，但只要Ｓ盒足够大就足以对抗这些攻击，并且随机Ｓ盒对于未来可能的密码攻击也有足够的抵抗性【１１。．但是８
ｂｉｔ×８
ｂｉｔ的Ｓ盒一共占用８×２８＝２
０４８ｂｉｔ
的存储量，这么长的密钥在使用中不方便，密钥建立与分发是ＲＫＭ算法的一个问题．在ＲＫＭ．１Ｉ算法中设计了密钥进化算法来解决这个问题．
ＲＫＭ—ＩＩ算法有一个初始密钥矩阵也称主密
钥，它要么由可靠的随机源产生，要么用安全的伪随机数发生器产生．主密钥是用来加密数据密钥的，而数据密钥才是真正用来加密用户数据的．在加密系统中，主密钥必须由安全的备用信道发送，比如存储在ＲＯＭ芯片或ＩＣ卡中手工发送【８１；当需要传输加密数据时，由发送方确定数据密钥并由主密钥加密，然后通过普通信道传输给接收方，接受方再用主密钥解密数据密钥，接着收发双方就可
ｍ。，再经过特征因子子矩阵查表得ｍ：．其中对特征
因子子矩阵的查表运算可以用右边的图示来等价代替，也就是先用主密钥矩阵查表得ｍ‘，再与ｋ
异或得ｍ：．其中ｋ可以看成一个子密钥．由于％
＝ｍ‘ｏ七，所以ｋ＝ｍ‘０ｍ２，也就是说ｋ是间接依赖于明文的．输入不同的明文ｍ，ｍ‘也将发生改变，从而ｋ也将改变．如果不采用特征因子子矩阵，而采用与特征因子的异或运算，就不会有随明文改
以用数据密钥进行加解密传输数据了．ＲＫＭ—Ｈ算
法的大致步骤也跟上述一样，但有一个大的不同是：ＲＫＭ—ＩＩ算法由主密钥加密传输的不是数据加
Ｉｍ
Ｉ
ｌ
密密钥，而是密钥进化指针，而密钥进化指针还要
经过一个密钥进化算法才能计算出真正的数据加密密钥．这样做的效果是，虽然每次传输的只是
１２８
主密钥矩阵
Ｉ
主密钥矩阵
Ｊｍ－
主密钥矩阵
Ｉ
ｍ１
ｂｉｔ的密钥进化指针，但是攻击者需要穷举的
ｌ特征因子子矩阵
Ｉ
ｍ。
密钥空间仍然是２５６１，解决了密钥空间和密钥传输之间的矛盾．３．１密钥进化算法
异或ｋ
图３子矩阵效应
密钥进化算法用一个密钥进化指针和一个原
万方数据
１４
东南大学学报（自然科学版）第３８卷
置换密钥矩阵计算出一个新的置换密钥矩阵，它的流程分为２个步骤：
步骤１
以１２８位的密钥进化指针和原矩阵
作为输入，对进化指针的每一个元素做以下工作：
①与密钥矩阵中的每个元素进行异或，产生
新的矩阵；
。
②对该矩阵进行采样，采样频率取进化指针
中的值．２５６轮采样之后，将产生一个新的矩阵．在采样的过程中，为了保证原矩阵的每个元素都被采到，也就是矩阵中不能有重复的数据，需要将进化指针中的偶数变成奇数，这是通过把偶数加上１来实现的．另外，如果采样频率为１，则没有意义，所以采样频率最小为３；同理，２５５也没有意义，所以采样频率最大为２５３．
对进化指针中的１６个元素都作上述运算得到一个新的矩阵。对矩阵再进行一个整理：遍历矩阵中的元素，检查查表值Ｒ（Ｘ）＝Ｘ的元素，将那些Ｒ（ｘ）＝Ｘ的元素与其后的元素互换，这就完成了密钥进化算法的第１个步骤．
步骤２把步骤１所得的中间矩阵的横向特征因子和纵向特征因子进行异或，再把异或值作为进化指针重新代人步骤１中，再进行一次密钥进化，最后得到所要的结果密钥矩阵．这样做的目的是防止由结果矩阵和进化指针逆推出原密钥矩阵，因为原密钥矩阵通常是非常重要的主密钥，在最坏的情况下也应该是安全的．３．２密钥分发和更新
在ＲＫＭ—ＩＩ算法中主密钥用手工发送，而数据加密密钥，也就是会话密钥是这样产生的：在每次需要进行数据传输时由发送方确定进化指针，并用主密钥加密后传输给接受方，再由收发双方分别运行密钥进化算法计算出会话密钥．这样产生的会话密钥用来进行对数据进行加密传输工作，通常只作一次性使用．
ＲＫＭ—ＩＩ算法数据密钥的分发实际上是一种
密钥拆分技术．将真正用于数据加密的密钥分解成
２个部分，即主密钥和进化指针，知道其中任何一个而缺乏另一个都无法得到数据密钥．而且这种密钥拆分方案不是简单的异或，而是一个不可逆的单向函数，这就保证了即使数据加密密钥被攻破或失窃，也无法逆向求出主密钥，因为在密钥进化算法的第ｌ步骤输出和第２步骤中输入的中间矩阵是求不出的．由于主密钥只用来加密很短的进化指针，而且进化算法保证了主密钥很难被逆向计算，
万
方数据所以主密钥不需要经常变动．数据密钥矩阵和主密钥矩阵有一样的强度，却只需传输进化指针而不用
传输整个矩阵就得到很高的强度，密钥进化算法解
决安全性和效率的矛盾．
ＲＫＭ一１Ｉ算法用于定期的数据链路加密时，每次都分发进化指针也十分麻烦，这时可以采取密钥自进化的办法进行自动更新密钥．密钥更新是根据密钥矩阵自身的信息进行进化，不需要外部输入信息，自进化可以每隔几小时或每天进行．自进化的规则如图４所示，从上一轮密钥中计算出横向特征因子和纵向特征因子，从横向特征因子中提取第１，３，５，７，９，１１，１３，１５字节，从纵向特征因子中提取第２，４，６，８，１０，１２，１４，１６字节，组成共１６字节的数组．将这个数组与密钥矩阵进化深度ｎ进行异或，再用原密钥矩阵加密后作为进化指针和原密钥矩阵一起代入密钥进化算法，从而得到新的密钥，同时密钥矩阵的进化深度加１．与进化深度进行异或运算的目的是保证不陷入僵化矩阵，因为进化深度每次都加ｌ，所以进入基本进化算法的自进化指针不会循环重复．初始密钥的进化深度为０，每进化一次进化深度加１，当然系统必须记住自己的进化深度ｎ．
原矩阵
１－－－纵向特征因子卜Ｊ
＼‘用原矩阵加密ｉ到自进化羹针
’
Ｔ
代人密钥进化算法
图４密钥自进化流程
。
密钥更新过程是一个单向函数，发送方和接收方同步进行密钥更新，只要他们都有相同的初始密钥就可以一直保持同步．初始密钥可以直接采用主密钥，密钥更新的单向性保证了即使密钥序列后面的密钥失窃也不会危害主密钥的安全．如果发生系统丢失数据密钥或进化深度，ｌ的情况（比如系统瘫痪重启），只要由相邻的节点传送当前系统的进化深度，再进行相应次数的密钥进化运算就可以产生新的数据密钥．４
结语
本文在兼顾算法的安全性和效率的基础上，对
ＲＫＭ算法进行了改进，主要包括２个方面：一方面
第１期叶峰，等：置换密钥矩阵加密算法的改进
是提出置换密钥矩阵特征因子子矩阵的概念，将ＲＫＭ算法改进为加、解密完全对称的算法，新的
ＲＫＭ－１Ｉ算法用特征因子子矩阵的查表运算替代
与矩阵特征因子的异或运算，使得加密运算更加非线性化，同时又省去了４个异或步骤，这样就既保证了安全性，又提高了效率；另一方面是在兼顾安全性和效率的基础上，提出一个密钥进化算法，研究了ＲＫＭ．Ⅱ算法的密钥建立、分发与更新，以利于算法的实际应用．
参考文献（Ｒｅｆｅｒｅｎｃｅｓ）
［１］Ｓｃｈｎｅｉｅｒ
Ｂ．Ｄｅｓｃｒｉｐｔｉｏｎｏｆ
ａ
ｎｅｗｖａｒｉａｂｌｅ・ｌｅｎｇｔｈｋｅｙ，
６４－ｂｉｔｂｌｏｃｋ
ｃｉｐｈｅｒ（Ｂｌｏｗｆｉｓｈ）［ｃ］／／ＦａｓｔＳｏｆｔｗａｒｅ
Ｅｎｃｒｙｐｔｉｏｎ，ＣａｍｂｒｉｄｇｅＳｅｃｕｒｉｔｙ
Ｗｏｒｋｓｈｏｐ
Ｐｒｏｃｅｅｄ－
ｉｎｇｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ。１９９４：１９１—２０４．
［２］Ｓｃｈｎｅｉｅｒ
Ｂ．Ｔｈｅｂｌｏｗｆｉｓｈｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍ［Ｊ］．Ｄｒ
Ｄｏｂｂ’ｓ
Ｊｏｕｒｎａｌ，１９９４，１９（４）：３８—４０．
［３］Ｒｉｖｅｓｔ
Ｒ
Ｌ．Ｔｈｅ
ＲＣ５ｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍ［Ｊ］．Ｄｒ
Ｄｏｂｂ＇ｓＪｏｕｒｎａｌ，１９９５，２０（１）：１４６—１４８．
［４］ＤａｅｍｅｎＪ，ＲｉｊｍｅｎＶ．高级加密标准（ＡＥＳ）算法——
Ｒｉｊｎｄａｅｌ的设计［Ｍ］．谷大武，徐胜波，译．北京：清华大学出版社，２００３：３１—５２．
［５］吴文玲，马恒太，冯登国，等．ＡＣ分组密码［Ｊ］．通信
学报，２００２，２３（５）：１３０—１３４．
ＷｕＷｅｎＬｉｎｇ，ＭａＨｅｎｇｔａｉ，ＦｅｎｇＤｅｎｇｇｕｏ，ｅｔａ１．Ｔｈｅ
万
方数据ＡＣ
ｂｌｏｃｋｃｉｐｈｅｒ［Ｊ］．ＪｏｕｒｎａｌｏｆＣｈｉｎａＩｎｓｔｉｔｕｔｅｏｆ
Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００２，２３（５）：１３０—１３４．（ｉｎＣｈｉ・
ｎｅｓｅ）
［６］袁家斌，叶峰．一种全新的基于置换密钥矩阵加密算
法［Ｊ］．南京航空航天大学学报，２００５，３７（６）：７５４—
７５９．
ＹｕａｎＪｉａｂｉｎ，ＹｅＦｅｎｇ．Ａｎｏｖｅｌｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍｏｆ
ｒｅｐｌａｃｅｋｅｙ
ｍａｔｒｉｘ［Ｊ］．ＪｏｕｒｎａｌｏｆＮａｎｊｉｎｇ
Ｕｎｉｖｅｒｓｉｔｙ
ｏｆＡｅｒｏｎａｕｔｉｃｓ＆Ａｓｔｒｏｎａｕｔｉｃｓ，２００５，３７（６）：７５４—７５９．（ｉｎＣｈｉｎｅｓｅ）
［７］ＳｆｉｎｓｏｎＤ．密码学原理与实践［Ｍ］．冯登国，译．北
京：电子工业出版社，２００３：７８．［８］Ｂａｌｅｎｓｏｎ
Ｄ．Ａｕｔｏｍａｔｅｄ
ｄｉｓｔｒｉｂｕｔｉｏｎｏｆｃｒｙｐｔｏｇｒａｐｈｉｅ
ｋｅｙｓ
ｕｓｉｎｇｔｈｅｆｉｎａｎｃｉａｌ
ｉｎｓｔｉｔｕｔｉｏｎ
ｋｅｙ
ｍａｎａｇｅｍｅｎｔ
ｓｔａｎｄａｒｄ［Ｊ］．ＩＥＥＥＣｏｍｍｕｎｉｃａｔｉｏｎｓＭａｇａｚｉｎｅ，１９８５，
２３（９）：４１—４６．［９］ＬｉＣｅｆｉａ，Ｙａｎｇ
Ｃｕｎｇａｎｇ，ＣｈｅｕｎｇＲｉｃｈａｒｄ．Ｋｅｙｍａｎ－
ａｇｅｍｅｎｔｆｏｒｒｏｌｅｈｉｅｒａｒｃｈｙｉｎｄｉｓｔｒｉｂｕｔｅｄｓｙｓｔｅｍｓ［Ｊ］．
Ｊｏｕｒｎａｌ
ｏｆＮｅｔｗｏｒｋａｎｄＣｏｍｐｕｔｅｒ
Ａｐｐｌｉｃａ矗ｏｎｓ，２００７，
∞（３）：９２０—９３６．［１０］Ｉ．－Ｉａｓｓｅｎ
ＨＲａｇａｂ，ＢｏｕａｂｄａｌｌａｈＡ，ＢｅｔｔａｈａｒＨ，ｅｔａ１．
Ｋｅｙ
ｍａｎａｇｅｍｅｎｔｆｏｒ
ｃｏｎｔｅｎｔ
ａｃ，ｃｅｓｓ
ｃｏｎｔｒｏｌｉｎ
ａ
ｈｉｅｒａｒ－
ｃｌａｙ［Ｊ］．ＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋｓ，２００７，５１（１１）：３１９７—
３２１９．
［１１］ＳｃｈｎｅｉｅｒＢ．应用密码学——协议、算法与Ｃ源程序
［Ｍ］．吴世忠，祝世雄，张文政，等译．北京：机械工业出版社，２０００：２４８．
置换密钥矩阵加密算法的改进
作者：作者单位：刊名：英文刊名：年，卷(期)：
叶峰， 袁家斌， Ye Feng， Yuan Jiabin
南京航空航天大学信息科学与技术学院,南京,210016
东南大学学报（自然科学版）
JOURNAL OF SOUTHEAST UNIVERSITY(NATURAL SCIENCE EDITION)2008,38(1)
参考文献(11条)
1. Li Celia;Yang Cungang;Cheung Richard Key man-agement for role hierarchy in distributed systems[外文期刊] 2007(03)
2. Balenson D Automated distribution of cryptographie keys using the financial institution keymanagement standard 1985(09)
3. Stinson D;冯登国 密码学原理与实践 2003
4. 袁家斌;叶峰 一种全新的基于置换密钥矩阵加密算法[期刊论文]-南京航空航天大学学报 2005(06)5. 吴文玲;马恒太;冯登国 AC分组密码[期刊论文]-通信学报 2002(05)
6. Daemen J;Rijmen V;谷大武;徐胜波 高级加密标准(AES)算法--Rijndael的设计 20037. Rivest R L The RC5 encryption algorithm 1995(01)
8. Schneier B;吴世忠;祝世雄;张文政 应用密码学--协议、算法与C源程序 2000
9. Hassen H Ragab;Bouabdallah A;Bettahar H Keymanagementfor content ac,cess controlin ahierar-clay[外文期刊] 2007(11)
10. Schneier B The blowfish encryption algorithm 1994(04)
11. Schneier B Description of a new variable-length key,64-bit block cipher(Blowfish) 1994
本文链接：http://d.g.wanfangdata.com.cn/Periodical_dndxxb200801003.aspx
第３８卷第１期２００８年１月
东南大学学报（自然科学版）
ＪＯＵＲＮＡＬＯＦ
ＳＯＵＴＨＥＡＳＴ
ＶｏＬ３８
Ｅｄｉｔｉｏｎ）
Ｎｏ．１
ＵＮＩＶＥＲＳＩＴＹ（Ｎａｎｎ＿ａｌ
Ｓｃｉｅｎｃｅ
Ｊａｎ．２００８
置换密钥矩阵加密算法的改进
叶峰
袁家斌
（南京航空航天大学信息科学与技术学院，南京２１００１６）
摘要：提出了对分组加密算法（ＲＫＭ）的改进，主要包括密钥进化算法、特征因子子矩阵和密钥
的分发与更新算法．密钥进化算法是特征因子子矩阵生成算法和密钥分发与更新算法的基本组
件，由一个１６字节的单字节数组（称为进化指针）和一个密钥矩阵计算一个新的密钥矩阵．特征因子子矩阵是把１２８ｂｉｔ矩阵特征因子作为进化指针代入密钥进化算法计算而得．在引入特征因子子矩阵的基础上对算法流程进行了改进，使算法的加、解密完全对称．在不降低算法安全性的基础上减少了４轮异或运算，从而降低了运算量．在密钥进化算法的基础上设计了密钥的分发与更新算法，使算法无需每次传输密钥矩阵就能共享．
关键词：加密算法；置换密钥矩阵；密钥进化算法；特征因子子矩阵
中圈分类号：ＴＰ３０９．７
文献标识码：Ａ
文章编号：１００１—０５０５（２００８）０１．００１１－０５
Ｅｎｈａｎｃｅｍｅｎｔｏｆｒｅｐｌａｃｉｎｇｋｅｙｍａｔｒｉｘｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍ
ＹｅＦｅｎｇ
ＹｕａｎＪｉａｂｉｎ
ｏｆ
（ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＮａａｊｉｎｇＵｎｉｖｅｒｓｉｔｙ
Ａｅｒｏｎａｕｔｉｃｓａｎｄ
Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ２１００１６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｅｅｎｈａｎｃｅｍｅｎｔｏｆｔｈｅｎｏｖｅｌｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍｒｅｐｌａｃｉｎｇｋｅｙｔｅｄ．Ｔｈｅ
ｍａｔｒｉｘ（ＲＫＭ）ｉｓ
ｐｒｅｓｅｎ—
ｅｎｈａｎｃｅｍｅｎｔｃｏｍｐｒｉｓｅｓ：ｋｅｙ
ａｎｄ
ｅｖｏｌｕｔｉｏｎａｌｇｏｒｉｔｈｍ，ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｆａｃｔｏｒｍａｔｒｉｘ，ａｎｄｔｈｅ
ｋｅｙｄｉｓｔｒｉｂｕｔｉｏｎｕｐｄａｍａｌｇｏｒｉｔｈｍ．Ｋｅｙｅｖｏｌｕｔｉｏｎａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｉｓｔｈｅｂａｓｉｃｍｏｄｕｌｅｏｆｔｈｅ
ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｆａｃｔｏｒｃａｌｃｕｌａｔｅｓ
ａ
ｎｅｗｋｅｙ
ｏｎ
ｍａｔｒｉｘ—ｃａｌｃｕｌａｔｉｎｇａｌｇｏｒｉｔｈｍａｎｄｔｈｅｋｅｙｄｉｓｔｒｉｂｕｔｉｏｎａｎｄｕｐｄａｔｅｍａｔｒｉｘｆｒｏｍ１６－ｂｙｔｅａｒｒａｙ（ＳＯ－ｃａｌｌｅｄ“ｅｖｏｌｕｔｉｏｎｐｏｉｎｔｅｒ”）ａｎｄ
ａ
ａｌｇｏｒｉｔｈｍ，
ａｎ
ｏｌｄｋｅｙ
ｍａｔｒｉｘ．Ｂａｓｅｄ
ｔｈｅｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｆａｃｔｏｒｍａｔｒｉｘ，ｗｈｉｃｈｉｓｃａｌｃｕｌａｔｅｄｆｒｏｍｔｈｅ１２８ｂｉｔｋｅｙｍａｔｒｉｘ
ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｆａｃｔｏｒ，ｔｈｅｅｎｈａｎｃｅｍｅｎｔｏｆｔｈｅｅｎｃｒｙｐｔｉｏｎｐｒｏｃｅｓｓｉｓｄｅｃｒｙｐｔｉｏｎｐｒｏｃｅｓｓｏｆｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｉｓａｂｓｏｌｕｔｅｌｙｔｈｅ
ｍａｄｅ．Ｔｈｅ
ｅｎｃｒｙｐｆｉｏｎ
ａｎｄ
ｔｈｅ
ｓａｍｅ．Ｔｈｅ
ｎｅｗａｌｇｏｒｉｔｈｍｏｍｉｔｓ４ｒｏｕｎｄｓ
ＸＯＲｏｐｅｒａｔｉｏｎｓｗｉｔｈｏｕｔｈａｒｍｉｎｇｔｈｅｓｅｃｕｒｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ｕｓｉｎｇｔｈｅｋｅｙｄｉｓｔｒｉｂｕｔｉｏｎａｌｇｏｒｉｔｈｍ．ｔｈｅｒｅｉｓ
ｎｏ
ａｎｄ
ｕｐｄａｔｅ
ｎｅｅｄｔｏｎａｎｓｆｅｒｔｈｅｋｅｙｍａｔｒｉｘｅｖｅｒｙｔｉｍｅ．
Ｋｅｙｗｏｒｄｓ：ｅｎｃｒｙｐｆｉｏｎａｌｇｏｒｉｔｈｍ；ｒｅｐｌａｃｉｎｇｋｅｙｍａｔｒｉｘ；ｋｅｙｅｖｏｌｕｔｉｏｎａｌｇｏｒｉｔｈｍ；ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ
ｆａｃｔｏｒｍａｔｒｉｘ
对称分组加密算法（如Ｂｌｏｗｆｉｓｈｕ吲，ＲＣ５ＨＪ，
ＡＥＳ［４］，ＡＣ”１等）是信息安全的基础部件，具有安全性高、加解密速度快、软硬件实现标准化等优点，自主研究设计高安全性对称分组加密算法是十分必要的．置换密钥矩阵加密算法【６０（ｒｅｐｌａｃｉｎｇ
ｋｅｙ
缺点是：它的解密算法和加密算法是不相同的，这一点与Ｆｅｉｓｔｅｌ型密码＂１有明显的不同．Ｆｅｉｓｔｅｌ型密码的巧妙之处在于，除了子密钥输入顺序之外，其加密和解密的步骤完全相同，这就使得在制作芯片时易于做到标准化和通用化．本文对ＲＫＭ算法进行改进（ＲＫＭ・ＩＩ），统一了算法的加、解密流程，有利于用硬件实现ＲＫＭ一Ⅱ算法．ＲＫＭ－Ⅱ算法用特征因子子矩阵的查表运算，替代了与矩阵特征因子的异或运算，
ｍａｔｒｉｘ，ＲＫＭ）是一种新的基于置换密钥矩阵的非
线性多米诺查表加密算法，它既不同于ＡＥＳＭｌ的固定Ｓ盒，也不同于Ｂｌｏｗｆｉｓｈ【１刮的密钥相关Ｓ盒，它的密钥就是一个随机Ｓ盒．但ＲＫＭ算法的一个
收稿日期：２００７旬７—１０．作者简介：叶峰（１９７４一），男，博士生，ｙｅｆｅｎｇ．ｎｕａａ＠ｈｏｔｍａｉｌ．ｃｏｍ．
引文格式：叶峰，袁家斌．置换密钥矩阵加密算法的改进［Ｊ］．东南大学学报：自然科学版，２００８，３８（１）：ｌｌ—１５
万方数据
１２
东南大学学报（自然科学版）
第３８卷
在不降低安全性的前提下减少了运算量．
在密码算法的实际应用中，密钥的建立、分发与管理哺’１训是密码系统的重要组成部分．ＲＫＭ算法的密钥矩阵过大，不利于密钥的分发与管理．本文设计了一个密钥进化算法，并在密钥进化算法的基础上研究了ＲＫＭ一Ⅱ算法的密钥分发与更新问题．１
ＲＫＭ－ＩＩ算法流程
文献［６］给出了ＲＫＭ算法的详细描述．ＲＫＭ
算法的加密流程包括３个部分：初始变换、中间变换和结束变换．初始变换是２轮与特征因子的异或运算加上多米诺查表运算和字节换位运算的组合．中间变换是４轮多米诺查表运算和字节换位运算的组合．结束变换同样是２轮与特征因子的异或运算加上多米诺查表运算和字节换位运算的组合，总共进行８轮运算．ＲＫＭ算法的加、解密过程是不对称的，它的解密过程是加密过程的反演．图１为ＲＫＭ—ＩＩ算法流程，该算法与Ｆｅｉｓｔｅｌ型密码一样，是一种加、解密流程完全对称的分组加密算法，也就是说，其解密算法和加密算法的计算流程相同．
ＲＫＭ．ＩＩ加密算法对１２８位明文进行加密时，以字节为最小单位进行，整个算法计算过程同样有８轮，但与ＲＫＭ算法不同，ＲＫＭ一１１算法不分初始变换、中间变换与结束变换．算法主要计算过程是多米诺查表∞１和字节换位．多米诺查表的目的有２
个：①为了制造混乱；②为了增加雪崩效应．通过多
米诺查表可以将明文和密钥通过非线性的方式结合在一起．在ＲＫＭ．ＩＩ算法中用到的查表同ＲＫＭ算法一样是一个随机密钥矩阵Ｍ］．在多米诺查表之后要进行字节换位，方法是将１６个单字节数逆序排列，其目的是进一步增强扩散的效果．
ＲＫＭ—ＩＩ加密算法除了最后一轮，每一轮都是一次多米诺查表加字节换位，最后一轮多米诺查表之后不进行字节换位．８轮多米诺查表使用的矩阵是对称的：首先是主密钥矩阵，接着是横向特征因子子矩阵和纵向特征因子子矩阵，然后再跟一个主密钥矩阵；后４轮是前４轮的逆过程，首先是主密钥矩阵，接着是纵向特征因子子矩阵和横向特征因子子矩阵，最后再跟一个主密钥矩阵．明文经过以上８轮计算之后就得到密文．
ＲＫＭ—１１算法在对１２８位密文进行解密时，其解密过程和加密过程完全一样，但是输入的密钥矩阵不同．加密使用某个密钥矩阵，解密时就使用其逆矩阵哺］．ＲＫＭ．ＩＩ算法之所以加、解密对称，是因
万
方数据输入（１６字节）
１２３４５６７８９１０１１１２１３１４１５１６●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
ｔ
多米诺查表（主密钥矩阵）＋字节换位●
●
●
ｔ●●●●●●●●●
●●●
多米诺查表（横向特征因子子矩阵）＋字节换位●
●●●●●●●●●●●●●●
●
多米诺查表（纵向特征因子子矩阵）＋字节换位
●●●●●●●●●●●●●●●●
多米诺查表（主密钥矩阵）＋字节换位
●●●●●●●●●●●●ｔ
●
●
●
多米诺查表（主密钥矩阵）＋字节换位●●
●●●●●●●●●●●
●●●多米诺查表（纵向特征因子子矩阵）＋字节换位●
●●＋●●●●●●●●●●●●
多米诺查表（横向特征因子子矩阵）＋字节换位
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
多米诺查表（主密钥矩阵）
●●●●
●●●●●●●●
●●●●
输出（１６字节）图１
ＲＫＭ．ＩＩ算法流程
ＲＫＭ—ＩＩ算法提供２种分组长度选择：１２８位和２５６位．上述为１２８位ＲＫＭ—ＩＩ算法流程，当输ＲＫＭ算法的特点之一是引入了矩阵特征因子．置换密钥矩阵特征因子Ｍ１是置换密钥矩阵经在一定程度上反映该置换密钥矩阵的元素序列特征．置换密钥矩阵特征因子包括置换密钥矩阵横向特征因子和置换密钥矩阵纵向特征因子，它们是置
换密钥矩阵从横向和纵向２个不同的方向运算得
到的．引入特征因子的目的是尽可能将置换密钥矩阵的特征映射到密文上，提高算法的安全性．在ＲＫＭ算法中，特征因子和明文数据的作用方式是异或运算．
为了增强混乱和扩散效果，在ＲＫＭ—ＩＩ算法中设计了特征因子子矩阵．所谓特征因子子矩阵就是将横向特征因子作为进化指针，和密钥矩阵一起代人密钥进化算法中，得到的新矩阵称为横向特征因子子矩阵；同样，将纵向特征因子作为进化指针，和密钥矩阵一起代入密钥进化算法中，得到的新矩阵称为纵向特征因子子矩阵（见图２）．这样，在实际加密运算过程中，就将有３个密钥矩阵参加运算．
为它的每一步都是自反的，包括多米诺查表和字节换位．
入是２５６位明文，也就是３２个字节时，加、解密算法和１２８位基本相同，只是在多米诺查表和字节换位时运算长度增加一倍．
２特征因子子矩阵
２．１特征因子子矩阵的计算
过特征因子算法而得到的一组值，这一组数值能够
第１期
叶峰，等：置换密钥矩阵加密算法的改进
置换密钥矩阵计算其特征因子代入密钥进化算法特征因子子矩阵
１３
变的ｋ了，因为特征因子仅仅是主密钥矩阵的函
Ｕ
数，而与输人明文无关．所以说特征因子子矩阵的引入相当于引入一个随明文改变的子密钥ｋ．
由前文分析可知，ＲＫＭ—ＩＩ算法的特征因子子矩阵查表运算相当于ＲＫＭ算法的主密钥矩阵查表运算加上与特征因子的异或运算相结合的效果，这样使算法省去了４轮异或步骤而不降低安全性．
图２特征因子子矩阵计算
２．２特征因子子矩阵的安全性
在ＲＫＭ算法中，是用特征因子跟明文进行按位异或运算怕Ｊ．明文按分组进行加密，每个分组有１２８位，而特征因子的长度也正好是１２８位，所以可以先用明文跟横向特征因子进行异或运算，再跟纵向特征因子进行异或运算，这部分运算为初始替换．同样，在结束替换中，先用明文跟纵向特征因子进行异或运算，再跟横向特征因子进行异或运算．
在ＲＫＭ－ＩＩ算法中，将算法的初始变换和结束变换从与横向、纵向特征因子的异或改成查横向、纵向特征因子子矩阵．横向特征因子子矩阵和纵向特征因子子矩阵是分别利用横向特征因子和纵向特征因子经过密钥进化算法进化而来的，它们包含了横向特征因子和纵向特征因子的信息．经过改进，不但特征因子的计算是非线性的，而且特征因子和明文数据的组合计算也是非线性的，增加了密码分析的难度从而增加了算法的安全性．而且，算法将只保留查表和字节换位２种运算，从而算法更加对称了．
不仅如此，特征因子子矩阵的引入还相当于引进了随明文变化而变化的密钥的作用．这个效果可以从图３看出．设明文ｍ经过主密钥矩阵查表得
经过改进后，算法更加简单、对称，也更加高效，算
法也更容易用软件和硬件来实现；另外，复杂的子矩阵生成过程也增加了穷举攻击的代价．３
ＲＫＭ－Ⅱ算法的密钥建立与分发
ＲＫＭ算法是基于置换密钥矩阵的，置换密钥
矩阵旧１既是算法的密钥，又是算法的运算函数，这是ＲＫＭ算法区别于其他对称加密算法的主要特征．置换密钥矩阵是一个８ｂｉｔ输入８ｂｉｔ输出的随机Ｓ盒，随机选择的Ｓ盒对于抵抗已知的攻击方法如线性攻击和差分攻击也许不是最优的，但只要Ｓ盒足够大就足以对抗这些攻击，并且随机Ｓ盒对于未来可能的密码攻击也有足够的抵抗性【１１。．但是８
ｂｉｔ×８
ｂｉｔ的Ｓ盒一共占用８×２８＝２
０４８ｂｉｔ
的存储量，这么长的密钥在使用中不方便，密钥建立与分发是ＲＫＭ算法的一个问题．在ＲＫＭ．１Ｉ算法中设计了密钥进化算法来解决这个问题．
ＲＫＭ—ＩＩ算法有一个初始密钥矩阵也称主密
钥，它要么由可靠的随机源产生，要么用安全的伪随机数发生器产生．主密钥是用来加密数据密钥的，而数据密钥才是真正用来加密用户数据的．在加密系统中，主密钥必须由安全的备用信道发送，比如存储在ＲＯＭ芯片或ＩＣ卡中手工发送【８１；当需要传输加密数据时，由发送方确定数据密钥并由主密钥加密，然后通过普通信道传输给接收方，接受方再用主密钥解密数据密钥，接着收发双方就可
ｍ。，再经过特征因子子矩阵查表得ｍ：．其中对特征
因子子矩阵的查表运算可以用右边的图示来等价代替，也就是先用主密钥矩阵查表得ｍ‘，再与ｋ
异或得ｍ：．其中ｋ可以看成一个子密钥．由于％
＝ｍ‘ｏ七，所以ｋ＝ｍ‘０ｍ２，也就是说ｋ是间接依赖于明文的．输入不同的明文ｍ，ｍ‘也将发生改变，从而ｋ也将改变．如果不采用特征因子子矩阵，而采用与特征因子的异或运算，就不会有随明文改
以用数据密钥进行加解密传输数据了．ＲＫＭ—Ｈ算
法的大致步骤也跟上述一样，但有一个大的不同是：ＲＫＭ—ＩＩ算法由主密钥加密传输的不是数据加
Ｉｍ
Ｉ
ｌ
密密钥，而是密钥进化指针，而密钥进化指针还要
经过一个密钥进化算法才能计算出真正的数据加密密钥．这样做的效果是，虽然每次传输的只是
１２８
主密钥矩阵
Ｉ
主密钥矩阵
Ｊｍ－
主密钥矩阵
Ｉ
ｍ１
ｂｉｔ的密钥进化指针，但是攻击者需要穷举的
ｌ特征因子子矩阵
Ｉ
ｍ。
密钥空间仍然是２５６１，解决了密钥空间和密钥传输之间的矛盾．３．１密钥进化算法
异或ｋ
图３子矩阵效应
密钥进化算法用一个密钥进化指针和一个原
万方数据
１４
东南大学学报（自然科学版）第３８卷
置换密钥矩阵计算出一个新的置换密钥矩阵，它的流程分为２个步骤：
步骤１
以１２８位的密钥进化指针和原矩阵
作为输入，对进化指针的每一个元素做以下工作：
①与密钥矩阵中的每个元素进行异或，产生
新的矩阵；
。
②对该矩阵进行采样，采样频率取进化指针
中的值．２５６轮采样之后，将产生一个新的矩阵．在采样的过程中，为了保证原矩阵的每个元素都被采到，也就是矩阵中不能有重复的数据，需要将进化指针中的偶数变成奇数，这是通过把偶数加上１来实现的．另外，如果采样频率为１，则没有意义，所以采样频率最小为３；同理，２５５也没有意义，所以采样频率最大为２５３．
对进化指针中的１６个元素都作上述运算得到一个新的矩阵。对矩阵再进行一个整理：遍历矩阵中的元素，检查查表值Ｒ（Ｘ）＝Ｘ的元素，将那些Ｒ（ｘ）＝Ｘ的元素与其后的元素互换，这就完成了密钥进化算法的第１个步骤．
步骤２把步骤１所得的中间矩阵的横向特征因子和纵向特征因子进行异或，再把异或值作为进化指针重新代人步骤１中，再进行一次密钥进化，最后得到所要的结果密钥矩阵．这样做的目的是防止由结果矩阵和进化指针逆推出原密钥矩阵，因为原密钥矩阵通常是非常重要的主密钥，在最坏的情况下也应该是安全的．３．２密钥分发和更新
在ＲＫＭ—ＩＩ算法中主密钥用手工发送，而数据加密密钥，也就是会话密钥是这样产生的：在每次需要进行数据传输时由发送方确定进化指针，并用主密钥加密后传输给接受方，再由收发双方分别运行密钥进化算法计算出会话密钥．这样产生的会话密钥用来进行对数据进行加密传输工作，通常只作一次性使用．
ＲＫＭ—ＩＩ算法数据密钥的分发实际上是一种
密钥拆分技术．将真正用于数据加密的密钥分解成
２个部分，即主密钥和进化指针，知道其中任何一个而缺乏另一个都无法得到数据密钥．而且这种密钥拆分方案不是简单的异或，而是一个不可逆的单向函数，这就保证了即使数据加密密钥被攻破或失窃，也无法逆向求出主密钥，因为在密钥进化算法的第ｌ步骤输出和第２步骤中输入的中间矩阵是求不出的．由于主密钥只用来加密很短的进化指针，而且进化算法保证了主密钥很难被逆向计算，
万
方数据所以主密钥不需要经常变动．数据密钥矩阵和主密钥矩阵有一样的强度，却只需传输进化指针而不用
传输整个矩阵就得到很高的强度，密钥进化算法解
决安全性和效率的矛盾．
ＲＫＭ一１Ｉ算法用于定期的数据链路加密时，每次都分发进化指针也十分麻烦，这时可以采取密钥自进化的办法进行自动更新密钥．密钥更新是根据密钥矩阵自身的信息进行进化，不需要外部输入信息，自进化可以每隔几小时或每天进行．自进化的规则如图４所示，从上一轮密钥中计算出横向特征因子和纵向特征因子，从横向特征因子中提取第１，３，５，７，９，１１，１３，１５字节，从纵向特征因子中提取第２，４，６，８，１０，１２，１４，１６字节，组成共１６字节的数组．将这个数组与密钥矩阵进化深度ｎ进行异或，再用原密钥矩阵加密后作为进化指针和原密钥矩阵一起代入密钥进化算法，从而得到新的密钥，同时密钥矩阵的进化深度加１．与进化深度进行异或运算的目的是保证不陷入僵化矩阵，因为进化深度每次都加ｌ，所以进入基本进化算法的自进化指针不会循环重复．初始密钥的进化深度为０，每进化一次进化深度加１，当然系统必须记住自己的进化深度ｎ．
原矩阵
１－－－纵向特征因子卜Ｊ
＼‘用原矩阵加密ｉ到自进化羹针
’
Ｔ
代人密钥进化算法
图４密钥自进化流程
。
密钥更新过程是一个单向函数，发送方和接收方同步进行密钥更新，只要他们都有相同的初始密钥就可以一直保持同步．初始密钥可以直接采用主密钥，密钥更新的单向性保证了即使密钥序列后面的密钥失窃也不会危害主密钥的安全．如果发生系统丢失数据密钥或进化深度，ｌ的情况（比如系统瘫痪重启），只要由相邻的节点传送当前系统的进化深度，再进行相应次数的密钥进化运算就可以产生新的数据密钥．４
结语
本文在兼顾算法的安全性和效率的基础上，对
ＲＫＭ算法进行了改进，主要包括２个方面：一方面
第１期叶峰，等：置换密钥矩阵加密算法的改进
是提出置换密钥矩阵特征因子子矩阵的概念，将ＲＫＭ算法改进为加、解密完全对称的算法，新的
ＲＫＭ－１Ｉ算法用特征因子子矩阵的查表运算替代
与矩阵特征因子的异或运算，使得加密运算更加非线性化，同时又省去了４个异或步骤，这样就既保证了安全性，又提高了效率；另一方面是在兼顾安全性和效率的基础上，提出一个密钥进化算法，研究了ＲＫＭ．Ⅱ算法的密钥建立、分发与更新，以利于算法的实际应用．
参考文献（Ｒｅｆｅｒｅｎｃｅｓ）
［１］Ｓｃｈｎｅｉｅｒ
Ｂ．Ｄｅｓｃｒｉｐｔｉｏｎｏｆ
ａ
ｎｅｗｖａｒｉａｂｌｅ・ｌｅｎｇｔｈｋｅｙ，
６４－ｂｉｔｂｌｏｃｋ
ｃｉｐｈｅｒ（Ｂｌｏｗｆｉｓｈ）［ｃ］／／ＦａｓｔＳｏｆｔｗａｒｅ
Ｅｎｃｒｙｐｔｉｏｎ，ＣａｍｂｒｉｄｇｅＳｅｃｕｒｉｔｙ
Ｗｏｒｋｓｈｏｐ
Ｐｒｏｃｅｅｄ－
ｉｎｇｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ。１９９４：１９１—２０４．
［２］Ｓｃｈｎｅｉｅｒ
Ｂ．Ｔｈｅｂｌｏｗｆｉｓｈｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍ［Ｊ］．Ｄｒ
Ｄｏｂｂ’ｓ
Ｊｏｕｒｎａｌ，１９９４，１９（４）：３８—４０．
［３］Ｒｉｖｅｓｔ
Ｒ
Ｌ．Ｔｈｅ
ＲＣ５ｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍ［Ｊ］．Ｄｒ
Ｄｏｂｂ＇ｓＪｏｕｒｎａｌ，１９９５，２０（１）：１４６—１４８．
［４］ＤａｅｍｅｎＪ，ＲｉｊｍｅｎＶ．高级加密标准（ＡＥＳ）算法——
Ｒｉｊｎｄａｅｌ的设计［Ｍ］．谷大武，徐胜波，译．北京：清华大学出版社，２００３：３１—５２．
［５］吴文玲，马恒太，冯登国，等．ＡＣ分组密码［Ｊ］．通信
学报，２００２，２３（５）：１３０—１３４．
ＷｕＷｅｎＬｉｎｇ，ＭａＨｅｎｇｔａｉ，ＦｅｎｇＤｅｎｇｇｕｏ，ｅｔａ１．Ｔｈｅ
万
方数据ＡＣ
ｂｌｏｃｋｃｉｐｈｅｒ［Ｊ］．ＪｏｕｒｎａｌｏｆＣｈｉｎａＩｎｓｔｉｔｕｔｅｏｆ
Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００２，２３（５）：１３０—１３４．（ｉｎＣｈｉ・
ｎｅｓｅ）
［６］袁家斌，叶峰．一种全新的基于置换密钥矩阵加密算
法［Ｊ］．南京航空航天大学学报，２００５，３７（６）：７５４—
７５９．
ＹｕａｎＪｉａｂｉｎ，ＹｅＦｅｎｇ．Ａｎｏｖｅｌｅｎｃｒｙｐｔｉｏｎａｌｇｏｒｉｔｈｍｏｆ
ｒｅｐｌａｃｅｋｅｙ
ｍａｔｒｉｘ［Ｊ］．ＪｏｕｒｎａｌｏｆＮａｎｊｉｎｇ
Ｕｎｉｖｅｒｓｉｔｙ
ｏｆＡｅｒｏｎａｕｔｉｃｓ＆Ａｓｔｒｏｎａｕｔｉｃｓ，２００５，３７（６）：７５４—７５９．（ｉｎＣｈｉｎｅｓｅ）
［７］ＳｆｉｎｓｏｎＤ．密码学原理与实践［Ｍ］．冯登国，译．北
京：电子工业出版社，２００３：７８．［８］Ｂａｌｅｎｓｏｎ
Ｄ．Ａｕｔｏｍａｔｅｄ
ｄｉｓｔｒｉｂｕｔｉｏｎｏｆｃｒｙｐｔｏｇｒａｐｈｉｅ
ｋｅｙｓ
ｕｓｉｎｇｔｈｅｆｉｎａｎｃｉａｌ
ｉｎｓｔｉｔｕｔｉｏｎ
ｋｅｙ
ｍａｎａｇｅｍｅｎｔ
ｓｔａｎｄａｒｄ［Ｊ］．ＩＥＥＥＣｏｍｍｕｎｉｃａｔｉｏｎｓＭａｇａｚｉｎｅ，１９８５，
２３（９）：４１—４６．［９］ＬｉＣｅｆｉａ，Ｙａｎｇ
Ｃｕｎｇａｎｇ，ＣｈｅｕｎｇＲｉｃｈａｒｄ．Ｋｅｙｍａｎ－
ａｇｅｍｅｎｔｆｏｒｒｏｌｅｈｉｅｒａｒｃｈｙｉｎｄｉｓｔｒｉｂｕｔｅｄｓｙｓｔｅｍｓ［Ｊ］．
Ｊｏｕｒｎａｌ
ｏｆＮｅｔｗｏｒｋａｎｄＣｏｍｐｕｔｅｒ
Ａｐｐｌｉｃａ矗ｏｎｓ，２００７，
∞（３）：９２０—９３６．［１０］Ｉ．－Ｉａｓｓｅｎ
ＨＲａｇａｂ，ＢｏｕａｂｄａｌｌａｈＡ，ＢｅｔｔａｈａｒＨ，ｅｔａ１．
Ｋｅｙ
ｍａｎａｇｅｍｅｎｔｆｏｒ
ｃｏｎｔｅｎｔ
ａｃ，ｃｅｓｓ
ｃｏｎｔｒｏｌｉｎ
ａ
ｈｉｅｒａｒ－
ｃｌａｙ［Ｊ］．ＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋｓ，２００７，５１（１１）：３１９７—
３２１９．
［１１］ＳｃｈｎｅｉｅｒＢ．应用密码学——协议、算法与Ｃ源程序
［Ｍ］．吴世忠，祝世雄，张文政，等译．北京：机械工业出版社，２０００：２４８．
置换密钥矩阵加密算法的改进
作者：作者单位：刊名：英文刊名：年，卷(期)：
叶峰， 袁家斌， Ye Feng， Yuan Jiabin
南京航空航天大学信息科学与技术学院,南京,210016
东南大学学报（自然科学版）
JOURNAL OF SOUTHEAST UNIVERSITY(NATURAL SCIENCE EDITION)2008,38(1)
参考文献(11条)
1. Li Celia;Yang Cungang;Cheung Richard Key man-agement for role hierarchy in distributed systems[外文期刊] 2007(03)
2. Balenson D Automated distribution of cryptographie keys using the financial institution keymanagement standard 1985(09)
3. Stinson D;冯登国 密码学原理与实践 2003
4. 袁家斌;叶峰 一种全新的基于置换密钥矩阵加密算法[期刊论文]-南京航空航天大学学报 2005(06)5. 吴文玲;马恒太;冯登国 AC分组密码[期刊论文]-通信学报 2002(05)
6. Daemen J;Rijmen V;谷大武;徐胜波 高级加密标准(AES)算法--Rijndael的设计 20037. Rivest R L The RC5 encryption algorithm 1995(01)
8. Schneier B;吴世忠;祝世雄;张文政 应用密码学--协议、算法与C源程序 2000
9. Hassen H Ragab;Bouabdallah A;Bettahar H Keymanagementfor content ac,cess controlin ahierar-clay[外文期刊] 2007(11)
10. Schneier B The blowfish encryption algorithm 1994(04)
11. Schneier B Description of a new variable-length key,64-bit block cipher(Blowfish) 1994
本文链接：http://d.g.wanfangdata.com.cn/Periodical_dndxxb200801003.aspx