rsa.h

   1 /* rsa.h
   2  *
   3  * The RSA publickey algorithm.
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2001, 2002 Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  23  * MA 02111-1307, USA.
  24  */
  25
  26 #ifndef NETTLE_RSA_H_INCLUDED
  27 #define NETTLE_RSA_H_INCLUDED
  28
  29 #include <gmp.h>
  30 #include "nettle-types.h"
  31
  32 #include "md5.h"
  33 #include "sha.h"
  34
  35 /* For nettle_random_func */
  36 #include "nettle-meta.h"
  37
  38 #ifdef __cplusplus
  39 extern "C" {
  40 #endif
  41
  42 /* Name mangling */
  43 #define rsa_public_key_init nettle_rsa_public_key_init
  44 #define rsa_public_key_clear nettle_rsa_public_key_clear
  45 #define rsa_public_key_prepare nettle_rsa_public_key_prepare
  46 #define rsa_private_key_init nettle_rsa_private_key_init
  47 #define rsa_private_key_clear nettle_rsa_private_key_clear
  48 #define rsa_private_key_prepare nettle_rsa_private_key_prepare
  49 #define rsa_md5_sign nettle_rsa_md5_sign
  50 #define rsa_md5_verify nettle_rsa_md5_verify
  51 #define rsa_sha1_sign nettle_rsa_sha1_sign
  52 #define rsa_sha1_verify nettle_rsa_sha1_verify
  53 #define rsa_sha256_sign nettle_rsa_sha256_sign
  54 #define rsa_sha256_verify nettle_rsa_sha256_verify
  55 #define rsa_sha512_sign nettle_rsa_sha512_sign
  56 #define rsa_sha512_verify nettle_rsa_sha512_verify
  57 #define rsa_md5_sign_digest nettle_rsa_md5_sign_digest
  58 #define rsa_md5_verify_digest nettle_rsa_md5_verify_digest
  59 #define rsa_sha1_sign_digest nettle_rsa_sha1_sign_digest
  60 #define rsa_sha1_verify_digest nettle_rsa_sha1_verify_digest
  61 #define rsa_sha256_sign_digest nettle_rsa_sha256_sign_digest
  62 #define rsa_sha256_verify_digest nettle_rsa_sha256_verify_digest
  63 #define rsa_sha512_sign_digest nettle_rsa_sha512_sign_digest
  64 #define rsa_sha512_verify_digest nettle_rsa_sha512_verify_digest
  65 #define rsa_encrypt nettle_rsa_encrypt
  66 #define rsa_decrypt nettle_rsa_decrypt
  67 #define rsa_compute_root nettle_rsa_compute_root
  68 #define rsa_generate_keypair nettle_rsa_generate_keypair
  69 #define rsa_keypair_to_sexp nettle_rsa_keypair_to_sexp
  70 #define rsa_keypair_from_sexp_alist nettle_rsa_keypair_from_sexp_alist
  71 #define rsa_keypair_from_sexp nettle_rsa_keypair_from_sexp
  72 #define rsa_public_key_from_der_iterator nettle_rsa_public_key_from_der_iterator
  73 #define rsa_private_key_from_der_iterator nettle_rsa_private_key_from_der_iterator
  74 #define rsa_keypair_from_der nettle_rsa_keypair_from_der
  75 #define rsa_keypair_to_openpgp nettle_rsa_keypair_to_openpgp
  76 #define _rsa_verify _nettle_rsa_verify
  77 #define _rsa_check_size _nettle_rsa_check_size
  78
  79 /* This limit is somewhat arbitrary. Technically, the smallest modulo
  80    which makes sense at all is 15 = 3*5, phi(15) = 8, size 4 bits. But
  81    for ridiculously small keys, not all odd e are possible (e.g., for
  82    5 bits, the only possible modulo is 3*7 = 21, phi(21) = 12, and e =
  83    3 don't work). The smallest size that makes sense with pkcs#1, and
  84    which allows RSA encryption of one byte messages, is 12 octets, 89
  85    bits. */
  86
  87 #define RSA_MINIMUM_N_OCTETS 12
  88 #define RSA_MINIMUM_N_BITS (8*RSA_MINIMUM_N_OCTETS - 7)
  89
  90 struct rsa_public_key
  91 {
  92   /* Size of the modulo, in octets. This is also the size of all
  93    * signatures that are created or verified with this key. */
  94   unsigned size;
  95
  96   /* Modulo */
  97   mpz_t n;
  98
  99   /* Public exponent */
 100   mpz_t e;
 101 };
 102
 103 struct rsa_private_key
 104 {
 105   unsigned size;
 106
 107   /* d is filled in by the key generation function; otherwise it's
 108    * completely unused. */
 109   mpz_t d;
 110
 111   /* The two factors */
 112   mpz_t p; mpz_t q;
 113
 114   /* d % (p-1), i.e. a e = 1 (mod (p-1)) */
 115   mpz_t a;
 116
 117   /* d % (q-1), i.e. b e = 1 (mod (q-1)) */
 118   mpz_t b;
 119
 120   /* modular inverse of q , i.e. c q = 1 (mod p) */
 121   mpz_t c;
 122 };
 123
 124 /* Signing a message works as follows:
 125  *
 126  * Store the private key in a rsa_private_key struct.
 127  *
 128  * Call rsa_private_key_prepare. This initializes the size attribute
 129  * to the length of a signature.
 130  *
 131  * Initialize a hashing context, by callling
 132  *   md5_init
 133  *
 134  * Hash the message by calling
 135  *   md5_update
 136  *
 137  * Create the signature by calling
 138  *   rsa_md5_sign
 139  *
 140  * The signature is represented as a mpz_t bignum. This call also
 141  * resets the hashing context.
 142  *
 143  * When done with the key and signature, don't forget to call
 144  * mpz_clear.
 145  */
 146
 147 /* Calls mpz_init to initialize bignum storage. */
 148 void
 149 rsa_public_key_init(struct rsa_public_key *key);
 150
 151 /* Calls mpz_clear to deallocate bignum storage. */
 152 void
 153 rsa_public_key_clear(struct rsa_public_key *key);
 154
 155 int
 156 rsa_public_key_prepare(struct rsa_public_key *key);
 157
 158 /* Calls mpz_init to initialize bignum storage. */
 159 void
 160 rsa_private_key_init(struct rsa_private_key *key);
 161
 162 /* Calls mpz_clear to deallocate bignum storage. */
 163 void
 164 rsa_private_key_clear(struct rsa_private_key *key);
 165
 166 int
 167 rsa_private_key_prepare(struct rsa_private_key *key);
 168
 169
 170 /* PKCS#1 style signatures */
 171 int
 172 rsa_md5_sign(const struct rsa_private_key *key,
 173              struct md5_ctx *hash,
 174              mpz_t signature);
 175
 176
 177 int
 178 rsa_md5_verify(const struct rsa_public_key *key,
 179                struct md5_ctx *hash,
 180                const mpz_t signature);
 181
 182 int
 183 rsa_sha1_sign(const struct rsa_private_key *key,
 184               struct sha1_ctx *hash,
 185               mpz_t signature);
 186
 187 int
 188 rsa_sha1_verify(const struct rsa_public_key *key,
 189                 struct sha1_ctx *hash,
 190                 const mpz_t signature);
 191
 192 int
 193 rsa_sha256_sign(const struct rsa_private_key *key,
 194                 struct sha256_ctx *hash,
 195                 mpz_t signature);
 196
 197 int
 198 rsa_sha256_verify(const struct rsa_public_key *key,
 199                   struct sha256_ctx *hash,
 200                   const mpz_t signature);
 201
 202 int
 203 rsa_sha512_sign(const struct rsa_private_key *key,
 204                 struct sha512_ctx *hash,
 205                 mpz_t signature);
 206
 207 int
 208 rsa_sha512_verify(const struct rsa_public_key *key,
 209                   struct sha512_ctx *hash,
 210                   const mpz_t signature);
 211
 212 /* Variants taking the digest as argument. */
 213 int
 214 rsa_md5_sign_digest(const struct rsa_private_key *key,
 215                     const uint8_t *digest,
 216                     mpz_t s);
 217
 218 int
 219 rsa_md5_verify_digest(const struct rsa_public_key *key,
 220                       const uint8_t *digest,
 221                       const mpz_t signature);
 222
 223 int
 224 rsa_sha1_sign_digest(const struct rsa_private_key *key,
 225                      const uint8_t *digest,
 226                      mpz_t s);
 227
 228 int
 229 rsa_sha1_verify_digest(const struct rsa_public_key *key,
 230                        const uint8_t *digest,
 231                        const mpz_t signature);
 232
 233 int
 234 rsa_sha256_sign_digest(const struct rsa_private_key *key,
 235                        const uint8_t *digest,
 236                        mpz_t s);
 237
 238 int
 239 rsa_sha256_verify_digest(const struct rsa_public_key *key,
 240                          const uint8_t *digest,
 241                          const mpz_t signature);
 242
 243 int
 244 rsa_sha512_sign_digest(const struct rsa_private_key *key,
 245                        const uint8_t *digest,
 246                        mpz_t s);
 247
 248 int
 249 rsa_sha512_verify_digest(const struct rsa_public_key *key,
 250                          const uint8_t *digest,
 251                          const mpz_t signature);
 252
 253
 254 /* RSA encryption, using PKCS#1 */
 255 /* These functions uses the v1.5 padding. What should the v2 (OAEP)
 256  * functions be called? */
 257
 258 /* Returns 1 on success, 0 on failure, which happens if the
 259  * message is too long for the key. */
 260 int
 261 rsa_encrypt(const struct rsa_public_key *key,
 262             /* For padding */
 263             void *random_ctx, nettle_random_func random,
 264             unsigned length, const uint8_t *cleartext,
 265             mpz_t cipher);
 266
 267 /* Message must point to a buffer of size *LENGTH. KEY->size is enough
 268  * for all valid messages. On success, *LENGTH is updated to reflect
 269  * the actual length of the message. Returns 1 on success, 0 on
 270  * failure, which happens if decryption failed or if the message
 271  * didn't fit. */
 272 int
 273 rsa_decrypt(const struct rsa_private_key *key,
 274             unsigned *length, uint8_t *cleartext,
 275             const mpz_t ciphertext);
 276
 277 /* Compute x, the e:th root of m. Calling it with x == m is allowed. */
 278 void
 279 rsa_compute_root(const struct rsa_private_key *key,
 280                  mpz_t x, const mpz_t m);
 281
 282
 283 /* Key generation */
 284
 285 /* Note that the key structs must be initialized first. */
 286 int
 287 rsa_generate_keypair(struct rsa_public_key *pub,
 288                      struct rsa_private_key *key,
 289
 290                      void *random_ctx, nettle_random_func random,
 291                      void *progress_ctx, nettle_progress_func progress,
 292
 293                      /* Desired size of modulo, in bits */
 294                      unsigned n_size,
 295
 296                      /* Desired size of public exponent, in bits. If
 297                       * zero, the passed in value pub->e is used. */
 298                      unsigned e_size);
 299
 300
 301 #define RSA_SIGN(key, algorithm, ctx, length, data, signature) ( \
 302   algorithm##_update(ctx, length, data), \
 303   rsa_##algorithm##_sign(key, ctx, signature) \
 304 )
 305
 306 #define RSA_VERIFY(key, algorithm, ctx, length, data, signature) ( \
 307   algorithm##_update(ctx, length, data), \
 308   rsa_##algorithm##_verify(key, ctx, signature) \
 309 )
 310
 311 \f
 312 /* Keys in sexp form. */
 313
 314 struct nettle_buffer;
 315
 316 /* Generates a public-key expression if PRIV is NULL .*/
 317 int
 318 rsa_keypair_to_sexp(struct nettle_buffer *buffer,
 319                     const char *algorithm_name, /* NULL means "rsa" */
 320                     const struct rsa_public_key *pub,
 321                     const struct rsa_private_key *priv);
 322
 323 struct sexp_iterator;
 324
 325 int
 326 rsa_keypair_from_sexp_alist(struct rsa_public_key *pub,
 327                             struct rsa_private_key *priv,
 328                             unsigned limit,
 329                             struct sexp_iterator *i);
 330
 331 /* If PRIV is NULL, expect a public-key expression. If PUB is NULL,
 332  * expect a private key expression and ignore the parts not needed for
 333  * the public key. */
 334 /* Keys must be initialized before calling this function, as usual. */
 335 int
 336 rsa_keypair_from_sexp(struct rsa_public_key *pub,
 337                       struct rsa_private_key *priv,
 338                       unsigned limit,
 339                       unsigned length, const uint8_t *expr);
 340
 341
 342 /* Keys in PKCS#1 format. */
 343 struct asn1_der_iterator;
 344
 345 int
 346 rsa_public_key_from_der_iterator(struct rsa_public_key *pub,
 347                                  unsigned limit,
 348                                  struct asn1_der_iterator *i);
 349
 350 int
 351 rsa_private_key_from_der_iterator(struct rsa_public_key *pub,
 352                                   struct rsa_private_key *priv,
 353                                   unsigned limit,
 354                                   struct asn1_der_iterator *i);
 355
 356 /* For public keys, use PRIV == NULL */
 357 int
 358 rsa_keypair_from_der(struct rsa_public_key *pub,
 359                      struct rsa_private_key *priv,
 360                      unsigned limit,
 361                      unsigned length, const uint8_t *data);
 362
 363 /* OpenPGP format. Experimental interface, subject to change. */
 364 int
 365 rsa_keypair_to_openpgp(struct nettle_buffer *buffer,
 366                        const struct rsa_public_key *pub,
 367                        const struct rsa_private_key *priv,
 368                        /* A single user id. NUL-terminated utf8. */
 369                        const char *userid);
 370
 371 /* Internal functions. */
 372 int
 373 _rsa_verify(const struct rsa_public_key *key,
 374             const mpz_t m,
 375             const mpz_t s);
 376
 377 unsigned
 378 _rsa_check_size(mpz_t n);
 379
 380 #ifdef __cplusplus
 381 }
 382 #endif
 383
 384 #endif /* NETTLE_RSA_H_INCLUDED */