前一课的笔记【网络信息安全】密码学入门笔记

主要内容和重点

1. 密码技术的起源和历史
2. 对称密码
3. 公钥密码
4. 消息验证和数字签名

重点

• 对称加密算法的六条基本要求？其中几条也是现代密码学所有算法的基本要求
• DES算法的简单框图，16轮迭代和16个子**生成
• DES的S盒的计算
• DES的雪崩效应
• 单一性距离的意义、公式
• 用单一性距离说明一次一密理论上难以**
• 三重DES，D-H算法

密码技术的起源和历史

三个阶段：
阶段一(古代~1949)：密码学诞生的前夜

• 这一阶段有众多密码实践，比如二次世界大战中通信密码的应用和破译，但密码学还没有成为一门科学的体系。
• 这一时期的密码专家常常靠直觉、猜测和信念来设计、分析密码，而不是凭借推理和证明。

阶段二(1949~1975)：1949年，香农发表论文《保密系统的通信理论》

• 为对称密码系统奠定了理论基础，使密码成为一门科学。
• 而从1949年到1975年这段时间内，密码学的理论进展不大。

阶段三(1976~现在)：1976年，Diffie和Hellman发表《密码学的新方向》

• 建立了公钥密码系统，引发了密码学上的一次革命性的变革。

随着在密码学理论和技术上的探索和实践，人们逐渐认识到认证和保密是两个独立的密码属性。

Simmons系统研究了认证问题，并建立了一套与香农保密理论平行的认证（Hash）理论。

对称密码

对称密码技术也叫做单钥或常规密码技术，

• 分支1：分组密码技术
• 分支2：流密码技术

在公钥密码技术出现之前，它是唯一的加密类型。

基本原理

对称密码必须满足如下要求：

• 算法足够强大。
  无法通过部分明文密文对计算出**或明文。
• 不依赖于算法的保密，而依赖于**。
  著名的 Kerckhoff 原则。
• 正常加密和解密要快，破译越慢越好。
• 密文相对明文最好无数据位扩展。
• 好的加密算法要具有雪崩效应。
• 好的加密算法的密文很难被压缩。

分组密码

分组密码是一个明文分组被作为一个整体来产生一个等长的密文分组的密码，通常使用的是 64bit 的分组大小。

数据加密标准DES

• DES是一种对二元数据进行加密的算法，将明文消息分成 64bit 一组进行加密。
  密文分组的长度也是 64bit ，没有数据扩展。

• DES使用 “**” 进行加密，“**” 的长度是64bit。

• DES算法中每逢第 8bit 就被忽略(校验位)，因此**的实际大小为 56bit。

• DES整个体制公开，系统的安全性完全依赖**的保密。

DES算法主要包括：

• 初始置换 IP
• 16 轮变换的乘积变换
• 逆初始置换 IP-1
• 16 个**产生器

DES具有雪崩效应：明文或** 1bit 改变引起
密文许多 bit 改变。如果密文的变化太小，很容易找到某种规律从而破译密码。

两种形式的雪崩效应：

• **不变，明文产生1bit变化
  在3次循环后，两个分组有 21bit 不同
  整个加密过程结束后，两个密文有34个位置不同。
• 明文不变，**发生1bit变化
  密文中有大约一半的 bit 不同。

DES算法可能有如下安全问题：

• 算法本身安全，但56位**太小。
  1998年7月，EFE宣布攻破了DES算法，他们使用的是不到25万美元的特殊的“DES破译机”，这种攻击只需要不到3天的时间。

• DES的迭代次数可能太少（16次恰巧能抵抗差分分析）。

• S盒（替代函数S）中可能有不安全因素。

• DES的一些关键部分不应当保密。

S盒代换(S-box Substitution)

• S盒有6位输入，4位输出
• 48位数据经过8个S盒后输出32位数据。
• 将异或后的 48bit 依次分成8组，每组 6bit，分别送入8个S盒中进行代换。
• 每个S盒由一个4行16列的表确定。

算法：对每个S盒，将6位输入的第一位和最后一位组成一个二进制数，用于选择S盒中的一行。用中间的4位选择S盒16列中的某一列，行列交叉处的十进制数转换为二进制数可得到4位输出。

例：对于S1盒而言, 如果输入为011001，则行是01(十进制1，即S盒的第2行)，列1100(12，即S盒的第13列)，该处的值是9，转换为二进制数为1001，即为该S盒的输出.。

单一性距离

已知密文/明文对时，**搜索攻击就是简单地搜索所有可能的**；
没有已知的密文/明文对时，攻击者必须自己识别明文。
(1) 如果报文是以普通英语写成的，可以使用程序自动完成英语的识别。
(2) 如果明文报文在加密之前做过压缩，那么识别工作就更加困难。
(3) 如果报文是某种更一般的类型，如二进制文件，那么问题就更加难以自动化。

单一性距离

• 可在其他事物中测定出所需的只含有合理明文的加密文本的数量。
• 单一性距离越大，密文越难**。
• 计算公式：K/6.8个字符
  • DES：56 / 6.8 = 8.2个字节
  • IDEA：128 / 6.8 = 19个字节
• 如果明文含有一个格式的文件头(例如邮件文件头)，易识别
  如果明文是二进制(压缩文件)，很难识别明文。

用单一性距离说明一次一密是理论上无法**的：
一次一密中，K趋向无穷大，单一性距离非常大，越大所以越难**。

三重DES

三重DES是人们在发现DES**过短，易受到蛮力**而提出的一种替代加密算法。

出现过二重DES，但很快被**。
针对二重DES的**方法：相遇攻击

三重DES 使用3个**，执行3次DES算法。
加密过程为：加密-解密-加密（EDE），可表示为如下的公式：
$C=E_{K3}(D_{K2}(E_{K1}(M)))$C=EK3​(DK2​(EK1​(M)))

为了避免三重DES使用3个**进行三阶段加密带来的**过长(168bit) 的缺点，Tuchman提出使用两个**的三重加密方法，这个方法只要求112bit **，即令其 $K1=K3$K1=K3：
$C=E_{K1}(D_{K2}(E_{K1}(M)))$C=EK1​(DK2​(EK1​(M)))

三重DES的第二阶段的解密并没有密码编码学上的意义。它的唯一优点是可以使用三重DES解密原来的单次DES加密的数据，即$K1=K2=K3$K1=K2=K3。
$C=E_{K1}(D_{K1}(E_{K1}(M)))=E_{K1}(M)$C=EK1​(DK1​(EK1​(M)))=EK1​(M)

国际数据加密算法IDEA

IDEA使用的是 128bit **(最早使用)。IDEA 与 DES 的明显区别在于：循环函数和子**生成函数的不同。

(1) 对循环函数来说，IDEA不使用S盒子，而且IDEA依赖于3种不同的数学运算：

• 异或XOR、
• 16位整数的二进制加法
• 16位整数的二进制乘法

这些函数结合起来可以产生复杂的转换，这些转换很难分析，也很难进行密码分析。

(2) 子**生成算法完全依赖于循环移位的使用，但使用方式复杂，对 IDEA 的8个循环中的每一个都会生成6个子**。

IDEA算法有如下优点：

• 加密速度快
• **产生简单
• 用软硬件都能实现

IDEA 是最早的 128bit 替换中的一个，经历了大量的审查，其安全性主要体现在：

• 穷举搜索破译，要求进行$2^{128}$2128约为$10^{38}$1038次尝试，对每秒完成100万次加密的机器，需要$10^{13}$1013年；
• 能抗差分分析和相关分析攻击；
• 没有 DES 意义下的弱**(**的01串有规律)，但仍然有$2^{51}$251个弱**。

高级加密标准 AES

AES 的基本要求是:

• 比三重 DES 快而且至少和三重 DES 一样安全。
• AES分组长度为 128bit，**长度为 128/192/256 bit。

1998年8月NIST(美国国家标准与技术研究院)召开了第一次 AES 候选会议，并公布了15个 AES 候选算法。
经过一年的考察 MARS、RC6、Rijndael、Serpent、Twofish 共 5 种算法通过了第二轮的选拔。
2000年10月，NIST 选择 Rijndael 作为 AES 的算法。

Rijndael 算法是一种分组长度和**长度均可变的分组密码算法，其分组长度和密码长度都分别可为 128/192/256 bit。

一般说来， Rijndael 汇聚了安全、效率、简单、灵活等优点，使它能成为 AES 最合适的选择。

• 安全性
  Rijndael 算法抗线性攻击和抗差分攻击的能力大大增强。
  没有比穷举更有效的攻击方法。

• 算法的速度
  RC6 需要用到乘法运算，并且需要大量内存；
  Twofish 不便于在硬件中实现；
  Mars 和 Serpent 的速度都不如 Rijndael。

• 灵活性
  Rijndael 的**长度可根据不同的加密级别进行选择。
  Rijndael 的分组长度也是可变的，弥补了DES的弊端。
  Rijndael 的循环次数允许在一定范围内根据安全要求进行修正。

分组加密算法对比

流密码（是通信双方事先共享的，可重复）

流密码是密码体制中的一个重要分支。20世纪50年代，数字电子技术的发展使**可以方便地利用移位寄存器为基础的电路来产生，这促使线性和非线性移位寄存器理论迅速发展。

流密码一直是作为军事和外交场合使用的主要密码技术。通常情况下，流密码总是以明文的位作为加密的单位。

与一次一密的异同：

• 一次一密绝对安全，但没有实用性。
• 流加密在一次一密的基础上，降低安全性，增加实用性。
  **流生成器(硬件的)将一个短的随机 Key 值扩展为一个长得多的伪随机序列，使得与真随机序在计算上不可区分，以替换对真随机Key流的需求，同时又能满足计算上的安全性。

加密和解密过程:

• 加密时，将一段类似于噪声的伪随机序列与明文序列模2加后作为密文序列，这样即使对于一段全“0”或全“1”的明文序列，经过流密码加密后也会变成类似于随机噪声的乱数流。
• 在接收端，用相同的随机序列与密文序列模2加便可恢复明文序列。
• 保持收发两端**的精确同步是实现可靠解密的关键技术。

RC-4

RC-4 是由 RSA 公司的 Rivest 在1987年提出的**长度可变流密码。
它对差分攻击和线性分析具有免疫力，没有短循环，且具有高度非线性，尚无公开的分析结果。
它大约有 $256! * 2562=2^{1700}$256!∗2562=21700 个可能的状态。

公钥密码（基于单向陷门函数）

单向陷门函数包含两个明显特征：

• 一是单向性
  所谓单向性，也称不可逆性。
  即对于一个函数 $y=f(x)$y=f(x)，若已知 $x$x 要计算出 $y$y 很容易
  但是已知 $y$y 要计算出 $x=f ^{-1} (y)$x=f−1(y) 则很困难。
  单向函数的命名就是源于其只有一个方向能够计算。
• 二是存在陷门。
  所谓陷门，也被称为后门。
  对于单向函数，若存在一个 $z$z 使得知道 $z$z 则可以很容易地计算出 $x=f ^{-1}(y)$x=f−1(y)
  而不知道 $z$z 则无法计算出 x = $f ^{-1}(y)$f−1(y)，则称函数 $y=f(x)$y=f(x) 为单向陷门函数，而 $z$z 称为陷门。

公钥密码技术是在试图解决常规加密面临的两个最突出问题**分配和数字签名的过程中发展起来的。

(1) 1976年，Diffie和Hellman创造性地提出了公开密码体制。
(2) 这一体制的最大特点是采用两个**将加密和解密分开：一个公开作为加***，叫做公钥；一个为用户专用，作为解***，叫做私钥。
(3) 要从公钥和密文分析出明文或私钥，在计算上是不可行的。

Diffie-Hellman**交换算法

• Whitfield Diffie 和 Martin Hellman 提出 D-H**交换算法代 —— 公钥密码体制出现
• D-H**交换算法的重大意义 —— 第一次提出不需要保密信道来安全分发对称**
• 公钥加密是重大创新（每人一对**）—— 从根本上改变 加密/解密 过程

公开加密系统中每个用户有两个**，私钥 和 公钥

• 私钥保密，只能在一方保存
• 公钥不保密，可广泛共享
• **对具有数学上特殊的互补关系（一对一关系）
  每个**只能与**对中的另一个**配合进行加/解密。

D-H算法的用途：

• 算法本身只用于**交换，而不能实现加密和数字签名。
• 安全性依赖于计算离散对数的困难性。

D-H算法特点：

• 只在需要时才计算出对称**，对称**不需保存，也不会泄密。
• **交换只需要约定全局参数。
• 不需要 PKI 的支持，目前 SSL、IPSec 等都使用 D-H **交换算法。