Date: Mon, 22 Jan 1996 14:37:52 CST
From: rusin@math.niu.edu (Dave Rusin)
To: Matt Bernstein
Subject: Re: Prime number encyptions
In article <4dat6t$8dc@power1.powernet.co.uk> you write:
>I know the basic principle behind prime number enryption, ie. the
>product of two primes has only those two factors and that it is much
>much much harder to find those factors from the product than the
>converse, but...
> 2) What encyption process can you do with the product but which
>requires the two factors for decryption?
Well, I didn't see a posted response to this so I'll have a go --
You know factoring is harder than multiplying. The problem is to find a
method of encryption which capitalizes on this fact. Here is one method.
Suppose Alice needs to send a message to Bob, which she needs to keep
secret from Chris. She needs to get from Bob two numbers, which can
be made public (e.g., Bob can freely display them at his Web site).
One number N is, say greater than 2^1024, and the other number e is
usually a little less than N.
Alice takes her long message and changes it in some simple agreed-upon
way (e.g. ASCII) to a long string of bits. She breaks the message
stream into, say, 1024-bit chunks which she views as a sequence of
integers a_i mod N. What she sends to Bob is the encrypted sequence
of integers b_i where b_i = a_i^e mod N.
What Bob has, and has not made public, is another integer f with
the property that for every integer a we have a = a^(e*f) mod N .
Thus all Bob needs to do to decrypt the message is to take the
incoming integers b_i, recover the original integers a_i = b_i^f mod N,
view as 1024-bit strings of bits, then run them together and reconsititute
as text (or whatever) in the originally-agreed-upon way (e.g. ASCII).
Thus Bob has the original message.
Note that both Alice and Bob have very little work to do. Writing
e and f in binary shows that computing a^e and b^f can be done
with about 1024 squarings and multiplies. We only need to keep the
results mod N, which (by the Euclidean algorithm) only takes at worst
another 1024 or so. Of course conversions from binary to text and vice
versa can be done about as fast as the data streams can be transmitted.
How much work would Chris have to do in order to read the message
illegally? Chris is just as able as Alice to find the two integers
N and e at Bob's site; if the integer f were available too, it
would be possible to read the message as quickly as Bob does. So it's
only a question of being able to compute f.
Now, if N were prime, this would be easy: Fermat's "little" theorem
states that for every integer a we have a^p=a mod p, so that also
a^r=a mod p as long as r = 1 mod p-1. Thus the magic property which
f is to have is that e*f = 1 mod p-1. It's very easy to solve this
equation using the Euclidean algorithm. Since f need only be computed
once, this would make the coding scheme above quite insecure.
But suppose N is not prime. Suppose for simplicity N=p*q where
p and q are two distinct primes. We still want a^(e*f)=a mod N for
all integers a. This requires a^(e*f)=a mod p and simultaneously
a^(e*f)=a mod q. As in the preceding paragraph, we need only find f
so that e*f = 1 mod p-1 and also e*f=1 mod q-1. Equivalently, we
only need to have e*f = 1 mod lcm(p-1,q-1). But once again the
Euclidean algorithm may be used, first to compute the lcm of these
two integers, then to find this inverse f of e.
So on the face of it, this method of decryption is just a tad harder with
N composite as with N prime, which is to say, not nearly hard enough
to be an effective deterrent to decryption.
The big difference, though, is that in order to find f, and thus to
decode the message, one must know the factors p and q. It is not
these factors separately, but rather their product N which is publicly
available. Thus, the decryption by Chris is only easy if Chris knows
an efficient way of factoring 1024-bit numbers.
In fact, for numbers N which are known to be a product of two primes,
finding f is roughly _equivalent_ to factoring N: one task is more
or less as hard as the other. Now, it's not _known_ that factoring is
"hard", but despite impressive progress resulting from lots of careful
work, the fact remains that factoring a run-of-the-mill 1024-bit number
is beyond the scope of today's machines unless you're very lucky.
Thus this method of encryption is held to be fairly secure against
attack by most agents. (If Chris works for the NSA, perhaps I would not
be so confident...)
Remember this the next time someone says number theory is useless.
dave