]>
Commit | Line | Data |
---|---|---|
90112edb NM |
1 | /* ecc-mod.c |
2 | ||
3 | Copyright (C) 2013 Niels Möller | |
4 | ||
5 | This file is part of GNU Nettle. | |
6 | ||
7 | GNU Nettle is free software: you can redistribute it and/or | |
8 | modify it under the terms of either: | |
9 | ||
10 | * the GNU Lesser General Public License as published by the Free | |
11 | Software Foundation; either version 3 of the License, or (at your | |
12 | option) any later version. | |
13 | ||
14 | or | |
15 | ||
16 | * the GNU General Public License as published by the Free | |
17 | Software Foundation; either version 2 of the License, or (at your | |
18 | option) any later version. | |
19 | ||
20 | or both in parallel, as here. | |
21 | ||
22 | GNU Nettle is distributed in the hope that it will be useful, | |
23 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
24 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
25 | General Public License for more details. | |
26 | ||
27 | You should have received copies of the GNU General Public License and | |
28 | the GNU Lesser General Public License along with this program. If | |
29 | not, see http://www.gnu.org/licenses/. | |
30 | */ | |
9422a551 | 31 | |
f1812845 | 32 | /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */ |
9422a551 NM |
33 | |
34 | #if HAVE_CONFIG_H | |
35 | # include "config.h" | |
36 | #endif | |
37 | ||
38 | #include <assert.h> | |
39 | ||
40 | #include "ecc-internal.h" | |
41 | ||
f4f5625e NM |
42 | /* Computes r <-- x mod m, input 2*m->size, output m->size. It's |
43 | * allowed to have rp == xp or rp == xp + m->size, but no other kind | |
44 | * of overlap is allowed. */ | |
9422a551 | 45 | void |
f4f5625e | 46 | ecc_mod (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp) |
9422a551 NM |
47 | { |
48 | mp_limb_t hi; | |
a78c9459 NM |
49 | mp_size_t mn = m->size; |
50 | mp_size_t bn = m->B_size; | |
9422a551 | 51 | mp_size_t sn = mn - bn; |
0b511c91 | 52 | mp_size_t rn = 2*mn; |
9422a551 | 53 | mp_size_t i; |
a78c9459 | 54 | unsigned shift; |
9422a551 | 55 | |
90e3aee6 | 56 | assert (bn < mn); |
9422a551 NM |
57 | |
58 | /* FIXME: Could use mpn_addmul_2. */ | |
a78c9459 NM |
59 | /* Eliminate sn limbs at a time */ |
60 | if (m->B[bn-1] < ((mp_limb_t) 1 << (GMP_NUMB_BITS - 1))) | |
9422a551 NM |
61 | { |
62 | /* Multiply sn + 1 limbs at a time, so we get a mn+1 limb | |
63 | product. Then we can absorb the carry in the high limb */ | |
64 | while (rn > 2 * mn - bn) | |
65 | { | |
66 | rn -= sn; | |
67 | ||
68 | for (i = 0; i <= sn; i++) | |
f4f5625e NM |
69 | xp[rn+i-1] = mpn_addmul_1 (xp + rn - mn - 1 + i, m->B, bn, xp[rn+i-1]); |
70 | xp[rn-1] = xp[rn+sn-1] | |
71 | + mpn_add_n (xp + rn - sn - 1, xp + rn - sn - 1, xp + rn - 1, sn); | |
9422a551 | 72 | } |
9422a551 NM |
73 | } |
74 | else | |
75 | { | |
c17a6a09 | 76 | while (rn > 2 * mn - bn) |
9422a551 NM |
77 | { |
78 | rn -= sn; | |
79 | ||
80 | for (i = 0; i < sn; i++) | |
f4f5625e | 81 | xp[rn+i] = mpn_addmul_1 (xp + rn - mn + i, m->B, bn, xp[rn+i]); |
9422a551 | 82 | |
f4f5625e NM |
83 | hi = mpn_add_n (xp + rn - sn, xp + rn - sn, xp + rn, sn); |
84 | hi = mpn_cnd_add_n (hi, xp + rn - mn, xp + rn - mn, m->B, mn); | |
0e1d3111 | 85 | assert_maybe (hi == 0); |
9422a551 NM |
86 | } |
87 | } | |
88 | ||
c17a6a09 NM |
89 | assert (rn > mn); |
90 | rn -= mn; | |
91 | assert (rn <= sn); | |
92 | ||
93 | for (i = 0; i < rn; i++) | |
f4f5625e | 94 | xp[mn+i] = mpn_addmul_1 (xp + i, m->B, bn, xp[mn+i]); |
c17a6a09 | 95 | |
f4f5625e | 96 | hi = mpn_add_n (xp + bn, xp + bn, xp + mn, rn); |
c17a6a09 | 97 | if (rn < sn) |
f4f5625e | 98 | hi = sec_add_1 (xp + bn + rn, xp + bn + rn, sn - rn, hi); |
9422a551 | 99 | |
a78c9459 | 100 | shift = m->size * GMP_NUMB_BITS - m->bit_size; |
9422a551 NM |
101 | if (shift > 0) |
102 | { | |
103 | /* Combine hi with top bits, add in */ | |
f4f5625e NM |
104 | hi = (hi << shift) | (xp[mn-1] >> (GMP_NUMB_BITS - shift)); |
105 | xp[mn-1] = (xp[mn-1] & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1)) | |
106 | + mpn_addmul_1 (xp, m->B_shifted, mn-1, hi); | |
107 | /* FIXME: Can this copying be eliminated? */ | |
108 | if (rp != xp) | |
109 | mpn_copyi (rp, xp, mn); | |
9422a551 NM |
110 | } |
111 | else | |
112 | { | |
f4f5625e | 113 | hi = mpn_cnd_add_n (hi, rp, xp, m->B, mn); |
0e1d3111 | 114 | assert_maybe (hi == 0); |
9422a551 NM |
115 | } |
116 | } |