Encryption Algorithms

Symmetric Cryptography

What is it?

The basic thing about symmetric encryption is that the same key is used for both encryption and decryption.

If Alice wants to send a message to Bob, she writes the message and puts it in a safe. She locks the save using a special key. She gives this key to Bob and he can open the safe with this key and read the message.

DES a symmetric encryption algorithm

The original algorithm Lucifer was implemented in the early 1970’s by IBM and was verified and altered by the NSA, after the National Bureau of Standards (NBS), pointed out the need of a standard encryption algorithm.

DES stands for Data Encryption Standard.

Preparation

The DES works on blocks of 64bit of a given message. Let M be the hexadecimal message, which we want to encrypt. Message M = 0123456789ABCDEF

In binary format M looks like this: M= 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

We read M from left to right, so the first bit of M would be 0 and the last one 1.

DES uses a 64bit key, so let K be K= 1334577BBCDFF1 in hexadecimal format.

In binary format K looks like this: K=0001 0011 0011 0100 0101 0111 0111 1001 1001 1011 1011 1100 1101 1111 1111 0001

The first step is to create 16 48bit sub keys, therefore we need to change our 64bit key into a 56bit key.

To do so we permute the Key K according to the table PC-1, which means that the 57th bit of K becomes the first bit of K+ and the 4th bit becomes the last one.

                    PC-1 (7bit*8=56bit)
	57	49	41	33	25	17	9 
	1	58	50	42	34	26	18
	10	2	59	51	43	35	27
	19	11	3	60	52	44	36
	63	55	47	39	31	23	15
	7	62	54	46	38	30	22
	14	6	61	53	45	37	29
	21	13	5	28	20	12	4

As we can see every 8th bit is thrown away, so the new Key K+ has only 56bit all together. After this we split K+ into a left part which we call C0 and a right part called D0.

Then we compute Cn and Dn by left shifting Cn-1 and Dn-1 with a given number according to the following table.

Iteration	   	        Number
Number 			of Left Shifts
1 				1
2 				1
3 				2
4 				2
5 				2
6 				2
7 				2
8 				2
9 				1
10 				2
11 				2
12 				2
13 				2
14 				2
15 				2
16 				1

The final step of creating the sub keys is now to concatenate all 16 Cn and Dn and to permute them according to table PC-2

           PC-2 (6bit*8=48bit)
14	17	11	24	1	5
3	28	15	6	21	10
23 	19	12	4	26	8
16	7	27	20	13	2
41 	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

As the result we get 16 Sub keys, where each sub key has a length of 48 bit.

Encryption

To encode a message we first rearrange every 64bit block of it according to table IP

                           IP
58      50      42      34      26      18      10      2
60      52      44      36      28      20      12      4
62      54      46      38      30      22      14      6
64      56      48      40      32      24      16      8
57      49      41      33      25      17       9      1
59      51      43      35      27      19      11      3
61      53      45      37      29      21      13      5
63      55      47      39      31      23      15      7

Then we split the result into a left (L0) and a right part (R0) and compute 16 iterations of:

Ln=Rn-1 Rn=Ln-1 + f(Rn-1, Kn)

What does f do? First of all f is a function that needs 2 48bit parts, but as you know if you split a 64bit block into 2 halves you get only a 32bit part, so we need to expand the Rn-1 before we can use it with f. This is easily done by permuting the original block with the E-Bit selection table.

E Bit-Selection Table (6bit * 8 = 48bit)

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

In f we XOR (+) the expanded Rn-1 with the key Kn, which was already 48 bit long.

f(Kn, Rn-1)=Kn + E(Rn-1) =B1B2B3B4B5B6B7B8

Then we use every 6 bit group (B1 to B8) as an address in an „S-BOX“, where the binary number given by the first and the last bit determines the row and the 4 bit number between them determines the column.

                                                  S1
		0    1    2    3    4    5    6    7    8    9    10    11    12    13    14    15
	0 	14   4   13    1    2   15   11    8    3   10     6    12     5     9     0     7
	1 	0   15    7    4   14    2   13    1   10    6    12    11     9     5     3     8
	2 	4    1   14    8   13    6    2   11   15   12     9     7     3    10     5     0
	3 	15  12    8    2    4    9    1    7    5   11     3    14    10     0     6    13

Every B has its own S-Box. The final stage of f is to do a permutation of the S-BOX-output using P

  P (4bit * 8 = 32bit)
16 	7 	20	 2
29 	12 	28	 17
1 	15	23	 26
5 	18	31	 10
2 	8 	24	 14
32 	27	3	 9
19 	13	30	 6
22 	11	4	 25

When we have finished this for all 16 L’s and R’s we apply the final permutation according to table IP-1.

               IP-1
	40 8 48 16 56 24 64 32
	39 7 47 15 55 23 63 31
	38 6 46 14 54 22 62 30
	37 5 45 13 53 21 61 29
       36 4 44 12 52 20 60 28
	35 3 43 11 51 19 59 27
	34 2 42 10 50 18 58 26
	33 1 41  9 49 17 57 25

This output is the encrypted 64bit block of message.

Modes of Operation

Even more important than the algorithm itself is the mode you are using it.

ECB

If everything is done like shown above the mode is called Electronic Code Book or ECB.

CBC

If you XOR the previous block of cipher text with the current block of plaintext, before you encrypt the message, the mode is called Cipher Block Chaining (CBC)

CFB

The CBC is also used for the Cipher Feedback (CFB) mode. First the message is encrypted using CBC mode but when everything is computed we just throw away everything but the last block. As you can see the last block depends on all the other blocks before it, so it can be used as message authentification code (MAC). Then this last block is added to the end of the message and everything is encrypted again with CBC and a second key. This way the receiver of the message is able to check if the message was altered.

Types of DES

DES is a very old algorithm so there are some different implementations today.

DESX

DESX (k0, k1, k2, M)=DES(k0, M+k1)+k2

First we XOR the message with the key k1, then we encrypt it using k0 and after this the result is XOR’ed with k2. The keys k0 and k2 are only used to make it harder for a possible attacker to find out the original k1.

3DES

3DES (k0, k1, k2, M)=DES(DES-1(DES(k0,M),k1),k2)

Triple-DES first encrypts a message with the key k0, then tries to decrypt it with a second key k1, which scrambles the message even more and then encrypts it again with k2.

This type was necessary as it expands the effective encryption strength from 2 to the power 56 to 2 to the power 112. In 1999 it took about 2 days to encrypt a DES encrypted message by brute force, but from today’s view our sun will become a supernova before 3DES can be decrypted by brute force.

Asymmetric Cryptography

What is it?

The concept of Asymetric Cryptography, also called Public Key Cryptography, was described for the first time by Whitfield Diffie and Martin Hellman in 1976. In contrast to the Symmetric Cryptography in which we have the same secret key for encryption and decryption, we now have one public key e_P (ecncryption key) and one private key d_P (decryption key) for each person P . While the public key e_P can be published to the whole world the private key d_P is to be treaten as a secret and only the person P knows it. An important characteristic of such a crypto system is that it is computationally infeasible to determine the private key given the corresponding public key.

The idea of Public Key Cryptography can be visualised like a mailbox. Generally the address of someone is public and everybody can send him a letter, but only the reciever owns the key for opening the mailbox and reading the letters. Remember that Symmetric Cryptography works like a safe. For instance assume that Alice wants to send a message m to Bob. She encrypts the plaintext m with Bob's public key e , computes the ciphertext c=f(m,e) and sends c to him. Now Bob can decrypt the recieved cipher c with his private key d and computes the plaintext m=f'(c,d).

The biggest advantage of Asymetric Cryptography is the enormously reduced effort for the key management. Imagine a company with 100 staffers gets a new employee Bob and you have to offer Bob the possibility to communicate securely to each other person. Using a symmetric crypto system means that you must create 100 new keys and distribute them. With a asymetric system you only have to create the key pair (e_P,d_P) , publish e_Bob and tell Bob his private key d_Bob .

A disadvantage is the velocity. Comparing DES and RSA the most popular representatives of both worlds, we get that DES is at least 100 times as fast in software and between 1,000 and 10,000 times as fast in hardware. Generally we can say that asymetric algorithms are significant slower than symmetric algorithms.

A solution for this are Hybride Systems which work as follows:

• First asymmetric cryptography is used for the key exchange of a session key k_s .
• Then symmetric cryptography is used for encryption and decryption of the data with the exchanged key k_s.

So these method offers the comfortable key management as well as the velocity.

RSA an asymmetric encryption algorithm

The RSA Algorithm was invented by R.Rivest,A.Shamir and L.Adleman in 1977 while they were attempting to show that Public Key Cryptography is impossible.

How does it work?

RSA is based on the following fact:
Let n=pq be the product of 2 primes p,q (p≠q). Then for every natural number m<n and for every natural number k we have

$m^{k(p-1)(q-1)+1}{\bmod {n}}=m$

$((p-1)(q-1)=\phi (n))$

The function φ is called the Euler phi function, where φ(n) is the number of positive integers less than n that are relatively prime to n (a positive integers a is relativly prime to n if the greatest common divisor of a and n is 1).

If you want, read cryptography-books for more details of number theory. There you also find the necessary information for proving the above statement. The focus of this site is just to present and not to deduce the basic statements used by RSA.

Preparation work

Since RSA is an asymetric encryption algorithm we need a public key e and a private key d for each Person. This is done by ...

1. searching big primes p,q
2. computing n=pq
3. computing φ(n)=(p-1)(q-1)
4. choosing a number e which is relatively prime to φ(n)
5. computing d with ed≡1 mod φ(n) (that is when ed=k(p-1)(q-1)+1 and k is a integer)
6. forgetting p,q,φ(n) (or keeping this numbers secret!!)
7. giving d to the person as a private (secret) key
8. publishing e and n

Encryption with RSA

Suppose that you want to encrypt a message m and send the cipher to Bob who has the public key (e,n).

• Compute the cipher

c = m^e mod n

• Send the cipher c to Bob
• Bob can decrypt the cipher c with his private key d by computing

c^d mod n = m^ed mod n = m^{k(p-1)(q-1)+1} mod n = m

If the message is too long that is if m≥n you have to encrypt m blockwhisely. That means that you decompose m to smaller messageblocks m_i with m_i<n for all i and encrypt them block by block.

Digital Signatures with RSA

RSA also enables us to make digital signitures. Let (e,n) and d be your public and your private key and let m be a message or a hash value of a message which you want to send to Bob. You can sign the message by computing

sig = m^d mod n

send the message with the signature (m,sig) to Bob. He can verify the signature sig with your public key (e,n) by computing

sig^e mod n = m^de mod n = m^{k(p-1)(q-1)+1} mod n = m

Final Remarks

The secureness of RSA depends on the keylength. Today one should use a length with at least 1024 bit for the modulus n=pq( a number with approx. 300 decimal digits). By the way, have a look at the RSA factoring challenge. There you can get money for factoring numbers. Up to now the largest factored number is RSA-576 a 576 bit number and it was factored on december 3, 2003. The factorization was led by the german researchers Jens Franke und Thorsten Kleinjung from the Pure Mathematics Institute at Bonn University.

Considering RSA as a Trapdoor One Way Function we know that its trapdoors are the private key d, the prime factors of n: p and q and φ(n). It can be shown easily that knowing one of these informations you can deduce the others. But it has not been prooved yet that there is no other trapdoor information for this Algorithm.