[cryptography] ciphers with keys modifying control flow?

Marsh Ray marsh at extendedsubset.com
Wed Sep 29 13:29:28 EDT 2010


On 09/29/2010 02:28 AM, Sandy Harris wrote:
>
> pht2(T *a, T *b)
> {
>      T x, y ;
>      x = *a + *b ;
>      y = x + *a ;    // 2*a+b
>      if (z&  1) {
>          *a = x ;
>          *b = y ;
>     }
>     else {
>          *a = y ;
>          *b = x ;
>     }
>     z>>= 1 ;
> }
>
> 32 bits of z then control the 32 2-way PHTs that
> make up the 16-way one. The key-derived data
> z is directly controlling a bunch of if/else choices.

We can transform this so that the low bit of z basically controls a 
conditional swap:

void pht2(T & a, T & b) // I like C++ refs
{
     b += a;
     a += b;

     if (z & 1)
	swap(a, b);

     z >>= 1;
}

We can implement a conditional swap without the 'if' statement:

void cswap(bool cond, T & a, T & b)
{
     // m is just a mask formed by copying the low bit of cond
     // to all positions.
     T m = cond ? T(-1) : T(0);    // assuming T is unsigned here

     a ^= b & m;
     b ^= a & m;
     a ^= b & m;
}

void pht2(T & a, T & b) // I like C++ refs
{
     b += a;
     a += b;
     cswap(z & 1, a, b);
     z >>= 1;
}

But looking again at your code comment:

     T x = *a + *b;
     T y = x + *a; // 2*a+b

We're really just swapping between (a + b) and (2a + b).
Since (a << 0 == a) and (a << 1 == 2a), we can write:

void pht2(T & a, T & b) // C++ refs again
{
     bool r = z & 1;
     z >>= 1;

     T a_in = a;
     a = b;
     a += a_in << r;
     b += a_in << !r;
}

So it's equivalent to a data-dependent shift or (with minor adjustment) 
rotate operation.

I have another interesting variation in mind, but it will have to wait, 
I left my laptop charger at home today.

- Marsh



More information about the cryptography mailing list