.........,.........,.........,.........,.........,.........,.........,.......|
[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 rimes
p2 = the other
e = the 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.