简单学习一点密码学基础知识。

概述

密码学是研究如何保护信息免受未经授权访问和篡改的科学。它是信息安全的一个重要组成部分，涉及加密、解密、身份验证、数据完整性等多个方面。

主要应用情景：

  • 数据加密：保护敏感数据，如金融信息、个人数据等。
  • 身份验证：保护系统免受未经授权的访问。
  • 数据完整性：确保数据未被篡改。

主要算法分类：

  • 对称加密：对称加密是一种加密方法，其中加密和解密使用相同的密钥。
  • 非对称加密：非对称加密使用一对不同的密钥：一个用于加密（公钥），一个用于解密（私钥）。
  • 哈希算法（摘要算法）：哈希算法将输入数据转换为固定长度的输出，通常用于传输数据的完整性验证和密码的服务端存储。

注意：现代密码算法的具体实现都是公开的，使用者仅仅需要对密钥进行保密和安全传输，破解通常只能基于暴力穷举，密钥的长度往往决定了算法的安全性。

我们只关注数据的加密解密部分，包括常见的对称加密和非对称加密算法，只是宏观地介绍，并不涉及算法具体的细节。

对称加密

对称加密的特点是加密和解密过程是对等的，在加密解密过程中使用相同的密钥。 对称密码的安全性完全依赖于密钥的严格保密，加密以后的密文可以在不安全的信道上传输， 但是用于加密解密的密钥却必须通过安全的信道传递，一旦密钥泄露，安全性全都不复存在。 根据处理方式的不同，可以分为分组密码（块密码）和流密码（序列密码）两大类算法。

对称加密的密钥通常可以通过非对称加密进行传输。

分组密码

分组密码算法的框架如下：

  • 首先按照固定长度（如128比特）对明文进行分组（通常需要先填充为分组长度的整数倍），得到 N 个固定长度的明文块，
  • 然后用相同的密钥和算法依次对每一个明文块进行加密，得到 N 个等长的密文块
  • 将密文块按照顺序组合起来得到密文

对每一个明文块的加密和解密过程的数学模型如下： \[ \begin{aligned} E:K\times P &\rightarrow C = E(K,P): & \{0,1\}^k \times \{0,1\}^n &\rightarrow \{0,1\}^n \\ D:K\times C &\rightarrow P = D(K,C): &\{0,1\}^k \times \{0,1\}^n &\rightarrow \{0,1\}^n \end{aligned} \] 这里\(K\)是固定长度\(k\)的密钥，\(P\)和\(C\)是固定长度\(n\)的明文和密文，\(E\)和\(D\)是抽象的加密解密子程序，互为反函数，满足 \[ D(K,E(K,P)) = E(K,D(K,P)) = P, \forall P \] 因此在数学上它们都是针对\(\{0,1\}^n\)的置换函数。

实践中对每一个块会用相同的加密程序和一组不同的密钥\(\{K_i\}\)进行多轮加密，解密同理。 \[ M_0 = P, M_{i+1} = E(K_i,M_i) \]

最简单的分组加密算法是对每一组进行完全一样的并行处理，块与块之间是相互独立的。 后续还引入了更复杂的工作模式，在不同的块的加密之间引入额外的联系，例如用上一个块的密文或密钥参与当前块的加密。

典型的分组密码算法有DES，AES，3DES等，其中早期的DES不够安全，已经被AES取代，

流密码

主流的流密码算法的框架是一样的：加密和解密双方使用相同伪随机数据流作为每一位的密钥，明文数据每次与密钥流顺次对应加密（实践中通常是直接对每一位数据和密钥使用异或操作），得到密文数据流。

数学模型如下，使用\(P\)、\(K\)和\(C\)分别代表明文流、密钥流和密文流 \[ \begin{aligned} P = \{p_0,p_1,p_1,\dots\}, K = \{k_0,k_1,k_2,\dots\}, C = \{c_0,c_1,c_2,\dots\} \end{aligned} \] 加密解密过程只是简单的按位异或 \[ c_i = \text{XOR}(k_i,p_i),\, p_i = \text{XOR}(k_i,c_i) \]

流密码算法的关键是伪随机密钥流\(K\)的生成，由于密钥流和数据流一样长，不可能传递完整的密钥流， 实践中双方会采用一个固定的伪随机数生成程序\(G\)，在加密和解密时采用相同的种子（\(\text{key}\)）来启动 \[ k_0 = G(\text{key}),\, k_i = G(\text{void}), i = 1,2,\dots \] 流密码算法中真正的密钥其实就是用于启动的随机数生成种子（\(\text{key}\)），需要通过安全的信道传递给对方。

实践中，伪随机数生成程序\(G\)既可以是与数据流完全独立的子程序，也可以将之前的明文或密文作为参数传入，例如 \[ k_0 = G(\text{key}),\, k_i = G(k_{i-1},c_{i-1}), i = 1,2,\dots \]

由于理论上的安全性较低，流密码在一些加密要求高的地方不适合使用，但是由于流密码自身具有实现简单，计算高效的优势，在一些存储空间有限、功耗要求苛刻、性能羸弱的硬件应用程序中，流密码仍然被广泛使用。

常见的流密码算法可以分成两种：

  • 针对软件设计：RC4、SEAL等
  • 针对硬件设计：基于LFSR算法的A5/1、A5/2、Trivium等

非对称加密

与对称加密不同，非对称加密使用一对不同的密钥：公钥和私钥， 经过公钥加密的密文必须使用私钥解密，经过私钥加密的密文必须使用公钥解密。 公钥和私钥是相互匹配的，通过算法同时生成，通常甲方会将私钥保密，将公钥公布出来，乙方在与之通信时，使用甲方公布的公钥加密明文，得到的密文只有通过对应的私钥才能解密，即只有甲方可以解密，反之同理。

数学模型如下，用\(E\)和\(D\)代表加密和解密程序，用\(K_a,K_b\)代表公钥和私钥，用\(P\)和\(C\)代表明文和密文 \[ C = E(K_a,P), P=D(K_b,C) \] 满足互逆关系 \[ E(K_a,D(K_b,P)) = E(K_b,D(K_a,P)) = D(K_a,E(K_b,P)) = D(K_b,E(K_a,P)) = P,\forall P \]

从理论上来说，公钥和私钥之间的联系是确定的，必然可以从一个推出另一个， 但是在实践中这种算法可能非常低效，例如对于大数的素因子分解是非常困难的，可以利用这种特点保证在信息保密的时效内，第三方无法通过公钥反解出私钥， 进而保证信息安全。

常见的非对称加密算法：

  • 基于大数分解：RSA
  • 基于离散对数：ElGamal
  • 基于椭圆曲线：ECC

这几种非对称加密算法的数学原理有空可以专门整理，涉及到很多数论知识，这里暂时忽略。

相比于对称加密，非对称加密算法的执行效率很慢，通常适合处理小规模数据的加密（包括数字签名），或者对于大规模数据先用对称密码加密，然后将密钥通过非对称加密进行处理。