密码学概述Cryptology Summary.ppt

密码学概述 (Cryptology Summary)哈尔滨理工大学网络中心 导师 孙名松教授 学生 刘杰引言 密码学简介• 密码学是一门古老而年轻的科学，在当今的信息 时代，大量敏感信息如法庭记录、私人文档、软 件源代码、银行交易、保险单据等常常通过公共 通信设施或计算机网络来进行交换 • 为了保证这些信息的私密性、完整性、真实性， 必须使用技术手段对其进行处理 – 私密性:对信息处理后，保证让他人不能读懂 – 真实性:对信息处理后，保证他人不能篡改信息（改了 之后会被接收者发觉） – 完整性:对信息处理后，保证他人不能从原始信息中删 除或插入其它信息（删除或插入后会被接收者发觉） 密码学常识 – 密码学（cryptology）作为数学的一个分支，是密码编码学和密码分析学的统称使消息保密的技术和科学叫做密码编码学（cryptography) 破译密文的科学和技术就是密码分析学（cryptanalysis） – 明文：是作为加密输入的原始信息，即消息的原始形 式，通常用m或p表示所有可能明文的有限集称为明文空间，通常用M或P来表示。

.– 密文：是明文经加密变换后的结果，即消息被加密处 理后的形式，通常用c表示所有可能密文的有限集称 为密文空间，通常用C来表示 – 密钥：是参与密码变换的参数，通常用k表示一切可 能的密钥构成的有限集称为密钥空间，通常用K表示 – 加密算法：是将明文变换为密文的变换函数，相应的 变换过程称为加密，即编码的过程（通常用E表示，即 c=Ek(p)） – 解密算法：是将密文恢复为明文的变换函数，相应的 变换过程称为解密，即解码的过程（通常用D表示，即 p=Dk(c)）第一章 密码学的发展历史密码学的发展历程大致经历了三个阶段：古代加密方法、 古典密码和近代密码 • 古代加密方法（手工阶段） 源于应用的无穷需求总是推动技术发明和进步的直接 动力存于石刻或史书中的记载表明，许多古代文明，包 括埃及人、希伯来人、亚述人都在实践中逐步发明了密码 系统从某种意义上说，战争是科学技术进步的催化剂 人类自从有了战争，就面临着通信安全的需求，密码技术 源远流长 – 古代加密方法大约起源于公元前440年出现在古希腊战 争中的隐写术当时为了安全传送军事情报，奴隶主 剃光奴隶的头发，将情报写在– 奴隶的光头上，待头发长长后将奴隶送到另一个部落 ，再次剃光头发，原有的信息复现出来，从而实现这 两个部落之间的秘密通信。

– 密码学用于通信的另一个记录是斯巴达人于公元前400 年应用Scytale加密工具在军官间传递秘密信息 Scytale实际上是一个锥形指挥棒，周围环绕一张羊皮 纸，将要保密的信息写在羊皮纸上解下羊皮纸，上 面的消息杂乱无章、无法理解，但将它绕在另一个同 等尺寸的棒子上后，就能看到原始的消息 – 我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等 形式，将要表达的真正意思或“密语”隐藏在诗文或画卷 中特定位置的记载，一般人只注意诗或画的表面意境 ，而不会去注意或很难发现隐藏其中的“话外之音”– 传输密文的发明地是古希腊，一个叫Aeneas Tacticus 的希腊人 ,他使用了一个称为Polybius的校验表，这个 表中包含许多后来在加密系统中非常常见的成分，如 代替与换位Polybius校验表由一个5×5的网格组成（ 如表1-1所示），网格中包含26个英文字母，其中I和J 在同一格中每一个字母被转换成两个数字，第一个 是字母所在的行数，第二个是字母所在的列数如字 母A就对应着11，字母B就对应着12，以此类推使用 这种密码可以将明文“message”置换为密文“32 15 43 43 11 22 15”。

在古代，这种棋盘密码被广泛 使用– 表1-1 Polybius校验表123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ• 古典密码（机械阶段）– 古典密码的加密方法一般是文字置换，使用手工或机械变换的方 式实现古典密码系统已经初步体现出近代密码系统的雏形，它 比古代加密方法复杂，其变化较小古典密码的代表密码体制主 要有：单表代替密码、多表代替密码及转轮密码Caesar密码就 是一种典型的单表加密体制；多表代替密码有Vigenere密码、Hill 密码；著名的Enigma密码就是第二次世界大战中使用的转轮密码 – 在第一次世界大战期间，敌对双方都使用加密系统（Cipher System），主要用于战术通信，一些复杂的加密系统被用于高级 通信中，直到战争结束而密码本系统（Code System）主要用 于高级命令和外交通信中 – 到了20世纪20年代，随着机械和机电技术的成熟，以及电报和无 线电需求的出现，引起了密码设备方面的一场革命——发明了转 轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的 重要标志之一美国人Edward Hebern认识到：通过硬件卷绕实 现从转轮机的一边到另一边的单字母代替，然后将多个这样的转 轮机连接起来，就可以实现几乎任何复杂度的多个字母代替。

转 轮机由一个键盘和一系列转轮组成，每个转轮是26个字母的任意 组合转轮被齿轮连接起来，这样就能实现当一个齿轮转动当一个转轮转动时，可以将一个字母转换成另一个字母 照此传递下去，当最后一个转轮处理完毕时，就可以得到 加密后的字母为了使转轮密码更安全，人们还把几种转 轮和移动齿轮结合起来，所有转轮以不同的速度转动，并 且通过调整转轮上字母的位置和速度为破译设置更大的障 碍 – 典型的密码机Hagelin C-48型（即M-209 )是哈格林对 C-36改进后的产品 ,共由6个共轴转轮组成，每个转轮 外边缘分别有17, 19, 21, 23, 25, 26个齿，它们互为素 数，从而使它的密码周期达到了26×25×23×21×19×17 = 101 405 850(数量级达到了亿) • 近代密码（计算机阶段） – 密码形成一门新的学科是在20世纪70年代，这 是受计算机科学蓬勃发展刺激和推动的结果 快速电子计算机和现代数学方法一方面为加密 技术提供了新的概念和工具，另一方面也给破 译者提供了有力武器计算机和电子学时代的 到来给密码设计者带来了前所未有的自由，他 们可以轻易地摆脱原先用铅笔和纸进行手工设 计时易犯的错误，也不用再面对用电子机械方 式实现的密码机的高额费用。

总之，利用电子 计算机可以设计出更为复杂的密码系统• 关于二战的密码小插曲:– 计算机和电子学时代的到来使得美国在1942年制造出 了世界上第一台计算机.二战期间,日本采用的最高级别 的加密手段是采用M-209转轮机械加密改进型—紫密, 在手工计算的情况下不可能在有限的时间破解,美国利 用计算机轻松地破译了日本的紫密密码,使日本在中途 岛海战中一败涂地,日本海军的主力损失殆尽. 1943年, 在获悉山本五十六将于4月18日乘中型轰炸机，由6架 战斗机护航，到 中途岛视察时,罗斯福总统亲自做出决 定截击山本,山本乘坐的飞机在去往中途岛的路上被美 军击毁,山本坠机身亡,日本海军从此一蹶不振.密码学的 发展直接影响了二战的战局!• 密码学的理论基础 – 密码学的理论基础之一是1949年Claude Shannon发表 的“保密系统的通信理论”（The Communication Theory of Secrecy Systems），这篇文章发表了30年 后才显示出它的价值1976年W.Diffie和M.Hellman发 表了“密码学的新方向”（New Directions in Cryptography）一文，提出了适应网络上保密通信的 公钥密码思想，开辟了公开密钥密码学的新领域，掀 起了公钥密码研究的序幕。

受他们的思想启迪，各种 公钥密码体制被提出，特别是1978年RSA公钥密码体 制的出现，成为公钥密码的杰出代表，并成为事实标 准，在密码学史上是一个里程碑 – 1976美国国家标准局（NBS，即现在的国家标准与技 术研究所NIST）正式公布实施了美国的数据加密标准 （Data Encryption Standard，DES），公开它的加密 算法，并被批准用于政府等非机密单位及商业上的保 密通信第二章密码体制的分类及应用• 密码体制 • 密码体制就是完成加密和解密功能的密码方案近代密码 学中所出现的密码体制可分为两大类：对称加密体制和非 对称加密体制 • 对称密码体制（Symmetric Encryption） – 对称密码体制也称为秘密密钥密码体制、单密钥密码 体制或常规密码体制，对称密码体制的基本特征是加 密密钥与解密密钥相同对称密码体制的基本元素包 括原始的明文、加密算法、密钥、密文及攻击者– 发送方的明文消息P = [P1，P2，…，PM]，P的M个元 素是某个语言集中的字母，如26个英文字母，现在最 常见的是二进制字母表{0,1}中元素组成的二进制串 加密之前先生成一个形如K = [K1，K2，…，KJ]的密 钥作为密码变换的输入参数之一。

该密钥或者由消息 发送方生成，然后通过安全的渠道送到接收方；或者 由可信的第三方生成，然后通过安全渠道分发给发送 方和接收方 – 发送方通过加密算法根据输入的消息P和密钥K生成密 文C = [C1，C2，…，CN]，C=EK(P) – 接收方通过解密算法根据输入的密文C和密钥K恢复明 文P = [P1，P2，…，PM]，即P = EK(C) – 目前普遍使用的对称加密算法主要有DES、3DES、 RC4、RC5和AES（Rijndeal算法）等，AES是目前最 新的加密标准，DES将被渐渐淘汰 – 安全性 AES>3DES>DESDES算法介绍DES是Data Encryption Standard（数据加密标准）的缩写 它是由IBM公司研制的一种加密算法，二十年来，它一直活 跃在国际保密通信的舞台上，扮演了十分重要的角色DES是一个分组加密算法，它以64位为分组对数据加密同时 DES也是一个对称算法：加密和解密用的是同一个算法它的 密钥长度是56位（因为每个第8位都用作奇偶校验），密钥可以 是任意的56位的数。

DES由于密钥长度短，因此不够安全，而且它不易于硬 件实现，未来会被渐渐替代（AES），但其设计方法是没有过 时的明文（64bits）IP置换（64bits）L0(32bits)R0(32bits)L1=R0R1=L0 f(R0,k1)fki+16轮同样运算…L16+R16=L15 f(R15,ki)+IP-1置换（64bits）DES算法结构IP置换表 585042342618102 605244362820124 625446383022146 645648403224168 57494133251791 595143352719113 615345372921135 635547393123157(1) 58表示：结果中位于第1个位置的值，等于原文中第58个位置的值(2) 图中的一格代表1bit，共有64bit，即8字节DES：IP置换DES：f 的结构(即黑盒变换)R（32bit）EE(R) （48bit）K （48bit）B1 B2 B3 B4 B5 B6 B7 B8S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P+（48bit）（32bit）• 非对称密码体（Asymmetric Encryption ） – 非对称密码体制也叫公开密钥密码体制、双密钥密码体制。

其原 理是加密密钥与解密密钥不同，形成一个密钥对，用其中一个密 钥加密的结果，可以用另一个密钥来解密 – 目前普遍使用的对称加密算法主要有RSA、Elgamal（离散对数）。