legacy-libs/grpc-cloned/deps/grpc/third_party/boringssl/crypto/fipsmodule/bn/rsaz_exp.c

   1 /*
   2  * Copyright 2013-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright (c) 2012, Intel Corporation. All Rights Reserved.
   4  *
   5  * Licensed under the OpenSSL license (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  *
  10  * Originally written by Shay Gueron (1, 2), and Vlad Krasnov (1)
  11  * (1) Intel Corporation, Israel Development Center, Haifa, Israel
  12  * (2) University of Haifa, Israel
  13  */
  14
  15 #include <openssl/base.h>
  16
  17 #if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64)
  18
  19 #include "rsaz_exp.h"
  20
  21 #include <openssl/mem.h>
  22
  23 #include "../../internal.h"
  24
  25
  26 // See crypto/bn/asm/rsaz-avx2.pl for further details.
  27 void rsaz_1024_norm2red_avx2(void *red, const void *norm);
  28 void rsaz_1024_mul_avx2(void *ret, const void *a, const void *b, const void *n,
  29                         BN_ULONG k);
  30 void rsaz_1024_sqr_avx2(void *ret, const void *a, const void *n, BN_ULONG k,
  31                         int cnt);
  32 void rsaz_1024_scatter5_avx2(void *tbl, const void *val, int i);
  33 void rsaz_1024_gather5_avx2(void *val, const void *tbl, int i);
  34 void rsaz_1024_red2norm_avx2(void *norm, const void *red);
  35
  36 // one is 1 in RSAZ's representation.
  37 alignas(64) static const BN_ULONG one[40] = {
  38     1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  39     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  40 // two80 is 2^80 in RSAZ's representation. Note RSAZ uses base 2^29, so this is
  41 // 2^(29*2 + 22) = 2^80, not 2^(64*2 + 22).
  42 alignas(64) static const BN_ULONG two80[40] = {
  43     0, 0, 1 << 22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  44     0, 0, 0,       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  45
  46 void RSAZ_1024_mod_exp_avx2(BN_ULONG result_norm[16],
  47         const BN_ULONG base_norm[16], const BN_ULONG exponent[16],
  48         const BN_ULONG m_norm[16], const BN_ULONG RR[16], BN_ULONG k0) {
  49   alignas(64) uint8_t storage[(320 * 3) + (32 * 9 * 16)];  // 5.5KB
  50   unsigned char *a_inv, *m, *result, *table_s = storage + (320 * 3),
  51                                      *R2 = table_s;  // borrow
  52   if (((((uintptr_t)storage & 4095) + 320) >> 12) != 0) {
  53     result = storage;
  54     a_inv = storage + 320;
  55     m = storage + (320 * 2);  // should not cross page
  56   } else {
  57     m = storage;  // should not cross page
  58     result = storage + 320;
  59     a_inv = storage + (320 * 2);
  60   }
  61
  62   rsaz_1024_norm2red_avx2(m, m_norm);
  63   rsaz_1024_norm2red_avx2(a_inv, base_norm);
  64   rsaz_1024_norm2red_avx2(R2, RR);
  65
  66   // Convert |R2| from the usual radix, giving R = 2^1024, to RSAZ's radix,
  67   // giving R = 2^(36*29) = 2^1044.
  68   rsaz_1024_mul_avx2(R2, R2, R2, m, k0);
  69   // R2 = 2^2048 * 2^2048 / 2^1044 = 2^3052
  70   rsaz_1024_mul_avx2(R2, R2, two80, m, k0);
  71   // R2 = 2^3052 * 2^80 / 2^1044 = 2^2088 = (2^1044)^2
  72
  73   // table[0] = 1
  74   rsaz_1024_mul_avx2(result, R2, one, m, k0);
  75   // table[1] = a_inv^1
  76   rsaz_1024_mul_avx2(a_inv, a_inv, R2, m, k0);
  77
  78   rsaz_1024_scatter5_avx2(table_s, result, 0);
  79   rsaz_1024_scatter5_avx2(table_s, a_inv, 1);
  80
  81   // table[2] = a_inv^2
  82   rsaz_1024_sqr_avx2(result, a_inv, m, k0, 1);
  83   rsaz_1024_scatter5_avx2(table_s, result, 2);
  84 #if 0
  85   // This is almost 2x smaller and less than 1% slower.
  86   for (int index = 3; index < 32; index++) {
  87     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
  88     rsaz_1024_scatter5_avx2(table_s, result, index);
  89   }
  90 #else
  91   // table[4] = a_inv^4
  92   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
  93   rsaz_1024_scatter5_avx2(table_s, result, 4);
  94   // table[8] = a_inv^8
  95   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
  96   rsaz_1024_scatter5_avx2(table_s, result, 8);
  97   // table[16] = a_inv^16
  98   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
  99   rsaz_1024_scatter5_avx2(table_s, result, 16);
 100   // table[17] = a_inv^17
 101   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 102   rsaz_1024_scatter5_avx2(table_s, result, 17);
 103
 104   // table[3]
 105   rsaz_1024_gather5_avx2(result, table_s, 2);
 106   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 107   rsaz_1024_scatter5_avx2(table_s, result, 3);
 108   // table[6]
 109   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 110   rsaz_1024_scatter5_avx2(table_s, result, 6);
 111   // table[12]
 112   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 113   rsaz_1024_scatter5_avx2(table_s, result, 12);
 114   // table[24]
 115   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 116   rsaz_1024_scatter5_avx2(table_s, result, 24);
 117   // table[25]
 118   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 119   rsaz_1024_scatter5_avx2(table_s, result, 25);
 120
 121   // table[5]
 122   rsaz_1024_gather5_avx2(result, table_s, 4);
 123   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 124   rsaz_1024_scatter5_avx2(table_s, result, 5);
 125   // table[10]
 126   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 127   rsaz_1024_scatter5_avx2(table_s, result, 10);
 128   // table[20]
 129   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 130   rsaz_1024_scatter5_avx2(table_s, result, 20);
 131   // table[21]
 132   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 133   rsaz_1024_scatter5_avx2(table_s, result, 21);
 134
 135   // table[7]
 136   rsaz_1024_gather5_avx2(result, table_s, 6);
 137   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 138   rsaz_1024_scatter5_avx2(table_s, result, 7);
 139   // table[14]
 140   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 141   rsaz_1024_scatter5_avx2(table_s, result, 14);
 142   // table[28]
 143   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 144   rsaz_1024_scatter5_avx2(table_s, result, 28);
 145   // table[29]
 146   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 147   rsaz_1024_scatter5_avx2(table_s, result, 29);
 148
 149   // table[9]
 150   rsaz_1024_gather5_avx2(result, table_s, 8);
 151   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 152   rsaz_1024_scatter5_avx2(table_s, result, 9);
 153   // table[18]
 154   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 155   rsaz_1024_scatter5_avx2(table_s, result, 18);
 156   // table[19]
 157   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 158   rsaz_1024_scatter5_avx2(table_s, result, 19);
 159
 160   // table[11]
 161   rsaz_1024_gather5_avx2(result, table_s, 10);
 162   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 163   rsaz_1024_scatter5_avx2(table_s, result, 11);
 164   // table[22]
 165   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 166   rsaz_1024_scatter5_avx2(table_s, result, 22);
 167   // table[23]
 168   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 169   rsaz_1024_scatter5_avx2(table_s, result, 23);
 170
 171   // table[13]
 172   rsaz_1024_gather5_avx2(result, table_s, 12);
 173   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 174   rsaz_1024_scatter5_avx2(table_s, result, 13);
 175   // table[26]
 176   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 177   rsaz_1024_scatter5_avx2(table_s, result, 26);
 178   // table[27]
 179   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 180   rsaz_1024_scatter5_avx2(table_s, result, 27);
 181
 182   // table[15]
 183   rsaz_1024_gather5_avx2(result, table_s, 14);
 184   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 185   rsaz_1024_scatter5_avx2(table_s, result, 15);
 186   // table[30]
 187   rsaz_1024_sqr_avx2(result, result, m, k0, 1);
 188   rsaz_1024_scatter5_avx2(table_s, result, 30);
 189   // table[31]
 190   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 191   rsaz_1024_scatter5_avx2(table_s, result, 31);
 192 #endif
 193
 194   const uint8_t *p_str = (const uint8_t *)exponent;
 195
 196   // load first window
 197   int wvalue = p_str[127] >> 3;
 198   rsaz_1024_gather5_avx2(result, table_s, wvalue);
 199
 200   int index = 1014;
 201   while (index > -1) {  // Loop for the remaining 127 windows.
 202
 203     rsaz_1024_sqr_avx2(result, result, m, k0, 5);
 204
 205     uint16_t wvalue_16;
 206     memcpy(&wvalue_16, &p_str[index / 8], sizeof(wvalue_16));
 207     wvalue = wvalue_16;
 208     wvalue = (wvalue >> (index % 8)) & 31;
 209     index -= 5;
 210
 211     rsaz_1024_gather5_avx2(a_inv, table_s, wvalue);  // Borrow |a_inv|.
 212     rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 213   }
 214
 215   // Square four times.
 216   rsaz_1024_sqr_avx2(result, result, m, k0, 4);
 217
 218   wvalue = p_str[0] & 15;
 219
 220   rsaz_1024_gather5_avx2(a_inv, table_s, wvalue);  // Borrow |a_inv|.
 221   rsaz_1024_mul_avx2(result, result, a_inv, m, k0);
 222
 223   // Convert from Montgomery.
 224   rsaz_1024_mul_avx2(result, result, one, m, k0);
 225
 226   rsaz_1024_red2norm_avx2(result_norm, result);
 227
 228   OPENSSL_cleanse(storage, sizeof(storage));
 229 }
 230
 231 #endif  // OPENSSL_X86_64