marcos@caus-dp.UUCP (Marcos R. Della) (11/18/87)
Hello there, I am trying to put together a minor public key system (not a
totally secure system with mega large prime numbers, but a resonably small
one) mainly for the method of usage, not because it is really secure...
As I understand it, the public key system works on the principle of
K(D(P)) = P where K is the key function and
D is the decryption function.
Now, I can't remember the entire algorythm, but I do remember that somehow
you take your number, multiply it by your key and mod it by k*d. Is this
right so far? Then you do something with your decrypt key and you should
get the original number back...
The big question is, what am I doing wrong and does someone have a better
explination than I have? Also, if anyone has any code that would show
or illustrate this better, could you post it to the net?
Thanks for any help you can provide!
Marcos R. Della
--
...!lll-crg -> !csustan -\ | Whatever I said doesn't
...!sdsu ----->->!polyslo!caus-dp!marcos | mean diddly as I forgot
...!ihnp4 -> !csun ----/ | it even before finishing
...!dmsd ---/ | typing it all out!!!carroll@snail.UUCP (11/20/87)
(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"
sysop@stech.UUCP (Jan Harrington) (11/26/87)
in article <283@caus-dp.UUCP>, marcos@caus-dp.UUCP (Marcos R. Della) says: > > Hello there, I am trying to put together a minor public key system (not a > totally secure system with mega large prime numbers, but a resonably small > one) mainly for the method of usage, not because it is really secure... > > As I understand it, the public key system works on the principle of > > K(D(P)) = P where K is the key function and > D is the decryption function. > > Now, I can't remember the entire algorythm, but I do remember that somehow > you take your number, multiply it by your key and mod it by k*d. Is this > right so far? Then you do something with your decrypt key and you should > get the original number back... > As I understand it, it works like this: Choose r as the product of two large primes, p and q. Your encryption key, e, is another prime number, relatively prime to (p-1)*(q-1). Any prime larger than p and q will do. You publish r and e. d, the decryption key is computed as: d * e mod (p-1)*(q-1) = 1 (this is the only part I'm not certain about, as I'm doing this from memory) To encrypt you do the following: P (the plain text) ^^e mod r To decrypt you do the opposite: C (cyphered text) ^^d mod r So, if anyone knows r and e they can encrypt, but without factoring r to get p and q you can't decrypt. Somebody out there should verify my formula for d. I know it's close, but I'm not confident that it's exactly right! Jan Harrington, sysop Scholastech Telecommunications ihnp4!husc6!amcad!stech!sysop or allegra!stech!sysop ******************************************************************************** Miscellaneous profundity: "No matter where you go, there you are." Buckaroo Banzai ********************************************************************************