Classical Cryptography
Classical Cryptography
This section will provide some examples of how to write classical ciphers using Python and Sage.
Useful Functions
Here we will describe several useful functions used by several of the classical cipher implementations.
Built-in Functions
There are two important functions that will be used throughout these examples ord and chr. ord takes a character as a parameter and returns an integer representing the ascii value of that character. chr takes an integer value in the range (0,256) and returns the character with that ascii value.
Blocked Strings
When encrypting text it is common to print the ciphertext in 5 letter blocks so as not to give away word length. The function blockedString takes a string and returns that string divided up into blocks of the size specified.
Code:
def blockedString(string,blockLength):
blocked = ""
i = 1
for cur in string:
if cur.isalpha():
blocked += cur
if i % blockLength == 0:
blocked += " "
i += 1
return blocked
Usage:
blockedString( 'hello world', 2 )
Output:
'he ll ow or ld '
Removing Non Alpha Characters
Often it is necessary to remove any punctuation or non-alpha characters from a message before performing encryption. The function removeNonAlpha takes a string and returns the string with all non-alpha characters removed.
Code:
def removeNonAlpha(mesg):
newMesg = ""
for letter in mesg:
if letter.isalpha():
newMesg += letter
return newMesg
Caesar Cipher
A Caesar Cipher is a simple cipher that works be shifting the letters of a message over by a certain shift value. The shift value then acts as the key to be used in decrypting the message.
Here a Caesar Cipher implementation for Sage:
#Class to perform caesar cypher
#Encryption and Decryption
class CaesarCypher:
def __init__(self,shift):
self.__shiftAmt = shift
self.__blockLength = 5
def __shift(self,letter,amt):
return chr( ( ( ord(letter) - ord('A') + amt) ) % 26 + ord('A') )
def __shiftString(self,mesg,amt):
shifted = ""
for i in mesg:
if i.isalpha():
shifted += self.__shift(i,amt)
return shifted
def setBlockLength(self,length):
self.__blockLength = length
def encrypt(self,mesg):
return blockedString(self.__shiftString(mesg.upper(),self.__shiftAmt),self.__blockLength)
def decrypt(self,mesg):
return blockedString(self.__shiftString(mesg.upper(),26 - self.__shiftAmt).lower(),self.__blockLength).lower()
def setKey(self,key):
self.__shiftAmt = key
Note: When performing the shift each letter is first converted to it's number based on it's position in the alphabet by subtracting the ascii value of 'A', then shifted modulo 26, then the ascii value of 'A' is added to get the shifted letters ascii value.
Usage:
a = CaesarCypher( 5 )
a.encrypt('hello world my name is bob')
Output:
'MJQQT BTWQI RDSFR JNXGT G'
a.decrypt( 'MJQQT BTWQI RDSFR JNXGT G' )
Output:
'hello world mynam eisbo b'
Multiplicative Cipher
A multiplicative cipher works similar to Caesar Cipher except that instead of adding the key to each letter to encrypt, the key is multiplied by each letter during in encryption ( all done modulo 26). Multiplicative Ciphers add a restraint on the key such that the key must be relative prime to 26.
Here a Multiplicative Cipher implementation for Sage:
class MultiplicativeCypher:
def __init__(self,key):
#Make sure we get a key that provides 1 to 1 mapping
if self.__validKey(key) == False:
raise KeyError, 'Error: ' + str(key) + ' is an invalid key.'
self.__key = key
self.__inverse = self.__keyInverse()
#Returns a list all the factors of val
def __getFactors(self,val):
factors = []
i = 2
while i <= val:
if val % i == 0:
factors.append(i)
i += 1
return factors
#Returns true if key is not relatively prime
#to 26
def __validKey(self,key):
keyFactors = self.__getFactors(key)
unavailableFactors = self.__getFactors(26)
for val in unavailableFactors:
if val in keyFactors:
return False
return True
def __keyInverse(self):
for i in range(1,27):
if (i * self.__key) % 26 == 1:
return i
return -1
#multiply the character by the key
def __multChar(self,char,key):
intVal = ( ( ord( char.lower() ) - ord('a') + 1 ) * key ) % 26
if intVal == 0:
intVal = 26
return ( chr( intVal + ord('a') - 1 ) )
#Encrpyt mesg with a multiplicative cypher using
#the set key
def encrypt(self,mesg):
encStr = ""
for char in mesg:
if char.isalpha():
encStr += self.__multChar(char,self.__key)
return encStr.upper()
def decrypt(self,mesg):
decStr = ""
for char in mesg:
if char.isalpha():
decStr += self.__multChar(char,self.__inverse)
return decStr
def setKey(self,key):
self.__key = key
Notes: The constructor checks to ensure that the key is relative prime to 26 or raises an error. The key inverse is determined by finding the number that when multiplied by the key modulo 26 will equal 1.
Usage:
a = MultiplicativeCypher( 15 )
a.encrypt( 'hello world' )
Output:
'PWXXQGQJXH'
a.decrypt('PWXXQGQJXH')
Output:
'helloworld'
Affine Cipher
An Affine Cipher is a composition of a Caesar Cipher and a Multiplicative Cipher. It works by first encrypting the message with the multiplicative cipher and then encrypting the result with a Caesar cipher. Since we have already created classes for Caesar and Multiplicative Ciphers the Affine Cipher class is very simple.
Here an Affine Cipher implementation for Sage:
class AffineCypher:
def __init__(self,ka,km):
self.__aCypher = CaesarCypher( ka )
self.__mCypher = MultiplicativeCypher( km )
def encrypt(self,mesg):
return self.__aCypher.encrypt(self.__mCypher.encrypt(str(mesg)))
def decrypt(self,mesg):
return self.__mCypher.decrypt(self.__aCypher.decrypt(str(mesg)))
def setKey(self,ka,km):
self.__aCypher.setKey(ka)
self.__mCypher.setKey(km)
Affine Known Plain-text attack
Affine Ciphers can often be cracked by trying searching for common tri-graphs in the ciphertext. The following code shows a method of doing this in Sage. It works by taking a list of common trigraphs and searching for them using every possible combination of keys for the Caesar and Multiplicative Ciphers. It returns back a list of dictionaries of keys where a match was found.
triGraphs = [ 'the', 'ing', 'ned','ess','and', 'ere' ]
multKeys = [1, 3, 5, 7, 9, 11, 15, 17, 21, 23, 25 ]
def knownPlainText(cypherObj,mesg):
for cur in triGraphs:
enc = cypherObj.encrypt(cur)
if enc in mesg:
return True
return False
class AffineCrack():
def __init__(self,mesg):
self.__mesg = mesg
self.__cypher = AffineCypher(0,1)
self.__removeSpaces()
def __removeSpaces(self):
newMesg = ""
for letter in self.__mesg:
if letter.isalpha():
newMesg += letter
self.__mesg = newMesg
def knownAttack(self):
results = []
for i in range(0, 26):
for j in multKeys:
self.__cypher.setKey(i,j)
if knownPlainText(self.__cypher,self.__mesg):
results.append( { 'ka' : i, 'km' : j} )
return results
Usage:
a = AffineCypher( 5, 17 )
a.encrypt('today is the first day of the month')
Output:
'GZUVN BPGKL CBYPG UVNZC GKLRZ IGK'
a = AffineCrack('GZUVN BPGKL CBYPG UVNZC GKLRZ IGK')
a.knownAttack()
Output:
[{'ka': 5, 'km': 17}, {'ka': 6, 'km': 9}, {'ka': 8, 'km': 25}, {'ka': 13, 'km': 3}, {'ka': 24, 'km': 1}]
Playfair Cipher
Playfair Cipher is a poly-alphabetic cipher that uses a 5x5 square to hold the alphabet in (i and j are usually stored in the same square). A keyword is used to determine the placement of the letters in the square. Two letters are encrypted at a time and the cipher text is based on the location of the two letters in the square, if there is an odd number of letters a garbage letter usually is padded at the end.
Here is a Playfair Cipher implementation in Sage:
#Removes duplicate letters from a word
def removeDuplicate(word):
newWord = ""
for i in word:
if i.isalpha() and i not in newWord:
newWord += i
return newWord
#returns the row,column index of the val in the 2 dimensional table
#or (-1,-1) if it is not found
def indexOf(val,table):
i = 0
for curRow in table:
j = 0
for curColumn in curRow:
if val in curColumn:
return (i,j)
j += 1
i += 1
return (-1,-1)
#returns the encryption substituions for val1,val2
#in table as a tuple (val1Sub,val2Sub)
#returns (-1,-1) on error
def getEncSubstitution(val1,val2,table):
index1 = indexOf(val1,table)
index2 = indexOf(val2,table)
#val1 or val2 not in table
if -1 in index1 or -1 in index2:
return (-1,-1)
if val1 == val2:
return (-1,-1)
#give us some shorthand for the rows and columns
row1 = index1[0]
col1 = index1[1]
row2 = index2[0]
col2 = index2[1]
#Check the three possible cases
#case 1 they are in the same row
if index1[0] == index2[0]:
sub1 = table[row1][ (col1 + 1) % len(table[row1]) ][0]
sub2 = table[row2][ (col2 + 1) % len(table[row2]) ][0]
#case 2 they are in the same column
elif index1[1] == index2[1]:
sub1 = table[ (row1 + 1) % len(table) ][col1][0]
sub2 = table[ (row2 + 1) % len(table) ][col2][0]
#case 3 differrent row and different column
else:
sub1 = table[ row1 ][ col2 ][0]
sub2 = table[ row2 ][ col1 ][0]
return (sub1, sub2)
#returns the decryption substituions for val1,val2
#in table as a tuple (val1Sub,val2Sub)
#returns (-1,-1) on error
def getDecSubstitution(val1,val2,table):
index1 = indexOf(val1,table)
index2 = indexOf(val2,table)
#val1 or val2 not in table
if -1 in index1 or -1 in index2:
return (-1,-1)
if val1 == val2:
return (-1,-1)
#give us some shorthand for the rows and columns
row1 = index1[0]
col1 = index1[1]
row2 = index2[0]
col2 = index2[1]
#Check the three possible cases
#case 1 they are in the same row
if index1[0] == index2[0]:
if col1 == 0:
col1 = len(table[row1])
if col2 == 0:
col2 = len(table[row2])
sub1 = table[row1][ (col1 - 1) % len(table[row1]) ][0]
sub2 = table[row2][ (col2 - 1) % len(table[row2]) ][0]
#case 2 they are in the same column
elif index1[1] == index2[1]:
if row1 == 0:
row1 = len(table)
if row2 == 0:
row2 = len(table)
sub1 = table[ (row1 - 1) % len(table) ][col1][0]
sub2 = table[ (row2 - 1) % len(table) ][col2][0]
#case 3 differrent row and different column
else:
sub1 = table[ row1 ][ col2 ][0]
sub2 = table[ row2 ][ col1 ][0]
return (sub1, sub2)
class PlayFairCypher:
def __init__(self,keyword):
#character to be used when a filler is needed
self.__filler = 'x'
self.__unused = 'j'
self.__unusedSub = 'i'
#note: i,j will share the same box
self.__alphabet = self.__getAlphabet()
self.__key = self.__cleanString(keyword)
self.__buildTable()
#cleanup our keyword
def __cleanString(self,word):
clean = removeDuplicate( removeNonAlpha( word.lower() ) )
clean = self.__replaceUnused(clean)
return clean
#replace the unused letter with the letter sharing it's box
def __replaceUnused(self,word):
return word.replace(self.__unused,self.__unusedSub)
def __getAlphabet(self):
return ['a','b','c','d','e','f','g','h','i','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
#build our 5x5 square with our keyword
def __buildTable(self):
self.__table = [ [], [], [], [], [] ]
curRow = 0
i = 0
#first put the keyword in the table
for letter in self.__key:
#move down a row as necessary
if i == len(self.__table):
curRow += 1
i = 0
self.__table[curRow].append(letter)
#take the letter out of the alphabet as it's in the table now
self.__alphabet.remove(letter)
i += 1
#put the rest of the alphabet index
for letter in self.__alphabet:
if i == len(self.__table):
curRow += 1
i = 0
self.__table[curRow].append(letter)
i += 1
#reset our alphabet
self.__alphabet = self.__getAlphabet()
def __substituteEnc(self,mesg):
newMesg = ""
while len(mesg) > 0:
#add filler to get a digraph if necessary
if len(mesg) == 1:
mesg += self.__filler
diagraph = mesg[:2]
#add filler between two of the same consecutive letters
if diagraph[0] == diagraph[1]:
diagraph = [diagraph[0],self.__filler]
mesg = mesg[1:]
else:
mesg = mesg[2:]
s1,s2 = getEncSubstitution(diagraph[0],diagraph[1],self.__table)
newMesg += s1 + s2
return newMesg
def __substituteDec(self,mesg):
newMesg = ""
while len(mesg) > 0:
diagraph = mesg[:2]
mesg = mesg[2:]
s1,s2 = getDecSubstitution(diagraph[0],diagraph[1],self.__table)
newMesg += s1 + s2
return newMesg
def encrypt(self,mesg):
return self.__substituteEnc( self.__replaceUnused( removeNonAlpha( mesg.lower() ) ) )
def decrypt(self,mesg):
return self.__substituteDec( removeNonAlpha( mesg.lower() ) )
def getTable(self):
return copy( self.__table )
Sage's Cryptosystems
Vigenere Cipher
Vigenere Cipher is a poly-alphabetic cipher based on a table of Caesar Cipher alphabets.
Sage has built-in support for Vigenere Ciphers via the VigenereCryptosystem class. The way this class works is somewhat peculiar.
The constructor is setup as follows: VigenereCryptosystem( self, parent, key) where key is actually the length of the keyword. Parent will typically be an instance of the AlphabeticStrings() class.
To use the class you create an instance of the AlphabeticStrings class. Then you construct a VigenereCryptosystem object passing in the AlphabeticStrings object that you created and the length of your keyword. You then create your key using the AlphabeticStrings object you created. Then the key needs to be passed to the VigenereCryptosystem object and assigned to a new variable. Then you can construct another AlphabeticStrings object containing your ciphertext, and pass it to the new VigenereCryptosystem object that was given your key. Note: your ciphertext must be uppercase cannot contain any spaces or other non-alpha characters.
Here is an example of the encryption process:
We start by creating an instance of the parent.
S = AlphabeticStrings()
Then we can create a VigenereCryptosystem object using our parent S and keyword length of 8.
E = VigenereCryptosystem(S,8)
Now we can pass our key to the VigenereCryptosystem object to get a VigenereCipher.
e = E( S("PASSWORD") )
e is now a VigenereCipher. We can use e now to encrypt our message.
encMesg = e( S("MESSAGETOENCRYPT") )
encMesg
#Output: BEKKWUVWDEFUNMGW
Now to decrypt our message we need to get the key inverse from our VigenereCipher e.
i = e.inverse()
The inverse method returns us a VigenereCipher with the key set to the key inverse of our original cipher. We then use it to decrypt our message.
decMesg = i( encMesg ) decMesg #Output: MESSAGETOENCRYPT
Hill Cipher
Hill Cipher is a poly-alphabetic cipher that uses a n x n matrix as key, and the matrix inverse as the inverse key. Sage provides built-in support for Hill Ciphers via the HillCryptosystem class. The constructor for the HillCryptosystem is setup as follows HillCryptosystem( self, parent, key ) where key is the dimension of the n x n matrix.
Here is step by step example for working with Hill Ciphers in Sage.
We start by creating an instance of the parent which for this example is AlphabeticStrings. What this means is that the strings we encrypt must be alphabetic containing only uppercase letters.
S = AlphabeticStrings()
Next we create an instance of the HillCryptosystem class. We pass in the parent instance which in this example is S and the dimension of our nxn matrix which will be 2 for this example.
E = HillCryptosystem(S, 2)
Sage allows us to see what the key space of our HillCryptosystem object is:
E.key_space() #output: #Full MatrixSpace of 2 by 2 dense matrices over Ring of integers modulo 26
So we can see that our key space is all 2x2 matrices of integers modulo 26. Next we can use our key space to generate our key.
M = E.key_space() A = M( [ [12,19], [21,3] ] )
Now we can use our HillCryptosystem object E to generate an instance of the HillCipher class.
e = E(A)
Now we can encrypt a string using our HillCipher object e. Note: You need to pad your string if necessary as Sage will not do this for you.
encMesg = e( S("THISISMYMESSAGEX") )
encMesg
#output:
#LSGYGYYOUGWGWSLP
Now we can decrypt our encrypted message. First we need to call the inverse method on our HillCipher object e which will return a new HillCipher object with the key set to the inverse of the key used for encryption.
i = e.inverse() type( i ) #output #<class 'sage.crypto.classical_cipher.HillCipher'>
Now we can use our new HillCipher object to decrypt our encrypted message.
i(encMesg) #output: #THISISMYMESSAGEX
Simple Substitution Cipher
A simple substitution cipher is a cipher where letters are swapped so for example 'a' may be mapped to 'e' and 'e' may be mapped to 'q'. There doesn't need to be any order to the how the substitutions are made. Sage provides built-in support for substitution ciphers via the SubstitutionCryptosystem class. The constructor for the SubstitutionCryptosystem works as follows SubstitutionCryptosystem( self, parent).
Here is a step by step example of working with substitution ciphers using Sage:
Let's start by generating an instance of the parent which for this example will be AlphabeticStrings.
S = AlphabeticStrings()
Now we can use the parent object S to create a SubstitutionCryptosystem object.
E = SubstitutionCryptosystem(S)
Now we need to generate an alphabet containing the substitutions we want to use. We want the alphabet to be random so we will use the shuffle function to randomize the element in the list. The list we generate will just be the numbers 0 - 25. Note: shuffle operates on the original list it does not make a copy, and it returns None when complete.
alphabet = range(0,26) shuffle( alphabet ) print alphabet #output #[15, 22, 2, 3, 13, 5, 19, 23, 24, 20, 21, 9, 14, 6, 12, 7, 4, 10, 11, 25, 1, 17, 16, 0, 18, 8]
Now we can use our randomized alphabet to create a SubstitutionCipher object.
e = E( S( alphabet ) )
Now we can encrypt a message using our SubstitutionCipher object e.
encMesg = e( S("THISISMYMESSAGE") )
encMesg
#output
#ZXYLYLOSONLLPTN
Now to decrypt we need to get the key inverse from our cipher object.
i = e.inverse()
We can then use the inverse to decrypt the message:
i( encMesg ) #output #THISISMYMESSAGE
Caesar Ciphers
Using Sage's SubstitutionCryptosystem class it is easy to create a Caesar Cipher, we just have to modify how we create our alphabet.
The basic syntax for generating an alphabet for a Caesar Cipher is as follows:
S = AlphabeticStrings() alphabet = [ (i + shift_amt)%26 for i in range(0,26) ] A = S( alphabet )
Let's say we want a Caesar Shift of 5:
S = AlphabeticStrings()
E = SubstitutionCryptosystem(S)
alphabet = [ (i + 5)%26 for i in range(0,26) ]
A = S( alphabet )
e = E( A )
e("MESSAGETOENCRYPT")