Some Python code relevant to the CS402 cryptography course is contained in the file cs402.py . A dictionary of English words is contained in the file dictionary.txt . Both files should be placed in the Python directory (such as C:\Python27). You'll need to have the Python numpy module installed in orderd to use cs402.py.

Affine cryptosystem with single letter message units

Suppose we wish to use the enciphering function 

x |---> ax + b       modulo 26

on single letter message units over a 26-letter alphabet A=0, B=1, ..., Z=26, with enciphering key (a,b)=(3,4), to encipher the plaintex

"THISISONEOFTHEMOSTINSECURECRYPTOSYSTEMTSONTHEMARKET".

We can do this by placing the plaintext in a file plain.txt in our Python directory and then using the following Python code.

>>> from cs402 import AffineCipher
>>> C=AffineCipher
>>> C.setAlphabet("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
>>> k=[3,4]
>>> C.encipher("plain.txt")
'JZCGCGURQUTJZQOUGJCRGQKMDQKDYXJUGYGJQOJGURJZQOEDIQJ'

The ciphertext is

"JZCGCGURQUTJZQOUGJCRGQKMDQKDYXJUGYGJQOJGURJZQOEDIQJ" .

We can decipher by placing this ciphertext in a file cipher.txt in our Python directory, noting that the deciphering function is x |---> cx + d with (c,d)=(9,16), and then using the following Python code.

>>> C.setDecipherKey([9,16])
>>> C.decipher("cipher.txt")
'THISISONEOFTHEMOSTINSECURECRYPTOSYSTEMTSONTHEMARKET'


Affine cryptosystem with block message units

Suppose we wish to use the enciphering function 

x |---> Ax + B       modulo 26

on 2-letter message units over a 26-letter alphabet A=0, B=1, ..., Z=26, with enciphering key matrix A=[[3,3],[4,5]] and vector B=[[1],[2]], to encipher the plaintex

"THISISONEOFTHEMOSTINSECURECRYPTOSYSTEMTSONTHEMARKET".

We can do this by placing the plaintext in a file plain.txt in our Python directory and then using the following Python code. The first line of code imports the function mat from the numpy module.

>>> from numpy import mat
>>> A=mat([[3,3],[4,5]])
>>> B=mat([[1],[2]])
>>> from cs402 import AffineCipher
>>> C=AffineCipher
>>> C.setAlphabet("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
>>> C.setEncipherKey([A,B])
>>> C.encipher("plain.txt")
'BJBUBUETDKVNIYBQINMVPQPGMMGRORWSXMINXAIMETBJXAAJ'

The ciphertex is

"BJBUBUETDKVNIYBQINMVPQPGMMGRORWSXMINXAIMETBJXAAJ"

We can decipher by placing this ciphertext in a file cipher.txt in our Python directory, noting that the deciphering function is x |---> Ax + B with A=[[19,25],[16,1]], B=[[9],[8]] and then using the following Python code.

>>> A=mat([[19,25],[16,1]])
>>> B=mat([[9],[8]])
>>> C.setDecipherKey([A,B])
>>> C.decipher("cipher.txt")
'THISISONEOFTHEMOSTINSECURECRYPTOSYSTEMTSONTHEM'


Exhaustive search through all deciphering keys

Suppose we know that the ciphertext

APHIZHIZNVMZNEZAPMZCNIAZHVIMBTQMZBQOFANIOIAMCAIZNVZAPMZCRQSMA

was produced using a affine cryptosystem x |---> ax + b on single letter message units over an alphabet A=0, B=1, ..., Z=25, space=26. Suppose also that we know that the plaintext is in English. There are only Phi(27)*27=486 possible deciphering keys, so we could try all possible deciphering keys until we hit an output in English. If we have placed the ciphertext in a file cipher.txt then the following Python code does just this for us.

>>> from cs402 import AffineCipher
>>> from cs402 import isEnglish
>>> C=AffineCipher
>>> C.setAlphabet("ABCDEFGHIJKLMNOPQRSTUVWXYZ ")
>>> for a in range(1,26):
...   for b in range(0,26):
...    txt=C.decipher("cipher.txt")
...    if isEnglish(txt) : print(txt); print(" ")
...
>>>
>>> from cs402 import AffineCipher
>>> from cs402 import isEnglish
>>> C=AffineCipher
>>> C.setAlphabet("ABCDEFGHIJKLMNOPQRSTUVWXYZ ")
>>> for a in range(1,26):
...   for b in range(0,26):
...     C.setDecipherKey([a,b])
...     txt=C.decipher("cipher.txt")
...     if isEnglish(txt) : print(txt); print(" ")
...
MP BI BILAJILUIMPJIQLBMI ABJOXRJIORNWMLBNBMJQMBILAIMPJIQTRVJM
 
RUEGNEGNQFONQZNRUONVQGRNEFGOTBWONTWSARQGSGROVRGNQFNRUONVYW OR
 
FX C  C ROO RR FXO LRCF  OCOII O I UUFRCUCFOLFC RO FXO LC FOF
 
LU F  F ICC II LUC XIFL  CFCRR C R OOLIFOFLCXLF IC LUC XF LCL
 
IFDKVDKVSULVSJVIFLVWSKIVDUKLPGMLVPMZQISKZKILWIKVSUVIFLVWTM LI
 
RR I  I  RR    RRR I IR  RIR   R   IIR IIIRRIRI  R RRR II RRR
 
THIS IS ONE OF THE MOST INSECURE CRYPTOSYSTEMTS ON THE MARKET
 
RUNYWNYWZFOWZHWRUOWMZYRWNFYOBKEOWBEJSRZYJYROMRYWZFWRUOWMPE OR
 
CL O  O IUU II CLU FIOC  UOURR U R XXCIOXOCUFCO IU CLU FO CUC
 
IRFUFFUFO  FOOFIR FLOUIFF U XXF FXFCCIOUCUI LIUFO FIR FLUFI I
 
IFMBDMBDAULDASDIFLDNABIDMUBLYPVLDYVQHIABQBILNIBDAUDIFLDNKV LI
 
II R  R  II    III R RI  IRI   I   RRI RRRIIRIR  I III RR III
 
RUWPEWPEHFOEHQERUOEDHPREWFPOKTNOEKNAJRHPAPRODRPEHFERUOEDGN OR
 
OF U  U RXX RR OFX CRUO  XUXII X I LLORULUOXCOU RX OFX CU OXO
 
RICXCCXCU  CUUCRI CFUXRCC X LLC CLCOORUXOXR FRXCU CRI CFXCR R
 
UC X  X ILL II UCL OIXU  LXLRR L R FFUIXFXULOUX IL UCL OX ULU
 
IFVTMVTMJULMJAMIFLMEJTIMVUTLGYDLMGDHZIJTHTILEITMJUMIFLMEBD LI


We see from this brute force search that the plaintext in this case is most probably

"THIS IS ONE OF THE MOST INSECURE CRYPTOSYSTEMTS ON THE MARKET" .

The function isEnglish(string) returns true if at least p=80% of the words in string, defined by spaces, are in the file dictionary.txt. The value of p can be adjusted in the code to give potentially better results.

Frequency analysis

To perform frequency analysys on a piece of text we need to be able to count the number of occurences of a particular letter, or a particular pair of letters, or triple of letters in the text. Suppose for instance we wanted to count the number of times "t" or "T" occurs in the following text, and also the number of times "the" or "The" occurs.
 
But here I must deal with a misconception. It is sometimes suggested that pure mathematicians glory in the uselessness of their work [16], and make it a boast that it has no practical applications. The imputation is usually based on an incautious saying attributed to Gauss, to the effect that, if mathematics is the queen of the sciences, then the theory of numbers is, because of its supreme uselessness, the queen of mathematics—I have never been able to find an exact quotation. I am sure that Gauss’s saying (if indeed it be his) has been rather crudely misinterpreted. If the theory of numbers could be employed for any practical and obviously honourable purpose, if it could be turned directly to the furtherance of human happiness or the relief of human suffering,
as physiology and even chemistry can, then surely neither Gauss nor any other mathematician would have been so foolish as to decry or regret such applications. But science works for evil as well as for good (and particularly, of course, in time of war); and
both Gauss and less mathematicians may be justified in rejoicing that there is one science at any rate, and that their own, whose very remoteness from ordinary human activities should keep it gentle and clean.

The following Python code performs the required counts.

>>> str="But here I must deal with a misconception. It is sometimes suggested that pure mathematicians glory in the uselessness of their work [16], and make it a boast that it has no practical applications. The imputation is usually based on an incautious saying attributed to Gauss, to the effect that, if mathematics is the queen of the sciences, then the theory of numbers is, because of its supreme uselessness, the queen of mathematics—I have never been able to find an exact quotation. I am sure that Gauss’s saying (if indeed it be his) has been rather crudely misinterpreted. If the theory of numbers could be employed for any practical and obviously honourable purpose, if it could be turned directly to the furtherance of human happiness or the relief of human suffering, as physiology and even chemistry can, then surely neither Gauss nor any other mathematician would have been so foolish as to decry or regret such applications. But science works for evil as well as for good (and particularly, of course, in time of war); and both Gauss and less mathematicians may be justified in rejoicing that there is one science at any rate, and that their own, whose very remoteness from ordinary human activities should keep it gentle and clean."
>>>
>>> str.count('t')+str.count('T')
93
>>> str.count('the')+str.count('The')
26

Instead of typing the text directly into Python it is often more convenient to place it in a file named say file.txt and then use the following commands.

>>> f=open("file.txt","r")  #The "r" is because we are reading from the file. Use "w" to write to a file
>>> str=f.read()
>>> f.close()
>>> str.count('t')+str.count('T')
93
>>> str.count('the')+str.count('The')
26

Converting between decimal lists and binary lists

The python class Cipher defined in the file cs402.py converts a text over an alphabet to a sequence of integers. In many cases, such as with stream ciphers, we need to convert text to a binary sequence. There are several standard ways of doing this in Python, but for pedagocial reasons in this CS402 course we shall not use these standard methods. Rather we shall use the following functions dec2bin(L,n) and bin2dec(B,n) . The first function inputs a list L of decimal integers and a decimal integer n; it converts each term in L to a binary list of length n and then returns the concatenation of these lists.  The second function is the invers of the first.

>>> from cs402 import dec2bin
>>> from cs402 import bin2dec
>>> D=[2,3,5,7,11,13]
>>> B=dec2bin(D,8)
>>> print(B)
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1]
>>> D1=bin2dec(B,8)
>>> print(D1)
[2, 3, 5, 7, 11, 13]


Linear Feedback Shift Registers

A binary Linear Feedback Shift Register R is determined by its connection polynomial
C(X) = 1 + c1X + c2X2 + ... + cnXn
where each ci = 0 or 1 and cn = 1. For any given binary list s1, s2, ... , sn of length n the shift register determines an infinite binary sequence
s1, s2, ... , sn, sn+1, ...., si, ...
where for i > n we have
si = c1sj-1 + c2sj-2 + c3sj-3+ ... + cnsj-n .

Let K=[i1,i2,...im] be the list of indices of the non-zero coefficients ci in the polynomial C(X). Given K and a list Si=[si,si+1,...,si+n-1] the Python function LSFR(K,Si) in the file cs402.py returns the list  Si+1=[si+1,si+2,...,si+n] .  So for example, the following Python commands produce the first 30 terms of the sequence s1, s2, ... , sn, sn+1, ...., for

C(X) = 1 + X + X3

s1=1, s2=1, s3=0.

>>> from cs402 import LFSR
>>> K=[1,3]
>>> S=[1,1,0]
>>> L=[1,1,0]
>>> for i in range(0,27): S=LFSR(K,S); L.append(S[2]);
...
>>> print L
[1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1]