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