Caesar's cipher is to move a letter 3 places forward in the alphabet.
def caesar_letter(letter):
"""Return the 3rd letter after the input"""
assert type(letter) is str and len(letter)==1
letter = letter.upper()
num = ord(letter) - ord('A') #now letter in [0,..,25]
num = (num+3)%26 #shift
letter = chr(num+ord('A')) #take number back to letter
return letter
caesar_letter('a'),caesar_letter('b'),caesar_letter('c'),caesar_letter('d')
alphabet = "abcdefghijklmnopqrstuvwxyz"
for a in alphabet:
print a," ---> ", caesar_letter(a)
def caesar_string(S):
T = str()
for s in S:
if s==' ':
T = T+s
else:
T = T+caesar_letter(s)
return T
caesar_string("all of gaul is divided into three parts")
A generalization of Caesar's cipher is to shift not by 3, but by some amount $k$.
This makes it a cipher with a key
def shift_letter(letter,k):
"""Return the kth letter after the input"""
assert type(letter) is str and len(letter)==1 and type(k) is int
letter = letter.upper()
num = ord(letter) - ord('A') #now letter in [0,..,25]
num = (num+k)%26 #shift
letter = chr(num+ord('A')) #take number back to letter
return letter
def shift_string(S,k):
T = str()
for s in S:
if s==' ':
T = T+s
else:
T = T+shift_letter(s,k)
return T
shift_string("all of gaul is divided into three parts",3)
for i in range(27):
print i,":",shift_string("all of gaul is divided into three parts",i)
shift_string("DOO RI JDXO LV GLYLGHG LQWR WKUHH SDUWV",-3)
shift_string("KVV YP QKEV SC NSFSNON SXDY DRBOO ZKBDC",-10)
The shift cipher is not a good cipher!
But why, exactly?
Because the key space is very small.
We can check 26 possibilities in a millisecond.
Note that the first 5 characters of the message more or less tells us if the key is correct or not.
Decrypt KTBG BG LITBG YTEEL BG MAX IETBG
ciphertext = "KTBG BG LITBG YTEEL BG MAX IETBG"
for i in range(27):
print i,":",shift_string(ciphertext,i)
It is brute force because it just tries every key.
Sometimes we know the plaintext and the ciphertext and just want to find the key.
This is a known plaintext attack. Example:
"hot pie" --- > DKP LEA
ord('D')-ord('H')
Thus the shift is $k=-4$, or equivalently $k=22$.
shift_string("DKP LEA",-22)
Note that while the time necessary for a ciphertext only attack was (in this case) proportional to the keyspace size, the time necessary for a known plaintext attack is constant.
This makes sense: Having more information about the cipher helps you break it.
shift cipher is
$E_k(x) = (x+k)\%26$
$D_k(x) = (x-k)\%26$
This assumes that the alphabet is {0,1,...,25} rather than {A,B,C,...,Z}.
But this is just a superficial difference.
$E_{a,b} = (a\cdot x + b)\%26$
Now the key $k = (a,b)$ is a pair of numbers in {0..25} and the keyspace has size seems to be
$26^2 = 676$
Actually we will see below that some $a$ are unsuitable and there are only
$12\cdot26 = 312$
pairs (a,b) that give an invertible $E_{a,b}$.
It is important that $E$ be an invertible function, because we eventually want to decrypt things!
def affine_letter(letter,k):
"""Return the affine cipher with a = k[0], b = k[1]"""
assert type(letter) is str and len(letter)==1
letter = letter.upper()
x = ord(letter) - ord('A') #now letter in [0,..,25]
x = (x*k[0]+k[1])%26 #affine cipher
letter = chr(x+ord('A')) #take number back to letter
return letter
affine_letter('A',(1,3)) #The Caesar cipher
def affine_string(S,k):
T = str()
for s in S:
if s==' ':
T = T+s
else:
T = T+affine_letter(s,k)
return T
affine_string("hello how are you",(3,11))
Does it even have an inverse?
for a in "abcdefghijklmnopqrstuvwxyz":
print a,"-->",affine_letter(a,(2,0))
Therefore it has no inverse.
The problem is basically that there is no element $g$ in {0..25} for which
$(2g)\%26=1$
Note that if there were such a $g$ then we could invert $E_{2,0}$ by applying $E_{g,0}$.
Meaning, that:
$E_{g,0}(E_{2,0}(x)) = (g2x)\%26 = x$
from fractions import gcd
invertables = [a for a in range(26) if gcd(a,26)==1]
invertables
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
for i in invertables:
print "%d * %d mod 26 = %d"%(i,modinv(i,26),1)
If we denote the multiplicative inverse of $a$ mod 26 by $a^{-1}$ then
for $E_{a,b}(x)$ we decrypt by
$D_{a,b}(x) = E_{a^{-1},-a^{-1}b}(x) = (a^{-1}x-a^{-1}b)\%26 $
Proof:
$D_{a,b}(E_{a,b}(x)) = E_{a^{-1},-a^{-1}b}(ax + b) =$
$a^{-1}(ax+b) - a^{-1}b = x+a^{-1}b-a^{-1}b = x$
But it illustrates some important things.
For one thing, the keyspace is still too tiny.
For another thing, it does not disguise the statistics of the language enough.
We will crack it in a lab, or as an assignment (maybe).
import random
abet = alphabet[:]
bizzarrobet = str()
while len(bizzarrobet) < 26:
r = random.randint(0,len(abet)-1)
print ("%3d %s")%(r,abet)
bizzarrobet += abet[r]
abet = abet.replace(abet[r],"")
bizzarrobet
Emap = dict(zip(alphabet,bizzarrobet))
Emap[' '] = ' '
Emap
S = "a stitch in time saves nine"
EncryptedS = str()
for s in S:
EncryptedS += Emap[s]
EncryptedS
Dmap = {v: k for k, v in Emap.items()}
Dmap
SS = str()
for s in EncryptedS:
SS += Dmap[s]
SS
math.factorial(26)
S = """Describing him as a normal, well-adjusted individual in nearly every respect, acquaintances of 32-year-old Gary Morgan confirmed Monday that the otherwise reasonable man earnestly believes the U.S. government landed a spacecraft on the moon. "Gary's a pretty regular, levelheaded guy unless he gets going on one of his ridiculous rants about how American astronauts actually walked on the moon back in 1969,” said friend Jeremy Lesser, adding that you would never guess by looking at Morgan that he’s absolutely convinced NASA successfully sent six different crews on lunar missions. “Honestly, I’ve found it’s best just to avoid the topic of space exploration altogether when we hang out. I’ve come to realize that no matter what I say, I’m never going to change his mind about the Apollo program. And I’d rather talk to him about anything else than hear him go off about astronauts exploring the lunar surface and bringing samples back to Earth again.” At press time, Lesser was reportedly biting his tongue as Morgan explained the existence of several American flags allegedly planted on the moon."""
S = S.lower()
S = S.replace('\xe2',"")
S = S.replace('\x80',"")
S = S.replace('\x9d',"")
S = S.replace('\x99',"")
S = S.replace('\x9c',"")
Emap[',']=','
Emap["'"]="'"
Emap["."]="."
Emap["-"]="-"
Emap["9"]="9"
Emap["6"]="6"
Emap["3"]="3"
Emap["2"]="2"
Emap["1"]="1"
Emap['"']='"'
EncryptedS = str()
for s in S:
EncryptedS += Emap[s]
EncryptedS
import string
def hist(string):
d = {}
tot =0
for i in string.lower():
tot += 1
if i.isalpha():
d[i] = d[i] + 1 if i in d else 1
result = list()
for k in d.keys():
result.append((k,float(d[k])/tot))
return result
def getKey(item):
return item[1]
S1 = sorted(hist(S),key=getKey)
S2 = sorted(hist(EncryptedS),key=getKey)
Z = zip(S1,S2)
print S
print EncryptedS
Z
for z in Z:
print z[0][0],"--->",z[1][0],
Emap