[plug] [semi-OT] Public/private keys?

[levsky at rave.iinet.net.au]

On Sun, Nov 24, 2002 at 03:33:31PM +1100, Andrew Furey wrote:
> > A -->(process)-->B    but B -->(reverse process) 
> > !>A  (you cannot ge A from > B)
> > 
> > If you can accept that as fact for now, this is how
> > it works ........
> 
> [snip]
> 
> Hmm. Yes, I understand that side of it (and to answer
> Craig's question, I was thinking of digital signing
> when I said "vice versa").
> 
> I also assumed that there was no way to reverse it, or
> else PK crypto would be basically useless. I was just
> curious as to precisely _how_ it works... although
> using factorisation seems to make sense, as Craig
> suggested.
> 

RSA (the most common PK cryptosystem) is actually dead easy really.
It's simple enough to perform that a standard question on the UWA 3rd
year algorithms exam is to use RSA - with small keys of course - to encrypt
a couple of bytes of text, using just pen and paper (and a non-programmable
calculator).  You just need to know a little about how modulo arithmetic
works.  It works like this..

Pick two (large) random prime numbers, call them p and q
Calculate n=pq
Pick a small odd integer that is relatively prime to phi(n), where phi(n) 
is equal to (p-1)(q-1).  Call this small number e.
Calculate d, where d is the muliplicative inverse of e (modulo phi(n))

Now, your public key is the pair of numbers e and n.
Your secret key is the pair of numbers d and n.

Lets say we want to encrypt a message M.  We calculate P(M) by going

P(M)=M^e (mod n)

And to decrypt a ciphertext C we can calculate D(M) by going

D(M)=C^d (mod n).

That's the process - here's why it works, following Rivest's proof - The 
algebra is his, the explanations are mine.

--------------------------------------------------------------------------

Now, these two operations cascaded just produce M.

D(P(M)) = M^(e*d) (mod n)

Now - Remember how we said earlier that e and d are multiplicative inverses
modulo phi(n) - ie, e * d (mod phi(n)) = 1, and that phi(n) = (p-1)(q-1)

That means that ed = 1 + (p-1)(q-1)*k, where k is some integer constant (putting
the *k in allows us to remove the modulo phi(n) terms)

Now, the next step depends on whether M (mod p) is zero or not.
If M *is* zero (mod p), then we can trivially say that M^(e*d) = M (mod p)
If M is *not* zero (mod p), then

	M^(e*d) = M(M^(p-1))^(k(q-1)) (mod p) - by using ed = 1+k(p-1)(q-1)
		= M(1)^k(q-1)         (mod p)
			We can do this step because p was prime, and
			Fermat's theorem states that for all prime numbers p
			a^(p-1)=1 for all a.   I'll state this one without
		= M (mod p) - because 1^(n) = 1 for all n


Therefore, we've just shown that no matter what M is, M^(ed) = M (mod p)
We can follow exactly the same argument to show that M^(ed) = M (mod q)

And finally, putting those two together M^(ed) = M (mod n) for all M

Therefore - going right back to the original equation

D(P(M)) = M^(e*d) (mod n) = M and therefore doing D(P(M)) gives you the
original message back.

The security arises from the fact that it's considered difficult to get
d and n, when you've only got e and n.  Currently, the only way that
has been thought of of doing this is by factoring n, which is shared.
If you can factor n, you can get p and q, and therefore you can regenerate
d from e, just as we did when we created the original keypair.


Hope this has explained the theory behind it reasonably clearly.

Cheers

Mark






-- 
Perl is designed to help people learn the bits of programming they need 
right now without forcing them to learn the techniques they aren't ready 
for. But when they are ready for them, Perl tries to be there too. We just 
don't tell the beginners that the speedometer on their golf cart wraps 
around several times.    - Larry Wall