src/curves.c

   1 /*
   2  * netsniff-ng - the packet sniffing beast
   3  * By Daniel Borkmann <daniel@netsniff-ng.org>
   4  * Copyright 2011 Daniel Borkmann <dborkma@tik.ee.ethz.ch>,
   5  * Swiss federal institute of technology (ETH Zurich)
   6  * Subject to the GPL.
   7  */
   8
   9 /*
  10  *  seccure  -  Copyright 2009 B. Poettering
  11  *
  12  *  This program is free software; you can redistribute it and/or
  13  *  modify it under the terms of the GNU General Public License as
  14  *  published by the Free Software Foundation; either version 2 of the
  15  *  License, or (at your option) any later version.
  16  *
  17  *  This program is distributed in the hope that it will be useful,
  18  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  *  General Public License for more details.
  21  *
  22  *  You should have received a copy of the GNU General Public License
  23  *  along with this program; if not, write to the Free Software
  24  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  25  *  02111-1307 USA
  26  */
  27
  28 /*
  29  *   SECCURE Elliptic Curve Crypto Utility for Reliable Encryption
  30  *
  31  *              http://point-at-infinity.org/seccure/
  32  *
  33  *
  34  * seccure implements a selection of asymmetric algorithms based on
  35  * elliptic curve cryptography (ECC). See the manpage or the project's
  36  * homepage for further details.
  37  *
  38  * This code links against the GNU gcrypt library "libgcrypt" (which
  39  * is part of the GnuPG project). Use the included Makefile to build
  40  * the binary.
  41  *
  42  * Report bugs to: seccure AT point-at-infinity.org
  43  *
  44  */
  45
  46 #include <gcrypt.h>
  47 #include <assert.h>
  48 #include <stdio.h>
  49 #include <stdlib.h>
  50
  51 #include "curves.h"
  52 #include "ecc.h"
  53 #include "serialize.h"
  54
  55 #define CURVE_NUM  8
  56
  57 struct curve {
  58         const char *name, *a, *b, *m, *base_x, *base_y, *order;
  59         int cofactor;
  60         int pk_len_compact;
  61 };
  62
  63 static const struct curve curves[CURVE_NUM] = {
  64         {"secp112r1",
  65          "db7c2abf62e35e668076bead2088",
  66          "659ef8ba043916eede8911702b22",
  67          "db7c2abf62e35e668076bead208b",
  68          "09487239995a5ee76b55f9c2f098",
  69          "a89ce5af8724c0a23e0e0ff77500",
  70          "db7c2abf62e35e7628dfac6561c5",
  71          1, 18},
  72
  73         {"secp128r1",
  74          "fffffffdfffffffffffffffffffffffc",
  75          "e87579c11079f43dd824993c2cee5ed3",
  76          "fffffffdffffffffffffffffffffffff",
  77          "161ff7528b899b2d0c28607ca52c5b86",
  78          "cf5ac8395bafeb13c02da292dded7a83",
  79          "fffffffe0000000075a30d1b9038a115",
  80          1, 20},
  81
  82         {"secp160r1",
  83          "ffffffffffffffffffffffffffffffff7ffffffc",
  84          "1c97befc54bd7a8b65acf89f81d4d4adc565fa45",
  85          "ffffffffffffffffffffffffffffffff7fffffff",
  86          "4a96b5688ef573284664698968c38bb913cbfc82",
  87          "23a628553168947d59dcc912042351377ac5fb32",
  88          "0100000000000000000001f4c8f927aed3ca752257",
  89          1, 25},
  90
  91         {"secp192r1/nistp192",
  92          "fffffffffffffffffffffffffffffffefffffffffffffffc",
  93          "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
  94          "fffffffffffffffffffffffffffffffeffffffffffffffff",
  95          "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012",
  96          "07192b95ffc8da78631011ed6b24cdd573f977a11e794811",
  97          "ffffffffffffffffffffffff99def836146bc9b1b4d22831",
  98          1, 30},
  99
 100         {"secp224r1/nistp224",
 101          "fffffffffffffffffffffffffffffffefffffffffffffffffffffffe",
 102          "b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
 103          "ffffffffffffffffffffffffffffffff000000000000000000000001",
 104          "b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21",
 105          "bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34",
 106          "ffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d",
 107          1, 35},
 108
 109         {"secp256r1/nistp256",
 110          "ffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
 111          "5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
 112          "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
 113          "6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
 114          "4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5",
 115          "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
 116          1, 40},
 117
 118         {"secp384r1/nistp384",
 119          "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffc",
 120          "b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef",
 121          "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff",
 122          "aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7",
 123          "3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f",
 124          "ffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973",
 125          1, 60},
 126
 127         {"secp521r1/nistp521",
 128          "1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc",
 129          "051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00",
 130          "1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
 131          "0c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66",
 132          "11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650",
 133          "1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409",
 134          1, 81},
 135 };
 136
 137 #define SCAN(x, s) do {                                               \
 138         assert(! gcry_mpi_scan(x, GCRYMPI_FMT_HEX, s, 0, NULL));      \
 139         gcry_mpi_set_flag(*x, GCRYMPI_FLAG_SECURE);                   \
 140  } while(0)
 141
 142 static struct curve_params *load_curve(const struct curve *c)
 143 {
 144         gcry_mpi_t h;
 145         struct curve_params *cp;
 146         struct domain_params *dp;
 147
 148         if (!(cp = malloc(sizeof(struct curve_params))))
 149                 return NULL;
 150
 151         cp->name = c->name;
 152
 153         dp = &cp->dp;
 154         SCAN(&dp->a, c->a);
 155         SCAN(&dp->b, c->b);
 156         SCAN(&dp->m, c->m);
 157         SCAN(&dp->order, c->order);
 158         SCAN(&dp->base.x, c->base_x);
 159         SCAN(&dp->base.y, c->base_y);
 160         dp->cofactor = c->cofactor;
 161
 162         h = gcry_mpi_new(0);
 163
 164         gcry_mpi_add(h, dp->m, dp->m);
 165         gcry_mpi_sub_ui(h, h, 1);
 166         cp->pk_len_bin = get_serialization_len(h, DF_BIN);
 167         cp->pk_len_compact = get_serialization_len(h, DF_COMPACT);
 168
 169         gcry_mpi_mul(h, dp->order, dp->order);
 170         gcry_mpi_sub_ui(h, h, 1);
 171         cp->sig_len_bin = get_serialization_len(h, DF_BIN);
 172         cp->sig_len_compact = get_serialization_len(h, DF_COMPACT);
 173
 174         cp->dh_len_bin = (gcry_mpi_get_nbits(dp->order) / 2 + 7) / 8;
 175         if (cp->dh_len_bin > 32)
 176                 cp->dh_len_bin = 32;
 177
 178         gcry_mpi_set_ui(h, 0);
 179         gcry_mpi_set_bit(h, 8 * cp->dh_len_bin);
 180         gcry_mpi_sub_ui(h, h, 1);
 181         cp->dh_len_compact = get_serialization_len(h, DF_COMPACT);
 182
 183         cp->elem_len_bin = get_serialization_len(dp->m, DF_BIN);
 184         cp->order_len_bin = get_serialization_len(dp->order, DF_BIN);
 185
 186 #if 0   /* enable this when adding a new curve to do some sanity checks */
 187         if (!gcry_mpi_cmp_ui(dp->b, 0)) {
 188                 fprintf(stderr, "FATAL: b == 0\n");
 189                 exit(1);
 190         }
 191         if (cp->pk_len_compact != c->pk_len_compact) {
 192                 fprintf(stderr, "FATAL: c->pk_len_compact != %d\n",
 193                         cp->pk_len_compact);
 194                 exit(1);
 195         }
 196         if (!point_on_curve(&dp->base, dp)) {
 197                 fprintf(stderr, "FATAL: base point not on curve!\n");
 198                 exit(1);
 199         }
 200         struct affine_point p = pointmul(&dp->base, dp->order, dp);
 201         if (!point_is_zero(&p)) {
 202                 fprintf(stderr, "FATAL: wrong point order!\n");
 203                 exit(1);
 204         }
 205         point_release(&p);
 206
 207         gcry_mpi_mul_ui(h, dp->order, dp->cofactor);
 208         gcry_mpi_sub(h, h, dp->m);
 209         gcry_mpi_sub_ui(h, h, 1);
 210         gcry_mpi_mul(h, h, h);
 211         gcry_mpi_rshift(h, h, 2);
 212         if (gcry_mpi_cmp(h, dp->m) > 0) {
 213                 fprintf(stderr, "FATAL: invalid cofactor!\n");
 214                 exit(1);
 215         }
 216 #endif
 217
 218         gcry_mpi_release(h);
 219         return cp;
 220 }
 221
 222 struct curve_params *curve_by_name(const char *name)
 223 {
 224         int i;
 225         const struct curve *c = curves;
 226
 227         for (i = 0; i < CURVE_NUM; i++, c++)
 228                 if (strstr(c->name, name))
 229                         return load_curve(c);
 230         return NULL;
 231 }
 232
 233 void curve_list(void)
 234 {
 235         int i;
 236         const struct curve *c = curves;
 237
 238         for (i = 0; i < CURVE_NUM; i++, c++)
 239                 printf("%s\n", c->name);
 240 }
 241
 242 struct curve_params *curve_by_pk_len_compact(int len)
 243 {
 244         int i;
 245         const struct curve *c = curves;
 246
 247         for (i = 0; i < CURVE_NUM; i++, c++)
 248                 if (c->pk_len_compact == len)
 249                         return load_curve(c);
 250         return NULL;
 251 }
 252
 253 void curve_release(struct curve_params *cp)
 254 {
 255         struct domain_params *dp = &cp->dp;
 256
 257         gcry_mpi_release(dp->a);
 258         gcry_mpi_release(dp->b);
 259         gcry_mpi_release(dp->m);
 260         gcry_mpi_release(dp->order);
 261         gcry_mpi_release(dp->base.x);
 262         gcry_mpi_release(dp->base.y);
 263         free(cp);
 264 }