bakry99
asked on
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
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
sorry, i found a typo
// this one is correct
Random(e, Log2(Log2(p * q)) * 4)
// this one is correct
Random(e, Log2(Log2(p * q)) * 4)
ASKER
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)).
:)
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)).
:)
ASKER
sorry for delaying ... yesterday was our Religion Day
bakry
bakry
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
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
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.
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.
ASKER
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;
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;
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 !!
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 !!
ASKER
i will try
:)
:)
ASKER
Please Hagen
can u get me a ful code ???
can u get me a ful code ???
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
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
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.
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 ??
@AvonWyss:
I'm very interessting, mailto:HaReddmann@T-Online
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 ??
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 ;-)
Du hast ubrigens richtig geraten, ich bin Schweizer ;-)
ASKER
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
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
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.
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.
https://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. https://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.
https://www.experts-exchange.com/questions/Q.20064557.html
https://www.experts-exchange.com/questions/Q.20113946.html
https://www.experts-exchange.com/questions/Q.11266855.html
https://www.experts-exchange.com/questions/Q.20128885.html
https://www.experts-exchange.com/questions/Q.20138412.html
https://www.experts-exchange.com/questions/Q.20179513.html
https://www.experts-exchange.com/questions/Q.20189500.html
https://www.experts-exchange.com/questions/Q.20203706.html
https://www.experts-exchange.com/questions/Q.20241461.html
To view your locked questions, please click the following link(s) and evaluate the proposed answer.
https://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 https://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.
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.
https://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. https://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.
https://www.experts-exchange.com/questions/Q.20064557.html
https://www.experts-exchange.com/questions/Q.20113946.html
https://www.experts-exchange.com/questions/Q.11266855.html
https://www.experts-exchange.com/questions/Q.20128885.html
https://www.experts-exchange.com/questions/Q.20138412.html
https://www.experts-exchange.com/questions/Q.20179513.html
https://www.experts-exchange.com/questions/Q.20189500.html
https://www.experts-exchange.com/questions/Q.20203706.html
https://www.experts-exchange.com/questions/Q.20241461.html
To view your locked questions, please click the following link(s) and evaluate the proposed answer.
https://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 https://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.
See posting 08/26/2001 08:18AM PST.
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 -> https://www.experts-exchange.com/jsp/qManageQuestion.jsp?qid=20289339
I believe this is the fair outcome, but listening further.
Moondancer - EE Moderator
I believe this is the fair outcome, but listening further.
Moondancer - EE Moderator
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