Skip to content

Cryptography

约 1650 个字 预计阅读时间 6 分钟

Some Theorem of Discrete Mathematics

alt text

alt text

alt text

alt text

alt text

alt text

RSA

RSA (Rivest-Shamir-Adleman) 是一种非对称加密算法，用于安全数据传输。它基于两个大质数的数学性质，具有公钥和私钥两个密钥。

RSA的工作原理：

  1. 密钥生成：
  2. 选择两个大质数 \(p\) 和 \(q\)。
  3. 计算它们的乘积 \(n = p \times q\)，这个 \(n\) 是 RSA 模型的模数。
  4. 计算 \( \varphi(n) = (p-1) \times (q-1) \)。
  5. 选择一个整数 \(e\)，满足 \(1 < e < \varphi(n)\) 且 \(e\) 与 \( \varphi(n) \) 互质。

  6. 计算 \(d\)，使得 \(d \times e \equiv 1 \ (\text{mod} \ \varphi(n))\)。这里的 \(d\) 是私钥的密钥指数。

  7. 密钥发布：

  8. 公钥 \( (e, n) \) 公开发布，供加密使用。

  9. 私钥 \( (d, n) \) 保密，供解密使用。

  10. 加密：

  11. 加密方使用接收方的公钥 \(e\) 和 \(n\) 对消息 \(M\) 进行加密： [ C = M^e \ (\text{mod} \ n) ] 其中 \(C\) 是密文。

  12. 解密：

  13. 接收方使用私钥 \(d\) 对密文 \(C\) 解密： [ M = C^d \ (\text{mod} \ n) ] 恢复原始消息 \(M\)。

特点：

  • 非对称性：公钥用于加密，私钥用于解密，且无法通过公钥轻易推导出私钥。
  • 安全性：RSA的安全性依赖于大数分解的困难性，即使知道 \(n\) 和 \(e\)，破解私钥 \(d\) 非常困难。

AES

AES（Advanced Encryption Standard，高级加密标准）是一种对称加密算法，广泛用于数据加密。它是由美国国家标准与技术研究院（NIST）在2001年发布的加密标准，用于替代旧的DES加密标准。

AES的主要特点：

  1. 对称加密：加密和解密使用相同的密钥，意味着发送方和接收方必须共享同一密钥来进行加解密。
  2. 分组加密：AES是分组加密算法，它把明文分成固定长度的块，每块128位（16字节）进行加密。
  3. 密钥长度：AES支持三种不同长度的密钥：
  4. 128位（16字节）
  5. 192位（24字节）
  6. 256位（32字节）

AES的工作原理：

AES 使用若干轮的加密操作，轮数取决于密钥长度： - 128位密钥使用10轮。 - 192位密钥使用12轮。 - 256位密钥使用14轮。

每一轮包括一系列的操作，如下： 1. SubBytes（字节替代）：使用S盒（Substitution box）替换每个字节的值，从而增加数据的混淆性。 2. ShiftRows（行移位）：逐字节移位操作，增加数据的扩散性。 3. MixColumns（列混淆）：将每一列的数据混合，进一步扩散数据。 4. AddRoundKey（轮密钥加）：每一轮都会将数据与一个特定的轮密钥进行异或操作。

AES的主要步骤：

  1. 密钥扩展：根据原始密钥生成多个轮密钥。
  2. 初始轮：仅进行AddRoundKey操作。
  3. 主轮：执行SubBytes、ShiftRows、MixColumns、AddRoundKey等操作。
  4. 最终轮：与主轮类似，但不执行MixColumns操作。

AES的优势：

  • 安全性高：AES基于复杂的数学函数和多轮加密操作，使得破解极其困难。
  • 速度快：由于设计的高效性，AES在硬件和软件实现中都表现出色，常用于加密通信、文件加密等场景。
  • 灵活性：AES支持不同的密钥长度和多种工作模式（如ECB、CBC、CFB、OFB等），可以适应多种需求。

Universal Hashing

Universal Hashing（通用哈希）是一种哈希函数设计方法，旨在减少哈希冲突并提供更强的随机性，尤其在可能面对恶意输入时表现良好。通用哈希的思想是从一组预定义的哈希函数中随机选择一个来进行哈希，以减少最坏情况下的哈希冲突机会。

通用哈希的基本概念：

假设有一个哈希表 \( T \)，其大小为 \( m \)，我们希望将一组元素（键）映射到这个表的槽位中。通用哈希通过在哈希函数集合中随机选取一个哈希函数 \( h \)，来将一个键 \( k \) 映射到哈希表的槽中。

通用哈希函数的定义： 设 \( H \) 是一个哈希函数的集合。如果对于任何不同的两个键 \( k_1 \) 和 \( k_2 \)，哈希函数 \( h \) 从 \( H \) 中随机选取，使得： [ \Pr[h(k_1) = h(k_2)] \leq \frac{1}{m} ] 则称 \( H \) 是一个通用的哈希函数族。

这意味着任意两个不同的键在哈希表中发生冲突的概率不会超过 \( \frac{1}{m} \)，其中 \( m \) 是哈希表的大小。

为什么需要通用哈希？

普通的哈希函数如果设计不当，可能会导致大量的哈希冲突（即多个键映射到相同的槽）。尤其在最坏情况下，如果输入数据经过精心设计，所有的键可能都映射到同一个槽，这会使哈希表的性能大幅下降，接近线性查找。

通用哈希通过随机化哈希函数的选择，保证了即使是最坏情况，冲突的概率也能得到控制。这对抗恶意输入或有意设计的攻击尤为有效。

常见的通用哈希构造方法：

一种常见的构造通用哈希函数的方法是使用基于模运算的哈希函数。假设我们有一个素数 \( p \)，并且定义一个哈希函数族 \( H \)，其中每个哈希函数 \( h \in H \) 的形式如下：

[ h_{a,b}(k) = ((a \cdot k + b) \ \text{mod} \ p) \ \text{mod} \ m ] 其中： - \( k \) 是要被哈希的键， - \( a \) 是一个随机选择的数，满足 \( 1 \leq a < p \)， - \( b \) 是一个随机选择的数，满足 \( 0 \leq b < p \)， - \( p \) 是一个比键空间大且足够大的素数， - \( m \) 是哈希表的大小。

这种构造的哈希函数族满足通用哈希的条件，因此可以有效减少冲突概率。

通用哈希的优点：

  1. 降低最坏情况下的冲突概率：通过从哈希函数集合中随机选取，减少冲突发生的概率，避免了恶意输入带来的最坏情况。
  2. 随机性：在处理未知数据或潜在的恶意输入时，通用哈希函数表现更为鲁棒。
  3. 适用于动态数据：在需要处理动态输入或存在大量插入和删除操作时，通用哈希的冲突概率控制能力较好。

应用场景：

  • 密码学：通用哈希被用于构造加密算法中的哈希函数，帮助抵御某些攻击类型。
  • 哈希表实现：在设计高效的哈希表时，通用哈希能够有效减少冲突，保证查找和插入的效率。