Home | History | Annotate | Download | only in mpi
      1 /* ***** BEGIN LICENSE BLOCK *****
      2  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
      3  *
      4  * The contents of this file are subject to the Mozilla Public License Version
      5  * 1.1 (the "License"); you may not use this file except in compliance with
      6  * the License. You may obtain a copy of the License at
      7  * http://www.mozilla.org/MPL/
      8  *
      9  * Software distributed under the License is distributed on an "AS IS" basis,
     10  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
     11  * for the specific language governing rights and limitations under the
     12  * License.
     13  *
     14  * The Original Code is the Netscape security libraries.
     15  *
     16  * The Initial Developer of the Original Code is
     17  * Netscape Communications Corporation.
     18  * Portions created by the Initial Developer are Copyright (C) 2000
     19  * the Initial Developer. All Rights Reserved.
     20  *
     21  * Contributor(s):
     22  *   Sheueling Chang Shantz <sheueling.chang (at) sun.com>,
     23  *   Stephen Fung <stephen.fung (at) sun.com>, and
     24  *   Douglas Stebila <douglas (at) stebila.ca> of Sun Laboratories.
     25  *
     26  * Alternatively, the contents of this file may be used under the terms of
     27  * either the GNU General Public License Version 2 or later (the "GPL"), or
     28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
     29  * in which case the provisions of the GPL or the LGPL are applicable instead
     30  * of those above. If you wish to allow use of your version of this file only
     31  * under the terms of either the GPL or the LGPL, and not to allow others to
     32  * use your version of this file under the terms of the MPL, indicate your
     33  * decision by deleting the provisions above and replace them with the notice
     34  * and other provisions required by the GPL or the LGPL. If you do not delete
     35  * the provisions above, a recipient may use your version of this file under
     36  * the terms of any one of the MPL, the GPL or the LGPL.
     37  *
     38  * ***** END LICENSE BLOCK ***** */
     39 /*
     40  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
     41  * Use is subject to license terms.
     42  *
     43  * Sun elects to use this software under the MPL license.
     44  */
     45 
     46 #pragma ident	"%Z%%M%	%I%	%E% SMI"
     47 
     48 /* $Id: mpmontg.c,v 1.20 2006/08/29 02:41:38 nelson%bolyard.com Exp $ */
     49 
     50 /* This file implements moduluar exponentiation using Montgomery's
     51  * method for modular reduction.  This file implements the method
     52  * described as "Improvement 1" in the paper "A Cryptogrpahic Library for
     53  * the Motorola DSP56000" by Stephen R. Dusse' and Burton S. Kaliski Jr.
     54  * published in "Advances in Cryptology: Proceedings of EUROCRYPT '90"
     55  * "Lecture Notes in Computer Science" volume 473, 1991, pg 230-244,
     56  * published by Springer Verlag.
     57  */
     58 
     59 #define MP_USING_CACHE_SAFE_MOD_EXP 1
     60 #ifndef _KERNEL
     61 #include <string.h>
     62 #include <stddef.h> /* ptrdiff_t */
     63 #endif
     64 #include "mpi-priv.h"
     65 #include "mplogic.h"
     66 #include "mpprime.h"
     67 #ifdef MP_USING_MONT_MULF
     68 #include "montmulf.h"
     69 #endif
     70 
     71 /* if MP_CHAR_STORE_SLOW is defined, we  */
     72 /* need to know endianness of this platform. */
     73 #ifdef MP_CHAR_STORE_SLOW
     74 #if !defined(MP_IS_BIG_ENDIAN) && !defined(MP_IS_LITTLE_ENDIAN)
     75 #error "You must define MP_IS_BIG_ENDIAN or MP_IS_LITTLE_ENDIAN\n" \
     76        "  if you define MP_CHAR_STORE_SLOW."
     77 #endif
     78 #endif
     79 
     80 #ifndef STATIC
     81 #define STATIC
     82 #endif
     83 
     84 #define MAX_ODD_INTS    32   /* 2 ** (WINDOW_BITS - 1) */
     85 
     86 #ifndef _KERNEL
     87 #if defined(_WIN32_WCE)
     88 #define ABORT  res = MP_UNDEF; goto CLEANUP
     89 #else
     90 #define ABORT abort()
     91 #endif
     92 #else
     93 #define ABORT  res = MP_UNDEF; goto CLEANUP
     94 #endif /* _KERNEL */
     95 
     96 /* computes T = REDC(T), 2^b == R */
     97 mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm)
     98 {
     99   mp_err res;
    100   mp_size i;
    101 
    102   i = MP_USED(T) + MP_USED(&mmm->N) + 2;
    103   MP_CHECKOK( s_mp_pad(T, i) );
    104   for (i = 0; i < MP_USED(&mmm->N); ++i ) {
    105     mp_digit m_i = MP_DIGIT(T, i) * mmm->n0prime;
    106     /* T += N * m_i * (MP_RADIX ** i); */
    107     MP_CHECKOK( s_mp_mul_d_add_offset(&mmm->N, m_i, T, i) );
    108   }
    109   s_mp_clamp(T);
    110 
    111   /* T /= R */
    112   s_mp_div_2d(T, mmm->b);
    113 
    114   if ((res = s_mp_cmp(T, &mmm->N)) >= 0) {
    115     /* T = T - N */
    116     MP_CHECKOK( s_mp_sub(T, &mmm->N) );
    117 #ifdef DEBUG
    118     if ((res = mp_cmp(T, &mmm->N)) >= 0) {
    119       res = MP_UNDEF;
    120       goto CLEANUP;
    121     }
    122 #endif
    123   }
    124   res = MP_OKAY;
    125 CLEANUP:
    126   return res;
    127 }
    128 
    129 #if !defined(MP_ASSEMBLY_MUL_MONT) && !defined(MP_MONT_USE_MP_MUL)
    130 mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c,
    131 	           mp_mont_modulus *mmm)
    132 {
    133   mp_digit *pb;
    134   mp_digit m_i;
    135   mp_err   res;
    136   mp_size  ib;
    137   mp_size  useda, usedb;
    138 
    139   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
    140 
    141   if (MP_USED(a) < MP_USED(b)) {
    142     const mp_int *xch = b;	/* switch a and b, to do fewer outer loops */
    143     b = a;
    144     a = xch;
    145   }
    146 
    147   MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
    148   ib = MP_USED(a) + MP_MAX(MP_USED(b), MP_USED(&mmm->N)) + 2;
    149   if((res = s_mp_pad(c, ib)) != MP_OKAY)
    150     goto CLEANUP;
    151 
    152   useda = MP_USED(a);
    153   pb = MP_DIGITS(b);
    154   s_mpv_mul_d(MP_DIGITS(a), useda, *pb++, MP_DIGITS(c));
    155   s_mp_setz(MP_DIGITS(c) + useda + 1, ib - (useda + 1));
    156   m_i = MP_DIGIT(c, 0) * mmm->n0prime;
    157   s_mp_mul_d_add_offset(&mmm->N, m_i, c, 0);
    158 
    159   /* Outer loop:  Digits of b */
    160   usedb = MP_USED(b);
    161   for (ib = 1; ib < usedb; ib++) {
    162     mp_digit b_i    = *pb++;
    163 
    164     /* Inner product:  Digits of a */
    165     if (b_i)
    166       s_mpv_mul_d_add_prop(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib);
    167     m_i = MP_DIGIT(c, ib) * mmm->n0prime;
    168     s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
    169   }
    170   if (usedb < MP_USED(&mmm->N)) {
    171     for (usedb = MP_USED(&mmm->N); ib < usedb; ++ib ) {
    172       m_i = MP_DIGIT(c, ib) * mmm->n0prime;
    173       s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
    174     }
    175   }
    176   s_mp_clamp(c);
    177   s_mp_div_2d(c, mmm->b);
    178   if (s_mp_cmp(c, &mmm->N) >= 0) {
    179     MP_CHECKOK( s_mp_sub(c, &mmm->N) );
    180   }
    181   res = MP_OKAY;
    182 
    183 CLEANUP:
    184   return res;
    185 }
    186 #endif
    187