X-Hamster-Info: Score=0 Received=20010730142309
Xref: localhost sci.crypt:1097
Path: news.t-online.com!newsmm00.sul.t-online.com!newsfeed01.sul.t-online.de!t-online.de!newsfeed.hanau.net!news-fra1.dfn.de!news.tele.dk!195.54.122.107!newsfeed1.bredband.com!bredband!newsfeed.sovam.com!nf1.bellglobal.com!nf2.bellglobal.com!news20.bellglobal.com.POSTED!not-for-mail
Message-ID: <3B651D48.E5D47EFE@invalid.addr>
From: Carl Duncan <nospam@invalid.addr>
X-Mailer: Mozilla 4.76 [en] (Win98; U)
X-Accept-Language: en
MIME-Version: 1.0
Newsgroups: sci.crypt
Subject: RSA in 7 Steps
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 63
Date: Mon, 30 Jul 2001 04:39:36 -0400
NNTP-Posting-Host: 64.229.99.187
X-Complaints-To: abuse@sympatico.ca
X-Trace: news20.bellglobal.com 996482420 64.229.99.187 (Mon, 30 Jul 2001 04:40:20 EDT)
NNTP-Posting-Date: Mon, 30 Jul 2001 04:40:20 EDT
Organization: Bell Sympatico
X-Old-Xref: news.t-online.com sci.crypt:145779

I wrote the following capsule summary of RSA and the simplest example
I could devise. This was just for my own education but maybe it will be
useful to others so I'll put it here. (I put these notes in the public
domain, so feel free to use it in any way.)  If the more knowledgeable
readers of this list find errors, please do followup with a correction!

=-=-=-=-=-=-=-=-=-=-=-=-=-

RSA Algorithm in 7 Steps:

(1) Pick 2 large primes, p and q, each 1000-2000 bits long. Use 4 Fermat
    Tests to test for primality: If b^(x-1) % x = 1 for each of b={2,3,5,7}
    then x is very likely prime. If != 1 for any b, then x is definitely
    not prime.

(2) Compute the public modulous, n = p*q.

(3) Choose the public exponent e such that e<n and relatively prime
    (no common factors) to (p-1)(q-1).

(4) Calculate the private exponent d = e^-1 mod [(p-1)(q-1)]. This means the
    inverse of e in the field of integers modulo (p-1)(q-1). Extended Euclid
    algorithm will solve this.

(5) The public key is (n,e). The private (secret) key is (n,d).
    Primes p and q are no longer needed and may be discarded, though PGP
    keeps them to speed operations using the Chinese Remainder Theorem.

(6) To encrypt: divide message into blocks smaller than n (i.e., m<n),
    then ciphertext c = m^e mod n. This creates a one-to-one mapping between
    the set of integers {0..n-1} (plaintext) and {0..n-1} (ciphertext).

(7) To decrypt: plaintext m = c^d mod n.


Example:

Using the smallest possible values for p,q,e,d that are all different
and all larger than 2. Using 2 or smaller gives uninteresting examples.

(1) Pick p=3 and q=17
    Check: 2^2 % 3 = 1, 3^2 % 3 = 0 (note: Fermat Test n/a if b=x), etc.
    Check: 2^16 % 17 = 1, 3^16 % 17 = 1, etc.

(2) Compute n = p*q = 3*17 = 51

(3) Choose e=13, such that e<51 and e is relatively prime to (p-1)(q-1) =
    (3-1)(17-1) = 32.

(4) Calculate d=5, such that e*d = 1 mod [(p-1)(q-1)]
    Check: 13*5 = 65 = 1 mod 32

(5) Public key is (n,e) = (51, 13). Private key is (n,d) = (51, 5).

(6) Let letters A=1, B=2, C=3, etc. To encrypt message "BED", divide into
    blocks smaller than 51, so using single letters, m = 2, m = 5, and m = 4.
    c = 2^13 mod 51 = 32
    c = 5^13 mod 51 = 20
    c = 4^13 mod 51 = 4

(7) m = 32^5 mod 51 = 2
    m = 20^5 mod 51 = 5
    m =  4^5 mod 51 = 4