ENCODING - COMPUTATIONS AND COMPUTERS - The Remarkable Role of Evolution in the Making of Mathematics - Mathematics and the Real World

Mathematics and the Real World: The Remarkable Role of Evolution in the Making of Mathematics (2014)

CHAPTER VII. COMPUTATIONS AND COMPUTERS

55. ENCODING

Encoding information, or cryptology, has always fascinated mankind. We have mentioned the German code, Enigma, used in World War II; it was broken with the use of electromechanical calculators. The mathematics of computation enables practical methods of encrypting to be used, which as far as we know today, cannot be decrypted even by the fastest computers. We will present the basic idea, which is known as a one-way function.

Take for example the multiplication and factorization of two prime numbers. When given two prime numbers p and q, finding the product, pq = n is a very simple task, even if the numbers are big, and certainly for a computer. If we are given only the product, that is, n, to find p and q is today an impractical task, even for the fastest computers. An exponential algorithm can be found to solve the problem, but it is not known whether a polynomial algorithm exists. Such a relation, which can be calculated easily in one direction but is difficult to calculate in the reverse direction, is called a one-way function. Thus, in the framework of the state of mathematical knowledge today, the relation of the product of two prime numbers to the factorizing of the product is a one-way function. If you find a polynomial algorithm for the factorizing of this product, the function will no longer be called one-way and, moreover, your discovery will have far-reaching implications. Some other one-way functions, not many it must be said, have been put forward in the professional literature. The product of prime numbers and factorizing the result is a function that has found its way into day-to-day use.

The idea of using a one-way function for encoding was presented by three American scientists. Two of them, Martin Hellman and his colleague Whitfield Diffie, published the idea of encryption using the so-called public-key cryptology in 1976, following a paper written by the third, Ralph Merkel, on a similar topic. The three are generally acknowledged as being the pioneers of the method. The idea was translated into a practical system by three scientists then at MIT, Ron Rivest, who is still there, Adi Shamir of the Weizmann Institute, and Leonard Adelman, currently at the University of Southern California. The three were joint recipients of the Turing Award in 2002; and their initials, RSA, provide the name by which the system—currently the most widely used encryption system—is known today. The method is based on the fact that the product of two prime numbers is a one-way function. Moreover, not even an efficient probabilistic algorithm is known today for finding the prime factors of a given number. If tomorrow you find an efficient algorithm for doing that, you will have neutralized the primary instrument for encoding currently in use. The mathematics underlying the use of a one-way function is as follows.

I want to convince you that I know the result of tomorrow's drawing in the national lottery without actually telling you what the winning numbers are. I choose two large prime numbers and insert the results of the next day's draw into the lower of the two numbers; for example, I identify the six winners in the drawing at the beginning of the lower prime number. I multiply the two prime numbers, show you the product, and tell you how the winning numbers appear in the lower prime factor without showing you the number itself. If you manage to factorize the product, you will know the numbers that I encoded. Multiplying the two numbers is a simple matter, as we have said. In contrast, to factorize the product is extremely difficult. Even if you were to work all night and all the next day, using the fastest computers, you would be unable to factorize the product and discover the winning numbers of the draw. After the draw and the announcement of the winning numbers, I reveal to you the factorization and the winning numbers written there. I cannot cheat. The product is known to you, and it is easy to check that that number is in fact the product of the two prime numbers.

The method can be used to send encrypted messages. I provide you beforehand a large prime number. When I want to send you a message, I embed it in a new prime number and send to you the product of it with the prime number you already have. You can decipher the message very easily. The product of the two numbers can be safely delivered over the telephone or via e-mail, and there is no concern that anyone who might intercept the e-mail message or eavesdrop on the phone call would be able to understand the message. Even if the method is widely publicized (this is the source of the term public key), no one but you will manage to decipher the code, that is, to calculate the prime factors of the number. This example illustrates the mathematical basis of the system. Its practical application requires several adjustments, which we have not described here, particularly if we wish to send encoded messages to many customers and to enable each one to open the message. The underlying idea of the system in this case is to give each customer one of the prime numbers and to send him the product of the encoded number and the prime number he knows. It is a simple matter to divide the product by the prime number he has been given, which enables him to decipher the message easily, while the message remains coded and inaccessible to anyone who does not have one of the prime numbers.