同余理论在仿射加密中的应用.doc

同余理论在仿射加密中的应用（西安文理学院 陕西西安 段勇花）摘 要：本文简单介绍了数论中的同余理论在仿射加密中的应用。首先说明了字母与整数的对应，接着介绍了凯撒密码这一简单的加密方法，然后利用同余理论分析了通过明文中字母出现的频率与英文字母本身出现的频率的对应关系。介绍了对明文加密及对密文解密的方法，体现了数论的应用价值。关键词: 明文，密文，仿射加密，同余理论在现在的社会，信息无处不在。在一些情况下，传递信息的人希望他的信息只被特定的接收者知道要说明的内容。那么信息的加密就显得越来越重要了。数论作为一门理论性的学科，在现实生活中的这一领域也显示出了它的实用性。一、了解相关概念明文是一目了然的信息。把这些信息传递给某些人时，要先对明文进行“加密”处理，经加密处理的明文，称之为密文。只有在接收者掌握了一定的方法，才能由密文知道明文的信息。这个信息的传递包括了两个层面。第一，把明文写成密文的方法；第二，解密的方法。二、同余在仿射加密中的应用 首先建立明文与正整数的对应关系。一个文件总是由文字和其他符号组成的，如果用汉语拼音书写汉字，那么，文件就可以用26个拉丁字母和一些符号来表示，假设共个，那么这些符号和个正整数建立了一一对应的关系，例如：ab cdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202122232425那么，你真好（nizhenhao）对应的数字就是130825070413070014.接着给出仿射加密方法。1、选取参数。取大正整数，以及正整数使得，明文满足。2、加密。对于明文计算，就是与对应的密文。3、解密。对于密文，计算。就是与对应的明文。其中.例如：凯撒密码作为一种最为古老的对称加密体制，在古罗马的时候都已经很流行，他的基本思想是：通过把字母移动一定的位数来实现加密和解密。明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例如，当偏移量是3的时候，设符号分别与数字对应，取，对明文中的每一个符号用公式加密。比如对于明文有，依此可得明文ab cdefghijklm密文defghijklmnop明文nopqrstuvwxyz密文qrstuvwxyzabc六点钟（liudianzhong）被加密成olxgldqckrqj.对于密文可用得到明文，例如由此可见，位数就是凯撒密码加密和解密的密钥。再例，假如事先知道信息的每一个字母通过同余公式进行变换，我们试对以下密文进行分析： YFXMPCESPZCJTDFDPQFWQZCPYNTASPCTYRXPDDLRPD首先我们要对密文中每个字母的出现字数进行统计，如下表所示：字母 A B C D E F G H I J K LM次数 1 0 4 5 1 3 00 0 1 0 1 1字母N O P Q R S T U VW X Y Z次数 1 0 7 2 2 2 3 0 0 1 2 3 2“P”是出现频率最高的字母，“C、D、F、T、Y”频率较高。而我们知道“E”是英文信息中出现频率最高的字母，可以猜测密文中的“P”表示明文中的“E”,则则。因此，我们有同余公式以及,可得密文 A B C D E F G H I J K LM 明文 P Q R S T U VW X Y Z A B密文 N O P Q R S T U VW X Y Z明文 C D E F G H I J K LM N O尝试破解密文得到:NUMBERTHORYISUSEFULFORENCIPHERINGMESSAGES通过明文的意思我们知道破解密码正确，如果得到明文的字母混乱，则可以通过密文其他频率较高字母的可能变换来解密。一般的，对于仿射加密方法，只要知道两对（不同的）相对应的明文与密文就可以求出解密方法。若 ，所以 ,用 表示同余方程 的全部解，记 则就可能是中的。当时，这样的只有一组，当时，首先利用删去一些，接着用它们验证是否成立，再用它们试着破译一些密文，就能确定正确的。最后把代入求出，就可得到解密公式。已知有形如的仿射变换来加密信息，试对以下加密信息进行破解：USLELJUTCCYRTPSURKLTYGGFVELYUSLRYXDJURTUULVCUURJRKQLLQLYXSRVLBRYZCYREKLVEXBRYZDGHRGUSLJLLMLYPDJLJTJUFALGUPTGVTJULYUSLDALTJRWUSLJFEOLPU首先我们要对密文中每个字母的出现字数进行统计，如下表所示：字母 A B C D E F G H I J K LM次数2 2 4 4 5 3 61 010 322 1字母N O P Q R S T U VW X Y Z次数 0 1 4 212 7 816 5 1 310 2“L”是出现频率最高的字母，“U”频率次高。而我们知道“E”是英文信息中出现频率最高的字母，其次是“T”,可以猜测密文中的“L”表示明文中的“E”, “U”表示明文中的“T”则，解同余方程组得，可知，则解密变换为可得对应关系如下图所示密文 A B C D E F G H I J K LM 明文 DW P I B U NG ZS L E X密文 N O P Q R S T U VW X Y Z明文 Q J C V O H A TM FY R K即可得明文为：THE BEST APPROACH TO LEARN NUMBER THEORYIS TO ATTEMPT TO SOLVE EVERY HOMEWORK PROBLEM BY WORKING ON THESE EXERCISES A STUDENT CAN MASTER THE IDEAS OF THE SUSJECT通过明文的意思我们知道破解密码的方法是正确的。参考文献：1数论与密码冯克勤著，科学出版社2007,3:61-762数论与应用纪建著，清华大学出版2013,1:217-220Abstract: This paper briefly describes the number theory congruence theory in affine Encryption. First, the corresponding letters and integers, then introduces the simple Caesar cipher encryption method, and then use congruence theory to analyze the relationship between the frequency and alphabetical letters appear by express itself appears frequencies. Describes a method for encryp