Botan  2.4.0
Crypto and TLS for C++11
sc_reduce.cpp
Go to the documentation of this file.
1 /*
2 * Ed25519
3 * (C) 2017 Ribose Inc
4 *
5 * Based on the public domain code from SUPERCOP ref10 by
6 * Peter Schwabe, Daniel J. Bernstein, Niels Duif, Tanja Lange, Bo-Yin Yang
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 */
10 
11 #include <botan/internal/ed25519_internal.h>
12 
13 namespace Botan {
14 
15 /*
16 Input:
17  s[0]+256*s[1]+...+256^63*s[63] = s
18 
19 Output:
20  s[0]+256*s[1]+...+256^31*s[31] = s mod l
21  where l = 2^252 + 27742317777372353535851937790883648493.
22  Overwrites s in place.
23 */
24 
25 void sc_reduce(uint8_t* s)
26  {
27  const int64_t X20 = (1 << 20);
28  const int64_t X21 = (1 << 21);
29 
30 
31  int64_t s0 = 2097151 & load_3(s);
32  int64_t s1 = 2097151 & (load_4(s + 2) >> 5);
33  int64_t s2 = 2097151 & (load_3(s + 5) >> 2);
34  int64_t s3 = 2097151 & (load_4(s + 7) >> 7);
35  int64_t s4 = 2097151 & (load_4(s + 10) >> 4);
36  int64_t s5 = 2097151 & (load_3(s + 13) >> 1);
37  int64_t s6 = 2097151 & (load_4(s + 15) >> 6);
38  int64_t s7 = 2097151 & (load_3(s + 18) >> 3);
39  int64_t s8 = 2097151 & load_3(s + 21);
40  int64_t s9 = 2097151 & (load_4(s + 23) >> 5);
41  int64_t s10 = 2097151 & (load_3(s + 26) >> 2);
42  int64_t s11 = 2097151 & (load_4(s + 28) >> 7);
43  int64_t s12 = 2097151 & (load_4(s + 31) >> 4);
44  int64_t s13 = 2097151 & (load_3(s + 34) >> 1);
45  int64_t s14 = 2097151 & (load_4(s + 36) >> 6);
46  int64_t s15 = 2097151 & (load_3(s + 39) >> 3);
47  int64_t s16 = 2097151 & load_3(s + 42);
48  int64_t s17 = 2097151 & (load_4(s + 44) >> 5);
49  int64_t s18 = 2097151 & (load_3(s + 47) >> 2);
50  int64_t s19 = 2097151 & (load_4(s + 49) >> 7);
51  int64_t s20 = 2097151 & (load_4(s + 52) >> 4);
52  int64_t s21 = 2097151 & (load_3(s + 55) >> 1);
53  int64_t s22 = 2097151 & (load_4(s + 57) >> 6);
54  int64_t s23 = (load_4(s + 60) >> 3);
55  int64_t carry0;
56  int64_t carry1;
57  int64_t carry2;
58  int64_t carry3;
59  int64_t carry4;
60  int64_t carry5;
61  int64_t carry6;
62  int64_t carry7;
63  int64_t carry8;
64  int64_t carry9;
65  int64_t carry10;
66  int64_t carry11;
67  int64_t carry12;
68  int64_t carry13;
69  int64_t carry14;
70  int64_t carry15;
71  int64_t carry16;
72 
73  s11 += s23 * 666643;
74  s12 += s23 * 470296;
75  s13 += s23 * 654183;
76  s14 -= s23 * 997805;
77  s15 += s23 * 136657;
78  s16 -= s23 * 683901;
79  s23 = 0;
80 
81  s10 += s22 * 666643;
82  s11 += s22 * 470296;
83  s12 += s22 * 654183;
84  s13 -= s22 * 997805;
85  s14 += s22 * 136657;
86  s15 -= s22 * 683901;
87  s22 = 0;
88 
89  s9 += s21 * 666643;
90  s10 += s21 * 470296;
91  s11 += s21 * 654183;
92  s12 -= s21 * 997805;
93  s13 += s21 * 136657;
94  s14 -= s21 * 683901;
95  s21 = 0;
96 
97  s8 += s20 * 666643;
98  s9 += s20 * 470296;
99  s10 += s20 * 654183;
100  s11 -= s20 * 997805;
101  s12 += s20 * 136657;
102  s13 -= s20 * 683901;
103  s20 = 0;
104 
105  s7 += s19 * 666643;
106  s8 += s19 * 470296;
107  s9 += s19 * 654183;
108  s10 -= s19 * 997805;
109  s11 += s19 * 136657;
110  s12 -= s19 * 683901;
111  s19 = 0;
112 
113  s6 += s18 * 666643;
114  s7 += s18 * 470296;
115  s8 += s18 * 654183;
116  s9 -= s18 * 997805;
117  s10 += s18 * 136657;
118  s11 -= s18 * 683901;
119  s18 = 0;
120 
121  carry6 = (s6 + X20) >> 21;
122  s7 += carry6;
123  s6 -= carry6 * X21;
124  carry8 = (s8 + X20) >> 21;
125  s9 += carry8;
126  s8 -= carry8 * X21;
127  carry10 = (s10 + X20) >> 21;
128  s11 += carry10;
129  s10 -= carry10 * X21;
130  carry12 = (s12 + X20) >> 21;
131  s13 += carry12;
132  s12 -= carry12 * X21;
133  carry14 = (s14 + X20) >> 21;
134  s15 += carry14;
135  s14 -= carry14 * X21;
136  carry16 = (s16 + X20) >> 21;
137  s17 += carry16;
138  s16 -= carry16 * X21;
139 
140  carry7 = (s7 + X20) >> 21;
141  s8 += carry7;
142  s7 -= carry7 * X21;
143  carry9 = (s9 + X20) >> 21;
144  s10 += carry9;
145  s9 -= carry9 * X21;
146  carry11 = (s11 + X20) >> 21;
147  s12 += carry11;
148  s11 -= carry11 * X21;
149  carry13 = (s13 + X20) >> 21;
150  s14 += carry13;
151  s13 -= carry13 * X21;
152  carry15 = (s15 + X20) >> 21;
153  s16 += carry15;
154  s15 -= carry15 * X21;
155 
156  s5 += s17 * 666643;
157  s6 += s17 * 470296;
158  s7 += s17 * 654183;
159  s8 -= s17 * 997805;
160  s9 += s17 * 136657;
161  s10 -= s17 * 683901;
162  s17 = 0;
163 
164  s4 += s16 * 666643;
165  s5 += s16 * 470296;
166  s6 += s16 * 654183;
167  s7 -= s16 * 997805;
168  s8 += s16 * 136657;
169  s9 -= s16 * 683901;
170  s16 = 0;
171 
172  s3 += s15 * 666643;
173  s4 += s15 * 470296;
174  s5 += s15 * 654183;
175  s6 -= s15 * 997805;
176  s7 += s15 * 136657;
177  s8 -= s15 * 683901;
178  s15 = 0;
179 
180  s2 += s14 * 666643;
181  s3 += s14 * 470296;
182  s4 += s14 * 654183;
183  s5 -= s14 * 997805;
184  s6 += s14 * 136657;
185  s7 -= s14 * 683901;
186  s14 = 0;
187 
188  s1 += s13 * 666643;
189  s2 += s13 * 470296;
190  s3 += s13 * 654183;
191  s4 -= s13 * 997805;
192  s5 += s13 * 136657;
193  s6 -= s13 * 683901;
194  s13 = 0;
195 
196  s0 += s12 * 666643;
197  s1 += s12 * 470296;
198  s2 += s12 * 654183;
199  s3 -= s12 * 997805;
200  s4 += s12 * 136657;
201  s5 -= s12 * 683901;
202  s12 = 0;
203 
204  carry0 = (s0 + X20) >> 21;
205  s1 += carry0;
206  s0 -= carry0 * X21;
207  carry2 = (s2 + X20) >> 21;
208  s3 += carry2;
209  s2 -= carry2 * X21;
210  carry4 = (s4 + X20) >> 21;
211  s5 += carry4;
212  s4 -= carry4 * X21;
213  carry6 = (s6 + X20) >> 21;
214  s7 += carry6;
215  s6 -= carry6 * X21;
216  carry8 = (s8 + X20) >> 21;
217  s9 += carry8;
218  s8 -= carry8 * X21;
219  carry10 = (s10 + X20) >> 21;
220  s11 += carry10;
221  s10 -= carry10 * X21;
222 
223  carry1 = (s1 + X20) >> 21;
224  s2 += carry1;
225  s1 -= carry1 * X21;
226  carry3 = (s3 + X20) >> 21;
227  s4 += carry3;
228  s3 -= carry3 * X21;
229  carry5 = (s5 + X20) >> 21;
230  s6 += carry5;
231  s5 -= carry5 * X21;
232  carry7 = (s7 + X20) >> 21;
233  s8 += carry7;
234  s7 -= carry7 * X21;
235  carry9 = (s9 + X20) >> 21;
236  s10 += carry9;
237  s9 -= carry9 * X21;
238  carry11 = (s11 + X20) >> 21;
239  s12 += carry11;
240  s11 -= carry11 * X21;
241 
242  s0 += s12 * 666643;
243  s1 += s12 * 470296;
244  s2 += s12 * 654183;
245  s3 -= s12 * 997805;
246  s4 += s12 * 136657;
247  s5 -= s12 * 683901;
248  s12 = 0;
249 
250  carry0 = s0 >> 21;
251  s1 += carry0;
252  s0 -= carry0 * X21;
253  carry1 = s1 >> 21;
254  s2 += carry1;
255  s1 -= carry1 * X21;
256  carry2 = s2 >> 21;
257  s3 += carry2;
258  s2 -= carry2 * X21;
259  carry3 = s3 >> 21;
260  s4 += carry3;
261  s3 -= carry3 * X21;
262  carry4 = s4 >> 21;
263  s5 += carry4;
264  s4 -= carry4 * X21;
265  carry5 = s5 >> 21;
266  s6 += carry5;
267  s5 -= carry5 * X21;
268  carry6 = s6 >> 21;
269  s7 += carry6;
270  s6 -= carry6 * X21;
271  carry7 = s7 >> 21;
272  s8 += carry7;
273  s7 -= carry7 * X21;
274  carry8 = s8 >> 21;
275  s9 += carry8;
276  s8 -= carry8 * X21;
277  carry9 = s9 >> 21;
278  s10 += carry9;
279  s9 -= carry9 * X21;
280  carry10 = s10 >> 21;
281  s11 += carry10;
282  s10 -= carry10 * X21;
283  carry11 = s11 >> 21;
284  s12 += carry11;
285  s11 -= carry11 * X21;
286 
287  s0 += s12 * 666643;
288  s1 += s12 * 470296;
289  s2 += s12 * 654183;
290  s3 -= s12 * 997805;
291  s4 += s12 * 136657;
292  s5 -= s12 * 683901;
293  s12 = 0;
294 
295  carry0 = s0 >> 21;
296  s1 += carry0;
297  s0 -= carry0 * X21;
298  carry1 = s1 >> 21;
299  s2 += carry1;
300  s1 -= carry1 * X21;
301  carry2 = s2 >> 21;
302  s3 += carry2;
303  s2 -= carry2 * X21;
304  carry3 = s3 >> 21;
305  s4 += carry3;
306  s3 -= carry3 * X21;
307  carry4 = s4 >> 21;
308  s5 += carry4;
309  s4 -= carry4 * X21;
310  carry5 = s5 >> 21;
311  s6 += carry5;
312  s5 -= carry5 * X21;
313  carry6 = s6 >> 21;
314  s7 += carry6;
315  s6 -= carry6 * X21;
316  carry7 = s7 >> 21;
317  s8 += carry7;
318  s7 -= carry7 * X21;
319  carry8 = s8 >> 21;
320  s9 += carry8;
321  s8 -= carry8 * X21;
322  carry9 = s9 >> 21;
323  s10 += carry9;
324  s9 -= carry9 * X21;
325  carry10 = s10 >> 21;
326  s11 += carry10;
327  s10 -= carry10 * X21;
328 
329  s[0] = s0 >> 0;
330  s[1] = s0 >> 8;
331  s[2] = (s0 >> 16) | (s1 << 5);
332  s[3] = s1 >> 3;
333  s[4] = s1 >> 11;
334  s[5] = (s1 >> 19) | (s2 << 2);
335  s[6] = s2 >> 6;
336  s[7] = (s2 >> 14) | (s3 << 7);
337  s[8] = s3 >> 1;
338  s[9] = s3 >> 9;
339  s[10] = (s3 >> 17) | (s4 << 4);
340  s[11] = s4 >> 4;
341  s[12] = s4 >> 12;
342  s[13] = (s4 >> 20) | (s5 << 1);
343  s[14] = s5 >> 7;
344  s[15] = (s5 >> 15) | (s6 << 6);
345  s[16] = s6 >> 2;
346  s[17] = s6 >> 10;
347  s[18] = (s6 >> 18) | (s7 << 3);
348  s[19] = s7 >> 5;
349  s[20] = s7 >> 13;
350  s[21] = s8 >> 0;
351  s[22] = s8 >> 8;
352  s[23] = (s8 >> 16) | (s9 << 5);
353  s[24] = s9 >> 3;
354  s[25] = s9 >> 11;
355  s[26] = (s9 >> 19) | (s10 << 2);
356  s[27] = s10 >> 6;
357  s[28] = (s10 >> 14) | (s11 << 7);
358  s[29] = s11 >> 1;
359  s[30] = s11 >> 9;
360  s[31] = s11 >> 17;
361  }
362 
363 }
void sc_reduce(uint8_t *)
Definition: sc_reduce.cpp:25
uint64_t load_4(const uint8_t *in)
uint64_t load_3(const uint8_t in[3])
Definition: alg_id.cpp:13