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 <[EMAIL PROTECTED]> 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
