«

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.grayproductions.net/ruby_quiz/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Cryptologist Bruce Schneier designed the hand cipher "Solitaire" for Neal
Stephenson's book "Cryptonomicon". Created to be the first truly secure hand
cipher, Solitaire requires only a deck of cards for the encryption and
decryption of messages.

While it's true that Solitaire is easily completed by hand given ample time,
using a computer is much quicker and easier. Because of that, Solitaire
conversion routines are available in many languages, though I've not yet run
across one in Ruby.

This week's quiz is to write a Ruby script that does the encryption and
decryption of messages using the Solitaire cipher.

Let's look at the steps of encrypting a message with Solitaire.

1. Discard any non A to Z characters, and uppercase all remaining letters.
Split the message into five character groups, using Xs to pad the last group, if
needed. If we begin with the message "Code in Ruby, live longer!", for example,
we would now have:

CODEI NRUBY LIVEL ONGER

2. Use Solitaire to generate a keystream letter for each letter in the message.
This step is detailed below, but for the sake of example let's just say we get:

DWJXH YRFDG TMSHP UURXJ

3. Convert the message from step 1 into numbers, A = 1, B = 2, etc:

3 15 4 5 9 14 18 21 2 25 12 9 22 5 12 15 14 7 5 18

4. Convert the keystream letters from step 2 using the same method:

4 23 10 24 8 25 18 6 4 7 20 13 19 8 16 21 21 18 24 10

5. Add the message numbers from step 3 to the keystream numbers from step 4 and
subtract 26 from the result if it is greater than 26. For example, 6 + 10 = 16
as expected, but 26 + 1 = 1 (27 - 26):

7 12 14 3 17 13 10 1 6 6 6 22 15 13 2 10 9 25 3 2

6. Convert the numbers from step 5 back to letters:

GLNCQ MJAFF FVOMB JIYCB

That took a while to break down, but it's really a very simple process.
Decrypting with Solitaire is even easier, so let's look at those steps now.
We'll work backwards with our example now, decrypting "GLNCQ MJAFF FVOMB JIYCB".

1. Use Solitaire to generate a keystream letter for each letter in the message
to be decoded. Again, I detail this process below, but sender and receiver use
the same key and will get the same letters:

DWJXH YRFDG TMSHP UURXJ

2. Convert the message to be decoded to numbers:

7 12 14 3 17 13 10 1 6 6 6 22 15 13 2 10 9 25 3 2

3. Convert the keystream letters from step 1 to numbers:

4 23 10 24 8 25 18 6 4 7 20 13 19 8 16 21 21 18 24 10

4. Subtract the keystream numbers from step 3 from the message numbers from
step 2. If the keystream number is less than or equal to the message number,
add 26 to the keystream number before subtracting. For example, 22 - 1 = 21 as
expected, but 1 - 22 = 5 (27 - 22):

3 15 4 5 9 14 18 21 2 25 12 9 22 5 12 15 14 7 5 18

5. Convert the numbers from step 4 back to letters:

CODEI NRUBY LIVEL ONGER

Transforming messages is that simple. Finally, let's look at the missing piece
of the puzzle, generating the keystream letters.

First, let's talk a little about the deck of cards. Solitaire needs a full deck
of 52 cards and the two jokers. The jokers need to be visually distinct and
I'll refer to them below as A and B. Some steps involve assigning a value to
the cards. In those cases, use the cards face value as a base, Ace = 1, 2 =
2... 10 = 10, Jack = 11, Queen = 12, King = 13. Then modify the base by the
bridge ordering of suits, Clubs is simply the base value, Diamonds is base value
+ 13, Hearts is base value + 26, and Spades is base value + 39. Either joker
values at 53. When the cards must represent a letter Clubs and Diamonds values
are taken to be the number of the letter (1 to 26), as are Hearts and Spades
after subtracting 26 from their value (27 to 52 drops to 1 to 26). Now let's
make sense of all that by putting it to use.

1. Key the deck. This is the critical step in the actual operation of the
cipher and the heart of it's security. There are many methods to go about this,
such as shuffling a deck and then arranging the receiving deck in the same order
or tracking a bridge column in the paper and using that to order the cards.
Because we want to be able to test our answers though, we'll use an unkeyed
deck, cards in order of value. That is, from top to bottom, we'll always start
with the deck:

Ace of Clubs
...to...
King of Clubs
Ace of Diamonds
...to...
King of Diamonds
Ace of Hearts
...to...
King of Hearts
Ace of Spades
...to...
King of Spades
"A" Joker
"B" Joker

2. Move the A joker down one card. If the joker is at the bottom of the deck,
move it to just below the first card. (Consider the deck to be circular.) The
first time we do this, the deck will go from:

1 2 3 ... 52 A B

To:

1 2 3 ... 52 B A

3. Move the B joker down two cards. If the joker is the bottom card, move it
just below the second card. If the joker is the just above the bottom card,
move it below the top card. (Again, consider the deck to be circular.) This
changes our example deck to:

1 B 2 3 4 ... 52 A

4. Perform a triple cut around the two jokers. All cards above the top joker
move to below the bottom joker and vice versa. The jokers and the cards between
them do not move. This gives us:

B 2 3 4 ... 52 A 1

5. Perform a count cut using the value of the bottom card. Cut the bottom
card's value in cards off the top of the deck and reinsert them just above the
bottom card. This changes our deck to:

2 3 4 ... 52 A B 1 (the 1 tells us to move just the B)

6. Find the output letter. Convert the top card to it's value and count down
that many cards from the top of the deck, with the top card itself being card
number one. Look at the card immediately after your count and convert it to a
letter. This is the next letter in the keystream. If the output card is a
joker, no letter is generated this sequence. This step does not alter the deck.
For our example, the output letter is:

D (the 2 tells us to count down to the 4, which is a D)

7. Return to step 2, if more letters are needed.

For the sake of testing, the first ten output letters for an unkeyed deck are:

D (4) W (49) J (10) Skip Joker (53) X (24) H (
Y (51) R (44) F (6) D (4) G (33)

That's all there is to Solitaire, finally. It's really longer to explain than
it is to code up.

Solutions to this quiz should accept a message as a command line argument and
encrypt or decrypt is as needed. It should be easy to tell which is needed by
the pattern of the message, but you can use a switch if you prefer.

All the examples for this quiz assume an unkeyed deck, but your script can
provide a way to key the deck, if desired. (A real script would require this,
of course.)

Here's a couple of messages to test your work with. You'll know when you have
them right:

CLEPK HHNIY CFPWH FDFEH

ABVAW LWZSY OORYK DUPVH

Ruby Quiz wrote:

> 5. Perform a count cut using the value of the bottom card. Cut the bottom
> card's value in cards off the top of the deck and reinsert them just above the
> bottom card. This changes our deck to:
>
> 2 3 4 ... 52 A B 1 (the 1 tells us to move just the B)
>
> 6. Find the output letter. Convert the top card to it's value and count down
> that many cards from the top of the deck, with the top card itself being card
> number one. Look at the card immediately after your count and convert it to a
> letter. This is the next letter in the keystream. If the output card is a
> joker, no letter is generated this sequence. This step does not alter the deck.
> For our example, the output letter is:
>
> D (the 2 tells us to count down to the 4, which is a D)

Step six says that the "top card itself [is] card number one". That
said, if I count 2 from the top, with the top card being #1, shouldn't
that have given me a 3 (per the listing in step 5), instead of a 4?
Which means the first output letter would be "C"...

Am I missing something? Did I misread the instructions, or is there an
error there?

- Jamis

--
Jamis Buck

http://www.jamisbuck.org/jamis

"I use octal until I get to 8, and then I switch to decimal."

On Sep 24, 2004, at 12:39 PM, Jamis Buck wrote:

> Ruby Quiz wrote:
>
>> 6. Find the output letter. Convert the top card to it's value and
>> count down
>> that many cards from the top of the deck, with the top card itself
>> being card
>> number one. Look at the card immediately after your count and
>> convert it to a
>> letter. This is the next letter in the keystream. If the output
>> card is a
>> joker, no letter is generated this sequence. This step does not
>> alter the deck.
>> For our example, the output letter is:
>> D (the 2 tells us to count down to the 4, which is a D)
>
> Step six says that the "top card itself [is] card number one". That
> said, if I count 2 from the top, with the top card being #1, shouldn't
> that have given me a 3 (per the listing in step 5), instead of a 4?
> Which means the first output letter would be "C"...
>
> Am I missing something? Did I misread the instructions, or is there an
> error there?

The top card is number one, yes, and you do count down two cards. The
instructions for step 6 say, immediately after that, "Look at the card
immediately after your count and...". So card 2 is number 1, card 3 is
number 2 and the card immediately after that count is card 4.

I apologize if it isn't clear. I was disappointed with how long and
complex I made that quiz look, it's actually a super simple procedure.

James Edward Gray II

On Sep 24, 2004, at 1:15 PM, Jamis Buck wrote:

> Thanks for the clarification, James.

My pleasure.

If anyone ever has trouble reading my quiz babble, don't hesitate to
ask. I'll try to watch for clarification requests.

> This is great fun. I've actually got it working!

I'm glad you enjoyed it. That's the idea.

> (I did it the hard way, though, using Copland...I figured it might be
> another good way to demonstrate how to use IoC, even though the
> assignment is really much too small to use IoC efficiently...)

Well, since I'm 100% Copland ignorant, I look forward to seeing your
solution. Don't forget to post it after the No-Spoiler Period expires.

James Edward Gray II

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

On Sep 25, 2004, at 12:04 PM, Dominik Werder wrote:

> So do I understand that right, Bruce Schneier claims that Solitair is
> a real cyrptographic secure pseudo random number generator?
> Cool, a PRNG for the small budget

The real question is, do you think he's right?

James Edward Gray II

On Fri, 24 Sep 2004 22:54:07 +0900, Ruby Quiz <> wrote:

> 1. Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.

Maybe a fixed cutoff would be best... nothing before Sunday at **pm
(GMT or UTC) no matter when it's posted.

> 5. Convert the numbers from step 4 back to letters:
>
> CODEI NRUBY LIVEL ONGER

> Solutions to this quiz should accept a message as a command line argument and
> encrypt or decrypt is as needed. It should be easy to tell which is needed by
> the pattern of the message, but you can use a switch if you prefer.

What if you fed it the output from above, exactly as is? Either
you're assuming that "normal" text is fed into it, or you have
seriously overestimated my regex abilities

An amusing little puzzle. You're off to a great start

--
Bill Guindon (aka aGorilla)

On Sep 25, 2004, at 6:27 PM, Bill Guindon wrote:

> On Fri, 24 Sep 2004 22:54:07 +0900, Ruby Quiz
> <> wrote:
>
>> 1. Please do not post any solutions or spoiler discussion for this
>> quiz until
>> 48 hours have passed from the time on this message.
>
> Maybe a fixed cutoff would be best... nothing before Sunday at **pm
> (GMT or UTC) no matter when it's posted.

One of the early quizzes for the Perl Quiz of the Week was to take an
e-mail on STDIN and determine if it was okay to send spoilers yet. Do
we need to do that one too?

I believe the assumption is that eventually I'll be a day or two late.
When that happens the No-Spoiler Period will still function as intended
the way I have it now.

I actually changed the period to 48 hours to make it super easy to
calculate at a glance. Just read the Date: field and add two days.

Also, discussion is not a problem. Just hold off on the spoilers,
hints and solutions until the 48 hours pass. Everything I've seen so
far has been fine.

>> 5. Convert the numbers from step 4 back to letters:
>>
>> CODEI NRUBY LIVEL ONGER
>
>> Solutions to this quiz should accept a message as a command line
>> argument and
>> encrypt or decrypt is as needed. It should be easy to tell which is
>> needed by
>> the pattern of the message, but you can use a switch if you prefer.
>
> What if you fed it the output from above, exactly as is? Either
> you're assuming that "normal" text is fed into it, or you have
> seriously overestimated my regex abilities

I'm a reasonable interface kind of guy.

When I'm typing in a message to be encoded, I don't want to think in
all caps and five character increments, so I won't. When I'm decoding
a message, I know nothing about that string of letters and thus will
enter it as is (probably with copy and paste).

Knowing that, my program has the perfect clue to tell what I want,
without me prompting it. I like my software to read my mind like this.
It makes me feel loved. If this bothers you, or you already feel
loved enough, feel free to use a switch. I won't mind.

This was just a tidbit I threw in for fun. It's not the heart of the
quiz, obviously.

> An amusing little puzzle. You're off to a great start

Thank you. I really appreciate that. I enjoy little code challenges
and I hope others are enjoying them too.

Tune in next week...

James Edward Gray II

Moin!

Here's my solution for the Solitaire Cipher quiz. It's fairly
class-oriented and longish.

There's support for generating either a completely random key or one
that's based on a word file.

I had to fight a nasty bug in my KeyStream generator while writing this
(I screwed up the triple cut) -- I think it would have been easier to
solve if I had developed test-first.

This was a nice quiz and I eagerly look forward to the next one. Thank
you.

Regards,
Florian Gross


class Array
# Moves the item from a specified index to
# just before the item with the specified index.
def move(from_index, to_index)
from_index += self.size if from_index < 0
to_index += self.size if to_index < 0

item = self.slice!(from_index)
self.insert(to_index, item)
end
end

module Solitaire
extend self

Letters = ('A' .. 'Z').to_a

class Card < Struct.new(:face, :type)
Faces = [:ace, :two, :three, :four, :five, :six, :seven,
:eight, :nine, :ten, :jack, :queen, :king]
Types = [:clubs, :diamonds, :hearts, :spades, :special]
SpecialFaces = [:joker_a, :joker_b]

def self.deck
Types.map do |type|
if type == :special
SpecialFaces.map do |face|
new(face, type)
end
else
Faces.map do |face|
new(face, type)
end
end
end.flatten
end

def special?; type == :special; end

def value
if special? then 53
else
Faces.index(face) + 1 + 13 * Types.index(type)
end
end

def letter
Letters[(value - 1) % 26]
end

def name
if face == :joker_a then "JokerA"
elsif face == :joker_b then "JokerB"
else
face_str = face.to_s.capitalize.gsub(/_(\w)/) { $1.upcase }
type_str = type.to_s.capitalize
face_str + " of " + type_str
end
end

def compact_inspect
if face == :joker_a then "A"
elsif face == :joker_b then "B"
else value end
end

def inspect
"#<#{self.class} #{name} (#{letter}/#{value})>"
end
alias :to_s :inspect

deck.each do |card|
const_set(card.name.sub(" of ", "Of"), card)
end
end

class KeyStream
def initialize(key_method = nil)
case key_method
when true then
@deck = Card.deck.sort_by { rand }
when String then
@deck = Card.deck
generate_letter(key_method)
else
@deck = Card.deck
end
end

def generate_letter(seed_phrase = nil)
if seed_phrase
seed_phrase = Solitaire.clean(seed_phrase)
seed_phrase = nil if seed_phrase.empty?
end

result = nil

until result
deck_size = @deck.size

# Move JokerA down one card
old_a_pos = @deck.index(Card::JokerA)
new_a_pos = case old_a_pos
when deck_size - 1 then 1
else old_a_pos + 1
end
@deck.move(old_a_pos, new_a_pos)

# Move JokerB down two cards
old_b_pos = @deck.index(Card::JokerB)
new_b_pos = case old_b_pos
when deck_size - 1 then 2
when deck_size - 2 then 1
else old_b_pos + 2
end
@deck.move(old_b_pos, new_b_pos)

# Perform triple cut
top_pos, bot_pos = [@deck.index(Card::JokerA), @deck.index(Card::JokerB)].sort
@deck.replace(
@deck[(bot_pos + 1) .. -1] +
@deck[top_pos .. bot_pos] +
@deck[0 ... top_pos])

# Perform count cut
top = @deck.slice!(0 ... @deck.last.value)
@deck.insert(-2, *top)

if seed_phrase
key = seed_phrase.slice!(0, 1)
top = @deck.slice!(0 ... Solitaire.letter_to_number(key))
@deck.insert(-2, *top)
result = true if seed_phrase.empty?
else
# Fetch result
card = @deck[@deck.first.value]
result = card.letter unless card.special?
end
end

return result
end
alias :shift :generate_letter
end

def letter_to_number(letter)
Letters.index(letter) + 1
end

def number_to_letter(number)
Letters[number - 1]
end

def clean(text)
text.upcase.delete("^A-Z")
end

def pretty(text)
clean(text).scan(/.{1,5}/).join(" ")
end

def encrypt(raw_text, keystream = nil, pretty = true)
keystream ||= KeyStream.new
text = clean(raw_text)
text += "X" * ((text.size / 5.0).ceil * 5 - text.size)

result = ""
0.upto(text.size - 1) do |index|
source_num = letter_to_number(text[index, 1])
key_num = letter_to_number(keystream.shift)
result << number_to_letter((source_num + key_num) % 26)
end

result = pretty(result) if pretty
return result
end

def decrypt(raw_text, keystream = nil, pretty = true)
keystream ||= KeyStream.new
text = clean(raw_text)

result = ""
0.upto(text.size - 1) do |index|
source_num = letter_to_number(text[index, 1])
key_num = letter_to_number(keystream.shift)
result << number_to_letter((source_num - key_num) % 26)
end

result = pretty(result) if pretty
return result
end
end

if __FILE__ == $0
require 'optparse'

options = {
:mode => nil,
:keystream => nil,
:keylength => 80,
:text => nil
}

ARGV.options do |opts|
script_name = File.basename($0)
opts.banner = "Usage: ruby #{script_name} [options]"

opts.separator ""

opts.on("-d", "--decrypt",
"Decrypt an encrypted message.",
"This is the default if the message looks encrypted.") do
options[:mode] = :decrypt
end
opts.on("-e", "--encrypt",
"Encrypt an unencrypted message.") do
options[:mode] = :encrypt
end
opts.on("-m", "--message message",
"Specify the message.",
"Default: Read from terminal.") do |text|
options[:text] = text
end
opts.on("-k", "--key=key",
"Specify the key that will be used for shuffling the deck.",
"Default: Use an unshuffled deck.") do |key|
options[:keystream] = Solitaire::KeyStream.new(key)
end
opts.on("-R", "--random-key length", Integer,
"Use a randomly generated key for shuffling the deck.",
"The key length can be specified. It defaults to 80.",
"The key will be printed to the first line of STDOUT.") do |width|
options[:keylength] = width if width
options[:keystream] = :random
end
opts.on("-W", "--word-key file",
"Use a randomly generated key phrase.",
"It will consist of random words in the specified file.",
"The key length can be specified via the -R option.",
"The key phrase and the key will be printed to STDOUT.") do |word_file|
options[:keystream] = :random_words
options[:word_file] = word_file
end

opts.separator ""

opts.on("-h", "--help",
"Show this help message.") do
puts opts; exit
end

opts.parse!
end

input = options[:text] || STDIN.read

options[:mode] = :decrypt if /\A(?:[A-Z]{5}\s*)+\Z/.match(input)

case options[:keystream]
when :random then
key = Array.new(options[:keylength]) { Solitaire::Letters[rand(26)] }.join

puts "Key: " + Solitaire.pretty(key)
options[:keystream] = Solitaire::KeyStream.new(key)
when :random_words then
begin
words = File.read(options[:word_file]).scan(/\w+/)
rescue
STDERR.puts "Word file doesn't exist or can't be read."
exit -1
end

words_size = words.size

min_words = options[:keylength] / 6
if words_size < min_words
STDERR.puts "Word file must contain at least #{min_words} words," +
" but it contains only #{words_size} words!"
exit -2
end

key = []
until key.join("").length >= options[:keylength]
key << words[rand(words_size)]
end
key = key.join(" ")

puts "Keyphrase: " + key
puts "Key: " + Solitaire.pretty(key)
options[:keystream] = Solitaire::KeyStream.new(key)
end

if options[:mode] == :decrypt
puts Solitaire.decrypt(input, options[:keystream])
else
unless options[:keystream]
STDERR.puts "WARNING: Using an unshuffled deck for encrypting!"
end
puts Solitaire.encrypt(input, options[:keystream])
end
end

[Florian Gross <>, 2004-09-26 16.24 CEST]
> Here's my solution for the Solitaire Cipher quiz. It's fairly
> class-oriented and longish.
>
> There's support for generating either a completely random key or one
> that's based on a word file.

Well, here is mine. It's not class oriented, doesn't allow to key the deck
and doesn't guess anything .

I discarded all these "card" notions and used only numbers (and jokers) .

I liked this quiz very much.

The code:

class Numeric
def value
self
end

def to_letter
((self-1)%26 + ?A).chr
end
end

class String
# returns an array with the code of the letters,
# padded with the code of X
def to_numbers
res=upcase.unpack("C*").collect { |b|
if b.between? ?A, ?Z
b - ?A + 1
else
nil
end
}.compact
# 24 == X
res.fill 24, res.length, (5 - res.length % 5) % 5
end

def crypt (deck, decrypt=false)
numbers = to_numbers
keystream = deck.generate_keystream numbers.length
result = ""
numbers.zip(keystream) do |n, k|
k = -k if decrypt
result << (n+k).to_letter
end
result
end

def encrypt (deck)
crypt deck, false
end

def decrypt (deck)
crypt deck, true
end
end

class Joker
def value
53
end
end

A = Joker.new
B = Joker.new

class Array
def wrap_down pos
pos %= length
if pos == 0
pos = length
end
pos
end

def next_key
# step 2: move A joker down 1 card
pos = index A
slice! pos
pos = wrap_down(pos + 1)
self[pos, 0] = A

# step 3: move B joker down 2 cards
pos = index B
slice! pos
pos = wrap_down(pos + 2)
self[pos, 0] = B

# step 4: triple cut
first_joker, second_joker = [index(A), index(B)].sort
cards_above = slice! 0...first_joker
second_joker -= cards_above.length
cards_below = slice! second_joker+1..-1
push *cards_above
unshift *cards_below

# step 5: count cut using the value of the bottom card.
# reinsert above the last card
cut = slice! 0, last.value
self[-1,0] = cut

# step 6: find the letter
card = self[first.value]

return Joker===card ? nil : card.value
end

def generate_keystream len
(1..len).collect {|i| next_key or redo }
end
end

def new_deck
(1..52).to_a + [A, B]
end

res = if ARGV[0] == "-d"
ARGV[1..-1].join("").decrypt(new_deck)
else
ARGV.join("").encrypt(new_deck)
end

puts res.scan(/.{5}/).join(" ")