Classical Cryptography

From www.norsemathology.org

Jump to: navigation, search

Contents

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")
Personal tools