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


thanks in advance.
  Bakry
LVL 1
bakry99Asked:
Who is Participating?
 
AvonWyssConnect With a Mentor 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;

Hope this answers your question.
0
 
Hagen040798Commented:
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
 
Hagen040798Commented:
sorry, i found a typo

// this one is correct
 Random(e, Log2(Log2(p * q)) * 4)
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
bakry99Author Commented:
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
 
bakry99Author Commented:
sorry for delaying ... yesterday was our Religion Day


bakry
0
 
Hagen040798Commented:
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
 
AvonWyssCommented:
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
 
bakry99Author Commented:
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
 
Hagen040798Commented:
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
 
bakry99Author Commented:
i will try
:)
0
 
bakry99Author Commented:
Please Hagen
can u get me a ful code ???
0
 
Hagen040798Commented:
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
 
AvonWyssCommented:
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
 
Hagen040798Commented:
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
 
AvonWyssCommented:
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
 
bakry99Author Commented:
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
 
AvonWyssCommented:
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
 
MoondancerCommented:
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
 
AvonWyssCommented:
See posting 08/26/2001 08:18AM PST.
0
 
MoondancerCommented:
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.

All Courses

From novice to tech pro — start learning today.