rsa-sign.c

   1 /* rsa-sign.c
   2  *
   3  * Creating RSA signatures.
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2001, 2003 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 #if HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include "rsa.h"
  31
  32 #include "bignum.h"
  33
  34 void
  35 rsa_private_key_init(struct rsa_private_key *key)
  36 {
  37   mpz_init(key->d);
  38   mpz_init(key->p);
  39   mpz_init(key->q);
  40   mpz_init(key->a);
  41   mpz_init(key->b);
  42   mpz_init(key->c);
  43
  44   /* Not really necessary, but it seems cleaner to initialize all the
  45    * storage. */
  46   key->size = 0;
  47 }
  48
  49 void
  50 rsa_private_key_clear(struct rsa_private_key *key)
  51 {
  52   mpz_clear(key->d);
  53   mpz_clear(key->p);
  54   mpz_clear(key->q);
  55   mpz_clear(key->a);
  56   mpz_clear(key->b);
  57   mpz_clear(key->c);
  58 }
  59
  60 int
  61 rsa_private_key_prepare(struct rsa_private_key *key)
  62 {
  63   mpz_t n;
  64
  65   /* The size of the product is the sum of the sizes of the factors,
  66    * or sometimes one less. It's possible but tricky to compute the
  67    * size without computing the full product. */
  68
  69   mpz_init(n);
  70   mpz_mul(n, key->p, key->q);
  71
  72   key->size = _rsa_check_size(n);
  73
  74   mpz_clear(n);
  75
  76   return (key->size > 0);
  77 }
  78
  79 /* Computing an rsa root. */
  80 void
  81 rsa_compute_root(const struct rsa_private_key *key,
  82                  mpz_t x, const mpz_t m)
  83 {
  84   mpz_t xp; /* modulo p */
  85   mpz_t xq; /* modulo q */
  86
  87   mpz_init(xp); mpz_init(xq);
  88
  89   /* Compute xq = m^d % q = (m%q)^b % q */
  90   mpz_fdiv_r(xq, m, key->q);
  91   mpz_powm(xq, xq, key->b, key->q);
  92
  93   /* Compute xp = m^d % p = (m%p)^a % p */
  94   mpz_fdiv_r(xp, m, key->p);
  95   mpz_powm(xp, xp, key->a, key->p);
  96
  97   /* Set xp' = (xp - xq) c % p. */
  98   mpz_sub(xp, xp, xq);
  99   mpz_mul(xp, xp, key->c);
 100   mpz_fdiv_r(xp, xp, key->p);
 101
 102   /* Finally, compute x = xq + q xp'
 103    *
 104    * To prove that this works, note that
 105    *
 106    *   xp  = x + i p,
 107    *   xq  = x + j q,
 108    *   c q = 1 + k p
 109    *
 110    * for some integers i, j and k. Now, for some integer l,
 111    *
 112    *   xp' = (xp - xq) c + l p
 113    *       = (x + i p - (x + j q)) c + l p
 114    *       = (i p - j q) c + l p
 115    *       = (i c + l) p - j (c q)
 116    *       = (i c + l) p - j (1 + kp)
 117    *       = (i c + l - j k) p - j
 118    *
 119    * which shows that xp' = -j (mod p). We get
 120    *
 121    *   xq + q xp' = x + j q + (i c + l - j k) p q - j q
 122    *              = x + (i c + l - j k) p q
 123    *
 124    * so that
 125    *
 126    *   xq + q xp' = x (mod pq)
 127    *
 128    * We also get 0 <= xq + q xp' < p q, because
 129    *
 130    *   0 <= xq < q and 0 <= xp' < p.
 131    */
 132   mpz_mul(x, key->q, xp);
 133   mpz_add(x, x, xq);
 134
 135   mpz_clear(xp); mpz_clear(xq);
 136 }