HIR Issue 5: RSA Public Key Encryption
[eqAhy3Hu79.Lt0ferW!zP6} RSA Public Key Encryption {3islX4bQheu%Lgp1Wfg;Gm2] By Frogman
'Tis time you all got a dose of crypto fer your own use. With this little explination, you will get a quick understanding of how simple, yet how complex RSA (and with IDEA: PGP) is.
So, this info comes to me from Bruce Bosworths' "Codes, Ciphers, and Computers. An Introduction to Information Security." Copyright 1982 ISBN 0-8104-45149-2
Lib. O' Congress Z103.b58
Dewey Decimal!!! 001.54'36
If you can not find the book with that information, you're screwed. With the big stink the govt. is putting out about crypto being too powerful, I felt it was time for an article about a cryptosystem published 15 years ago, and designed 20 years ago. Ronald Rivest, Adi Shamir, and Len Adelman are the MIT dudes who wrote "A Method for Obtaining Digital Signatures and Public-Key Cyptosystems" in the MIT Technical Memo LCS/TM82, in April, 1977. Their combined lastname initials, R. S. A., are how the algorithm got its name. I'll try to skip the plaintext, crytotext blahblahblah, because for now, I'm just giving you the algo. I'm about up to my ears in stuff to do, and don't have the time to get much code churned out. I'll just follow the book, and 'splain the algo, and give an example.
The Math Bits:
We're gonna need some algebra level math, but it's nothing that can't be done pretty easily with some programming work.
Prime numbers are the heart of this whole thing! For those who were asleep that day in math class, or each day for each level you took (I had this con- cept beat into my head every year from 4th grade division to 12th grade calculus) I'll explain. You may know that division is multiplications tricky friend, and that it sometimes (read most of the time) will give you a frac- tion or decimal if your numbers don't divide evenly. A prime number is one that can be divided by every number between itsself and one, and no number will give you a nice whole answer.
The Greatest Common Divisor is the biggest number that you can divide two numbers by, and get a whole answer for both.
Modular Arithmetic is a way of defining that we want the remainder of a pair of numbers. Umm... b (mod a) = c would look like:
a / b == d, Remain c Now, We Start:
Everyone needs three numbers to create a keyset for RSA. Two must be prime, and for a higher level of security, the bigger they must be. The third is a big number. Pick it at random, though it is recommended to pick either 3 or 65536, because that part of the key is in the public key, and doesn't really matter.
When you hear about 48-bit, 56-bit, and 64-bit+ encryption, you are hearing about the number of 1s and 0s that are in the binary numbers the crypto programs use (ie. pretty big). Most systems use a 32-bit address to specify the location of up to four gigs of RAM. With a 48-bit number, you can address 281,474,976,710,656 locations. Yes, that is trillions. And with that many choices, one can find a good number of prime numbers. Imagine what you can do with a number in the range of a 128-bit number: 340,282,366, 920,938,463,463,374,607,431,768,211,456 possibilities. If you want a load of choices, w/ a 1000-bit code you got: 107150860718626732094842504906000181056 14048117055336074437503883703510511249361224931983788156958581275946729175 53146825187145285692314043598457757469857480393456777482309854210746050623 71141877954182153046474983581941267398767559165543946077062914571196477686 542167660429831652624386837205668069376!!! Fuck it, my fingers are getting sick of it... But it's a bitch of a long number, 302 digits, and I do not feel like double checking them either.
To make a keyset we do the math. The numbers used are labeled as follows:
- p1 = one of the <p>rimes
- p2 = the other
- e = the <e>xtra number
The public key is the easiest:
Multiply your two prime numbers and find n.
- p1 * p2 = n
The public key you give to your buddies is (e,n), though with PGP, your key is encrypted with RSA, and the encrypted key is used for IDEA encryption.
Is know as a KEK, or a Key Encrypting Key.
The secret key is found with:
d = GCD((p1-1)*(p2-1))*((p1-1)*(p2-1))+1
------------------------------------
e (d,n) will be your secret key.
Now we gotta check and see if the math and all was right (error correction rules!)
Check and see if:
1 = e * d (mod ((p1-1)*(p2-1))) Okay, so let's find out how to crypt everything:
Use a number to represent every character in the message. Hrm.. what set of numbers is an American standard, and is used alot internationally anyway?? Could it be our old friend, the American Standard Code for Information Interchange?? Gee, lets use a 6-bit number, and assign a character to each one, that gets rid of most of those odd chars... look at RFC1113 for the pofficial list.
- m = char number
- c = char number spit out after formula
Take your number, use a public key and run it through the formula as such:
- c = m^e (mod n)
Change all your numbers to letters, send the text to your
And to get back what you send, your friend would do the same thing, with their secret key:
- m = c^d (mod n)
And change all the numbers back to letters, and read your plans for world domination, or the answers to that math quiz he's taking 6th hour, that you took 2nd...
So, with that basic intro to the algo, I'll end. For another article, I'll give some refinements, and show some code.
