[SUMMARY] The Solitaire Cipher (#1)


R

Ruby Quiz

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, a[j] = a[j], a if i != j
}
end

# From pleac.sf.net
def naive_shuffle( a )
for i in 0...a.size
j = rand(a.size)
a, a[j] = a[j], a
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...
 
Ad

Advertisements

R

Raphael Bauduin

Ruby said:
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...

Thank you for the quiz. I really liked your summary!

Raph (just a reader for this one)
 
Ad

Advertisements

J

James Edward Gray II

Thank you for the quiz. I really liked your summary!

And I really appreciate you saying so. Thanks.
Raph (just a reader for this one)

Well, I hope you'll join us for future quizzes and give one a whirl.

James Edward Gray II
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top