Using playing cards to store hidden data:
The Implied Card Method for
Encoding Data Into Playing Cards.
Recursive Implied Card Method:
The Implied Card Method as described so far is straightforward and fairly efficient. However it is possible to take it to an even higher level that allows us to encode even more data into a pack of 52 cards. This adds more complexity to the idea which will make decoding the pack more time consuming. Encoding the pack, however, isn't much different to normal.
This optimisation is based on the following idea when thinking about an already encoded pack of cards: If we were to remove the part of the encoded pack up to where the previously absent cards start re-appearing (i.e. up to and including the King of Diamonds, or at least where the King of Diamonds should appear), we would still have enough information in the rest of the pack to work out what the first section would have been. The contents and order of the first part of the pack is logically implied by the existence of the cards in the second part of the pack. Therefore we don't actually need the first part of the pack to be included in our pack of cards for it to be successfully decoded, and therefore we can use all those cards again to represent even more numbers.
For example, if there is an Ace of Spades anywhere in the second part of the pack, then we know for sure that it was an absent card in the first part of the encoding and doesn't appear in the first part of the pack. Similarly, if there *isn't* an Ace of Spades anywhere in the second part of the pack then we know for sure that it was present in the first part of the encoding. If the Ace of Spades *was* in the first part of the pack then it would have been the very first card - there is *nowhere* else it could have been. Similarly, for example, if the King of Diamonds was in the first part of the pack, then it would have been the last card - there is nowhere else it could have been either. In this way, any card which isn't in the second part of the pack would have originally been in the first part of the pack in a position we know.
Whereas before we have been reusing cards that represented 0s, now we will be reusing cards that represented 1s. Before, our cards were reused by just putting them at the back of the pack. Now we actually have to make sure we keep them separate to the rest of the pack. It is vital not to confuse our two parts of the pack or else the second part will be decoded incorrectly. To do this we can separate them with a Joker or the "Rules for Bridge" card.
When *encoding* a pack which will eventually have a recursive section, we encode normally for the whole of the pack until we have run out of cards in exactly the same way as normal. We then split the encoded pack at the point the King of Diamonds first appears (or where it *should* first appear). The first part we'll call Part 1a; the second part, Part 1b. We then put a Joker on the back of the Part 1b to act as a separator, and encode the rest of our numbers into Part 1a as if nothing were different. To indicate that Part 1a now contains a different combination of the same cards, we will call it Part 2.
When it comes to *decoding* a pack with a recursive section, we are missing Part 1a so we have to analyse Part 1b to see which cards would have been in Part 1a. In other words we just see which cards are in Part 1b, and mark them as 0s in our first Decoding Row (made up as usual to be a list of all 52 cards in order from the Ace of Spades to the King of Diamonds). We mark them with 0s because if they aren't in Part 1b then they would have originally been in Part 1a. (We can't analyse Part 2 to do this as Part 1b might contain a few final unused cards from the first encoding). When we have marked the 0s, we then mark the other entries with 1s. Having done that means that the Decoding Row shows how Part 1a originally looked, and we then decode Part 1b as normal in a new row underneath, based on the cards marked with 0s in the first row. We go through Part 1b as normal marking 1s for present cards and 0s for absent cards, and making new rows underneath when needed.
When it comes to Part 2, we know the original order of those cards and which ones were actually there, as they are the cards marked with 1s in the first Decoding Row. Therefore we can create a new set of Decoding Rows on a separate piece of paper starting with a row listing those cards. We then decode Part 2 using that row as normal, and creating more rows as needed. Our final binary number will be based on both sets of rows.
Now, given that we know which cards are in Part 2 from the cards in Part 1b, and given that we could calculate which cards are in the first part of Part 2 from the cards in the second part of Part 2, we don't actually need the first part of Part 2 either. We can therefore split Part 2 and make another part, Part 3, which in turn can be later split to produce parts that in turn can be split and so on. In this way we can carry on using smaller and smaller parts derived from previous parts until we get to one with too few cards to use. We would need to keep putting dividers into the pack to indicate where the parts are separated, and after every level of splitting decoding would become slightly more complicated. The ability to keep reusing smaller and smaller portions of the pack is why I called it the Recursive Implied Card Method. It also sounds fancy.
A diagram showing how we split the pack for more "recursions":
Which, in a way, is a bit reminiscent of this:
(Image from http://en.wikipedia.org/wiki/File:Fibonacci_spiral_34.svg)
An example: Encoding using recursion just once:
To show how much more we can encode using this optimisation, and to help explain it, I'll use the original example of encoding the binary numbers 0001 to 1111 and 0000 to 1010. We'll continue from where we stopped in that example. In that case we ended up with three leftover cards: the 4 of Hearts, the 5 of Spades and the 6 of Clubs. Although it would be useful to use them again, we have to keep them at the end of the pack where we had them, as, despite not being representing any cards, they are needed to indicate which cards are in the first part of the pack. These extra cards won't confuse matters if the person decoding the pack is aware that they are decoding 4-bit numbers. Three cards on their own that don't make up a 4-bit number will be interpreted as the leftover, meaningless cards that they are.
To see where we need to split the pack we look through it until we find the last card that represented a 1 before the cards started to be reused. In other words, the point at which we started reusing cards that had previously been zeroes. This is also the point at which, were we decoding them, we would have finished our first Decoding Row. Usually (but I don't think necessarily always) this will be the first point where the cards of the pack stop being in order. Anyway, to cut a long story short, in this example, we'll look for the first place where the King of Diamonds either is or should be. The King of Diamonds *is* there, and the next card is the Ace of Spades. The Ace of Spades is the first of the cards that were used to represent a zero on their first appearance, so that is where we'll split the pack. Our cards from the start (the 4 of Spades) to the King of Diamonds inclusive will make up our Part 1a (and the basis of our future Part 2). The other cards will make up Part 1b. There are 25 cards in Part 1a and 27 in Part 1b.
We put Part 1b face down on a table, and put a Joker face down on that. The Joker will indicate the point where the new third section (Part 2) will begin, and is also an indicator that we are using the Recursive Method.
We then take Part 1a in our hand and start encoding numbers into it in the usual way. We will put the kept cards (the ones that represent 1s) face down on the pile on the desk, and pass the removed cards (those that represent 0s) to the back of Part 1a to be used again in the future. Our first number is 1011 (eleven in decimal). The next cards are the 4, 7, Jack and Queen of Spades. We put the 7 at the back, and put the other three face down on our pile on the desk.
Our next number is 1100 (twelve in decimal). Our cards are the Ace, 5, 7 and 9 of Clubs. We keep the Ace and 5 and put them on our pile; we remove the 7 and 9 and put them to the back.
The next number is 1101. The cards are the 10 and King of Clubs and the Ace and 2 of Hearts. All except for the Ace of Hearts go on the pile.
We continue like this until we reach 1111 at which point we will keep the King of Hearts, and the 2, 4 and 5 of Diamonds. Then we can start at 0000 again. The cards are the 6, 7, 10 and Jack of Diamonds. We pass them all to the back. We then continue until we have run out of cards. The last number we can do is 0101 (five in decimal). After that we have three cards left: The 7 and 10 of Diamonds and the 7 of Clubs. We can't use these cards so we put them face down on the desk pile and we are done. The pack now consists of Part 1b and Part 2. Part 1a no longer exists.
We now have a pack of cards that has the numbers 0001 to 1111 (1 to 15 in decimal), 0000 to 1111 (0 to 15 in decimal) and 0000 to 0101 (0 to 5 in decimal) encoded in it. Therefore it contains 37 4-bit numbers, which amounts to 148 bits of data. Before our new Recursive Method we could only store 26 numbers which amounted to 104 bits of data.
Decoding this data:
Decoding will take up more time than before. The person decoding needs to be sure that we are using the Recursive Method. This can be discovered by the presence of a Joker in the middle of the pack. Without knowing that we're using the recursive method a person might start decoding the pack as normal, in which case they would just produce meaningless data.
First, split the pack into two parts: The part before the Joker and the part after the Joker. The part before the Joker is Part 1b, the part after the Joker is Part 2. Put Part 2 and the Joker in a safe place for now.
Now, write out a Decoding Row as we would do normally. It will contain all the possible cards in a pack in order from the Ace of Spades to the King of Diamonds.
We need to recreate the contents and layout of the missing Part 1a. To do this look through Part 1b and if a card in Part 1b appears in our Decoding Row, then put a *0* underneath its entry. The reason we put a 0 against the entry is because if a card is in Part 1b then it couldn't have been in Part 1a. When you have been through Part 1b, then mark 1s under the other cards in the row. (The cards probably won't be in order so it's easier to do it this way).
In our example, the Ace of Spades is in Part 1b, so we put a zero against it in our row. The 2 and 3 of Spades are similarly in Part 1b, so they get zeroes too. After going through the whole of Part 1b, it turns out that the 4 of Spades is not here so it gets a 1, nor is the 7 of Spades etc etc etc.
A picture of the process of going through the cards in 1b one by one to create the original order and contents of 1a:
Doing this not only recreates the decoded numbers from Part 1a, but it also shows us the original order of the cards we will find in Part 2 for when we come to decode that.
Now we decode Part 1b in the usual fashion as if it were a continuation of that row (which it technically is). Write out a new row underneath the first row, made up of the cards that were marked with 0s in that row. In our example it will contain the A, 2, 3, 5, 6, 8, 9, 10, King of Spades; the 2, 3, 4, 6, 8, Jack, and Queen of Clubs; the 4, 5, 6, 8, 9 and Queen of Hearts; the Ace, 3, 8, 9, and Queen of Diamonds.
Then go through Part 1b in the usual way - marking 1s against cards that are there and 0s against cards that are absent. When you get to the end of the row, create a new row underneath consisting of the cards marked with 0s in the previous row. Then carry on marking 1s and 0s and creating new rows until the whole of Part 1b is done. We will end up using 6 Decoding Rows, the last of which contains two cards: the 5 of Spades and the 6 of Clubs. The set of completed rows should be identical to those when we first counted up from 0001 to 1111 and from 0000 to 1010 in the example in the Basic Encoding explanation.
Now we decode Part 2. To do this we create a new row on a separate piece of paper listing the cards that were marked with 1s in the row when we decoded the implied Part 1a. This new row will consist of: The 4, 7, Jack and Queen of Spades; the Ace, 5, 7, 9, 10 and King of Clubs; the Ace, 2, 3, 7, 10, Jack and King of Hearts; the 2, 4, 5, 6, 7, 10, Jack and King of Diamonds.
We then go through Part 2 decoding it in the normal way - marking off the cards which are present with 1s, and the cards which are absent with 0s, and creating new rows when we get to the ends of old rows. In this example we use 5 Decoding Rows, the last of which has just one card in it: the 7 of Clubs.
After doing that, we have completely decoded the cards for the whole pack. We can read the binary numbers from the set of rows for Part 1a and Part 1b, and from the set of rows for Part 2.
A second level of recursion:
Now we have seen how the recursive method works in the example, we can apply it again to the pack and use the first part of Part 2 to encode more cards. We will leave Part 1b as it was.
First we find the point where we will split the pack. We will search from the start of Part 2 until we reach the point where cards started to be reused. The most surefire way of knowing this point is to have made a note of it when the pack was being encoded. [Another way that has always worked so far for me, but might not always work, is to look for the first place where the cards stop being in order. I think there may be situations where this isn't reliable, but I haven't given it much thought yet]. If you have checked to see if your encoding was correct so far by decoding it as you went along, and you kept the Decoding Rows, then the point where you split Part 2 will be at the last card that was marked with a 1 in the first row for Part 2.
In this example we split the pack after the 5 of Diamonds. Our Part 2a will consist of: the 4, Jack and Queen of Spades; the Ace, 5, 10 and King of Clubs; the 2, 3, 7, 10 and King of Hearts; and the 2, 4, and 5 of Diamonds. Our Part 2b will be the 9 of Clubs onwards. Part 2a is removed and contains the cards that will become our Part 3.
With Part 1b face down on a desk, put a Joker over it to act as a marker, then put Part 2b face down on top of that, and another Joker on top of that.
Using Part 2a, we will now carry on counting from where we left off. We will put "kept" cards face down on the rest of the pack; we will pass "removed" cards to the back of Part 2a (which will become Part 3 when we're done).
Our first number will be 0110 (six in decimal). The first four cards available are the 4, Jack and Queen of Spades and the Ace of Clubs. We keep the Jack and Queen and pass the 4 and Ace to the back of Part 2a. The encoding for the rest of Part 2a is just as you'd expect. The last number we can encode is 1011 (eleven in decimal). We are left with two cards: the 10 of Hearts and the 4 of Diamonds. We have encoded 6 new 4-bit numbers into this section. Therefore we have 43 4-bit numbers (172 bits of data) encoded in this pack of 52 cards.
Decoding this second level of recursion:
Because this is now getting more complicated I'll show how to decode this pack from the very beginning.
Looking through the cards we can see two Jokers which means the pack has 3 distinct *existing* parts: Part 1b, Part 2b and Part 3. It has 5 parts in all: Part 1a (which isn't actually there but can be worked out from the rest of the cards), Part 1b, Part 2a (which isn't actually there but can be worked out from Part 2b), Part 2b and Part 3. Part 3 was originally made up from Part 2a, and Part 2a was in turn made up from a portion of Part 2, which in turn was originally Part 1a.
1: First we need to recreate the non-existent Part 1a. Therefore we need to find which cards would have been in it and where they were. To do this we write out a Decoding Row of all 52 cards in the pack in order from the Ace of Spades to the King of Diamonds. We'll call this "Row A". Next, we look through the cards in Part 1b, and put *zeroes* under every entry in the row for each card that appears in Part 1b. If a card is in Part 1b then it means it wasn't in Part 1a. When we have been through the row we put 1s underneath the entries that don't have 0s underneath them.
2: Next we decode Part 1b. This is decoded normally as if it were an extension of Part 1a. In other words, we write out a second row underneath Row A containing the cards that were marked with zeroes in Row A. We then go through Part 1b and mark 1s for existing cards, and 0s for absent cards as normal. We create more rows if needed until we have completed Part 1b.
3: Next we need to recreate the non-existent Part 2a. We can do this by finding out which cards were in the whole of Part 2 before it split, and which cards are currently in Part 2b. The cards that appeared in the whole of Part 2 before it split are those marked by 1s in Row A. Therefore we create a new row based on those cards on a separate piece of paper, and we'll call the row "Row B". Row B will consist of: The 4, 7, Jack, and Queen of Spades; the Ace, 5, 7, 9, 10 and King of Clubs; the Ace, 2, 3, 7, 10, Jack and King of Hearts; and the 2, 4, 5, 6, 7, 10, Jack and King of Diamonds.
To see which cards were actually in Part 2a, we look through the cards in Part 2b. When a card in Part 2b appears in Row B then we mark it with a *0* (because if it is in Part 2b then it wasn't in Part 2a). When we have been through the row we put 1s under the cards without 0s.
4: We then decode Part 2b. This is decoded normally as if it were an extension of Part 2a, so we write a row underneath Row B of the cards that were marked with 0s in Row B. We then go through Part 2b as normal, marking cards that are present with 1s and those that are absent with 0s, and making new rows as needed. 4 rows are needed to decode Part 2b, which added to the first row (Row B) makes 5 rows needed to decode both Parts 2a and 2b. The last row has only one card in it, the 7 of Clubs.
5: On a separate piece of paper, we then create a list of all the cards marked with 1s in Row B. We will call this list, Row C. In this example, Row C will contain the cards: the 4, Jack and Queen of Spades; the Ace, 5, 10 and King of Clubs; the 2, 3, 7, 10 and King of Hearts; and the 2, 4 and 5 of Diamonds.
We decode Part 3 of the pack normally using Row C. Cards that are absent are marked with 0s, those present are marked with 1s. We finish this row and create new rows underneath until we finish Part 3. We end up using 3 rows to decode Part 3. The last one contains 3 cards: the 5 of Clubs, the 10 of Hearts and the 4 of Diamonds.
When that is done we have successfully finished decoding the pack. We can read off our original number by reading the 0s and 1s of Row A and the rows underneath, Row B and the rows underneath, and Row C and the rows underneath.
Summary of how to encode any level of recursion:
Encode the whole pack as normal.
Split the pack at the point where cards that represented 0s came around the second time. We now have two parts: 1a & 1b.
Encode numbers into Part 1a and put it (now referred to as Part 2) to the back of Part 1b separated by a Joker.
Then repeat the following forever:
Split Part X at the point where cards that represented 0s came around the second time in it, creating Part Xa and Part Xb.
Encode numbers into Part Xa and put it (now referred to as Part X+1) to the back of Part Xb separated by a Joker, the Rules for Bridge, or a piece of paper.
Summary of how to decode any level of recursion:
Make a list of all 52 cards in the pack in order from Ace of Spades to the King of Diamonds in a row across the top of a piece of paper. We'll call this, Row A.
If Part 1 is *not* split then we go through the pack as normal starting with Row A, and we are done.
If Part 1 *is* split, then we recreate Part 1a by marking 0s against the cards in Row A that appear in Part 1b, and 1s against the cards that don't. We then carry on decoding Part 1b as normal as if it were a continuation of Part 1a.
4: We create a list of all the cards marked with 1s in Row A on a separate piece of paper. We'll call this, Row B.
If Part 2 is *not* split, then we go through it as normal using Row B, and we are done.
If Part 2 *is* split, then we recreate Part 2a by marking 0s against the cards in Row B that appear Part 2b, and 1s against the cards that don't. We then carry on decoding Part 2b as normal as if it were a continuation of Part 2a.
7: We create a list of all the cards marked with 1s in Row B on a separate piece of paper. We'll call this, Row C.
If Part 3 is *not* split, then we go through it as normal using Row C, and we are done.
If Part 3 *is* split, then we recreate Part 3a by marking 0s against the cards in Row C that appear in Part 3b, and 1s against the cards that don't. We then carry on decoding Part 3b as normal as if it were a continuation of Part 3a.
10: We create a list of all the cards marked with 1s in Row C. We'll call this Row D.
If Part 4 is *not* split, then we go through it as normal using Row D, and we are done.
If Part 4 *is* split...... etc etc etc etc.
And so on....
"Real world" examples:
Just for the sake of showing the method being used to encode numbers seen "in the wild", here are some examples:
The MD5 hash of the word "apple" is 1f3870be274f6c49b3e31a0c6728957f.
This is 00011111, 00111000, 01110000 etc in binary, and amounts to 128 bits. On the first (non-recursive run) we can encode 96 bits, which is: "1f3870be274f6c49b3e31a0c". We have four cards left over.
Part 1a (= Part 2) has 28 cards in it, and we can encode the rest of the number easily into it without needing to split Part 2 afterwards. We have 10 unused cards left over. On decoding, those 10 unused cards will all appear as 1s, but because we know the length of the binary number (128 bits) that won't be a problem. If we didn't know the length then we might presume that the last numbers were 11111111, 11111111 (0xff in hex), followed by 2 single 1 bits.
A long string of hex bytes:
Here is the public key for the certificate for the secure Google.com website. There's no relevance to this number or any use in encoding it - it's just a long number I found on the internet. The key is as follows:
"04 f2 e1 38 24 4a 53 3d a8 0d 9b 34 7c 71 26 29 84 38 51 5a 2d ca 00 7b cb 1b 38 0c fa 93 f2 c6 b7 ba 08 f4 21 c0 b5 28 9e 19 66 a3 45 7d 70 63 18 12 a1 0f 52 7e 29 ef ec 36 2b 06 29 cc 26 f1 96"
In binary, this starts off as: 00000100, 11110010, 11100001 and so on.
On the first run before recursion, we encode 104 bits and have 6 cards left over. On the first recursion run (i.e. creating Part 2) we encode another 44 bits and have 5 cards left over. On the second recursion run (i.e. creating Part 3) we encode another 8 bits and have 5 cards left over. We only have 3 cards available for Part 4 which isn't enough to encode anything so we have to stop there.
Therefore, in total we have encoded 156 bits of data into a pack of 52 cards (exactly 3 bits per card). We have encoded the following part of the key: "04 f2 e1 38 24 4a 53 3d a8 0d 9b 34 7c 71 26 29 84 38 51"