cross
|
|
response 2 of 5:
| 
Oct 9 00:09 UTC 2006 |
To kick this item off, after Todd's post, here's an explanation of how the
RSA cryptosystem works. RSA (which stands for Rivest, Shamir, Adleman - the
names of its authors, all professors at MIT) is a ``public key'' encryption
algorithm. That is, it uses two separate keys for encryption and
decryption. The two share a relationship which makes it possible for data
encrypted with the public key to be decrypted with the private key, but not
the other way around. Further, it is considered computationally infeasible
to derive the private key from the public key (meaning, it could in theory
be done, but would require more processing power than anyone has available).
The RSA algorithm is based on the idea that, as of right now, there is no
known way to factor large integers into their prime factors. Here, large
means having decimal representations with many hundreds of digits (or binary
representations with many thousands of digits). However, there *is* a way
to tell whether a large number is prime fairly efficiently. In fact, there
are several ways to do this: most implementations use a probabilistic test
called the Rabin-Miller randomized primality test that tells, with extremely
high likelihood, whether or not a given number is prime (with the
probability of error being somewhere on order of 1/2^200 - so small that the
computer is much more likely to be broken than the algorithm wrong). There
is also a completely deterministic method, but it's fairly expensive and in
practice most people use Rabin-Miller.
To show how the algorithm works, we need some definitions and theorems from
Algebra to understand the mathematics. I introduce these here, but don't
give much in the way of proof (in most cases, the proofs are not
particularly hard anyway); for those are interested in proofs of the
underlying mathematics, I recommend getting a good book on abstract algebra
to understand them. Michael Artin's ``Algebra'' is considered standard and
is quite good.
DEFINITION OF THE mod OPERATOR IN THE INTEGERS:
Given an integer a and another integer N, we define the _modulus_ operator,
a (mod N)
to be the remainder of a when divided by N.
That is, for all a and N in the naturals, there exist integers q and r with
r < N such that,
a = q * N + r
and we say that (a (mod N)) = r.
In fact, it can be shown that q and r are unique. Several properties of mod
can also be shown from this definition:
For all a, b, c, N in the integers,
M1: (a (mod N))(b (mod N)) = (ab) (mod N)
M2: ((a (mod N)^b) (mod N) = a^b (mod N)
M3: (a^b (mod N))^c (mod N) = (a^b)^c (mod N) = a^(bc) (mod N)
Note also that, if no confusion will arise, I will drop the parenthesis from
around (mod N).
GROUP DEFINITIONS:
A _group_ (G, *) is a set G, together with some binary operation * on G that
set such that the following axioms hold:
G0: * is closed on G.
That is, for all x, y in G, x * y and y * x are in G.
G1: * is associative on G.
That is, for all x, y, z in G, x * (y * z) = (x * y) * z
G2: Existence of an identity.
There exists an element e in G such that, for all x in G,
e * x = x * e = e. Note that this implies that e * e = e.
It can be shown that e is unique for any given group, and
we call e the _identity_ or _identity_element_ of G.
G3: Existence of inverses.
For every element x of G, there exists an element x^{-1} such
that x*x^{-1} = x^{-1}*x = e.
Suppose that (G, *) is a group, and that G is a finite set, then we call
(G, *) a _finite_group_.
Note that I didn't say that * need be commutative on G (that is, for
x, y in G x * y = y * x). In general, this is not true of groups. But,
if * _is_ commutative, then we say that the group is commutative and
call it an Abelian group.
If no ambiguity will arise, we often just write G to mean (G, *).
If G and G' are two groups, and there exists a function f: G -> G' such
that, for all x, y in G, f(x * y) = f(x) *' f(y), then we say that f is a
_homomorphism_ and that G and G' are _homomorphic_.
If G and G' are homomorphic groups and f is a bijective homomorphism between
then, then we call f an _isomorphism_ (or _group_isomorphism_) and say that
G and G' are _isomorphic_.
EULER'S TOTIENT FUNCTION PHI:
(It's a shame you can't type greek letters on grex.... Oh well.)
For a positive integer N, Euler defined the totient function (phi(N)) to be
the number of positive integers less than or equal and relatively prime to
N. That is,
phi(N) = #{ k an integer : 0 < k < N and gcd(N, k) = 1 }
It can be shown that the numbers {1, ..., phi(N)} taken with multiplication
mod phi(N) form a group. We say that this group is isomorphic to the group
((Z/NZ)*, *), but I'm not going to get into what that means. Again,
interested parties should see Artin; just recognize the notation.
STATEMENT OF FERMAT'S LITTLE THEOREM AND GENERALIZATION TO A GROUP:
(Not to be confused with his last theorem!)
Fermat's little theorem says that, given a prime number p and any integer a,
a^{p - 1} = 1 (mod p) => a^p = a (mod p). This generalizes for any integer
n, and we get: a^phi(n) = 1 (mod n) => a^{phi(n) + 1} = a (mod n).
For a proof, once again, see Artin or a similar reference.
We can generalize this theorem to apply to a group by noting that, for any
element a in a group (Z/NZ)* with order phi(N) for some positive integer N,
a^{phi(N)} = e. That is, a * a * ... * a for phi(N) factors is the
identity.
For more details, again, see Artin or another reference.
THE EXTENDED EUCLIDIAN ALGORITHM AND FINDING INVERSES IN A FINITE GROUP
OF INTEGERS:
We know that G = (Z/NZ)* for some positive integer N is a finite group under
multiplication mod N. Further, this group is isomorphic to the group, ({1,
..., phi(N)}, * (mod phi(N))}. Then, for every x in G, x also has an
inverse in G. The question is, how do we find it? That is, we want a
number y such that,
xy = 1 (mod N)
But recall that this means,
xy - q*N = 1
Several thousand years ago, Euclid gave his famous algorithm for finding the
greatest common divisor of two integers a and b: it was later extended to
finding integers c and d such that:
ac + bd = gcd(a, b)
This is the so called "Extended Euclidean Algorithm." Here is a version in
Python:
def euclid(a, b):
if (a % b) == 0:
return [0, 1]
else:
[x, y] = euclid(b, a % b)
return [y, x - y*(a / b)]
I'm not going to go into more details about this since it's really beyond
the scope of what I want to cover. For more information, see Fraliegh's
book, ``A First Course in Abstract Algebra.'' It's a bit lighter than
Artin, but has some good information and covers the extended Euclidean
algorithm rather nicely.
To find inverses in the group G, realize that every element in G will be
relatively prime to N by definition, including our element x. So let a = x,
c = y, and b = N, d = -q. Then we have:
1 = gcd(a, b) = ac + bd
And by applying euclid() we can recover -q = d and c = y, the inverse of x.
We are now ready to proceed to the RSA algorithm itself.
GENERATING KEYS:
I'm just going to jump straight into the algorithms for generating keys
and doing encryption and decryption. This just builds on the machinery
that I've collected (if not properly assembled) above.
1) Randomly pick two prime integers p and q; make sure they are very large,
as described in the beginning of this post.
2) Compute N = p*q
3) Pick some number e randomly from (Z/NZ)*, which has order (p - 1)(q - 1).
4) By calculating inverses in a group, find the number d such
that f(d) = f(e^{-1}) => f(ed) = 1 (mod phi(N)), where f
is an isomorphism from (Z/NZ)* to Z/phi(N)Z.
That is, e and d are inverses when considered in the group Z/phi(N)Z
which is isomorphic to (Z/NZ)*.
5) The tuple (d, N) is the (private) decryption key. Keep it safe.
6) The tuple (e, N) is the (public) encryption key. Publish it widely.
ENCRYPTION AND DECRYPTION ALGORITHMS:
Consider a message M. We can think of M as some number (even if
it's really ASCII text or whatever). We require that gcd(M, N) = 1
and that O < M < N. Then, we encrypt M as follows:
C = M^e mod N
That's it. Given an encrypted message C', we decrypt C' as follows:
M' = (C')^d mod N
Suppose that C' = C as above. Then, we can see that M' = M as follows:
M' = (C')^d mod N
= C^d mod N
= (M^e mod N)^d mod N
= M^(ed) mod N
But, recall that ed = 1 (mod phi(N)) => ed = q*phi(N) + 1. Therefore,
M' = M^(q*phi(N) + 1) mod N
= (M^(q*phi(N)) * M) mod N
= ((M^phi(N))^q * M) mod N
= ((M^phi(N) mod N)^q * M) mod N
But M^phi(N) (mod N) = 1, by Fermat's little theorem. Then,
M' = (1^q * M) mod N
= 1 * M mod N
= M mod N
But, 0 < M < N, so
M' = M
As desired.
But what about the constraints we imposed on the message? They seem
unreasonable. Well, they can all be worked around.
Any message we wish to send will be > 0. Messages, by their very nature,
are unsigned when considered as numbers. So, that's not a problem. Suppose
that M > N. Then, we can simply split M up smaller messages M_1, M_2, ...,
M_n such that 0 < M_i < N for i in {1, ..., n}. But, probably a better way
to do it is to generate some random number k that can be used as a secret
key for a symmetric encryption algorithm (e.g., blowfish, AES, etc). Then,
we encrypt the message M using k, and encrypt the key k using RSA,
concatenate the two, and send them to the recipient. The recipient then
splits them apart, decrypts the symmetric key using RSA, and uses that to
decrypt the message itself.
Now, what if gcd(M, N) != 1? Then either M = N, M = p, M = q, or M = 0. If
M = 0; just set it to some constant and encrypt it. Otherwise, we can pad M
in some constant way to make it different than one of the aforementioned
numbers, and then we proceed as before.
....And that's basically how RSA works (provided I didn't make any stupid
mistakes in typing all this out!).
|