1 /* 2 * Copyright 2013-2023 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2012, Intel Corporation. All Rights Reserved. 4 * 5 * Licensed under the Apache License 2.0 (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/opensslconf.h> 16 #include "internal/common.h" 17 #include "rsaz_exp.h" 18 19 #ifndef RSAZ_ENABLED 20 NON_EMPTY_TRANSLATION_UNIT 21 #else 22 23 /* 24 * See crypto/bn/asm/rsaz-avx2.pl for further details. 25 */ 26 void rsaz_1024_norm2red_avx2(void *red, const void *norm); 27 void rsaz_1024_mul_avx2(void *ret, const void *a, const void *b, 28 const void *n, BN_ULONG k); 29 void rsaz_1024_sqr_avx2(void *ret, const void *a, const void *n, BN_ULONG k, 30 int cnt); 31 void rsaz_1024_scatter5_avx2(void *tbl, const void *val, int i); 32 void rsaz_1024_gather5_avx2(void *val, const void *tbl, int i); 33 void rsaz_1024_red2norm_avx2(void *norm, const void *red); 34 35 #if defined(__SUNPRO_C) 36 # pragma align 64(one,two80) 37 #endif 38 39 ALIGN64 static const BN_ULONG one[40] = { 40 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 41 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 42 }; 43 44 ALIGN64 static const BN_ULONG two80[40] = { 45 0, 0, 1 << 22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 46 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 47 }; 48 49 void RSAZ_1024_mod_exp_avx2(BN_ULONG result_norm[16], 50 const BN_ULONG base_norm[16], 51 const BN_ULONG exponent[16], 52 const BN_ULONG m_norm[16], const BN_ULONG RR[16], 53 BN_ULONG k0) 54 { 55 unsigned char storage[320 * 3 + 32 * 9 * 16 + 64]; /* 5.5KB */ 56 unsigned char *p_str = storage + (64 - ((size_t)storage % 64)); 57 unsigned char *a_inv, *m, *result; 58 unsigned char *table_s = p_str + 320 * 3; 59 unsigned char *R2 = table_s; /* borrow */ 60 int index; 61 int wvalue; 62 BN_ULONG tmp[16]; 63 64 if ((((size_t)p_str & 4095) + 320) >> 12) { 65 result = p_str; 66 a_inv = p_str + 320; 67 m = p_str + 320 * 2; /* should not cross page */ 68 } else { 69 m = p_str; /* should not cross page */ 70 result = p_str + 320; 71 a_inv = p_str + 320 * 2; 72 } 73 74 rsaz_1024_norm2red_avx2(m, m_norm); 75 rsaz_1024_norm2red_avx2(a_inv, base_norm); 76 rsaz_1024_norm2red_avx2(R2, RR); 77 78 rsaz_1024_mul_avx2(R2, R2, R2, m, k0); 79 rsaz_1024_mul_avx2(R2, R2, two80, m, k0); 80 81 /* table[0] = 1 */ 82 rsaz_1024_mul_avx2(result, R2, one, m, k0); 83 /* table[1] = a_inv^1 */ 84 rsaz_1024_mul_avx2(a_inv, a_inv, R2, m, k0); 85 86 rsaz_1024_scatter5_avx2(table_s, result, 0); 87 rsaz_1024_scatter5_avx2(table_s, a_inv, 1); 88 89 /* table[2] = a_inv^2 */ 90 rsaz_1024_sqr_avx2(result, a_inv, m, k0, 1); 91 rsaz_1024_scatter5_avx2(table_s, result, 2); 92 #if 0 93 /* this is almost 2x smaller and less than 1% slower */ 94 for (index = 3; index < 32; index++) { 95 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 96 rsaz_1024_scatter5_avx2(table_s, result, index); 97 } 98 #else 99 /* table[4] = a_inv^4 */ 100 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 101 rsaz_1024_scatter5_avx2(table_s, result, 4); 102 /* table[8] = a_inv^8 */ 103 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 104 rsaz_1024_scatter5_avx2(table_s, result, 8); 105 /* table[16] = a_inv^16 */ 106 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 107 rsaz_1024_scatter5_avx2(table_s, result, 16); 108 /* table[17] = a_inv^17 */ 109 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 110 rsaz_1024_scatter5_avx2(table_s, result, 17); 111 112 /* table[3] */ 113 rsaz_1024_gather5_avx2(result, table_s, 2); 114 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 115 rsaz_1024_scatter5_avx2(table_s, result, 3); 116 /* table[6] */ 117 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 118 rsaz_1024_scatter5_avx2(table_s, result, 6); 119 /* table[12] */ 120 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 121 rsaz_1024_scatter5_avx2(table_s, result, 12); 122 /* table[24] */ 123 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 124 rsaz_1024_scatter5_avx2(table_s, result, 24); 125 /* table[25] */ 126 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 127 rsaz_1024_scatter5_avx2(table_s, result, 25); 128 129 /* table[5] */ 130 rsaz_1024_gather5_avx2(result, table_s, 4); 131 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 132 rsaz_1024_scatter5_avx2(table_s, result, 5); 133 /* table[10] */ 134 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 135 rsaz_1024_scatter5_avx2(table_s, result, 10); 136 /* table[20] */ 137 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 138 rsaz_1024_scatter5_avx2(table_s, result, 20); 139 /* table[21] */ 140 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 141 rsaz_1024_scatter5_avx2(table_s, result, 21); 142 143 /* table[7] */ 144 rsaz_1024_gather5_avx2(result, table_s, 6); 145 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 146 rsaz_1024_scatter5_avx2(table_s, result, 7); 147 /* table[14] */ 148 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 149 rsaz_1024_scatter5_avx2(table_s, result, 14); 150 /* table[28] */ 151 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 152 rsaz_1024_scatter5_avx2(table_s, result, 28); 153 /* table[29] */ 154 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 155 rsaz_1024_scatter5_avx2(table_s, result, 29); 156 157 /* table[9] */ 158 rsaz_1024_gather5_avx2(result, table_s, 8); 159 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 160 rsaz_1024_scatter5_avx2(table_s, result, 9); 161 /* table[18] */ 162 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 163 rsaz_1024_scatter5_avx2(table_s, result, 18); 164 /* table[19] */ 165 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 166 rsaz_1024_scatter5_avx2(table_s, result, 19); 167 168 /* table[11] */ 169 rsaz_1024_gather5_avx2(result, table_s, 10); 170 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 171 rsaz_1024_scatter5_avx2(table_s, result, 11); 172 /* table[22] */ 173 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 174 rsaz_1024_scatter5_avx2(table_s, result, 22); 175 /* table[23] */ 176 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 177 rsaz_1024_scatter5_avx2(table_s, result, 23); 178 179 /* table[13] */ 180 rsaz_1024_gather5_avx2(result, table_s, 12); 181 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 182 rsaz_1024_scatter5_avx2(table_s, result, 13); 183 /* table[26] */ 184 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 185 rsaz_1024_scatter5_avx2(table_s, result, 26); 186 /* table[27] */ 187 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 188 rsaz_1024_scatter5_avx2(table_s, result, 27); 189 190 /* table[15] */ 191 rsaz_1024_gather5_avx2(result, table_s, 14); 192 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 193 rsaz_1024_scatter5_avx2(table_s, result, 15); 194 /* table[30] */ 195 rsaz_1024_sqr_avx2(result, result, m, k0, 1); 196 rsaz_1024_scatter5_avx2(table_s, result, 30); 197 /* table[31] */ 198 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 199 rsaz_1024_scatter5_avx2(table_s, result, 31); 200 #endif 201 202 /* load first window */ 203 p_str = (unsigned char *)exponent; 204 wvalue = p_str[127] >> 3; 205 rsaz_1024_gather5_avx2(result, table_s, wvalue); 206 207 index = 1014; 208 209 while (index > -1) { /* loop for the remaining 127 windows */ 210 211 rsaz_1024_sqr_avx2(result, result, m, k0, 5); 212 213 wvalue = (p_str[(index / 8) + 1] << 8) | p_str[index / 8]; 214 wvalue = (wvalue >> (index % 8)) & 31; 215 index -= 5; 216 217 rsaz_1024_gather5_avx2(a_inv, table_s, wvalue); /* borrow a_inv */ 218 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 219 } 220 221 /* square four times */ 222 rsaz_1024_sqr_avx2(result, result, m, k0, 4); 223 224 wvalue = p_str[0] & 15; 225 226 rsaz_1024_gather5_avx2(a_inv, table_s, wvalue); /* borrow a_inv */ 227 rsaz_1024_mul_avx2(result, result, a_inv, m, k0); 228 229 /* from Montgomery */ 230 rsaz_1024_mul_avx2(result, result, one, m, k0); 231 232 rsaz_1024_red2norm_avx2(result_norm, result); 233 234 bn_reduce_once_in_place(result_norm, /*carry=*/0, m_norm, tmp, 16); 235 236 OPENSSL_cleanse(storage, sizeof(storage)); 237 OPENSSL_cleanse(tmp, sizeof(tmp)); 238 } 239 240 /* 241 * See crypto/bn/rsaz-x86_64.pl for further details. 242 */ 243 void rsaz_512_mul(void *ret, const void *a, const void *b, const void *n, 244 BN_ULONG k); 245 void rsaz_512_mul_scatter4(void *ret, const void *a, const void *n, 246 BN_ULONG k, const void *tbl, unsigned int power); 247 void rsaz_512_mul_gather4(void *ret, const void *a, const void *tbl, 248 const void *n, BN_ULONG k, unsigned int power); 249 void rsaz_512_mul_by_one(void *ret, const void *a, const void *n, BN_ULONG k); 250 void rsaz_512_sqr(void *ret, const void *a, const void *n, BN_ULONG k, 251 int cnt); 252 void rsaz_512_scatter4(void *tbl, const BN_ULONG *val, int power); 253 void rsaz_512_gather4(BN_ULONG *val, const void *tbl, int power); 254 255 void RSAZ_512_mod_exp(BN_ULONG result[8], 256 const BN_ULONG base[8], const BN_ULONG exponent[8], 257 const BN_ULONG m[8], BN_ULONG k0, const BN_ULONG RR[8]) 258 { 259 unsigned char storage[16 * 8 * 8 + 64 * 2 + 64]; /* 1.2KB */ 260 unsigned char *table = storage + (64 - ((size_t)storage % 64)); 261 BN_ULONG *a_inv = (BN_ULONG *)(table + 16 * 8 * 8); 262 BN_ULONG *temp = (BN_ULONG *)(table + 16 * 8 * 8 + 8 * 8); 263 unsigned char *p_str = (unsigned char *)exponent; 264 int index; 265 unsigned int wvalue; 266 BN_ULONG tmp[8]; 267 268 /* table[0] = 1_inv */ 269 temp[0] = 0 - m[0]; 270 temp[1] = ~m[1]; 271 temp[2] = ~m[2]; 272 temp[3] = ~m[3]; 273 temp[4] = ~m[4]; 274 temp[5] = ~m[5]; 275 temp[6] = ~m[6]; 276 temp[7] = ~m[7]; 277 rsaz_512_scatter4(table, temp, 0); 278 279 /* table [1] = a_inv^1 */ 280 rsaz_512_mul(a_inv, base, RR, m, k0); 281 rsaz_512_scatter4(table, a_inv, 1); 282 283 /* table [2] = a_inv^2 */ 284 rsaz_512_sqr(temp, a_inv, m, k0, 1); 285 rsaz_512_scatter4(table, temp, 2); 286 287 for (index = 3; index < 16; index++) 288 rsaz_512_mul_scatter4(temp, a_inv, m, k0, table, index); 289 290 /* load first window */ 291 wvalue = p_str[63]; 292 293 rsaz_512_gather4(temp, table, wvalue >> 4); 294 rsaz_512_sqr(temp, temp, m, k0, 4); 295 rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue & 0xf); 296 297 for (index = 62; index >= 0; index--) { 298 wvalue = p_str[index]; 299 300 rsaz_512_sqr(temp, temp, m, k0, 4); 301 rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue >> 4); 302 303 rsaz_512_sqr(temp, temp, m, k0, 4); 304 rsaz_512_mul_gather4(temp, temp, table, m, k0, wvalue & 0x0f); 305 } 306 307 /* from Montgomery */ 308 rsaz_512_mul_by_one(result, temp, m, k0); 309 310 bn_reduce_once_in_place(result, /*carry=*/0, m, tmp, 8); 311 312 OPENSSL_cleanse(storage, sizeof(storage)); 313 OPENSSL_cleanse(tmp, sizeof(tmp)); 314 } 315 316 #endif 317