Copy Link
Add to Bookmark
Report
NuKE Issue 06-011
================================================================================
Volume 1, Issue 6, May 1993
NuKE Info-Journal #6
NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE
uK E-
KE "Rivest, Shamir, Adleman, (RSA) Encryption" -N
E- Nu
-N uK
Nu By KE
uK Rock Steady E-
KE -N
E-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-NuKE-Nu
Ahh, the last NuKE Informational Journal #5, concerning DES Encryption brought
about a fair amount of generous reviews. It has even inspired me to continue
this topic of `Digital Security' hence forth I introduce to you RSA. Rivest,
Shamir, Adlemen (RSA) are the three mathematicians whom have patented the idea
of `Public-Key' encryption, which by far isn't `just another' encryption
method.
Public-Key crypto-systems are often referred to as `asymmetric' crypto-systems. The
now famous DES is of a form of `symmetric' crypto-systems. Symmetric, consists
the use of a single key for decrypting and encrypting. Asymmetric on the other
hand, consists of two keys; a public key used to encrypt, and a private key
used to decrypt the cipher. (Cipher, is data that is encrypted)
RSA algorithm work on the idea that prime numbers cannot be broken into a
product of smaller factors. The algorithms work like so; first pick a number
N that is the product of two prime numbers (call the two primes a and b so
that N = a x b). Next, pick a number that will become your public key, and
call it P; P _must_ be less than N. Now to encrypt a message M, you simple
apply the following formula:
C=M^P(mod N)
% What the hells `mod'? %
Public-key crypto-systems depend heavily on a number theory known as modular
arithmetic or finite math. "Mod" can be said to be a remainder of a number.
13 mod 5 = 3, since that's the remainder when 13 is divided by 5. But the
theory of Modular Math contains a pattern, a range, depending on the modular
numbers. The modular of 50, are numbers from 0, 1, 2, ..., 49; the smallest
being 0, and the largest is the modulus number minus 1.
A less formal and probably easier-to-visualise is called the `clock arithmetic'
If you restrict yourself to performing math by moving the hour hand clockwise
(addition) or counterclockwise (subtraction) around the face of a clock, you'll
soon see obvious patterns. Mostly, no matter how complex the math is, your
answer will _always_ be some number in the range of 1 to 12, which are the
number of hours on a standard clock. This actually is the basis of `finite'
mathematics, whereby you are always working with integers and you're always
working with a finite set of integers.
Therefore, results of addition, subtraction, multiplication and division
will _always_ land in the set defined by the modulus. (huh? how can that be?)
As with the clock theory, the numbers "wrap around", meaning if the modular of
50 is a set of integers from 0 -> 49, once we reach 49 (the largest number) and
add 1, we would get 0. The number 49 will wrap around to 0, and the reverse is
true (0 wraps around to 49).
The great think about modular math, is that it's finite, you don't have to worry
about calculations yielding numbers that grow out of control, and also, since
we are working with integers, you don't lose any information through round-off
errors as you would with floating-point.
Back to our formula;
C=M^P(mod N)
where C is the encrypted message, notice the message will be represented as
numbers, you can use the ASCII value of each characters. See it's not hard to
find two large prime numbers (a and b) but if I hand you their product (N), you
will perhaps never find a and b again! So in RSA, you get a huge 512-1024 bit
prime number which is the product of two large primes, a and b. The number N is
made public, while a and b remains secret. And after the formula is completed
the encrypted message cannot be cracked without factoring N!
Now to decrypt the message we use the some-what same formula with different
factors;
M=C^p(mod N) (Note: This is lower case `p')
where `p' (lower case) is the secret key. The secret key is calculated using
the formula;
P x p = 1(mod L)
where L is the least common multiple of (a-1) and (b-1). In mathematical
terminology, `p' is the multiplicative inverse of `P' in the modulus L.
Algorithms are available for computing least common multiples and
multiplicative inverses in modular arithmetic. You can look-up theses formulas
for more understanding in almost any good college mathematic book, as I cannot
teach you math in a matter of paragraphs. But I suspect most of the readers
already know such basic mathematical skills.
Anyhow, RSA has undergone quite a bit of research around its algorithm.
Breaking the system requires the determination of `a' and `b', which are
the factors of `N' (don't forget `N' and `P' are publicly known). Once you
know `a' and `b', the factors of `N', you can easily calculate L. Knowing L
and P, you can calculate `p' (lower case), and decrypt the ciphertext. This
boils down to the task of factoring a number into its prime components, an
ongoing popular problem in number theory that continues to occupy the minds
and computers of mathematicians around the world.
In October 1988, it took an international group of computer scientists nearly
a month to factor a 100-digit number. More than 400 computers worked on the
problem during idle hours to find the number's two factors. One 41 digits long,
the other 60 digits long. In June 1990, another team factored a 155-digit
number. The number was hand-picked to make the task easier, but it still took
275 years worth of ONE computer's time. To keep pace with even-faster computers
RSA's inventors can simply add more digits to the system's key.
================================================================================
