ecc-ecdsa-sign.c

   1 /* ecc-ecdsa-sign.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 <assert.h>
  30 #include <stdlib.h>
  31
  32 #include "ecdsa.h"
  33 #include "ecc-internal.h"
  34
  35 /* Low-level ECDSA signing */
  36
  37 mp_size_t
  38 ecc_ecdsa_sign_itch (const struct ecc_curve *ecc)
  39 {
  40   /* Needs 3*ecc->size + scratch for ecc_mul_g. */
  41   return ECC_ECDSA_SIGN_ITCH (ecc->size);
  42 }
  43
  44 /* NOTE: Caller should check if r or s is zero. */
  45 void
  46 ecc_ecdsa_sign (const struct ecc_curve *ecc,
  47                 const mp_limb_t *zp,
  48                 /* Random nonce, must be invertible mod ecc group
  49                    order. */
  50                 const mp_limb_t *kp,
  51                 unsigned length, const uint8_t *digest,
  52                 mp_limb_t *rp, mp_limb_t *sp,
  53                 mp_limb_t *scratch)
  54 {
  55   mp_limb_t cy;
  56 #define P           scratch
  57 #define kinv        scratch                /* Needs 5*ecc->size for computation */
  58 #define hp          (scratch  + ecc->size) /* NOTE: ecc->size + 1 limbs! */
  59 #define tp          (scratch + 2*ecc->size)
  60   /* Procedure, according to RFC 6090, "KT-I". q denotes the group
  61      order.
  62
  63      1. k <-- uniformly random, 0 < k < q
  64
  65      2. R <-- (r_x, r_y) = k g
  66
  67      3. s1 <-- r_x mod q
  68
  69      4. s2 <-- (h + z*s1)/k mod q.
  70   */
  71
  72   ecc_mul_g (ecc, P, kp, P + 3*ecc->size);
  73   /* x coordinate only */
  74   ecc_j_to_a (ecc, 3, rp, P, P + 3*ecc->size);
  75
  76   /* We need to reduce x coordinate mod ecc->q. It should already
  77      be < 2*ecc->q, so one subtraction should suffice. */
  78   cy = mpn_sub_n (scratch, rp, ecc->q, ecc->size);
  79   cnd_copy (cy == 0, rp, scratch, ecc->size);
  80
  81   /* Invert k, uses 5 * ecc->size including scratch */
  82   mpn_copyi (hp, kp, ecc->size);
  83   ecc_modq_inv (ecc, kinv, hp, tp);
  84
  85   /* Process hash digest */
  86   ecc_hash (ecc, hp, length, digest);
  87
  88   ecc_modq_mul (ecc, tp, zp, rp);
  89   ecc_modq_add (ecc, hp, hp, tp);
  90   ecc_modq_mul (ecc, tp, hp, kinv);
  91
  92   mpn_copyi (sp, tp, ecc->size);
  93 #undef P
  94 #undef hp
  95 #undef kinv
  96 #undef tp
  97 }