Re: ::scr tales from the crypto

["Simon Kinahan" <simon@xxxxxxxxxxxxxxxxxxx>]

> Right. Imagine we have a message, which can be thought of as
> the variable $message, and public and private keys which can be thought
> of as functions (like wot you get in maths).
>
> Public/Private key cryptography works on the premise that
>
>   $message == private(public($message))
>
> and
>
>   $message == public(private($message))
>
>
> ie. public is the inverse function of private[0]. The functions can be
> anything but obviously you want something that's difficult to break but
> that starts getting into the realm of scary maths so I won't go into it
> now.

The other important thing - the thing that actually makes it difficult to
break - is that it should be very hard to deduce what private is, given only
public. If, for instance, we chose "add 5 to each byte of the message" to be
public, then it would be very easy to deduce that private is "subtract 5
from each byte of the message", and that wouldn't work at all well as an
encryption scheme.

The actual choice of public and private used in (most of ?) the dual key
encryption schemes we have are based on the fact that it is easy, given two
prime numbers, to find their product, but given the product of two prime
numbers, it is very hard (NP-complete, actually) to find those numbers. We
choose public so that it encrypts the message using two prime numbers in
such a way that the only way to decrypt it is using private, which uses the
product of the same two prime numbers.

Another way of looking at it (due, I think, to Diffie and Hellman) is that
sending a message in a conventional encryption scheme is like sending a
message in a padlocked box. Before you send the message, you have to send
the key to the box. If we assume that the communication channel is not
secure (which is why you have to padlock the box), you need another, secure,
channel to send the key through. Before that chap at GCHQ discovered dual
key cryptography the first time, this was a very real problem: governments
spent huge sums securely transporting carefully generated random noise
around the world for use in One Time Pad crypto schemes.

Although it definitely is not safe to send a key through an unsecured
channel, there's no reason not to send a padlock. After all, what use is a
padlock with no key ? So, if John wants to communicate with Jane, they first
of all exchange padlocks, to which each of them owns the key. So John now
has the key to a lock that Jane has, and vice versa. When John wants to send
a message, he uses Jane's padlock to lock the message in  a box. He sends
the box to Jane, through the unsecure channel. Jane can unlock it and read
the message. Bingo: we can turn an insecure channel into a secure one,
without needing a secure channel to already exist.

Now, replace the key with "private" and the padlock with "public", and we
can make an insecure electronic channel secure.

Simon