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