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