Botan  2.6.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 uint32_t MASK = 0x1fffff;
28 
29  int64_t s0 = MASK & load_3(s);
30  int64_t s1 = MASK & (load_4(s + 2) >> 5);
31  int64_t s2 = MASK & (load_3(s + 5) >> 2);
32  int64_t s3 = MASK & (load_4(s + 7) >> 7);
33  int64_t s4 = MASK & (load_4(s + 10) >> 4);
34  int64_t s5 = MASK & (load_3(s + 13) >> 1);
35  int64_t s6 = MASK & (load_4(s + 15) >> 6);
36  int64_t s7 = MASK & (load_3(s + 18) >> 3);
37  int64_t s8 = MASK & load_3(s + 21);
38  int64_t s9 = MASK & (load_4(s + 23) >> 5);
39  int64_t s10 = MASK & (load_3(s + 26) >> 2);
40  int64_t s11 = MASK & (load_4(s + 28) >> 7);
41  int64_t s12 = MASK & (load_4(s + 31) >> 4);
42  int64_t s13 = MASK & (load_3(s + 34) >> 1);
43  int64_t s14 = MASK & (load_4(s + 36) >> 6);
44  int64_t s15 = MASK & (load_3(s + 39) >> 3);
45  int64_t s16 = MASK & load_3(s + 42);
46  int64_t s17 = MASK & (load_4(s + 44) >> 5);
47  int64_t s18 = MASK & (load_3(s + 47) >> 2);
48  int64_t s19 = MASK & (load_4(s + 49) >> 7);
49  int64_t s20 = MASK & (load_4(s + 52) >> 4);
50  int64_t s21 = MASK & (load_3(s + 55) >> 1);
51  int64_t s22 = MASK & (load_4(s + 57) >> 6);
52  int64_t s23 = (load_4(s + 60) >> 3);
53 
54  redc_mul(s11, s12, s13, s14, s15, s16, s23);
55  redc_mul(s10, s11, s12, s13, s14, s15, s22);
56  redc_mul( s9, s10, s11, s12, s13, s14, s21);
57  redc_mul( s8, s9, s10, s11, s12, s13, s20);
58  redc_mul( s7, s8, s9, s10, s11, s12, s19);
59  redc_mul( s6, s7, s8, s9, s10, s11, s18);
60 
61  carry<21>(s6, s7);
62  carry<21>(s8, s9);
63  carry<21>(s10, s11);
64  carry<21>(s12, s13);
65  carry<21>(s14, s15);
66  carry<21>(s16, s17);
67 
68  carry<21>(s7, s8);
69  carry<21>(s9, s10);
70  carry<21>(s11, s12);
71  carry<21>(s13, s14);
72  carry<21>(s15, s16);
73 
74  redc_mul(s5, s6, s7, s8, s9, s10, s17);
75  redc_mul(s4, s5, s6, s7, s8, s9, s16);
76  redc_mul(s3, s4, s5, s6, s7, s8, s15);
77  redc_mul(s2, s3, s4, s5, s6, s7, s14);
78  redc_mul(s1, s2, s3, s4, s5, s6, s13);
79  redc_mul(s0, s1, s2, s3, s4, s5, s12);
80 
81  carry<21>(s0, s1);
82  carry<21>(s2, s3);
83  carry<21>(s4, s5);
84  carry<21>(s6, s7);
85  carry<21>(s8, s9);
86  carry<21>(s10, s11);
87 
88  carry<21>(s1, s2);
89  carry<21>(s3, s4);
90  carry<21>(s5, s6);
91  carry<21>(s7, s8);
92  carry<21>(s9, s10);
93  carry<21>(s11, s12);
94 
95  redc_mul(s0, s1, s2, s3, s4, s5, s12);
96 
97  carry0<21>(s0, s1);
98  carry0<21>(s1, s2);
99  carry0<21>(s2, s3);
100  carry0<21>(s3, s4);
101  carry0<21>(s4, s5);
102  carry0<21>(s5, s6);
103  carry0<21>(s6, s7);
104  carry0<21>(s7, s8);
105  carry0<21>(s8, s9);
106  carry0<21>(s9, s10);
107  carry0<21>(s10, s11);
108  carry0<21>(s11, s12);
109 
110  redc_mul(s0, s1, s2, s3, s4, s5, s12);
111 
112  carry0<21>(s0, s1);
113  carry0<21>(s1, s2);
114  carry0<21>(s2, s3);
115  carry0<21>(s3, s4);
116  carry0<21>(s4, s5);
117  carry0<21>(s5, s6);
118  carry0<21>(s6, s7);
119  carry0<21>(s7, s8);
120  carry0<21>(s8, s9);
121  carry0<21>(s9, s10);
122  carry0<21>(s10, s11);
123  carry0<21>(s11, s12);
124 
125  s[0] = s0 >> 0;
126  s[1] = s0 >> 8;
127  s[2] = (s0 >> 16) | (s1 << 5);
128  s[3] = s1 >> 3;
129  s[4] = s1 >> 11;
130  s[5] = (s1 >> 19) | (s2 << 2);
131  s[6] = s2 >> 6;
132  s[7] = (s2 >> 14) | (s3 << 7);
133  s[8] = s3 >> 1;
134  s[9] = s3 >> 9;
135  s[10] = (s3 >> 17) | (s4 << 4);
136  s[11] = s4 >> 4;
137  s[12] = s4 >> 12;
138  s[13] = (s4 >> 20) | (s5 << 1);
139  s[14] = s5 >> 7;
140  s[15] = (s5 >> 15) | (s6 << 6);
141  s[16] = s6 >> 2;
142  s[17] = s6 >> 10;
143  s[18] = (s6 >> 18) | (s7 << 3);
144  s[19] = s7 >> 5;
145  s[20] = s7 >> 13;
146  s[21] = s8 >> 0;
147  s[22] = s8 >> 8;
148  s[23] = (s8 >> 16) | (s9 << 5);
149  s[24] = s9 >> 3;
150  s[25] = s9 >> 11;
151  s[26] = (s9 >> 19) | (s10 << 2);
152  s[27] = s10 >> 6;
153  s[28] = (s10 >> 14) | (s11 << 7);
154  s[29] = s11 >> 1;
155  s[30] = s11 >> 9;
156  s[31] = s11 >> 17;
157  }
158 
159 }
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
void redc_mul(int64_t &s1, int64_t &s2, int64_t &s3, int64_t &s4, int64_t &s5, int64_t &s6, int64_t &X)