/* Copyright (c) 2018, Google Inc. * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include <openssl/bn.h> #include <assert.h> #include "internal.h" // The following functions use a Barrett reduction variant to avoid leaking the // numerator. See http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html // // We use 32-bit numerator and 16-bit divisor for simplicity. This allows // computing |m| and |q| without architecture-specific code. // mod_u16 returns |n| mod |d|. |p| and |m| are the "magic numbers" for |d| (see // reference). For proof of correctness in Coq, see // https://github.com/davidben/fiat-crypto/blob/barrett/src/Arithmetic/BarrettReduction/RidiculousFish.v // Note the Coq version of |mod_u16| additionally includes the computation of // |p| and |m| from |bn_mod_u16_consttime| below. static uint16_t mod_u16(uint32_t n, uint16_t d, uint32_t p, uint32_t m) { … } // shift_and_add_mod_u16 returns |r| * 2^32 + |a| mod |d|. |p| and |m| are the // "magic numbers" for |d| (see reference). static uint16_t shift_and_add_mod_u16(uint16_t r, uint32_t a, uint16_t d, uint32_t p, uint32_t m) { … } uint16_t bn_mod_u16_consttime(const BIGNUM *bn, uint16_t d) { … }