python - 使用Python代码计算离散对数的问题

Question

我有一组对数，它们是 L1、L2 和 L3，我从论文 An Ultra-secure Router-to-router Spontaneous Key Exchange System (2015), here 中检索到它。本文的目的是在 Alice 和 Bob 之间安全地共享 key 。例如，Alice 向 Bob 发送了 K = 46。 Bob 从 Alice 那里收到了 key 。 key 可以表示为:

key 需要使用三阶段过程共享。 L1:爱丽丝给鲍勃。 L2:鲍勃给爱丽丝。 L3:爱丽丝到鲍勃。等式是:

Bob 可以使用以下方法评估 key :

这是方程式的结果:

给定 alpha = 5 的值，x = 15 和 p = 97。我用Python实现后，得到了错误的结果，与表中的结果不一样:

a=5
x=15
p=97
i1=0.958478
i2=4.238835

L1=a**(x+i1)%p
L2=a**(x+i1+i2)%p
L3=a**(x+i2)%p
K=L3*(a**(-i2))

print ("L1",L1)
print ("L2",L2)
print ("L3",L3)
print ("K",K)

产生这个结果:

L1 55.596893310546875
L2 2.15625
L3 68.87890625
K 0.07503566293789979

另一个问题是我尝试手动计算，但结果仍然与表中的结果不一样。我希望任何人都可以帮助我。谢谢。

Answer 1

我的一位精通数学的 friend 帮助我找出了问题所在。你得到的答案是正确的。问题在于作者为 i1 和 i2 给出的值。

一个单独的附加十进制数完全改变了这部分中 mod p 操作的结果:

L1 = a**(x+i1)%p在 i1 等于 0.958478 的情况下，输出为:55.596893310546875

现在，如果您在 i1 的值末尾再加一个 1，导致 i1 为 0.9584781，则同一等式的输出将变成一个完全不同的数字:37.163330078125

如果你比较算法确定K = L3*a**(-i2)，使用给定的i2 4.238835，你也会很快发现结果不等于46。K的初始值，用算法 (a**x)%p 计算得出，是 46，所以这就是上面的算法应该评估的结果。相反，具有给定值的该等式的结果是 0.05102662974。

我的 friend 根据作者说他们使用的是 Matlab 这一事实提出了一个理论。 Matlab 具有允许用户限制显示的小数位数字的功能。小数仍然按照它们的实际值运行，但它们在屏幕上的表示被截断到指定的小数位。对于大多数操作，这完全没问题，对计算结果的影响可以忽略不计。但是，在执行模运算时，单个 1，即使在数字的最低有效小数位，也可以改变整个数字。

因此我们推测实际的 i1 和 i2 值被它们在 Matlab 中的显示设置截断了。这不会改变算法的真实性，也不会阻止它在操作结束时评估变量 K 的正确值。所有使用 i1 和 i2 的完整十进制值的结果都会显示出来。但是，对于使用 Matlab 在计算时向我们的作者显示的相同数字的人来说，这也会使整个过程无法重现。