Generate MPU certificates for proven primes.

Conveniently checkable certificates of primality aren't a new concept.
I didn't invent them, and I wasn't the first to implement them. Given
that, I thought it might be useful to be able to independently verify
a prime generated by PuTTY's provable prime system. Then, even if you
don't trust _this_ code, you might still trust someone else's
verifier, or at least be less willing to believe that both were
colluding.

The Perl module Math::Prime::Util is the only free software I've found
that defines a specific text-file format for certificates of
primality. The MPU format (as it calls it) supports various different
methods of certifying the primality of a number (most of which, like
Pockle's, depend on having previously proved some smaller number(s) to
be prime). The system implemented by Pockle is on its list: MPU calls
it by the name "BLS5".

So this commit introduces extra stored data inside Pockle so that it
remembers not just _that_ it believes certain numbers to be prime, but
also _why_ it believed each one to be prime. Then there's an extra
method in the Pockle API to translate its internal data structures
into the text of an MPU certificate for any number it knows about.

Math::Prime::Util doesn't come with a command-line verification tool,
unfortunately; only a Perl function which you feed a string argument.
So also in this commit I add test/mpu-check.pl, which is a trivial
command-line client of that function.

At the moment, this new piece of API is only exposed via testcrypt. I
could easily put some user interface into the key generation tools
that would save a few primality certificates alongside the private
key, but I have yet to think of any good reason to do it. Mostly this
facility is intended for debugging and cross-checking of the
_algorithm_, not of any particular prime.

1 files changed, 8 insertions, 0 deletions

diff --git a/sshkeygen.h b/sshkeygen.h
index f8c3a370..7dddcc5c 100644
--- a/sshkeygen.h
+++ b/sshkeygen.h
@@ -161,6 +161,10 @@ void pockle_release(Pockle *pockle, size_t mark);
 /* Free a Pockle. */
 void pockle_free(Pockle *pockle);
 
+/* Generate a certificate of primality for a prime already known to
+ * the Pockle, in a format acceptable to Math::Prime::Util. */
+strbuf *pockle_mpu(Pockle *pockle, mp_int *p);
+
 /* ----------------------------------------------------------------------
  * Callback API that allows key generation to report progress to its
  * caller.
@@ -243,6 +247,7 @@ struct PrimeGenerationPolicy {
     mp_int *(*generate)(
         PrimeGenerationContext *ctx,
         PrimeCandidateSource *pcs, ProgressReceiver *prog);
+    strbuf *(*mpu_certificate)(PrimeGenerationContext *ctx, mp_int *p);
 
     const void *extra; /* additional data a particular impl might need */
 };
@@ -259,6 +264,9 @@ static inline mp_int *primegen_generate(
     PrimeGenerationContext *ctx,
     PrimeCandidateSource *pcs, ProgressReceiver *prog)
 { return ctx->vt->generate(ctx, pcs, prog); }
+static inline strbuf *primegen_mpu_certificate(
+    PrimeGenerationContext *ctx, mp_int *p)
+{ return ctx->vt->mpu_certificate(ctx, p); }
 
 extern const PrimeGenerationPolicy primegen_probabilistic;
 extern const PrimeGenerationPolicy primegen_provable_fast;