1ebfedea0SLionel Sambuc /* crypto/engine/eng_rsax.c */
2ebfedea0SLionel Sambuc /* Copyright (c) 2010-2010 Intel Corp.
3ebfedea0SLionel Sambuc  *   Author: Vinodh.Gopal@intel.com
4ebfedea0SLionel Sambuc  *           Jim Guilford
5ebfedea0SLionel Sambuc  *           Erdinc.Ozturk@intel.com
6ebfedea0SLionel Sambuc  *           Maxim.Perminov@intel.com
7ebfedea0SLionel Sambuc  *           Ying.Huang@intel.com
8ebfedea0SLionel Sambuc  *
9ebfedea0SLionel Sambuc  * More information about algorithm used can be found at:
10ebfedea0SLionel Sambuc  *   http://www.cse.buffalo.edu/srds2009/escs2009_submission_Gopal.pdf
11ebfedea0SLionel Sambuc  */
12ebfedea0SLionel Sambuc /* ====================================================================
13ebfedea0SLionel Sambuc  * Copyright (c) 1999-2001 The OpenSSL Project.  All rights reserved.
14ebfedea0SLionel Sambuc  *
15ebfedea0SLionel Sambuc  * Redistribution and use in source and binary forms, with or without
16ebfedea0SLionel Sambuc  * modification, are permitted provided that the following conditions
17ebfedea0SLionel Sambuc  * are met:
18ebfedea0SLionel Sambuc  *
19ebfedea0SLionel Sambuc  * 1. Redistributions of source code must retain the above copyright
20ebfedea0SLionel Sambuc  *    notice, this list of conditions and the following disclaimer.
21ebfedea0SLionel Sambuc  *
22ebfedea0SLionel Sambuc  * 2. Redistributions in binary form must reproduce the above copyright
23ebfedea0SLionel Sambuc  *    notice, this list of conditions and the following disclaimer in
24ebfedea0SLionel Sambuc  *    the documentation and/or other materials provided with the
25ebfedea0SLionel Sambuc  *    distribution.
26ebfedea0SLionel Sambuc  *
27ebfedea0SLionel Sambuc  * 3. All advertising materials mentioning features or use of this
28ebfedea0SLionel Sambuc  *    software must display the following acknowledgment:
29ebfedea0SLionel Sambuc  *    "This product includes software developed by the OpenSSL Project
30ebfedea0SLionel Sambuc  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
31ebfedea0SLionel Sambuc  *
32ebfedea0SLionel Sambuc  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
33ebfedea0SLionel Sambuc  *    endorse or promote products derived from this software without
34ebfedea0SLionel Sambuc  *    prior written permission. For written permission, please contact
35ebfedea0SLionel Sambuc  *    licensing@OpenSSL.org.
36ebfedea0SLionel Sambuc  *
37ebfedea0SLionel Sambuc  * 5. Products derived from this software may not be called "OpenSSL"
38ebfedea0SLionel Sambuc  *    nor may "OpenSSL" appear in their names without prior written
39ebfedea0SLionel Sambuc  *    permission of the OpenSSL Project.
40ebfedea0SLionel Sambuc  *
41ebfedea0SLionel Sambuc  * 6. Redistributions of any form whatsoever must retain the following
42ebfedea0SLionel Sambuc  *    acknowledgment:
43ebfedea0SLionel Sambuc  *    "This product includes software developed by the OpenSSL Project
44ebfedea0SLionel Sambuc  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
45ebfedea0SLionel Sambuc  *
46ebfedea0SLionel Sambuc  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
47ebfedea0SLionel Sambuc  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48ebfedea0SLionel Sambuc  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
49ebfedea0SLionel Sambuc  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
50ebfedea0SLionel Sambuc  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
51ebfedea0SLionel Sambuc  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
52ebfedea0SLionel Sambuc  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
53ebfedea0SLionel Sambuc  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
54ebfedea0SLionel Sambuc  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
55ebfedea0SLionel Sambuc  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
56ebfedea0SLionel Sambuc  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
57ebfedea0SLionel Sambuc  * OF THE POSSIBILITY OF SUCH DAMAGE.
58ebfedea0SLionel Sambuc  * ====================================================================
59ebfedea0SLionel Sambuc  *
60ebfedea0SLionel Sambuc  * This product includes cryptographic software written by Eric Young
61ebfedea0SLionel Sambuc  * (eay@cryptsoft.com).  This product includes software written by Tim
62ebfedea0SLionel Sambuc  * Hudson (tjh@cryptsoft.com).
63ebfedea0SLionel Sambuc  */
64ebfedea0SLionel Sambuc 
65ebfedea0SLionel Sambuc #include <openssl/opensslconf.h>
66ebfedea0SLionel Sambuc 
67ebfedea0SLionel Sambuc #include <stdio.h>
68ebfedea0SLionel Sambuc #include <string.h>
69ebfedea0SLionel Sambuc #include <openssl/crypto.h>
70ebfedea0SLionel Sambuc #include <openssl/buffer.h>
71ebfedea0SLionel Sambuc #include <openssl/engine.h>
72ebfedea0SLionel Sambuc #ifndef OPENSSL_NO_RSA
73ebfedea0SLionel Sambuc # include <openssl/rsa.h>
74ebfedea0SLionel Sambuc #endif
75ebfedea0SLionel Sambuc #include <openssl/bn.h>
76ebfedea0SLionel Sambuc #include <openssl/err.h>
77ebfedea0SLionel Sambuc 
78ebfedea0SLionel Sambuc /* RSAX is available **ONLY* on x86_64 CPUs */
79ebfedea0SLionel Sambuc #undef COMPILE_RSAX
80ebfedea0SLionel Sambuc 
81ebfedea0SLionel Sambuc #if (defined(__x86_64) || defined(__x86_64__) || \
82ebfedea0SLionel Sambuc      defined(_M_AMD64) || defined (_M_X64)) && !defined(OPENSSL_NO_ASM)
83ebfedea0SLionel Sambuc # define COMPILE_RSAX
84ebfedea0SLionel Sambuc static ENGINE *ENGINE_rsax(void);
85ebfedea0SLionel Sambuc #endif
86ebfedea0SLionel Sambuc 
ENGINE_load_rsax(void)87ebfedea0SLionel Sambuc void ENGINE_load_rsax(void)
88ebfedea0SLionel Sambuc {
89ebfedea0SLionel Sambuc /* On non-x86 CPUs it just returns. */
90ebfedea0SLionel Sambuc #ifdef COMPILE_RSAX
91ebfedea0SLionel Sambuc     ENGINE *toadd = ENGINE_rsax();
92*0a6a1f1dSLionel Sambuc     if (!toadd)
93*0a6a1f1dSLionel Sambuc         return;
94ebfedea0SLionel Sambuc     ENGINE_add(toadd);
95ebfedea0SLionel Sambuc     ENGINE_free(toadd);
96ebfedea0SLionel Sambuc     ERR_clear_error();
97ebfedea0SLionel Sambuc #endif
98ebfedea0SLionel Sambuc }
99ebfedea0SLionel Sambuc 
100ebfedea0SLionel Sambuc #ifdef COMPILE_RSAX
101ebfedea0SLionel Sambuc # define E_RSAX_LIB_NAME "rsax engine"
102ebfedea0SLionel Sambuc 
103ebfedea0SLionel Sambuc static int e_rsax_destroy(ENGINE *e);
104ebfedea0SLionel Sambuc static int e_rsax_init(ENGINE *e);
105ebfedea0SLionel Sambuc static int e_rsax_finish(ENGINE *e);
106ebfedea0SLionel Sambuc static int e_rsax_ctrl(ENGINE *e, int cmd, long i, void *p, void (*f) (void));
107ebfedea0SLionel Sambuc 
108ebfedea0SLionel Sambuc # ifndef OPENSSL_NO_RSA
109ebfedea0SLionel Sambuc /* RSA stuff */
110*0a6a1f1dSLionel Sambuc static int e_rsax_rsa_mod_exp(BIGNUM *r, const BIGNUM *I, RSA *rsa,
111*0a6a1f1dSLionel Sambuc                               BN_CTX *ctx);
112ebfedea0SLionel Sambuc static int e_rsax_rsa_finish(RSA *r);
113ebfedea0SLionel Sambuc # endif
114ebfedea0SLionel Sambuc 
115ebfedea0SLionel Sambuc static const ENGINE_CMD_DEFN e_rsax_cmd_defns[] = {
116ebfedea0SLionel Sambuc     {0, NULL, NULL, 0}
117ebfedea0SLionel Sambuc };
118ebfedea0SLionel Sambuc 
119ebfedea0SLionel Sambuc # ifndef OPENSSL_NO_RSA
120ebfedea0SLionel Sambuc /* Our internal RSA_METHOD that we provide pointers to */
121*0a6a1f1dSLionel Sambuc static RSA_METHOD e_rsax_rsa = {
122ebfedea0SLionel Sambuc     "Intel RSA-X method",
123ebfedea0SLionel Sambuc     NULL,
124ebfedea0SLionel Sambuc     NULL,
125ebfedea0SLionel Sambuc     NULL,
126ebfedea0SLionel Sambuc     NULL,
127ebfedea0SLionel Sambuc     e_rsax_rsa_mod_exp,
128ebfedea0SLionel Sambuc     NULL,
129ebfedea0SLionel Sambuc     NULL,
130ebfedea0SLionel Sambuc     e_rsax_rsa_finish,
131ebfedea0SLionel Sambuc     RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE,
132ebfedea0SLionel Sambuc     NULL,
133ebfedea0SLionel Sambuc     NULL,
134ebfedea0SLionel Sambuc     NULL
135ebfedea0SLionel Sambuc };
136ebfedea0SLionel Sambuc # endif
137ebfedea0SLionel Sambuc 
138ebfedea0SLionel Sambuc /* Constants used when creating the ENGINE */
139ebfedea0SLionel Sambuc static const char *engine_e_rsax_id = "rsax";
140ebfedea0SLionel Sambuc static const char *engine_e_rsax_name = "RSAX engine support";
141ebfedea0SLionel Sambuc 
142ebfedea0SLionel Sambuc /* This internal function is used by ENGINE_rsax() */
bind_helper(ENGINE * e)143ebfedea0SLionel Sambuc static int bind_helper(ENGINE *e)
144ebfedea0SLionel Sambuc {
145ebfedea0SLionel Sambuc # ifndef OPENSSL_NO_RSA
146ebfedea0SLionel Sambuc     const RSA_METHOD *meth1;
147ebfedea0SLionel Sambuc # endif
148ebfedea0SLionel Sambuc     if (!ENGINE_set_id(e, engine_e_rsax_id) ||
149ebfedea0SLionel Sambuc         !ENGINE_set_name(e, engine_e_rsax_name) ||
150ebfedea0SLionel Sambuc # ifndef OPENSSL_NO_RSA
151ebfedea0SLionel Sambuc         !ENGINE_set_RSA(e, &e_rsax_rsa) ||
152ebfedea0SLionel Sambuc # endif
153ebfedea0SLionel Sambuc         !ENGINE_set_destroy_function(e, e_rsax_destroy) ||
154ebfedea0SLionel Sambuc         !ENGINE_set_init_function(e, e_rsax_init) ||
155ebfedea0SLionel Sambuc         !ENGINE_set_finish_function(e, e_rsax_finish) ||
156ebfedea0SLionel Sambuc         !ENGINE_set_ctrl_function(e, e_rsax_ctrl) ||
157ebfedea0SLionel Sambuc         !ENGINE_set_cmd_defns(e, e_rsax_cmd_defns))
158ebfedea0SLionel Sambuc         return 0;
159ebfedea0SLionel Sambuc 
160ebfedea0SLionel Sambuc # ifndef OPENSSL_NO_RSA
161ebfedea0SLionel Sambuc     meth1 = RSA_PKCS1_SSLeay();
162ebfedea0SLionel Sambuc     e_rsax_rsa.rsa_pub_enc = meth1->rsa_pub_enc;
163ebfedea0SLionel Sambuc     e_rsax_rsa.rsa_pub_dec = meth1->rsa_pub_dec;
164ebfedea0SLionel Sambuc     e_rsax_rsa.rsa_priv_enc = meth1->rsa_priv_enc;
165ebfedea0SLionel Sambuc     e_rsax_rsa.rsa_priv_dec = meth1->rsa_priv_dec;
166ebfedea0SLionel Sambuc     e_rsax_rsa.bn_mod_exp = meth1->bn_mod_exp;
167ebfedea0SLionel Sambuc # endif
168ebfedea0SLionel Sambuc     return 1;
169ebfedea0SLionel Sambuc }
170ebfedea0SLionel Sambuc 
ENGINE_rsax(void)171ebfedea0SLionel Sambuc static ENGINE *ENGINE_rsax(void)
172ebfedea0SLionel Sambuc {
173ebfedea0SLionel Sambuc     ENGINE *ret = ENGINE_new();
174ebfedea0SLionel Sambuc     if (!ret)
175ebfedea0SLionel Sambuc         return NULL;
176*0a6a1f1dSLionel Sambuc     if (!bind_helper(ret)) {
177ebfedea0SLionel Sambuc         ENGINE_free(ret);
178ebfedea0SLionel Sambuc         return NULL;
179ebfedea0SLionel Sambuc     }
180ebfedea0SLionel Sambuc     return ret;
181ebfedea0SLionel Sambuc }
182ebfedea0SLionel Sambuc 
183ebfedea0SLionel Sambuc # ifndef OPENSSL_NO_RSA
184ebfedea0SLionel Sambuc /* Used to attach our own key-data to an RSA structure */
185ebfedea0SLionel Sambuc static int rsax_ex_data_idx = -1;
186ebfedea0SLionel Sambuc # endif
187ebfedea0SLionel Sambuc 
e_rsax_destroy(ENGINE * e)188ebfedea0SLionel Sambuc static int e_rsax_destroy(ENGINE *e)
189ebfedea0SLionel Sambuc {
190ebfedea0SLionel Sambuc     return 1;
191ebfedea0SLionel Sambuc }
192ebfedea0SLionel Sambuc 
193ebfedea0SLionel Sambuc /* (de)initialisation functions. */
e_rsax_init(ENGINE * e)194ebfedea0SLionel Sambuc static int e_rsax_init(ENGINE *e)
195ebfedea0SLionel Sambuc {
196ebfedea0SLionel Sambuc # ifndef OPENSSL_NO_RSA
197ebfedea0SLionel Sambuc     if (rsax_ex_data_idx == -1)
198*0a6a1f1dSLionel Sambuc         rsax_ex_data_idx = RSA_get_ex_new_index(0, NULL, NULL, NULL, NULL);
199ebfedea0SLionel Sambuc # endif
200ebfedea0SLionel Sambuc     if (rsax_ex_data_idx == -1)
201ebfedea0SLionel Sambuc         return 0;
202ebfedea0SLionel Sambuc     return 1;
203ebfedea0SLionel Sambuc }
204ebfedea0SLionel Sambuc 
e_rsax_finish(ENGINE * e)205ebfedea0SLionel Sambuc static int e_rsax_finish(ENGINE *e)
206ebfedea0SLionel Sambuc {
207ebfedea0SLionel Sambuc     return 1;
208ebfedea0SLionel Sambuc }
209ebfedea0SLionel Sambuc 
e_rsax_ctrl(ENGINE * e,int cmd,long i,void * p,void (* f)(void))210ebfedea0SLionel Sambuc static int e_rsax_ctrl(ENGINE *e, int cmd, long i, void *p, void (*f) (void))
211ebfedea0SLionel Sambuc {
212ebfedea0SLionel Sambuc     int to_return = 1;
213ebfedea0SLionel Sambuc 
214*0a6a1f1dSLionel Sambuc     switch (cmd) {
215ebfedea0SLionel Sambuc         /* The command isn't understood by this engine */
216ebfedea0SLionel Sambuc     default:
217ebfedea0SLionel Sambuc         to_return = 0;
218ebfedea0SLionel Sambuc         break;
219ebfedea0SLionel Sambuc     }
220ebfedea0SLionel Sambuc 
221ebfedea0SLionel Sambuc     return to_return;
222ebfedea0SLionel Sambuc }
223ebfedea0SLionel Sambuc 
224ebfedea0SLionel Sambuc # ifndef OPENSSL_NO_RSA
225ebfedea0SLionel Sambuc 
226ebfedea0SLionel Sambuc #  ifdef _WIN32
227ebfedea0SLionel Sambuc typedef unsigned __int64 UINT64;
228ebfedea0SLionel Sambuc #  else
229ebfedea0SLionel Sambuc typedef unsigned long long UINT64;
230ebfedea0SLionel Sambuc #  endif
231ebfedea0SLionel Sambuc typedef unsigned short UINT16;
232ebfedea0SLionel Sambuc 
233*0a6a1f1dSLionel Sambuc /*
234*0a6a1f1dSLionel Sambuc  * Table t is interleaved in the following manner: The order in memory is
235*0a6a1f1dSLionel Sambuc  * t[0][0], t[0][1], ..., t[0][7], t[1][0], ... A particular 512-bit value is
236*0a6a1f1dSLionel Sambuc  * stored in t[][index] rather than the more normal t[index][]; i.e. the
237*0a6a1f1dSLionel Sambuc  * qwords of a particular entry in t are not adjacent in memory
238ebfedea0SLionel Sambuc  */
239ebfedea0SLionel Sambuc 
240ebfedea0SLionel Sambuc /* Init BIGNUM b from the interleaved UINT64 array */
241ebfedea0SLionel Sambuc static int interleaved_array_to_bn_512(BIGNUM *b, UINT64 *array);
242ebfedea0SLionel Sambuc 
243*0a6a1f1dSLionel Sambuc /*
244*0a6a1f1dSLionel Sambuc  * Extract array elements from BIGNUM b To set the whole array from b, call
245*0a6a1f1dSLionel Sambuc  * with n=8
246ebfedea0SLionel Sambuc  */
247*0a6a1f1dSLionel Sambuc static int bn_extract_to_array_512(const BIGNUM *b, unsigned int n,
248*0a6a1f1dSLionel Sambuc                                    UINT64 *array);
249ebfedea0SLionel Sambuc 
250ebfedea0SLionel Sambuc struct mod_ctx_512 {
251ebfedea0SLionel Sambuc     UINT64 t[8][8];
252ebfedea0SLionel Sambuc     UINT64 m[8];
253ebfedea0SLionel Sambuc     UINT64 m1[8];               /* 2^278 % m */
254ebfedea0SLionel Sambuc     UINT64 m2[8];               /* 2^640 % m */
255ebfedea0SLionel Sambuc     UINT64 k1[2];               /* (- 1/m) % 2^128 */
256ebfedea0SLionel Sambuc };
257ebfedea0SLionel Sambuc 
258ebfedea0SLionel Sambuc static int mod_exp_pre_compute_data_512(UINT64 *m, struct mod_ctx_512 *data);
259ebfedea0SLionel Sambuc 
260ebfedea0SLionel Sambuc void mod_exp_512(UINT64 *result, /* 512 bits, 8 qwords */
261ebfedea0SLionel Sambuc                  UINT64 *g,     /* 512 bits, 8 qwords */
262ebfedea0SLionel Sambuc                  UINT64 *exp,   /* 512 bits, 8 qwords */
263ebfedea0SLionel Sambuc                  struct mod_ctx_512 *data);
264ebfedea0SLionel Sambuc 
265*0a6a1f1dSLionel Sambuc typedef struct st_e_rsax_mod_ctx {
266ebfedea0SLionel Sambuc     UINT64 type;
267ebfedea0SLionel Sambuc     union {
268ebfedea0SLionel Sambuc         struct mod_ctx_512 b512;
269ebfedea0SLionel Sambuc     } ctx;
270ebfedea0SLionel Sambuc 
271ebfedea0SLionel Sambuc } E_RSAX_MOD_CTX;
272ebfedea0SLionel Sambuc 
e_rsax_get_ctx(RSA * rsa,int idx,BIGNUM * m)273ebfedea0SLionel Sambuc static E_RSAX_MOD_CTX *e_rsax_get_ctx(RSA *rsa, int idx, BIGNUM *m)
274ebfedea0SLionel Sambuc {
275ebfedea0SLionel Sambuc     E_RSAX_MOD_CTX *hptr;
276ebfedea0SLionel Sambuc 
277ebfedea0SLionel Sambuc     if (idx < 0 || idx > 2)
278ebfedea0SLionel Sambuc         return NULL;
279ebfedea0SLionel Sambuc 
280ebfedea0SLionel Sambuc     hptr = RSA_get_ex_data(rsa, rsax_ex_data_idx);
281ebfedea0SLionel Sambuc     if (!hptr) {
282ebfedea0SLionel Sambuc         hptr = OPENSSL_malloc(3 * sizeof(E_RSAX_MOD_CTX));
283*0a6a1f1dSLionel Sambuc         if (!hptr)
284*0a6a1f1dSLionel Sambuc             return NULL;
285ebfedea0SLionel Sambuc         hptr[2].type = hptr[1].type = hptr[0].type = 0;
286ebfedea0SLionel Sambuc         RSA_set_ex_data(rsa, rsax_ex_data_idx, hptr);
287ebfedea0SLionel Sambuc     }
288ebfedea0SLionel Sambuc 
289ebfedea0SLionel Sambuc     if (hptr[idx].type == (UINT64)BN_num_bits(m))
290ebfedea0SLionel Sambuc         return hptr + idx;
291ebfedea0SLionel Sambuc 
292ebfedea0SLionel Sambuc     if (BN_num_bits(m) == 512) {
293ebfedea0SLionel Sambuc         UINT64 _m[8];
294ebfedea0SLionel Sambuc         bn_extract_to_array_512(m, 8, _m);
295ebfedea0SLionel Sambuc         memset(&hptr[idx].ctx.b512, 0, sizeof(struct mod_ctx_512));
296ebfedea0SLionel Sambuc         mod_exp_pre_compute_data_512(_m, &hptr[idx].ctx.b512);
297ebfedea0SLionel Sambuc     }
298ebfedea0SLionel Sambuc 
299ebfedea0SLionel Sambuc     hptr[idx].type = BN_num_bits(m);
300ebfedea0SLionel Sambuc     return hptr + idx;
301ebfedea0SLionel Sambuc }
302ebfedea0SLionel Sambuc 
e_rsax_rsa_finish(RSA * rsa)303ebfedea0SLionel Sambuc static int e_rsax_rsa_finish(RSA *rsa)
304ebfedea0SLionel Sambuc {
305ebfedea0SLionel Sambuc     E_RSAX_MOD_CTX *hptr = RSA_get_ex_data(rsa, rsax_ex_data_idx);
306*0a6a1f1dSLionel Sambuc     if (hptr) {
307ebfedea0SLionel Sambuc         OPENSSL_free(hptr);
308ebfedea0SLionel Sambuc         RSA_set_ex_data(rsa, rsax_ex_data_idx, NULL);
309ebfedea0SLionel Sambuc     }
310ebfedea0SLionel Sambuc     if (rsa->_method_mod_n)
311ebfedea0SLionel Sambuc         BN_MONT_CTX_free(rsa->_method_mod_n);
312ebfedea0SLionel Sambuc     if (rsa->_method_mod_p)
313ebfedea0SLionel Sambuc         BN_MONT_CTX_free(rsa->_method_mod_p);
314ebfedea0SLionel Sambuc     if (rsa->_method_mod_q)
315ebfedea0SLionel Sambuc         BN_MONT_CTX_free(rsa->_method_mod_q);
316ebfedea0SLionel Sambuc     return 1;
317ebfedea0SLionel Sambuc }
318ebfedea0SLionel Sambuc 
e_rsax_bn_mod_exp(BIGNUM * r,const BIGNUM * g,const BIGNUM * e,const BIGNUM * m,BN_CTX * ctx,BN_MONT_CTX * in_mont,E_RSAX_MOD_CTX * rsax_mod_ctx)319ebfedea0SLionel Sambuc static int e_rsax_bn_mod_exp(BIGNUM *r, const BIGNUM *g, const BIGNUM *e,
320*0a6a1f1dSLionel Sambuc                              const BIGNUM *m, BN_CTX *ctx,
321*0a6a1f1dSLionel Sambuc                              BN_MONT_CTX *in_mont,
322*0a6a1f1dSLionel Sambuc                              E_RSAX_MOD_CTX *rsax_mod_ctx)
323ebfedea0SLionel Sambuc {
324ebfedea0SLionel Sambuc     if (rsax_mod_ctx && BN_get_flags(e, BN_FLG_CONSTTIME) != 0) {
325ebfedea0SLionel Sambuc         if (BN_num_bits(m) == 512) {
326ebfedea0SLionel Sambuc             UINT64 _r[8];
327ebfedea0SLionel Sambuc             UINT64 _g[8];
328ebfedea0SLionel Sambuc             UINT64 _e[8];
329ebfedea0SLionel Sambuc 
330ebfedea0SLionel Sambuc             /* Init the arrays from the BIGNUMs */
331ebfedea0SLionel Sambuc             bn_extract_to_array_512(g, 8, _g);
332ebfedea0SLionel Sambuc             bn_extract_to_array_512(e, 8, _e);
333ebfedea0SLionel Sambuc 
334ebfedea0SLionel Sambuc             mod_exp_512(_r, _g, _e, &rsax_mod_ctx->ctx.b512);
335ebfedea0SLionel Sambuc             /* Return the result in the BIGNUM */
336ebfedea0SLionel Sambuc             interleaved_array_to_bn_512(r, _r);
337ebfedea0SLionel Sambuc             return 1;
338ebfedea0SLionel Sambuc         }
339ebfedea0SLionel Sambuc     }
340ebfedea0SLionel Sambuc 
341ebfedea0SLionel Sambuc     return BN_mod_exp_mont(r, g, e, m, ctx, in_mont);
342ebfedea0SLionel Sambuc }
343ebfedea0SLionel Sambuc 
344*0a6a1f1dSLionel Sambuc /*
345*0a6a1f1dSLionel Sambuc  * Declares for the Intel CIAP 512-bit / CRT / 1024 bit RSA modular
346ebfedea0SLionel Sambuc  * exponentiation routine precalculations and a structure to hold the
347*0a6a1f1dSLionel Sambuc  * necessary values.  These files are meant to live in crypto/rsa/ in the
348*0a6a1f1dSLionel Sambuc  * target openssl.
349ebfedea0SLionel Sambuc  */
350ebfedea0SLionel Sambuc 
351ebfedea0SLionel Sambuc /*
352ebfedea0SLionel Sambuc  * Local method: extracts a piece from a BIGNUM, to fit it into
353ebfedea0SLionel Sambuc  * an array. Call with n=8 to extract an entire 512-bit BIGNUM
354ebfedea0SLionel Sambuc  */
bn_extract_to_array_512(const BIGNUM * b,unsigned int n,UINT64 * array)355*0a6a1f1dSLionel Sambuc static int bn_extract_to_array_512(const BIGNUM *b, unsigned int n,
356*0a6a1f1dSLionel Sambuc                                    UINT64 *array)
357ebfedea0SLionel Sambuc {
358ebfedea0SLionel Sambuc     int i;
359ebfedea0SLionel Sambuc     UINT64 tmp;
360ebfedea0SLionel Sambuc     unsigned char bn_buff[64];
361ebfedea0SLionel Sambuc     memset(bn_buff, 0, 64);
362ebfedea0SLionel Sambuc     if (BN_num_bytes(b) > 64) {
363ebfedea0SLionel Sambuc         printf("Can't support this byte size\n");
364*0a6a1f1dSLionel Sambuc         return 0;
365*0a6a1f1dSLionel Sambuc     }
366ebfedea0SLionel Sambuc     if (BN_num_bytes(b) != 0) {
367ebfedea0SLionel Sambuc         if (!BN_bn2bin(b, bn_buff + (64 - BN_num_bytes(b)))) {
368ebfedea0SLionel Sambuc             printf("Error's in bn2bin\n");
369ebfedea0SLionel Sambuc             /* We have to error, here */
370*0a6a1f1dSLionel Sambuc             return 0;
371*0a6a1f1dSLionel Sambuc         }
372*0a6a1f1dSLionel Sambuc     }
373ebfedea0SLionel Sambuc     while (n-- > 0) {
374ebfedea0SLionel Sambuc         array[n] = 0;
375ebfedea0SLionel Sambuc         for (i = 7; i >= 0; i--) {
376ebfedea0SLionel Sambuc             tmp = bn_buff[63 - (n * 8 + i)];
377*0a6a1f1dSLionel Sambuc             array[n] |= tmp << (8 * i);
378*0a6a1f1dSLionel Sambuc         }
379*0a6a1f1dSLionel Sambuc     }
380ebfedea0SLionel Sambuc     return 1;
381ebfedea0SLionel Sambuc }
382ebfedea0SLionel Sambuc 
383ebfedea0SLionel Sambuc /* Init a 512-bit BIGNUM from the UINT64*_ (8 * 64) interleaved array */
interleaved_array_to_bn_512(BIGNUM * b,UINT64 * array)384ebfedea0SLionel Sambuc static int interleaved_array_to_bn_512(BIGNUM *b, UINT64 *array)
385ebfedea0SLionel Sambuc {
386ebfedea0SLionel Sambuc     unsigned char tmp[64];
387ebfedea0SLionel Sambuc     int n = 8;
388ebfedea0SLionel Sambuc     int i;
389ebfedea0SLionel Sambuc     while (n-- > 0) {
390ebfedea0SLionel Sambuc         for (i = 7; i >= 0; i--) {
391*0a6a1f1dSLionel Sambuc             tmp[63 - (n * 8 + i)] = (unsigned char)(array[n] >> (8 * i));
392*0a6a1f1dSLionel Sambuc     }}
393ebfedea0SLionel Sambuc     BN_bin2bn(tmp, 64, b);
394ebfedea0SLionel Sambuc     return 0;
395ebfedea0SLionel Sambuc }
396ebfedea0SLionel Sambuc 
397ebfedea0SLionel Sambuc /* The main 512bit precompute call */
mod_exp_pre_compute_data_512(UINT64 * m,struct mod_ctx_512 * data)398ebfedea0SLionel Sambuc static int mod_exp_pre_compute_data_512(UINT64 *m, struct mod_ctx_512 *data)
399ebfedea0SLionel Sambuc {
400ebfedea0SLionel Sambuc     BIGNUM two_768, two_640, two_128, two_512, tmp, _m, tmp2;
401ebfedea0SLionel Sambuc 
402ebfedea0SLionel Sambuc     /* We need a BN_CTX for the modulo functions */
403ebfedea0SLionel Sambuc     BN_CTX *ctx;
404ebfedea0SLionel Sambuc     /* Some tmps */
405ebfedea0SLionel Sambuc     UINT64 _t[8];
406ebfedea0SLionel Sambuc     int i, j, ret = 0;
407ebfedea0SLionel Sambuc 
408ebfedea0SLionel Sambuc     /* Init _m with m */
409ebfedea0SLionel Sambuc     BN_init(&_m);
410ebfedea0SLionel Sambuc     interleaved_array_to_bn_512(&_m, m);
411ebfedea0SLionel Sambuc     memset(_t, 0, 64);
412ebfedea0SLionel Sambuc 
413ebfedea0SLionel Sambuc     /* Inits */
414ebfedea0SLionel Sambuc     BN_init(&two_768);
415ebfedea0SLionel Sambuc     BN_init(&two_640);
416ebfedea0SLionel Sambuc     BN_init(&two_128);
417ebfedea0SLionel Sambuc     BN_init(&two_512);
418ebfedea0SLionel Sambuc     BN_init(&tmp);
419ebfedea0SLionel Sambuc     BN_init(&tmp2);
420ebfedea0SLionel Sambuc 
421ebfedea0SLionel Sambuc     /* Create our context */
422*0a6a1f1dSLionel Sambuc     if ((ctx = BN_CTX_new()) == NULL) {
423*0a6a1f1dSLionel Sambuc         goto err;
424*0a6a1f1dSLionel Sambuc     }
425ebfedea0SLionel Sambuc     BN_CTX_start(ctx);
426ebfedea0SLionel Sambuc 
427ebfedea0SLionel Sambuc     /*
428ebfedea0SLionel Sambuc      * For production, if you care, these only need to be set once,
429ebfedea0SLionel Sambuc      * and may be made constants.
430ebfedea0SLionel Sambuc      */
431ebfedea0SLionel Sambuc     BN_lshift(&two_768, BN_value_one(), 768);
432ebfedea0SLionel Sambuc     BN_lshift(&two_640, BN_value_one(), 640);
433ebfedea0SLionel Sambuc     BN_lshift(&two_128, BN_value_one(), 128);
434ebfedea0SLionel Sambuc     BN_lshift(&two_512, BN_value_one(), 512);
435ebfedea0SLionel Sambuc 
436ebfedea0SLionel Sambuc     if (0 == (m[7] & 0x8000000000000000)) {
437*0a6a1f1dSLionel Sambuc         goto err;
438ebfedea0SLionel Sambuc     }
439ebfedea0SLionel Sambuc     if (0 == (m[0] & 0x1)) {    /* Odd modulus required for Mont */
440*0a6a1f1dSLionel Sambuc         goto err;
441ebfedea0SLionel Sambuc     }
442ebfedea0SLionel Sambuc 
443ebfedea0SLionel Sambuc     /* Precompute m1 */
444ebfedea0SLionel Sambuc     BN_mod(&tmp, &two_768, &_m, ctx);
445ebfedea0SLionel Sambuc     if (!bn_extract_to_array_512(&tmp, 8, &data->m1[0])) {
446*0a6a1f1dSLionel Sambuc         goto err;
447*0a6a1f1dSLionel Sambuc     }
448ebfedea0SLionel Sambuc 
449ebfedea0SLionel Sambuc     /* Precompute m2 */
450ebfedea0SLionel Sambuc     BN_mod(&tmp, &two_640, &_m, ctx);
451ebfedea0SLionel Sambuc     if (!bn_extract_to_array_512(&tmp, 8, &data->m2[0])) {
452ebfedea0SLionel Sambuc         goto err;
453ebfedea0SLionel Sambuc     }
454ebfedea0SLionel Sambuc 
455ebfedea0SLionel Sambuc     /*
456ebfedea0SLionel Sambuc      * Precompute k1, a 128b number = ((-1)* m-1 ) mod 2128; k1 should
457ebfedea0SLionel Sambuc      * be non-negative.
458ebfedea0SLionel Sambuc      */
459ebfedea0SLionel Sambuc     BN_mod_inverse(&tmp, &_m, &two_128, ctx);
460*0a6a1f1dSLionel Sambuc     if (!BN_is_zero(&tmp)) {
461*0a6a1f1dSLionel Sambuc         BN_sub(&tmp, &two_128, &tmp);
462*0a6a1f1dSLionel Sambuc     }
463ebfedea0SLionel Sambuc     if (!bn_extract_to_array_512(&tmp, 2, &data->k1[0])) {
464*0a6a1f1dSLionel Sambuc         goto err;
465*0a6a1f1dSLionel Sambuc     }
466ebfedea0SLionel Sambuc 
467ebfedea0SLionel Sambuc     /* Precompute t */
468ebfedea0SLionel Sambuc     for (i = 0; i < 8; i++) {
469ebfedea0SLionel Sambuc         BN_zero(&tmp);
470*0a6a1f1dSLionel Sambuc         if (i & 1) {
471*0a6a1f1dSLionel Sambuc             BN_add(&tmp, &two_512, &tmp);
472*0a6a1f1dSLionel Sambuc         }
473*0a6a1f1dSLionel Sambuc         if (i & 2) {
474*0a6a1f1dSLionel Sambuc             BN_add(&tmp, &two_512, &tmp);
475*0a6a1f1dSLionel Sambuc         }
476*0a6a1f1dSLionel Sambuc         if (i & 4) {
477*0a6a1f1dSLionel Sambuc             BN_add(&tmp, &two_640, &tmp);
478*0a6a1f1dSLionel Sambuc         }
479ebfedea0SLionel Sambuc 
480ebfedea0SLionel Sambuc         BN_nnmod(&tmp2, &tmp, &_m, ctx);
481ebfedea0SLionel Sambuc         if (!bn_extract_to_array_512(&tmp2, 8, _t)) {
482*0a6a1f1dSLionel Sambuc             goto err;
483*0a6a1f1dSLionel Sambuc         }
484*0a6a1f1dSLionel Sambuc         for (j = 0; j < 8; j++)
485*0a6a1f1dSLionel Sambuc             data->t[j][i] = _t[j];
486*0a6a1f1dSLionel Sambuc     }
487ebfedea0SLionel Sambuc 
488ebfedea0SLionel Sambuc     /* Precompute m */
489ebfedea0SLionel Sambuc     for (i = 0; i < 8; i++) {
490*0a6a1f1dSLionel Sambuc         data->m[i] = m[i];
491*0a6a1f1dSLionel Sambuc     }
492ebfedea0SLionel Sambuc 
493ebfedea0SLionel Sambuc     ret = 1;
494ebfedea0SLionel Sambuc 
495ebfedea0SLionel Sambuc  err:
496ebfedea0SLionel Sambuc     /* Cleanup */
497ebfedea0SLionel Sambuc     if (ctx != NULL) {
498*0a6a1f1dSLionel Sambuc         BN_CTX_end(ctx);
499*0a6a1f1dSLionel Sambuc         BN_CTX_free(ctx);
500*0a6a1f1dSLionel Sambuc     }
501ebfedea0SLionel Sambuc     BN_free(&two_768);
502ebfedea0SLionel Sambuc     BN_free(&two_640);
503ebfedea0SLionel Sambuc     BN_free(&two_128);
504ebfedea0SLionel Sambuc     BN_free(&two_512);
505ebfedea0SLionel Sambuc     BN_free(&tmp);
506ebfedea0SLionel Sambuc     BN_free(&tmp2);
507ebfedea0SLionel Sambuc     BN_free(&_m);
508ebfedea0SLionel Sambuc 
509ebfedea0SLionel Sambuc     return ret;
510ebfedea0SLionel Sambuc }
511ebfedea0SLionel Sambuc 
e_rsax_rsa_mod_exp(BIGNUM * r0,const BIGNUM * I,RSA * rsa,BN_CTX * ctx)512*0a6a1f1dSLionel Sambuc static int e_rsax_rsa_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa,
513*0a6a1f1dSLionel Sambuc                               BN_CTX *ctx)
514ebfedea0SLionel Sambuc {
515ebfedea0SLionel Sambuc     BIGNUM *r1, *m1, *vrfy;
516ebfedea0SLionel Sambuc     BIGNUM local_dmp1, local_dmq1, local_c, local_r1;
517ebfedea0SLionel Sambuc     BIGNUM *dmp1, *dmq1, *c, *pr1;
518ebfedea0SLionel Sambuc     int ret = 0;
519ebfedea0SLionel Sambuc 
520ebfedea0SLionel Sambuc     BN_CTX_start(ctx);
521ebfedea0SLionel Sambuc     r1 = BN_CTX_get(ctx);
522ebfedea0SLionel Sambuc     m1 = BN_CTX_get(ctx);
523ebfedea0SLionel Sambuc     vrfy = BN_CTX_get(ctx);
524ebfedea0SLionel Sambuc 
525ebfedea0SLionel Sambuc     {
526ebfedea0SLionel Sambuc         BIGNUM local_p, local_q;
527ebfedea0SLionel Sambuc         BIGNUM *p = NULL, *q = NULL;
528ebfedea0SLionel Sambuc         int error = 0;
529ebfedea0SLionel Sambuc 
530*0a6a1f1dSLionel Sambuc         /*
531*0a6a1f1dSLionel Sambuc          * Make sure BN_mod_inverse in Montgomery intialization uses the
532*0a6a1f1dSLionel Sambuc          * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set)
533ebfedea0SLionel Sambuc          */
534*0a6a1f1dSLionel Sambuc         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
535ebfedea0SLionel Sambuc             BN_init(&local_p);
536ebfedea0SLionel Sambuc             p = &local_p;
537ebfedea0SLionel Sambuc             BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
538ebfedea0SLionel Sambuc 
539ebfedea0SLionel Sambuc             BN_init(&local_q);
540ebfedea0SLionel Sambuc             q = &local_q;
541ebfedea0SLionel Sambuc             BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
542*0a6a1f1dSLionel Sambuc         } else {
543ebfedea0SLionel Sambuc             p = rsa->p;
544ebfedea0SLionel Sambuc             q = rsa->q;
545ebfedea0SLionel Sambuc         }
546ebfedea0SLionel Sambuc 
547*0a6a1f1dSLionel Sambuc         if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
548*0a6a1f1dSLionel Sambuc             if (!BN_MONT_CTX_set_locked
549*0a6a1f1dSLionel Sambuc                 (&rsa->_method_mod_p, CRYPTO_LOCK_RSA, p, ctx))
550ebfedea0SLionel Sambuc                 error = 1;
551*0a6a1f1dSLionel Sambuc             if (!BN_MONT_CTX_set_locked
552*0a6a1f1dSLionel Sambuc                 (&rsa->_method_mod_q, CRYPTO_LOCK_RSA, q, ctx))
553ebfedea0SLionel Sambuc                 error = 1;
554ebfedea0SLionel Sambuc         }
555ebfedea0SLionel Sambuc 
556ebfedea0SLionel Sambuc         /* clean up */
557*0a6a1f1dSLionel Sambuc         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
558ebfedea0SLionel Sambuc             BN_free(&local_p);
559ebfedea0SLionel Sambuc             BN_free(&local_q);
560ebfedea0SLionel Sambuc         }
561ebfedea0SLionel Sambuc         if (error)
562ebfedea0SLionel Sambuc             goto err;
563ebfedea0SLionel Sambuc     }
564ebfedea0SLionel Sambuc 
565ebfedea0SLionel Sambuc     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
566*0a6a1f1dSLionel Sambuc         if (!BN_MONT_CTX_set_locked
567*0a6a1f1dSLionel Sambuc             (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx))
568ebfedea0SLionel Sambuc             goto err;
569ebfedea0SLionel Sambuc 
570ebfedea0SLionel Sambuc     /* compute I mod q */
571*0a6a1f1dSLionel Sambuc     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
572ebfedea0SLionel Sambuc         c = &local_c;
573ebfedea0SLionel Sambuc         BN_with_flags(c, I, BN_FLG_CONSTTIME);
574*0a6a1f1dSLionel Sambuc         if (!BN_mod(r1, c, rsa->q, ctx))
575*0a6a1f1dSLionel Sambuc             goto err;
576*0a6a1f1dSLionel Sambuc     } else {
577*0a6a1f1dSLionel Sambuc         if (!BN_mod(r1, I, rsa->q, ctx))
578*0a6a1f1dSLionel Sambuc             goto err;
579ebfedea0SLionel Sambuc     }
580ebfedea0SLionel Sambuc 
581ebfedea0SLionel Sambuc     /* compute r1^dmq1 mod q */
582*0a6a1f1dSLionel Sambuc     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
583ebfedea0SLionel Sambuc         dmq1 = &local_dmq1;
584ebfedea0SLionel Sambuc         BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
585*0a6a1f1dSLionel Sambuc     } else
586ebfedea0SLionel Sambuc         dmq1 = rsa->dmq1;
587ebfedea0SLionel Sambuc 
588ebfedea0SLionel Sambuc     if (!e_rsax_bn_mod_exp(m1, r1, dmq1, rsa->q, ctx,
589*0a6a1f1dSLionel Sambuc                            rsa->_method_mod_q, e_rsax_get_ctx(rsa, 0,
590*0a6a1f1dSLionel Sambuc                                                               rsa->q)))
591*0a6a1f1dSLionel Sambuc         goto err;
592ebfedea0SLionel Sambuc 
593ebfedea0SLionel Sambuc     /* compute I mod p */
594*0a6a1f1dSLionel Sambuc     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
595ebfedea0SLionel Sambuc         c = &local_c;
596ebfedea0SLionel Sambuc         BN_with_flags(c, I, BN_FLG_CONSTTIME);
597*0a6a1f1dSLionel Sambuc         if (!BN_mod(r1, c, rsa->p, ctx))
598*0a6a1f1dSLionel Sambuc             goto err;
599*0a6a1f1dSLionel Sambuc     } else {
600*0a6a1f1dSLionel Sambuc         if (!BN_mod(r1, I, rsa->p, ctx))
601*0a6a1f1dSLionel Sambuc             goto err;
602ebfedea0SLionel Sambuc     }
603ebfedea0SLionel Sambuc 
604ebfedea0SLionel Sambuc     /* compute r1^dmp1 mod p */
605*0a6a1f1dSLionel Sambuc     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
606ebfedea0SLionel Sambuc         dmp1 = &local_dmp1;
607ebfedea0SLionel Sambuc         BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
608*0a6a1f1dSLionel Sambuc     } else
609ebfedea0SLionel Sambuc         dmp1 = rsa->dmp1;
610ebfedea0SLionel Sambuc 
611ebfedea0SLionel Sambuc     if (!e_rsax_bn_mod_exp(r0, r1, dmp1, rsa->p, ctx,
612*0a6a1f1dSLionel Sambuc                            rsa->_method_mod_p, e_rsax_get_ctx(rsa, 1,
613*0a6a1f1dSLionel Sambuc                                                               rsa->p)))
614ebfedea0SLionel Sambuc         goto err;
615ebfedea0SLionel Sambuc 
616*0a6a1f1dSLionel Sambuc     if (!BN_sub(r0, r0, m1))
617*0a6a1f1dSLionel Sambuc         goto err;
618*0a6a1f1dSLionel Sambuc     /*
619*0a6a1f1dSLionel Sambuc      * This will help stop the size of r0 increasing, which does affect the
620*0a6a1f1dSLionel Sambuc      * multiply if it optimised for a power of 2 size
621*0a6a1f1dSLionel Sambuc      */
622*0a6a1f1dSLionel Sambuc     if (BN_is_negative(r0))
623*0a6a1f1dSLionel Sambuc         if (!BN_add(r0, r0, rsa->p))
624*0a6a1f1dSLionel Sambuc             goto err;
625*0a6a1f1dSLionel Sambuc 
626*0a6a1f1dSLionel Sambuc     if (!BN_mul(r1, r0, rsa->iqmp, ctx))
627*0a6a1f1dSLionel Sambuc         goto err;
628*0a6a1f1dSLionel Sambuc 
629*0a6a1f1dSLionel Sambuc     /* Turn BN_FLG_CONSTTIME flag on before division operation */
630*0a6a1f1dSLionel Sambuc     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
631*0a6a1f1dSLionel Sambuc         pr1 = &local_r1;
632*0a6a1f1dSLionel Sambuc         BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
633*0a6a1f1dSLionel Sambuc     } else
634*0a6a1f1dSLionel Sambuc         pr1 = r1;
635*0a6a1f1dSLionel Sambuc     if (!BN_mod(r0, pr1, rsa->p, ctx))
636*0a6a1f1dSLionel Sambuc         goto err;
637*0a6a1f1dSLionel Sambuc 
638*0a6a1f1dSLionel Sambuc     /*
639*0a6a1f1dSLionel Sambuc      * If p < q it is occasionally possible for the correction of adding 'p'
640*0a6a1f1dSLionel Sambuc      * if r0 is negative above to leave the result still negative. This can
641*0a6a1f1dSLionel Sambuc      * break the private key operations: the following second correction
642*0a6a1f1dSLionel Sambuc      * should *always* correct this rare occurrence. This will *never* happen
643*0a6a1f1dSLionel Sambuc      * with OpenSSL generated keys because they ensure p > q [steve]
644*0a6a1f1dSLionel Sambuc      */
645*0a6a1f1dSLionel Sambuc     if (BN_is_negative(r0))
646*0a6a1f1dSLionel Sambuc         if (!BN_add(r0, r0, rsa->p))
647*0a6a1f1dSLionel Sambuc             goto err;
648*0a6a1f1dSLionel Sambuc     if (!BN_mul(r1, r0, rsa->q, ctx))
649*0a6a1f1dSLionel Sambuc         goto err;
650*0a6a1f1dSLionel Sambuc     if (!BN_add(r0, r1, m1))
651*0a6a1f1dSLionel Sambuc         goto err;
652*0a6a1f1dSLionel Sambuc 
653*0a6a1f1dSLionel Sambuc     if (rsa->e && rsa->n) {
654*0a6a1f1dSLionel Sambuc         if (!e_rsax_bn_mod_exp
655*0a6a1f1dSLionel Sambuc             (vrfy, r0, rsa->e, rsa->n, ctx, rsa->_method_mod_n,
656*0a6a1f1dSLionel Sambuc              e_rsax_get_ctx(rsa, 2, rsa->n)))
657*0a6a1f1dSLionel Sambuc             goto err;
658*0a6a1f1dSLionel Sambuc 
659*0a6a1f1dSLionel Sambuc         /*
660*0a6a1f1dSLionel Sambuc          * If 'I' was greater than (or equal to) rsa->n, the operation will
661*0a6a1f1dSLionel Sambuc          * be equivalent to using 'I mod n'. However, the result of the
662*0a6a1f1dSLionel Sambuc          * verify will *always* be less than 'n' so we don't check for
663*0a6a1f1dSLionel Sambuc          * absolute equality, just congruency.
664*0a6a1f1dSLionel Sambuc          */
665*0a6a1f1dSLionel Sambuc         if (!BN_sub(vrfy, vrfy, I))
666*0a6a1f1dSLionel Sambuc             goto err;
667*0a6a1f1dSLionel Sambuc         if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
668*0a6a1f1dSLionel Sambuc             goto err;
669ebfedea0SLionel Sambuc         if (BN_is_negative(vrfy))
670*0a6a1f1dSLionel Sambuc             if (!BN_add(vrfy, vrfy, rsa->n))
671*0a6a1f1dSLionel Sambuc                 goto err;
672*0a6a1f1dSLionel Sambuc         if (!BN_is_zero(vrfy)) {
673*0a6a1f1dSLionel Sambuc             /*
674*0a6a1f1dSLionel Sambuc              * 'I' and 'vrfy' aren't congruent mod n. Don't leak
675*0a6a1f1dSLionel Sambuc              * miscalculated CRT output, just do a raw (slower) mod_exp and
676*0a6a1f1dSLionel Sambuc              * return that instead.
677*0a6a1f1dSLionel Sambuc              */
678ebfedea0SLionel Sambuc 
679ebfedea0SLionel Sambuc             BIGNUM local_d;
680ebfedea0SLionel Sambuc             BIGNUM *d = NULL;
681ebfedea0SLionel Sambuc 
682*0a6a1f1dSLionel Sambuc             if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
683ebfedea0SLionel Sambuc                 d = &local_d;
684ebfedea0SLionel Sambuc                 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
685*0a6a1f1dSLionel Sambuc             } else
686ebfedea0SLionel Sambuc                 d = rsa->d;
687ebfedea0SLionel Sambuc             if (!e_rsax_bn_mod_exp(r0, I, d, rsa->n, ctx,
688*0a6a1f1dSLionel Sambuc                                    rsa->_method_mod_n, e_rsax_get_ctx(rsa, 2,
689*0a6a1f1dSLionel Sambuc                                                                       rsa->n)))
690*0a6a1f1dSLionel Sambuc                 goto err;
691ebfedea0SLionel Sambuc         }
692ebfedea0SLionel Sambuc     }
693ebfedea0SLionel Sambuc     ret = 1;
694ebfedea0SLionel Sambuc 
695ebfedea0SLionel Sambuc  err:
696ebfedea0SLionel Sambuc     BN_CTX_end(ctx);
697ebfedea0SLionel Sambuc 
698ebfedea0SLionel Sambuc     return ret;
699ebfedea0SLionel Sambuc }
700ebfedea0SLionel Sambuc # endif                         /* !OPENSSL_NO_RSA */
701ebfedea0SLionel Sambuc #endif                          /* !COMPILE_RSAX */
702