Wednesday, August 09, 2006

Ruby : Permutations

I've been interested in the field of cryptography recently after reading all of Dan Brown's excellent books, he wrote 3 crackers before the Da Vinci Code and I highly recommend them, especially Angels & Demons and Deception Point. Anyway, a brute force attack on a code simply iterates through every possible permutation of a key and decyphers the ciphertext until the resulting plaintext is intelligible. The two downsides of a brute force attack are firstly it can take many, many iterations before the correct key is found (which requires a lot of processing power) and secondly that matching the plaintext against an english dictionary every time round the loop is quite expensive. This makes for a slow algorithm. So, I guess Ruby wouldn't be the language of choice to implement something like this. However, Ruby is nice and expressive and good for learning the basic without getting bogged down with low level optimisations.

To this end I've developed an extension to the standard Array class which simply allows you to iterate through every unique permutation of an array. It is based on a Python algorithm I googled for but it's nice to see it more elegantly expressed in Ruby...


class Array

def each_permutation(&blockproc)

a = []
self.each do |c|
a.push(c)
end
n = a.length
p = Array.new(n+1,0)
i = 1

blockproc.call(a)

while i < n do

if p[i] < i

j = 0
j = p[i] if (i % 2) == 1
t = a[j]
a[j] = a[i]
a[i] = t

p[i] = p[i] + 1
i = 1

blockproc.call(a)

else

p[i] = 0
i = i + 1

end

end

end

end




["a","b","c"].each_permutation { |arr| puts arr.join }

abc
bac
cab
acb
bca
cba



Ruby's String class has a built in "crypt" method which applies a one-way cryptographic hash but I think it's nice to develop something new. I'll post more about the simple transposition encryption/decryption and crack algorithms that I developed soon.

No comments: