如何利用密码学以及数论基础攻击一个“宣称安全”的密码系统

最近在对基于区块链构建的信任社会（未来社会形态）非常感兴趣，区块技术去中心化的特性，让没有金融机构成为了可能（包括央行，以及各种商业银行）。

除了在数字货币领域大放异彩外，在包括供应链，网络购物，公平合约等方面的应用也非常广泛。其中智能合约的特性十分的吸引我。

不过我今天并不想讨论区块技术，因为区块技术建立在密码学的技术之上，今天我们讨论如何利用密码学以及数论基础攻击一个宣称安全的密码系统。

在密码学中，算法，秘钥以及协议构成了一个完整的密码系统。

算法是密码系统的基础，它是将一组或多组输入信息转化成一组或多组输出信息的数学方法，算法的输出会被秘钥影响，秘钥不同，输出也不同。因此，加密同样的信息，A用秘钥Ka加密与B用秘钥Kb加密输出的信息是完全不同的。

秘钥是密码系统的核心，奥秘在于算法存在一个最优解（最优解有很多种解释，例如超递增序列，因式分解两素数之和等），这个秘密就是秘钥。如果一个人想要解密别人的密文，在不知道秘钥的情况下，他只能尝试解数学难题，这对于普通人拥有的资源来说，直到宇宙毁灭也无法得出答案。

有了算法和秘钥，没有协议就不是一个密码系统。协议是指由多方参与的，确定要去完成一些事情。如果没有多方参与，或者没有去完成一些目标就不叫协议。协议有很多种，最明显比如秘钥交换协议（例如A和B要在一个加密的通道中传递信息，在这之前A和B要协商一个秘钥并交换，使得A可以加密消息发送给B并确保B可以解密信息）。

密钥交换协议

在一个安全的密码系统中，必须是算法，秘钥，协议都安全，如果其中一个是不安全的，那么整个系统就是不安全的。

大多数流行的公开算法，已经被广泛的证明是安全的，它们经历过很多理论数学家的分析。秘钥的安全性由秘钥长度，以及你是否妥当的保管你的秘钥来决定。如果你做的不错，那么秘钥也是安全的。

协议却不是如此了，协议很脆弱。举个例子，A将重要的信息加密发送给B，只有B有秘钥可以解密这些信息，C在网路上监听到了A发送给B的秘密，但是C没有秘钥无法解密信息，怎么办。上面说过，秘钥是这个数学难题的最优解，如果没有秘钥，C就只能尝试解数学难题，恐怕C这一生都无法解开，但是C的老板要求他必须在72小时内解密信息，不然C所在的公司就要遭受重大损失。于是C决定铤而走险，他绑架了B，并对B进行严刑拷打，B扛不住，交出了他的秘钥，C拿着B的秘钥解密了秘密，并干掉了B。

上面的例子说明了协议在整个密码系统中是一个易攻击的薄弱环节，这样的攻击类型很多（贿赂，美色诱惑，威胁等）。

我们来尝试把这种攻击带入到软件破解上来，同样的结论也是攻击协议，而非攻击算法和秘钥。同样来举个例子，软件D采用RSA公开秘钥算法来对用户的信息以及软件产品序列号摘要进行加密，并发送给软件D公司的注册服务器，软件公司D的计算机收到用户A发送给它的加密信息，用自己的私钥解密并把用户信息与数据库中的信息进行对比，如果序列号不在D公司的数据库中说明这个产品的不是D公司销售的产品，如果序列号在D公司的数据库中，并且A用户信息不在数据库中，那么A是第一次注册，将A的信息与序列号绑定在一起保存在数据库中，此序列号将不能再给其他人使用。如果序列号和A都在数据库中，并且序列号与A绑定，那么D公司用私钥加密一段许可信息发送给A，A每次使用D软件的时候验证这段信息，如果是D公司发送的许可信息允许使用，如果不是不允许登陆。

看起来很不错，RSA是安全的公开密钥算法，并且秘钥被D公司保存起来，除非你能贿赂D公司的员工获得秘钥，或者攻破D公司的网路，否则秘钥也是安全的。因此攻击算法和秘钥是不现实的。那么，我们可以从协议的角度入手，看看有没有弱点。

先简单说一下RSA算法：

1. 选择两个大素数 p 和 q，假设 p=3，q=11
2. 计算 n = p × q = 3 × 11 = 33
3. 计算 ∅(n) = (p – 1) × (q – 1) = 2 × 10 = 20
4. 选择 e 且 1 < e < ∅(n) , e 与 n 互为素数. 假设 e = 7
5. 计算 d，使 (d × e) % ∅(n) = 1. 假设 d = 3，且 d = (3 × 7) % 20 = 1，满足条件
6. 公开 e, n => (7, 33)
7. 保密 d => 3
8. 加密公式 C = Me % n
9. 解密公式 M = Cd % n

用上面的公式加密，假如消息是2，C = 27 % 33 = 29，密文就是29。解密的话就是M = 293 % 33 = 2。

回到刚才的软件破解问题上，软件产品中有e和n，如果能够分解n我们就能够构造d，也就知道了D公司的秘钥，由于分解n是一个数学难题，我们不知道最优解很难解出答案。我们采用另一种方法，破坏协议，首先我们自己选择2个大素数，构造另一个n，并分别求出对应的e和d。然后我们架设一个服务器，用来模仿D公司的验证服务器。

我们侵入D公司的软件，用我们自己的n和e替换D公司的n和e，这时软件D会用我们的公开秘钥加密用户信息以及序列号，这段信息是无法送给D公司验证的，因为D公司没有我们的保密秘钥，无法解密信息，因此这样还无法完成软件的验证。

下一步，我们使软件D将加密好的信息发送给我们刚才架设的模仿D公司的服务器，这台机器拥有我们的保密秘钥，它成功的解密信息，并直接构造一个验证通过的数据块，并用保密秘钥加密发送给D软件。D软件用我们的公开秘钥解密信息，验证一切正常，并将这段信息保存到计算机中。每次D软件启动时，重新检查是否存在验证通过信息块，并用我们设给它的公开秘钥解密，解密成功后通过验证，启动D软件。只要通过一次验证，D软件就无需再次与D公司服务器进行交互，因此完成了破解。

再次说明，算法，秘钥，协议是一个密码系统的组成部分，任何一个方面不安全，整个系统就是不安全的。当下，很多厂商对算法和秘钥很关注，在算法的选择与秘钥的长度上下足了功夫。但他们的系统并不像他们想象的那么安全，因为他们忽视了协议。

PS. 本文仅仅是基于理论方面的讨论，真正的软件破解过程比本文描述的要复杂的多，在real world中尝试发现n和e可能要困难的多。至于Patch程序代码，改变程序运行流程来达到破解目的与本文讨论的主题无关。