The prime numbers will be recognized, the cipher will be broken

An algorithm that makes it possible to determine with certainty whether a number is prime may deplete one of the leading encryption methods in the world, which is very common on the Internet

by Uriel Brizon

Three Indian computer scientists claim to have developed a new method that makes it possible to determine whether a number is prime or not. The uniqueness of the method is that it can be used to test even very large numbers, and if it does work, as leading mathematicians who tested it believe, it could be used as an effective means of breaking digital ciphers.

The three scientists - Manindra Agrawal, Neeraj Kayal and Nitin Saxena from the Indian Institute of Technology in the city of Kanpur - claimed to have found an algorithm that makes it possible to determine, quickly and with absolute certainty, whether a certain number is prime. Prime numbers are of enormous importance when it comes to encrypting digital messages, and most of the encryption mechanisms used by secret services, large organizations and other entities that need confidentiality are based on them. To crack the encryption you have to find large prime numbers. The methods that exist today for determining the primes of numbers are too slow or uncertain. With these methods, the most powerful computers are required to work for months or even years to check primality, which makes the whole thing not worthwhile. On the other hand, the price of shortening the time is inconclusive results - an equally problematic solution.

Prime numbers are numbers that are not divisible by any number except themselves and one. The small initial numbers (23, 19, 17, 13, 11, 7, 5, 3..., 2, 1) are the beginning of a very complex list. The study of the distribution of the prime numbers on the number line occupied mathematicians in ancient Greece, and it continues to occupy mathematicians even today. To determine if a number is prime, make sure that it has no factors other than one and itself. This operation is simple with small numbers, but the larger the number being tested, the more difficult the task becomes, to the point that even supercomputers cannot perform it. For example: Microsoft's popular browser "Explorer" comes today equipped with 128-bit encryption. Cracking this encryption requires checking the primality of numbers of the order of 39 digits. Even the most powerful computer will need a long time to check if such a number is divisible by another number without a remainder.

The importance and prevalence of ciphers increased greatly with the development of the Internet. The convenience of using the network and the accessibility it allows were a strong incentive for organizations and many factors to use it to transport information - including sensitive and classified information. Various types of encryption methods, which until now were mainly used by armies and secret services, have become a highly demanded commodity, and the community of computer scientists and computer engineers is required to respond to the complex need to transmit sensitive information on a public and open information network such as the Internet. The effort gives rise to innovative methods and great development.
Let's say I want to send an encrypted message over the Internet to my brother in New York. Many classic encryption methods allow me to confuse the message (which is written in Hebrew) so that if it falls into the wrong hands it will not be understandable - it will resemble an unreadable sequence of letters and signs. When scrambling, or encrypting, I will use a password. To decode the message it will be necessary to pass it again through the encryption mechanism, while performing the opposite operation, decoding, and using the encryption password. But there is a serious problem here. My brother, the recipient of the message, is not a secret agent, so he did not bother to coordinate with me an agreed upon password for the transmission of secret messages ahead of time. I can send him the password I used, but once this is done on a communication channel, an outsider can eavesdrop on the unencrypted message and thus obtain the password and render all our efforts futile. It turns out, in fact, that in order to send an encrypted message, essential information must first be transmitted in an encrypted message.

This problem was solved a long time ago, and through the solution it is possible to demonstrate the importance of prime numbers to cryptography. In 1977, three scientists - Adi Shamir, professor of computer science from the Weizmann Institute, Ronald Rivest and Leonard Edelman - developed a method for encrypting messages without prior coordination. The method is based on an idea known as "public key - private key". According to this method, an encryption mechanism is built that has two passwords - one for encryption only and one for decryption only; A message encrypted by the first password can only be decrypted using the second password. The first password can be sent openly to any person from whom we would like to receive secret messages. That person will use it to encrypt the message and send it back to us. There is no danger in revealing the first password (the public key) since it only encrypts and does not decrypt anything. Only the second password (the private key), which we will keep confidential, will allow us to decrypt messages encrypted by its public counterpart.

The idea can be illustrated as follows: in order to receive a secret letter from a certain person, I will first send him a spring lock, the type that locks with a click. I will leave the key with me. That person will get the lock open and use it to lock the secret letter he wants to send me. He will place the letter in the box and lock it with the lock, by clicking. From the moment it is locked, no one but me (not even the "locker" of the letter) can get to the letter, since only the key is in my hands. If I now want to send a secret letter back, I will ask that person to send me a lock and leave the key with him, in the same way. The sophistication comes from separating the lock from the key - the encryption password from the decryption password. This way you can send secret messages without coordinating passwords.

The method is actually implemented on the Internet, and with great success. Messages are encrypted using the public key and decrypted using the private key. Both types of keys consist of prime numbers. It works something like this: the encryption and decryption software is distributed for free, as part of browsers, e-mail programs or other utilities. These programs generate public and private keys for the user. The public key, which encrypts only, is a very large number obtained by multiplying two prime numbers (the numbers themselves are not known, only their multiplication). The private key, which enables decryption, consists of the two initial numbers themselves. We will keep these two numbers confidential on our computer. The public key can be sent without fear to friends or customers. Whoever receives the public key from us uses it to encrypt messages he sends to us. Only we can decipher these messages because only we hold two initial numbers that were multiplied and created the public encryption key. Whoever does not possess them and tries to crack the message will have to find those prime multiples himself, and for that he will have to scan very large numbers and check if they are prime. And to scan large prime numbers efficiently and reliably requires a method like the one now developed by the scientists from India.

The Indian researchers have yet to publish their findings in an accepted scientific journal. The details have been sent to several scientists in the world for review, and responses are being received these days. One of the prominent researchers in the field of prime numbers is Prof. Shafi Goldwasser from the Weizmann Institute, who told the "New York Times" that "this is the best research result in the last decade." The method, the researchers themselves admit, has a certain limitation: it is slower than other previously developed methods. But at the price of not much additional processing time, the researchers guarantee absolute reliability. In the near future it will become clear if this is indeed a development that undermines the ability to encrypt digital information.

science

With all due respect to the deterministic algorithm in polynomial time, the cipher will not be broken

By Tamir Tesa

The article "The first numbers will be identified, the code will be broken" ("Haaretz", 19.8/XNUMX) reported on the discovery of an algorithm used to check the primacy of numbers. However, the conclusions drawn by the reporter from the very discovery were sensational and unfounded.
Checking the primality of numbers is indeed a classical problem, of both theoretical and practical importance. A simple test is to try to divide the number by all the numbers up to its root. If all attempts at division have failed - we have an initial number. But the "running time" of such an algorithm is unreasonable when it comes to large numbers. In the language of computer science theory, the running time of such an algorithm is "exponential in the length of the input". That is, if we want to check the primality of a number with d decimal digits (d indicates in this case the "length of the input"), the number of division operations we will need to perform will be, approximately, ten to the d/2 power. For example, for the purpose of testing the primacy of

The number 728,639 (for which d=6), the number of operations we will have to perform will be approximately ten to the power of 3(d/2), that is, about a thousand operations. The practical meaning is that the algorithm has become impractical even when dealing with modest numbers. Since in information security implementations we require huge prime numbers (for example, 1,024 bits, which equals about 309 decimal digits), other ways are necessary.

Due to the brevity of the page, we will skip over a 300-year history, which began with Fermat in the 17th century and ended in 1980, when the mathematician Michael Rabin, winner of the Israel Prize and the Turing Prize, published his version of G.L.'s test. Miller from 1976 to test primality. It is a random algorithm of the type known as "Monte Carlo". Such an algorithm conducts a series of experiments on the given number. If one of the trials fails, the algorithm stops and declares the number as freak (non-prime) accompanied by a confident exclamation mark. On the other hand, if all the experiments were successful, the algorithm indicates the number as prime accompanied by the footnote "with a very high probability". For example, if the probability of a freak number successfully passing a single trial is a quarter (25%), the probability that he will succeed in a series of twenty trials drops to a quarter to the power of 20 - an extremely tiny number. The more we increase the number of trials, the less likely we are to mistakenly identify a freak number as prime.

From a practical point of view, the algorithm is simple and easy to implement: it works quickly and efficiently, even on huge numbers as is customary in the encryption business, and it can also be implemented on a home computer. The number of experiments can be adjusted so that we get completely negligible error probabilities, which are thousands of times lower than the probability that a giant meteor will crash into the earth before the reader finishes reading this sentence.

It should be noted that there is also a deterministic algorithm for checking primality, one that is able to decide the question one way or the other with absolute certainty. Its running time is much better than an exponential running time, but it is still not polynomial (it means a running time in which the length of the input, d, appears only in the base of the power, for example d2 or d10, as opposed to the exponential 2d or 10d). Because the Miller-Rabin algorithm is faster and easier than the deterministic algorithm, it is the one used in most applications.

The three mathematicians from the Kanpur Institute of Technology have developed a deterministic algorithm that definitively solves the question of primes/discharges of a given number, and does so in polynomial runtime. This fact is what gives this algorithm its importance, since before it was not clear if the problem of primality could be decided in polynomial time. But this importance is, at least at this stage, only theoretical. It is worth noting in this context that the deepest question in the theory of computer science is related to the characterization of the family of problems that can be solved in polynomial time. This question is probably still far from being resolved.

And now regarding the ciphers: checking the primacy of numbers is essential when setting up information security systems. This statement is valid, for example, in relation to the well-known encryption system, RSA, the Diffie-Hellman method used to exchange keys, or the digital signature protocol .DSA, but the problem of checking the initiality does not and cannot have any implications for breaking such systems. If the ability to check primality had such a devastating consequence, then a concerned article on the subject would have been published as early as 1980 and even earlier.

Any encryption method that belongs to the "public key" family of methods, the nature of which was described in the article, throws Yahava on a mathematical problem that is very difficult to solve. For example, the RSA method is based on the assumption that it is very difficult to decompose a given number into its initial factors if these factors are very large numbers. In this method, the public key includes a number that is a product of two huge prime numbers (one of the accepted sizes for these numbers is 512 bits, which are about 155 decimal digits). When building such a system, the Miller-Rabin algorithm is used to find two such prime numbers.

The problem facing an attacker who wants to break such a cipher, that is to calculate the private key from the public one in order to be able to decipher the encrypted messages, is the problem of decomposing a number into its initial factors. This is a completely different problem from the initialization problem, and as of now it is still considered the most difficult. Algorithms exist for solving it, but they are not effective at all and especially against the large numbers used in practice.

The new algorithm, like the algorithms that preceded it, makes it possible to successfully identify prime numbers. However, those who wish to break the RSA method are not required to just prime numbers, but to two very specific prime numbers. That is, those who seek to decompose a number into its factors are not looking for a prime number; It looks for a divisor of a given number. And this is a completely different opera.

Dr. Tessa is a faculty member in the Department of Applied Mathematics at Tel Aviv University