[REBOL] Re: RSA Encryption
From: joel:neely:fedex at: 13-Nov-2003 11:14
Hi, Matt,
I'll give it a shot...
Matt MacDonald wrote:
>Can someone please explain to me, in as few mathematical equations as
>possible, why RSA public/private encryption works? ... How is this
>any different from using a syncronous encryption method and then just
>sending the encryption key along with the data? It just doesn't make sense to me.
>
Let's sneak up on it. For simplicity of examples, suppose that
all of my messages will be made up of ONLY uppercase letters,
spaces, periods, or question marks (29 possible characters).
We can represent our characters via:
0 = space, 1-26 = A-Z, 27 = period, 28 = question mark
and then encode messages by doing arithmetic on the numbers (
as long as our results are limited to the range 0-28).
A trivial example would encode by adding some fixed value (mod
29) to the plaintext and decode by subtracting that same fixed
value (mod 29) to the plain text. Here the here the algorithms
for encoding and decoding are different, but the keys for those
operations are the same. Let's make the algorithm the same (by
adding the key mod 29 to each value), which means that the
decoding key is must be the mod-29 complement of the encoding
key. IOW, if I encode by adding 3, I decode by adding 26.
In that simple case it is trivial to figure out the decoding key
from the encoding key.
Suppose I multiply by the encoding key (mod 29) instead. It's
a bit more work, but still easy to figure out what decoding key
I can multiply by (mod 29) to get back the original character.
Suppose I use two encoding keys (a and b) and encode a character
by evaluating
encoded-character: a * plain-character + b // 29
Now it's slightly more complicated (or just plain time consuming)
to figure out what values of (c and d) will give me
plain-character: c * encoded-character + d // 29
i.e. the original character's number.
Enough dinky examples. As we increase the mathematical complexity
of the formula, we discover that that the effort to find the
decoding key *EVEN IF WE KNOW THE ENCODING KEY AND THE FORMULA*
can increase substantially.
Public key cryptography is based on using certain mathematical
operations that *NOBODY* knows how to invert in reasonable time.
(Of course, that could change dramatically if quantum computing
provides us a way to factor arbitrary huge numbers quickly!)
Anyway, that's the core idea of why the public key can be made
... well ... public! without exposing the message content.
HTH!
-jn-