How can i check the authenticity of a private key

[gfgs pedo]

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 at 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