A Question of Permutations of Vectors of Bits

From: Simon G Best (s.g.best_at_btopenworld.com)
Date: 07/31/03 

Date: Thu, 31 Jul 2003 05:09:14 +0000 (UTC)

Hello!

P is a permutation of 2n-bit vectors. x and y are 2n-bit vectors, such that

         y = x + P(x)

(where '+' is bitwise-xor). P is easily invertible.

What I'm interested in right now are general approaches to solving for x
when y and P are known. In particular, I'm interested in general
solutions that take less than 2^n steps (a step being comparable to
trying a single guess for x, and seeing if it works).

(Why? Well, I've been competing against myself, trying to devise a PRNG
that's as simple as I can make it without being able to break it. So
far, I've gone through several PRNGs in quick succession. This is just
to give me a little bit of practice with cryptanalysis, and is rather
like a little bit of leisurely hill-walking compared to taking on the
Himalayan peak of something like AES.)

So, I'd like to ask for some pointers and comments, and that sort of
thing, please :-)

Simon

Relevant Pages