1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
/* ecc-mod.c */
/* nettle, low-level cryptographics library
*
* Copyright (C) 2013 Niels Möller
*
* The nettle library is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2.1 of the License, or (at your
* option) any later version.
*
* The nettle library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
* License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with the nettle library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02111-1301, USA.
*/
/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
#if HAVE_CONFIG_H
# include "config.h"
#endif
#include <assert.h>
#include "ecc-internal.h"
/* Computes r mod m, where m is of size mn. bp holds B^mn mod m, as mn
limbs, but the upper mn - bn libms are zero. */
void
ecc_mod (mp_limb_t *rp, mp_size_t rn, mp_size_t mn,
const mp_limb_t *bp, mp_size_t bn,
const mp_limb_t *b_shifted, unsigned shift)
{
mp_limb_t hi;
mp_size_t sn = mn - bn;
mp_size_t i;
assert (sn > 0);
/* FIXME: Could use mpn_addmul_2. */
/* Eliminate sn = mn - bn limbs at a time */
if (bp[bn-1] < ((mp_limb_t) 1 << (GMP_NUMB_BITS - 1)))
{
/* Multiply sn + 1 limbs at a time, so we get a mn+1 limb
product. Then we can absorb the carry in the high limb */
while (rn > 2 * mn - bn)
{
rn -= sn;
for (i = 0; i <= sn; i++)
rp[rn+i-1] = mpn_addmul_1 (rp + rn - mn - 1 + i, bp, bn, rp[rn+i-1]);
rp[rn-1] = rp[rn+sn-1]
+ mpn_add_n (rp + rn - sn - 1, rp + rn - sn - 1, rp + rn - 1, sn);
}
goto final_limbs;
}
else
{
while (rn >= 2 * mn - bn)
{
rn -= sn;
for (i = 0; i < sn; i++)
rp[rn+i] = mpn_addmul_1 (rp + rn - mn + i, bp, bn, rp[rn+i]);
hi = mpn_add_n (rp + rn - sn, rp + rn - sn, rp + rn, sn);
hi = cnd_add_n (hi, rp + rn - mn, bp, mn);
assert (hi == 0);
}
}
if (rn > mn)
{
final_limbs:
sn = rn - mn;
for (i = 0; i < sn; i++)
rp[mn+i] = mpn_addmul_1 (rp + i, bp, bn, rp[mn+i]);
hi = mpn_add_n (rp + bn, rp + bn, rp + mn, sn);
hi = sec_add_1 (rp + bn + sn, rp + bn + sn, mn - bn - sn, hi);
}
if (shift > 0)
{
/* Combine hi with top bits, add in */
hi = (hi << shift) | (rp[mn-1] >> (GMP_NUMB_BITS - shift));
rp[mn-1] = (rp[mn-1] & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
+ mpn_addmul_1 (rp, b_shifted, mn-1, hi);
}
else
{
hi = cnd_add_n (hi, rp, bp, mn);
assert (hi == 0);
}
}
|
