Fix math in BN_bn2dec comment.
[openssl.git] / crypto / bn / rsaz_exp.c
1 /*
2  * Copyright 2013-2016 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 /*****************************************************************************
11 *                                                                            *
12 *  Copyright (c) 2012, Intel Corporation                                     *
13 *                                                                            *
14 *  All rights reserved.                                                      *
15 *                                                                            *
16 *  Redistribution and use in source and binary forms, with or without        *
17 *  modification, are permitted provided that the following conditions are    *
18 *  met:                                                                      *
19 *                                                                            *
20 *  *  Redistributions of source code must retain the above copyright         *
21 *     notice, this list of conditions and the following disclaimer.          *
22 *                                                                            *
23 *  *  Redistributions in binary form must reproduce the above copyright      *
24 *     notice, this list of conditions and the following disclaimer in the    *
25 *     documentation and/or other materials provided with the                 *
26 *     distribution.                                                          *
27 *                                                                            *
28 *  *  Neither the name of the Intel Corporation nor the names of its         *
29 *     contributors may be used to endorse or promote products derived from   *
30 *     this software without specific prior written permission.               *
31 *                                                                            *
32 *                                                                            *
33 *  THIS SOFTWARE IS PROVIDED BY INTEL CORPORATION ""AS IS"" AND ANY          *
34 *  EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE         *
35 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        *
36 *  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL INTEL CORPORATION OR            *
37 *  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,     *
38 *  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,       *
39 *  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR        *
40 *  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    *
41 *  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      *
42 *  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
43 *  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              *
44 *                                                                            *
45 ******************************************************************************
46 * Developers and authors:                                                    *
47 * Shay Gueron (1, 2), and Vlad Krasnov (1)                                   *
48 * (1) Intel Corporation, Israel Development Center, Haifa, Israel            *
49 * (2) University of Haifa, Israel                                            *
50 *****************************************************************************/
51
52 #include <openssl/opensslconf.h>
53 #include "rsaz_exp.h"
54
55 #ifndef RSAZ_ENABLED
56 NON_EMPTY_TRANSLATION_UNIT
57 #else
58
59 /*
60  * See crypto/bn/asm/rsaz-avx2.pl for further details.
61  */
62 void rsaz_1024_norm2red_avx2(void *red, const void *norm);
63 void rsaz_1024_mul_avx2(void *ret, const void *a, const void *b,
64                         const void *n, BN_ULONG k);
65 void rsaz_1024_sqr_avx2(void *ret, const void *a, const void *n, BN_ULONG k,
66                         int cnt);
67 void rsaz_1024_scatter5_avx2(void *tbl, const void *val, int i);
68 void rsaz_1024_gather5_avx2(void *val, const void *tbl, int i);
69 void rsaz_1024_red2norm_avx2(void *norm, const void *red);
70
71 #if defined(__GNUC__)
72 # define ALIGN64        __attribute__((aligned(64)))
73 #elif defined(_MSC_VER)
74 # define ALIGN64        __declspec(align(64))
75 #elif defined(__SUNPRO_C)
76 # define ALIGN64
77 # pragma align 64(one,two80)
78 #else
79 /* not fatal, might hurt performance a little */
80 # define ALIGN64
81 #endif
82
83 ALIGN64 static const BN_ULONG one[40] = {
84     1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
85     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
86 };
87
88 ALIGN64 static const BN_ULONG two80[40] = {
89     0, 0, 1 << 22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
90     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
91 };
92
93 void RSAZ_1024_mod_exp_avx2(BN_ULONG result_norm[16],
94                             const BN_ULONG base_norm[16],
95                             const BN_ULONG exponent[16],
96                             const BN_ULONG m_norm[16], const BN_ULONG RR[16],
97                             BN_ULONG k0)
98 {
99     unsigned char storage[320 * 3 + 32 * 9 * 16 + 64]; /* 5.5KB */
100     unsigned char *p_str = storage + (64 - ((size_t)storage % 64));
101     unsigned char *a_inv, *m, *result;
102     unsigned char *table_s = p_str + 320 * 3;
103     unsigned char *R2 = table_s; /* borrow */
104     int index;
105     int wvalue;
106
107     if ((((size_t)p_str & 4095) + 320) >> 12) {
108         result = p_str;
109         a_inv = p_str + 320;
110         m = p_str + 320 * 2;    /* should not cross page */
111     } else {
112         m = p_str;              /* should not cross page */
113         result = p_str + 320;
114         a_inv = p_str + 320 * 2;
115     }
116
117     rsaz_1024_norm2red_avx2(m, m_norm);
118     rsaz_1024_norm2red_avx2(a_inv, base_norm);
119     rsaz_1024_norm2red_avx2(R2, RR);
120
121     rsaz_1024_mul_avx2(R2, R2, R2, m, k0);
122     rsaz_1024_mul_avx2(R2, R2, two80, m, k0);
123
124     /* table[0] = 1 */
125     rsaz_1024_mul_avx2(result, R2, one, m, k0);
126     /* table[1] = a_inv^1 */
127     rsaz_1024_mul_avx2(a_inv, a_inv, R2, m, k0);
128
129     rsaz_1024_scatter5_avx2(table_s, result, 0);
130     rsaz_1024_scatter5_avx2(table_s, a_inv, 1);
131
132     /* table[2] = a_inv^2 */
133     rsaz_1024_sqr_avx2(result, a_inv, m, k0, 1);
134     rsaz_1024_scatter5_avx2(table_s, result, 2);
135 #if 0
136     /* this is almost 2x smaller and less than 1% slower */
137     for (index = 3; index < 32; index++) {
138         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
139         rsaz_1024_scatter5_avx2(table_s, result, index);
140     }
141 #else
142     /* table[4] = a_inv^4 */
143     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
144     rsaz_1024_scatter5_avx2(table_s, result, 4);
145     /* table[8] = a_inv^8 */
146     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
147     rsaz_1024_scatter5_avx2(table_s, result, 8);
148     /* table[16] = a_inv^16 */
149     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
150     rsaz_1024_scatter5_avx2(table_s, result, 16);
151     /* table[17] = a_inv^17 */
152     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
153     rsaz_1024_scatter5_avx2(table_s, result, 17);
154
155     /* table[3] */
156     rsaz_1024_gather5_avx2(result, table_s, 2);
157     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
158     rsaz_1024_scatter5_avx2(table_s, result, 3);
159     /* table[6] */
160     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
161     rsaz_1024_scatter5_avx2(table_s, result, 6);
162     /* table[12] */
163     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
164     rsaz_1024_scatter5_avx2(table_s, result, 12);
165     /* table[24] */
166     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
167     rsaz_1024_scatter5_avx2(table_s, result, 24);
168     /* table[25] */
169     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
170     rsaz_1024_scatter5_avx2(table_s, result, 25);
171
172     /* table[5] */
173     rsaz_1024_gather5_avx2(result, table_s, 4);
174     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
175     rsaz_1024_scatter5_avx2(table_s, result, 5);
176     /* table[10] */
177     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
178     rsaz_1024_scatter5_avx2(table_s, result, 10);
179     /* table[20] */
180     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
181     rsaz_1024_scatter5_avx2(table_s, result, 20);
182     /* table[21] */
183     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
184     rsaz_1024_scatter5_avx2(table_s, result, 21);
185
186     /* table[7] */
187     rsaz_1024_gather5_avx2(result, table_s, 6);
188     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
189     rsaz_1024_scatter5_avx2(table_s, result, 7);
190     /* table[14] */
191     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
192     rsaz_1024_scatter5_avx2(table_s, result, 14);
193     /* table[28] */
194     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
195     rsaz_1024_scatter5_avx2(table_s, result, 28);
196     /* table[29] */
197     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
198     rsaz_1024_scatter5_avx2(table_s, result, 29);
199
200     /* table[9] */
201     rsaz_1024_gather5_avx2(result, table_s, 8);
202     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
203     rsaz_1024_scatter5_avx2(table_s, result, 9);
204     /* table[18] */
205     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
206     rsaz_1024_scatter5_avx2(table_s, result, 18);
207     /* table[19] */
208     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
209     rsaz_1024_scatter5_avx2(table_s, result, 19);
210
211     /* table[11] */
212     rsaz_1024_gather5_avx2(result, table_s, 10);
213     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
214     rsaz_1024_scatter5_avx2(table_s, result, 11);
215     /* table[22] */
216     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
217     rsaz_1024_scatter5_avx2(table_s, result, 22);
218     /* table[23] */
219     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
220     rsaz_1024_scatter5_avx2(table_s, result, 23);
221
222     /* table[13] */
223     rsaz_1024_gather5_avx2(result, table_s, 12);
224     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
225     rsaz_1024_scatter5_avx2(table_s, result, 13);
226     /* table[26] */
227     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
228     rsaz_1024_scatter5_avx2(table_s, result, 26);
229     /* table[27] */
230     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
231     rsaz_1024_scatter5_avx2(table_s, result, 27);
232
233     /* table[15] */
234     rsaz_1024_gather5_avx2(result, table_s, 14);
235     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
236     rsaz_1024_scatter5_avx2(table_s, result, 15);
237     /* table[30] */
238     rsaz_1024_sqr_avx2(result, result, m, k0, 1);
239     rsaz_1024_scatter5_avx2(table_s, result, 30);
240     /* table[31] */
241     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
242     rsaz_1024_scatter5_avx2(table_s, result, 31);
243 #endif
244
245     /* load first window */
246     p_str = (unsigned char *)exponent;
247     wvalue = p_str[127] >> 3;
248     rsaz_1024_gather5_avx2(result, table_s, wvalue);
249
250     index = 1014;
251
252     while (index > -1) {        /* loop for the remaining 127 windows */
253
254         rsaz_1024_sqr_avx2(result, result, m, k0, 5);
255
256         wvalue = (p_str[(index / 8) + 1] << 8) | p_str[index / 8];
257         wvalue = (wvalue >> (index % 8)) & 31;
258         index -= 5;
259
260         rsaz_1024_gather5_avx2(a_inv, table_s, wvalue); /* borrow a_inv */
261         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
262     }
263
264     /* square four times */
265     rsaz_1024_sqr_avx2(result, result, m, k0, 4);
266
267     wvalue = p_str[0] & 15;
268
269     rsaz_1024_gather5_avx2(a_inv, table_s, wvalue); /* borrow a_inv */
270     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
271
272     /* from Montgomery */
273     rsaz_1024_mul_avx2(result, result, one, m, k0);
274
275     rsaz_1024_red2norm_avx2(result_norm, result);
276
277     OPENSSL_cleanse(storage, sizeof(storage));
278 }
279
280 /*
281  * See crypto/bn/rsaz-x86_64.pl for further details.
282  */
283 void rsaz_512_mul(void *ret, const void *a, const void *b, const void *n,
284                   BN_ULONG k);
285 void rsaz_512_mul_scatter4(void *ret, const void *a, const void *n,
286                            BN_ULONG k, const void *tbl, unsigned int power);
287 void rsaz_512_mul_gather4(void *ret, const void *a, const void *tbl,
288                           const void *n, BN_ULONG k, unsigned int power);
289 void rsaz_512_mul_by_one(void *ret, const void *a, const void *n, BN_ULONG k);
290 void rsaz_512_sqr(void *ret, const void *a, const void *n, BN_ULONG k,
291                   int cnt);
292 void rsaz_512_scatter4(void *tbl, const BN_ULONG *val, int power);
293 void rsaz_512_gather4(BN_ULONG *val, const void *tbl, int power);
294
295 void RSAZ_512_mod_exp(BN_ULONG result[8],
296                       const BN_ULONG base[8], const BN_ULONG exponent[8],
297                       const BN_ULONG m[8], BN_ULONG k0, const BN_ULONG RR[8])
298 {
299     unsigned char storage[16 * 8 * 8 + 64 * 2 + 64]; /* 1.2KB */
300     unsigned char *table = storage + (64 - ((size_t)storage % 64));
301     BN_ULONG *a_inv = (BN_ULONG *)(table + 16 * 8 * 8);
302     BN_ULONG *temp = (BN_ULONG *)(table + 16 * 8 * 8 + 8 * 8);
303     unsigned char *p_str = (unsigned char *)exponent;
304     int index;
305     unsigned int wvalue;
306
307     /* table[0] = 1_inv */
308     temp[0] = 0 - m[0];
309     temp[1] = ~m[1];
310     temp[2] = ~m[2];
311     temp[3] = ~m[3];
312     temp[4] = ~m[4];
313     temp[5] = ~m[5];
314     temp[6] = ~m[6];
315     temp[7] = ~m[7];
316     rsaz_512_scatter4(table, temp, 0);
317
318     /* table [1] = a_inv^1 */
319     rsaz_512_mul(a_inv, base, RR, m, k0);
320     rsaz_512_scatter4(table, a_inv, 1);
321
322     /* table [2] = a_inv^2 */
323     rsaz_512_sqr(temp, a_inv, m, k0, 1);
324     rsaz_512_scatter4(table, temp, 2);
325
326     for (index = 3; index < 16; index++)
327         rsaz_512_mul_scatter4(temp, a_inv, m, k0, table, index);
328
329     /* load first window */
330     wvalue = p_str[63];
331
332     rsaz_512_gather4(temp, table, wvalue >> 4);
333     rsaz_512_sqr(temp, temp, m, k0, 4);
334     rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue & 0xf);
335
336     for (index = 62; index >= 0; index--) {
337         wvalue = p_str[index];
338
339         rsaz_512_sqr(temp, temp, m, k0, 4);
340         rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue >> 4);
341
342         rsaz_512_sqr(temp, temp, m, k0, 4);
343         rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue & 0x0f);
344     }
345
346     /* from Montgomery */
347     rsaz_512_mul_by_one(result, temp, m, k0);
348
349     OPENSSL_cleanse(storage, sizeof(storage));
350 }
351
352 #endif