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 void
  42 ecc_j_to_a (const struct ecc_curve *ecc,
  43             int op,
  44             mp_limb_t *r, const mp_limb_t *p,
  45             mp_limb_t *scratch)
  46 {
  47 #define izp   scratch
  48 #define up   (scratch + 2*ecc->p.size)
  49 #define iz2p (scratch + ecc->p.size)
  50 #define iz3p (scratch + 2*ecc->p.size)
  51 #define izBp (scratch + 3*ecc->p.size)
  52 #define tp    scratch
  53
  54   mp_limb_t cy;
  55
  56   if (ecc->use_redc)
  57     {
  58       /* Set v = (r_z / B^2)^-1,
  59
  60          r_x = p_x v^2 / B^3 =  ((v/B * v)/B * p_x)/B
  61          r_y = p_y v^3 / B^4 = (((v/B * v)/B * v)/B * p_y)/B
  62       */
  63
  64       mpn_copyi (up, p + 2*ecc->p.size, ecc->p.size);
  65       mpn_zero (up + ecc->p.size, ecc->p.size);
  66       ecc->p.reduce (&ecc->p, up);
  67       mpn_zero (up + ecc->p.size, ecc->p.size);
  68       ecc->p.reduce (&ecc->p, up);
  69
  70       ecc->p.invert (&ecc->p, izp, up, up + ecc->p.size);
  71
  72       /* Divide this common factor by B */
  73       mpn_copyi (izBp, izp, ecc->p.size);
  74       mpn_zero (izBp + ecc->p.size, ecc->p.size);
  75       ecc->p.reduce (&ecc->p, izBp);
  76
  77       ecc_modp_mul (ecc, iz2p, izp, izBp);
  78     }
  79   else
  80     {
  81       /* Set s = p_z^{-1}, r_x = p_x s^2, r_y = p_y s^3 */
  82
  83       mpn_copyi (up, p+2*ecc->p.size, ecc->p.size); /* p_z */
  84       ecc->p.invert (&ecc->p, izp, up, up + ecc->p.size);
  85
  86       ecc_modp_sqr (ecc, iz2p, izp);
  87     }
  88
  89   ecc_modp_mul (ecc, iz3p, iz2p, p);
  90   /* ecc_modp (and ecc_modp_mul) may return a value up to 2p - 1, so
  91      do a conditional subtraction. */
  92   cy = mpn_sub_n (r, iz3p, ecc->p.m, ecc->p.size);
  93   cnd_copy (cy, r, iz3p, ecc->p.size);
  94
  95   if (op)
  96     {
  97       /* Skip y coordinate */
  98       if (op > 1)
  99         {
 100           /* Also reduce the x coordinate mod ecc->q. It should
 101              already be < 2*ecc->q, so one subtraction should
 102              suffice. */
 103           cy = mpn_sub_n (scratch, r, ecc->q.m, ecc->p.size);
 104           cnd_copy (cy == 0, r, scratch, ecc->p.size);
 105         }
 106       return;
 107     }
 108   ecc_modp_mul (ecc, iz3p, iz2p, izp);
 109   ecc_modp_mul (ecc, tp, iz3p, p + ecc->p.size);
 110   /* And a similar subtraction. */
 111   cy = mpn_sub_n (r + ecc->p.size, tp, ecc->p.m, ecc->p.size);
 112   cnd_copy (cy, r + ecc->p.size, tp, ecc->p.size);
 113
 114 #undef izp
 115 #undef up
 116 #undef iz2p
 117 #undef iz3p
 118 #undef tp
 119 }