密码学

绪论密码学的发展历史(1)1.3密码学的发展历史密码学的发展历程大致经历了三个阶段：古代加密方法、古典密码和近代密码。1.3.1古代加密方法（手工阶段）源于应用的无穷需求总是推动技术发明和进步的直接动力。存于石刻或史书中的记载表明，许多古代文明，包括埃及人、希伯来人、亚述人都在实践中逐步发明了密码系统。从某种意义上说，战争是科学技术进步的催化剂。人类自从有了战争，就面临着通信安全的需求，密码技术源远流长。古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。密码学用于通信的另一个记录是斯巴达人于公元前400年应用Scytale加密工具在军官间传递秘密信息。Scytale实际上是一个锥形指挥棒，周围环绕一张羊皮纸，将要保密的信息写在羊皮纸上。解下羊皮纸，上面的消息杂乱无章、无法理解，但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息。我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定位置的记载，一般人只注意诗或画的表面意境，而不会去注意或很难发现隐藏其中的“话外之音”。由上可见，自从有了文字以来，人们为了某种需要总是想法设法隐藏某些信息，以起到保证信息安全的目的。这些古代加密方法体现了后来发展起来的密码学的若干要素，但只能限制在一定范围内使用。传输密文的发明地是古希腊，一个叫AeneasTacticus的希腊人在《论要塞的防护》一书中对此做了最早的论述。公元前2世纪，一个叫Polybius的希腊人设计了一种将字母编码成符号对的方法，他使用了一个称为Polybius的校验表，这个表中包含许多后来在加密系统中非常常见的成分，如代替与换位。Polybius校验表由一个55的网格组成（如表1-1所示），网格中包含26个英文字母，其中I和J在同一格中。每一个字母被转换成两个数字，第一个是字母所在的行数，第二个是字母所在的列数。如字母A就对应着11，字母B就对应着12，以此类推。使用这种密码可以将明文“message”置换为密文“32154343112215”。在古代，这种棋盘密码被广泛使用。表1-1Polybius校验表123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ古代加密方法主要基于手工的方式实现，因此称为密码学发展的手工阶段。1.3.2古典密码（机械阶段）古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。古典密码的代表密码体制主要有：单表代替密码、多表代替密码及转轮密码。Caesar密码就是一种典型的单表加密体制；多表代替密码有Vigenere密码、Hill密码；著名的Enigma密码就是第二次世界大战中使用的转轮密码。阿拉伯人是第一个清晰地理解密码学原理的人，他们设计并且使用代替和换位加密，并且发现了密码分析中的字母频率分布关系。大约在1412年，al-Kalka-shandi在他的大百科全书中论述了一个著名的基本处理办法，这个处理方法后来广泛应用于多个密码系统中。他清楚地给出了一个如何应用字母频率分析密文的操作方法及相应的实例。欧洲的密码学起源于中世纪的罗马和意大利。大约在1379年，欧洲第一本关于密码学的手册由GabrieladeLavinde编写，由几个加密算法组成，并且为罗马教皇Clement七世服务。这个手册包括一套用于通信的密钥，并且用符号取代字母和空格，形成了第一个简要的编码字符表（称为Nomenclators）。该编码字符表后来被逐渐扩展，并且流行了几个世纪，成为当时欧洲政府外交通信的主流方法。到了1860年，密码系统在外交通信中已得到普遍使用，并且已成为类似应用中的宠儿。当时，密码系统主要用于军事通信，如在美国国内战争期间，联邦军广泛地使用了换位加密，主要使用的是Vigenere密码，并且偶尔使用单字母代替。然而联合军密码分析人员破译了截获的大部分联邦军密码。在第一次世界大战期间，敌对双方都使用加密系统（CipherSystem），主要用于战术通信，一些复杂的加密系统被用于高级通信中，直到战争结束。而密码本系统（CodeSystem）主要用于高级命令和外交通信中。到了20世纪20年代，随着机械和机电技术的成熟，以及电报和无线电需求的出现，引起了密码设备方面的一场革命——发明了转轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的重要标志之一。美国人EdwardHebern认识到：通过硬件卷绕实现从转轮机的一边到另一边的单字母代替，然后将多个这样的转轮机连接起来，就可以实现几乎任何复杂度的多个字母代替。转轮机由一个键盘和一系列转轮组成，每个转轮是26个字母的任意组合。转轮被齿轮连接起来，当一个转轮转动时，可以将一个字母转换成另一个字母。照此传递下去，当最后一个转轮处理完毕时，就可以得到加密后的字母。为了使转轮密码更安全，人们还把几种转轮和移动齿轮结合起来，所有转轮以不同的速度转动，并且通过调整转轮上字母的位置和速度为破译设置更大的障碍。几千年来，对密码算法的研究和实现主要是通过手工计算来完成的。随着转轮机的出现，传统密码学有了很大的进展，利用机械转轮可以开发出极其复杂的加密系统。1921年以后的十几年里，Hebern构造了一系列稳步改进的转轮机，并投入美国海军的试用评估，并申请了第一个转轮机的专利，这种装置在随后的近50年里被指定为美军的主要密码设备。毫无疑问，这个工作奠定了二次世界大战中美国在密码学方面的重要地位。在美国Hebern发明转轮密码机的同时，欧洲的工程师们，如荷兰的HugoKoch、德国的ArthurScherbius都独立地提出了转轮机的概念。ArthurScherbius于1919年设计出了历史上最著名的密码机——德国的Enigma机，在二次世界大战期间，Enigma曾作为德国陆、海、空三军最高级密码机。Enigma机（如图1-1（a）所示）面板前有灯泡和插接板，它使用了3个正规轮和1个反射轮。这使得英军从1942年2月到12月都没能解读出德国潜艇发出的信号。4轮Enigma机在1944年装备德国海军。绪论密码学的发展历史(2)这些机器也刺激了英国在二次世界大战期间发明并使用TYPEX密码机，如图1-1（b）所示。英国的TYPEX密码机是德国3轮Enigma的改进型密码机，它增加了两个轮使得破译更加困难，在英军通信中使用广泛，并帮助英军破译了德军信号。Hagelin（哈格林）密码机是在二次世界大战期间得到广泛使用的另一类转轮密码机。它由瑞典的BorisCaesarWilhelmHagelin发明。二战中，HagelinC-36型密码机（如图1-1（c）所示）曾在法国军队中广泛使用，它由AktiebolagetCryptoeknidStockholm于1936年制造，密钥周期长度为3900255。对于纯机械的密码机来说，这已是非常不简单了。HagelinC-48型（即M-209，如图1-1（d）所示）是哈格林对C-36改进后的产品，由Smith-Corna公司负责为美国陆军生产，曾装备美军师到营级部队，在朝鲜战争期间还在使用。M-209增加了一个有26个齿的密钥轮，共由6个共轴转轮组成，每个转轮外边缘分别有17,19,21,23,25,26个齿，它们互为素数，从而使它的密码周期达到了262523211917=101405850。日本人在二次世界大战期间所使用的密码机与Hebern和Enigma密码机间有一段有趣的历史渊源。在第一次世界大战期间及之后，美国政府组织了第一个正式的密码分析活动，一位曾指导该活动的美国密码学家出版了《TheAmericanBlackChamber》一书。该书列举了美国人成功破译日军密码的细节：日本政府致力于开发尽可能最好的密码机，为了达到这个目的，它购买了Hebern的转轮机和商业的Enigma机，包括其他几个当时流行的密码机来研究。在1930年，日本的第一个转轮密码机（美国分析家把它称之为RED）开始为日本外交部服务。然而，因为具有分析Hebern转轮密码机的经验，美国的密码分析家们成功地分析出了RED所加密的内容。在1939年，日本人引入了一个新的加密机（美国分析家将其称为PURPLE），其中的转轮机用电话步进交换机所取代。图1-1几个典型的密码机转轮密码机的使用大大提高了密码加密速度，但由于密钥量有限，到二战中后期时，引出了一场关于加密与破译的对抗。二次大战期间，波兰人和英国人破译了Enigma密码，美国密码分析者攻破了日本的RED,ORANGE和PURPLE密码，这对联军在二次世界大战中获胜起到了关键性作用，是密码分析最伟大的成功。二次大战后，电子学开始被引入到密码机中。第一个电子密码机仅仅是一个转轮机，只是转轮被电子器件取代。这些电子转轮机的惟一优势在于它们的操作速度，但它们仍受到机械式转轮密码机固有弱点（密码周期有限、制造费用高等）的影响。绪论密码学的发展历史(3)1.3.3近代密码（计算机阶段）密码形成一门新的学科是在20世纪70年代，这是受计算机科学蓬勃发展刺激和推动的结果。快速电子计算机和现代数学方法一方面为加密技术提供了新的概念和工具，另一方面也给破译者提供了有力武器。计算机和电子学时代的到来给密码设计者带来了前所未有的自由，他们可以轻易地摆脱原先用铅笔和纸进行手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。总之，利用电子计算机可以设计出更为复杂的密码系统。密码学的理论基础之一是1949年ClaudeShannon发表的“保密系统的通信理论”（TheCommunicationTheoryofSecrecySystems），这篇文章发表了30年后才显示出它的价值。1976年W.Diffie和M.Hellman发表了“密码学的新方向”（NewDirectionsinCryptography）一文，提出了适应网络上保密通信的公钥密码思想，开辟了公开密钥密码学的新领域，掀起了公钥密码研究的序幕。受他们的思想启迪，各种公钥密码体制被提出，特别是1978年RSA公钥密码体制的出现，成为公钥密码的杰出代表，并成为事实标准，在密码学史上是一个里程碑。可以这么说：“没有公钥密码的研究就没有近代密码学”。同年，美国国家标准局（NBS，即现在的国家标准与技术研究所NIST）正式公布实施了美国的数据加密标准（DataEncryptionStandard，DES），公开它的加密算法，并被批准用于政府等非机密单位及商业上的保密通信。上述两篇重要的论文和美国数据加密标准DES的实施，标志着密码学的理论与技术的划时代的革命性变革，宣布了近代密码学的开始。近代密码学与计算机技术、电子通信技术紧密相关。在这一阶段，密码理论蓬勃发展，密码算法设计与分析互相促进，出现了大量的密码算法和各种攻击方法。另外，密码使用的范围也在不断扩张，而且出现了许多通用的加密标准，促进网络和技术的发展。现在，由于现实生活的实际需要及计算机技术的进步，密码学有了突飞猛进的发展，密码学研究领域出现了许多新的课题、新的方向。例如：在分组密码领域，由于DES已经无法满足高保密性的要求，美国于1997年1月开始征集新一代数据加密标准，即高级数据加密标准（AdvancedEncryptionStandard，AES）。目前，AES的征集已经选择了比利时密码学家所设计的Rijndael算法作为标准草案，并正在对Rijndael算法做进一步评估。AES征集活动使国际密码学界又掀起了一次分组密码研究高潮。同时，在公开密钥密码领域，椭圆曲线密码体制由于其安全性高、计算速度快等优点引起了人们的普遍关注，许多公司与科研机构都投入到对椭圆曲线密码的研究当中。目前，椭圆曲线密码已经被列入一些标准中作为推荐算法。另外，由于嵌入