5 ms·

I came to post this same comment, then found that the paper itself cites Solitaire! The only downside I see for this implementation is that a stack of "weird"

• zokier 9y ago
  I don't see any obvious reason why you couldn't use deck of cards with ElsieFour 1) shuffle the deck 2) split into two parts, first part having 36 cards 3) Assign the alphabet to the 36 card part (e.g. by sorting the cards and assigning characters sequentially) 4) shuffle parts separately 5) combine the parts in a easily reversible way (e.g. simply appending) When doing the crypto, just use the 36 card part. I suppose the remaining cards could relatively easily be repurposed as RNG for nonce generation.
  • maxerickson 9y ago
    It'd be simpler to just ignore the tens and face cards.
  • zokier 9y ago
    > I suppose the remaining cards could relatively easily be repurposed as RNG for nonce generation I spent better part of a hour trying to google this to no avail. How do you convert random permutation of n items into random number <n! ? Intuitively it feels like it should be possible, if not even easy, but I can't figure it out. edit: yay, finally found a lead: "rank of a permutation" and "lehmer code". So I guess it is doable, have to check how they would actually work in application
    • e12e 9y ago
      [ed: no, that's not right. With two cards, you can have red-back or black-red. I guess that'd translate to N bits for 2 n cards, but it's not quite trivial... For four, we have: rrbb, rbrb, rbbr, bbrr, brbr, brrb etc] I think I'm misunderstanding you - but say you have 2n cards, n red, n black. If you shuffle them, you have 2n random bits, read from first to last? (this is assuming it's feasible to actually randomly shuffle cards).
      • HelloNurse 9y ago
        No, in this application cards are all distinct, not merely half red and half black. There are n! permutation of a deck of n cards, and a uniformly chosen random permutation contains entropy equal to the base 2 logarithm of n!. Both choosing a random permutation given a supply of random bits and, as noted in the parent post, extracting random bits from a given random permutation are nontrivial computational problems leading to interesting algorithms; shuffling cards or tiles is a good practical shortcut to obtain a random permutation more directly.
        • e12e 9y ago
          Indeed. I was attempting to induct from basic principles - as in two distinct cards.. But gp's right - it's not trivial. Unsure if it's simple :)
    • KMag 9y ago
      You'll want to basically perform the reverse of a Fisher-Yates shuffle. Instead of generating a random number, you look at which card needs to be swapped with the Kth card in the deck to make the top K to N positions of the deck in sorted order. If deck is a list holding a permutation of the numbers 0 to N - 1, it looks something like: random_value = 0 for i in range(len(deck)-1, 0, -1): index = deck.index(i) random_value += index random_value *= i deck[index], deck[i] = deck[i], deck[index] The above is a one-minute prototype and may or may not work. When I get some time, I'll actually test the above code, but it's close to doing the right thing. The above naive implementation is O(N^2). Your end result is a sorted deck, and random_value is a number that when repeatedly mod'd and divided by the appropriate index to generate a "random" number during a Fisher-Yates shuffle would produce your original permutation. In practice, you'd implement the algorithm in O(N) by first doing a single linear scan to build an index (actually just held in an array) of cards to their positions. Also, you wouldn't actually perform the swap, since you never look at deck[i] after performing the swap. You just do deck[index] = deck[i]. So, at the end, you won't wind up with deck being sorted.
  • zokier 9y ago
    Okay, I got a deck of cards and had quick try. Immediately I noticed few issues: 1) You practically need two decks of cards. One which stores your key, and another which you use for the encryption process. This is needed because the matrix is mutated when doing encryption, meaning that you lose the original key. So before you start encrypting, you sync the two decks so that one can be messed up and another still retains the key. 2) Nonce generation is an problem. Simplest way I got for now is shuffle unused 16 cards (e.g. 10,J,Q,K) and draw them pairwise and use the pair to get character (base4->base36 conversion). It is not ideal, but doable. 3) Signature is supposed to be a secret, but no method for managing it is provided. Again, leftover cards could be used here, but if the above simple card-pair -> character mapping is used then you get only 8 characters when the paper recommends 10. It is not clear how critical the randomness here is. Practically it can be considered part of your key almost. 4) Surprisingly large amount of desk space required. Not something that really would pose a problem, but you definitely need some space to layout the 6x6 matrix. I imagine with standard sized cards, 7x7 (as mentioned in one of the comments) would be already challenging. If you additionally need to manage the second deck (see 1.) then that might need some more space. 5) For effective use you need will need lookup tables for both card->character->card mapping and card->movement mappings. They can easily be generated on demand (basically base conversion table between 6/9/36) and as such do not need to be permanent, but its still a consideration. 6) Lookup tables feel like they will slow down the process. You will be doing at least 3 (or 5 depending on how you count) lookups for each character encrypted. And of course you will need to be careful with the lookups, try to avoid mixing up down vs right movements and adjacent rows/columns. 7) 36 characters is actually pretty limited. Sure, you can write messages with just [A-Z0-9], using e.g. 0 (or #/_ like in the article) as word-separator etc. 7x7 would be significant improvement here. If you don't mind extending the length of the message then I suppose you could use some sort of preprocessing to widen the character set (e.g. use 4 symbols to encode 3 chars). Although that might make the already laborous process too much so. 8) Still need to time the process. I feel like initially it will be super slow, but especially if you can manage to keep the lookups in your head then it might actually not be that bad.
• maxerickson 9y ago
  It'd be easy enough to store a key in a deck of cards. (just map the alphabet to cards 1:1 and ignore some cards)