Encryption

in Miscellaneous Last modified at:

Whether you open a website, play a multi-player game, or simply make a WhatsApp call, there is always the risk of being intercepted.

Imagine an open area with a large crevice. On one side is Alice, on the other is Bob. Alice wants to tell Bob something important, but Eve wants to hear this message. How can Alice and Bob talk to each other now that they can only call?

Symmetric encryption

The term “symmetric” is used to refer to an encryption method when Alice and Bob use the same secret, the same key. This is in contrast to asymmetrical encryption.

Caesar Cipher

In the so-called Caesar procedure, which is ascribed to this, only the common alphabet from A to Z is used to encode data. Before that, Alice and Bob agreed on a secret number. Now Alice wants to send the sentence “HELLO WORLD” to Bob. For this purpose, she takes the position in the alphabet for each letter, adds the secret number, and writes the letter in the alphabet at this new index. Bob just turns this process around, so subtracts. “H” is on the 8th letter. Alice now calculates 8 + 5 = 13 and writes the 13th letter down: “M”. For the whole sentence “HELLO WORLD”, it is used as follows: “MJQQT BTWQI”. Bob now only has to subtract the secret number to get back to “HELLO WORLD”.

Data Encryption Standard (DES)

DES is a modern application of block cipher. Block ciphers divide the data to be encrypted by size (here 64 bits) into blocks, which are individually encrypted. However, the keys are very short for DES (for encryption only 56 bits), so that a computer can crack the key quickly by simply trying out (Brute-Force) of around 72 billion possibilities. To prevent the lack of data encrypted with DES, you can use the encryption method several times, resulting in Triple-DES if you do it three times. At the beginning, the secret key is split into sub-keys. In block interlocking, each block passes through several rounds of encryption, where each of the sub-keys is applied. The encryption consists of substitutions and permutations.

The aim is to make the encrypted data appear as random as possible, so that potential attackers cannot detect any patterns.

Advanced Encryption Standard (AES) / Rijndael

AES has been the official successor of DES since 2001, and therefore also a block-cipher, but each block has a size of 128 bit. It is split into AES-128, AES-192 and AES-256, with the number always indicating the key length in bits. AES-256 is used today for most data encryption, such as hard disk backups and data exchange with HTTPS. First, the key is read with the corresponding length, which generates 10 further partial keys with the defined key length (128,192 or 256 bits). Each block is now placed in a 4x4 table, so that each field has a byte. Then each block is combined with a partial key via XOR. The following shall be repeated for each round:

  • bytes are substituted to 01100011{01100011}
  • the last three rows are moved cyclically
  • the columns are multiplied by the following vector [02,01,01,03][{02}, {01}, {01}, {03}]
  • each block will be combined with a partial key via XOR At the last run, the columns are not multiplied.

Here, too, the goal is to make the encrypted data appear as randomly as possible.

Asymmetric encryption

The term “asymmetric” is used to describe an encryption method when Alice and Bob use different secrets. Often only in one direction, i.e. only from Alice to Bob and not from vise-versa can be encrypted. This is in contrast to symmetric encryption. Often, asymmetrical procedures are used for key exchange such as for HTTPS, and the actual data is then exchanged by symmetrical encryption.

RSA (Rivest–Shamir–Adleman)

RSA is still used in many protocols for key exchange, such as SSH and HTTPS, but is no longer the preferred method of choice. At the beginning Alice and Bob choose a prime number. Now a public key and a private key are generated from these prime numbers. To cover up, irreversible calculations are carried out based on the public key and data. The only way Bob can now decrypt the encrypted data is to perform another calculation using the private key.

Key Generation

Given the primes pp and qq. n=p×q ϕ(n)=(p−1)×(q−1)\begin{gathered} &n = p \times q\\\ &\phi(n) = (p - 1) \times (q-1) \end{gathered}

ϕ(n)\phi(n) represents the Euler’s totient function, which indicates how many positive are relatively prime to nn. Now you search for a number ee which is not part of ϕ(n)\phi(n), with the greatest common divisor (gcdgcd) of ee and ϕ(n)1\phi(n) 1 being 11. gcd(e,(p−1)×(q−1))=1\begin{aligned} &gcd(e, (p-1) \times (q-1)) = 1 \end{aligned}

To ensure the irreversibility, modmod is used. e×d=1mod  ϕ(n)\begin{aligned} &e \times d = 1 \mod \phi(n) \end{aligned}

This results in (e,n)(e, n) for the public key and (p,q,d)(p, q, d) for the private key.

The remarkable thing about this is that you cannot conclude from the public key on the private. So Bob can now freely distribute the public key, so that every one encode data, but only he can decode it again, using the private key.

As an example, Bob now selects the prime numbers p=5p = 5 and q=11q = 11. n=p×q=5×11=55\begin{aligned} &n = p \times q = 5 \times 11 = 55 \end{aligned}

Bob now chooses 33 for ee. e×d=1mod  ϕ(n)=3×d=1mod  ϕ(55)\begin{aligned} &e \times d = 1 \mod \phi(n) = 3 \times d = 1 \mod \phi(55) \end{aligned}

As a public key, he receives (3,55)(3, 55) and (5,1127)(5, 11 27) as a private key.

Encryption

Encryption is relatively simple thanks to the public key: y=xemod  n\begin{aligned} &y = x^e \mod n \end{aligned}

Suppose Alice wants to send the message “B” now, she takes the position in the alphabet, 22, and Bob’s public key, (3,55)(3, 55). y=23mod  55=8\begin{aligned} &y = 2^3 \mod 55 = 8 \end{aligned}

The 8th letter in the alphabet is “H”, so the letter “B” is now encrypted to “H”.

Decryption

Decryption is similar to encryption: x=ydmod  n\begin{aligned} &x = y^d \mod n \end{aligned}

Bob is now getting the letter “H” from Alice and wants to decode it. For this, he takes the place in the alphabet again, that is 88, and his private key, that is (5,11,27)(5, 11, 27). x=827mod  n=827mod  (p×q)=2\begin{aligned} &x = 8^27 \mod n = 8^27 \mod (p \times q) = 2 \end{aligned}

The second letter in the alphabet is “B”, so Bob successfully decrypted the message.

Diffie–Hellman key exchange

This procedure is used in TLS 1.3, i.e. the latest version of SSL/TLS for key exchange. To explain it easier, imagine Alice and Bob swap colors instead of numbers. First they think of a common color, then everyone thinks of a secret color. They add up and send the result. To the received result they now add their color again, and thus ever get to the same common secret without ever publishing their private secret colors. It is assumed that one cannot conclude from the mixed colour on the original colors. This is not yet proven in a mathematical way for the Diffie Hellman method.

Divie-Hellman Key Exchange with Colors

Original schema: A.J.jacquie MacLaine /Vinck, University of Duisburg-EssenSVG version: Flugaal, Public domain, via Wikimedia Commons

References