Line data Source code
1 : /* prime.c - part of the Libgcrypt test suite.
2 : Copyright (C) 2001, 2002, 2003, 2005 Free Software Foundation, Inc.
3 :
4 : This program is free software; you can redistribute it and/or
5 : modify it under the terms of the GNU General Public License as
6 : published by the Free Software Foundation; either version 2 of the
7 : License, or (at your option) any later version.
8 :
9 : This program is distributed in the hope that it will be useful, but
10 : WITHOUT ANY WARRANTY; without even the implied warranty of
11 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 : General Public License for more details.
13 :
14 : You should have received a copy of the GNU General Public License
15 : along with this program; if not, write to the Free Software
16 : Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
17 : USA. */
18 :
19 : #ifdef HAVE_CONFIG_H
20 : #include <config.h>
21 : #endif
22 : #include <assert.h>
23 : #include <stdio.h>
24 : #include <string.h>
25 : #include <stdlib.h>
26 :
27 : #include "../src/gcrypt-int.h"
28 :
29 : static int verbose;
30 :
31 : static void
32 0 : die (const char *format, ...)
33 : {
34 : va_list arg_ptr;
35 :
36 0 : va_start (arg_ptr, format);
37 0 : vfprintf (stderr, format, arg_ptr);
38 0 : va_end (arg_ptr);
39 0 : exit (1);
40 : }
41 :
42 : static void
43 1 : check_primes (void)
44 : {
45 1 : gcry_error_t err = GPG_ERR_NO_ERROR;
46 1 : gcry_mpi_t *factors = NULL;
47 1 : gcry_mpi_t prime = NULL;
48 : gcry_mpi_t g;
49 1 : unsigned int i = 0;
50 : struct prime_spec
51 : {
52 : unsigned int prime_bits;
53 : unsigned int factor_bits;
54 : unsigned int flags;
55 1 : } prime_specs[] =
56 : {
57 : { 1024, 100, GCRY_PRIME_FLAG_SPECIAL_FACTOR },
58 : { 128, 0, 0 },
59 : { 0 },
60 : };
61 :
62 3 : for (i = 0; prime_specs[i].prime_bits; i++)
63 : {
64 2 : err = gcry_prime_generate (&prime,
65 : prime_specs[i].prime_bits,
66 : prime_specs[i].factor_bits,
67 : &factors,
68 : NULL, NULL,
69 : GCRY_WEAK_RANDOM,
70 : prime_specs[i].flags);
71 2 : assert (! err);
72 2 : if (verbose)
73 : {
74 0 : fprintf (stderr, "test %d: p = ", i);
75 0 : gcry_mpi_dump (prime);
76 0 : putc ('\n', stderr);
77 : }
78 :
79 2 : err = gcry_prime_check (prime, 0);
80 2 : assert (! err);
81 :
82 2 : err = gcry_prime_group_generator (&g, prime, factors, NULL);
83 2 : assert (!err);
84 2 : gcry_prime_release_factors (factors); factors = NULL;
85 :
86 2 : if (verbose)
87 : {
88 0 : fprintf (stderr, " %d: g = ", i);
89 0 : gcry_mpi_dump (g);
90 0 : putc ('\n', stderr);
91 : }
92 2 : gcry_mpi_release (g);
93 :
94 :
95 2 : gcry_mpi_add_ui (prime, prime, 1);
96 2 : err = gcry_prime_check (prime, 0);
97 2 : assert (err);
98 2 : gcry_mpi_release (prime); prime = NULL;
99 : }
100 1 : }
101 :
102 :
103 : /* Print an MPI S-expression. */
104 : static void
105 0 : print_mpi (const char *name, gcry_mpi_t a)
106 : {
107 : gcry_error_t err;
108 : unsigned char *buf;
109 0 : int writerr = 0;
110 :
111 0 : err = gcry_mpi_aprint (GCRYMPI_FMT_HEX, &buf, NULL, a);
112 0 : if (err)
113 0 : die ("gcry_mpi_aprint failed: %s\n", gcry_strerror (err));
114 :
115 0 : printf (" (%s #%s#)\n", name, buf);
116 0 : if (ferror (stdout))
117 0 : writerr++;
118 0 : if (!writerr && fflush (stdout) == EOF)
119 0 : writerr++;
120 0 : if (writerr)
121 0 : die ("writing output failed\n");
122 0 : gcry_free (buf);
123 0 : }
124 :
125 :
126 : /* Create the key for our public standard dummy CA. */
127 : static void
128 0 : create_42prime (void)
129 : {
130 : gcry_error_t err;
131 : char string[128*2+1];
132 : int i;
133 0 : gcry_mpi_t start = NULL;
134 : gcry_mpi_t p, q, n, t1, t2, phi, f, g, e, d, u;
135 :
136 :
137 : /* Our start value is a string of 0x42 values, with the exception
138 : that the two high order bits are set. This is to resemble the
139 : way Lingcrypt generates RSA primes. */
140 0 : for (i=0; i < 128;)
141 : {
142 0 : string[i++] = '4';
143 0 : string[i++] = '2';
144 : }
145 0 : string[i] = 0;
146 0 : string[0] = 'C';
147 :
148 0 : err = gcry_mpi_scan (&start, GCRYMPI_FMT_HEX, string, 0, NULL);
149 0 : if (err)
150 0 : die ("gcry_mpi_scan failed: %s\n", gcry_strerror (err));
151 0 : fputs ("start:", stderr); gcry_mpi_dump (start); putc ('\n', stderr);
152 :
153 : /* Generate two primes with p < q. We take the first primes below
154 : and above a start value. */
155 0 : p = gcry_mpi_copy (start);
156 0 : gcry_mpi_sub_ui (p, p, 1);
157 0 : while (gcry_prime_check (p, 0))
158 0 : gcry_mpi_sub_ui (p, p, 2);
159 0 : fputs (" p:", stderr); gcry_mpi_dump (p); putc ('\n', stderr);
160 0 : q = gcry_mpi_copy (start);
161 0 : gcry_mpi_add_ui (q, q, 1);
162 0 : while (gcry_prime_check (q, 0))
163 0 : gcry_mpi_add_ui (q, q, 2);
164 0 : fputs (" q:", stderr); gcry_mpi_dump (q); putc ('\n', stderr);
165 :
166 : /* Compute the modulus. */
167 0 : n = gcry_mpi_new (1024);
168 0 : gcry_mpi_mul (n, p, q);
169 0 : fputs (" n:", stderr); gcry_mpi_dump (n); putc ('\n', stderr);
170 0 : if (gcry_mpi_get_nbits (n) != 1024)
171 0 : die ("Oops: the size of N is not 1024 but %u\n", gcry_mpi_get_nbits (n));
172 :
173 : /* Calculate Euler totient: phi = (p-1)(q-1) */
174 0 : t1 = gcry_mpi_new (0);
175 0 : t2 = gcry_mpi_new (0);
176 0 : phi = gcry_mpi_new (0);
177 0 : g = gcry_mpi_new (0);
178 0 : f = gcry_mpi_new (0);
179 0 : gcry_mpi_sub_ui (t1, p, 1);
180 0 : gcry_mpi_sub_ui (t2, q, 1);
181 0 : gcry_mpi_mul (phi, t1, t2);
182 0 : gcry_mpi_gcd (g, t1, t2);
183 0 : gcry_mpi_div (f, NULL, phi, g, -1);
184 :
185 : /* Check the public exponent. */
186 0 : e = gcry_mpi_set_ui (NULL, 65537);
187 0 : if (!gcry_mpi_gcd (t1, e, phi))
188 0 : die ("Oops: E is not a generator\n");
189 0 : fputs (" e:", stderr); gcry_mpi_dump (e); putc ('\n', stderr);
190 :
191 : /* Compute the secret key: d = e^-1 mod phi */
192 0 : d = gcry_mpi_new (0);
193 0 : gcry_mpi_invm (d, e, f );
194 0 : fputs (" d:", stderr); gcry_mpi_dump (d); putc ('\n', stderr);
195 :
196 : /* Compute the inverse of p and q. */
197 0 : u = gcry_mpi_new (0);
198 0 : gcry_mpi_invm (u, p, q);
199 0 : fputs (" u:", stderr); gcry_mpi_dump (u); putc ('\n', stderr);
200 :
201 : /* Print the S-expression. */
202 0 : fputs ("(private-key\n (rsa\n", stdout);
203 0 : print_mpi ("n", n);
204 0 : print_mpi ("e", e);
205 0 : print_mpi ("d", d);
206 0 : print_mpi ("p", p);
207 0 : print_mpi ("q", q);
208 0 : print_mpi ("u", u);
209 0 : fputs ("))\n", stdout);
210 :
211 0 : gcry_mpi_release (p);
212 0 : gcry_mpi_release (q);
213 0 : gcry_mpi_release (n);
214 0 : gcry_mpi_release (t1);
215 0 : gcry_mpi_release (t2);
216 0 : gcry_mpi_release (phi);
217 0 : gcry_mpi_release (f);
218 0 : gcry_mpi_release (g);
219 0 : gcry_mpi_release (e);
220 0 : gcry_mpi_release (d);
221 0 : gcry_mpi_release (u);
222 0 : }
223 :
224 :
225 :
226 :
227 : int
228 1 : main (int argc, char **argv)
229 : {
230 1 : int debug = 0;
231 1 : int mode42 = 0;
232 :
233 1 : if ((argc > 1) && (! strcmp (argv[1], "--verbose")))
234 0 : verbose = 1;
235 1 : else if ((argc > 1) && (! strcmp (argv[1], "--debug")))
236 0 : verbose = debug = 1;
237 1 : else if ((argc > 1) && (! strcmp (argv[1], "--42")))
238 0 : verbose = debug = mode42 = 1;
239 :
240 1 : gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
241 1 : if (! gcry_check_version (GCRYPT_VERSION))
242 0 : die ("version mismatch\n");
243 :
244 1 : gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
245 1 : if (debug)
246 0 : gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);
247 :
248 1 : if (mode42)
249 0 : create_42prime ();
250 : else
251 1 : check_primes ();
252 :
253 1 : return 0;
254 : }
|
