[SUMMARY] The Solitaire Cipher (#1)

	YOURC IPHER ISWOR KINGX

	WELCO METOR UBYQU IZXXX

That's what you should have seen, if you ran a working Solitaire cipher
decryption script over the last two lines of the quiz.  All the submitted
solutions did just that in my tests, though some needed a tiny tweak here or
there.

I think the steps of the algorithm are much easier than I made them sound in the
quiz.  In fact, I was wondering if anyone would just combine encryption and
decryption, as they are nearly the same process.  And look, someone did:

	class Encrypter
	  def initialize(keystream)
	    @keystream = keystream
	  end
	
	  def sanitize(s)
	    s = s.upcase
	    s = s.gsub(/[^A-Z]/, "")
	    s = s + "X" * ((5 - s.size % 5) % 5)
	    out = ""
	    (s.size / 5).times {|i| out << s[i*5,5] << " "}
	    return out
	  end
	
	  def mod(c)
	    return c - 26 if c > 26
	    return c + 26 if c < 1
	    return c
	  end
	
	  def process(s, &combiner)
	    s = sanitize(s)
	    out = ""
	    s.each_byte { |c|
	      if c >= ?A and c <= ?Z
	        key = @keystream.get
	        res = combiner.call(c, key[0])
	        out << res.chr
	      else
	        out << c.chr
	      end
	    }
	    return out
	  end
	
	  def encrypt(s)
	    return process(s) {|c, key| 64 + mod(c + key - 128)}
	  end
	
	  def decrypt(s)
	    return process(s) {|c, key| 64 + mod(c -key)}
	  end
	end

That's a pretty straight forward class to handle both operations by Niklas
Frykholm.  The heart of this operation is the process() method.  It guides the
conversion for both encryption and decryption.  It starts by handing off the
message to the sanitize() method for the stripping of non-letter characters,
uppercasing, and being broken into proper chunks.  Note that if we're
decrypting, this call should have no noticeable effects (though it does waste a
little processing time).

Once the message has been placed into the proper format, process() continues
walking the now almost identical steps to transform the message either way.  In
the one other place the steps diverge, the addition or subtraction of the
keystream letters, Niklas uses a passed in block to do the right thing.  The
block comes from the methods encrypt() and decrypt(), which are just an
interface to the clever processing routine.

I didn't mention this in the quiz itself, but the above process of encryption
and decryption is actually fundamental to many ciphers, not just Solitaire. 
With a different method of keystream generation, the above class could instead
be used for DES encryption or other methods.  Niklas supports this well, by
having the keystream object passed into the constructor.

The other half of Solitaire is keystream generation, of course.  Many people
used a Deck class (and some a Card class) to drive this process.  Here's one
such class by Thomas Leitner:

	# Handles the deck
	class Deck
	
	  # Initializes the deck with the default values
	  def initialize
		@deck = (1..52).to_a << 'A' << 'B'
	  end
	
	  # Operation "move a" (step 2)
	  def move_A
		move_down( @deck.index( 'A' ) )
	  end
	
	  # Operation "move b" (step 3)
	  def move_B
		2.times { move_down( @deck.index( 'B' ) ) }
	  end
	
	  # Operation "triple cut" (step 4)
	  def triple_cut
		a = @deck.index( 'A' )
		b = @deck.index( 'B' )
		a, b = b, a if a > b
		@deck.replace( [ @deck[(b + 1)..-1],
		                 @deck[a..b],
		                 @deck[0...a] ].flatten )
	  end
	
	  # Operation "count cut" (step 5)
	  def count_cut
		temp = @deck[0..(@deck[-1] - 1)]
		@deck[0..(@deck[-1] - 1)] = []
		@deck[-1..-1] = [temp, @deck[-1]].flatten
	  end
	
	  # Operation "output the found letter" (step 6)
	  def output_letter
		a = @deck.first
		a = 53 if a.instance_of? String
		output = @deck[a]
		if output.instance_of? String
		  nil
		else
		  output -= 26 if output > 26
		  (output + 64).chr
		end
	  end
	
	  # Shuffle the deck using the initialization number +init+
	  # and the method +method+.
	  # Currently there are only two methods: <tt>:fisher_yates</tt>
	  # and <tt>naive</tt>.
	  def shuffle( init, method = :fisher_yates )
		srand( init )
		self.send( method.id2name + "_shuffle", @deck )
	  end
	
	  private
	
	  # From pleac.sf.net
	  def fisher_yates_shuffle( a )
		(a.size-1).downto(0) { |i|
		  j = rand(i+1)
		  a[i], a[j] = a[j], a[i] if i != j
		}
	  end
	
	  # From pleac.sf.net
	  def naive_shuffle( a )
		for i in 0...a.size
		  j = rand(a.size)
		  a[i], a[j] = a[j], a[i]
		end
	  end
	
	  # Moves the index one place down while treating the used array
	  # as circular list.
	  def move_down( index )
		if index == @deck.length - 1
		  @deck[1..1] = @deck[index], @deck[1]
		  @deck.pop
		else
		  @deck[index], @deck[index + 1] = @deck[index + 1], @deck[index]
		end
	  end
	
	end

Notice that Thomas doesn't retain much notion of "cards" per say, but instead
just treats them as the numbers they represent.  Most of the methods in this
class are just steps from keystream generation:  move_A() and move_B() which are
just an interface for the private move_down(), triple_cut(), and count_cut(). 
Turning those into the actual process needed is trivial:

	# Generates a keystream for the given +length+.
	def generate_keystream( length )
	  deck = @deck.dup
	  result = []
	  while result.length != length
		deck.move_A
		deck.move_B
		deck.triple_cut
		deck.count_cut
		letter = deck.output_letter
		result << letter unless letter.nil?
	  end
	  result.join
	end

That's all there was to solving the quiz, but that's certainly not all their was
to the submissions.  I'll see if I can point out a few highlights you might want
to take a look at, if you haven't already.

Several people provided alternate ways to key the deck, similar to Thomas'
shuffle() method above.  They real trick to keying the deck for the cipher is
that two decks will need to be keyed identically for it to work.  Given that, I
believe Moses Hohman has a very nice solution, reading in a deck.yaml file
format as the key.  Moses also makes thorough use of unit testing in his
solution, which was a real eye opener for people like me who haven't taken the
time to learn Ruby's modules for this process.

The solution by Florian Gross is a tricky code module, you probably saw me
trying decipher out loud on Ruby Talk.  I think it's a really good example of
how to make a module that doubles as an application, once you get your head
around it.  The main trick involved is mixing the module into itself, to
duplicate its interface in its own class methods.  Those class methods provide
the stand-alone application interface, while the module can still be mixed into
future projects.  Because of this, and the fact that Florian uses a Card class,
I bet his solution adapts well to solving other hand ciphers, many of which use
a deck of cards.

Finally, Jamis Buck submitted a solution that makes use of his Copland Inversion
of Control framework for Ruby.  I don't want to say too much about this, lest my
ignorance show through, but this seems to be a handy abstraction for handling
code dependancies, among other things.  I have it installed now and am reading
the manual, so I hope to understand even more about how it works soon.  I can
already say though that I think it's worth a look, especially if you're familiar
with IoC or even Aspect Oriented Programming (feels similar to me).

Really all the solutions had interesting elements to them.  I think I saw
something clever in every last one of them, even the ones I didn't single out. 
For example, many of you convinced me I need to kick 'getoptlong' to the curb
and look into 'optparse' immediately.  The Pickaxe II just can't get here soon
enough.  My advice:  Browse through the submitted solutions when you have some
time and learn some handy tricks of the Ruby trade.

One last thing I wanted to mention, from the quiz discussion.  Dominik Werder
asked:

	So do I understand that right, Bruce Schneier claims that Solitaire is a
	real cryptographic secure pseudo random number generator?
	Cool, a PRNG for the small budget :)

I was hoping this would spark some interesting discussion, but either no one had
any thoughts on this, or everyone just Googled for the answer.

Bruce Schneier set out to design Solitaire to be the first truly secure hand
cipher.  However, Paul Crowley has found a bias in the random number generation
used by the cipher.  In other words, it's not as strong as originally intended
and being a hand cipher it does not compete with the more powerful forms of
digital encryption, naturally.

If you're interested in this or other Solitaire issues, I refer you to the
author's site:

	http://www.schneier.com/solitaire.html is The Official Solitaire Site

My thanks to those who played and those who just watched.  New quiz tomorrow and
I think it's a fun problem, so don't forget to check your e-mail even if you're
at RubyConf...