Driven by data; ridden with liberty.
“What is a man? A miserable little pile of secrets”, says Dracula, in the famous game Castlevania: Symphony of the Night. It is a common refrain, usually heard from students of mathematics, that people hate mathematics. However, mathematics often underlies our wondrous world, even the world of secrets.
Cryptography is the process of writing using various methods, called ciphers, to make and keep communications secret. Cryptanalyst is the opposite process: breaking these ciphers to reveal the encoded information. The Caesar cipher is one of the simplest examples of a substitution cipher, used by Roman statesman Julius Caesar in communications with his generals. Substitution ciphers permute each letter of the alphabet to another letter. The Caesar cipher prescribes a set shift along the alphabet. For a shift of three letters rightwards, which was always used by Caesar, ‘CATS’ will be replaced by ‘FDWV’. A famous instance of the Caesar cipher is the name of the computer HAL in the science-fiction film 2001: A Space Odyssey, which is simply IBM shifted leftwards by one letter. The Braille language is also a type of cipher, as was confusingly used in a puzzle in Pokémon Ruby & Sapphire.
Caesar ciphers are dependent on modular arithmetic – the arithmetic of remainders. A common example of modular arithmetic is the 12-hour clock: three hours after eleven o’clock is called two o’clock, as the remainder of 14 divided by 12 is 2. For the standard alphabet, the calculations are done modulo 26. Suppose A is assigned to 0, B assigned to 1 and so on. If Y is represented by 24, and then adding three to this number is 27, which is equal to 1 (modulo 26). This cipher says Y is replaced by B. There are 26 different Caesar ciphers, including the identity cipher which does not shift any letters, and so is not particularly useful for encryption.
An immediate question arises as to how many substitution ciphers there are. These permutations of the 26 letters form what is called a group, because applying one permutation after another yield a further permutation, there is always a permutation that can undo any other given permutation, and the identity permutation – swapping no letters – exists. The size (or order) of a permutation group is the factorial of the number of symbols being swapped: 26!; about four times ten to the power of 26. Another way of thinking about the number of permutations of 26 letters is that it is about half of the approximate diameter of the visible universe in metres.
A second important area for modern encryption is the mathematics of prime numbers. A positive whole number greater than 1 is called prime if its only positive divisors are 1 and itself. Primes are the building block of all numbers, as the Fundamental Theorem of Arithmetic says that a whole number’s factorisation into primes is unique. Public-key encryption systems aim to find a pair of functions, represented by numerical keys, which are inverses of each other. The second function – decryption – should not easily be deduced from the encrypting function. The RSA algorithm, named after Rivest, Shamir and Adelman, is the most celebrated and practical public-key encryption system.
This algorithm works in the modulo arithmetic of two large prime numbers multiplied together; from the observation that multiplying two whole numbers together is easy, but finding a worthwhile factorisation of a whole number is hard. These encryption schemes utilise both Fermat’s Little Theorem and Euler’s Corollary. If Alice sends a message to Bob, using Bob’s public key to encrypt a message expressed as a number. The act of encryption is incredibly simple: raising Alice’s original number to the power of Bob’s public key. To decrypt, Bob raises the received encrypted message to the exponent of his private key, revealing the message in that modular arithmetic.
Mathematics is not only used to encrypt messages, but also to break codes. A substitution cipher can be broken by considering the relative frequencies of each letter. English is not a random series of letters: languages have words and so statistical regularities in the frequency of use of each letter. The article itself contains 3,682 characters (without spaces), where 440 of those characters are the letter ‘e’.
The world is dark and full of secrets, but mathematics is making both the locks and the keys. Lastly, ZTFQB HLTPQ XABKQ OBAFC.
Note: This article was written for bite, bathimpact’s pull-out section, edited by Ben Hooper.