ecc-j-to-a.c

   1 /* ecc-j-to-a.c */
   2
   3 /* nettle, low-level cryptographics library
   4  *
   5  * Copyright (C) 2013 Niels Möller
   6  *
   7  * The nettle library is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU Lesser General Public License as published by
   9  * the Free Software Foundation; either version 2.1 of the License, or (at your
  10  * option) any later version.
  11  *
  12  * The nettle library is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15  * License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public License
  18  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  20  * MA 02111-1301, USA.
  21  */
  22
  23 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  24
  25 #if HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 #include "ecc.h"
  30 #include "ecc-internal.h"
  31
  32 mp_size_t
  33 ecc_j_to_a_itch (const struct ecc_curve *ecc)
  34 {
  35   /* Needs 2*ecc->size + scratch for ecc_modq_inv */
  36   return ECC_J_TO_A_ITCH (ecc->size);
  37 }
  38
  39 void
  40 ecc_j_to_a (const struct ecc_curve *ecc,
  41             int flags,
  42             mp_limb_t *r, const mp_limb_t *p,
  43             mp_limb_t *scratch)
  44 {
  45 #define izp   scratch
  46 #define up   (scratch + ecc->size)
  47 #define iz2p (scratch + ecc->size)
  48 #define iz3p (scratch + 2*ecc->size)
  49 #define izBp (scratch + 3*ecc->size)
  50 #define tp    scratch
  51
  52   mp_limb_t cy;
  53
  54   if (ecc->use_redc)
  55     {
  56       /* Set v = (r_z / B^2)^-1,
  57
  58          r_x = p_x v^2 / B^3 =  ((v/B * v)/B * p_x)/B
  59          r_y = p_y v^3 / B^4 = (((v/B * v)/B * v)/B * p_x)/B
  60
  61          Skip the first redc, if we want to stay in Montgomery
  62          representation.
  63       */
  64
  65       mpn_copyi (up, p + 2*ecc->size, ecc->size);
  66       mpn_zero (up + ecc->size, ecc->size);
  67       ecc->redc (ecc, up);
  68       mpn_zero (up + ecc->size, ecc->size);
  69       ecc->redc (ecc, up);
  70
  71       ecc_modp_inv (ecc, izp, up, up + ecc->size);
  72
  73       if (flags & 1)
  74         {
  75           /* Divide this common factor by B */
  76           mpn_copyi (izBp, izp, ecc->size);
  77           mpn_zero (izBp + ecc->size, ecc->size);
  78           ecc->redc (ecc, izBp);
  79
  80           ecc_modp_mul (ecc, iz2p, izp, izBp);
  81         }
  82       else
  83         ecc_modp_sqr (ecc, iz2p, izp);
  84     }
  85   else
  86     {
  87       /* Set s = p_z^{-1}, r_x = p_x s^2, r_y = p_y s^3 */
  88
  89       mpn_copyi (up, p+2*ecc->size, ecc->size); /* p_z */
  90       ecc_modp_inv (ecc, izp, up, up + ecc->size);
  91
  92       ecc_modp_sqr (ecc, iz2p, izp);
  93     }
  94
  95   ecc_modp_mul (ecc, iz3p, iz2p, p);
  96   /* ecc_modp (and ecc_modp_mul) may return a value up to 2p - 1, so
  97      do a conditional subtraction. */
  98   cy = mpn_sub_n (r, iz3p, ecc->p, ecc->size);
  99   cnd_copy (cy, r, iz3p, ecc->size);
 100
 101   if (flags & 2)
 102     /* Skip y coordinate */
 103     return;
 104
 105   ecc_modp_mul (ecc, iz3p, iz2p, izp);
 106   ecc_modp_mul (ecc, tp, iz3p, p + ecc->size);
 107   /* And a similar subtraction. */
 108   cy = mpn_sub_n (r + ecc->size, tp, ecc->p, ecc->size);
 109   cnd_copy (cy, r + ecc->size, tp, ecc->size);
 110
 111 #undef izp
 112 #undef up
 113 #undef iz2p
 114 #undef iz3p
 115 #undef tp
 116 }