Cryptography and Functions
In this post I will introduce functions using cryptography to motivate the definition of functions. We often think of functions as being synonymous with polynomials, trig functions etc as these are generally the function examples we encounter in introductory math classes. Thus, it can be difficult to make the transition to thinking of functions as relations between sets.
However, cryptography provides an interesting example of functions begin used in this more general manner with real world applications. Here we will define substitution ciphers as a method of introducing functions.
In cryptography we want to encode a message written in plain text into a cipher text version which conceals the meaning to an adversary if it should fall into their hands. When the intended recipient receives the message they should be able to reverse the encoding process and receive the plain text.
To give a concrete example consider that you are a radio operator in Great Britain during World War II. You have received a piece of intelligence that a ship convoy is headed directly towards a section of German U-boats. You need to pass a message to the convoy to change routes. The catch is that the German U-boats will also be able to hear your message as you send it. Therefore you need to encode your message. Luckily, before the ship convoy left you worked out a cryptographic scheme just for this purpose.
A function is a mapping between two sets where for every input the function produces a single output. This is one of the requirements for a cipher, each plain text message should yield a single cipher message once we encrypt it.
If we had some ambiguity in this process say the message “change your route you are headed for three u-boats” encrypted to “glerki csyv vsyxi csy evi liehih jsv xlvii y-fsexw” or “ejcpig aqwt tqwvg aqw ctg jgcfgf hqt vjtgg w-dqcvu” then it is unclear which of these options we should send and the poor ships would have no idea which of the two we picked. This requirement means our cipher should be a function.
Thinking about the ship’s captain who needs to decode our message brings up an additional requirement on the nature of our function: each plain text message should map to a unique cipher text. Otherwise our receiving ship will be faced with a dilemma again when they go to decode the message. Now when they decode the message they will have more than one option again with no way of knowing which message was the one intended!
In mathematical terms this is a requirement that our cipher is and one to one (1-1) function. Meaning each input is mapped to a unique value. In a mathematical prospective this allows our function to be invertible. Therefore, decoding the message is an example of using an inverse function.
A simple method of encrypting these messages is a substitution cipher. This method just maps each character in the plain text message to a different character. The diagram below (taken from wikipedia) shows this process graphically.
A simple version of this is to just shift the characters by some fixed amount in the alphabet. This can be represented by two wheels of characters an outside ring which gives the plain text letter and the inside ring which can be rotated around to create new ciphers.
To encode a message you replace the letter on the outside ring with the inner ring letter which is aligned with it. When the message is decoded the receiver pulls out a Caesar cipher ring and rotates it to the correct position (they have to know this in advance). They now read through the message replacing each on the inner ring with the aligned letter on the outer ring.
This is a very ancient idea and was used by Julius Caesar to encode his messages sent across the Roman Empire! For this reason these ciphers are called Caesar ciphers.
These days we don’t need a handy Caesar Cipher ring to perform this process as it is easy enough to have a computer perform this process. The below python code will cipher a plain text message using a Caesar Cipher to encode the text.
import sys def encode(k, plaintext): """Pass in an integer rotation key k and a plain text message and this function will return a Caesar cipher encoding of the message""" k=int(k) alphabet = list('abcdefghijklmnopqrstuvwxyz') cipher = '' for c in plaintext: if c.lower() in alphabet: cipher += alphabet[(alphabet.index(c.lower())+k)%(len(alphabet))] else: cipher+=c #if the character isnt in the alphabet above then dont change it print 'Your encrypted message is: ' + cipher return(cipher) def decode(k, ciphertext): """Pass in an integer rotation key k and a ciphertext message and this function will return the plain text message""" k=int(k) alphabet = list('abcdefghijklmnopqrstuvwxyz') plaintext = '' for c in ciphertext: if c.lower() in alphabet: plaintext += alphabet[(alphabet.index(c.lower())-k)%(len(alphabet))] else: plaintext+=c #if the character isnt in the alphabet above then dont change it print 'Your decrypted message is: ' + plaintext return(plaintext) if __name__ == "__main__": plaintext = list(raw_input('Enter message: ')) ciphertext=encode(2, plaintext) decode(2,ciphertext)
Breaking the Caesar Cipher
The Caesar cipher provided a reasonably secure form of communication in the ancient world, perhaps because the majority of Rome’s enemies were illiterate or would assume the coded message was written in a language they didn’t know. However, if you suspect the message is encoded using a Caesar cipher you can check each of the 25 possible rotations systematically to see if any of the messages convert to a plain text message which makes sense. This would have be difficult to check in the ancient world but with the advent of computers we can perform this task in a matter of seconds. The simple python script below can be used to break our Caesar cipher:
def breakCode(ciphertext): """Give this an encrypted message and this will print out all possible Caesar ciphers""" for k in range(26): alphabet = list('abcdefghijklmnopqrstuvwxyz') plaintext = '' for c in ciphertext: if c.lower() in alphabet: plaintext += alphabet[(alphabet.index(c.lower())-k)%(len(alphabet))] else: plaintext+=c #if the character isnt in the alphabet above then dont change it print k,plaintext
The output of this program if we encrypted the message “The Germans are coming!” with a key (number of rotations of 2) is shown below:
0 vjg igtocpu ctg eqokpi!
1 uif hfsnbot bsf dpnjoh!
2 the germans are coming!
3 sgd fdqlzmr zqd bnlhmf!
4 rfc ecpkylq ypc amkgle!
5 qeb dbojxkp xob zljfkd!
6 pda caniwjo wna ykiejc!
7 ocz bzmhvin vmz xjhdib!
8 nby aylguhm uly wigcha!
9 max zxkftgl tkx vhfbgz!
10 lzw ywjesfk sjw ugeafy!
11 kyv xvidrej riv tfdzex!
12 jxu wuhcqdi qhu secydw!
13 iwt vtgbpch pgt rdbxcv!
14 hvs usfaobg ofs qcawbu!
15 gur treznaf ner pbzvat!
16 ftq sqdymze mdq oayuzs!
17 esp rpcxlyd lcp nzxtyr!
18 dro qobwkxc kbo mywsxq!
19 cqn pnavjwb jan lxvrwp!
20 bpm omzuiva izm kwuqvo!
21 aol nlythuz hyl jvtpun!
22 znk mkxsgty gxk iusotm!
23 ymj ljwrfsx fwj htrnsl!
24 xli kivqerw evi gsqmrk!
25 wkh jhupdqv duh frplqj!
This illustrates the cat and mouse game which is cryptography. Most codes in use today are theoretically breakable but are what is called computationally secure — they would take a unrealistic amount of computing power to crack them. However, as technology improves their is a constant need for new ciphers which can keep just ahead of the technological advances of our adversaries.