usr/src/common/mpi/mpmontg.c

   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@sun.com>,
  23  *   Stephen Fung <stephen.fung@sun.com>, and
  24  *   Douglas Stebila <douglas@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