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