fprime.c

   1 /* Arithmetic in prime fields
   2  * Daniel Beer <dlbeer@gmail.com>, 10 Jan 2014
   3  *
   4  * This file is in the public domain.
   5  */
   6
   7 #include "fprime.h"
   8
   9 static void raw_add(uint8_t *x, const uint8_t *p)
  10 {
  11         uint16_t c = 0;
  12         int i;
  13
  14         for (i = 0; i < FPRIME_SIZE; i++) {
  15                 c += ((uint16_t)x[i]) + ((uint16_t)p[i]);
  16                 x[i] = c;
  17                 c >>= 8;
  18         }
  19 }
  20
  21 static void raw_try_sub(uint8_t *x, const uint8_t *p)
  22 {
  23         uint8_t minusp[FPRIME_SIZE];
  24         uint16_t c = 0;
  25         int i;
  26
  27         for (i = 0; i < FPRIME_SIZE; i++) {
  28                 c = ((uint16_t)x[i]) - ((uint16_t)p[i]) - c;
  29                 minusp[i] = c;
  30                 c = (c >> 8) & 1;
  31         }
  32
  33         fprime_select(x, minusp, x, c);
  34 }
  35
  36 /* Warning: this function is variable-time */
  37 static int prime_msb(const uint8_t *p)
  38 {
  39         int i;
  40         uint8_t x;
  41
  42         for (i = FPRIME_SIZE - 1; i >= 0; i--)
  43                 if (p[i])
  44                         break;
  45
  46         x = p[i];
  47         i <<= 3;
  48
  49         while (x) {
  50                 x >>= 1;
  51                 i++;
  52         }
  53
  54         return i - 1;
  55 }
  56
  57 /* Warning: this function may be variable-time in the argument n */
  58 static void shift_n_bits(uint8_t *x, int n)
  59 {
  60         uint16_t c = 0;
  61         int i;
  62
  63         for (i = 0; i < FPRIME_SIZE; i++) {
  64                 c |= ((uint16_t)x[i]) << n;
  65                 x[i] = c;
  66                 c >>= 8;
  67         }
  68 }
  69
  70 static inline int min_int(int a, int b)
  71 {
  72         return a < b ? a : b;
  73 }
  74
  75 void fprime_from_bytes(uint8_t *n,
  76                        const uint8_t *x, size_t len,
  77                        const uint8_t *modulus)
  78 {
  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;
  83         int i;
  84
  85         memset(n, 0, FPRIME_SIZE);
  86
  87         for (i = 0; i < preload_bytes; i++)
  88                 n[i] = x[len - preload_bytes + i];
  89
  90         if (preload_bits) {
  91                 shift_n_bits(n, preload_bits);
  92                 n[0] |= x[len - preload_bytes - 1] >> (8 - preload_bits);
  93         }
  94
  95         for (i = rbits - 1; i >= 0; i--) {
  96                 const uint8_t bit = (x[i >> 3] >> (i & 7)) & 1;
  97
  98                 shift_n_bits(n, 1);
  99                 n[0] |= bit;
 100                 raw_try_sub(n, modulus);
 101         }
 102 }
 103
 104 void fprime_select(uint8_t *dst,
 105                    const uint8_t *zero, const uint8_t *one,
 106                    uint8_t condition)
 107 {
 108         const uint8_t mask = -condition;
 109         int i;
 110
 111         for (i = 0; i < FPRIME_SIZE; i++)
 112                 dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
 113 }
 114
 115 void fprime_add(uint8_t *r, const uint8_t *a, const uint8_t *modulus)
 116 {
 117         raw_add(r, a);
 118         raw_try_sub(r, modulus);
 119 }
 120
 121 void fprime_mul(uint8_t *r, const uint8_t *a, const uint8_t *b,
 122                 const uint8_t *modulus)
 123 {
 124         int i;
 125
 126         memset(r, 0, FPRIME_SIZE);
 127
 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];
 131
 132                 shift_n_bits(r, 1);
 133                 raw_try_sub(r, modulus);
 134
 135                 fprime_copy(plusa, r);
 136                 fprime_add(plusa, a, modulus);
 137
 138                 fprime_select(r, r, plusa, bit);
 139         }
 140 }