1 /* ecc-mul-m.c
2
3 Point multiplication using Montgomery curve representation.
4
5 Copyright (C) 2014 Niels Möller
6
7 This file is part of GNU Nettle.
8
9 GNU Nettle is free software: you can redistribute it and/or
10 modify it under the terms of either:
11
12 * the GNU Lesser General Public License as published by the Free
13 Software Foundation; either version 3 of the License, or (at your
14 option) any later version.
15
16 or
17
18 * the GNU General Public License as published by the Free
19 Software Foundation; either version 2 of the License, or (at your
20 option) any later version.
21
22 or both in parallel, as here.
23
24 GNU Nettle is distributed in the hope that it will be useful,
25 but WITHOUT ANY WARRANTY; without even the implied warranty of
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 General Public License for more details.
28
29 You should have received copies of the GNU General Public License and
30 the GNU Lesser General Public License along with this program. If
31 not, see http://www.gnu.org/licenses/.
32 */
33
34 #if HAVE_CONFIG_H
35 # include "config.h"
36 #endif
37
38 #include <assert.h>
39
40 #include "ecc.h"
41 #include "ecc-internal.h"
42
43 void
ecc_mul_m(const struct ecc_modulo * m,mp_limb_t a24,unsigned bit_low,unsigned bit_high,mp_limb_t * qx,const uint8_t * n,const mp_limb_t * px,mp_limb_t * scratch)44 ecc_mul_m (const struct ecc_modulo *m,
45 mp_limb_t a24,
46 unsigned bit_low, unsigned bit_high,
47 mp_limb_t *qx, const uint8_t *n, const mp_limb_t *px,
48 mp_limb_t *scratch)
49 {
50 unsigned i;
51 mp_limb_t swap;
52
53 #define x2 (scratch)
54 #define z2 (scratch + m->size)
55 #define x3 (scratch + 2*m->size)
56 #define z3 (scratch + 3*m->size)
57
58 /* Formulas from RFC 7748:
59
60 A = x_2 + z_2
61 AA = A^2
62 B = x_2 - z_2
63 BB = B^2
64 E = AA - BB
65 C = x_3 + z_3
66 D = x_3 - z_3
67 DA = D * A
68 CB = C * B
69 x_3 = (DA + CB)^2
70 z_3 = x_1 * (DA - CB)^2
71 x_2 = AA * BB
72 z_2 = E * (AA + a24 * E)
73
74 For pure doubling, we use:
75
76 A = x_2 + z_2
77 AA = A^2
78 B = x_2 - z_2
79 BB = B^2
80 E = AA - BB
81 x3 = AA * BB
82 z3 = E * (AA + a24 * E)
83 */
84
85 #define A (scratch + 4*m->size)
86 #define AA A
87 #define D (scratch + 5*m->size)
88 #define DA D
89
90 #define tp (scratch + 6*m->size)
91
92 /* For the doubling formulas. */
93 #define B D
94 #define BB D
95 #define E D
96
97 /* Initialize, x2 = px, z2 = 1 */
98 mpn_copyi (x2, px, m->size);
99 z2[0] = 1;
100 mpn_zero (z2+1, m->size - 1);
101
102 /* Get x3, z3 from doubling. Since most significant bit is forced to 1. */
103 ecc_mod_add (m, A, x2, z2);
104 ecc_mod_sub (m, B, x2, z2);
105 ecc_mod_sqr (m, AA, A, tp);
106 ecc_mod_sqr (m, BB, B, tp);
107 ecc_mod_mul (m, x3, AA, BB, tp);
108 ecc_mod_sub (m, E, AA, BB);
109 ecc_mod_addmul_1 (m, AA, E, a24);
110 ecc_mod_mul (m, z3, E, AA, tp);
111
112 for (i = bit_high, swap = 0; i >= bit_low; i--)
113 {
114 mp_limb_t bit = (n[i/8] >> (i & 7)) & 1;
115
116 mpn_cnd_swap (swap ^ bit, x2, x3, 2*m->size);
117 swap = bit;
118
119 ecc_mod_add (m, A, x2, z2);
120 ecc_mod_sub (m, D, x3, z3);
121 ecc_mod_mul (m, DA, D, A, tp);
122 ecc_mod_sqr (m, AA, A, tp);
123
124 /* Store B, BB and E at z2 */
125 ecc_mod_sub (m, z2, x2, z2); /* B */
126 /* Store C and CB at z3 */
127 ecc_mod_add (m, z3, x3, z3); /* C */
128 ecc_mod_mul (m, z3, z3, z2, tp); /* CB */
129 ecc_mod_sqr (m, z2, z2, tp); /* BB */
130
131 /* Finish x2 */
132 ecc_mod_mul (m, x2, AA, z2, tp);
133
134 ecc_mod_sub (m, z2, AA, z2); /* E */
135
136 /* Finish z2 */
137 ecc_mod_addmul_1 (m, AA, z2, a24);
138 ecc_mod_mul (m, z2, z2, AA, tp);
139
140 /* Finish x3 */
141 ecc_mod_add (m, x3, DA, z3);
142 ecc_mod_sqr (m, x3, x3, tp);
143
144 /* Finish z3 */
145 ecc_mod_sub (m, z3, DA, z3); /* DA - CB */
146 ecc_mod_sqr (m, z3, z3, tp);
147 ecc_mod_mul (m, z3, z3, px, tp);
148 }
149 mpn_cnd_swap (swap, x2, x3, 2*m->size);
150
151 /* Do the low zero bits, just duplicating x2 */
152 for (i = 0; i < bit_low; i++)
153 {
154 ecc_mod_add (m, A, x2, z2);
155 ecc_mod_sub (m, B, x2, z2);
156 ecc_mod_sqr (m, AA, A, tp);
157 ecc_mod_sqr (m, BB, B, tp);
158 ecc_mod_mul (m, x2, AA, BB, tp);
159 ecc_mod_sub (m, E, AA, BB);
160 ecc_mod_addmul_1 (m, AA, E, a24);
161 ecc_mod_mul (m, z2, E, AA, tp);
162 }
163 assert (m->invert_itch <= 7 * m->size);
164 m->invert (m, x3, z2, z3 + m->size);
165 ecc_mod_mul_canonical (m, qx, x2, x3, z3);
166 }
167