R
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
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