hi,
I was helping a friend if mine with rsa key
generation.if it helps u here it is.
I am posting the mail which i sent to him.
1:>Choose 2 large prime numbers p & q
2:>choose n=p*q & z=(p-1)*(q-1)
3:>choose a number relatively prime to z anc call it
d.
two numbers (a,b) are said to be relatively prime if
gcd(a,b)=1
eg:
(5,25) are not relatively prime coz 5 is gcd & not 1
how ever (5,27) are relatively prime coz gcd is 1
In particualr a prime number is relatively prime to
all the numbers except its multiples.
4:>find e such that e*d=1 mod z
here ' = ' means equalance or congrurnce & not equal
to.
a ( congruent) b modulo c,if c/(a-b) or in other words
if a/c gives remainder b
5:>to encrypt plain text p,cipher text c is calculated
as
if ^ denote exponent
c=p^e (mod n)
6:>to decrypt,
p=c^d(mod n)
We take an example,
It is just for the understanding of the reader & uses
very small numbers.
choose
p=3
q=11
hence n=3*11=33
z=(3-1)*(11-1)=20
we find e,such that 7*e(congruent)1 (mod 20),yeilds
e=3
I will try explain with the same example.
7*e=1 (mod 20) means,find e such that 20/( (7*e)-1)
For this we use the euclidean algorithm & the euiler
fermat theorom
The eucledian algorithm simply find the gcd of 2
numbers.
here our purpose of using it is to find gcd of 2
numbers & see if they are relatively prime.
Accoring to euiler-fermat theorom if gcd(a,m)=1, that
is they are relatively prime
then the solution (unique mod m) of the linear
congruence
ax (congruent) b (mod m) is given by
x (congruent) b* ( a^(phi(m)-1)) (mod m) where phi(m)
is the euiler totient function or
the euiler phi function.
if(a,m)=d,then it will have d solutions modulo m.
how ever we are only interested in (a,m)=1,hence 1
solution mod m.
well,Just a few defenitions
Defenition of Euiler Totient
If n>=1 ,the euiler totient phi(n) is defined as the
number of positive integers not exceeding
n that are relatively prime to n.
here are just a few examples
if n=1 phi(1)=1
if n=2 phi(2)=1 (only 1 is relatively prime to 2)
if n=3 phi(3)=2 (1 & 2 are relatively prime to 3)
if n=4 phi(4)=3 (1,2,3 are ...)
if n=5 phi(5)=4 (1,2,3,4 are...)
if n=6 phi(6)=2 (1,5 are...)
here is a usefull property 1 might need to apply some
times
phi(m*n)=phi(m)*phi(n) if gcd(m,n)=1
If a prime p does not divide a then
a^(p-1) (congruent) 1 (mod p)
now as in the example
7*e (congruent) 1 (mod 20)
let us take e=x
so,
7*x (congruent) 1 (mod 20)
by eulier fermat theorom
x(congruent) 1*(7^(phi(20)-1)) (mod 20)
phi(20)=8.i.e there are 8 numbers less than 20 which
are relatively prime to 20
This process of computing the euiler totoient is
speeded up on a computer using the eucledian
algorithm which finds gcd(a,b),for all a les than b &
count those a which are relatively prime to b
whose sum gives the euiler totient.
ok,so x (congruent) 1*(7^(8-1)) (mod 20)
x (congruent) (7^7)mod 20
x (congruent) 823543(mod 20)
823543/20 gives remainder 3,that is 823543(mod 20)=3
therefore x=3 or e=3.
this is how e is actually obtained in the above
example.
the rest of the encryption & decryption are as
mentioned above,i haven't continued the
example with that part since i guess u only need to
know how the key is generated.
to encrypt we have 2 keys (e,n)
to decrypt we have 2 keys (d,n)
n=p*q is easy to calculate
d is a number relatively prime to z
choose a random d,test gcd(d,z) =1 using the euclidean
algorithm,continue the process till u find one.
the only othe key is e,which as above explained is
found using the euiler-fermat theorom &
the euclidean algorithm.
In this manner e,n,d can be found for large primes as
well.
Data.
--- Mike Rosing
On Fri, 31 May 2002, surinder pal singh makkar wrote:
I am a newbie in cryptography. What I have learnt till now is that in assymeric cryptography scenario we have a private key and we generate the public key corresponding to it and then we send it to the central agency.
You don't have to send the public key to a repository, it's just convienient.
Suppose after sometime I have a private key and the public key. Is there some software tool which can tell me whether the public key is the same corresponding to the private key I am having. Also is there some tool which can tell me whether the keys have been curropted or not
With ECC you just recompute the public key from the private key and make sure it matches what's out in public. With RSA you just pick some random value (not zero or 1) and see if r^(e*d) = 1 mod N, or if you know p and q (where N = p*q) check that e*d = 1 mod (p-1)*(q-1). It's the same thing as encrypting/decrypting something to see if you get the same thing back. If not, something is wrong.
I'm not sure how you can tell which key might be corrupted. For the public side, having the key reside in many places would do it - you can just check that they are all the same. so it may well be that saving the public key in a private place for that purpose is also useful.
Patience, persistence, truth, Dr. mike
__________________________________________________ Do You Yahoo!? Yahoo! - Official partner of 2002 FIFA World Cup http://fifaworldcup.yahoo.com