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 #include <netinet/in.h>
  40
  41 #include <gcrypt.h>
  42
  43 #include "math_group.h"
  44
  45 /* We do not want to export these definitions.  */
  46 int modp_getlen(struct group *);
  47 void modp_getraw(struct group *, gcry_mpi_t, unsigned char *);
  48 int modp_setraw(struct group *, gcry_mpi_t, unsigned char *, int);
  49 int modp_setrandom(struct group *, gcry_mpi_t);
  50 int modp_operation(struct group *, gcry_mpi_t, gcry_mpi_t, gcry_mpi_t);
  51
  52 struct modp_group {
  53         gcry_mpi_t gen; /* Generator */
  54         gcry_mpi_t p; /* Prime */
  55         gcry_mpi_t a, b, c, d;
  56 };
  57
  58 /*
  59  * This module provides access to the operations on the specified group
  60  * and is absolutly free of any cryptographic devices. This is math :-).
  61  */
  62
  63 /* Describe preconfigured MODP groups */
  64
  65 /*
  66  * The Generalized Number Field Sieve has an asymptotic running time
  67  * of: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))), where q is the
  68  * group order, e.g. q = 2**768.
  69  */
  70
  71 struct modp_dscr oakley_modp[] = {
  72         {
  73                 OAKLEY_GRP_1, 72, /* This group is insecure, only sufficient for DES */
  74                 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  75                 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  76                 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  77                 "E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF",
  78                 "2"
  79         },
  80         {
  81                 OAKLEY_GRP_2, 82, /* This group is a bit better */
  82                 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  83                 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  84                 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  85                 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
  86                 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
  87                 "FFFFFFFFFFFFFFFF",
  88                 "2"
  89         },
  90         {
  91                 OAKLEY_GRP_5, 102, /* This group is yet a bit better, but non-standard */
  92                 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  93                 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  94                 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  95                 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
  96                 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
  97                 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
  98                 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
  99                 "670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF",
 100                 "2"
 101         },
 102 };
 103
 104 /* XXX I want to get rid of the casting here.  */
 105 struct group groups[] = {
 106         {
 107                 MODP, OAKLEY_GRP_1, 0, &oakley_modp[0], 0, 0, 0, 0, 0,
 108                 (int (*)(struct group *))modp_getlen,
 109                 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
 110                 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
 111                 (int (*)(struct group *, void *))modp_setrandom,
 112                 (int (*)(struct group *, void *, void *, void *))modp_operation
 113         },
 114         {
 115                 MODP, OAKLEY_GRP_2, 0, &oakley_modp[1], 0, 0, 0, 0, 0,
 116                 (int (*)(struct group *))modp_getlen,
 117                 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
 118                 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
 119                 (int (*)(struct group *, void *))modp_setrandom,
 120                 (int (*)(struct group *, void *, void *, void *))modp_operation
 121         },
 122         {
 123                 MODP, OAKLEY_GRP_5, 0, &oakley_modp[2], 0, 0, 0, 0, 0,
 124                 (int (*)(struct group *))modp_getlen,
 125                 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
 126                 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
 127                 (int (*)(struct group *, void *))modp_setrandom,
 128                 (int (*)(struct group *, void *, void *, void *))modp_operation
 129         },
 130 };
 131
 132 /*
 133  * Initialize the group structure for later use,
 134  * this is done by converting the values given in the describtion
 135  * and converting them to their native representation.
 136  */
 137 void group_init(void)
 138 {
 139         int i;
 140
 141         for (i = sizeof(groups) / sizeof(groups[0]) - 1; i >= 0; i--) {
 142                 assert(groups[i].type == MODP);
 143                 modp_init(&groups[i]); /* Initialize an over GF(p) */
 144         }
 145 }
 146
 147 struct group *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 group_free(struct group *grp)
 165 {
 166         assert(grp->type == MODP);
 167         modp_free(grp);
 168         free(grp);
 169 }
 170
 171 struct group *modp_clone(struct group *new, struct group *clone)
 172 {
 173         struct modp_group *new_grp, *clone_grp = clone->group;
 174
 175         new_grp = malloc(sizeof *new_grp);
 176         assert(new_grp);
 177
 178         memcpy(new, clone, sizeof(struct group));
 179
 180         new->group = new_grp;
 181         new_grp->p = gcry_mpi_copy(clone_grp->p);
 182         new_grp->gen = gcry_mpi_copy(clone_grp->gen);
 183
 184         new_grp->a = gcry_mpi_new(clone->bits);
 185         new_grp->b = gcry_mpi_new(clone->bits);
 186         new_grp->c = gcry_mpi_new(clone->bits);
 187
 188         new->gen = new_grp->gen;
 189         new->a = new_grp->a;
 190         new->b = new_grp->b;
 191         new->c = new_grp->c;
 192
 193         return new;
 194 }
 195
 196 void modp_free(struct group *old)
 197 {
 198         struct modp_group *grp = old->group;
 199
 200         gcry_mpi_release(grp->p);
 201         gcry_mpi_release(grp->gen);
 202         gcry_mpi_release(grp->a);
 203         gcry_mpi_release(grp->b);
 204         gcry_mpi_release(grp->c);
 205
 206         free(grp);
 207 }
 208
 209 void modp_init(struct group *group)
 210 {
 211         struct modp_dscr *dscr = (struct modp_dscr *)group->group;
 212         struct modp_group *grp;
 213
 214         grp = malloc(sizeof *grp);
 215         assert(grp);
 216
 217         group->bits = dscr->bits;
 218
 219         gcry_mpi_scan(&grp->p, GCRYMPI_FMT_HEX, dscr->prime, 0, NULL);
 220         gcry_mpi_scan(&grp->gen, GCRYMPI_FMT_HEX, dscr->gen, 0, NULL);
 221
 222         grp->a = gcry_mpi_new(group->bits);
 223         grp->b = gcry_mpi_new(group->bits);
 224         grp->c = gcry_mpi_new(group->bits);
 225
 226         group->gen = grp->gen;
 227         group->a = grp->a;
 228         group->b = grp->b;
 229         group->c = grp->c;
 230
 231         group->group = grp;
 232 }
 233
 234 int modp_getlen(struct group *group)
 235 {
 236         struct modp_group *grp = (struct modp_group *)group->group;
 237
 238         return (gcry_mpi_get_nbits(grp->p) + 7) / 8;
 239 }
 240
 241 void modp_getraw(struct group *grp, gcry_mpi_t v, unsigned char *d)
 242 {
 243         size_t l, l2;
 244         unsigned char *tmp;
 245         int ret;
 246
 247         l = grp->getlen(grp);
 248         ret = gcry_mpi_aprint(GCRYMPI_FMT_STD, &tmp, &l2, v);
 249         memcpy(d, tmp + (l2 - l), l);
 250         gcry_free(tmp);
 251 #if 0
 252         {
 253                 char *p;
 254                 gcry_mpi_aprint(GCRYMPI_FMT_HEX, (void **)&p, NULL, v);
 255                 printf("export %d - %d(%d):\n%s\n", l, l2, ret, p);
 256                 gcry_free(p);
 257         }
 258 #endif
 259 }
 260
 261 int modp_setraw(struct group *grp, gcry_mpi_t d, unsigned char *s, int l)
 262 {
 263         int i;
 264
 265         grp = 0; /* unused */
 266
 267         gcry_mpi_set_ui(d, 0);
 268         for (i = 0; i < l; i++) {
 269                 gcry_mpi_mul_2exp(d, d, 8);
 270                 gcry_mpi_add_ui(d, d, s[i]);
 271         }
 272 #if 0
 273         {
 274                 char *p;
 275                 gcry_mpi_aprint(GCRYMPI_FMT_HEX, (void **)&p, NULL, d);
 276                 printf("import %d:\n%s\n", l, p);
 277                 gcry_free(p);
 278         }
 279 #endif
 280         return 0;
 281 }
 282
 283 int modp_setrandom(struct group *grp, gcry_mpi_t d)
 284 {
 285         int i, l = grp->getlen(grp);
 286         uint32_t tmp = 0;
 287
 288         gcry_mpi_set_ui(d, 0);
 289
 290         for (i = 0; i < l; i++) {
 291                 if (i % 4)
 292                         gcry_randomize((unsigned char *)&tmp, sizeof(tmp), GCRY_WEAK_RANDOM);
 293
 294                 gcry_mpi_mul_2exp(d, d, 8);
 295                 gcry_mpi_add_ui(d, d, tmp & 0xFF);
 296                 tmp >>= 8;
 297         }
 298         return 0;
 299 }
 300
 301 int modp_operation(struct group *group, gcry_mpi_t d, gcry_mpi_t a, gcry_mpi_t e)
 302 {
 303         struct modp_group *grp = (struct modp_group *)group->group;
 304
 305         gcry_mpi_powm(d, a, e, grp->p);
 306         return 0;
 307 }