h a l f b a k e r yWhat's a nice idea like yours doing in a place like this?
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
browse anonymously,
or get an account
and write.
register,
|
|
|
Please log in.
Before you can vote, you need to register.
Please log in or create an account.
|
rot(52!)
No exclamation-marks were harmed in the making of this idea | |
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.
Pontifex / Solitaire
https://en.wikipedi...itaire_%28cipher%29
as mentioned in anno [Loris, May 06 2015]
StackOverFlow: Credit where it's due
https://stackoverfl...lexicographic-index
This 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]
[link]
|
| |
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. |
|
| |
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. |
|
| |
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. |
|
| |
//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. |
|
| |
//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. |
|
| |
//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. |
|
| |
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. |
|
| |
//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". |
|
| |
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? |
|
| |
If the key length is the same as the number of cards why not
just use a one time pad? |
|
| |
//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. |
|
| |
And the difference between this and the TV spy shows fixture,where they reassemble strips of shredded paper in software, is ? |
|
| |
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. |
|
| |
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? |
|
| |
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. |
|
| |
<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. |
|
| |