Electroneum
curve25519-donna-32bit.h
Go to the documentation of this file.
1 /*
2  Public domain by Andrew M. <liquidsun@gmail.com>
3  See: https://github.com/floodyberry/curve25519-donna
4 
5  32 bit integer curve25519 implementation
6 */
7 
8 typedef uint32_t bignum25519[10];
10 
11 static const uint32_t reduce_mask_25 = (1 << 25) - 1;
12 static const uint32_t reduce_mask_26 = (1 << 26) - 1;
13 
14 
15 /* out = in */
16 DONNA_INLINE static void
17 curve25519_copy(bignum25519 out, const bignum25519 in) {
18  out[0] = in[0];
19  out[1] = in[1];
20  out[2] = in[2];
21  out[3] = in[3];
22  out[4] = in[4];
23  out[5] = in[5];
24  out[6] = in[6];
25  out[7] = in[7];
26  out[8] = in[8];
27  out[9] = in[9];
28 }
29 
30 /* out = a + b */
31 DONNA_INLINE static void
32 curve25519_add(bignum25519 out, const bignum25519 a, const bignum25519 b) {
33  out[0] = a[0] + b[0];
34  out[1] = a[1] + b[1];
35  out[2] = a[2] + b[2];
36  out[3] = a[3] + b[3];
37  out[4] = a[4] + b[4];
38  out[5] = a[5] + b[5];
39  out[6] = a[6] + b[6];
40  out[7] = a[7] + b[7];
41  out[8] = a[8] + b[8];
42  out[9] = a[9] + b[9];
43 }
44 
45 DONNA_INLINE static void
47  uint32_t c;
48  out[0] = a[0] + b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26;
49  out[1] = a[1] + b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25;
50  out[2] = a[2] + b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26;
51  out[3] = a[3] + b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25;
52  out[4] = a[4] + b[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26;
53  out[5] = a[5] + b[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25;
54  out[6] = a[6] + b[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26;
55  out[7] = a[7] + b[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25;
56  out[8] = a[8] + b[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26;
57  out[9] = a[9] + b[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25;
58  out[0] += 19 * c;
59 }
60 
61 DONNA_INLINE static void
62 curve25519_add_reduce(bignum25519 out, const bignum25519 a, const bignum25519 b) {
63  uint32_t c;
64  out[0] = a[0] + b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26;
65  out[1] = a[1] + b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25;
66  out[2] = a[2] + b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26;
67  out[3] = a[3] + b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25;
68  out[4] = a[4] + b[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26;
69  out[5] = a[5] + b[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25;
70  out[6] = a[6] + b[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26;
71  out[7] = a[7] + b[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25;
72  out[8] = a[8] + b[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26;
73  out[9] = a[9] + b[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25;
74  out[0] += 19 * c;
75 }
76 
77 /* multiples of p */
78 static const uint32_t twoP0 = 0x07ffffda;
79 static const uint32_t twoP13579 = 0x03fffffe;
80 static const uint32_t twoP2468 = 0x07fffffe;
81 static const uint32_t fourP0 = 0x0fffffb4;
82 static const uint32_t fourP13579 = 0x07fffffc;
83 static const uint32_t fourP2468 = 0x0ffffffc;
84 
85 /* out = a - b */
86 DONNA_INLINE static void
87 curve25519_sub(bignum25519 out, const bignum25519 a, const bignum25519 b) {
88  uint32_t c;
89  out[0] = twoP0 + a[0] - b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26;
90  out[1] = twoP13579 + a[1] - b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25;
91  out[2] = twoP2468 + a[2] - b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26;
92  out[3] = twoP13579 + a[3] - b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25;
93  out[4] = twoP2468 + a[4] - b[4] + c;
94  out[5] = twoP13579 + a[5] - b[5] ;
95  out[6] = twoP2468 + a[6] - b[6] ;
96  out[7] = twoP13579 + a[7] - b[7] ;
97  out[8] = twoP2468 + a[8] - b[8] ;
98  out[9] = twoP13579 + a[9] - b[9] ;
99 }
100 
101 /* out = a - b, where a is the result of a basic op (add,sub) */
102 DONNA_INLINE static void
103 curve25519_sub_after_basic(bignum25519 out, const bignum25519 a, const bignum25519 b) {
104  uint32_t c;
105  out[0] = fourP0 + a[0] - b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26;
106  out[1] = fourP13579 + a[1] - b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25;
107  out[2] = fourP2468 + a[2] - b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26;
108  out[3] = fourP13579 + a[3] - b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25;
109  out[4] = fourP2468 + a[4] - b[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26;
110  out[5] = fourP13579 + a[5] - b[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25;
111  out[6] = fourP2468 + a[6] - b[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26;
112  out[7] = fourP13579 + a[7] - b[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25;
113  out[8] = fourP2468 + a[8] - b[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26;
114  out[9] = fourP13579 + a[9] - b[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25;
115  out[0] += 19 * c;
116 }
117 
118 DONNA_INLINE static void
119 curve25519_sub_reduce(bignum25519 out, const bignum25519 a, const bignum25519 b) {
120  uint32_t c;
121  out[0] = fourP0 + a[0] - b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26;
122  out[1] = fourP13579 + a[1] - b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25;
123  out[2] = fourP2468 + a[2] - b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26;
124  out[3] = fourP13579 + a[3] - b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25;
125  out[4] = fourP2468 + a[4] - b[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26;
126  out[5] = fourP13579 + a[5] - b[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25;
127  out[6] = fourP2468 + a[6] - b[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26;
128  out[7] = fourP13579 + a[7] - b[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25;
129  out[8] = fourP2468 + a[8] - b[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26;
130  out[9] = fourP13579 + a[9] - b[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25;
131  out[0] += 19 * c;
132 }
133 
134 /* out = -a */
135 DONNA_INLINE static void
136 curve25519_neg(bignum25519 out, const bignum25519 a) {
137  uint32_t c;
138  out[0] = twoP0 - a[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26;
139  out[1] = twoP13579 - a[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25;
140  out[2] = twoP2468 - a[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26;
141  out[3] = twoP13579 - a[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25;
142  out[4] = twoP2468 - a[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26;
143  out[5] = twoP13579 - a[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25;
144  out[6] = twoP2468 - a[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26;
145  out[7] = twoP13579 - a[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25;
146  out[8] = twoP2468 - a[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26;
147  out[9] = twoP13579 - a[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25;
148  out[0] += 19 * c;
149 }
150 
151 /* out = a * b */
152 #define curve25519_mul_noinline curve25519_mul
153 static void
154 curve25519_mul(bignum25519 out, const bignum25519 a, const bignum25519 b) {
155  uint32_t r0,r1,r2,r3,r4,r5,r6,r7,r8,r9;
156  uint32_t s0,s1,s2,s3,s4,s5,s6,s7,s8,s9;
157  uint64_t m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,c;
158  uint32_t p;
159 
160  r0 = b[0];
161  r1 = b[1];
162  r2 = b[2];
163  r3 = b[3];
164  r4 = b[4];
165  r5 = b[5];
166  r6 = b[6];
167  r7 = b[7];
168  r8 = b[8];
169  r9 = b[9];
170 
171  s0 = a[0];
172  s1 = a[1];
173  s2 = a[2];
174  s3 = a[3];
175  s4 = a[4];
176  s5 = a[5];
177  s6 = a[6];
178  s7 = a[7];
179  s8 = a[8];
180  s9 = a[9];
181 
182  m1 = mul32x32_64(r0, s1) + mul32x32_64(r1, s0);
183  m3 = mul32x32_64(r0, s3) + mul32x32_64(r1, s2) + mul32x32_64(r2, s1) + mul32x32_64(r3, s0);
184  m5 = mul32x32_64(r0, s5) + mul32x32_64(r1, s4) + mul32x32_64(r2, s3) + mul32x32_64(r3, s2) + mul32x32_64(r4, s1) + mul32x32_64(r5, s0);
185  m7 = mul32x32_64(r0, s7) + mul32x32_64(r1, s6) + mul32x32_64(r2, s5) + mul32x32_64(r3, s4) + mul32x32_64(r4, s3) + mul32x32_64(r5, s2) + mul32x32_64(r6, s1) + mul32x32_64(r7, s0);
186  m9 = mul32x32_64(r0, s9) + mul32x32_64(r1, s8) + mul32x32_64(r2, s7) + mul32x32_64(r3, s6) + mul32x32_64(r4, s5) + mul32x32_64(r5, s4) + mul32x32_64(r6, s3) + mul32x32_64(r7, s2) + mul32x32_64(r8, s1) + mul32x32_64(r9, s0);
187 
188  r1 *= 2;
189  r3 *= 2;
190  r5 *= 2;
191  r7 *= 2;
192 
193  m0 = mul32x32_64(r0, s0);
194  m2 = mul32x32_64(r0, s2) + mul32x32_64(r1, s1) + mul32x32_64(r2, s0);
195  m4 = mul32x32_64(r0, s4) + mul32x32_64(r1, s3) + mul32x32_64(r2, s2) + mul32x32_64(r3, s1) + mul32x32_64(r4, s0);
196  m6 = mul32x32_64(r0, s6) + mul32x32_64(r1, s5) + mul32x32_64(r2, s4) + mul32x32_64(r3, s3) + mul32x32_64(r4, s2) + mul32x32_64(r5, s1) + mul32x32_64(r6, s0);
197  m8 = mul32x32_64(r0, s8) + mul32x32_64(r1, s7) + mul32x32_64(r2, s6) + mul32x32_64(r3, s5) + mul32x32_64(r4, s4) + mul32x32_64(r5, s3) + mul32x32_64(r6, s2) + mul32x32_64(r7, s1) + mul32x32_64(r8, s0);
198 
199  r1 *= 19;
200  r2 *= 19;
201  r3 = (r3 / 2) * 19;
202  r4 *= 19;
203  r5 = (r5 / 2) * 19;
204  r6 *= 19;
205  r7 = (r7 / 2) * 19;
206  r8 *= 19;
207  r9 *= 19;
208 
209  m1 += (mul32x32_64(r9, s2) + mul32x32_64(r8, s3) + mul32x32_64(r7, s4) + mul32x32_64(r6, s5) + mul32x32_64(r5, s6) + mul32x32_64(r4, s7) + mul32x32_64(r3, s8) + mul32x32_64(r2, s9));
210  m3 += (mul32x32_64(r9, s4) + mul32x32_64(r8, s5) + mul32x32_64(r7, s6) + mul32x32_64(r6, s7) + mul32x32_64(r5, s8) + mul32x32_64(r4, s9));
211  m5 += (mul32x32_64(r9, s6) + mul32x32_64(r8, s7) + mul32x32_64(r7, s8) + mul32x32_64(r6, s9));
212  m7 += (mul32x32_64(r9, s8) + mul32x32_64(r8, s9));
213 
214  r3 *= 2;
215  r5 *= 2;
216  r7 *= 2;
217  r9 *= 2;
218 
219  m0 += (mul32x32_64(r9, s1) + mul32x32_64(r8, s2) + mul32x32_64(r7, s3) + mul32x32_64(r6, s4) + mul32x32_64(r5, s5) + mul32x32_64(r4, s6) + mul32x32_64(r3, s7) + mul32x32_64(r2, s8) + mul32x32_64(r1, s9));
220  m2 += (mul32x32_64(r9, s3) + mul32x32_64(r8, s4) + mul32x32_64(r7, s5) + mul32x32_64(r6, s6) + mul32x32_64(r5, s7) + mul32x32_64(r4, s8) + mul32x32_64(r3, s9));
221  m4 += (mul32x32_64(r9, s5) + mul32x32_64(r8, s6) + mul32x32_64(r7, s7) + mul32x32_64(r6, s8) + mul32x32_64(r5, s9));
222  m6 += (mul32x32_64(r9, s7) + mul32x32_64(r8, s8) + mul32x32_64(r7, s9));
223  m8 += (mul32x32_64(r9, s9));
224 
225  r0 = (uint32_t)m0 & reduce_mask_26; c = (m0 >> 26);
226  m1 += c; r1 = (uint32_t)m1 & reduce_mask_25; c = (m1 >> 25);
227  m2 += c; r2 = (uint32_t)m2 & reduce_mask_26; c = (m2 >> 26);
228  m3 += c; r3 = (uint32_t)m3 & reduce_mask_25; c = (m3 >> 25);
229  m4 += c; r4 = (uint32_t)m4 & reduce_mask_26; c = (m4 >> 26);
230  m5 += c; r5 = (uint32_t)m5 & reduce_mask_25; c = (m5 >> 25);
231  m6 += c; r6 = (uint32_t)m6 & reduce_mask_26; c = (m6 >> 26);
232  m7 += c; r7 = (uint32_t)m7 & reduce_mask_25; c = (m7 >> 25);
233  m8 += c; r8 = (uint32_t)m8 & reduce_mask_26; c = (m8 >> 26);
234  m9 += c; r9 = (uint32_t)m9 & reduce_mask_25; p = (uint32_t)(m9 >> 25);
235  m0 = r0 + mul32x32_64(p,19); r0 = (uint32_t)m0 & reduce_mask_26; p = (uint32_t)(m0 >> 26);
236  r1 += p;
237 
238  out[0] = r0;
239  out[1] = r1;
240  out[2] = r2;
241  out[3] = r3;
242  out[4] = r4;
243  out[5] = r5;
244  out[6] = r6;
245  out[7] = r7;
246  out[8] = r8;
247  out[9] = r9;
248 }
249 
250 /* out = in*in */
251 static void
253  uint32_t r0,r1,r2,r3,r4,r5,r6,r7,r8,r9;
254  uint32_t d6,d7,d8,d9;
255  uint64_t m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,c;
256  uint32_t p;
257 
258  r0 = in[0];
259  r1 = in[1];
260  r2 = in[2];
261  r3 = in[3];
262  r4 = in[4];
263  r5 = in[5];
264  r6 = in[6];
265  r7 = in[7];
266  r8 = in[8];
267  r9 = in[9];
268 
269  m0 = mul32x32_64(r0, r0);
270  r0 *= 2;
271  m1 = mul32x32_64(r0, r1);
272  m2 = mul32x32_64(r0, r2) + mul32x32_64(r1, r1 * 2);
273  r1 *= 2;
274  m3 = mul32x32_64(r0, r3) + mul32x32_64(r1, r2 );
275  m4 = mul32x32_64(r0, r4) + mul32x32_64(r1, r3 * 2) + mul32x32_64(r2, r2);
276  r2 *= 2;
277  m5 = mul32x32_64(r0, r5) + mul32x32_64(r1, r4 ) + mul32x32_64(r2, r3);
278  m6 = mul32x32_64(r0, r6) + mul32x32_64(r1, r5 * 2) + mul32x32_64(r2, r4) + mul32x32_64(r3, r3 * 2);
279  r3 *= 2;
280  m7 = mul32x32_64(r0, r7) + mul32x32_64(r1, r6 ) + mul32x32_64(r2, r5) + mul32x32_64(r3, r4 );
281  m8 = mul32x32_64(r0, r8) + mul32x32_64(r1, r7 * 2) + mul32x32_64(r2, r6) + mul32x32_64(r3, r5 * 2) + mul32x32_64(r4, r4 );
282  m9 = mul32x32_64(r0, r9) + mul32x32_64(r1, r8 ) + mul32x32_64(r2, r7) + mul32x32_64(r3, r6 ) + mul32x32_64(r4, r5 * 2);
283 
284  d6 = r6 * 19;
285  d7 = r7 * 2 * 19;
286  d8 = r8 * 19;
287  d9 = r9 * 2 * 19;
288 
289  m0 += (mul32x32_64(d9, r1 ) + mul32x32_64(d8, r2 ) + mul32x32_64(d7, r3 ) + mul32x32_64(d6, r4 * 2) + mul32x32_64(r5, r5 * 2 * 19));
290  m1 += (mul32x32_64(d9, r2 / 2) + mul32x32_64(d8, r3 ) + mul32x32_64(d7, r4 ) + mul32x32_64(d6, r5 * 2));
291  m2 += (mul32x32_64(d9, r3 ) + mul32x32_64(d8, r4 * 2) + mul32x32_64(d7, r5 * 2) + mul32x32_64(d6, r6 ));
292  m3 += (mul32x32_64(d9, r4 ) + mul32x32_64(d8, r5 * 2) + mul32x32_64(d7, r6 ));
293  m4 += (mul32x32_64(d9, r5 * 2) + mul32x32_64(d8, r6 * 2) + mul32x32_64(d7, r7 ));
294  m5 += (mul32x32_64(d9, r6 ) + mul32x32_64(d8, r7 * 2));
295  m6 += (mul32x32_64(d9, r7 * 2) + mul32x32_64(d8, r8 ));
296  m7 += (mul32x32_64(d9, r8 ));
297  m8 += (mul32x32_64(d9, r9 ));
298 
299  r0 = (uint32_t)m0 & reduce_mask_26; c = (m0 >> 26);
300  m1 += c; r1 = (uint32_t)m1 & reduce_mask_25; c = (m1 >> 25);
301  m2 += c; r2 = (uint32_t)m2 & reduce_mask_26; c = (m2 >> 26);
302  m3 += c; r3 = (uint32_t)m3 & reduce_mask_25; c = (m3 >> 25);
303  m4 += c; r4 = (uint32_t)m4 & reduce_mask_26; c = (m4 >> 26);
304  m5 += c; r5 = (uint32_t)m5 & reduce_mask_25; c = (m5 >> 25);
305  m6 += c; r6 = (uint32_t)m6 & reduce_mask_26; c = (m6 >> 26);
306  m7 += c; r7 = (uint32_t)m7 & reduce_mask_25; c = (m7 >> 25);
307  m8 += c; r8 = (uint32_t)m8 & reduce_mask_26; c = (m8 >> 26);
308  m9 += c; r9 = (uint32_t)m9 & reduce_mask_25; p = (uint32_t)(m9 >> 25);
309  m0 = r0 + mul32x32_64(p,19); r0 = (uint32_t)m0 & reduce_mask_26; p = (uint32_t)(m0 >> 26);
310  r1 += p;
311 
312  out[0] = r0;
313  out[1] = r1;
314  out[2] = r2;
315  out[3] = r3;
316  out[4] = r4;
317  out[5] = r5;
318  out[6] = r6;
319  out[7] = r7;
320  out[8] = r8;
321  out[9] = r9;
322 }
323 
324 
325 /* out = in ^ (2 * count) */
326 static void
327 curve25519_square_times(bignum25519 out, const bignum25519 in, int count) {
328  uint32_t r0,r1,r2,r3,r4,r5,r6,r7,r8,r9;
329  uint32_t d6,d7,d8,d9;
330  uint64_t m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,c;
331  uint32_t p;
332 
333  r0 = in[0];
334  r1 = in[1];
335  r2 = in[2];
336  r3 = in[3];
337  r4 = in[4];
338  r5 = in[5];
339  r6 = in[6];
340  r7 = in[7];
341  r8 = in[8];
342  r9 = in[9];
343 
344  do {
345  m0 = mul32x32_64(r0, r0);
346  r0 *= 2;
347  m1 = mul32x32_64(r0, r1);
348  m2 = mul32x32_64(r0, r2) + mul32x32_64(r1, r1 * 2);
349  r1 *= 2;
350  m3 = mul32x32_64(r0, r3) + mul32x32_64(r1, r2 );
351  m4 = mul32x32_64(r0, r4) + mul32x32_64(r1, r3 * 2) + mul32x32_64(r2, r2);
352  r2 *= 2;
353  m5 = mul32x32_64(r0, r5) + mul32x32_64(r1, r4 ) + mul32x32_64(r2, r3);
354  m6 = mul32x32_64(r0, r6) + mul32x32_64(r1, r5 * 2) + mul32x32_64(r2, r4) + mul32x32_64(r3, r3 * 2);
355  r3 *= 2;
356  m7 = mul32x32_64(r0, r7) + mul32x32_64(r1, r6 ) + mul32x32_64(r2, r5) + mul32x32_64(r3, r4 );
357  m8 = mul32x32_64(r0, r8) + mul32x32_64(r1, r7 * 2) + mul32x32_64(r2, r6) + mul32x32_64(r3, r5 * 2) + mul32x32_64(r4, r4 );
358  m9 = mul32x32_64(r0, r9) + mul32x32_64(r1, r8 ) + mul32x32_64(r2, r7) + mul32x32_64(r3, r6 ) + mul32x32_64(r4, r5 * 2);
359 
360  d6 = r6 * 19;
361  d7 = r7 * 2 * 19;
362  d8 = r8 * 19;
363  d9 = r9 * 2 * 19;
364 
365  m0 += (mul32x32_64(d9, r1 ) + mul32x32_64(d8, r2 ) + mul32x32_64(d7, r3 ) + mul32x32_64(d6, r4 * 2) + mul32x32_64(r5, r5 * 2 * 19));
366  m1 += (mul32x32_64(d9, r2 / 2) + mul32x32_64(d8, r3 ) + mul32x32_64(d7, r4 ) + mul32x32_64(d6, r5 * 2));
367  m2 += (mul32x32_64(d9, r3 ) + mul32x32_64(d8, r4 * 2) + mul32x32_64(d7, r5 * 2) + mul32x32_64(d6, r6 ));
368  m3 += (mul32x32_64(d9, r4 ) + mul32x32_64(d8, r5 * 2) + mul32x32_64(d7, r6 ));
369  m4 += (mul32x32_64(d9, r5 * 2) + mul32x32_64(d8, r6 * 2) + mul32x32_64(d7, r7 ));
370  m5 += (mul32x32_64(d9, r6 ) + mul32x32_64(d8, r7 * 2));
371  m6 += (mul32x32_64(d9, r7 * 2) + mul32x32_64(d8, r8 ));
372  m7 += (mul32x32_64(d9, r8 ));
373  m8 += (mul32x32_64(d9, r9 ));
374 
375  r0 = (uint32_t)m0 & reduce_mask_26; c = (m0 >> 26);
376  m1 += c; r1 = (uint32_t)m1 & reduce_mask_25; c = (m1 >> 25);
377  m2 += c; r2 = (uint32_t)m2 & reduce_mask_26; c = (m2 >> 26);
378  m3 += c; r3 = (uint32_t)m3 & reduce_mask_25; c = (m3 >> 25);
379  m4 += c; r4 = (uint32_t)m4 & reduce_mask_26; c = (m4 >> 26);
380  m5 += c; r5 = (uint32_t)m5 & reduce_mask_25; c = (m5 >> 25);
381  m6 += c; r6 = (uint32_t)m6 & reduce_mask_26; c = (m6 >> 26);
382  m7 += c; r7 = (uint32_t)m7 & reduce_mask_25; c = (m7 >> 25);
383  m8 += c; r8 = (uint32_t)m8 & reduce_mask_26; c = (m8 >> 26);
384  m9 += c; r9 = (uint32_t)m9 & reduce_mask_25; p = (uint32_t)(m9 >> 25);
385  m0 = r0 + mul32x32_64(p,19); r0 = (uint32_t)m0 & reduce_mask_26; p = (uint32_t)(m0 >> 26);
386  r1 += p;
387  } while (--count);
388 
389  out[0] = r0;
390  out[1] = r1;
391  out[2] = r2;
392  out[3] = r3;
393  out[4] = r4;
394  out[5] = r5;
395  out[6] = r6;
396  out[7] = r7;
397  out[8] = r8;
398  out[9] = r9;
399 }
400 
401 /* Take a little-endian, 32-byte number and expand it into polynomial form */
402 static void
403 curve25519_expand(bignum25519 out, const unsigned char in[32]) {
404  static const union { uint8_t b[2]; uint16_t s; } endian_check = {{1,0}};
405  uint32_t x0,x1,x2,x3,x4,x5,x6,x7;
406 
407  if (endian_check.s == 1) {
408  x0 = *(uint32_t *)(in + 0);
409  x1 = *(uint32_t *)(in + 4);
410  x2 = *(uint32_t *)(in + 8);
411  x3 = *(uint32_t *)(in + 12);
412  x4 = *(uint32_t *)(in + 16);
413  x5 = *(uint32_t *)(in + 20);
414  x6 = *(uint32_t *)(in + 24);
415  x7 = *(uint32_t *)(in + 28);
416  } else {
417  #define F(s) \
418  ((((uint32_t)in[s + 0]) ) | \
419  (((uint32_t)in[s + 1]) << 8) | \
420  (((uint32_t)in[s + 2]) << 16) | \
421  (((uint32_t)in[s + 3]) << 24))
422  x0 = F(0);
423  x1 = F(4);
424  x2 = F(8);
425  x3 = F(12);
426  x4 = F(16);
427  x5 = F(20);
428  x6 = F(24);
429  x7 = F(28);
430  #undef F
431  }
432 
433  out[0] = ( x0 ) & 0x3ffffff;
434  out[1] = ((((uint64_t)x1 << 32) | x0) >> 26) & 0x1ffffff;
435  out[2] = ((((uint64_t)x2 << 32) | x1) >> 19) & 0x3ffffff;
436  out[3] = ((((uint64_t)x3 << 32) | x2) >> 13) & 0x1ffffff;
437  out[4] = (( x3) >> 6) & 0x3ffffff;
438  out[5] = ( x4 ) & 0x1ffffff;
439  out[6] = ((((uint64_t)x5 << 32) | x4) >> 25) & 0x3ffffff;
440  out[7] = ((((uint64_t)x6 << 32) | x5) >> 19) & 0x1ffffff;
441  out[8] = ((((uint64_t)x7 << 32) | x6) >> 12) & 0x3ffffff;
442  out[9] = (( x7) >> 6) & 0x1ffffff;
443 }
444 
445 /* Take a fully reduced polynomial form number and contract it into a
446  * little-endian, 32-byte array
447  */
448 static void
449 curve25519_contract(unsigned char out[32], const bignum25519 in) {
450  bignum25519 f;
451  curve25519_copy(f, in);
452 
453  #define carry_pass() \
454  f[1] += f[0] >> 26; f[0] &= reduce_mask_26; \
455  f[2] += f[1] >> 25; f[1] &= reduce_mask_25; \
456  f[3] += f[2] >> 26; f[2] &= reduce_mask_26; \
457  f[4] += f[3] >> 25; f[3] &= reduce_mask_25; \
458  f[5] += f[4] >> 26; f[4] &= reduce_mask_26; \
459  f[6] += f[5] >> 25; f[5] &= reduce_mask_25; \
460  f[7] += f[6] >> 26; f[6] &= reduce_mask_26; \
461  f[8] += f[7] >> 25; f[7] &= reduce_mask_25; \
462  f[9] += f[8] >> 26; f[8] &= reduce_mask_26;
463 
464  #define carry_pass_full() \
465  carry_pass() \
466  f[0] += 19 * (f[9] >> 25); f[9] &= reduce_mask_25;
467 
468  #define carry_pass_final() \
469  carry_pass() \
470  f[9] &= reduce_mask_25;
471 
474 
475  /* now t is between 0 and 2^255-1, properly carried. */
476  /* case 1: between 0 and 2^255-20. case 2: between 2^255-19 and 2^255-1. */
477  f[0] += 19;
479 
480  /* now between 19 and 2^255-1 in both cases, and offset by 19. */
481  f[0] += (reduce_mask_26 + 1) - 19;
482  f[1] += (reduce_mask_25 + 1) - 1;
483  f[2] += (reduce_mask_26 + 1) - 1;
484  f[3] += (reduce_mask_25 + 1) - 1;
485  f[4] += (reduce_mask_26 + 1) - 1;
486  f[5] += (reduce_mask_25 + 1) - 1;
487  f[6] += (reduce_mask_26 + 1) - 1;
488  f[7] += (reduce_mask_25 + 1) - 1;
489  f[8] += (reduce_mask_26 + 1) - 1;
490  f[9] += (reduce_mask_25 + 1) - 1;
491 
492  /* now between 2^255 and 2^256-20, and offset by 2^255. */
494 
495  #undef carry_pass
496  #undef carry_full
497  #undef carry_final
498 
499  f[1] <<= 2;
500  f[2] <<= 3;
501  f[3] <<= 5;
502  f[4] <<= 6;
503  f[6] <<= 1;
504  f[7] <<= 3;
505  f[8] <<= 4;
506  f[9] <<= 6;
507 
508  #define F(i, s) \
509  out[s+0] |= (unsigned char )(f[i] & 0xff); \
510  out[s+1] = (unsigned char )((f[i] >> 8) & 0xff); \
511  out[s+2] = (unsigned char )((f[i] >> 16) & 0xff); \
512  out[s+3] = (unsigned char )((f[i] >> 24) & 0xff);
513 
514  out[0] = 0;
515  out[16] = 0;
516  F(0,0);
517  F(1,3);
518  F(2,6);
519  F(3,9);
520  F(4,12);
521  F(5,16);
522  F(6,19);
523  F(7,22);
524  F(8,25);
525  F(9,28);
526  #undef F
527 }
528 
529 
530 /* out = (flag) ? in : out */
531 DONNA_INLINE static void
532 curve25519_move_conditional_bytes(uint8_t out[96], const uint8_t in[96], uint32_t flag) {
533  const uint32_t nb = flag - 1, b = ~nb;
534  const uint32_t *inl = (const uint32_t *)in;
535  uint32_t *outl = (uint32_t *)out;
536  outl[0] = (outl[0] & nb) | (inl[0] & b);
537  outl[1] = (outl[1] & nb) | (inl[1] & b);
538  outl[2] = (outl[2] & nb) | (inl[2] & b);
539  outl[3] = (outl[3] & nb) | (inl[3] & b);
540  outl[4] = (outl[4] & nb) | (inl[4] & b);
541  outl[5] = (outl[5] & nb) | (inl[5] & b);
542  outl[6] = (outl[6] & nb) | (inl[6] & b);
543  outl[7] = (outl[7] & nb) | (inl[7] & b);
544  outl[8] = (outl[8] & nb) | (inl[8] & b);
545  outl[9] = (outl[9] & nb) | (inl[9] & b);
546  outl[10] = (outl[10] & nb) | (inl[10] & b);
547  outl[11] = (outl[11] & nb) | (inl[11] & b);
548  outl[12] = (outl[12] & nb) | (inl[12] & b);
549  outl[13] = (outl[13] & nb) | (inl[13] & b);
550  outl[14] = (outl[14] & nb) | (inl[14] & b);
551  outl[15] = (outl[15] & nb) | (inl[15] & b);
552  outl[16] = (outl[16] & nb) | (inl[16] & b);
553  outl[17] = (outl[17] & nb) | (inl[17] & b);
554  outl[18] = (outl[18] & nb) | (inl[18] & b);
555  outl[19] = (outl[19] & nb) | (inl[19] & b);
556  outl[20] = (outl[20] & nb) | (inl[20] & b);
557  outl[21] = (outl[21] & nb) | (inl[21] & b);
558  outl[22] = (outl[22] & nb) | (inl[22] & b);
559  outl[23] = (outl[23] & nb) | (inl[23] & b);
560 
561 }
562 
563 /* if (iswap) swap(a, b) */
564 DONNA_INLINE static void
565 curve25519_swap_conditional(bignum25519 a, bignum25519 b, uint32_t iswap) {
566  const uint32_t swap = (uint32_t)(-(int32_t)iswap);
567  uint32_t x0,x1,x2,x3,x4,x5,x6,x7,x8,x9;
568 
569  x0 = swap & (a[0] ^ b[0]); a[0] ^= x0; b[0] ^= x0;
570  x1 = swap & (a[1] ^ b[1]); a[1] ^= x1; b[1] ^= x1;
571  x2 = swap & (a[2] ^ b[2]); a[2] ^= x2; b[2] ^= x2;
572  x3 = swap & (a[3] ^ b[3]); a[3] ^= x3; b[3] ^= x3;
573  x4 = swap & (a[4] ^ b[4]); a[4] ^= x4; b[4] ^= x4;
574  x5 = swap & (a[5] ^ b[5]); a[5] ^= x5; b[5] ^= x5;
575  x6 = swap & (a[6] ^ b[6]); a[6] ^= x6; b[6] ^= x6;
576  x7 = swap & (a[7] ^ b[7]); a[7] ^= x7; b[7] ^= x7;
577  x8 = swap & (a[8] ^ b[8]); a[8] ^= x8; b[8] ^= x8;
578  x9 = swap & (a[9] ^ b[9]); a[9] ^= x9; b[9] ^= x9;
579 }
#define curve25519_square(r, n)
unsigned short uint16_t
Definition: stdint.h:125
#define curve25519_add_after_basic
#define mul32x32_64(a, b)
#define DONNA_INLINE
unsigned char uint8_t
Definition: stdint.h:124
uint32_t bignum25519[10]
mdb_size_t count(MDB_cursor *cur)
unsigned int uint32_t
Definition: stdint.h:126
unsigned __int64 uint64_t
Definition: stdint.h:136
#define carry_pass_final()
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
uint32_t bignum25519align16[12]
#define carry_pass_full()
#define F(s)
signed int int32_t
Definition: stdint.h:123