d69f09ac398344fe20aa3f2097cbc8bcf93d4a9c
[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 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             if( DBG_CIPHER )
102                 fputc('.', stderr);
103
104             mpi_add_ui( prime, prime, step );
105
106             /* do a Fermat test */
107             count2++;
108             mpi_powm( result, val_2, prime, prime );
109             if( mpi_cmp_ui(result, 2) )
110                 continue;  /* stepping (fermat test failed) */
111             if( DBG_CIPHER )
112                 fputc('+', stderr);
113
114             /* perform stronger tests */
115             if( !is_not_prime(prime, nbits, 5, &count2 ) ) {
116                 if( !mpi_test_bit( prime, nbits-1 ) ) {
117                     if( DBG_CIPHER ) {
118                         fputc('\n', stderr);
119                         log_debug("overflow in prime generation\n");
120                         break; /* step loop, cont with a new prime */
121                     }
122                 }
123                 if( DBG_CIPHER ) {
124                     fputc('\n', stderr);
125                     log_debug("performed %u simple and %u stronger tests\n",
126                                         count1, count2 );
127                     log_mpidump("found prime: ", prime );
128                 }
129
130                 mpi_free(val_2);
131                 mpi_free(val_3);
132                 mpi_free(result);
133                 m_free(mods);
134                 return prime;
135             }
136         }
137         if( DBG_CIPHER )
138             fputc(':', stderr); /* restart with a new random value */
139     }
140 }
141
142
143 /****************
144  * Return 1 if n is not a prime
145  */
146 static int
147 is_not_prime( MPI n, unsigned nbits, int steps, int *count )
148 {
149     MPI x = mpi_alloc( mpi_get_nlimbs( n ) );
150     MPI y = mpi_alloc( mpi_get_nlimbs( n ) );
151     MPI z = mpi_alloc( mpi_get_nlimbs( n ) );
152     MPI nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
153     MPI a2 = mpi_alloc_set_ui( 2 );
154     MPI q;
155     unsigned i, j, k;
156     int rc = 1;
157
158     mpi_sub_ui( nminus1, n, 1 );
159
160     /* find q and k, so that n = 1 + 2^k * q */
161     q = mpi_copy( nminus1 );
162     k = mpi_trailing_zeros( q );
163     mpi_tdiv_q_2exp(q, q, k);
164
165     for(i=0 ; i < steps; i++ ) {
166         ++*count;
167         do {
168             mpi_set_bytes( x, nbits, get_random_byte, 0 );
169         } while( mpi_cmp( x, n ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
170         mpi_powm( y, x, q, n);
171         if( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) {
172             for( j=1; j < k; j++ ) {
173                 mpi_powm(y, y, a2, n);
174                 if( !mpi_cmp_ui( y, 1 ) )
175                     goto leave; /* not a prime */
176                 if( !mpi_cmp( y, nminus1 ) )
177                     break;  /* may be a prime */
178             }
179             if( j == k )
180                 goto leave;
181         }
182         if( DBG_CIPHER )
183             fputc('+', stderr);
184     }
185     rc = 0; /* may be a prime */
186
187   leave:
188     mpi_free( x );
189     mpi_free( y );
190     mpi_free( z );
191     mpi_free( nminus1 );
192     mpi_free( q );
193
194     return rc;
195 }
196