【非对称加密学习笔记】Merkle-Hellman加密算法

从背包问题入手

如果你曾经学习过一些算法竞赛知识，你一定不会对“背包”感到陌生。无论是利用贪心算法来解决分数背包问题，还是利用DP来求解0-1背包问题，这些问题里都涉及了“背包”。

背包问题，即假定一个容量为$W$的背包，对于给定的$n$个物品，每个物品的重量依次为$a_1,a_2,...a_n$，求背包正好可以装入哪些物品。

事实上，我们是在求解下面的方程：

$$\sum_{i=1}^{n}x_ia_i=W$$

显然$x_i$的值只能是0或1，即放入或未放入。那么求解这一方程的时间复杂度也是显而易见的 $\mathcal{O}(2^n)$。

我们假设所有的$x_i$构成一个$n$维的向量 $X=(x_1,x_2,...,x_n),x_i \in \{0,1\}$。这样，我们就得到了一个二进制向量X。同样地还能得到一个向量 $A=(a_1,a_2,...,a_n)$。那么对于我们想要加密的明文$m$，我们可以将其同样表示为一个二进制向量$M$。然后让其与向量$A$相乘(二者维度相同)得到密文$E$。

不过，在我们解密时，这一方法的时间复杂度依然是 $\mathcal{O}(2^n)$。故我们需要构造一个超递增序列，即序列的每一项都大于之前所有项的和。可以表示为：

$$a_i>\sum_{k=1}^{i-1}a_k$$

为什么超递增序列的解密就会简单很多呢？我们可以试着计算一下：已知$x_i$只能是0或1，如果密文$E$大于$a_n$，则$x_n$必为1。再用$E-a_n$和 $a_{n-1}$比较，以此类推，即可解出明文$m$。如果最后总重量不为0，则密文无解。

但这样的加解密仍然是不安全的：加密时使用的向量$A$是公开的，如果密文$E$被攻击者截获，密码很容易被破解。故我们需要一个更安全的背包生成算法，一对公私钥生成算法。

Merkle–Hellman算法

Merkle–Hellman背包加密算法是由Ralph Merkle和Martin Hellman于1978年首次提出的公钥加密算法，其安全性基于背包难题。尽管这个算法后来被证明是不安全的,但它实现了如何将NP完全问题用于设计公钥密码算法,所以这一算法也很值得我们研究。

生成私钥

私钥即初始的背包集$A$，我们生成一个超递增序列$A$即可。

from random import randint

A = [randint(1, 5)] # 可以自行修改初始值
sum = A[0]
for i in range(1, 8):
    A.append(sum+randint(1, 5))
    sum += A[i]

生成公钥

首先取两个素数$p,q$并确保满足以下条件

$$p>\sum_{i=1}^{n}a_i,q \in [1,p-1],(p,q)=1$$

$q$将作为解密时的私钥。

接下来通过模乘计算出一个新的序列$B=(b_1,b_2,...,b_n)$：

$$b_i \equiv qa_i\pmod{p}$$

公钥即生成的新序列(背包)$B$和素数$p$。

from Crypto.Util.number import getPrime

p = getPrime(16)
q = getPrime(16)
B = []
while q >= p:
    q = getPrime(16)
for i in A:
    B.append(q * i % p)

print(A, q)
print(B, p)

加密

对于明文$m$,将其构造成一个序列$M=(x_1,x_2,...,x_n)$，利用公钥$(B,p)$加密如下：

$$E=\sum_{i=1}^{n}x_ib_i \bmod p$$

M = [0, 1, 1, 0, 1, 1, 0, 1]  # 明文二进制序列
E = 0
cnt = 0
while cnt < len(M):
    E += M[cnt] * B[cnt]
    cnt += 1
E %= p
print(E)

解密

对于密文$E$，在我们拥有私钥$(A,q)$的情况下，按如下方式解密：
首先计算$E'$

$$E'=Eq^{-1}\bmod{p}$$

再对$E'$利用超递增背包解密即可得到明文的二进制$M$。

from sympy import mod_inverse

Q = mod_inverse(q, p)
E = E * Q % p
print(E)
decrypted = []
for i in A[::-1]:
    if E >= i:
        decrypted.insert(0, 1)
        E -= i
    else:
        decrypted.insert(0, 0)
if E != 0:
    print("Decryption failed")
else:
    print(decrypted)

完整实现

将以上过程修改并整合，即可实现完整的Merkle–Hellman算法。

from random import randint
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from sympy import mod_inverse

A = B = []
p = q = sum = 0


def generatePrivateKey(length, init, maxAdd):
    global A, sum
    A = [init]
    sum = A[0]
    for i in range(1, length):
        A.append(sum + randint(1, maxAdd))
        sum += A[i]


def generatePublicKey():
    global A, B, p, q
    size = 16
    p = getPrime(16)
    q = getPrime(16)
    while p <= sum:
        p = getPrime(size := size + 1)
        q = getPrime(size)
    while q >= p:
        q = getPrime(size)
    B = [q * i % p for i in A]


def encrypt(message):
    global A, B, p, q
    M = [int(i) for i in bin(bytes_to_long(message))[2:]]
    generatePrivateKey(len(M), 1, 5)
    generatePublicKey()
    E = 0
    for cnt in range(len(M)):
        E += M[cnt] * B[cnt]
    print("Private Key (A):", A)
    print("Public Key (B):", B)
    print("Public p:", p)
    print("Private q:", q)
    print("Encrypted (E):", E)
    return E


def decrypt(encrypted):
    global A, B, p, q
    Q = mod_inverse(q, p)
    encrypted = encrypted * Q % p
    decrypted = []
    for i in A[::-1]:
        if encrypted >= i:
            decrypted.insert(0, 1)
            encrypted -= i
        else:
            decrypted.insert(0, 0)
    if encrypted != 0:
        print("Decryption failed")
    else:
        text = "".join([str(i) for i in decrypted])
        print("Decrypted (text):", long_to_bytes(int(text, 2)))


if __name__ == "__main__":
    message = b"Hello!"
    encrypted = encrypt(message)
    decrypt(encrypted)

破解Merkle–Hellman

在不到两年内，Merkle–Hellman加密算法便被人破解。破解的核心思想是我们不一定要找出正确的乘数 $q$（陷门信息），只需找出任意模数 $p′$和乘数$q′$，只要使用$q′$去乘公开的背包向量$B$时，能够产生超递增的背包向量即可。

具体的破解实现（LLL算法等）将在后续更新。

总结

Merkle–Hellman加密算法为后来的非对称加密算法设计提供了基本思路：寻找一个NP完全类问题，利用加解密的复杂度不对称生成公私钥并实现非对称加密。此外，背包加密体制也并未Merkle–Hellman的被破解而被宣告死刑，后续又出现了不少基于背包加密的变式，但在今天，我们最好还是不要信任它们，尽量选择更安全、高效、广泛的RSA、ECC等非对称加密算法。