密码学备忘

本文最后更新于 2023年3月3日下午

自己在学习密码学课程时做的总结，AES 那一部分写得比较简略

密码学备忘

引言

密码学的意义
密码学基础
- 对称密码
- 公钥密码
- 数据完整性算法
- 相互信任

安全概述

CIA三元组
- 保密性（数据保密性、隐私性）
- 完整性（数据完整性、系统完整性）
- 可用性
  
  ※：真实性、可追溯性
安全攻击
- 安全威胁：
  - 自然威胁
  - 人为威胁
    - 主动攻击：拒绝服务、消息修改、伪装、重放
    - 被动攻击（窃听）：信息内容的泄露，流量分析
安全服务：（OSI安全体系结构）安全服务通过安全机制来实现安全策略
1. 数据保密性：防止被动攻击
2. 认证：保证通信的真实性
3. 数据完整性：功能与保护对象有关
  ※：满足完整性业务，不一定同时满足认证性，因为敌手可以假冒合法用户发送满足完整性的数据包
4. 不可否认性
5. 访问控制
基本安全设计准则
攻击面和攻击树
- 攻击面：网络由系统中一系列可访问且可利用的漏洞组成，包括网络攻击面、软件攻击面、人类攻击面
- 攻击树：采用分支化、层次化表示来利用安全漏洞的可能技术集合的数据结构
  - 根节点：攻击的目的
  - 叶节点：发起攻击的不同方式
  - 与节点：该节点的所有子节点代表的字母表都必须优先完成
  - 或节点：需要至少完成应该子目标

网络安全模型

信息流安全基本模型：
- 消息的安全变换（基本成分）: 包括对消息的加密和认证
- 通信双方共享的秘密信息（基本成分）
- 一个可行的第三方（可选成分）：分发密钥建立安全通道、仲裁
安全网络通信需要考虑的4个要素：
- 加密、认证算法
- 用于算法的秘密信息：密钥、秘密参数等
- 秘密信息的分发与共享
- 使用加密、认证算法和密钥以获得安全服务所需的协议（安全协议）
防止未授权访问的模型：守卫者和内部控制部件构成两道防线
信息安全的三个层次：系统安全、数据安全（密码技术）、内容安全（不良内容过滤）

传统加密技术

密钥 $K$ $K$ （密钥空间即 $K$ $K$ 的可能值范围）——加解密密钥不一定相同
- 明文： $m$
- 密文： $C$
- 加密函数： $E_{K}(m)=C$
- 解密函数： $D_{K}(E_{K}(m))=m$

对称密码模型

（传统密码/常规密码/私钥密码/单钥密码/conventional/private-key/single-key）

发送方和接收方共享同一个密钥
基本成分：明文(plaintext)、加密算法(encryption)、密钥(key)、密文(cipher)、解密算法(decryption)
保证安全的两个条件：加密算法足够强、保证密钥安全
Kerckhoff原则：系统的保密性不依赖于对加密体制或算法的保密，而依赖于对密钥的保密（这也降低了保密成本）

密码编码学(cryptography)

特征：
- 转换明文为密文的运算类型（不允许信息丢失，即运算均可逆）：代替（映射）/置换（重新排列）
- 所用的密钥数：单密钥密码（基于计算安全性，运行速度快，但是不便于密钥管理）/双密钥密码（基于可证明安全性，便于密钥的管理，还可用于消息认证，但是运行速度慢）
- 处理明文的方法
  - 分组(块)密码：按组处理，l每次处理一组元素。适合数据库加密，组内有错误扩散；一般用于公开的理论研究。
  - 序列(流)密码：连续处理输入元素，每次输出一个元素。加解密速度快，无错误扩散；一般用于实际的安全产品

密码分析学(cryptanalytics)

典型目标：得到密钥，而不是仅仅得到单个密文对应的明文

攻击传统密码体制的一般方法

穷举攻击：对一条密文尝试所有可能的密钥，知道把它转化为可读的有意义的明文。平均而言，成功至少需要尝试所有可能密钥的一半。
密码分析：利用算法的性质和明文的特征或某些明密文对

攻击类型	攻击者已知的东西
唯密文攻击	加密算法待破译的密文
已知明文	加密算法待破译的密文由密钥形成的一个或多个明文-密文对
选择明文	加密算法待破译的密文由破译者选择的明文信息，连同对应的由密钥生成的密文
选择密文	加密算法待破译的密文由破译者选择的猜测性密文，连同对应的由密钥生成的已破译明文
	CCA-1攻击（午餐攻击）：有限的解密机（得到目标密文之后不能再使用）
	CCA-2攻击（凌晨攻击）：无限的解密机（得到目标密文之后能继续使用）
选择文本	加密算法待破译的密文由破译者选择的明文信息，连同对应的由密钥生成的密文由破译者选择的猜测性密文，连同对应的由密钥生成的已破译明文

加密算法要经得住已知明文攻击
分析依据
对称密码：明文的结构和模式在加密之后仍然保存了下来，能在密文中找到一些蛛丝马迹
公钥密码：密钥对的数学性质

无条件安全：如果算法产生的密文不能给出惟一决定相应明文的足够信息。此时无论敌手截获多少密文、花费多少时间，都不能解密密文
- Shannon指出，仅当密钥至少和明文一样长时，才能达到无条件安全。（一次一密）
- 计算上安全：破译密文的代价超过被加密信息的价值或破译密文所花的时间超过信息的有用期

代替技术

代替法：将明文字母替换成其他字母、数字、符号的方法

恺撒密码 Caesar Cipher

加密算法： $C=E(p,k)=(p+k)mod26$

解密算法： $p=D(C)=(C-k)mod26$

加解密算法已知，密钥只有25个，适合穷举攻击

采样密码 Decimation Cipher

密文字母是将明文字母按下标每隔k位去除要给字母排列而成（字母表首尾相接），又称为乘法代替密码

加密算法： $E_{k}(m)=mk\equiv C\pmod p,0\leq C<q$

在乘法代替密码中，当且仅当 $gcd(k,q)=1$ ， $E_{k}$ 才是一一映射
$k=1$ 是，称为平凡密钥，此时所有字母映射到自身，不是一个合适的密钥
合适的密钥有 $\varphi(26)-1$ 个

解密算法： $D_{k}(j)=k^{-1}\cdot j\equiv i \pmod q,0\leq j<q$

仿射代替密码

将移位代替密码和乘法代替密码结合起来就构成仿射代替密码

加密算法： $E_{k}(m)=mk_{1}+k_{0}\equiv c\pmod q$ ，其中 $k_{0},k_{1}\in Z_{q},gcd(k_{1},q)=1$

当 $k_{0}=0$ ，就是乘法代替密码；当 $k_{1}=1$ ，就是移位代替密码
$q=26$ 时，密钥空间大小为 $26*12-1=311$ 个

解密算法： $D_{k}(c)\equiv (c-k_{0})\cdot k_{1}^{-1}\pmod q$

单表代替密码

每个明文字母映射到一个不同的随机密文字母

可以选取一个英文短语，称为key word/key phrase，按顺序去掉重复字母，将它依次写在明文字母表下，将明文字母表中未在短语中出现过的字母依次写在短语之后，即构造出一个代替表。
密钥空间： $26!>4*10^{26}$ ，大于56位DES的密钥空间
看似安全，实则不然：可以基于语言统计规律进行破译
缺陷：密文带有原始字母使用频率的一些统计学特征，每个元素仅仅密文中的一个元素产生影响（解决：多个字母一起加密、多表代替）

语言的冗余与密码的分析（密码破译就是研究明文信息在密文信息中有多大程度泄露）

英文字母的出现频率大小排列顺序：E TAO INSHR DL CMWFGYPBU VK JXQX
双字母的出现频率大小排列顺序：th he in er an
三字母、数字、标点符号等等
冠词the
英文中一半的词以e，s，d，t结尾，以t，a，s，w开头
分析步骤：统计密报的一节统计特性，识别报文为单表密，然后利用猜字法

最著名的多字母代替密码——Playfair密码

把明文的双字母音节作为一个单元并将其转换为密文的“双字母音节”

Playfair 密钥矩阵
- 5*5字母矩阵
- 从左往右，从上到下：填充key word，用其他字母填写剩下的空缺
- I=J

M	O	N	A	R
C	H	Y	B	D
E	F	G	I/J	K
L	P	Q	S	T
U	V	W	X	Z

加密规则
- 明文字母（填充）：2个字母分为一组，不够则添加一个字母
- 同行字母对加密：循环向右，ei→FK
- 同列字母对加密：循环向下：cu→EM
- 其他字母加密：矩形对角线字母，且按行排序，hs→BP
解密规则：加密的逆向操作
安全性：优于简单的单表代替密码，难用频率分析字母；但是密文中仍含有明文的部分结构信息，给定几百个字母即可被攻破

另一个多字母代换密码——Hill Cipher

加密方法是由 $m$ 个线性方程（矩阵）决定的，方程中每个字母被指定为一个数值

加密算法：1. 明文分组并编码 2. $C\equiv KP\pmod{26}$ ，其中 $K$ 为密钥矩阵， $P,C$ 分别为明、密文分组

解密算法：1. 密文分组并编码 2. $P\equiv K^{-1}C\pmod{26}$

完全隐藏了单字母的频率特性（连续m个明文替换成m个密文）
所用矩阵越大所隐藏的频率信息越多
足以抵抗唯密文攻击，但是不能抵抗已知明文攻击

多表代替密码 Polyalphabetic Ciphers

令明文字母表为 $Z_{q}$ ， $k=(\sigma_{1},\sigma_{2},\dots)$ 为代替表序列，明文 $m=m_{1},m_{2},m_{3},\dots$ ，则相应的密文为： $C=E_{k}(m)=\sigma_{1}(m_1),\sigma_2(m_2),\dots$

若 $k$ 是非周期的无限序列，则相应的密码为非周期多表代替密码
对于每个明文字母都采用不同的代替表进行加密，称之为一次一密密码（one-time pad cipher）
实际中多采用周期多表代替密码 $k=(\sigma_{1},\sigma_{2},\dots,\sigma_d,\sigma_{1},\sigma_{2},\dots,\sigma_d,\sigma_{1},\sigma_{2},\dots)$

维吉尼亚密码 Vigenère Cipher

设明文为 $P=p_1p_2\cdots p_n$ ，密钥为 $K=k_1k_2\cdots k_n$ ，密文 $C=c_1c_2\cdots c_n$

加密算法：

$c_i=p_i+k_i\pmod {26},i=1,2,\dots,n$
查表法

博福特密码 Beaufort Cipher

加密算法： $c_{i+td}=\sigma(m_{i+td})\equiv(k_i-m_{i+td})\pmod q$

解密算法： $m_{i+td}=\sigma(c_{i+td})\equiv(k_i-c_{i+td})\pmod q$ （完全相同！）

对应的Vigenère cipher： $C_{i+td}=[(q-1)-m_{i+td}+(k_i+1)]\pmod q$

弗纳姆密码 Vernam Cipher

选择择随机二元数字序列作为密钥，以 $k=k_1,k_2,\dots,k_i,\dots(k_i\in F_2)$ 表示
文字母变成二元向量后也可以表示成二元序列 $m=m_1,m_2,\dots,m_i,\dots(m_i\in F_2)$ ， $k$ 和 $m$ 分别记录在穿孔纸带上。
加密算法：将 $k$ 和 $m$ 的相应位逐位模2相加，即 $c_i=m_i\bigoplus k_i,j=1,2,\dots$
解密算法： $m_i=c_i\bigoplus k_i,j=1,2,\dots$

这种加密方式如果使用电子器件实现，就是一种序列密码
如果采用的密钥不重复就是一次一密体制，理论上不可破，但是实际上不可行

周期多表代替密码的破译

判断加密类型是单表代替密码还是多表代替密码

粗糙度 $M.R$ $M . R$ ：定义为每个密文字母出现的频率与均匀分布时每个字母出现的概率的离差的平方和。
- 对于英文字母而言，明文或单表代替密码的粗糙度为0.027，一般密文的粗糙度将在0~0.027之间变化。

初步判定多表代替密码所用的密表数

重合指数I.C值：知道了I.C值就可以提取密钥字长或密表数的近似值信息

确定多表代替密码所用的密表数

移位法：对密文进行移位并和原来的密文进行逐位比较以求重码数，根据重码数来确定密表数
重复字模式分析法（Kasiski检验）：计算密文中重复字模式的距离

密表匹配

※：转轮机

eg：German Enigma，Allied Hagelin，Japanese Purple

实现了复杂多变的多表代替密码，多层加密
每个圆柱体有26个输入、输出引脚，代表26个字母
单个圆柱体定义一个单表代换
每个圆柱体每次定义的单表代换算法不同
单个圆柱体定义了周期为26的多表代换

置换技术

栅栏技术：按对角线顺序写出明文，以行的顺序读出作为密文

改进：带有密钥，重复加密，多步置换

矩阵排列法：优先行/列置换

隐写术

不可见的墨水
打字机的色带校正
缺点：开销大，需要额外的付出来隐藏相对较少的信息；一旦被发现就完全没有价值
一个可选的方案：先加密，然后用隐写术隐藏

分组密码和数据加密协议

Feistel分组密码结构

理想分组密码：设每 $n$ 个一组，不同的映射/代换（即密钥）有 $2^n!$ 种，每一种密钥的大小是 $n*2^n$ 位（并不实用）
Feistel 提出了一种近似体制：使用乘积密码的概念来逼近理想分组密码

乘积密码 Product Cipher

在单个加密机制中依次使用两个或两个以上不同类型的基本密码（如：代换和置换），所得结果的密码强度将强于每个单个密码的强度。
- 本质：开发一个分组密码，密钥长为 $k$ 位，分组长为 $n$ 位，采用 $2^k$ 个变换

Claude Shannon and Substitution-Permutation Ciphers

1949年，Claude Shannon 引进了 substitution-permutation (S-P) networks 的思想，即现代的乘积加密器，形成了现代分组加密的基础
S-P Networks 基于代替和置换这两个基本操作，提供了对明文信息处理所做的混淆和扩散
Shannon认为，为了对付基于统计分析的密码破译，必须对明文作混淆和扩散处理，以减少密文的统计特性，为统计分析制造障碍
- 混淆 Confusion：尽可能使密文和加密密钥之间的关系变得复杂，以阻止攻击者发现密钥
- 扩散 Diffusion：让每个明文数字尽可能地影响多个密文数字，使明文的统计特性消散在密文中
Feistel建议交替使用代换和置换，增强密码的扩散和混淆性能

Feistel密码

加密算法：

令 $F$ 为轮函数；令 $K_1,K_2,\dots,K_n$ 分别为第 $1,2,\dots,n$ 轮的子密钥。那么基本构造过程如下：
（1）将明文信息均分为两块： $(L_0,R_0)$ ；
（2）在每一轮中，进行如下运算（ $i$ 为当前轮数）：
$L_{i+1} = R_i$ ；
$R_{i+1} = Li\bigoplus F(R_i,K_i)$

所得的结果即为： $(R_{i+1},L_{i+1})$

解密算法：

对于密文 $(R_{n+1},L_{n+1})$ ，我们将 $i$ 由 $n$ 向 $0$ 进行，即 $i = n,n-1,\dots,0$ 。然后对密文进行加密的逆向操作，如下：

（1） $R_i = L_{i+1}$ ；

（2） $L_i = R_{i+1}\bigoplus F(L_{i+1},K_i)$

所得结果为 $(L_0,R_0)$ ，即原来的明文信息
依赖的参数和设计特点
- 分组大小：分组越大意味着安全性越高（如果其他条件相同），但加密/解密速度也越慢
- 密钥大小：密钥长度越长则安全性越高，但加密/解密速度也越慢
- 循环次数：一个循环不能保证足够的安全性，而循环越多则安全性越高
- 子密钥产生算法：算法越复杂则密码分析就应该越困难
- Round函数：复杂性越高则抗击密码分析的能力就越强

数据加密标准 DES

DES 的基本概念

Data Encryption Standard：1977年美国国家标准局公布的IBM公司研制的一种数据加密算法:数据加密标准
破译方法
- DES 受到的最大攻击是它的密钥长度仅有56比特
- 1990年 S.Biham 和 A.Shamir 提出了差分攻击的方法，采用选择明文 $2^{47}$ 攻击，最终找到可能的密钥
- M.Matsui 提出的线性分析方法，利用 $2^{47}$ 个已知明文，成功地破译了16圈 DES算法，到目前为止，这是最有效的破译方法
实现步骤：
1. 给定明文 $X$ ，通过一个固定的初始置换 $IP$ 来排列 $X$ 中的位，得到 $X_0$ 。 $X_0=IP(X)=L_0R_0$ 。其中 $L_0$ 由 $X_0$ 前32位组成， $R_0$ 由 $X_0$ 的后32位组成。
2. 计算函数 $F$ 的16次迭代, 根据下述规则来计算 $L_iR_i(1\leq i\leq 16 ): L_i=R_{i-1},R_i=L_{i-1}\bigoplus(R_i,K_i)$ 。其中 $K_i$ 是长为48位的子密钥。子密钥 $K_1,K_2,\dots,K_{16}$ 是作为密钥 $K$ （56位）的函数而计算出的。
3. 对比特串 $R_{16}L_{16}$ 使用逆置换 $IP^{-1}$ 得到密文 $Y$ 。 $Y=IP^{-1}(R_{16}L_{16})$
DES 加密流程图
DES 一轮迭代
S盒选取

每一个S盒都接受6个比特作为输入并产生4个比特作为输出。

输入的第一和最后一个比特构成一个2位二进制数，用来选择由 $S_i$ 表中的四行所定义的四种替代的一种，中间的4个比特则选出一列
子密钥的产生
- 弱密钥：给定的初始密钥k产生的16个子密钥相同
- 半弱密钥：若存在种子密钥 $k'(k'\neq k)$ ，使 $DES_{k'}(m)=DES_k(m)$ ，则称 $k$ 是半弱密钥，且称 $k'$ 与 $k$ 是对合的
DES 的雪崩效应：（P置换的目的是提供雪崩效应）明文或密钥的一点小的变动都引起密文的较大变化
攻击方法：差分密码分析攻击线性密码分析

差分分析方法

对于 DES 的分析，可忽略初始置换 $IP$ 和 $IP^{-1}$ 。
对DES 限制到 $n$ 轮（ $n\leq 16$ ）。
以 $L_0R_0$ 为明文，且以 $L_0R_0$ 作为 $n$ 轮 DES 的密文。
对两个明文 $L_0R_0$ 和 $L_0^*R_0^*$ ，规定它们的异或值为 $L_0^{'}R_0^{'} =L_0R_0\oplus L_0^*R_0^*$ ，整个讨论都使用撇号（ $'$ ）表示两个比特串的异或值。）表示两个比特串的异或值。

定义 1：设 $𝑆_j$ 是一个特定的 S盒 ( $1\leq j\leq 8$ )，考虑长度为 $6$ 的比特串的一个有序对 $(B_j,B^*_j)$ ,我们说 $𝑆_j$ 的输入异或是 $B_j\oplus B^*_j$ ,输出异或是 $S_j(B_j)\oplus S_j(B^*_j)$
- 输入异或是长度为 $6$ 的比特串，输出异或是长度为 $4$ 的比特串。
定义 2：对任何一个 B_j^' \in (𝑍_2)^6=\left\{(a_0,a_1,a_2,a_3,a_4,a_5)|a_j\in \left\{0,1 \right \} \right \}，定义集合 \Delta(B_j^') 是由输入异或为 B_j^' 的有序对 $(B_j,B_j^*)$ 组成
- 对比特串 B_j^' 来说，集合 \Delta(B_j^') 包含 $2^6=64$ 个有序对元素。有 $\Delta (B^{'}_j)=(B_j, B_j\oplus B_j^{'})|B_j \in (Z_2)^6$
  
  这是因为 $B_j⨁\oplus B_j^{*}= B_j^{'}$ ，所以 $B_j\oplus B_j^{'}= B_j^*$
- 对 \Delta(B_j^') 中的每一对，我们能够计算出 $S_j$ 的输出异或，同时用表列出结果的分布。有 $64$ 个输入异或，它们经 $S_j$ 的输出分布在 $2^4=16$ 种可能值中，这些分布的非均匀性，就是攻击 DES 的基础
- 表示一个 S 盒的所有可能对的输入异或盒输出异或分布的表称为该 S 盒的差分分布表
定义 3：对于长度 6 的比特串 $B_j^{'}$ 和长度为 4 的比特串 $C_j^{'}(1\leq j\leq 8)$ ，定义 $IN_j(B_j^{'},C_j^{'})=\left\{B_j\in (Z_2)^6|S_j(B_j)\oplus S_j(B_j\oplus B_j^{'})=C_j^{'}\right\}，N_j(B_j^{'},C_j^{'})=| {IN_j}(B_j^{'},C_j^{'})|$
- 那些输出异或相同的 $B_j$ 的集合
- 考虑一般的情况：对于 $DES$ 的 8 个 S 盒的每一个盒有 64 可能的输入异或，于是有 512 个分布
定义 4：设 $E_j$ 和 $E_j^*$ 是长度为 6 的比特串， $C_j^{'}$ 是长度为 4 的比特串，定义 $Test_j(E_j,E_j^*,C_j^{'})=\left\{B_j\oplus E_j|B_j\in IN_j(E_j^{'},C_j^{'})\right\}$ ， $B_j\oplus E_j$ 是 $J_j$ 的形式。
- 假设 $E_j^*$ 是 S 盒 $S_j$ 的两个输入， $S_j$ 的输出异或为 $C_j^{'}$ ，记为 $E_j^{'}=E_j\oplus E_j^*$ ，那么密钥比特 $J_J$ 出现在集合 $Test_j(E_j,E_j^*,C_j^{'})$ 之中。
3 轮 DES 的差分攻击模式：

输入： $L_0R_0,L_0^*R_0^*,L_3R_3 和 L_3^*R_3^*$ ，其中 $R_0=R_0^*$
1. 计算： $C^{'}=P^{-1}(R_3^{'}\oplus L_0^{'})$
2. 计算： $E=E(L_3)$ 和 $E^*$
3. For j in range(0,8) 计算： $Test_j(E_j,E_j^*,C_j^{'})$

三重 DES

设 $E$ 是一个密码算法，如果对任意的密钥 $k_1$ ， $k_2$ ，都存在密钥 $k_3$ ，使得对任意的明文 $x$ 有： $E_{k_1}(E_{k_2}(x))=E_{k_3}(x)$ ，则称 $E$ 是闭合的。显然，

※：1992年，K.W. Campbell，M.J. Wiener 证明了 DES 不是一个群。

正因以上结论，二重 DES，三重 DES 有一定的价值，其穷举攻击的安全性虽有所改进，然而并非2倍，3倍的密钥量那么坚强

中途相遇攻击法

若有明文密文对 $(x_i,y_i)$ 满足 $y_i=E_{k_2}(E_{k_1}(x_i))$

则可得 $z=E_{k_1}(x_i)=D_{k_2}(y_i)$

给定一已知明密文对 $(x_1,y_1)$ ，可按下述方法攻击：

以密钥 $k_1$ 的所有 $2^{56}$ 个可能的取值对此明文 $x_1$ 加密，并将密文 $z$ 存储在一个表中；
从所有可能的 $2^{56}$ 个密钥 $k_2$ 中依任意次序选出一个对给定的密文 $y_1$ 解密，并将每次解密结果 $z$ ，在上述表中查找相匹配的值。一旦找到，则可确定出两个密钥 $k_1$ 和 $k_2$ ；
以此对密钥 $k_1$ 和 $k_2$ 对另一已知明文密文对 $(x_2,y_2)$ 中的明文 $x_2$ 进行加密，如果能得出相应的密文就可确定 $k_1$ 和 $k_2$ 是所要找的密钥。

eg:

对于给定明文，以两重DES加密将有 $2^{64}$ 个可能的密文。
可能的密钥数为 $2^{112}$ 个。所以，在给定明文下，将有 $2^{112}/2^{64} =2^{48}$ 个密钥能产生给定的密文。
用另一对64bits明文密文对进行检验，就使虚报率降为 $2^(48-64)=2^{-16}$ 。
这一攻击法所需的存储量为 $2^{56}×8$ Byte，最大试验的加密次数 $2×2^{56} =2^{57}$ 。这说明破译双重DES的难度为 $2^{57}$ 量级。

三重DES加密

加密算法： $y=E_{k_1}[D_{k_2}[E_{k_1} [x]]]$

解密算法： $x=D_{k_1}[E_{k_2}[D_{k_1}[y]]]$

称其为加密-解密-加密方案，简记为EDE(encrypt-decrypt-encrypt)。

高级加密标准 AES

评估要求：安全性、计算效率、内存要求、使用简便性、灵活性

AES 是一个迭代型分组密码，分组长度固定为 128 比特，密钥长度则可以是 128，192 或 256 比特
Rijndael 是一个迭代型分组密码，分组长度和密钥长度均可以是 128，192 或 256 比特
AES加密过程涉及到4种操作，分别是字节替代、行移位、列混淆和轮密钥加。

解密过程分别为对应的逆操作。

加解密中每轮的密钥分别由初始密钥扩展得到。算法中16个字节的明文、密文和轮密钥都以一个4x4的矩阵表示。

字节替代 SubBytes

它独立地将状态中的每个字节利用代换表(S盒)进行运算
- S盒被设计成能够抵挡所有已知的攻击
- S盒是由16×16个字节组成的矩阵，包含了8位值所能表达的256种可能的变换
- ※ DES：S: 6→4 AES: 8→8
State中的每个字节按照如下的方式映射为一个新的字节：将该字节的高4位作为行值，低4位作为列值，然后取出S盒中对应行列交叉处的元素作为输出

S盒的构造方法

逐行按照上升排列的方式初始化 S 盒。第一行是 $\{00\},\{01\},\dots,\{0F\}$ ；第二行是 $\{10\},\{11\},\dots,\{1F\}$ 等，在 x 行 y 列的字节值是 $\{xy\}$ ；
把S盒中的每个字节映射为它在有限域 $GF(2^8)$ 上的乘法逆；其中，元素 $\{00\}$ 映射到它自身 $\{00\}$ ；
把S盒中的每个字节表示为 $\left(b_{7}, b_{6}, b_{5}, b_{4}, b_{3}, b_{2}, b_{1}, b_{0}\right)$ 8位，对 S 盒中的每个字节中的每个位做如下变换： $b_{i}^{\prime}=b_{i} \oplus b_{(i+4) \bmod 8} \oplus b_{(i+5) \bmod 8} \oplus b_{(i+6) \bmod 8} \oplus b_{(i+7) \bmod 8} \oplus c_{i}$

其中，对于 $0 \leq i<8$ ，是字节的第 $i$ 位， $c_i$ 是值为 $\{63\}$ 或 ${01100011}$ 的字节 c 的第 i 位

行移位

行移位变换完成基于行的循环移位操作，变换方法为：第0行不变，第1行循环左移1个字节，第2行循环左移两个字节，第3行循环左移3个字节

列混淆

利用GF(28)域上算术特性的一个代替，同样用于提供算法的扩散性
列混淆：左乘列混淆矩阵
- 计算方式：
  1. $x*01$ ，为 $x$ 本身
  2. $x*02$ ， $x$ 的二进制左移一位（右边补0），如果溢出（即如果 $x$ 的二进制最高位为1），那么再异或上 $1B$
  3. $x*03$ ，结果为 $(x*02)XOR(x)$
- $02 * 87$ ： $87$ 的二进制位 $1000 0111$ ，左移一位得到 $0000 1110$ ，因为本身的二进制最高位为 $1$ ，所以再异或 $1B$ ，即 $(00001110) XOR (00011011)$ ，得到 $(00010101)$ 即： $15$

轮密相加

在轮密钥加中，128 位的 state 按位与 128 位的轮密钥 XOR

密钥扩展

分组加密的工作模式

问题引入：每次使用相同的密钥对多个分组加密，会引发许多安全问题

工作模式简介

工作模式：是一项增强密码算法或者使算法适应具体应用的技术，如将分组密码应用于数据块组成的序列或者数据流
初始化向量 IV：许多工作模式中用于随机化加密的一块数据，因此可以有相同的密文、相同的密钥产生不同的密文而无需重新产生密钥。一般无需保密。

电码本 ECB 模式

ECB 模式是最简单的运行模式。
- 直接利用加密算法分别对分组数据组加密
- 一次处理一组明文分块，每次使用相同的密钥加密

特点：在给定的密钥下，同一明文组总产生同样的密文组
往往需填充
ECB 用于短数据（如加密密钥）时非常理想，因此如需安全传递DES、AES 等密钥，ECB是最合适的模式
- ECB 用于长消息时可能不够安全：如果消息有固定结构，密码分析者有可能找出这种关系。

密文分组连接模式 CBC

加密算法的输入是当前明文分组和前一次密文分组的异或
串行，不能并行化
明文有一组有错，以后的密文组都受影响

加密： $C_n=E_K[C_{n-1}\oplus P_n],C_{-1}=IV$

解密时，每一个密文分组被解密后，再与前一个密文分组异或
两个邻接的密文块即可得到一个明文块，可以并行化（错误不传播）

解密： $P_n=D_K[C_n]\oplus C_{n-1}$

同样需要填充
IV 对于收发双方都应是已知的，为使安全性最高，IV 应像密钥一样被保护，可使用 ECB 加密模式来发送IV
- 保护 IV 的原因：敌手篡改 IV 中的某些比特，则接收方收到的相应的比特也发生了变化

密文反馈模式 CFB

若待加密消息必须按字符(如电传电报)或按比特处理时，可采用CFB模式
利用 CFB 模式或 OFB 模式可将分组对称密码转换为流密码。流密码不需要对消息填充，而且运行是实时的
流密码具有密文和明文一样长这一性质，因此，如果需要发送的每个字符长为 8 比特，就应使用 8 比特密钥来加密每个字符。如果密钥长超过 8比特，则造成浪费。
加密过程：

加密函数的输入是 b 位的移位寄存器，其初值为某个初始向量 IV。
输出最左边的 s 位与明文的第一个分段 P1 异或得到密文的第一个单元 C1，发送 C1 ；
移位寄存器左移 s 位，C1 填入移位寄存器的最右边 s 位；
直至所有明文单元被加密完

串行，不能并行化

解密过程：

将收到的密文单元与加密函数的输出异或得到明文单元。
使用加密函数而非解密函数。
CFB 与 CBC 的区别是反馈的密文长度为 k ，且不是直接与明文相加，而是反馈至密钥产生器。

两个邻接的密文块即可得到一个明文块，可以并行化（错误不传播）

优点：
- 适合数据以比特或字节为单位出现，适合加密数据流；
- 能隐蔽明文数据图样，也能检测出对手对于密文的篡改；
- 仅需要实现加密算法；
- CFB模式除能获得保密性外，还能用于认证。
缺点：
- 对信道错误较敏感，错误传播：1个比特密文传输错误会传播约64/j 个分组
- CFB也需要一个初始矢量，并要和密钥同时进行更换**。**

输出反馈模式 OFB

OFB 模式的结构类似于 CFB
- 不同之处：OFB 模式是将加密算法的输出反馈到移位寄存器，而 CFB 模式中是将密文单元反馈到移位寄存器

OFB的特点：
- 消息作为比特流，移位寄存器
- 分组加密的输出与被加密的消息相异或
- 只需要实现加密算法
- 不适合认证
预处理加密输出分组之后可以并行
优点：传输过程中的比特错误不会被传播，
适合有扰信道，比如卫星等
缺点：
- 比 CFB 模式更易受到对消息流的篡改攻击
  如在密文中取1比特的补，那么在恢复的明文中相应位置的比特也为原比特的补。因此使得敌手有可能通过对消息校验部分的篡改和对数据部分的篡改，而以纠错码不能检测的方式篡改密文。
- 不具有自同步能力，要求系统要保持严格的同步

计数器模式 CTR

CTR 模式：与 OFB 相似，CTR 将块密码变成流密码。它通过递增要给加密计数器已产生连续的密钥流
可并行

工作模式对比

模式	描述	用途
电码本(ECB)模式	每个明文组独立地以同一密钥加密	传送短数据(如一个加密密钥)
密码分组链接(CBC)	加密算法的输入是当前明文组与前一密文组的异或	传送数据分组；认证
密码反馈(CFB)模式	每次只处理输入的 j 比特，将上一次的密文作加密算法的输入以产生伪随机输出，该输出再与当前明文异或以产生当前密文	传送数据流；认证
输出反馈(OFB)模式	与 CFB 类似不同之处是本次加密算法的输入为前一次加密算法的输出	噪声信道(如卫星通信)传送数据流
计数器(CTR)模式	对计数器依次用 k 加密后与明文异或	适合并行，可随机访问

伪随机数的产生和流密码

随机数的使用

大量基于密码学的网络安全算法和协议都使用了二进制随机数，如：

密钥分发和相互认证方案。如在密钥分配中，需使用时变值进行握手以防止重放攻击。时变值使用随机数可以防止攻击者判断或者猜测出时变值
会话密钥的产生。用随机数作为会话密钥
公钥密码算法中密钥的产生。用随机数作为公钥密码算法中的密钥，或以随机数来产生公钥密码算法中的密钥
用于对称流密码加密的位流的产生

随机数源

真随机数：很难获得
- 物理噪声产生器，如：离子辐射脉冲检测器、气体放电管、漏电容等
- 将高质量的随机数作为随机数库编辑成书
伪随机数：使用算法来生成随机数。

随机数的产生要求

随机性

以下两个准则常用来保障数列的随机性：
1. 分布均匀性：序列中的位分布应是均匀的，即0和1出现的频率大约相等；
2. 独立性：序列中任何子序列不能由其他子序列推导出。
- 序列是否满足均匀分布可通过检测得出，而是否满足独立性则无法检测，相反却有很多检测方法能证明序列不满足独立性
不可预测性
- 在设计密码算法时，由于真随机数难以获得，经常使用似乎是随机的序列（这样的序列称为伪随机数序列，这样的随机数称为伪随机数

对 PRNG 要求

通用要求：输出保密性——不知道种子的敌手不能决定伪随机串
特定要求：随机性、不可预测性、种子的特性
- 随机性：生成的位流尽管是确定的，但要显示随机。
  - 没有单个的测试可以判定一个PRNG生成的数据具有随机性；
  - NIST规定测试应建立三个特征：
    - 均匀性：在产生随机或伪随机位序列的任何点，0或1出现的量大约相等，即每个出现的概率恰好为1/2
    - 可伸缩性：用于序列测试的任何测试也可以用于从序列中抽取的子序列的测试
    - 一致性：对于所有初始值（种子），发生器的行为必须具有一致性
- 不可预测性
  - 前向不可预测性：如果不知道种子，那么不管知道序列中前面的多少位，都无法预测序列中的下一位；
  - 后向不可预测性：从产生的任何值都不能推断出种子值
- 种子的要求：安全、不可预测

伪随机数发生器

线性同余发生器

线性同余法
- 参数
  - $m$ 模数 $m>0$ $2^31$
  - $a$ 乘数 $0<a<m$
  - $c$ 增量 $0\leq c<m$
  - $X_0$ 种子 $0 \leq X_0<m$
- 随机数序列 ${X_n}$ 按下面的迭代式获得：
  
  $X_{n+1} = (aX_n+c) \pmod m$
线性同余发生器：定义 $f\left(x_{0}\right)=\left(z_{1}, z_{2}, \ldots z_{l}\right)$ ，其中 $z_{n}=x_{n} \bmod 2$ ，称 $f$ 为一个 $(k,l)$ 线性同余生成器
- 评价线性同余算法的性能有以下3个标准：
  1. 迭代函数应是全周期的，即函数在重复之前应产生0到m-1之间的所有数
  2. 产生的序列看上去应是随机的
  3. 迭代函数能有效地利用32位运算器方便的实现
- 为使随机数数列的周期尽可能大，m应尽可能大，普遍原则是选 m 接近等于计算机能表示的最大整数
- 假定敌手能确定 $X_0,X_1,X_2,X_3$ ，就可通过以下方程组，
  
  $\mathrm{X}_{1}=\left(\mathrm{aX}_{0}+\mathrm{c}\right) \mathrm{mod} \mathrm{m}$
  $\mathrm{X}_{2}=\left(\mathrm{aX}_{1}+\mathrm{c}\right) \mathrm{mod} \mathrm{m}$
  $\mathrm{X}_{3}=\left(\mathrm{aX}_{2}+\mathrm{c}\right) \mathrm{mod} \mathrm{m}$
  
  解出 a，c 和 m。
  
  ※：改进的方法：利用内部系统时钟修正随机数数列
  1. 每当产生N个数后，就利用当前的时钟值模m后作为种子
  2. 直接将当前的时钟值加到每个随机数上(模m加)
- 常用变形
  - 幂形式： $\mathrm{X}_{\mathrm{n}+1}=\left(\mathrm{X}_{\mathrm{n}}\right)^{\mathrm{d}} \bmod \mathrm{m}, \quad \mathrm{n}=1,2, \ldots$
  - 离散指数形式： $\mathrm{X}_{\mathrm{n}+1}=\mathrm{g}^{\mathrm{Xn}} \bmod \mathrm{m}, \quad \mathrm{n}=1,2, \ldots$

BBS 发生器

已经证明过的密码强度最强的伪随机数产生器，
整个过程如下：

选：选择两个大素数 $p,q$ ，满足 p\equivq\equiv3 \bmod 4。
算：计算 $n=p×q$ 。
选：选一随机数 $s$ ，使得 $s$ 与 $n$ 互素。
算：按以下算法产生比特序列 $\{B_i\}$ ：

$$\mathrm{X}{0}=\mathrm{s}^{2} \bmod \mathrm{n}\
for\quad i=1 \quad to \quad\infty \quad do{\
\quad\begin{array}{l}
X{i}=X^{2}{i-1} \bmod n \
\left.B{i}=X_{i} \bmod 2\right}
\end{array}$$
即在每次循环中取Xi的最低有效位

如果伪随机比特产生器能通过下一比特检验，则称为密码安全伪随机比特产生器
- 即以伪随机比特产生器的输出序列的前 $k$ 个比特作为输入，如果不存在多项式时间算法，能以大于1/2的概率预测第 $k+1$ 个比特。

使用分组密码的伪随机数产生

推荐：CTR模式和OFB模式
使用分组密码工作模式的 PRNG
ANSI X9.17 伪随机数产生器
- 密码强度最高的伪随机数产生器之一
- 组成部分
  - 输入： $DT_i$ 表示当前的日期和时间；Vi是产生第 $i$ 个随机数时的种子
  - 密钥: $K_1,K_2$
  - 输出：一个64比特的伪随机数 $R_i$ ，一个64比特的新种子 $V_{i+1}$ ，

流密码

流密码的概念

加密算法： $c=E_k(m)=E_{k_{0}}(m_0)E_{k_{1}}(m_1)E_{k_{2}}(m_2)\dots$

解密算法： $m=D_k(c)=D_{k_0}(c_0)D_{k_1}(c_1)D_{k_2}(c_2)\dots$

在使用的流密码中，加密变换通常采用二元加法运算。即： $c_i=m_i\oplus k_i$
由于一次一密的传输和存储麻烦，所以可行改进的办法是，用一个较小的密钥伪随机产生一个密钥流（从无条件安全变成了计算上安全）
- 密钥发生器：驱动部分（统计特性好序列）和非线性组合部分（密码学特性好序列）

流密码分类

根据 $σ_i$ 与明文信息的关系，流密码可以分为同步流密码和自同步流密码两类

同步流密码

$σ_i$ 独立于明文字符的叫做同步流密码。
对明文而言，同步流密码的加密变换无记忆；解密要求密钥流与加密密钥严格同步

特性
- 只要通信双方的密钥序列产生器具有相同的“种子序列”和相同的“初始状态”,就能产生相同的密钥序列.
- 容易检测插入、删除、重播等主动攻击.
- 没有差错传播.

自同步流密码

$σ_i$ 与明文 $m_1,m_2,\dots,m_{i-1}$ 有关，称为自同步流密码

特性
- 密钥流生成器是一种有记忆变换器，密钥流与明文符号有关：
  - i 时刻的密文不仅取决于 i 时刻的明文，且与 i 时刻之前的 l 个明文符号有关；
- 具有有限的差错传播；
- 具有自同步能力；
- 把明文每个字符扩散在密文多个字符中,强化了抗统计分析的能力

线性移位寄存器

反馈移存器是序列密码设计中常用乱源。
目的：以种子密钥为序列的初态，按照确定的递推关系，产生一个周期长、线性复杂度高、统计特性好的初始乱源，然后利用非线性函数、有记忆变换等密码变换，最终产生抗破译能力强的乱数序列。
线性移位寄存器序列是构造密钥流序列的基础。

反馈移位寄存器

一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数，其抽象的简单逻辑框图如下图所示。

称这一函数为该组合门电路的反馈逻辑函数，表示为：

$x_{r+1}=f(x_1,x_2,⋯,x_r)$ ，函数 $f$ 是一个含有 $r$ 个逻辑变元的布尔函数
若反馈移存器的反馈逻辑函数是线性函数，则称该反馈移存器为线性反馈移存器，否则称为非线性反馈移存器
- 如果反馈函数 $f(x_1,x_2,⋯,x_r)$ 是 $n$ 个变量的线性函数:
  
  $x_{r+1}=f(x_1,x_2,⋯,x_r)=c_1x_n+c_2x_{n-1}+\cdots+c_nx_1 (c_i\in\{0,1\})$
  
  则称为线性反馈移位寄存器(LFSR: linear feedback shift register)。
  
  输出的序列称为线性反馈移位寄存器序列, 记为LFSR序列。
  - 递推关系式： $a_{n+k}=c_1 a_{n+k-1}+c_2 a_{n+k-2}+⋯+c_n a_k (k≥n)$
  - 如果 $c_n=0$ ，则称LFSR是退化的；否则称 LFSR 是非退化的。
  - 把多项式：
    
    $f(x)=1+c_1x+c_2x^2+\cdots+c_nx^n$
    
    称为 LFSR 的特征多项式(characteristic polynomial), 或级连多项式或生成多项式
反馈移存器工作原理
- 反馈移存器的功能完全由其反馈逻辑函数来决定
- 移存器受时钟脉冲控制，在某一时刻各级都有一个确定的值，把此时刻各级的值称为移存器的一个内部状态
序列和周期
- 对于序列 $\underline{a}=a_0 a_1 a_2⋯a_i⋯$ ，若存在整数 $p$ 使得对任意整数 $k$ 有 $a_k=a_{k+p}$ 成立，称满足该式的最小正整数 $p$ 为序列的周期。
- 最长周期: $2^r-1$ ，能达到最长周期的线性移存器序列称为 m 序列
线性移存器表示方法
- 一个 $r$ 级线性移存器的线性递推式表示为： $a_n=c_1 a_{n-1}\oplus c_2 a_{n-2}\oplus \dots\oplus c_ra_{n-r}(n\geq r)$

流密码算法

RC4 算法

RC4是由Rivest于1987年开发的一种序列密码，它已被广泛应用于Windows、 Lotus Notes和其它软件，还被用于安全套接字(SSL)和无线通信系统等；
RC4优点是算法简单、高效，特别适于软件实现，加密速度比DES大约快10倍。
RC4可以支持不同密钥长度，美国政府特别限定，用于出口的RC4的密钥长度不得超过40位。
算法步骤
- RC4 使用了一个 28 字节大小的非线性数据表(简称 S表)，S 表的值 $S_0,S_1,…,S_{255}$ 是数字 0 到 255 的一个排列。对 S 表进行非线性变换，得到密钥流。
- RC4对S表的初始化算法(两个计数器 I 和 J, I =0 , J=0)
  1. 对S表进行线性填充： $S_I=I, 0≤I<255$ ；
  2. 用密钥填充另一个 256 字节的数组 K，如果密钥长度小于256字节，则依次重复填充，直至填满这个数组中： $K_0, K_1,…, K_{255}$ ；
  3. 对于 I=0 到 255 重复以下步骤：
    
    (1) $J=J+S_I+K_I(mod 256)$ ；
    
    (2) 交换 $S_I$ 和 $S_J$ 。
- 将 $S$ 和明文进行 xor 运算，得到密文

公钥密码原理

为什么引入公钥密码体制？

对称密码体制的问题

密钥分配问题
密钥传输问题：传输信道安全性并不理想
密钥管理问题：需管理的密钥 $C_n^2$ ，加入一个用户，产生 $n$ 个密钥
没有签名功能

※ 根源：对称密码的加密密钥与解密密钥相同

解决方法

将密钥分为加密密钥和解密密钥
加密密钥公开，解密密钥保密

问题描述	公钥密码体制完美解决
密钥分配	无需密钥的秘密分配。
密钥管理	每个用户需秘密保存1个私钥；网络中需要管理的密钥数目为n对。新用户加入时，系统只需产生1对公私钥对。
签名功能	提供了数字签名功能。

什么是公钥密码体制？

公钥密码体制的原理

公钥体制：每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布
主要特点：
- 加密和解密能力分开
- 多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）
- 只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）
- 无需事先分配密钥

公钥密码体制概述

公钥密码体制是密码学研究的一个具有里程碑意义的重要事件。
公钥密码技术又称为双钥密码或非对称密码技术。
1976年由Diffie和Hellman在其《密码学新方向》一文中首次提出公钥密码思想

公钥密码体制组成

公钥密码体制有6个组成部分：
- 明文：算法的输入；
- 密文：算法的输出；
- 公钥和私钥：算法的输入；
- 加密算法：对明文进行各种变换；
- 解密算法：接收密文和相应的密钥，并产生原始的明文。

公钥密码体制功能

公钥密码体制的主要特点是将加密和解密能力分开，因而可以实现多个用户加密的信息只能由一个用户解读，或由一个用户加密的信息而多个用户可以解读。
- 前者可以用于公共网络中实现通信保密，而后者可以用于实现对用户的认证。

公钥体制加、解密安全保障

用公钥密码实现保密

用户 B 拥有自己的密钥对 $(e_B,d_B)$ $(e_{B}, d_{B})$
- 公钥 $e_B$ 公开,私钥 $d_B$ 保密
- $A→ B: Y=E_{e_{B}}(X)$ （公钥加密）
- $B: D_{d_{B}}(Y)=D_{d_{B}}(E_{e_{B}}(X))=X$ （私钥解密）

从公开钥 $PK_{B}$ 和密文 $c$ 要推出明文 $m$ 或解密钥 $SK_{B}$ 计算上不可行。
由于任一用户都可用用户 B 的公开钥 $PK_{B}$ 向他发送机密消息，因而密文 $c$ 不具有认证性。

用公钥密码实现认证

条件: 两个密钥中任何一个都可以用作加密而另一个用作解密
认证:
$A→ALL: Y=E_{d_{A}}(X)$ （A用私钥签名）
$ALL: E_{e_{A}}(Y)= D_{e_{A}} (E_{d_{A}} (X))=X$ （用A的公钥认证）

由于 $Sk_A$ 是保密的，其他人都不可能伪造密文 $c$ ，可用 A 的公开钥解密时得到有意义的消息 $m$ 。因此可以验证消息 $m$ 来自 A 而不是其他人，而实现了对 A 所发消息的认证。

公钥保密和认证体制

认证+保密:

$A→B: Z= E_{e_{B}}(E_{d_{A}}(X))$

$B: D_{e_{A}}(D_{d_{B}}(Z))=X$

公钥密钥的应用范围

算法	加/解密	数字签名	密钥交换
RSA	是	是	是
Dieffie-Hellman	否	否	是
DSS	否	是	否

公钥密码应满足的要求

公钥密码应满足的要求
- 涉及到各方：发送方、接收方、攻击者
- 涉及到数据：公钥、私钥、明文、密文
公钥算法的条件：
- 对于接收者：产生一对密钥是计算可行的
- 对于发送者：已知公钥和明文，产生密文是计算可行的
- 对于接收者：接收方利用私钥来解密密文是计算可行的
- 对于攻击者：利用公钥来推断私钥是计算不可行的
- 对于攻击者：已知公钥和密文，恢复明文是计算不可行的

如何设计公钥密码体制？

第一步转化：设计公钥密码体制变成了寻找陷门单向函数

单向陷门函数是满足下列条件的函数 $f$ ：
(1) 计算 $y=f(x)$ 是容易的；
(2) 给定 $y$ , 计算 $x$ 使 $y=f(x)$ 是困难的；
(3) 存在 $δ$ ，已知 $δ$ 时，对给定的任何 $y$ ，若相应的 $x$ 存在，则计算 $x$ 使 $y=f(x)$ 是容易的。
仅满足(1)、(2)两条的称为单向函数，单向函数不能用于加密
第(3)条称为陷门性， $δ$ 称为陷门信息。

第二步转化：如何在求解NP完全问题中设置合理“后门”

由于利用目前现有的技术无法在多项式时间里对NP完全问题进行求解，公钥密码思想的首创者 Diffie 和 Hellmen 在其研究中指出：
计算复杂性可以被用作设计加密算法的基础，NP完全问题则是一个理想的解决途径！

信息通过编码被加密在一个 NP 完全问题之中，使得要破译这种密码以普通的方法就要解这个 NP 完全问题；
若使用解密密钥，就可能有捷径求解。
- 为构造这样的密码，陷门信息必须被嵌在一个计算困难问题中。
并非所有困难问题都可用于设计公钥密码系统。通过检验，已找到的可提供单向函数的数学难题包括：
- 整数分解问题(简称IFP)
- 有限域离散对数问题(简称DLP)
- 椭圆曲线离散对数问题(简称ECDLP)
基本思想：
1. 选择一个容易求解的子集和问题实例，伪装成一个很难求解的一般子集和问题实例；
2. 容易求解的子集和问题实例用作私钥；
3. 不易求解的子集和问题实例用作公钥。

※： 举例：如何使用背包问题构造背包密码体制

已知一长度为 B 的背包，及长度分别为 $a_1,...,a_n$ 的 n 个物品。假定这些物品的半径和背包相同，若从这 n 个物品中选出若干个正好装满这个背包。现在反过来问：究竟是哪些物品？

等价于求 $x_i= 0 或 1$ ，使其满足： $\sum_{i=1}^{n} a_{i} x_{i}=b$ ，其中和 $a_{1}, \dots, a_{n},$ $b$ 都是整数。
背包问题属于NP完备类(NP问题中难度最大的一类)，对这类问题没有有效算法。但是，如果序列 $a_{1}, \dots, a_{n}$ 是超递增序列，则背包问题有多项式解法。
对于背包问题进行如下定义：
背包向量： $(a_{1}, \dots, a_{n})$ ，
选择向量：长度为 n 的比特串。
超递增背包向量： $(a_{1}, \dots, a_{n})$ 超递增序列。
已知背包向量和选择向量，可得到背包的容积： $f$ (背包向量，选择向量)=容积
已知容积和背包向量，很难求出选择向量； $f^{-1}(\text{背包向量，容积}) \nrightarrow \text{选择向量}$
已知超递增背包向量和容积，易求选择向量： $f^{-1} (\text{超递增背包向量，容积})=\text{选择向量}$
- 对应公钥密码体制，设置：
  明文 $m$ 为选择向量，密文 $C$ 为容积，公钥 $Pk$ 为背包向量，私钥 $Sk$ 为超递增背包向量。

RSA 公钥密码体制

算法背景

该算法的数学基础是初等数论中的Euler(欧拉)定理，并建立在大整数因子分解的困难性之上，目前还不存在一般性的有效解决算法。
大整数的分解问题可以被表述：已知整数 $n$ 是两个素数的积，即 $n=pq$ 。求解 $p,q$ 的值。
$m$ 与 $n$ 互素，则由 Euler 定理得：

$m^{\varphi(n)} \equiv 1 \bmod n$
$m^{k \varphi(n)} \equiv 1 \bmod n$
$m^{k \varphi(n)+1} \equiv m \bmod n$
即 $\quad c^{d} \equiv m \bmod n$
$m^{\mathrm{ed}} \equiv m \bmod \mathrm{n}$
$ed=k \varphi(n)+1$
$\mathrm{ed} \equiv 1 \bmod \varphi(\mathrm{n})$
$\mathrm{C}=\mathrm{M}^{\mathrm{e}} \bmod n$
$\mathrm{M}=\mathrm{C}^{\mathrm{d}} \bmod n$

算法描述

密钥产生算法

随机生成两个不同且大小相近的大素数 $p$ 和 $q$ 。
计算 $n=p×q$ ， $φ(n)=(p-1)(q-1)$ ,其中 $φ(n)$ 是 $n$ 的欧拉函数值。
选一整数 $e$ ，满足 $1<e<φ(n)$ ，且 $gcd(φ(n),e)=1$ 。
计算 $d$ ，满足 $d·e\equiv1 mod φ(n)$ ,即 $d$ 是 $e$ 在模 $φ(n)$ 下的乘法逆元，因 $e$ 与 $φ(n)$ 互素，由模运算可知，它的乘法逆元一定存在。
以 ${e,n}$ 为公开钥, ${d,n}$ 为秘密钥。

密钥产生细节

选取大素数的方法：随机产生一个大整数，利用素性检测算法判定该整数是否为素数
以往素检测的算法都是概率性的，即存在一定的错误概率；
2003年，印度人发表文章 “Primes is in P”，证明了素判定问题是一个多项式时间问题。

加解密

加密

获得 A 的可信公钥 $(n,e)$ ；
将明文 $M$ 比特串分组，使得每个分组对应的十进制数小于 $n$ ，即分组的长度小于 $log_2n$ ；
对每组明文分组，作加密运算：

$C=M^e \bmod n$

将密文 C 发送给 A 。

解密

对密文分组的解密运算为:

$M=C^d \bmod n$

加解密细节

实际应用中，在RSA算法的加密与解密过程中，被加密的是经过分组的数据段。各数据段的长度相等，并且小于比 $n$ $n$ 小的 2 的最大次幂。
- 当需要加密固定长度的数据段时，可以在长度不足的各数据段的左边位上填充 0 作为补充。
  解密过程针对的也是被加密的这些数据段。因此，经解密得到的依然是经过分组的数据段。将这些数据段依次连接便能得到被传输的消息原文。

RSA 中的计算问题

计算技巧

RSA 加密

$(a×b) \bmod n=[(a \bmod n)×(b \bmod n)] \bmod n$
模指数运算的快速算法

RSA 解密

加密很快，指数小；解密比较慢，指数较大
- 利用中国剩余定理CRT，加快计算速度。
CRT 对RSA解密算法生成两个解密方程（利用 $M=C^d \bmod R$ ）

即:

$M_1 = M \bmod p = (C \bmod p )^{d \bmod (p-1)} \bmod p\\ M_2 = M \bmod q = (C \bmod q )^{d \bmod (q-1) }\bmod q$

解方程组：

$M = M_1 \bmod p\\ M = M_2 \bmod q$

利用CRT:

$X_1=q*(q^{-1}\bmod p)\\ X_2=p*(p^{-1}\bmod q)$

具有唯一解：

$M = M_1 X_1 + M_2X_2 \pmod n$

密钥生成

Miller Rabin 素数判定测试

RSA 安全性分析

已知 $e$ ， $n$ 和 $M$ ，产生 $C$ 是计算可行的——加密函数 $C = M^e(\bmod n)$
对于攻击者，已知 $e$ ， $n$ 和 $C$ ，要恢复 $M$ 是计算不可行的——解密函数 $M = C^d(\bmod n)$
存在能解密的陷门——解密私钥 $d$ 。

理解求d的困难性

解密函数 $M = C^d(\bmod n)$
1）Attacker得到一对 $(M,C)$ ，试图还原 $d$ ，以便以后的解密，这就是离散对数问题。也就是找到 $x$ ，满足 $a^x \equiv b \bmod q$ 是很难的。
2）Attacker知道公钥 $(e,n)$ ，通过公钥去得到私钥是很难的。
$de \equiv 1 \bmod \varphi(n)$ → 求 $\varphi(n)$ → 求素因子 $p$ ， $q$ → 大数因子分解的困难性

RSA 的攻击

穷举攻击：穷举所有可能的私钥
数学攻击：
- 因式分解攻击
- 参数的选取不当造成的攻击
- 选择密文攻击
- 共模攻击
- Hastad对广播信息的攻击(小e攻击)
- 小指数攻击（可以用连分数方法）
- 加密及签名攻击
- 鲁棒性攻击
- 数学性的鲁棒性攻击
计时攻击
用定时攻击方法分解出私钥 $d$
基于密码分析的错误攻击（基于脆弱性的中国剩余定理）
对于已知部分密钥位的攻击

RSA密码体制的实现要求

对 n,p,q,e 的要求

若使 RSA 安全， $p$ 与 $q$ 必为足够大的素数，使分析者没有办法在多项式时间内将 $n$ 分解出来。建议选择：

$p$ 和 $q$ 大约是 100 位的十进制素数。
模 $n$ 的长度要求至少是 512 比特。
- EDI（电子数据交换）国际标准使用的 RSA 算法中规定 $n$ 的长度为 512 至 1024 比特位之间，但必须是 128 的倍数。
- 国际数字签名标准ISO/IEC 9796中规定 $n$ 的长度为 512 比特位。
- SET(secure electronic transaction) 协议中要求 CA 采用 2048 位的密钥，其它实体使用 1024 位的密钥
为了抵抗现有的整数分解算法，对RSA模 $n$ 的素因子 $p$ 和 $q$ 还有如下要求：
- $|p-q|$ 很大，通常 $p$ 和 $q$ 的长度相同；
- $p,q$ $p, q$ 为强素数。
  - 一个素数 $p$ $p$ 是强素数需要满足以下三个条件：
    1. $p-1$ 有大的素数因子，称为 $r$ ；
    2. $p+1$ 也有大的素数因子；
    3. $r -1$ 仍然有大的素数因子。
    - 原因：
      1. 第一个条件的原因是存在 $p-1$ 分解算法，这一算法只在模 $n$ 存在一个素数因子 $p$ 满足 $p-1$ 平滑时有效；
      2. 第二个条件的原因是存在 $p+1$ 分解算法，这一算法只在模 $n$ 存在一个素数因子 $p$ 满足 $p+1$ 平滑时有效；
      3. 第三个条件的原因为了保证循环攻击无效。

RSA 的速度

在RSA的软件实现上，RSA 大约比 DES 慢 100 倍。
在RSA的硬件实现上，粗略地说，RSA 比 DES 慢 1500 倍。
为了提高加密速度，通常取e为特定的小整数，如 EDI 国际标准中规定 $e=2^{16}+1$ ，ISO/IEC9796中甚至允许取 $e=3$ 。这时加密速度一般比解密速度快 10 倍以上。
虽然因为计算机技术的改进，RSA 的速度不断改变，但其永远无法达到对称密钥算法的运行速度。
具体应用中将 RSA 算法更多地用于密钥的安全传输过程，而在针对具体传输信息的加密与解密中依靠对称密钥算法，这样便能够增进密码系统的运行速度。

RSA算法的优缺点

优点

是第一个能同时用于加密和数字签名的算法，也易于理解和操作.
特别符合计算机网络环境。
对于网上的大量用户，可以将加密密钥用电话簿的方式印出。

缺点

产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；
分组长度太大，为保证安全性，n 至少也要 600 位以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。

椭圆曲线密码体制 ECC

椭圆曲线密码简介

椭圆曲线密码是基于椭圆曲线数学的一种公钥密码的方法
椭圆曲线在密码学中的使用在 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出
与传统的基于大质数因子分解困难性的加密方法不同，ECC通过椭圆曲线方程式的性质产生密钥。
ECC被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。
ECC的主要优势：在某些情况下它比其他的方法使用更小的密钥提供相当的或更高等级的安全
- 速度快、密钥短
椭圆曲线密码学的许多形式有稍微的不同，所有都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上，对应有限域上椭圆曲线的群。
对椭圆曲线来说最流行的有限域是
- 以素数为模的整数域 $GF(p)$ ，通常在通用处理器上更为有效；
- 特征为2的伽罗华域 $GF(2^m)$ ，在专门的硬件实现上计算更为有效。

椭圆曲线的基本概念

无穷远点
- 定义平行线相交于无穷远点 $P^{∞}$ ，使平面上所有直线都统一为有唯一的交点
- 性质：
  - 一条直线只有一个无穷远点；一对平行线有公共的无穷远点
  - 任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）
  - 平面上全体无穷远点构成一条无穷远直线
射影平面
- 平面上全体无穷远点与全体平常点构成射影平面
- 对普通平面上点 $(x,y)$ $(x, y)$ ，令 $x=X/Z，y=Y/Z，Z≠0$ $x = X / Z ， y = Y / Z ， Z \neq = 0$ ，则投影为射影平面上的点 $(X:Y:Z)$ $(X : Y : Z)$
  - 例如：点 $(1,3)$ 可投影为 $(Z:3Z:Z)$ ，可为 $(1:3:1)，(2.3:6.9:2.3)$ 等
  - 对普通平面上的直线 $ax+by+c=0$ ，同样变换，得到对应于射影平面上的直线为 $aX+bY+cZ=0$
  - 无穷远点的坐标为 $(X:Y:0)$
椭圆曲线
- 一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（Weierstrass）所有点的集合： $Y^2 Z+a_1 XYZ+a_3 Y Z ^2=X^3+a_2 X^2 Z+a_4 X Z ^2+a_6 Z^3$
- 椭圆曲线方程是一个齐次方程，无穷远点 $O∞(0,Y,0)$
- 椭圆曲线普通方程： $y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6$
- 曲线上的每个点都必须是非奇异的（光滑的），偏导数 $F_X(X,Y,Z),F_Y(X,Y,Z),F_Z(X,Y,Z)$ 不同为0
- 椭圆曲线并非椭圆，称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。
椭圆曲线普通方程
- 椭圆曲线普通方程： $y^2+axy+by=x^3+cx^2+dx+e$
- 常见形式为： $y^2=x^3+ax+b$ ，其中 $4a^3+27b^2≠0$
- 曲线关于 $y=0$ 对称
- 平常点 $(x,y)$ 斜率 $k$
  
  $F_{x}(x, y)=a y-3 x^{2}-2 b x-d$
  $F_{y}(x, y)=2 y+a x+c$
  $k=f^{\prime}(x)=-\frac{F_{x}(x, y)}{F_{y}(x, y)}=\frac{3 x^{2}+2 b x+d-a y}{2 y+a x+c}$

实域R上的椭圆曲线

椭圆曲线表示为平面上通常曲线上的点，外加无穷远点 $θ$ 。
设 $L∈P^2(R)$ 为一条直线。因为 E 的方程是三次的，所以 L 可与 E 在 $P^2(R)$ 上恰有三个交点，记为P、Q、R(如果 L 与 E 相切，那么 P、Q、R 可以不相异)。

椭圆曲线上的加法运算

如果其上的 3 个点位于同一直线上，那么它们的和为 $O$ 。进一步可如下定义椭圆曲线上的加法律
1. $O$ 为加法单位元，即对椭圆曲线上任一点 $P$ ，有 $P+O=P$

设 $P_1=(x,y)$ 是椭圆曲线上的一点，它的加法逆元定义为 $P_2=-P_1=(x, -y)$
设 $Q$ 和 $R$ 是椭圆曲线上 x 坐标不同的两点， $Q+R$ 的定义如下：画一条通过 $Q,R$ 的直线与椭圆曲线交于 $P$ ，由 $Q+R+P=O$ 得 $Q+R= -P$ 。

点加公式

$P=(x_p,y_p),Q=(x_Q,y_Q),R=P+Q=(x_R,y_R)$

则：

$x_R=(\lambda^2-x_P-x_Q )\bmod p$

$y_R=(\lambda(x_P-x_R)-y_P)\bmod p$

$\begin{cases}\frac{y_Q-y_P}{x_Q-x_P}\bmod p && P\neq Q \\\frac{3x_P^2+a}{2y_P}\bmod p &&P=Q \end{cases}$
数乘定义为重复相加

有限域上的椭圆曲线

$Z_p$ 上的椭圆曲线

定义： $y^2\equiv(x^3+ax+b) \bmod p (a,b∈GF(p),(4a^3+27b^2) \bmod \neq0)$

满足上式的所有整数对和无穷远点组成的集合 $E_p(a,b)$
点加公式

$P=(x_p,y_p),Q=(x_Q,y_Q),R=P+Q=(x_R,y_R)$

则：

$x_R=(\lambda^2-x_P-x_Q )\bmod p$

$y_R=(\lambda(x_P-x_R)-y_P)\bmod p$

$\lambda=\begin{cases}\frac{y_Q-y_P}{x_Q-x_P}\bmod p && P\neq Q \\\frac{3x_P^2+a}{2y_P}\bmod p &&P=Q \end{cases}$

$GF(2^m)$ 上的椭圆曲线

$P(x_p,y_p),-p=(x_p,x_p+y_p)$
点加公式
- $P=(x_p,y_p),Q=(x_Q,y_Q),P\neq \pm Q,R=P+Q=(x_R,y_R)$
  
  则：
  
  $x_R=\lambda^2+\lambda+x_P+x_Q+a$
  
  $y_R=\lambda(x_P+x_R)+x_R+y_P$
  
  $\lambda =\frac{y_Q+y_P}{x_Q+x_P}$
- $R=2P$
  
  则：
  
  $x_R=\lambda^2+\lambda+a$
  
  $y_R=x_P^2+(\lambda+1)x_R$
  
  $\lambda=\frac{y_P}{x_P}+x_P$

椭圆曲线密码体制

椭圆曲线密码体制依据是定义在椭圆曲线点群上的离散对数问题的难解性
ECC Diffie-Hellman 密钥交换

用椭圆曲线实现ElGamal密码体制

密钥生成过程
- 用户 A 选择一条椭圆曲线 $E_p(a,b)$ ，取椭圆曲线上的一个生成元 $G$
- 用户 A 选择一个正整数 $n_A$ 作为秘密密钥，并生成公开密钥 $P_A=n_AG$
- 用户 A 把 $E_p(a,b)$ 、 $P_A$ 和 $G$ 传给用户 B
加密过程

Alice要发送消息m给Bob，Alice执行：
1. 查找 Bob 的公钥 $(E(F_q),p,n,Q)$
2. 将 m 表示成一个域元素 $m\in F_q$
3. 在区间 $[1，n-1]$ 内选取一个随机数 $k$
4. 依据 Bob 的公钥计算点 $(x_1,y_1) =kP$ ( $k$ 个 $P$ 相加)
5. 计算点 $(x_2,y_2)=kQ$ ，如果 $x_2=0$ ，则回到第3步
6. 计算 $C=m * x_2$
7. 传送加密数据 $(x_1,y_1,C)$ 给 Bob
解密过程

Bob收到Alice的密文 $(x_1,y_1,C)$ 后，执行
1. 使用私钥 $d$ ，计算点 $(x_2 , y_2)=d(x_1,y_1)$ ，再计算 $F_q$ 中 $x_2^{-1}=?$
2. 通过计算 $m=C·x_2^{-1}$ ，恢复出明文数据 $m$

椭圆曲线密码体制的优点

安全性高，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全
密钥量小
灵活性好：在密钥长度相等的情况下，RSA和ECC的速度相当；但是在相同的安全强度要求下，ECC可以使用较少的位数就可以
速度快：在密钥长度相等的情况下，RSA和ECC的速度相当；但是在相同的安全强度要求下，ECC可以使用较少的位数就可以

其他密码体制

Rabin 密码体制

Rabin密码体制有两个特点：
1. 不以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文
2. 破译该体制与分解大整数是等价的
密钥产生算法
- 随机选择两个大素数 $p,q$ ，满足 $p\equiv q\equiv 3 \bmod 4$ ，即这两个素数形式为 $4k+3$ ；计算 $n=p*q$ 。以 $n$ 作为公钥， $p,q$ 作为密钥。
加密

$c\equiv m^2 \bmod n$

$m$ 是明文分组， $c$ 是对应的密文分组。
解密
解密即为求解 $x^2\equiv c\equiv m^2 \bmod n$ ，由 CRT知该方程等价于解方程组：
$\begin{cases}x^2\equiv c\bmod p \\x^2\equiv c \bmod q \end{cases}$

Diffine-Hellman密钥交换

Diffie-Hellman算法是第一个公开密钥算法，发明于1976年。Diffie-Hellman算法能够用于密钥分配，但不能用于加密或解密信息
Diffie-Hellman 算法的安全性依赖于有限域上计算离散对数非常困难
步骤

如果A和B想在不安全信道交换密钥，可采用如下步骤：
1. A 和 B 协商一个大素数 $p$ 及 $p$ 的本原根 $a$ ， $a$ 和 $p$ 公开

A 秘密产生随机数 $x$ ，计算 $X=a^x \bmod p$ ，发送 $X$ 给 B
B 秘密产生随机数 $y$ ，计算 $Y= a^y \bmod p$ ，发送 $Y$