| /* Copyright (C) 1995-1998 Eric Young ([email protected]) |
| * All rights reserved. |
| * |
| * This package is an SSL implementation written |
| * by Eric Young ([email protected]). |
| * The implementation was written so as to conform with Netscapes SSL. |
| * |
| * This library is free for commercial and non-commercial use as long as |
| * the following conditions are aheared to. The following conditions |
| * apply to all code found in this distribution, be it the RC4, RSA, |
| * lhash, DES, etc., code; not just the SSL code. The SSL documentation |
| * included with this distribution is covered by the same copyright terms |
| * except that the holder is Tim Hudson ([email protected]). |
| * |
| * Copyright remains Eric Young's, and as such any Copyright notices in |
| * the code are not to be removed. |
| * If this package is used in a product, Eric Young should be given attribution |
| * as the author of the parts of the library used. |
| * This can be in the form of a textual message at program startup or |
| * in documentation (online or textual) provided with the package. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. All advertising materials mentioning features or use of this software |
| * must display the following acknowledgement: |
| * "This product includes cryptographic software written by |
| * Eric Young ([email protected])" |
| * The word 'cryptographic' can be left out if the rouines from the library |
| * being used are not cryptographic related :-). |
| * 4. If you include any Windows specific code (or a derivative thereof) from |
| * the apps directory (application code) you must include an acknowledgement: |
| * "This product includes software written by Tim Hudson ([email protected])" |
| * |
| * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
| * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
| * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| * SUCH DAMAGE. |
| * |
| * The licence and distribution terms for any publically available version or |
| * derivative of this code cannot be changed. i.e. this code cannot simply be |
| * copied and put under another distribution licence |
| * [including the GNU Public Licence.] |
| */ |
| /* ==================================================================== |
| * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * |
| * 3. All advertising materials mentioning features or use of this |
| * software must display the following acknowledgment: |
| * "This product includes software developed by the OpenSSL Project |
| * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
| * |
| * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
| * endorse or promote products derived from this software without |
| * prior written permission. For written permission, please contact |
| * [email protected]. |
| * |
| * 5. Products derived from this software may not be called "OpenSSL" |
| * nor may "OpenSSL" appear in their names without prior written |
| * permission of the OpenSSL Project. |
| * |
| * 6. Redistributions of any form whatsoever must retain the following |
| * acknowledgment: |
| * "This product includes software developed by the OpenSSL Project |
| * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
| * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
| * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| * OF THE POSSIBILITY OF SUCH DAMAGE. |
| * ==================================================================== |
| * |
| * This product includes cryptographic software written by Eric Young |
| * ([email protected]). This product includes software written by Tim |
| * Hudson ([email protected]). */ |
| |
| #include "internal.h" |
| #include "../../internal.h" |
| |
| #include "../../limbs/limbs.h" |
| #include "../../limbs/limbs.inl" |
| |
| OPENSSL_STATIC_ASSERT(BN_MONT_CTX_N0_LIMBS == 1 || BN_MONT_CTX_N0_LIMBS == 2, |
| "BN_MONT_CTX_N0_LIMBS value is invalid"); |
| OPENSSL_STATIC_ASSERT( |
| sizeof(BN_ULONG) * BN_MONT_CTX_N0_LIMBS == sizeof(uint64_t), |
| "uint64_t is insufficient precision for n0"); |
| |
| int bn_from_montgomery_in_place(BN_ULONG r[], size_t num_r, BN_ULONG a[], |
| size_t num_a, const BN_ULONG n[], |
| size_t num_n, |
| const BN_ULONG n0_[BN_MONT_CTX_N0_LIMBS]) { |
| if (num_n == 0 || num_r != num_n || num_a != 2 * num_n) { |
| return 0; |
| } |
| |
| // Add multiples of |n| to |r| until R = 2^(nl * BN_BITS2) divides it. On |
| // input, we had |r| < |n| * R, so now |r| < 2 * |n| * R. Note that |r| |
| // includes |carry| which is stored separately. |
| BN_ULONG n0 = n0_[0]; |
| BN_ULONG carry = 0; |
| for (size_t i = 0; i < num_n; i++) { |
| BN_ULONG v = limbs_mul_add_limb(a + i, n, a[i] * n0, num_n); |
| v += carry + a[i + num_n]; |
| carry |= (v != a[i + num_n]); |
| carry &= (v <= a[i + num_n]); |
| a[i + num_n] = v; |
| } |
| |
| // Shift |num_n| words to divide by R. We have |a| < 2 * |n|. Note that |a| |
| // includes |carry| which is stored separately. |
| a += num_n; |
| |
| // |a| thus requires at most one additional subtraction |n| to be reduced. |
| // Subtract |n| and select the answer in constant time. |
| BN_ULONG v = limbs_sub(r, a, n, num_n) - carry; |
| // |v| is one if |a| - |n| underflowed or zero if it did not. Note |v| cannot |
| // be -1. That would imply the subtraction did not fit in |num_n| words, and |
| // we know at most one subtraction is needed. |
| v = 0u - v; |
| for (size_t i = 0; i < num_n; i++) { |
| r[i] = constant_time_select_w(v, a[i], r[i]); |
| a[i] = 0; |
| } |
| return 1; |
| } |
