Extended Euclidean Alogorithm??

Hi all,
How can i calculate this equation
d= e^-1 mod ((p-1)(q-1)).
using Extended Euclidean Alogorithm.

Note:
it's one of the RSA equations :).

Bakry
LVL 1
Who is Participating?

Commented:
The EEA (Extended Euclidean Alogorithm) can be used to computer GCD of two numbers as well as the solution to this sort of equation: A*X+B*Y=C, where all variables are integers and X and Y are unknown; A, B and C are given. EEA computes the solution (if any) for A*X+B*Y=1, but both X and Y can then be multiplied by C to reflect the first equation.

So you can reverse mod like this:
I mod J=K
and therefore
I=K+J*X (where X can be any rational number)
which is one of the equations mentionned above.

The algorithm goes like this:

function ExtEuclid(A: Integer; var X: Integer; B: Integer; var Y: Integer): Integer;
{           1. Start with two nonzero integers A and B, and set
(u,U) = (1,0) and (v,V) = (0,1).
2. Express A = q*B + r, q and r integers with 0 <= r < |B|.
3. If r = 0, output |B|, U, and V, and stop.
4. Replace (A,B) by (B,r), (u,U) by (U,u-q*U), and (v,V) by
(V,v-q*V).
5. Go to Step 2 above.}
var
U,V: array[0..1] of Integer;
Q,I: Integer;
begin
I:=0;
U[0]:=1;
V[0]:=0;
U[1]:=0;
V[1]:=1;
repeat
Result:=B;
Q:=A div B;
B:=A-Q*B;
A:=Result;
I:=1-I;
Dec(U[I xor 1],Q*U[I]);
Dec(V[I xor 1],Q*V[I]);
until B=0;
X:=U[I];
Y:=V[I];
end;

0

Commented:
Hi

For computation of the RSA Decryption Exponent You not need

d= e^-1 mod ((p-1)(q-1))

far better or correct is

d = e^-1 mod LCM(p-1, q-1)

LCM is the "Least Common Multiple" and

LCM(A, B) = A div GCD(A, B) * B

For e^-1 You need the modular Inverse = InvMod()

repeat
Random(e, Log2(p * q)) //randomize e to Log2(x) Bits
e = e or 1
d = InvMod(e, LCM(p -1, q -1))
until Log2(d) >= Log2(e) and GCD(d, p * q) = 1

For the GCD and extended GCD the Lehmer-Collins Variant is far faster as the binary Method above.

Regards, Hagen

0

Commented:
sorry, i found a typo

// this one is correct
Random(e, Log2(Log2(p * q)) * 4)
0

Author Commented:
what's X, Y.
the resukt of Function is GCD.
but how can i use it to Calculate the
Expression
d= e^-1 mod ((p-1)(q-1)).
:)
0

Author Commented:
sorry for delaying ... yesterday was our Religion Day

bakry
0

Commented:
Hi

You need the GCD() to compute the LCM() and the extended GCD() is used to compute the modular Inverse

x := 1/x mod m

d := 1/e mod LCM(p -1, q -1), because e^-1 = 1/e

Hagen
0

Commented:
My function will compute A*X+B*Y=1 (where A and B are given, X and Y are returned).

If we have:

I mod A=J

then we know that

J+A*X=I

and thus

A*X=I-J

Now we assume that B=0 and we substitute I-J by C, so we get:

A*X+B*Y=C

Now if we know X in the equation

A*X=1

we can multiply it by C and get:

A*X*C=C

So that's what you are finally looking for. The number you're looking is X*(I-J); the function I wrote down will compute X and you know all other numbers as constants.
0

Author Commented:
this is my code

function ExtEuclid(A: Integer; B: Integer): Integer;
{           1. Start with two nonzero integers A and B, and set
(u,U) = (1,0) and (v,V) = (0,1).
2. Express A = q*B + r, q and r integers with 0 <= r < |B|.
3. If r = 0, output |B|, U, and V, and stop.
4. Replace (A,B) by (B,r), (u,U) by (U,u-q*U), and (v,V) by
(V,v-q*V).
5. Go to Step 2 above.}
var
U,V: array[0..1] of Integer;
Q,I: Integer;
X, Y: Integer;
begin
I:=0;
U[0]:=1;
V[0]:=0;
U[1]:=0;
V[1]:=1;
repeat
Result:=B;
Q:=A div B;
B:=A-Q*B;
A:=Result;
I:=1-I;
Dec(U[I xor 1],Q*U[I]);
Dec(V[I xor 1],Q*V[I]);
until B=0;
end;

function isPrime(Number: int64): Boolean;
var
Count: int64;
begin
Count:= 2;
if Number < 4 then
Result:= True
else
begin
While Number Mod Count <> 0 do
Inc(Count);
Result := Count = Number;
end;
end;

function GetN(P, Q: int64): int64;
begin
Result:= P * Q
end;

function GetPHI(P, Q: int64): int64;
begin
Result:= (P-1) * (Q-1);
end;

function GetE(N, P, Q: int64): int64;                         //invMod
var
PHI: int64;
i: int64;
begin
Randomize;
PHI:= GetPHI(P, Q);
Result:= Random(PHI) + 3;
While (not isPrime(Result)) and (ExtEuclid(Result, PHI) <>1) do
Result:= Random(PHI) + 3;
end;

function Power(X, P: int64): int64;
var
i: int64;
begin
Result:= 1;
i:= 1;
While i <= P do
begin
Result:= Result * X;
inc(i);
end;
end;

function GetD(E,PHI: int64): int64;
var
z, uu, q, vv, u1, u2, u3, v1, v2, v3, t1, t2, t3: int64;
begin
u1:= 1;
u2:= 0;
u3:= PHI;
v1 := 0;
v2 := 1;
v3 := E;

while (v3 <> 0) do
Begin
q := floor(u3/v3);
t1 := u1 - q * v1;
t2 := u2 - q * v2;
t3 := u3 - q * v3;

u1 := v1;
u2 := v2;
u3 := v3;

v1 := t1;
v2 := t2;
v3 := t3;
z := 1;
end;
uu := u1;
vv := u2;
if (vv < 0) then
Result := vv + PHI
else
Result := vv
end;

function RSAEncrypt(m: int64; e, n: int64): int64;
begin
Result:= power(m, e) mod n;
end;

function RSaDecrypt(C: int64; d, n: int64): int64;
begin
Result:= Power(c, d) mod n;
end;
0

Commented:
Hi

1.) in GetE(), E must NOT prime, only preferable odd and >= 3.

procedure BuildRSAKey(var N,P,Q,D,E: Integer);
var
L: Int64;
begin
GeneratePrime(P);
GeneratePrime(Q);
N := P * Q;
L := LCM(P-1, Q-1);
repeat
repeat
E := random(Log2(N)) * 4;
E := E or 1;  // make Odd
until E >= 3;
D := InvMod(E, L);
until (D > E) and (GCD(D, N) = 1);
end;

2.) in RSAEncrypt/RSADecrypt You do a Power(m, e) mod n, but what happend with large e and m ?? You produce very provable overflows !! A better way would be a binary PowMod() procedure, like

procedure PowMod(B,E,M: Int64): Int64;
// B^E mod M
var
T: Int64;
begin
T := B;
B := 1;
while E <> 0 do
begin
B := B * B;
if Odd(E) then B := (B * T) mod M;
E := E shr 1;
end;
Result := B;
end;

Finally:

Your code is part of a School Project to demonstrate how RSA work ??
For a real secure Solution You can't use small Int64, because a secure RSA need >= 1024 Bit Modulus N, means two ~512Bit Primes, minimal !!

0

Author Commented:
i will try
:)
0

Author Commented:
can u get me a ful code ???
0

Commented:
Hm

difficult, I have no code for < Int64, because that's useloss. Above is a basicaly starting point. My own code use Large Integers upto 4Gb. For such large Numbers we need ALL stuff new and common strategies don't work fast. As Example only my Multiplication of large Integers are ~1000 lines assembler and use 4 different algortihms dependend from the Integer-size. The modular exponentation is basicaly as describe above, but use a right to left binary variable M-array sliding window technology. Today I have three times fully rewriten my math stuff developed in the last two years.

As starting point I can You suggest a very good book:

"Handbook of applied Cryptography" A.Menezes, ISBN: 0-8493-8523-7, in this book You will find all relevant stuff.

Another Book come's from Knuth, but that is out of sale (I hope that's correct english :)

Hagen

0

Commented:
bakry99, as startin point for large integers you can send me a mail ar avw@gmx.ch and I'll send you a unit of mine which is designed to handle positive integers of any size, including multiplication, division, modulo, prime test etc. It will probably be slower that Hagen's code, but it's available and easy to use.
0

Commented:
Hi

@AvonWyss:

I'm very interessting, mailto:HaReddmann@T-Online.de

You currently develop on that stuff ??
I search allways new peoples for discussion on such themes.

My current solution use a very fast forged Interface based version, with automatical de/allocation, assigmnents, reference counting and stacks.

Hagen

.ch, erzeugt den Eindruck Du bist ein Schweizer ??
0

Commented:
Hagen, code is on the way... its actually is an old unit (1997), written when Delphi 2 was brand new, so there's no interface stuff in it (unlike newer projects of mine which heavily use interfaces). The most basic operations (add, sub, shift, logic) are written in fair assembly code, the rest of the stuff is done using plain object pascal.

Du hast ubrigens richtig geraten, ich bin Schweizer ;-)
0

Author Commented:
now i have a problem with RSA See my Code and try to make your change on it so as to make a Simple RSA.

bakry
0

Commented:
Bakry99, how's it going? I believe that hagen's or my comments should have answered your initial question. I answered the exact question, while hagen has provided the solution for the computation you should use whan doing RSA.
0

Commented:
ADMINISTRATION WILL BE CONTACTING YOU SHORTLY.  Moderators Computer101 or Netminder will return to finalize these if still open in seven days.  Please post closing recommendations before that time.

Question(s) below appears to have been abandoned. Your options are:

1. Accept a Comment As Answer (use the button next to the Expert's name).
2. Close the question if the information was not useful to you, but may help others. You must tell the participants why you wish to do this, and allow for Expert response.  This choice will include a refund to you, and will move this question to our PAQ (Previously Asked Question) database.  If you found information outside this question thread, please add it.
3. Ask Community Support to help split points between participating experts, or just comment here with details and we'll respond with the process.
4. Delete the question (if it has no potential value for others).
--> Post comments for expert of your intention to delete and why
--> You cannot delete a question with comments, special handling by a Moderator is required.

For special handling needs, please post a zero point question in the link below and include the URL (question QID/link) that it regards with details.
http://www.experts-exchange.com/jsp/qList.jsp?ta=commspt

Please click the Help Desk link on the left for Member Guidelines, Member Agreement and the Question/Answer process for further information, if needed.  http://www.experts-exchange.com/jsp/cmtyHelpDesk.jsp

http://www.experts-exchange.com/questions/Q.20064557.html
http://www.experts-exchange.com/questions/Q.20113946.html
http://www.experts-exchange.com/questions/Q.11266855.html
http://www.experts-exchange.com/questions/Q.20128885.html
http://www.experts-exchange.com/questions/Q.20138412.html
http://www.experts-exchange.com/questions/Q.20179513.html
http://www.experts-exchange.com/questions/Q.20189500.html
http://www.experts-exchange.com/questions/Q.20203706.html
http://www.experts-exchange.com/questions/Q.20241461.html

http://www.experts-exchange.com/questions/Q.20084169.html

PLEASE DO NOT AWARD THE POINTS TO ME.

------------>  EXPERTS:  Please leave any comments regarding your closing recommendations if this item remains inactive another seven (7) days.  Also, if you are interested in the cleanup effort, please click this link http://www.experts-exchange.com/jsp/qManageQuestion.jsp?ta=commspt&qid=20274643

Moderators will finalize this question if still open in 7 days, by either moving this to the PAQ (Previously Asked Questions) at zero points, deleting it or awarding expert(s) when recommendations are made, or an independent determination can be made.  Expert input is always appreciated to determine the fair outcome.

Thank you everyone.

Moondancer
Moderator @ Experts Exchange

P.S.  For any year 2000 questions, special attention is needed to ensure the first correct response is awarded, since they are not in the comment date order, but rather in Member ID order.
0

Commented:
See posting 08/26/2001 08:18AM PST.
0

Commented:
Thanks, AvonWyss.  Since there is a 300 point maximum on a per-question basis, I have awarded you 200 points and the other 100 points to Hagen here -> http://www.experts-exchange.com/jsp/qManageQuestion.jsp?qid=20289339

I believe this is the fair outcome, but listening further.

Moondancer - EE Moderator
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.