ni...@lysator.liu.se (Niels Möller) writes:
As you can see, it depends on a couple of other functions,
mpn_sec_add_1, mpn_cnd_neg, mpn_cnd_swap, mpn_sec_eq_ui, which would
probably have to be written in assembly to ensure that they avoid
operations with branches or data-dependent timing.
Torbjorn Granlund t...@gmplib.org writes:
I suppose I already suggested that one computes a^{-1} mod b
as a^{b-1} mod b, using a plain old modexp.
For prime b (which is an important special case).
I realise that this will be asymptotically slower, in this setting
O(n^3) vs O(n^2), but it
Torbjorn Granlund t...@gmplib.org writes:
* mpn_sec_add_1
I'd say use the obvious algorithm: Create vector of n-1 zeros and then
the input limb arg at index 0, invoke mpn_add_n.
That's good enough, I guess, at the cost of some extra scratch space.
* mpn_cnd_neg
Create zero vector,
ni...@lysator.liu.se (Niels Möller) writes:
Create zero vector, invoke mpn_sub_n.
That doesn't make it conditional. And I see no obvious way to do
conditional negation on top of mpn_cnd_sub_n.
Oops.
Compute T = 2 x A using mpn_add_n or mpn_lshift.
Use mpn_cnd_sub_n with A, T as
Torbjorn Granlund t...@gmplib.org writes:
Compute T = 2 x A using mpn_add_n or mpn_lshift.
Use mpn_cnd_sub_n with A, T as arguments.
Should work (except if T is computed mod B^n, one doesn't get the
correct carry out, but that isn't needed here). But it's a bit awkward,
and this is a
ni...@lysator.liu.se (Niels Möller) writes:
Should work (except if T is computed mod B^n, one doesn't get the
correct carry out, but that isn't needed here). But it's a bit awkward,
I realise one needs some (straightforward) handling of carry out.
and this is a performacne critical
Torbjorn Granlund t...@gmplib.org writes:
I had neglected the significance of modular inversion for elliptic curve
arithmetic.
In my implementation, it's needed in two places.
* For ecdsa signatures, the random nonce k is inverted mod q, the ecc
group order.
* When converting coordinates
I suppose I already suggested that one computes a^{-1} mod b
as a^{b-1} mod b, using a plain old modexp.
I realise that this will be asymptotically slower, in this setting
O(n^3) vs O(n^2), but it ought have a much lower constant factor.
Torbjörn
___
Ciao,
Il Ven, 27 Dicembre 2013 12:53 am, Torbjorn Granlund ha scritto:
I realise that this will be asymptotically slower, in this setting
O(n^3) vs O(n^2), but it ought have a much lower constant factor.
We will introduce a side-channel silent threshold...
Regards,
m
--
http://bodrato.it/
