代数在密码学中的应用*

付 丽,丁 慧

(绥化学院 信息工程学院,黑龙江 绥化 152061)

代数在密码学中的应用*

付 丽,丁 慧

(绥化学院 信息工程学院,黑龙江 绥化 152061)

矩阵的初等变换是线性代数的重要内容，而密码学中很多经典的密码及其编码与解密的方法，都要用到矩阵及初等变换，如棋盘密码、希尔密码、凯撒密码、Walsh谱等.

棋盘密码;希尔密码;凯撒密码;Walsh谱

1 引言

二战期间，一些优秀的数学家，包括著名数学家图灵等对己方信息的加密和对敌方信息的破译工作做出了突出贡献.目前密码学的应用不再局限于军事、政治和外交，而扩大到商务、金融和社会各个领域，特别是全球范围的互联网的出现和发展，为人们提供了快捷、高速和廉价的通信，大量敏感信息常常要通过互联网进行交换.现代电子商务也是以互联网为基础，人们十分关心在网络上交换信息的安全性.因此在计算机安全方面研究了数据库保密和保密数据库的攻击问题，形成了一个广阔的研究领域.数学在密码学中具有重要的地位，线性代数、概率论与数理统计、数论等知识都是对密码进行加密和解密的常用工具.

表1 码字表

2 矩阵在密码学中的简单应用

我们把消息称为明文.用某种方法伪装消息以隐藏它的内容的过程称为加密.加了密的消息称为密文.把密文转换成明文的过程称为解密.无论是加密还是解密的过程都会用到代数学的知识.例如可逆矩阵可用来对需要传输的信息加密，首先要给每个字母指派一个码字(如表1).[1]

如果直接发送矩阵B，这是不加密的信息，容易被破译，无论军事或商业上均不可行，因此必须对信息予以加密，使得只有知道密钥的接收者才能准确、快速破译.为此，可以取定3阶可逆矩阵A，并且满足A的元素均为整数；|A|=±1，这样A-1的元素也均为整数.令C=AB(即对B做线性变换)，则C是3×4矩阵，其元素也均为整数.现发送加密后的信息矩阵C，己方接收者只需用A-1(即对C做线性变换)进行解密，就得到发送者的信息：B=A-1C.

2.1 棋盘密码[2]

棋盘密码产生于公元前两世纪的希腊，相传是世界上最早的一种密码.简单的来说就是把字母排列好，用坐标的形式表现出来.字母是密文，明文便是字母的坐标.常见的排列方法：

从这个密码诞生开始表中i和j就在同一格中.每个字母对应一个二元有序组ij，i是字母所在行号，j是所在的列号.这是一个比较常用的排列方法.不同的国家有不同的排列法.举个例子school，加密后就是43 13 23 31 34 34 31.

另一种常见的排列法ADFGX：

这里字母的顺序打乱了，但与前面一种相同的是i和j视为同一个字，使字母数量仍符合5×5格.

第一次世界大战将要结束时，法军截获了一份所有单词都由A、D、F、G、X五个字母拼成的德军电报，因此被称为ADFGX密码.1918年3月德军上校FritzNebel发明了ADFGX密码，其是结合了Polybius密码和置换密码的双重加密方案.还是上面那个例子school，使用这个表格加密，就是FGGFDDDFDFAG.但由于ADFGX的加密法发送含有大量数字的简短信息.1918年6月又加入了一个字符V对ADFGX进行扩充，变成了共36个字符的6×6格的加密，这就是ADFGVX.这使得数字0到9以及所有英文字母(不再将i和j视为同一个字)都可以混合使用.

2.2 希尔密码

希尔密码是1929年提出的一种密码体制，主要思想是利用矩阵的线性变换方法，运用基本矩阵论原理的替换密码.每个字母当作26进制数字：A=0,B=1,C=2…一串字母当成n维向量，跟一个n×n的矩阵相乘，再将得出的结果模26.用作加密的矩阵(即密匙)必须是可逆的，否则就不可译码.只有矩阵的行列式和26互质，才是可逆的.在希尔密码中，密钥是一个可逆的m×m方阵，m表示分组的大小.如果把密钥矩阵称为A，矩阵的每个元素就是aij.

把明文中每个分组中的m字符称为b1,b2,…,bm，相应的密文中的字符称为c1,c2,…,cm，则加密算法为

c1=b1a11+b2a21+…+bmam1(mod26)，

c2=b1a12+b2a22+…+bmam2(mod26)，

…………,

cm=b1a1m+b2a2m+…+bmamm(mod26)，

这样可以利用矩阵对整个明文进行加密，如果明文就是一个l×m的矩阵，l为分组数，m表示分组的大小.

这就是用希尔密码进行加密和解密的一个简单的例子.实际应用中，用于加密的可逆矩阵A的阶数可能很大，其构造也十分复杂，同时密码的编制还有许多其他方法.

2.3 凯撒密码

凯撒密码是一种代换密码.他的基本思想是：通过把字母移动一定的位数来实现加密和解密.明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文.若将26个字母分别对应于0,1，…，25，则凯撒密码加密变换可以看做矩阵的加法再模26的计算:ci≡mi+k(mod26),i=1,2,…,n.其中M=(m1.m2,…,mn)是明文对应的数据矩阵，C=(c1,c2,…,cn)是与之对应的密文数据矩阵，k=(k1,k2,…,kn)是密钥数据矩阵.例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推X将变成A，Y变成B，Z变成C.由此可见，位数就是凯撒密码加密和解密的密钥.

若明文为Iwishyouhappiness,对应的数据矩阵为(9,0,23,9,19,8,0,25,15,21,0,8,1,16,16,9,14,5,19,19)，密钥矩阵为(3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3)，则密文为lczlvkcarxckdsslqhvv.

2.4Walsh谱[4]

称为f(x)的第一种谱或Walsh谱.

定理1S(f)(w)与Sf(w)关系如下：

定理2 设x=(x1,…,xn)，w=(w1,…,wn)∈GF(2)n，f(x)是n元布尔函数，

则

3 结论

虽然在密码学中运用的代数知识都比较简单，但足以看出代数是一个重要的工具，它的应用是十分广泛的，特别是矩阵的知识.所以老师在进行这部分教学时，应该讲解一些应用的实例，这样不仅能提高学生学习的兴趣，使学生在学习中体会到所学知识在解决问题中可以发挥巨大作用，也能逐渐增强学生应用数学解决实际问题的意识，提高学生应用数学知识解决问题的能力.

[1]吴香华,熊萍萍,朱连华.线性代数教学中的一点体会[J].科技创新导报,2009(36).

[2]汤燕.矩阵在密码学中的应用[J].科教文汇,2010(08).

[3]刘木兰.数学在密码中的某些应用[J].数学的实践与认识,1986(03).

[4]周建钦.密码学中的线性变换[J].电子科技大学学报,2007(1).

[5]章照止.现代密码学基础[M].北京:北京邮电大学出版社,2004.

(责任编辑:王宏志)

2013-12-10

付丽(1982-),女,黑龙江绥化人,讲师.

绥化学院青年基金项目(项目编号：QK1103002).

O

A

1008-7974(2014)01-0029-03