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