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 <eresrch@eskimo.com> wrote:

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

On Fri, 31 May 2002, Mike Rosing wrote:

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.

Also with RSA, if you know p/q, you should probably check to see if they're actually prime. :) For DSA, assuming only one of the keys has been changed, checking y == g^x mod p should detect it. Again, checking primality (and that q divides p-1) seems prudent. -Jack