可证明安全密码学与启发式密码学

0. 什么是可证明安全密码学与启发式密码学

在密码学领域，密码算法的安全性评估通常分为两大类：可证明安全密码学（Provably Secure Cryptography）和启发式密码学（Heuristic Cryptography）。这两种方法在评估密码算法的安全性方面有着不同的理论基础和实践应用。

1. 可证明安全密码学

可证明安全密码学（Provably Secure Cryptography）是一种基于数学证明的方法来评估密码算法安全性的方式。其核心追求的是数学上的严谨证明。一般来说，可证明安全密码学的算法都是基于某个机器困难的数学问题的，例如整数分解问题、离散对数问题等。通过证明一个密码算法的安全性可以归约到一个已知的困难问题上，我们可以得出该算法在理论上的安全性。

2. 启发式密码学

启发式密码学（Heuristic Cryptography）则是一种基于经验和实践的方式来评估密码算法安全性的方式。启发式密码学的算法通常是基于一些经验法则和实践观察来设计的，而不是基于严格的数学证明。这些算法可能在某些情况下表现出良好的安全性，但没有经过严格的数学证明，因此在理论上可能存在潜在的安全漏洞。但这不意味着启发式密码学的算法一定不安全，许多启发式密码算法在实践中被广泛使用，并且没有被发现严重的安全漏洞。

3. 比较

特点	可证明安全密码学	启发式密码学
安全根基	归约到已知的数学难题	抵抗所有已知的密码分析攻击手段
安全证明	基于数学证明	基于经验和实践观察
效率（一般而言）	较低，计算开销大	较高，适合大规模数据

4. 常见的安全算法的归类

算法类型	归类	归类原因
AES	启发式密码学	AES 的核心结构被称为 SPN（代换-置换网络）。它通过 S 盒（Substitution）进行混淆，通过行移位和列混淆进行扩散。其并不归属于任何一个数学难题，但是我们缺少有效的密码分析手段来攻击
MD5	启发式密码学	MD5 依赖于极其复杂的位操作（位移、异或、逻辑与/或）和多轮循环。进而制造出“雪崩效应”。MD5 的设计并不基于任何一个数学难题，所以可能被破解，2004 年，王小云教授及其团队展示了 MD5 的碰撞攻击，意味着 MD5 不再安全
RSA	可证明安全密码学	RSA 的安全性可以严格归约到大整数分解问题的困难性上。也就是说，如果存在一个有效的算法能够在多项式时间内分解大整数，那么 RSA 就不安全。反之，如果我们假设大整数分解问题是困难的，那么我们可以证明 RSA 是安全的
ECC	可证明安全密码学	ECC 的安全性归约到椭圆曲线离散对数问题。目前我们公认这个问题是困难的，因此 ECC 被认为是安全的