math_group.c

   1 /* borrowed from isakmpd-20030718 (-; */
   2
   3 /*      $OpenBSD: math_group.c,v 1.18 2003/06/03 14:28:16 ho Exp $      */
   4 /*      $EOM: math_group.c,v 1.25 2000/04/07 19:53:26 niklas Exp $      */
   5
   6 /*
   7  * Copyright (c) 1998 Niels Provos.  All rights reserved.
   8  * Copyright (c) 1999, 2000 Niklas Hallqvist.  All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 /*
  32  * This code was written under funding by Ericsson Radio Systems.
  33  */
  34
  35 #include <assert.h>
  36 #include <sys/param.h>
  37 #include <stdlib.h>
  38 #include <string.h>
  39
  40 #include <gcrypt.h>
  41
  42 #include "math_group.h"
  43
  44 /* We do not want to export these definitions.  */
  45 int modp_getlen (struct group *);
  46 void modp_getraw (struct group *, gcry_mpi_t, unsigned char *);
  47 int modp_setraw (struct group *, gcry_mpi_t, unsigned char *, int);
  48 int modp_setrandom (struct group *, gcry_mpi_t);
  49 int modp_operation (struct group *, gcry_mpi_t, gcry_mpi_t, gcry_mpi_t);
  50
  51 struct modp_group {
  52   gcry_mpi_t gen;                       /* Generator */
  53   gcry_mpi_t p;                         /* Prime */
  54   gcry_mpi_t a, b, c, d;
  55 };
  56
  57 /*
  58  * This module provides access to the operations on the specified group
  59  * and is absolutly free of any cryptographic devices. This is math :-).
  60  */
  61
  62 /* Describe preconfigured MODP groups */
  63
  64 /*
  65  * The Generalized Number Field Sieve has an asymptotic running time
  66  * of: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))), where q is the
  67  * group order, e.g. q = 2**768.
  68  */
  69
  70 struct modp_dscr oakley_modp[] =
  71 {
  72   { OAKLEY_GRP_1, 72,   /* This group is insecure, only sufficient for DES */
  73     "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  74     "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  75     "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  76     "E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF",
  77     "2"
  78   },
  79   { OAKLEY_GRP_2, 82,   /* This group is a bit better */
  80     "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  81     "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  82     "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  83     "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
  84     "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
  85     "FFFFFFFFFFFFFFFF",
  86     "2"
  87   },
  88   { OAKLEY_GRP_5, 102,  /* This group is yet a bit better, but non-standard */
  89     "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  90     "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  91     "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  92     "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
  93     "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
  94     "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
  95     "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
  96     "670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF",
  97     "2"
  98   },
  99 };
 100
 101
 102 /* XXX I want to get rid of the casting here.  */
 103 struct group groups[] = {
 104   {
 105     MODP, OAKLEY_GRP_1, 0, &oakley_modp[0], 0, 0, 0, 0, 0,
 106     (int (*) (struct group *))modp_getlen,
 107     (void (*) (struct group *, void *, unsigned char *))modp_getraw,
 108     (int (*) (struct group *, void *, unsigned char *, int))modp_setraw,
 109     (int (*) (struct group *, void *))modp_setrandom,
 110     (int (*) (struct group *, void *, void *, void *))modp_operation
 111   },
 112   {
 113     MODP, OAKLEY_GRP_2, 0, &oakley_modp[1], 0, 0, 0, 0, 0,
 114     (int (*) (struct group *))modp_getlen,
 115     (void (*) (struct group *, void *, unsigned char *))modp_getraw,
 116     (int (*) (struct group *, void *, unsigned char *, int))modp_setraw,
 117     (int (*) (struct group *, void *))modp_setrandom,
 118     (int (*) (struct group *, void *, void *, void *))modp_operation
 119   },
 120   {
 121     MODP, OAKLEY_GRP_5, 0, &oakley_modp[2], 0, 0, 0, 0, 0,
 122     (int (*) (struct group *))modp_getlen,
 123     (void (*) (struct group *, void *, unsigned char *))modp_getraw,
 124     (int (*) (struct group *, void *, unsigned char *, int))modp_setraw,
 125     (int (*) (struct group *, void *))modp_setrandom,
 126     (int (*) (struct group *, void *, void *, void *))modp_operation
 127   },
 128 };
 129
 130 /*
 131  * Initialize the group structure for later use,
 132  * this is done by converting the values given in the describtion
 133  * and converting them to their native representation.
 134  */
 135 void
 136 group_init (void)
 137 {
 138   int i;
 139
 140   for (i = sizeof (groups) / sizeof (groups[0]) - 1; i >= 0; i--) {
 141     assert(groups[i].type == MODP);
 142     modp_init (&groups[i]); /* Initialize an over GF(p) */
 143   }
 144 }
 145
 146 struct group *
 147 group_get (int id)
 148 {
 149   struct group *new, *clone;
 150
 151   assert(id >= 1);
 152   assert(id <= (int)(sizeof (groups) / sizeof (groups[0])));
 153
 154   clone = &groups[id - 1];
 155
 156   new = malloc (sizeof *new);
 157   assert(new);
 158
 159   assert(clone->type == MODP);
 160   new = modp_clone (new, clone);
 161   return new;
 162 }
 163
 164 void
 165 group_free (struct group *grp)
 166 {
 167   assert (grp->type == MODP);
 168   modp_free (grp);
 169   free (grp);
 170 }
 171
 172 struct group *
 173 modp_clone (struct group *new, struct group *clone)
 174 {
 175   struct modp_group *new_grp, *clone_grp = clone->group;
 176
 177   new_grp = malloc (sizeof *new_grp);
 178   assert (new_grp);
 179
 180   memcpy (new, clone, sizeof (struct group));
 181
 182   new->group = new_grp;
 183   new_grp->p = gcry_mpi_copy (clone_grp->p);
 184   new_grp->gen = gcry_mpi_copy (clone_grp->gen);
 185
 186   new_grp->a = gcry_mpi_new (clone->bits);
 187   new_grp->b = gcry_mpi_new (clone->bits);
 188   new_grp->c = gcry_mpi_new (clone->bits);
 189
 190   new->gen = new_grp->gen;
 191   new->a = new_grp->a;
 192   new->b = new_grp->b;
 193   new->c = new_grp->c;
 194
 195   return new;
 196 }
 197
 198 void
 199 modp_free (struct group *old)
 200 {
 201   struct modp_group *grp = old->group;
 202
 203   gcry_mpi_release (grp->p);
 204   gcry_mpi_release (grp->gen);
 205   gcry_mpi_release (grp->a);
 206   gcry_mpi_release (grp->b);
 207   gcry_mpi_release (grp->c);
 208
 209   free (grp);
 210 }
 211
 212 void
 213 modp_init (struct group *group)
 214 {
 215   struct modp_dscr *dscr = (struct modp_dscr *)group->group;
 216   struct modp_group *grp;
 217
 218   grp = malloc (sizeof *grp);
 219   assert(grp);
 220
 221   group->bits = dscr->bits;
 222
 223   gcry_mpi_scan(&grp->p, GCRYMPI_FMT_HEX, dscr->prime, 0, NULL);
 224   gcry_mpi_scan(&grp->gen, GCRYMPI_FMT_HEX, dscr->gen, 0, NULL);
 225
 226   grp->a = gcry_mpi_new (group->bits);
 227   grp->b = gcry_mpi_new (group->bits);
 228   grp->c = gcry_mpi_new (group->bits);
 229
 230   group->gen = grp->gen;
 231   group->a = grp->a;
 232   group->b = grp->b;
 233   group->c = grp->c;
 234
 235   group->group = grp;
 236 }
 237
 238 int
 239 modp_getlen (struct group *group)
 240 {
 241   struct modp_group *grp = (struct modp_group *)group->group;
 242
 243   return (gcry_mpi_get_nbits (grp->p) + 7) / 8;
 244 }
 245
 246 void
 247 modp_getraw (struct group *grp, gcry_mpi_t v, unsigned char *d)
 248 {
 249   size_t l, l2;
 250   unsigned char *tmp;
 251   int ret;
 252
 253   l = grp->getlen (grp);
 254   ret = gcry_mpi_aprint(GCRYMPI_FMT_STD, &tmp, &l2, v);
 255   memcpy(d, tmp + (l2-l), l);
 256 #if 0
 257   {
 258           char *p;
 259           gcry_mpi_aprint(GCRYMPI_FMT_HEX, (void **)&p, NULL, v);
 260           printf("export %d - %d(%d):\n%s\n", l, l2, ret, p);
 261   }
 262 #endif
 263 }
 264
 265 int
 266 modp_setraw (struct group *grp, gcry_mpi_t d, unsigned char *s, int l)
 267 {
 268   int i;
 269
 270   grp = 0; /* unused */
 271
 272   gcry_mpi_set_ui(d, 0);
 273   for (i = 0; i < l; i++)
 274     {
 275       gcry_mpi_mul_2exp (d, d, 8);
 276       gcry_mpi_add_ui (d, d, s[i]);
 277     }
 278 #if 0
 279   {
 280           char *p;
 281           gcry_mpi_aprint(GCRYMPI_FMT_HEX, (void **)&p, NULL, d);
 282           printf("import %d:\n%s\n", l, p);
 283   }
 284 #endif
 285   return 0;
 286 }
 287
 288 int
 289 modp_setrandom (struct group *grp, gcry_mpi_t d)
 290 {
 291   int i, l = grp->getlen (grp);
 292   u_int32_t tmp = 0;
 293
 294   gcry_mpi_set_ui (d, 0);
 295
 296   for (i = 0; i < l; i++)
 297     {
 298       if (i % 4)
 299         gcry_randomize((unsigned char *)&tmp, sizeof(tmp), GCRY_WEAK_RANDOM);
 300
 301       gcry_mpi_mul_2exp (d, d, 8);
 302       gcry_mpi_add_ui (d, d, tmp & 0xFF);
 303       tmp >>= 8;
 304     }
 305   return 0;
 306 }
 307
 308 int
 309 modp_operation (struct group *group, gcry_mpi_t d, gcry_mpi_t a, gcry_mpi_t e)
 310 {
 311   struct modp_group *grp = (struct modp_group *)group->group;
 312
 313   gcry_mpi_powm(d, a, e, grp->p);
 314   return 0;
 315 }
 316