These days, we’re often warned about the dangers of hacking and data theft, or reminded of the need to protect our vital documents, sensitive information, and credentials by encryption, when they’re transmitted over the internet or an unprotected network. But what does that mean, exactly?
Well, in simple terms, encryption is the process of taking a recognizable item (such as a written message, list of figures. or an image) and scrambling it so that it becomes unrecognizable to everyone except the person or entity intended to recognize it – who of course must have a key for unscrambling what’s been done to make it unrecognizable.
Though the results may look random to the casual observer, encryption isn’t a haphazard process. There are established mechanisms and systematic techniques. And yes – there’s mathematics involved.
Math and Matrices in Encryption
What’s commonly referred to as an encryption algorithm is really just a collection of operations performed on the elements (alphabet letters, numbers, bits of digital data, etc.) making up an object to be scrambled or encrypted. Typically, these operations will manifest as some kind of mathematical or geometric formula, governing how the component parts of an original object are dispersed to make up its encrypted counterpart.
As encryption is all about making the original source material indecipherable or unrecognizable, these mathematical functions typically involve moving its constituent elements around (shifting them to different positions), or replacing them with something else (substitution). Matrix functions are ideal for this, which is why they’re involved in many of the more advanced encryption techniques.
Doing the Rounds
The more sophisticated or advanced an encryption technique becomes, the more complex its encryption algorithm must be. You’d logically expect this to mean that the algorithm would have to consist of many operations of great complexity – and to a certain extent, this is true.
This brings us to the concept of a “round”. In cryptography, a round is made up of a number of algorithmic building blocks (mathematical functions, matrix transformations, etc.) strung together to create a function that’s run multiple times on source material to encrypt it according to a specific cipher or encryption algorithm.
The number of rounds performed on the source equates to how many times the information passes through the algorithm before it’s considered to have been sufficiently encrypted.
When encrypting data for digital transmission, we’re dealing with bits or bytes of information. A block cipher is an encryption algorithm which acts on a fixed-length group of bits, which is referred to as a block. This is why encryption algorithms are said to be 128-bit, 192-bit, 256-bit, and so on.
A block cipher’s transformations are specified by a symmetric encryption key, and many are performed by specifying a round which is then run multiple times.
The Feistel Cipher is a design model which formed the basis of many different block ciphers. Cryptographic systems based on Feistel use the same algorithm for encrypting and decrypting data.
Typically, the encryption process for a Feistel Cipher imposes multiple rounds of processing onto the plain text of the source. Each round involves a substitution step, followed by a permutation step.
DES and Triple DES
The Data Encryption Standard (DES) is a symmetric-key block cipher derived from the Feistel model. It was published by the National Institute of Standards and Technology (NIST), and uses a 16-round Feistel structure operating on a block size of 64 bits.
The key length for DES is 64 bits, but this is effectively reduced to 56 bits, as 8 of the 64 bits in the key aren’t used by the encryption algorithm, acting instead as check bits.
DES has some great strengths as a cipher. Any small changes made in the original plain text result in huge changes in the cipher text, once the algorithm is run. This is known as the “Avalanche Effect”. Each bit of cipher text also depends on many bits of plain text, making it more difficult to crack.
Difficult, but not impossible – and an improved variant known as Triple DES or 3-DES was adopted to address the vulnerability of DES to brute force attacks stemming from its relatively small key size. However, Triple DES was found to be too slow for practical applications.
The Advanced Encryption Standard AES
Hoping for an improvement on the performance of DES and Triple DES, the National Institute of Standards and Technology (NIST) started development of an Advanced Encryption Standard (AES) in 1997. This was to be the symmetric block cipher of choice for the US government in protecting classified information – and one that could be deployed in software and hardware across the world, for encrypting sensitive data.
NIST specified that the algorithm chosen for the AES should be a block cipher capable of handling 128 bit blocks, using keys sized at 128, 192, and 256 bits. It should also be resistant to attack, low-cost in terms of computational power and memory usage (the algorithm itself being released on a global, nonexclusive and royalty-free basis), and able to be deployed on a range of software and hardware platforms.
Fifteen symmetric key algorithm schemes were presented for analysis, from which five finalists were chosen, including:
- MARS, from an IBM Research team
- RC6, from RSA Security
- Rijndael, submitted by Joan Daemen and Vincent Rijmen, two Belgian cryptographers
- Serpent, submitted by Ross Anderson, Eli Biham and Lars Knudsen
- Twofish, submitted by researchers from Counterpane Internet Security
AES uses an iterative model, rather than the Feistel structure. Its basis is a “substitution–permutation network” consisting of a set of linked operations, some replacing inputs with specific outputs (substitution), and others shifting components of the plain text source around (permutation).
AES computations are performed on bytes, rather than bits, with 128 bits of a plain text block being treated as 16 bytes. These 16 bytes may be arranged in four columns and four rows, for processing as a matrix.
The Shift Row Transformation
The matrix function crucial to an AES cipher is known as a shift row transformation. As its name suggests, the function shifts the bytes in each row of a matrix by a certain offset, determined by the encryption algorithm.
For AES, the first row of the matrix is left unchanged. Each byte in the second row is shifted one position to the left. Bytes in the third and fourth rows are shifted by offsets of two and three, respectively. The shifting pattern for blocks of 128 bits and 192 bits is the same, with each row n being shifted left circular by n-1 bytes.
So for a 128-bit block (16 bytes under AES, a four by four matrix), the shift row transformation looks like this:
|1 5 9 13||1 5 9 13|
|2 6 10 14||6 10 14 2|
|3 7 11 15||11 15 3 7|
|4 8 12 16||16 4 8 12|
For 192 bits, the transformation takes this form:
|1 5 9 13 17 21||1 5 9 13 17 21|
|2 6 10 14 18 22||6 10 14 18 22 2|
|3 7 11 15 19 23||11 15 19 23 3 7|
|4 8 12 16 20 24||16 20 24 4 8 12|
The Rijndael Cipher
It was the Rijndael Cipher (whose name derives from the surnames of its creators, Rijmen and Daemen) that was ultimately selected as the basis for the new Advanced Encryption Standard (AES).
The cipher consists of a variable number of rounds: 9 if both the block and key are 128 bits long, and 11 if either the block or the key is 192 bits long, and neither one is longer than that. This doesn’t include an extra round performed at the end of the encryption, with one step omitted.
Rijndael also allows for encryption with 256-bit keys, in which case the shift row transformation looks like this:
|1 5 9 13 17 21 25 29||1 5 9 13 17 21 25 29|
|2 6 10 14 18 22 26 30||6 10 14 18 22 26 30 2|
|3 7 11 15 19 23 27 31||15 19 23 27 31 3 7 11|
|4 8 12 16 20 24 28 32||20 24 28 32 4 8 12 16|
Each regular round involves four steps:
- A Byte Substitution
- The Shift Row transformation
- A Mix Column step, where matrix multiplication is performed
- An Add Round Key, where a logical operation known as XOR is performed
The AES as based on the Rijndael Cipher was adopted as a US federal government standard in 2002, and has since proven to be resistant to most forms of attack targeting it. The exceptions have been “side-channel” attacks focusing on weaknesses found in the implementation or key management of specific encryption products based on AES.
Share this Post