ElGamal funktioniert und ist default
[libgcrypt.git] / cipher / rsa.c
1 /* rsa.c  -  RSA function
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
3  *
4  * ATTENTION: This code should not be exported from the United States
5  * nor should it be used their without a license agreement with PKP.
6  * The RSA alorithm is protected by U.S. Patent #4,405,829 which
7  * expires on September 20, 2000!
8  *
9  * For a description of the algorithm, see:
10  *   Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
11  *   ISBN 0-471-11709-9. Pages 466 ff.
12  *
13  * This file is part of G10.
14  *
15  * G10 is free software; you can redistribute it and/or modify
16  * it under the terms of the GNU General Public License as published by
17  * the Free Software Foundation; either version 2 of the License, or
18  * (at your option) any later version.
19  *
20  * G10 is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with this program; if not, write to the Free Software
27  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
28  */
29
30 #include <config.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include "util.h"
35 #include "mpi.h"
36 #include "cipher.h"
37
38
39 void
40 rsa_free_public_key( RSA_public_key *pk )
41 {
42     mpi_free( pk->n ); pk->n = NULL;
43     mpi_free( pk->e ); pk->e = NULL;
44 }
45
46 void
47 rsa_free_secret_key( RSA_secret_key *sk )
48 {
49     mpi_free( sk->e ); sk->e = NULL;
50     mpi_free( sk->n ); sk->n = NULL;
51     mpi_free( sk->p ); sk->p = NULL;
52     mpi_free( sk->q ); sk->q = NULL;
53     mpi_free( sk->d ); sk->d = NULL;
54     mpi_free( sk->u ); sk->u = NULL;
55 }
56
57
58 static void
59 test_keys( RSA_public_key *pk, RSA_secret_key *sk, unsigned nbits )
60 {
61     MPI test = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
62     MPI out1 = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
63     MPI out2 = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
64
65     mpi_set_bytes( test, nbits, get_random_byte, 0 );
66
67     rsa_public( out1, test, pk );
68     rsa_secret( out2, out1, sk );
69     if( mpi_cmp( test, out2 ) )
70         log_fatal("RSA operation: public, secret failed\n");
71     rsa_secret( out1, test, sk );
72     rsa_public( out2, out1, pk );
73     if( mpi_cmp( test, out2 ) )
74         log_fatal("RSA operation: secret, public failed\n");
75     mpi_free( test );
76     mpi_free( out1 );
77     mpi_free( out2 );
78 }
79
80 /****************
81  * Generate a key pair with a key of size NBITS
82  * Returns: 2 structures filles with all needed values
83  */
84 void
85 rsa_generate( RSA_public_key *pk, RSA_secret_key *sk, unsigned nbits )
86 {
87     MPI p, q; /* the two primes */
88     MPI d;    /* the private key */
89     MPI u;
90     MPI t1, t2;
91     MPI n;    /* the public key */
92     MPI e;    /* the exponent */
93     MPI phi;  /* helper: (p-a)(q-1) */
94     MPI g;
95     MPI f;
96
97     /* select two (very secret) primes */
98     p = generate_secret_prime( nbits / 2 );
99     q = generate_secret_prime( nbits / 2 );
100     if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
101         mpi_swap(p,q);
102     /* calculate Euler totient: phi = (p-1)(q-1) */
103     t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
104     t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
105     phi = mpi_alloc_secure( nbits / BITS_PER_MPI_LIMB  );
106     g   = mpi_alloc_secure( nbits / BITS_PER_MPI_LIMB  );
107     f   = mpi_alloc_secure( nbits / BITS_PER_MPI_LIMB  );
108     mpi_sub_ui( t1, p, 1 );
109     mpi_sub_ui( t2, q, 1 );
110     mpi_mul( phi, t1, t2 );
111     mpi_gcd(g, t1, t2);
112     mpi_fdiv_q(f, phi, g);
113     /* multiply them to make the private key */
114     n = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
115     mpi_mul( n, p, q );
116     /* find a public exponent  */
117     e = mpi_alloc(1);
118     mpi_set_ui( e, 17); /* start with 17 */
119     while( !mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
120         mpi_add_ui( e, e, 2);
121     /* calculate the secret key d = e^1 mod phi */
122     d = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
123     mpi_invm(d, e, f );
124     /* calculate the inverse of p and q (used for chinese remainder theorem)*/
125     u = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
126     mpi_invm(u, p, q );
127
128     if( DBG_CIPHER ) {
129         log_mpidump("  p= ", p );
130         log_mpidump("  q= ", q );
131         log_mpidump("phi= ", phi );
132         log_mpidump("  g= ", g );
133         log_mpidump("  f= ", f );
134         log_mpidump("  n= ", n );
135         log_mpidump("  e= ", e );
136         log_mpidump("  d= ", d );
137         log_mpidump("  u= ", u );
138     }
139
140     mpi_free(t1);
141     mpi_free(t2);
142     mpi_free(phi);
143     mpi_free(f);
144     mpi_free(g);
145
146     pk->n = mpi_copy(n);
147     pk->e = mpi_copy(e);
148     sk->n = n;
149     sk->e = e;
150     sk->p = p;
151     sk->q = q;
152     sk->d = d;
153     sk->u = u;
154
155     /* now we can test our keys (this should never fail!) */
156     test_keys( pk, sk, nbits - 64 );
157 }
158
159
160
161
162 /****************
163  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
164  *
165  *      c = m^e mod n
166  *
167  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
168  */
169 void
170 rsa_public(MPI output, MPI input, RSA_public_key *pkey )
171 {
172     if( output == input ) { /* powm doesn't like output and input the same */
173         MPI x = mpi_alloc( mpi_get_nlimbs(input)*2 );
174         mpi_powm( x, input, pkey->e, pkey->n );
175         mpi_set(output, x);
176         mpi_free(x);
177     }
178     else
179         mpi_powm( output, input, pkey->e, pkey->n );
180 }
181
182 /****************
183  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
184  *
185  *      m = c^d mod n
186  *
187  * Where m is OUTPUT, c is INPUT and d,n are elements of PKEY.
188  *
189  * FIXME: We should better use the Chinese Remainder Theorem
190  */
191 void
192 rsa_secret(MPI output, MPI input, RSA_secret_key *skey )
193 {
194     mpi_powm( output, input, skey->d, skey->n );
195 }
196
197
198