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.

1 comment:

rduht said...

There are wow gold 3 men in a plane. wow gold A priest, a baseball player world of warcraft power leveling and a soldier. the pilot goes into dog clothes the cabin and 2moons gold tells them that there Atlantica gold is a weight overload 2moons power leveling on the plane and they would each have to throw world of warcraft gold one personalworld of warcraft power leveling belonging out aoc power leveling the window to safely land. Power Leveling the priest throws flyff money out a bible and says,"forgive me lord, i will last chaos gold get another one.archlord power leveling The baseball player world of warcraft gold throws a baseball out and says, aoc gold "i play professional baseball, i can get thesearchlord gold whenever i want." Now