绪论

网络信息安全概述

信息安全问题的来源：

1. 网络自身安全缺陷
2. 网络开放性
3. 人为因素

隐私泄露事件：Uber泄露用户信息、前些时间某快递公司采用明文存储导致数据库被拖

信息安全五大属性

机密性、可用性、完整性、认证性、不可否认性

密码学发展历史

• 经典密码
• 手工加密阶段：凯撒移位密码
• 机械加密阶段：维吉尼亚密码
• 现代密码-计算机加密阶段：DES+RSA
• 第一次质的飞跃：1949-香农-保密系统的通信理论-密码学学科
• 第二次质的飞跃：1976-D+H-密码学的新方向-公钥密码

手工加密阶段	主要基于手工方式实现，简单
机械加密阶段	轮转机的出现大大提高密码加密速度
现代密码学	理论蓬勃发展、范围不断扩张、消息、新兴技术出现

网络信息安全的机制和安全服务

安全机制

用来保护系统免受侦听，阻止安全攻击及恢复系统的机制

• 特定安全机制
• 加密
• 数字签名
• 访问控制
• 数据完整性
• 认证交换
• 流量填充
• 路由控制
• 公证
• 通用安全机制

安全服务

加强数据处理系统和信息传输安全性的一类服务，其目的在于利用一种或多种安全机制阻止安全攻击

1. 机密性：不泄露给未授权用户的特性。信息安全最基本的需求
2. 完整性：未经授权不能进行改变
3. 鉴别：实体认证和数据源认证
4. 非否认性：不可抵赖性
5. 访问控制：定义：限制或控制经通信链路对主机系统和应用程序等系统资源进行访问的能力；策略模型：基于身份、规则、角色的策略
6. 可用性：可被授权实体访问并按需求使用的特性

安全攻击

• 截取
• 中断：DoS，攻击者通过删除某一连接的所有协议数据单元PDU，从而抑制所有的消息指向某个特殊的目的地
• 篡改
• 伪造
• 重放
• 否认

• 被动攻击
• 只截取一个连接的PDU，不修改数据或危害系统。
• 主动攻击
• 通过对PDU进行各种处理，威胁数据的完整性、机密性和可用性等

密码相关法律

• 2019.10：《密码法》
• 中国密码分级
• 核心
• 普通
• 商用
• 个人

密码学基础

密码学相关概念

密码学是密码编码学和密码分析学的统称

• 密码编码学：设计密码算法
• 密码分析学：从密文推算出明文、密钥、解密算法

加密体制

• 明文 PlainText
• 密文 CipherText
• 密钥 Key
• 加密算法 Encryption
• 解密算法 Decryption

五种安全级别刻画

• 唯密文攻击
• 密码分析者只知道密文，最容易实施，是密码算法设计的最低要求
• 已知明文攻击
• 密码分析者知道部分明-密文对
• 选择明文攻击
• 密码分析者能选择部分明文来获取对应密文
• 选择密文攻击
• 密码分析者能选择部分密文来获取对应明文
  • 非适应性选择密文攻击
  • 尝试破解目标密文之前可以访问解密预言机，之后不行
  • 适应性选择密文攻击
  • 尝试破解目标密文前后都可访问

上述攻击的难度是逐渐递减的，强度是逐渐递增的，安全级别（抵挡住某一级别的攻击）是逐渐增高的。

前两种是被动的，后三种是主动的。

前两种是切合实际的，任何合理的加密方案都应满足前两者，后三种是有点特殊的。

密码系统

用于加密与解密的系统，是明文与加密密钥作为加密变换的输入参数，经过一定的加密变换处理以后得到的输出密文；基于密文与解密密钥，经解密变换恢复明文。

包括：加密算法、解密算法、明文空间、密文空间、密钥、信源、信宿、敌手等

科尔霍夫原则

算法必须公开，对密钥进行保护。

密码系统的安全条件

• 密码破译的级别
• 衡量攻击方法的复杂性
• 评价密码体制安全性的三个途径
• 计算安全性
  • 密码分析方法：穷举攻击、统计分析攻击、数学分析攻击
• 可证明安全性：安全性严格建立在一些广泛接受的计算困难性假设上（大整数分解、离散对数问题等）
• 无条件安全性：计算资源不受限依然无法攻破

• 理论上，任何实用的密码都是可破的
• 我们追求的是计算上的安全
• 一个密码系统实际可用，需要满足：
• 有效计算
• 攻击者获得密文不能在有效时间内破解
• 穷举搜索不可行（密钥空间足够大）

安全模型

• 网络传输中信息安全
• 信道是将消息从一个实体传输到另一个实体的一种物理的或逻辑的通道
• 计算机系统中信息安全

密码体制

对称密码

优点

• 加解密速度快，密钥相对较短

缺点

• 密钥分发管理困难
• 双方需要事先共享密钥
• 存在数字签名难问题（不满足不可抵赖性）

公钥密码体制

非对称密码算法有一个密钥对，公钥可以公开，私钥由密钥持有人自己秘密保存，且不能由公钥推导出私钥

优点

• 密钥便于管理
• 可以实现数字签名

缺点

• 加密解密速度相对慢，密钥位数较多

古典密码

隐写术

隐写术和加密的区别与联系

隐写术能够进行秘密通信隐藏消息本身存在，加密很容易被发现秘密通信双方通过转换编码使得原消息内容变得不可理解。

代替

代替密码体制

• 单表代换密码
• 凯撒密码 K=3
• 使用密钥的单表代替加密
• 仿射加密
• 多表代替密码
• Playfair：补全字母表（5X5，IJ算作一个字母）->明文每两个字母为一组进行加密->同行靠右、同列在下、否则矩形对角（按反序)
• Vigenere：密文=明文+密钥(mod 26) t+c-1=v
• Hill：将明文分为同等大小的组，按组整体加密，将一个分组中的d个连续明文字母通过线性变换转换为d个密文字母，解密使用逆变换

频率分析攻击

统计学的思想

1. 对密文中各个字母的出现频次进行分析
2. 与英语字母标准频率进行对比分析，做出假设
3. 证实假设或继续做其他假设

换位（置换）

凯撒（移位）密码等

小结

• 隐写术、代替、移位一般是结合使用
• 以近代密码学的观点来看，许多经典密码是不安全的（极易破译），但其历史地位是不可忽略的
• 编制经典密码的基本方法对于编制近代密码任然有效

密码学的数学引论

数论

素数

除数：
若𝑎=𝑚𝑏，其中𝑎,𝑚,𝑏均为整数，则当𝑏≠0时，称𝑏整除𝑎，记 作：𝑏|𝑎，并称𝑏是𝑎的一个除数（或因子）。

素数：
若整数𝑝>1且因子只有±1,±𝑝,则称𝑝为素数（质数）；否则，称为合数。

公约数：
若𝑎,𝑏,𝑐∈Z，如果𝑐∣𝑎，𝑐∣𝑏，称𝑐是𝑎和𝑏的公约数。

最大公约数记作：𝑔𝑐𝑑（𝑎,𝑏）＝𝑑,或简记为（𝑎,𝑏）＝𝑑。

若𝑔𝑐𝑑（𝑎,𝑏）=1，称𝑎与𝑏是互素的。

模

模和余

同余

如果𝑎 𝑚𝑜𝑑 𝑚 =𝑏 𝑚𝑜𝑑 𝑚，则称整数𝑎和𝑏模𝑚同余，可写作：a ≡ 𝑏（𝑚𝑜𝑑 𝑚），𝑚称为模数。

称与𝑎模𝑚同余的数的全体为𝑎的同余类，记为[𝑎]，称𝑎为这个同余类的表示元素。

性质：

模运算

模指数运算

欧几里得算法

对任何非负整数𝑎和𝑏：

辗转相除法(求最大公因数gcd)

拓展欧几里得算法

如果两个正整数互素（最大公约数为1），则可以求解其中一个数关于另一个数的逆元

求逆元方法：

最后应该化成ax+by=1的形式，x即为a模b的乘法逆元。

首步的式子来源于求gcd的倒数第二步

费马定理

欧拉定理

群、环、域

群：封闭性、可结合性、存在单位元和幺元

环和域：

域的实质：域是一个可以在其上进行加法、减法、乘法和除法运算而结果不会超出域的集合。如有理数集合、实数集合、复数集合都是域，但整数集合不是。

计算复杂性理论

• 算法的复杂性：可以用这个问题的算法的计算时间和存储空间来描述。如果破译一个密码方案所需的时间是指数阶的，则认为其在计算上是安全的。
• 问题的复杂性：问题根据解法的复杂性可以分为：P问题、NP问题、NPC问题。

对称密码体制

分组密码

明文分组长度：𝑛，密文分组长度：𝑚； 通常取𝑛=𝑚。

分组密码设计

准则

• 分组长度n要足够大
• 密钥量要足够大
• 由密钥确定的置换算法足够复杂
• 加密和解密运算简单
• 数据拓展尽可能小
• 差错传播尽可能小

原理

• 扩散和混淆是分组密码最本质的要求
• 扩散：将明文中的统计特性散布到密文中去，隐藏明文统计特性
• 混淆：使密文和明文之间的统计关系变得尽可能复杂，隐藏密文和密钥之间的关系
• 乘积密码：扩散和混淆的组合变换（多次迭代）
• Feistel结构即为乘积形式的密码变换。

常见分组密码模式

• 电子码本-ECB：直出、并行处理、安全性最弱，同一个消息中的两个相同的明文被加密成相同的密文
• 密码分组链接-CBC：每个密文分组不仅依赖于产生他的明文分组还依赖于前面的所有分组、非并行、同一个消息中的两个相同的明文被加密成不同的密文（后面几种都是）
• 密码反馈-CFB：
• 输出反馈-OFB:无错误传播，是软件加密的最好选择。
• 计数模式-CTR

Feistel(分组密码的迭代结构)

代换：每轮右半经过F函数后再与左半进行异或

置换：每轮的子密钥Ki不同，代换完成后再交换左右两半

对于Feistel结构而言，其分组长度、密钥长度、迭代轮数越多，子密钥生成算法越复杂则安全性越高

• S盒
• 不宜过大，唯一非线性组件
• P盒
• 实现雪崩效应（输入（明文或密钥）即使只有很小的变化，也会导致输出发生巨大变化的现象）--AES具有良好的雪崩效应特性
  • 普通型P盒：输入输出均为n时，有n!种映射关系
  • 压缩型P盒：输出位数小于输入
  • 拓展型P盒
• 轮函数
• 安全性、速度、灵活性
• 迭代轮数
• 使密码分析的难度大于简单穷尽搜索攻击的难度
• 子密钥的生成方法
• 实现简单、速度、无弱密钥

DES

有效密钥长度为56bits，是严格的Feistel密码结构

设计的一般准则

• 随机性
• 雪崩效应
• 完全性：每个输出位都是所有输入位的一个复杂函数
• 非线性性
• 相关免疫性

初始置换IP

逆：

作用在于打乱原来输入𝑥的ASCII码字划分的关系

F轮函数

E拓展

S盒

P置换

把数据打乱重排

乘积变换体现在：

选择拓展运算E->密钥加密运算->选择压缩运算S

子密钥产生

（密钥编排）

64位密钥经过置换选择1、循环左移、置换选择2等变换，产生16个子密钥𝐾1,𝐾2,…,𝐾16,分别供各次加密迭代使用。

解密过程

二重与三重DES

利用DES进行两次加密，其强度不等于112bit密钥的强度

中间相遇攻击(Meet-in-the-Middle Attack)：这种攻击不依赖于 DES的任何特性，因而可用于攻击任何分组密码。

所以在实施中间相遇攻击时，如果已知两个明密文对，则找到正确密钥的概率为1−2^16。

3DES：

相较于DES，增加了抗差分分析和线性分析的能力但处理的速度较慢。

非对称密码体制

为了解决对称加密体制的密钥管理难、数字签名困难的问题，非对称密码体制应运而生。

公钥加密体制的原理

• 由接收者B 产生一对密钥PK和SK
• 将PK存放在一个公开的寄存器中，SK由用户保存
• 若发送者想要向B发送消息m，首先要获得PK对m加密
• B收到A加密的密文C后，用自己的SK做解密得到明文消息

陷门单向函数

D-H密钥交换协议

解决公钥加密体制密钥交换问题：KDC

Diffie-Hellman密钥交换：算法描述

安全性基于离散对数问题的困难性

公钥加密

安全性定义

可证明安全（语义安全）

是完美安全性的多项式版本，攻击者具有的攻击能力是多项式阶的，即使攻击者能够选择明文并观察其密文，也不能从密文中推断出明文的有关信息。

多项式安全性

它是指在多项式时间内，攻击者无法区分两个不同的明文所产生的密文。

完美安全

如果一个具有无限计算能力的敌手从给定的密文中不能获取明文的任何有用信息，我们就说这个加密体制具有完美安全性或信息论安全性。

能达到这个安全条件的加密算法为“一次一密”（公钥加密体制是不可能达到的，因为其密钥长度短而且会被使用多次），公钥加密填通常符合前两项安全定义。

公钥加密特点

• 随机性：加密算法是随机的
• 确定性：解密算法是确定
• 安全性（单向性）：各种不可行性
• 有效性：密钥生成是容易的
• 一致性
• 陷门性

实例

基于大整数因子分解问题的公钥密码系统（RSA方案）

基于有限域乘法群上的离散对数问题的公钥密码（ElGamal方案）

基于椭圆曲线上离散对数问题的椭圆曲线公钥密码系统（ECC）

RSA

公钥:{e,n} 私钥:{d,n}

实例

设计公钥密码体制的安全要求是IND-CCA（选择密文攻击下不可密文区分），有时也称是达到了语义安全

杂凑算法与消息认证

杂凑函数

数据的保密性：古典密码体制、序列密码（流密码）、分组密码

数据的完整性：可以用杂凑函数来完成

不可逆映射，由任意长度输入得到固定长度输出

别称：散列函数、杂凑函数

特征：算法公开、数据压缩、容易计算

安全性要求：（要求逐渐增加）

• 单向性：给哈希值找原数字
• 抗弱碰撞性：给x找哈希值相同的另一x
• 抗强碰撞性：给定相等哈希值，找满足此的原始数字对

• 如果hash函数H是抗强碰撞的，则H一定是抗弱碰撞的。
• 已知H是抗强碰撞的，则H不一定是单向的。

哈希碰撞

不同消息产生相同哈希值

碰撞是存在的，但是没人能按要求找到一个碰撞

哈希函数一般结构

预处理:附加填充比特+长度分组

用一个公开算法在消息𝑥的右方添加若干位，得到比特串 𝑦，使得𝑦的长度为𝑡的整数倍。(t是压缩的位数)

迭代处理

反复利用压缩函数

输出变换

哈希函数一般构造

常见哈希函数：MD4、MD5、SHA

三种构造类型：

• 直接构造复杂的非线性关系实现单向性
• 基于分组密码的哈希函数
• 基于计算复杂性的方法

直接构造法-SHA-1

附加填充位->初始化缓冲区->以512位的分组为单位压缩n次，最终输出160b

✅基于分组密码构造-CFB

选取初始值并按照分组密码模型计算

基于计算复杂性方法的构造

大整数分解、离散对数问题等。

安全性可以证明。

哈希函数的攻击

一般而言，抗强碰撞是最容易实现的

消息认证

把不带密钥的哈希函数称为修改检测码（MDC）：完整性

把带密钥的哈希函数称为消息鉴别码（MAC）：身份验证

消息验证码是指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值，也被称作校验和。

MAC的安全性定义

MAC的安全性是指：自适应选择消息攻击下的存在性不可伪造

MAC构造方法

分组密码构造MAC

• 文件的制造者和检验者共享密钥
• 检验者实现得知文件冗余度
• 检验者检验约定的冗余度是否正确

基于哈希函数构造HMAC

直接利用哈希函数来构造MAC

数字签名

数字签名的工作原理

• 创建数字签名
• 计算文件哈希
• 用私钥对哈希值进行签名:{x,y}
• 阅读数字签名
• 计算文件哈希值
• 用公钥解密签名
• 比较文件哈希和私钥解密的签名值是否相等（若相等则可说明消息来源和未被篡改）

数字签名的性质

• 可信的：任何人都可以验证签名
• 不可伪造
• 不可复制：对一个消息的签名不能通过复制变为另一个消息的签名
• 不可改变
• 不可抵赖：签名者事后不能否认自己的签名（签名的产生必须使用发送方独有的一些信息）

分类

• 基于数学难题分类：RSA
• 基于数字签名是否具有恢复特性分类：改进RSA
• 基于不同加密方法分类
• 基于签名用户分类
• 基于签名人对消息是否可见分类
• 基于签名人是否受别人委托分类
• 基于签名是否有仲裁分类

安全性定义

选择消息攻击下的存在性不可伪造

数字签名与MAC的区别

• 当发送方需要与多个接收方通信时使用数字签名（方便密钥管理，发送者只需要计算一个签名）
• 数字签名可以公开验证
• 数字签名可以传递（传递性和公开验证是将数字签名应用到证书和公钥基础设施的基础）
• 数字签名具有不可抵赖性（一旦S对某一个消息进行签名此后都不能否认）；而MAC不具备（接收者无法证明MAC是由S生成）
• MAC效率高

公钥加密与数字签名的区别

数字签名经常被误认为是公钥加密的逆向操作，将发送者和接收者互换位置。

RSA+DSA签名算法

RSA

RSA密钥产生与RSA加密方案一致

安全性：

• 无消息攻击
• 任意消息伪造签名

改进：

• 加盐
• 使用哈希函数：在签名之前对消息应用某个函数𝐻

DSA

安全性是基于离散对数问题的困难性假设

各类型数字签名

盲签名

• 电子现金，电子投票

将文件放入带有复写纸的信封，签名者在信封上对文件进行签名而不知道文件的具体内容。

群签名

• 电子拍卖

保护签名者身份的隐私

各个部门的打印机只允许本部门人员使用，部门员工对文档进行签名，打印机校验合法性

环签名

保护签名者身份的隐私（让接收者确信此消息来自某个群体但又不清除具体是哪个成员）

代理签名

实现签名权的安全传递

序列密码

对称加密的一种，按位或字节处理。效率较高

特点：

• 实现简单
• 便于硬件实现
• 加解密处理速度快
• 没有或只有有限的错误传播等

密钥流产生：

• 同步流密码：发送方和接收方必须是同步的（这点区别于DES解密，DES解密使用的子密钥顺序与加密时相反）。用同样的密钥且该密钥操 作在同样的位置，才能保证正确解密。
• 自同步流密码：自同步序列密码的密钥流的产生，与密钥和已经产生的固定数量的密文字符有关，是一种有记忆变换的序列密码；

流密码与分组密码

分组密码以一定大小的分组作为每次处理的基本单元；
序列密码则是以一个元素作为基本的处理单元；

线性反馈移位寄存器

伪随机序列：如果密钥流是周期的，要完全做到随机性是困难的。严格的说，这样的序列不可能做到随机，只能要求截获比周期短一段时，不会泄露更多信息，这样的序列称为伪随机序列。

RC4

RC4是Ronald Rivest在1987年为RSA公司设计的一种流密码；

RC4=密钥调度算法KSA+伪随机数生成算法PRGA

序列密码设计原则

密钥流生成器的不可预测性：

• 长周期
• 高线性复杂度
• 统计性能良好
• 足够混乱、扩散
• 抵抗不同形式的攻击