hiding messages in playing cards
I was recently thinking about the huge number of ways you can shuffle a deck of 52 cards and wondered if it would be possible to store arbitrary data, which I explore in this blog post.
This blog post will go into the detail of how I found a way to store text inside the order of a deck of cards. If you want to play around with the tool, go here. How many different ways can we shuffle a deck of 52 cards? We can think of it like picking one card from 52, then one from the remaining 51, and so on. We would get an expression that looks like ( 52 ) ⋅ ( 52 − 1 ) ⋅ ( 52 − 2 ) ⋅ . . . ⋅ ( 52 − 51 ) (52)\cdot(52-1)\cdot(52-2)\cdot...\cdot(52-51) (52)⋅(52−1)⋅(52−2)⋅...⋅(52−51), which is the same as the factorial of 52, which is shown as 52 ! 52! 52!. If we evaluate 52 ! 52! 52! we get around 8 ⋅ 10 67 8 \cdot 10^{67} 8⋅1067. This tells us that the number of bits that can be represented by a deck of cards is ⌊ l o g 2 ( 8 ⋅ 10 67 ) ⌋ \left\lfloor log_2(8 \cdot 10^{67}) \right\rfloor ⌊log2(8⋅1067)⌋, or 225 225 225 bits. But how do we actually store arbitrary bits? We need a one-to one mapping between the order of the cards and the theoretically usable bits. Initial thinking made me believe it could be done by using the color of the cards, because a deck of 52 cards will have 26 black cards and 26 red cards, however that would, in a worst-case scenario, only give you 26 26 26 bits, only 11. 5 ˙ 11.\dot5 11.5˙% of our theoretical limit. I later came across the concept of a Lehmer code, which allows you to numerically represent each unique permutation of set of elements. The easiest way to compute a Lehmer code is to make each element have its own number or id, and then for each element we count the number of elements to the right of it that are less than it. An animation of this process is below.
Another way to generate a lehmer code is to make a list of all the numbers you have, and for each number, find the index of the number of your list and then remove it. This is not as fast as the first method but its a bit easier to implement. Now that we can turn our deck of 52 cards into a Lehmer code, how can we actually use that to store data? We have our code as a list of cards i = 0 , 1 , 2...51 i=0,1,2 ... 51 i=0,1,2...51 where each card's code N i N_i Ni can be in the range [ 0 , 51 − i ] [0, 51 -i] [0,51−i]. It is difficult to take that and just store arbitrary data using this array, so we can finally convert it a (very large) denary base10 number. We can do this because this Lehmer code is given to us as a factorial number. The factorial number system represents numbers using how many factorial numbers you need to make it. For example, let's try to turn the denary number 17 into a factorial number. We use the factorial numbers 1 , 1 , 2 , 6 , 24 , 120... 1, 1, 2, 6, 24, 120 ... 1,1,2,6,24,120... and so if we wanted to make 17 we would use two 6s, two 2s, and one 1, giving us a factoradic of 2 : 2 : 1 : 0 ! 2:2:1:0_! 2:2:1:0! (Numbers in the factorial system are separated by colons and end with a !). We can convert from this back to decimal in a trivial way by just adding the factorial numbers for each factoradic digit. Some code for converting between decimal and factoradic is below.
def convertToFactoradic ( number: int ) -> [ int ]: result = [] divisor = 1 while (number > 0 ): result.insert( 0 , number % divisor) number //= divisor divisor+= 1 return result def convertToDenary ( number: [ int ] ) -> int : global factorials result = 0 numlen = len (number) for i in range (numlen): result += number[i]*factorials[numlen-i- 1 ] return result
Now we can use this to store huge numbers inside our deck of cards. Shuffle a deck and run its permutation through the Lehmer code process, and then turn its factoradic number into a decimal number, and it will be huge. This is because its storing our 225 bits of data in a number. We have found a way to use 100 100 100% of bits we calculated previously. But how can we make this usable? We have 225 bits to play around with and so if we wanted to store alphabetical characters, we could use ⌈ l o g 2 ( 26 ) ⌉ = 5 \lceil log_2(26) \rceil = 5 ⌈log2(26)⌉=5 bits per character, which would leave us with some extra 6 characters. Most important is a space character, and after that I think a full stop is useful. If people want to put domains in there I thought a / slash might be useful. Finally a quotation mark, comma and dash are added to get our 5 bit, 32 symbol character set. With 5 bits per character, our 225 bits can store 225 5 = 45 \frac{225}{5} = 45 5225=45 characters.
alphabet = " .,-\"/abcdefghijklmnopqrstuvwxyz"
In Python converting text to and from a 225 bit number is quite simple and just requires some bitwise operations. Additionally, the function to convert a number to a permutation just requires converting it to a factoradic and then using each digit to index into a list of available elements, removing each element after it is used.
def convertToPermutation ( number: int , permutationElements: int ) -> [ int ]: global factorials if (number >= factorials[permutationElements]): raise ValueError( "Given number is outside of permutation range" ) factoradic = convertToFactoradic(number) while len (factoradic) < permutationElements: factoradic.insert( 0 , 0 ) available = list ( range (permutationElements)) permutation = [] for i in factoradic: permutation.append(available[i]) available.pop(i) return permutation def textToPackOfCards ( text: str ) -> [ int ]: global alphabet if ( len (text) > 45 ): raise ValueError( "Text must be <=45 characters to be represented in one deck of cards" ) for i in text.lower(): if not i in alphabet: raise ValueError( "Text must only be characters A-Z or '., -\"/' in order to use 5bit" ) data = 0 for i in text.lower(): data<<= 5 data|=alphabet.index(i) data <<= ( 5 *( 45 - len (text))) return convertToPermutation(data, 52 )
The overall process of converting text to a deck of cards is shown below, and the main reason this works to both encode and decode is that each step shown is reversible.