freeswan/pluto/gcryptfix.c

   1 /* Routines to make gcrypt routines feel at home in Pluto.
   2  * Copyright (C) 1999  D. Hugh Redelmeier.
   3  *
   4  * This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License as published by the
   6  * Free Software Foundation; either version 2 of the License, or (at your
   7  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  11  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * for more details.
  13  *
  14  * RCSID $Id: gcryptfix.c,v 1.4 2000/05/20 19:43:55 dhr Exp $
  15  */
  16
  17 #include <stdlib.h>
  18
  19 #include <gmp.h>
  20 #include <freeswan.h>
  21 #include "constants.h"
  22 #include "defs.h"
  23 #include "log.h"
  24 #include "rnd.h"
  25 #include "gcryptfix.h"  /* includes <gmp.h> "defs.h" "rnd.h" */
  26
  27 MPI
  28 mpi_alloc( unsigned nlimbs UNUSED )
  29 {
  30     MPI n = alloc_bytes(sizeof *n, "mpi_alloc");
  31
  32     mpz_init(n);
  33     return n;
  34 }
  35
  36 MPI
  37 mpi_alloc_secure( unsigned nlimbs )
  38 {
  39     return mpi_alloc(nlimbs);
  40 }
  41
  42 MPI
  43 mpi_alloc_set_ui( unsigned long u)
  44 {
  45     MPI n = alloc_bytes(sizeof *n, "mpi_copy");
  46
  47     mpz_init_set_ui(n, u);
  48     return n;
  49 }
  50
  51 MPI
  52 mpi_copy( MPI a )
  53 {
  54     MPI n = alloc_bytes(sizeof *n, "mpi_copy");
  55
  56     mpz_init_set(n, a);
  57     return n;
  58 }
  59
  60 void
  61 mpi_free( MPI a )
  62 {
  63     mpz_clear(a);
  64     pfree(a);
  65 }
  66
  67 int
  68 mpi_divisible_ui(MPI dividend, ulong divisor )
  69 {
  70     ulong rem;
  71     mpz_t remtoo;
  72
  73     mpz_init(remtoo);
  74     rem = mpz_mod_ui(remtoo, dividend, divisor);
  75     mpz_clear(remtoo);
  76     return rem == 0;
  77 }
  78
  79 unsigned
  80 mpi_trailing_zeros( MPI a )
  81 {
  82     return mpz_scan1(a, 0);
  83 }
  84
  85 unsigned
  86 mpi_get_nbits( MPI a )
  87 {
  88     return mpz_sizeinbase(a, 2);
  89 }
  90
  91 int
  92 mpi_test_bit( MPI a, unsigned n )
  93 {
  94     /* inspired by gmp/mpz/clrbit.c */
  95     mp_size_t li = n / mp_bits_per_limb;
  96
  97     if (li >= a->_mp_size)
  98         return 0;
  99     return (a->_mp_d[li] & ((mp_limb_t) 1 << (n % mp_bits_per_limb))) != 0;
 100 }
 101
 102 void
 103 mpi_set_bit( MPI a, unsigned n )
 104 {
 105     mpz_setbit(a, n);
 106 }
 107
 108 void
 109 mpi_clear_bit( MPI a, unsigned n )
 110 {
 111     mpz_clrbit(a, n);
 112 }
 113
 114 void
 115 mpi_clear_highbit( MPI a, unsigned n )
 116 {
 117     /* This seems whacky, but what do I know. */
 118     mpz_fdiv_r_2exp(a, a, n);
 119 }
 120
 121 void
 122 mpi_set_highbit( MPI a, unsigned n )
 123 {
 124     /* This seems whacky, but what do I know. */
 125     mpz_fdiv_r_2exp(a, a, n+1);
 126     mpz_setbit(a, n);
 127 }
 128
 129 void
 130 mpi_set_buffer( MPI a, const u_char *buffer, unsigned nbytes, int sign )
 131 {
 132     /* this is a lot like n_to_mpz */
 133     size_t i;
 134
 135     passert(sign == 0); /* we won't hit any negative numbers */
 136     mpz_init_set_ui(a, 0);
 137
 138     for (i = 0; i != nbytes; i++)
 139     {
 140         mpz_mul_ui(a, a, 1 << BITS_PER_BYTE);
 141         mpz_add_ui(a, a, buffer[i]);
 142     }
 143 }
 144
 145 u_char *
 146 get_random_bits(size_t nbits, int level UNUSED, int secure UNUSED)
 147 {
 148     size_t nbytes = (nbits+7)/8;
 149     u_char *b = alloc_bytes(nbytes, "random bytes");
 150
 151     get_rnd_bytes(b, nbytes);
 152     return b;
 153 }
 154 /**************** from gnupg-1.0.0/mpi/mpi-mpow.c
 155  * RES = (BASE[0] ^ EXP[0]) *  (BASE[1] ^ EXP[1]) * ... * mod M
 156  */
 157 #define barrett_mulm( w, u, v, m, y, k, r1, r2 ) mpi_mulm( (w), (u), (v), (m) )
 158
 159 static int
 160 build_index( MPI *exparray, int k, int i, int t )
 161 {
 162     int j, bitno;
 163     int index = 0;
 164
 165     bitno = t-i;
 166     for(j=k-1; j >= 0; j-- ) {
 167         index <<= 1;
 168         if( mpi_test_bit( exparray[j], bitno ) )
 169             index |= 1;
 170     }
 171     /*log_debug("t=%d i=%d index=%d\n", t, i, index );*/
 172     return index;
 173 }
 174
 175 void
 176 mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m)
 177 {
 178     int k;      /* number of elements */
 179     int t;      /* bit size of largest exponent */
 180     int i, j, idx;
 181     MPI *G;     /* table with precomputed values of size 2^k */
 182     MPI tmp;
 183   #ifdef USE_BARRETT
 184     MPI barrett_y, barrett_r1, barrett_r2;
 185     int barrett_k;
 186   #endif
 187
 188     for(k=0; basearray[k]; k++ )
 189         ;
 190     passert(k);
 191     for(t=0, i=0; (tmp=exparray[i]); i++ ) {
 192         /*log_mpidump("exp: ", tmp );*/
 193         j = mpi_get_nbits(tmp);
 194         if( j > t )
 195             t = j;
 196     }
 197     /*log_mpidump("mod: ", m );*/
 198     passert(i==k);
 199     passert(t);
 200     passert( k < 10 );
 201
 202 #ifdef PLUTO
 203     m_alloc_ptrs_clear(G, 1<<k);
 204 #else
 205     G = m_alloc_clear( (1<<k) * sizeof *G );
 206 #endif
 207
 208   #ifdef USE_BARRETT
 209     barrett_y = init_barrett( m, &barrett_k, &barrett_r1, &barrett_r2 );
 210   #endif
 211     /* and calculate */
 212     tmp =  mpi_alloc( mpi_get_nlimbs(m)+1 );
 213     mpi_set_ui( res, 1 );
 214     for(i = 1; i <= t; i++ ) {
 215         barrett_mulm(tmp, res, res, m, barrett_y, barrett_k,
 216                                        barrett_r1, barrett_r2 );
 217         idx = build_index( exparray, k, i, t );
 218         passert( idx >= 0 && idx < (1<<k) );
 219         if( !G[idx] ) {
 220             if( !idx )
 221                  G[0] = mpi_alloc_set_ui( 1 );
 222             else {
 223                 for(j=0; j < k; j++ ) {
 224                     if( (idx & (1<<j) ) ) {
 225                         if( !G[idx] )
 226                             G[idx] = mpi_copy( basearray[j] );
 227                         else
 228                             barrett_mulm( G[idx], G[idx], basearray[j],
 229                                                m, barrett_y, barrett_k, barrett_r1, barrett_r2  );
 230                     }
 231                 }
 232                 if( !G[idx] )
 233                     G[idx] = mpi_alloc(0);
 234             }
 235         }
 236         barrett_mulm(res, tmp, G[idx], m, barrett_y, barrett_k, barrett_r1, barrett_r2  );
 237     }
 238
 239     /* cleanup */
 240     mpi_free(tmp);
 241   #ifdef USE_BARRETT
 242     mpi_free(barrett_y);
 243     mpi_free(barrett_r1);
 244     mpi_free(barrett_r2);
 245   #endif
 246     for(i=0; i < (1<<k); i++ )
 247         mpi_free(G[i]);
 248     m_free(G);
 249 }
 250
 251 void
 252 log_mpidump( const char *text UNUSED, MPI a )
 253 {
 254     /* Print number in hex -- helpful to see if they match bytes.
 255      * Humans are not going to do arithmetic with the large numbers!
 256      * Much code adapted from mpz_to_n.
 257      */
 258     u_char buf[8048];   /* this ought to be big enough */
 259     size_t len = (mpz_sizeinbase(a, 16) + 1) / 2;   /* bytes */
 260     MP_INT temp1, temp2;
 261     int i;
 262
 263     passert(len <= sizeof(buf));
 264
 265     mpz_init(&temp1);
 266     mpz_init(&temp2);
 267
 268     mpz_set(&temp1, a);
 269
 270     for (i = len-1; i >= 0; i--)
 271     {
 272         buf[i] = mpz_mdivmod_ui(&temp2, NULL, &temp1, 1 << BITS_PER_BYTE);
 273         mpz_set(&temp1, &temp2);
 274     }
 275
 276     passert(mpz_sgn(&temp1) == 0);      /* we must have done all the bits */
 277     mpz_clear(&temp1);
 278     mpz_clear(&temp2);
 279
 280 #ifdef DEBUG
 281     DBG_dump(text, buf, len);
 282 #endif /* DEBUG */
 283 }