crypto/bn/rsaz_exp.c

   1 /******************************************************************************\r
   2 * Copyright(c) 2012, Intel Corp.                                             \r
   3 * Developers and authors:                                                    \r
   4 * Shay Gueron (1, 2), and Vlad Krasnov (1)                                   \r
   5 * (1) Intel Corporation, Israel Development Center, Haifa, Israel                               \r
   6 * (2) University of Haifa, Israel                                              \r
   7 ******************************************************************************\r
   8 * LICENSE:                                                                \r
   9 * This submission to OpenSSL is to be made available under the OpenSSL  \r
  10 * license, and only to the OpenSSL project, in order to allow integration    \r
  11 * into the publicly distributed code. \r
  12 * The use of this code, or portions of this code, or concepts embedded in\r
  13 * this code, or modification of this code and/or algorithm(s) in it, or the\r
  14 * use of this code for any other purpose than stated above, requires special\r
  15 * licensing.                                                                  \r
  16 ******************************************************************************\r
  17 * DISCLAIMER:                                                                \r
  18 * THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS AND THE COPYRIGHT OWNERS     \r
  19 * ``AS IS''. ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED \r
  20 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR \r
  21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS OR THE COPYRIGHT\r
  22 * OWNERS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, \r
  23 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF    \r
  24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS   \r
  25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN    \r
  26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)    \r
  27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE \r
  28 * POSSIBILITY OF SUCH DAMAGE.                                                \r
  29 ******************************************************************************/\r
  30 \r
  31 #include "rsaz_exp.h"\r
  32 \r
  33 /*\r
  34  * See crypto/bn/asm/rsaz-avx2.pl for further details.\r
  35  */\r
  36 void rsaz_1024_norm2red_avx2(void *red,const void *norm);\r
  37 void rsaz_1024_mul_avx2(void *ret,const void *a,const void *b,const void *n,unsigned long k);\r
  38 void rsaz_1024_sqr_avx2(void *ret,const void *a,const void *n,unsigned long k,int cnt);\r
  39 void rsaz_1024_scatter5_avx2(void *tbl,const void *val,int i);\r
  40 void rsaz_1024_gather5_avx2(void *val,const void *tbl,int i);\r
  41 void rsaz_1024_red2norm_avx2(void *norm,const void *red);\r
  42 \r
  43 #if defined(__GNUC__)\r
  44 # define ALIGN64        __attribute__((aligned(64)))\r
  45 #elif defined(_MSC_VER)\r
  46 # define ALIGN64        __declspec(align(64))\r
  47 #elif defined(__SUNPRO_C)\r
  48 # define ALIGN64\r
  49 # pragma align 64(one,two80)\r
  50 #else\r
  51 # define ALIGN64        /* not fatal, might hurt performance a little */\r
  52 #endif\r
  53 \r
  54 ALIGN64 static const unsigned long one[40] =\r
  55         {1,0,0,    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};\r
  56 ALIGN64 static const unsigned long two80[40] =\r
  57         {0,0,1<<22,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};\r
  58 \r
  59 void RSAZ_1024_mod_exp_avx2(BN_ULONG result_norm[16],\r
  60         const BN_ULONG base_norm[16], const BN_ULONG exponent[16],\r
  61         const BN_ULONG m_norm[16], const BN_ULONG RR[16], BN_ULONG k0)\r
  62 {\r
  63         unsigned char    storage[320*3+32*9*16+64];     /* 5.5KB */\r
  64         unsigned char   *p_str = storage + (64-((size_t)storage%64));\r
  65         unsigned char   *a_inv, *m, *result,\r
  66                         *table_s = p_str+320*3,\r
  67                         *R2      = table_s;     /* borrow */\r
  68         int index;\r
  69         int wvalue;\r
  70 \r
  71         if ((((size_t)p_str&4095)+320)>>12) {\r
  72                 result = p_str;\r
  73                 a_inv = p_str + 320;\r
  74                 m = p_str + 320*2;      /* should not cross page */\r
  75         } else {\r
  76                 m = p_str;              /* should not cross page */\r
  77                 result = p_str + 320;\r
  78                 a_inv = p_str + 320*2;\r
  79         }\r
  80 \r
  81         rsaz_1024_norm2red_avx2(m, m_norm);\r
  82         rsaz_1024_norm2red_avx2(a_inv, base_norm);\r
  83         rsaz_1024_norm2red_avx2(R2, RR);\r
  84 \r
  85         rsaz_1024_mul_avx2(R2, R2, R2, m, k0);\r
  86         rsaz_1024_mul_avx2(R2, R2, two80, m, k0);\r
  87 \r
  88         /* table[0] = 1 */\r
  89         rsaz_1024_mul_avx2(result, R2, one, m, k0);\r
  90         /* table[1] = a_inv^1 */\r
  91         rsaz_1024_mul_avx2(a_inv, a_inv, R2, m, k0);\r
  92 \r
  93         rsaz_1024_scatter5_avx2(table_s,result,0);\r
  94         rsaz_1024_scatter5_avx2(table_s,a_inv,1);\r
  95 \r
  96         /* table[2] = a_inv^2 */\r
  97         rsaz_1024_sqr_avx2(result, a_inv, m, k0, 1);\r
  98         rsaz_1024_scatter5_avx2(table_s,result,2);\r
  99 #if 0\r
 100         /* this is almost 2x smaller and less than 1% slower */\r
 101         for (index=3; index<32; index++) {\r
 102                 rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 103                 rsaz_1024_scatter5_avx2(table_s,result,index);\r
 104         }\r
 105 #else\r
 106         /* table[4] = a_inv^4 */\r
 107         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 108         rsaz_1024_scatter5_avx2(table_s,result,4);\r
 109         /* table[8] = a_inv^8 */\r
 110         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 111         rsaz_1024_scatter5_avx2(table_s,result,8);\r
 112         /* table[16] = a_inv^16 */\r
 113         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 114         rsaz_1024_scatter5_avx2(table_s,result,16);\r
 115         /* table[17] = a_inv^17 */\r
 116         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 117         rsaz_1024_scatter5_avx2(table_s,result,17);\r
 118 \r
 119         /* table[3] */\r
 120         rsaz_1024_gather5_avx2(result,table_s,2);\r
 121         rsaz_1024_mul_avx2(result,result,a_inv,m,k0);\r
 122         rsaz_1024_scatter5_avx2(table_s,result,3);\r
 123         /* table[6] */\r
 124         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 125         rsaz_1024_scatter5_avx2(table_s,result,6);\r
 126         /* table[12] */\r
 127         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 128         rsaz_1024_scatter5_avx2(table_s,result,12);\r
 129         /* table[24] */\r
 130         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 131         rsaz_1024_scatter5_avx2(table_s,result,24);\r
 132         /* table[25] */\r
 133         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 134         rsaz_1024_scatter5_avx2(table_s,result,25);\r
 135 \r
 136         /* table[5] */\r
 137         rsaz_1024_gather5_avx2(result,table_s,4);\r
 138         rsaz_1024_mul_avx2(result,result,a_inv,m,k0);\r
 139         rsaz_1024_scatter5_avx2(table_s,result,5);\r
 140         /* table[10] */\r
 141         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 142         rsaz_1024_scatter5_avx2(table_s,result,10);\r
 143         /* table[20] */\r
 144         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 145         rsaz_1024_scatter5_avx2(table_s,result,20);\r
 146         /* table[21] */\r
 147         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 148         rsaz_1024_scatter5_avx2(table_s,result,21);\r
 149 \r
 150         /* table[7] */\r
 151         rsaz_1024_gather5_avx2(result,table_s,6);\r
 152         rsaz_1024_mul_avx2(result,result,a_inv,m,k0);\r
 153         rsaz_1024_scatter5_avx2(table_s,result,7);\r
 154         /* table[14] */\r
 155         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 156         rsaz_1024_scatter5_avx2(table_s,result,14);\r
 157         /* table[28] */\r
 158         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 159         rsaz_1024_scatter5_avx2(table_s,result,28);\r
 160         /* table[29] */\r
 161         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 162         rsaz_1024_scatter5_avx2(table_s,result,29);\r
 163 \r
 164         /* table[9] */\r
 165         rsaz_1024_gather5_avx2(result,table_s,8);\r
 166         rsaz_1024_mul_avx2(result,result,a_inv,m,k0);\r
 167         rsaz_1024_scatter5_avx2(table_s,result,9);\r
 168         /* table[18] */\r
 169         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 170         rsaz_1024_scatter5_avx2(table_s,result,18);\r
 171         /* table[19] */\r
 172         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 173         rsaz_1024_scatter5_avx2(table_s,result,19);\r
 174 \r
 175         /* table[11] */\r
 176         rsaz_1024_gather5_avx2(result,table_s,10);\r
 177         rsaz_1024_mul_avx2(result,result,a_inv,m,k0);\r
 178         rsaz_1024_scatter5_avx2(table_s,result,11);\r
 179         /* table[22] */\r
 180         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 181         rsaz_1024_scatter5_avx2(table_s,result,22);\r
 182         /* table[23] */\r
 183         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 184         rsaz_1024_scatter5_avx2(table_s,result,23);\r
 185 \r
 186         /* table[13] */\r
 187         rsaz_1024_gather5_avx2(result,table_s,12);\r
 188         rsaz_1024_mul_avx2(result,result,a_inv,m,k0);\r
 189         rsaz_1024_scatter5_avx2(table_s,result,13);\r
 190         /* table[26] */\r
 191         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 192         rsaz_1024_scatter5_avx2(table_s,result,26);\r
 193         /* table[27] */\r
 194         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 195         rsaz_1024_scatter5_avx2(table_s,result,27);\r
 196 \r
 197         /* table[15] */\r
 198         rsaz_1024_gather5_avx2(result,table_s,14);\r
 199         rsaz_1024_mul_avx2(result,result,a_inv,m,k0);\r
 200         rsaz_1024_scatter5_avx2(table_s,result,15);\r
 201         /* table[30] */\r
 202         rsaz_1024_sqr_avx2(result, result, m, k0, 1);\r
 203         rsaz_1024_scatter5_avx2(table_s,result,30);\r
 204         /* table[31] */\r
 205         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 206         rsaz_1024_scatter5_avx2(table_s,result,31);\r
 207 #endif\r
 208 \r
 209         /* load first window */\r
 210         p_str = (unsigned char*)exponent;\r
 211         wvalue = p_str[127] >> 3;\r
 212         rsaz_1024_gather5_avx2(result,table_s,wvalue);\r
 213 \r
 214         index = 1014;\r
 215 \r
 216         while(index > -1) {     /* loop for the remaining 127 windows */\r
 217 \r
 218                 rsaz_1024_sqr_avx2(result, result, m, k0, 5);\r
 219 \r
 220                 wvalue = *((unsigned short*)&p_str[index/8]);\r
 221                 wvalue = (wvalue>> (index%8)) & 31;\r
 222                 index-=5;\r
 223 \r
 224                 rsaz_1024_gather5_avx2(a_inv,table_s,wvalue);   /* borrow a_inv */\r
 225                 rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 226         }\r
 227 \r
 228         /* square four times */\r
 229         rsaz_1024_sqr_avx2(result, result, m, k0, 4);\r
 230 \r
 231         wvalue = p_str[0] & 15;\r
 232 \r
 233         rsaz_1024_gather5_avx2(a_inv,table_s,wvalue);   /* borrow a_inv */\r
 234         rsaz_1024_mul_avx2(result, result, a_inv, m, k0);\r
 235 \r
 236         /* from Montgomery */\r
 237         rsaz_1024_mul_avx2(result, result, one, m, k0);\r
 238 \r
 239         rsaz_1024_red2norm_avx2(result_norm, result);\r
 240 \r
 241         OPENSSL_cleanse(storage,sizeof(storage));\r
 242 }\r
 243 \r
 244 /*\r
 245  * See crypto/bn/rsaz-x86_64.pl for further details.\r
 246  */\r
 247 void rsaz_512_mul(void *ret,const void *a,const void *b,const void *n,unsigned long k);\r
 248 void rsaz_512_mul_scatter4(void *ret,const void *a,const void *n,unsigned long k,const void *tbl,unsigned int power);\r
 249 void rsaz_512_mul_gather4(void *ret,const void *a,const void *tbl,const void *n,unsigned long k,unsigned int power);\r
 250 void rsaz_512_mul_by_one(void *ret,const void *a,const void *n,unsigned long k);\r
 251 void rsaz_512_sqr(void *ret,const void *a,const void *n,unsigned long k,int cnt);\r
 252 void rsaz_512_scatter4(void *tbl, const unsigned long *val, int power);\r
 253 void rsaz_512_gather4(unsigned long *val, const void *tbl, int power);\r
 254 \r
 255 void RSAZ_512_mod_exp(BN_ULONG result[8],\r
 256         const BN_ULONG base[8], const BN_ULONG exponent[8],\r
 257         const BN_ULONG m[8], BN_ULONG k0, const BN_ULONG RR[8])\r
 258 {\r
 259         unsigned char    storage[16*8*8+64*2+64];       /* 1.2KB */\r
 260         unsigned char   *table = storage + (64-((size_t)storage%64));\r
 261         unsigned long   *a_inv = (unsigned long *)(table+16*8*8),\r
 262                         *temp  = (unsigned long *)(table+16*8*8+8*8);\r
 263         unsigned char   *p_str = (unsigned char*)exponent;\r
 264         int index;\r
 265         unsigned int wvalue;\r
 266 \r
 267         /* table[0] = 1_inv */\r
 268         temp[0] = 0-m[0];       temp[1] = ~m[1];\r
 269         temp[2] = ~m[2];        temp[3] = ~m[3];\r
 270         temp[4] = ~m[4];        temp[5] = ~m[5];\r
 271         temp[6] = ~m[6];        temp[7] = ~m[7];\r
 272         rsaz_512_scatter4(table, temp, 0);\r
 273 \r
 274         /* table [1] = a_inv^1 */\r
 275         rsaz_512_mul(a_inv, base, RR, m, k0);\r
 276         rsaz_512_scatter4(table, a_inv, 1);\r
 277 \r
 278         /* table [2] = a_inv^2 */\r
 279         rsaz_512_sqr(temp, a_inv, m, k0, 1);\r
 280         rsaz_512_scatter4(table, temp, 2);\r
 281 \r
 282         for (index=3; index<16; index++)\r
 283                 rsaz_512_mul_scatter4(temp, a_inv, m, k0, table, index);\r
 284 \r
 285         /* load first window */\r
 286         wvalue = p_str[63];\r
 287 \r
 288         rsaz_512_gather4(temp, table, wvalue>>4);\r
 289         rsaz_512_sqr(temp, temp, m, k0, 4);\r
 290         rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue&0xf);\r
 291 \r
 292         for (index=62; index>=0; index--) {\r
 293                 wvalue = p_str[index];\r
 294 \r
 295                 rsaz_512_sqr(temp, temp, m, k0, 4);\r
 296                 rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue>>4);\r
 297 \r
 298                 rsaz_512_sqr(temp, temp, m, k0, 4);\r
 299                 rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue&0x0f);\r
 300         }\r
 301 \r
 302         /* from Montgomery */\r
 303         rsaz_512_mul_by_one(result, temp, m, k0);\r
 304 \r
 305         OPENSSL_cleanse(storage,sizeof(storage));\r
 306 }\r