rsa.h

   1 /* rsa.h
   2
   3    The RSA publickey algorithm.
   4
   5    Copyright (C) 2001, 2002 Niels Möller
   6
   7    This file is part of GNU Nettle.
   8
   9    GNU Nettle is free software: you can redistribute it and/or
  10    modify it under the terms of either:
  11
  12      * the GNU Lesser General Public License as published by the Free
  13        Software Foundation; either version 3 of the License, or (at your
  14        option) any later version.
  15
  16    or
  17
  18      * the GNU General Public License as published by the Free
  19        Software Foundation; either version 2 of the License, or (at your
  20        option) any later version.
  21
  22    or both in parallel, as here.
  23
  24    GNU Nettle is distributed in the hope that it will be useful,
  25    but WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  27    General Public License for more details.
  28
  29    You should have received copies of the GNU General Public License and
  30    the GNU Lesser General Public License along with this program.  If
  31    not, see http://www.gnu.org/licenses/.
  32 */
  33
  34 #ifndef NETTLE_RSA_H_INCLUDED
  35 #define NETTLE_RSA_H_INCLUDED
  36
  37 #include "nettle-types.h"
  38 #include "bignum.h"
  39
  40 #include "md5.h"
  41 #include "sha1.h"
  42 #include "sha2.h"
  43
  44 #ifdef __cplusplus
  45 extern "C" {
  46 #endif
  47
  48 /* Name mangling */
  49 #define rsa_public_key_init nettle_rsa_public_key_init
  50 #define rsa_public_key_clear nettle_rsa_public_key_clear
  51 #define rsa_public_key_prepare nettle_rsa_public_key_prepare
  52 #define rsa_private_key_init nettle_rsa_private_key_init
  53 #define rsa_private_key_clear nettle_rsa_private_key_clear
  54 #define rsa_private_key_prepare nettle_rsa_private_key_prepare
  55 #define rsa_pkcs1_verify nettle_rsa_pkcs1_verify
  56 #define rsa_pkcs1_sign nettle_rsa_pkcs1_sign
  57 #define rsa_pkcs1_sign_tr nettle_rsa_pkcs1_sign_tr
  58 #define rsa_md5_sign nettle_rsa_md5_sign
  59 #define rsa_md5_sign_tr nettle_rsa_md5_sign_tr
  60 #define rsa_md5_verify nettle_rsa_md5_verify
  61 #define rsa_sha1_sign nettle_rsa_sha1_sign
  62 #define rsa_sha1_sign_tr nettle_rsa_sha1_sign_tr
  63 #define rsa_sha1_verify nettle_rsa_sha1_verify
  64 #define rsa_sha256_sign nettle_rsa_sha256_sign
  65 #define rsa_sha256_sign_tr nettle_rsa_sha256_sign_tr
  66 #define rsa_sha256_verify nettle_rsa_sha256_verify
  67 #define rsa_sha512_sign nettle_rsa_sha512_sign
  68 #define rsa_sha512_sign_tr nettle_rsa_sha512_sign_tr
  69 #define rsa_sha512_verify nettle_rsa_sha512_verify
  70 #define rsa_md5_sign_digest nettle_rsa_md5_sign_digest
  71 #define rsa_md5_sign_digest_tr nettle_rsa_md5_sign_digest_tr
  72 #define rsa_md5_verify_digest nettle_rsa_md5_verify_digest
  73 #define rsa_sha1_sign_digest nettle_rsa_sha1_sign_digest
  74 #define rsa_sha1_sign_digest_tr nettle_rsa_sha1_sign_digest_tr
  75 #define rsa_sha1_verify_digest nettle_rsa_sha1_verify_digest
  76 #define rsa_sha256_sign_digest nettle_rsa_sha256_sign_digest
  77 #define rsa_sha256_sign_digest_tr nettle_rsa_sha256_sign_digest_tr
  78 #define rsa_sha256_verify_digest nettle_rsa_sha256_verify_digest
  79 #define rsa_sha512_sign_digest nettle_rsa_sha512_sign_digest
  80 #define rsa_sha512_sign_digest_tr nettle_rsa_sha512_sign_digest_tr
  81 #define rsa_sha512_verify_digest nettle_rsa_sha512_verify_digest
  82 #define rsa_pss_sha256_sign_digest_tr nettle_rsa_pss_sha256_sign_digest_tr
  83 #define rsa_pss_sha256_verify_digest nettle_rsa_pss_sha256_verify_digest
  84 #define rsa_pss_sha384_sign_digest_tr nettle_rsa_pss_sha384_sign_digest_tr
  85 #define rsa_pss_sha384_verify_digest nettle_rsa_pss_sha384_verify_digest
  86 #define rsa_pss_sha512_sign_digest_tr nettle_rsa_pss_sha512_sign_digest_tr
  87 #define rsa_pss_sha512_verify_digest nettle_rsa_pss_sha512_verify_digest
  88 #define rsa_encrypt nettle_rsa_encrypt
  89 #define rsa_decrypt nettle_rsa_decrypt
  90 #define rsa_decrypt_tr nettle_rsa_decrypt_tr
  91 #define rsa_oaep_sha256_encrypt nettle_rsa_oaep_sha256_encrypt
  92 #define rsa_oaep_sha256_decrypt nettle_rsa_oaep_sha256_decrypt
  93 #define rsa_oaep_sha384_encrypt nettle_rsa_oaep_sha384_encrypt
  94 #define rsa_oaep_sha384_decrypt nettle_rsa_oaep_sha384_decrypt
  95 #define rsa_oaep_sha512_encrypt nettle_rsa_oaep_sha512_encrypt
  96 #define rsa_oaep_sha512_decrypt nettle_rsa_oaep_sha512_decrypt
  97 #define rsa_sec_decrypt nettle_rsa_sec_decrypt
  98 #define rsa_compute_root nettle_rsa_compute_root
  99 #define rsa_compute_root_tr nettle_rsa_compute_root_tr
 100 #define rsa_generate_keypair nettle_rsa_generate_keypair
 101 #define rsa_keypair_to_sexp nettle_rsa_keypair_to_sexp
 102 #define rsa_keypair_from_sexp_alist nettle_rsa_keypair_from_sexp_alist
 103 #define rsa_keypair_from_sexp nettle_rsa_keypair_from_sexp
 104 #define rsa_public_key_from_der_iterator nettle_rsa_public_key_from_der_iterator
 105 #define rsa_private_key_from_der_iterator nettle_rsa_private_key_from_der_iterator
 106 #define rsa_keypair_from_der nettle_rsa_keypair_from_der
 107 #define rsa_keypair_to_openpgp nettle_rsa_keypair_to_openpgp
 108
 109 /* This limit is somewhat arbitrary. Technically, the smallest modulo
 110    which makes sense at all is 15 = 3*5, phi(15) = 8, size 4 bits. But
 111    for ridiculously small keys, not all odd e are possible (e.g., for
 112    5 bits, the only possible modulo is 3*7 = 21, phi(21) = 12, and e =
 113    3 don't work). The smallest size that makes sense with pkcs#1, and
 114    which allows RSA encryption of one byte messages, is 12 octets, 89
 115    bits. */
 116
 117 #define RSA_MINIMUM_N_OCTETS 12
 118 #define RSA_MINIMUM_N_BITS (8*RSA_MINIMUM_N_OCTETS - 7)
 119
 120 struct rsa_public_key
 121 {
 122   /* Size of the modulo, in octets. This is also the size of all
 123    * signatures that are created or verified with this key. */
 124   size_t size;
 125
 126   /* Modulo */
 127   mpz_t n;
 128
 129   /* Public exponent */
 130   mpz_t e;
 131 };
 132
 133 struct rsa_private_key
 134 {
 135   size_t size;
 136
 137   /* d is filled in by the key generation function; otherwise it's
 138    * completely unused. */
 139   mpz_t d;
 140
 141   /* The two factors */
 142   mpz_t p; mpz_t q;
 143
 144   /* d % (p-1), i.e. a e = 1 (mod (p-1)) */
 145   mpz_t a;
 146
 147   /* d % (q-1), i.e. b e = 1 (mod (q-1)) */
 148   mpz_t b;
 149
 150   /* modular inverse of q , i.e. c q = 1 (mod p) */
 151   mpz_t c;
 152 };
 153
 154 /* Signing a message works as follows:
 155  *
 156  * Store the private key in a rsa_private_key struct.
 157  *
 158  * Call rsa_private_key_prepare. This initializes the size attribute
 159  * to the length of a signature.
 160  *
 161  * Initialize a hashing context, by callling
 162  *   md5_init
 163  *
 164  * Hash the message by calling
 165  *   md5_update
 166  *
 167  * Create the signature by calling
 168  *   rsa_md5_sign
 169  *
 170  * The signature is represented as a mpz_t bignum. This call also
 171  * resets the hashing context.
 172  *
 173  * When done with the key and signature, don't forget to call
 174  * mpz_clear.
 175  */
 176
 177 /* Calls mpz_init to initialize bignum storage. */
 178 void
 179 rsa_public_key_init(struct rsa_public_key *key);
 180
 181 /* Calls mpz_clear to deallocate bignum storage. */
 182 void
 183 rsa_public_key_clear(struct rsa_public_key *key);
 184
 185 int
 186 rsa_public_key_prepare(struct rsa_public_key *key);
 187
 188 /* Calls mpz_init to initialize bignum storage. */
 189 void
 190 rsa_private_key_init(struct rsa_private_key *key);
 191
 192 /* Calls mpz_clear to deallocate bignum storage. */
 193 void
 194 rsa_private_key_clear(struct rsa_private_key *key);
 195
 196 int
 197 rsa_private_key_prepare(struct rsa_private_key *key);
 198
 199
 200 /* PKCS#1 style signatures */
 201 int
 202 rsa_pkcs1_sign(const struct rsa_private_key *key,
 203                size_t length, const uint8_t *digest_info,
 204                mpz_t s);
 205
 206 int
 207 rsa_pkcs1_sign_tr(const struct rsa_public_key *pub,
 208                   const struct rsa_private_key *key,
 209                   void *random_ctx, nettle_random_func *random,
 210                   size_t length, const uint8_t *digest_info,
 211                   mpz_t s);
 212 int
 213 rsa_pkcs1_verify(const struct rsa_public_key *key,
 214                  size_t length, const uint8_t *digest_info,
 215                  const mpz_t signature);
 216
 217 int
 218 rsa_md5_sign(const struct rsa_private_key *key,
 219              struct md5_ctx *hash,
 220              mpz_t signature);
 221
 222 int
 223 rsa_md5_sign_tr(const struct rsa_public_key *pub,
 224                 const struct rsa_private_key *key,
 225                 void *random_ctx, nettle_random_func *random,
 226                 struct md5_ctx *hash, mpz_t s);
 227
 228
 229 int
 230 rsa_md5_verify(const struct rsa_public_key *key,
 231                struct md5_ctx *hash,
 232                const mpz_t signature);
 233
 234 int
 235 rsa_sha1_sign(const struct rsa_private_key *key,
 236               struct sha1_ctx *hash,
 237               mpz_t signature);
 238
 239 int
 240 rsa_sha1_sign_tr(const struct rsa_public_key *pub,
 241                  const struct rsa_private_key *key,
 242                  void *random_ctx, nettle_random_func *random,
 243                  struct sha1_ctx *hash,
 244                  mpz_t s);
 245
 246 int
 247 rsa_sha1_verify(const struct rsa_public_key *key,
 248                 struct sha1_ctx *hash,
 249                 const mpz_t signature);
 250
 251 int
 252 rsa_sha256_sign(const struct rsa_private_key *key,
 253                 struct sha256_ctx *hash,
 254                 mpz_t signature);
 255
 256 int
 257 rsa_sha256_sign_tr(const struct rsa_public_key *pub,
 258                    const struct rsa_private_key *key,
 259                    void *random_ctx, nettle_random_func *random,
 260                    struct sha256_ctx *hash,
 261                    mpz_t s);
 262
 263 int
 264 rsa_sha256_verify(const struct rsa_public_key *key,
 265                   struct sha256_ctx *hash,
 266                   const mpz_t signature);
 267
 268 int
 269 rsa_sha512_sign(const struct rsa_private_key *key,
 270                 struct sha512_ctx *hash,
 271                 mpz_t signature);
 272
 273 int
 274 rsa_sha512_sign_tr(const struct rsa_public_key *pub,
 275                    const struct rsa_private_key *key,
 276                    void *random_ctx, nettle_random_func *random,
 277                    struct sha512_ctx *hash,
 278                    mpz_t s);
 279
 280 int
 281 rsa_sha512_verify(const struct rsa_public_key *key,
 282                   struct sha512_ctx *hash,
 283                   const mpz_t signature);
 284
 285 /* Variants taking the digest as argument. */
 286 int
 287 rsa_md5_sign_digest(const struct rsa_private_key *key,
 288                     const uint8_t *digest,
 289                     mpz_t s);
 290
 291 int
 292 rsa_md5_sign_digest_tr(const struct rsa_public_key *pub,
 293                        const struct rsa_private_key *key,
 294                        void *random_ctx, nettle_random_func *random,
 295                        const uint8_t *digest, mpz_t s);
 296
 297 int
 298 rsa_md5_verify_digest(const struct rsa_public_key *key,
 299                       const uint8_t *digest,
 300                       const mpz_t signature);
 301
 302 int
 303 rsa_sha1_sign_digest(const struct rsa_private_key *key,
 304                      const uint8_t *digest,
 305                      mpz_t s);
 306
 307 int
 308 rsa_sha1_sign_digest_tr(const struct rsa_public_key *pub,
 309                         const struct rsa_private_key *key,
 310                         void *random_ctx, nettle_random_func *random,
 311                         const uint8_t *digest,
 312                         mpz_t s);
 313
 314 int
 315 rsa_sha1_verify_digest(const struct rsa_public_key *key,
 316                        const uint8_t *digest,
 317                        const mpz_t signature);
 318
 319 int
 320 rsa_sha256_sign_digest(const struct rsa_private_key *key,
 321                        const uint8_t *digest,
 322                        mpz_t s);
 323
 324 int
 325 rsa_sha256_sign_digest_tr(const struct rsa_public_key *pub,
 326                           const struct rsa_private_key *key,
 327                           void *random_ctx, nettle_random_func *random,
 328                           const uint8_t *digest,
 329                           mpz_t s);
 330
 331 int
 332 rsa_sha256_verify_digest(const struct rsa_public_key *key,
 333                          const uint8_t *digest,
 334                          const mpz_t signature);
 335
 336 int
 337 rsa_sha512_sign_digest(const struct rsa_private_key *key,
 338                        const uint8_t *digest,
 339                        mpz_t s);
 340
 341 int
 342 rsa_sha512_sign_digest_tr(const struct rsa_public_key *pub,
 343                           const struct rsa_private_key *key,
 344                           void *random_ctx, nettle_random_func *random,
 345                           const uint8_t *digest,
 346                           mpz_t s);
 347
 348 int
 349 rsa_sha512_verify_digest(const struct rsa_public_key *key,
 350                          const uint8_t *digest,
 351                          const mpz_t signature);
 352
 353 /* PSS style signatures */
 354 int
 355 rsa_pss_sha256_sign_digest_tr(const struct rsa_public_key *pub,
 356                               const struct rsa_private_key *key,
 357                               void *random_ctx, nettle_random_func *random,
 358                               size_t salt_length, const uint8_t *salt,
 359                               const uint8_t *digest,
 360                               mpz_t s);
 361
 362 int
 363 rsa_pss_sha256_verify_digest(const struct rsa_public_key *key,
 364                              size_t salt_length,
 365                              const uint8_t *digest,
 366                              const mpz_t signature);
 367
 368 int
 369 rsa_pss_sha384_sign_digest_tr(const struct rsa_public_key *pub,
 370                               const struct rsa_private_key *key,
 371                               void *random_ctx, nettle_random_func *random,
 372                               size_t salt_length, const uint8_t *salt,
 373                               const uint8_t *digest,
 374                               mpz_t s);
 375
 376 int
 377 rsa_pss_sha384_verify_digest(const struct rsa_public_key *key,
 378                              size_t salt_length,
 379                              const uint8_t *digest,
 380                              const mpz_t signature);
 381
 382 int
 383 rsa_pss_sha512_sign_digest_tr(const struct rsa_public_key *pub,
 384                               const struct rsa_private_key *key,
 385                               void *random_ctx, nettle_random_func *random,
 386                               size_t salt_length, const uint8_t *salt,
 387                               const uint8_t *digest,
 388                               mpz_t s);
 389
 390 int
 391 rsa_pss_sha512_verify_digest(const struct rsa_public_key *key,
 392                              size_t salt_length,
 393                              const uint8_t *digest,
 394                              const mpz_t signature);
 395
 396
 397 /* RSA encryption, using PKCS#1 */
 398
 399 /* Returns 1 on success, 0 on failure, which happens if the
 400  * message is too long for the key. */
 401 int
 402 rsa_encrypt(const struct rsa_public_key *key,
 403             /* For padding */
 404             void *random_ctx, nettle_random_func *random,
 405             size_t length, const uint8_t *cleartext,
 406             mpz_t cipher);
 407
 408 /* Message must point to a buffer of size *LENGTH. KEY->size is enough
 409  * for all valid messages. On success, *LENGTH is updated to reflect
 410  * the actual length of the message. Returns 1 on success, 0 on
 411  * failure, which happens if decryption failed or if the message
 412  * didn't fit. */
 413 int
 414 rsa_decrypt(const struct rsa_private_key *key,
 415             size_t *length, uint8_t *cleartext,
 416             const mpz_t ciphertext);
 417
 418 /* Timing-resistant version, using randomized RSA blinding. */
 419 int
 420 rsa_decrypt_tr(const struct rsa_public_key *pub,
 421                const struct rsa_private_key *key,
 422                void *random_ctx, nettle_random_func *random,
 423                size_t *length, uint8_t *message,
 424                const mpz_t gibberish);
 425
 426 /* like rsa_decrypt_tr but with additional side-channel resistance.
 427  * NOTE: the length of the final message must be known in advance. */
 428 int
 429 rsa_sec_decrypt(const struct rsa_public_key *pub,
 430                 const struct rsa_private_key *key,
 431                 void *random_ctx, nettle_random_func *random,
 432                 size_t length, uint8_t *message,
 433                 const mpz_t gibberish);
 434
 435 /* RSA encryption, using OAEP */
 436
 437 int
 438 rsa_oaep_sha256_encrypt (const struct rsa_public_key *key,
 439                          void *random_ctx, nettle_random_func *random,
 440                          size_t label_length, const uint8_t *label,
 441                          size_t length, const uint8_t * message,
 442                          uint8_t *ciphertext);
 443
 444 int
 445 rsa_oaep_sha256_decrypt (const struct rsa_public_key *pub,
 446                          const struct rsa_private_key *key,
 447                          void *random_ctx, nettle_random_func *random,
 448                          size_t label_length, const uint8_t *label,
 449                          size_t *length, uint8_t *message,
 450                          const uint8_t *ciphertext);
 451
 452 int
 453 rsa_oaep_sha384_encrypt (const struct rsa_public_key *key,
 454                          void *random_ctx, nettle_random_func *random,
 455                          size_t label_length, const uint8_t *label,
 456                          size_t length, const uint8_t * message,
 457                          uint8_t *ciphertext);
 458
 459 int
 460 rsa_oaep_sha384_decrypt (const struct rsa_public_key *pub,
 461                          const struct rsa_private_key *key,
 462                          void *random_ctx, nettle_random_func *random,
 463                          size_t label_length, const uint8_t *label,
 464                          size_t *length, uint8_t *message,
 465                          const uint8_t *ciphertext);
 466
 467 int
 468 rsa_oaep_sha512_encrypt (const struct rsa_public_key *key,
 469                          void *random_ctx, nettle_random_func *random,
 470                          size_t label_length, const uint8_t *label,
 471                          size_t length, const uint8_t *message,
 472                          uint8_t *ciphertext);
 473
 474 int
 475 rsa_oaep_sha512_decrypt (const struct rsa_public_key *pub,
 476                          const struct rsa_private_key *key,
 477                          void *random_ctx, nettle_random_func *random,
 478                          size_t label_length, const uint8_t *label,
 479                          size_t *length, uint8_t *message,
 480                          const uint8_t *ciphertext);
 481
 482 /* Compute x, the e:th root of m. Calling it with x == m is allowed.
 483    It is required that 0 <= m < n. */
 484 void
 485 rsa_compute_root(const struct rsa_private_key *key,
 486                  mpz_t x, const mpz_t m);
 487
 488 /* Safer variant, using RSA blinding, and checking the result after
 489    CRT. It is required that 0 <= m < n. */
 490 int
 491 rsa_compute_root_tr(const struct rsa_public_key *pub,
 492                     const struct rsa_private_key *key,
 493                     void *random_ctx, nettle_random_func *random,
 494                     mpz_t x, const mpz_t m);
 495
 496 /* Key generation */
 497
 498 /* Note that the key structs must be initialized first. */
 499 int
 500 rsa_generate_keypair(struct rsa_public_key *pub,
 501                      struct rsa_private_key *key,
 502
 503                      void *random_ctx, nettle_random_func *random,
 504                      void *progress_ctx, nettle_progress_func *progress,
 505
 506                      /* Desired size of modulo, in bits */
 507                      unsigned n_size,
 508
 509                      /* Desired size of public exponent, in bits. If
 510                       * zero, the passed in value pub->e is used. */
 511                      unsigned e_size);
 512
 513
 514 #define RSA_SIGN(key, algorithm, ctx, length, data, signature) ( \
 515   algorithm##_update(ctx, length, data), \
 516   rsa_##algorithm##_sign(key, ctx, signature) \
 517 )
 518
 519 #define RSA_VERIFY(key, algorithm, ctx, length, data, signature) ( \
 520   algorithm##_update(ctx, length, data), \
 521   rsa_##algorithm##_verify(key, ctx, signature) \
 522 )
 523
 524 \f
 525 /* Keys in sexp form. */
 526
 527 struct nettle_buffer;
 528
 529 /* Generates a public-key expression if PRIV is NULL .*/
 530 int
 531 rsa_keypair_to_sexp(struct nettle_buffer *buffer,
 532                     const char *algorithm_name, /* NULL means "rsa" */
 533                     const struct rsa_public_key *pub,
 534                     const struct rsa_private_key *priv);
 535
 536 struct sexp_iterator;
 537
 538 int
 539 rsa_keypair_from_sexp_alist(struct rsa_public_key *pub,
 540                             struct rsa_private_key *priv,
 541                             unsigned limit,
 542                             struct sexp_iterator *i);
 543
 544 /* If PRIV is NULL, expect a public-key expression. If PUB is NULL,
 545  * expect a private key expression and ignore the parts not needed for
 546  * the public key. */
 547 /* Keys must be initialized before calling this function, as usual. */
 548 int
 549 rsa_keypair_from_sexp(struct rsa_public_key *pub,
 550                       struct rsa_private_key *priv,
 551                       unsigned limit,
 552                       size_t length, const uint8_t *expr);
 553
 554
 555 /* Keys in PKCS#1 format. */
 556 struct asn1_der_iterator;
 557
 558 int
 559 rsa_public_key_from_der_iterator(struct rsa_public_key *pub,
 560                                  unsigned limit,
 561                                  struct asn1_der_iterator *i);
 562
 563 int
 564 rsa_private_key_from_der_iterator(struct rsa_public_key *pub,
 565                                   struct rsa_private_key *priv,
 566                                   unsigned limit,
 567                                   struct asn1_der_iterator *i);
 568
 569 /* For public keys, use PRIV == NULL */
 570 int
 571 rsa_keypair_from_der(struct rsa_public_key *pub,
 572                      struct rsa_private_key *priv,
 573                      unsigned limit,
 574                      size_t length, const uint8_t *data);
 575
 576 /* OpenPGP format. Experimental interface, subject to change. */
 577 int
 578 rsa_keypair_to_openpgp(struct nettle_buffer *buffer,
 579                        const struct rsa_public_key *pub,
 580                        const struct rsa_private_key *priv,
 581                        /* A single user id. NUL-terminated utf8. */
 582                        const char *userid);
 583
 584
 585 #ifdef __cplusplus
 586 }
 587 #endif
 588
 589 #endif /* NETTLE_RSA_H_INCLUDED */