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