Cryptography

Abstract

Cryptography has always been an important task. The main goal of every cryptographic activity is Data Security (e.g. “hiding messages from unauthorized eyes”). Cryptography encodes messages in such a way, that only the sender and the receiver can understand them. One famous story, if not the most famous story, about cryptography is the break of the ENIGMA-Code in World War II. The British MI6 made an enormous effort to break into ENIGMA – with success by the way. Some estimations say, that without this, the end of the war would have been at least six months later… Cryptography, or “Crypto Analysis” if we’re talking just about “breaking codes”, is an interesting research area, in particular for military purposes, obviously.

Today, cryptography has its place not only in the army, but also in the civilian sector: With the upcoming mainframe computers in the seventies and with the personal computers in the eighties, cryptography has become available to everyone. Nowadays an ordinary PC can produce codes of such complexity, that the most powerful supercomputer, using the best available attack algorithms, would not break them in millions of years! Cryptography is used to secure telephone, internet, and email communication and to protect software and other digital property. Generally: to keep privacy in the bad world of communication. So, it is possible to communicate, without someone listening and understanding what you are saying…

This paper gives only a short introduction to basic cryptography and it is (really) far away from being complete. For further information, please consider the literature below.

Introduction to Cryptography

First thing you really need in order to do cryptography (e.g. encryption, decryption) is a cryptographic algorithm. “Do I need a computer?” you may ask. It depends on the algorithm and its complexity, but most generally the answer is “yes, you need one”! There are algorithms that could be used by hand. But the question is: Why would you do that? You surely don’t want to spend a week or two to encrypt a message until you can send it, or do you?

Today, we know many cryptographic algorithms. RSA, DES, 3DES, Blowfish, AES are just the names of a few. You will find some further details on some of these in the next chapter.

Cryptographic algorithms, also called Ciphers, are classified as either symmetric or asymmetric.

Symmetric Ciphers (Secret-Key-Ciphers)

Classical (symmetric) algorithms, such as DES, are based on a common secret key for both, encryption and decryption. This is the reason why this scheme is also called “Secret-Key”-Scheme:

Figure 1

As all cryptographic algorithms, symmetric ones have their strengths and weaknesses, too. Their strengths include especially fast encryption/decryption. However, their weaknesses include the need for a separate (secure) channel for key transfer, and the need for very complex key management. Especially the key transfer is a big problem: You need a secure channel to build up another secure channel?? Why you don’t just use the first secure channel? … Good question!

Asymmetric Ciphers (Public Key Ciphers)

Asymmetric ciphers are based on principles that differ to those governing symmetric ones in the following ways:

  • The encryption key is different than the decryption key.
  • The decryption key cannot be calculated from the encryption key (i.e. it is a one-way function).

Such a scheme is also called a “Public-Key”-Scheme, because the encryption key is made public. This way, a complete stranger can use the encryption key to encrypt a message, but only someone with the corresponding decryption key can decrypt the message. The encryption key is called the Public Key, and the decryption key is called the Private Key. Opposing to the Secret-Key-Cryptography, the pool of good Public-Key algorithms is far smaller. Today, the best-known and also most used asymmetric cipher, is RSA, which we will discuss later.

Asymmetric ciphers provide secrecy by having the sender use the receiver’s public key to encrypt the data, while only the intended receiver, using his private key, can decrypt the data and use it (Figure 2).

Again, asymmetric ciphers offer both, strengths and weaknesses. Their primary weakness is that encryption/decryption is relatively slow, involving intensive computations. Their strengths include:

  • Fewer security issues in key transfer (all public).
  • Simple key management (N users  N public keys).

Symmetric and Asymmetric ciphers are useful, and both have strengths and weaknesses. Thus, what would be closer than to combine the strengths of these two schemes and avoid their weaknesses? What we then get is a Hybrid Scheme. Please see the exercises & solutions for more details on Hybrid Systems!

Figure 2

Examples of Cryptographic Algorithms

In this chapter, we will discuss the basic ideas of three cryptographic algorithms: ROT13, DES and RSA.

ROT13

If we’d ask you to “invent” a cryptographic algorithm in three minutes, almost surely it would be that one, or at least, kind of that one! Let’s go into detail: ROT13 is a simple substitution Cipher. All you have to do is just replace each plaintext character by the character thirteen to the right modulo 26. So, “A” is replaced by “N”, “B” is replaced by “O” and so on. Every letter is rotated 13 places. Encryption of a message twice with ROT13 restores the original text:

It is obvious, that this is not a very secure encryption. Simple substitution ciphers can easily be broken, because the cipher does not hide the underlying frequencies of the different letters of the plaintext. Indeed, ROT13 is not used to secure communication paths. It is often used on Usenet to hide offensive text or just to make a simple puzzle a little bit harder to solve. Implementations of this algorithm can be found at [4].

DES (Data Encryption Standard)

DES stands for “Data Encryption Standard” and it was developed in the 70ies by IBM. Later (1977), it was certified by NIST (US National Institute of Standards and Technology). Since then, DES is what its name implies: the standard for symmetric encryption.DES is a combination of three operations:

  • XOR-Operation
  • Permutation (order of a bit sequence is altered)
  • Substitution (a bit sequence is replaced by another)

DES encrypts blocks of 64 bits using a 56 bit key. After an initial permutation of the 64-bit block of plaintext, the block is divided into two blocks of 32 bit (L and R). What follows then, is 16 times the same sequence, also called the 16 rounds of DES (Figure 3):

  • applying a function  on L
  • the result will be XORed with R and stored as the new L
  • the old L becomes the new R.

(this happens 16 times, as mentioned)

After these 16 rounds, there will be a final permutation. Et voilà, we have our 64-bit ciphertext.

Figure 3

The really important thing happens in the function . In every DES round, another part of the key is used by  to produce the encryption.  is a relatively complex function. The literature will give you further information on this. But the basic ideas of DES should have been made clear. To decrypt, a message passes exactly the same algorithm. The only difference is that the key is reversed.

DES is considered as very secure, but it has its weaknesses. Today’s multi-million dollar computer hardware is able to compute the key in a finite amount of time. DES However, there is a new algorithm at the horizon: AES. AES is even stronger than DES and it surely will be the new standard for symmetric encryption.

RSA

RSA is based on one important mathematical phenomenon: the difficulty of factoring large numbers. RSA is a member of the asymmetric encryption algorithms. The public and private keys are derived from a pair of large (min. 200 digits) prime numbers, and . Keys are generated as follows:

  1. Compute n = pq and z = (p-1)(q-1).
  2. Randomly choose the encryption key e, such that e and z are relatively prime.
  3. Choose a decryption key d, such that ed mod z = 1. In general, d is calculated with help of the Euclidean algorithm.

Key generation is now completed. The public key is defined as <e, n> and the private key as <d, n>. The two prime numbers p and q are not longer needed and should be discarded. To encrypt a message m, compute c = me mod n. For decryption use m = cd mod n.

RSA is extremely slow compared to DES. In hardware, RSA is about 1000 times slower than DES and in software about 100 times.

The security of RSA depends wholly on the problem of factoring large numbers. With today’s factorial algorithms it would take millions of years to compute the private key from the public key and the encrypted message. As long as there cannot be found a better factorial algorithm the encrypted message is safe.

Literature

[1]Bruce Schneier, “Applied Cryptography”, John Wiley & Sons Inc., 1996

[2]Friedrich L. Bauer, “Entzifferte Geheimnisse”, Springer 1995

[3]Klaus Schmeh, „Kryptographie“, dpunkt.verlag GmbH 2001

[4]Implementations of ROT13,

[5]International PGP Home Page,

Exercises

1) Complete key search

A complete key search is a method to find a key out of an encrypted message. It is also called a “brute force attack”, because the message is decrypted with every possible key. The result is a (very large) pool of potentially correct plaintext messages. But just one of them is the correct one!

How long would it take to do a complete key search on a DES-encrypted message? (Assume the decryption of a message with a certain key takes 1s.)

Answer:

DES works with a 56-bit key. So you have to try keys.

This is surely not the best way to break DES, but the simplest!

2) Why is symmetric encryption still used?

Answer:

Symmetric encryption is much faster than asymmetric encryption and in general easier to implement. There are good symmetric encryption algorithms that are not patented. RSA in contrary is patented in the US.

3) Give two scenarios where you would use symmetric encryption.

Answer:

  • HD encryption
  • Encrypted network session

Symmetric encryption is used where large amounts of data have to be encrypted and decrypted and where both parties already know the secret key or where the secret key can be exchanged through a secure channel.

4) How would you exchange the secret key of a symmetric encryption?

Answer:

A secure channel is needed. Thus you could encrypt it with an asymmetric encryption algorithm. The combination of asymmetric and symmetric encryption in such a way is known as hybrid system:

The whole stream of data is encrypted with a symmetric scheme. Thus, you can profit from the fast encryption and decryption. It is obvious, that you cannot transmit the key to decrypt the data over the same channel… at least not in plaintext! This is where asymmetric encryption comes up. The key is encrypted with the receiver’s public key. Because the key is far smaller than the actual data, there is not much time loss using an asymmetric algorithm.

5) Give two scenarios where you would use asymmetric encryption.

Answer:

  • Password encryption
  • Email encryption

Asymmetric encryption is used where there is no safe secure channel to transfer the key. Messages are relatively short.