密码学基础

1第一讲密码学基础杨照峰软件学院网络技术方向222内容安排1.1密码学的背景—现实与历史1.2基本概念和术语1.3密码学的发展1.4常用加密算法31.1现在的背景-1保密与安全随着计算机的广泛使用，尤其是Internet的出现与发展，信息安全受到越来越多人的关注，象社会安全和经济安全等一样作为国家安全的重要组成部份，各国政府都予以高度重视发达国家和地区投入巨资来保护其信息基础建设的安全，增强其综合实力在一些发展中国家（如中国），则更多地依赖于国家政策，来维护自身的信息安全41.1现在的背景-2然而，全球一体化的经济和科技的发展，使得国与国，人与人之间有了更加紧密的依靠和渗透当前国际形势复杂多变，世界范围内黑客对计算机网络的攻击与破坏活动日趋猖獗，一些发达国家正在利用其信息技术、经济和军事优势来达到称霸世界的目的为了更快地发展我国的经济、增强综合国力，维护国家和世界的和平，我们自然不能袖手旁观5关注焦点•目前在信息安全领域的关注焦点：⒈密码理论与技术；⒉安全协议理论与技术；⒊安全体系结构理论与技术；⒋信息保障体系；⒌信息对抗理论与技术；⒍安全产品。6历史背景一开始人就具备保守秘密的本能。这是一种很自然的人类行为。这些秘密要么只能由自己掌握，要么由自己和自己允许的人掌握。要想保密，最简单的做法就是不把它告诉别人。在远古，只有少数人才有读书、写字的特权十六世纪以前，秘密书写方法－隐匿法(隐藏讯息本身)与密码法(隐藏讯息意义)自凯撒大帝的年代开始，一直到当代，通信技术在稳步地发展着。从纸张到电报、电传、电话、传真以及E-mail，人和人之间的通信变得如此方便和普遍。与此同时，保障这些通信的安全也逐渐成为一项重要课题。7历史背景根据不同时期密码技术采用的加密和解密实现手段的不同特点，密码技术的发展历史大致可以划分为三个时期，即古典密码、近代密码和现代密码时期。一、古典密码时期（手工密码）这一时期为从古代到十九世纪末，长达数千年。这个时期产生的许多密码体制都是以“手工作业”的方式进行，用纸笔或简单的器械来实现加密/解密的。8主要特征：手工加、解密源远流长（十九世纪以前的漫长时期）最初起源记录占星术等不宜公开的秘诀师徒相传（口授、书写）发展结果用于军事、外交等秘密保护古典密码时期——最早的密码9古典密码时期——最早的密码早在公元前1900年左右，一位佚名的埃及书吏在碑文中使用了非标准的象形文字,这或许是目前已知最早的密码术实例。在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史。这篇颇具神秘感的碑文，已具备了密码的基本特征：把一种符号(明文)用另一种符号(密文)代替10古典密码时期——最早的密码公元前440年，古希腊战争中应用隐写术奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长起后将奴隶送到另一个部落，从而实现这两个部落之间的秘密通信。11古典密码时期——最早的密码公元前5世纪，古斯巴达人使用了一种叫做“天书”的器械，这是人类历史上最早使用的密码器械。“天书”是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。12古典密码时期——最早的密码公元前1世纪古罗马凯撒大帝时代曾使用过一种“替代式密码”，在这种密码中，每个字母都由其后的第三个字母（按字母顺序）所代替。这种替代式密码直到第二次大战时还被日本海军使用。公元前4世纪前后，希腊著名作家艾奈阿斯在著作《城市防卫论》中就曾提到一种被称为“艾奈阿斯绳结”的密码。它的作法是从绳子的一端开始，每隔一段距离打一个绳结，而绳结之间距离不等，不同的距离表达不同的字母。13古典密码时期——最早的密码恺撒密码：古罗马皇帝（公元前50年）单表代换密码。明文中的每个字母用字母表中该字母后面的第3个字母代替。维吉尼亚密码：16世纪法国外交官多表代换密码，曾号称300年不破。将26个恺撒密表合成一个，引入了“密钥”14古典密码时期——最早的密码兵书《六韬.龙韬》记载西周时期采用阴符传递情报----以不同物体形状表示不同情报内容；采用阴书传递情报----将1份战斗文书书写在3枚竹简上分送一地，受文者必须合而为一方知其意。兵书《武经总要》记载北宋时期用1首无重复汉字五言律诗的40个字分别表示40条不同的军情。15藏头诗芦花丛中一扁舟，俊杰俄从此地游。义士若能知此理，反躬难逃可无忧。水浒传我画蓝江清悠悠，爱晚亭前枫叶愁。秋雾茫茫笼佛寺，香烟袅袅绕经楼。唐伯虎1616世纪卡尔达诺发明“卡尔达诺漏格板”．漏格板是一张用硬质材料(如硬纸、羊皮、金属等)做成的板，上面挖了一些长方形的孔，即漏格．网格密码17网格密码隐写术18近代密码时期二、近代密码时期（机电密码）近代密码时期是指二十世纪初到二十世纪50年代左右。从1919年以后的几十年中，密码研究人员设计出了各种各样采用机电技术的转轮密码机来取代手工编码加密方法，实现保密通信的自动编解码。19主要特征：以机械、电子方式加解密文字代换，但比古典加密方法复杂使用转轮机，大大提高了密码加解密速度应用电子技术，初步解决了在线实时加解密的问题少数保留手工密码方式在外交、军事领域得到广泛应用近代密码时期20近代密码时期密码学真正成为科学是在19世纪末和20世纪初期，两次世界大战中对军事信息保密传递和破获敌方信息的需求，密码学得到了发展，并广泛的用于军事情报部门的决策。在希特勒一上台时，德国就试验并使用了一种命名为“谜”的密码机，假如一个人日夜不停地工作，每分钟测试一种密钥的话，需要约4.2万年才能将所有的密钥可能组合试完，希特勒完全相信了这种密码机的安全性。然而，英国获知了“谜”型机的密码原理，完成了一部针对“谜”型机的绰号叫“炸弹”的密码破译机，每秒钟可处理2000个字符，它几乎可以破译截获德国的所有情报。21历史背景后来又研制出一种每秒钟可处理5000个字符的“巨人”型密码破译机并投入使用，至此同盟国几乎掌握了德国纳粹的绝大多数军事秘密和机密，而德国军方却对此一无所知。太平洋战争中，美军成功破译了日本海军的密码机，读懂了日本舰队司令官山本五十六发给各指挥官的命令，在中途岛彻底击溃了日本海军，击毙了山本五十六，导致了太平洋战争的决定性转折。因此，可以说，密码学为战争的胜利立了大功。22二战中最负盛名的密码机M-209密码机ENIGMA密码机23ENIGMA机（“谜”的密码机）上个世纪20年代，出现了转轮密码，而由德国发明家亚瑟·谢尔比乌斯发明的Enigma密码机最为著名。它主要由经电线相连的键盘、转子和显示器组成，转子本身也集成了26条线路（在下图中显示了6条），把键盘的信号对应到显示器不同的小灯上去。在图2-5中可以看到，如果按下a键，那么灯B就会亮，这意味着a被加密成了B。同样地我们看到，b被加密成了A，c被加密成了D，d被加密成了F，e被加密成了E，f被加密成了C。于是如果我们在键盘上依次键入cafe（咖啡），显示器上就会依次显示DBCE，这是最简单的加密方法之一——简单替换密码。2425不仅仅如此，因为当键盘上一个键被按下时，相应的密文在显示器上显示，然后转子的方向就自动地转动一个字母的位置（在图中就是转动1/6圈，而在实际中转动1/26圈）。26当第一次键入b时，信号通过转子中的连线，灯A亮起来，放开键后，转子转动一格，各字母所对应的密码就改变了；第二次键入b时，它所对应的字母就变成了C；同样地，第三次键入b时，灯E闪亮。为使机器更安全，可以把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26n。为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。27德国人为了战时使用，大大加强了其基本设计，军用的Enigma由3个转轮，从5个转轮中选取。转轮机中还有一块稍微改名明文序列的插板，有一个反射器导致每个转轮对每一个明文字母操作两次。28ENIGMA的原理-转子29ENIGMA的原理-转子当第一个转子转动整整一圈以后，它上面有一个齿拨动第二个转子，使得它转动一个字母的位置30ENIGMA的原理-反射器反射器和转子一样，把某一个字母连在另一个字母上，但是它并不转动。乍一看它并不增加可以使用的编码数目，但是把它和解码联系起来就是这种设计的别具匠心31(转子自身的初始方向，转子之间的相互位置，以及连接板连线的状况就组成了所有可能的密钥：三个转子不同的方向组成了26*26*26=17576种不同可能性；三个转子间不同的相对位置为6种可能性；连接板上两两交换6对字母的可能性数目非常巨大，有100391791500种；于是一共有17576*6*100391791500，大约为10000000000000000，即一亿亿种可能性。但如此复杂的密码机在第二次世界大战中被破解了，首先是波兰人利用德军电报中前几个字母的重复出现，破解了早期的Enigma密码机，而后又将破译的方法告诉了法国人和英国人。英国人在计算机理论之父——图灵的带领下，通过寻找德国人在密钥选择上的失误，并成功夺取德军的部分密码本，获得密钥，以及进行选择明文攻击等等手段，破解出相当多非常重要的德军情报。ENIGMA的原理32现代密码时期三、现代密码时期（计算机密码）主要特征：计算机加解密与计算机技术、电子通信技术紧密相关密码理论蓬勃发展，密码算法设计与分析互相促进，出现了大量的密码算法和各种攻击方法密码使用的范围也在不断扩张，出现了许多通用的加密标准出现了一些新的密码技术，如混沌密码、量子密码等33现代密码时期1949年C.Shannon发表了“保密系统的通信理论（Thecommunicationtheoryofsecrecysystems）”，提出了保密系统的理论模型，从此可以对保密系统进行定量分析；指出了提高保密度的途径：增大密钥量，减少多余度，为设计高保密度密码系统指明了方向。首次将信息论引入密码技术的研究，为现代密码学研究与发展奠定了坚实的理论基础，使密码学成为一门真正的科学。遗憾：差不多30年后才受到重视。1949年至1975年，密码学主要研究单钥密码体制，且发展比较缓慢。1976年11月，美国斯坦福大学的著名密码学家Diffie和Hellman发表了NewDirectioninCryptography一文，首次提出了公钥密码体制的概念和设计思想，开辟了公开密钥密码学的新领域，34现代密码时期1977年美国联邦政府颁布数据加密标准（DES）。2001年美国联邦政府颁布高级加密标准（AES）。后来，新的密码技术不断涌现，例如，混沌密码、量子密码、DNA密码等等。这些新的密码技术正在逐步地走向实用化。同时，在公钥密码领域，椭圆曲线密码体制由于其安全性高、计算速度快等优点引起了人们的普遍关注。在数字签名方面，各种有不同实际应用背景的签名方案，如盲签名、群签名、环签名、指定验证人签名、聚合签名等不断出现。随着其他技术的发展，一些具有潜在密码应用价值的技术也得到了密码学家的重视，出现了一些新的密码技术，如混沌密码、量子密码、DNA密码等等。现在，密码学的研究和应用已大规模地扩展到民用方面。35两款著名的密码设备计算机密码板STU-Ⅲ型数字电话保密机36密码从军事走向生活应用领域--军事，外交，商业，个人通信，古文化研究等目前，应用重点已经更多的集中在实际应用在生活中有越来越多使用密码的例子。随着科技的发展和信息保密的需求，密码学的应用已融入了日常生活37密码学的新问题：信息安全的概念的演变通信保密(COMSEC)：60-70年代信息保密信息安全(INFOSEC)：80-90年代机密性、完整性、可用性、可控性、不可否认性等信息保障(IA)：90年代-38为什么需要密码?信息的存储：在公开的地方信息的交换：使用非隐秘介质信息的传输：通过不安全信道39威胁和