On Wed, Jan 19, 2011 at 10:37 PM, < [email protected]<travis%[email protected]> > wrote:
> > 4. You can now construct an encryption algorithm which encrypts within > this > > set. Alternatives include: > > Ah, I hadn't considered the re-hashing until it fell within range. > > But why do I not see "cryptographically-strong permutations for sets > with cardinality other than 2^n"? It seems like a very natural > primitive for certain things, albeit not for passing octet streams. > Seems like academics would be all over that like wet on water. Maybe > I'm just not googling the right things, or looking in the right > places. I wrote an essay on this once, but I can't find it now. I had diagrams & everything. You can avoid the rehashing by building a feistel-constructed block cipher that works modulo N, with addition as the mixing operator rather than XOR. For example, if you wanted to encrypt 8-character C++ identifiers (cardinality of the set = 53*63^7 = 208765973875851), then you can, in each round, split into two unbalanced halves (left = v / 63^4 (truncating division); right = v % 63^4); then, the left has values 0..13252490, and the right has values 0..15752960. In each round, you calculate f(right), where f is a cryptographically mostly-secure keyed mapping (not necessarily reversible) from the values 0..15752960 to 0..13252490. For our purposes, AES-encrypting the right side and then reducing the result modulo 13252491 is probably fine; it's not a perfectly balanced value, but I'm guessing it's enough for your purposes; even if it weren't, it's nothing that a few more rounds wouldn't fix. The output of the round is right * 13252491 + (f(right) + left) % 13252491. I found http://www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf linked-to from the Wikipedia Feistel cipher article. It has some citations that will get you further in the literature. - Tim
_______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
