|
Packit Service |
4684c1 |
/* ecc-mod.c
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
Copyright (C) 2013 Niels Möller
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
This file is part of GNU Nettle.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
GNU Nettle is free software: you can redistribute it and/or
|
|
Packit Service |
4684c1 |
modify it under the terms of either:
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
* the GNU Lesser General Public License as published by the Free
|
|
Packit Service |
4684c1 |
Software Foundation; either version 3 of the License, or (at your
|
|
Packit Service |
4684c1 |
option) any later version.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
or
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
* the GNU General Public License as published by the Free
|
|
Packit Service |
4684c1 |
Software Foundation; either version 2 of the License, or (at your
|
|
Packit Service |
4684c1 |
option) any later version.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
or both in parallel, as here.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
GNU Nettle is distributed in the hope that it will be useful,
|
|
Packit Service |
4684c1 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
4684c1 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit Service |
4684c1 |
General Public License for more details.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
You should have received copies of the GNU General Public License and
|
|
Packit Service |
4684c1 |
the GNU Lesser General Public License along with this program. If
|
|
Packit Service |
4684c1 |
not, see http://www.gnu.org/licenses/.
|
|
Packit Service |
4684c1 |
*/
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
#if HAVE_CONFIG_H
|
|
Packit Service |
4684c1 |
# include "config.h"
|
|
Packit Service |
4684c1 |
#endif
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
#include <assert.h>
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
#include "ecc-internal.h"
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* Computes r mod m, input 2*m->size, output m->size. */
|
|
Packit Service |
4684c1 |
void
|
|
Packit Service |
4684c1 |
ecc_mod (const struct ecc_modulo *m, mp_limb_t *rp)
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
mp_limb_t hi;
|
|
Packit Service |
4684c1 |
mp_size_t mn = m->size;
|
|
Packit Service |
4684c1 |
mp_size_t bn = m->B_size;
|
|
Packit Service |
4684c1 |
mp_size_t sn = mn - bn;
|
|
Packit Service |
4684c1 |
mp_size_t rn = 2*mn;
|
|
Packit Service |
4684c1 |
mp_size_t i;
|
|
Packit Service |
4684c1 |
unsigned shift;
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
assert (bn < mn);
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* FIXME: Could use mpn_addmul_2. */
|
|
Packit Service |
4684c1 |
/* Eliminate sn limbs at a time */
|
|
Packit Service |
4684c1 |
if (m->B[bn-1] < ((mp_limb_t) 1 << (GMP_NUMB_BITS - 1)))
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
/* Multiply sn + 1 limbs at a time, so we get a mn+1 limb
|
|
Packit Service |
4684c1 |
product. Then we can absorb the carry in the high limb */
|
|
Packit Service |
4684c1 |
while (rn > 2 * mn - bn)
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
rn -= sn;
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
for (i = 0; i <= sn; i++)
|
|
Packit Service |
4684c1 |
rp[rn+i-1] = mpn_addmul_1 (rp + rn - mn - 1 + i, m->B, bn, rp[rn+i-1]);
|
|
Packit Service |
4684c1 |
rp[rn-1] = rp[rn+sn-1]
|
|
Packit Service |
4684c1 |
+ mpn_add_n (rp + rn - sn - 1, rp + rn - sn - 1, rp + rn - 1, sn);
|
|
Packit Service |
4684c1 |
}
|
|
Packit Service |
4684c1 |
goto final_limbs;
|
|
Packit Service |
4684c1 |
}
|
|
Packit Service |
4684c1 |
else
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
/* The loop below always runs at least once. But the analyzer
|
|
Packit Service |
4684c1 |
doesn't realize that, and complains about hi being used later
|
|
Packit Service |
4684c1 |
on without a well defined value. */
|
|
Packit Service |
4684c1 |
#ifdef __clang_analyzer__
|
|
Packit Service |
4684c1 |
hi = 0;
|
|
Packit Service |
4684c1 |
#endif
|
|
Packit Service |
4684c1 |
while (rn >= 2 * mn - bn)
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
rn -= sn;
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
for (i = 0; i < sn; i++)
|
|
Packit Service |
4684c1 |
rp[rn+i] = mpn_addmul_1 (rp + rn - mn + i, m->B, bn, rp[rn+i]);
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
hi = mpn_add_n (rp + rn - sn, rp + rn - sn, rp + rn, sn);
|
|
Packit Service |
4684c1 |
hi = cnd_add_n (hi, rp + rn - mn, m->B, mn);
|
|
Packit Service |
4684c1 |
assert (hi == 0);
|
|
Packit Service |
4684c1 |
}
|
|
Packit Service |
4684c1 |
}
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
if (rn > mn)
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
final_limbs:
|
|
Packit Service |
4684c1 |
sn = rn - mn;
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
for (i = 0; i < sn; i++)
|
|
Packit Service |
4684c1 |
rp[mn+i] = mpn_addmul_1 (rp + i, m->B, bn, rp[mn+i]);
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
hi = mpn_add_n (rp + bn, rp + bn, rp + mn, sn);
|
|
Packit Service |
4684c1 |
hi = sec_add_1 (rp + bn + sn, rp + bn + sn, mn - bn - sn, hi);
|
|
Packit Service |
4684c1 |
}
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
shift = m->size * GMP_NUMB_BITS - m->bit_size;
|
|
Packit Service |
4684c1 |
if (shift > 0)
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
/* Combine hi with top bits, add in */
|
|
Packit Service |
4684c1 |
hi = (hi << shift) | (rp[mn-1] >> (GMP_NUMB_BITS - shift));
|
|
Packit Service |
4684c1 |
rp[mn-1] = (rp[mn-1] & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
|
|
Packit Service |
4684c1 |
+ mpn_addmul_1 (rp, m->B_shifted, mn-1, hi);
|
|
Packit Service |
4684c1 |
}
|
|
Packit Service |
4684c1 |
else
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
hi = cnd_add_n (hi, rp, m->B_shifted, mn);
|
|
Packit Service |
4684c1 |
assert (hi == 0);
|
|
Packit Service |
4684c1 |
}
|
|
Packit Service |
4684c1 |
}
|