nettle  3.7.3
About: Nettle is a low-level cryptographic library.
  Fossies Dox: nettle-3.7.3.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

rsa-sign.c
Go to the documentation of this file.
1 /* rsa-sign.c
2 
3  Creating RSA signatures.
4 
5  Copyright (C) 2001, 2003 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 #if HAVE_CONFIG_H
35 # include "config.h"
36 #endif
37 
38 #include <assert.h>
39 
40 #include "rsa.h"
41 #include "rsa-internal.h"
42 #include "gmp-glue.h"
43 
44 void
46 {
47  mpz_init(key->d);
48  mpz_init(key->p);
49  mpz_init(key->q);
50  mpz_init(key->a);
51  mpz_init(key->b);
52  mpz_init(key->c);
53 
54  /* Not really necessary, but it seems cleaner to initialize all the
55  * storage. */
56  key->size = 0;
57 }
58 
59 void
61 {
62  mpz_clear(key->d);
63  mpz_clear(key->p);
64  mpz_clear(key->q);
65  mpz_clear(key->a);
66  mpz_clear(key->b);
67  mpz_clear(key->c);
68 }
69 
70 int
72 {
73  mpz_t n;
74 
75  /* A key is invalid if the sizes of q and c are smaller than
76  * the size of n, we rely on that property in calculations so
77  * fail early if that happens. */
78  if (mpz_size (key->q) + mpz_size (key->c) < mpz_size(key->p))
79  return 0;
80 
81  /* The size of the product is the sum of the sizes of the factors,
82  * or sometimes one less. It's possible but tricky to compute the
83  * size without computing the full product. */
84 
85  mpz_init(n);
86  mpz_mul(n, key->p, key->q);
87 
88  key->size = _rsa_check_size(n);
89 
90  mpz_clear(n);
91 
92  return (key->size > 0);
93 }
94 
95 #if NETTLE_USE_MINI_GMP
96 
97 /* Computing an rsa root. */
98 void
99 rsa_compute_root(const struct rsa_private_key *key,
100  mpz_t x, const mpz_t m)
101 {
102  mpz_t xp; /* modulo p */
103  mpz_t xq; /* modulo q */
104 
105  mpz_init(xp); mpz_init(xq);
106 
107  /* Compute xq = m^d % q = (m%q)^b % q */
108  mpz_fdiv_r(xq, m, key->q);
109  mpz_powm_sec(xq, xq, key->b, key->q);
110 
111  /* Compute xp = m^d % p = (m%p)^a % p */
112  mpz_fdiv_r(xp, m, key->p);
113  mpz_powm_sec(xp, xp, key->a, key->p);
114 
115  /* Set xp' = (xp - xq) c % p. */
116  mpz_sub(xp, xp, xq);
117  mpz_mul(xp, xp, key->c);
118  mpz_fdiv_r(xp, xp, key->p);
119 
120  /* Finally, compute x = xq + q xp'
121  *
122  * To prove that this works, note that
123  *
124  * xp = x + i p,
125  * xq = x + j q,
126  * c q = 1 + k p
127  *
128  * for some integers i, j and k. Now, for some integer l,
129  *
130  * xp' = (xp - xq) c + l p
131  * = (x + i p - (x + j q)) c + l p
132  * = (i p - j q) c + l p
133  * = (i c + l) p - j (c q)
134  * = (i c + l) p - j (1 + kp)
135  * = (i c + l - j k) p - j
136  *
137  * which shows that xp' = -j (mod p). We get
138  *
139  * xq + q xp' = x + j q + (i c + l - j k) p q - j q
140  * = x + (i c + l - j k) p q
141  *
142  * so that
143  *
144  * xq + q xp' = x (mod pq)
145  *
146  * We also get 0 <= xq + q xp' < p q, because
147  *
148  * 0 <= xq < q and 0 <= xp' < p.
149  */
150  mpz_mul(x, key->q, xp);
151  mpz_add(x, x, xq);
152 
153  mpz_clear(xp); mpz_clear(xq);
154 }
155 
156 #else /* !NETTLE_USE_MINI_GMP */
157 
158 /* Computing an rsa root. */
159 void
161  mpz_t x, const mpz_t m)
162 {
163  TMP_GMP_DECL (scratch, mp_limb_t);
164  TMP_GMP_DECL (ml, mp_limb_t);
165  mp_limb_t *xl;
166  size_t key_size;
167 
168  key_size = NETTLE_OCTET_SIZE_TO_LIMB_SIZE(key->size);
169  assert(mpz_size (m) <= key_size);
170 
171  /* we need a copy because m can be shorter than key_size,
172  * but _rsa_sec_compute_root expect all inputs to be
173  * normalized to a key_size long buffer length */
174  TMP_GMP_ALLOC (ml, key_size);
175  mpz_limbs_copy(ml, m, key_size);
176 
178 
179  xl = mpz_limbs_write (x, key_size);
180  _rsa_sec_compute_root (key, xl, ml, scratch);
181  mpz_limbs_finish (x, key_size);
182 
183  TMP_GMP_FREE (ml);
184  TMP_GMP_FREE (scratch);
185 }
186 #endif /* !NETTLE_USE_MINI_GMP */
#define x
#define xp
#define TMP_GMP_DECL(name, type)
Definition: gmp-glue.h:51
#define NETTLE_OCTET_SIZE_TO_LIMB_SIZE(n)
Definition: gmp-glue.h:72
#define TMP_GMP_FREE(name)
Definition: gmp-glue.h:57
#define TMP_GMP_ALLOC(name, size)
Definition: gmp-glue.h:53
#define mpz_limbs_copy
Definition: gmp-glue.h:40
void mpz_limbs_finish(mpz_t x, mp_size_t xs)
Definition: mini-gmp.c:1662
void mpz_add(mpz_t r, const mpz_t a, const mpz_t b)
Definition: mini-gmp.c:2008
void mpz_init(mpz_t r)
Definition: mini-gmp.c:1410
void mpz_mul(mpz_t r, const mpz_t u, const mpz_t v)
Definition: mini-gmp.c:2058
void mpz_fdiv_r(mpz_t r, const mpz_t n, const mpz_t d)
Definition: mini-gmp.c:2329
void mpz_clear(mpz_t r)
Definition: mini-gmp.c:1435
void mpz_sub(mpz_t r, const mpz_t a, const mpz_t b)
Definition: mini-gmp.c:2021
size_t mpz_size(const mpz_t u)
Definition: mini-gmp.c:1622
mp_ptr mpz_limbs_write(mpz_t x, mp_size_t n)
Definition: mini-gmp.c:1656
__mpz_struct mpz_t[1]
Definition: mini-gmp.h:77
unsigned long mp_limb_t
Definition: mini-gmp.h:60
#define _rsa_sec_compute_root_itch
Definition: rsa-internal.h:44
#define _rsa_check_size
Definition: rsa-internal.h:41
#define _rsa_sec_compute_root
Definition: rsa-internal.h:45
#define rsa_private_key_clear
Definition: rsa.h:53
#define rsa_private_key_init
Definition: rsa.h:52
#define rsa_private_key_prepare
Definition: rsa.h:54
#define rsa_compute_root
Definition: rsa.h:92
mpz_t p
Definition: rsa.h:136
mpz_t d
Definition: rsa.h:133
mpz_t c
Definition: rsa.h:145
size_t size
Definition: rsa.h:129
mpz_t a
Definition: rsa.h:139
mpz_t q
Definition: rsa.h:136
mpz_t b
Definition: rsa.h:142