Polyalphabetic substitution
A friend of mine just planted a geocache in which you needed to use polyalphabetic substitution to solve it. This was a kind of cipher I wasn’t familiar with and I have to admit — I was intriqued.
Like most lazy computer guys, I wrote a program to encrypt the puzzle instead of solving it manually. It was an interesting excersise — the code wasn’t hard, but you had to have a good understanding of arrays and how they work in your language of choice. I chose Python, and I had to think a little about lists before getting things quite right.
Implementing a polyalphabetic substitution may be a decent excercise in learning a new language.
October 25th, 2006 at 3:04 pm
I like to understand my arrays for the Vigenere cipher a little differently (surprise, surprise…) In Ruby:
Set e = -1 to decrypt
def vigenere(c,k,e=1)
base=’A’[0]
wk=k.upcase.gsub(/[^A-Z]/, ”).unpack(’c‘).map {|ch| ch-base}
wc=c.upcase.gsub(/[^A-Z]/, ”).unpack(’c‘).map {|ch| ch-base}
wy=[]
wc.zip(wk * (c.length / k.length + 1)) {|a| wy.push((a[0] + (e * a[1])) % 26)}
wy.map {|ch| ch + base}.pack(’c*’)
end
vigenere(’thiscryptosystemisnotsecure’, ‘cipher’)
vigenere(’VPXZGIAXIVWPUBTTMJPWIZITWZT’, ‘cipher’, -1)
October 25th, 2006 at 8:56 pm
I’ll throw some love python’s way too. I don’t think this LOOKS as nice, but I think that’s because I put the lambda inline:
import string
def vigenere(c, k, e=1):
trans = string.maketrans(string.asciiletters, 2*string.asciiuppercase)
elim = string.digits + string.punctuation + string.whitespace
wk = k.translate(trans, elim)
wc = c.translate(trans, elim)
return ”.join(map(lambda x: chr(((ord(x[0]) + (e * ord(x[1])) - 2*ord(’A')) % 26) + ord(’A')),
zip(wc, wk * (len(wc)/len(wk) + 1))))
vigenere(’thiscryptosystemisnotsecure’, ‘cipher’)
vigenere(’VPXZGIAXIVWPUBTTMJPWIZITWZT’, ‘cipher’, -1)
October 26th, 2006 at 3:50 am
Okay, I admit that my original Python code looked nothing like yours. But here’s a Python version that is based off of your Ruby one. Note that I didn’t even use map or lamba:
In case people are wondering, Jeremy and I took too many math classes in college together.
October 26th, 2006 at 8:17 am
Yeah, I like that better actually, I should have thought about the list comps. Makes it MUCH cleaner. I went back and forth on the spaces. For the purposes you described, it’s probably a nicer thing to do for the geocache finder but, cryptographically, leaving the signature of the spaces in the ciphertext weakens it vastly (you start to have the original weakness of the cyclically repeating key plus the weakness of retaining the original word lengths. This COULD be partially fixed if you altered the ring to Z_27 by adding the space somewhere — There would still be extra information in the ciphertext bu this would actually also encourage multi-word keys / longer keys which would be stronger. If you think about it, if you secret key approaches the length of you plaintext, the strength of the cipher begins to increase due to replication of a so-called “one time pad”
–Jeremy
And computer science classes — but most of them didn’t give problems quite this fun.
October 26th, 2006 at 9:21 am
yeah, this was much better than any CS projects we had.
I’m glad you liked my example. List comprehensions are a wonderful thing. Much better than the map function, IMHO, because you can put an ‘if’ statement in, therefore you don’t have to return the same size set that you put in.
In the geocache example, I preserved the spaces where they are. Yeah, if I were a spy I would take them out or just make a space every four letters (that’s generally the convention).
Actually, if you just used one keyphrase per cipher, then making keyphrases as long as your message would be a good thing. But if you re-use the key over and over again, you want it shorter than the message, otherwise an analysis will discover the message (or, worse yet, the key). Of course, having a short key for a long message is also bad, because then they can discover the length of the key, which is only two steps away from finding the key. I’m not sure what’s optimal — a key half as long as the message?
October 26th, 2006 at 5:08 pm
[...] Jeremy and I are having an interesting discussion on thePolyalphabetic Substitution post. Before jumping in, though, you better learn/review some ring theory. [...]