fingerprints and self signatures added
[libgcrypt.git] / cipher / primegen.c
1 /* primegen.c - prime number generator
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
3  *
4  * This file is part of G10.
5  *
6  * G10 is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * G10 is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <assert.h>
26 #include "util.h"
27 #include "mpi.h"
28 #include "cipher.h"
29
30 static int no_of_small_prime_numbers;
31 static int is_not_prime( MPI n, unsigned nbits, int steps, int *count );
32 static MPI gen_prime( unsigned  nbits, int mode );
33
34
35 /****************
36  * Generate a prime number (stored in secure memory)
37  */
38 MPI
39 generate_secret_prime( unsigned  nbits )
40 {
41     return gen_prime( nbits, 1 );
42 }
43
44 MPI
45 generate_public_prime( unsigned  nbits )
46 {
47     return gen_prime( nbits, 0 );
48 }
49
50 static MPI
51 gen_prime( unsigned  nbits, int secret )
52 {
53     unsigned  nlimbs;
54     MPI prime, val_2, val_3, result;
55     int i;
56     unsigned x, step;
57     unsigned count1, count2;
58     int *mods;
59
60     if( DBG_CIPHER )
61         log_debug("generate a prime of %u bits ", nbits );
62
63     if( !no_of_small_prime_numbers ) {
64         for(i=0; small_prime_numbers[i]; i++ )
65             no_of_small_prime_numbers++;
66     }
67     mods = m_alloc( no_of_small_prime_numbers * sizeof *mods );
68     /* make nbits fit into MPI implementation */
69     nlimbs = (nbits + BITS_PER_MPI_LIMB - 1) /  BITS_PER_MPI_LIMB;
70     assert( nlimbs );
71     val_2  = mpi_alloc( nlimbs );
72     mpi_set_ui(val_2, 2);
73     val_3  = mpi_alloc( nlimbs );
74     mpi_set_ui(val_3, 3);
75     result = mpi_alloc( nlimbs );
76     prime  = secret? mpi_alloc_secure( nlimbs ): mpi_alloc( nlimbs );
77     count1 = count2 = 0;
78     /* enter (endless) loop */
79     for(;;) {
80         /* generate a random number */
81         mpi_set_bytes( prime, nbits, get_random_byte, 2 );
82         /* set high order bit to 1, set low order bit to 1 */
83         mpi_set_bit( prime, nbits-1 );
84         mpi_set_bit( prime, 0 );
85
86         /* calculate all remainders */
87         for(i=0; (x = small_prime_numbers[i]); i++ )
88             mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
89
90         for(step=0; step < 20000; step += 2 ) {
91             /* check against all the small primes we have in mods */
92             count1++;
93             for(i=0; (x = small_prime_numbers[i]); i++ ) {
94                 while( mods[i] + step >= x )
95                     mods[i] -= x;
96                 if( !(mods[i] + step) )
97                     break;
98             }
99             if( x )
100                 continue;   /* found a multiple of a already known prime */
101             fputc('.', stderr);
102
103             mpi_add_ui( prime, prime, step );
104
105             /* do a Fermat test */
106             count2++;
107             mpi_powm( result, val_2, prime, prime );
108             if( mpi_cmp_ui(result, 2) )
109                 continue;  /* stepping (fermat test failed) */
110             fputc('+', stderr);
111
112             /* perform stronger tests */
113             if( !is_not_prime(prime, nbits, 5, &count2 ) ) {
114                 if( !mpi_test_bit( prime, nbits-1 ) ) {
115                     if( DBG_CIPHER ) {
116                         fputc('\n', stderr);
117                         log_debug("overflow in prime generation\n");
118                         break; /* step loop, cont with a new prime */
119                     }
120                 }
121
122                 fputc('\n', stderr);
123                 if( DBG_CIPHER ) {
124                     log_debug("performed %u simple and %u stronger tests\n",
125                                         count1, count2 );
126                     log_mpidump("found prime: ", prime );
127                 }
128
129                 mpi_free(val_2);
130                 mpi_free(val_3);
131                 mpi_free(result);
132                 m_free(mods);
133                 return prime;
134             }
135         }
136         fputc(':', stderr); /* restart with a new random value */
137     }
138 }
139
140
141 /****************
142  * Return 1 if n is not a prime
143  */
144 static int
145 is_not_prime( MPI n, unsigned nbits, int steps, int *count )
146 {
147     MPI x = mpi_alloc( mpi_get_nlimbs( n ) );
148     MPI y = mpi_alloc( mpi_get_nlimbs( n ) );
149     MPI z = mpi_alloc( mpi_get_nlimbs( n ) );
150     MPI nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
151     MPI a2 = mpi_alloc_set_ui( 2 );
152     MPI q;
153     unsigned i, j, k;
154     int rc = 1;
155
156     mpi_sub_ui( nminus1, n, 1 );
157
158     /* find q and k, so that n = 1 + 2^k * q */
159     q = mpi_copy( nminus1 );
160     k = mpi_trailing_zeros( q );
161     mpi_tdiv_q_2exp(q, q, k);
162
163     for(i=0 ; i < steps; i++ ) {
164         ++*count;
165         do {
166             mpi_set_bytes( x, nbits, get_random_byte, 0 );
167         } while( mpi_cmp( x, n ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
168         mpi_powm( y, x, q, n);
169         if( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) {
170             for( j=1; j < k; j++ ) {
171                 mpi_powm(y, y, a2, n);
172                 if( !mpi_cmp_ui( y, 1 ) )
173                     goto leave; /* not a prime */
174                 if( !mpi_cmp( y, nminus1 ) )
175                     break;  /* may be a prime */
176             }
177             if( j == k )
178                 goto leave;
179         }
180         fputc('+', stderr);
181     }
182     rc = 0; /* may be a prime */
183
184   leave:
185     mpi_free( x );
186     mpi_free( y );
187     mpi_free( z );
188     mpi_free( nminus1 );
189     mpi_free( q );
190
191     return rc;
192 }
193