论文部分内容阅读
愚蠢的齐默尔曼电报
第一次世界大战期间，长距离传送信息的技术有了大幅度发展。用莫尔斯电码发送的电报和无线电报不久便在战争中显示了其胜负攸关的作用。
1917年1月17日，英军截获了一份以德国最高外交密码0075加密的电报。这个令人无法想象的密码系统由1万个词和词组组成。与1000个数字码群对应。密电来自德国外交部长阿瑟·齐默尔曼。传送给德国驻华盛顿大使，然后继续传给德国驻墨西哥大使。电文将在那里解密，最后要交给墨西哥总统。
密件从柏林经美国海底电缆送到了华盛顿。英军在那里将其截获并意识到了它的重要性。英国密码破译专家开始全力以赴进行破译，然而，面对这个未曾被破译的新外交密码系统。专家们绞尽脑汁仍一筹莫展。
令英国密码破译专家意想不到的机遇降临了。接到密件的德国驻华盛顿大使在他的华盛顿办公室里犯下了愚蠢的错误：他们在将电报用新的0075密件本译出后。却又用老的密件本将电报加密后传送到墨西哥城。
没过多久，已经破译了旧密码的英方便从德国大使的糊涂操作中获得了新旧密码的比较版本。英国的破译人员开始了艰苦的工作：将密件在旧密码中译出，用纸笔建构模型。随着齐默尔曼的密件逐渐清晰。
惊人的电报内容浮现出来……
当时的情况是，尽管1915年美国的远洋客轮“露斯塔尼亚”号被德军击沉。但只要德国此后对其潜艇的攻击行动加以限制，美国仍将一直保持中立。齐默尔曼的电文概括了德国要在1917年2月1日重新开始无限制海战以抑制英国的企图。为了让美国无暇他顾，齐默尔曼建议墨西哥入侵美国。宣布得克萨斯州、新墨西哥州和亚利桑那州重新归其所有。德国还要墨西哥说服日本进攻美国，德国将提供军事和资金援助。
美国愤怒了。原先只是东海岸的人在关心战局的进展，现在整个美国都开始担心墨西哥的举动。电文破译后6个星期，美国总统威尔逊宣布美国对德宣战。此时。站在他背后的是一个团结起来的愤怒的国家。
齐默尔曼的电文使整个美国相信德国是国家的敌人。这次破译由此也被称为密码学历史上最伟大的密码破译。
密码机械之“谜”——恩格玛
19世纪末，密码编码学处于一种混乱状态。自从巴比奇破坏了维氏密码的安全性之后，密码编码师一直在寻找一种新的密码。希望能够重新建立安全的秘密通讯，这样，商人和军人就可以充分利用电报和无线电的快捷。同时，通讯信息的指数爆炸也让密码编码师们认识到进行机械化加密的必要。
最早的密码机器是密码盘，是15世纪由意大利建筑师利昂发明的，利昂也是多字母替换密码创始人之一。他使用两个铜盘。一个比另一个稍大，在每个盘的边缘刻上了26个字母。将小盘子放在大盘子上，中间用一根针作为轴心。美国南北战争时，南部联邦通讯局便采用了类似的加密装置。
1918年。德国发明家谢尔比斯与他的好朋友里特建立了谢尔比斯＆里特公司，这是个锐意进取的工程公司，涉及许多发明领域，从涡轮机到热枕垫。几乎无所不能。在汉诺威和慕尼黑接受过电气工程专业训练的谢尔比斯发明了一个密码编码装置，本质上它是将提昂密码盘电子化。他的发明被称做恩格玛，意为谜。当时并没有人认识到它将成为历史上最厉害的加密机械。
恩格玛机基本上由三大部件组成，它们之间通过电线连接起来。一个键盘，用来输入每个明文字母；一个扰频器，用来将每个明文字母加密；一个显示板，由各种灯构成。用来显示密文字母。扰频器本质上是定义了一个密码表，它可以用来实现一个简单的单字母替换密码。扰频器在每次加密一个字母后会自动的旋转1／6圈。这样，当敲入字母B将被加密成A，但这一次加密完后，扰频器会自动旋转1／6圈，再次输入字母B将被加密成C。这样，连续输入同一个字母B将产生完全不同的密文。
但这台机器还是具有一个弱点，即输入B六次后，将使扰频器回到原始位置，这样。再输入B将重复同样的加密模式，这将导致产生的密文具有规则性和结构性。于是。谢尔比斯引入第二个扰频器来解决这个问题。这两个扰频器配合使用，就相当于一个汽车里程表，代表单数英里转轮完成一圈后到达9时，会带动代表10位数英里的转轮转动一次。加入第二个扰频器的好处在于，加密的模式直到第二个扰频器完成一圈后才出现重复，这需要第一个扰频器完成6次转圈，即需要加密6×6即36个字母。因此通过组合扰频器产生的密码机将连续在不同的密码表中切换。谢尔比斯可以增加更多的扰频器来提高安全性。第二种新的特性是谢尔比斯在键盘和第一扰频器之间加入一个插件板。它允许发送者插入连接器，能在字母进入扰频器之前先交换字母的位置。我们将插件板连接器的数目和扰频器的可能组合的排列综合起来，便可计算出密钥的数目可达到多少。假如有3个扰频器，每个有26个状态。因此将有26×26×26=17576种设置。扰频器共有6种排列：123，132，213，231，312，321。插件板在26个字母中任意交换6对字母。那么连接方式的数目是巨大的：100391791500。将三个数相乘17576×6×100391791500＝1016，这在当时几乎意味着不可。破译。
1923年，英国皇家海军出版了关于第一次世界大战的官方历史资料，里面提到对德军通讯的截获和分析，使得盟军具有明显的优势。英国情报部门所取得的令人骄傲的成果，使德国安全防卫官员深受刺激。他们决心在密码编码上避免发生一战时的惨痛失败，并得出结论：恩格玛机是最好的解决办法。在接下来20年内。德国军方购买了近2000台恩格玛机，谢尔比斯的发明为德国军方提供了世界上最安全的加密系统保护。曾经一度，恩格玛机给战场上的纳粹带来决定性的胜利。然而，它最终也成了希特勒垮台的一个因素。
布莱切利公园里的神秘人物
二战爆发后的整整13年里，英国人和法国人都以为恩格玛像它的名字一样，是一个不可破译的谜，直到波兰人取得了突破性进展。德军有条规定，每封密文的最开始六个字母须由此信密钥的三个字母重复两遍。这种规定本意是防止密码员输入错误，却弄巧成拙，成为波兰人破译恩格玛的重要线索。
波兰情报人员研究了密钥循环圈的规律。最终用数学严格证明，每个循环圈的长度仅由扰频器的位置与初始方向决定的，与连接板上的字母交换无关。这是个极其重大的突破，因为若要强行试遍所有的密钥来破解，得尝试一亿亿个密钥。但是恩格玛的密钥主要是由连接板来提供的；如果只考虑扰频器的位置与初始方向，则只有105456种可能性。1939年9月28日，德军占领华沙。波兰人对德军密码的破译活动中止了，但 他们取得的成果被英国人、法国人继承下来。
1939年8月，在英国白金汉郡的一个叫布莱切利的庄园里，突然出没一群神秘人物。他们的身份五花八门，数学家、科学家、语言学家、历史学家。甚至还有象棋大师、纵横填字专家。原来他们是英国代码和加密学校(GC＆CS)召集起来的“一群嗅觉灵敏的猎狗”。被政府认为是当时最可能破译恩格玛的人才。在布莱切利庄园有许多伟大的密码破译师，但如果非得提及一个人的话，那就是阿兰·图灵。28岁的图灵不仅找到了恩格玛的最大一个弱点。还在密码破译的过程中，提出了图灵机的伟大概念。
图灵从布莱切利巨大的解密信息的数据库中观察到许多固定的结构。军事组织通常是按照严格的规定行事，也就意味着这样的信息在格式上肯定是高度统一的。例如，经验表明德军在每天早晨6点会发布一条天气预报，当然这是加密的。因此，在早晨6点的截获的加密信息中几乎必会含单词wetter(德语：天气)。
当一篇明文和一篇密文联系起来时，这种组合称做crib。图灵坚信他能够利用这些crib来破解恩格玛。图灵不是单单用一台恩格玛机来测试他的想法，他开始想象有三台独立的机器，三台机器有着完全相同的设置，但第二台机器的扰频器的定位和第一台相比前进了一个位置。第三台则前进了两个位置。然后图灵想象有一个疯狂的密码分析师，希望能最终得到准确的加密设置。但是在第一台机器中无论连接器怎么改变，其他两台机器也要做同样的变换。这时。密码分析师不得不检查1.59×10×29种可能设置。但是图灵天才的设想一条电线通过输入输出端把三台机器连接起来，这样，crib中的环通过电环路并行起来，巧妙地抵消了插件板的影响，因此容许他忽略近上万亿种的插件板设置。
cri环路和电线连接的机器三者综合在一起最终构成了密码史上一件不朽之作，也只有图灵，利用他独特的数
学背景。才能够做到这一点。他的图灵机遐想本是希望解决数学上深奥的不可判定性。但这个纯学术的研究。却促成他在密码破译领域发明出一台强大的破译机器。布莱切利筹集了10万英镑把图灵的想法变成能够工作的机械装置。被命名为“炸弹”。
由于密码学校的工作为高度机密，布莱切利公园以外没有人知道图灵所取得的卓越成就，就连他的父母也不知道。他母亲曾为此感到失望。她认为儿子至少也该理一种看得过去的头发。尽管布莱切利受军方管理，但他们承认他们有时不得不容忍这些教授形象上的邋遢和古怪。他不修边幅，他的指甲里充满了泥垢。衣服总是皱巴巴的，他还是个同性恋。布莱切利一位老兵战后评价道：“幸运的是。当局不知道图灵是个同性恋者。要不然我们可能会输掉这场战争。”
孙子剩余定理与RSA公钥加密
传说汉朝大将韩信计算士兵数目的方法十分特别，他无须亲自数。也不要士兵“一、二、三、四、五……”地报数，而是叫他们排起队伍，依次在他面前列队行进：先是一排三人。再是一排五人，然后是一排七人。他只将三次所余的士兵记下来，就知道了士兵的总数。士兵们都感到十分惊奇。原来他利用的是孙子剩余定理。
我国古代四、五世纪的数学著作《孙子算经》详细记载了“物不知数”问题与它的解法：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何?这种“物不知数题”在我国古代流传的算法名称很多。宋朝周宓称它为“鬼谷算”、“隔墙算”。杨辉则称为“剪管术”，秦九韶将之推广，并又发现一种算法，称之为“大衍求一术”。
1977年，美国麻省理工学院计算机科学实验室的Rivest·Shamir和Adleman三人联合设计了一个密钥方案，这就是著名的RSA方案。他们的编码方法，便是来自于古老的孙子剩余定理。
公元前3世纪。希腊数学家欧几里德在《几何原本》中叙述了以下定理并且给出了证明：每个大于1的整数都可唯一分解有限个素数的乘积。
这个定理在理论上是很漂亮的，但是，要把一个相当大的数分解，看起来简单，做起来却不那么容易。现在普遍使用的方法，只能是用一个一个较小的素数去试除。
第一次世界大战期间，长距离传送信息的技术有了大幅度发展。用莫尔斯电码发送的电报和无线电报不久便在战争中显示了其胜负攸关的作用。
1917年1月17日，英军截获了一份以德国最高外交密码0075加密的电报。这个令人无法想象的密码系统由1万个词和词组组成。与1000个数字码群对应。密电来自德国外交部长阿瑟·齐默尔曼。传送给德国驻华盛顿大使，然后继续传给德国驻墨西哥大使。电文将在那里解密，最后要交给墨西哥总统。
密件从柏林经美国海底电缆送到了华盛顿。英军在那里将其截获并意识到了它的重要性。英国密码破译专家开始全力以赴进行破译，然而，面对这个未曾被破译的新外交密码系统。专家们绞尽脑汁仍一筹莫展。
令英国密码破译专家意想不到的机遇降临了。接到密件的德国驻华盛顿大使在他的华盛顿办公室里犯下了愚蠢的错误：他们在将电报用新的0075密件本译出后。却又用老的密件本将电报加密后传送到墨西哥城。
没过多久，已经破译了旧密码的英方便从德国大使的糊涂操作中获得了新旧密码的比较版本。英国的破译人员开始了艰苦的工作：将密件在旧密码中译出，用纸笔建构模型。随着齐默尔曼的密件逐渐清晰。
惊人的电报内容浮现出来……
当时的情况是，尽管1915年美国的远洋客轮“露斯塔尼亚”号被德军击沉。但只要德国此后对其潜艇的攻击行动加以限制，美国仍将一直保持中立。齐默尔曼的电文概括了德国要在1917年2月1日重新开始无限制海战以抑制英国的企图。为了让美国无暇他顾，齐默尔曼建议墨西哥入侵美国。宣布得克萨斯州、新墨西哥州和亚利桑那州重新归其所有。德国还要墨西哥说服日本进攻美国，德国将提供军事和资金援助。
美国愤怒了。原先只是东海岸的人在关心战局的进展，现在整个美国都开始担心墨西哥的举动。电文破译后6个星期，美国总统威尔逊宣布美国对德宣战。此时。站在他背后的是一个团结起来的愤怒的国家。
齐默尔曼的电文使整个美国相信德国是国家的敌人。这次破译由此也被称为密码学历史上最伟大的密码破译。
密码机械之“谜”——恩格玛
19世纪末，密码编码学处于一种混乱状态。自从巴比奇破坏了维氏密码的安全性之后，密码编码师一直在寻找一种新的密码。希望能够重新建立安全的秘密通讯，这样，商人和军人就可以充分利用电报和无线电的快捷。同时，通讯信息的指数爆炸也让密码编码师们认识到进行机械化加密的必要。
最早的密码机器是密码盘，是15世纪由意大利建筑师利昂发明的，利昂也是多字母替换密码创始人之一。他使用两个铜盘。一个比另一个稍大，在每个盘的边缘刻上了26个字母。将小盘子放在大盘子上，中间用一根针作为轴心。美国南北战争时，南部联邦通讯局便采用了类似的加密装置。
1918年。德国发明家谢尔比斯与他的好朋友里特建立了谢尔比斯＆里特公司，这是个锐意进取的工程公司，涉及许多发明领域，从涡轮机到热枕垫。几乎无所不能。在汉诺威和慕尼黑接受过电气工程专业训练的谢尔比斯发明了一个密码编码装置，本质上它是将提昂密码盘电子化。他的发明被称做恩格玛，意为谜。当时并没有人认识到它将成为历史上最厉害的加密机械。
恩格玛机基本上由三大部件组成，它们之间通过电线连接起来。一个键盘，用来输入每个明文字母；一个扰频器，用来将每个明文字母加密；一个显示板，由各种灯构成。用来显示密文字母。扰频器本质上是定义了一个密码表，它可以用来实现一个简单的单字母替换密码。扰频器在每次加密一个字母后会自动的旋转1／6圈。这样，当敲入字母B将被加密成A，但这一次加密完后，扰频器会自动旋转1／6圈，再次输入字母B将被加密成C。这样，连续输入同一个字母B将产生完全不同的密文。
但这台机器还是具有一个弱点，即输入B六次后，将使扰频器回到原始位置，这样。再输入B将重复同样的加密模式，这将导致产生的密文具有规则性和结构性。于是。谢尔比斯引入第二个扰频器来解决这个问题。这两个扰频器配合使用，就相当于一个汽车里程表，代表单数英里转轮完成一圈后到达9时，会带动代表10位数英里的转轮转动一次。加入第二个扰频器的好处在于，加密的模式直到第二个扰频器完成一圈后才出现重复，这需要第一个扰频器完成6次转圈，即需要加密6×6即36个字母。因此通过组合扰频器产生的密码机将连续在不同的密码表中切换。谢尔比斯可以增加更多的扰频器来提高安全性。第二种新的特性是谢尔比斯在键盘和第一扰频器之间加入一个插件板。它允许发送者插入连接器，能在字母进入扰频器之前先交换字母的位置。我们将插件板连接器的数目和扰频器的可能组合的排列综合起来，便可计算出密钥的数目可达到多少。假如有3个扰频器，每个有26个状态。因此将有26×26×26=17576种设置。扰频器共有6种排列：123，132，213，231，312，321。插件板在26个字母中任意交换6对字母。那么连接方式的数目是巨大的：100391791500。将三个数相乘17576×6×100391791500＝1016，这在当时几乎意味着不可。破译。
1923年，英国皇家海军出版了关于第一次世界大战的官方历史资料，里面提到对德军通讯的截获和分析，使得盟军具有明显的优势。英国情报部门所取得的令人骄傲的成果，使德国安全防卫官员深受刺激。他们决心在密码编码上避免发生一战时的惨痛失败，并得出结论：恩格玛机是最好的解决办法。在接下来20年内。德国军方购买了近2000台恩格玛机，谢尔比斯的发明为德国军方提供了世界上最安全的加密系统保护。曾经一度，恩格玛机给战场上的纳粹带来决定性的胜利。然而，它最终也成了希特勒垮台的一个因素。
布莱切利公园里的神秘人物
二战爆发后的整整13年里，英国人和法国人都以为恩格玛像它的名字一样，是一个不可破译的谜，直到波兰人取得了突破性进展。德军有条规定，每封密文的最开始六个字母须由此信密钥的三个字母重复两遍。这种规定本意是防止密码员输入错误，却弄巧成拙，成为波兰人破译恩格玛的重要线索。
波兰情报人员研究了密钥循环圈的规律。最终用数学严格证明，每个循环圈的长度仅由扰频器的位置与初始方向决定的，与连接板上的字母交换无关。这是个极其重大的突破，因为若要强行试遍所有的密钥来破解，得尝试一亿亿个密钥。但是恩格玛的密钥主要是由连接板来提供的；如果只考虑扰频器的位置与初始方向，则只有105456种可能性。1939年9月28日，德军占领华沙。波兰人对德军密码的破译活动中止了，但 他们取得的成果被英国人、法国人继承下来。
1939年8月，在英国白金汉郡的一个叫布莱切利的庄园里，突然出没一群神秘人物。他们的身份五花八门，数学家、科学家、语言学家、历史学家。甚至还有象棋大师、纵横填字专家。原来他们是英国代码和加密学校(GC＆CS)召集起来的“一群嗅觉灵敏的猎狗”。被政府认为是当时最可能破译恩格玛的人才。在布莱切利庄园有许多伟大的密码破译师，但如果非得提及一个人的话，那就是阿兰·图灵。28岁的图灵不仅找到了恩格玛的最大一个弱点。还在密码破译的过程中，提出了图灵机的伟大概念。
图灵从布莱切利巨大的解密信息的数据库中观察到许多固定的结构。军事组织通常是按照严格的规定行事，也就意味着这样的信息在格式上肯定是高度统一的。例如，经验表明德军在每天早晨6点会发布一条天气预报，当然这是加密的。因此，在早晨6点的截获的加密信息中几乎必会含单词wetter(德语：天气)。
当一篇明文和一篇密文联系起来时，这种组合称做crib。图灵坚信他能够利用这些crib来破解恩格玛。图灵不是单单用一台恩格玛机来测试他的想法，他开始想象有三台独立的机器，三台机器有着完全相同的设置，但第二台机器的扰频器的定位和第一台相比前进了一个位置。第三台则前进了两个位置。然后图灵想象有一个疯狂的密码分析师，希望能最终得到准确的加密设置。但是在第一台机器中无论连接器怎么改变，其他两台机器也要做同样的变换。这时。密码分析师不得不检查1.59×10×29种可能设置。但是图灵天才的设想一条电线通过输入输出端把三台机器连接起来，这样，crib中的环通过电环路并行起来，巧妙地抵消了插件板的影响，因此容许他忽略近上万亿种的插件板设置。
cri环路和电线连接的机器三者综合在一起最终构成了密码史上一件不朽之作，也只有图灵，利用他独特的数
学背景。才能够做到这一点。他的图灵机遐想本是希望解决数学上深奥的不可判定性。但这个纯学术的研究。却促成他在密码破译领域发明出一台强大的破译机器。布莱切利筹集了10万英镑把图灵的想法变成能够工作的机械装置。被命名为“炸弹”。
由于密码学校的工作为高度机密，布莱切利公园以外没有人知道图灵所取得的卓越成就，就连他的父母也不知道。他母亲曾为此感到失望。她认为儿子至少也该理一种看得过去的头发。尽管布莱切利受军方管理，但他们承认他们有时不得不容忍这些教授形象上的邋遢和古怪。他不修边幅，他的指甲里充满了泥垢。衣服总是皱巴巴的，他还是个同性恋。布莱切利一位老兵战后评价道：“幸运的是。当局不知道图灵是个同性恋者。要不然我们可能会输掉这场战争。”
孙子剩余定理与RSA公钥加密
传说汉朝大将韩信计算士兵数目的方法十分特别，他无须亲自数。也不要士兵“一、二、三、四、五……”地报数，而是叫他们排起队伍，依次在他面前列队行进：先是一排三人。再是一排五人，然后是一排七人。他只将三次所余的士兵记下来，就知道了士兵的总数。士兵们都感到十分惊奇。原来他利用的是孙子剩余定理。
我国古代四、五世纪的数学著作《孙子算经》详细记载了“物不知数”问题与它的解法：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何?这种“物不知数题”在我国古代流传的算法名称很多。宋朝周宓称它为“鬼谷算”、“隔墙算”。杨辉则称为“剪管术”，秦九韶将之推广，并又发现一种算法，称之为“大衍求一术”。
1977年，美国麻省理工学院计算机科学实验室的Rivest·Shamir和Adleman三人联合设计了一个密钥方案，这就是著名的RSA方案。他们的编码方法，便是来自于古老的孙子剩余定理。
公元前3世纪。希腊数学家欧几里德在《几何原本》中叙述了以下定理并且给出了证明：每个大于1的整数都可唯一分解有限个素数的乘积。
这个定理在理论上是很漂亮的，但是，要把一个相当大的数分解，看起来简单，做起来却不那么容易。现在普遍使用的方法，只能是用一个一个较小的素数去试除。