CODEWITHSUNDEEP
erlangrsa
YazanLpizra
YazanLpizra

Reputation: 540

Is there a modular inverse function in erlang? - Erlang

Im trying to recreate an RSA encryption program I had already made in Java into Erlang. I cannot figure out how to generate the private key though. My original java code:

privateKey = publicKey.modInverse(phi);

I couldn't find any general algorithms to find the 'd' or private key online. most feature small simple equations that cannot be implemented in larger problems or the tutorial simply gives the private key without explaining the process. Can someone point me in a direction so I could learn to generate the private key? Or if there is a modular inverse function in Erlang, indicate what it is please.

Thank you in advance.

EDIT: the actual equation to solve is [e*d mod (phi) = 1], where e is the public key, and d is the private key, and phi = [p-1][q-1]. I pretty much want to solve for d when all the other variables are known

EDIT2: Wolframalpha.com returns multiple possible values for d. How does that work?

Upvotes: 1

Views: 447

Answers (3)

Pascal
Pascal

Reputation: 14042

the following code do the job, what is missing in the wolfram page is that you have to choose the solution greater than 2 and smaller than phi, and then there is one single solution.

[edit] add a test to detect when M and C are not relative primes and then return an error tuple more explicit than the arithmetic error reported previously

-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.

Upvotes: 2

Peer Stritzinger
Peer Stritzinger

Reputation: 8372

While ther might be something like this hidden somewhere in crypto or public_key modules it is not part of their public API.

Since Erlang has builtin big-integers (the normal integers can get practically arbitrary size) it is quite easy to implement one of the usual algorithms to calculate your value.

For example the Extended Euclidean Algorithm would be particularly easy to implement with recursive functions.

Upvotes: 3

ThaBomb
ThaBomb

Reputation: 722

There's no such thing as an inverse modulo, because technicly there's an infinit amount of solutions to an inverse modulo.

The only way you can recreate a usable version is by using the modulo itself

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

int modInv = dividor*quotient+rest;

Upvotes: 2

Related Questions