Cryptography is the science of using codes and ciphers to protect messages. And encryption involves encoding messages so that only the intended recipient can understand the meaning of the message. It's often used to protect data in transit.

Encryption is a two way function – that is, you need to be able to undo whatever scrambling you’ve done to the message.

Today, there are two basic types of algorithms — symmetric and asymmetric.

Symmetric algorithms are also known as ‘secret key’ algorithms, and asymmetric algorithms are known as ‘public key’ algorithms.

The key difference between the two is that symmetric algorithms use the same key for encryption and decryption, while asymmetric algorithms use different keys for encryption and decryption.

For a general overview of cryptography and the difference between symmetric and asymmetric ciphers, check out this article.

What Principles are Important When You're Developing a Cipher?

Kerckhoff's principle states that a cryptographic system should be secure, even if all the details (other than the key) are known publicly. Claude Shannon later rewrote this message as 'The enemy knows the system.'

Essentially, a very well designed system should be able to send secret messages even if an attacker can encrypt and decrypt their own messages using the same algorithm (with a different key). The security of the encrypted message should depend entirely on the key.

Additionally, in order to hinder statistical analysis (attempts to break an encryption algorithm), a good cryptographic system should employ the principles of confusion and diffusion.

Confusion requires that the key does not relate to the ciphertext in a simple manner. Each character of the ciphertext should depend on multiple parts of the key. The goal is to make it very difficult for an attacker to determine the key from the ciphertext.

Diffusion means that if a single character of the plaintext is changed, then several characters of the ciphertext should change. And if a single character of the ciphertext is changed, then several characters of the plaintext should change.

Ideally, the relationship between the ciphertext and the plaintext is hidden. No diffusion is perfect (all will have some patterns), but the best diffusion scatters patterns widely, even scrambling several patterns together.

Diffusion makes patterns hard for an attacker to spot, and requires the attacker to have more data in order to mount a successful attack.

If you want to read up on this a bit more, check out A Mathematical Theory of Cryptography.

What are Block and Stream Ciphers?

Both block and stream ciphers are symmetric key ciphers (like DES, RCx, Blowfish, and Rijndael AES). Block ciphers convert plaintext to ciphertext block by block, while stream ciphers convert one byte at a time.

Most modern symmetric algorithms are block ciphers, though the block sizes vary (such as DES (64 bits), AES (128, 192, and 256 bits), and so on).

What is the advantage of a stream cipher?

Stream encryption is faster (linear in time) and constant in space. It is unlikely to propagate errors, as an error in one byte's translation won't impact the next byte.

However, there's little diffusion as one plaintext symbol is directly translated to one ciphertext symbol. Also, the ciphertext is susceptible to insertions or modifications. If an attacker is able to break the algorithm, they may be able to insert text which looks authentic.

You typically use a stream cipher when the amount of plaintext is unknown (like audio or video streaming), or when extreme performance is important (like with very high speed connections, or for devices which need to be very efficient and compact, like smart cards).

A stream cipher works by generating a series of pseudorandom bytes which depend on the key (for any given key, the series of bytes is the same for encryption and decryption). Different keys will produce different strings of bytes.

In order to encrypt data the plaintext bytes are XORed with the string of pseudorandom bytes. To decrypt, the ciphertext is XORed with the same string in order to see the plaintext.

What is the advantage of a block cipher?

A block cipher has high diffusion (information from one plaintext symbol is spread into several cipher-text symbols). It is also fairly difficult for an attacker to insert symbols without detection, because they can't easily insert them into the middle of a block.

However, it is slower than a stream cipher (an entire block needs to be transmitted before encryption/decryption can happen) and if an error does occur, it can propagate throughout the block, corrupting the entire section.

Block ciphers are a better choice when you know the transmission size – such as in file transfer.

What are the common modes of Block Ciphers?

In order to encrypt data which is longer than a single block, there are several 'modes' which have been developed. These describe how to apply the single block principles to longer messages.

There are 5 confidentiality modes for block ciphers. Some of these modes require an initialization vector (IV) in order to function.

What is an Initialization Vector (IV)?

An IV is essentially just another input (in addition to the plaintext and the key) used to create ciphertext. It's a data block, used by several modes of block ciphers to randomize encryption so that different cipher text is created even if the same plain text is repeatedly encrypted.

It usually does not need to be secret, though it cannot be re-used. Ideally, it should be random, unpredictable, and single-use.

Two of the same messages encrypted with the same key, but different IVs, will result in different ciphertext. This makes an attacker's job more difficult.

Electronic Code Book Mode (ECB)

There is a fixed mapping between input blocks of plaintext and output blocks of ciphertext (essentially like an actual code book where ciphertext words directly relate to plaintext words).

ECB applies the cipher function independently to each block of plaintext to encrypt it (and the inverse function to each block of ciphertext to decrypt it). This means that CBC can encrypt and decrypt multiple blocks in parallel (since they don't depend on each other), speeding up the process.

_https://en.wikipedia.org/wiki/Block_cipher_mode_ofoperation

For this mode to work correctly, either the message length needs to be a multiple of the block size or you need to use padding for the length condition to be met.

Padding is essentially extra data that's added in order to ensure that the block size is met. With this mode, given the same key, the same plaintext block will always result in the same ciphertext block. That makes it vulnerable to attack, so this mode is rarely used (and should be avoided).

Cipher Block Chaining Mode (CBC)

This mode 'chains' or combines new plaintext blocks with the previous ciphertext block when encrypting them which requires an IV for the first block. The IV doesn't need to be secret, but it needs to be unpredictable.

CBC exclusive ors (XORs) the first block of plaintext with the IV ciphertext block to create the first ciphertext block. The IV is sent separately as a short message using ECB Mode.

Then, CBC applies the encryption algorithm to the block, creating the first block of ciphertext. CBC then XORs this block with the second plaintext block and the applies the encryption algorithm to produce the second ciphertext block, and so on until the end of the message.

In order to decrypt the message, CBC does the reverse - applies the inverse of the encryption algorithm to the first ciphertext block and then XORs the block with the IV to obtain the first plaintext block.

CBC then applies the inverse of the encryption algorithm to the second ciphertext block and XORs the block with the first ciphertext block to obtain the second plaintext block. This process continues until the message is decrypted.

_https://en.wikipedia.org/wiki/Block_cipher_mode_ofoperation

Because each input block (except the first) relies on the previous block being encrypted, CBC can't perform encryption in parallel. However, since the decryption requires XORing with the (immediately available) ciphertext blocks, it can be done in parallel. CBC is one of the most commonly used modes.

Similarly to ECB, for this mode to work correctly, either the message length needs to be a multiple of the block size or you need to use padding for the length condition to be met.

Cipher Feedback Mode (CFB)

CFB is similar to CBC, but instead of using the entire previous ciphertext block to compute the next block, CFB uses a fraction of the previous block.

CFB starts with an IV of the same block size as expected by the block cipher, and encrypts it with the encryption algorithm.

CFB retains s (significant) bytes from this output and XORs them with s bytes of plaintext to be transmitted.

Then, CFB shifts the IV s bytes to the left, inserting the ciphertext bytes produced by step 2 as the righthand bytes (IV stays the same length).

Then it repeats these steps.

To decrypt a message, CFB uses the IV as the first block and forms each following block by performing step 3 above and applying the encryption algorithm to form blocks. CFB then XORs s bites with the corresponding ciphertext to reveal the plaintext.

Within CFB, the encryption system processes s < b plaintext bits at a time, even though the algorithm itself carries out b-bits to b-bits transformation. This means that s can be any number, including 1 byte and CFP can functionally operate as a stream cipher.

_https://en.wikipedia.org/wiki/Block_cipher_mode_ofoperation

Unfortunately, this means that CFB can propagate errors downstream. If a byte is received with an error, when CFB uses it to decrypt the first byte, it will produce an erroneous decryption, causing downstream errors when fed back into the decryption.

Like CBC, when CFB encrypts, the input to each round relies on the result of the previous round, meaning that encryption cannot be done in parallel, though decryption can be performed in parallel if the input blocks are first created from the IV and ciphertext.

Output Feedback (OFB)

OFB is similar to CFB, but instead of processing s < b bits into a b-bits to b-bits transformation, it processes s bits directly. Similarly to CFB, OFB can be functionally used as a stream cipher.

OFB requires that the IV be a unique nonce (number used once) for each execution with a given key.

First, OFB encrypts the IV with the encryption algorithm, to produce an output block. OFB then XORs this block with the first plaintext block, producing the first ciphertext block.

OFB encrypts the first output block with the encryption algorithm to produce the second output block. It then XORs this block with the second plaintext block to produce the second ciphertext block. OFB repeats this process for the length of the message.

_https://en.wikipedia.org/wiki/Block_cipher_mode_ofoperation

When decrypting, OFB encrypts the IV with the encryption algorithm, producing an output block. OFB then XORs this block with the first ciphertext block, recovering the first plaintext block.

OFB encrypts the first output block with the encryption algorithm to produce the second output block. OFB then XORs it with the second ciphertext block to recover the second plaintext block. OFB repeats this process for the length of the message.

Because the output blocks for decryption are locally generated, OFB is more resistant to transmission errors than CFB.

Counter (CTR)

CTR applies the encryption algorithm to a set of unique input blocks (counters) in order to produce outputs which are XORed with the plaintext to produce ciphertext.

CTR encrypts the first counter with the encryption algorithm, then XORs the resulting output with the first plaintext block to produce the first ciphertext block. CTR repeats this for each block (with a new counter – counters must be unique across all messages encrypted using a single key).

If the final block is a partial block of s bytes, the most significant bits, s, of the output block are used for the XOR, while the b - s bytes of the output block are discarded.

_https://en.wikipedia.org/wiki/Block_cipher_mode_ofoperation

The decryption follows the same pattern. CTR encrypts the counter with the encryption algorithm, then XORs the output with the corresponding ciphertext block to produce the plaintext block.

If the final block is a partial block of s bytes, the most significant bits, s, of the output block are used for the XOR, while the b - s bytes of the output block are discarded.

CTR has been shown to be at least as secure as the other four modes, while also being able to be executed in parallel (both encryption and decryption), meaning that it is very fast.

Each block can be recovered independently if its counter block can be determined and the encryption can be applied to the counters in advance of receiving the plaintext or ciphertext (if memory is no constraint).

Further Reading: NIST Recommendation for Block Cipher Modes of Operation

How do Attackers Attempt to Break Ciphers?

There are a number of techniques attackers use, but they broadly fall into the following categories of attack, based on information required to carry it out.

This isn't an exhaustive list (there are other attacks such side channel attacks), but many of the most common fall into one of these categories.

Known Ciphertext Attack

An attacker has some ciphertext, but does not know what plaintext was used to generate this ciphertext. The attacker does not get to choose which ciphertext they have and they cannot obtain/produce more.

This is the easiest type of attack to try, since it's easiest to eavesdrop on an encrypted conversation (since presumably the people having the conversation are using strong encryption and aren't as worried about eavesdroppers). But it's the hardest to be successful, as long as the people sending messages used appropriately strong encryption.

_For example: David finds an encrypted message (ciphertext) in a dead drop, but has no idea what the message means._

Known Plaintext Attack

An attacker has some plaintext and ciphertext pairs which they didn't choose (so the attacker didn't choose the message that was encrypted, but was able to successfully steal a plaintext message and its associated ciphertext). The attacker cannot obtain/produce more pairs.

For example: David finds an enemy spy's hiding place and interrupts him while he is sending an encrypted message. The spy is silly enough to have fled, leaving both the plaintext message and its associated ciphertext written down.

Chosen Plaintext Attack

An attacker can choose any plaintext and obtain the ciphertext in return (but they can't see the key itself).

This is further broken down into batch chosen plaintext (where the attacker can submit a set of plaintexts and receive the ciphertext, but cannot do so again) and adaptive chosen-plaintext (where the attacker can submit plaintext, receive the ciphertext and submit additional plaintext based on the previous ciphertext.)

For example: One nation-state is eavesdropping on another's encrypted communication and knows they use the same key for all of their encryption. They send a sensitive diplomatic communication to the other nation-state, knowing it will be transmitted via the encrypted channel, thus giving them a chosen plaintext - ciphertext pair.

Chosen Ciphertext Attack

This is the opposite of the last attack, where the attacker can choose any ciphertext and obtain the plaintext in return (but they can't see the key itself).

For example: David knows an enemy spy is going to send an encrypted message tomorrow, so he replaces the text with his own chosen ciphertext, then spies on the recipient, listening as they read out the plaintext of the message.

Sources/Further Reading:

• NIST Recommendations for Block Cipher Modes of Operation
• Diffusion and Confusion
• Confusion and Diffusion
• Kerckhoffs's Principle
• Padding Mechanisms
• Foundations of Computer Science: Stream and Block Encryption

All around us data is transferred faster than ever. Sensitive data is also part of our everyday life. To protect that data, we use encryption. When we encrypt data, it changes in some way that renders it useless to the possible viewer, but that can be changed back to its original state when it arrives safely to the meant receiver. These transformations rely heavily on math, and particularly on a field of math called number theory. This text takes us through the basics of cryptography both from a mathematical perspective and as a programming matter.

Ciphers Yesterday and Today

For as long as writing has existed, the concept of encryption has lived and developed alongside the plain text writing. The idea of rendering text seemingly incomprehensible for purposes of guarding a secret has been central especially in military use and politics. The word cipher originates from the medieval times, from words such as the latin cifra and Arabic صفر (sifr), which means “zero”. There are numerous theories on why zero would have been used to describe encryption, including that the concept of zero was not part of the roman number system and seen as a mystery among numbers. One of the oldest and most widely known ciphers used in military context is Caesars cipher, also known as Caesars shift.

Caesars Shift in Python3.

Caesars shift takes one key, which is used to shift each character in the plaintext. This single key is the weakness of the cipher: once the correct shift is figured out, the whole message is revealed. Mathematically, this type of cipher can be written as a problem in modular arithmetic, which works with values wrapped up in a specific range. We’ll discuss this in more depth later.

Shift encryption and decryption as modular arithmetic using a 26-letter alphabet.

The way we can solve the plaintext from the encrypted text is by finding the key. In the case of a Caesars cipher of value 3, finding out the key (3) lets us decrypt the whole text in one chunk. The key specifies the output of the encryption algorithm.

Factors and Primes

Perhaps surprisingly, one of the foundational concepts that lays the ground for encryption is that of divisibility. To define what it means, let’s lay down some rules. Firstly, if we have a and b that are integers and a is not 0, a divides b if there is such an integer k that satisfies the following statement.

A is a factor of b.

In case we find an integer which is larger than 1 and that does not have other positive factors than 1 and itself, we call it a prime. Integers larger than one which are not primes are known as composite numbers, due to their composed nature. For example, 4 is larger than 1 and it has a factor 2. Hence, it is a composite. On the other hand, 3 is an integer larger than one, but it does not have any other positive factors than 1 and itself. It is a prime. Other small primes are 2, 5, 7, 11 and 13.

According to the fundamental theorem of arithmetic, every integer larger than 1 can be written as an unique product of primes. This is good news for cryptographers, since they love working with primes. Why would that be? Well, one of the most straightforward reasons is that prime factorisation of large numbers takes up a lot of time. Many well known encryption systems such as RSA is fully based on this fact. The principal it works on is that there exists a public key (a product of two large primes) which is used to encrypt the message, and a secret key (containing those primes) which is used to decrypt the message. These primes are usually around 300 digits long.

A Matter of Congruence

Modularity is one of the foundational pillars of cryptography. Let’s approach this concept first from a perspective of division. What happens if we have 5 small candies and three students? Each student gets a candy, and 2 remain. This can be described as the following.

R is the remainder of a when divided by n.

Can you find the other amounts of candies which leave 2 as a remainder when divided to the 3 students? The next amount would be 8, since each student would get two candies and again 2 would be left over. This can be described using congruence. 8 and 5 are congruent is modulo 3, meaning that they leave the same remainder when divided by 3.

5 is congruent to 8 in modulo 3.

In the example of Caesars shift, we use an alphabet that consists of 26 letters. We only work with those 26 values. After ‘Z’, we go back to ‘A’. This is modularity in practice. ‘A’ will always be at position 1 in our 26-letter list, so any count of position we get, if we divide it by 26 and the remainder is 1, we know to use ‘A’. This wraps up our numbers into a finite field, in which the largest value is 26. In practice, if my secret message would be ‘ABC’, I would first convert this to the numbers 123. After that, I would apply the shift. In case the key would be 3, the shift would produce 456. After this, I would point the numbers back to their letter representations, which are in the class of modulo 26. The encrypted message becomes ‘DEF’.

Again, encryption and decryption as modular arithmetic using a 26-letter alphabet.

You can think of this like a clock. When the arrow has gone around the clock, it ends up where it started. In modular arithmetics, the last integer is followed by the first. Another way to understand this is that the world of a specific modulo, only that amount of values exist. For example in modulo 2, only 2 values exist. In our alphabet, 26 values exist, and so on.

Types of Ciphers

What kind of keys a cipher uses can be used to categorise the cipher into asymmetric and symmetric keys. They differ in the question of which key is used for encryption and decryption. Symmetric ciphers are encrypted and decrypted using the same key (such as Caesars Cipher). Asymmetric key ciphers are decrypted with a different key than they are created with, such as the RSA encryption system which we briefly discussed earlier. This results in a longer time for creating the encryption, but the result is also much more secure.

Another way to categorise ciphers is by their way of operating in streams or blocks. Stream ciphers are symmetric key ciphers that operate on continuous streams of symbols. For example the encryptions used in Bluetooth is a stream cipher. Needless to say, in the age of wireless communication with a need for encryption, stream ciphers have become a vital part of mobile technology.

A Look at Stream Ciphers

Remember that we discussed the concept of modular arithmetic earlier? In short, modular arithmetics are arithmetics in a finite field. Now, let’s take a look at another cipher that works with a finite field of values (also known as a Galois field). This cipher, however, does not always produce the same values given the same input, like shifting does. Its purpose is to produce a stream of keys used to encrypt another stream. Like a snake eating its own tail (a symbol often used for eternity), linear feedback shift registers work by feeding on their own output. They are constructed in a way that makes them endlessly cycle through a pattern of values while outputting that seemingly random pattern. The seed and all the outputted values are binary, meaning they get values 0 or 1. The way new values are created is by using a logical operator, usually exclusive or (XOR).

Logical Gate XOR.

To describe this in a practical way, lets start looking at what we need to create a LFSR. We need a seed, which is a list of ones and zeros. The seed will be what we start shifting. In addition to our seed (or shift register) we have a collection of taps. The taps tell us which parts of the register we use when feeding back into it. Say that we have a seed 001 and two taps, 1 and 3. This means that when we start shifting, the new value will be a combination of the first and third numbers of the seed, 0 and 1. We use an operation called exclusive or to combine the two. 0 xor 1 gives 1. Since we are working with binary values, the feedback from our taps can be expressed as a polynomial in modulo 2.

The feedback polynomial from taps 3 and 1.

So, if our shift register is 001 and we get a new value, 1, we insert it in the beginning and drop the last number out. Our new shift register state is now 100. We continue this shifting until we notice that our shift register has returned to it’s initial state, 001. Depending on the seed and taps we select, we can get loops of different lengths. A loop is called maximal length if it passes through all possible different combinations before reaching its original state. Since we’re using the binary system, the maximal length of a loop will be 2^n-1. The loop can also end up leaving its original state and getting stuck in a shorter loop within, never returning to its original state. Finding the seeds and taps that lead to a maximal-length cycle is essential. Some of the criterions for finding these taps is that the number of taps must be even and that the taps are setwise co-primes, meaning that they have no common divisor except 1.

Wait, that doesn’t seem so random! Wouldn’t a cycle like that be pretty easy to crack? The thing about shift registers is that they get pretty long, pretty quickly. Say we choose a seed of 20 bits and a tap of two values, 2 and 19. The length of the loop produced is 1 048 575, meaning we would get quite a large amount of seemingly random binary values.

Linear Feedback Shift Register in Python3.

The flavour of LFSR we have briefly gone through is called Fibonacci LFSR. There are also other variations, in which the way the register is shifted differs. They all work to produce a pseudorandom stream of bits used to encrypt streams. The range of applications for this type of encryption ranges from bluetooth to GSM (cellphone communication) standards.

In Conclusion

As a programmer, learning about the concept of modular arithmetics and division opens new ways in thinking about everyday coding problems. However, in security-critical projects using ready-made systems and standards for encryption is always recommended, since specialists in the field of cryptography probably find a safer and more effective solution than an enthusiastic hobbyist.

Sources:

Algebraic Structures in Cryptography by V. Niemi

Tutorial on Linear Feedback Shift Registers by EETimes

Encyclopedia of Cryptography and Security by Anne Canteout