在C中生成私有RSA密钥＃

我的值为p,q,n和e并且想要计算私钥d。我怎么能这样做，有人可以给我的例子C＃代码？我正在使用BigInteger类来表示p,q,n和e的值，所以我假设d也将是BigInteger。在C中生成私有RSA密钥＃

来源

2010-09-18 b3n

短方式是计算È模的逆（P-1）*（Q-1）。其实你只需要p-1和q-1的最小公倍数，但这不会给你买太多（是的，d有几个可能的值，这是正常的，它们都是等价的）。

如果您的BigInteger类具有模块化逆方法，那么这将很容易：只需调用它即可。否则，你将不得不使用扩展欧几里德算法自己计算它（这是BigInteger类倾向于用来计算模块反转的东西）。

来源

2010-09-20 12:31:30

从Wikipedia：

确定d（使用模算术）满足全等关系

换句话说，ED - 1可以被均匀地由欧拉除以（P - 1）（q - 1）。

这通常使用扩展的欧几里得算法来计算。

d保持为私钥指数。

扩展欧几里德算法可以让你找到整数，这样使得下式成立：

alt text

扩展欧几里德算法是特别有用，当a和b是互质，因为x是模b的模乘法逆。

在这个公式设置a到e，b到(p-1)(q-1)和gcd(a, b)为1（因为需要e和φ（PQ）在RSA算法进行互质）和解决x，让你的d。维基百科页面extended Euclidean algorithm有关于如何编写算法来解决x和y的更多细节。例如，你可以使用这个递归函数（伪代码）：

function extended_gcd(a, b) 
    if a mod b = 0 
     return {0, 1} 
    else 
     {x, y} := extended_gcd(b, a mod b) 
     return {y, x-(y*(a div b))}

在.NET中，如果你只是想生成你不必自己实现RSA算法的一些RSA密钥。在.NET框架中已经有了一个可以使用的RSA实现。

Generating Keys for Encryption and Decryption

来源

2010-09-18 08:24:18

我知道如何从头开始生成密钥，但出于好奇心我试图从上述值恢复d。 – b3n 2010-09-18 08:54:46

这是我做到了。

素数p = 7和q = 17

计算N = P * Q = 119

计算F（N）=（P-1）*（Q-1）= 96

计算d = e^-1 mod f（n），例如峰，d = 77

来源

2010-09-18 09:56:55 b3n

在C中生成私有RSA密钥＃

回答

相关问题