# [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

```