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 : #define PGM "prime"
28 : #include "t-common.h"
29 :
30 : static void
31 1 : check_primes (void)
32 : {
33 1 : gcry_error_t err = GPG_ERR_NO_ERROR;
34 1 : gcry_mpi_t *factors = NULL;
35 1 : gcry_mpi_t prime = NULL;
36 : gcry_mpi_t g;
37 1 : unsigned int i = 0;
38 : struct prime_spec
39 : {
40 : unsigned int prime_bits;
41 : unsigned int factor_bits;
42 : unsigned int flags;
43 1 : } prime_specs[] =
44 : {
45 : { 1024, 100, GCRY_PRIME_FLAG_SPECIAL_FACTOR },
46 : { 128, 0, 0 },
47 : { 0 },
48 : };
49 :
50 3 : for (i = 0; prime_specs[i].prime_bits; i++)
51 : {
52 2 : err = gcry_prime_generate (&prime,
53 : prime_specs[i].prime_bits,
54 : prime_specs[i].factor_bits,
55 : &factors,
56 : NULL, NULL,
57 : GCRY_WEAK_RANDOM,
58 : prime_specs[i].flags);
59 2 : assert (! err);
60 2 : if (verbose)
61 : {
62 0 : fprintf (stderr, "test %d: p = ", i);
63 0 : gcry_mpi_dump (prime);
64 0 : putc ('\n', stderr);
65 : }
66 :
67 2 : err = gcry_prime_check (prime, 0);
68 2 : assert (! err);
69 :
70 2 : err = gcry_prime_group_generator (&g, prime, factors, NULL);
71 2 : assert (!err);
72 2 : gcry_prime_release_factors (factors); factors = NULL;
73 :
74 2 : if (verbose)
75 : {
76 0 : fprintf (stderr, " %d: g = ", i);
77 0 : gcry_mpi_dump (g);
78 0 : putc ('\n', stderr);
79 : }
80 2 : gcry_mpi_release (g);
81 :
82 :
83 2 : gcry_mpi_add_ui (prime, prime, 1);
84 2 : err = gcry_prime_check (prime, 0);
85 2 : assert (err);
86 2 : gcry_mpi_release (prime); prime = NULL;
87 : }
88 1 : }
89 :
90 :
91 : /* Print an MPI S-expression. */
92 : static void
93 0 : print_mpi (const char *name, gcry_mpi_t a)
94 : {
95 : gcry_error_t err;
96 : unsigned char *buf;
97 0 : int writerr = 0;
98 :
99 0 : err = gcry_mpi_aprint (GCRYMPI_FMT_HEX, &buf, NULL, a);
100 0 : if (err)
101 0 : die ("gcry_mpi_aprint failed: %s\n", gcry_strerror (err));
102 :
103 0 : printf (" (%s #%s#)\n", name, buf);
104 0 : if (ferror (stdout))
105 0 : writerr++;
106 0 : if (!writerr && fflush (stdout) == EOF)
107 0 : writerr++;
108 0 : if (writerr)
109 0 : die ("writing output failed\n");
110 0 : gcry_free (buf);
111 0 : }
112 :
113 :
114 : /* Create the key for our public standard dummy CA. */
115 : static void
116 0 : create_42prime (void)
117 : {
118 : gcry_error_t err;
119 : char string[128*2+1];
120 : int i;
121 0 : gcry_mpi_t start = NULL;
122 : gcry_mpi_t p, q, n, t1, t2, phi, f, g, e, d, u;
123 :
124 :
125 : /* Our start value is a string of 0x42 values, with the exception
126 : that the two high order bits are set. This is to resemble the
127 : way Lingcrypt generates RSA primes. */
128 0 : for (i=0; i < 128;)
129 : {
130 0 : string[i++] = '4';
131 0 : string[i++] = '2';
132 : }
133 0 : string[i] = 0;
134 0 : string[0] = 'C';
135 :
136 0 : err = gcry_mpi_scan (&start, GCRYMPI_FMT_HEX, string, 0, NULL);
137 0 : if (err)
138 0 : die ("gcry_mpi_scan failed: %s\n", gcry_strerror (err));
139 0 : fputs ("start:", stderr); gcry_mpi_dump (start); putc ('\n', stderr);
140 :
141 : /* Generate two primes with p < q. We take the first primes below
142 : and above a start value. */
143 0 : p = gcry_mpi_copy (start);
144 0 : gcry_mpi_sub_ui (p, p, 1);
145 0 : while (gcry_prime_check (p, 0))
146 0 : gcry_mpi_sub_ui (p, p, 2);
147 0 : fputs (" p:", stderr); gcry_mpi_dump (p); putc ('\n', stderr);
148 0 : q = gcry_mpi_copy (start);
149 0 : gcry_mpi_add_ui (q, q, 1);
150 0 : while (gcry_prime_check (q, 0))
151 0 : gcry_mpi_add_ui (q, q, 2);
152 0 : fputs (" q:", stderr); gcry_mpi_dump (q); putc ('\n', stderr);
153 :
154 : /* Compute the modulus. */
155 0 : n = gcry_mpi_new (1024);
156 0 : gcry_mpi_mul (n, p, q);
157 0 : fputs (" n:", stderr); gcry_mpi_dump (n); putc ('\n', stderr);
158 0 : if (gcry_mpi_get_nbits (n) != 1024)
159 0 : die ("Oops: the size of N is not 1024 but %u\n", gcry_mpi_get_nbits (n));
160 :
161 : /* Calculate Euler totient: phi = (p-1)(q-1) */
162 0 : t1 = gcry_mpi_new (0);
163 0 : t2 = gcry_mpi_new (0);
164 0 : phi = gcry_mpi_new (0);
165 0 : g = gcry_mpi_new (0);
166 0 : f = gcry_mpi_new (0);
167 0 : gcry_mpi_sub_ui (t1, p, 1);
168 0 : gcry_mpi_sub_ui (t2, q, 1);
169 0 : gcry_mpi_mul (phi, t1, t2);
170 0 : gcry_mpi_gcd (g, t1, t2);
171 0 : gcry_mpi_div (f, NULL, phi, g, -1);
172 :
173 : /* Check the public exponent. */
174 0 : e = gcry_mpi_set_ui (NULL, 65537);
175 0 : if (!gcry_mpi_gcd (t1, e, phi))
176 0 : die ("Oops: E is not a generator\n");
177 0 : fputs (" e:", stderr); gcry_mpi_dump (e); putc ('\n', stderr);
178 :
179 : /* Compute the secret key: d = e^-1 mod phi */
180 0 : d = gcry_mpi_new (0);
181 0 : gcry_mpi_invm (d, e, f );
182 0 : fputs (" d:", stderr); gcry_mpi_dump (d); putc ('\n', stderr);
183 :
184 : /* Compute the inverse of p and q. */
185 0 : u = gcry_mpi_new (0);
186 0 : gcry_mpi_invm (u, p, q);
187 0 : fputs (" u:", stderr); gcry_mpi_dump (u); putc ('\n', stderr);
188 :
189 : /* Print the S-expression. */
190 0 : fputs ("(private-key\n (rsa\n", stdout);
191 0 : print_mpi ("n", n);
192 0 : print_mpi ("e", e);
193 0 : print_mpi ("d", d);
194 0 : print_mpi ("p", p);
195 0 : print_mpi ("q", q);
196 0 : print_mpi ("u", u);
197 0 : fputs ("))\n", stdout);
198 :
199 0 : gcry_mpi_release (p);
200 0 : gcry_mpi_release (q);
201 0 : gcry_mpi_release (n);
202 0 : gcry_mpi_release (t1);
203 0 : gcry_mpi_release (t2);
204 0 : gcry_mpi_release (phi);
205 0 : gcry_mpi_release (f);
206 0 : gcry_mpi_release (g);
207 0 : gcry_mpi_release (e);
208 0 : gcry_mpi_release (d);
209 0 : gcry_mpi_release (u);
210 0 : }
211 :
212 :
213 :
214 :
215 : int
216 1 : main (int argc, char **argv)
217 : {
218 1 : int mode42 = 0;
219 :
220 1 : if ((argc > 1) && (! strcmp (argv[1], "--verbose")))
221 0 : verbose = 1;
222 1 : else if ((argc > 1) && (! strcmp (argv[1], "--debug")))
223 0 : verbose = debug = 1;
224 1 : else if ((argc > 1) && (! strcmp (argv[1], "--42")))
225 0 : verbose = debug = mode42 = 1;
226 :
227 1 : xgcry_control (GCRYCTL_DISABLE_SECMEM, 0);
228 1 : if (! gcry_check_version (GCRYPT_VERSION))
229 0 : die ("version mismatch\n");
230 :
231 1 : xgcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
232 1 : if (debug)
233 0 : xgcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);
234 :
235 1 : if (mode42)
236 0 : create_42prime ();
237 : else
238 1 : check_primes ();
239 :
240 1 : return 0;
241 : }
|