密码学中的算法问题及矩阵分析.doc

密码学中的算法问题及矩阵分析【摘要】本文关于密码学之中关于密码的破译，矩阵所起到的决定性的作用，来反映mod算法以及逆矩阵的运用。针对希尔密码以及维吉尼亚密码进行解剖分析，从而得出在密码的破译之中，mod26伴随着逆矩阵共同分解，能够更快更高效地破解密码。【关键词】mod26 逆矩阵 希尔密码 维吉尼亚密码一、利用mod算法进行密码分析在线性代数中，对于一个阶矩阵，如果存在一个阶矩阵，使得，且为阶的单位矩阵，则称矩阵为矩阵的逆矩阵，并记为。例如2阶矩阵，则容易得到它的逆矩阵，。所使用的方法如下：一、 . (其中为的伴随矩阵, 为的行列式的值) ；二、是通过增广矩阵, 在右侧附加一个阶单位矩阵, 再通过初等变换将增广矩阵的左侧变换为一个阶单位矩阵, 这时右侧便是所求的逆矩阵。关于密码学，我们所需要的是密钥矩阵，这里我们举一个例子： 逆矩阵算法公式： 例如密钥矩阵，所以。 知道了矩阵的算法，接下来就要开始从密码入手。我们所研究的是希尔密码，维吉尼亚密码这两大密码。先从第一个希尔密码入手。二、各类密码学算法1.【希尔密码】希尔密码所用到的是Z26字母表。将英文单词中二十六个字母进行编号。如下表ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567891011121314151617181920212223242526我们随意地说出一句话，例如：Good moring.按照上表，可将字母转化为7 15 15 4 13 15 18 9 14 7然后按照矩阵将数字按规律排好，如下7 15 15 4 13 15 18 9 14 77 49 105 105 28 91 105 126 63 98 4915 105 225 225 60 195 225 270 135 210 10515 105 225 225 60 195 225 270 135 210 1054 28 60 60 16 52 60 72 36 56 2813 91 195 195 52 169 195 234 117 182 9115 105 225 225 60 195 225 270 135 210 10518 126 270 270 72 234 270 324 162 252 1269 63 135 135 36 117 135 162 81 126 6314 98 210 210 56 182 210 252 126 196 987 19 105 105 28 91 105 126 63 98 49我们可以看到，希尔密码是将数列排好，依次相乘。得出的横列亦或者数列便是明文。若当我们用普通的算法进行解析的话，估计要算得十分庞大，也抑或寻找不到其中的规律，如果用Mod算法则容易得多。这是使用正矩阵的，而逆矩阵的使用算法则更加容易。假设密文为“FOAOESWO” FO AO ES WO 6 1 5 23 15 15 19 15 ，所以密文“FOAOESWO”的明文为“WEREDONE”由此我们可见mod算法与逆矩阵的效用，接下来是第二个密码的分析。2.【维吉尼亚密码】 频率的分析可以很好地打破密码的禁锢，然而，维吉利亚密码将密钥与矩阵相结合，创造出了新的密码，从中进行剖析。加密算法：例如密钥的字母为d，明文对应的字母b。根据字母表的顺序d=4,b=2，那么密文就是d+b-1=4+2-1=5=e，因此加密的结果为e。解密即做此逆运算。 加密公式：密文=(明文+密钥)Mod26-1 解密公式：明文=26+(密文-密钥)Mod26+1 假如对如下明文加密： tobeornottobethatisthequestion 当选定“have”作为密钥时，加密过程是：密钥第一个字母为h，明文第一个为t，因此可以找到在h行t列中的字母a，依此类推，得出对应关系如下： 密钥：havehavehavehavehavehavehaveha 明文：tobeornottobethatisthequestion 密文：aowivrisatjfltceainxoelylsomvn 维吉利亚密码的特点便是将密钥矩阵和mod26的算法很好地融合在一起。也因而，如果要破解这一密码的话，要从矩阵以及mod26算法入手。3.【凯撒密码】 也称凯撒移位，是最简单的加密方法之一，相传是古罗马恺撒大帝用来保护重要军情的加密系统，它是一种替代密码。 加密公式：密文=(明文+位移数)Mod26 解密公式：明文=(密文-位移数)Mod26 例如J DBO只需把每个字母都按字母表中的顺序依次后移一个字母即可A变成B，B就成了C，依此类推。因此明文为： I CAN。英文字母的移位以移25位为一个循环，移26位等于没有移位。所以可以用穷举法列出所有可能的组合。 例如：phhwphdiwhuwkhwrjdsduwb 所以可以翻译得到的明文为：kccrkcydrcprfcrmeynyprw lddsldzesdqsgdsnfzozqsx meetmeafterthetogapartynffunfbgufsuifuphbqbsuz oggvogchvgtvjgvqicrctva 可知明文为：meetmeafterthetogaparty 三、总结解析通过上述的举例我们可以发现，矩阵在密码学之中至关重要。在使用Mod算法进行加密的同时，利用矩阵，可以清晰的得到答案。例如前面3提到的凯撒密码，所使用的矩阵：A B C D E F G H I J K L M N O P Q R S T U V W X Y ZA -A B C D E F G H I J K L M N O P Q R S T U V W X Y ZB -B C D E F G H I J K L M N O P Q R S T U V W X Y Z AC-C D E F G H I J K L M N O P Q R S T U V W X Y Z A BD- D E F G H I J K L M N O P Q R S T U V W X Y Z A B CE- E F G H I J K L M N O P Q R S T U V W X Y Z A B C DF- F G H I J K L M N O P Q R S T U V W X Y Z A B C D EG- G H I J K L M N O P Q R S T U V W X Y Z A B C D E FH- H I J K L M N O P Q R S T U V W X Y Z A B C D E F GI- I J K L M N O P Q R S T U V W X Y Z A B C D E F G HJ- J K L M N O P Q R S T U V W X Y Z A B C D E F G H IK- K L M N O P Q R S T U V W X Y Z A B C D E F G H I JL -L M N O P Q R S T U V W X Y Z A B C D E F G H I J KM- M N O P Q R S T U V W X Y Z A B C D E F G H I J K LN- N O P Q R S T U V W X Y Z A B C D E F G H I J K L MO- O P Q R S T U V W X Y Z A B C D E F G H I J K L M NP- P Q R S T U V W X Y Z A B C D E F G H I J K L M N OQ- Q R S T U V W X Y Z A B C D E F G H I J K L M N O PR- R S T U V W X Y Z A B C D E F G H I J K L M N O P QS- S T U V W X Y Z A B C D E F G H I J K L M N O P Q RT- T U V W X Y Z A B C D E F G H I J K L M N O P Q R SU- U V W X Y Z A B C D E F G H I J K L M N O P Q R S TV- V W X Y Z A B C D E F G H I J K L M N O P Q R S T UW- W X Y Z A B C D E F G H I J K L M N O P Q R S T U VX- X Y Z A B C D E F G H I J K L M N O P Q R S T U V WY- Y Z A B C D E F G H I J K L M N O P Q R S T U V W XZ- Z A B C D E F G H I J K L