Remove macro hacks for internal vs. external functions. Part 1.
[libgcrypt.git] / cipher / rsa-common.c
1 /* rsa-common.c - Supporting functions for RSA
2  * Copyright (C) 2011 Free Software Foundation, Inc.
3  * Copyright (C) 2013  g10 Code GmbH
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
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "g10lib.h"
27 #include "mpi.h"
28 #include "cipher.h"
29 #include "pubkey-internal.h"
30
31
32 /* Turn VALUE into an octet string and store it in an allocated buffer
33    at R_FRAME or - if R_RAME is NULL - copy it into the caller
34    provided buffer SPACE; either SPACE or R_FRAME may be used.  If
35    SPACE if not NULL, the caller must provide a buffer of at least
36    NBYTES.  If the resulting octet string is shorter than NBYTES pad
37    it to the left with zeroes.  If VALUE does not fit into NBYTES
38    return an error code.  */
39 static gpg_err_code_t
40 octet_string_from_mpi (unsigned char **r_frame, void *space,
41                        gcry_mpi_t value, size_t nbytes)
42 {
43   return _gcry_mpi_to_octet_string (r_frame, space, value, nbytes);
44 }
45
46
47
48 /* Encode {VALUE,VALUELEN} for an NBITS keys using the pkcs#1 block
49    type 2 padding.  On sucess the result is stored as a new MPI at
50    R_RESULT.  On error the value at R_RESULT is undefined.
51
52    If {RANDOM_OVERRIDE, RANDOM_OVERRIDE_LEN} is given it is used as
53    the seed instead of using a random string for it.  This feature is
54    only useful for regression tests.  Note that this value may not
55    contain zero bytes.
56
57    We encode the value in this way:
58
59      0  2  RND(n bytes)  0  VALUE
60
61    0   is a marker we unfortunately can't encode because we return an
62        MPI which strips all leading zeroes.
63    2   is the block type.
64    RND are non-zero random bytes.
65
66    (Note that OpenPGP includes the cipher algorithm and a checksum in
67    VALUE; the caller needs to prepare the value accordingly.)
68   */
69 gpg_err_code_t
70 _gcry_rsa_pkcs1_encode_for_enc (gcry_mpi_t *r_result, unsigned int nbits,
71                                 const unsigned char *value, size_t valuelen,
72                                 const unsigned char *random_override,
73                                 size_t random_override_len)
74 {
75   gcry_err_code_t rc = 0;
76   unsigned char *frame = NULL;
77   size_t nframe = (nbits+7) / 8;
78   int i;
79   size_t n;
80   unsigned char *p;
81
82   if (valuelen + 7 > nframe || !nframe)
83     {
84       /* Can't encode a VALUELEN value in a NFRAME bytes frame.  */
85       return GPG_ERR_TOO_SHORT; /* The key is too short.  */
86     }
87
88   if ( !(frame = gcry_malloc_secure (nframe)))
89     return gpg_err_code_from_syserror ();
90
91   n = 0;
92   frame[n++] = 0;
93   frame[n++] = 2; /* block type */
94   i = nframe - 3 - valuelen;
95   gcry_assert (i > 0);
96
97   if (random_override)
98     {
99       int j;
100
101       if (random_override_len != i)
102         {
103           gcry_free (frame);
104           return GPG_ERR_INV_ARG;
105         }
106       /* Check that random does not include a zero byte.  */
107       for (j=0; j < random_override_len; j++)
108         if (!random_override[j])
109           {
110             gcry_free (frame);
111             return GPG_ERR_INV_ARG;
112           }
113       memcpy (frame + n, random_override, random_override_len);
114       n += random_override_len;
115     }
116   else
117     {
118       p = _gcry_random_bytes_secure (i, GCRY_STRONG_RANDOM);
119       /* Replace zero bytes by new values. */
120       for (;;)
121         {
122           int j, k;
123           unsigned char *pp;
124
125           /* Count the zero bytes. */
126           for (j=k=0; j < i; j++)
127             {
128               if (!p[j])
129                 k++;
130             }
131           if (!k)
132             break; /* Okay: no (more) zero bytes. */
133
134           k += k/128 + 3; /* Better get some more. */
135           pp = _gcry_random_bytes_secure (k, GCRY_STRONG_RANDOM);
136           for (j=0; j < i && k; )
137             {
138               if (!p[j])
139                 p[j] = pp[--k];
140               if (p[j])
141                 j++;
142             }
143           gcry_free (pp);
144         }
145       memcpy (frame+n, p, i);
146       n += i;
147       gcry_free (p);
148     }
149
150   frame[n++] = 0;
151   memcpy (frame+n, value, valuelen);
152   n += valuelen;
153   gcry_assert (n == nframe);
154
155   rc = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, n, &nframe);
156   if (!rc &&DBG_CIPHER)
157     log_mpidump ("PKCS#1 block type 2 encoded data", *r_result);
158   gcry_free (frame);
159
160   return rc;
161 }
162
163
164 /* Decode a plaintext in VALUE assuming pkcs#1 block type 2 padding.
165    NBITS is the size of the secret key.  On success the result is
166    stored as a newly allocated buffer at R_RESULT and its valid length at
167    R_RESULTLEN.  On error NULL is stored at R_RESULT.  */
168 gpg_err_code_t
169 _gcry_rsa_pkcs1_decode_for_enc (unsigned char **r_result, size_t *r_resultlen,
170                                 unsigned int nbits, gcry_mpi_t value)
171 {
172   gcry_error_t err;
173   unsigned char *frame = NULL;
174   size_t nframe = (nbits+7) / 8;
175   size_t n;
176
177   *r_result = NULL;
178
179   if ( !(frame = gcry_malloc_secure (nframe)))
180     return gpg_err_code_from_syserror ();
181
182   err = _gcry_mpi_print (GCRYMPI_FMT_USG, frame, nframe, &n, value);
183   if (err)
184     {
185       gcry_free (frame);
186       return gcry_err_code (err);
187     }
188
189   nframe = n; /* Set NFRAME to the actual length.  */
190
191   /* FRAME = 0x00 || 0x02 || PS || 0x00 || M
192
193      pkcs#1 requires that the first byte is zero.  Our MPIs usually
194      strip leading zero bytes; thus we are not able to detect them.
195      However due to the way gcry_mpi_print is implemented we may see
196      leading zero bytes nevertheless.  We handle this by making the
197      first zero byte optional.  */
198   if (nframe < 4)
199     {
200       gcry_free (frame);
201       return GPG_ERR_ENCODING_PROBLEM;  /* Too short.  */
202     }
203   n = 0;
204   if (!frame[0])
205     n++;
206   if (frame[n++] != 0x02)
207     {
208       gcry_free (frame);
209       return GPG_ERR_ENCODING_PROBLEM;  /* Wrong block type.  */
210     }
211
212   /* Skip the non-zero random bytes and the terminating zero byte.  */
213   for (; n < nframe && frame[n] != 0x00; n++)
214     ;
215   if (n+1 >= nframe)
216     {
217       gcry_free (frame);
218       return GPG_ERR_ENCODING_PROBLEM; /* No zero byte.  */
219     }
220   n++; /* Skip the zero byte.  */
221
222   /* To avoid an extra allocation we reuse the frame buffer.  The only
223      caller of this function will anyway free the result soon.  */
224   memmove (frame, frame + n, nframe - n);
225   *r_result = frame;
226   *r_resultlen = nframe - n;
227
228   if (DBG_CIPHER)
229     log_printhex ("value extracted from PKCS#1 block type 2 encoded data",
230                   *r_result, *r_resultlen);
231
232   return 0;
233 }
234
235
236 /* Encode {VALUE,VALUELEN} for an NBITS keys and hash algorith ALGO
237    using the pkcs#1 block type 1 padding.  On success the result is
238    stored as a new MPI at R_RESULT.  On error the value at R_RESULT is
239    undefined.
240
241    We encode the value in this way:
242
243      0  1  PAD(n bytes)  0  ASN(asnlen bytes) VALUE(valuelen bytes)
244
245    0   is a marker we unfortunately can't encode because we return an
246        MPI which strips all leading zeroes.
247    1   is the block type.
248    PAD consists of 0xff bytes.
249    0   marks the end of the padding.
250    ASN is the DER encoding of the hash algorithm; along with the VALUE
251        it yields a valid DER encoding.
252
253    (Note that PGP prior to version 2.3 encoded the message digest as:
254       0   1   MD(16 bytes)   0   PAD(n bytes)   1
255     The MD is always 16 bytes here because it's always MD5.  GnuPG
256     does not not support pre-v2.3 signatures, but I'm including this
257     comment so the information is easily found if needed.)
258 */
259 gpg_err_code_t
260 _gcry_rsa_pkcs1_encode_for_sig (gcry_mpi_t *r_result, unsigned int nbits,
261                                 const unsigned char *value, size_t valuelen,
262                                 int algo)
263 {
264   gcry_err_code_t rc = 0;
265   byte asn[100];
266   byte *frame = NULL;
267   size_t nframe = (nbits+7) / 8;
268   int i;
269   size_t n;
270   size_t asnlen, dlen;
271
272   asnlen = DIM(asn);
273   dlen = _gcry_md_get_algo_dlen (algo);
274
275   if (_gcry_md_algo_info (algo, GCRYCTL_GET_ASNOID, asn, &asnlen))
276     {
277       /* We don't have yet all of the above algorithms.  */
278       return GPG_ERR_NOT_IMPLEMENTED;
279     }
280
281   if ( valuelen != dlen )
282     {
283       /* Hash value does not match the length of digest for
284          the given algorithm.  */
285       return GPG_ERR_CONFLICT;
286     }
287
288   if ( !dlen || dlen + asnlen + 4 > nframe)
289     {
290       /* Can't encode an DLEN byte digest MD into an NFRAME byte
291          frame.  */
292       return GPG_ERR_TOO_SHORT;
293     }
294
295   if ( !(frame = gcry_malloc (nframe)) )
296     return gpg_err_code_from_syserror ();
297
298   /* Assemble the pkcs#1 block type 1. */
299   n = 0;
300   frame[n++] = 0;
301   frame[n++] = 1; /* block type */
302   i = nframe - valuelen - asnlen - 3 ;
303   gcry_assert (i > 1);
304   memset (frame+n, 0xff, i );
305   n += i;
306   frame[n++] = 0;
307   memcpy (frame+n, asn, asnlen);
308   n += asnlen;
309   memcpy (frame+n, value, valuelen );
310   n += valuelen;
311   gcry_assert (n == nframe);
312
313   /* Convert it into an MPI. */
314   rc = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, n, &nframe);
315   if (!rc && DBG_CIPHER)
316     log_mpidump ("PKCS#1 block type 1 encoded data", *r_result);
317   gcry_free (frame);
318
319   return rc;
320 }
321
322
323 /* Mask generation function for OAEP.  See RFC-3447 B.2.1.  */
324 static gcry_err_code_t
325 mgf1 (unsigned char *output, size_t outlen, unsigned char *seed, size_t seedlen,
326       int algo)
327 {
328   size_t dlen, nbytes, n;
329   int idx;
330   gcry_md_hd_t hd;
331   gcry_error_t err;
332
333   err = _gcry_md_open (&hd, algo, 0);
334   if (err)
335     return err;
336
337   dlen = _gcry_md_get_algo_dlen (algo);
338
339   /* We skip step 1 which would be assert(OUTLEN <= 2^32).  The loop
340      in step 3 is merged with step 4 by concatenating no more octets
341      than what would fit into OUTPUT.  The ceiling for the counter IDX
342      is implemented indirectly.  */
343   nbytes = 0;  /* Step 2.  */
344   idx = 0;
345   while ( nbytes < outlen )
346     {
347       unsigned char c[4], *digest;
348
349       if (idx)
350         _gcry_md_reset (hd);
351
352       c[0] = (idx >> 24) & 0xFF;
353       c[1] = (idx >> 16) & 0xFF;
354       c[2] = (idx >> 8) & 0xFF;
355       c[3] = idx & 0xFF;
356       idx++;
357
358       _gcry_md_write (hd, seed, seedlen);
359       _gcry_md_write (hd, c, 4);
360       digest = _gcry_md_read (hd, 0);
361
362       n = (outlen - nbytes < dlen)? (outlen - nbytes) : dlen;
363       memcpy (output+nbytes, digest, n);
364       nbytes += n;
365     }
366
367   _gcry_md_close (hd);
368   return GPG_ERR_NO_ERROR;
369 }
370
371
372 /* RFC-3447 (pkcs#1 v2.1) OAEP encoding.  NBITS is the length of the
373    key measured in bits.  ALGO is the hash function; it must be a
374    valid and usable algorithm.  {VALUE,VALUELEN} is the message to
375    encrypt.  {LABEL,LABELLEN} is the optional label to be associated
376    with the message, if LABEL is NULL the default is to use the empty
377    string as label.  On success the encoded ciphertext is returned at
378    R_RESULT.
379
380    If {RANDOM_OVERRIDE, RANDOM_OVERRIDE_LEN} is given it is used as
381    the seed instead of using a random string for it.  This feature is
382    only useful for regression tests.
383
384    Here is figure 1 from the RFC depicting the process:
385
386                              +----------+---------+-------+
387                         DB = |  lHash   |    PS   |   M   |
388                              +----------+---------+-------+
389                                             |
390                   +----------+              V
391                   |   seed   |--> MGF ---> xor
392                   +----------+              |
393                         |                   |
394                +--+     V                   |
395                |00|    xor <----- MGF <-----|
396                +--+     |                   |
397                  |      |                   |
398                  V      V                   V
399                +--+----------+----------------------------+
400          EM =  |00|maskedSeed|          maskedDB          |
401                +--+----------+----------------------------+
402   */
403 gpg_err_code_t
404 _gcry_rsa_oaep_encode (gcry_mpi_t *r_result, unsigned int nbits, int algo,
405                        const unsigned char *value, size_t valuelen,
406                        const unsigned char *label, size_t labellen,
407                        const void *random_override, size_t random_override_len)
408 {
409   gcry_err_code_t rc = 0;
410   unsigned char *frame = NULL;
411   size_t nframe = (nbits+7) / 8;
412   unsigned char *p;
413   size_t hlen;
414   size_t n;
415
416   *r_result = NULL;
417
418   /* Set defaults for LABEL.  */
419   if (!label || !labellen)
420     {
421       label = (const unsigned char*)"";
422       labellen = 0;
423     }
424
425   hlen = _gcry_md_get_algo_dlen (algo);
426
427   /* We skip step 1a which would be to check that LABELLEN is not
428      greater than 2^61-1.  See rfc-3447 7.1.1. */
429
430   /* Step 1b.  Note that the obsolete rfc-2437 uses the check:
431      valuelen > nframe - 2 * hlen - 1 .  */
432   if (valuelen > nframe - 2 * hlen - 2 || !nframe)
433     {
434       /* Can't encode a VALUELEN value in a NFRAME bytes frame. */
435       return GPG_ERR_TOO_SHORT; /* The key is too short.  */
436     }
437
438   /* Allocate the frame.  */
439   frame = gcry_calloc_secure (1, nframe);
440   if (!frame)
441     return gpg_err_code_from_syserror ();
442
443   /* Step 2a: Compute the hash of the label.  We store it in the frame
444      where later the maskedDB will commence.  */
445   _gcry_md_hash_buffer (algo, frame + 1 + hlen, label, labellen);
446
447   /* Step 2b: Set octet string to zero.  */
448   /* This has already been done while allocating FRAME.  */
449
450   /* Step 2c: Create DB by concatenating lHash, PS, 0x01 and M.  */
451   n = nframe - valuelen - 1;
452   frame[n] = 0x01;
453   memcpy (frame + n + 1, value, valuelen);
454
455   /* Step 3d: Generate seed.  We store it where the maskedSeed will go
456      later. */
457   if (random_override)
458     {
459       if (random_override_len != hlen)
460         {
461           gcry_free (frame);
462           return GPG_ERR_INV_ARG;
463         }
464       memcpy (frame + 1, random_override, hlen);
465     }
466   else
467     _gcry_randomize (frame + 1, hlen, GCRY_STRONG_RANDOM);
468
469   /* Step 2e and 2f: Create maskedDB.  */
470   {
471     unsigned char *dmask;
472
473     dmask = gcry_malloc_secure (nframe - hlen - 1);
474     if (!dmask)
475       {
476         rc = gpg_err_code_from_syserror ();
477         gcry_free (frame);
478         return rc;
479       }
480     rc = mgf1 (dmask, nframe - hlen - 1, frame+1, hlen, algo);
481     if (rc)
482       {
483         gcry_free (dmask);
484         gcry_free (frame);
485         return rc;
486       }
487     for (n = 1 + hlen, p = dmask; n < nframe; n++)
488       frame[n] ^= *p++;
489     gcry_free (dmask);
490   }
491
492   /* Step 2g and 2h: Create maskedSeed.  */
493   {
494     unsigned char *smask;
495
496     smask = gcry_malloc_secure (hlen);
497     if (!smask)
498       {
499         rc = gpg_err_code_from_syserror ();
500         gcry_free (frame);
501         return rc;
502       }
503     rc = mgf1 (smask, hlen, frame + 1 + hlen, nframe - hlen - 1, algo);
504     if (rc)
505       {
506         gcry_free (smask);
507         gcry_free (frame);
508         return rc;
509       }
510     for (n = 1, p = smask; n < 1 + hlen; n++)
511       frame[n] ^= *p++;
512     gcry_free (smask);
513   }
514
515   /* Step 2i: Concatenate 0x00, maskedSeed and maskedDB.  */
516   /* This has already been done by using in-place operations.  */
517
518   /* Convert the stuff into an MPI as expected by the caller.  */
519   rc = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, nframe, NULL);
520   if (!rc && DBG_CIPHER)
521     log_mpidump ("OAEP encoded data", *r_result);
522   gcry_free (frame);
523
524   return rc;
525 }
526
527
528 /* RFC-3447 (pkcs#1 v2.1) OAEP decoding.  NBITS is the length of the
529    key measured in bits.  ALGO is the hash function; it must be a
530    valid and usable algorithm.  VALUE is the raw decrypted message
531    {LABEL,LABELLEN} is the optional label to be associated with the
532    message, if LABEL is NULL the default is to use the empty string as
533    label.  On success the plaintext is returned as a newly allocated
534    buffer at R_RESULT; its valid length is stored at R_RESULTLEN.  On
535    error NULL is stored at R_RESULT.  */
536 gpg_err_code_t
537 _gcry_rsa_oaep_decode (unsigned char **r_result, size_t *r_resultlen,
538                        unsigned int nbits, int algo,
539                        gcry_mpi_t value,
540                        const unsigned char *label, size_t labellen)
541 {
542   gcry_err_code_t rc;
543   unsigned char *frame = NULL; /* Encoded messages (EM).  */
544   unsigned char *masked_seed;  /* Points into FRAME.  */
545   unsigned char *masked_db;    /* Points into FRAME.  */
546   unsigned char *seed = NULL;  /* Allocated space for the seed and DB.  */
547   unsigned char *db;           /* Points into SEED.  */
548   unsigned char *lhash = NULL; /* Hash of the label.  */
549   size_t nframe;               /* Length of the ciphertext (EM).  */
550   size_t hlen;                 /* Length of the hash digest.  */
551   size_t db_len;               /* Length of DB and masked_db.  */
552   size_t nkey = (nbits+7)/8;   /* Length of the key in bytes.  */
553   int failed = 0;              /* Error indicator.  */
554   size_t n;
555
556   *r_result = NULL;
557
558   /* This code is implemented as described by rfc-3447 7.1.2.  */
559
560   /* Set defaults for LABEL.  */
561   if (!label || !labellen)
562     {
563       label = (const unsigned char*)"";
564       labellen = 0;
565     }
566
567   /* Get the length of the digest.  */
568   hlen = _gcry_md_get_algo_dlen (algo);
569
570   /* Hash the label right away.  */
571   lhash = gcry_malloc (hlen);
572   if (!lhash)
573     return gpg_err_code_from_syserror ();
574   _gcry_md_hash_buffer (algo, lhash, label, labellen);
575
576   /* Turn the MPI into an octet string.  If the octet string is
577      shorter than the key we pad it to the left with zeroes.  This may
578      happen due to the leading zero in OAEP frames and due to the
579      following random octets (seed^mask) which may have leading zero
580      bytes.  This all is needed to cope with our leading zeroes
581      suppressing MPI implementation.  The code implictly implements
582      Step 1b (bail out if NFRAME != N).  */
583   rc = octet_string_from_mpi (&frame, NULL, value, nkey);
584   if (rc)
585     {
586       gcry_free (lhash);
587       return GPG_ERR_ENCODING_PROBLEM;
588     }
589   nframe = nkey;
590
591   /* Step 1c: Check that the key is long enough.  */
592   if ( nframe < 2 * hlen + 2 )
593     {
594       gcry_free (frame);
595       gcry_free (lhash);
596       return GPG_ERR_ENCODING_PROBLEM;
597     }
598
599   /* Step 2 has already been done by the caller and the
600      gcry_mpi_aprint above.  */
601
602   /* Allocate space for SEED and DB.  */
603   seed = gcry_malloc_secure (nframe - 1);
604   if (!seed)
605     {
606       rc = gpg_err_code_from_syserror ();
607       gcry_free (frame);
608       gcry_free (lhash);
609       return rc;
610     }
611   db = seed + hlen;
612
613   /* To avoid choosen ciphertext attacks from now on we make sure to
614      run all code even in the error case; this avoids possible timing
615      attacks as described by Manger.  */
616
617   /* Step 3a: Hash the label.  */
618   /* This has already been done.  */
619
620   /* Step 3b: Separate the encoded message.  */
621   masked_seed = frame + 1;
622   masked_db   = frame + 1 + hlen;
623   db_len      = nframe - 1 - hlen;
624
625   /* Step 3c and 3d: seed = maskedSeed ^ mgf(maskedDB, hlen).  */
626   if (mgf1 (seed, hlen, masked_db, db_len, algo))
627     failed = 1;
628   for (n = 0; n < hlen; n++)
629     seed[n] ^= masked_seed[n];
630
631   /* Step 3e and 3f: db = maskedDB ^ mgf(seed, db_len).  */
632   if (mgf1 (db, db_len, seed, hlen, algo))
633     failed = 1;
634   for (n = 0; n < db_len; n++)
635     db[n] ^= masked_db[n];
636
637   /* Step 3g: Check lhash, an possible empty padding string terminated
638      by 0x01 and the first byte of EM being 0.  */
639   if (memcmp (lhash, db, hlen))
640     failed = 1;
641   for (n = hlen; n < db_len; n++)
642     if (db[n] == 0x01)
643       break;
644   if (n == db_len)
645     failed = 1;
646   if (frame[0])
647     failed = 1;
648
649   gcry_free (lhash);
650   gcry_free (frame);
651   if (failed)
652     {
653       gcry_free (seed);
654       return GPG_ERR_ENCODING_PROBLEM;
655     }
656
657   /* Step 4: Output M.  */
658   /* To avoid an extra allocation we reuse the seed buffer.  The only
659      caller of this function will anyway free the result soon.  */
660   n++;
661   memmove (seed, db + n, db_len - n);
662   *r_result = seed;
663   *r_resultlen = db_len - n;
664   seed = NULL;
665
666   if (DBG_CIPHER)
667     log_printhex ("value extracted from OAEP encoded data",
668                   *r_result, *r_resultlen);
669
670   return 0;
671 }
672
673
674 /* RFC-3447 (pkcs#1 v2.1) PSS encoding.  Encode {VALUE,VALUELEN} for
675    an NBITS key.  Note that VALUE is already the mHash from the
676    picture below.  ALGO is a valid hash algorithm and SALTLEN is the
677    length of salt to be used.  On success the result is stored as a
678    new MPI at R_RESULT.  On error the value at R_RESULT is undefined.
679
680    If {RANDOM_OVERRIDE, RANDOM_OVERRIDE_LEN} is given it is used as
681    the salt instead of using a random string for the salt.  This
682    feature is only useful for regression tests.
683
684    Here is figure 2 from the RFC (errata 595 applied) depicting the
685    process:
686
687                                   +-----------+
688                                   |     M     |
689                                   +-----------+
690                                         |
691                                         V
692                                       Hash
693                                         |
694                                         V
695                           +--------+----------+----------+
696                      M' = |Padding1|  mHash   |   salt   |
697                           +--------+----------+----------+
698                                          |
699                +--------+----------+     V
700          DB =  |Padding2| salt     |   Hash
701                +--------+----------+     |
702                          |               |
703                          V               |    +----+
704                         xor <--- MGF <---|    |0xbc|
705                          |               |    +----+
706                          |               |      |
707                          V               V      V
708                +-------------------+----------+----+
709          EM =  |    maskedDB       |     H    |0xbc|
710                +-------------------+----------+----+
711
712   */
713 gpg_err_code_t
714 _gcry_rsa_pss_encode (gcry_mpi_t *r_result, unsigned int nbits, int algo,
715                       const unsigned char *value, size_t valuelen, int saltlen,
716                       const void *random_override, size_t random_override_len)
717 {
718   gcry_err_code_t rc = 0;
719   size_t hlen;                 /* Length of the hash digest.  */
720   unsigned char *em = NULL;    /* Encoded message.  */
721   size_t emlen = (nbits+7)/8;  /* Length in bytes of EM.  */
722   unsigned char *h;            /* Points into EM.  */
723   unsigned char *buf = NULL;   /* Help buffer.  */
724   size_t buflen;               /* Length of BUF.  */
725   unsigned char *mhash;        /* Points into BUF.  */
726   unsigned char *salt;         /* Points into BUF.  */
727   unsigned char *dbmask;       /* Points into BUF.  */
728   unsigned char *p;
729   size_t n;
730
731   /* This code is implemented as described by rfc-3447 9.1.1.  */
732
733   /* Get the length of the digest.  */
734   hlen = _gcry_md_get_algo_dlen (algo);
735   gcry_assert (hlen);  /* We expect a valid ALGO here.  */
736
737   /* Allocate a help buffer and setup some pointers.  */
738   buflen = 8 + hlen + saltlen + (emlen - hlen - 1);
739   buf = gcry_malloc (buflen);
740   if (!buf)
741     {
742       rc = gpg_err_code_from_syserror ();
743       goto leave;
744     }
745   mhash = buf + 8;
746   salt  = mhash + hlen;
747   dbmask= salt + saltlen;
748
749   /* Step 2: That would be: mHash = Hash(M) but our input is already
750      mHash thus we do only a consistency check and copy to MHASH.  */
751   if (valuelen != hlen)
752     {
753       rc = GPG_ERR_INV_LENGTH;
754       goto leave;
755     }
756   memcpy (mhash, value, hlen);
757
758   /* Step 3: Check length constraints.  */
759   if (emlen < hlen + saltlen + 2)
760     {
761       rc = GPG_ERR_TOO_SHORT;
762       goto leave;
763     }
764
765   /* Allocate space for EM.  */
766   em = gcry_malloc (emlen);
767   if (!em)
768     {
769       rc = gpg_err_code_from_syserror ();
770       goto leave;
771     }
772   h = em + emlen - 1 - hlen;
773
774   /* Step 4: Create a salt.  */
775   if (saltlen)
776     {
777       if (random_override)
778         {
779           if (random_override_len != saltlen)
780             {
781               rc = GPG_ERR_INV_ARG;
782               goto leave;
783             }
784           memcpy (salt, random_override, saltlen);
785         }
786       else
787         _gcry_randomize (salt, saltlen, GCRY_STRONG_RANDOM);
788     }
789
790   /* Step 5 and 6: M' = Hash(Padding1 || mHash || salt).  */
791   memset (buf, 0, 8);  /* Padding.  */
792   _gcry_md_hash_buffer (algo, h, buf, 8 + hlen + saltlen);
793
794   /* Step 7 and 8: DB = PS || 0x01 || salt.  */
795   /* Note that we use EM to store DB and later Xor in-place.  */
796   p = em + emlen - 1 - hlen - saltlen - 1;
797   memset (em, 0, p - em);
798   *p++ = 0x01;
799   memcpy (p, salt, saltlen);
800
801   /* Step 9: dbmask = MGF(H, emlen - hlen - 1).  */
802   mgf1 (dbmask, emlen - hlen - 1, h, hlen, algo);
803
804   /* Step 10: maskedDB = DB ^ dbMask */
805   for (n = 0, p = dbmask; n < emlen - hlen - 1; n++, p++)
806     em[n] ^= *p;
807
808   /* Step 11: Set the leftmost bits to zero.  */
809   em[0] &= 0xFF >> (8 * emlen - nbits);
810
811   /* Step 12: EM = maskedDB || H || 0xbc.  */
812   em[emlen-1] = 0xbc;
813
814   /* Convert EM into an MPI.  */
815   rc = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, em, emlen, NULL);
816   if (!rc && DBG_CIPHER)
817     log_mpidump ("PSS encoded data", *r_result);
818
819  leave:
820   if (em)
821     {
822       wipememory (em, emlen);
823       gcry_free (em);
824     }
825   if (buf)
826     {
827       wipememory (buf, buflen);
828       gcry_free (buf);
829     }
830   return rc;
831 }
832
833
834 /* Verify a signature assuming PSS padding.  VALUE is the hash of the
835    message (mHash) encoded as an MPI; its length must match the digest
836    length of ALGO.  ENCODED is the output of the RSA public key
837    function (EM).  NBITS is the size of the public key.  ALGO is the
838    hash algorithm and SALTLEN is the length of the used salt.  The
839    function returns 0 on success or on error code.  */
840 gpg_err_code_t
841 _gcry_rsa_pss_verify (gcry_mpi_t value, gcry_mpi_t encoded,
842                       unsigned int nbits, int algo, size_t saltlen)
843 {
844   gcry_err_code_t rc = 0;
845   size_t hlen;                 /* Length of the hash digest.  */
846   unsigned char *em = NULL;    /* Encoded message.  */
847   size_t emlen = (nbits+7)/8;  /* Length in bytes of EM.  */
848   unsigned char *salt;         /* Points into EM.  */
849   unsigned char *h;            /* Points into EM.  */
850   unsigned char *buf = NULL;   /* Help buffer.  */
851   size_t buflen;               /* Length of BUF.  */
852   unsigned char *dbmask;       /* Points into BUF.  */
853   unsigned char *mhash;        /* Points into BUF.  */
854   unsigned char *p;
855   size_t n;
856
857   /* This code is implemented as described by rfc-3447 9.1.2.  */
858
859   /* Get the length of the digest.  */
860   hlen = _gcry_md_get_algo_dlen (algo);
861   gcry_assert (hlen);  /* We expect a valid ALGO here.  */
862
863   /* Allocate a help buffer and setup some pointers.
864      This buffer is used for two purposes:
865         +------------------------------+-------+
866      1. | dbmask                       | mHash |
867         +------------------------------+-------+
868            emlen - hlen - 1              hlen
869
870         +----------+-------+---------+-+-------+
871      2. | padding1 | mHash | salt    | | mHash |
872         +----------+-------+---------+-+-------+
873              8       hlen    saltlen     hlen
874   */
875   buflen = 8 + hlen + saltlen;
876   if (buflen < emlen - hlen - 1)
877     buflen = emlen - hlen - 1;
878   buflen += hlen;
879   buf = gcry_malloc (buflen);
880   if (!buf)
881     {
882       rc = gpg_err_code_from_syserror ();
883       goto leave;
884     }
885   dbmask = buf;
886   mhash = buf + buflen - hlen;
887
888   /* Step 2: That would be: mHash = Hash(M) but our input is already
889      mHash thus we only need to convert VALUE into MHASH.  */
890   rc = octet_string_from_mpi (NULL, mhash, value, hlen);
891   if (rc)
892     goto leave;
893
894   /* Convert the signature into an octet string.  */
895   rc = octet_string_from_mpi (&em, NULL, encoded, emlen);
896   if (rc)
897     goto leave;
898
899   /* Step 3: Check length of EM.  Because we internally use MPI
900      functions we can't do this properly; EMLEN is always the length
901      of the key because octet_string_from_mpi needs to left pad the
902      result with zero to cope with the fact that our MPIs suppress all
903      leading zeroes.  Thus what we test here are merely the digest and
904      salt lengths to the key.  */
905   if (emlen < hlen + saltlen + 2)
906     {
907       rc = GPG_ERR_TOO_SHORT; /* For the hash and saltlen.  */
908       goto leave;
909     }
910
911   /* Step 4: Check last octet.  */
912   if (em[emlen - 1] != 0xbc)
913     {
914       rc = GPG_ERR_BAD_SIGNATURE;
915       goto leave;
916     }
917
918   /* Step 5: Split EM.  */
919   h = em + emlen - 1 - hlen;
920
921   /* Step 6: Check the leftmost bits.  */
922   if ((em[0] & ~(0xFF >> (8 * emlen - nbits))))
923     {
924       rc = GPG_ERR_BAD_SIGNATURE;
925       goto leave;
926     }
927
928   /* Step 7: dbmask = MGF(H, emlen - hlen - 1).  */
929   mgf1 (dbmask, emlen - hlen - 1, h, hlen, algo);
930
931   /* Step 8: maskedDB = DB ^ dbMask.  */
932   for (n = 0, p = dbmask; n < emlen - hlen - 1; n++, p++)
933     em[n] ^= *p;
934
935   /* Step 9: Set leftmost bits in DB to zero.  */
936   em[0] &= 0xFF >> (8 * emlen - nbits);
937
938   /* Step 10: Check the padding of DB.  */
939   for (n = 0; n < emlen - hlen - saltlen - 2 && !em[n]; n++)
940     ;
941   if (n != emlen - hlen - saltlen - 2 || em[n++] != 1)
942     {
943       rc = GPG_ERR_BAD_SIGNATURE;
944       goto leave;
945     }
946
947   /* Step 11: Extract salt from DB.  */
948   salt = em + n;
949
950   /* Step 12:  M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt */
951   memset (buf, 0, 8);
952   memcpy (buf+8, mhash, hlen);
953   memcpy (buf+8+hlen, salt, saltlen);
954
955   /* Step 13:  H' = Hash(M').  */
956   _gcry_md_hash_buffer (algo, buf, buf, 8 + hlen + saltlen);
957
958   /* Step 14:  Check H == H'.   */
959   rc = memcmp (h, buf, hlen) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
960
961  leave:
962   if (em)
963     {
964       wipememory (em, emlen);
965       gcry_free (em);
966     }
967   if (buf)
968     {
969       wipememory (buf, buflen);
970       gcry_free (buf);
971     }
972   return rc;
973 }