1/* Copyright (c) (2017-2023) Apple Inc. All rights reserved.
2 *
3 * corecrypto is licensed under Apple Inc.’s Internal Use License Agreement (which
4 * is contained in the License.txt file distributed with corecrypto) and only to
5 * people who accept that license. IMPORTANT: Any license rights granted to you by
6 * Apple Inc. (if any) are limited to internal use within your organization only on
7 * devices and computers you own or control, for the sole purpose of verifying the
8 * security characteristics and correct functioning of the Apple Software. You may
9 * not, directly or indirectly, redistribute the Apple Software or any portions thereof.
10 *
11 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
12 *
13 * This file contains Original Code and/or Modifications of Original Code
14 * as defined in and that are subject to the Apple Public Source License
15 * Version 2.0 (the 'License'). You may not use this file except in
16 * compliance with the License. The rights granted to you under the License
17 * may not be used to create, or enable the creation or redistribution of,
18 * unlawful or unlicensed copies of an Apple operating system, or to
19 * circumvent, violate, or enable the circumvention or violation of, any
20 * terms of an Apple operating system software license agreement.
21 *
22 * Please obtain a copy of the License at
23 * http://www.opensource.apple.com/apsl/ and read it before using this file.
24 *
25 * The Original Code and all software distributed under the License are
26 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
27 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
28 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
29 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
30 * Please see the License for the specific language governing rights and
31 * limitations under the License.
32 *
33 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
34 */
35
36#ifndef _CORECRYPTO_CCN_INTERNAL_H
37#define _CORECRYPTO_CCN_INTERNAL_H
38
39#include <corecrypto/ccn.h>
40#include "cc_workspaces.h"
41#include "cc_memory.h"
42#include "cc_internal.h"
43
44CC_PTRCHECK_CAPABLE_HEADER()
45
46#if CCN_UNIT_SIZE == 8
47
48 #if CC_DUNIT_SUPPORTED
49typedef unsigned cc_dunit __attribute__((mode(TI)));
50 #endif
51
52#define cc_clz_nonzero cc_clz64
53#define cc_ctz_nonzero cc_ctz64
54#define CC_STORE_UNIT_BE(x, out) cc_store64_be(x, out)
55#define CC_LOAD_UNIT_BE(x, out) (x = cc_load64_be(out))
56
57#elif CCN_UNIT_SIZE == 4
58
59typedef uint64_t cc_dunit;
60
61#define cc_clz_nonzero cc_clz32
62#define cc_ctz_nonzero cc_ctz32
63#define CC_STORE_UNIT_BE(x, out) cc_store32_be(x, out)
64#define CC_LOAD_UNIT_BE(x, out) (x = cc_load32_be(out))
65
66#else
67
68#error Unsupported CCN_UNIT_SIZE
69
70#endif
71
72#if CC_DUNIT_SUPPORTED
73
74// r := x + y
75#define CC_DUNIT_ADD(r, x, y, tmp) \
76 do { \
77 tmp = ((cc_dunit)(x)) + (y); \
78 r = (cc_unit)tmp; \
79 } while (0);
80
81// r := x + y + (tmp >> 64)
82#define CC_DUNIT_ADC(r, x, y, tmp) \
83 do { \
84 cc_unit _c = (tmp) >> CCN_UNIT_BITS; \
85 tmp = ((cc_dunit)(x)) + (y) + _c; \
86 r = (cc_unit)tmp; \
87 } while (0);
88
89// r := x - y
90#define CC_DUNIT_SUB(r, x, y, tmp) \
91 do { \
92 tmp = ((cc_dunit)(x)) - (y); \
93 r = (cc_unit)tmp; \
94 } while (0);
95
96// r := x - y - (tmp >> 127)
97#define CC_DUNIT_SBC(r, x, y, tmp) \
98 do { \
99 cc_unit _b = (tmp) >> (2 * CCN_UNIT_BITS - 1); \
100 tmp = ((cc_dunit)(x)) - (y) - _b; \
101 r = (cc_unit)tmp; \
102 } while (0);
103
104// (hi,lo) += (x * y)
105#define CC_DUNIT_MUL(x, y, hi, lo, tmp) \
106 do { \
107 tmp = (cc_dunit)(x) * (y); \
108 lo += (tmp) & CCN_UNIT_MASK; \
109 hi += (tmp) >> CCN_UNIT_BITS; \
110 } while (0);
111
112// (hi,lo) += (x * y) * i
113#define CC_DUNIT_MULI(x, y, hi, lo, tmp, i) \
114 do { \
115 tmp = (cc_dunit)(x) * (y); \
116 lo += ((tmp) & CCN_UNIT_MASK) * (i); \
117 hi += ((tmp) >> CCN_UNIT_BITS) * (i); \
118 } while (0);
119
120// r := lo and (hi,lo) >>= 64
121#define CC_STORE_LO(r, hi, lo) \
122 do { \
123 r = (cc_unit)lo; \
124 hi += lo >> CCN_UNIT_BITS; \
125 lo = hi & CCN_UNIT_MASK; \
126 hi >>= CCN_UNIT_BITS; \
127 } while (0);
128
129#endif
130
131CC_NONNULL((2, 3))
132void ccn_set(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s);
133
134CC_INLINE
135CC_NONNULL((2, 4))
136void
137ccn_setn(cc_size n, cc_unit *cc_counted_by (n)r, const cc_size s_size, const cc_unit *cc_counted_by (s_size)s)
138{
139 cc_assert(n > 0 && s_size <= n);
140
141 if (s_size > 0) {
142 ccn_set(n: s_size, r, s);
143 }
144
145 ccn_zero(n: n - s_size, r: r + s_size);
146}
147
148CC_INLINE
149CC_NONNULL((2))
150void
151ccn_clear(cc_size n, cc_unit *cc_sized_by (n)r)
152{
153 cc_clear(ccn_sizeof_n(n), dst: r);
154}
155
156/* Returns the value of bit _k_ of _ccn_, both are only evaluated once. */
157CC_INLINE cc_unit
158ccn_bit(const cc_unit *cc_indexable x, size_t k)
159{
160 return 1 & (x[k >> CCN_LOG2_BITS_PER_UNIT] >> (k & (CCN_UNIT_BITS - 1)));
161}
162
163/* |s - t| -> r return 1 iff t > s, 0 otherwise */
164CC_WARN_RESULT
165cc_unit ccn_abs(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, const cc_unit *cc_counted_by(n) t);
166
167/* Returns the number of bits which are zero before the first one bit
168 * counting from least to most significant bit. */
169CC_WARN_RESULT
170CC_NONNULL((2))
171size_t ccn_trailing_zeros(cc_size n, const cc_unit *s);
172
173/*! @function ccn_shift_right
174 * @abstract Shifts s to the right by k bits, where 0 <= k < CCN_UNIT_BITS.
175 *
176 * @param n Length of r and s
177 * @param r Resulting big int.
178 * @param s Big int to shift.
179 * @param k Number of bits to shift by.
180 */
181CC_NONNULL_ALL
182void ccn_shift_right(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, size_t k) __asm__("_ccn_shift_right");
183
184/*! @function ccn_shift_right_multi
185 * @abstract Constant-time, SPA-safe, right shift.
186 *
187 * @param n Length of r and s as number of cc_units.
188 * @param r Destination, can overlap with s.
189 * @param s Input that's shifted by k bits.
190 * @param k Number of bits by which to shift s to the right.
191 */
192CC_NONNULL_ALL
193void ccn_shift_right_multi(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, size_t k);
194
195/* s << k -> r return bits shifted out of most significant word in bits [0, n>
196 * { N bit, scalar -> N bit } N = n * sizeof(cc_unit) * 8
197 * the _multi version doesn't return the shifted bits, but does support multiple
198 * word shifts */
199CC_NONNULL_ALL
200void ccn_shift_left(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, size_t k) __asm__("_ccn_shift_left");
201
202CC_NONNULL_ALL
203void ccn_shift_left_multi(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, size_t k);
204
205// Conditionally swap the content of r0 and r1 buffers in constant time
206// r0:r1 <- r1*k1 + s0*(k1-1)
207CC_NONNULL_ALL
208void ccn_cond_swap(cc_size n, cc_unit ki, cc_unit *cc_counted_by(n) r0, cc_unit *cc_counted_by(n) r1);
209
210/*! @function ccn_cond_shift_right
211 * @abstract Constant-time, SPA-safe, conditional right shift.
212 *
213 * @param n Length of each of r and a as number of cc_units.
214 * @param s Selector bit (0 or 1).
215 * @param r Destination, can overlap with a.
216 * @param a Input that's shifted by k bits, if s=1.
217 * @param k Number of bits by which to shift a to the right, if s=1.
218 * (k must not be larger than CCN_UNIT_BITS.)
219 */
220CC_NONNULL_ALL
221void ccn_cond_shift_right(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) a, size_t k);
222
223/*! @function ccn_cond_neg
224 * @abstract Constant-time, SPA-safe, conditional negation.
225 *
226 * @param n Length of each of r and x as number of cc_units.
227 * @param s Selector bit (0 or 1).
228 * @param r Destination, can overlap with x.
229 * @param x Input that's negated, if s=1.
230 */
231void ccn_cond_neg(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x);
232
233/*! @function ccn_cond_shift_right_carry
234 * @abstract Constant-time, SPA-safe, conditional right shift.
235 *
236 * @param n Length of each of r and a as number of cc_units.
237 * @param s Selector bit (0 or 1).
238 * @param r Destination, can overlap with a.
239 * @param a Input that's shifted by k bits, if s=1.
240 * @param k Number of bits by which to shift a to the right, if s=1.
241 * (k must not be larger than CCN_UNIT_BITS.)
242 * @param c Carry bit(s), the most significant bit(s) after shifting, if s=1.
243 */
244CC_NONNULL_ALL
245void ccn_cond_shift_right_carry(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) a, size_t k, cc_unit c);
246
247/*! @function ccn_cond_add
248 * @abstract Constant-time, SPA-safe, conditional addition.
249 * Computes r:= x + y, iff s = 1. Set r := x otherwise.
250 *
251 * @param n Length of each of r, x, and y as number of cc_units.
252 * @param s Selector bit (0 or 1).
253 * @param r Destination, can overlap with x or y.
254 * @param x First addend.
255 * @param y Second addend.
256 *
257 * @return The carry bit, if s=1. 0 otherwise.
258 */
259CC_WARN_RESULT CC_NONNULL_ALL
260cc_unit ccn_cond_add(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x, const cc_unit *cc_counted_by(n) y);
261
262/*! @function ccn_cond_rsub
263 * @abstract Constant-time, SPA-safe, conditional reverse subtraction.
264 * Computes r := y - x, iff s = 1. Sets r := x otherwise.
265 *
266 * @param n Length of each of r, x, and y as number of cc_units.
267 * @param s Selector bit (0 or 1).
268 * @param r Destination, can overlap with x or y.
269 * @param x Subtrahend.
270 * @param y Minuend.
271 *
272 * @return The carry bit, if s=1. 0 otherwise.
273 */
274CC_WARN_RESULT CC_NONNULL_ALL
275cc_unit ccn_cond_rsub(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x, const cc_unit *cc_counted_by(n) y);
276
277/*! @function ccn_cond_sub
278 * @abstract Constant-time, SPA-safe, conditional subtraction.
279 * Computes r := x - y, iff s = 1. Sets r := x otherwise.
280 *
281 * @param n Length of each of r, x, and y as number of cc_units.
282 * @param s Selector bit (0 or 1).
283 * @param r Destination, can overlap with x or y.
284 * @param x Minuend.
285 * @param y Subtrahend.
286 *
287 * @return The carry bit, if s=1. 0 otherwise.
288 */
289CC_WARN_RESULT CC_NONNULL_ALL
290cc_unit ccn_cond_sub(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x, const cc_unit *cc_counted_by(n) y);
291
292/*! @function ccn_cond_clear
293 * @abstract Constant-time, SPA-safe, conditional zeroization.
294 * Sets r := 0, if s = 1. Does nothing otherwise.
295 *
296 * @param n Length of r as number of cc_units.
297 * @param s Selector bit (0 or 1).
298 * @param r Destination, can overlap with x or y.
299 */
300CC_NONNULL_ALL
301void ccn_cond_clear(cc_size n, cc_unit s, cc_unit *r);
302
303/*! @function ccn_mux
304 * @abstract Constant-time, SPA-safe multiplexer. Sets r = (s ? a : b).
305 *
306 * @discussion This works like a normal multiplexer (s & a) | (~s & b) but is
307 * slightly more complicated and expensive. Out of `s` we build
308 * half-word masks to hide extreme Hamming weights of operands.
309 *
310 * @param n Length of each of r, a, and b as number of cc_units.
311 * @param s Selector bit (0 or 1).
312 * @param r Destination, can overlap with a or b.
313 * @param a Input selected when s=1.
314 * @param b Input selected when s=0.
315 */
316CC_NONNULL_ALL
317void ccn_mux(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) a, const cc_unit *cc_counted_by(n) b);
318
319/*! @function ccn_gcd_ws
320 * @abstract Computes the greatest common divisor of s and t,
321 * r = gcd(s,t) / 2^k, and returns k.
322 *
323 * @param ws Workspace.
324 * @param rn Length of r as a number of cc_units.
325 * @param r Resulting GCD.
326 * @param sn Length of s as a number of cc_units.
327 * @param s First number s.
328 * @param tn Length of t as a number of cc_units.
329 * @param t First number t.
330 *
331 * @return The factor of two to shift r by to compute the actual GCD.
332 */
333CC_WARN_RESULT
334CC_NONNULL_ALL
335size_t ccn_gcd_ws(cc_ws_t ws, cc_size rn, cc_unit *cc_counted_by(rn) r, cc_size sn, const cc_unit *cc_counted_by(sn) s, cc_size tn, const cc_unit *cc_counted_by(tn) t);
336
337/*! @function ccn_lcm_ws
338 * @abstract Computes lcm(s,t), the least common multiple of s and t.
339 *
340 * @param ws Workspace.
341 * @param n Length of s,t as a number of cc_units.
342 * @param r2n Resulting LCM of length 2*n.
343 * @param s First number s.
344 * @param t First number t.
345 */
346void ccn_lcm_ws(cc_ws_t ws, cc_size n, cc_unit *cc_unsafe_indexable r2n, const cc_unit *cc_counted_by(n)s, const cc_unit *cc_counted_by(n)t);
347
348/* s * t -> r_2n r_2n must not overlap with s nor t
349 * { n bit, n bit -> 2 * n bit } n = count * sizeof(cc_unit) * 8
350 * { N bit, N bit -> 2N bit } N = ccn_bitsof(n) */
351CC_NONNULL((2, 3, 4))
352void ccn_mul(cc_size n, cc_unit *cc_unsafe_indexable r_2n, const cc_unit *cc_counted_by(n)s, const cc_unit *cc_counted_by(n)t) __asm__("_ccn_mul");
353
354/* s[0..n) * v -> r[0..n)+return value
355 * { N bit, sizeof(cc_unit) * 8 bit -> N + sizeof(cc_unit) * 8 bit } N = n * sizeof(cc_unit) * 8 */
356CC_WARN_RESULT
357CC_NONNULL((2, 3))
358cc_unit ccn_mul1(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, const cc_unit v);
359
360/* s[0..n) * v[0..nv] -> r[0..n+nv)
361* { n bit, nv bit -> n + nv bit} n = count * sizeof(cc_unit) * 8
362* { N bit, NV bit -> N + NV bit} N = ccn_bitsof(n), NV = ccn_bitsof(nv)
363* r, s, and v should not overlap
364* Leaks n and nv through timing */
365CC_NONNULL_ALL
366void ccn_muln(cc_size n, cc_unit *cc_counted_by(n + nv) r, const cc_unit *cc_counted_by(n) s, cc_size nv, const cc_unit *cc_counted_by(n) v);
367
368/* s[0..n) * v + r[0..n) -> r[0..n)+return value
369 * { N bit, sizeof(cc_unit) * 8 bit -> N + sizeof(cc_unit) * 8 bit } N = n * sizeof(cc_unit) * 8 */
370CC_WARN_RESULT
371CC_NONNULL((2, 3))
372cc_unit ccn_addmul1(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, const cc_unit v);
373
374/* s * t -> r_2n r_2n must not overlap with s nor t
375 * { n bit, n bit -> 2 * n bit } n = count * sizeof(cc_unit) * 8
376 * { N bit, N bit -> 2N bit } N = ccn_bitsof(n)
377 * Provide a workspace for potential speedup */
378CC_NONNULL_ALL
379void ccn_mul_ws(cc_ws_t ws, cc_size count, cc_unit *cc_unsafe_indexable r, const cc_unit *cc_counted_by(count)s, const cc_unit *cc_counted_by(count)t);
380
381/* s^2 -> r
382 * { n bit -> 2 * n bit } */
383CC_NONNULL_ALL
384void ccn_sqr_ws(cc_ws_t ws, cc_size n, cc_unit *cc_unsafe_indexable r, const cc_unit *cc_counted_by(n)s);
385
386/*! @function ccn_mod_ws
387 * @abstract Computes r = a % d.
388 *
389 * @discussion Use CCN_DIVMOD_WORKSPACE_N(n) for the workspace.
390 *
391 * @param ws Workspace
392 * @param na Length of a as a number of cc_units.
393 * @param a The dividend a.
394 * @param n Length of r,d as a number of cc_units.
395 * @param r The resulting remainder.
396 * @param d The divisor d.
397 */
398#define ccn_mod_ws(ws, na, a, n, r, d) ccn_divmod_ws(ws, na, a, 0, NULL, n, r, d)
399#define ccn_mod(na, a, n, r, d) ccn_divmod(na, a, 0, NULL, n, r, d)
400
401/*! @function ccn_neg
402 * @abstract Computes the two's complement of x.
403 *
404 * @param n Length of r and x
405 * @param r Result of the negation
406 * @param x Number to negate
407 */
408CC_NONNULL_ALL
409void ccn_neg(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x);
410
411/*! @function ccn_invert
412 * @abstract Computes x^-1 (mod 2^w).
413 *
414 * @param x Number to invert
415 *
416 * @return x^-1 (mod 2^w)
417 */
418CC_WARN_RESULT
419CC_CONST CC_NONNULL_ALL
420CC_INLINE cc_unit
421ccn_invert(cc_unit x)
422{
423 cc_assert(x & 1);
424
425 // Initial precision is 5 bits.
426 cc_unit y = (3 * x) ^ 2;
427
428 // Newton-Raphson iterations.
429 // Precision doubles with every step.
430 y *= 2 - y * x;
431 y *= 2 - y * x;
432 y *= 2 - y * x;
433#if CCN_UNIT_SIZE == 8
434 y *= 2 - y * x;
435#endif
436
437 cc_assert(y * x == 1);
438 return y;
439}
440
441/*! @function ccn_div_exact_ws
442 * @abstract Computes q = a / d where a = 0 (mod d).
443 *
444 * @param ws Workspace
445 * @param n Length of q,a,d as a number of cc_units.
446 * @param q The resulting exact quotient.
447 * @param a The dividend a.
448 * @param d The divisor d.
449 */
450CC_NONNULL_ALL
451void ccn_div_exact_ws(cc_ws_t ws, cc_size n, cc_unit *cc_counted_by(n) q, const cc_unit *cc_counted_by(n) a, const cc_unit *cc_counted_by(n) d);
452
453/*! @function ccn_divides1
454 * @abstract Returns whether q divides x.
455 *
456 * @param n Length of x as a number of cc_units.
457 * @param x The dividend x.
458 * @param q The divisor q.
459 *
460 * @return True if q divides x without remainder, false otherwise.
461 */
462CC_WARN_RESULT
463CC_NONNULL_ALL
464bool ccn_divides1(cc_size n, const cc_unit *cc_counted_by(n)x, cc_unit q);
465
466/*! @function ccn_select
467 * @abstract Select r[i] in constant-time, not revealing i via cache-timing.
468 *
469 * @param start Start index.
470 * @param end End index (length of r).
471 * @param r Big int r.
472 * @param i Offset into r.
473 *
474 * @return r[i], or zero if start > i or end < i.
475 */
476CC_WARN_RESULT
477CC_INLINE cc_unit
478ccn_select(cc_size start, cc_size end, const cc_unit *cc_counted_by(end)r, cc_size i)
479{
480 cc_unit ri = 0;
481
482 for (cc_size j = start; j < end; j++) {
483 cc_size i_neq_j; // i≠j?
484 CC_HEAVISIDE_STEP(i_neq_j, i ^ j);
485 ri |= r[j] & ((cc_unit)i_neq_j - 1);
486 }
487
488 return ri;
489}
490
491/*! @function ccn_invmod_ws
492 * @abstract Computes the inverse of x modulo m, r = x^-1 (mod m).
493 * Returns an error if there's no inverse, i.e. gcd(x,m) ≠ 1.
494 *
495 * @discussion This is a very generic version of the binary XGCD algorithm. You
496 * don't want to use it when you have an odd modulus.
497 *
498 * This function is meant to be used by RSA key generation, for
499 * computation of d = e^1 (mod lcm(p-1,q-1)), where m can be even.
500 *
501 * x > m is allowed as long as xn == n, i.e. they occupy the same
502 * number of cc_units.
503 *
504 * @param ws Workspace.
505 * @param n Length of r and m as a number of cc_units.
506 * @param r The resulting inverse r.
507 * @param xn Length of x as a number of cc_units.
508 * @param x The number to invert.
509 * @param m The modulus.
510 *
511 * @return 0 on success, non-zero on failure. See cc_error.h for more details.
512 */
513CC_WARN_RESULT
514int ccn_invmod_ws(cc_ws_t ws, cc_size n, cc_unit *cc_counted_by(n) r, cc_size xn, const cc_unit *cc_counted_by(xn) x, const cc_unit *cc_counted_by(n) m);
515
516/*! @function ccn_mux_seed_mask
517 * @abstract Refreshes the internal state of the PRNG used to mask cmov/cswap
518 * operations with a given seed.
519 *
520 * @discussion The seed should be of good entropy, i.e. generated by our default
521 * RNG. This function should be called before running algorithms that
522 * defend against side-channel attacks by using cmov/cswap. Examples
523 * are blinded modular exponentation (for RSA, DH, or MR) and EC
524 * scalar multiplication.
525 *
526 * @param seed A seed value.
527 */
528void ccn_mux_seed_mask(cc_unit seed);
529
530/*! @function ccn_divmod
531 * @abstract Computes a = q * d + r with r < d.
532 *
533 * @param na Length of a as a number of cc_units.
534 * @param a The dividend a.
535 * @param nq Length of q as a number of cc_units.
536 * @param q The quotient q.
537 * @param n Length of r and d as a number of cc_units.
538 * @param r The remainder r.
539 * @param d The divisor d.
540 *
541 * @return 0 on success, non-zero on failure. See cc_error.h for more details.
542 */
543CC_NONNULL((2, 7)) CC_WARN_RESULT
544int ccn_divmod(cc_size na, const cc_unit *cc_counted_by(na) a, cc_size nq, cc_unit *cc_counted_by(nq) q, cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) d);
545
546CC_NONNULL((1, 3, 8))
547void ccn_divmod_ws(cc_ws_t ws, cc_size na, const cc_unit *cc_counted_by(na) a, cc_size nq, cc_unit *cc_counted_by(nq) q, cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) d);
548
549CC_NONNULL((2)) CC_SENTINEL
550void ccn_zero_multi(cc_size n, cc_unit *r, ...);
551
552CC_NONNULL((3, 4, 5))
553cc_unit ccn_add_ws(cc_ws_t ws, cc_size count, cc_unit *r, const cc_unit *s, const cc_unit *t);
554
555CC_NONNULL((3, 4, 5))
556cc_unit ccn_sub_ws(cc_ws_t ws, cc_size count, cc_unit *r, const cc_unit *s, const cc_unit *t);
557
558CC_NONNULL((3, 4))
559cc_unit ccn_add1_ws(cc_ws_t ws, cc_size n, cc_unit *r, const cc_unit *s, cc_unit v);
560
561/* s + t -> r return carry if result doesn't fit in n bits
562 * { N bit, NT bit -> N bit NT <= N} N = n * sizeof(cc_unit) * 8 */
563CC_NONNULL_ALL
564cc_unit ccn_addn(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, cc_size nt, const cc_unit *cc_counted_by(nt) t);
565
566/* s - v -> r return 1 iff v > s return 0 otherwise.
567 * { N bit, sizeof(cc_unit) * 8 bit -> N bit } N = n * sizeof(cc_unit) * 8 */
568CC_NONNULL_ALL
569cc_unit ccn_sub1(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, cc_unit v);
570
571/* s - t -> r return 1 iff t > s
572 * { N bit, NT bit -> N bit NT <= N} N = n * sizeof(cc_unit) * 8 */
573CC_NONNULL_ALL
574cc_unit ccn_subn(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, cc_size nt, const cc_unit *cc_counted_by(nt) t);
575
576/* Return the number of used units after stripping leading 0 units. */
577CC_NONNULL_ALL
578cc_size ccn_n(cc_size n, const cc_unit *cc_counted_by(n)s);
579
580/* Make a ccn of size ccn_nof(nbits) units with up to nbits sized random value. */
581CC_NONNULL_ALL
582int ccn_random_bits(cc_size nbits, cc_unit *cc_unsafe_indexable r, struct ccrng_state *rng);
583
584/* Like ccn_random_bits, but uses ccrng_generate_fips under the hood. */
585CC_NONNULL_ALL
586int ccn_random_bits_fips(cc_size nbits, cc_unit *cc_unsafe_indexable r, struct ccrng_state *rng);
587
588// Joint Sparse Form recoding context for EC double-scalar multiplication.
589struct ccn_rjsf_state {
590 uint8_t u[2];
591 const cc_unit *s;
592 const cc_unit *t;
593};
594
595/*! @function ccn_recode_jsf_init
596 * @abstract Initialize Joint Sparse Form recoding for EC scalars s and t.
597 *
598 * @param r JSF-recoding context.
599 * @param nbits Max. bit length of s and t.
600 * @param s Scalar to be recoded.
601 * @param t Scalar to be recoded.
602 */
603CC_NONNULL_ALL
604void ccn_recode_jsf_init(struct ccn_rjsf_state *r, size_t nbits, const cc_unit *s, const cc_unit *t);
605
606/*! @function ccn_recode_jsf_column
607 * @abstract Retrieve JSF-recoded digits for column k.
608 *
609 * @param r JSF-recoding context.
610 * @param k Column index.
611 * @param c Digits (output).
612 */
613CC_NONNULL_ALL
614void ccn_recode_jsf_column(struct ccn_rjsf_state *r, size_t k, int c[2]);
615
616/*! @function ccn_recode_jsf_index
617 * @abstract Retrieve the lookup table index for given column digits.
618 *
619 * @discussion For EC double-scalar multiplication, we assume a lookup table
620 * holding the four values [P, Q, P+Q, P-Q], in the same order.
621 *
622 * @param c Column digits.
623 *
624 * @return The lookup table index.
625 */
626CC_NONNULL_ALL CC_WARN_RESULT
627size_t ccn_recode_jsf_index(int c[2]);
628
629/*! @function ccn_recode_jsf_direction
630 * @abstract Retrieve the "direction" for given column digits.
631 *
632 * @discussion For EC double-scalar multiplication, we assume a lookup table
633 * holding the four values [P, Q, P+Q, P-Q]. Negating each of
634 * these also yields [-P, -Q, -P-Q, -P+Q].
635 *
636 * An EC double-and-add algorithm will either add or subtract a
637 * precomputed point to cover all possible digit combinations of two
638 * JSF-recoded EC scalars.
639 *
640 * @param c Column digits.
641 *
642 * @return The "direction". 1 for addition. -1 for subtraction.
643 */
644CC_NONNULL_ALL CC_WARN_RESULT
645int ccn_recode_jsf_direction(int c[2]);
646
647/*! @function ccn_read_le_bytes
648 * @abstract Copies a number given as little-endian bytes into `out`.
649 *
650 * @param n Number of limbs of `out`.
651 * @param in Number to parse as little-endian bytes.
652 * @param out Output.
653 */
654CC_NONNULL_ALL
655CC_INLINE void
656ccn_read_le_bytes(cc_size n, const uint8_t *in, cc_unit *out)
657{
658 for (cc_size i = 0; i < n; i++) {
659 out[i] = cc_load_le(y: &in[i * CCN_UNIT_SIZE]);
660 }
661}
662
663/*! @function ccn_write_le_bytes
664 * @abstract Encodes a number as little-endian bytes into `out`.
665 *
666 * @param n Number of limbs of `in`.
667 * @param in Number to encode as little-endian bytes.
668 * @param out Output.
669 */
670CC_NONNULL_ALL
671CC_INLINE void
672ccn_write_le_bytes(cc_size n, const cc_unit *in, uint8_t *out)
673{
674 for (cc_size i = 0; i < n; i++) {
675 cc_store_le(x: in[i], y: &out[i * CCN_UNIT_SIZE]);
676 }
677}
678
679/*! @function ccn_recode_ssw
680 * @abstract Recodes a given number into signed sliding windows.
681 *
682 * @param n Number of limbs of `s`.
683 * @param s Number to recode.
684 * @param w Recode width, for windows in range (-2^w,2^w).
685 * @param r Output for the computed signed sliding windows.
686 */
687CC_NONNULL_ALL
688void ccn_recode_ssw(cc_size n, const cc_unit *s, int w, int8_t *r);
689
690#endif // _CORECRYPTO_CCN_INTERNAL_H
691