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