Branch data Line data Source code
1 : : /* Arithmetic in prime fields
2 : : * Daniel Beer <dlbeer@gmail.com>, 10 Jan 2014
3 : : *
4 : : * This file is in the public domain.
5 : : */
6 : :
7 : : #include "fprime.h"
8 : :
9 : : #ifndef COMPACT_DISABLE_ED25519
10 : : #ifdef FULL_C25519_CODE
11 : : const uint8_t fprime_zero[FPRIME_SIZE] = {0};
12 : : const uint8_t fprime_one[FPRIME_SIZE] = {1};
13 : : #endif
14 : :
15 : 508 : static void raw_add(uint8_t *x, const uint8_t *p)
16 : : {
17 : 508 : uint16_t c = 0;
18 : 508 : int i;
19 : :
20 [ + + ]: 16764 : for (i = 0; i < FPRIME_SIZE; i++) {
21 : 16256 : c += ((uint16_t)x[i]) + ((uint16_t)p[i]);
22 : 16256 : x[i] = c;
23 : 16256 : c >>= 8;
24 : : }
25 : 508 : }
26 : :
27 : 2590 : static void raw_try_sub(uint8_t *x, const uint8_t *p)
28 : : {
29 : 2590 : uint8_t minusp[FPRIME_SIZE];
30 : 2590 : uint16_t c = 0;
31 : 2590 : int i;
32 : :
33 [ + + ]: 85470 : for (i = 0; i < FPRIME_SIZE; i++) {
34 : 82880 : c = ((uint16_t)x[i]) - ((uint16_t)p[i]) - c;
35 : 82880 : minusp[i] = c;
36 : 82880 : c = (c >> 8) & 1;
37 : : }
38 : :
39 : 2590 : fprime_select(x, minusp, x, c);
40 : 2590 : }
41 : :
42 : : /* Warning: this function is variable-time */
43 : 10 : static int prime_msb(const uint8_t *p)
44 : : {
45 : 10 : int i;
46 : 10 : uint8_t x;
47 : :
48 [ + - ]: 10 : for (i = FPRIME_SIZE - 1; i >= 0; i--)
49 [ - + ]: 10 : if (p[i])
50 : : break;
51 : :
52 : 10 : x = p[i];
53 : 10 : i <<= 3;
54 : :
55 [ + + ]: 60 : while (x) {
56 : 50 : x >>= 1;
57 : 50 : i++;
58 : : }
59 : :
60 : 10 : return i - 1;
61 : : }
62 : :
63 : : /* Warning: this function may be variable-time in the argument n */
64 : 2090 : static void shift_n_bits(uint8_t *x, int n)
65 : : {
66 : 2090 : uint16_t c = 0;
67 : 2090 : int i;
68 : :
69 [ + + ]: 68970 : for (i = 0; i < FPRIME_SIZE; i++) {
70 : 66880 : c |= ((uint16_t)x[i]) << n;
71 : 66880 : x[i] = c;
72 : 66880 : c >>= 8;
73 : : }
74 : 2090 : }
75 : :
76 : : #ifdef FULL_C25519_CODE
77 : : void fprime_load(uint8_t *x, uint32_t c)
78 : : {
79 : : unsigned int i;
80 : :
81 : : for (i = 0; i < sizeof(c); i++) {
82 : : x[i] = c;
83 : : c >>= 8;
84 : : }
85 : :
86 : : for (; i < FPRIME_SIZE; i++)
87 : : x[i] = 0;
88 : : }
89 : : #endif
90 : :
91 : 8 : static inline int min_int(int a, int b)
92 : : {
93 : 8 : return a < b ? a : b;
94 : : }
95 : :
96 : 8 : void fprime_from_bytes(uint8_t *n,
97 : : const uint8_t *x, size_t len,
98 : : const uint8_t *modulus)
99 : : {
100 : 8 : const int preload_total = min_int(prime_msb(modulus) - 1, len << 3);
101 : 8 : const int preload_bytes = preload_total >> 3;
102 : 8 : const int preload_bits = preload_total & 7;
103 : 8 : const int rbits = (len << 3) - preload_total;
104 : 8 : int i;
105 : :
106 : 8 : memset(n, 0, FPRIME_SIZE);
107 : :
108 [ + + ]: 256 : for (i = 0; i < preload_bytes; i++)
109 : 248 : n[i] = x[len - preload_bytes + i];
110 : :
111 [ + - ]: 8 : if (preload_bits) {
112 : 8 : shift_n_bits(n, preload_bits);
113 : 8 : n[0] |= x[len - preload_bytes - 1] >> (8 - preload_bits);
114 : : }
115 : :
116 [ + + ]: 1584 : for (i = rbits - 1; i >= 0; i--) {
117 : 1576 : const uint8_t bit = (x[i >> 3] >> (i & 7)) & 1;
118 : :
119 : 1576 : shift_n_bits(n, 1);
120 : 1576 : n[0] |= bit;
121 : 1576 : raw_try_sub(n, modulus);
122 : : }
123 : 8 : }
124 : :
125 : : #ifdef FULL_C25519_CODE
126 : : void fprime_normalize(uint8_t *x, const uint8_t *modulus)
127 : : {
128 : : uint8_t n[FPRIME_SIZE];
129 : :
130 : : fprime_from_bytes(n, x, FPRIME_SIZE, modulus);
131 : : fprime_copy(x, n);
132 : : }
133 : :
134 : : uint8_t fprime_eq(const uint8_t *x, const uint8_t *y)
135 : : {
136 : : uint8_t sum = 0;
137 : : int i;
138 : :
139 : : for (i = 0; i < FPRIME_SIZE; i++)
140 : : sum |= x[i] ^ y[i];
141 : :
142 : : sum |= (sum >> 4);
143 : : sum |= (sum >> 2);
144 : : sum |= (sum >> 1);
145 : :
146 : : return (sum ^ 1) & 1;
147 : : }
148 : : #endif
149 : 3096 : void fprime_select(uint8_t *dst,
150 : : const uint8_t *zero, const uint8_t *one,
151 : : uint8_t condition)
152 : : {
153 : 3096 : const uint8_t mask = -condition;
154 : 3096 : int i;
155 : :
156 [ + + ]: 102168 : for (i = 0; i < FPRIME_SIZE; i++)
157 : 99072 : dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
158 : 3096 : }
159 : :
160 : 508 : void fprime_add(uint8_t *r, const uint8_t *a, const uint8_t *modulus)
161 : : {
162 : 508 : raw_add(r, a);
163 : 508 : raw_try_sub(r, modulus);
164 : 508 : }
165 : :
166 : : #ifdef FULL_C25519_CODE
167 : : void fprime_sub(uint8_t *r, const uint8_t *a, const uint8_t *modulus)
168 : : {
169 : : raw_add(r, modulus);
170 : : raw_try_sub(r, a);
171 : : raw_try_sub(r, modulus);
172 : : }
173 : : #endif
174 : :
175 : 2 : void fprime_mul(uint8_t *r, const uint8_t *a, const uint8_t *b,
176 : : const uint8_t *modulus)
177 : : {
178 : 2 : int i;
179 : :
180 : 2 : memset(r, 0, FPRIME_SIZE);
181 : :
182 [ + + ]: 508 : for (i = prime_msb(modulus); i >= 0; i--) {
183 : 506 : const uint8_t bit = (b[i >> 3] >> (i & 7)) & 1;
184 : 506 : uint8_t plusa[FPRIME_SIZE];
185 : :
186 : 506 : shift_n_bits(r, 1);
187 : 506 : raw_try_sub(r, modulus);
188 : :
189 : 506 : fprime_copy(plusa, r);
190 : 506 : fprime_add(plusa, a, modulus);
191 : :
192 : 506 : fprime_select(r, r, plusa, bit);
193 : : }
194 : 2 : }
195 : :
196 : : #ifdef FULL_C25519_CODE
197 : : void fprime_inv(uint8_t *r, const uint8_t *a, const uint8_t *modulus)
198 : : {
199 : : uint8_t pm2[FPRIME_SIZE];
200 : : uint16_t c = 2;
201 : : int i;
202 : :
203 : : /* Compute (p-2) */
204 : : fprime_copy(pm2, modulus);
205 : : for (i = 0; i < FPRIME_SIZE; i++) {
206 : : c = modulus[i] - c;
207 : : pm2[i] = c;
208 : : c >>= 8;
209 : : }
210 : :
211 : : /* Binary exponentiation */
212 : : fprime_load(r, 1);
213 : :
214 : : for (i = prime_msb(modulus); i >= 0; i--) {
215 : : uint8_t r2[FPRIME_SIZE];
216 : :
217 : : fprime_mul(r2, r, r, modulus);
218 : :
219 : : if ((pm2[i >> 3] >> (i & 7)) & 1)
220 : : fprime_mul(r, r2, a, modulus);
221 : : else
222 : : fprime_copy(r, r2);
223 : : }
224 : : }
225 : : #endif
226 : : #endif
|
