From: Jeremy Cooper <jeremy@crl.com>
Date: Mon, 7 Mar 94 11:04:00 PST
To: ANGeL <craig@hebron.connected.com>
Subject: Re: basic RSA info
In-Reply-To: <Pine.3.89.9403061624.A19239-0100000@hebron.connected.com>
Message-ID: <Pine.3.87.9403062148.A9061-0100000@crl2.crl.com>
MIME-Version: 1.0
Content-Type: text/plain


On Sun, 6 Mar 1994, ANGeL wrote:

> I'm working on writing some simple code fora class, and I was wondering 
> if anyone had some information on the RSA algorithm that I could look 
> at.  I don't know a lot about cryptology at the moment, so I'd need it in 
> layman's terms.  
> 
> /|NGeL of |>eATH
> 21 keystrokes south of Seattle (on a clear day)
> Finger me for my PGP 2.3a public key.
> Have you terrorized a Republican today?
> 

From what I know, RSA thrives on the following formula.  Every key in an RSA 
public key system has two parts.  One part is a very very large number, 
and the other is a relatively small number.  We will call the large 
number 'l' and the small number 's'.  These two numbers are calculated 
beforehand (shown in a later equation).  To encrypt plaintext (which is 
what we call the stuff to be encrypted) with an RSA key, you use the 
following formula:

[ E stands for encrypted text.  P stands for plaintext ]

      P^s
E =  ------ 
       l   

In this example.  Let's use the letter 'A' for our plaintext.
Let's say we have a key with l = 85 and s = 3.  (don't worry about where 
those numbers came from, we'll make them later).  If we use the ASCII 
standard, the character 'A' has a value of 65.  So if we plug in all the 
values we get:

      65^3
E = -------- = 2307 and a remainder of 92
      119 

To decrypt, you use the private key.  In this case, the private key is
l = 119   s = 32 and the new equation is:

     92^32
D = ------- = 6937619471... and a remainder of 65
      119

So we have encrypted with one key, and decrypted with the other.  Now as 
to how we arrived at these two key parts, I will explain.

When you make an RSA key, you generate three numbers.  Two of them are 
prime and one is just odd.  We'll name these P Q and E respectively.
The first part of the key is P * Q, the second part of the key is E.
In the above example, P = 17  Q = 7  E = 3.  So we end up with the key
{119, 3}.  This is the public key.  To make the private key, we keep the 
first part the same, but we change E.  The new E now equals:

	(P - 1)(Q - 1)
E  =    --------------
              Eo             (Eo means the old value of E)

So the value of E for the private key is (16 * 6) / 3 = 32.  
Now that I think about it.  I am sure to have messed something up.  
Please send a flame back attacking what I foobared.  Thank you.
                   _  .  _ ___ _  .  _
===-|)/\\/|V|/\/\ (_)/_\|_|\_/(_)/_\|_| Stop by for an excursion into the-===
===-|)||| | |\/\/  mud.crl.com 8888 (_) Virtual Bay Area!                -===