ecc-point.c

   1 /* ecc-point.c
   2
   3    Copyright (C) 2013, 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 /* 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_point_init (struct ecc_point *p, const struct ecc_curve *ecc)
  43 {
  44   p->ecc = ecc;
  45   p->p = gmp_alloc_limbs (2*ecc->p.size);
  46 }
  47
  48 void
  49 ecc_point_clear (struct ecc_point *p)
  50 {
  51   gmp_free_limbs (p->p, 2*p->ecc->p.size);
  52 }
  53
  54 int
  55 ecc_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y)
  56 {
  57   mp_size_t size;
  58   mpz_t lhs, rhs;
  59   mpz_t t;
  60   int res;
  61
  62   size = p->ecc->p.size;
  63
  64   if (mpz_sgn (x) < 0 || mpz_limbs_cmp (x, p->ecc->p.m, size) >= 0
  65       || mpz_sgn (y) < 0 || mpz_limbs_cmp (y, p->ecc->p.m, size) >= 0)
  66     return 0;
  67
  68   mpz_init (lhs);
  69   mpz_init (rhs);
  70
  71   mpz_mul (lhs, y, y);
  72
  73   if (p->ecc->p.bit_size == 255)
  74     {
  75       /* ed25519 special case. FIXME: Do in some cleaner way? */
  76       mpz_t x2;
  77       mpz_init (x2);
  78       mpz_mul (x2, x, x);
  79       mpz_mul (rhs, x2, lhs);
  80       /* Check that -x^2 + y^2 = 1 - (121665/121666) x^2 y^2
  81          or 121666 (1 + x^2 - y^2) = 121665 x^2 y^2 */
  82       mpz_sub (lhs, x2, lhs);
  83       mpz_add_ui (lhs, lhs, 1);
  84       mpz_mul_ui (lhs, lhs, 121666);
  85       mpz_mul_ui (rhs, rhs, 121665);
  86       mpz_clear (x2);
  87     }
  88   else if (p->ecc->p.bit_size == 448)
  89     {
  90       /* curve448 special case. FIXME: Do in some cleaner way? */
  91       mpz_t x2, d;
  92       mpz_init (x2);
  93       mpz_init_set_ui (d, 39081);
  94       mpz_mul (x2, x, x); /* x^2 */
  95       mpz_mul (d, d, x2); /* 39081 x^2 */
  96       mpz_set_ui (rhs, 1);
  97       mpz_submul (rhs, d, lhs); /* 1 - 39081 x^2 y^2 */
  98       /* Check that x^2 + y^2 = 1 - 39081 x^2 y^2 */
  99       mpz_add (lhs, x2, lhs);   /* x^2 + y^2 */
 100       mpz_clear (d);
 101       mpz_clear (x2);
 102     }
 103   else
 104     {
 105       /* Check that y^2 = x^3 - 3*x + b (mod p) */
 106       mpz_mul (rhs, x, x);
 107       mpz_sub_ui (rhs, rhs, 3);
 108       mpz_mul (rhs, rhs, x);
 109       mpz_add (rhs, rhs, mpz_roinit_n (t, p->ecc->b, size));
 110     }
 111
 112   res = mpz_congruent_p (lhs, rhs, mpz_roinit_n (t, p->ecc->p.m, size));
 113
 114   mpz_clear (lhs);
 115   mpz_clear (rhs);
 116
 117   if (!res)
 118     return 0;
 119
 120   mpz_limbs_copy (p->p, x, size);
 121   mpz_limbs_copy (p->p + size, y, size);
 122
 123   return 1;
 124 }
 125
 126 void
 127 ecc_point_get (const struct ecc_point *p, mpz_t x, mpz_t y)
 128 {
 129   mp_size_t size = p->ecc->p.size;
 130   if (x)
 131     mpz_set_n (x, p->p, size);
 132   if (y)
 133     mpz_set_n (y, p->p + size, size);
 134 }