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
);