mpn_cnd_swap
Niels Möller
nisse at lysator.liu.se
Sun Sep 7 08:00:29 UTC 2014
Can we make mpn_cnd_swap public and documented? Currently, it's a static
function in sec_invert.c.
void
mpn_cnd_swap (int cnd, volatile mp_limb_t *ap, volatile mp_limb_t *bp,
mp_size_t n);
Hmm, or maybe the cnd argument ought to be of type mp_limb_t, same as
for mpn_cnd_add_n? I don't quite remember exactly why we do that, but I
think the point was to be able to use any carry out limb as a condition,
and using a plain int breaks in the case that the limb is non-zero but
with the low 32 bits clear.
One use case for mpn_cnd_swap is side-channel silent montgomery-ladder
elliptic curve multiplication, as described by djb at
http://www.ietf.org/mail-archive/web/cfrg/current/msg05004.html:
x2,z2,x3,z3 = 1,0,x1,1
for i in reversed(range(255)):
bit = 1 & (n >> i)
x2,x3 = cswap(x2,x3,bit)
z2,z3 = cswap(z2,z3,bit)
x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2)
x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^2+A*x2*z2+z2^2))
x2,x3 = cswap(x2,x3,bit)
z2,z3 = cswap(z2,z3,bit)
return x2*z2^(p-2)
(I think the initial swap could be replaced by a conditional copy of
appropriate intermediate values, since the point is to select which
point to double in the x2,z2 update, while the x3,z3 update is an
addition which is symmetric and gives the correct result also if applied
to the unswapped inputs. But the final swap really needs to be a swap).
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list