Debian Codegraph @

crypto/bigint/encoding.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 // The following code was initially ported from BearSSL.
5 //
6 // Copyright (c) 2017 Thomas Pornin <[email protected]>
7 //
8 // Permission is hereby granted, free of charge, to any person obtaining a copy
9 // of this software and associated documentation files (the "Software"), to deal
10 // in the Software without restriction, including without limitation the rights
11 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 // copies of the Software, and to permit persons to whom the Software is
13 // furnished to do so, subject to the following conditions:
14 //
15 // The above copyright notice and this permission notice shall be included in
16 // all copies or substantial portions of the Software.
17 //
18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 // SOFTWARE.
25 use crypto::math::*;
26
27 // Minimal required words to encode 'x' into an []word. To statically allocate
28 // resources, following expression may be used:
29 //
30 // ((number_of_bits + WORD_BITSZ - 1) / WORD_BITSZ) + 1
31 export fn encodelen(x: []u8) size = {
32 return (((len(x) * 8) + WORD_BITSZ - 1) / WORD_BITSZ) + 1;
33 };
34
35 // Encode 'src' from its big-endian unsigned encoding into the internal
36 // representation. The caller must make sure that 'dest' has enough space to
37 // store 'src'. See [[encodelen]] for how to calculate the required size.
38 //
39 // This function runs in constant time for given 'src' length.
40 export fn encode(dest: []word, src: const []u8) void = {
41 let acc: u32 = 0;
42 let accbits: u32 = 0;
43 let didx: size = 1;
44
45 for (let i = len(src) - 1; i < len(src); i -= 1) {
46 acc |= (src[i] << accbits);
47 accbits += 8;
48
49 if (accbits >= WORD_BITSZ) {
50 dest[didx] = (acc & WORD_BITMASK): word;
51 accbits -= WORD_BITSZ;
52 acc = src[i] >> (8 - accbits);
53 didx += 1;
54 };
55 };
56
57 dest[didx] = acc: word;
58
59 dest[0] = countbits(dest[1..didx + 1]): word;
60 };
61
62 // Get the announced bit length of 'n' in encoded form.
63 fn countbits(n: const []word) u32 = {
64 let tw: u32 = 0;
65 let twk: u32 = 0;
66
67 for (let i = len(n) - 1; i < len(n); i -= 1) {
68 const c = equ32(tw, 0);
69 const w = n[i];
70 tw = muxu32(c, w, tw);
71 twk = muxu32(c, i: u32, twk);
72 };
73
74 return (twk << WORD_SHIFT) + word_countbits(tw);
75 };
76
77 // Counts the number of bits until including the highest bit set to 1.
78 fn word_countbits(x: u32) u32 = {
79 let k: u32 = nequ32(x, 0);
80 let c: u32 = 0;
81
82 c = gtu32(x, 0xffff);
83 x = muxu32(c, x >> 16, x);
84 k += c << 4;
85
86 c = gtu32(x, 0x00ff);
87 x = muxu32(c, x >> 8, x);
88 k += c << 3;
89
90 c = gtu32(x, 0x000f);
91 x = muxu32(c, x >> 4, x);
92 k += c << 2;
93
94 c = gtu32(x, 0x0003);
95 x = muxu32(c, x >> 2, x);
96 k += c << 1;
97
98 k += gtu32(x, 0x0001);
99
100 return k;
101 };
102
103 // Get the encoded bit length of a word.
104 fn ebitlen(x: const []word) u32 = {
105 return x[0];
106 };
107
108 // Get the effective word lenght of 'x'. The effective wordlen is the number of
109 // words that are used to represent the actual value. Eg. the number 7 will have
110 // an effective word length of 1, no matter of len(x). The first element
111 // containing the encoded word len is not added to the result.
112 export fn ewordlen(x: const []word) u32 = {
113 return (x[0] + WORD_BITSZ) >> WORD_SHIFT;
114 };
115
116 // Decode 'src' into a big-endian unsigned byte array. The caller must ensure
117 // that 'dest' has enough space to store the decoded value. See [[decodelen]] on
118 // how to determine the required length.
119 export fn decode(dest: []u8, src: const []word) void = {
120 let acc: u64 = 0;
121 let accbits: u64 = 0;
122 let sidx: size = 1;
123 let sz = ewordlen(src);
124 for (let i = len(dest) - 1; i < len(dest); i -= 1) {
125 if (accbits < 8) {
126 if (sidx <= sz) {
127 acc |= ((src[sidx]: u64) << accbits: u64): u64;
128 sidx += 1;
129 };
130 accbits += WORD_BITSZ;
131 };
132 dest[i] = acc: u8;
133 acc >>= 8;
134 accbits -= 8;
135 };
136 };
137
138 // Returns the number of bytes required to store a big integer given by 'src'.
139 //
140 // For static allocation following expression may be used:
141 //
142 // ((len(src) - 1) * WORD_BITSZ + 7) / 8
143 export fn decodelen(src: const []word) size = {
144 return ((len(src) - 1) * WORD_BITSZ + 7) / 8;
145 };
146
147 // Encodes an integer from its big-endian unsigned encoding. 'src' must be lower
148 // than 'm'. If not 'dest' will be set to 0. 'dest' will have the announced bit
149 // length of 'm' after decoding.
150 //
151 // The return value is 1 if the decoded value fits within 'm' or 0 otherwise.
152 //
153 // This function runs in constant time for a given 'src' length and announced
154 // bit length of m, independent of whether the value fits within 'm' or not.
155 export fn encodemod(dest: []word, src: const []u8, m: const []word) u32 = {
156 // Two-pass algorithm: in the first pass, we determine whether the
157 // value fits; in the second pass, we do the actual write.
158 //
159 // During the first pass, 'r' contains the comparison result so
160 // far:
161 // 0x00000000 value is equal to the modulus
162 // 0x00000001 value is greater than the modulus
163 // 0xFFFFFFFF value is lower than the modulus
164 //
165 // Since we iterate starting with the least significant bytes (at
166 // the end of src[]), each new comparison overrides the previous
167 // except when the comparison yields 0 (equal).
168 //
169 // During the second pass, 'r' is either 0xFFFFFFFF (value fits)
170 // or 0x00000000 (value does not fit).
171 //
172 // We must iterate over all bytes of the source, _and_ possibly
173 // some extra virtual bytes (with value 0) so as to cover the
174 // complete modulus as well. We also add 4 such extra bytes beyond
175 // the modulus length because it then guarantees that no accumulated
176 // partial word remains to be processed.
177
178 let mlen = 0z, tlen = 0z;
179
180 mlen = ewordlen(m);
181 tlen = mlen << (WORD_SHIFT - 3); // mlen in bytes
182 if (tlen < len(src)) {
183 tlen = len(src);
184 };
185 tlen += 4;
186 let r: u32 = 0;
187 for (let pass = 0z; pass < 2; pass += 1) {
188 let v: size = 1;
189 let acc: u32 = 0, acc_len: u32 = 0;
190
191 for (let u = 0z; u < tlen; u += 1) {
192 // inner loop is similar to encode until the mlen check
193 let b: u32 = 0;
194
195 if (u < len(src)) {
196 b = src[len(src) - 1 - u];
197 };
198 acc |= (b << acc_len);
199 acc_len += 8;
200 if (acc_len >= WORD_BITSZ) {
201 const xw: u32 = acc & WORD_BITMASK;
202 acc_len -= WORD_BITSZ;
203 acc = b >> (8 - acc_len);
204 if (v <= mlen) {
205 if (pass == 1) {
206 dest[v] = (r & xw): word;
207 } else {
208 let cc = cmpu32(xw, m[v]: u32): u32;
209 r = muxu32(equ32(cc, 0), r, cc);
210 };
211 } else {
212 if (pass == 0) {
213 r = muxu32(equ32(xw, 0), r, 1);
214 };
215 };
216 v += 1;
217 };
218 };
219
220 // When we reach this point at the end of the first pass:
221 // r is either 0, 1 or -1; we want to set r to 0 if it
222 // is equal to 0 or 1, and leave it to -1 otherwise.
223 //
224 // When we reach this point at the end of the second pass:
225 // r is either 0 or -1; we want to leave that value
226 // untouched. This is a subcase of the previous.
227 r >>= 1;
228 r |= (r << 1);
229 };
230
231 dest[0] = m[0];
232 return r & 1;
233 };
234
235 // Encode an integer from its big-endian unsigned representation, and reduce it
236 // modulo the provided modulus 'm'. The announced bit length of the result is
237 // set to be equal to that of the modulus.
238 //
239 // 'dest' must be distinct from 'm'.
240 export fn encodereduce(dest: []word, src: const []u8, m: const []word) void = {
241 assert(&dest[0] != &m[0], "'dest' and 'm' must be distinct");
242
243 // Get the encoded bit length.
244 const m_ebitlen = m[0];
245
246 // Special case for an invalid (null) modulus.
247 if (m_ebitlen == 0) {
248 dest[0] = 0;
249 return;
250 };
251
252 zero(dest, m_ebitlen);
253
254 // First decode directly as many bytes as possible. This requires
255 // computing the actual bit length.
256 let m_rbitlen = m_ebitlen >> WORD_SHIFT;
257 m_rbitlen = (m_ebitlen & WORD_BITSZ)
258 + (m_rbitlen << WORD_SHIFT) - m_rbitlen;
259 const mblen: size = (m_rbitlen + 7) >> 3;
260 let k: size = mblen - 1;
261 if (k >= len(src)) {
262 encode(dest, src);
263 dest[0] = m_ebitlen;
264 return;
265 };
266 encode(dest, src[..k]);
267 dest[0] = m_ebitlen;
268
269 // Input remaining bytes, using 31-bit words.
270 let acc: word = 0;
271 let acc_len: word = 0;
272 for (k < len(src)) {
273 const v = src[k];
274 k += 1;
275 if (acc_len >= 23) {
276 acc_len -= 23;
277 acc <<= (8 - acc_len);
278 acc |= v >> acc_len;
279 muladd_small(dest, acc, m);
280 acc = v & (0xFF >> (8 - acc_len));
281 } else {
282 acc = (acc << 8) | v;
283 acc_len += 8;
284 };
285 };
286
287 // We may have some bits accumulated. We then perform a shift to
288 // be able to inject these bits as a full 31-bit word.
289 if (acc_len != 0) {
290 acc = (acc | (dest[1] << acc_len)) & WORD_BITMASK;
291 rshift(dest, WORD_BITSZ - acc_len);
292 muladd_small(dest, acc, m);
293 };
294 };