python解密代码中pow(a，b，n)函数的反函数

Question

我正在使用已经可用的加密代码处理python解密代码。

在加密代码中，我有战俘(B， XYZ， ABC(

数字被加密并传递到数组中。

现在在解密时，我需要获取"b"的值(来自上面的 pow 函数(，因为我在 Array 中有值。

使用模数给出范围内的值，而不是确切的值，这是我的解密逻辑工作所必需的。

如何继续这样做？

Answer 1

首先你分解928108726777524737。它有 2 个质因数，称为 P 和 Q。然后，您需要找到一个d的值，以便d * 65539 mod (P-1)(Q-1) == 1(为此使用扩展欧几里得算法(。

完成此操作后，给定c = pow (b, 65539, 928108726777524737)您可以使用pow(c, d, 928108726777524737)计算回b

为了帮助您多一点P=948712711，Q=978282167给d=872653594828486879

>>> c = pow(99, 65539, 928108726777524737)
>>> pow(c, 872653594828486879, 928108726777524737)
99

当然，在

现实生活中，你会从质因数开始，并使它们比这大得多，在这种情况下，在不知道因素的情况下逆转这个过程是不切实际的。对于这样的小值，很容易分解和计算逆值。

d的计算：

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

首先找到质因数：

>>> P, Q = 948712711, 978282167
>>> P*Q
928108726777524737
>>> egcd(65539, (P-1)*(Q-1))
(1, -55455130022042981, 3916)

我们想要中间值x：

>>> gcd, x, y = egcd(65539, (P-1)*(Q-1))

但是我们必须让它变得积极，我们可以通过添加(P-1)*(Q-1)值来做到这一点：

>>> x + (P-1)*(Q-1)
872653594828486879