curve25519-mul.c

   1 /* curve25519-mul.c
   2
   3    Copyright (C) 2014 Niels Möller
   4
   5    This file is part of GNU Nettle.
   6
   7    GNU Nettle is free software: you can redistribute it and/or
   8    modify it under the terms of either:
   9
  10      * the GNU Lesser General Public License as published by the Free
  11        Software Foundation; either version 3 of the License, or (at your
  12        option) any later version.
  13
  14    or
  15
  16      * the GNU General Public License as published by the Free
  17        Software Foundation; either version 2 of the License, or (at your
  18        option) any later version.
  19
  20    or both in parallel, as here.
  21
  22    GNU Nettle is distributed in the hope that it will be useful,
  23    but WITHOUT ANY WARRANTY; without even the implied warranty of
  24    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25    General Public License for more details.
  26
  27    You should have received copies of the GNU General Public License and
  28    the GNU Lesser General Public License along with this program.  If
  29    not, see http://www.gnu.org/licenses/.
  30 */
  31
  32 #if HAVE_CONFIG_H
  33 # include "config.h"
  34 #endif
  35
  36 #include <string.h>
  37
  38 #include "curve25519.h"
  39
  40 #include "ecc.h"
  41 #include "ecc-internal.h"
  42
  43 /* Intended to be compatible with NaCl's crypto_scalarmult. */
  44 void
  45 curve25519_mul (uint8_t *q, const uint8_t *n, const uint8_t *p)
  46 {
  47   const struct ecc_curve *ecc = &_nettle_curve25519;
  48   mp_size_t itch;
  49   mp_limb_t *scratch;
  50   int i;
  51   mp_limb_t cy;
  52
  53   /* FIXME: Could save some more scratch space, e.g., by letting BB
  54      overlap C, D, and CB overlap A, D. And possibly reusing some of
  55      x2, z2, x3, z3. */
  56 #define x1 scratch
  57 #define x2 (scratch + ecc->p.size)
  58 #define z2 (scratch + 2*ecc->p.size)
  59 #define x3 (scratch + 3*ecc->p.size)
  60 #define z3 (scratch + 4*ecc->p.size)
  61
  62 #define A  (scratch + 5*ecc->p.size)
  63 #define B  (scratch + 6*ecc->p.size)
  64 #define C  (scratch + 7*ecc->p.size)
  65 #define D  (scratch + 8*ecc->p.size)
  66 #define AA  (scratch + 9*ecc->p.size)
  67 #define BB  (scratch +10*ecc->p.size)
  68 #define E  (scratch + 10*ecc->p.size) /* Overlap BB */
  69 #define DA  (scratch + 9*ecc->p.size) /* Overlap AA */
  70 #define CB  (scratch + 10*ecc->p.size) /* Overlap BB */
  71
  72   itch = ecc->p.size * 12;
  73   scratch = gmp_alloc_limbs (itch);
  74
  75   mpn_set_base256_le (x1, ecc->p.size, p, CURVE25519_SIZE);
  76
  77   /* Initialize, x2 = x1, z2 = 1 */
  78   mpn_copyi (x2, x1, ecc->p.size);
  79   z2[0] = 1;
  80   mpn_zero (z2+1, ecc->p.size - 1);
  81
  82   /* Get x3, z3 from doubling. Since bit 254 is forced to 1. */
  83   ecc_modp_add (ecc, A, x2, z2);
  84   ecc_modp_sub (ecc, B, x2, z2);
  85   ecc_modp_sqr (ecc, AA, A);
  86   ecc_modp_sqr (ecc, BB, B);
  87   ecc_modp_mul (ecc, x3, AA, BB);
  88   ecc_modp_sub (ecc, E, AA, BB);
  89   ecc_modp_addmul_1 (ecc, AA, E, 121665);
  90   ecc_modp_mul (ecc, z3, E, AA);
  91
  92   for (i = 253; i >= 3; i--)
  93     {
  94       int bit = (n[i/8] >> (i & 7)) & 1;
  95
  96       cnd_swap (bit, x2, x3, 2*ecc->p.size);
  97
  98       /* Formulas from draft-turner-thecurve25519function-00-Mont. We
  99          compute new coordinates in memory-address order, since mul
 100          and sqr clobbers higher limbs. */
 101       ecc_modp_add (ecc, A, x2, z2);
 102       ecc_modp_sub (ecc, B, x2, z2);
 103       ecc_modp_sqr (ecc, AA, A);
 104       ecc_modp_sqr (ecc, BB, B);
 105       ecc_modp_mul (ecc, x2, AA, BB); /* Last use of BB */
 106       ecc_modp_sub (ecc, E, AA, BB);
 107       ecc_modp_addmul_1 (ecc, AA, E, 121665);
 108       ecc_modp_add (ecc, C, x3, z3);
 109       ecc_modp_sub (ecc, D, x3, z3);
 110       ecc_modp_mul (ecc, z2, E, AA); /* Last use of E and AA */
 111       ecc_modp_mul (ecc, DA, D, A);  /* Last use of D, A. FIXME: could
 112                                         let CB overlap. */
 113       ecc_modp_mul (ecc, CB, C, B);
 114
 115       ecc_modp_add (ecc, C, DA, CB);
 116       ecc_modp_sqr (ecc, x3, C);
 117       ecc_modp_sub (ecc, C, DA, CB);
 118       ecc_modp_sqr (ecc, DA, C);
 119       ecc_modp_mul (ecc, z3, DA, x1);
 120
 121       cnd_swap (bit, x2, x3, 2*ecc->p.size);
 122     }
 123   /* Do the 3 low zero bits, just duplicating x2 */
 124   for ( ; i >= 0; i--)
 125     {
 126       ecc_modp_add (ecc, A, x2, z2);
 127       ecc_modp_sub (ecc, B, x2, z2);
 128       ecc_modp_sqr (ecc, AA, A);
 129       ecc_modp_sqr (ecc, BB, B);
 130       ecc_modp_mul (ecc, x2, AA, BB);
 131       ecc_modp_sub (ecc, E, AA, BB);
 132       ecc_modp_addmul_1 (ecc, AA, E, 121665);
 133       ecc_modp_mul (ecc, z2, E, AA);
 134     }
 135   ecc->p.invert (&ecc->p, x3, z2, z3 + ecc->p.size);
 136   ecc_modp_mul (ecc, z3, x2, x3);
 137   cy = mpn_sub_n (x2, z3, ecc->p.m, ecc->p.size);
 138   cnd_copy (cy, x2, z3, ecc->p.size);
 139   mpn_get_base256_le (q, CURVE25519_SIZE, x2, ecc->p.size);
 140
 141   gmp_free_limbs (scratch, itch);
 142 }