← Back to branch summary

~hamo/ubuntu/precise/grub2/grub2.hi_res

« back to all changes in this revision

Viewing changes to lib/libgcrypt/cipher/elgamal.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Robert Millan, Updated translations
  • Date: 2010-11-22 12:24:56 UTC
  • mfrom: (1.26.4 upstream) (17.3.36 sid)
  • mto: (17.3.43 sid)
  • mto: This revision was merged to the branch mainline in revision 89.
  • Revision ID: james.westby@ubuntu.com-20101122122456-y82z3sfb7k4zfdcc
Tags: 1.99~20101122-1
http://bugs.debian.org/550658
http://bugs.debian.org/550702
http://bugs.debian.org/591416
http://bugs.debian.org/593347
http://bugs.debian.org/551627
http://bugs.debian.org/589325
http://bugs.debian.org/543924
http://bugs.debian.org/603354
http://bugs.debian.org/604003
http://bugs.debian.org/604102
[ Colin Watson ]
* New Bazaar snapshot.  Too many changes to list in full, but some of the
  more user-visible ones are as follows:
  - GRUB script:
    + Function parameters, "break", "continue", "shift", "setparams",
      "return", and "!".
    + "export" command supports multiple variable names.
    + Multi-line quoted strings support.
    + Wildcard expansion.
  - sendkey support.
  - USB hotunplugging and USB serial support.
  - Rename CD-ROM to cd on BIOS.
  - Add new --boot-directory option to grub-install, grub-reboot, and
    grub-set-default; the old --root-directory option is still accepted
    but was often confusing.
  - Basic btrfs detection/UUID support (but no file reading yet).
  - bash-completion for utilities.
  - If a device is listed in device.map, always assume that it is
    BIOS-visible rather than using extra layers such as LVM or RAID.
  - Add grub-mknetdir script (closes: #550658).
  - Remove deprecated "root" command.
  - Handle RAID devices containing virtio components.
  - GRUB Legacy configuration file support (via grub-menulst2cfg).
  - Keyboard layout support (via grub-mklayout and grub-kbdcomp).
  - Check generated grub.cfg for syntax errors before saving.
  - Pause execution for at most ten seconds if any errors are displayed,
    so that the user has a chance to see them.
  - Support submenus.
  - Write embedding zone using Reed-Solomon, so that it's robust against
    being partially overwritten (closes: #550702, #591416, #593347).
  - GRUB_DISABLE_LINUX_RECOVERY and GRUB_DISABLE_NETBSD_RECOVERY merged
    into a single GRUB_DISABLE_RECOVERY variable.
  - Fix loader memory allocation failure (closes: #551627).
  - Don't call savedefault on recovery entries (closes: #589325).
  - Support triple-indirect blocks on ext2 (closes: #543924).
  - Recognise DDF1 fake RAID (closes: #603354).

[ Robert Millan ]
* Use dpkg architecture wildcards.

[ Updated translations ]
* Slovenian (Vanja Cvelbar).  Closes: #604003
* Dzongkha (dawa pemo via Tenzin Dendup).  Closes: #604102

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/libgcrypt/cipher/elgamal.c
1
 
/* Elgamal.c  -  Elgamal Public Key encryption
2
 
 * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3
 
 *               2008  Free Software Foundation, Inc.
4
 
 *
5
 
 * This file is part of Libgcrypt.
6
 
 *
7
 
 * Libgcrypt is free software; you can redistribute it and/or modify
8
 
 * it under the terms of the GNU Lesser General Public License as
9
 
 * published by the Free Software Foundation; either version 2.1 of
10
 
 * the License, or (at your option) any later version.
11
 
 *
12
 
 * Libgcrypt is distributed in the hope that it will be useful,
13
 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14
 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
 
 * GNU Lesser General Public License for more details.
16
 
 *
17
 
 * You should have received a copy of the GNU Lesser General Public
18
 
 * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19
 
 *
20
 
 * For a description of the algorithm, see:
21
 
 *   Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
22
 
 *   ISBN 0-471-11709-9. Pages 476 ff.
23
 
 */
24
 
 
25
 
#include <config.h>
26
 
#include <stdio.h>
27
 
#include <stdlib.h>
28
 
#include <string.h>
29
 
#include "g10lib.h"
30
 
#include "mpi.h"
31
 
#include "cipher.h"
32
 
 
33
 
typedef struct
34
 
{
35
 
  gcry_mpi_t p;     /* prime */
36
 
  gcry_mpi_t g;     /* group generator */
37
 
  gcry_mpi_t y;     /* g^x mod p */
38
 
} ELG_public_key;
39
 
 
40
 
 
41
 
typedef struct
42
 
{
43
 
  gcry_mpi_t p;     /* prime */
44
 
  gcry_mpi_t g;     /* group generator */
45
 
  gcry_mpi_t y;     /* g^x mod p */
46
 
  gcry_mpi_t x;     /* secret exponent */
47
 
} ELG_secret_key;
48
 
 
49
 
 
50
 
static int test_keys (ELG_secret_key *sk, unsigned int nbits, int nodie);
51
 
static gcry_mpi_t gen_k (gcry_mpi_t p, int small_k);
52
 
static void generate (ELG_secret_key *sk, unsigned nbits, gcry_mpi_t **factors);
53
 
static int  check_secret_key (ELG_secret_key *sk);
54
 
static void do_encrypt (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
55
 
                        ELG_public_key *pkey);
56
 
static void decrypt (gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b,
57
 
                     ELG_secret_key *skey);
58
 
static void sign (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
59
 
                  ELG_secret_key *skey);
60
 
static int  verify (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
61
 
                    ELG_public_key *pkey);
62
 
 
63
 
 
64
 
static void (*progress_cb) (void *, const char *, int, int, int);
65
 
static void *progress_cb_data;
66
 
 
67
 
void
68
 
_gcry_register_pk_elg_progress (void (*cb) (void *, const char *,
69
 
                                            int, int, int),
70
 
                                void *cb_data)
71
 
{
72
 
  progress_cb = cb;
73
 
  progress_cb_data = cb_data;
74
 
}
75
 
 
76
 
 
77
 
static void
78
 
progress (int c)
79
 
{
80
 
  if (progress_cb)
81
 
    progress_cb (progress_cb_data, "pk_elg", c, 0, 0);
82
 
}
83
 
 
84
 
 
85
 
/****************
86
 
 * Michael Wiener's table on subgroup sizes to match field sizes.
87
 
 * (floating around somewhere, probably based on the paper from
88
 
 * Eurocrypt 96, page 332)
89
 
 */
90
 
static unsigned int
91
 
wiener_map( unsigned int n )
92
 
{
93
 
  static struct { unsigned int p_n, q_n; } t[] =
94
 
    { /*   p      q      attack cost */
95
 
      {  512, 119 },    /* 9 x 10^17 */
96
 
      {  768, 145 },    /* 6 x 10^21 */
97
 
      { 1024, 165 },    /* 7 x 10^24 */
98
 
      { 1280, 183 },    /* 3 x 10^27 */
99
 
      { 1536, 198 },    /* 7 x 10^29 */
100
 
      { 1792, 212 },    /* 9 x 10^31 */
101
 
      { 2048, 225 },    /* 8 x 10^33 */
102
 
      { 2304, 237 },    /* 5 x 10^35 */
103
 
      { 2560, 249 },    /* 3 x 10^37 */
104
 
      { 2816, 259 },    /* 1 x 10^39 */
105
 
      { 3072, 269 },    /* 3 x 10^40 */
106
 
      { 3328, 279 },    /* 8 x 10^41 */
107
 
      { 3584, 288 },    /* 2 x 10^43 */
108
 
      { 3840, 296 },    /* 4 x 10^44 */
109
 
      { 4096, 305 },    /* 7 x 10^45 */
110
 
      { 4352, 313 },    /* 1 x 10^47 */
111
 
      { 4608, 320 },    /* 2 x 10^48 */
112
 
      { 4864, 328 },    /* 2 x 10^49 */
113
 
      { 5120, 335 },    /* 3 x 10^50 */
114
 
      { 0, 0 }
115
 
    };
116
 
  int i;
117
 
 
118
 
  for(i=0; t[i].p_n; i++ )  
119
 
    {
120
 
      if( n <= t[i].p_n )
121
 
        return t[i].q_n;
122
 
    }
123
 
  /* Not in table - use an arbitrary high number. */
124
 
  return  n / 8 + 200;
125
 
}
126
 
 
127
 
static int
128
 
test_keys ( ELG_secret_key *sk, unsigned int nbits, int nodie )
129
 
{
130
 
  ELG_public_key pk;
131
 
  gcry_mpi_t test = gcry_mpi_new ( 0 );
132
 
  gcry_mpi_t out1_a = gcry_mpi_new ( nbits );
133
 
  gcry_mpi_t out1_b = gcry_mpi_new ( nbits );
134
 
  gcry_mpi_t out2 = gcry_mpi_new ( nbits );
135
 
  int failed = 0;
136
 
 
137
 
  pk.p = sk->p;
138
 
  pk.g = sk->g;
139
 
  pk.y = sk->y;
140
 
 
141
 
  gcry_mpi_randomize ( test, nbits, GCRY_WEAK_RANDOM );
142
 
 
143
 
  do_encrypt ( out1_a, out1_b, test, &pk );
144
 
  decrypt ( out2, out1_a, out1_b, sk );
145
 
  if ( mpi_cmp( test, out2 ) )
146
 
    failed |= 1;
147
 
 
148
 
  sign ( out1_a, out1_b, test, sk );
149
 
  if ( !verify( out1_a, out1_b, test, &pk ) )
150
 
    failed |= 2;
151
 
 
152
 
  gcry_mpi_release ( test );
153
 
  gcry_mpi_release ( out1_a );
154
 
  gcry_mpi_release ( out1_b );
155
 
  gcry_mpi_release ( out2 );
156
 
 
157
 
  if (failed && !nodie)
158
 
    log_fatal ("Elgamal test key for %s %s failed\n",
159
 
               (failed & 1)? "encrypt+decrypt":"",
160
 
               (failed & 2)? "sign+verify":"");
161
 
  if (failed && DBG_CIPHER) 
162
 
    log_debug ("Elgamal test key for %s %s failed\n",
163
 
               (failed & 1)? "encrypt+decrypt":"",
164
 
               (failed & 2)? "sign+verify":"");
165
 
 
166
 
  return failed;
167
 
}
168
 
 
169
 
 
170
 
/****************
171
 
 * Generate a random secret exponent k from prime p, so that k is
172
 
 * relatively prime to p-1.  With SMALL_K set, k will be selected for
173
 
 * better encryption performance - this must never be used signing!
174
 
 */
175
 
static gcry_mpi_t
176
 
gen_k( gcry_mpi_t p, int small_k )
177
 
{
178
 
  gcry_mpi_t k = mpi_alloc_secure( 0 );
179
 
  gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(p) );
180
 
  gcry_mpi_t p_1 = mpi_copy(p);
181
 
  unsigned int orig_nbits = mpi_get_nbits(p);
182
 
  unsigned int nbits, nbytes;
183
 
  char *rndbuf = NULL;
184
 
 
185
 
  if (small_k)
186
 
    {
187
 
      /* Using a k much lesser than p is sufficient for encryption and
188
 
       * it greatly improves the encryption performance.  We use
189
 
       * Wiener's table and add a large safety margin. */
190
 
      nbits = wiener_map( orig_nbits ) * 3 / 2;
191
 
      if( nbits >= orig_nbits )
192
 
        BUG();
193
 
    }
194
 
  else
195
 
    nbits = orig_nbits;
196
 
 
197
 
 
198
 
  nbytes = (nbits+7)/8;
199
 
  if( DBG_CIPHER )
200
 
    log_debug("choosing a random k ");
201
 
  mpi_sub_ui( p_1, p, 1);
202
 
  for(;;) 
203
 
    {
204
 
      if( !rndbuf || nbits < 32 ) 
205
 
        {
206
 
          gcry_free(rndbuf);
207
 
          rndbuf = gcry_random_bytes_secure( nbytes, GCRY_STRONG_RANDOM );
208
 
        }
209
 
      else
210
 
        { 
211
 
          /* Change only some of the higher bits.  We could improve
212
 
             this by directly requesting more memory at the first call
213
 
             to get_random_bytes() and use this the here maybe it is
214
 
             easier to do this directly in random.c Anyway, it is
215
 
             highly inlikely that we will ever reach this code. */
216
 
          char *pp = gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
217
 
          memcpy( rndbuf, pp, 4 );
218
 
          gcry_free(pp);
219
 
        }
220
 
      _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
221
 
        
222
 
      for(;;)
223
 
        {
224
 
          if( !(mpi_cmp( k, p_1 ) < 0) )  /* check: k < (p-1) */
225
 
            {
226
 
              if( DBG_CIPHER )
227
 
                progress('+');
228
 
              break; /* no  */
229
 
            }
230
 
          if( !(mpi_cmp_ui( k, 0 ) > 0) )  /* check: k > 0 */
231
 
            {
232
 
              if( DBG_CIPHER )
233
 
                progress('-');
234
 
              break; /* no */
235
 
            }
236
 
          if (gcry_mpi_gcd( temp, k, p_1 ))
237
 
            goto found;  /* okay, k is relative prime to (p-1) */
238
 
          mpi_add_ui( k, k, 1 );
239
 
          if( DBG_CIPHER )
240
 
            progress('.');
241
 
        }
242
 
    }
243
 
 found:
244
 
  gcry_free(rndbuf);
245
 
  if( DBG_CIPHER )
246
 
    progress('\n');
247
 
  mpi_free(p_1);
248
 
  mpi_free(temp);
249
 
 
250
 
  return k;
251
 
}
252
 
 
253
 
/****************
254
 
 * Generate a key pair with a key of size NBITS
255
 
 * Returns: 2 structures filled with all needed values
256
 
 *          and an array with n-1 factors of (p-1)
257
 
 */
258
 
static void
259
 
generate ( ELG_secret_key *sk, unsigned int nbits, gcry_mpi_t **ret_factors )
260
 
{
261
 
  gcry_mpi_t p;    /* the prime */
262
 
  gcry_mpi_t p_min1;
263
 
  gcry_mpi_t g;
264
 
  gcry_mpi_t x;    /* the secret exponent */
265
 
  gcry_mpi_t y;
266
 
  unsigned int qbits;
267
 
  unsigned int xbits;
268
 
  byte *rndbuf;
269
 
 
270
 
  p_min1 = gcry_mpi_new ( nbits );
271
 
  qbits = wiener_map( nbits );
272
 
  if( qbits & 1 ) /* better have a even one */
273
 
    qbits++;
274
 
  g = mpi_alloc(1);
275
 
  p = _gcry_generate_elg_prime( 0, nbits, qbits, g, ret_factors );
276
 
  mpi_sub_ui(p_min1, p, 1);
277
 
 
278
 
 
279
 
  /* Select a random number which has these properties:
280
 
   *     0 < x < p-1
281
 
   * This must be a very good random number because this is the
282
 
   * secret part.  The prime is public and may be shared anyway,
283
 
   * so a random generator level of 1 is used for the prime.
284
 
   *
285
 
   * I don't see a reason to have a x of about the same size
286
 
   * as the p.  It should be sufficient to have one about the size
287
 
   * of q or the later used k plus a large safety margin. Decryption
288
 
   * will be much faster with such an x.
289
 
   */
290
 
  xbits = qbits * 3 / 2;
291
 
  if( xbits >= nbits )
292
 
    BUG();
293
 
  x = gcry_mpi_snew ( xbits );
294
 
  if( DBG_CIPHER )
295
 
    log_debug("choosing a random x of size %u", xbits );
296
 
  rndbuf = NULL;
297
 
  do 
298
 
    {
299
 
      if( DBG_CIPHER )
300
 
        progress('.');
301
 
      if( rndbuf )
302
 
        { /* Change only some of the higher bits */
303
 
          if( xbits < 16 ) /* should never happen ... */
304
 
            {
305
 
              gcry_free(rndbuf);
306
 
              rndbuf = gcry_random_bytes_secure( (xbits+7)/8,
307
 
                                                 GCRY_VERY_STRONG_RANDOM );
308
 
            }
309
 
          else
310
 
            {
311
 
              char *r = gcry_random_bytes_secure( 2,
312
 
                                                  GCRY_VERY_STRONG_RANDOM );
313
 
              memcpy(rndbuf, r, 2 );
314
 
              gcry_free(r);
315
 
            }
316
 
        }
317
 
      else 
318
 
        {
319
 
          rndbuf = gcry_random_bytes_secure( (xbits+7)/8,
320
 
                                             GCRY_VERY_STRONG_RANDOM );
321
 
        }
322
 
      _gcry_mpi_set_buffer( x, rndbuf, (xbits+7)/8, 0 );
323
 
      mpi_clear_highbit( x, xbits+1 );
324
 
    } 
325
 
  while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, p_min1 )<0 ) );
326
 
  gcry_free(rndbuf);
327
 
 
328
 
  y = gcry_mpi_new (nbits);
329
 
  gcry_mpi_powm( y, g, x, p );
330
 
 
331
 
  if( DBG_CIPHER ) 
332
 
    {
333
 
      progress('\n');
334
 
      log_mpidump("elg  p= ", p );
335
 
      log_mpidump("elg  g= ", g );
336
 
      log_mpidump("elg  y= ", y );
337
 
      log_mpidump("elg  x= ", x );
338
 
    }
339
 
 
340
 
  /* Copy the stuff to the key structures */
341
 
  sk->p = p;
342
 
  sk->g = g;
343
 
  sk->y = y;
344
 
  sk->x = x;
345
 
 
346
 
  gcry_mpi_release ( p_min1 );
347
 
 
348
 
  /* Now we can test our keys (this should never fail!) */
349
 
  test_keys ( sk, nbits - 64, 0 );
350
 
}
351
 
 
352
 
 
353
 
/* Generate a key pair with a key of size NBITS not using a random
354
 
   value for the secret key but the one given as X.  This is useful to
355
 
   implement a passphrase based decryption for a public key based
356
 
   encryption.  It has appliactions in backup systems.
357
 
 
358
 
   Returns: A structure filled with all needed values and an array
359
 
            with n-1 factors of (p-1).  */
360
 
static gcry_err_code_t
361
 
generate_using_x (ELG_secret_key *sk, unsigned int nbits, gcry_mpi_t x,
362
 
                  gcry_mpi_t **ret_factors )
363
 
{
364
 
  gcry_mpi_t p;      /* The prime.  */
365
 
  gcry_mpi_t p_min1; /* The prime minus 1.  */
366
 
  gcry_mpi_t g;      /* The generator.  */
367
 
  gcry_mpi_t y;      /* g^x mod p.  */
368
 
  unsigned int qbits;
369
 
  unsigned int xbits;
370
 
 
371
 
  sk->p = NULL;
372
 
  sk->g = NULL;
373
 
  sk->y = NULL;
374
 
  sk->x = NULL;
375
 
 
376
 
  /* Do a quick check to see whether X is suitable.  */
377
 
  xbits = mpi_get_nbits (x);
378
 
  if ( xbits < 64 || xbits >= nbits )
379
 
    return GPG_ERR_INV_VALUE;
380
 
 
381
 
  p_min1 = gcry_mpi_new ( nbits );
382
 
  qbits  = wiener_map ( nbits );
383
 
  if ( (qbits & 1) ) /* Better have an even one.  */
384
 
    qbits++;
385
 
  g = mpi_alloc (1);
386
 
  p = _gcry_generate_elg_prime ( 0, nbits, qbits, g, ret_factors );
387
 
  mpi_sub_ui (p_min1, p, 1);
388
 
 
389
 
  if (DBG_CIPHER)
390
 
    log_debug ("using a supplied x of size %u", xbits );
391
 
  if ( !(mpi_cmp_ui ( x, 0 ) > 0 && mpi_cmp ( x, p_min1 ) <0 ) )
392
 
    {
393
 
      gcry_mpi_release ( p_min1 );
394
 
      gcry_mpi_release ( p );
395
 
      gcry_mpi_release ( g );
396
 
      return GPG_ERR_INV_VALUE;
397
 
    }
398
 
 
399
 
  y = gcry_mpi_new (nbits);
400
 
  gcry_mpi_powm ( y, g, x, p );
401
 
 
402
 
  if ( DBG_CIPHER ) 
403
 
    {
404
 
      progress ('\n');
405
 
      log_mpidump ("elg  p= ", p );
406
 
      log_mpidump ("elg  g= ", g );
407
 
      log_mpidump ("elg  y= ", y );
408
 
      log_mpidump ("elg  x= ", x );
409
 
    }
410
 
 
411
 
  /* Copy the stuff to the key structures */
412
 
  sk->p = p;
413
 
  sk->g = g;
414
 
  sk->y = y;
415
 
  sk->x = gcry_mpi_copy (x);
416
 
 
417
 
  gcry_mpi_release ( p_min1 );
418
 
 
419
 
  /* Now we can test our keys. */
420
 
  if ( test_keys ( sk, nbits - 64, 1 ) )
421
 
    {
422
 
      gcry_mpi_release ( sk->p ); sk->p = NULL;
423
 
      gcry_mpi_release ( sk->g ); sk->g = NULL;
424
 
      gcry_mpi_release ( sk->y ); sk->y = NULL;
425
 
      gcry_mpi_release ( sk->x ); sk->x = NULL;
426
 
      return GPG_ERR_BAD_SECKEY;
427
 
    }
428
 
 
429
 
  return 0;
430
 
}
431
 
 
432
 
 
433
 
/****************
434
 
 * Test whether the secret key is valid.
435
 
 * Returns: if this is a valid key.
436
 
 */
437
 
static int
438
 
check_secret_key( ELG_secret_key *sk )
439
 
{
440
 
  int rc;
441
 
  gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
442
 
 
443
 
  gcry_mpi_powm( y, sk->g, sk->x, sk->p );
444
 
  rc = !mpi_cmp( y, sk->y );
445
 
  mpi_free( y );
446
 
  return rc;
447
 
}
448
 
 
449
 
 
450
 
static void
451
 
do_encrypt(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
452
 
{
453
 
  gcry_mpi_t k;
454
 
 
455
 
  /* Note: maybe we should change the interface, so that it
456
 
   * is possible to check that input is < p and return an
457
 
   * error code.
458
 
   */
459
 
 
460
 
  k = gen_k( pkey->p, 1 );
461
 
  gcry_mpi_powm( a, pkey->g, k, pkey->p );
462
 
  /* b = (y^k * input) mod p
463
 
   *     = ((y^k mod p) * (input mod p)) mod p
464
 
   * and because input is < p
465
 
   *     = ((y^k mod p) * input) mod p
466
 
   */
467
 
  gcry_mpi_powm( b, pkey->y, k, pkey->p );
468
 
  gcry_mpi_mulm( b, b, input, pkey->p );
469
 
#if 0
470
 
  if( DBG_CIPHER )
471
 
    {
472
 
      log_mpidump("elg encrypted y= ", pkey->y);
473
 
      log_mpidump("elg encrypted p= ", pkey->p);
474
 
      log_mpidump("elg encrypted k= ", k);
475
 
      log_mpidump("elg encrypted M= ", input);
476
 
      log_mpidump("elg encrypted a= ", a);
477
 
      log_mpidump("elg encrypted b= ", b);
478
 
    }
479
 
#endif
480
 
  mpi_free(k);
481
 
}
482
 
 
483
 
 
484
 
 
485
 
 
486
 
static void
487
 
decrypt(gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b, ELG_secret_key *skey )
488
 
{
489
 
  gcry_mpi_t t1 = mpi_alloc_secure( mpi_get_nlimbs( skey->p ) );
490
 
 
491
 
  /* output = b/(a^x) mod p */
492
 
  gcry_mpi_powm( t1, a, skey->x, skey->p );
493
 
  mpi_invm( t1, t1, skey->p );
494
 
  mpi_mulm( output, b, t1, skey->p );
495
 
#if 0
496
 
  if( DBG_CIPHER ) 
497
 
    {
498
 
      log_mpidump("elg decrypted x= ", skey->x);
499
 
      log_mpidump("elg decrypted p= ", skey->p);
500
 
      log_mpidump("elg decrypted a= ", a);
501
 
      log_mpidump("elg decrypted b= ", b);
502
 
      log_mpidump("elg decrypted M= ", output);
503
 
    }
504
 
#endif
505
 
  mpi_free(t1);
506
 
}
507
 
 
508
 
 
509
 
/****************
510
 
 * Make an Elgamal signature out of INPUT
511
 
 */
512
 
 
513
 
static void
514
 
sign(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_secret_key *skey )
515
 
{
516
 
    gcry_mpi_t k;
517
 
    gcry_mpi_t t   = mpi_alloc( mpi_get_nlimbs(a) );
518
 
    gcry_mpi_t inv = mpi_alloc( mpi_get_nlimbs(a) );
519
 
    gcry_mpi_t p_1 = mpi_copy(skey->p);
520
 
 
521
 
   /*
522
 
    * b = (t * inv) mod (p-1)
523
 
    * b = (t * inv(k,(p-1),(p-1)) mod (p-1)
524
 
    * b = (((M-x*a) mod (p-1)) * inv(k,(p-1),(p-1))) mod (p-1)
525
 
    *
526
 
    */
527
 
    mpi_sub_ui(p_1, p_1, 1);
528
 
    k = gen_k( skey->p, 0 /* no small K ! */ );
529
 
    gcry_mpi_powm( a, skey->g, k, skey->p );
530
 
    mpi_mul(t, skey->x, a );
531
 
    mpi_subm(t, input, t, p_1 );
532
 
    mpi_invm(inv, k, p_1 );
533
 
    mpi_mulm(b, t, inv, p_1 );
534
 
 
535
 
#if 0
536
 
    if( DBG_CIPHER ) 
537
 
      {
538
 
        log_mpidump("elg sign p= ", skey->p);
539
 
        log_mpidump("elg sign g= ", skey->g);
540
 
        log_mpidump("elg sign y= ", skey->y);
541
 
        log_mpidump("elg sign x= ", skey->x);
542
 
        log_mpidump("elg sign k= ", k);
543
 
        log_mpidump("elg sign M= ", input);
544
 
        log_mpidump("elg sign a= ", a);
545
 
        log_mpidump("elg sign b= ", b);
546
 
      }
547
 
#endif
548
 
    mpi_free(k);
549
 
    mpi_free(t);
550
 
    mpi_free(inv);
551
 
    mpi_free(p_1);
552
 
}
553
 
 
554
 
 
555
 
/****************
556
 
 * Returns true if the signature composed of A and B is valid.
557
 
 */
558
 
static int
559
 
verify(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
560
 
{
561
 
  int rc;
562
 
  gcry_mpi_t t1;
563
 
  gcry_mpi_t t2;
564
 
  gcry_mpi_t base[4];
565
 
  gcry_mpi_t ex[4];
566
 
 
567
 
  if( !(mpi_cmp_ui( a, 0 ) > 0 && mpi_cmp( a, pkey->p ) < 0) )
568
 
    return 0; /* assertion      0 < a < p  failed */
569
 
 
570
 
  t1 = mpi_alloc( mpi_get_nlimbs(a) );
571
 
  t2 = mpi_alloc( mpi_get_nlimbs(a) );
572
 
 
573
 
#if 0
574
 
  /* t1 = (y^a mod p) * (a^b mod p) mod p */
575
 
  gcry_mpi_powm( t1, pkey->y, a, pkey->p );
576
 
  gcry_mpi_powm( t2, a, b, pkey->p );
577
 
  mpi_mulm( t1, t1, t2, pkey->p );
578
 
 
579
 
  /* t2 = g ^ input mod p */
580
 
  gcry_mpi_powm( t2, pkey->g, input, pkey->p );
581
 
 
582
 
  rc = !mpi_cmp( t1, t2 );
583
 
#elif 0
584
 
  /* t1 = (y^a mod p) * (a^b mod p) mod p */
585
 
  base[0] = pkey->y; ex[0] = a;
586
 
  base[1] = a;       ex[1] = b;
587
 
  base[2] = NULL;    ex[2] = NULL;
588
 
  mpi_mulpowm( t1, base, ex, pkey->p );
589
 
 
590
 
  /* t2 = g ^ input mod p */
591
 
  gcry_mpi_powm( t2, pkey->g, input, pkey->p );
592
 
 
593
 
  rc = !mpi_cmp( t1, t2 );
594
 
#else
595
 
  /* t1 = g ^ - input * y ^ a * a ^ b  mod p */
596
 
  mpi_invm(t2, pkey->g, pkey->p );
597
 
  base[0] = t2     ; ex[0] = input;
598
 
  base[1] = pkey->y; ex[1] = a;
599
 
  base[2] = a;       ex[2] = b;
600
 
  base[3] = NULL;    ex[3] = NULL;
601
 
  mpi_mulpowm( t1, base, ex, pkey->p );
602
 
  rc = !mpi_cmp_ui( t1, 1 );
603
 
 
604
 
#endif
605
 
 
606
 
  mpi_free(t1);
607
 
  mpi_free(t2);
608
 
  return rc;
609
 
}
610
 
 
611
 
/*********************************************
612
 
 **************  interface  ******************
613
 
 *********************************************/
614
 
 
615
 
static gpg_err_code_t
616
 
elg_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
617
 
                  const gcry_sexp_t genparms,
618
 
                  gcry_mpi_t *skey, gcry_mpi_t **retfactors,
619
 
                  gcry_sexp_t *r_extrainfo)
620
 
{
621
 
  gpg_err_code_t ec;
622
 
  ELG_secret_key sk;
623
 
  gcry_mpi_t xvalue = NULL;
624
 
  gcry_sexp_t l1;
625
 
 
626
 
  (void)algo;
627
 
  (void)evalue;
628
 
  (void)r_extrainfo;
629
 
 
630
 
  if (genparms)
631
 
    {
632
 
      /* Parse the optional xvalue element. */
633
 
      l1 = gcry_sexp_find_token (genparms, "xvalue", 0);
634
 
      if (l1)
635
 
        {
636
 
          xvalue = gcry_sexp_nth_mpi (l1, 1, 0);
637
 
          gcry_sexp_release (l1);
638
 
          if (!xvalue)
639
 
            return GPG_ERR_BAD_MPI;
640
 
        }
641
 
    }
642
 
 
643
 
  if (xvalue)
644
 
    ec = generate_using_x (&sk, nbits, xvalue, retfactors);
645
 
  else
646
 
    {
647
 
      generate (&sk, nbits, retfactors);
648
 
      ec = 0;
649
 
    }
650
 
 
651
 
  skey[0] = sk.p;
652
 
  skey[1] = sk.g;
653
 
  skey[2] = sk.y;
654
 
  skey[3] = sk.x;
655
 
  
656
 
  return ec;
657
 
}
658
 
 
659
 
 
660
 
static gcry_err_code_t
661
 
elg_generate (int algo, unsigned int nbits, unsigned long evalue,
662
 
              gcry_mpi_t *skey, gcry_mpi_t **retfactors)
663
 
{
664
 
  ELG_secret_key sk;
665
 
 
666
 
  (void)algo;
667
 
  (void)evalue;
668
 
 
669
 
  generate (&sk, nbits, retfactors);
670
 
  skey[0] = sk.p;
671
 
  skey[1] = sk.g;
672
 
  skey[2] = sk.y;
673
 
  skey[3] = sk.x;
674
 
  
675
 
  return GPG_ERR_NO_ERROR;
676
 
}
677
 
 
678
 
 
679
 
static gcry_err_code_t
680
 
elg_check_secret_key (int algo, gcry_mpi_t *skey)
681
 
{
682
 
  gcry_err_code_t err = GPG_ERR_NO_ERROR;
683
 
  ELG_secret_key sk;
684
 
 
685
 
  (void)algo;
686
 
 
687
 
  if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]))
688
 
    err = GPG_ERR_BAD_MPI;
689
 
  else
690
 
    {
691
 
      sk.p = skey[0];
692
 
      sk.g = skey[1];
693
 
      sk.y = skey[2];
694
 
      sk.x = skey[3];
695
 
      
696
 
      if (! check_secret_key (&sk))
697
 
        err = GPG_ERR_BAD_SECKEY;
698
 
    }
699
 
 
700
 
  return err;
701
 
}
702
 
 
703
 
 
704
 
static gcry_err_code_t
705
 
elg_encrypt (int algo, gcry_mpi_t *resarr,
706
 
             gcry_mpi_t data, gcry_mpi_t *pkey, int flags)
707
 
{
708
 
  gcry_err_code_t err = GPG_ERR_NO_ERROR;
709
 
  ELG_public_key pk;
710
 
 
711
 
  (void)algo;
712
 
  (void)flags;
713
 
 
714
 
  if ((! data) || (! pkey[0]) || (! pkey[1]) || (! pkey[2]))
715
 
    err = GPG_ERR_BAD_MPI;
716
 
  else
717
 
    {
718
 
      pk.p = pkey[0];
719
 
      pk.g = pkey[1];
720
 
      pk.y = pkey[2];
721
 
      resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.p));
722
 
      resarr[1] = mpi_alloc (mpi_get_nlimbs (pk.p));
723
 
      do_encrypt (resarr[0], resarr[1], data, &pk);
724
 
    }
725
 
  return err;
726
 
}
727
 
 
728
 
 
729
 
static gcry_err_code_t
730
 
elg_decrypt (int algo, gcry_mpi_t *result,
731
 
             gcry_mpi_t *data, gcry_mpi_t *skey, int flags)
732
 
{
733
 
  gcry_err_code_t err = GPG_ERR_NO_ERROR;
734
 
  ELG_secret_key sk;
735
 
 
736
 
  (void)algo;
737
 
  (void)flags;
738
 
 
739
 
  if ((! data[0]) || (! data[1])
740
 
      || (! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]))
741
 
    err = GPG_ERR_BAD_MPI;
742
 
  else
743
 
    {
744
 
      sk.p = skey[0];
745
 
      sk.g = skey[1];
746
 
      sk.y = skey[2];
747
 
      sk.x = skey[3];
748
 
      *result = mpi_alloc_secure (mpi_get_nlimbs (sk.p));
749
 
      decrypt (*result, data[0], data[1], &sk);
750
 
    }
751
 
  return err;
752
 
}
753
 
 
754
 
 
755
 
static gcry_err_code_t
756
 
elg_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
757
 
{
758
 
  gcry_err_code_t err = GPG_ERR_NO_ERROR;
759
 
  ELG_secret_key sk;
760
 
 
761
 
  (void)algo;
762
 
 
763
 
  if ((! data)
764
 
      || (! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]))
765
 
    err = GPG_ERR_BAD_MPI;
766
 
  else
767
 
    {
768
 
      sk.p = skey[0];
769
 
      sk.g = skey[1];
770
 
      sk.y = skey[2];
771
 
      sk.x = skey[3];
772
 
      resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.p));
773
 
      resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.p));
774
 
      sign (resarr[0], resarr[1], data, &sk);
775
 
    }
776
 
  
777
 
  return err;
778
 
}
779
 
 
780
 
 
781
 
static gcry_err_code_t
782
 
elg_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
783
 
            int (*cmp) (void *, gcry_mpi_t), void *opaquev)
784
 
{
785
 
  gcry_err_code_t err = GPG_ERR_NO_ERROR;
786
 
  ELG_public_key pk;
787
 
 
788
 
  (void)algo;
789
 
  (void)cmp;
790
 
  (void)opaquev;
791
 
 
792
 
  if ((! data[0]) || (! data[1]) || (! hash)
793
 
      || (! pkey[0]) || (! pkey[1]) || (! pkey[2]))
794
 
    err = GPG_ERR_BAD_MPI;
795
 
  else
796
 
    {
797
 
      pk.p = pkey[0];
798
 
      pk.g = pkey[1];
799
 
      pk.y = pkey[2];
800
 
      if (! verify (data[0], data[1], hash, &pk))
801
 
        err = GPG_ERR_BAD_SIGNATURE;
802
 
    }
803
 
 
804
 
  return err;
805
 
}
806
 
 
807
 
 
808
 
static unsigned int
809
 
elg_get_nbits (int algo, gcry_mpi_t *pkey)
810
 
{
811
 
  (void)algo;
812
 
 
813
 
  return mpi_get_nbits (pkey[0]);
814
 
}
815
 
 
816
 
 
817
 
static const char *elg_names[] =
818
 
  {
819
 
    "elg",
820
 
    "openpgp-elg",
821
 
    "openpgp-elg-sig",
822
 
    NULL,
823
 
  };
824
 
 
825
 
 
826
 
gcry_pk_spec_t _gcry_pubkey_spec_elg =
827
 
  {
828
 
    "ELG", elg_names,
829
 
    "pgy", "pgyx", "ab", "rs", "pgy",
830
 
    GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR,
831
 
    elg_generate,
832
 
    elg_check_secret_key,
833
 
    elg_encrypt,
834
 
    elg_decrypt,
835
 
    elg_sign,
836
 
    elg_verify,
837
 
    elg_get_nbits
838
 
  };
839
 
 
840
 
pk_extra_spec_t _gcry_pubkey_extraspec_elg = 
841
 
  {
842
 
    NULL,
843
 
    elg_generate_ext,
844
 
    NULL
845
 
  };
846