密码学基础（一）分组密码与序列密码

密码学

密码学的发展历史密码学简介密码学的典型应用密码学图解 密码算法特性凯撒密码序列密码序列密码的分类同步序列密码自同步序列密码密钥流产生器 分组密码ECB（电子密码本模式）CBC（密码分组链接模式）CFB（密文反馈模式）OFB（输出反馈模式）CTR（计数器模式） 分组密码模式的比较序列密码与分组密码的对比

密码学的发展历史

从公元前400年斯巴达人将莎草纸缠绕到木棍开始，至今密码学已经历过几千年的发展，大体可分为三个阶段：

古代密码学（1949年之前）

主要特点：数据的安全基于算法的保密

古典密码编码方法：置换和代换。置换：明文中的字母重新排列，字母本身不变，但其位置改变了。代换：将明文中的字符替代成其它字符。

近代密码学（1949~1975年）

主要特点：数据的安全基于密钥而不是算法的保密，密码学从此开始成为一门学科。

1949年 克劳德·艾尔伍德·香农 编写了《保密系统的通信理论》，正式奠定了近代密码学的基础。

现代密码学（1976年以后）

产生了新的方向-公钥密码学。

主要特点：解决了秘钥分发和管理的问题，密码学真正广泛应用在商业中。

1976年，罗纳尔多·里弗斯特（Ronald Rivest）、阿迪·沙缪尔（Adi Shamir）和里昂纳多·阿多乐曼（Leonard Adleman）在麻省理工学院推动了公钥加密技术的革新发展，并在1982年三人正式成立了RSA Data Security。

密码学简介

密码学是研究编制密码和破译密码的技术科学。

编码学：研究密码变化的客观规律，应用于编制密码以保守通信秘密的。破译学：应用于破译密码以获取通信情报的。

密码学是研究如何隐秘地传递信息的学科。在现代特别指对信息以及其传输的数学性研究，常被认为是数学和计算机科学的分支，和信息论也相关。

密码学的典型应用

密码学图解

在网络上通讯时，始终假设有第三人对信息进行窃取或者篡改。

alice和Bob是密码学中通讯的双方，Oscar是想窃听或者篡改信息的家伙。

在Alice和Bob通讯中，需要保证信息的安全，首先要解决的是怎么证明信息一定是Alice发的。为了实现这一目的，Alice会在消息上附上自己的数字签名。

数字签名通过非对称加密算法实现，它是用Alice私钥进行加密的某些特定信息，并且由Bob拿到的Alice的公钥对这个已加密信息进行解密。

由于数字签名附在消息上，数签又是由Alice的密钥对其进行处理，因此能证明这个信息是Alice发出的。

证明了发信人以后，还要保证信息不被窃听。于是Alice和Bob会选择通过对称加密的方式对消息进行加密。

对称密钥加密：双方共享一个密钥，并使用相同的加密方法和解密方法。

对称加密的效率比非对称加密的效率高100~1000倍，所以一般使用对称加密。

Alice和Bob共享一个密钥，Alice加密完成后还需要通过网络将密钥传递给Bob，这会导致信息很容易被窃听。所以还需要使用非对称加密对密钥（加密信息所产生的密钥）再次进行加密。

非对称加密：Whitfield Diffie,Martin Hellman,Ralph Merkle在1976年提出的密码类型。

非对称加密：与对称密码学一样，在公钥密码学中用户也有一个密钥（也叫私钥）；但不同的是，他同时还拥有一个公钥。

解决了密钥传递的问题，还需要确定传递过来的信息没有被篡改（篡改了加密后的消息会使得密文跟着改变）。因此我们需要在对信息加密前进行摘要提取，如图由Alice对信息提取摘要并公布摘要，由Bob验证摘要。

摘要提取主要通过摘要提取算法进行。

所以，Alice和Bob通讯的整个流程如图所示：

密码算法特性

凯撒密码

凯撒密码的思路：将字表中的一个字符用另一个字符进行替换。

凯撒密码的加密方法：通过将当前字母替换为常规字母表中第n个位置后的字母。

这种密码非常容易被破解（例如：蛮力攻击和穷尽密码搜索）。

序列密码

序列密码：将明文和密钥进行异或运算。

序列密码就是对密文进行逐一的加密或者解密。

序列密码用于单独加密每个位。他是通过将密钥序列中的每个位与每个明文位相加实现的。

序列密码也称为流密码（Stream Cipher），它是对称密码算法的一种。序列密码具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点，因此在实际应用中，特别是专用或机密机构中保持着优势，典型的应用领域包括无线通信、外交通信。

序列密码的安全性能主要取决于密钥流或者密钥流产生器的特性。

优点：实现简单、加密和解密速度快、安全性能较好、没有或少有差错传播

缺点：1.密钥长度与明文长度一致；2.序列密码容易被篡改。

序列密码通常用于传输协议中。如：RC4（最常用的流密码之一），它的密钥长度可变，用于SSL协议，以前曾被应用在802.11WEP协议标准中。

序列密码的分类

同步序列密码

同步序列密码的原理：

种子密钥k经过由安全信道传送给收、发双方后，由密钥流产生器生成加密和解密所需要的密钥流，而加、解密本身就是简单的模2加法运算。同步序列密码的特点：

① 密钥流仅仅依赖于种子密钥和密钥流产生器的结构，而与明文流（或密文流）无关。

② 如果密钥流完全随机产生且长度至少和明文流一样长，则可实现绝对安全的“一次一密”。但实际上，这很难做到。

③ 无差错传播。因为密钥流独立于密文流，所以一个密文的传输错误不会影响下一个密文的解密。

④ 为了保障接收端能够正确解密，要求收、发双方必须严格同步。

自同步序列密码

自同步序列密码的简介：

与同步序列密码需要收、发双方严格同步不同，自同步序列密码能够依靠自身的能力“自动地”实现收、发双方的同步，因而是一种不需要外部同步的序列密码系统。自同步序列密码的特点：

①密钥流不仅依赖于种子密钥和密钥流产生器的结构，还与密文流（或明文流）有关。初始向量IV在这里相当于初始密文的作用，要求收、发双方必须相同。

②自同步。解密只取决于先前特定数量的密文字符，因此，即使出现删除、插入等非法攻击，收方最终都能够自动重建同步解密，因而收、发双方不再需要外部同步。

③ 有差错传播。因为密钥流与密文流有关，所以一个密文的传输错误会影响下面有限个密文的解密。

密钥流产生器

密钥流产生器是决定序列密码安全性能的主要因素，因而线性反馈寄存器是密钥流产生器最基本也是最重要的部件。

1.线性反馈移位器

定义：如果将移位寄存器的某些级的输出通过异或（模2加）运算函数运算后反馈回它的第一级输入端，便构成了线性反馈移位寄存器。该式为用右移方式的n级线性反馈移位寄存器的反馈函数，其中如果n级线性反馈移位寄存器产生的输出序列的周期为2^n-1，则称为m序列产生器。m序列不仅周期长，而且伪随机特性好，这正是序列密码的密钥流所需要的特性。

2.基于LFSR的密钥流产生器

分组密码

分组密码(blockcipher)的数学模型是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每个组有m个字节，每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。分组密码只能加密固定长度的分组，需要加密的明文长度可能超过分组密码的分组长度，此时就需要对分组密码算法进行迭代，以便将长明文进行加密，迭代的方法就称为分组密码的模式。注：当需要加密的分组短于分组密码的长度时，需要在明文中添加相应长度的特定数据进行填充

ECB（电子密码本模式）

将明文分组加密后结果直接成为密文分组。明文分组与密文分组是一一对应的关系；且每个明文分组各自独立地进行加密和解密。这种加密攻击者无需破译密码就能操纵明文。

CBC（密码分组链接模式）

先将明文与前一个密文分组进行异或（XOR）运算，再进行加解密。初始化向量（IV）：在加密第一个明文分组时，需要事先准备一个长度为一个分组的比特序列代替；每次加密时，都会随机产生一个不同的比特序列作为初始化向量。无法对单独一个中间的明文分组加密；对初始化向量没有加密。当CBC模式中的密文分组有一个分组损坏，只要密文分组的长度没有发生变化，解密时最多会有两个分组受到数据损坏的影响。当CBC的密文分组中有一些比特缺失了，导致密码分组的长度发生变化，此分组发生错位，在缺失比特位置之后的密文分组也就无法全部解密了。这种加密攻击者一般只能攻击初始化向量。

CFB（密文反馈模式）

前一个密文分组会被送回到密码算法的输入端。密文分组与明文分组之间只有XOR（而CBC中，明文分组与密文分组之间有XOR和密码算法两个步骤）。CFB模式中有密码算法产生的比特序列成为密钥流（在CFB中密码算法相当于伪随机数生成器）。在CFB中分组密码算法在解密时仍执行加密操作（因为密钥流通过加密生成）。对CFB模式可实施重放攻击。

OFB（输出反馈模式）

密码算法的输出会反馈到密码算法的输入中并非通过密码算法加密明文分组的，而通过将明文分组和密码算法的输出进行XOR来产生密文分组（与CFB的区别在于密码算法的输入）CFB是对密文分组进行反馈，必须按顺序进行加密；OFB是对密钥流进行加密（生成密钥流与XOR运算可以并行）

CTR（计数器模式）

通过将逐次累加的计数器进行加密来生成密钥流每个分组对应一个逐次累加的计数器每次加密都会生成一个不同的值（ｎｏｎｃｅ）作为计数器的初始值，且在每次加密时都必须不同在初始值之后为分组序列号，会逐次累加在CTR中如果密文分组有１ｂｉｔ被反转，解密后的铭文中所对应的比特会被反转，该错误不会放大

总结：

分组密码模式的比较

序列密码与分组密码的对比

分组密码以一定大小作为每次处理的基本单元，而序列密码则是以一个元素（一个字母或一个比特）作为基本的处理单元。序列密码是一个随时间变化的加密变换，具有转换速度快、低错误传播的优点，硬件实现电路更简单；其缺点是：低扩散（意味着混乱不够）、插入及修改的不敏感性。分组密码使用的是一个不随时间变化的固定变换，具有扩散性好、插入敏感等优点；其缺点是：加解密处理速度慢、存在错误传播。