[3698] in cryptography@c2.net mail archive
Re: Is a serial cable as good as thin air?
daemon@ATHENA.MIT.EDU (Colin Plumb)
Fri Dec 4 10:56:45 1998
Date: Thu, 3 Dec 1998 19:42:59 -0700 (MST)
From: Colin Plumb <colin@nyx.net>
To: aba@dcs.ex.ac.uk, drc@adni.net
Cc: cryptography@c2.net
> static uint16 mul(register uint16 a, register uint16 b)
> {
> register word32 p;
>
> p = (word32) a *b;
> if (p) {
> b = low16(p);
> a = p >> 16;
> return (b - a) + (b < a);
> } else if (a) {
> return 1 - a;
> } else {
> return 1 - b;
> }
> } /* mul */
> There was some discussion of approaches to coding a constant time
> multiplication mod 65537 function on sci.crypt around October 96.
Note that on many microprocessors multiply is not a constant-time instruction,
leading to difficulties.
However, in more recent code there are two alternatives:
An optimized version of the above:
{
register PGPUInt32 p;
p = (uint32)a * b;
if (p) {
b = low16(p);
a = p>>16;
return (b - a) + (b < a);
} else {
return 1-a-b;
}
}
and the AVOID_JUMPS case, which is constant-time if the multiply is
(it's also faster on some processors):
{
register word32 p;
a = low16(a-1);
b = low16(b-1);
p = (uint32)a*b + a + b;
a = low16(p);
b = p >> 16;
return (a - b) + (a < b) + 1;
}
The only potential gotcha is the "a < b" part, which compilers
usually find branch-free code for, but sometimes they're dumb.
--
-Colin
