A pack of cards can be ordered in one of a number of ways (80,658,175,170,943, 878,571,660,636,856,403, 766,975,289,505,440,883, 277,823,000,000,000,000 to be precise)
A simple computer function can be written to translate this number into an ordering e.g. in Python, this might look like:
....def generatePermutationByIndex(n, i): ........p = list(range(0,n)) ........r = [] ........for k in list ( range ( 1, n+1 )): ............f = factorial(n-k) ............d = (i // f) ............r.append (p[d]) ............p.remove(p[d]) ............i = i % f ........return r
(my (....) for indentation purposes) Where inputs are n = 52, and i is a number between 0 and the big number above.
Once a number is chosen, a pack of cards is ordered according to the output of the function above (which simply enumerates all possible orderings and outputs the specific enumeration associated with a particular number)
Then, the person wishing to send a message writes it on the side of the pack of cards with a pencil or pen, shuffles the deck, and sends it via post, dead-drop or carrier- pigeon to the intended recipient.
Via a separate channel, the enumeration chosen is also transmitted - and picked up by the recipient, who uses it to re-order the pack of cards to reveal the original message.
Obviously, it's low tech, and suffers from the same problems that a non public/private key system shares - and I'm sure it must have been mooted in some detective/spy thriller or other by now - but it seemed a nice one to me in so far as it could be explained to someone relatively non- technical and could offer some degree of security to lay- folk, luddites and other fringe arrangements.
In actual fact, the number of combinations required to "crack" the code is halved since the same message would be revealed in the instance that the number is inverted (it would just appear upside down) and there might be some other trivially easy cases where the message is revealed - however, the physical nature of the transmission medium and the initial problem-size of 52! ought to be big enough to discourage all but the most enthusiastic cracking attempts.-- zen_tom, May 06 2015 Pontifex / Solitaire https://en.wikipedi...itaire_%28cipher%29as mentioned in anno [Loris, May 06 2015] StackOverFlow: Credit where it's due https://stackoverfl...lexicographic-indexThis I'm sure is where I lifted the original code from (which I still return to every now and then when faced with a combinatorial/enumeration problem) [zen_tom, Aug 24 2021] I could crack this code in <30min, without the aid of a computer.
Assuming that your letters are as high as several card thicknesses, it would not be hard to line up ink-marks on the card edges to reconstruct the original order.-- MaxwellBuchanan, May 06 2015 Hmm. You would want to make your font very tall and dense so it can't be cracked by eye.
Depending on the method of shuffling, some cards could be rotated 180 degrees - if each card has two states, how many combinations is that now?
I once saw some software (can't remember where... in fact I may have dreamt it) that let you scan shredded paper and it would algorithmically reassemble it.-- mitxela, May 06 2015 What Max said. You could argue that it's steganography, I suppose.
You could write the message on the face of the cards, one letter per card. Limits you to 52 letters, of course.
But also:
//Via a separate channel, the enumeration chosen is also transmitted//
It might be easier just to send the message via that channel.
You could have previously agreed a card order with the recipient, I suppose.
There's a book which describes a crypto system using a shuffled deck of cards. "Cryptonomicon", IIRC. I didn't try very hard to understand it - and I don't think it's very secure by current standards.-- Loris, May 06 2015 //one letter per card. Limits you to 52 letters//
I suspect that a 52-letter anagram would be easy to solve, unless you splixy included a few nonsense words in the message brint.-- MaxwellBuchanan, May 06 2015 //I suspect that a 52-letter anagram would be easy to solve, unless you splixy included a few nonsense words in the message brint.//
yes, I think it would be wise to pad to 52 chars. orsp9uae3em1lh
Or have a message with multiple plausible solutions.-- Loris, May 06 2015 Thoughtful points all - thanks for those - I was thinking of ways to level-up the trickyness on the way home - wiggly/tall fonts would be one method, or alternately, writing various messages, some of which would be false ones overlapping one another, at different pack- permutations would make a visual crack a few orders harder.
The non private/public-key thing is of course the biggest weakness here - but what I'd really like to be able to figure out is a method of mapping from an integer (the key) to a pack-permutation without recourse to a computer. But in a way that I can explain to (and expect them to be able to replicate) a seven-year-old, or someone reading Dan Brown's latest, for example.-- zen_tom, May 06 2015 //a method of mapping from an integer (the key) to a pack-permutation without recourse to a computer.//
If you numbered each card (clubs through hearts; aces through kings) from 00 to 51 (with leading zeroes), then it would be easy (01/32/44/16... etc).
If you didn't have the leading zeroes, it would be trickier: 127 could be 1/27 or 12/7.
Actually, I hereby propose Buchanan's Conjecture: if all numbers from 0 to 51 are written consecutively in any order, with no leading zeroes and without spaces between digits, it will always be possible to deduce the boundaries between single- and double-digit boundaries, and therefore to split the sequence of digits into the 52 numbers in a unique way. Howevertheless, you could probably still solve it. For instance, if a "576" appeared somewhere, you'd know it had to be "5/7/6" or "x5/7/6", so the previous "127" would have to be "1/27" not "12/7".-- MaxwellBuchanan, May 06 2015 If the 1st 5 cards were taken from the set {1,2,3,12,23} I think 1231223 could be read either as {1,2,3,12,23} or {12,3,1,2,23} for example - does one counter-example blow the conjecture?-- zen_tom, May 06 2015 If the key length is the same as the number of cards why not just use a one time pad?-- Voice, May 06 2015 //does one counter-example blow the conjecture?//
OK. Buchanan's Second Conjecture: no conjecture can be blown without there being N counterexamples, where N>>1.-- MaxwellBuchanan, May 06 2015 And the difference between this and the TV spy shows fixture,where they reassemble strips of shredded paper in software, is ?-- FlyingToaster, May 06 2015 Writing several false messages on the same deck would be a sure sign for the cracker to keep looking. You want your code method to not attract attention at all.-- RayfordSteele, May 06 2015 Several lines of text on the side of the pack of cards would make it harder to crack just by inspection. The code is interesting - I got a bit bogged down trying to figure out exactly what it was doing - and I don't know what the '//' and '%' operators do. Can you explain it a bit more, and the maths behind it?-- hippo, May 07 2015 Sure [hippo] love to - it's in python (version 3+) :
The operator // is "floordiv" that returns the integer part of any division operation, dropping any non integer part. It should return the same as the pseudo-code int(x/y)
The % operator returns the remainder after a given division takes place - so 10%3 is 1 since 3x3 is 9 and 10-9 is 1.
The function takes in two values; n, the size of the set being permuted - and i, the "index" of the permutation required.
Since the total number of permutations possible on a set of size n is n!, then i must be in the range from 0 to n!-1.
If i = 0, then the set is returned in its "natural" order, if i = n!-1, then the set is returned in "reverse" order.
At each step in the k-loop, the item at the i//f's position is taken from the starting list p, and placed into the return list. That then means that the new starting list p is now one element smaller. At the end of the loop, i is recalculated based on the remainder of i into f. When i is less than the size of the remaining set (because n! always has i as a factor) it will always take the first element, but as i gets bigger (and the remaining set gets smaller) then the element picked in each iteration drifts up the list.
I wont pretend to understand it any more deeply than that (and should point out that the code above is an edited version of an unattributed scrape from stack- overflow somewhere), but it uses something called Lehmer coding, which has a basis in the Factorial Number System. What it does do very nicely is encode the details of a permutation in a very neat and tidy way. There ought to be a reverse-encoding method (where a permutation of a set of size n is input, and an integer is returned that corresponds to its permutation "index") but I'm yet to find a working method for that.
[edit] I figured out the reverse-function, it's a bit simpler and looks like this:
def identifyPermutation(p): ....s = list(range(0,len(p))) ....i = 0 ....c = 0 ....for k in p: ........f = factorial(len(s)-1) ........d = s.index(k) ........c = c + ( d * f ) ........s.remove(k) ....return c
Taking a list consisting of permutation of the numbers {0,1,2,...,n} and returning the index of that permutation according to the original function. The two should operate as mirror images of one another.-- zen_tom, May 07 2015 <update on earlier comment> A quick bit of programming suggests that, if the numbers 0-51 without leading zeroes are arranged in random order without any spaces, the order of the numbers can be determined unambiguously in 83% of tests.-- MaxwellBuchanan, May 10 2015 random, halfbakery