《利用函数表示求解vigenere加密系统》由会员分享，可在线阅读，更多相关《利用函数表示求解vigenere加密系统（16页珍藏版）》请在金锄头文库上搜索。
1、利用函数表示求解 Vigenere 加密系统 利用函数表示求解 Vigenere 加密系统 利用函数表示求解 Vigenere 加密系统 作 者：王郑耀（理学院 信息与计算科学 92 班 99092050） 指导教师：程正兴(教授) 吴云江(副教授) 摘 要 作为一个学习信息与计算专业的学生，用计算数学的方法理论来研究信息论中的问题当然是很有意义的！ 本文就在信息论学习中遇到的 Vigenere 加密系统的解密问题， 经过数学的抽象， 经过概率统计意义下转化和连续化处理,转化为函数表示理论领域中的问题。然后对于这个函数表示的问题进行分析、处理，找到密钥的性质和特征。最后利用多次快速傅里叶变换提
2、取出上述特征。 这种算法与原来书上算法相比有以下优势： 1） 没有构造原来算法所必需的统计量，也就不用计算统计量，避免了很多烦杂的计算；2）由于有快速算法，所以速度很快！3）直观，简单易懂。由于所学知识的限制，对于密钥长度较大时的,Fourier 变换所造成的干扰尚无法排除.此外,在离散处理时从图形上看起来很清晰的结果尚不能用统一的公式利用计算机得到. 这个算法与原来算法的差别的本质在采用了快速算法。在统计中使用快速算法尚没有得到统计界重视，这应当是统计学的一个发展方向！ 2002 年 9 月 1 日 A n d y数字签名人A n d y D N：c n = A n d y , o = Sc
3、 i e n c e c o l l e g e o f Xj t u , c = CN 日期：2 0 0 3. 0 2 . 15 14: 31: 44 + 0 8 0 0 签名未 验证利用函数表示理论求解 Vigenere 加密系统加密系统 1.问题的背景及问题的提出 1.问题的背景及问题的提出 1.1.加密: 1.1.加密: 为了说清楚 Vigenere 加密系统，我们先讲讲加密。 考虑下面这个例子，假设甲国派一个间谍 A 到乙国去执行任务。现在的问题是 A 怎样和指挥部怎样联系？为了安全， 他不可能带什么专用的工具；但是他可以利用乙国的民用设施往指挥部发消息并接受指挥部的指示；但是这就意
4、味着他与指挥部的通讯几乎是公开的，可以被任何人知道。这就需要加密。再考虑我们在抗战影片或解放战争的影片中常见的镜头，比如说“渡江侦察记“中解放军的先遣小分队带着发报机潜入敌人军事禁区侦察，并用发报机把消息报告给指挥部；这时发报内容有一个加密的问题，否则被国民党截听后就成了公开的秘密。 那么怎样加密呢？对汉语来说， 每个字你都可以查到邮局电报系统的汉字代号（常用汉字） ，比如说（国内电报通信） ： - 软 件 加 密 6516 0115 1378 4316 - 有了这些代码，邮局的工作人员先把你要发电报的汉字翻译成代码，然后按照一定的规则用“点划线”发到接收地去。另一边的邮局人员再按照相反的过程
5、就可以解码成汉字。因此，只要我们对每一个汉字的代码再做一个可逆的变换。变成另外一组数据，那么即使对方收到这组信息，他也1利用函数表示理论求解 Vigenere 加密系统加密系统 无法知道电报的内容。 以下我们主要谈谈英语的加密与解密，他们的原理都是差不多一样的。 下面这是江泽民总书记 2002.5.28 日的一段讲话的英文翻译： “Civil affairs work is of great significance in guaranteeing the basic livelihood of people in difficulty, maintaining social stabilit
6、y and supporting national defense and military modernization, he said.” 去掉标点符号后就变成： ”civilaffairsworkisofgreatsignificanceinguaranteeingthebasiclivelihoodofpeopleindifficultymaintainingsocialstabilityandsupportingnationaldefenseandmilitarymodernizationhesaid”（这段文字以下我们看记做字符串 S） ，对于一个英语国家的人来说或者对英语十分熟悉
7、的人来说：没有标点他也是可以理解的。作为一种加密规则，我们可以这样做：对上文作如下可逆变换（注意是可逆的） ： 每个字母向后平移一个字母：即 ba ，d， cb dc ezy az 则字符串 S 编为字符串 S1： S1“djwjmbggbjstxpsljtpghsfbutjhojgjdbodfjohvbsbouffjohuifcbtjd mjwfmjippepgqfpqmfjoejggjdvmuznbjoubjojohtpdjbmtubcjmjuzboetvqqpsujohobujpobmefgfotfboenjmjubsznpefsojabujpoiftbje“； 显然， 这样一来如果不知
8、道是加密的或者不知道密码就看不懂了。 但是，自己人可轻而易举利用密码知道消息或传达任务。 显然，上述这种类型的加密方式有很多，平移 2，3，4，N，2利用函数表示理论求解 Vigenere 加密系统加密系统 都可行；但是，事实上只有 25 种，这就叫 Caesar 加密方式。 这种加密方式人类最早使用，但是他的缺点也是显然的。容易破解。简直太简单了。 1.2. Vigenere 加密系统 1.2. Vigenere 加密系统 显然像 1.1 中那样的可逆的变换太多了。 我们随手就可以举出许许多多很麻烦的，让对手很难破解或者几乎不可能破解的加密方式（比如说规定第一个字母加 4，第二个字母加 9，
9、这种一字一密可以证明是不可能破译的） 。但是，对间谍 A 来说，他不可能带着密码本的，密码过于麻烦对自己也不利。 实用的密码要满足以下几个要求： 1） 系统的保密期内，破解起来很不容易； 2） 加密解密的方法（密钥）易于记忆； 3） 规则简单，不麻烦通讯者。 所以一个比较折衷的方法就是 Vigenere 加密系统。就是把一个相对较短的密钥，周期延拓为一个无限长密钥，对明文进行加密。 举个例子: 还是对于字符串 S，我们可以选用“2677078”作为密钥。我们先把“2677078”作周期扩展“26770782677078267707826770782677078” 利用这个无限长密码我们就可以对
10、任何一个字符串进行逐字加密。第一个字母平移 2，第二个字母平移 6，第三个字母平移 7，第四个字母平移 7，对字符串 S 加密，得到字符串 S2： S2“eocplhnhgpysdwtqpzomotkhaspopompchvekpugbitguaelqpmaoei 3利用函数表示理论求解 Vigenere 加密系统加密系统 iuojsicmnoovokwhvlvpsmktkpfmqeasaytiktahiuqpmzvcpinyahbptkzfhnkawvwvraqpmuhtpwpgskemmpylhnkukrpaaygouklruqbgapoupgyhpd” ； 显然，这种加密方式破解起来要比
11、 Caesar 加密方式的破解要难。你必须知道原始密钥是几位，比如上边就是七位。即使你知道，你还得知道这个七位数是什么？比如上边是“2677078” 。 假设你是乙国的安全工作人员，你截获了 A 与甲国的一段电文，如下边字符串 SS: SS“ktaoizkqtjpslbgdaahliwzovrzxtucpdlaqrpkfvcpjhaivvuzvahlbjkv yypvrgyaijcngyhchzglbsauinezpsvnvnlxuhvvatjiykwoatokmngukcvdgxzlllkvkkaowqeypudlxvnzvmlwhzolrlawrazhhdgtvaawxggyldltukd
12、oeymynpsevbjkyzitxtucloumzozaiuoyuyrspverbkekitkhjotxnkalpywqlvmtomuusvvhgmoahecbjkvyetekzohcjctgalasoqxpahtkqswseeqveivuulugwwrvfkshaivvqlbuiaitevweyivuyzbfkkxjbiaaqlkvuitarvnayqvntpckmrzohmvviuaoeyqpzlyezbktnaowqeyhyeawtojjokmuguktomkxyllhbkuuaoapggufouirvyvajpvuxbaubwsjvmwcvoun“（原文是摘自美国数学会网站的一个书评
13、。 ） 你的任务就是怎样破解它？！ 当然这里假定你知道这一定是用 Vigenere加密系统加密的。 1.3 解密 1.3 解密 谈到解密，就要先说说信源分布。 在我们这里，信源就是指 26 个字母。因为我们面对的字符串 SS 中每一个字母就是从这 26 个字母组成的集合中取出的。信源分布就是指这 26 个4利用函数表示理论求解 Vigenere 加密系统加密系统 字母的自然分布，或者说人们从大量文章中经过统计得出的各个字母的分布。下面这个就是一个比较好比较常用的信源分布： A B C D E F G H I J K L M 0.0856 0.0139 0.0279 0.0378 0.13040
14、.02890.01990.05280.06270.0013 0.0042 0.03390.0249N O P Q R S T U V W X Y Z 0.0707 0.0797 0.0199 0.0012 0.06770.06070.10450.02490.00920.0147 0.0017 0.01990.0008(参看 参考文献1) 按照概率论的理论，任何一段话中 26 个字母的频率在文章充分长时都应是收敛于或接近于这个信源分布。按照概率论的理论，任何一段话中 26 个字母的频率在文章充分长时都应是收敛于或接近于这个信源分布。这就我们解密的依据。当然，要解密就要有足够多的数据，使得概率论的
15、原理能够使用，数据越多越好！在实际中，通常是解密方收集多次通信数据，积累起来。 于是,我们的问题就是:已知一个 Vigenere 加密系统,且假设我们有足够多的密文,求其密钥 K 和明文. 2.问题转化为一个函数表示方面的问题 2.问题转化为一个函数表示方面的问题 2.1.上面问题在一定程度上可以化为下面这个问题： 2.1.上面问题在一定程度上可以化为下面这个问题： 为了方便，我们规定一个符号： yx 存在充分小的， 把第 , 1, 13 , 12 , 1, 1+NkNNN个字母作为第一份; 把第 , 2, 23 , 22 , 2, 2+NkNNN个字母作为第二份; , 12利用函数表示理论求解 Vigenere 加密系统加密系统 把第 ,3 ,2 ,tNktNtNtNt+个字母作为第 t 份; , 把第 ,3 ,2 ,NkNNN个字母作为第 N 份; 由 Vigenere 加密系统的性质,每一份都是由同一个密钥长为 1 的密码加密的.这样就转化为前面我们已经解决的 Caesar 问题。 到此，从理论上来说 Vigenere 加密系统解密问题解决了。 4.连续问题的离散化 4.连续问题的离散化 由于我们知道的只是一些离散的数据,所以我们要对我们连续模型
