[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