Decomposition of key numbers against certain codes
2011/11/01 Alberdi Celaya, Elisabete - Matematikan lizentziatua eta doktoregaia Iturria: Elhuyar aldizkaria
If you've ever accessed a "secure" website--because you've bought an airplane trip over the Internet, you've agreed to see the latest account operations right now, communication has been done through a secure platform, called SSL, which is within an https (secure) protocol. In these cases you have been able to check that a lock appears in the taskbar of the browser. It indicates that to access this page you need key or key, that no one who has no key cannot access. That is, communication is safe to the extent that the recipient is the only one that decodes the message. So when you buy a ticket in Iberia, Iberia encrypts or encodes your visa number. The encrypted message travels over the network and upon reaching Iberia decrypt or decode the encrypted message. Communication is secure to the extent that the only one who knows how to decrypt the message is the recipient.
Cryptography is a technician who uses different methods to protect a message. Although initially he was in the field of mathematics, at present he has also extended computer science and telematics. However, the use of cryptography techniques is very old. Early civilizations developed techniques for sending messages in military campaigns. Although the messenger fell into the hands of the enemy, they did not get the enemy to appropriate the message, since they sent the message encrypted with cryptography techniques. The recipient of the message upon receipt deciphered the encoded message with the reverse operation. In the fifth century BC, the tool used to encrypt messages was the so-called “Scytal”. On a stick a leather ribbon is wrapped in which the message was written. Once the ribbon was removed from the baton, the letters of the message were mixed and only the baton with the same diameter of the scandal could decipher the message. In those times, these poles were the force of the peoples, and since then comes the stick that today is given to the mayors of the peoples.
Classic encryption methods
Message encryption methods are divided into two large blocks: classic and modern. Some of the classical methods are based on substitution. These methods replace each letter of the message with another letter or number. An example of such methods a. C. It is the cipher used by Julius Caesar in the first century, in which each letter was replaced by a letter that in the alphabet is three spaces more to the right than it. Thus, the letter A was replaced by D, the letter B by E, etc. Whoever received a message encoded with Caesar's technique, substituting each letter for which he was alphabetically 3 spaces further to the left, obtained the initial message. This method was not safe at all.
Caesar's cipher can be generalized by replacing each letter with a letter b space more right than it. In a twenty-seven letter alphabet there are 26 ways to replace one letter with another. By testing the twenty-six ways you get the message. Therefore, this generalized method is also very weak. In addition, testing with all the ways to replace a letter when using this method is not the only way to clarify the encoded message. You can also clarify the encoded message by knowing the language in which the message is written and the frequency of the letters in that language. To do this, simply replace the letter that appears the most in the encoded message with the most frequent in that language, and the distance between both letters is the one that tells us the position in which we must move each letter. Once the value of b is known, moving each encrypted message letter to the left of space b, we will get the full message. It is evident that this method is not safe.
More sophisticated encryption is related encryption; Ki = a . With the operation Mi + b (mod27) you can encode each letter Mi of the message. This result is obtained by assigning a number to each letter and substituting the number corresponding to the letter for this formula. Then a . The value Mi + b is divided by 27, the resulting residue being the value of Ki. To finish, enter the letter corresponding to this number. For example, H corresponds to number 7 and to a = 5, b = 7, Ki = 5 . Gives 7 + 7 = 42 = 15 (mod27). The letter O corresponds to number 15. This means that, using this encryption, the letter H becomes O. Although this method seems more complex than the previous one, when the encoded message is long, using the frequencies of the letters of a language, it is easy to detect the message.
Modern encryption methods
Modern encryption methods can use private key or public key. Private key users can be block or flow. Block ciphers apply the algorithm several times in a dataset using the same key. Examples of block encryption are DES (Data Encryption Standard) and AES (Advanced Encryption Standard). In both methods, the algorithm is known and the key, unknown (private). In those of flow, each character is encrypted by a long random key in which it is also unknown.
But modernity has also not freed these methods from the fingers of insecurity. The main disadvantage of the DES encoder is the small size of the key (56 bits). This means that there are 256 = 72.057.594.037.927.936 options to choose the key, and in the world of computers that number is small. An example of this is that in an DES challenge organized in January 1998 the key was broken in 56 hours, since computers that evaluated 90,000 keys per second were used. Because it has a longer key, 112 bits, it currently uses more than triple DES, since it offers 2112 options for the key. The key to the AES method is also longer: 128, 129 and 256 bits. The disadvantage of flow is that individual character encryption makes the relationship between the characters of the encoded message weak.
Among the methods that use the public key is known as RSA (Rivest, Shamir, Adleman). It is a method so far safe, but how can you get certainty with a key known to everyone? The key is in the difficult decryption operation.
Decomposition of numbers
Human beings began to break down numbers as a child. One of the concepts we learn first is the number one: The number a is the first, only if it can be divided by ±a and ±1. Thus, numbers 2, 3, 5, 7... are the first. When we want to break down a number, we begin to divide by prime numbers smaller than him. For example, number 15 is broken down as the product of prime numbers 3 and 5. When a number is not divided by prime numbers smaller than that, it is said to be the first. Therefore, we are adding to the list of prime numbers that we have indicated above the ratio of the following first numbers: 11, 13, 17, 19, 23,...131, 137,... Or: 244497-1, 213466917-1,... Yes, there are no smaller numbers that can divide them.
Although small numbers give work, we can say quite easily whether they are the first or not. But what can we say about the number 94550!-1? Is it the first? In mathematics there are several tools to say whether a number is the first or not. And if a number is not the first, how does it break down?
Although there are effective algorithms to break down certain numbers, the decomposition of any number remains a mathematical mystery and the RSA system takes advantage of this mystery to build its coding. Using the RSA, the message recipient makes two numbers public: e and n The first number, e, is the one that the sender will use to encode the message. That is, if x is a message, the sender will perform the following operation: x - e ; and that will be the encoded message that will go through the network. The recipient, in order to decipher the encoded message received, will use the number e ', which will calculate by recognizing the number n and which meets ( x - e) e' = x -. In this way, the recipient will retrieve the initial message. In the RSA system, the number n is chosen as the product of two prime numbers, and the mystery surrounding the decomposition of numbers makes the number n practically inseparable. Consequently, the number e ' necessary for the operation to be performed to clarify the message can be obtained by those who know almost exclusively to break down n, that is, by those who created the number.
Conclusions
As in their day the methods of replacement were left behind, as computer speeds increased, cryptography techniques using short keys have been lagging behind and will go as the current long key can be short tomorrow. Although the RSA system does not have such disadvantages, it depends on the decomposition of the numbers; if an effective number decomposition algorithm was found, it would be the end of the RSA system that we have so far had as insurance. If this happens, we would need a new coding system. Who will give the effective algorithm for decomposing numbers? And who will create a secure encryption system that cannot master the speed of computers?
Bibliography
