0173b3d0bd439b0772b8fb7d59d71120344cfd07
[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 rabin_miller( MPI n );
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
54     unsigned  nlimbs;
55     MPI prime, val_2, val_3, result;
56     int i;
57     unsigned x, step;
58     unsigned count1, count2;
59     int *mods;
60
61     if( DBG_CIPHER )
62         log_debug("generate a prime of %u bits ", nbits );
63
64     if( !no_of_small_prime_numbers ) {
65         for(i=0; small_prime_numbers[i]; i++ )
66             no_of_small_prime_numbers++;
67     }
68     mods = m_alloc( no_of_small_prime_numbers * sizeof *mods );
69     /* make nbits fit into MPI implementation */
70     nlimbs = (nbits + BITS_PER_MPI_LIMB - 1) /  BITS_PER_MPI_LIMB;
71     assert( nlimbs );
72     val_2  = mpi_alloc( nlimbs );
73     mpi_set_ui(val_2, 2);
74     val_3  = mpi_alloc( nlimbs );
75     mpi_set_ui(val_3, 3);
76     result = mpi_alloc( nlimbs );
77     prime  = secret? mpi_alloc_secure( nlimbs ): mpi_alloc( nlimbs );
78     count1 = count2 = 0;
79     /* enter (endless) loop */
80     for(;;) {
81         /* generate a random number */
82         mpi_set_bytes( prime, nbits, get_random_byte, 2 );
83         /* set high order bit to 1, set low order bit to 1 */
84         mpi_set_bit( prime, nbits-1 );
85         mpi_set_bit( prime, 0 );
86
87         /* calculate all remainders */
88         for(i=0; (x = small_prime_numbers[i]); i++ )
89             mods[i] = mpi_fdiv_r_ui(NULL, prime, x);
90
91         for(step=0; step < 20000; step += 2 ) {
92             /* check against all the small primes we have in mods */
93             count1++;
94             for(i=0; (x = small_prime_numbers[i]); i++ ) {
95                 while( mods[i] + step >= x )
96                     mods[i] -= x;
97                 if( !(mods[i] + step) )
98                     break;
99             }
100             if( x )
101                 continue;   /* found a multiple of a already known prime */
102             if( DBG_CIPHER )
103                 fputc('.', stderr);
104
105             mpi_add_ui( prime, prime, step );
106
107             /* do a Fermat test */
108             count2++;
109             mpi_powm( result, val_2, prime, prime );
110             if( mpi_cmp_ui(result, 2) )
111                 continue;  /* stepping (fermat test failed) */
112             if( DBG_CIPHER )
113                 fputc('+', stderr);
114             /* and a second one */
115             count2++;
116             mpi_powm( result, val_3, prime, prime );
117             if( mpi_cmp_ui(result, 3) )
118                 continue;  /* stepping (fermat test failed) */
119             if( DBG_CIPHER )
120                 fputc('+', stderr);
121
122             /* perform Rabin-Miller tests */
123             for(i=5; i > 0; i-- ) {
124                 if( DBG_CIPHER )
125                     fputc('+', stderr);
126                 if( rabin_miller(prime) )
127                     break;
128             }
129             if( !i ) {
130                 if( !mpi_test_bit( prime, nbits-1 ) ) {
131                     if( DBG_CIPHER ) {
132                         fputc('\n', stderr);
133                         log_debug("overflow in prime generation\n");
134                         break; /* step loop, cont with a new prime */
135                     }
136                 }
137                 if( DBG_CIPHER ) {
138                     fputc('\n', stderr);
139                     log_debug("performed %u simple and %u Fermat/Rabin-Miller tests\n",
140                                         count1, count2 );
141                     log_mpidump("found prime: ", prime );
142                 }
143
144                 mpi_free(val_2);
145                 mpi_free(val_3);
146                 mpi_free(result);
147                 m_free(mods);
148                 return prime;
149             }
150         }
151         if( DBG_CIPHER )
152             fputc(':', stderr); /* restart with a new random value */
153     }
154 }
155
156
157 /****************
158  * Return 1 if n is not a prime
159  */
160 static int
161 rabin_miller( MPI n )
162 {
163     return 0;
164 }
165