Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!cbosgd!ihnp4!inuxc!iuvax!pur-ee!uiucdcs!snail!carroll
From: carroll@snail.UUCP
Newsgroups: comp.sys.ibm.pc
Subject: Re: Public Key systems
Message-ID: <15500002@snail>
Date: Fri, 20-Nov-87 10:39:00 EST
Article-I.D.: snail.15500002
Posted: Fri Nov 20 10:39:00 1987
Date-Received: Mon, 23-Nov-87 01:58:13 EST
References: <283@caus-dp.UUCP>
Lines: 41
Nf-ID: #R:caus-dp.UUCP:283:snail:15500002:000:1609
Nf-From: snail.CS.UIUC.EDU!carroll    Nov 20 09:39:00 1987


(Apologies to R,S & A if this violates some copyright law...)

RSA public key encryption :

1. Find 2 primes, about the same size (with in a couple orders of magnitude)
   Call them p and q.

2. Let n = p * q

3. Let z = (p-1) * (q-1)

4. Pick a number e that is relatively prime to z. (In practice, most people
   pick e prime, but that's not strictly necessary). e should be less than
   z.

5. Pick d such that it has the property that e*d mod z = 1.

6. Tell everyone e,n but not any of the other numbers. (Given any of p,q,z,d,
   a person familier with the RSA system can break it very easily).

7. To encode a message, break it up into units that map onto integers in the
   range (1..n-1). It's not necessary to use all of the range, but the more
   range the more secure. Take each unit (P) and produce the encoded version
   (C) by setting C = pow(P,e) mod n.

8. To decode, use the fact that P = pow(C,d) mod n.

Hints: This should all be done using arbritrary precision integer math,
not floating point. To speed up the pow function, there is a trick involving
squaring and multiplying that works that same way as shifts and adds for
multiplying, which makes pow linear in the magnitude of d,e instead of
exponential. I have some code that does this for small values of p,q,n,
written in pseudo-stack machine (it was part of mp test data for students,
who wrote the simulator). I can e-mail it to you with explanations if you
want.


Alan M. Carroll		amc@woodshop.cs.uiuc.edu	carroll@s.cs.uiuc.edu
...ihnp4!uiucdcs!woodshop!amc
Quote of the day - "I just work here, I don't make policy decisions"