请解释 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

代码正在搜索与已经 select 编辑的值 q 互质的值。在我看来，它做得很差，但你说它是一个模拟器？我不确定那是什么意思，但也许它只是意味着代码又快又脏，而不是又慢又安全。

直接回答您的问题：

Why is random number generated with upper bound 1000?

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

1000的上限可以保证选择的r足够大。一般来说，大键比小键更难破解，所以如果 q 很大，那么这段代码只会找到大的 r.

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

Why is it subtracted from q?

减法很重要，因为 r 必须小于 q。 Merkle-Hellmen 算法就是这样指定的。我不认为它需要那样做。 public 密钥是通过将 w 中的每个元素乘以 r 并取 modulus q。如果 r 非常大，大于 q，它似乎会进一步混淆 q 并且每个w.

中的元素

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

但是，如果 nextInt 可以 return 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互质。显然，随机 selected 的数字不能保证与另一个其他数字互质，因此随机生成的候选数可能不适用于此 q.

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

请解释 Merkle–Hellman 背包密码系统的这段代码？

Please explain this code for Merkle–Hellman knapsack cryptosystem?

cryptography