unforum

[kian]

[Koblin]

Re: Genetic Algorithms and Deck Order.

[FranG]

All possible messages

[ariock]

Re: Genetic Algorithms and Deck Order.

[James Siegesmund]

Just throwing more stuff out there, hoping I can spark someone else into a solve. This whole thing is spec...

As was previously discussed with my "working backward" idea, the Jokers can never end a round of encryption on the bottom of the deck. This means that although there are 54! possible starting orders, there are less than that number of possible ending deck orders after a single round of encryption.

When working the other way (from encrypted deck order back to starting order), this makes Solitaire non-reversable -- if you're working backwards, and a joker should go on top, you don't know whether to put it on the top of the deck or on the bottom, because Solitaire treats those two positions as identical.

What I'm wondering is whether we can work with the fact that Garnet DID solve it. If he never had a keyword, he was able to work backwards from some ending order, through 100+ itterations, to get the starting order. How many starting orders, put through 100 rounds of encrytion, NEVER hit that joker on top/bottom state that makes Solitaire unreversable? Any math lovers out there that could answer this?

To put it another way, an encryption method is non-reversable if some critical piece of information is lost during encryption and can't be recovered (e.g. I take a message and use a random number generator to ROT each letter 0-25. The encryption is unreversable unless you know what random numbers I used -- that's why a one-time pad cypher's only weakness is that someone could learn the key). Solitaire loses information via the looped deck, bottom-card-is-also-on-top-card thing; we know this because 54! starting orders go to less than 54! round two orders, so some 2 starting orders must produce identical round two orders. Those two starting orders have lost info -- you can't look at the round two order and know which starting order it came from.

But what if this one time, somebody used a starting deck and a message order that didn't lose any info, allowing Garnet to reverse it from the deck order he got (but didn't share with us). It is possible that for such a long message, there are a severely limited (maybe even only 1 -- though also maybe none) number of deck orders that meet that criteria. If we could find that limited number, maybe solving this would be just a matter of using the right one of those.

The basic idea: 100% of the 54! starting orders are possible. But only some fraction of those (say 99.9%) are possible orders after a single round of encryption. As this continues round by round, the fractions multiply. 54! is a huge number, but it gets smaller as it is multiplied by fractions round after round. If there are "only" a billion possible deck orderings after 108 rounds, how many of those correspond to one, AND ONLY ONE starting order?

[FranG]

Deck orders/messages

[Koblin]

Deck orders/messages

[ariock]

Re: Deck orders/messages

[cwmajors]

Could the deck as received by Garnet be the -ending- deck order? (I am almost sure I'm not the first person to think this.) Would it be possible to start at the end and work backwards through the cyphertext assuming that whatever the starting deck order is, the -ending- deck order is the same as an unopened deck? (or do we run into the lost-data situation where the jokers are on top and bottom?)

[James Siegesmund]

[cmlobue]

[sixsidedsquare]

I've been mulling this idea over for the past few days and am wondering if maybe we could actually crack the solitaire cipher kind of how the Enigma was cracked.

In simplified theory the solitaire cipher can give you any possible keystream, therefore a brute force of all decks would give you all possible outputs containing every possible string of the length of your message. In actual fact though, not every keystream is possible as I try to explain below.

If you take any of the 54! possible starting deck orders and move one step in producing a keystream it will of course come to one of the other possible deck orders. So one deck order will lead to another deck order, which in turn comes to another and eventually you would have come back to your original starting order. This essentially creates a loop or chain of deck orders and keystream output.

I assume (though am not certain) that in each of these chains there would be cards that never influence the movement steps,. So for each chain, the number of total overall deck orders that create different keystream chains is reduced by the factorial of this number. If you could somehow get all these chains of keystreams you could just cycle them along the cipher text, checking the output for English words till you find the correct keystream.

The problem with all this of course is it's all just words. I have no idea how any of the numbers of this would work out, such as the number of chains, or even the lengths of these chains. In fact the more I think about it the more the numbers still seem they will too big to be able to deal with. A very basic probe into sizes involved could be a small program that takes a single deck order and steps through the movement parts of the cipher algorithm, until it comes back to the deck order it started with. Running this overnight would give an indication the length of chains (and if they are actually small enough to be found for that matter). The most likely outcome though, is that this idea isn't at all plausible and just to find one chain would take longer than as many seconds as there are atoms in the universe or some such defeating conclusion.

Comments? Ideas? Crushing facts about the reality of the size of 54!?

-EDIT-
As I woke up this morning I realised that I got something slightly wrong to do with the the total number of deck orders with unique keystream outputs. Rather than it just being reduced by the factorial of the number of non used cards in a chain, it would be the factorial of them multiplied by the length of the chain. It's a small difference, but every reduction counts.

[Koblin]

[sixsidedsquare]

[kian]

When keying a deck for Solitaire using a passphrase, some different keys result in the same deck order. For example, here is the process for the keys "EFO" and "EKT", taken step by step...