aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/linden/indra/libgcrypt/libgcrypt-1.2.2/cipher/rsa.c
diff options
context:
space:
mode:
Diffstat (limited to 'linden/indra/libgcrypt/libgcrypt-1.2.2/cipher/rsa.c')
-rw-r--r--[-rwxr-xr-x]linden/indra/libgcrypt/libgcrypt-1.2.2/cipher/rsa.c1264
1 files changed, 632 insertions, 632 deletions
diff --git a/linden/indra/libgcrypt/libgcrypt-1.2.2/cipher/rsa.c b/linden/indra/libgcrypt/libgcrypt-1.2.2/cipher/rsa.c
index 4738f43..9cceba2 100755..100644
--- a/linden/indra/libgcrypt/libgcrypt-1.2.2/cipher/rsa.c
+++ b/linden/indra/libgcrypt/libgcrypt-1.2.2/cipher/rsa.c
@@ -1,632 +1,632 @@
1/* rsa.c - RSA function 1/* rsa.c - RSA function
2 * Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn) 2 * Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
3 * Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc. 3 * Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
4 * 4 *
5 * This file is part of Libgcrypt. 5 * This file is part of Libgcrypt.
6 * 6 *
7 * Libgcrypt is free software; you can redistribute it and/or modify 7 * Libgcrypt is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU Lesser General Public License as 8 * it under the terms of the GNU Lesser General Public License as
9 * published by the Free Software Foundation; either version 2.1 of 9 * published by the Free Software Foundation; either version 2.1 of
10 * the License, or (at your option) any later version. 10 * the License, or (at your option) any later version.
11 * 11 *
12 * Libgcrypt is distributed in the hope that it will be useful, 12 * Libgcrypt is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU Lesser General Public License for more details. 15 * GNU Lesser General Public License for more details.
16 * 16 *
17 * You should have received a copy of the GNU Lesser General Public 17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this program; if not, write to the Free Software 18 * License along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
20 */ 20 */
21 21
22/* This code uses an algorithm protected by U.S. Patent #4,405,829 22/* This code uses an algorithm protected by U.S. Patent #4,405,829
23 which expired on September 20, 2000. The patent holder placed that 23 which expired on September 20, 2000. The patent holder placed that
24 patent into the public domain on Sep 6th, 2000. 24 patent into the public domain on Sep 6th, 2000.
25*/ 25*/
26 26
27#include <config.h> 27#include <config.h>
28#include <stdio.h> 28#include <stdio.h>
29#include <stdlib.h> 29#include <stdlib.h>
30#include <string.h> 30#include <string.h>
31#include "g10lib.h" 31#include "g10lib.h"
32#include "mpi.h" 32#include "mpi.h"
33#include "cipher.h" 33#include "cipher.h"
34 34
35 35
36typedef struct 36typedef struct
37{ 37{
38 gcry_mpi_t n; /* modulus */ 38 gcry_mpi_t n; /* modulus */
39 gcry_mpi_t e; /* exponent */ 39 gcry_mpi_t e; /* exponent */
40} RSA_public_key; 40} RSA_public_key;
41 41
42 42
43typedef struct 43typedef struct
44{ 44{
45 gcry_mpi_t n; /* public modulus */ 45 gcry_mpi_t n; /* public modulus */
46 gcry_mpi_t e; /* public exponent */ 46 gcry_mpi_t e; /* public exponent */
47 gcry_mpi_t d; /* exponent */ 47 gcry_mpi_t d; /* exponent */
48 gcry_mpi_t p; /* prime p. */ 48 gcry_mpi_t p; /* prime p. */
49 gcry_mpi_t q; /* prime q. */ 49 gcry_mpi_t q; /* prime q. */
50 gcry_mpi_t u; /* inverse of p mod q. */ 50 gcry_mpi_t u; /* inverse of p mod q. */
51} RSA_secret_key; 51} RSA_secret_key;
52 52
53 53
54static void test_keys (RSA_secret_key *sk, unsigned nbits); 54static void test_keys (RSA_secret_key *sk, unsigned nbits);
55static void generate (RSA_secret_key *sk, 55static void generate (RSA_secret_key *sk,
56 unsigned int nbits, unsigned long use_e); 56 unsigned int nbits, unsigned long use_e);
57static int check_secret_key (RSA_secret_key *sk); 57static int check_secret_key (RSA_secret_key *sk);
58static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey); 58static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey);
59static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey); 59static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey);
60 60
61 61
62static void 62static void
63test_keys( RSA_secret_key *sk, unsigned nbits ) 63test_keys( RSA_secret_key *sk, unsigned nbits )
64{ 64{
65 RSA_public_key pk; 65 RSA_public_key pk;
66 gcry_mpi_t test = gcry_mpi_new ( nbits ); 66 gcry_mpi_t test = gcry_mpi_new ( nbits );
67 gcry_mpi_t out1 = gcry_mpi_new ( nbits ); 67 gcry_mpi_t out1 = gcry_mpi_new ( nbits );
68 gcry_mpi_t out2 = gcry_mpi_new ( nbits ); 68 gcry_mpi_t out2 = gcry_mpi_new ( nbits );
69 69
70 pk.n = sk->n; 70 pk.n = sk->n;
71 pk.e = sk->e; 71 pk.e = sk->e;
72 gcry_mpi_randomize( test, nbits, GCRY_WEAK_RANDOM ); 72 gcry_mpi_randomize( test, nbits, GCRY_WEAK_RANDOM );
73 73
74 public( out1, test, &pk ); 74 public( out1, test, &pk );
75 secret( out2, out1, sk ); 75 secret( out2, out1, sk );
76 if( mpi_cmp( test, out2 ) ) 76 if( mpi_cmp( test, out2 ) )
77 log_fatal("RSA operation: public, secret failed\n"); 77 log_fatal("RSA operation: public, secret failed\n");
78 secret( out1, test, sk ); 78 secret( out1, test, sk );
79 public( out2, out1, &pk ); 79 public( out2, out1, &pk );
80 if( mpi_cmp( test, out2 ) ) 80 if( mpi_cmp( test, out2 ) )
81 log_fatal("RSA operation: secret, public failed\n"); 81 log_fatal("RSA operation: secret, public failed\n");
82 gcry_mpi_release ( test ); 82 gcry_mpi_release ( test );
83 gcry_mpi_release ( out1 ); 83 gcry_mpi_release ( out1 );
84 gcry_mpi_release ( out2 ); 84 gcry_mpi_release ( out2 );
85} 85}
86 86
87 87
88/* Callback used by the prime generation to test whether the exponent 88/* Callback used by the prime generation to test whether the exponent
89 is suitable. Returns 0 if the test has been passed. */ 89 is suitable. Returns 0 if the test has been passed. */
90static int 90static int
91check_exponent (void *arg, gcry_mpi_t a) 91check_exponent (void *arg, gcry_mpi_t a)
92{ 92{
93 gcry_mpi_t e = arg; 93 gcry_mpi_t e = arg;
94 gcry_mpi_t tmp; 94 gcry_mpi_t tmp;
95 int result; 95 int result;
96 96
97 mpi_sub_ui (a, a, 1); 97 mpi_sub_ui (a, a, 1);
98 tmp = _gcry_mpi_alloc_like (a); 98 tmp = _gcry_mpi_alloc_like (a);
99 result = !gcry_mpi_gcd(tmp, e, a); /* GCD is not 1. */ 99 result = !gcry_mpi_gcd(tmp, e, a); /* GCD is not 1. */
100 gcry_mpi_release (tmp); 100 gcry_mpi_release (tmp);
101 mpi_add_ui (a, a, 1); 101 mpi_add_ui (a, a, 1);
102 return result; 102 return result;
103} 103}
104 104
105/**************** 105/****************
106 * Generate a key pair with a key of size NBITS. 106 * Generate a key pair with a key of size NBITS.
107 * USE_E = 0 let Libcgrypt decide what exponent to use. 107 * USE_E = 0 let Libcgrypt decide what exponent to use.
108 * = 1 request the use of a "secure" exponent; this is required by some 108 * = 1 request the use of a "secure" exponent; this is required by some
109 * specification to be 65537. 109 * specification to be 65537.
110 * > 2 Try starting at this value until a working exponent is found. 110 * > 2 Try starting at this value until a working exponent is found.
111 * Returns: 2 structures filled with all needed values 111 * Returns: 2 structures filled with all needed values
112 */ 112 */
113static void 113static void
114generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e) 114generate (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e)
115{ 115{
116 gcry_mpi_t p, q; /* the two primes */ 116 gcry_mpi_t p, q; /* the two primes */
117 gcry_mpi_t d; /* the private key */ 117 gcry_mpi_t d; /* the private key */
118 gcry_mpi_t u; 118 gcry_mpi_t u;
119 gcry_mpi_t t1, t2; 119 gcry_mpi_t t1, t2;
120 gcry_mpi_t n; /* the public key */ 120 gcry_mpi_t n; /* the public key */
121 gcry_mpi_t e; /* the exponent */ 121 gcry_mpi_t e; /* the exponent */
122 gcry_mpi_t phi; /* helper: (p-1)(q-1) */ 122 gcry_mpi_t phi; /* helper: (p-1)(q-1) */
123 gcry_mpi_t g; 123 gcry_mpi_t g;
124 gcry_mpi_t f; 124 gcry_mpi_t f;
125 125
126 /* make sure that nbits is even so that we generate p, q of equal size */ 126 /* make sure that nbits is even so that we generate p, q of equal size */
127 if ( (nbits&1) ) 127 if ( (nbits&1) )
128 nbits++; 128 nbits++;
129 129
130 if (use_e == 1) /* Alias for a secure value. */ 130 if (use_e == 1) /* Alias for a secure value. */
131 use_e = 65537; /* as demanded by Spinx. */ 131 use_e = 65537; /* as demanded by Spinx. */
132 132
133 /* Public exponent: 133 /* Public exponent:
134 In general we use 41 as this is quite fast and more secure than the 134 In general we use 41 as this is quite fast and more secure than the
135 commonly used 17. Benchmarking the RSA verify function 135 commonly used 17. Benchmarking the RSA verify function
136 with a 1024 bit key yields (2001-11-08): 136 with a 1024 bit key yields (2001-11-08):
137 e=17 0.54 ms 137 e=17 0.54 ms
138 e=41 0.75 ms 138 e=41 0.75 ms
139 e=257 0.95 ms 139 e=257 0.95 ms
140 e=65537 1.80 ms 140 e=65537 1.80 ms
141 */ 141 */
142 e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB ); 142 e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
143 if (!use_e) 143 if (!use_e)
144 mpi_set_ui (e, 41); /* This is a reasonable secure and fast value */ 144 mpi_set_ui (e, 41); /* This is a reasonable secure and fast value */
145 else 145 else
146 { 146 {
147 use_e |= 1; /* make sure this is odd */ 147 use_e |= 1; /* make sure this is odd */
148 mpi_set_ui (e, use_e); 148 mpi_set_ui (e, use_e);
149 } 149 }
150 150
151 n = gcry_mpi_new (nbits); 151 n = gcry_mpi_new (nbits);
152 152
153 p = q = NULL; 153 p = q = NULL;
154 do 154 do
155 { 155 {
156 /* select two (very secret) primes */ 156 /* select two (very secret) primes */
157 if (p) 157 if (p)
158 gcry_mpi_release (p); 158 gcry_mpi_release (p);
159 if (q) 159 if (q)
160 gcry_mpi_release (q); 160 gcry_mpi_release (q);
161 if (use_e) 161 if (use_e)
162 { /* Do an extra test to ensure that the given exponent is 162 { /* Do an extra test to ensure that the given exponent is
163 suitable. */ 163 suitable. */
164 p = _gcry_generate_secret_prime (nbits/2, check_exponent, e); 164 p = _gcry_generate_secret_prime (nbits/2, check_exponent, e);
165 q = _gcry_generate_secret_prime (nbits/2, check_exponent, e); 165 q = _gcry_generate_secret_prime (nbits/2, check_exponent, e);
166 } 166 }
167 else 167 else
168 { /* We check the exponent later. */ 168 { /* We check the exponent later. */
169 p = _gcry_generate_secret_prime (nbits/2, NULL, NULL); 169 p = _gcry_generate_secret_prime (nbits/2, NULL, NULL);
170 q = _gcry_generate_secret_prime (nbits/2, NULL, NULL); 170 q = _gcry_generate_secret_prime (nbits/2, NULL, NULL);
171 } 171 }
172 if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/ 172 if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
173 mpi_swap(p,q); 173 mpi_swap(p,q);
174 /* calculate the modulus */ 174 /* calculate the modulus */
175 mpi_mul( n, p, q ); 175 mpi_mul( n, p, q );
176 } 176 }
177 while ( mpi_get_nbits(n) != nbits ); 177 while ( mpi_get_nbits(n) != nbits );
178 178
179 /* calculate Euler totient: phi = (p-1)(q-1) */ 179 /* calculate Euler totient: phi = (p-1)(q-1) */
180 t1 = mpi_alloc_secure( mpi_get_nlimbs(p) ); 180 t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
181 t2 = mpi_alloc_secure( mpi_get_nlimbs(p) ); 181 t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
182 phi = gcry_mpi_snew ( nbits ); 182 phi = gcry_mpi_snew ( nbits );
183 g = gcry_mpi_snew ( nbits ); 183 g = gcry_mpi_snew ( nbits );
184 f = gcry_mpi_snew ( nbits ); 184 f = gcry_mpi_snew ( nbits );
185 mpi_sub_ui( t1, p, 1 ); 185 mpi_sub_ui( t1, p, 1 );
186 mpi_sub_ui( t2, q, 1 ); 186 mpi_sub_ui( t2, q, 1 );
187 mpi_mul( phi, t1, t2 ); 187 mpi_mul( phi, t1, t2 );
188 gcry_mpi_gcd(g, t1, t2); 188 gcry_mpi_gcd(g, t1, t2);
189 mpi_fdiv_q(f, phi, g); 189 mpi_fdiv_q(f, phi, g);
190 190
191 while (!gcry_mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */ 191 while (!gcry_mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */
192 { 192 {
193 if (use_e) 193 if (use_e)
194 BUG (); /* The prime generator already made sure that we 194 BUG (); /* The prime generator already made sure that we
195 never can get to here. */ 195 never can get to here. */
196 mpi_add_ui (e, e, 2); 196 mpi_add_ui (e, e, 2);
197 } 197 }
198 198
199 /* calculate the secret key d = e^1 mod phi */ 199 /* calculate the secret key d = e^1 mod phi */
200 d = gcry_mpi_snew ( nbits ); 200 d = gcry_mpi_snew ( nbits );
201 mpi_invm(d, e, f ); 201 mpi_invm(d, e, f );
202 /* calculate the inverse of p and q (used for chinese remainder theorem)*/ 202 /* calculate the inverse of p and q (used for chinese remainder theorem)*/
203 u = gcry_mpi_snew ( nbits ); 203 u = gcry_mpi_snew ( nbits );
204 mpi_invm(u, p, q ); 204 mpi_invm(u, p, q );
205 205
206 if( DBG_CIPHER ) 206 if( DBG_CIPHER )
207 { 207 {
208 log_mpidump(" p= ", p ); 208 log_mpidump(" p= ", p );
209 log_mpidump(" q= ", q ); 209 log_mpidump(" q= ", q );
210 log_mpidump("phi= ", phi ); 210 log_mpidump("phi= ", phi );
211 log_mpidump(" g= ", g ); 211 log_mpidump(" g= ", g );
212 log_mpidump(" f= ", f ); 212 log_mpidump(" f= ", f );
213 log_mpidump(" n= ", n ); 213 log_mpidump(" n= ", n );
214 log_mpidump(" e= ", e ); 214 log_mpidump(" e= ", e );
215 log_mpidump(" d= ", d ); 215 log_mpidump(" d= ", d );
216 log_mpidump(" u= ", u ); 216 log_mpidump(" u= ", u );
217 } 217 }
218 218
219 gcry_mpi_release (t1); 219 gcry_mpi_release (t1);
220 gcry_mpi_release (t2); 220 gcry_mpi_release (t2);
221 gcry_mpi_release (phi); 221 gcry_mpi_release (phi);
222 gcry_mpi_release (f); 222 gcry_mpi_release (f);
223 gcry_mpi_release (g); 223 gcry_mpi_release (g);
224 224
225 sk->n = n; 225 sk->n = n;
226 sk->e = e; 226 sk->e = e;
227 sk->p = p; 227 sk->p = p;
228 sk->q = q; 228 sk->q = q;
229 sk->d = d; 229 sk->d = d;
230 sk->u = u; 230 sk->u = u;
231 231
232 /* now we can test our keys (this should never fail!) */ 232 /* now we can test our keys (this should never fail!) */
233 test_keys( sk, nbits - 64 ); 233 test_keys( sk, nbits - 64 );
234} 234}
235 235
236 236
237/**************** 237/****************
238 * Test wether the secret key is valid. 238 * Test wether the secret key is valid.
239 * Returns: true if this is a valid key. 239 * Returns: true if this is a valid key.
240 */ 240 */
241static int 241static int
242check_secret_key( RSA_secret_key *sk ) 242check_secret_key( RSA_secret_key *sk )
243{ 243{
244 int rc; 244 int rc;
245 gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 ); 245 gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
246 246
247 mpi_mul(temp, sk->p, sk->q ); 247 mpi_mul(temp, sk->p, sk->q );
248 rc = mpi_cmp( temp, sk->n ); 248 rc = mpi_cmp( temp, sk->n );
249 mpi_free(temp); 249 mpi_free(temp);
250 return !rc; 250 return !rc;
251} 251}
252 252
253 253
254 254
255/**************** 255/****************
256 * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT. 256 * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
257 * 257 *
258 * c = m^e mod n 258 * c = m^e mod n
259 * 259 *
260 * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY. 260 * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
261 */ 261 */
262static void 262static void
263public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey ) 263public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
264{ 264{
265 if( output == input ) /* powm doesn't like output and input the same */ 265 if( output == input ) /* powm doesn't like output and input the same */
266 { 266 {
267 gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 ); 267 gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
268 mpi_powm( x, input, pkey->e, pkey->n ); 268 mpi_powm( x, input, pkey->e, pkey->n );
269 mpi_set(output, x); 269 mpi_set(output, x);
270 mpi_free(x); 270 mpi_free(x);
271 } 271 }
272 else 272 else
273 mpi_powm( output, input, pkey->e, pkey->n ); 273 mpi_powm( output, input, pkey->e, pkey->n );
274} 274}
275 275
276#if 0 276#if 0
277static void 277static void
278stronger_key_check ( RSA_secret_key *skey ) 278stronger_key_check ( RSA_secret_key *skey )
279{ 279{
280 gcry_mpi_t t = mpi_alloc_secure ( 0 ); 280 gcry_mpi_t t = mpi_alloc_secure ( 0 );
281 gcry_mpi_t t1 = mpi_alloc_secure ( 0 ); 281 gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
282 gcry_mpi_t t2 = mpi_alloc_secure ( 0 ); 282 gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
283 gcry_mpi_t phi = mpi_alloc_secure ( 0 ); 283 gcry_mpi_t phi = mpi_alloc_secure ( 0 );
284 284
285 /* check that n == p * q */ 285 /* check that n == p * q */
286 mpi_mul( t, skey->p, skey->q); 286 mpi_mul( t, skey->p, skey->q);
287 if (mpi_cmp( t, skey->n) ) 287 if (mpi_cmp( t, skey->n) )
288 log_info ( "RSA Oops: n != p * q\n" ); 288 log_info ( "RSA Oops: n != p * q\n" );
289 289
290 /* check that p is less than q */ 290 /* check that p is less than q */
291 if( mpi_cmp( skey->p, skey->q ) > 0 ) 291 if( mpi_cmp( skey->p, skey->q ) > 0 )
292 { 292 {
293 log_info ("RSA Oops: p >= q - fixed\n"); 293 log_info ("RSA Oops: p >= q - fixed\n");
294 _gcry_mpi_swap ( skey->p, skey->q); 294 _gcry_mpi_swap ( skey->p, skey->q);
295 } 295 }
296 296
297 /* check that e divides neither p-1 nor q-1 */ 297 /* check that e divides neither p-1 nor q-1 */
298 mpi_sub_ui(t, skey->p, 1 ); 298 mpi_sub_ui(t, skey->p, 1 );
299 mpi_fdiv_r(t, t, skey->e ); 299 mpi_fdiv_r(t, t, skey->e );
300 if ( !mpi_cmp_ui( t, 0) ) 300 if ( !mpi_cmp_ui( t, 0) )
301 log_info ( "RSA Oops: e divides p-1\n" ); 301 log_info ( "RSA Oops: e divides p-1\n" );
302 mpi_sub_ui(t, skey->q, 1 ); 302 mpi_sub_ui(t, skey->q, 1 );
303 mpi_fdiv_r(t, t, skey->e ); 303 mpi_fdiv_r(t, t, skey->e );
304 if ( !mpi_cmp_ui( t, 0) ) 304 if ( !mpi_cmp_ui( t, 0) )
305 log_info ( "RSA Oops: e divides q-1\n" ); 305 log_info ( "RSA Oops: e divides q-1\n" );
306 306
307 /* check that d is correct */ 307 /* check that d is correct */
308 mpi_sub_ui( t1, skey->p, 1 ); 308 mpi_sub_ui( t1, skey->p, 1 );
309 mpi_sub_ui( t2, skey->q, 1 ); 309 mpi_sub_ui( t2, skey->q, 1 );
310 mpi_mul( phi, t1, t2 ); 310 mpi_mul( phi, t1, t2 );
311 gcry_mpi_gcd(t, t1, t2); 311 gcry_mpi_gcd(t, t1, t2);
312 mpi_fdiv_q(t, phi, t); 312 mpi_fdiv_q(t, phi, t);
313 mpi_invm(t, skey->e, t ); 313 mpi_invm(t, skey->e, t );
314 if ( mpi_cmp(t, skey->d ) ) 314 if ( mpi_cmp(t, skey->d ) )
315 { 315 {
316 log_info ( "RSA Oops: d is wrong - fixed\n"); 316 log_info ( "RSA Oops: d is wrong - fixed\n");
317 mpi_set (skey->d, t); 317 mpi_set (skey->d, t);
318 _gcry_log_mpidump (" fixed d", skey->d); 318 _gcry_log_mpidump (" fixed d", skey->d);
319 } 319 }
320 320
321 /* check for correctness of u */ 321 /* check for correctness of u */
322 mpi_invm(t, skey->p, skey->q ); 322 mpi_invm(t, skey->p, skey->q );
323 if ( mpi_cmp(t, skey->u ) ) 323 if ( mpi_cmp(t, skey->u ) )
324 { 324 {
325 log_info ( "RSA Oops: u is wrong - fixed\n"); 325 log_info ( "RSA Oops: u is wrong - fixed\n");
326 mpi_set (skey->u, t); 326 mpi_set (skey->u, t);
327 _gcry_log_mpidump (" fixed u", skey->u); 327 _gcry_log_mpidump (" fixed u", skey->u);
328 } 328 }
329 329
330 log_info ( "RSA secret key check finished\n"); 330 log_info ( "RSA secret key check finished\n");
331 331
332 mpi_free (t); 332 mpi_free (t);
333 mpi_free (t1); 333 mpi_free (t1);
334 mpi_free (t2); 334 mpi_free (t2);
335 mpi_free (phi); 335 mpi_free (phi);
336} 336}
337#endif 337#endif
338 338
339 339
340 340
341/**************** 341/****************
342 * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT. 342 * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
343 * 343 *
344 * m = c^d mod n 344 * m = c^d mod n
345 * 345 *
346 * Or faster: 346 * Or faster:
347 * 347 *
348 * m1 = c ^ (d mod (p-1)) mod p 348 * m1 = c ^ (d mod (p-1)) mod p
349 * m2 = c ^ (d mod (q-1)) mod q 349 * m2 = c ^ (d mod (q-1)) mod q
350 * h = u * (m2 - m1) mod q 350 * h = u * (m2 - m1) mod q
351 * m = m1 + h * p 351 * m = m1 + h * p
352 * 352 *
353 * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY. 353 * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
354 */ 354 */
355static void 355static void
356secret(gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey ) 356secret(gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
357{ 357{
358 if (!skey->p && !skey->q && !skey->u) 358 if (!skey->p && !skey->q && !skey->u)
359 { 359 {
360 mpi_powm (output, input, skey->d, skey->n); 360 mpi_powm (output, input, skey->d, skey->n);
361 } 361 }
362 else 362 else
363 { 363 {
364 gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); 364 gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
365 gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); 365 gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
366 gcry_mpi_t h = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); 366 gcry_mpi_t h = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
367 367
368 /* m1 = c ^ (d mod (p-1)) mod p */ 368 /* m1 = c ^ (d mod (p-1)) mod p */
369 mpi_sub_ui( h, skey->p, 1 ); 369 mpi_sub_ui( h, skey->p, 1 );
370 mpi_fdiv_r( h, skey->d, h ); 370 mpi_fdiv_r( h, skey->d, h );
371 mpi_powm( m1, input, h, skey->p ); 371 mpi_powm( m1, input, h, skey->p );
372 /* m2 = c ^ (d mod (q-1)) mod q */ 372 /* m2 = c ^ (d mod (q-1)) mod q */
373 mpi_sub_ui( h, skey->q, 1 ); 373 mpi_sub_ui( h, skey->q, 1 );
374 mpi_fdiv_r( h, skey->d, h ); 374 mpi_fdiv_r( h, skey->d, h );
375 mpi_powm( m2, input, h, skey->q ); 375 mpi_powm( m2, input, h, skey->q );
376 /* h = u * ( m2 - m1 ) mod q */ 376 /* h = u * ( m2 - m1 ) mod q */
377 mpi_sub( h, m2, m1 ); 377 mpi_sub( h, m2, m1 );
378 if ( mpi_is_neg( h ) ) 378 if ( mpi_is_neg( h ) )
379 mpi_add ( h, h, skey->q ); 379 mpi_add ( h, h, skey->q );
380 mpi_mulm( h, skey->u, h, skey->q ); 380 mpi_mulm( h, skey->u, h, skey->q );
381 /* m = m2 + h * p */ 381 /* m = m2 + h * p */
382 mpi_mul ( h, h, skey->p ); 382 mpi_mul ( h, h, skey->p );
383 mpi_add ( output, m1, h ); 383 mpi_add ( output, m1, h );
384 384
385 mpi_free ( h ); 385 mpi_free ( h );
386 mpi_free ( m1 ); 386 mpi_free ( m1 );
387 mpi_free ( m2 ); 387 mpi_free ( m2 );
388 } 388 }
389} 389}
390 390
391 391
392 392
393/* Perform RSA blinding. */ 393/* Perform RSA blinding. */
394static gcry_mpi_t 394static gcry_mpi_t
395rsa_blind (gcry_mpi_t x, gcry_mpi_t r, gcry_mpi_t e, gcry_mpi_t n) 395rsa_blind (gcry_mpi_t x, gcry_mpi_t r, gcry_mpi_t e, gcry_mpi_t n)
396{ 396{
397 /* A helper. */ 397 /* A helper. */
398 gcry_mpi_t a; 398 gcry_mpi_t a;
399 399
400 /* Result. */ 400 /* Result. */
401 gcry_mpi_t y; 401 gcry_mpi_t y;
402 402
403 a = gcry_mpi_snew (gcry_mpi_get_nbits (n)); 403 a = gcry_mpi_snew (gcry_mpi_get_nbits (n));
404 y = gcry_mpi_snew (gcry_mpi_get_nbits (n)); 404 y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
405 405
406 /* Now we calculate: y = (x * r^e) mod n, where r is the random 406 /* Now we calculate: y = (x * r^e) mod n, where r is the random
407 number, e is the public exponent, x is the non-blinded data and n 407 number, e is the public exponent, x is the non-blinded data and n
408 is the RSA modulus. */ 408 is the RSA modulus. */
409 gcry_mpi_powm (a, r, e, n); 409 gcry_mpi_powm (a, r, e, n);
410 gcry_mpi_mulm (y, a, x, n); 410 gcry_mpi_mulm (y, a, x, n);
411 411
412 gcry_mpi_release (a); 412 gcry_mpi_release (a);
413 413
414 return y; 414 return y;
415} 415}
416 416
417/* Undo RSA blinding. */ 417/* Undo RSA blinding. */
418static gcry_mpi_t 418static gcry_mpi_t
419rsa_unblind (gcry_mpi_t x, gcry_mpi_t ri, gcry_mpi_t n) 419rsa_unblind (gcry_mpi_t x, gcry_mpi_t ri, gcry_mpi_t n)
420{ 420{
421 gcry_mpi_t y; 421 gcry_mpi_t y;
422 422
423 y = gcry_mpi_snew (gcry_mpi_get_nbits (n)); 423 y = gcry_mpi_snew (gcry_mpi_get_nbits (n));
424 424
425 /* Here we calculate: y = (x * r^-1) mod n, where x is the blinded 425 /* Here we calculate: y = (x * r^-1) mod n, where x is the blinded
426 decrypted data, ri is the modular multiplicative inverse of r and 426 decrypted data, ri is the modular multiplicative inverse of r and
427 n is the RSA modulus. */ 427 n is the RSA modulus. */
428 428
429 gcry_mpi_mulm (y, ri, x, n); 429 gcry_mpi_mulm (y, ri, x, n);
430 430
431 return y; 431 return y;
432} 432}
433 433
434/********************************************* 434/*********************************************
435 ************** interface ****************** 435 ************** interface ******************
436 *********************************************/ 436 *********************************************/
437 437
438gcry_err_code_t 438gcry_err_code_t
439_gcry_rsa_generate (int algo, unsigned int nbits, unsigned long use_e, 439_gcry_rsa_generate (int algo, unsigned int nbits, unsigned long use_e,
440 gcry_mpi_t *skey, gcry_mpi_t **retfactors) 440 gcry_mpi_t *skey, gcry_mpi_t **retfactors)
441{ 441{
442 RSA_secret_key sk; 442 RSA_secret_key sk;
443 443
444 generate (&sk, nbits, use_e); 444 generate (&sk, nbits, use_e);
445 skey[0] = sk.n; 445 skey[0] = sk.n;
446 skey[1] = sk.e; 446 skey[1] = sk.e;
447 skey[2] = sk.d; 447 skey[2] = sk.d;
448 skey[3] = sk.p; 448 skey[3] = sk.p;
449 skey[4] = sk.q; 449 skey[4] = sk.q;
450 skey[5] = sk.u; 450 skey[5] = sk.u;
451 451
452 /* make an empty list of factors */ 452 /* make an empty list of factors */
453 *retfactors = gcry_xcalloc( 1, sizeof **retfactors ); 453 *retfactors = gcry_xcalloc( 1, sizeof **retfactors );
454 454
455 return GPG_ERR_NO_ERROR; 455 return GPG_ERR_NO_ERROR;
456} 456}
457 457
458 458
459gcry_err_code_t 459gcry_err_code_t
460_gcry_rsa_check_secret_key( int algo, gcry_mpi_t *skey ) 460_gcry_rsa_check_secret_key( int algo, gcry_mpi_t *skey )
461{ 461{
462 gcry_err_code_t err = GPG_ERR_NO_ERROR; 462 gcry_err_code_t err = GPG_ERR_NO_ERROR;
463 RSA_secret_key sk; 463 RSA_secret_key sk;
464 464
465 sk.n = skey[0]; 465 sk.n = skey[0];
466 sk.e = skey[1]; 466 sk.e = skey[1];
467 sk.d = skey[2]; 467 sk.d = skey[2];
468 sk.p = skey[3]; 468 sk.p = skey[3];
469 sk.q = skey[4]; 469 sk.q = skey[4];
470 sk.u = skey[5]; 470 sk.u = skey[5];
471 471
472 if (! check_secret_key (&sk)) 472 if (! check_secret_key (&sk))
473 err = GPG_ERR_PUBKEY_ALGO; 473 err = GPG_ERR_PUBKEY_ALGO;
474 474
475 return err; 475 return err;
476} 476}
477 477
478 478
479gcry_err_code_t 479gcry_err_code_t
480_gcry_rsa_encrypt (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, 480_gcry_rsa_encrypt (int algo, gcry_mpi_t *resarr, gcry_mpi_t data,
481 gcry_mpi_t *pkey, int flags) 481 gcry_mpi_t *pkey, int flags)
482{ 482{
483 RSA_public_key pk; 483 RSA_public_key pk;
484 484
485 pk.n = pkey[0]; 485 pk.n = pkey[0];
486 pk.e = pkey[1]; 486 pk.e = pkey[1];
487 resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.n)); 487 resarr[0] = mpi_alloc (mpi_get_nlimbs (pk.n));
488 public (resarr[0], data, &pk); 488 public (resarr[0], data, &pk);
489 489
490 return GPG_ERR_NO_ERROR; 490 return GPG_ERR_NO_ERROR;
491} 491}
492 492
493gcry_err_code_t 493gcry_err_code_t
494_gcry_rsa_decrypt (int algo, gcry_mpi_t *result, gcry_mpi_t *data, 494_gcry_rsa_decrypt (int algo, gcry_mpi_t *result, gcry_mpi_t *data,
495 gcry_mpi_t *skey, int flags) 495 gcry_mpi_t *skey, int flags)
496{ 496{
497 RSA_secret_key sk; 497 RSA_secret_key sk;
498 gcry_mpi_t r = MPI_NULL; /* Random number needed for blinding. */ 498 gcry_mpi_t r = MPI_NULL; /* Random number needed for blinding. */
499 gcry_mpi_t ri = MPI_NULL; /* Modular multiplicative inverse of 499 gcry_mpi_t ri = MPI_NULL; /* Modular multiplicative inverse of
500 r. */ 500 r. */
501 gcry_mpi_t x = MPI_NULL; /* Data to decrypt. */ 501 gcry_mpi_t x = MPI_NULL; /* Data to decrypt. */
502 gcry_mpi_t y; /* Result. */ 502 gcry_mpi_t y; /* Result. */
503 503
504 /* Extract private key. */ 504 /* Extract private key. */
505 sk.n = skey[0]; 505 sk.n = skey[0];
506 sk.e = skey[1]; 506 sk.e = skey[1];
507 sk.d = skey[2]; 507 sk.d = skey[2];
508 sk.p = skey[3]; 508 sk.p = skey[3];
509 sk.q = skey[4]; 509 sk.q = skey[4];
510 sk.u = skey[5]; 510 sk.u = skey[5];
511 511
512 y = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n)); 512 y = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
513 513
514 if (! (flags & PUBKEY_FLAG_NO_BLINDING)) 514 if (! (flags & PUBKEY_FLAG_NO_BLINDING))
515 { 515 {
516 /* Initialize blinding. */ 516 /* Initialize blinding. */
517 517
518 /* First, we need a random number r between 0 and n - 1, which 518 /* First, we need a random number r between 0 and n - 1, which
519 is relatively prime to n (i.e. it is neither p nor q). */ 519 is relatively prime to n (i.e. it is neither p nor q). */
520 r = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n)); 520 r = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
521 ri = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n)); 521 ri = gcry_mpi_snew (gcry_mpi_get_nbits (sk.n));
522 522
523 gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n), 523 gcry_mpi_randomize (r, gcry_mpi_get_nbits (sk.n),
524 GCRY_STRONG_RANDOM); 524 GCRY_STRONG_RANDOM);
525 gcry_mpi_mod (r, r, sk.n); 525 gcry_mpi_mod (r, r, sk.n);
526 526
527 /* Actually it should be okay to skip the check for equality 527 /* Actually it should be okay to skip the check for equality
528 with either p or q here. */ 528 with either p or q here. */
529 529
530 /* Calculate inverse of r. */ 530 /* Calculate inverse of r. */
531 if (! gcry_mpi_invm (ri, r, sk.n)) 531 if (! gcry_mpi_invm (ri, r, sk.n))
532 BUG (); 532 BUG ();
533 } 533 }
534 534
535 if (! (flags & PUBKEY_FLAG_NO_BLINDING)) 535 if (! (flags & PUBKEY_FLAG_NO_BLINDING))
536 x = rsa_blind (data[0], r, sk.e, sk.n); 536 x = rsa_blind (data[0], r, sk.e, sk.n);
537 else 537 else
538 x = data[0]; 538 x = data[0];
539 539
540 /* Do the encryption. */ 540 /* Do the encryption. */
541 secret (y, x, &sk); 541 secret (y, x, &sk);
542 542
543 if (! (flags & PUBKEY_FLAG_NO_BLINDING)) 543 if (! (flags & PUBKEY_FLAG_NO_BLINDING))
544 { 544 {
545 /* Undo blinding. */ 545 /* Undo blinding. */
546 gcry_mpi_t a = gcry_mpi_copy (y); 546 gcry_mpi_t a = gcry_mpi_copy (y);
547 547
548 gcry_mpi_release (y); 548 gcry_mpi_release (y);
549 y = rsa_unblind (a, ri, sk.n); 549 y = rsa_unblind (a, ri, sk.n);
550 550
551 gcry_mpi_release (a); 551 gcry_mpi_release (a);
552 } 552 }
553 553
554 if (! (flags & PUBKEY_FLAG_NO_BLINDING)) 554 if (! (flags & PUBKEY_FLAG_NO_BLINDING))
555 { 555 {
556 /* Deallocate resources needed for blinding. */ 556 /* Deallocate resources needed for blinding. */
557 gcry_mpi_release (x); 557 gcry_mpi_release (x);
558 gcry_mpi_release (r); 558 gcry_mpi_release (r);
559 gcry_mpi_release (ri); 559 gcry_mpi_release (ri);
560 } 560 }
561 561
562 /* Copy out result. */ 562 /* Copy out result. */
563 *result = y; 563 *result = y;
564 564
565 return GPG_ERR_NO_ERROR; 565 return GPG_ERR_NO_ERROR;
566} 566}
567 567
568gcry_err_code_t 568gcry_err_code_t
569_gcry_rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey) 569_gcry_rsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
570{ 570{
571 RSA_secret_key sk; 571 RSA_secret_key sk;
572 572
573 sk.n = skey[0]; 573 sk.n = skey[0];
574 sk.e = skey[1]; 574 sk.e = skey[1];
575 sk.d = skey[2]; 575 sk.d = skey[2];
576 sk.p = skey[3]; 576 sk.p = skey[3];
577 sk.q = skey[4]; 577 sk.q = skey[4];
578 sk.u = skey[5]; 578 sk.u = skey[5];
579 resarr[0] = mpi_alloc( mpi_get_nlimbs (sk.n)); 579 resarr[0] = mpi_alloc( mpi_get_nlimbs (sk.n));
580 secret (resarr[0], data, &sk); 580 secret (resarr[0], data, &sk);
581 581
582 return GPG_ERR_NO_ERROR; 582 return GPG_ERR_NO_ERROR;
583} 583}
584 584
585gcry_err_code_t 585gcry_err_code_t
586_gcry_rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey, 586_gcry_rsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
587 int (*cmp) (void *opaque, gcry_mpi_t tmp), 587 int (*cmp) (void *opaque, gcry_mpi_t tmp),
588 void *opaquev) 588 void *opaquev)
589{ 589{
590 RSA_public_key pk; 590 RSA_public_key pk;
591 gcry_mpi_t result; 591 gcry_mpi_t result;
592 gcry_err_code_t rc; 592 gcry_err_code_t rc;
593 593
594 pk.n = pkey[0]; 594 pk.n = pkey[0];
595 pk.e = pkey[1]; 595 pk.e = pkey[1];
596 result = gcry_mpi_new ( 160 ); 596 result = gcry_mpi_new ( 160 );
597 public( result, data[0], &pk ); 597 public( result, data[0], &pk );
598 /*rc = (*cmp)( opaquev, result );*/ 598 /*rc = (*cmp)( opaquev, result );*/
599 rc = mpi_cmp (result, hash) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR; 599 rc = mpi_cmp (result, hash) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
600 gcry_mpi_release (result); 600 gcry_mpi_release (result);
601 601
602 return rc; 602 return rc;
603} 603}
604 604
605 605
606unsigned int 606unsigned int
607_gcry_rsa_get_nbits (int algo, gcry_mpi_t *pkey) 607_gcry_rsa_get_nbits (int algo, gcry_mpi_t *pkey)
608{ 608{
609 return mpi_get_nbits (pkey[0]); 609 return mpi_get_nbits (pkey[0]);
610} 610}
611 611
612static char *rsa_names[] = 612static char *rsa_names[] =
613 { 613 {
614 "rsa", 614 "rsa",
615 "openpgp-rsa", 615 "openpgp-rsa",
616 "oid.1.2.840.113549.1.1.1", 616 "oid.1.2.840.113549.1.1.1",
617 NULL, 617 NULL,
618 }; 618 };
619 619
620gcry_pk_spec_t _gcry_pubkey_spec_rsa = 620gcry_pk_spec_t _gcry_pubkey_spec_rsa =
621 { 621 {
622 "RSA", rsa_names, 622 "RSA", rsa_names,
623 "ne", "nedpqu", "a", "s", "n", 623 "ne", "nedpqu", "a", "s", "n",
624 GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR, 624 GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR,
625 _gcry_rsa_generate, 625 _gcry_rsa_generate,
626 _gcry_rsa_check_secret_key, 626 _gcry_rsa_check_secret_key,
627 _gcry_rsa_encrypt, 627 _gcry_rsa_encrypt,
628 _gcry_rsa_decrypt, 628 _gcry_rsa_decrypt,
629 _gcry_rsa_sign, 629 _gcry_rsa_sign,
630 _gcry_rsa_verify, 630 _gcry_rsa_verify,
631 _gcry_rsa_get_nbits, 631 _gcry_rsa_get_nbits,
632 }; 632 };
generated by cgit v1.1 at 2025-02-16 05:19:25 +0000