Hiding knowledge in permutations

The newest situation of Paged Out! has an article by Stephen Hewitt “An off-line backup of your cryptographic key utilizing enjoying playing cards.” The concept is to make use of a deck of 52 to retailer a 128-bit cryptographic key. To erase the important thing, shuffle the deck. Hewitt provides his algorithm for embedding a key, one that may be carried out manually however isn’t maximally environment friendly.

You might retailer a 225-bit key as a permutation of 52 playing cards as a result of

log₂(52!) = 225.581.

However then how would you quantity permutations so you might go from a quantity to a specific permutation and later decode the permutation to a quantity? Is that this even sensible? For a small quantity n, you might encode a quantity ok < n by enumerating the primary ok permutations of a set of n objects, and you might decode by enumerating permutations till you discover the one you may have. However that is fully impractical for big n, reminiscent of n = 52.

The method of mapping permutation to an integer known as rating, and the mapping from an integer to a permutation known as unranking. How effectively can rankings and unrankings be calculated?

Let n be the variety of symbols being permuted. Then there are easy algorithms for rating and unranking with respect to lexicographical order which have complexity O(n²) and extra subtle algorithms which have complexity O(n log n). There are additionally O(n) algorithms that don’t protect lexicographical order.

The Permutations class in SymPy has strategies unrank_lex and rank to unrank and rank permutations in accordance with lexicographical order.

The notation the Permutations class makes use of requires just a little clarification. For instance, suppose we unrank 2026.

>>> from sympy.combinatorics import Permutation
>>> Permutation.unrank_lex(52, 2026)
Permutation(45, 47, 51, 48, 46, 50)

The output just isn’t a full listing of 52 numbers in permuted order; it is just a cycle. The notation refers back to the permutation that sends 45 to 47, 47 to 51, …, 50 to 45 and leaves the whole lot else fastened.

If we rank the permutation given above, we get 2026 again.

>>> Permutation.rank(Permutation(45, 47, 51, 48, 46, 50))
2026

Word that we didn’t say what number of components (45, 47, 51, 48, 46, 50) is a permutation of. Due to lexicographical order, the rank could be the identical whether or not we seen this as a permutation of 52 objects or of extra objects.

Now let’s do one thing bigger. Let’s generate a 220-bit quantity and encode it as a permutation.

>>> n = random.getrandbits(225)
>>> a = Permutation.unrank_lex(52, n)
>>> n
40234719030664563684489051530416964877785781669439875437823431388841
>>> a
Permutation(0, 25, 32, 15, 8, 28)(1, 48, 34, 14, 10, 51, 38, 31, 21, 5, 42, 47, 29, 26, 46, 30, 50, 49, 37, 22, 18, 23)(2, 45, 17, 20, 36, 40, 11, 4, 7, 41, 33, 3, 43, 44, 19, 16, 35, 39, 12, 6, 9)
>>> Permutation.rank(a) == n
True

Now only for enjoyable, let’s show the permutation above utilized to an ordinary (French) deck of 52 playing cards. As defined right here, symbols related to these playing cards have a spread of Unicode values. By printing these values, we are able to visualize the permuted deck.

Right here’s the code that made the picture above.

spades = listing(vary(0x1F0A1, 0x1F0AF))
spades.take away(0x1F0AC) # take out the knight
playing cards = [s + 16*i for s in spades for i in range(4)]

a = Permutation.unrank_lex(52, n)
p = a(playing cards)

for i in vary(4):
    for j in vary(13):
        print(chr(p[13*i + j]), finish="")
    print()

The code above is a lot quick, however Permutation has strategies rank_nonlex and unrank_nonlex that run in O(n) time, which may very well be helpful for n a lot bigger than 52.