this also got to sci.crypt:
I was looking for an algorithm which cryptographically secure permutes integers in [0 .. n] (or maps a integer from [0..n] to another integer [0..n]). This is quite easy when n is of the form n=2**(2v)-1 with v being an positive integer (in this case one could use a simple blockcipher with the blocksize being 2v).
The strongest criterion for being cryptographically secure I thought of is that an attacker knowing all mappings of x to x' except a->a' and b->b' (and not knowing the secret key of course) can not decide with a probability larger than 50% if a maps to a' or b'.
A possible solution for this problem would be to store the integers from 0 to n in an array ant then permute the entrys in the array in a pseudo random way. Due to the relative high memory usage of this method a implementation is not feasible for me (I'm developing for a microcontroller system which has only 2KiB RAM).
So I designed an algorithm by myself and I'm very interested in your opinions, comments, critics and analysis.
I use a construction consisting of multiple rounds, where the input is linearly transformed (x' = x*a+b mod n), and then subsets are independently transformed by a blockcipher.
Now the description in pseudo-code (a implementation in C can be downloaded from ):
in: x from [0..n]; n; key out: x'
set v so that: 2**(v)-1 <= n < 2**(v+1); v <- v&~1; /* clear the last bit of v */
enc(k,x): [0..2**(v)-1] -> [0..2**(v)-1]; /* encryption of a v-bit block*/ dec(k, enc(k,x)) = x;
limita <- 1*2**(v)-1; limitb <- 2*2**(v)-1; limitc <- 3*2**(v)-1; limitd <- n-2**(v)-1;
if(limitb > n) limitb <- 0; if(limitc > n) limitc <- 0;
--subkey-generation-- k[i] <- k || 'a' || i; /* i is 32bit, little endian */ k[i] <- k || 'b' || i; k[i] <- k || 'c' || i; k[i] <- k || 'd' || i;
a[i] is pseudo randomly derived from k, gcd(n, a[i])=1; b[i] is pseudo randomly derived from k q[i] <- a[i]**(-1) mod n;
for i in [0..rounds-1] do x <- (x*a[i]+b[i]) mod (n+1); /* affine transformation */ if(x <=limita) x <- enc(k[i], x); if(limita < x <=limitb) x <- enc(k[i], x-limita-1)+limita+1; if(limitb < x <=limitc) x <- enc(k[i], x-limitb-1)+limitb+1; if(limitd < x) x <- enc(k[i], x-limitd-1)+limitd+1; end x' <- x;
for i in [rounds-1..0] do if(limitd < x) x <- dec(k[i], x-limitd-1)+limitd+1; if(limitb < x <=limitc) x <- dec(k[i], x-limitb-1)+limitb+1; if(limita < x <=limitb) x <- dec(k[i], x-limita-1)+limita+1; if(x <=limita) x <- dec(k[i], x); x <- ((x-b[i])+q[i]) mod (n+1); /* affine transformation */ end x' <- x;
I thought of different modifications to achieve different aims:
- reducing the number of different keys would allow fast implementations using look-up-tables.
- setting a top limit for v would also reduce the memory requirements of a LUT-implementation
- using a block-cipher which takes blocks of even and odd size would improve security and speed (depending on the cipher)
--Bg 04:41, 21. Mai 2008 (CEST)