Solved

Extended Euclidean Alogorithm??

Posted on 2001-06-02
20
319 Views
Last Modified: 2010-04-06
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 :).


thanks in advance.
  Bakry
0
Comment
Question by:bakry99
  • 6
  • 6
  • 6
  • +1
20 Comments
 
LVL 14

Accepted Solution

by:
AvonWyss earned 200 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;

Hope this answers your question.
0
 
LVL 2

Expert Comment

by:Hagen040798
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

by:Hagen040798
ID: 6150206
sorry, i found a typo

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

Author Comment

by:bakry99
ID: 6151747
in your Function AvonWyss
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

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


bakry
0
 
LVL 2

Expert Comment

by:Hagen040798
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

by:AvonWyss
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

by:bakry99
ID: 6155747
this is my code
please try it and tell me what about it??

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

by:Hagen040798
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

by:bakry99
ID: 6158939
i will try
:)
0
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 1

Author Comment

by:bakry99
ID: 6173189
Please Hagen
can u get me a ful code ???
0
 
LVL 2

Expert Comment

by:Hagen040798
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

by:AvonWyss
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

by:Hagen040798
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

by:AvonWyss
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

by:bakry99
ID: 6176097
please guys
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

by:AvonWyss
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

by:Moondancer
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

Click you Member Profile to view your question history and keep them all current with updates as the collaboration effort continues, to track all your open and locked questions at this site.  If you are an EE Pro user, use the Power Search option to find them.  Anytime you have questions which are LOCKED with a Proposed Answer but does not serve your needs, please reject it and add comments as to why.  In addition, when you do grade the question, if the grade is less than an A, please add a comment as to why.  This helps all involved, as well as future persons who may access this item in the future to seek help.

To view your open questions, please click the following link(s) and keep them all current with updates.
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


To view your locked questions, please click the following link(s) and evaluate the proposed answer.
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

by:AvonWyss
ID: 6902068
See posting 08/26/2001 08:18AM PST.
0
 
LVL 1

Expert Comment

by:Moondancer
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

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

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…
This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi proj…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now