another feature RNGs could provide

Ben Laurie ben at algroup.co.uk
Wed Dec 21 15:08:32 EST 2005


Matt Crawford wrote:
> On Dec 21, 2005, at 0:10, Ben Laurie wrote:
>> Good ciphers aren't permutations, though, are they? Because if they
>> were, they'd be groups, and that would be bad.
> 
> A given cipher, with a given key, is a permutation of blocks.  (Assuming
> output blocks and input blocks are the same size.)  It may be (and often
> is) the case that the set of all keys does not span the set of all
> possible permutations, in which case the permutations
> 
>   { E_k() | k in set of all keys }
> 
> may or may not turn out to be a group.
> 
> For blocks of n bits and keys of m bits, there are n! permutations but
> 2^m of them are representable by some key.  If m = n, this is a fraction
> roughly equal to
> 
>   (2e/n)^n
> 
> About 10^-70 for n=64.  I don't know the probability of a randomly
> selected subset of a permutation group being a group, but at these
> scales, I bet it's small.

Must try not to post to crypto when I'm jetlagged! I had my wires
crossed here, what's bad is when the keys form a group, of course (as
others have also pointed out).

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/
**  ApacheCon - Dec 10-14th - San Diego - http://apachecon.com/ **
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list