cryptography - 请解释一下 Merkle–Hellman 背包密码系统的代码？

Question

这是实现 Merkle–Hellman 背包密码系统的程序的代码片段。

// Generates keys based on input data size
private void generateKeys(int inputSize) 
{
    // Generating values for w
    // This first value of the private key (w) is set to 1
    w.addNode(new BigInteger("1"));
    for (int i = 1; i < inputSize; i++) 
    {
        w.addNode(nextSuperIncreasingNumber(w));
    }
    // Generate value for q
    q = nextSuperIncreasingNumber(w);

    // Generate value for r
    Random random = new Random();

    // Generate a value of r such that r and q are coprime
    do 
    {
        r = q.subtract(new BigInteger(random.nextInt(1000) + ""));
    }
    while ((r.compareTo(new BigInteger("0")) > 0) && (q.gcd(r).intValue() != 1));

    // Generate b such that b = w * r mod q
    for (int i = 0; i < inputSize; i++) 
    {
        b.addNode(w.get(i).getData().multiply(r).mod(q));
    }
}

请告诉我以下几行发生了什么:

    do 
    {
        r = q.subtract(new BigInteger(random.nextInt(1000) + ""));
    }
    while ((r.compareTo(new BigInteger("0")) > 0) && (q.gcd(r).intValue() != 1));

(1)为什么生成的随机数上限为1000？

(2)为什么要从q中减去它？

Answer 1

代码正在搜索与已选择的值q互质的值。在我看来，它做得相当糟糕，但你提到它是一个模拟器？我不确定这意味着什么，但也许这只是意味着代码快速而肮脏，而不是缓慢而安全。

直接回答您的问题:

1. Why is random number generated with upper bound 1000?

Merkle-Hellman algorithm 确实表明r应该是“随机”。这样做的实现非常随意；这可能就是让你失望的原因。从技术上讲，该代码不是算法，因为不能保证循环终止。理论上，r 的伪随机候选选择可能是任意长的数字序列，这些数字与 q 不互质，从而导致无限循环。

上限 1000 可能是为了确保所选的 r 足够大。一般来说，大按键比小按键更难破解，因此如果 q 很大，那么此代码只会找到大的 r。

获得随机互质数的一种更具确定性的方法是测试低于 q 的每个数字，生成互质数列表并随机选择一个。这可能会更安全，因为攻击者知道 q 和 r 彼此相差在 1000 以内，搜索空间就会显着减少。

2. Why is it subtracted from q?

减法很重要，因为r 必须小于q。 Merkle-Hellmen 算法就是这样指定的。我不相信事情必须如此。公钥是通过将 w 中的每个元素乘以 r 并取模 q 生成的。如果r非常大，大于q，似乎会进一步混淆q和w中的每个元素>.

另一方面，Merkle-Hellmen 的解密步骤取决于 modular inverse每个加密字母a x r⁻¹ mod q。此操作可能会因 r > q 受到阻碍；看来还是可以解决的。

但是，如果 nextInt 可以返回 0，则循环的迭代就是一种浪费，因为 q 和 r 必须不同(gcd(a,a) 只是 a)。

分解代码:

do 

至少尝试一次。在调用该方法之前，r 可能为 null 或未定义。

    r = q.subtract(new BigInteger(random.nextInt(1000) + ""));

查找 q 和 q - 1000 之间的候选值。

while ((r.compareTo(new BigInteger("0")) > 0) && (q.gcd(r).intValue() != 1));

继续前进，直到找到一个 r :

• 大于 0 r.compareTo(new BigInteger("0")) > 0，并且
• 与 q 互质，q.gcd(r).intValue() != 1。显然，随机选择的数字不能保证与另一个数字互质，因此随机生成的候选数字可能不适用于此 q。

这样就清楚了吗？我必须承认我不是 Merkle-Hellman 方面的专家。