Locks and Fingerprints (Part 1): How Encryption Keep Data Safe
Encryption and Hashing are two powerful and common tools to protect data from malicious attackers. This article aims at presenting the different encryption algorithms.
Encryption Algorithms
Encryption algorithms are mathematical procedures used to convert readable data (plaintext) into unreadable data (ciphertext) to protect it from unauthorized access. These algorithms ensure confidentiality: only someone with the right decryption key can revert the data back to its original form.
Let’s look at the two main categories of encryption algorithms: Symmetric and Asymmetric.
Symmetric Encryption Algorithms
In symmetric encryption, the same key is used for both encrypting and decrypting data. This approach is generally faster and well-suited for encrypting large volumes of data, such as personally identifiable information (PII). However, it presents key management challenges, as both the sender and the receiver must securely share and store the same secret key.
DES (Data Encryption Standard) and 3DES
These algorithms are deprecated because they are vulnerable to bruteforce attacks and birthday attacks.
As a reference purpose, here is an overview of DES and 3DES algorithm processes:
3DES applies DES 3-times with 3 different keys:
Ciphertext = Encrypt(Key1, Decrypt(Key2, Encrypt(Key3, Plaintext)))AES (Advanced Encryption Standard)
AES is a symmetric cipher: it uses a single key to encrypt and decrypt the same data. They key can be 128, 192 or 256 bits. AES is also a block cipher, which means it encrypts data in fixed-size blocks. If the data is longer than 16 bytes (128 bits), AES splits it into multiple blocks and encrypts them one by one.
At the very beginning of the algorithm, AES takes an input plaintext (P) and a secret encryption key, convert it to hexadecimal format and arrange each block of the plaintext into a 4x4 matrix and repeatedly perform a set of operations on it in order to obtain a ciphertext (C).
Encryption
The basic idea of AES is to encrypt a block through a series of rounds. Each round performs some substitutions and permutations. The number of rounds are depending on the key length:
- 10 rounds for a 128-bit key
- 12 rounds for a 196-bit key
- 14 rounds for a 256 bit key
Each round gets a different key called round key. The round keys are derived and obtained from the secret key. The way round keys are obtained is described later in this article.
Here is an overview of AES algorithm:
The algorithm is made up of 4 functions:
- SubBytes: a simple substitution (mapping) based on the AES S-box.
- ShiftRows: applies some rotations on the state.
- MixColumns: divides the state in multiple words and mix them together.
- AddRoundKey: XORs a round key to the state.
Note: The AES state is the current value of the bytes being encrypted.
The initial round only does the AddRoundKey() method doing P ⊕ K0. Then, N rounds are done applying all 4 methods in the same order. Finally, at the last round, only 3 methods are applied since the MixColumns() doesn’t add more security.
AES uses key expansion to generate all keys.
At initialization, k0, k1, k2, k3 are added to give w0. The same thing is done to calculate w1, w2 and w3. w3 is then pass as parameter of g function to output w3’ (w’ = g(w)). The result w3' is XORed with w0 to ouput w4. Similarly w4 is XORed with w1 to output w5 and so on until w7. The steps are repeated until w43 (for AES-128).
Here are the steps inside the g function:
- w is splited into 4 parts (B0, B1, B2, B3)
- Rotword: 1-byte left circular shift
- Subword: substitution using AES S-box is done
- Rcon: a XOR operation with RC_j followed by 3 Zero-bytes
Decryption
Decryption is very similar to encryption. It performs the encryption algorithm in reverse using the inverses of the operations.
For MixColumns() there is the inverse matrix:
For shiftRows(), the inverse S-box is the following:
To sum up on AES, the algorithm is designed to add confusion and diffusion. AddRoundKey() adds dependency on the key as well as some confusion. ShiftRows() and MixColumns() add diffusion. Finally, SubBytes() adds nonlinearity and confusion to avoid retrieving the key using Gaussian elimination.
Confusion refers to making the relationship between the encryption key and the ciphertext as complex and unpredictable as possible. The goal is to hide patterns so that if an attacker sees the ciphertext, they can’t figure out anything about the key. Confusion protects against key analysis (trying to learn the key).
Diffusion ensures that small changes in the plaintext (like flipping a single bit) result in large, unpredictable changes in the ciphertext — ideally affecting about half of the output bits. Diffusion protects against plaintext analysis (looking for patterns).
When combined, they help ensure that encrypted data is secure, even if attackers have access to many encrypted messages.
Blowfish
As this algorithm is slow to setup, even if still no practical cryptanalysis has fully broken it, its successors Twofish offers stronger security and better performance.
Nevertheless, here is an overview how this algorithm works:
In the Blowfish encryption process, a 64-bit plaintext block is split into two 32-bit halves. The left half is first XORed with the first value from the P-array, resulting in an intermediate value called P′. This value is passed through a transformation function F, and the output is then XORed with the right half of the original block, producing a new value we’ll call F′.
Next, F′ becomes the new left half, and P′ becomes the new right half. This process is repeated 16 times, using successive values from the P-array.
Finally, after the 16 rounds, the two halves are XORed with the last two values from the P-array (entries 17 and 18), and then recombined to form the final 64-bit ciphertext.
Here is the detail of F function:
The P-array (P1, P2, …, P17) and S-array (S-box 1, S-box 2, S-box 3, S-box 4) values used by Blowfish are precomputed based on the user’s secret key. This is where the operation is costly, even if is done once.
Twofish
Twofish algorithm was designed by the same creator of Blowfish and was finalist in the AES competition but the Rijndael algorithm was selected to become the AES. It’s a symmetric block cipher algorithm designed to be flexible and faster than its predecessor. It operates on blocks of 128 bits and supports key sizes of up to 256 bits.
Here is an overview of the algorithm process:
- The plaintext is first divided into 128-bit blocks.
- The first block is encrypted using the Twofish algorithm and the chosen key.
- The result is XORed with the next block of plaintext, combining them in a secure way.
- This process is repeated for all blocks, chaining them together securely.
- The final output block is the ciphertext.
From the original key, it derives a set of unique round keys used during each stage of encryption. This key schedule doesn’t just rely on the main key. It also generates subkeys and S-boxes (substitution boxes) that are essential for the 16 round operations.
Twofish also applies mathematical transformations such as the Pseudo-Hadamard Transform (PHT) and uses a special Maximum Distance Separable (MDS) matrix. These components are responsible for mixing the data. That’s the diffusion principle.
A special function called the F-function processes the data in halves and mixes it repeatedly to ensure both confusion and diffusion.
ChaCha20
ChaCha20 is a stream cipher. Unlike block ciphers like AES, stream ciphers encrypt data bit by bit or byte by byte by generating a keystream and XORing it with plaintext. ChaCha20 is built around a 20-round transformation function that scrambles a 512-bit internal state to generate pseudorandom output blocks.
ChaCha20 works with 4 byte words, takes 16 words of plaintext and outputs 16 words of ciphertext. Here is an overview of the whole process:
A 16 words input matrix is formed as follows:
- 4 words of constant value (“expand 32-byte k”)
- 8 words of secret key
- 2 words of block counter (incremented after each 20 rounds) that ensures each output block is unique
- 2 words of nonce (a randomly chosen number for each encryption session)
For every new 16 words of plaintext, 20 rounds are performed on the original input matrix by alternating column and diagonal rounds.
Each round performs 4 quarter rounds on 4 words as follows:
A += B; D ^= A; D <<<= 16;
C += D; B ^= C; B <<<= 12;
A += B; D ^= A; D <<<= 8;
C += D; B ^= C; B <<<= 7;This round operations are illustrated in the following schema:
The output of the 20 rounds is summed to the original input matrix.
Finally, this sum is XORed to the 16 words of plaintext to produce 16 words of ciphertext.
Camellia
Camellia is a symmetric key block cipher designed to offer strong security and high performance, comparable to AES. Camellia is based on a Feistel network, just like Twofish. That means encryption and decryption use the same structure, just with reversed keys. Despite the complexity, it’s designed for efficiency on both hardware and software.
Here is how it works:
- The first thing is to generates round keys and 52 subkeys using rotations, XORs and S-boxes.
- There is an initial round to XOR the plaintext with 2 subkeys.
- 18 / 24 Fesitel rounds (128-bit keys / 192/256-bit keys). Each round uses a round function F ensuring both confusion and diffusion.
F(input, roundKey) = P(S(input XOR roundKey))
P is a linear permutation layer
S is a layer of 8-bit S-boxes (4 S-boxes total)- FL/FL^(-1) functions are inserted every 6 rounds to add extra diffusion and nonlinearity. They are bitwise operations applied to the left and right halves of the data block.
Encryption
X_R' = X_R ⊕ (X_L & k1)
X_L' = X_L ⊕ (X_R' | k2)
Decryption
X_L' = X_L ⊕ (X_R | k4)
X_R' = X_R ⊕ (X_L' & k3)
with k1, k2, k3, k4 subkeys- Finally, after the last round, 2 more subkeys are XORed with the result.
Asymmetric Encryption Algorithms
Asymmetric encryption relies on a pair of keys: a public key, which is openly shared and used for encryption, and a private key, which is kept secret and used for decryption. Since the private key is never transmitted or exposed, this method offers stronger security compared to symmetric encryption. However, it is slower due to the computational complexity involved in key generation and encryption processes.
This category of systems is based on mathematical problems that are simple to perform in one direction but extremely difficult to reverse. These are often referred to as trapdoor functions.
Here are some cryptographic security bases that will be presented in this article:
- Integer Factorization: multiplying primes is easy, factoring is hard
- Discrete Logarithm Problem (DLP): easy to exponentiate, hard to reverse
- Elliptic Curve DLP (ECDLP): DLP over elliptic curves
- Lattice Problems: hard to solve short vector problem
- Learning with Errors (LWE): noise in linear equations makes solving hard
Diffie-Hellman
The Diffie–Hellman key exchange (DH) is a method that allows two parties to establish a shared secret key, even though they communicate over an unsecured public channel.
Instead of exchanging the key directly (which could be intercepted), each party computes the shared secret independently using modular arithmetic and a bit of math.
Here is the process described:
The parameters are public and do not need to be secret:
- A large prime number
p, a 2048-bit prime or larger. - A primitive root modulo
p, called the generatorg
The security relies on the difficulty of the Discrete Logarithm Problem: Given g, p, and A = g^a mod p, it is computationally infeasible to find a.
Get Sylvain Tiset’s stories in your inbox
Join Medium for free to get updates from this writer.
Note that Elliptic Curve Diffie-Hellman (ECDH) uses elliptic curves instead of modular arithmetic which is faster and more secure at smaller key sizes.
S = dA × QB = dA × dB × G
G is a point on the elliptic cruve
dA is the private key of Alice
dB is the private key of Bob
QB is the public key of Bob
QA is the public key of Alice
S is the shared keyRSA (Rivest–Shamir–Adleman)
RSA (named after its inventors: Rivest, Shamir, and Adleman) is an asymmetric cryptographic algorithm. RSA is based on the difficulty of factoring large prime numbers. Here’s how it works:
pandqmust be random, large, and secret.- It’s hard to reverse n = p × q if
pandqare large enough (e.g., 2048-bit). - φ(n) is called Euler’s totien function.
eand φ(n) are coprime (a common choice fore: 65537, because it’s large enough for security but small enough to be efficient).dis the modular multiplicative inverse ofemod φ(n).- Message
Mmust be a number < n
RSA is not obsolete yet, but it’s slowly being replaced in new systems by ECC.
ElGamal
The ElGamal encryption algorithm is a public-key cryptosystem based on the Diffie-Hellman key exchange and discrete logarithms. It provides confidentiality by encrypting messages using randomized asymmetric encryption.
Here is how encryption and decryption works:
The constraints are the following:
- p is a large prime number
- g is a generator of the group Z*p
- 1 < x < p−1
- Y = g^x mod(p)
- 1 < r < p−1
It works because of the following formulas:
b = Y^r . M = M . (g^x)^r = M . g^(xr)
M = b / a^x (mod p) = M . g^(xr) / g^xr (mod p) = MECC (Elliptic Curve Cryptography)
Elliptic Curve Cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields.
The strong advantage of ECC over RSA and ElGamal is the key size for the same security level: 256 bits for ECC os 3072 bits for RSA or ElGamal.
Here is a graphic representation of the equation:
Elliptic curves have some unique properties:
- Any
(x, y)pair that satisfies the equation is a point on the curve. There’s also a special point called “point at infinity” (O), acting as the identity element. - Operation Point Addition (P + Q): Add two different points on the curve
- Operation Point Doubling (2P): Add a point to itself
Given an elliptic curve and a point P and an integer k: Q = k × P operation is easy to perform, but the reverse (finding k given P and Q) is computationally hard.
k is the secret key and Qthe public key.
Generally, the chosen elliptic curve is secp256r1 or Curve25519. The are represented that way:
In the cryptography context, these curves are applied over a finite fields. The equation become y² ≡ x³ + ax + b (mod p) and the graphical representation is the following:
Finally, given the following inputs:
- An elliptic curve E over a finite field
- A generator point G on the curve
- The receiver (Bob) chooses the private key:
dBand the public key:QB = dB . G
Encryption process is described as follow:
- Map the message to a point
PMon the curve. The messageMis encoded as a point on the elliptic curve using mathematical techniques like try-and-increment. - The sender (Alice) picks a random integer
k(the ephemeral private key (only used once)) - Compute two points:
C1 = k.G
C2 = PM + k.QB- Send the pair
(C1, C2)as the ciphertext to Bob
Decryption process is then the following:
- Compute shared secret:
dB.C1 = dB.k.G = k.QB - Recover original point:
PM = C2 — dB.C1 = (PM + k.QB) — k.QB - Decode the point back into message
Musing reversing try-and-increment method
NTRU / Kyber (Post-Quantom cryptography)
NTRU (short for Nth-degree Truncated Polynomial Ring Units) is a public-key cryptosystem that offers high efficiency, small key sizes and especially resistance to quantom attacks (unlike RSA or ECC). It’s based on lattice cryptography.
In mathematics, a lattice is a regular, repeating grid of points in space.
L = { a·v₁ + b·v₂ | a, b ∈ ℤ }
In 2D, v1 and v2 are two vectorsHere are 2 different, 2-dimensional lattice examples:
One of the interesting properties of lattices is that the same lattice can be generated using different sets of vectors. In the following picture, both the blue/green dot-dashed vectors and the red/black vectors can produce the same grid of points. These sets of vectors are known as the basis of the lattice. Different bases can define the same underlying lattice structure. In contrast of the lattice, a basis is a simple finite object (which can be represented in a computer’s memory).
A basis is defined as short if it consists of short vectors and nearly orthogonal. Conversely, a basis is long if it consists only of long vectors. A vector is long if it is far away from the origin and short if it is close to the origin.
The trapdoor comes with what is called the shortest vector problem: Given a lattice L, find a grid point as close as possible (but not equal to) the origin point. It’s more complicated to find a solution within a long basis rather than within a short basis. That’s why short basis are used for private keys and long basis rather for public keys.
Another math concept that is required to understand is LWE (Learning With Errors). LWE is a hard mathematical problem that involves solving systems of linear equations where small random errors (noise) are added. The problem is believed to be hard even for quantum computers, making it a strong candidate for post-quantum cryptography.
Suppose there is a series of equations like this:
a₁·s + e₁ ≡ b₁ mod q
a₂·s + e₂ ≡ b₂ mod q
...
aₙ·s + eₙ ≡ bₙ mod q
aᵢ is a known vector (part of the public key)
s is the secret vector
eᵢ is a small error (random noise)
q is a modulus (a large prime number)
bᵢ is the output
All equations are taken modulo qEven though aᵢ and bᵢ are known, recovering the secret s is very difficult because of the added noise eᵢ.
LWE lives in the world of modular arithmetic but it can be reduced to geometric problems on lattices, which are known to be hard (especially in high dimensions)
Finally, to well understand NTRU, let’s explain what is Ring LWE. Ring LWE is similar to LWE: there are “noisy” linear equations and the goal is to solve the hidden secret, but it’s done over ring structures rather than over vectors and matrices. All operations happen in a ring of polynomials like:
R = ℤ_q[x] / (xⁿ + 1).
A ring a of polynomials works this way: this is a regular polynomial, modulos q, and dividing by (xⁿ + 1), meaning the highest degree of the polynomial is n-1. In NTRU and Kyber algorithms, it uses symetric modulos instead of regular modulos. They map results into the interval [-q/2, q/2[ instead of [0, q[.
Ring-LWE is used because operations are faster than with vectors and matrices and also because key sizes are smaller.
Here is how NTRU works:
Choose parameters: N(degree of polynomials), p, and q are coprime integers (typically, q >> p)
Note: The elements modulo p (respectively q) are given in the set [−p/2,p/2[ (respectively [−q/2,q/2[) instead of the usual representation between [0,p−1] (respectively [0,q−1]). This is to ensure that when performing modular arithmetic (mod q), the coefficients are well-behaved and easily recoverable.
- Select two small random polynomials:
f: invertible modpand modq, andg: another small polynomial - Compute inverse:
f_p⁻¹such thatf * f_p⁻¹ ≡ 1 mod p - Compute inverse:
f_q⁻¹such thatf * f_q⁻¹ ≡ 1 mod q - Generate public key:
h = p * f_q⁻¹ * g mod q- Public key is
hand Private key isf,f_p⁻¹andg
For encryption:
- Pick a random message polynomial
mwith small coefficients - Pick a random small blinding polynomial
r - Compute ciphertext:
c = r∗h + m mod q
For decryption:
- Multiply ciphertext with private polynomial and calculate
m:
a = f∗c mod q
a = f(r*h + m) mod q
a = f(pr * f_q⁻¹ * g + m) mod q
a = pr * g + f*m mod q (because f_q⁻¹ is inverse of f mod q)
a = pr * g + f*m (because a, r, g, f and m are in [-p/2, p/2[ and p << q)
a = f*m mod p
=> m = f_p⁻¹ * a mod p
Kyber is a post-quantum Key Encapsulation Mecanism (KEM) based on Module-Lattice Learning With Errors (MLWE). As NTRU, Kyber works with a ring and polynomials: R = ℤ_q[x] / (xⁿ + 1).
Difference between KEM and Diffie-Hellman:
In KEM, one person makes a random key, encrypts it using the other person’s public key, and sends it.
In Diffie-Hellman, both people send partial secrets and combine them mathematically to get the same shared key (without actually sending the key itself).
Under the following Kyber table specification, here’s how Kyber works:
- Generate small random polynomials s and e (secret vectors) modulo a prime number q.
- Generate a public random matrix A.
- Compute: b = A×s + e (mod q) under ring R
- The public key is (A,b), and the secret key is s.
For encryption:
- Pick new small random vectors r, e1, e2.
- Compute ciphertext (u,v):
u = A^T x r + e1 (mod q)
v = b^T x r + e2 + m (mod q)
A^T is the transpose of A
b^T is the transpose of b
m is the embeded message converted to a polynomialFor decryption:
m = v - u^T x s (mod q)
m = (b^T x r + e2 + m) - (r^T x A x s + r^T x e1) (mod q)
m = (r^T x A x s + r^T x e + e2 + m) - (r^T x A x s + r^T x e1) (mod q)
m = m + r^T x (e-e1) + e2 (mod q)
m = m + "noise"
u^T is the thranspose of u
r^T is the thranspose of rSince all e1, e2, e, r and small, the total noise is small (ususally smaller than q/4) and m can be decoded, and then use for asymetric encryption.
Note that Kyber uses rounding: this is where the result of mod-s q is divided into two sections. If the coefficient is closer to the threshold, decode it as bit 0, else decode it as bit 1. For Kyber, the threashold is around q/4.
Common Attacks
To understand why some algorithms are deprecated and why best practices exist, it’s necessary to understand the common encryption attacks. Here is a list of the most common ones:
- Brute Force Attack: Tries every possible key until the correct one is found.
- Dictionnary Attack: Tries a precompiled list of common passwords or keys.
- Known-Plaintext Attack: Attacker has access to both plaintext and ciphertext, and uses it to deduce the key or decrypt other messages.
- Chosen-Plaintext Attack: Attacker can choose arbitrary plaintexts and obtain their ciphertexts in order to learn patterns and reverse-engineer the key or algorithm behavior.
- Chosen-Ciphertext Attack: Attacker can choose ciphertexts and get their plaintexts (from a “decryption oracle”).
- Side-Channel Attacks: Instead of attacking the algorithm, attackers analyze timing, power usage, EM leaks, etc.
- Differential Cryptanalysis: Studies how differences in input affect output to uncover patterns in the cipher.
- Linear Cryptanalysis: Uses linear approximations to the cipher’s components to analyze the key structure.
- Replay Attack: Re-sending a previously captured encrypted message to bypass security.
Use cases
Here are the common use cases of the presented encryption algorithms:
- Encrypting data in transit: Secures communication across networks, like HTTPS, VPNs, or secure emails.
- End-to-end messaging encryption: Used by apps like Signal and WhatsApp to ensure that only the sender and receiver can read the messages.
- Cloud storage security: Ensures user files remain private while stored in services like Google Drive or Dropbox.
- Email encryption: Used to protect the content and attachments of emails via PGP or S/MIME.
- Database encryption: Encrypts specific sensitive fields such as credit card numbers or social security numbers.
- Document encryption: Protects files like PDFs or Word documents with passwords and encryption settings.
Hoping encryption algorithms have no more secrets to you. If you liked this article, feel free to clap it, comment it or share it. To stay updated with my content, you can follow me on Medium.
