When you were little, you may have tried encrypting messages in order to communicate in the classroom or on the playground with an acquainted neighbor without third parties, such as your teacher, being able to read them – even if the messages were intercepted in transit.
Sending encrypted messages via an insecure transport channel that can be viewed by any opponent has a long tradition. Even the ancient Greeks and Romans used various such methods to ensure the confidentiality of their messages. The so-called Caesar cipher, for example, is based on rotating the alphabet by a certain number of letters. A much more sophisticated variant of this principle (almost any permutation of the alphabet instead of a simple rotation) was used around two millennia later by the German Wehrmacht during the Second World War: Enigma. In the digital age, the Data Encryption Standard (DES) or asymmetric public key procedures are common methods.
What all these methods have in common is that a message (plaintext) and a key are combined to form an encrypted message (ciphertext) using a defined procedure, this is transmitted on an insecure channel (e.g. the Internet) and then decrypted again using a defined procedure and a key to form the plaintext. Before the publication of the RSA cryptosystem in 1977, the same key was used by both the recipient and the sender in all known procedures. The procedures are therefore still called “symmetric” procedures today.
A symmetric cryptosystem can be summarized graphically as follows:
Among other things, cryptography deals systematically with what guarantees such systems provide and under what assumptions. (For example, how easy or difficult is it to guess a key based on a known ciphertext without knowing it? – This is a problem that was a major concern for the Allies with Enigma).
Assumptions and guarantees or not, two major problems could not be solved satisfactorily until fundamental breakthroughs in cryptography in the 1970s:
- The key used had to be transmitted from the sender to the recipient (or vice versa) before it was used for the first time. This had to be designed in such a way that the key could not be intercepted by anyone en route. Otherwise, the encryption used was useless, no matter how strong the actual process was.
- Even worse: the sender and recipient had to be able to assume that the other party would keep the key secret after receiving it, i.e. that they would trust each other. Nowadays, trust, combined with the anonymity of the Internet, is a notoriously difficult issue.
Problem one was solved in 1976 with the Diffie-Hellmann (DH) key exchange method. DH makes it possible for two parties, usually the infamous “Alice” and her friend “Bob”, to negotiate a secret key via an insecure channel using a defined sequence of messages without a third party, who can read every single one of these messages, also knowing Alice and Bob’s key at the end of the exchange.
Problem two was solved a year later, in 1977, with the publication of the RSA cryptosystem. The RSA cryptosystem allows plaintext to be encrypted with a key (usually called a public key ), but does not allow this to be reversed with the same key. A second key (usually called a private key ), which is different from the first, is required to decrypt the ciphertext. The following figure summarizes these processes.
This opens up a whole range of possibilities without which the Internet in its current form would not be what it is (a global hypertext transmission medium bent into a content delivery system – but more on that in another blog post).
A look under the hood of asymmetric processes
In contrast to pre-70 symmetric methods, which essentially permuted the plaintext using the (symmetric) key according to a predefined procedure, asymmetric methods use special properties of the underlying mathematical structures (so-called cyclic groups). To a certain extent, the asymmetry of the methods results from an asymmetry in the properties of the underlying mathematical concepts. More specifically, these are arithmetical operations that are easy to perform but very difficult to reverse. (This fits intuitively with the statement above that encryption is simple, but decryption with the same key is difficult/impossible). Such operations are usually called one-way or trapdoor functions in the context of cryptography.
As an example to illustrate the principle of a one-way function, let’s take the square (multiplication by itself) of a natural number, e.g. 273:
273 * 273 = 74529
This calculation (i.e. the outward direction) is relatively simple, e.g. done by written multiplication. However, the way back seems much more difficult: If you are given the task of calculating the square root of 74529 without a calculator, you will be busy for a moment.
How long you need for this task depends on how skillfully you proceed: For example, you could simply square all the integers starting with 1 in order and check to see if you get 74529. You will get a pretty bad style score for this approach, but on the other hand you will have to think little or not at all about your chosen approach before you can start. It would be a little more clever to only check the odd numbers. (Since 74529 is also odd, it is not possible that you have the square of an even number in front of you). This simple observation would already reduce your effort by about half!
My aim here is not to develop an efficient method for calculating square roots, but to show what effects improvements to the procedure for solving a problem – algorithmic improvements – can have.
Complexity classes and P=NP (or not)
The question of how difficult or easy it is to solve a particular problem using an algorithm is the subject of a branch of theoretical computer science: complexity theory. This involves asymptotic considerations, i.e. investigating what happens when the effort required to find a solution increases with the “size” of the task.
In the example of multiplication above, the “size” of the task would be the number of digits of the input number – three digits in the example. It would therefore be investigated how the necessary computational effort (how many arithmetic operations are required?) behaves if the input numbers do not contain three, but 100, 1000, 10000 digits.
Based on the results of such considerations, problems are divided into “complexity classes”. Problems within a certain class are considered to be “approximately equally difficult” if a procedure from a simpler class exists to “translate” the tasks of the more difficult class back and forth. (If the problems become “big” enough, the translation effort becomes negligible). In the mathematical operations that are used today as trapdoor functions, it is assumed that the handling of the forward and reverse directions belong to different complexity classes (one simple and one difficult). The most important such classes for the purposes of cryptography are the classes “P” (simple) and “NP” (difficult).
The exact meaning of these classes is beyond the scope of this blog post. However, the point here is as follows: According to the current state of knowledge, it is unclear whether an efficient, (currently still unknown) procedure exists with the help of which the “gap” between the two classes can be bridged so that they would ultimately be identical. It is therefore unclear whether the reverse direction, from the trapdoor function, is really so difficult to master, or whether an efficient algorithm does not perhaps exist that could accomplish this. The formal answer to this question is the subject of the famous P=NP problem, one of the so-called millennium problems for whose solution the Clay Mathematics Institute has offered prize money of USD 1 million.
Back to RSA and consorts
The mathematical operations used in asymmetric cryptosystems are more complex and at least as difficult to invert as the square of an integer. For example, the RSA cryptosystem is based on a problem related to our example, namely decomposing the product of two large prime numbers back into these prime numbers without the associated factors being known in advance.
Similarly to how we have previously saved work by cleverly calculating the square root, the algorithms that solve the RSA problem (and similar related problems) are constantly being improved. So could it be that an efficient way to reverse the one-way function used by RSA exists? Yes. Do we know of such a procedure? No. Can we therefore conclude that no such procedure exists? Also no! The security of asymmetric cryptosystems is therefore based on the unproven assumption that the fundamental asymmetry in the time complexity of the outward and return paths of a one-way function actually exists (or that the handling of the outward and return directions belong to different complexity classes).
And now back to practice
Apart from the fundamental theoretical problems mentioned above, in practice there are always cases in which certain configurations or even entire families of cryptographic methods have to be “retired”. For example, because newly developed methods or increasing computing power mean that key lengths previously considered secure no longer offer the necessary security. It also happens that parameters of the cryptographic procedures used are consciously or unconsciously chosen in an insecure manner, or attack methods become known that render a particular procedure useless (for example, the possibility of constructing so-called collisions with the MD5 hash algorithm reduces the usefulness of MD5 for checking the integrity of information to a very modest level). There is therefore a kind of “arms race” in the use of cryptographic procedures, which is often forgotten in the hustle and bustle of everyday life.
The network specialists at United Security Providers will be happy to advise you on the choice of cryptographic parameters and procedures in your infrastructure.