#include <stdlib.h>

/* cnd-memcpy.c

   Copyright (C) 2018 Niels Möller

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or

   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free

       Software Foundation; either version 3 of the License, or (at your

       option) any later version.

   or

     * the GNU General Public License as published by the Free

       Software Foundation; either version 2 of the License, or (at your

       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   General Public License for more details.

   You should have received copies of the GNU General Public License and

   the GNU Lesser General Public License along with this program.  If

   not, see http://www.gnu.org/licenses/.

*/

#if HAVE_CONFIG_H

# include "config.h"

#endif

#include "memops.h"

void

cnd_memcpy(int cnd, volatile void *dst, const volatile void *src, size_t n)

{

  const volatile unsigned char *sp = src;

  volatile unsigned char *dp = dst;

  volatile unsigned char c;

  volatile unsigned char m;

  size_t i;

  m = -(unsigned char) cnd;

  for (i = 0; i < n; i++)

    {

      c = (sp[i] & m);

      c |= (dp[i] & ~m);

      dp[i] = c;

    }

}

#include <stdlib.h>

mpn_get_base256 (uint8_t *rp, size_t rn,

		 const mp_limb_t *xp, mp_size_t xn)

{

  unsigned bits;

  mp_limb_t in;

  for (bits = in = 0; xn > 0 && rn > 0; )

    {

      if (bits >= 8)

	{

	  rp[--rn] = in;

	  in >>= 8;

	  bits -= 8;

	}

      else

	{

	  uint8_t old = in;

	  in = *xp++;

	  xn--;

	  rp[--rn] = old | (in << bits);

	  in >>= (8 - bits);

	  bits += GMP_NUMB_BITS - 8;

	}

    }

  while (rn > 0)

    {

      rp[--rn] = in;

      in >>= 8;

    }

}

void

#define mpn_get_base256 _nettle_mpn_get_base256

#define NETTLE_OCTET_SIZE_TO_LIMB_SIZE(n) \

  (((n) * 8 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)

mpn_get_base256 (uint8_t *rp, size_t rn,

	         const mp_limb_t *xp, mp_size_t xn);

void

		 cnd-memcpy.c \

		  pkcs1-sec-decrypt.c \

		  rsa-sec-compute-root.c \

	rsa-internal.h \

#define cnd_memcpy nettle_cnd_memcpy

/* Side-channel silent conditional memcpy. cnd must be 0 (nop) or 1

   (copy). */

void

cnd_memcpy(int cnd, volatile void *dst, const volatile void *src, size_t n);

#include "rsa-internal.h"

/* pkcs1-sec-decrypt.c

   The RSA publickey algorithm. Side channel resistant PKCS#1 decryption.

   Copyright (C) 2001, 2012 Niels Möller

   Copyright (C) 2018 Red Hat, Inc.

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or

   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free

       Software Foundation; either version 3 of the License, or (at your

       option) any later version.

   or

     * the GNU General Public License as published by the Free

       Software Foundation; either version 2 of the License, or (at your

       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   General Public License for more details.

   You should have received copies of the GNU General Public License and

   the GNU Lesser General Public License along with this program.  If

   not, see http://www.gnu.org/licenses/.

*/

#if HAVE_CONFIG_H

# include "config.h"

#endif

#include <assert.h>

#include <string.h>

#include "memops.h"

#include "gmp-glue.h"

#include "rsa.h"

#include "rsa-internal.h"

/* Inputs are always cast to uint32_t values. But all values used in this

 * function should never exceed the maximum value of a uint32_t anyway.

 * these macros returns 1 on success, 0 on failure */

#define NOT_EQUAL(a, b) \

    ((0U - ((uint32_t)(a) ^ (uint32_t)(b))) >> 31)

#define EQUAL(a, b) \

    ((((uint32_t)(a) ^ (uint32_t)(b)) - 1U) >> 31)

#define GREATER_OR_EQUAL(a, b) \

    (1U - (((uint32_t)(a) - (uint32_t)(b)) >> 31))

int

_pkcs1_sec_decrypt (size_t length, uint8_t *message,

                    size_t padded_message_length,

                    const volatile uint8_t *padded_message)

{

  volatile int ok;

  size_t i, t;

  assert (padded_message_length >= length);

  t = padded_message_length - length - 1;

  /* Check format, padding, message_size */

  ok = EQUAL(padded_message[0], 0);       /* ok if padded_message[0] == 0 */

  ok &= EQUAL(padded_message[1], 2);      /* ok if padded_message[1] == 2 */

  for (i = 2; i < t; i++)      /* check padding has no zeros */

    {

      ok &= NOT_EQUAL(padded_message[i], 0);

    }

  ok &= EQUAL(padded_message[t], 0);      /* ok if terminator == 0 */

  /* fill destination buffer regardless of outcome */

  cnd_memcpy(ok, message, padded_message + t + 1, length);

  return ok;

}

int

_pkcs1_sec_decrypt_variable(size_t *length, uint8_t *message,

                            size_t padded_message_length,

                            const volatile uint8_t *padded_message)

{

  volatile int not_found = 1;

  volatile int ok;

  volatile size_t offset;

  size_t buflen, msglen;

  size_t shift, i;

  /* Check format, padding, message_size */

  ok = EQUAL(padded_message[0], 0);

  ok &= EQUAL(padded_message[1], 2);

  /* length is discovered in a side-channel silent way.

   * not_found goes to 0 when the terminator is found.

   * offset strts at 3 as it includes the terminator and

   * the fomat bytes already */

  offset = 3;

  for (i = 2; i < padded_message_length; i++)

    {

      not_found &= NOT_EQUAL(padded_message[i], 0);

      offset += not_found;

    }

  /* check if we ran out of buffer */

  ok &= NOT_EQUAL(not_found, 1);

  /* padding must be >= 11 (2 format bytes + 8 pad bytes min. + terminator) */

  ok &= GREATER_OR_EQUAL(offset, 11);

  /* offset can vary between 3 and padded_message_length, due to the loop

   * above, therefore msglen can't underflow */

  msglen = padded_message_length - offset;

  /* we always fill the whole buffer but only up to

   * padded_message_length length */

  buflen = *length;

  if (buflen > padded_message_length) { /* input independent branch */

    buflen = padded_message_length;

  }

  /* if the message length is larger than the buffer we must fail */

  ok &= GREATER_OR_EQUAL(buflen, msglen);

  /* fill destination buffer fully regardless of outcome. Copies the message

   * in a memory access independent way. The destination message buffer will

   * be clobbered past the message length. */

  shift = padded_message_length - buflen;

  cnd_memcpy(ok, message, padded_message + shift, buflen);

  offset -= shift;

  /* In this loop, the bits of the 'offset' variable are used as shifting

   * conditions, starting from the least significant bit. The end result is

   * that the buffer is shifted left exactly 'offset' bytes. */

  for (shift = 1; shift < buflen; shift <<= 1, offset >>= 1)

    {

      /* 'ok' is both a least significant bit mask and a condition */

      cnd_memcpy(offset & ok, message, message + shift, buflen - shift);

    }

  /* update length only if we succeeded, otherwise leave unchanged */

  *length = (msglen & (-(size_t) ok)) + (*length & ((size_t) ok - 1));

  return ok;

}

#define rsa_sec_decrypt nettle_rsa_sec_decrypt

/* like rsa_decrypt_tr but with additional side-channel resistance.

 * NOTE: the length of the final message must be known in advance. */

int

rsa_sec_decrypt(const struct rsa_public_key *pub,

	        const struct rsa_private_key *key,

	        void *random_ctx, nettle_random_func *random,

	        size_t length, uint8_t *message,

	        const mpz_t gibberish);

/* rsa-internal.h

   The RSA publickey algorithm.

   Copyright (C) 2001, 2002 Niels Möller

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or

   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free

       Software Foundation; either version 3 of the License, or (at your

       option) any later version.

   or

     * the GNU General Public License as published by the Free

       Software Foundation; either version 2 of the License, or (at your

       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   General Public License for more details.

   You should have received copies of the GNU General Public License and

   the GNU Lesser General Public License along with this program.  If

   not, see http://www.gnu.org/licenses/.

*/

#ifndef NETTLE_RSA_INTERNAL_H_INCLUDED

#define NETTLE_RSA_INTERNAL_H_INCLUDED

#include "nettle-types.h"

#include "rsa.h"

#define _rsa_sec_compute_root_itch _nettle_rsa_sec_compute_root_itch

#define _rsa_sec_compute_root _nettle_rsa_sec_compute_root

#define _rsa_sec_compute_root_tr _nettle_rsa_sec_compute_root_tr

#define _pkcs1_sec_decrypt _nettle_pkcs1_sec_decrypt

#define _pkcs1_sec_decrypt_variable _nettle_pkcs1_sec_decrypt_variable

/* side-channel silent root computation */

mp_size_t

_rsa_sec_compute_root_itch(const struct rsa_private_key *key);

void

_rsa_sec_compute_root(const struct rsa_private_key *key,

                      mp_limb_t *rp, const mp_limb_t *mp,

                      mp_limb_t *scratch);

/* Safe side-channel silent variant, using RSA blinding, and checking the

 * result after CRT. */

int

_rsa_sec_compute_root_tr(const struct rsa_public_key *pub,

			 const struct rsa_private_key *key,

			 void *random_ctx, nettle_random_func *random,

			 mp_limb_t *x, const mp_limb_t *m, size_t mn);

/* additional resistance to memory access side-channel attacks.

 * Note: message buffer is returned unchanged on error */

int

_pkcs1_sec_decrypt (size_t length, uint8_t *message,

                    size_t padded_message_length,

                    const volatile uint8_t *padded_message);

int

_pkcs1_sec_decrypt_variable(size_t *length, uint8_t *message,

                            size_t padded_message_length,

                            const volatile uint8_t *padded_message);

#endif /* NETTLE_RSA_INTERNAL_H_INCLUDED */

/* rsa-sec-compute-root.c

   Side-channel silent RSA root computation.

   Copyright (C) 2018 Niels Möller

   Copyright (C) 2018 Red Hat, Inc

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or

   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free

       Software Foundation; either version 3 of the License, or (at your

       option) any later version.

   or

     * the GNU General Public License as published by the Free

       Software Foundation; either version 2 of the License, or (at your

       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   General Public License for more details.

   You should have received copies of the GNU General Public License and

   the GNU Lesser General Public License along with this program.  If

   not, see http://www.gnu.org/licenses/.

*/

#if HAVE_CONFIG_H

# include "config.h"

#endif

#include <assert.h>

#include "rsa.h"

#include "rsa-internal.h"

#include "gmp-glue.h"

#if !NETTLE_USE_MINI_GMP

#define MAX(a, b) ((a) > (b) ? (a) : (b))

/* Like mpn_sec_mul_itch, monotonously increasing in operand sizes. */

static mp_size_t

sec_mul_itch (mp_size_t an, mp_size_t bn)

{

  if (an >= bn)

    return mpn_sec_mul_itch (an, bn);

  else

    return mpn_sec_mul_itch (bn, an);

}

/* Writes an + bn limbs to the rp area */

static void

sec_mul (mp_limb_t *rp,

	 const mp_limb_t *ap, mp_size_t an,

	 const mp_limb_t *bp, mp_size_t bn, mp_limb_t *scratch)

{

  if (an >= bn)

    mpn_sec_mul (rp, ap, an, bp, bn, scratch);

  else

    mpn_sec_mul (rp, bp, bn, ap, an, scratch);

}

static mp_size_t

sec_mod_mul_itch (mp_size_t an, mp_size_t bn, mp_size_t mn)

{

  mp_size_t mul_itch = sec_mul_itch (an, bn);

  mp_size_t mod_itch = mpn_sec_div_r_itch (an + bn, mn);

  return MAX(mul_itch, mod_itch);

}

/* Sets r <-- a b % m. Needs space for an + bn limbs at rp. It is

   required than an + bn >= mn. */

static void

sec_mod_mul (mp_limb_t *rp,

	     const mp_limb_t *ap, mp_size_t an,

	     const mp_limb_t *bp, mp_size_t bn,

	     const mp_limb_t *mp, mp_size_t mn,

	     mp_limb_t *scratch)

{

  assert (an + bn >= mn);

  sec_mul (rp, ap, an, bp, bn, scratch);

  mpn_sec_div_r (rp, an + bn, mp, mn, scratch);

}

static mp_size_t

sec_powm_itch (mp_size_t bn, mp_size_t en, mp_size_t mn)

{

  mp_size_t mod_itch = bn + mpn_sec_div_r_itch (bn, mn);

  mp_size_t pow_itch = mn + mpn_sec_powm_itch (mn, en * GMP_NUMB_BITS, mn);

  return MAX (mod_itch, pow_itch);

}

/* Sets r <-- b ^ e % m. Performs an initial reduction b mod m, and

   requires bn >= mn. */

static void

sec_powm (mp_limb_t *rp,

	  const mp_limb_t *bp, mp_size_t bn,

	  const mp_limb_t *ep, mp_size_t en,

	  const mp_limb_t *mp, mp_size_t mn, mp_limb_t *scratch)

{

  assert (bn >= mn);

  assert (en <= mn);

  mpn_copyi (scratch, bp, bn);

  mpn_sec_div_r (scratch, bn, mp, mn, scratch + bn);

  mpn_sec_powm (rp, scratch, mn, ep, en * GMP_NUMB_BITS, mp, mn,

		scratch + mn);

}

mp_size_t

_rsa_sec_compute_root_itch (const struct rsa_private_key *key)

{

  mp_size_t nn = NETTLE_OCTET_SIZE_TO_LIMB_SIZE (key->size);

  mp_size_t pn = mpz_size (key->p);

  mp_size_t qn = mpz_size (key->q);

  mp_size_t an = mpz_size (key->a);

  mp_size_t bn = mpz_size (key->b);

  mp_size_t cn = mpz_size (key->c);

  mp_size_t powm_p_itch = sec_powm_itch (nn, an, pn);

  mp_size_t powm_q_itch = sec_powm_itch (nn, bn, qn);

  mp_size_t mod_mul_itch = cn + MAX(pn, qn) 

    + sec_mod_mul_itch (MAX(pn, qn), cn, pn);

  mp_size_t mul_itch = sec_mul_itch (qn, pn);

  mp_size_t add_1_itch = mpn_sec_add_1_itch (nn - qn);

  /* pn + qn for the product q * r_mod_p' */

  mp_size_t itch = pn + qn + MAX (mul_itch, add_1_itch);

  itch = MAX (itch, powm_p_itch);

  itch = MAX (itch, powm_q_itch);

  itch = MAX (itch, mod_mul_itch);

  /* pn + qn for the r_mod_p and r_mod_q temporaries. */

  return pn + qn + itch;

}

void

_rsa_sec_compute_root (const struct rsa_private_key *key,

		       mp_limb_t *rp, const mp_limb_t *mp,

		       mp_limb_t *scratch)

{

  mp_size_t nn = NETTLE_OCTET_SIZE_TO_LIMB_SIZE (key->size);

  /* The common case is pn = qn. This function would be simpler if we

   * could require that pn >= qn. */

  const mp_limb_t *pp = mpz_limbs_read (key->p);

  const mp_limb_t *qp = mpz_limbs_read (key->q);

  mp_size_t pn = mpz_size (key->p);

  mp_size_t qn = mpz_size (key->q);

  mp_size_t an = mpz_size (key->a);

  mp_size_t bn = mpz_size (key->b);

  mp_size_t cn = mpz_size (key->c);

  mp_limb_t *r_mod_p = scratch;

  mp_limb_t *r_mod_q = scratch + pn;

  mp_limb_t *scratch_out = r_mod_q + qn;

  mp_limb_t cy;

  assert (pn <= nn);

  assert (qn <= nn);

  assert (an <= pn);

  assert (bn <= qn);

  assert (cn <= pn);

  /* Compute r_mod_p = m^d % p = (m%p)^a % p */

  sec_powm (r_mod_p, mp, nn, mpz_limbs_read (key->a), an, pp, pn, scratch_out);

  /* Compute r_mod_q = m^d % q = (m%q)^b % q */

  sec_powm (r_mod_q, mp, nn, mpz_limbs_read (key->b), bn, qp, qn, scratch_out);

  /* Set r_mod_p' = r_mod_p * c % p - r_mod_q * c % p . */

  sec_mod_mul (scratch_out, r_mod_p, pn, mpz_limbs_read (key->c), cn, pp, pn,

	       scratch_out + cn + pn);

  mpn_copyi (r_mod_p, scratch_out, pn);

  sec_mod_mul (scratch_out, r_mod_q, qn, mpz_limbs_read (key->c), cn, pp, pn,

	       scratch_out + cn + qn);

  cy = mpn_sub_n (r_mod_p, r_mod_p, scratch_out, pn);

  cnd_add_n (cy, r_mod_p, pp, pn);

  /* Finally, compute x = r_mod_q + q r_mod_p' */

  sec_mul (scratch_out, qp, qn, r_mod_p, pn, scratch_out + pn + qn);

  cy = mpn_add_n (rp, scratch_out, r_mod_q, qn);

  mpn_sec_add_1 (rp + qn, scratch_out + qn, nn - qn, cy, scratch_out + pn + qn);

}

#endif

/* rsa-sec-decrypt.c

   RSA decryption, using randomized RSA blinding to be more resistant

   to side-channel attacks like timing attacks or cache based memory

   access measurements.

   Copyright (C) 2001, 2012 Niels Möller, Nikos Mavrogiannopoulos

   Copyright (C) 2018 Red Hat, Inc.

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or

   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free

       Software Foundation; either version 3 of the License, or (at your

       option) any later version.

   or

     * the GNU General Public License as published by the Free

       Software Foundation; either version 2 of the License, or (at your

       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   General Public License for more details.

   You should have received copies of the GNU General Public License and

   the GNU Lesser General Public License along with this program.  If

   not, see http://www.gnu.org/licenses/.

*/

#if HAVE_CONFIG_H

# include "config.h"

#endif

#include "rsa.h"

#include "rsa-internal.h"

#include "gmp-glue.h"

int

rsa_sec_decrypt(const struct rsa_public_key *pub,

	        const struct rsa_private_key *key,

	        void *random_ctx, nettle_random_func *random,

	        size_t length, uint8_t *message,

	        const mpz_t gibberish)

{

  TMP_GMP_DECL (m, mp_limb_t);

  TMP_GMP_DECL (em, uint8_t);

  int res;

  TMP_GMP_ALLOC (m, mpz_size(pub->n));

  TMP_GMP_ALLOC (em, key->size);

  res = _rsa_sec_compute_root_tr (pub, key, random_ctx, random, m,

				  mpz_limbs_read(gibberish),

				  mpz_size(gibberish));

  mpn_get_base256 (em, key->size, m, mpz_size(pub->n));

  res &= _pkcs1_sec_decrypt (length, message, key->size, em);

  TMP_GMP_FREE (em);

  TMP_GMP_FREE (m);

  return res;

}

#if NETTLE_USE_MINI_GMP

#else /* !NETTLE_USE_MINI_GMP */

/* Computing an rsa root. */

void

rsa_compute_root(const struct rsa_private_key *key,

		 mpz_t x, const mpz_t m)

{

  TMP_GMP_DECL (scratch, mp_limb_t);

  TMP_GMP_DECL (ml, mp_limb_t);

  mp_limb_t *xl;

  size_t key_size;

  key_size = NETTLE_OCTET_SIZE_TO_LIMB_SIZE(key->size);

  assert(mpz_size (m) <= key_size);

  /* we need a copy because m can be shorter than key_size,

   * but _rsa_sec_compute_root expect all inputs to be

   * normalized to a key_size long buffer length */

  TMP_GMP_ALLOC (ml, key_size);

  mpz_limbs_copy(ml, m, key_size);

  TMP_GMP_ALLOC (scratch, _rsa_sec_compute_root_itch(key));

  xl = mpz_limbs_write (x, key_size);

  _rsa_sec_compute_root (key, xl, ml, scratch);

  mpz_limbs_finish (x, key_size);

  TMP_GMP_FREE (ml);

  TMP_GMP_FREE (scratch);

}

#endif /* !NETTLE_USE_MINI_GMP */

   Copyright (C) 2018 Red Hat Inc.

#include <assert.h>

#include "gmp-glue.h"

#include "rsa-internal.h"

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#if NETTLE_USE_MINI_GMP

int

_rsa_sec_compute_root_tr(const struct rsa_public_key *pub,

			 const struct rsa_private_key *key,

			 void *random_ctx, nettle_random_func *random,

			 mp_limb_t *x, const mp_limb_t *m, size_t mn)

{

  mpz_t mz;

  mpz_t xz;

  int res;

  mpz_init(mz);

  mpz_init(xz);

  mpn_copyi(mpz_limbs_write(mz, mn), m, mn);

  mpz_limbs_finish(mz, mn);

  res = rsa_compute_root_tr(pub, key, random_ctx, random, xz, mz);

  if (res)

    mpz_limbs_copy(x, xz, mpz_size(pub->n));

  mpz_clear(mz);

  mpz_clear(xz);

  return res;

}

#else

/* Blinds m, by computing c = m r^e (mod n), for a random r. Also

   returns the inverse (ri), for use by rsa_unblind. */

static void

rsa_sec_blind (const struct rsa_public_key *pub,

               void *random_ctx, nettle_random_func *random,

               mp_limb_t *c, mp_limb_t *ri, const mp_limb_t *m,

               mp_size_t mn)

{

  const mp_limb_t *ep = mpz_limbs_read (pub->e);

  const mp_limb_t *np = mpz_limbs_read (pub->n);

  mp_bitcnt_t ebn = mpz_sizeinbase (pub->e, 2);

  mp_size_t nn = mpz_size (pub->n);

  size_t itch;

  size_t i2;

  mp_limb_t *scratch;

  TMP_GMP_DECL (tp, mp_limb_t);

  TMP_GMP_DECL (rp, mp_limb_t);

  TMP_GMP_DECL (r, uint8_t);

  TMP_GMP_ALLOC (rp, nn);

  TMP_GMP_ALLOC (r, nn * sizeof(mp_limb_t));

  /* c = m*(r^e) mod n */

  itch = mpn_sec_powm_itch(nn, ebn, nn);

  i2 = mpn_sec_mul_itch(nn, mn);

  itch = MAX(itch, i2);

  i2 = mpn_sec_div_r_itch(nn + mn, nn);

  itch = MAX(itch, i2);

  i2 = mpn_sec_invert_itch(nn);

  itch = MAX(itch, i2);

  TMP_GMP_ALLOC (tp, nn + mn + itch);

  scratch = tp + nn + mn;

  /* ri = r^(-1) */

  do

    {

      random(random_ctx, nn * sizeof(mp_limb_t), (uint8_t *)r);

      mpn_set_base256(rp, nn, r, nn * sizeof(mp_limb_t));

      mpn_copyi(tp, rp, nn);

      /* invert r */

    }

  while (!mpn_sec_invert (ri, tp, np, nn, 2 * nn * GMP_NUMB_BITS, scratch));

  mpn_sec_powm (c, rp, nn, ep, ebn, np, nn, scratch);

  /* normally mn == nn, but m can be smaller in some cases */

  mpn_sec_mul (tp, c, nn, m, mn, scratch);

  mpn_sec_div_r (tp, nn + mn, np, nn, scratch);

  mpn_copyi(c, tp, nn);

  TMP_GMP_FREE (r);

  TMP_GMP_FREE (rp);

  TMP_GMP_FREE (tp);

}

/* m = c ri mod n */

static void

rsa_sec_unblind (const struct rsa_public_key *pub,

                 mp_limb_t *x, mp_limb_t *ri, const mp_limb_t *c)

{

  const mp_limb_t *np = mpz_limbs_read (pub->n);

  mp_size_t nn = mpz_size (pub->n);

  size_t itch;

  size_t i2;

  mp_limb_t *scratch;

  TMP_GMP_DECL(tp, mp_limb_t);

  itch = mpn_sec_mul_itch(nn, nn);

  i2 = mpn_sec_div_r_itch(nn + nn, nn);

  itch = MAX(itch, i2);

  TMP_GMP_ALLOC (tp, nn + nn + itch);

  scratch = tp + nn + nn;

  mpn_sec_mul (tp, c, nn, ri, nn, scratch);

  mpn_sec_div_r (tp, nn + nn, np, nn, scratch);

  mpn_copyi(x, tp, nn);

  TMP_GMP_FREE (tp);

}

static int

sec_equal(const mp_limb_t *a, const mp_limb_t *b, size_t limbs)

{

  volatile mp_limb_t z = 0;

  for (size_t i = 0; i < limbs; i++)

    {

      z |= (a[i] ^ b[i]);

    }

  /* FIXME: Might compile to a branch instruction on some platforms. */

  return z == 0;

}

static int

rsa_sec_check_root(const struct rsa_public_key *pub,

                   const mp_limb_t *x, const mp_limb_t *m)

{

  mp_size_t nn = mpz_size (pub->n);

  mp_size_t ebn = mpz_sizeinbase (pub->e, 2);

  const mp_limb_t *np = mpz_limbs_read (pub->n);

  const mp_limb_t *ep = mpz_limbs_read (pub->e);

  int ret;

  mp_size_t itch;

  mp_limb_t *scratch;

  TMP_GMP_DECL(tp, mp_limb_t);

  itch = mpn_sec_powm_itch (nn, ebn, nn);

  TMP_GMP_ALLOC (tp, nn + itch);

  scratch = tp + nn;

  mpn_sec_powm(tp, x, nn, ep, ebn, np, nn, scratch);

  ret = sec_equal(tp, m, nn);

  TMP_GMP_FREE (tp);

  return ret;

}

static void

cnd_mpn_zero (int cnd, volatile mp_ptr rp, mp_size_t n)

{

  volatile mp_limb_t c;

  volatile mp_limb_t mask = (mp_limb_t) cnd - 1;

  while (--n >= 0)

    {

      c = rp[n];

      c &= mask;

      rp[n] = c;

    }

}

/* Checks for any errors done in the RSA computation. That avoids

 * attacks which rely on faults on hardware, or even software MPI

 * implementation.

 * This version is side-channel silent even in case of error,

 * the destination buffer is always overwritten */

int

_rsa_sec_compute_root_tr(const struct rsa_public_key *pub,

			 const struct rsa_private_key *key,

			 void *random_ctx, nettle_random_func *random,

			 mp_limb_t *x, const mp_limb_t *m, size_t mn)

{

  TMP_GMP_DECL (c, mp_limb_t);

  TMP_GMP_DECL (ri, mp_limb_t);

  TMP_GMP_DECL (scratch, mp_limb_t);

  size_t key_limb_size;

  int ret;

  key_limb_size = NETTLE_OCTET_SIZE_TO_LIMB_SIZE(key->size);

  /* mpz_powm_sec handles only odd moduli. If p, q or n is even, the

     key is invalid and rejected by rsa_private_key_prepare. However,

     some applications, notably gnutls, don't use this function, and

     we don't want an invalid key to lead to a crash down inside

     mpz_powm_sec. So do an additional check here. */

  if (mpz_even_p (pub->n) || mpz_even_p (key->p) || mpz_even_p (key->q))

    {

      mpn_zero(x, key_limb_size);

      return 0;

    }

  assert(mpz_size(pub->n) == key_limb_size);

  assert(mn <= key_limb_size);

  TMP_GMP_ALLOC (c, key_limb_size);

  TMP_GMP_ALLOC (ri, key_limb_size);

  TMP_GMP_ALLOC (scratch, _rsa_sec_compute_root_itch(key));

  rsa_sec_blind (pub, random_ctx, random, x, ri, m, mn);

  _rsa_sec_compute_root(key, c, x, scratch);

  ret = rsa_sec_check_root(pub, c, x);

  rsa_sec_unblind(pub, x, ri, c);

  cnd_mpn_zero(1 - ret, x, key_limb_size);

  TMP_GMP_FREE (scratch);

  TMP_GMP_FREE (ri);

  TMP_GMP_FREE (c);

  return ret;

}

/* Checks for any errors done in the RSA computation. That avoids

 * attacks which rely on faults on hardware, or even software MPI

 * implementation.

 * This version is maintained for API compatibility reasons. It

 * is not completely side-channel silent. There are conditionals

 * in buffer copying both in case of success or error.

 */

int

rsa_compute_root_tr(const struct rsa_public_key *pub,

		    const struct rsa_private_key *key,

		    void *random_ctx, nettle_random_func *random,

		    mpz_t x, const mpz_t m)

{

  TMP_GMP_DECL (l, mp_limb_t);

  int res;

  mp_size_t l_size = NETTLE_OCTET_SIZE_TO_LIMB_SIZE(key->size);

  TMP_GMP_ALLOC (l, l_size);

  res = _rsa_sec_compute_root_tr (pub, key, random_ctx, random, l,

				  mpz_limbs_read(m), mpz_size(m));

  if (res) {

    mp_limb_t *xp = mpz_limbs_write (x, l_size);

    mpn_copyi (xp, l, l_size);

    mpz_limbs_finish (x, l_size);

  }

  TMP_GMP_FREE (l);

  return res;

}

#endif

#include "testutils.h"

#include "knuth-lfib.h"

#include "memops.h"

#if HAVE_VALGRIND_MEMCHECK_H

# include <valgrind/memcheck.h>

static void

cnd_memcpy_for_test(int cnd, void *dst, const void *src, size_t n)

{

  /* Makes valgrind trigger on any branches depending on the input

     data. */

  VALGRIND_MAKE_MEM_UNDEFINED (dst, n);

  VALGRIND_MAKE_MEM_UNDEFINED (src, n);

  VALGRIND_MAKE_MEM_UNDEFINED (&cnd, sizeof(cnd));

  cnd_memcpy (cnd, dst, src, n);

  VALGRIND_MAKE_MEM_DEFINED (src, n);

  VALGRIND_MAKE_MEM_DEFINED (dst, n);

}

#else

#define cnd_memcpy_for_test cnd_memcpy

#endif

#define MAX_SIZE 50

void

test_main(void)

{

  uint8_t src[MAX_SIZE];

  uint8_t dst[MAX_SIZE];

  uint8_t res[MAX_SIZE];

  struct knuth_lfib_ctx random_ctx;

  knuth_lfib_init (&random_ctx, 11);

  size_t size;

  for (size = 1; size < 50; size++)

    {

      knuth_lfib_random (&random_ctx, size, src);

      knuth_lfib_random (&random_ctx, size, dst);

      memcpy (res, dst, size);

      cnd_memcpy_for_test (0, res, src, size);

      ASSERT (memcmp (res, dst, size) == 0);

      cnd_memcpy_for_test (1, res, src, size);

      ASSERT (memcmp (res, src, size) == 0);

    }

}

		    cnd-memcpy-test.c \

		     rsa-sec-decrypt-test.c \

		     rsa-compute-root-test.c \

#include "testutils.h"

#include "rsa.h"

#include "rsa-internal.h"

#if HAVE_VALGRIND_MEMCHECK_H

# include <valgrind/memcheck.h>

static int

pkcs1_decrypt_for_test(size_t msg_len, uint8_t *msg,

                       size_t pad_len, uint8_t *pad)

{

  int ret;

  VALGRIND_MAKE_MEM_UNDEFINED (msg, msg_len);

  VALGRIND_MAKE_MEM_UNDEFINED (pad, pad_len);

  ret = _pkcs1_sec_decrypt (msg_len, msg, pad_len, pad);

  VALGRIND_MAKE_MEM_DEFINED (msg, msg_len);

  VALGRIND_MAKE_MEM_DEFINED (pad, pad_len);

  VALGRIND_MAKE_MEM_DEFINED (&ret, sizeof (ret));

  return ret;

}

#else

#define pkcs1_decrypt_for_test _pkcs1_sec_decrypt

#endif

void

test_main(void)

{

  uint8_t pad[128];

  uint8_t buffer[] =

    "\x00\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10"

    "\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x20"

    "\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2a\x2b\x2c\x2d\x2e\x2f\x30"

    "\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3a\x3b\x3c\x3d\x3e\x3f\x40"

    "\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4a\x4b\x4c\x4d\x4e\x4f\x50"

    "\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x5b\x5c\x5d\x5e\x5f\x60"

    "\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c\x6d\x6e\x6f\x70"

    "\x00\x53\x49\x47\x4e\x45\x44\x20\x4d\x45\x53\x53\x41\x47\x45\x2e";

  uint8_t message[15];

  memcpy(pad, buffer, 128);

  memset (message, 'A', 15);

  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 1);

  ASSERT (memcmp (message, "SIGNED MESSAGE.", 15) == 0);

  /* break format byte 1 */

  memcpy(pad, buffer, 128);

  pad[0] = 1;

  memset (message, 'B', 15);

  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 0);

  ASSERT (memcmp (message, "BBBBBBBBBBBBBBB", 15) == 0);

  /* break format byte 2 */

  memcpy(pad, buffer, 128);

  pad[1] = 1;

  memset (message, 'C', 15);

  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 0);

  ASSERT (memcmp (message, "CCCCCCCCCCCCCCC", 15) == 0);

  /* break padding */

  memcpy(pad, buffer, 128);

  pad[24] = 0;

  memset (message, 'D', 15);

  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 0);

  ASSERT (memcmp (message, "DDDDDDDDDDDDDDD", 15) == 0);

  /* break terminator */

  memcpy(pad, buffer, 128);

  pad[112] = 1;

  memset (message, 'E', 15);

  ASSERT (pkcs1_decrypt_for_test(15, message, 128, pad) == 0);

  ASSERT (memcmp (message, "EEEEEEEEEEEEEEE", 15) == 0);

}

#include "testutils.h"

#include <assert.h>

#include <errno.h>

#include <limits.h>

#include <sys/time.h>

#include "rsa.h"

#define KEY_COUNT 20

#define COUNT 100

static void

random_fn (void *ctx, size_t n, uint8_t *dst)

{

  gmp_randstate_t *rands = (gmp_randstate_t *)ctx;

  mpz_t r;

  mpz_init (r);

  mpz_urandomb (r, *rands, n*8);

  nettle_mpz_get_str_256 (n, dst, r);

  mpz_clear (r);

}

static void

test_one (gmp_randstate_t *rands, struct rsa_public_key *pub,

          struct rsa_private_key *key, mpz_t plaintext)

{

  mpz_t ciphertext;

  mpz_t decrypted;

  mpz_init (ciphertext);

  mpz_init (decrypted);

  mpz_powm (ciphertext, plaintext, pub->e, pub->n);

  rsa_compute_root_tr (pub, key, rands, random_fn, decrypted, ciphertext);

  if (mpz_cmp (plaintext, decrypted)) {

    fprintf (stderr, "rsa_compute_root_tr failed\n");

    fprintf(stderr, "Public key: size=%lu\n n:", pub->size);

    mpz_out_str (stderr, 10, pub->n);

    fprintf(stderr, "\n e:");

    mpz_out_str (stderr, 10, pub->e);

    fprintf(stderr, "\nPrivate key: size=%lu\n p:", key->size);

    mpz_out_str (stderr, 10, key->p);

    fprintf(stderr, "\n q:");

    mpz_out_str (stderr, 10, key->q);

    fprintf(stderr, "\n a:");

    mpz_out_str (stderr, 10, key->a);

    fprintf(stderr, "\n b:");

    mpz_out_str (stderr, 10, key->b);

    fprintf(stderr, "\n c:");

    mpz_out_str (stderr, 10, key->c);

    fprintf(stderr, "\n d:");

    mpz_out_str (stderr, 10, key->d);

    fprintf(stderr, "\n");

    fprintf (stderr, "plaintext(%lu) = ", mpz_sizeinbase (plaintext, 2));

    mpz_out_str (stderr, 10, plaintext);

    fprintf (stderr, "\n");

    fprintf (stderr, "ciphertext(%lu) = ", mpz_sizeinbase (ciphertext, 2));

    mpz_out_str (stderr, 10, ciphertext);

    fprintf (stderr, "\n");

    fprintf (stderr, "decrypted(%lu) = ", mpz_sizeinbase (decrypted, 2));

    mpz_out_str (stderr, 10, decrypted);

    fprintf (stderr, "\n");

    abort();

  }

  mpz_clear (ciphertext);

  mpz_clear (decrypted);

}

#if !NETTLE_USE_MINI_GMP

/* We want to generate keypairs that are not "standard" but have more size

 * variance between q and p.

 * Function is otherwise the same as standard rsa_generate_keypair()

 */

static void

generate_keypair (gmp_randstate_t rands,

                  struct rsa_public_key *pub, struct rsa_private_key *key)

{

  unsigned long int psize;

  unsigned long int qsize;

  mpz_t p1;

  mpz_t q1;

  mpz_t phi;

  mpz_t tmp;

  mpz_init (p1);

  mpz_init (q1);

  mpz_init (phi);

  mpz_init (tmp);

  psize = 100 + gmp_urandomm_ui (rands, 400);

  qsize = 100 + gmp_urandomm_ui (rands, 400);

  mpz_set_ui (pub->e, 65537);

  for (;;)

    {

      for (;;)

        {

          mpz_rrandomb (key->p, rands, psize);

          mpz_nextprime (key->p, key->p);

          mpz_sub_ui (p1, key->p, 1);

          mpz_gcd (tmp, pub->e, p1);

          if (mpz_cmp_ui (tmp, 1) == 0)

            break;

        }

      for (;;)

        {

          mpz_rrandomb (key->q, rands, qsize);

          mpz_nextprime (key->q, key->q);

          mpz_sub_ui (q1, key->q, 1);

          mpz_gcd (tmp, pub->e, q1);

          if (mpz_cmp_ui (tmp, 1) == 0)

            break;

        }

      if (mpz_invert (key->c, key->q, key->p))

        break;

    }

  mpz_mul(phi, p1, q1);

  assert (mpz_invert(key->d, pub->e, phi));

  mpz_fdiv_r (key->a, key->d, p1);

  mpz_fdiv_r (key->b, key->d, q1);

  mpz_mul (pub->n, key->p, key->q);

  pub->size = key->size = mpz_size(pub->n) * sizeof(mp_limb_t);

  mpz_clear (tmp);

  mpz_clear (phi);

  mpz_clear (q1);

  mpz_clear (p1);

}

#endif

#if !NETTLE_USE_MINI_GMP

static void

get_random_seed(mpz_t seed)

{

  struct timeval tv;

  FILE *f;

  f = fopen ("/dev/urandom", "rb");

  if (f)

    {

      uint8_t buf[8];

      size_t res;

      setbuf (f, NULL);

      res = fread (&buf, sizeof(buf), 1, f);

      fclose(f);

      if (res == 1)

	{

	  nettle_mpz_set_str_256_u (seed, sizeof(buf), buf);

	  return;

	}

      fprintf (stderr, "Read of /dev/urandom failed: %s\n",

	       strerror (errno));

    }

  gettimeofday(&tv, NULL);

  mpz_set_ui (seed, tv.tv_sec);

  mpz_mul_ui (seed, seed, 1000000UL);

  mpz_add_ui (seed, seed, tv.tv_usec);

}

#endif /* !NETTLE_USE_MINI_GMP */

void

test_main (void)

{

  const char *nettle_test_seed;

  gmp_randstate_t rands;

  struct rsa_public_key pub;

  struct rsa_private_key key;

  mpz_t plaintext;

  unsigned i, j;

  rsa_private_key_init(&key);

  rsa_public_key_init(&pub);

  mpz_init (plaintext);

  gmp_randinit_default (rands);

#if !NETTLE_USE_MINI_GMP

  nettle_test_seed = getenv ("NETTLE_TEST_SEED");

  if (nettle_test_seed && *nettle_test_seed)

    {

      mpz_t seed;

      mpz_init (seed);

      if (mpz_set_str (seed, nettle_test_seed, 0) < 0

	  || mpz_sgn (seed) < 0)

	die ("Invalid NETTLE_TEST_SEED: %s\n",

	     nettle_test_seed);

      if (mpz_sgn (seed) == 0)

	get_random_seed (seed);

      fprintf (stderr, "Using NETTLE_TEST_SEED=");

      mpz_out_str (stderr, 10, seed);

      fprintf (stderr, "\n");

      gmp_randseed (rands, seed);

      mpz_clear (seed);

    }

#endif

  for (j = 0; j < KEY_COUNT; j++)

    {

#if !NETTLE_USE_MINI_GMP

      generate_keypair(rands, &pub, &key);

#else

      rsa_generate_keypair(&pub, &key, &rands, random_fn, NULL, NULL, 512, 16);

#endif /* !NETTLE_USE_MINI_GMP */

      for (i = 0; i < COUNT; i++)

	{

	  mpz_urandomb(plaintext, rands, mpz_sizeinbase(pub.n, 2) - 1);

	  test_one(&rands, &pub, &key, plaintext);

	}

      for (i = 0; i < COUNT; i++)

	{

	  mpz_rrandomb(plaintext, rands, mpz_sizeinbase(pub.n, 2) - 1);

	  test_one(&rands, &pub, &key, plaintext);

	}

    }

  mpz_clear (plaintext);

  rsa_public_key_clear (&pub);

  rsa_private_key_clear (&key);

  gmp_randclear (rands);

}

  ASSERT(msg_length <= key.size);

  /* test side channel resistant variant */

  knuth_lfib_random (&lfib, msg_length + 1, decrypted);

  after = decrypted[msg_length];

  decrypted_length = msg_length;

  ASSERT(rsa_sec_decrypt(&pub, &key,

                         &lfib, (nettle_random_func *) knuth_lfib_random,

                         decrypted_length, decrypted, gibberish));

  ASSERT(MEMEQ(msg_length, msg, decrypted));

  ASSERT(decrypted[msg_length] == after);

  /* test invalid length to rsa_sec_decrypt */

  knuth_lfib_random (&lfib, msg_length + 1, decrypted);

  decrypted_length = msg_length - 1;

  after = decrypted[decrypted_length] = 'X';

  decrypted[0] = 'A';

  ASSERT(!rsa_sec_decrypt(&pub, &key,

                          &lfib, (nettle_random_func *) knuth_lfib_random,

                          decrypted_length, decrypted, gibberish));

  ASSERT(decrypted[decrypted_length] == after);

  ASSERT(decrypted[0] == 'A');

#include "testutils.h"

#include "rsa.h"

#include "knuth-lfib.h"

#if HAVE_VALGRIND_MEMCHECK_H

# include <valgrind/memcheck.h>

#define MARK_MPZ_LIMBS_UNDEFINED(parm) \

  VALGRIND_MAKE_MEM_UNDEFINED (mpz_limbs_read (parm), \

                               mpz_size (parm) * sizeof (mp_limb_t))

#define MARK_MPZ_LIMBS_DEFINED(parm) \

  VALGRIND_MAKE_MEM_DEFINED (mpz_limbs_read (parm), \

                               mpz_size (parm) * sizeof (mp_limb_t))

static int

rsa_decrypt_for_test(const struct rsa_public_key *pub,

                     const struct rsa_private_key *key,

                     void *random_ctx, nettle_random_func *random,

                     size_t length, uint8_t *message,

                     const mpz_t gibberish)

{

  int ret;

  /* Makes valgrind trigger on any branches depending on the input

     data. Except that (i) we have to allow rsa_sec_compute_root_tr to

     check that p and q are odd, (ii) mpn_sec_div_r may leak

     information about the most significant bits of p and q, due to

     normalization check and table lookup in invert_limb, and (iii)

     mpn_sec_powm may leak information about the least significant

     bits of p and q, due to table lookup in binvert_limb. */

  VALGRIND_MAKE_MEM_UNDEFINED (message, length);

  MARK_MPZ_LIMBS_UNDEFINED(gibberish);

  MARK_MPZ_LIMBS_UNDEFINED(key->a);

  MARK_MPZ_LIMBS_UNDEFINED(key->b);

  MARK_MPZ_LIMBS_UNDEFINED(key->c);

  VALGRIND_MAKE_MEM_UNDEFINED(mpz_limbs_read (key->p) + 1,

			      (mpz_size (key->p) - 3) * sizeof(mp_limb_t));

  VALGRIND_MAKE_MEM_UNDEFINED(mpz_limbs_read (key->q) + 1,

			      (mpz_size (key->q) - 3) * sizeof(mp_limb_t));

  ret = rsa_sec_decrypt (pub, key, random_ctx, random, length, message, gibberish);

  VALGRIND_MAKE_MEM_DEFINED (message, length);

  VALGRIND_MAKE_MEM_DEFINED (&ret, sizeof(ret));

  MARK_MPZ_LIMBS_DEFINED(gibberish);

  MARK_MPZ_LIMBS_DEFINED(key->a);

  MARK_MPZ_LIMBS_DEFINED(key->b);

  MARK_MPZ_LIMBS_DEFINED(key->c);

  MARK_MPZ_LIMBS_DEFINED(key->p);

  MARK_MPZ_LIMBS_DEFINED(key->q);

  return ret;

}

#else

#define rsa_decrypt_for_test rsa_sec_decrypt

#endif

#define PAYLOAD_SIZE 50

void

test_main(void)

{