| Here is how it works. You compute two very large primes p
and q. Let N = pq. Pick a random positive integer d less
than N. Compute a value e such that ed = 1 mod (p-1)(q-1).
You keep p, q, and d secret, and make N and e public. You
have to exercise some caution in how the numbers are
selected in order to get the most security.
If I want to send you a secret message, I codify it as a
sequence of big integers in the range 0, 1, ..., N-1. I
encrypt the number a by computing
e
b = a (mod N) ! N and e are public
where b is in the range 0, 1, ..., N-1. I send b to you.
Now, given b you decrypt it by computing
d
c = b (mod N) ! d is secret
where c is in the range 0, 1, ..., N-1.
That is all you have to do to decrypt it because c = a.
So you read the message, but anyone who has b must try to
find a number with the same property as the secret number d.
All of the known ways to do this I think are equivalent in
effort to factoring N into p and q. (It is easy to find a
value for d once you know both p and q).
Now, this method is "commutative". The value c is (read
everything on the next line as having a "(mod N)")
e d ed de d e
( a ) = a = a = ( a ) all (mod N)
So if you take a meaningful message a and "decrypt" it into
a random number by raising it to the d power [d is known
only to you], then anyone can get back the original a by
"encrypting" with the public value of e. So you can use
this method in reverse to "sign" something in a way that
only you, knowing the secret d, can create; but which anyone
can verify as being yours [because e is public].
It also works with two sets: Your (N,e) and my (N',e'). To
send you a message a I would "decrypt" it with my private
d'. Then I encrypt that with your public e and send it to
you. Only you can undo the latter transformation, by using
your private d; so the message can't be read even if it is
intercepted by someone else. After you undo the latter
transformation with your private d, you can then undo the
first one with my public e'. This assures you that the
message was really from me -- no one know my secret d'.
This prevents someone else from sending you a safe message
using only your public e but claiming to be me; only a
message protected by the d' transformation is guaranteed to
be mine.
Knowing this method is not enough; you have to choose your
protocol very carefully. For example, the bad guys can
intercept my phone call to directory assistance and give me
a their (N'',e'') instead of your (N,e). Then they will be
able to read my message, having both "keys" [my public e'
and their private d'']. Or they can give you bad values
instead of my (N',e'). So our communications with the
"public key server" must also be done in a secure way. Etc.
Dan
de
[a proof of a = a (mod N) isn't that difficult, I'll add
one later]
|
| re .-1
>> How do you get the two huge primes p,q to start with?
This is described in Knuth's series of books I believe
called The Art of Computer Programming. Vol. 2 has the
numerical stuff.
Briefly, there are probabilistic primality checking
algorithms that are reasonably efficient. So you generate a
very long random odd number, and test it and the following
odd numbers for primality until you find one that is
probably prime. Call that p'. Now look at numbers of the
form kp'+1 until finding a prime among them. This is the p
that you use; since p-1 has the huge prime factor p' this
has ruled out certain factoring methods that work if p-1 has
all (or all but one) small prime factors. I think Knuth
suggested 80 digits for p' for a 120 digit p. Don't quote
me on that.
>> How many primes are there in the range [0 : 10e40]?
The notation pi(x) [using a real pi, not spelling it out] is
used for the number of primes <= x. It turns out that as
x "approaches infinity" the ratio of pi(x) and (x / ln x)
approached one.
I think ln 10 is about 2.3, so ln 10e40 is about 40 * 2.3 or
92. So I would estimate about 10e38 primes in that range.
By the way, 10e40 is way too small a limit for secure use of
this method (called the RSA method).
>> Would it be possible to develop a complete list of primes in the
range of interest and use this to factor keys fast? It must be
difficult or people wouldn't have put so much faith in the scheme.
No. Well, wait. An electron weighs about 10e-30 kg., so if
you could store one prime per electron then 10e38 of them would
only weigh 10^8 kg (about 100,000 tons). If you want to
generate them each time instead of storing them, there are
about 10e7.5 seconds per year, so if you generated one every
10e-12 seconds, thats 10e19.5 per year, so it will only take
10e18.5 years to do so. :-) On the other hand, see the
recent note on factoring a 100 digit number. Factoring is
not necessarily a hopeless task, but listing all of the
primes is.
Dan
|
| re .3
>> de
>> [a proof of a = a (mod N) isn't that difficult, I'll add
>> one later]
... given that N is the product of large odd primes p and q,
and that de = 1 mod (p-1)(q-1).
Consider what a^(de) is mod p; a similar analysis holds for
mod q. Since de = 1 mod (p-1)(q-1), there is an integer k
such that de = 1 + k(p-1)(q-1). So
de 1 + k(p-1)(q-1) ( (p-1))k(q-1)
a = a = a * (a )
de
Now if a is divisible by p, i.e. if a = 0 mod p, then a is
also 0 mod p, and so a^(de) = a mod p. But if a is nonzero
mod p, then by Fermat's Little Theorem, a^(p-1) = 1 mod p.
So the above reduces to
de k(q-1)
a = a * 1 mod p = a mod p.
de de
So either way, a = a mod p. Likewise, a = a mod q.
de
Now, a is number in the range 0, 1, 2, ..., N-1. a is a
huge number, but we don't compute a^(de) directly, we
compute its remainder modulo N. Call this remainder r. So
r is a number in the range 0, 1, 2, ..., N-1, such that
r = a mod p, and r = a mod q.
Now by the Chinses Remainder Theorem, the pair of
simultaneous equations
x = b mod p b = 0, 1, 2, ..., p-1
x = c mod q c = 0, 1, 2, ..., q-1
has exactly one solution x in the range 0, 1, 2, ..., pq-1 = N-1.
As b takes on its p possible values and c takes on its q
possible values, the unique solution x ranges over the pq = N
possible answers.
Now, here the number a is not necessarily in 0, 1, ... p-1
or in 0, 1, ..., q-1. Suppose the remainder of a mod p, in
the range 0, 1, ..., p-1, is a'. Likewise, let the
remainder of a mod q, in the range 0, 1, ..., q-1, be a''.
Then we have
a = a' mod p a' in 0, 1, ..., p-1
a = a'' mod q a'' in 0, 1, ..., q-1
and a is in 0, 1, ..., pq-1 = N-1. And a is the *unique*
value in 0, 1, ..., N-1 with this property. But also
r = a = a' mod p a' in 0, 1, ..., p-1
r = a = a'' mod q a'' in 0, 1, ..., q-1
and r is in 0, 1, ..., pq-1 = N-1.
de
So r and a must be equal. But r is a reduced mod N, and
that means a^(de) reduced mod N is a.
d e
That's why the operations a -> a mod N and a -> a mod N
are inverse operations.
Dan
|