git.samba.org - gd/nettle/blob - ecc-j-to-a.c

   1 /* ecc-j-to-a.c
   2
   3    Copyright (C) 2013 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 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  33
  34 #if HAVE_CONFIG_H
  35 # include "config.h"
  36 #endif
  37
  38 #include "ecc.h"
  39 #include "ecc-internal.h"
  40
  41 mp_size_t
  42 ecc_j_to_a_itch (const struct ecc_curve *ecc)
  43 {
  44   /* Needs 2*ecc->size + scratch for ecc_modq_inv */
  45   return ECC_J_TO_A_ITCH (ecc->size);
  46 }
  47
  48 void
  49 ecc_j_to_a (const struct ecc_curve *ecc,
  50             int flags,
  51             mp_limb_t *r, const mp_limb_t *p,
  52             mp_limb_t *scratch)
  53 {
  54 #define izp   scratch
  55 #define up   (scratch + ecc->size)
  56 #define iz2p (scratch + ecc->size)
  57 #define iz3p (scratch + 2*ecc->size)
  58 #define izBp (scratch + 3*ecc->size)
  59 #define tp    scratch
  60
  61   mp_limb_t cy;
  62
  63   if (ecc->use_redc)
  64     {
  65       /* Set v = (r_z / B^2)^-1,
  66
  67          r_x = p_x v^2 / B^3 =  ((v/B * v)/B * p_x)/B
  68          r_y = p_y v^3 / B^4 = (((v/B * v)/B * v)/B * p_x)/B
  69
  70          Skip the first redc, if we want to stay in Montgomery
  71          representation.
  72       */
  73
  74       mpn_copyi (up, p + 2*ecc->size, ecc->size);
  75       mpn_zero (up + ecc->size, ecc->size);
  76       ecc->redc (ecc, up);
  77       mpn_zero (up + ecc->size, ecc->size);
  78       ecc->redc (ecc, up);
  79
  80       ecc_modp_inv (ecc, izp, up, up + ecc->size);
  81
  82       if (flags & 1)
  83         {
  84           /* Divide this common factor by B */
  85           mpn_copyi (izBp, izp, ecc->size);
  86           mpn_zero (izBp + ecc->size, ecc->size);
  87           ecc->redc (ecc, izBp);
  88
  89           ecc_modp_mul (ecc, iz2p, izp, izBp);
  90         }
  91       else
  92         ecc_modp_sqr (ecc, iz2p, izp);
  93     }
  94   else
  95     {
  96       /* Set s = p_z^{-1}, r_x = p_x s^2, r_y = p_y s^3 */
  97
  98       mpn_copyi (up, p+2*ecc->size, ecc->size); /* p_z */
  99       ecc_modp_inv (ecc, izp, up, up + ecc->size);
 100
 101       ecc_modp_sqr (ecc, iz2p, izp);
 102     }
 103
 104   ecc_modp_mul (ecc, iz3p, iz2p, p);
 105   /* ecc_modp (and ecc_modp_mul) may return a value up to 2p - 1, so
 106      do a conditional subtraction. */
 107   cy = mpn_sub_n (r, iz3p, ecc->p, ecc->size);
 108   cnd_copy (cy, r, iz3p, ecc->size);
 109
 110   if (flags & 2)
 111     /* Skip y coordinate */
 112     return;
 113
 114   ecc_modp_mul (ecc, iz3p, iz2p, izp);
 115   ecc_modp_mul (ecc, tp, iz3p, p + ecc->size);
 116   /* And a similar subtraction. */
 117   cy = mpn_sub_n (r + ecc->size, tp, ecc->p, ecc->size);
 118   cnd_copy (cy, r + ecc->size, tp, ecc->size);
 119
 120 #undef izp
 121 #undef up
 122 #undef iz2p
 123 #undef iz3p
 124 #undef tp
 125 }