NOTE - These HTML formatted notes are significantly outdated, contain various errors now corrected, and are replaced by the current OpenOffice/PDF/Powerpoint versions. The reason for keeping this version on the site is because many relevant articles are linked directly from this version.
Cryptography is a complex subject. So in order better to understand what it is now, let's start at the beginning and see how it developed.
Many children have played games using the Ceasar Cipher. This is a simple substitution cipher. Each letter in the message is substituted within the alphabet by a fixed number of positions. ROT1 means that a is changed for b, b is changed for c etc, until z is changed for a. The message HAL becomes IBM.
In order to decrypt a Ceasar Cipher, the rotation is reversed, so that b becomes a, c becomes b etc. Of course we are not restricted to using a key of 1. If we use a key of 2, during encryption a becomes c, b becomes d etc, y becomes a and z becomes b. Using a Ceasar Cipher with a key of 2 is called ROT2. 26 rotations exist, but ROT0 is a null cypher in the sense that the plaintext and cryptotexts are the same.
The advantage of having program source code is that we can experiment in a way that cuts out the manual effort.
A suitable programming language for study and experimentation purposes is Python due to its relative simplicity and ease of use. Here is an implementation of the Caesar Cipher in Python.
The programming style used by many leading Pythonistas generally involves hard coding test cases. This makes it easier to improve a program and to retest all existing components with minimum effort. The test cases also help those developing applications which use a set of library classes and functions by providing suitable examples.
def test(case="caesar"):
# test plan consisting of a number of cases
if(case == "caesar"):
key=17
plaintext="this is a message"
cryptotext=caesar(plaintext,key)
decrypt=caesar(cryptotext,key,decrypt=True)
print "plaintext: "+plaintext
print "cryptotext: "+cryptotext
print "decrypt: "+decrypt
rich@saturn:~/devel/cipher$ python Python 2.4.4c1 (#2, Oct 11 2006, 21:51:02) [GCC 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> import ciph >>> ciph.test() plaintext: this is a message cryptotext: kyzj zj r dvjjrxv decrypt: this is a message >>>
The fact that the decrypt operation reverses the encrypt operation and uses the same key makes the Caesar Cypher symmetrical.
We obviously wouldn't use this one for more than kids games, but how to break it shows us the beginnings of cryptanalysis.
For trivial ciphers like this one, the brute force cracking approach could involve ciphertexts being decrypted for all possible keys and checked manually for readability. For ciphers involving more keys than for which manual checking of all decrypts is feasible, the decrypts could be automatically scanned against spelling dictionaries containing language words likely to be present in the plaintext.
Developing an automated checker is left as an exercise for students.
The obvious problem with the Caesar Cipher is that the range of possible keys is trivially small. Let's suppose we don't have to rotate each letter by the same amount. This could give us a substitution table as in the following program generated example:
>>> import ciph
>>> ciph.test("gen_subst_key")
abcdefghijklmnopqrstuvwxyz
lqrzoghnfwybuitdepacxjmvks
Here I wrote a function that generated a substitution cipher key so that a in the plaintext is substituted by l in the ciphertext, b in the plaintext is substituted by q in the ciphertext etc. The program I used to generate this key made sure that the substitution key contains every letter in the alphabet exactly once. The encryption key is the 26 character string:
lqrzoghnfwybuitdepacxjmvks
How many possible values for this key are there ? If a letter is allowed to substitute as itself, there are 26 possible substitutes for a, 25 for b and 1 for z: 26 x 25 x 24 ... x 1 or factorial(26) which gives: 403291461126605635584000000 possible values. This is the number of possible ordered permutations of the set of all characters in the range a-z. In practice I am going to use factorial(25) possible keys, because it might not be a good idea to allow a character to substitute for itself.
Generating a valid key as in the above example needed a little more coding than the cipher itself.
This doesn't guarantee that z will substitute to a different letter, but does guarantee all other letters will. Modifying this code to remove this bug by testing the value given to z and swapping this with another letter if it does map itself to avoid this problem is left as an exercise for the reader.
elif case == "gen_subst_key":
print alphabet
print gen_subst_key()
test case: gen_subst_key abcdefghijklmnopqrstuvwxyz nofgvuadhlreywpcsqtmbkxjiz press enter to continue
elif case == "subst":
key=gen_subst_key()
plaintext="the quick brown fox jumps over the lazy dog"
ciphertext=subst(plaintext,key)
decrypt=subst(ciphertext,key,decrypt=True)
print "key: "+key
print "plaintext: "+plaintext
print "ciphertext: "+ciphertext
print "decrypt: "+decrypt
test case: subst key: rslwjpobnydkhauxcmivtgzefq plaintext: the quick brown fox jumps over the lazy dog ciphertext: vbj ctnld smuza pue ythxi ugjm vbj krqf wuo decrypt: the quick brown fox jumps over the lazy dog press enter to continue
This approach is stronger than the Caesar cipher in the sense that there is a very much greater number of possible keys. Of course a 26 character key is harder to remember. Any single letter substition cipher is going to be vulnerable to letter frequency analysis. In the English language, letters 't' and 'e' occur more frequently than letters 'q' and 'z'. An attacker having access to enough cryptotext can work out its letter frequency and start making guesses, starting with the cryptotext letters that occur most or least often.
You might want to include punctuation within the alphabet or better still get rid of punctation altogether by compressing the input message. Or you might consider treating the alphabet as being all possible values for an 8 bit byte. Compressing the input gives you the advantage of balancing the plaintext letter frequency. The fact that the letter 'r' occurs on its own in the cryptotext above gives the game away as the only single letter word in English is 'a'. Without input compression, the character frequency attack still exists, in the sense that each input plaintext character still substitutes for the same output ciphertext character. The above approach also still suffers from the weakness of allowing punctuation to go straight through unchanged from the plaintext to the ciphertext.
In the substitution ciphers described above, the encoded information for each letter in the plaintext was contained within its own position within the ciphertext. In a transposition cipher, the positions of letters are swapped for each other based on the key. A trivial example of a transposition cipher might swap letters with odd and even positions with each other.
Plaintext: this is a message Ciphertext: htsii s aemssga e
Of course just swapping odd and even positions in blocks of 2 is weak, but this illustrates the concept. Also, punctuation if included within the plaintext, has to be handled as part of the encrypted message. Decryption simply involves reversing the swaps. Another feature of this is that because the plaintext had a message size of 17, which was not a multiple of the blocksize, which is 2, the message had to be padded with an extra space prior to encryption, so that the message to be encrypted would be an exact multiple of the blocksize.
In our general purpose substitution cipher our key was effectively a substitution table, giving a replacement for each character in our alphabet, such that every replacement character was used to replace exactly one letter in the alphabet, so that no information would be lost during a complete encrypt decrypt cycle. If during encryption, a single replacement letter had been used for more than one plaintext letter, then decryption could not have been done without losing some of the letters in the original message.
If we construct a replacement table showing for each block of plaintext characters the positions these are swapped into, and each from and to positions are used exactly once, this transposition will also not lose any information and is reversible. Let's suppose we count the positions in each block 0-9 and use blocks of 10 characters. This gives us 10 x 9 x 8 ... x 1 possible keys which is factorial(10) or 3628800. In practice to avoid characters replacing themselves you would use factorial(9) possible keys. This is the number of possible ordered permutations of the set of numerals 0-9.
In a production environment we might be better off using a larger block size, but having a numeric key with 10 digits makes this easier to process and see what is happening for now, as the decimal digits in this key gives us the transposition table directly. Also to avoid the end of the message being more obvious, and this making the key easier to discover, we are going to transfer the message size along with the ciphertext, and pad the message with random characters to an exact multiple of the blocksize before encryption. Using the message size, we will be able to strip the extra padding following decryption.
elif case == "gen_transp_key":
blockpos="0123456789"
print blockpos
print gen_transp_key()
test case: gen_transp_key 0123456789 4670281539 press enter to continue
elif case == "pad":
message="this is a message not of multiple 10"
padmessage=pad(message,10,len(message))
stripmessage=pad(padmessage,10,len(message),pad=False)
print "message: "+message
print "length of message: "+str(len(message))
print "padmessage: "+padmessage
print "stripmessage: "+stripmessage
test case: pad message: this is a message not of multiple 10 length of message: 36 padmessage: this is a message not of multiple 10gryj stripmessage: this is a message not of multiple 10
elif case == "trans":
plaintext="prime numbers may contain the secrets of the universe"
key=gen_transp_key()
padplain=pad(plaintext,10,len(plaintext))
ciphertext=trans(padplain,key)
decryptpad=trans(ciphertext,key,decrypt=True)
decrypt=pad(decryptpad,10,len(plaintext),pad=False)
print "key: "+key
print "plaintext: "+plaintext
print "length of plaintext: "+str(len(plaintext))
print "padplain: "+padplain
print "ciphertext: "+ciphertext
print "decryptpad: "+decryptpad
print "decrypt: "+decrypt
test case: trans key: 3905871624 plaintext: prime numbers may contain the secrets of the universe length of plaintext: 53 padplain: prime numbers may contain the secrets of the universepzhvhih ciphertext: mbp murnie oeac rysmi n ehttanrfsto esceee uvitnh phrhihsvez decryptpad: prime numbers may contain the secrets of the universepzhvhih decrypt: prime numbers may contain the secrets of the universe
elif case == "block":
# generate combined key
skey=gen_subst_key()
tkey=gen_transp_key()
key=skey+","+tkey
plaintext="the quick brown fox jumps over the lazy dog"
ciphertext=block(plaintext,key)
decrypt=block(ciphertext,key,decrypt=True)
print "key: "+key
print "plaintext: "+plaintext
print "ciphertext: "+ciphertext
print "decrypt: "+decrypt
test case: block key: qiacyjnohkzuftmreslvwdxgbp,2739185406 plaintext: the quick brown fox jumps over the lazy dog ciphertext: 43,ya ozwevhmmx sg tijfdrswy lkmopy vbu qnvqlmfzace decrypt: the quick brown fox jumps over the lazy dog
The program snippets described above are downloadable. Students are encouraged to download and run this program during a tutorial session.
Just because the ciphers combined above would be difficult to decrypt manually without knowing the key doesn't mean a computer cracking program couldn't make very short work of them. Unfortunately there is too much of this kind of software being sold whose distributors seem to have little idea of the risks being taken and who manage to persuade naive customers that this kind of toy can be used for protecting confidential information. If this particular crypto learning toolkit encourages you to develop a program which automatically cracks the ciphertext and uncovers the key, or which exploits some of the weaknesses in the key generation algorithms, do please let me know.
A. If very few people use a program that implements a particular algorithm, it might be possible to keep this a secret. However, if just one copy of a program that implements this algorithm gets into the hands of an determined attacker, then every instance of this program would then be compromised, if the security of the system doesn't depend upon other secrets, i.e. the encryption/decryption keys.
It is obviously a lot cheaper to change the key if a key is disclosed or lost, than to install new software or cryptographic hardware every time one instance of a program or machine in wide use is obtained by an attacker. The fact that reverse engineering is possible makes it unwise to rely on the secrecy of the algorithm to protect the secrecy of messages encrypted using this algorithm.
A. Firstly this presumes that an attacker can't obtain an instance or couldn't reverse engineer one if he did obtain one.
A more serious problem is that the users of a system which has not yet been cracked can never be sure about how easy or difficult it might be to crack it, and a system that has been cracked isn't useful. Even if all the world's best cryptanalytic talent tries their hand at cracking a system and honestly report that they have not yet succeeded, this still doesn't guarantee that noone else will try their hand at cracking this system and succeed where others have failed.
The level of confidence that can be obtained in a system is dependent upon the amount of talent unsuccessfully directed towards trying to break it so far. If an algorithm is successfully kept secret this reduces the critical review of this system, which reduces the level of confidence anyone can objectively have in it.
For futher reading see Kerckhoffs' principle.
This approach to cryptography is very simple, and in some contexts provably secure. The idea is that the key has the same length as the plaintext. The key must never be reused. If the key is entirely random, it can be used to encrypt the plaintext, e.g. by combining the key and plaintext using a bitwise sequence of XOR (exclusive OR) boolean operations. The message recipient, if able to XOR the key material with the ciphertext in the same sequence as it was combined, is able to recover the plaintext.
| plaintext bits | 1 | 0 | 1 | 0 |
| key bits | 0 | 0 | 1 | 1 |
| ciphertext bits | 1 | 0 | 0 | 1 |
| decrypt bits | 1 | 0 | 1 | 0 |
In practice the need to use the key once and once only, to destroy the key securely after use and to have the same quantity of key material available as messages to be transmitted shifts the security requirement from keeping the message transmission channel secret to keeping the key distribution channel as well as all points of key storage secret. In most situations this doesn't give any useful security advantage. This technique might be used in situations where opportunites exist securely to transfer key material between secure storage locations in one direction, e.g. between a government and one of its embassies abroad, where urgent messages may need transmitting in the opposite direction using an insecure channel when no trusted courier is available, or more quickly than the courier can travel.
The idea of a stream cipher arises from the need to use communications channels in such a manner that the optimal packet sizes within the communication channel do not correspond to multiples of the block cipher blocksize. The way in which a particular bit sent to the communications channel is encrypted will depend upon how previous bits were encrypted. In this sense, a stream cipher might be considered stateful. One approach is for a random nonce (number used once) to be appended to a timestamp and hashed together with a shared secret key at both ends of the communications channel.
This hash value can then be used to seed a cryptographically strong pseudo-random number generator, based on the use of a block cipher. The pseudo random number sequence could then be used to encrypt and decrypt the message stream in a manner similar to the one-time pad.
This block cipher has been in use since the 1970ies, having been approved as a US Federal Information Processing Standard in 1976. It uses a 56 bit key and 64 bit message blocks. Internaly DES uses a Feistel network which has the advantage of using the same permutation and shuffling algorithms in the encrypt and decrypt stages, but with the subkey sequences reversed. This makes building custom DES hardware relatively cheap, and makes DES software simpler to program and validate.
DES is no longer considered secure against attack using a moderate sized network of modern computers. The Electronic Freedom Foundation built custom hardware in 1998 for $250,000 which could brute force DES in a few days. More recently it was discovered that minor changes to the DES design would have made it much less resistant to differential cryptanalysis which implies that this technique of code breaking was known about at the time DES was designed.
AES was developed in the late 1990ies and became a standard in 2002. It uses a 128 bit blocksize and a keysize of either 128 or 192 or 256 bits, involving 10, 12 or 14 rounds, or stages of encryption or decryption respectively. AES which is also known as Rijndael, uses a substitution permutation network.