Using playing cards to store hidden data:
The Implied Card Method for
Encoding Data Into Playing Cards.
The Basic Implied Card Method:
This method involves having a set order for a pack of cards. Each card's position in the pack represents a 1 or 0. If the card is absent from its position then there is an implied 0; if the card is present then it represents a 1. As we know the order of the pack we can tell if a card is absent. To encode the 4-bit binary number 1011 (eleven in decimal), we do as follows:
First we lay out the cards:
Then we take out the card that will represent the zero, and leave the cards that will represent 1s:
Despite the card no longer being there, we know that it should be there as the cards were in order when we started:
The absent card is put at the back of the pack and will be used again when it comes around the next time. We will know the order of that part of the pack when it does come around again, because we know which cards were removed the first time around and the order in which they were removed. Therefore we can carry on with this method of keeping 1s in position and putting 0s at the back of the pack until we have run out of cards to use.
By passing absent cards to the back of the pack and using them again, it allows us (usually) to encode far more than 52 bits of data.
The method is most easily explained with an in-depth example. Choose an order for a pack of cards that you will stick with. I use Aces to Kings for each suit in the order of Spades, Clubs, Hearts, then Diamonds.
Basic encoding example:
In this example, I'll be encoding into the cards all the 4-bit binary numbers in order from 0001 to 1111 (In other words the binary equivalents of the decimal numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15). We could just as easily encode 2-bit, 3-bit, 5-bit numbers etc, or just a string of unrelated ones and zeroes.
We lay out the cards face up, in order on a large table (or the floor) in groups of 4. Then starting at the beginning we'll convert the cards into the binary equivalent of the number we want them to represent. The first number will be 0001 so we'll remove the first, second and third cards and leave the fourth. In other words the only card left of that group will be the 4 of Spades. The removed (absent) cards (Ace, 2, and 3 of Spades) are put *in order* at the end of the whole set of laid out cards (i.e. after the King of Diamonds).
Next we want 0010 (2 in decimal) so from the next group of four cards we remove the first, second and fourth ones, while leaving the third in place. This leaves the 7 of Spades. The removed cards (5, 6, and 8 of Spades) are again put in order at the end of the laid out cards. The removed cards can now start to form groups of four themselves.
For the next group of four we want 0011 (3 in decimal) so we remove the first two and leave the second two. The remaining cards are the Jack and Queen of Spades.
We continue like this until eventually we have been through the entire pack once and end up once more at the Ace of Spades, which on the first run represented a zero so was removed as an absent card. At this point we will be about to encode the binary number 1110 (14 in decimal). The cards that we removed and passed to the back of the pack have a new set position and order. Where they are and where they should be can be worked out from the fact they were absent before. Therefore the Implied Card Method will continue to work here, and it will continue to work all the way through until we have no more cards to use.
In our example, at this point we are encoding 1110 into in this group of four previously removed cards (the Ace, 2, 3 and 5 of Spades). We keep the first three cards and take out the fourth (the 5 of Spades). We put the removed 5 of Spades at the end of the pack of laid out cards as before. The next number is 1111 (15 in decimal) which is the highest number we can represent with 4 bits. The cards in this group are the 6, 8, 9 and 10 of Spades. We keep them all. We could stop here but let's reset our counter and continue encoding into this pack. To make things different this time we'll start at 0000 (zero) and count up from there. The next group of four in the pack consists of the King of Spades and the 2, 3 and 4 of Clubs. As our number is 0000 we take all four cards and put them all at the back of the pack. One of the oddities of this method is that zeroes don't actually use up any cards. All those four cards will be used to encode further numbers in this pack when they come round again next time. I'll explain more about this later, but for now we'll continue counting. Our next number is 0001. The cards in the associated group of four are the 6, 8, Jack, and Queen of Clubs. We put the 6, 8 and Jack at the back and keep the Queen.
We continue counting until eventually we'll run out of enough cards to encode a 4-bit number. The second-last 4-bit number we can do is 1001 (9 in decimal). The cards are the 3 of Clubs, the 6 Clubs, the 4 of Hearts and the 5 of Hearts. We keep the 3 and the 5 and put the 6 and the 4 at the back of the pack. When we are at the very last number, 1010 (10 in decimal), there will be the Queen of Diamonds, the 5 of Spades, the King of Spades and the 6 of Clubs. The 5 and 6 go to the back of the pack while we keep the Queen and the King.
At this point there are only three cards left. Technically it is sometimes possible to encode a 4-bit number with three cards if there are enough zeroes in it, but to keep this more simple, we'll stop here. The remaining cards, in order, are the 4 of hearts, the 5 of spades and the 6 of Clubs.
If you are trying this yourself, then comparing the remaining cards in this and the following examples can help you see if your encoding was correct or if you made any mistakes. The remaining cards are equivalent to a very half-hearted checksum. There will be many different encodings that will produce the same leftover cards, however you can be sure that if your last cards are different then you (or I) have made a mistake somewhere.
At this point the sequence of binary numbers is completely encoded within the sequence of the cards. Pick up the laid out cards in order that we went through them, so the first card is face up at the top of the pack, and the last card (the 6 of Clubs) is face up at the bottom of the pack. Including the final unused meaningless cards keeps all 52 cards together, and won't confuse matters as long as the person decoding them knows the context behind what has been encrypted. The remaining cards if left in order will all represent 1s when decoded and it will usually be clear that the message has ended.
When you understand the encoding method then laying out the cards on a table or floor isn't really necessary and you can sort them in your hands to save the trouble of picking them all up afterwards. Laying them out on the floor just made it clearer as to what was going on.
Counting from 0001 to 1111 and then from 0000 to 1010 means we can represent 26 4-bit numbers (104 bits) in 49 cards with 3 cards left over, when other more simple methods would only get 13 4-bit numbers (52 bits) with a pack of 52. This is because the absent cards that represent zeroes are put to the back of the pack and used again. In the above example the five of Spades and the Six of Clubs are 'absent' five times, so act as zeroes in five different numbers. The more zeroes there are in the binary numbers involved, the more cards we can use several times, so the more numbers can be represented with just one pack.
As we saw, the number 0000 doesn't actually use any cards. All the cards are passed to the back of the pack. This is one of the paradoxes of this method - some numbers can be encoded without reducing the number of cards available for encoding other numbers.
Despite the encoding of a zero not actually using any cards, there is a limit to the number of repeating zero numbers you can use. You couldn't have a million 0000 4-bit numbers with 52 cards. At some point the cards that get to the back of the pack would end up in exactly the same order and position as at the beginning of the encoding. There would be no difference to the pack if the zeroes had never even been encoded, and when the cards are decoded the numbers wouldn't appear. The point where an uninterrupted string of zeroes become invisible occurs when there are the same amount of zeroes (or more) as there are remaining cards to be used for encoding. To stop it happening at least one card at the back of the pack at the time the zero string starts must be used to represent a 1.
If a whole pack is zeroed from the very start then, for 4-bit 0000s, it will repeat (the consecutive zeroes will become invisible) when all 52 cards have been used, which happens after thirteen 4-bit numbers have been encoded. The maximum number of consecutive 4-bit 0000s encodable in a full pack is 12. After the thirteenth number the pack is in exactly the same order as it was to start with so there is no way of telling if there are 52 absent cards or none at all. For zero numbers made up of say 3-bits or 5-bits (i.e. that aren't a neat divisor of 52) then when the pack wraps around it will be impossible to tell if there is a whole string of zeroes or some other valid number instead. Eleven 5-bit numbers would end up with the bits 00011 appearing at the start of a pack. This would be decoded as the number 3, which not only means the zeroes are all invisible but that we've started decoding nonsense.
It makes sense to be aware of this potential pitfall. Always make sure that there will be at least one 1 before you reach the end of the cards in the rest of the pack at the exact moment you start a very long string of zeroes.
Decoding the pack:
To decode a pack of cards, first write out the names and suits of the cards in order in a row across the top of a piece of paper:
Or if that picture is too small:
Spades: A 2 3 4 5 6 7 8 9 10 Jack Queen King; Clubs: A 2 3 4 5 6 7 8 9 10 Jack Queen King; Hearts: A 2 3 4 5 6 7 8 9 10 Jack Queen King; Diamonds: A 2 3 4 5 6 7 8 9 10 Jack Queen King.
Note: I will be calling this a "Decoding Row" as it is a row and it helps with decoding.
Looking at this "Decoding Row", go through the pack of cards *in order from the start* one by one to see which cards are absent and which are present. Write a 0 under the entries for cards that are absent, and a 1 for cards that are present. In our example the first card in the pack is the 4 of Spades. Therefore the Ace, 2 and 3 are absent so we put a 0 under their entries in our row, and a 1 under the 4 of Spades. The next card is the 7 of Spades. We put a 1 underneath that, and put a zero underneath the 5 and 6 as they are absent. Next we have the Jack of Spades. We put a 1 underneath that, and put a zero under each of the 8, 9, and 10 of Spades. Then the Queen of Spades is there so we put a 1 underneath that. The next present card is the A of Clubs. We put a 1 underneath that, and a 0 underneath the preceding absent King of Spades.
We continue like this until we get to the end of our row (the King of Diamonds, which has a 1).
We then write a new Decoding Row underneath the first one, but this one will just contain the cards that were marked with a zero in the first row - the absent cards. Make sure to include the suits in your row to avoid confusion. In our example this new Decoding Row will look like this:
Spades: Ace, 2, 3, 5, 6, 8, 9, 10, King; Clubs: 2, 3, 4, 6, 8, Jack, Queen; Hearts: 4, 5, 6, 8, 9, Queen; Diamonds: Ace, 3, 8, 9, Queen.
It is very easy to make mistakes decoding the pack, but it's not too much effort to correct them.
Once we have written out the second row, we go through it and mark a 1 or 0 underneath each entry depending on whether it's there or not. We put a 1 underneath the Ace of Spades, the 2 and the 3. The 5 of Spades is absent so we put a zero underneath that. The six is present so it gets a 1, and so on. You'll notice that in the second row, in this particular example, only one Club gets a 1 written underneath it.
When we get to the end of the second row (i.e. we reach the Queen of Diamonds, which happens to be absent so receives a 0), we start a third row of the cards that were absent in the second row. In our example this will turn out as follows:
Spades: 5, King; Clubs: 2, 3, 4, 6, 8, Jack; Hearts: 4, 5, 8, 9, Queen; Diamonds: 8, Queen.
We continue marking the 1s and 0s and creating more rows and going through them until we have gone through all the cards. In this example there are six Decoding Rows needed, although the last one only has two cards in it (the 5 of Spades and the 6 of Clubs) and those cards don't have any meaning attached to them. The 4 of Hearts at the end of the previous row likewise has no meaning.
We can now read off the binary numbers that were originally encoded in the cards by reading the ones and zeroes in the rows in order. If we didn't make any mistakes, then the numbers will be identical to the ones we originally encoded and we will have successfully decoded the hidden data. The last three cards will be 1s but we know to ignore them.
A Possible Optimisation For Encoding:
If there happened to be more 1s than 0s in the string of binary that we were encoding then it would make sense to have 1s as the removed cards, and keep the 0s. This would mean more cards would be available to be reused. The person decoding the data would need to know that this had been done, although they might be able to work it out by the context of the numbers involved. We'll ignore this optimisation here as it will just confuse the explanations.
The Final 1 Problem:
One of the problems with the encoding method is that cards that aren't used at the end of the pack will become decoded as 1s. This might cause confusion if the person who is decoding the pack doesn't know the length of the message or its likely contents. Supposing our data consisted of only 40 bits which were all 1s. When the pack is decoded, we would have another 12 bits of 1s.
Ways to solve the problem:
1: Mark where the data ends with a Joker, by turning the extra cards backwards, or by slipping bits of paper in. This is a simple and certain way to indicate where the data ends. It would also be possible to crease the corner of a card, but that would mean the pack could only be used once. These solutions are a bit noticeable, and when we get on to the Recursive Method, we'll need the Jokers for another purpose.
2: Work with known bit sizes of numbers rather than individual bits. If the person encoding and the person decoding both know that we are working with 4-bit numbers and there are three cards left at the end of the pack, then the decoder will know they can't be part of our number and are just unused cards. This would solve the problem of a few unused 1s but not the problem of a lot of them.
3: Work with fixed length numbers. If we only ever encode 128 bit numbers then any cards after we've completed the message can be ignored. However supposing we want to encode 64 bits, we'd still need to pad out our number to 128 so the problem would still be there.
4: Use escape characters. In other words we would use a particular encoding of bits to indicate that the next bits were a genuine set of 1s. If we were encoding 4-bit numbers then the escape character could be something like 0100. Every time 0100 preceded 1111 we'd know it was a genuine 1111 and not the end of the pack. This of course creates the problem of how to encode 0100 when it comes up. We could encode it by putting it in a pair so 0100 0100 means "0100", while 0100 1111 means "1111".
Another option for escape characters is to use "0100, 1111" to mean we've reached the end of the pack and that the following 1111s are false. A double 0100 would still mean a genuine 0100.
I'll ignore the "Final 1 Problem" in this explanation as it complicates matters.