这是实现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中减去？
代码正在搜索与已选择的值互质的值q。在我看来，这样做的效果很差，但是您提到它是模拟器吗？我不确定这意味着什么，但是也许这只是意味着代码既快速又肮脏，而不是缓慢而安全。
直接回答您的问题：
- 为什么生成上限为1000的随机数？
该梅克尔-Hellman算法 确实表明，r应该是“随机”。这样做的实现很偶然。那可能就是让你失望的原因。从技术上讲，该代码不是算法，因为不能保证循环会终止。从理论上讲，的伪随机候选者选择r可能是任意长的数字序列，这些序列不是互质的q，从而导致无限循环。
上限1000可能是为了确保所选r的足够大。通常，大键比小键更难破解，因此如果q大键，则此代码只会找到大r。
获取随机互素的更确定性的方法是测试每个小于q的互素，生成一个互素列表并随机选择一个。这可能会更安全，因为攻击者知道这一点q并且r彼此之间的距离在1000以内，搜索空间将大大减少。
- 为什么从q中减去？
减法很重要，因为r必须小于q。Merkle-Hellmen算法以这种方式指定它。我不认为一定要那样做。通过将w中的每个元素乘以r并取模数q来生成公共密钥。如果r非常大，大于q，似乎将进一步混淆q和w中的每个元素。
另一方面，Merkle-Hellmen的解密步骤取决于每个加密字母a x r -1 mod q的模逆。使用>可能会妨碍此操作。似乎仍然可以解决。rq
但是，如果nextInt可以返回0，则循环的迭代将浪费a，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是：
r.compareTo(new BigInteger("0")) > 0，并且q，q.gcd(r).intValue() != 1。显然，不能保证随机选择的数字与另一个数字互质为素数，因此随机生成的候选者可能对此无效q。这样可以清除吗？我必须承认我不是Merkle-Hellman的专家。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句