Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Extended Euclidean Alogorithm??

Posted on 2001-06-02
Medium Priority
335 Views
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
0
Question by:bakry99
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 6
• 6
• 6
• +1

LVL 14

Accepted Solution

AvonWyss earned 800 total points
ID: 6149056
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

LVL 2

Expert Comment

ID: 6150204
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

LVL 2

Expert Comment

ID: 6150206
sorry, i found a typo

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

LVL 1

Author Comment

ID: 6151747
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

LVL 1

Author Comment

ID: 6151765
sorry for delaying ... yesterday was our Religion Day

bakry
0

LVL 2

Expert Comment

ID: 6152111
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

LVL 14

Expert Comment

ID: 6153016
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

LVL 1

Author Comment

ID: 6155747
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

LVL 2

Expert Comment

ID: 6155801
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

LVL 1

Author Comment

ID: 6158939
i will try
:)
0

LVL 1

Author Comment

ID: 6173189
can u get me a ful code ???
0

LVL 2

Expert Comment

ID: 6173859
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

LVL 14

Expert Comment

ID: 6173971
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

LVL 2

Expert Comment

ID: 6174014
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

LVL 14

Expert Comment

ID: 6174076
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

LVL 1

Author Comment

ID: 6176097
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

LVL 14

Expert Comment

ID: 6426420
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

LVL 1

Expert Comment

ID: 6900982
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

LVL 14

Expert Comment

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

LVL 1

Expert Comment

ID: 6940648
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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A lot of questions regard threads in Delphi. Â  One of the more specific questions is how to show progress of the thread. Â  Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to theâ€¦
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small printâ€¦
Add bar graphs to Access queries using Unicode block characters. Graphs appear on every record in the color you want. Give life to numbers. Hopes this gives you ideas on visualizing your data in new ways ~ Create a calculated field in a query: â€¦
In this video, Percona Solution Engineer Dimitri Vanoverbeke discusses why you want to use at least three nodes in a database cluster. To discuss how Percona Consulting can help with your design and architecture needs for your database and infrasâ€¦
###### Suggested Courses
Course of the Month6 days, 7 hours left to enroll