第１８卷第２期 电 脑 与 信 息 技 术 Ｖ０１．１８ Ｎｏ．２ ２ ０ １ ０年４月 Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ Ａｐｒ．２０１０ 文章编号：１００５—１２２８（２０１０）０２－００３１—０３ Ｈｉｌｌ密码加密解密时矩阵的求法 徐小华，黎民英 （南华大学计算机学院，湖南衡阳４２１００１） 摘要：在计算机网络中，为了保证数据的安全，常常要对数据进行加密和解密。文章运用数学知识和Ｍａｄａｂ语言，介绍了 Ｈｉｌｌ密码加密时如何给出密钥矩阵以及解密时如何求密钥矩阵的逆，从而实现Ｈｉｌｌ密码快速加密和解密。 关键词：Ｈｉｌｌ密码；加密；解密；Ｍａｔｌａｂ ７．０ 中图分类号：ＴＰ３０９．７ 文献标识码：Ａ Ｔｈｅ Ｓｏｌｕｔｉｏｎ ｏｆ Ｍａｔｒｉｘ ｏｆ Ｈｉｌｌ Ｃｉｐｈｅｒ ｉｎ Ｅｎｅｒｙｐｔｉｏｎ ａｎｄ Ｄｅｅｒｙｐｔｉｏｎ ＸＵ Ｘｉａｏ－ｈｕａ ＬＩ Ｍｉｎ－ｙｉｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ．Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｏｕｔｈ Ｃｈｉｎａ，Ｈｅｎｇｙａｎｇ ４２１００１，Ｃ｝血１ａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｅｎｓｕｒｅ ｄａｔａ ｓｅｃｕｒｉｔｙ ｉｎ ｔｈｅ ｃｏｍｐｕｔｅｒ ｎｅｔｗｏｒｋ，ｐｅｏｐｌｅ ａｌ＇ｅ ｌｉｋｅｌｙ ｔｏ ｅｎｃｒｙｐｔ ａｎｄ ｄｅｃｒｙｐｔ ｄａｔａ．Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｋｅｙ ｍａｔｒｉｘ ｏｆ Ｈｉｌｌ Ｃｉｐｈｅｒ ｉｎ ｅｎｃｒｙｐｔｉｏｎ ａｎｄ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｉｎｖｅｒｓｉｏｎ ｏｆ ｔｈｅ ｋｅｙ ｍａｔｒｉｘ ｉｎ ｄｅｃｒｙｐｔｉｏｎ ｂｙ ｍａｔｈｅｍａｔｉｃａｌ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｔｈｅ Ｍａｄａｂ ｌａｎｇｕａｇｅ ｔｏ ａｃｈｉｅｖｅ ｔｈｅ ｐｕｒｐｏｓｅ ｑｕｉｃｋｌｙ． Ｋｅｙ ｗｏｒｄｓ：Ｈｉｌｌ ｃｉｐｈｅｒ；ｅｎｃｒｙｐｔｉｏｎ；ｄｅｃｒｙｐｔｉｏｎ；Ｍａｄａｂ ７．０ 在计算机网络或军事情报中，为了保证数据的安 中 ｅｌ＝（Ｋｌｌｍｌ＋Ｋｌ２Ｉｎ２＋…＋ＫｌＪｉ，ｌｌ１）ｍｏｄ２６ 全，常常要对数据进行加密和解密。对数据进行加密的 ｃ２＝（Ｋ２ｌｍｌ＋ｋ２２ｍ２＋…＋Ｋ ｍ１）ｒｏｏｄ２６ 方法很多，Ｈｉｌｌ密码是其中一种。Ｈｉｌｌ密码加密时就是 利用非退化的密钥矩阵Ｋ在模２６的意义下进行线性 ｃＦ（Ｋｌｌｍ１＋Ｋ唧２＋…＋Ｋｎｍ１）ｒｏｏｄ２６． 变换，解密时就是利用密钥矩阵Ｋ的逆矩阵 在模 或写成ｅ＝ＫＭ ｒｏｏｄ ２６ ２６的意义下进行线性变换。但是同学们在作业时，随 其中 便给一个非退化的密钥矩阵Ｋ，对明文加密没问题，但 ｍｌ 解密时，由于在通常的数学意义下，密钥矩阵Ｋ的逆 Ｃ２ ｍ２ 矩阵Ｋ 有可能是分数，有可能在模２６的意义下无整 Ｍ ，Ｍ＝ Ｍ 数解，往往得不出正确的明文。为保证解密时得出正确 明文，本人通过长期的计算与思考，给出加密时如何求 解密时得明文Ｍ：Ｍ＝Ｋ ｅｍｏｄ２６ 出合适的密钥矩阵以及解密时如何求密钥矩阵的逆的 其中ＫＫ—ｍｏｄ ２６＝１，Ｉ为数学中的单位矩阵。 一些方法。 ２ Ｈｉｌｌ密码加密解密算法实例分析 １ Ｈｉｌｌ密码算法介绍 由于明文、密文一般都是正整数，故密钥矩阵Ｋ Ｈｉｌｌ加密算法的基本思想是将１个明文字母通过 及其逆矩阵 的元素都应该是正整数，不能是负整 线性变换，将它们转换为１个密文字母。解密只要作一 数、分数或小数。当密钥矩阵Ｋ的行列式的值等于±１， 次逆变换就可以了。密钥就是变换矩阵本身。即设明文 即Ｉ Ｋ Ｉ＝±１时，由数学知识可知，密钥矩阵Ｋ的逆矩阵 为Ｍｍｍ。ｍ …ｍ。，经过线性变换得密文Ｃ＝Ｅ （Ｍ）＝ 的元素是整数，若密钥矩阵Ｋ的逆矩阵Ｋ 的元素 Ｃ１Ｃ２…Ｃ ｏ 有负整数，再对逆矩阵的所有元素加２６的若干倍，再 模２６，可保证密钥矩阵Ｋ的逆矩阵Ｋ 的所有元素为 收稿日期：２００９—１２—２２ 作者简介：徐小华（１９６６一），男，湖南衡阳人，副教授，从事《计算机密码学》教学和研究；黎民英（１９６３一），女，湖南衡阳人，副教授，从事计算机应用专业 课程教学和研究。 电 脑 与 信 息 技 术 ２０１０年４月 正整数，密文解密后可得正整数明文Ｍ，与原明文Ｍ １８ １８ ７ ２ 相同。下面介绍加密时如何求出合适的密钥矩阵以及 ２５ ２Ｏ １０ １０ 解密时如何求密钥矩阵的逆的方法。 Ｋ２＝ １３ １４ ２６ ７ 为求出合适的密钥矩阵Ｋ，在一个ｎ×ｎ阶矩阵中 ５ ５ ４ ６ （如４×４阶矩阵中），任设二元素的值为ｘ、Ｙ，其余元素 １ ０ ０ Ｏ 给出具体的正整数数字。并令其行列式的值等于＋１ １ Ｏ Ｏ 或一１，可得一个二元一次或二元二次不定方程，可求 不难验汪Ｋ＇Ｋ２ ｒｏｏｄ ２６＝ ０ ０ ０ ｌ Ｏ 其正整数解。现举几例加以说明。 ０ Ｏ ０ ｌ ４ Ｘ ８ Ｙ 故矩阵Ｋ２就是密钥矩阵Ｋ的逆矩阵 。现用密 例１如取Ｋ＝ １２ １ ６ ９ ３ ６ ４ ６ 令ｌ Ｋ ｌ＝１ 钥矩阵Ｋ加密，用Ｋ２解密。 输入明文Ｍ的值：＞＞Ｍ＝［７，１４，１２，４］’ ２ １１ ３ ８ 用＞＞Ｃ＝ｍｏｄ（Ｋ＊Ｍ，２６）命令对明文Ｍ加密得密文 得：一ｉ０５ｘ＋１８７ｙ＝７６１，可参考２００８年１２月出版的 Ｃ＝［２０，２４，２１，２１， 《计算机技术与发展》杂志第１７３页“二元一次不定方 故得密文Ｃ＝ｕｙｖｃ。 程整数解之程序求法”一文，借助其Ｍａｉｆａ／）语言程序 用＞＞ｒｏｏｄ（Ｋ２＊Ｃ，２６）命令对密文Ｃ解密得明文 解之得一正整数解：ｘ＝７，ｙ＝８。 Ｍ＝【７，１４，１２，４］＇ 、 ４ ７ ８ ８ 故得明文Ｍ＝ｈｏｍｅ，解密正确。 １２ １ ６ ９ 现取Ｋ＝ ３ ６ ４ ６ 对明文Ｍ＝ｈｏｍｅ ２ １１ ３ ８ 例２如取Ｋ＝ 令ｌＫ ｌ一１ 加密和解密。 若采用从ａ到ｚ的２６个字母依顺序从０到２５编 得：一１２ ３ １ １０＋１８９ｘ＋１４ ９ ５ｙ一２ｘｙ＝一１，可借助如下Ｍａｔｌａｂ 号，编号如下表格。 语言程序解之，因要求ｘ，５ ７ ２ ４ Ｙ都为正整数，故取ｘ，ｙ的范 Ｏ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ 围为０到１Ｘ ８ ０００，３ ６ 范围可以变化，能求到解就好。程序如 ７ ｙ ５ ３ ｂ ｄ ｅ ｆ ｇ ｈ ｌ● Ｊ ｋ Ｉ ｍ 下： ｆｏｒｘ＝０：１０００ － １３ １４ ｌ５ １６ １７ ｌ８ １９ ２０ ２１ ２２ ２３ ２４ ２５ ｏｆｒ ｙ＝Ｏ：ｌＯ００ ０ ｐ ｑ ｒ Ｓ ｔ ｗ Ｘ ｙ ｉｆ（ｌ（－１１１０＋１８９ ｘ＋１５ ｙ－２ ｘ ｙ）＝－－１） 明文Ｍ＝ｈｏｍｅ可分别得数字化后４个数字： ｎｔｆ（’ｘ＝％ｄ，ｙ＝％ｄｋｎ‘’］【，ｙ）； ７，１４，１２，４，即Ｍ＝［７，１４，１２，４］’。现利用Ｍａｔｌａｂ语言求解 ｂｒｅａｋ； ｅｎｄ 密钥矩阵Ｋ的逆矩阵 及加密和解密。 ｅｎｄ 设置为有理格式：＞＞ｆｏｒｍａｔ ｒａｔ ｅｎｄ 输入矩阵Ｋ的值：＞＞Ｋ＝［４ ７ ８ ８；１２ １ ６ ９；３ ６ ４ ６；２ 解之得－－ｔ整数解：ｘ＝８，ｙ＝４０３。 １１ ３ ８］； ２ ５ ７ 用＞＞ｄｅｔ（Ｋ）命令验证矩阵Ｋ的行列式的值为１ ３ ７ ４０３ 用＞＞Ｋ１＝ｉｎｖ（Ｋ）命令从数学角度求矩阵的逆Ｋｌ 现取Ｋ： ４ ２ ５ 对明文Ｍ＝ｈｉｌｌ加密 一１ｌ２ －３４ ３７１ －１２８ ９ ４ ３ －１０５ －３２ ３４８ －１２０ Ｋ１＝ 和解密。 －３９ －１２ １３０ －４５ 若采用从ａ到ｚ的２６个字母依顺序从Ｏ到２５编 号，编号如例１。Ｍ可分别得数字化后４个数字： 由于它的元素出现负整数，故把它的每一个元素 ７，８，１１，ｌｌ，即Ｍ＝［７，８，ｌｌ，１１］’。现利用Ｍａｔｌａｂ语言求 加上２６的若干倍，使它的元素全为正整数，再模２６。 解密钥矩阵Ｋ的逆矩阵Ｋ 及加密和解密。 用＞＞Ｋ２＝ｍｏｄ（Ｋ１＋２６００，２６）命令得： 设置为有理格式：＞＞ｆｏｒｍａｔ ｒａｔ 第１８卷第２期 徐小华等：Ｈｉｌｌ密码加密解密时矩阵的求法 ・３３・ 输入矩阵Ｋ的值：＞＞Ｋ＝［２ ５ ８ ７；３ ７ ８ ４０３；４ ２ ３ ５； ９４ ６ ３】； 事实上仿例ｌ解之，方程虽有很多解，但ｘ，Ｙ不可 能同为正整数，取一组整数解：ｘ＝２１Ｉ，ｙ＝－４６。 ４ ２１１ 用＞＞ｄｅｔ（Ｋ）命令验证矩阵Ｋ的行列式的值为一１． 用＞＞Ｋｌ＝ｉｎｖ 命令从数学角度求矩阵Ｋ的逆 Ｋ１． ７ ２ －４６ ６ ，得矩阵Ｋ＝ ９ １３ １１ １Ｏ ３ １４ ８ ｌ２ １６ ｌ５ 由于矩阵 ３５ ７ －８２８ ３５８ 中出现负元素，可能导致密文中出现负数。故此矩阵不 —１ｏｏ８ ２０１ －－２３７７８ １０２７７ Ｋ１＝ ６１７ １２３ —１４５５１ ６２８９ ５ １ —１１８ ５１ 由于它的元素出现负整数，故把它的每一个元素 加上２６的若干倍，使它的元素全为正整数，再模２６。 用＞＞Ｋ２＝ｍｏｄ（Ｋ１＋２６０００，２６）命令得： ９ ７ ４ ２Ｏ ６ ７ １４ １９ Ｋ２＝ １９ １９ ９ ２３ ５ ｌ １２ ２５ Ｏ ０ 不难验证Ｋ＇Ｋ２ ｍｏｄ ２６＝ ０ １ 故矩阵Ｋ２就是密钥矩阵Ｋ的逆矩阵 。现用密 钥矩阵Ｋ加密，用Ｋ２解密。 输人明文Ｍ的值：＞＞Ｍ＝［７，８，１１，１１］’ 用＞＞Ｃ＝ｍｏｄ Ｍ，２６）命令对明文Ｍ加密得密文 Ｃ＝【ｌｌ，２２，２，ｌ２】’ 故得密文Ｃ＝１ｗｃｍ。 用 ＞ｒｏｏｄ（Ｋ２＊Ｃ，２６）命令对密文Ｃ解密得明文 Ｍ＝［７，８，１１，１１］’ 故得明文Ｍ＝ｈｉｌｌ，解密正确。 但下列矩阵不适合Ｈｉｌｌ密码加密和解密。 ４ Ｘ ７ Ｙ ２ 例３如取矩阵Ｋ＝ ９ ｌＯ ６ １３ ３ ８ １６ ＋Ｉ Ｋ Ｉ：１ ｌ１ １４ ｌ２ １５ 得：２７８ｘ＋１０６６ｙ＝９６２２，由方程图形易知此方程的 解不可能同为正整数。 适合Ｈｉｌｌ密码加密和解密。 ２ ５ ｘ ３ ７ ９ １ ２ ３ 令ｌ Ｋ Ｉ＝±１ ９ ４ ６ 得：一１７６４＋２５２ｘ＋１０５ｙ一１４ｘｙ＝±１，仿例２解之，经 过计算，这样的方程无正整数解。也可用数学方法证明 这样的方程无正整数解。 ３结束语 在运用Ｈｉｌｌ密码加密时，密钥矩阵Ｋ不是随便给 的，它是符合一些条件的。如果随便给一个矩阵作为密 钥矩阵Ｋ加密，那利用密钥矩阵Ｋ的逆矩阵Ｋ一－解密， 结果有可能不正确。因此必须寻找正确的方法求密钥 矩阵Ｋ及其逆矩阵Ｋ～。 本文介绍了当行列式的值等于±１的密钥矩阵Ｋ 及其逆矩阵 的求法，在矩阵Ｋ中任设两个变量元 素，其余元素任给，令其行列式的值等于±１，再求其正 整数解。如果没有正整数解，再给定元素的值。重复上 述解法，就能很容易求出密钥矩阵Ｋ及其逆矩阵 ， 从而实现Ｈｉｌ密码快速加密和解密。 参考文献： 【１】卢开澄．计算机密码学【Ｍ】．清华大学出版社，２００３． ［２】张智星．ＭＡＴＬＡＢ程序没汁与应用 清华大学出版社，２００Ｚ 【３】周金萍，王冉，吴斌．ＭＡＴＬＡＢ６实践与提高【Ｍ】．中国电力出版社， ２ＯＯ２． 苏金明，王永利．ＭＡＴＬＡＢ７．０实用指南（上册）【Ｍ１．电子工业出版 社，２００４． 【５】 徐小华．二元一次不定方程整数解之程序求法【ｚ】．计算机技术与发 展。２００８。１８（１２）：１７３—１７４． 潘承洞，潘承彪．简明数论［ＭＪ．北京大学出版社，１９９８．