1-0密码学基础

Andy Gao

2023-10-11

notes › network_security

network_security

密码学基础

基本概念

密码是混淆，密码不是隐藏，密码也不是访问控制。

明文
密文
加密
解密
密码编码学
密码破译学
无条件安全
计算安全
s-DES:必考内容

密码编码学

密码编码学的三个特征

转换明文为密文的运算类型：加密的两个原理
- 置换 (transposition)
  
  重新排列
- 代换 (substitution)
  
  每个元素映射成另外的元素
原则是不允许丢失信息，即所有的运算都是可逆的
所用密钥数
- 对称加密、单钥加密
  - 安全性在于算法本身的保密性
- 非对称加密、公钥加密、1976年发表
  - 把算法和密钥分开，算法公开，密钥保密
  - 安全性在于保持密钥的保密性
处理明文的方法
- 分组密码/块密码（block cipher）
  
  每次处理一个分组
  
  现在使用的对称分组密码算法都基于Feistel分组密码结构的
- 流密码 (stream cipher)
  
  每次处理一个元素

密码编码学的历史

古典密码：~1949

1949：香农论文“保密通信的信息理论”
近代密码：1949~1976

1976：公钥出现 Diffie and Hellman 为1977年的RSA提供了理论基础

1977：DES数据加密标准公开，DES是对称加密算法
现代密码

古典密码：代换

古典密码都是自然语言编码

代换密码必须考虑：明文的语法模式和结构有多少仍然保留在密文中，减少这种保留信息的方法有

多个字母一起加密

采用多表代换密码

单表代换
1. 恺撒码（+3）
  
  可以采用穷举攻击破译Caesar 密码，因为
  1. 算法已知
  2. 只有26种密钥
  3. 明文所用语言已知
  4. 密文中还是带有原始字母使用频率的一些统计学特征
多表代换
- playFair：
  
  5x5码表，一个密钥词，先填密钥词再填剩下字
  
  I/J等价，同时编码两字母（如果该字母对是两个相同的字母，添加一个填充字），同行右移，同列下移，对角线切换
  - ar->rm
  - mu->cm
  - hs->bp
  但是Playfair密码依然完整地保留了明文语言的结构，几百个字母密文就足够分析出规律了
- Hill
  
  C=KP mod26，K是nxn矩阵，同时对n个字母组成的向量加密
- Vigenere
  
  多层凯撒，查表得到
- OTP （one time pad）一次一密（基于verman，verman是基于二进制位的otp）
  
  使用与消息一样长且无重复的随机密钥来加密消息，这就是著名的一次一密（One-time Pad； OTP），它是不可攻破的，即无条件安全的。
  - 但是密钥获取、分配、保护很困难

古典密码：置换

更复杂的方案是把消息一行一行写成矩形块，然后按列读出，同时把列的次序打乱；列的次序就是算法的密钥。

转轮机

对称密码

DES (Data Encryption Standard): 一种早期的对称密钥算法，使用56位的密钥。它的变形包括3DES（三重DES），提供更强的安全性，通过连续三次使用DES算法来增强加密强度。

3-DES:三重DES加密,密钥为k1,k2因此位数为112位

加密过程:k1加密,k2解密,k1再加密一次
- 3-DES速度慢,分组长度再长一些更安全
IDEA (International Data Encryption Algorithm): 使用128位密钥的对称算法，以其高效的实现和强大的安全性而闻名。它通常用于PGP加密。
RC2, RC4, RC5:
- RC2: 一种可变密钥长度的对称加密算法，早期在SSL协议中广泛使用。
- RC4: 是一种流加密算法，以其简单和速度快著称，曾经广泛应用于SSL和WEP加密。
- RC5: 这个算法的特点是其参数化的加密操作，允许用户自定义密钥大小、块大小和加密轮数。
AES (Advanced Encryption Standard): 现代最常用的对称密钥算法，使用128、192或256位的密钥。AES的安全性很高，是很多政府和企业的标准加密算法。

AES不是Feistel结构
- 算法结构简单
  - 字节代换
  - 行移位
  - 列混淆
  - 轮密钥加(实际上是一种vernam,因此非常安全.)<–从这里开始,然后执行九轮循环迭代,最后一轮没有列混淆
  三个代换,一个置换(行移位)
- 密钥被扩展成44(11*4)个32位字所构成的数组,每次用4个
Blowfish: 一种块加密算法，使用可变长度的密钥，从32位到448位。它以其加密速度快和有效的资源利用著称。
- Blowfish算法的子密钥和S盒都是用Blowfish算法本身生成的
- 与古典Feistel结构不同， Blowfish算法每轮运算都是对数据的左右两个部分同时执行运算

DES已经被认为不再安全，AES是新的标准

s-DES

TODO:搞懂S-DES

S-DES加密算法的输入为一个8位明文组和一个10位的密钥，输出为8位的密文组。
S-DES解密算法的输入为一个8位密文组和一个10位的密钥，输出为8位的明文组。

核心思想：

明文拆成两个部分，各加密一次，相互参与对方的加密

Feistel Cipher Structure

Feistel 建议交替使用代换和置换这实际上是Claude Shannon提出的交替使用混淆(Confusion )和扩散(Diffusion)乘积密码的实际应用

混淆 (Confusion):
- 混淆指的是使密钥与密文之间的关系尽可能复杂化，使得密文对密钥的依赖不是线性或直接的。这种方式通常是通过代换（substitution）操作来实现的，即将输入的数据的每一部分按照一定的方式替换成其他的数据。这样做的目的是为了防止攻击者能够找到密钥和明文之间的简单关系，从而保护信息。
- 在DES这样的Feistel结构中，混淆通常是通过复杂的代换盒（S-boxes）来实现的，这些盒对输入数据进行非线性变换。
扩散 (Diffusion):
- 扩散的目的是将明文的统计结构（如频率分布）分散到输出的密文中，使得原文的每个部分都影响到密文的多个部分。这样，即使原文做了微小的改变，也会在密文中产生广泛而显著的效果，从而避免了密文中的模式可被识别。
- 在Feistel网络和其他密码算法中，扩散通常是通过置换（permutation）或称作交换的过程来实现的，这个过程重新分布输入位，使得数据的每一部分都影响到其他多个部分。

feistel算法原理

输入分割：将数据块分割为左半部(L)和右半部®。
迭代：对数据进行多轮迭代。在每一轮中：
- 将右半部R应用于一个轮函数F，这个函数还需要一个子密钥（每一轮一个不同的子密钥）。
- 将函数F的输出与左半部L进行某种组合操作（通常是XOR）。
- 交换处理过的左半部和右半部。在最后一轮后，不进行交换，以确保解密过程能正确地逆向执行。
输出合并：经过多轮处理后，合并处理过的L和R作为密文输出。

Feistel网络的关键特点之一是加密和解密过程几乎相同，唯一的区别在于子密钥的应用顺序相反。这意味着相同的硬件或软件可以用于加密和解密，只需简单地反转密钥的顺序即可。

DES算法原理

非对称加密

数学原理：

陷门单向函数：

单向性：求原函数容易，求逆非常困难
陷门性：在已知一附加信息$\delta$后,求逆非常容易.$\delta$为陷门信息

符号表示

在讨论的非对称加密部分中，以下符号表示被使用来描述各种密钥和操作：

会话密钥 $(K_s)$
用户A的公钥 $(KU_a)$
用户A的私钥 $(KR_a)$
$(E_{KU_a}[P])$：表示用用户A的公钥 KU_a 对明文P进行加密。
$(E_{KR_a}[P])$：表示用用户A的私钥 KR_a 对明文P进行加密。
$(D_{KU_a}[C])$：表示用用户A的公钥 KU_a 对密文C进行解密。
$(D_{KR_a}[C])$：表示用用户A的私钥 KR_a 对密文C进行解密。

原理

加密过程:
- 使用公钥加密: 当发送者想要发送一个加密消息时，他们使用接收者的公钥对消息进行加密。公钥是公开的，任何人都可以使用它来加密消息，但只有持有对应私钥的接收者能够解密这个消息。
- 使用私钥解密: 一旦消息被公钥加密，它就可以安全地发送给接收者。接收者然后使用他们唯一的私钥来解密这个消息。由于私钥没有公开，只有接收者可以解密这个消息，保证了信息的机密性。
数字签名和验证:
- 使用私钥签名: 发送者也可以使用自己的私钥对一个消息进行加密，这通常被用作数字签名。这样做不是为了保密，而是为了验证身份和消息的完整性。
- 使用公钥验证: 接收者或任何人都可以使用发送者的公钥来解密签名。如果解密后的消息与原始消息一致，那么接收者可以确认消息确实来自于声称的发送者，并且消息在传输过程中未被篡改。
签名和加密同时使用

当数字签名和加密同时使用时，通常有两种主要的方法：一种是先签名后加密，另一种是先加密后签名。以下是使用之前的符号来表示这两种方法：
1. 先签名后加密（Sign-then-Encrypt）:
这是最常用的方法，确保了消息的机密性和身份验证。
- 签名:
  - 发送者使用自己的私钥 KR_S 对消息 P 进行签名:
    - 生成的数字签名为: $S = E_{KR_S}[P]$
- 加密:
  - 然后发送者使用接收者的公钥 KU_R 对含签名的消息进行加密:
    - 加密后的密文为: $C = E_{KU_R}[P, S]$
- 解密和验证:
  - 接收者首先使用自己的私钥 $KR_R$ 解密密文:
    - 得到 $P$ 和 S。
  - 然后使用发送者的公钥 $KU_S$ 验证签名:
    - 如果 $P = D_{KU_S}[S]$，则签名验证成功。
1. 先加密后签名（Encrypt-then-Sign）:
这种方法较少使用，因为它可能导致某些安全问题，但在某些特定场景下仍然有效。
- 加密:
  - 发送者使用接收者的公钥 $KU_R$ 对消息 $P$ 进行加密:
    - 生成的密文为: $C = E_{KU_R}[P]$
- 签名:
  - 发送者再对密文 $C$ 使用自己的私钥 $KR_S$ 进行签名:
    - 生成的签名为: $S = E_{KR_S}[C]$
- 验证和解密:
  - 接收者首先使用发送者的公钥 $KU_S$ 验证签名:
    - 如果 $C = D_{KU_S}[S]$，则签名验证成功。
  - 然后使用自己的私钥 $KR_R$ 解密密文 $C$ 来获取消息 $P$。
在实际应用中，先签名后加密通常是更推荐的做法，因为它既确保了消息内容的机密性，又能验证消息的来源和完整性。

数论基础

欧拉函数

在非对称加密系统中，尤其是在RSA算法中，密钥的生成过程是核心组成部分。以下是基于欧拉函数和其他数论概念的RSA密钥生成过程的一个概述：

RSA密钥生成步骤：

选择两个大的质数 $p$ 和 $q$:
- 这两个质数不应该公开，并且它们的选择对于系统的安全性至关重要。它们通常是随机选取的，且足够大，以使得其乘积难以被分解。
计算 $n = p \cdot q$:
- $n$ 是这两个质数的乘积，它将被用作公钥和私钥的一部分。$n$ 的位数和大小是加密强度的关键。
计算欧拉函数 $ \phi(n) = (p-1)(q-1) $:
- 这一步是利用了欧拉函数的性质。因为 $p$ 和 $q$ 是质数，所以每个数都分别与 $p-1$ 和 $q-1$ 互质。
选择一个公钥指数 $e$:
- $e$ 是公钥的一部分，通常可以是一个较小的质数。它必须满足$ 1 < e < \phi(n) $并且$ e $与$ \phi(n) $互质。常见的选择是65537，因为它满足上述条件且计算效率较高。
计算私钥指数 $d$:
- $d$ 是满足$ de \equiv 1 \mod \phi(n) $的整数。简单来说，$d$ 是$e$在模$ \phi(n) $下的乘法逆元。$d$ 可以通过扩展欧几里得算法计算得到。
形成密钥对:
- 公钥为 $(e, n)$。
- 私钥为 $(d, n)$。

Diffie-Hellman密钥交换算法

算法本身也只局限于进行密钥交换

Diffie-Hellman（DH）算法是一种密钥交换协议，它允许两方在没有共享秘密的前提下通过一个不安全的通信渠道建立一个共享的秘密密钥。这个共享的秘密可以用于之后的通信中作为对称加密的密钥。DH算法基于离散对数难题的数学性质。

数学基础：

模运算（Modular Arithmetic）:
- DH算法在一个有限群上操作，通常是模一个大质数的乘法群。模运算就是取余运算，它定义了这个群的结构。
离散对数问题（Discrete Logarithm Problem, DLP）:
- 在给定一个群生成元 $ g $ 和 $ g^a $ 的情况下，离散对数问题指的是找到指数 $ a $ 的难题。在足够大的群中，这个问题是计算上不可行的。DH算法的安全性就是基于离散对数问题的难度。

DH密钥交换步骤：

选择全局参数:
- 双方协定一个大质数 $ p $ 和其原根 $ g $（在模 $ p $ 下的一个生成元）。这两个值不需要保密，可以公开。
各自选择私钥:
- Alice选择一个私钥 $ a $，Bob选择一个私钥 $ b $。这些私钥是随机选择的，并且保持秘密。
各自计算并公开传输值:
- Alice计算 $ A = g^a \mod p $ 并将 $ A $ 发送给Bob。
- Bob计算 $ B = g^b \mod p $ 并将 $ B $ 发送给Alice。
各自计算共享密钥:
- Alice接收到 $ B $ 后，计算 $ s = B^a \mod p $。
- Bob接收到 $ A $ 后，计算 $ s = A^b \mod p $。

结果：

Alice和Bob现在共享密钥 $ s $，因为根据模幂运算的性质，$ B^a \mod p = A^b \mod p = g^{ab} \mod p $。
这个密钥$ s $可以用作后续通信的对称密钥。

DH算法的安全性基于离散对数问题的难度；即使攻击者知道$ p $，$ g $，$ A $，和 $ B $，在没有更多信息的情况下，他们不能有效地解决$ A = g^a \mod p $来找到$ a $，或者解决$ B = g^b \mod p $来找到$ b $，从而无法计算出共享密钥$ s $。

密钥分配

加密位置

链路加密保护数据在网络中的每个链接上，但在每个节点都会被解密和重新加密，适合网络层的广泛数据保护。
- 安全性:
  - 安全性取决于网络中各个节点的安全。如果任何一个节点受到攻击，数据可能会在那个点被解密和读取。
端到端加密保护数据从发送者到接收者的整个过程，适合保障敏感信息和个人通信的完整性和机密性。
- 安全性:
  - 端到端加密被认为是更安全的，因为密钥只在通信的两端持有，中间任何节点都没有密钥来解密内容。这意味着即使数据被截获，第三方也无法解读数据内容。

传统的对称密码分配

人工传送,链路加密
- A–>B
- A<–C–>B
A(用原有密钥加密)==不安全信道==>B(解密)
A<==安全信道==C==安全信道==>B

密钥分配中心KDC模式

1. 注册与存储密钥：

实体注册：在网络中的每个实体（用户或服务）首先需要在KDC注册。注册过程中，实体和KDC之间会共享一个初始的密钥，称为主密钥。这个密钥是保密的，只有实体和KDC知道。
密钥存储：KDC会安全地存储所有注册实体的主密钥信息。

2. 密钥请求与分发：

密钥请求：当一个实体（比如用户A）想要与另一个实体（比如用户B）安全通信时，它会向KDC发出一个密钥请求。这个请求通常包括请求者的标识和目标实体的标识。
KDC响应：KDC验证请求者的身份，并且使用与请求者和目标实体共享的主密钥生成一个会话密钥。然后，KDC将会话密钥安全地发送(用各自对应的主密钥加密)给请求者和目标实体。还会把原始请求同时告诉A,把A的id同时告诉B.

3. 会话密钥的使用：

会话建立：一旦两个实体收到了KDC发送的会话密钥，它们就可以使用这个密钥来加密通信内容，进行安全的会话。
会话结束：会话结束后，会话密钥可以被丢弃。对于新的会话，通常会生成新的会话密钥。

公钥的分配

公开发布

简单,但是任何人都可以伪造
公开可访问目录

管理员维护<姓名,公钥>目录
公钥授权

比公开目录更严格,获取目录需要认证
公钥证书

不通过管理员维护目录,而是通过传递证书

利用公钥分配传统密码

简单分配就是你能想到的最简单方法,先公开公钥,在Bob得到公钥后就可以不对称加密传递信息了.

不过容易受到主动攻击,因为Alice不能确定和她聊天的就是Bob
存在KDC的情况下,A和B已知对方公钥,则先用公钥确定身份.握手后再传密钥