Coverage Report

Created: 2024-11-21 07:03

/src/libgcrypt/cipher/elgamal.c
Line
Count
Source (jump to first uncovered line)
1
/* Elgamal.c  -  Elgamal Public Key encryption
2
 * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3
 *               2008  Free Software Foundation, Inc.
4
 * Copyright (C) 2013 g10 Code GmbH
5
 *
6
 * This file is part of Libgcrypt.
7
 *
8
 * Libgcrypt is free software; you can redistribute it and/or modify
9
 * it under the terms of the GNU Lesser General Public License as
10
 * published by the Free Software Foundation; either version 2.1 of
11
 * the License, or (at your option) any later version.
12
 *
13
 * Libgcrypt is distributed in the hope that it will be useful,
14
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
 * GNU Lesser General Public License for more details.
17
 *
18
 * You should have received a copy of the GNU Lesser General Public
19
 * License along with this program; if not, see <http://www.gnu.org/licenses/>.
20
 *
21
 * For a description of the algorithm, see:
22
 *   Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
23
 *   ISBN 0-471-11709-9. Pages 476 ff.
24
 */
25
26
#include <config.h>
27
#include <stdio.h>
28
#include <stdlib.h>
29
#include <string.h>
30
#include "g10lib.h"
31
#include "mpi.h"
32
#include "cipher.h"
33
#include "pubkey-internal.h"
34
#include "const-time.h"
35
36
37
/* Blinding is used to mitigate side-channel attacks.  You may undef
38
   this to speed up the operation in case the system is secured
39
   against physical and network mounted side-channel attacks.  */
40
#define USE_BLINDING 1
41
42
43
typedef struct
44
{
45
  gcry_mpi_t p;     /* prime */
46
  gcry_mpi_t g;     /* group generator */
47
  gcry_mpi_t y;     /* g^x mod p */
48
} ELG_public_key;
49
50
51
typedef struct
52
{
53
  gcry_mpi_t p;     /* prime */
54
  gcry_mpi_t g;     /* group generator */
55
  gcry_mpi_t y;     /* g^x mod p */
56
  gcry_mpi_t x;     /* secret exponent */
57
} ELG_secret_key;
58
59
60
static const char *elg_names[] =
61
  {
62
    "elg",
63
    "openpgp-elg",
64
    "openpgp-elg-sig",
65
    NULL,
66
  };
67
68
69
static int test_keys (ELG_secret_key *sk, unsigned int nbits, int nodie);
70
static gcry_mpi_t gen_k (gcry_mpi_t p);
71
static gcry_err_code_t generate (ELG_secret_key *sk, unsigned nbits,
72
                                 gcry_mpi_t **factors);
73
static int  check_secret_key (ELG_secret_key *sk);
74
static void do_encrypt (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
75
                        ELG_public_key *pkey);
76
static void decrypt (gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b,
77
                     ELG_secret_key *skey);
78
static void sign (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
79
                  ELG_secret_key *skey);
80
static int  verify (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
81
                    ELG_public_key *pkey);
82
static unsigned int elg_get_nbits (gcry_sexp_t parms);
83
84
85
static void (*progress_cb) (void *, const char *, int, int, int);
86
static void *progress_cb_data;
87
88
void
89
_gcry_register_pk_elg_progress (void (*cb) (void *, const char *,
90
                                            int, int, int),
91
        void *cb_data)
92
0
{
93
0
  progress_cb = cb;
94
0
  progress_cb_data = cb_data;
95
0
}
96
97
98
static void
99
progress (int c)
100
0
{
101
0
  if (progress_cb)
102
0
    progress_cb (progress_cb_data, "pk_elg", c, 0, 0);
103
0
}
104
105
106
/****************
107
 * Michael Wiener's table on subgroup sizes to match field sizes.
108
 * (floating around somewhere, probably based on the paper from
109
 * Eurocrypt 96, page 332)
110
 */
111
static unsigned int
112
wiener_map( unsigned int n )
113
0
{
114
0
  static struct { unsigned int p_n, q_n; } t[] =
115
0
    { /*   p    q  attack cost */
116
0
      {  512, 119 },  /* 9 x 10^17 */
117
0
      {  768, 145 },  /* 6 x 10^21 */
118
0
      { 1024, 165 },  /* 7 x 10^24 */
119
0
      { 1280, 183 },  /* 3 x 10^27 */
120
0
      { 1536, 198 },  /* 7 x 10^29 */
121
0
      { 1792, 212 },  /* 9 x 10^31 */
122
0
      { 2048, 225 },  /* 8 x 10^33 */
123
0
      { 2304, 237 },  /* 5 x 10^35 */
124
0
      { 2560, 249 },  /* 3 x 10^37 */
125
0
      { 2816, 259 },  /* 1 x 10^39 */
126
0
      { 3072, 269 },  /* 3 x 10^40 */
127
0
      { 3328, 279 },  /* 8 x 10^41 */
128
0
      { 3584, 288 },  /* 2 x 10^43 */
129
0
      { 3840, 296 },  /* 4 x 10^44 */
130
0
      { 4096, 305 },  /* 7 x 10^45 */
131
0
      { 4352, 313 },  /* 1 x 10^47 */
132
0
      { 4608, 320 },  /* 2 x 10^48 */
133
0
      { 4864, 328 },  /* 2 x 10^49 */
134
0
      { 5120, 335 },  /* 3 x 10^50 */
135
0
      { 0, 0 }
136
0
    };
137
0
  int i;
138
139
0
  for(i=0; t[i].p_n; i++ )
140
0
    {
141
0
      if( n <= t[i].p_n )
142
0
        return t[i].q_n;
143
0
    }
144
  /* Not in table - use an arbitrary high number. */
145
0
  return  n / 8 + 200;
146
0
}
147
148
static int
149
test_keys ( ELG_secret_key *sk, unsigned int nbits, int nodie )
150
0
{
151
0
  ELG_public_key pk;
152
0
  gcry_mpi_t test   = mpi_new ( 0 );
153
0
  gcry_mpi_t out1_a = mpi_new ( nbits );
154
0
  gcry_mpi_t out1_b = mpi_new ( nbits );
155
0
  gcry_mpi_t out2   = mpi_new ( nbits );
156
0
  int failed = 0;
157
158
0
  pk.p = sk->p;
159
0
  pk.g = sk->g;
160
0
  pk.y = sk->y;
161
162
0
  _gcry_mpi_randomize ( test, nbits, GCRY_WEAK_RANDOM );
163
164
0
  do_encrypt ( out1_a, out1_b, test, &pk );
165
0
  decrypt ( out2, out1_a, out1_b, sk );
166
0
  if ( mpi_cmp( test, out2 ) )
167
0
    failed |= 1;
168
169
0
  sign ( out1_a, out1_b, test, sk );
170
0
  if ( !verify( out1_a, out1_b, test, &pk ) )
171
0
    failed |= 2;
172
173
0
  _gcry_mpi_release ( test );
174
0
  _gcry_mpi_release ( out1_a );
175
0
  _gcry_mpi_release ( out1_b );
176
0
  _gcry_mpi_release ( out2 );
177
178
0
  if (failed && !nodie)
179
0
    log_fatal ("Elgamal test key for %s %s failed\n",
180
0
               (failed & 1)? "encrypt+decrypt":"",
181
0
               (failed & 2)? "sign+verify":"");
182
0
  if (failed && DBG_CIPHER)
183
0
    log_debug ("Elgamal test key for %s %s failed\n",
184
0
               (failed & 1)? "encrypt+decrypt":"",
185
0
               (failed & 2)? "sign+verify":"");
186
187
0
  return failed;
188
0
}
189
190
191
/****************
192
 * Generate a random secret exponent k from prime p, so that k is
193
 * relatively prime to p-1.
194
 */
195
static gcry_mpi_t
196
gen_k( gcry_mpi_t p )
197
0
{
198
0
  gcry_mpi_t k = mpi_alloc_secure( 0 );
199
0
  gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(p) );
200
0
  gcry_mpi_t p_1 = mpi_copy(p);
201
0
  unsigned int orig_nbits = mpi_get_nbits(p);
202
0
  unsigned int nbits, nbytes;
203
0
  char *rndbuf = NULL;
204
205
0
  nbits = orig_nbits;
206
207
0
  nbytes = (nbits+7)/8;
208
0
  if( DBG_CIPHER )
209
0
    log_debug("choosing a random k\n");
210
0
  mpi_sub_ui( p_1, p, 1);
211
0
  for(;;)
212
0
    {
213
0
      if( !rndbuf || nbits < 32 )
214
0
        {
215
0
          xfree(rndbuf);
216
0
          rndbuf = _gcry_random_bytes_secure( nbytes, GCRY_STRONG_RANDOM );
217
0
        }
218
0
      else
219
0
        {
220
          /* Change only some of the higher bits.  We could improve
221
             this by directly requesting more memory at the first call
222
             to get_random_bytes() and use this the here maybe it is
223
             easier to do this directly in random.c Anyway, it is
224
             highly inlikely that we will ever reach this code. */
225
0
          char *pp = _gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
226
0
          memcpy( rndbuf, pp, 4 );
227
0
          xfree(pp);
228
0
  }
229
0
      _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
230
231
0
      for(;;)
232
0
        {
233
0
          if( !(mpi_cmp( k, p_1 ) < 0) )  /* check: k < (p-1) */
234
0
            {
235
0
              if( DBG_CIPHER )
236
0
                progress('+');
237
0
              break; /* no  */
238
0
            }
239
0
          if( !(mpi_cmp_ui( k, 0 ) > 0) )  /* check: k > 0 */
240
0
            {
241
0
              if( DBG_CIPHER )
242
0
                progress('-');
243
0
              break; /* no */
244
0
            }
245
0
          if (mpi_gcd( temp, k, p_1 ))
246
0
            goto found;  /* okay, k is relative prime to (p-1) */
247
0
          mpi_add_ui( k, k, 1 );
248
0
          if( DBG_CIPHER )
249
0
            progress('.');
250
0
  }
251
0
    }
252
0
 found:
253
0
  xfree (rndbuf);
254
0
  if( DBG_CIPHER )
255
0
    progress('\n');
256
0
  mpi_free(p_1);
257
0
  mpi_free(temp);
258
259
0
  return k;
260
0
}
261
262
/****************
263
 * Generate a key pair with a key of size NBITS
264
 * Returns: 2 structures filled with all needed values
265
 *      and an array with n-1 factors of (p-1)
266
 */
267
static gcry_err_code_t
268
generate ( ELG_secret_key *sk, unsigned int nbits, gcry_mpi_t **ret_factors )
269
0
{
270
0
  gcry_err_code_t rc;
271
0
  gcry_mpi_t p;    /* the prime */
272
0
  gcry_mpi_t p_min1;
273
0
  gcry_mpi_t g;
274
0
  gcry_mpi_t x;    /* the secret exponent */
275
0
  gcry_mpi_t y;
276
0
  unsigned int qbits;
277
0
  unsigned int xbits;
278
0
  byte *rndbuf;
279
280
0
  p_min1 = mpi_new ( nbits );
281
0
  qbits = wiener_map( nbits );
282
0
  if( qbits & 1 ) /* better have a even one */
283
0
    qbits++;
284
0
  g = mpi_alloc(1);
285
0
  rc = _gcry_generate_elg_prime (0, nbits, qbits, g, &p, ret_factors);
286
0
  if (rc)
287
0
    {
288
0
      mpi_free (p_min1);
289
0
      mpi_free (g);
290
0
      return rc;
291
0
    }
292
0
  mpi_sub_ui(p_min1, p, 1);
293
294
295
  /* Select a random number which has these properties:
296
   *   0 < x < p-1
297
   * This must be a very good random number because this is the
298
   * secret part.  The prime is public and may be shared anyway,
299
   * so a random generator level of 1 is used for the prime.
300
   *
301
   * I don't see a reason to have a x of about the same size
302
   * as the p.  It should be sufficient to have one about the size
303
   * of q or the later used k plus a large safety margin. Decryption
304
   * will be much faster with such an x.
305
   */
306
0
  xbits = qbits * 3 / 2;
307
0
  if( xbits >= nbits )
308
0
    BUG();
309
0
  x = mpi_snew ( xbits );
310
0
  if( DBG_CIPHER )
311
0
    log_debug("choosing a random x of size %u\n", xbits );
312
0
  rndbuf = NULL;
313
0
  do
314
0
    {
315
0
      if( DBG_CIPHER )
316
0
        progress('.');
317
0
      if( rndbuf )
318
0
        { /* Change only some of the higher bits */
319
0
          if( xbits < 16 ) /* should never happen ... */
320
0
            {
321
0
              xfree(rndbuf);
322
0
              rndbuf = _gcry_random_bytes_secure ((xbits+7)/8,
323
0
                                                  GCRY_VERY_STRONG_RANDOM);
324
0
            }
325
0
          else
326
0
            {
327
0
              char *r = _gcry_random_bytes_secure (2, GCRY_VERY_STRONG_RANDOM);
328
0
              memcpy(rndbuf, r, 2 );
329
0
              xfree (r);
330
0
            }
331
0
  }
332
0
      else
333
0
        {
334
0
          rndbuf = _gcry_random_bytes_secure ((xbits+7)/8,
335
0
                                              GCRY_VERY_STRONG_RANDOM );
336
0
  }
337
0
      _gcry_mpi_set_buffer( x, rndbuf, (xbits+7)/8, 0 );
338
0
      mpi_clear_highbit( x, xbits+1 );
339
0
    }
340
0
  while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, p_min1 )<0 ) );
341
0
  xfree(rndbuf);
342
343
0
  y = mpi_new (nbits);
344
0
  mpi_powm( y, g, x, p );
345
346
0
  if( DBG_CIPHER )
347
0
    {
348
0
      progress ('\n');
349
0
      log_mpidump ("elg  p", p );
350
0
      log_mpidump ("elg  g", g );
351
0
      log_mpidump ("elg  y", y );
352
0
      log_mpidump ("elg  x", x );
353
0
    }
354
355
  /* Copy the stuff to the key structures */
356
0
  sk->p = p;
357
0
  sk->g = g;
358
0
  sk->y = y;
359
0
  sk->x = x;
360
361
0
  _gcry_mpi_release ( p_min1 );
362
363
  /* Now we can test our keys (this should never fail!) */
364
0
  test_keys ( sk, nbits - 64, 0 );
365
366
0
  return 0;
367
0
}
368
369
370
/* Generate a key pair with a key of size NBITS not using a random
371
   value for the secret key but the one given as X.  This is useful to
372
   implement a passphrase based decryption for a public key based
373
   encryption.  It has appliactions in backup systems.
374
375
   Returns: A structure filled with all needed values and an array
376
      with n-1 factors of (p-1).  */
377
static gcry_err_code_t
378
generate_using_x (ELG_secret_key *sk, unsigned int nbits, gcry_mpi_t x,
379
                  gcry_mpi_t **ret_factors )
380
0
{
381
0
  gcry_err_code_t rc;
382
0
  gcry_mpi_t p;      /* The prime.  */
383
0
  gcry_mpi_t p_min1; /* The prime minus 1.  */
384
0
  gcry_mpi_t g;      /* The generator.  */
385
0
  gcry_mpi_t y;      /* g^x mod p.  */
386
0
  unsigned int qbits;
387
0
  unsigned int xbits;
388
389
0
  sk->p = NULL;
390
0
  sk->g = NULL;
391
0
  sk->y = NULL;
392
0
  sk->x = NULL;
393
394
  /* Do a quick check to see whether X is suitable.  */
395
0
  xbits = mpi_get_nbits (x);
396
0
  if ( xbits < 64 || xbits >= nbits )
397
0
    return GPG_ERR_INV_VALUE;
398
399
0
  p_min1 = mpi_new ( nbits );
400
0
  qbits  = wiener_map ( nbits );
401
0
  if ( (qbits & 1) ) /* Better have an even one.  */
402
0
    qbits++;
403
0
  g = mpi_alloc (1);
404
0
  rc = _gcry_generate_elg_prime (0, nbits, qbits, g, &p, ret_factors );
405
0
  if (rc)
406
0
    {
407
0
      mpi_free (p_min1);
408
0
      mpi_free (g);
409
0
      return rc;
410
0
    }
411
0
  mpi_sub_ui (p_min1, p, 1);
412
413
0
  if (DBG_CIPHER)
414
0
    log_debug ("using a supplied x of size %u", xbits );
415
0
  if ( !(mpi_cmp_ui ( x, 0 ) > 0 && mpi_cmp ( x, p_min1 ) <0 ) )
416
0
    {
417
0
      _gcry_mpi_release ( p_min1 );
418
0
      _gcry_mpi_release ( p );
419
0
      _gcry_mpi_release ( g );
420
0
      return GPG_ERR_INV_VALUE;
421
0
    }
422
423
0
  y = mpi_new (nbits);
424
0
  mpi_powm ( y, g, x, p );
425
426
0
  if ( DBG_CIPHER )
427
0
    {
428
0
      progress ('\n');
429
0
      log_mpidump ("elg  p", p );
430
0
      log_mpidump ("elg  g", g );
431
0
      log_mpidump ("elg  y", y );
432
0
      log_mpidump ("elg  x", x );
433
0
    }
434
435
  /* Copy the stuff to the key structures */
436
0
  sk->p = p;
437
0
  sk->g = g;
438
0
  sk->y = y;
439
0
  sk->x = mpi_copy (x);
440
441
0
  _gcry_mpi_release ( p_min1 );
442
443
  /* Now we can test our keys. */
444
0
  if ( test_keys ( sk, nbits - 64, 1 ) )
445
0
    {
446
0
      _gcry_mpi_release ( sk->p ); sk->p = NULL;
447
0
      _gcry_mpi_release ( sk->g ); sk->g = NULL;
448
0
      _gcry_mpi_release ( sk->y ); sk->y = NULL;
449
0
      _gcry_mpi_release ( sk->x ); sk->x = NULL;
450
0
      return GPG_ERR_BAD_SECKEY;
451
0
    }
452
453
0
  return 0;
454
0
}
455
456
457
/****************
458
 * Test whether the secret key is valid.
459
 * Returns: if this is a valid key.
460
 */
461
static int
462
check_secret_key( ELG_secret_key *sk )
463
0
{
464
0
  int rc;
465
0
  gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
466
467
0
  mpi_powm (y, sk->g, sk->x, sk->p);
468
0
  rc = !mpi_cmp( y, sk->y );
469
0
  mpi_free( y );
470
0
  return rc;
471
0
}
472
473
474
static void
475
do_encrypt(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
476
0
{
477
0
  gcry_mpi_t k;
478
479
  /* Note: maybe we should change the interface, so that it
480
   * is possible to check that input is < p and return an
481
   * error code.
482
   */
483
484
0
  k = gen_k( pkey->p );
485
0
  mpi_powm (a, pkey->g, k, pkey->p);
486
487
  /* b = (y^k * input) mod p
488
   *   = ((y^k mod p) * (input mod p)) mod p
489
   * and because input is < p
490
   *   = ((y^k mod p) * input) mod p
491
   */
492
0
  mpi_powm (b, pkey->y, k, pkey->p);
493
0
  mpi_mulm (b, b, input, pkey->p);
494
#if 0
495
  if( DBG_CIPHER )
496
    {
497
      log_mpidump("elg encrypted y", pkey->y);
498
      log_mpidump("elg encrypted p", pkey->p);
499
      log_mpidump("elg encrypted k", k);
500
      log_mpidump("elg encrypted M", input);
501
      log_mpidump("elg encrypted a", a);
502
      log_mpidump("elg encrypted b", b);
503
    }
504
#endif
505
0
  mpi_free(k);
506
0
}
507
508
509
510
511
static void
512
decrypt (gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b, ELG_secret_key *skey )
513
0
{
514
0
  gcry_mpi_t t1, t2, r, r1, h;
515
0
  unsigned int nbits = mpi_get_nbits (skey->p);
516
0
  gcry_mpi_t x_blind;
517
518
0
  mpi_normalize (a);
519
0
  mpi_normalize (b);
520
521
0
  t1 = mpi_snew (nbits);
522
523
0
#ifdef USE_BLINDING
524
525
0
  t2 = mpi_snew (nbits);
526
0
  r  = mpi_new (nbits);
527
0
  r1 = mpi_new (nbits);
528
0
  h  = mpi_new (nbits);
529
0
  x_blind = mpi_snew (nbits);
530
531
  /* We need a random number of about the prime size.  The random
532
     number merely needs to be unpredictable; thus we use level 0.  */
533
0
  _gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);
534
535
  /* Also, exponent blinding: x_blind = x + (p-1)*r1 */
536
0
  _gcry_mpi_randomize (r1, nbits, GCRY_WEAK_RANDOM);
537
0
  mpi_set_highbit (r1, nbits - 1);
538
0
  mpi_sub_ui (h, skey->p, 1);
539
0
  mpi_mul (x_blind, h, r1);
540
0
  mpi_add (x_blind, skey->x, x_blind);
541
542
  /* t1 = r^x mod p */
543
0
  mpi_powm (t1, r, x_blind, skey->p);
544
  /* t2 = (a * r)^-x mod p */
545
0
  mpi_mulm (t2, a, r, skey->p);
546
0
  mpi_powm (t2, t2, x_blind, skey->p);
547
0
  mpi_invm (t2, t2, skey->p);
548
  /* t1 = (t1 * t2) mod p*/
549
0
  mpi_mulm (t1, t1, t2, skey->p);
550
551
0
  mpi_free (x_blind);
552
0
  mpi_free (h);
553
0
  mpi_free (r1);
554
0
  mpi_free (r);
555
0
  mpi_free (t2);
556
557
#else /*!USE_BLINDING*/
558
559
  /* output = b/(a^x) mod p */
560
  mpi_powm (t1, a, skey->x, skey->p);
561
  mpi_invm (t1, t1, skey->p);
562
563
#endif /*!USE_BLINDING*/
564
565
0
  mpi_mulm (output, b, t1, skey->p);
566
567
#if 0
568
  if( DBG_CIPHER )
569
    {
570
      log_mpidump ("elg decrypted x", skey->x);
571
      log_mpidump ("elg decrypted p", skey->p);
572
      log_mpidump ("elg decrypted a", a);
573
      log_mpidump ("elg decrypted b", b);
574
      log_mpidump ("elg decrypted M", output);
575
    }
576
#endif
577
0
  mpi_free (t1);
578
0
}
579
580
581
/****************
582
 * Make an Elgamal signature out of INPUT
583
 */
584
585
static void
586
sign(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_secret_key *skey )
587
0
{
588
0
    gcry_mpi_t k;
589
0
    gcry_mpi_t t   = mpi_alloc( mpi_get_nlimbs(a) );
590
0
    gcry_mpi_t inv = mpi_alloc( mpi_get_nlimbs(a) );
591
0
    gcry_mpi_t p_1 = mpi_copy(skey->p);
592
593
   /*
594
    * b = (t * inv) mod (p-1)
595
    * b = (t * inv(k,(p-1),(p-1)) mod (p-1)
596
    * b = (((M-x*a) mod (p-1)) * inv(k,(p-1),(p-1))) mod (p-1)
597
    *
598
    */
599
0
    mpi_sub_ui(p_1, p_1, 1);
600
0
    k = gen_k( skey->p );
601
0
    mpi_powm( a, skey->g, k, skey->p );
602
0
    mpi_mul(t, skey->x, a );
603
0
    mpi_subm(t, input, t, p_1 );
604
0
    mpi_invm(inv, k, p_1 );
605
0
    mpi_mulm(b, t, inv, p_1 );
606
607
#if 0
608
    if( DBG_CIPHER )
609
      {
610
  log_mpidump ("elg sign p", skey->p);
611
  log_mpidump ("elg sign g", skey->g);
612
  log_mpidump ("elg sign y", skey->y);
613
  log_mpidump ("elg sign x", skey->x);
614
  log_mpidump ("elg sign k", k);
615
  log_mpidump ("elg sign M", input);
616
  log_mpidump ("elg sign a", a);
617
  log_mpidump ("elg sign b", b);
618
      }
619
#endif
620
0
    mpi_free(k);
621
0
    mpi_free(t);
622
0
    mpi_free(inv);
623
0
    mpi_free(p_1);
624
0
}
625
626
627
/****************
628
 * Returns true if the signature composed of A and B is valid.
629
 */
630
static int
631
verify(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
632
0
{
633
0
  int rc;
634
0
  gcry_mpi_t t1;
635
0
  gcry_mpi_t t2;
636
0
  gcry_mpi_t base[4];
637
0
  gcry_mpi_t ex[4];
638
639
0
  if( !(mpi_cmp_ui( a, 0 ) > 0 && mpi_cmp( a, pkey->p ) < 0) )
640
0
    return 0; /* assertion  0 < a < p  failed */
641
642
0
  t1 = mpi_alloc( mpi_get_nlimbs(a) );
643
0
  t2 = mpi_alloc( mpi_get_nlimbs(a) );
644
645
#if 0
646
  /* t1 = (y^a mod p) * (a^b mod p) mod p */
647
  gcry_mpi_powm( t1, pkey->y, a, pkey->p );
648
  gcry_mpi_powm( t2, a, b, pkey->p );
649
  mpi_mulm( t1, t1, t2, pkey->p );
650
651
  /* t2 = g ^ input mod p */
652
  gcry_mpi_powm( t2, pkey->g, input, pkey->p );
653
654
  rc = !mpi_cmp( t1, t2 );
655
#elif 0
656
  /* t1 = (y^a mod p) * (a^b mod p) mod p */
657
  base[0] = pkey->y; ex[0] = a;
658
  base[1] = a;       ex[1] = b;
659
  base[2] = NULL;    ex[2] = NULL;
660
  mpi_mulpowm( t1, base, ex, pkey->p );
661
662
  /* t2 = g ^ input mod p */
663
  gcry_mpi_powm( t2, pkey->g, input, pkey->p );
664
665
  rc = !mpi_cmp( t1, t2 );
666
#else
667
  /* t1 = g ^ - input * y ^ a * a ^ b  mod p */
668
0
  mpi_invm(t2, pkey->g, pkey->p );
669
0
  base[0] = t2     ; ex[0] = input;
670
0
  base[1] = pkey->y; ex[1] = a;
671
0
  base[2] = a;       ex[2] = b;
672
0
  base[3] = NULL;    ex[3] = NULL;
673
0
  mpi_mulpowm( t1, base, ex, pkey->p );
674
0
  rc = !mpi_cmp_ui( t1, 1 );
675
676
0
#endif
677
678
0
  mpi_free(t1);
679
0
  mpi_free(t2);
680
0
  return rc;
681
0
}
682
683
/*********************************************
684
 **************  interface  ******************
685
 *********************************************/
686
687
static gpg_err_code_t
688
elg_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
689
0
{
690
0
  gpg_err_code_t rc;
691
0
  unsigned int nbits;
692
0
  ELG_secret_key sk;
693
0
  gcry_mpi_t xvalue = NULL;
694
0
  gcry_sexp_t l1;
695
0
  gcry_mpi_t *factors = NULL;
696
0
  gcry_sexp_t misc_info = NULL;
697
698
0
  memset (&sk, 0, sizeof sk);
699
700
0
  rc = _gcry_pk_util_get_nbits (genparms, &nbits);
701
0
  if (rc)
702
0
    return rc;
703
704
  /* Parse the optional xvalue element. */
705
0
  l1 = sexp_find_token (genparms, "xvalue", 0);
706
0
  if (l1)
707
0
    {
708
0
      xvalue = sexp_nth_mpi (l1, 1, 0);
709
0
      sexp_release (l1);
710
0
      if (!xvalue)
711
0
        return GPG_ERR_BAD_MPI;
712
0
    }
713
714
0
  if (xvalue)
715
0
    {
716
0
      rc = generate_using_x (&sk, nbits, xvalue, &factors);
717
0
      mpi_free (xvalue);
718
0
    }
719
0
  else
720
0
    {
721
0
      rc = generate (&sk, nbits, &factors);
722
0
    }
723
0
  if (rc)
724
0
    goto leave;
725
726
0
  if (factors && factors[0])
727
0
    {
728
0
      int nfac;
729
0
      void **arg_list;
730
0
      char *buffer, *p;
731
732
0
      for (nfac = 0; factors[nfac]; nfac++)
733
0
        ;
734
0
      arg_list = xtrycalloc (nfac+1, sizeof *arg_list);
735
0
      if (!arg_list)
736
0
        {
737
0
          rc = gpg_err_code_from_syserror ();
738
0
          goto leave;
739
0
        }
740
0
      buffer = xtrymalloc (30 + nfac*2 + 2 + 1);
741
0
      if (!buffer)
742
0
        {
743
0
          rc = gpg_err_code_from_syserror ();
744
0
          xfree (arg_list);
745
0
          goto leave;
746
0
        }
747
0
      p = stpcpy (buffer, "(misc-key-info(pm1-factors");
748
0
      for(nfac = 0; factors[nfac]; nfac++)
749
0
        {
750
0
          p = stpcpy (p, "%m");
751
0
          arg_list[nfac] = factors + nfac;
752
0
        }
753
0
      p = stpcpy (p, "))");
754
0
      rc = sexp_build_array (&misc_info, NULL, buffer, arg_list);
755
0
      xfree (arg_list);
756
0
      xfree (buffer);
757
0
      if (rc)
758
0
        goto leave;
759
0
    }
760
761
0
  rc = sexp_build (r_skey, NULL,
762
0
                   "(key-data"
763
0
                   " (public-key"
764
0
                   "  (elg(p%m)(g%m)(y%m)))"
765
0
                   " (private-key"
766
0
                   "  (elg(p%m)(g%m)(y%m)(x%m)))"
767
0
                   " %S)",
768
0
                   sk.p, sk.g, sk.y,
769
0
                   sk.p, sk.g, sk.y, sk.x,
770
0
                   misc_info);
771
772
0
 leave:
773
0
  mpi_free (sk.p);
774
0
  mpi_free (sk.g);
775
0
  mpi_free (sk.y);
776
0
  mpi_free (sk.x);
777
0
  sexp_release (misc_info);
778
0
  if (factors)
779
0
    {
780
0
      gcry_mpi_t *mp;
781
0
      for (mp = factors; *mp; mp++)
782
0
        mpi_free (*mp);
783
0
      xfree (factors);
784
0
    }
785
786
0
  return rc;
787
0
}
788
789
790
static gcry_err_code_t
791
elg_check_secret_key (gcry_sexp_t keyparms)
792
0
{
793
0
  gcry_err_code_t rc;
794
0
  ELG_secret_key sk = {NULL, NULL, NULL, NULL};
795
796
0
  rc = sexp_extract_param (keyparms, NULL, "pgyx",
797
0
                           &sk.p, &sk.g, &sk.y, &sk.x,
798
0
                           NULL);
799
0
  if (rc)
800
0
    goto leave;
801
802
0
  if (!check_secret_key (&sk))
803
0
    rc = GPG_ERR_BAD_SECKEY;
804
805
0
 leave:
806
0
  _gcry_mpi_release (sk.p);
807
0
  _gcry_mpi_release (sk.g);
808
0
  _gcry_mpi_release (sk.y);
809
0
  _gcry_mpi_release (sk.x);
810
0
  if (DBG_CIPHER)
811
0
    log_debug ("elg_testkey    => %s\n", gpg_strerror (rc));
812
0
  return rc;
813
0
}
814
815
816
static gcry_err_code_t
817
elg_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
818
0
{
819
0
  gcry_err_code_t rc;
820
0
  struct pk_encoding_ctx ctx;
821
0
  gcry_mpi_t mpi_a = NULL;
822
0
  gcry_mpi_t mpi_b = NULL;
823
0
  gcry_mpi_t data = NULL;
824
0
  ELG_public_key pk = { NULL, NULL, NULL };
825
826
0
  _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
827
0
                                   elg_get_nbits (keyparms));
828
829
  /* Extract the data.  */
830
0
  rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
831
0
  if (rc)
832
0
    goto leave;
833
0
  if (DBG_CIPHER)
834
0
    log_mpidump ("elg_encrypt data", data);
835
0
  if (mpi_is_opaque (data))
836
0
    {
837
0
      rc = GPG_ERR_INV_DATA;
838
0
      goto leave;
839
0
    }
840
841
  /* Extract the key.  */
842
0
  rc = sexp_extract_param (keyparms, NULL, "pgy",
843
0
                           &pk.p, &pk.g, &pk.y, NULL);
844
0
  if (rc)
845
0
    goto leave;
846
0
  if (DBG_CIPHER)
847
0
    {
848
0
      log_mpidump ("elg_encrypt  p", pk.p);
849
0
      log_mpidump ("elg_encrypt  g", pk.g);
850
0
      log_mpidump ("elg_encrypt  y", pk.y);
851
0
    }
852
853
  /* Do Elgamal computation and build result.  */
854
0
  mpi_a = mpi_new (0);
855
0
  mpi_b = mpi_new (0);
856
0
  do_encrypt (mpi_a, mpi_b, data, &pk);
857
0
  rc = sexp_build (r_ciph, NULL, "(enc-val(elg(a%m)(b%m)))", mpi_a, mpi_b);
858
859
0
 leave:
860
0
  _gcry_mpi_release (mpi_a);
861
0
  _gcry_mpi_release (mpi_b);
862
0
  _gcry_mpi_release (pk.p);
863
0
  _gcry_mpi_release (pk.g);
864
0
  _gcry_mpi_release (pk.y);
865
0
  _gcry_mpi_release (data);
866
0
  _gcry_pk_util_free_encoding_ctx (&ctx);
867
0
  if (DBG_CIPHER)
868
0
    log_debug ("elg_encrypt   => %s\n", gpg_strerror (rc));
869
0
  return rc;
870
0
}
871
872
873
static gcry_err_code_t
874
elg_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
875
0
{
876
0
  gpg_err_code_t rc, rc_sexp;
877
0
  struct pk_encoding_ctx ctx;
878
0
  gcry_sexp_t l1 = NULL;
879
0
  gcry_mpi_t data_a = NULL;
880
0
  gcry_mpi_t data_b = NULL;
881
0
  ELG_secret_key sk = {NULL, NULL, NULL, NULL};
882
0
  gcry_mpi_t plain = NULL;
883
0
  unsigned char *unpad = NULL;
884
0
  size_t unpadlen = 0;
885
0
  gcry_sexp_t result = NULL;
886
0
  gcry_sexp_t dummy = NULL;
887
888
0
  _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
889
0
                                   elg_get_nbits (keyparms));
890
891
  /* Extract the data.  */
892
0
  rc = _gcry_pk_util_preparse_encval (s_data, elg_names, &l1, &ctx);
893
0
  if (rc)
894
0
    goto leave;
895
0
  rc = sexp_extract_param (l1, NULL, "ab", &data_a, &data_b, NULL);
896
0
  if (rc)
897
0
    goto leave;
898
0
  if (DBG_CIPHER)
899
0
    {
900
0
      log_printmpi ("elg_decrypt  d_a", data_a);
901
0
      log_printmpi ("elg_decrypt  d_b", data_b);
902
0
    }
903
0
  if (mpi_is_opaque (data_a) || mpi_is_opaque (data_b))
904
0
    {
905
0
      rc = GPG_ERR_INV_DATA;
906
0
      goto leave;
907
0
    }
908
909
  /* Extract the key.  */
910
0
  rc = sexp_extract_param (keyparms, NULL, "pgyx",
911
0
                           &sk.p, &sk.g, &sk.y, &sk.x,
912
0
                           NULL);
913
0
  if (rc)
914
0
    goto leave;
915
0
  if (DBG_CIPHER)
916
0
    {
917
0
      log_printmpi ("elg_decrypt    p", sk.p);
918
0
      log_printmpi ("elg_decrypt    g", sk.g);
919
0
      log_printmpi ("elg_decrypt    y", sk.y);
920
0
      if (!fips_mode ())
921
0
        log_printmpi ("elg_decrypt    x", sk.x);
922
0
    }
923
924
0
  plain = mpi_snew (ctx.nbits);
925
0
  decrypt (plain, data_a, data_b, &sk);
926
0
  if (DBG_CIPHER)
927
0
    log_printmpi ("elg_decrypt  res", plain);
928
929
  /* Reverse the encoding and build the s-expression.  */
930
0
  switch (ctx.encoding)
931
0
    {
932
0
    case PUBKEY_ENC_PKCS1:
933
0
      rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain);
934
0
      mpi_free (plain);
935
0
      plain = NULL;
936
0
      rc_sexp = sexp_build (&result, NULL, "(value %b)", (int)unpadlen, unpad);
937
0
      *r_plain = sexp_null_cond (result, ct_is_not_zero (rc));
938
0
      dummy = sexp_null_cond (result, ct_is_zero (rc));
939
0
      sexp_release (dummy);
940
0
      rc = ct_ulong_select (rc_sexp, rc,
941
0
          ct_is_zero (rc) & ct_is_not_zero (rc_sexp));
942
0
      break;
943
944
0
    case PUBKEY_ENC_OAEP:
945
0
      rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
946
0
                                  ctx.nbits, ctx.hash_algo, plain,
947
0
                                  ctx.label, ctx.labellen);
948
0
      mpi_free (plain);
949
0
      plain = NULL;
950
0
      rc_sexp = sexp_build (&result, NULL, "(value %b)", (int)unpadlen, unpad);
951
0
      *r_plain = sexp_null_cond (result, ct_is_not_zero (rc));
952
0
      dummy = sexp_null_cond (result, ct_is_zero (rc));
953
0
      sexp_release (dummy);
954
0
      rc = ct_ulong_select (rc_sexp, rc,
955
0
          ct_is_zero (rc) & ct_is_not_zero (rc_sexp));
956
0
      break;
957
958
0
    default:
959
      /* Raw format.  For backward compatibility we need to assume a
960
         signed mpi by using the sexp format string "%m".  */
961
0
      rc = sexp_build (r_plain, NULL,
962
0
                       (ctx.flags & PUBKEY_FLAG_LEGACYRESULT)
963
0
                       ? "%m" : "(value %m)",
964
0
                       plain);
965
0
      break;
966
0
    }
967
968
969
0
 leave:
970
0
  xfree (unpad);
971
0
  _gcry_mpi_release (plain);
972
0
  _gcry_mpi_release (sk.p);
973
0
  _gcry_mpi_release (sk.g);
974
0
  _gcry_mpi_release (sk.y);
975
0
  _gcry_mpi_release (sk.x);
976
0
  _gcry_mpi_release (data_a);
977
0
  _gcry_mpi_release (data_b);
978
0
  sexp_release (l1);
979
0
  _gcry_pk_util_free_encoding_ctx (&ctx);
980
0
  if (DBG_CIPHER)
981
0
    log_debug ("elg_decrypt    => %s\n", gpg_strerror (rc));
982
0
  return rc;
983
0
}
984
985
986
static gcry_err_code_t
987
elg_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
988
0
{
989
0
  gcry_err_code_t rc;
990
0
  struct pk_encoding_ctx ctx;
991
0
  gcry_mpi_t data = NULL;
992
0
  ELG_secret_key sk = {NULL, NULL, NULL, NULL};
993
0
  gcry_mpi_t sig_r = NULL;
994
0
  gcry_mpi_t sig_s = NULL;
995
996
0
  _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
997
0
                                   elg_get_nbits (keyparms));
998
999
  /* Extract the data.  */
1000
0
  rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1001
0
  if (rc)
1002
0
    goto leave;
1003
0
  if (DBG_CIPHER)
1004
0
    log_mpidump ("elg_sign   data", data);
1005
0
  if (mpi_is_opaque (data))
1006
0
    {
1007
0
      rc = GPG_ERR_INV_DATA;
1008
0
      goto leave;
1009
0
    }
1010
1011
  /* Extract the key.  */
1012
0
  rc = sexp_extract_param (keyparms, NULL, "pgyx",
1013
0
                           &sk.p, &sk.g, &sk.y, &sk.x, NULL);
1014
0
  if (rc)
1015
0
    goto leave;
1016
0
  if (DBG_CIPHER)
1017
0
    {
1018
0
      log_mpidump ("elg_sign      p", sk.p);
1019
0
      log_mpidump ("elg_sign      g", sk.g);
1020
0
      log_mpidump ("elg_sign      y", sk.y);
1021
0
      if (!fips_mode ())
1022
0
        log_mpidump ("elg_sign      x", sk.x);
1023
0
    }
1024
1025
0
  sig_r = mpi_new (0);
1026
0
  sig_s = mpi_new (0);
1027
0
  sign (sig_r, sig_s, data, &sk);
1028
0
  if (DBG_CIPHER)
1029
0
    {
1030
0
      log_mpidump ("elg_sign  sig_r", sig_r);
1031
0
      log_mpidump ("elg_sign  sig_s", sig_s);
1032
0
    }
1033
0
  rc = sexp_build (r_sig, NULL, "(sig-val(elg(r%M)(s%M)))", sig_r, sig_s);
1034
1035
0
 leave:
1036
0
  _gcry_mpi_release (sig_r);
1037
0
  _gcry_mpi_release (sig_s);
1038
0
  _gcry_mpi_release (sk.p);
1039
0
  _gcry_mpi_release (sk.g);
1040
0
  _gcry_mpi_release (sk.y);
1041
0
  _gcry_mpi_release (sk.x);
1042
0
  _gcry_mpi_release (data);
1043
0
  _gcry_pk_util_free_encoding_ctx (&ctx);
1044
0
  if (DBG_CIPHER)
1045
0
    log_debug ("elg_sign      => %s\n", gpg_strerror (rc));
1046
0
  return rc;
1047
0
}
1048
1049
1050
static gcry_err_code_t
1051
elg_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1052
0
{
1053
0
  gcry_err_code_t rc;
1054
0
  struct pk_encoding_ctx ctx;
1055
0
  gcry_sexp_t l1 = NULL;
1056
0
  gcry_mpi_t sig_r = NULL;
1057
0
  gcry_mpi_t sig_s = NULL;
1058
0
  gcry_mpi_t data = NULL;
1059
0
  ELG_public_key pk = { NULL, NULL, NULL };
1060
1061
0
  _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1062
0
                                   elg_get_nbits (s_keyparms));
1063
1064
  /* Extract the data.  */
1065
0
  rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1066
0
  if (rc)
1067
0
    goto leave;
1068
0
  if (DBG_CIPHER)
1069
0
    log_mpidump ("elg_verify data", data);
1070
0
  if (mpi_is_opaque (data))
1071
0
    {
1072
0
      rc = GPG_ERR_INV_DATA;
1073
0
      goto leave;
1074
0
    }
1075
1076
  /* Extract the signature value.  */
1077
0
  rc = _gcry_pk_util_preparse_sigval (s_sig, elg_names, &l1, NULL);
1078
0
  if (rc)
1079
0
    goto leave;
1080
0
  rc = sexp_extract_param (l1, NULL, "rs", &sig_r, &sig_s, NULL);
1081
0
  if (rc)
1082
0
    goto leave;
1083
0
  if (DBG_CIPHER)
1084
0
    {
1085
0
      log_mpidump ("elg_verify  s_r", sig_r);
1086
0
      log_mpidump ("elg_verify  s_s", sig_s);
1087
0
    }
1088
1089
  /* Extract the key.  */
1090
0
  rc = sexp_extract_param (s_keyparms, NULL, "pgy",
1091
0
                                 &pk.p, &pk.g, &pk.y, NULL);
1092
0
  if (rc)
1093
0
    goto leave;
1094
0
  if (DBG_CIPHER)
1095
0
    {
1096
0
      log_mpidump ("elg_verify    p", pk.p);
1097
0
      log_mpidump ("elg_verify    g", pk.g);
1098
0
      log_mpidump ("elg_verify    y", pk.y);
1099
0
    }
1100
1101
  /* Verify the signature.  */
1102
0
  if (!verify (sig_r, sig_s, data, &pk))
1103
0
    rc = GPG_ERR_BAD_SIGNATURE;
1104
1105
0
 leave:
1106
0
  _gcry_mpi_release (pk.p);
1107
0
  _gcry_mpi_release (pk.g);
1108
0
  _gcry_mpi_release (pk.y);
1109
0
  _gcry_mpi_release (data);
1110
0
  _gcry_mpi_release (sig_r);
1111
0
  _gcry_mpi_release (sig_s);
1112
0
  sexp_release (l1);
1113
0
  _gcry_pk_util_free_encoding_ctx (&ctx);
1114
0
  if (DBG_CIPHER)
1115
0
    log_debug ("elg_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1116
0
  return rc;
1117
0
}
1118
1119
1120
/* Return the number of bits for the key described by PARMS.  On error
1121
 * 0 is returned.  The format of PARMS starts with the algorithm name;
1122
 * for example:
1123
 *
1124
 *   (dsa
1125
 *     (p <mpi>)
1126
 *     (g <mpi>)
1127
 *     (y <mpi>))
1128
 *
1129
 * More parameters may be given but we only need P here.
1130
 */
1131
static unsigned int
1132
elg_get_nbits (gcry_sexp_t parms)
1133
0
{
1134
0
  gcry_sexp_t l1;
1135
0
  gcry_mpi_t p;
1136
0
  unsigned int nbits;
1137
1138
0
  l1 = sexp_find_token (parms, "p", 1);
1139
0
  if (!l1)
1140
0
    return 0; /* Parameter P not found.  */
1141
1142
0
  p= sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1143
0
  sexp_release (l1);
1144
0
  nbits = p? mpi_get_nbits (p) : 0;
1145
0
  _gcry_mpi_release (p);
1146
0
  return nbits;
1147
0
}
1148
1149
1150

1151
gcry_pk_spec_t _gcry_pubkey_spec_elg =
1152
  {
1153
    GCRY_PK_ELG, { 0, 0 },
1154
    (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1155
    "ELG", elg_names,
1156
    "pgy", "pgyx", "ab", "rs", "pgy",
1157
    elg_generate,
1158
    elg_check_secret_key,
1159
    elg_encrypt,
1160
    elg_decrypt,
1161
    elg_sign,
1162
    elg_verify,
1163
    elg_get_nbits,
1164
  };