git.samba.org - gd/nettle/blob - 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_sec_decrypt nettle_rsa_sec_decrypt
  92 #define rsa_compute_root nettle_rsa_compute_root
  93 #define rsa_compute_root_tr nettle_rsa_compute_root_tr
  94 #define rsa_generate_keypair nettle_rsa_generate_keypair
  95 #define rsa_keypair_to_sexp nettle_rsa_keypair_to_sexp
  96 #define rsa_keypair_from_sexp_alist nettle_rsa_keypair_from_sexp_alist
  97 #define rsa_keypair_from_sexp nettle_rsa_keypair_from_sexp
  98 #define rsa_public_key_from_der_iterator nettle_rsa_public_key_from_der_iterator
  99 #define rsa_private_key_from_der_iterator nettle_rsa_private_key_from_der_iterator
 100 #define rsa_keypair_from_der nettle_rsa_keypair_from_der
 101 #define rsa_keypair_to_openpgp nettle_rsa_keypair_to_openpgp
 102 #define _rsa_verify _nettle_rsa_verify
 103 #define _rsa_verify_recover _nettle_rsa_verify_recover
 104 #define _rsa_check_size _nettle_rsa_check_size
 105 #define _rsa_blind _nettle_rsa_blind
 106 #define _rsa_unblind _nettle_rsa_unblind
 107
 108 /* This limit is somewhat arbitrary. Technically, the smallest modulo
 109    which makes sense at all is 15 = 3*5, phi(15) = 8, size 4 bits. But
 110    for ridiculously small keys, not all odd e are possible (e.g., for
 111    5 bits, the only possible modulo is 3*7 = 21, phi(21) = 12, and e =
 112    3 don't work). The smallest size that makes sense with pkcs#1, and
 113    which allows RSA encryption of one byte messages, is 12 octets, 89
 114    bits. */
 115
 116 #define RSA_MINIMUM_N_OCTETS 12
 117 #define RSA_MINIMUM_N_BITS (8*RSA_MINIMUM_N_OCTETS - 7)
 118
 119 struct rsa_public_key
 120 {
 121   /* Size of the modulo, in octets. This is also the size of all
 122    * signatures that are created or verified with this key. */
 123   size_t size;
 124
 125   /* Modulo */
 126   mpz_t n;
 127
 128   /* Public exponent */
 129   mpz_t e;
 130 };
 131
 132 struct rsa_private_key
 133 {
 134   size_t size;
 135
 136   /* d is filled in by the key generation function; otherwise it's
 137    * completely unused. */
 138   mpz_t d;
 139
 140   /* The two factors */
 141   mpz_t p; mpz_t q;
 142
 143   /* d % (p-1), i.e. a e = 1 (mod (p-1)) */
 144   mpz_t a;
 145
 146   /* d % (q-1), i.e. b e = 1 (mod (q-1)) */
 147   mpz_t b;
 148
 149   /* modular inverse of q , i.e. c q = 1 (mod p) */
 150   mpz_t c;
 151 };
 152
 153 /* Signing a message works as follows:
 154  *
 155  * Store the private key in a rsa_private_key struct.
 156  *
 157  * Call rsa_private_key_prepare. This initializes the size attribute
 158  * to the length of a signature.
 159  *
 160  * Initialize a hashing context, by callling
 161  *   md5_init
 162  *
 163  * Hash the message by calling
 164  *   md5_update
 165  *
 166  * Create the signature by calling
 167  *   rsa_md5_sign
 168  *
 169  * The signature is represented as a mpz_t bignum. This call also
 170  * resets the hashing context.
 171  *
 172  * When done with the key and signature, don't forget to call
 173  * mpz_clear.
 174  */
 175
 176 /* Calls mpz_init to initialize bignum storage. */
 177 void
 178 rsa_public_key_init(struct rsa_public_key *key);
 179
 180 /* Calls mpz_clear to deallocate bignum storage. */
 181 void
 182 rsa_public_key_clear(struct rsa_public_key *key);
 183
 184 int
 185 rsa_public_key_prepare(struct rsa_public_key *key);
 186
 187 /* Calls mpz_init to initialize bignum storage. */
 188 void
 189 rsa_private_key_init(struct rsa_private_key *key);
 190
 191 /* Calls mpz_clear to deallocate bignum storage. */
 192 void
 193 rsa_private_key_clear(struct rsa_private_key *key);
 194
 195 int
 196 rsa_private_key_prepare(struct rsa_private_key *key);
 197
 198
 199 /* PKCS#1 style signatures */
 200 int
 201 rsa_pkcs1_sign(const struct rsa_private_key *key,
 202                size_t length, const uint8_t *digest_info,
 203                mpz_t s);
 204
 205 int
 206 rsa_pkcs1_sign_tr(const struct rsa_public_key *pub,
 207                   const struct rsa_private_key *key,
 208                   void *random_ctx, nettle_random_func *random,
 209                   size_t length, const uint8_t *digest_info,
 210                   mpz_t s);
 211 int
 212 rsa_pkcs1_verify(const struct rsa_public_key *key,
 213                  size_t length, const uint8_t *digest_info,
 214                  const mpz_t signature);
 215
 216 int
 217 rsa_md5_sign(const struct rsa_private_key *key,
 218              struct md5_ctx *hash,
 219              mpz_t signature);
 220
 221 int
 222 rsa_md5_sign_tr(const struct rsa_public_key *pub,
 223                 const struct rsa_private_key *key,
 224                 void *random_ctx, nettle_random_func *random,
 225                 struct md5_ctx *hash, mpz_t s);
 226
 227
 228 int
 229 rsa_md5_verify(const struct rsa_public_key *key,
 230                struct md5_ctx *hash,
 231                const mpz_t signature);
 232
 233 int
 234 rsa_sha1_sign(const struct rsa_private_key *key,
 235               struct sha1_ctx *hash,
 236               mpz_t signature);
 237
 238 int
 239 rsa_sha1_sign_tr(const struct rsa_public_key *pub,
 240                  const struct rsa_private_key *key,
 241                  void *random_ctx, nettle_random_func *random,
 242                  struct sha1_ctx *hash,
 243                  mpz_t s);
 244
 245 int
 246 rsa_sha1_verify(const struct rsa_public_key *key,
 247                 struct sha1_ctx *hash,
 248                 const mpz_t signature);
 249
 250 int
 251 rsa_sha256_sign(const struct rsa_private_key *key,
 252                 struct sha256_ctx *hash,
 253                 mpz_t signature);
 254
 255 int
 256 rsa_sha256_sign_tr(const struct rsa_public_key *pub,
 257                    const struct rsa_private_key *key,
 258                    void *random_ctx, nettle_random_func *random,
 259                    struct sha256_ctx *hash,
 260                    mpz_t s);
 261
 262 int
 263 rsa_sha256_verify(const struct rsa_public_key *key,
 264                   struct sha256_ctx *hash,
 265                   const mpz_t signature);
 266
 267 int
 268 rsa_sha512_sign(const struct rsa_private_key *key,
 269                 struct sha512_ctx *hash,
 270                 mpz_t signature);
 271
 272 int
 273 rsa_sha512_sign_tr(const struct rsa_public_key *pub,
 274                    const struct rsa_private_key *key,
 275                    void *random_ctx, nettle_random_func *random,
 276                    struct sha512_ctx *hash,
 277                    mpz_t s);
 278
 279 int
 280 rsa_sha512_verify(const struct rsa_public_key *key,
 281                   struct sha512_ctx *hash,
 282                   const mpz_t signature);
 283
 284 /* Variants taking the digest as argument. */
 285 int
 286 rsa_md5_sign_digest(const struct rsa_private_key *key,
 287                     const uint8_t *digest,
 288                     mpz_t s);
 289
 290 int
 291 rsa_md5_sign_digest_tr(const struct rsa_public_key *pub,
 292                        const struct rsa_private_key *key,
 293                        void *random_ctx, nettle_random_func *random,
 294                        const uint8_t *digest, mpz_t s);
 295
 296 int
 297 rsa_md5_verify_digest(const struct rsa_public_key *key,
 298                       const uint8_t *digest,
 299                       const mpz_t signature);
 300
 301 int
 302 rsa_sha1_sign_digest(const struct rsa_private_key *key,
 303                      const uint8_t *digest,
 304                      mpz_t s);
 305
 306 int
 307 rsa_sha1_sign_digest_tr(const struct rsa_public_key *pub,
 308                         const struct rsa_private_key *key,
 309                         void *random_ctx, nettle_random_func *random,
 310                         const uint8_t *digest,
 311                         mpz_t s);
 312
 313 int
 314 rsa_sha1_verify_digest(const struct rsa_public_key *key,
 315                        const uint8_t *digest,
 316                        const mpz_t signature);
 317
 318 int
 319 rsa_sha256_sign_digest(const struct rsa_private_key *key,
 320                        const uint8_t *digest,
 321                        mpz_t s);
 322
 323 int
 324 rsa_sha256_sign_digest_tr(const struct rsa_public_key *pub,
 325                           const struct rsa_private_key *key,
 326                           void *random_ctx, nettle_random_func *random,
 327                           const uint8_t *digest,
 328                           mpz_t s);
 329
 330 int
 331 rsa_sha256_verify_digest(const struct rsa_public_key *key,
 332                          const uint8_t *digest,
 333                          const mpz_t signature);
 334
 335 int
 336 rsa_sha512_sign_digest(const struct rsa_private_key *key,
 337                        const uint8_t *digest,
 338                        mpz_t s);
 339
 340 int
 341 rsa_sha512_sign_digest_tr(const struct rsa_public_key *pub,
 342                           const struct rsa_private_key *key,
 343                           void *random_ctx, nettle_random_func *random,
 344                           const uint8_t *digest,
 345                           mpz_t s);
 346
 347 int
 348 rsa_sha512_verify_digest(const struct rsa_public_key *key,
 349                          const uint8_t *digest,
 350                          const mpz_t signature);
 351
 352 /* PSS style signatures */
 353 int
 354 rsa_pss_sha256_sign_digest_tr(const struct rsa_public_key *pub,
 355                               const struct rsa_private_key *key,
 356                               void *random_ctx, nettle_random_func *random,
 357                               size_t salt_length, const uint8_t *salt,
 358                               const uint8_t *digest,
 359                               mpz_t s);
 360
 361 int
 362 rsa_pss_sha256_verify_digest(const struct rsa_public_key *key,
 363                              size_t salt_length,
 364                              const uint8_t *digest,
 365                              const mpz_t signature);
 366
 367 int
 368 rsa_pss_sha384_sign_digest_tr(const struct rsa_public_key *pub,
 369                               const struct rsa_private_key *key,
 370                               void *random_ctx, nettle_random_func *random,
 371                               size_t salt_length, const uint8_t *salt,
 372                               const uint8_t *digest,
 373                               mpz_t s);
 374
 375 int
 376 rsa_pss_sha384_verify_digest(const struct rsa_public_key *key,
 377                              size_t salt_length,
 378                              const uint8_t *digest,
 379                              const mpz_t signature);
 380
 381 int
 382 rsa_pss_sha512_sign_digest_tr(const struct rsa_public_key *pub,
 383                               const struct rsa_private_key *key,
 384                               void *random_ctx, nettle_random_func *random,
 385                               size_t salt_length, const uint8_t *salt,
 386                               const uint8_t *digest,
 387                               mpz_t s);
 388
 389 int
 390 rsa_pss_sha512_verify_digest(const struct rsa_public_key *key,
 391                              size_t salt_length,
 392                              const uint8_t *digest,
 393                              const mpz_t signature);
 394
 395
 396 /* RSA encryption, using PKCS#1 */
 397 /* These functions uses the v1.5 padding. What should the v2 (OAEP)
 398  * functions be called? */
 399
 400 /* Returns 1 on success, 0 on failure, which happens if the
 401  * message is too long for the key. */
 402 int
 403 rsa_encrypt(const struct rsa_public_key *key,
 404             /* For padding */
 405             void *random_ctx, nettle_random_func *random,
 406             size_t length, const uint8_t *cleartext,
 407             mpz_t cipher);
 408
 409 /* Message must point to a buffer of size *LENGTH. KEY->size is enough
 410  * for all valid messages. On success, *LENGTH is updated to reflect
 411  * the actual length of the message. Returns 1 on success, 0 on
 412  * failure, which happens if decryption failed or if the message
 413  * didn't fit. */
 414 int
 415 rsa_decrypt(const struct rsa_private_key *key,
 416             size_t *length, uint8_t *cleartext,
 417             const mpz_t ciphertext);
 418
 419 /* Timing-resistant version, using randomized RSA blinding. */
 420 int
 421 rsa_decrypt_tr(const struct rsa_public_key *pub,
 422                const struct rsa_private_key *key,
 423                void *random_ctx, nettle_random_func *random,
 424                size_t *length, uint8_t *message,
 425                const mpz_t gibberish);
 426
 427 /* like rsa_decrypt_tr but with additional side-channel resistance.
 428  * NOTE: the length of the final message must be known in advance. */
 429 int
 430 rsa_sec_decrypt(const struct rsa_public_key *pub,
 431                 const struct rsa_private_key *key,
 432                 void *random_ctx, nettle_random_func *random,
 433                 size_t length, uint8_t *message,
 434                 const mpz_t gibberish);
 435
 436 /* Compute x, the e:th root of m. Calling it with x == m is allowed. */
 437 void
 438 rsa_compute_root(const struct rsa_private_key *key,
 439                  mpz_t x, const mpz_t m);
 440
 441 /* Safer variant, using RSA blinding, and checking the result after
 442    CRT. */
 443 int
 444 rsa_compute_root_tr(const struct rsa_public_key *pub,
 445                     const struct rsa_private_key *key,
 446                     void *random_ctx, nettle_random_func *random,
 447                     mpz_t x, const mpz_t m);
 448
 449 /* Key generation */
 450
 451 /* Note that the key structs must be initialized first. */
 452 int
 453 rsa_generate_keypair(struct rsa_public_key *pub,
 454                      struct rsa_private_key *key,
 455
 456                      void *random_ctx, nettle_random_func *random,
 457                      void *progress_ctx, nettle_progress_func *progress,
 458
 459                      /* Desired size of modulo, in bits */
 460                      unsigned n_size,
 461
 462                      /* Desired size of public exponent, in bits. If
 463                       * zero, the passed in value pub->e is used. */
 464                      unsigned e_size);
 465
 466
 467 #define RSA_SIGN(key, algorithm, ctx, length, data, signature) ( \
 468   algorithm##_update(ctx, length, data), \
 469   rsa_##algorithm##_sign(key, ctx, signature) \
 470 )
 471
 472 #define RSA_VERIFY(key, algorithm, ctx, length, data, signature) ( \
 473   algorithm##_update(ctx, length, data), \
 474   rsa_##algorithm##_verify(key, ctx, signature) \
 475 )
 476
 477 \f
 478 /* Keys in sexp form. */
 479
 480 struct nettle_buffer;
 481
 482 /* Generates a public-key expression if PRIV is NULL .*/
 483 int
 484 rsa_keypair_to_sexp(struct nettle_buffer *buffer,
 485                     const char *algorithm_name, /* NULL means "rsa" */
 486                     const struct rsa_public_key *pub,
 487                     const struct rsa_private_key *priv);
 488
 489 struct sexp_iterator;
 490
 491 int
 492 rsa_keypair_from_sexp_alist(struct rsa_public_key *pub,
 493                             struct rsa_private_key *priv,
 494                             unsigned limit,
 495                             struct sexp_iterator *i);
 496
 497 /* If PRIV is NULL, expect a public-key expression. If PUB is NULL,
 498  * expect a private key expression and ignore the parts not needed for
 499  * the public key. */
 500 /* Keys must be initialized before calling this function, as usual. */
 501 int
 502 rsa_keypair_from_sexp(struct rsa_public_key *pub,
 503                       struct rsa_private_key *priv,
 504                       unsigned limit,
 505                       size_t length, const uint8_t *expr);
 506
 507
 508 /* Keys in PKCS#1 format. */
 509 struct asn1_der_iterator;
 510
 511 int
 512 rsa_public_key_from_der_iterator(struct rsa_public_key *pub,
 513                                  unsigned limit,
 514                                  struct asn1_der_iterator *i);
 515
 516 int
 517 rsa_private_key_from_der_iterator(struct rsa_public_key *pub,
 518                                   struct rsa_private_key *priv,
 519                                   unsigned limit,
 520                                   struct asn1_der_iterator *i);
 521
 522 /* For public keys, use PRIV == NULL */
 523 int
 524 rsa_keypair_from_der(struct rsa_public_key *pub,
 525                      struct rsa_private_key *priv,
 526                      unsigned limit,
 527                      size_t length, const uint8_t *data);
 528
 529 /* OpenPGP format. Experimental interface, subject to change. */
 530 int
 531 rsa_keypair_to_openpgp(struct nettle_buffer *buffer,
 532                        const struct rsa_public_key *pub,
 533                        const struct rsa_private_key *priv,
 534                        /* A single user id. NUL-terminated utf8. */
 535                        const char *userid);
 536
 537 /* Internal functions. */
 538 int
 539 _rsa_verify(const struct rsa_public_key *key,
 540             const mpz_t m,
 541             const mpz_t s);
 542
 543 int
 544 _rsa_verify_recover(const struct rsa_public_key *key,
 545                     mpz_t m,
 546                     const mpz_t s);
 547
 548 size_t
 549 _rsa_check_size(mpz_t n);
 550
 551 /* _rsa_blind and _rsa_unblind are deprecated, unused in the library,
 552    and will likely be removed with the next ABI break. */
 553 void
 554 _rsa_blind (const struct rsa_public_key *pub,
 555             void *random_ctx, nettle_random_func *random,
 556             mpz_t c, mpz_t ri);
 557 void
 558 _rsa_unblind (const struct rsa_public_key *pub, mpz_t c, const mpz_t ri);
 559
 560 #ifdef __cplusplus
 561 }
 562 #endif
 563
 564 #endif /* NETTLE_RSA_H_INCLUDED */