Breaking Cryptosystems

Some useful preliminaries

An important objective of this course is to explain cryptography without the need for skills in mathematics. However, there are some very basic pieces of notation and terminology that we will need.

Binary numbers

It’s important to realize that although some historical encryption algorithms operate on letters of the alphabet, ‘real’ cryptographic algorithms are all designed to run on computers and thus process information (including plaintexts, ciphertexts, and cryptographic keys) as binary data consisting of zeros and ones. Individual zeros and ones are conventionally referred to as bits, and groups of eight bits are referred to as bytes.

For much of our discussion, we can probably get away with just considering binary data as sequences of zeros and ones. However, it’s important to note that a sequence (sometimes referred to as a string) of zeros and ones such as 1101001 can represent a binary number. A full explanation of binary numbers and how they relate to the more familiar decimal numbers is provided in the appendix. This also includes an explanation of hex, which is most useful to us as a compact way of representing binary numbers.

XOR

Modern symmetric cryptographic algorithms process binary data by conducting various different operations on the data. One common operation is to compute the exclusive or, better known as XOR, of two binary strings (numbers). This is essentially the equivalent of ‘addition’ for binary numbers but without a carry. Thus, every time we refer to the binary operation XOR, it’s reasonable to interpret this as ‘adding’ the two binary strings together. When we refer to this operation in text, we use the term XOR, but when we write XOR in mathematical notation, we commonly use the symbol $\oplus$ (which itself indicates that we are conducting a type of ‘addition’).

When used to combine single binary digits, XOR takes two bits as input and results in a third bit. The result is calculated according to the following rules: