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