[QUIZ] The Solitaire Cipher (#1)

[Ruby Quiz]

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 (8)
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

[Jamis Buck]

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
jg...@email.byu.edu
http://www.jamisbuck.org/jamis

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

[James Edward Gray II]

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

[Jamis Buck]

Thanks for the clarification, James. This is great fun. :) I've actually
got it working! (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...)

[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

[Dominik Werder]

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 :)

[James Edward Gray II]

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

James Edward Gray II

[Bill Guindon]

On Fri, 24 Sep 2004 22:54:07 +0900, Ruby Quiz <ja...@grayproductions.net> 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)

[James Edward Gray II]

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

> On Fri, 24 Sep 2004 22:54:07 +0900, Ruby Quiz
> <ja...@grayproductions.net> 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... :D

James Edward Gray II

[Florian Gross]

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

[Jamis Buck]

(Not sure how best to post my solution, so I'm just replying to
Florian's message...figured it might be nice to keep the solutions all
in the same thread, at least...)

I agree with Florian, it was a great quiz. I'm looking forward to the
next one, too!

My solution is posted here:

http://www.jamisbuck.org/ruby-quiz-01-jamis-buck.zip

I did it using Copland, both to demonstrate Copland, and to "test"
Copland (to see if I ran into anything that needed fixing or adding).
Although the assignment itself was really too small for IoC, it was
still fun. I just ended up with many tiny classes. :)

I implemented a few other keying algorithms: shuffle (which shuffles the
deck according to a given seed value) and reverse (which just reverses
the order of an unkeyed deck).

[Carlos]

[Florian Gross <fl...@ccan.de>, 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(" ")

[Florian Gross]

Jamis Buck wrote:

> My solution is posted here:
> http://www.jamisbuck.org/ruby-quiz-01-jamis-buck.zip

Nice, I didn't know that #delete_at exists. It's a bit clearer than
#slice! where it can be used.

> I did it using Copland, both to demonstrate Copland, and to "test"
> Copland (to see if I ran into anything that needed fixing or adding).
> Although the assignment itself was really too small for IoC, it was
> still fun. I just ended up with many tiny classes. :)

Good idea -- I think it can also be used as a sample for IoC in general.

> I implemented a few other keying algorithms: shuffle (which shuffles the
> deck according to a given seed value) and reverse (which just reverses
> the order of an unkeyed deck).

Ah, I also implemented the shuffle one, but I didn't provide a way for
specifying the seed so one would have to exchange the decks via Marshal
or YAML with my solution.

Regards,
Florian Gross

[Florian Gross]

Carlos wrote:

> if b.between? ?A, ?Z

Cool, I always used (?A .. ?Z).include?(b) for this.

Regards,
Florian Gross

[Bill Guindon]

On Sun, 26 Sep 2004 23:24:26 +0900, Florian Gross <fl...@ccan.de> wrote:
> Moin!
>
> Here's my solution for the Solitaire Cipher quiz. It's fairly
> class-oriented and longish.

and another one gets added to the pile... also class oriented, just
under 200 lines with comments.

# bail if you have nothing to do.
unless ARGV[0]
print <<-STOP_PRINT
Encrypts/decrypts a string of text.
Usage: Give it some text!
STOP_PRINT
exit
end

# the obligatory deck of cards.
###############################################################################
class Deck
attr_reader :cards, :order

def initialize
@cards = []
@order = []
build_deck
end

def to_s
return @cards.to_s
end

def build_deck
[:Clubs, :Diamonds, :Hearts, :Spades].each do |suit|
rank = 0
'A23456789TJQK'.each_byte do |name|
# 'real' cards have a rank value
rank += 1
add_card(name.chr, suit, rank)
end
end

# Jokers have no rank value
'AB'.each_byte {|name| add_card(name.chr, :Joker, 0)}
end

# build order while adding.
def add_card(name, suit, rank)
card = Card.new(name, suit, rank)
@cards << card
@order << card.to_s
end

# Uses order to hunt for cards (Joker searches).
def find_card(name, suit)
return @order.index(Card.to_s(name, suit))
end

# does as many cuts as you give it.
def cut_cards(cuts)
cards = []
loc = 0
[cuts].flatten.each_with_index do |cut, idx|
cards[idx] = @cards[loc...cut]
loc = cut
end
cards << @cards[loc...@cards.length]
end

def cards=(cards)
# flatten to handle cut results.
@cards = cards.flatten
# rebuild @order each time the deck changes.
update_order
end

# simple, but not very efficient.
def update_order
@order = @cards.collect {|card| card.to_s}
end

end

# the above deck is made up of...
###############################################################################
class Card
@@SUITS = {
:Clubs => 0,
:Diamonds => 13,
:Hearts => 26,
:Spades => 39,
:Joker => 53
}

def self.to_s(name, suit)
return name + ' ' + suit.to_s + "\n"
end

attr_reader :name, :suit, :rank

def initialize(name, suit, rank)
@name = name
@suit = suit
@rank = rank + @@SUITS[suit]
end

def to_s
Card.to_s(@name, @suit)
end
end

###############################################################################
class Solitaire

attr_reader :deck

def initialize(text)
@deck = Deck.new
@text = text.to_s
end

def process
# does it look encrypted? 5 letter blocks all uppercase?
looks_encrypted = @text.gsub(/[A-Z]{5}\s?/, '').empty?
results = ''

# prep the text for parsing.
if looks_encrypted
# strip off the blanks for consistency
text = @text.gsub(/\s/, '')
else
# Discard any non A to Z characters, and uppercase all remaining
text = @text.upcase.gsub!(/[^A-Z]/, '')
# Split the message into five character groups,
words, padding = word_count(text, 5)
# using Xs to pad the last group
text += padding
end

# parse it, and build up results.
text.each_byte do |char|
if looks_encrypted
char -= next_key
char += 26 if char < 65
else
char += next_key
char -= 26 if char > 90
end
results += char.chr
end

return space_text(results, 5)
end

# counts words as 5 char blocks
def word_count(text, len)
words, strays = text.length.divmod(len)
words += 1 if strays > 0
pad = "X" * (len - strays)
return [words, pad]
end

def space_text(text, len)
# adds a space every 5 letters.
# not sure how efficient this is.
return text.unpack(('A' + len.to_s) * word_count(text, len)[0]).join(' ')
end

def shift_card(name, suit, count)
# find the card
idx = @deck.find_card(name, suit)
# remove it from the deck.
card = @deck.cards.slice!(idx)
# calculate new placement.
idx += count
# the slice above makes length 'look' zero-based
idx -= @deck.cards.length if idx > @deck.cards.length

# glue the deck together as cards before, card, cards after.
@deck.cards = @deck.cards[0...idx] + [card] +
@deck.cards[idx...@deck.cards.length]
end

def next_key
shift_card('A', :Joker, 1)
shift_card('B', :Joker, 2)

# find the 2 jokers, and sort them for the cut.
jokers = [@deck.find_card('A', :Joker), @deck.find_card('B', :Joker)].sort
# increment the 2nd joker pos -- cut uses 'up to, but not including'
jokers[1] += 1
# reverse works nicely for the triple cut.
@deck.cards = @deck.cut_cards(jokers).reverse

# get the value from the last card, and cut up to it.
cuts = @deck.cut_cards([@deck.cards.last.rank, @deck.cards.length - 1])
@deck.cards = cuts[1] + cuts[0] + cuts[2]

# read top card value, count down that many cards + 1
key = @deck.cards[@deck.cards[0].rank].rank
# convert it to a letter, adjust if needed.
key -= 26 if key > 26

# if key is still > 26, then it's a joker!
return (key) unless key > 26
# try again if it's a joker!
next_key
end
end

test = Solitaire.new(ARGV[0])
puts test.process
puts test.deck

[James Edward Gray II]

On Sep 26, 2004, at 9:39 AM, Jamis Buck wrote:

> (Not sure how best to post my solution, so I'm just replying to
> Florian's message...figured it might be nice to keep the solutions all
> in the same thread, at least...)

Sounds good to me.

My own solution is below. Eating my own dog food, as it were.

I went for a nice boring step by step translation into Ruby. No
classes. I too just treated the deck as an array of numbers and the
two jokers. I didn't provide a way to key the deck. Pretty boring
stuff here.

James Edward Gray II

#!/usr/bin/ruby -w

$deck = (1..52).to_a + ["A", "B"] # Unkeyed deck - Keystream Step 1

def encrypt(message)
# Step 1
message = message.upcase.tr("^A-Z", "")
i = 5
while i < message.size
message[i, 0] = " "
i += 6
end
message += "X" while message.rindex(" ") != message.size - 6

# Step 2
key_stream = generate(message.count("^ "))

# Step 3
values = message.split("").map { |letter| letter[0] - ?A + 1 }

# Step 4
key_values = key_stream.split("").map { |letter| letter[0] - ?A + 1 }

# Step 5
values.each_with_index do |value, index|
next if value < 0
values[index] = value + key_values[index]
values[index] -= 26 if values[index] > 26
end

# Step 6
message = (values.map { |number| (number - 1 + ?A).chr }).join("")

return message
end

def decrypt(message)
# Step 1
key_stream = generate(message.size)

# Step 2
values = message.split("").map { |letter| letter[0] - ?A + 1 }

# Step 3
key_values = key_stream.split("").map { |letter| letter[0] - ?A + 1 }

# Step 4
values.each_with_index do |value, index|
next if value < 0
if value <= key_values[index]
values[index] = value + 26 - key_values[index]
else
values[index] = value - key_values[index]
end
end

# Step 5
message = (values.map { |number| (number - 1 + ?A).chr }).join("")

return message
end

def generate(count) # Keystream Steps
key_stream = [ ]

until key_stream.size == count
# Step 2
a = $deck.index("A")
if a == 53
$deck.insert(1, $deck.pop)
else
$deck.insert(a + 1, $deck.delete_at(a))
end

# Step 3
b = $deck.index("B")
if b == 53
$deck.insert(2, $deck.pop)
elsif b == 52
$deck.insert(1, $deck.delete_at(b))
else
$deck.insert(b + 2, $deck.delete_at(b))
end

# Step 4
a = $deck.index("A")
b = $deck.index("B")
top = [a, b].min
bottom = [a, b].max
$deck = $deck.values_at((bottom + 1)..53, top..bottom, 0...top)

# Step 5
if $deck[53].kind_of? Integer
$deck = $deck.values_at($deck[53]..52, 0...$deck[53], 53)
end

# Step 5
if $deck[0].kind_of? Integer
if $deck[$deck[0]].kind_of? Integer
key_stream.push($deck[$deck[0]])
end
else
if $deck[53].kind_of? Integer
key_stream.push($deck[53])
end
end
end # Step 7

key_stream.map! do |number|
if number > 26
(number - 26 - 1 + ?A).chr
else
(number - 1 + ?A).chr
end
end
key_stream = key_stream.join("")
i = 5
while i < key_stream.size
key_stream[i, 0] = " "
i += 6
end
return key_stream
end

# Mind reading interface
if ARGV.size == 1 and ARGV[0] =~ /^(?:[A-Z]{5} )*[A-Z]{5}$/
puts decrypt(ARGV[0])
elsif ARGV.size == 1
puts encrypt(ARGV[0])
else
puts "Usage: solitaire.rb MESSAGE"
end

__END__

[Florian Gross]

James Edward Gray II wrote:

> $deck = $deck.values_at((bottom + 1)..53, top..bottom, 0...top)

Nice. Way better than doing multiple fetches and adding them together.

Regards,
Florian Gross

[Thomas Leitner]

Hello!

Very nice quiz!!! :-)

Below is my solution.

Greetings,
Thomas

#!/usr/bin/env ruby

require 'optparse'
require 'ostruct'

# 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

# Implements the Solitaire Cipher algorithm
class SolitaireCipher

# Initialize the deck
def initialize( init = -1, method = :fisher_yates )
@deck = Deck.new
@deck.shuffle( init, method ) unless init == -1
end

# Decodes the given +msg+ using the internal deck
def decode( msg )
msgNumbers = to_numbers( msg )
cipherNumbers = to_numbers( generate_keystream( msg.length ) )

resultNumbers = []
msgNumbers.each_with_index do |item, index|
item += 26 if item <= cipherNumbers[index]
temp = item - cipherNumbers[index]
resultNumbers << temp
end

return to_chars( resultNumbers )
end

# Encodes the given +msg+ using the internal deck
def encode( msg )
msg = msg.gsub(/[^A-Za-z]/, '').upcase
msg += "X"*(5 - (msg.length % 5)) unless msg.length % 5 == 0

msgNumbers = to_numbers( msg )
cipherNumbers = to_numbers( generate_keystream( msg.length ) )

resultNumbers = []
msgNumbers.each_with_index do |item, index|
temp = item + cipherNumbers[index]
temp = temp - 26 if temp > 26
resultNumbers << temp
end

return to_chars( resultNumbers )
end

private

# Converts the string of uppercase letters into numbers (A=1, B=2, ...)
def to_numbers( chars )
chars.unpack("C*").collect {|x| x - 64}
end

# Converts the array of numbers to a string (1=A, 2=B, ...)
def to_chars( numbers )
numbers.collect {|x| x + 64}.pack("C*")
end

# 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

end

options = OpenStruct.new
options.key = -1
options.shuffle = :fisher_yates
options.call_method = :decode

opts = OptionParser.new do |opts|
opts.banner = "Usage: #{File.basename($0, '.*')} [options] message"
opts.separator ""
opts.separator "Options:"
opts.on( "-d", "--decode", "Decode the message" ) do
options.call_method = :decode
end
opts.on( "-e", "--encode", "Encode the message" ) do
options.call_method = :encode
end
opts.on( "-k", "--key KEY", Integer, "Key for shuffling the deck" ) do |key|
options.key = key
end
opts.on( "-m", "--method METHOD", [:fisher_yates, :naive],
"Select the shuffling method (fisher_yates, naive" ) do |method|
options.shuffle = method
end
opts.on( "-h", "--help", "Show help" ) do
puts opts
exit
end
end

if ARGV.length == 0
puts opts
exit
end

message = opts.permute!( ARGV )[0]
cipher = SolitaireCipher.new( options.key, options.shuffle )
puts cipher.send( options.call_method, message )

[Niklas Frykholm]

My solution.

----------------------------------------------------------------------

def succ?(*a)
begin
(0..(a.size-2)).each {|i| return false if a[i].succ != a[i+1]}
return true
rescue
return false
end
end

class Deck
def initialize
@deck = (1..52).to_a + [:A, :B]
end

def move_a
move_down(@deck.index(:A))
end

def move_b
move_down(move_down(@deck.index(:B)))
end

def move_down(index)
if index < 53
new = index + 1
@deck[new], @deck[index] = @deck[index], @deck[new]
else
@deck = @deck[0,1] + @deck[-1,1] + @deck[1..-2]
new = 1
end
return new
end

def triple_cut
jokers = [@deck.index(:A), @deck.index(:B)]
top, bottom = jokers.min, jokers.max
@deck = @deck[(bottom+1)..-1] + @deck[top..bottom] + @deck[0...top]
end

def number_value(x)
return 53 if x == :A or x == :B
return x
end

def count_cut
count = number_value( @deck[-1] )
@deck = @deck[count..-2] + @deck[0,count] + @deck[-1,1]
end

def output
return @deck[ number_value(@deck[0]) ]
end

def update
move_a
move_b
triple_cut
count_cut
end

def get
while true
update
c = output
if c != :A and c != :B
letter = ( ((c-1) % 26) + 65 ).chr
return letter
end
end
end

def to_s
a = []
@deck.each_index {|i|
if succ?(a[-1], @deck[i], @deck[i+1])
a << "..."
elsif a[-1] == "..." and succ?(@deck[i-1], @deck[i], @deck[i+1])
# nop
else
a << @deck[i]
end
}
return a.join(" ")
end
end

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

def test
d = Deck.new()
d.update
puts d

e = Encrypter.new( Deck.new() )
cipher = e.encrypt('Code in Ruby, live longer!')
puts cipher

e = Encrypter.new( Deck.new() )
puts e.decrypt(cipher)

e = Encrypter.new( Deck.new() )
puts e.decrypt("CLEPK HHNIY CFPWH FDFEH")

e = Encrypter.new( Deck.new() )
puts e.decrypt("ABVAW LWZSY OORYK DUPVH")
end

test()

[Glenn M. Lewis]

# Cool fun! I found that the majority of my problems came from
# misinterpreting the directions!!! That "vice-versa" thing really
# threw me for a loop for a while (or was that a while-loop?). :-)
# Anyway, here is my solution...

#!/usr/bin/env ruby
# Solitaire Cipher
# Ruby-lang quiz #1
# Solution by Glenn M. Lewis - 9/27/04

$debug = nil

class Card
attr_reader :value, :face_value, :suit

def initialize(face_value, suit)
@face_value = face_value
@suit = suit
if suit then
@value = calc_value(face_value, suit)
return
end
case face_value
when "AJoker"
@value = 53
when "BJoker"
@value = 53
else
puts "ERROR: Unknown joker: #{joker}, should be 'AJoker' or 'BJoker'"
exit
end
end

def calc_value(face_value, suit)
val = 0
case suit
when "S" then val += 39
when "H" then val += 26
when "D" then val += 13
when "C"
else
puts "ERROR: Unknown suit: #{suit}, should be C,D,H,S"
end
case face_value
when 2..10 then val += face_value
when "A" then val += 1
when "J" then val += 11
when "Q" then val += 12
when "K" then val += 13
else
puts "ERROR: Unknown card face value: #{face_value}, should be A,2-10,J,Q,K"
end
return val
end
end

class Deck < Array
def initialize
["C", "D", "H", "S"].each do |suit|
["A", 2, 3, 4, 5, 6, 7, 8, 9, 10, "J", "Q", "K"].each do |face_value|
self.push(Card.new(face_value, suit))
end
end
self.push(Card.new("AJoker", nil))
self.push(Card.new("BJoker", nil))
@deck_size = self.size
end

def dump
self.each do |c|
if (c.value == 53)
print c.face_value
else
print c.value
end
print " "
end
print "\n\n"
if (@deck_size != self.size) then
puts "ERROR! Deck size changed to #{self.size}"
exit
end
end

def find_joker(j)
self.each_index do |i|
if (self[i].face_value == j)
return i
end
end
puts "ERROR: Could not find joker '#{j}' in deck."
end

def move_card_down(pos, num)
print "before move_card_down(#{pos}, #{num}): " if $debug
self.dump if $debug
dest = pos + num
dest -= (self.size-1) if (dest >= self.size)
card = self.delete_at(pos)
temp = self.dup
self.clear
temp.slice(0, dest).each {|x| self.push(x) }
self << card
temp.slice(dest..(-1)).each {|x| self.push(x) }
print "after move_card_down(#{pos}, #{num}): " if $debug
self.dump if $debug
end

def triple_cut_split(a, b)
a,b=b,a if (a > b)
print "before triple_cut_split(#{a}, #{b}): " if $debug
self.dump if $debug
temp = self.dup
self.clear
temp.slice((b+1)..-1).each {|x| self.push(x) }
temp.slice(a..b).each {|x| self.push(x) }
temp.slice(0..(a-1)).each {|x| self.push(x) }
print "after triple_cut_split(#{a}, #{b}): " if $debug
self.dump if $debug
end

def count_cut
print "before count_cut: " if $debug
self.dump if $debug
temp = self.dup
self.clear
num = temp[-1].value
temp.slice(num..-2).each {|x| self.push(x) }
temp.slice(0..(num-1)).each {|x| self.push(x) }
self.push(temp[-1])
print "after count_cut: " if $debug
self.dump if $debug
end

def output_letter
num = self[0].value
card = self[num]
return nil if (card.value == 53)
num = (card.value > 26 ? card.value-26 : card.value)
char = (num-1 + "A"[0]).chr
puts "card.value=#{card.value}, char=#{char}" if $debug
return char
end

def keystream_message(msg)
# result = "DWJXHYRFDGTMSHPUURXJ"
result = ""
while (result.length < msg.length) do
# Step 2 - Move the A Joker down one card
pos = find_joker("AJoker")
move_card_down(pos, 1)
# Step 3 - Move the B Joker down two cards
pos = find_joker("BJoker")
move_card_down(pos, 2)
# Step 4 - Triple cut split around two jokers
apos = find_joker("AJoker")
bpos = find_joker("BJoker")
triple_cut_split(apos, bpos)
# Step 5 - Count cut
count_cut
# Step 6 - Output letter - might be nil
letter = output_letter
result << letter if letter
end
return result
end
end

message = ARGV[0].dup

encrypted = true
encrypted = false if (message =~ /[a-z]/)
words = message.split(/\s+/)
words.each do |word|
encrypted = false if (word.length != 5)
encrypted = false if (word =~ /[^A-Z]/)
end

def message2nums(msg)
result = []
msg.each_byte do |c|
result.push(c+1-"A"[0])
end
return result
end

def nums2message(nums)
result = ""
nums.each do |val|
result << (val-1+"A"[0]).chr
end
return result
end

deck = Deck.new

if encrypted then
puts "Encrypted message: '#{message}'"
message.gsub!(/[^A-Z]/, '')

# Step 1
keystream_message = deck.keystream_message(message)
# puts "keystream_message = #{keystream_message}"

# Step 2
num_message = message2nums(message)
# puts "num_message = "
# p num_message

# Step 3
num_keystream = message2nums(keystream_message)
# puts "num_keystream = "
# p num_keystream

# Step 4
num_result = []
num_message.each_index do |index|
num_result[index] = num_message[index] - num_keystream[index]
num_result[index] += 26 if (num_result[index] < 1)
end

# Step 6
result = nums2message(num_result)
print "Unencrypted message: "
count = 0
result.each_byte do |c|
print c.chr
count += 1
print " " if ((count % 5) == 0)
end
print "\n"

else
puts "Unencrypted message: '#{message}'"

# Step 1
message.upcase!
message.gsub!(/[^A-Z]/, '')
message << "X" * ((message.length % 5)==0 ? 0 : (5-(message.length % 5)))
# puts "message: #{message}"

# Step 2
keystream_message = deck.keystream_message(message)
# puts "keystream_message = #{keystream_message}"

# Step 3
num_message = message2nums(message)
# puts "num_message = "
# p num_message

# Step 4
num_keystream = message2nums(keystream_message)
# puts "num_keystream = "
# p num_keystream

# Step 5
num_result = []
num_message.each_index do |index|
num_result[index] = num_message[index] + num_keystream[index]
num_result[index] -= 26 if (num_result[index] > 26)
end

# Step 6
result = nums2message(num_result)
print "Encrypted message: "
count = 0
result.each_byte do |c|
print c.chr
count += 1
print " " if ((count % 5) == 0)
end
print "\n"
end

[James Edward Gray II]

On Sep 27, 2004, at 4:49 PM, Glenn M. Lewis wrote:

> # Cool fun! I found that the majority of my problems came from
> # misinterpreting the directions!!! That "vice-versa" thing really
> # threw me for a loop for a while (or was that a while-loop?). :-)

That's probably largely my fault and I apologize. That would be the
first quiz I ever wrote, so I'm sure I mangled it in places. I'll see
if I can't improve with practice. ;) (Note to self: Don't use
"vice-versa".)

> # Anyway, here is my solution...

Thanks for hanging in there and getting a solution together.

James Edward Gray II

[James Edward Gray II]

On Sep 26, 2004, at 9:24 AM, Florian Gross wrote:

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

Help. <laughs> I'm trying to figure this code out...

> module Solitaire
> extend self

# snip module definition...

> end

I'm trying to understand the above trick:

extends self

would be the same as:

self.extends self

Which just leaves the question of what is self? Obviously, it has to
be the module itself. That means we added the methods to the module
itself?

That doesn't make sense alone; however, I know extending a module in
in a class definition adds the module methods as class methods. If I
assume the same is happening here...

My guess: You duplicated all of Solitaires' methods as class methods?

If I'm right, you could have done the same by declaring all those
methods as:

def Solitaire.<method_name>...

Right?

Hmm, wait. Not quite. Then you would be missing the instance methods.

So why did you write it this way?

Big Guess (really reaching now): To provide a convenient interface to
use the module stand-alone while also allowing it to be mixed into
future creations?

Thanks for the lesson.

James Edward Gray II

[Jim Menard]

YAQS (Yet Another Quiz Solution): I've created
http://www.io.com/~jimm/rubyquiz/ to hold my solutions. My answer to quiz 1
can be found at http://www.io.com/~jimm/rubyquiz/quiz1/.

Jim
--
Jim Menard, ji...@io.com, http://www.io.com/~jimm

[Florian Gross]

James Edward Gray II wrote:

> I'm trying to understand the above trick:
>
> extends self
>

> My guess: You duplicated all of Solitaires' methods as class methods?
>

> [snip]

>
> So why did you write it this way?
>
> Big Guess (really reaching now): To provide a convenient interface to
> use the module stand-alone while also allowing it to be mixed into
> future creations?

Exactly. I think the same would be done if I had used a standalone
module_function(), but then all the instance methods would also be private.

It's interesting how Ruby's object model lets you do things like this.

> Thanks for the lesson.

Glad I could give it. :)

Regards,
Florian Gross

[Dennis Ranke]

Here is my solution, just one Deck class, no guessing:

###

class Deck
def initialize
@deck = Array.new(54) {|i| i}
end

def create_keystream(count)
stream = []
count.times do
letter = next_letter
redo unless letter
stream << letter
end
return stream
end

def next_letter
##
# move the jokers
##

2.times do |j|
# find the joker
index = @deck.index(52 + j)

# remove it from the deck

@deck.delete_at(index)

# calculate new index
index = ((index + j) % 53) + 1

# insert the joker at that index
@deck[index, 0] = 52 + j
end

##
# do the tripple cut
##

# first find both jokers
a = @deck.index(52)
b = @deck.index(53)

# sort the two indeces
low, hi = [a, b].sort

# get the lower and upper parts of the deck
upper = @deck.slice!((hi + 1)..-1)
lower = @deck.slice!(0, low)

# swap them
@deck = upper + @deck + lower

##
# do the count cut
##

# find out the number of cards to cut
count = value_at(53)

# remove them from the top of the deck
cards = @deck.slice!(0, count)

# reinsert them just above the lowest card
@deck[-1, 0] = cards

return letter_at(value_at(0))
end

def value_at(index)
id = @deck[index]
(id > 51) ? 53 : id + 1
end

def letter_at(index)
id = @deck[index]
(id > 51) ? nil : (id % 26) + 1
end

def to_s
@deck.map {|v| (v > 51) ? (v + 13).chr : (v + 1).to_s}.join(' ')
end
end

def encode(data, keystream)
result = []
data.size.times {|i| result << ((data[i] + keystream[i]) % 26)}
return result
end

def decode(data, keystream)
encode(data, keystream.map {|v| 26 - v})
end

def data_to_string(data)
data = data.map {|v| (v + 65).chr}.join
(0...(data.size / 5)).map {|i| data[i * 5, 5]}.join(' ')
end

if ARGV.size != 1
puts "Usage: solitaire.rb MESSAGE"
exit
end

data = ARGV[0].upcase.split(//).select {|c| c =~ /[A-Z]/}.map {|c| c[0] -
65}
data += [?X - 65] * (4 - (data.size + 4) % 5)

deck = Deck.new
keystream = deck.create_keystream(data.size)

puts 'encoded:', data_to_string(encode(data, keystream))
puts 'decoded:', data_to_string(decode(data, keystream))

###

That was fun to code :)

--
exoticorn/farbrausch