crypton-2.2.4: cbits/crypton_powm_ifma.c
/* Two secure exponentiations at once with AVX-512 IFMA, the CRT halves of
* RSA-2048, -3072 and -4096: crypton_powm_sec's walk with a five-bit window,
* over the multiplication generated by cbits/crypton_powm_ifma.py. */
#include <stdlib.h>
#include <string.h>
#include <crypton_bignum.h>
#include <crypton_bzero.h>
#include <crypton_powm.h>
#if defined(__x86_64__) && (defined(__GNUC__) || defined(__clang__))
#include <crypton_cpu.h>
#include "crypton_powm_ifma.h"
#define WIN 5
typedef void (*amm_fn)(uint64_t *, const uint64_t *, const uint64_t *, const uint64_t *,
uint64_t, uint64_t *, const uint64_t *, const uint64_t *,
const uint64_t *, uint64_t);
typedef void (*sel_fn)(uint64_t *, const uint64_t *, uint64_t, uint64_t *,
const uint64_t *, uint64_t);
/* limbs of 64 bits to digits of 52, d of them; the rest of the w words zero */
static void to_digits(uint64_t *dg, uint32_t w, const limb_t *l, uint32_t n, uint32_t d)
{
uint32_t i;
memset(dg, 0, w * sizeof(uint64_t));
for (i = 0; i < d; i++) {
uint32_t bit = 52 * i, li = bit / 64, sh = bit % 64;
uint64_t v = li < n ? l[li] >> sh : 0;
if (sh > 12 && li + 1 < n)
v |= l[li + 1] << (64 - sh);
dg[i] = v & IFMA_MASK52;
}
}
static void from_digits(limb_t *l, uint32_t n, const uint64_t *dg, uint32_t d)
{
uint32_t i;
memset(l, 0, n * sizeof(limb_t));
for (i = 0; i < d; i++) {
uint32_t bit = 52 * i, li = bit / 64, sh = bit % 64;
if (li < n)
l[li] |= dg[i] << sh;
if (sh > 12 && li + 1 < n)
l[li + 1] |= dg[i] >> (64 - sh);
}
}
/* Window k from the bottom of a big-endian exponent of len bytes. Which
* window is read is the loop counter's business, not the exponent's. */
static uint64_t window(const uint8_t *e, uint32_t len, uint32_t k)
{
uint64_t v = 0;
uint32_t j;
for (j = 0; j < WIN; j++) {
uint32_t bit = k * WIN + j;
if (bit < 8 * len)
v |= (uint64_t) ((e[len - 1 - bit / 8] >> (bit % 8)) & 1) << j;
}
return v;
}
/* m and k0 in digits, and R^2 mod m for R = 2^(52d): crypton's R^2 is for
* 2^(64n), so it is doubled the rest of the way */
static int setup(const uint8_t *mod, uint32_t modlen, uint32_t n, uint32_t d, uint32_t w,
limb_t *ml, uint64_t *md, uint64_t *rr, uint64_t *k0, limb_t *t)
{
limb_t *r2 = t + 4 * n;
uint32_t j;
if (from_be(ml, n, mod, modlen) != 0 || (ml[0] & 1) == 0)
return 1;
*k0 = mont_n0(ml[0]);
mont_r2(r2, ml, *k0, n, t);
for (j = 0; j < 2 * (52 * d - 64 * n); j++)
dbl_mod(r2, ml, n, t);
to_digits(md, w, ml, n, d);
to_digits(rr, w, r2, n, d);
return 0;
}
int crypton_powm_sec_x2(uint8_t *out1, const uint8_t *base1, uint32_t baselen1,
const uint8_t *exp1, uint32_t explen1,
const uint8_t *mod1, uint32_t modlen1,
uint8_t *out2, const uint8_t *base2, uint32_t baselen2,
const uint8_t *exp2, uint32_t explen2,
const uint8_t *mod2, uint32_t modlen2)
{
uint32_t n, d, w, nwin, k, j;
amm_fn amm;
sel_fn sel;
uint64_t *space, *m1, *m2, *rr1, *rr2, *x1, *x2, *s1, *s2, *one, *t1, *t2, k1, k2;
limb_t *l1, *l2, *lt, *lt2;
size_t words;
if (modlen1 != modlen2 || explen1 != explen2)
return 1;
if ((crypton_x86_simd_features() & CRYPTON_X86_IFMA) == 0)
return 1;
switch (modlen1) {
case 128: d = 20; amm = ifma_amm20_x2; sel = ifma_sel5; break;
case 192: d = 30; amm = ifma_amm30_x2; sel = ifma_sel8; break;
case 256: d = 40; amm = ifma_amm40_x2; sel = ifma_sel10; break;
default: return 1;
}
n = modlen1 / 8;
w = 4 * ((d + 3) / 4);
/* nine numbers in digits, two tables of 32, and limbs for the setup */
words = (size_t) w * (9 + 2 * 32) + (size_t) n * 12;
space = calloc(words, sizeof(uint64_t));
if (space == NULL)
return 1;
m1 = space; m2 = m1 + w; rr1 = m2 + w; rr2 = rr1 + w;
x1 = rr2 + w; x2 = x1 + w; s1 = x2 + w; s2 = s1 + w; one = s2 + w;
t1 = one + w; t2 = t1 + 32 * w;
l1 = (limb_t *)(t2 + 32 * w); l2 = l1 + n; lt = l2 + n; lt2 = lt + n;
if (setup(mod1, modlen1, n, d, w, l1, m1, rr1, &k1, lt) != 0
|| setup(mod2, modlen2, n, d, w, l2, m2, rr2, &k2, lt) != 0)
goto fail;
/* the bases, under their moduli as the contract says, into digits */
if (from_be(lt, n, base1, baselen1) != 0 || from_be(lt2, n, base2, baselen2) != 0)
goto fail;
to_digits(s1, w, lt, n, d);
to_digits(s2, w, lt2, n, d);
/* table[0] = R and table[1] = b R in Montgomery form, table[k] = b^k R */
one[0] = 1;
amm(t1, one, rr1, m1, k1, t2, one, rr2, m2, k2);
amm(t1 + w, s1, rr1, m1, k1, t2 + w, s2, rr2, m2, k2);
for (k = 2; k < 32; k++)
amm(t1 + k * w, t1 + (k - 1) * w, t1 + w, m1, k1,
t2 + k * w, t2 + (k - 1) * w, t2 + w, m2, k2);
memcpy(x1, t1, w * sizeof(uint64_t));
memcpy(x2, t2, w * sizeof(uint64_t));
nwin = (8 * explen1 + WIN - 1) / WIN;
for (k = nwin; k > 0; k--) {
for (j = 0; j < WIN; j++)
amm(x1, x1, x1, m1, k1, x2, x2, x2, m2, k2);
sel(s1, t1, window(exp1, explen1, k - 1), s2, t2, window(exp2, explen2, k - 1));
amm(x1, x1, s1, m1, k1, x2, x2, s2, m2, k2);
}
/* out of Montgomery form, then under m with one masked subtraction */
amm(x1, x1, one, m1, k1, x2, x2, one, m2, k2);
from_digits(lt, n, x1, d);
select_n(lt, lt2, lt, sub_n(lt2, lt, l1, n) ^ 1, n);
to_be(out1, modlen1, lt, n);
from_digits(lt, n, x2, d);
select_n(lt, lt2, lt, sub_n(lt2, lt, l2, n) ^ 1, n);
to_be(out2, modlen2, lt, n);
crypton_bzero(space, words * sizeof(uint64_t));
free(space);
return 0;
fail:
crypton_bzero(space, words * sizeof(uint64_t));
free(space);
return 1;
}
#else
int crypton_powm_sec_x2(uint8_t *out1, const uint8_t *base1, uint32_t baselen1,
const uint8_t *exp1, uint32_t explen1,
const uint8_t *mod1, uint32_t modlen1,
uint8_t *out2, const uint8_t *base2, uint32_t baselen2,
const uint8_t *exp2, uint32_t explen2,
const uint8_t *mod2, uint32_t modlen2)
{
(void) out1; (void) base1; (void) baselen1; (void) exp1; (void) explen1;
(void) mod1; (void) modlen1; (void) out2; (void) base2; (void) baselen2;
(void) exp2; (void) explen2; (void) mod2; (void) modlen2;
return 1;
}
#endif