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 } 141
This page was automatically generated by LXR 0.3.1. • OpenWrt