密码学概述 (Cryptology Summary) 哈尔滨理工大学网络中心 导师 孙名松教授 学生 刘杰

引言 密码学简介 密码学是一门古老而年轻的科学，在当今的信息时代，大量敏感信息如法庭记录、私人文档、软件源代码、银行交易、保险单据等常常通过公共通信设施或计算机网络来进行交换。 为了保证这些信息的私密性、完整性、真实性，必须使用技术手段对其进行处理。 私密性:对信息处理后，保证让他人不能读懂。 真实性:对信息处理后，保证他人不能篡改信息（改了之后会被接收者发觉）。 完整性:对信息处理后，保证他人不能从原始信息中删除或插入其它信息（删除或插入后会被接收者发觉）。

密码学常识 使消息保密的技术和科学叫做密码编码学（cryptography) 密码学（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 2 3 4 5 A B C D E F G H I/J K L M N O P Q R S T U V W X Y Z 表1-1  Polybius校验表 1 2 3 4 5 A B C D E F G H I/J K L M N O P Q R S T U V W X Y Z

古典密码（机械阶段） 古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。古典密码的代表密码体制主要有：单表代替密码、多表代替密码及转轮密码。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） 第二章 密码体制的分类及应用 密码体制 密码体制就是完成加密和解密功能的密码方案。近代密码学中所出现的密码体制可分为两大类：对称加密体制和非对称加密体制。 对称密码体制（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>DES

DES算法介绍 DES是Data Encryption Standard（数据加密标准）的缩写。它是由IBM公司研制的一种加密算法，二十年来，它一直活跃在国际保密通信的舞台上，扮演了十分重要的角色。 DES是一个分组加密算法，它以64位为分组对数据加密。同时DES也是一个对称算法：加密和解密用的是同一个算法。它的密钥长度是56位（因为每个第8位都用作奇偶校验），密钥可以是任意的56位的数。 DES由于密钥长度短，因此不够安全，而且它不易于硬件实现，未来会被渐渐替代（AES），但其设计方法是没有过时的。

算 法 结 构 DES 明文（64bits） IP置换（64bits） L0(32bits) R0(32bits) + f ki L1=R0 R1=L0 f(R0,k1) + 16轮同样运算… L16 R16=L15 f(R15,ki) + IP-1置换（64bits）

DES：IP置换 IP置换表 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 (1) 58表示：结果中位于第1个位置的值，等于原文中第58个位置的值 (2) 图中的一格代表1bit，共有64bit，即8字节

DES：f 的结构(即黑盒变换) R（32bit） K （48bit） E E(R) （48bit） + B1　B2　B3　B4　B5　B6　B7　B8 （48bit） S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C3 C4 C5 C6 C7 C8 （32bit） P

非对称密码体（Asymmetric Encryption） 非对称密码体制也叫公开密钥密码体制、双密钥密码体制。其原理是加密密钥与解密密钥不同，形成一个密钥对，用其中一个密钥加密的结果，可以用另一个密钥来解密 。 目前普遍使用的对称加密算法主要有RSA、Elgamal（离散对数）、ECC（椭圆曲线）等。

RSA算法介绍: 设p、q为两个大素数，n=pq 令φ(n)=(p-1)(q-1) 寻找一对e,d，使ed≡1 mod φ(n) 加密：E(X)=xemod n, x∈Zn 解密：E(y)=ydmod n, X∈Zn (其中x为原文,y为密文) 其原理是初等数论的费马小定理: a的（p-1）次方≡1（mod p）

Hash函数 Hash简单点讲就是把任意一段数据经过某种算法生成一段唯一的固定长度的数据。也叫做摘要。为了确保数据A免受意外或者故意（恶意）的修改，往往用这段数据A产生一个hash数据一起发送出去，Hash一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 目前常用的Hash函数有MD5（128bit）和SHA-1（160bits）等,它们都是以 MD4 为基础设计的。 Hash算法在信息安全方面的应用主要体现在以下的3个方面：

1) 文件校验 我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。 MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。

2) 数字签名 Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称“数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。 3) 鉴权协议 如下的鉴权协议又被称作"挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

第三章 密码技术的应用---数字签名技术 数字签名的定义 信息发送者使用公开密钥算法的主要技术产生的别人无法伪造的一段数字串。发送者用自己的私有密钥加密数据后传给接收者，接收者用发送者的公钥解开数据后，就可确定消息来自于谁，同时也是对发送者发送的信息的真实性的一个证明，发送者对所发信息不能抵赖。

数字签名中使用的加密算法 (1)同时使用非对称加密和哈希函数 (2)目前最常用的是RSA签名算法，常见的是SHA-1、RSA和MD5、 RSA组合 (3)数字签名标准：DSA、ECDSA、DSS

=? Receiver Sender 简单数字签名 原始信息 原始信息 加密结果 （称为签名） Hash算法 Hash算法 Hash值 私钥 加密 公钥 =? 加密结果 （称为签名） 解密 Hash值 Receiver Sender

加 密 信 息 解 密 信 息 =? Sender Receiver 带加密的数字签名 加 密 信 息 解 密 信 息 原始信息 原始信息 Hash算法 Hash算法 发送者 私钥 Hash值 Hash值 加密 =? 发送者公钥 加密结果 （数字签名） 解密 Hash值 Sender Receiver 接收者公钥 接收者私钥

加 密 信 息 解 密 信 息 =? Sender Receiver 改进的带加密的数字签名 加 密 信 息 解 密 信 息 原始信息 原始信息 Hash算法 Hash算法 发送者 私钥 Hash值 Hash值 加密 =? 发送者公钥 加密结果 （数字签名） 解密 Hash值 用接收者公钥加密分组加密密钥 用接收者私钥解密得分组加密密钥 Sender Receiver

CA:认证中心 虚拟世界的权威机构 为了防止上一页里欺骗的例子，必须有一个权威，负责发放和管理数字证书的权威机构。 所有人都信任CA。

A机构的 信息和公钥 CA的数字签名：数字证书 一个人或机构想要公布自己的公钥时，需要找一个CA，让CA对自己的公钥签名。 签名的内容还包含机构的基本信息。 A机构的 信息和公钥 CA的私钥 Hash 算法 如MD5 Hash 值 CA的签名 验证时：用CA的公钥（解密）CA的签名，看看结果是否等于A机构的Hash值。

终点: CA根证书 根证书是CA认证中心给自己颁发的证书，是信任链的起始点。安装根证书意味着对这个CA认证中心的信任。 已经有很多根证书安装在操作系统中，安装根证书可以从网站下载，也可以从颁发机构通过其它安全的途径得到。 CA根证书是CA用私钥对公钥签名的结果。

CA的公钥 (假定CA的公钥是众所周知的) 证书信任链（证书路径） CA私钥 CA公钥 CA的公钥 (假定CA的公钥是众所周知的) CA根证书 CA公钥 CA私钥 A公钥 A的证书 验证A的公钥 CA公钥 A私钥 B公钥 B的证书 验证B的公钥 A公钥

Thank you !