1 /* Arithmetic in prime fields
2 * Daniel Beer <dlbeer@gmail.com>, 10 Jan 2014
4 * This file is in the public domain.
9 static void raw_add(uint8_t *x, const uint8_t *p)
14 for (i = 0; i < FPRIME_SIZE; i++) {
15 c += ((uint16_t)x[i]) + ((uint16_t)p[i]);
21 static void raw_try_sub(uint8_t *x, const uint8_t *p)
23 uint8_t minusp[FPRIME_SIZE];
27 for (i = 0; i < FPRIME_SIZE; i++) {
28 c = ((uint16_t)x[i]) - ((uint16_t)p[i]) - c;
33 fprime_select(x, minusp, x, c);
36 /* Warning: this function is variable-time */
37 static int prime_msb(const uint8_t *p)
42 for (i = FPRIME_SIZE - 1; i >= 0; i--)
57 /* Warning: this function may be variable-time in the argument n */
58 static void shift_n_bits(uint8_t *x, int n)
63 for (i = 0; i < FPRIME_SIZE; i++) {
64 c |= ((uint16_t)x[i]) << n;
70 static inline int min_int(int a, int b)
75 void fprime_from_bytes(uint8_t *n,
76 const uint8_t *x, size_t len,
77 const uint8_t *modulus)
79 const int preload_total = min_int(prime_msb(modulus) - 1, len << 3);
80 const int preload_bytes = preload_total >> 3;
81 const int preload_bits = preload_total & 7;
82 const int rbits = (len << 3) - preload_total;
85 memset(n, 0, FPRIME_SIZE);
87 for (i = 0; i < preload_bytes; i++)
88 n[i] = x[len - preload_bytes + i];
91 shift_n_bits(n, preload_bits);
92 n[0] |= x[len - preload_bytes - 1] >> (8 - preload_bits);
95 for (i = rbits - 1; i >= 0; i--) {
96 const uint8_t bit = (x[i >> 3] >> (i & 7)) & 1;
100 raw_try_sub(n, modulus);
104 void fprime_select(uint8_t *dst,
105 const uint8_t *zero, const uint8_t *one,
108 const uint8_t mask = -condition;
111 for (i = 0; i < FPRIME_SIZE; i++)
112 dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
115 void fprime_add(uint8_t *r, const uint8_t *a, const uint8_t *modulus)
118 raw_try_sub(r, modulus);
121 void fprime_mul(uint8_t *r, const uint8_t *a, const uint8_t *b,
122 const uint8_t *modulus)
126 memset(r, 0, FPRIME_SIZE);
128 for (i = prime_msb(modulus); i >= 0; i--) {
129 const uint8_t bit = (b[i >> 3] >> (i & 7)) & 1;
130 uint8_t plusa[FPRIME_SIZE];
133 raw_try_sub(r, modulus);
135 fprime_copy(plusa, r);
136 fprime_add(plusa, a, modulus);
138 fprime_select(r, r, plusa, bit);