0

我试图将我已经用 Java 制作的 RSA 加密程序重新创建到 Erlang 中。我不知道如何生成私钥。我原来的java代码：

    privateKey = publicKey.modInverse(phi);

我找不到任何通用算法来在线查找“d”或私钥。大多数具有无法在更大的问题中实现的小简单方程，或者教程只是给出了私钥而没有解释过程。有人可以指点我一个方向，以便我可以学习生成私钥吗？或者如果 Erlang 中有模反函数，请指出它是什么。

先感谢您

编辑：要求解的实际方程是 [e*d mod (phi) = 1]，其中 e 是公钥，d 是私钥，phi = [p-1][q-1]。当所有其他变量都已知时，我非常想解决 d

EDIT2：Wolframalpha.com 返回 d 的多个可能值。这是如何运作的？

4

3 回答 3

2

虽然在 crypto 或 public_key 模块中可能隐藏着类似的东西，但它不是其公共 API 的一部分。

由于 Erlang 内置了大整数（普通整数实际上可以得到任意大小），因此很容易实现一种常用算法来计算您的值。

例如，扩展欧几里得算法将特别容易使用递归函数实现。

于 2013-10-31T19:46:08.563 回答
1

没有反模这样的东西，因为从技术上讲，反模有无数种解决方案。

重新创建可用版本的唯一方法是使用模本身

int rest = number%dividor;
int quotient = (number-rest)/dividor;

int modInv = dividor*quotient+rest;
于 2013-10-31T19:00:38.253 回答
1

下面的代码完成了这项工作，在 wolfram 页面中缺少的是您必须选择大于 2 且小于 phi 的解决方案，然后只有一个解决方案。

[编辑]添加一个测试来检测 M 和 C 何时不是相对素数，然后返回一个比之前报告的算术错误更明确的错误元组

-module (decod).

-export ([private/2]).

% In the key generation you start by choosing P and Q 2 big primes
% N = P*Q
% M = (P-1)*(Q-1)
% C a number smaller than M such as gcd(M,C) = 1
% the public key is made of {N,C}
% then lets find U and V such as C*U + M*V = 1 and 2 < U < M
% the private key is {U,N}
private(M,C) when is_integer(M), is_integer(C), M > C-> 
    P = private1({M,0},{C,1}),
    adjust(P,M).


private1(_,{1,P}) -> P;
private1(_,{0,_}) -> {error,gcd_not_1};
private1({R1,U1},{R2,U2}=A2) ->
    F = R1 div R2,
    private1(A2,{R1-R2*F,U1-U2*F}).

adjust(R,_) when is_tuple(R) -> 
    R;
adjust(P1,M) when P1 =< 2 ->
    K = (2 - P1) div M + 1,
    P1 + K * M;
adjust(P1,M) when P1 >= M ->
    K = (P1 - M) div M + 1,
    P1 - K * M;
adjust(P1,_) -> P1.
于 2013-11-01T06:42:22.120 回答