Introduction to cryptography

ArticleCategory:

System Administration

AuthorImage:

Pierre Loidreau

TranslationInfo:[Author and translation history]

original in fr Pierre Loidreau  

fr to en Axelle Apvrille  

AboutTheAuthor

Pierre works as a Teacher-Researcher at the ENSTA (Ecole Nationale Supérieure de Techniques Avancées). His research field concerns "cryptosystems" based on the theory of error correction codes. He "plays" with Linux everyday... and tennis quite often.

Abstract:

This article was first published in a Linux Magazine France special issue focusing on security. The editor, the authors, the translators kindly allowed LinuxFocus to publish every article from this special issue. Accordingly, LinuxFocus will bring them to you as soon as they are translated to English. Thanks to all the people involved in this work. This abstract will be reproduced for each article having the same origin.

ArticleIllustration:

mail

ArticleBody:[The article body]

Why cryptography - 2500 years of history.

The origin of cryptography probably goes back to the very beginning of human existence, as people tried to learn how to communicate. They consequently had to find means to guarantee secrecy as part of their communications. However, the first deliberate use of technical methods to encipher messages may be attributed to the ancient Greeks, around 6 years BC: a stick, named "scytale" was used. The sender would roll a strip of paper around the stick and write his message longitudinally on it. Then, he'd unfold the paper and send it over to the addressee. Decrypting the message without knowledge of the stick's width - acting here as a secret key - was meant to be impossible. Later, Roman armies used Caesar's cipher code to communicate (a three letter alphabet shift).

The next 19 centuries have been devoted to creating more or less clever experimental encipher techniques, whose security actually relied on how much trust user would grant them. During the 19th century, Kerchoffs wrote the principles of modern cryptography. One of those principles stated that security of a cryptographic system did not rely on the cryptographic process itself but on the key that was used.

So, from that point, cryptographic systems were expected to meet those requirements. However, existing systems still lacked mathematical background, and therefore tools to measure or benchmark their resistance to attacks. Even better if somebody could finally reach cryptographic's ultimate goal and find a 100% unconditionally safe system ! In 1948 and 1949, scientific background was added to cryptography with 2 papers of Claude Shannon: "A Mathematical Theory of Communication" and mainly "The Communication Theory of Secrecy Systems". Those articles swept away hopes and prejudices. Shannon proved Vernam's cipher that had been proposed a few years before - and also named One Time Pad -- was the only unconditionally safe system that could ever exist. Unfortunately, that system was unusable in practice... This is the reason why, nowadays, evaluation of security systems is based on computational security instead. One claims a secret key cipher is safe if no known attack's complexity is any better than a full search on all possible keys.

AES (Advanced Encryption Standard)

Recently, in October 2000, the NIST (National Institute of Standards and Technology) announced the approval of a new secret key cipher standard chosen among 15 candidates. This new standard algorithm was meant to replace the old DES algorithm, whose key sizes were becoming too small. Rijndael - a compressed name taken from its inventors Rijmen and Daemen - was chosen to become the future AES.

This encryption system is said to be a "block" cipher as messages are enciphered by entire 128-bit block units. Multiple options exist proposing the use of 128, 192 or 256 bit keys. Just for your information, DES enciphers 64 bit blocks with a key of only 56 bits. Triple DES usually enciphers 64 bit blocks with a 112-bit key.

AES

Table 1: AES iterations

AES operational mode is described at figure 1. First, a secret key K0 is XORed bitwise to the message. Then, similarly to all block ciphers, a function F is iterated, using subkeys generated by a key expansion routine initialized by the master key.

For AES, function F is iterated 10 times.
F function

Table 2: Function F

Now, let's see briefly how substitutions are built, and what constant ai is intended for. Technically - and for simplicity reasons - a byte should be considered as an element of a set of 256 elements, called a finite field, and onto which all sorts of simple operations (such as addition, multiplication and inverse) exist. As a matter
of fact, substitution S mentioned previously is an inverse in such a field. Substitution S is specified as a very simple operation and can consequently be easily implemented. Element ai corresponds to elevation to power i of an element of the field. Such considerations make AES implementations very efficient.

As AES is only built upon simple bytewise operations, this provides it with two major advantages:
Key expansion routine

Table 3: Key expansion routine

Public key cryptography

In 1976, Diffie and Hellman published an article "New Directions in Cryptography" which was a real scoop to the cryptographers community. This article introduces the concept of public key cryptography. Actually, the only family of algorithms known at that time - symmetric secret key algorithms - could no longer satisfy the new needs that had appeared due to the burst in communications methods such as networks.

Basically, the core of their novel idea was to introduce the concept of trapdoor one-way functions. Such functions are easy to operate in one way, but are computationally infeasible to invert without knowing the secret trap - even though the function itself is known by all. Then, the public key acts as the function, whereas the trap (only known by a limited number of users) is called a private key. This gave birth to the world of Alice and Bob (and others). Alice and Bob are two persons who try to communicate with integrity requirements, defeating intruders which might try to listen, eavesdrop or alter communication.

Of course, to decipher the message, the recipient just needs to invert the function, using the secret trap.

The nicest example of public key cryptosystem (and undoubtedly the simplest) was presented two years later in 1978. It was invented by Rivest, Shamir and Adleman and is therefore shortened RSA. It is based on the mathematical difficulty of integer factorization. The private key is made out of the triplet (p,q,d) with p and q two primes (having roughly same size), and d a relative prime to p-1 and q-1. The public key is made of pair (n,e), with n=pq, and e the inverse of d modulus (p-1)(q-1), i.e.

ed = 1 mod(p-1)(q-1).



Suppose Alice wants to send some text, enciphered with Bob's public key (n,e). She first transforms the message in an integer m less than n. Then, she processes 
c = me mod n,


and sends the result c over to Bob. On his side, Bob whose private key is (p,q,d) processes : 
cd mod n = med mod n = m.


For RSA, the one-way trap function is the function which associates an integer x <n to the value xe mod n.

Since RSA, many other public key cryptosystems have been invented. Currently, one of the most famous alternatives to RSA is a cryptosystem based on discrete logarithms.

Modern use of cryptography

Actually, public key cryptography is really interesting because it is easy to use and it solves many security problems heretofore unsolved. More precisely, it solves a few authentication problems: Besides, as secret key cryptography, public key cryptography provides encryption-based cryptosystems, guaranteeing confidentiality of communications.

Let's imagine Alice wants to communicate secretly with Bob. Alice retrieves Bob's public key in a public directory, and enciphers her message with this key. When Bob receives the ciphertext, he uses his private key to decipher the ciphertext and read initial clear text. Both keys have very different roles, this explains why such systems are called asymmetric cryptosystems - referring to secret key cryptosystems which use the same key for ciphering and deciphering and are also know as symmetric cryptosystems.


Public key cryptography offers another major benefit over secret key cryptography. As a matter of fact, if n users communicate through a secret key cryptosystem, each of them need one different secret key for each person in the group. So, n(n-1) keys need to be managed. If n is over thousands of users, then millions of keys need to be managed... Furthermore, adding a new user to the group is not an easy task, because n new keys need to be generated for the user to communicate with all members of the group. Then, those new keys need to be sent over to the group. On the contrary, in asymmetric cryptosystems, the n public keys of the members are stored in a public directory. Adding a new user simply consists in adding his public key to the directory.

Using a public or a secret key: finding a trade-off

The previous paragraph has explained that public key cryptography solved many problems secret key cryptography could not cope with. One might then wonder what for AES has been designed. Actually, there are two major explanations to this choice. As a consequence, for pure encipherment, secret key algorithms are preferred - when it's possible to use them. Zimmermann has worked over an interesting hybrid solution, implemented in PGP. Basically, when Alice and Bob want to communicate with integrity features, using a secret key algorithm (PGP uses IDEA): When they have finished communicating, the negotiated session key is discarded. Such a system uses both secret key cryptosystems and public key cryptosystems. Usually, people consider the less secure part of such a system is the key exchange protocol.

Bibliography

History of cryptography : For AES :
Cryptography in general :