another feature RNGs could provide

David Malone dwmalone at maths.tcd.ie
Tue Dec 27 17:18:53 EST 2005


On Mon, Dec 26, 2005 at 12:51:37PM +0000, Ben Laurie wrote:
> > The other day I was thinking of using a very large key to select a
> > permutation at random from the symmetric group S_(2^x).  That would be
> > a group, but I don't see how you knowing that I'm using a random
> > permutation would help you at all.

> Surely if you do this, then there's a meet-in-the middle attack: for a
> plaintext/ciphertext pair, P, C, I choose random keys to encrypt P and
> decrypt C. If E_A(P)=D_B(C), then your key was A.B, which reduces the
> strength of your cipher from 2^x to 2^(x/2)?

S_n has size n!, so the size of the keyspace is (2^x)!. The thing
is that if you compose two of these the resulting key space is of
size (2^x)!, because you've already got all possible permutations,
so you gain nothing from it.

Usually a cypher is a small subset of the set of all possible
permutations, so composing the permutations may result in a bigger
subset. If the subset turns out to be a subgroup, then you gain
nothing, because a subgroup would be closed under composition.

In the case of having a plaintext/cyphertext pair in a cypher where
the key can be any possible permutation, knowing E(P) = C tells you
nothing except D(C) = P and E(X) != C for X != P, because the image
of one element tells you nothing about the others.

	David.

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



More information about the cryptography mailing list