1 /*
2 * sshkeygen.h: routines used internally to key generation.
3 */
4
5 /* ----------------------------------------------------------------------
6 * A table of all the primes that fit in a 16-bit integer. Call
7 * init_primes_array to make sure it's been initialised.
8 */
9
10 #define NSMALLPRIMES 6542 /* number of primes < 65536 */
11 extern const unsigned short *const smallprimes;
12 void init_smallprimes(void);
13
14 /* ----------------------------------------------------------------------
15 * A system for making up random candidate integers during prime
16 * generation. This unconditionally ensures that the numbers have the
17 * right number of bits and are not divisible by any prime in the
18 * smallprimes[] array above. It can also impose further constraints,
19 * as documented below.
20 */
21 typedef struct PrimeCandidateSource PrimeCandidateSource;
22
23 /*
24 * pcs_new: you say how many bits you want the prime to have (with the
25 * usual semantics that an n-bit number is in the range [2^{n-1},2^n))
26 * and also optionally specify what you want its topmost 'nfirst' bits
27 * to be.
28 *
29 * (The 'first' system is used for RSA keys, where you need to arrange
30 * that the product of your two primes is in a more tightly
31 * constrained range than the factor of 4 you'd get by just generating
32 * two (n/2)-bit primes and multiplying them.)
33 */
34 PrimeCandidateSource *pcs_new(unsigned bits);
35 PrimeCandidateSource *pcs_new_with_firstbits(unsigned bits,
36 unsigned first, unsigned nfirst);
37
38 /* Insist that generated numbers must be congruent to 'res' mod 'mod' */
39 void pcs_require_residue(PrimeCandidateSource *s, mp_int *mod, mp_int *res);
40
41 /* Convenience wrapper for the common case where res = 1 */
42 void pcs_require_residue_1(PrimeCandidateSource *s, mp_int *mod);
43
44 /* Same as pcs_require_residue_1, but also records that the modulus is
45 * known to be prime */
46 void pcs_require_residue_1_mod_prime(PrimeCandidateSource *s, mp_int *mod);
47
48 /* Insist that generated numbers must _not_ be congruent to 'res' mod
49 * 'mod'. This is used to avoid being 1 mod the RSA public exponent,
50 * which is small, so it only needs ordinary integer parameters. */
51 void pcs_avoid_residue_small(PrimeCandidateSource *s,
52 unsigned mod, unsigned res);
53
54 /* Exclude any prime that has no chance of being a Sophie Germain prime. */
55 void pcs_try_sophie_germain(PrimeCandidateSource *s);
56
57 /* Mark a PrimeCandidateSource as one-shot, so that the prime generation
58 * function will return NULL if an attempt fails, rather than looping. */
59 void pcs_set_oneshot(PrimeCandidateSource *s);
60
61 /* Prepare a PrimeCandidateSource to actually generate numbers. This
62 * function does last-minute computation that has to be delayed until
63 * all constraints have been input. */
64 void pcs_ready(PrimeCandidateSource *s);
65
66 /* Actually generate a candidate integer. You must free the result, of
67 * course. */
68 mp_int *pcs_generate(PrimeCandidateSource *s);
69
70 /* Free a PrimeCandidateSource. */
71 void pcs_free(PrimeCandidateSource *s);
72
73 /* Return some internal fields of the PCS. Used by testcrypt for
74 * unit-testing this system. */
75 void pcs_inspect(PrimeCandidateSource *pcs, mp_int **limit_out,
76 mp_int **factor_out, mp_int **addend_out);
77
78 /* Query functions for primegen to use */
79 unsigned pcs_get_bits(PrimeCandidateSource *pcs);
80 unsigned pcs_get_bits_remaining(PrimeCandidateSource *pcs);
81 mp_int *pcs_get_upper_bound(PrimeCandidateSource *pcs);
82 mp_int **pcs_get_known_prime_factors(PrimeCandidateSource *pcs, size_t *nout);
83
84 /* ----------------------------------------------------------------------
85 * A system for doing Miller-Rabin probabilistic primality tests.
86 * These benefit from having set up some context beforehand, if you're
87 * going to do more than one of them on the same candidate prime, so
88 * we declare an object type here to store that context.
89 */
90
91 typedef struct MillerRabin MillerRabin;
92
93 /* Make and free a Miller-Rabin context. */
94 MillerRabin *miller_rabin_new(mp_int *p);
95 void miller_rabin_free(MillerRabin *mr);
96
97 /* Perform a single Miller-Rabin test, using a random witness value. */
98 bool miller_rabin_test_random(MillerRabin *mr);
99
100 /* Suggest how many tests are needed to make it sufficiently unlikely
101 * that a composite number will pass them all */
102 unsigned miller_rabin_checks_needed(unsigned bits);
103
104 /* An extension to the M-R test, which iterates until it either finds
105 * a witness value that is potentially a primitive root, or one
106 * that proves the number to be composite. */
107 mp_int *miller_rabin_find_potential_primitive_root(MillerRabin *mr);
108
109 /* ----------------------------------------------------------------------
110 * A system for proving numbers to be prime, using the Pocklington
111 * test, which requires knowing a partial factorisation of p-1
112 * (specifically, factors whose product is at least cbrt(p)) and a
113 * primitive root.
114 *
115 * The API consists of instantiating a 'Pockle' object, which
116 * internally stores a list of numbers you've already convinced it is
117 * prime, and can accept further primes if you give a satisfactory
118 * certificate of their primality based on primes it already knows
119 * about.
120 */
121
122 typedef struct Pockle Pockle;
123
124 /* In real use, you only really need to know whether the Pockle
125 * successfully accepted your prime. But for testcrypt, it's useful to
126 * expose many different failure modes so we can try to provoke them
127 * all in unit tests and check they're working. */
128 #define POCKLE_STATUSES(X) \
129 X(POCKLE_OK) \
130 X(POCKLE_SMALL_PRIME_NOT_SMALL) \
131 X(POCKLE_SMALL_PRIME_NOT_PRIME) \
132 X(POCKLE_PRIME_SMALLER_THAN_2) \
133 X(POCKLE_FACTOR_NOT_KNOWN_PRIME) \
134 X(POCKLE_FACTOR_NOT_A_FACTOR) \
135 X(POCKLE_PRODUCT_OF_FACTORS_TOO_SMALL) \
136 X(POCKLE_FERMAT_TEST_FAILED) \
137 X(POCKLE_DISCRIMINANT_IS_SQUARE) \
138 X(POCKLE_WITNESS_POWER_IS_1) \
139 X(POCKLE_WITNESS_POWER_NOT_COPRIME) \
140 /* end of list */
141
142 #define DEFINE_ENUM(id) id,
143 typedef enum PockleStatus { POCKLE_STATUSES(DEFINE_ENUM) } PockleStatus;
144 #undef DEFINE_ENUM
145
146 /* Make a new empty Pockle, containing no primes. */
147 Pockle *pockle_new(void);
148
149 /* Insert a prime below 2^32 into the Pockle. No evidence is required:
150 * Pockle will check it itself. */
151 PockleStatus pockle_add_small_prime(Pockle *pockle, mp_int *p);
152
153 /* Insert a general prime into the Pockle. You must provide a list of
154 * prime factors of p-1, whose product exceeds the cube root of p, and
155 * also a primitive root mod p. */
156 PockleStatus pockle_add_prime(Pockle *pockle, mp_int *p,
157 mp_int **factors, size_t nfactors,
158 mp_int *primitive_root);
159
160 /* If you call pockle_mark, and later pass the returned value to
161 * pockle_release, it will free all the primes that were added to the
162 * Pockle between those two calls. Useful in recursive algorithms, to
163 * stop the Pockle growing unboundedly if the recursion keeps having
164 * to backtrack. */
165 size_t pockle_mark(Pockle *pockle);
166 void pockle_release(Pockle *pockle, size_t mark);
167
168 /* Free a Pockle. */
169 void pockle_free(Pockle *pockle);
170
171 /* Generate a certificate of primality for a prime already known to
172 * the Pockle, in a format acceptable to Math::Prime::Util. */
173 strbuf *pockle_mpu(Pockle *pockle, mp_int *p);
174
175 /* ----------------------------------------------------------------------
176 * Callback API that allows key generation to report progress to its
177 * caller.
178 */
179
180 typedef struct ProgressReceiverVtable ProgressReceiverVtable;
181 typedef struct ProgressReceiver ProgressReceiver;
182 typedef union ProgressPhase ProgressPhase;
183
184 union ProgressPhase {
185 int n;
186 void *p;
187 };
188
189 struct ProgressReceiver {
190 const ProgressReceiverVtable *vt;
191 };
192
193 struct ProgressReceiverVtable {
194 ProgressPhase (*add_linear)(ProgressReceiver *prog, double overall_cost);
195 ProgressPhase (*add_probabilistic)(ProgressReceiver *prog,
196 double cost_per_attempt,
197 double attempt_probability);
198 void (*ready)(ProgressReceiver *prog);
199 void (*start_phase)(ProgressReceiver *prog, ProgressPhase phase);
200 void (*report)(ProgressReceiver *prog, double progress);
201 void (*report_attempt)(ProgressReceiver *prog);
202 void (*report_phase_complete)(ProgressReceiver *prog);
203 };
204
progress_add_linear(ProgressReceiver * prog,double c)205 static inline ProgressPhase progress_add_linear(ProgressReceiver *prog,
206 double c)
207 { return prog->vt->add_linear(prog, c); }
progress_add_probabilistic(ProgressReceiver * prog,double c,double p)208 static inline ProgressPhase progress_add_probabilistic(ProgressReceiver *prog,
209 double c, double p)
210 { return prog->vt->add_probabilistic(prog, c, p); }
progress_ready(ProgressReceiver * prog)211 static inline void progress_ready(ProgressReceiver *prog)
212 { prog->vt->ready(prog); }
progress_start_phase(ProgressReceiver * prog,ProgressPhase phase)213 static inline void progress_start_phase(
214 ProgressReceiver *prog, ProgressPhase phase)
215 { prog->vt->start_phase(prog, phase); }
progress_report(ProgressReceiver * prog,double progress)216 static inline void progress_report(ProgressReceiver *prog, double progress)
217 { prog->vt->report(prog, progress); }
progress_report_attempt(ProgressReceiver * prog)218 static inline void progress_report_attempt(ProgressReceiver *prog)
219 { prog->vt->report_attempt(prog); }
progress_report_phase_complete(ProgressReceiver * prog)220 static inline void progress_report_phase_complete(ProgressReceiver *prog)
221 { prog->vt->report_phase_complete(prog); }
222
223 ProgressPhase null_progress_add_linear(
224 ProgressReceiver *prog, double c);
225 ProgressPhase null_progress_add_probabilistic(
226 ProgressReceiver *prog, double c, double p);
227 void null_progress_ready(ProgressReceiver *prog);
228 void null_progress_start_phase(ProgressReceiver *prog, ProgressPhase phase);
229 void null_progress_report(ProgressReceiver *prog, double progress);
230 void null_progress_report_attempt(ProgressReceiver *prog);
231 void null_progress_report_phase_complete(ProgressReceiver *prog);
232 extern const ProgressReceiverVtable null_progress_vt;
233
234 /* A helper function for dreaming up progress cost estimates. */
235 double estimate_modexp_cost(unsigned bits);
236
237 /* ----------------------------------------------------------------------
238 * The top-level API for generating primes.
239 */
240
241 typedef struct PrimeGenerationPolicy PrimeGenerationPolicy;
242 typedef struct PrimeGenerationContext PrimeGenerationContext;
243
244 struct PrimeGenerationContext {
245 const PrimeGenerationPolicy *vt;
246 };
247
248 struct PrimeGenerationPolicy {
249 ProgressPhase (*add_progress_phase)(const PrimeGenerationPolicy *policy,
250 ProgressReceiver *prog, unsigned bits);
251 PrimeGenerationContext *(*new_context)(
252 const PrimeGenerationPolicy *policy);
253 void (*free_context)(PrimeGenerationContext *ctx);
254 mp_int *(*generate)(
255 PrimeGenerationContext *ctx,
256 PrimeCandidateSource *pcs, ProgressReceiver *prog);
257 strbuf *(*mpu_certificate)(PrimeGenerationContext *ctx, mp_int *p);
258
259 const void *extra; /* additional data a particular impl might need */
260 };
261
primegen_add_progress_phase(PrimeGenerationContext * ctx,ProgressReceiver * prog,unsigned bits)262 static inline ProgressPhase primegen_add_progress_phase(
263 PrimeGenerationContext *ctx, ProgressReceiver *prog, unsigned bits)
264 { return ctx->vt->add_progress_phase(ctx->vt, prog, bits); }
primegen_new_context(const PrimeGenerationPolicy * policy)265 static inline PrimeGenerationContext *primegen_new_context(
266 const PrimeGenerationPolicy *policy)
267 { return policy->new_context(policy); }
primegen_free_context(PrimeGenerationContext * ctx)268 static inline void primegen_free_context(PrimeGenerationContext *ctx)
269 { ctx->vt->free_context(ctx); }
primegen_generate(PrimeGenerationContext * ctx,PrimeCandidateSource * pcs,ProgressReceiver * prog)270 static inline mp_int *primegen_generate(
271 PrimeGenerationContext *ctx,
272 PrimeCandidateSource *pcs, ProgressReceiver *prog)
273 { return ctx->vt->generate(ctx, pcs, prog); }
primegen_mpu_certificate(PrimeGenerationContext * ctx,mp_int * p)274 static inline strbuf *primegen_mpu_certificate(
275 PrimeGenerationContext *ctx, mp_int *p)
276 { return ctx->vt->mpu_certificate(ctx, p); }
277
278 extern const PrimeGenerationPolicy primegen_probabilistic;
279 extern const PrimeGenerationPolicy primegen_provable_fast;
280 extern const PrimeGenerationPolicy primegen_provable_maurer_simple;
281 extern const PrimeGenerationPolicy primegen_provable_maurer_complex;
282
283 /* ----------------------------------------------------------------------
284 * The overall top-level API for generating entire key pairs.
285 */
286
287 int rsa_generate(RSAKey *key, int bits, bool strong,
288 PrimeGenerationContext *pgc, ProgressReceiver *prog);
289 int dsa_generate(struct dss_key *key, int bits, PrimeGenerationContext *pgc,
290 ProgressReceiver *prog);
291 int ecdsa_generate(struct ecdsa_key *key, int bits);
292 int eddsa_generate(struct eddsa_key *key, int bits);
293