Crygop/en

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 [1]):

INTERFACE

in: x from [0..n]; n; key
out: x'

PREPARATION

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][0] <- k || 'a' || i; /* i is 32bit, little endian */
k[i][0] <- k || 'b' || i;
k[i][0] <- k || 'c' || i;
k[i][0] <- 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;

"ENCRYPTION"

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][0], x);
  if(limita < x <=limitb)
    x <- enc(k[i][1], x-limita-1)+limita+1;
  if(limitb < x <=limitc)
    x <- enc(k[i][2], x-limitb-1)+limitb+1;
  if(limitd < x)
    x <- enc(k[i][3], x-limitd-1)+limitd+1; 
end
x' <- x;

"DECRYPTION"

for i in [rounds-1..0] do
  if(limitd < x)
    x <- dec(k[i][3], x-limitd-1)+limitd+1; 
  if(limitb < x <=limitc)
    x <- dec(k[i][2], x-limitb-1)+limitb+1;
  if(limita < x <=limitb)
    x <- dec(k[i][1], x-limita-1)+limita+1;
  if(x <=limita)
    x <- dec(k[i][0], x);
  x <- ((x-b[i])+q[i]) mod (n+1); /* affine transformation */
end
x' <- x;

---

I thought of different modifications to achieve different aims:

1. reducing the number of different keys would allow fast implementations using look-up-tables.
2. setting a top limit for v would also reduce the memory requirements of a LUT-implementation
3. using a block-cipher which takes blocks of even and odd size would improve security and speed (depending on the cipher)

---

Resources

[1] or [2]

SVN repository: [3] [4] (suitable for browsing)

--Bg 04:41, 21. Mai 2008 (CEST)