As in all systems where there are opposed ideologies, there is a kind of cold war in which advances on one side need to be balanced by advances on the other. In encryption, the availability of increased computing power at low cost made it easier to break codes, but it also made it easier to create strong codes.
Fortunately, the math is on the side of right, as the difficulty of cracking a code rises with complexity more rapidly than the difficulty of encoding it. For example adding one extra bit to a key is trivial in the encryption process, but it doubles the number of keys that need to be tried out by an attacker.
All forms of encryption are subject to attack and it is necessary to avoid weaknesses in the overall system. With modern computing power, brute force attacks are possible, where huge numbers of different keys can be tried to see if one works. This approach is simplified if an attacker has some idea of the kind of information that has been encrypted, as it would then be easier to identify when a key has been found.
For example a typical message might not be very large, whereas a secure encryption system might employ a long key and be designed to encrypt blocks of a certain size. If the message were to be zero-stuffed in the traditional way to extend it to the block size, an attacker would be helped because it would only be necessary to look for strings of zeros when trying different keys. The attacker might also look for commonly used words.
Securing an encryption system against such an attack is achieved using a technique called padding. Fig.1 shows how the padding system forms an extra layer outside the encryption system. The message to be encrypted is not simply zero-stuffed to bring it to standard size as is done in a Transport Stream packet or a hard disk block. Instead the message and its stuffing is randomized so that strings of zeros are broken up and so that the plain text cannot be recognized.
Obviously if a fixed or standardized randomization were used, as is done in the Serial Digital Interface (SDI) or DVB, the attacker would be aware of it. Instead the padding is done using a random number that is different for every block. The random number is attached to the block before encryption. The genuine recipient de-crypts the message, locates the random padding parameter and de-randomizes the block to recover the plain text.
Fig.1 - In padding, the plain text message is randomized and the randomization key is added to the block. With a randomized message it is hard for an attacker to tell if it has been decrypted.
Enclosing the randomizing pattern with the message might seem to be a weakness, but it is not. Both an incorrect key and the correct key result in apparently random data. This makes a brute force attack less effective because the effect of the randomizing is to make it impossible to tell if or when a correct key has been used.
The traditional form of encryption is shown in Fig.2. A key is created and the sender adds the key to the message so the message becomes scrambled. The message can only be recovered by adding the key once more. As the same key is used for encoding and decoding, the system is described as symmetrical. Such systems are reasonably secure, but have various vulnerabilities. The system cannot work unless sender and recipient both have the key. The key can only be generated by one of the parties, and so by definition it will have to be sent to the other party, and the transmission of the key risks interception. Once the key is known to a third party, the encryption and any padding is a waste of time.
The secure sharing of a key can be achieved if the two parties physically meet so that no one else can know what was shared. For example a naval vessel in its base can securely be provided with keys in a physical manner that can subsequently be used to decrypt or encrypt messages broadcast by radio when the vessel is far away. It would not be unusual to have a large set of keys, so a different one could be used each day.
Fig.2 - In symmetrical encryption, the same key is used for encryption and decryption. The recipient must be sent the key and it could be intercepted.
However, in many cases it is simply not practical for keys to be shared in such a secure way and that difficulty led to the development of more complex encryption schemes. Instead of having to keep the key secret, the party creating the key keeps secret a set of numbers, which never need to be revealed and should not be revealed to anyone.
From those numbers, two keys can be created by one-way functions, meaning that the secret numbers cannot be established from either of the keys. Fig.3 shows what the two keys do. The two keys are best understood as being mathematical mirrors of one another. In the RSA system, the keys incorporate power functions, somewhat like in television where video signals are raised to one power function in a gamma corrector and then linearized with a reciprocal power function.
In RSA coding, the mirroring is not done in any trivial sense, meaning that the decryption key cannot be determined from the encryption key. The relationship between the encoding key and the decoding key is known only to the recipient. The sender uses one key to encrypt the message and the recipient uses the other key to decrypt.
The crucial difference between traditional encryption and the later type is that the system is asymmetrical. The message cannot be de-crypted with the key that was used to encrypt it. That means it is not necessary to keep the encoding key secret. It doesn't matter who has access to the encoding key, legitimately or otherwise, as it can only be used for encoding.
Fig.3 - In asymmetrical encryption, the key is in two halves. Only the recipient knows both halves. The public key is needed to encrypt, but decryption requires the private key.
Typically the recipient holds the secret numbers and generates the pair of keys. As the encrypting key cannot be used to decode and the decryption key cannot be established from it, the recipient can provide the encryption key to anyone who wishes to send a secure message to the recipient. That key is therefore known as a public key.
Two of the secret numbers are both required to be prime and they are generally called p and q. One of the parameters in the keys, known as the modulus, generally called n, is the product of the two primes, such that n = pq. The security of the system depends on the infeasibility of establishing what pair of prime numbers multiplied together to form the modulus.
The word "modulus" is used in the mathematical sense in the encryption process. The plain text, or more likely, the padded message, is converted into a numerically huge binary number simply by running all of the bytes together serially. After being raised to the power specified in the public key, the result, which is an even bigger binary number, is expressed in modulo fashion, meaning that the modulus is subtracted from the result an integer number of times until the remainder is less than the modulus. The remainder is the encrypted output.
The creation of the modulus is a one-way function. The calculation itself is simple, but there is no easy way back from the product. One-way functions have been known to mathematics for a long time, but now instead of being mathematical curiosities they form an important building block in data integrity systems.
Fig.4 - In modulo arithmetic the infinite range of real numbers is wrapped endlessly around a finite field. The modulo number shown here could have come from real numbers A, B or C etc. The real number cannot be established from the modulo number.
There is no known way of calculating the primes. The only way they may be found is by trial and error. This is doubly difficult because the two primes are very large and are selected each to have a slightly different word length. Those two word lengths are not revealed by knowledge of the modulus. A further difficulty is that there is no easy way to establish if a number is prime other than attempting to divide it by all integers up to the square root of the number.
A determined hacker might prepare tables of prime numbers in advance, but that itself is a non-trivial undertaking.
The use of modulo arithmetic is also a one-way process. A number expressed is a finite field, which forms a ring as shown in Fig.4. Real numbers wrap around the ring so that many real numbers map to the same modulo value. Put another way, it is not possible to tell from the remainder how many times the modulus was subtracted from the result of the power calculation.
It follows from information theory that the size of the message block cannot exceed the modulus, as otherwise there could be more than one message that resulted in the same modulus. That is not a serious limitation as large plain text messages can be broken up into convenient blocks for encryption.
The RSA encryption technique is strong, but relatively slow in operation. One good application is to use the RSA algorithm securely to share the key to a symmetrical algorithm. If the key cannot be intercepted, the symmetrical encryption becomes more secure, especially if the key is changed frequently.
You might also like...
To see how to make computers secure, we have to go way back to see how they work.
Computer security is always a hot topic, but what do we mean by security and why do systems seem to be ever vulnerable. Comparing hardware to software helps understand vulnerabilities in software security.
Once upon a time, the cause of data corruption would be accidental. A dropout on a tape or interference picked up on a cable would damage a few bits. Error correction was designed to deal with that.
The arrival of 5G brings both opportunities and challenges to communications, media and entertainment companies, as well as the original equipment manufacturers (OEMs) working to support them.
The requirements for data transmission have changed out of all recognition since the early days of computing where the goal was simply to make something that worked. Today that’s the easy part.