# 密码学

## 古典密码

### 各种相应的密码

- 凯撒 m=c+3(mod 26)
- 仿射 加密 m=kc+k(mod 26) 解密c=k^-1*m-k(mod 26)
- hill A*M=C A为矩阵
- 维吉利亚 Ci=Mi+Ki(mod 26) Mi=Ci-Ki(mod 26)

### 古典密码的设计缺陷

- 密钥空间通常较小 对应现代密码的密钥须足够长以抵御穷举攻击
- 明文、密文、密钥三者之间只是简单的代数关系 对应现代密码的混淆性
- 明文的统计特性的隐藏并不好 对应现代密码的扩散性

### 设计方法

- 代换
- 置换

### 相关的时间节点

- 1949 Shannon 保密系统的通信理论
- 1917 Mauborbne和Vernam 一次一密
- 1976 Diffie和Hellman 公钥密码体制概念

### 信息安全的目标

- 机密性 通过aes等加密实现
- 完整性 hash函数，mac码校验完整性
- 认证性 消息认证码和数字签名
- 不可否认性 数字签名
- 可用性 不down

### 加密系统的密码分析

- 唯密文分析：密码分析者取得一个或多个用同一密钥加密的密文
- 已知明文分析：除要破译的密文外，密码分析者还取得一些用同一密钥加密的明密文对
- 选择明文分析：密码分析者可取得他所选择的任何明文所对应的密文
- 选择密文分析：密码分析者可取得他所选择的任何密文所对应的明文，它主要应用于公钥密码体制。

### 常见的攻击

- 被动攻击 对信道的侦听截获然后分析
- 主动攻击 伪造合法的用户，对消息进行篡改、伪造、中断、重放等攻击方式

## 分组密码（对称密码）

### 密码

#### DES

##### 特点

- Feistel结构
- 密钥有效长度 56位，8位校验码
- 1977确定des，第一个广泛应用于商用数据保密
- mac码不可提供不可否认性，原因在于双方有同样的密钥，导致接收方可以否认接收到的消息，发送方也可以否认发送过某消息，mac码不可提供不可否认性，原因在于双方有同样的密钥，导致接收方可以否认接收到的消息，发送方也可以否认发送过某消息

##### 安全性分析

- 56位有效密钥太短
- 弱密钥和半弱密钥
- 代数结构存在互补对称性

##### 流程

1. M=Li+Ri
2. Ri+1=Li xor F(Ri)
3. Li+1=Ri
其中 F函数为扩展置换（E表），代换（s盒），置换（p盒），其中，S盒实现混淆性，P盒跟E表实现扩散性

#### AES

##### 特点

- SP系统
- 轮数为 分组长度/32+密钥长度/32+2，最大为14轮
- 密钥长度为 128bits 192bits 256bits

#### 流程

- 字节代换 混淆性 S盒代换 非线性部分
- 行移位 扩散性 行移位操作要求第一行不变，第二行循环左移1个字节；第三行循环左移2个字节；第四行循环左移3个字节。
- 列混淆 扩散性
- 轮密钥加 非线性模块
将128bit的明文转换成4*4的矩阵，元素为字节，并与轮密钥做异或操作，然后经过9轮的4步操作，分别是S盒代换、行移位、列混合、轮密钥加，最后第10轮只3步操作，不做列混合。
S盒操作通过查表运算，对于输入字节，高4bit表示行数，低4比特表示列数

#### 工作模式

- **ECB** 最简单直接分成组然后用原本的方式去加密
- **CBC** 上一组加密完的密文跟本次的明文先进行xor操作后，在进行原本的方式去加密，有初始向量IV
- **OFB** 对IV选取64-j bits长度的进行加密，提取加密后的j bits插入原本的最后重新组成下一组的64bits的IV，并将这j bits的与明文进行xor获取输出的密文
- **CFB** 与OFB类似，区别在于提取到下一组的IV的j bits是输出的密文。

### 序列密码

- 对称密码体系
- m序列---指最大周期的序列密码 n级m序列的周期为2^(n) - 1
- 安全核心问题是序列的产生的设计
- n级线性反馈移位寄存器即an+1与前面n个ai存在关系

#### 与分组密码的区别

- 同属对称密码体系 但序列密码为对字符逐位加密，分组密码为按块加密

#### 工作模式

###### 同步序列密码

- 密钥流的产生与明密文消息流相互独立，也即是跟输出的密文无关

###### 自同步密码

- 密钥流的产生与己经产生的一定数量的密文有关

### HASH函数

#### 性质

- **单向性** 给定散列值H(m),m在计算上不可行
- **弱抗碰撞性** 给定消息m，寻找m'使得在计算上H(m)=H(m')不可行
- **强抗碰撞性** 任意两个m跟m'，使得H(m)=H(m')不可行

#### 分组长度与输出长度

- SHA-1 512bits 160bits
- SHA-256 512bits 256bits
- SHA-384 1024bits 384bits
- SHA-512 1024bits 512bits
- MD5 512bits 128bits

#### MD5

##### 步骤

1. 填充消息，使得lenbits(m)==448(mod 512),填充的第一个bits为1，其他为0
2. 补足长度，最后填充64bits，其中存储原始消息的长度
3. 初始数据
4. 数据处理，其中是进行4轮主循环操作

#### SHA-1

##### 步骤

1. 填充消息
2. 补足长度
3. 数据处理 4回合 共计80次

#### 生日攻击

对输出长度为n位，尝试2^(n) + 1个报文必定存在一个冲突，在1/2的概率下，需要的为2^(n/2)个报文//也就是开平方

#### 消息认证码

- 定义 消息认证码是消息被一密钥控制的公开函数作用后产生的、固定长度的数值，用于提供数据原发认证和数据完整性的密码校验值
- 过程 收发双发共享密钥K，在提供认证性的应用中，消息发送者在发送消息m的同时，计算并发送认证符MAC(K,m)，接收者利用共享密钥K，计算MAC'与接收到的MAC比较即可得到认证。
- 作用 **验证信息来源的正确性** 和 **验证消息的完整性**
- 利用mac码实现 用户首先计算其mac值：MAC(K2,m)，并加密并传送E(K1,m|| MAC(K2,m))；接收端首先用K1对消息解密，并用K2和相关MAC算法验证m的合法性。实现方式除了对称密码的mac码还可以通过hash函数实现

### 公钥密码（非对称密码）

#### 特点

- 基于数学难题，基于思想为陷门单向函数（即已知x，易求f(x),但已知f(x)不易求x)
- 解决了对称密码的**密钥分发问题 、密钥管理问题 和 数字签名问题**

#### 与对称密码的区别

- 使用的密钥等不一样
- 对称密码体制包括加密算法实现机密性，公钥多了不可否认性，解决密钥协商，数字签名问题
- 对称密码体制的设计通常基于置换和代换的结合设计；而公钥密码通常基于数学困难问题

#### RSA

基于大整数分解困难

##### 流程

- 取大素数p跟q，n=pq
- 取e，记欧拉函数为f，使得(e,f(n))=1
- 计算d，d=e^-1(mod f(n))
- 加密 C=M^e(mod n)
- 解密 M=C^d(mod n)

##### 安全性分析

- |q-p|要大，最好相差几个bits位 Attack：q-p=k，如果k较小，(p+q)^2 = k^2 +4n,容易爆破出k满足k^2+4n为完全平方数。
- 共享模数 在同一个模n的情况下，有(e1,e2)=1,则可有re1+se2=1，则有c1^r * c2^s(mod n)=m(mod n)
- e过小 过小直接开方求
- 不同用户生成n时使用同一个素数p (n1,n2)=p
- 安全的密钥长度最少1024bits

##### RSA签名算法

- 签名 s=H(m)^d(mod n)
- 验证 s^e(mod n)是否是H(m)

#### Elgamal

基于离散对数问题

##### 特点

- 非确定性，加密相同明文会出现不同密文
- 密文空间大于明文空间
- 选择密文可以获取(m*m')(mod p)

##### 流程

- 素数p（至少150位的十进制素数）
- g为其中的本原元，共享p g
- 用户挑选随机数x作为私钥，计算y=g^x(mod p),y作为自身公钥
- 加密 c1=g^r(mod p) c2=m*y^r(mod p),传递(c1,c2)
- 解密 m=c2*(c1^x)^-1(mod p)

##### Elgamal签名

- 签名 选择k，使得(k,p-1)=1,r=g^k(mod p),s=(H(m)-xr)*k^-1(mod p-1),分发(r,s)
- 验证 计算H(m)，验算y^r * r^s = g^H(m) (mod p)是否成立
- 安全性 重用随机数，对m1跟m2使用同样的k，则s1=(H(m1)-xr)*k^-1(mod p-1) s2=(H(m2)-xr) * k^-1(mod p-1)，联立可求私钥x

### 密钥管理

#### 管理的原则

- **全程安全原则** **必须在密钥的产生、存储、备份、分发、组织、使用、更新、终止和销毁等的全过程中对密钥采取妥善的安全管理。**
- **最小权利原则** **应当只分发给用户进行某一事务处理所需的最小的密钥集合。**
- **责任分离原则** **一个密钥应当专职一种功能**
- **密钥分级原则** •**可减少受保护的密钥的数量，又可简化密钥的管理工作。一般划分为三级：主密钥，二级密钥，初级密钥**
- **密钥更新原则**
- **密钥应当有足够的长度**
- **密码体制不同，密钥管理也不相同** **由于传统密码体制与公开密钥密码体制是性质不同的两种密码，因此它们在密钥管理方而有很大的不同。**

#### 分发方式

##### 离线分发方式

- 通过可靠的物理渠道

##### 在线分发方式

- 建立一个密钥分发中心（kdc）实现。每个用户与kdc共享一个保密的密钥，kdc通过这个密钥来鉴别用户。

#### **Diffie-Hellman**

##### 过程

- 选择素数p，g为p的本原元
- a随机选择a，计算g^a(mod p)，发送
- b随机选择b，计算g^b(mod p)，发送
- 分别计算获得共享密钥 g^ab(mod p)

##### 安全性分析

- 安全性基于离散对数问题（非对称密码
- 缺少消息认证机制，可被主动攻击（中间人） 可采用端到端的密钥协商协议，在发送时候，对其进行签名

#### Shamir门限方案

##### 过程

- q为一大素数，满足q>=n+1
- 在GF(q)上构造f(x)=a0+a1 * x+a2 * x^2....+ak-1 * x^k-1
- 分别计算得出f(xi),分发

##### 秘密重构

看书上公式