/* Copyright 2016 Brian Smith. * * 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" #include "../../internal.h" static uint64_t bn_neg_inv_mod_r_u64(uint64_t n); static_assert; static_assert; // LG_LITTLE_R is log_2(r). #define LG_LITTLE_R … uint64_t bn_mont_n0(const BIGNUM *n) { … } // bn_neg_inv_r_mod_n_u64 calculates the -1/n mod r; i.e. it calculates |v| // such that u*r - v*n == 1. |r| is the constant defined in |bn_mont_n0|. |n| // must be odd. // // This is derived from |xbinGCD| in Henry S. Warren, Jr.'s "Montgomery // Multiplication" (http://www.hackersdelight.org/MontgomeryMultiplication.pdf). // It is very similar to the MODULAR-INVERSE function in Stephen R. Dussé's and // Burton S. Kaliski Jr.'s "A Cryptographic Library for the Motorola DSP56000" // (http://link.springer.com/chapter/10.1007%2F3-540-46877-3_21). // // This is inspired by Joppe W. Bos's "Constant Time Modular Inversion" // (http://www.joppebos.com/files/CTInversion.pdf) so that the inversion is // constant-time with respect to |n|. We assume uint64_t additions, // subtractions, shifts, and bitwise operations are all constant time, which // may be a large leap of faith on 32-bit targets. We avoid division and // multiplication, which tend to be the most problematic in terms of timing // leaks. // // Most GCD implementations return values such that |u*r + v*n == 1|, so the // caller would have to negate the resultant |v| for the purpose of Montgomery // multiplication. This implementation does the negation implicitly by doing // the computations as a difference instead of a sum. static uint64_t bn_neg_inv_mod_r_u64(uint64_t n) { … } int bn_mont_ctx_set_RR_consttime(BN_MONT_CTX *mont, BN_CTX *ctx) { … }