C++伪RSA求解d（解密密钥）快速地与大量

for(d = 0;; d++) 
{ 
    if((d * e) % tn == 1) 
     break; 
}

下面的代码被用在我的RSA方案，以找到哪个将用作解密密钥d变量的值（d，N ）到目前为止，在处理大量数字时，此功能需要一段时间才能循环。我想知道是否有更快的算法，因为用大整数模数总是很慢。C++伪RSA求解d（解密密钥）快速地与大量

例如，如果e值是8161并且tn值是656316480，那么完全计算d需要4秒多的时间。该程序正常工作，只是这部分速度很慢。

我试过使用扩展欧几里得算法来计算D，但由于某种原因它总是给我带来麻烦。

uint64_t extended_gcd(uint64_t a, uint64_t b) 
{ 
uint64_t x = 0, lastx = 1, y = 1, lasty = 0, temp, quotient; 
    while(b != 0) 
    { 
     temp = b; 
     quotient = a/b; 
     b = a % b; 
     a = temp; 
     temp = x; 
     x = lastx - quotient * x; 
     lastx = temp; 
     temp = y; 
     y = lasty - quotient * y; 
     lasty = temp; 
    } 
    return lasty; 
}

捆绑有;

d = extended_gcd(tn, e) 
if(d < 0) //d CAN be negative 
    d += tn;

伊夫从当我搜索我看到一个老论坛帖子复制上述功能（extended_gcd），它实际上做的工作，但只有少数。当数字变得太过极端时，返回值意外的大，搞乱了整个解密密钥。我不知道问题出在哪里，我无法在其他地方用相同的算法找到可靠的函数。就像我说的，我想找到一个更好的算法，我发布了第一个for循环，但我都没有想法。

来源

2014-12-29 nurtul

如果可能的话，RSA会被破坏（并且每个人都会知道或者绝对没有人）。 –

@ElliottFrisch，所以你告诉我没有办法让它变得更快？ – nurtul

好悲伤。我希望不会：） – namezero

你正在运行到的问题是：你的整数太小，当值变大就会溢出...

固定大小的整数，对于像RSA ......没有什么好主意，除非你碰巧有整数与几千位长...而不是正常的整数，甚至uint64_t，尝试任意精度整数库像GMP ...

你的extended_gcd看起来是正确的...这是扩展欧几里得算法，应该为真正的工作世界RSA密钥生成

来源

2014-12-30 15:28:29 DarkSquirrel42

这很有道理我也会研究这个 – nurtul

好吧我找到了解决我的问题的答案。下面的函数是模逆，它显然是一个修改的扩展欧几里德算法，它可以正确求解。

uint64_t modinv(uint64_t u, uint64_t v) 
{ 
    uint64_t inv, u1, u3, v1, v3, t1, t3, q; 
    int64_t iter; 
    u1 = 1; 
    u3 = u; 
    v1 = 0; 
    v3 = v; 
    iter = 1; 
    while(v3 != 0) 
    { 
     q = u3/v3; 
     t3 = u3 % v3; 
     t1 = u1 + q * v1; 
     u1 = v1; 
     v1 = t1; 
     u3 = v3; 
     v3 = t3; 
     iter = -iter; 
    } 
    if(u3 != 1) 
     return 0; 
    if(iter < 0) 
     inv = v - u1; 
    else 
     inv = u1; 
    return inv; 
}

，其中 “U” 被设置为等于 “e” 和 “V” 被设定为等于 “TN”

例

P = 31 
Q = 7 
TN = (P - 1) * (Q - 1) = 180 
N = P * Q = 217 
E = 1 < E < TN and coprime with N so... 53 
D = Calculated using function above... 17 

Value to be encrypted with public key (E, N) = 32 
32^(E) % N = 32^7 % 217 = 156 
Value to be decrypted with private key (D, N) = 156 
156^(D) % N = 156^17 % 217 = 32

我假定上述数学已经正确因为完成这是我的程序直接复制粘贴。我用更大的数字尝试了它，一个达到〜90000的素数，结果是即时和正确的。我希望我不会被这里的东西蒙骗。

来源

2015-01-02 02:39:57 nurtul

C++伪RSA求解d（解密密钥）快速地与大量

回答

相关问题