pock.1: Fix Pocklington proof.

[catacomb-python] / pock.1

.\" -*-nroff-*-
.\"
.\" Describe the primality certificate generator and checker
.\"
.\" (c) 2016 Straylight/Edgeware
.\"
.
.\"----- Licensing notice ---------------------------------------------------
.\"
.\" This file is part of the Python interface to Catacomb.
.\"
.\" Catacomb/Python is free software; you can redistribute it and/or modify
.\" it under the terms of the GNU General Public License as published by
.\" the Free Software Foundation; either version 2 of the License, or
.\" (at your option) any later version.
.\"
.\" Catacomb/Python is distributed in the hope that it will be useful,
.\" but WITHOUT ANY WARRANTY; without even the implied warranty of
.\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
.\" GNU General Public License for more details.
.\"
.\" You should have received a copy of the GNU General Public License
.\" along with Catacomb/Python; if not, write to the Free Software Foundation,
.\" Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
.
.ie t \{\
.  if \n(.g \{\
.    fam P
.  \}
.  ds o \(bu
.  ds ss \s7\v'-4p'
.  ds se \v'4p'\s0
.  ds us \s7\v'2p'
.  ds ue \v'-2p'\s0
.  ds *e \(*e
.  ds mo \(mo
.  ds sr \(sr
.  ds cu \(cu
.  ds ca \(ca
.  ds iy \(if
.  ds == \(==
.  ds .. \&.\h'2p'.\h'2p'.\&
.  ds /= \h'(\w'\*(=='-\w'/')/2'/\h'-(\w'\*(=='+\w'/')/2'\*(==
.\}
.el \{\
.  ds o o
.  ds ss ^
.  ds se
.  ds us _
.  ds ue
.  ds *e \fIepsilon\fP
.  ds mo in
.  ds sr sqrt
.  ds cu union
.  ds ca isect
.  ds iy infty
.  ds == ==
.  ds .. \&...\&
.  ds /= /==
.\}
.de hP
.IP
\h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
..
.
.TH pock 1 "28 May 2017" "Straylight/Edgeware" "Catacomb cryptographic library"
.SH NAME
pock \- generate and verify primality certificates
.
.\"--------------------------------------------------------------------------
.SH SYNOPSIS
.
.B pock
.RB [ \-qv ]
.I command
.IR [ arguments ...]
.PP
Subcommands:
.RS
.br
.B gen
.I nbits
.br
.B ll
.I nbits
.I nsubbits
.br
.B check
.RI [ file ]
.RE
.
.\"--------------------------------------------------------------------------
.SH DESCRIPTION
.
Many cryptographic protocols make use of large prime numbers.
The usual way of determining primality in such circumstances
is due to Rabin and Miller.
Given a candidate
.I n
and a
.I witness
2 \(<=
.I a
<
.IR n ,
the test answers either `composite' or `unknown'.
If
.I n
is prime then the test answers `unknown' for every witness
.IR a ;
if
.I n
is in fact composite
then the test answers `composite'
for at least three quarters of the possible witnesses.
If
.I n
is a composite,
then the witnesses
.I a
for which the test reports `unknown'
are called
.IR liars .
.PP
Naively, then,
to reduce the probability of falsely accepting a composite
below some bound \*(*e,
one must perform
\-(log\*(us2\*(ue \*(*e)/2
iterations of the test,
with independent, uniformly distributed witnesses.
This is especially slow when high security levels are wanted,
both because tests take longer on larger candidate numbers,
and because one must do more tests
to reach the necessary higher confidence level.
.PP
The above is a worst-case bound:
very few composite numbers
.I n
have anywhere near
.IR n /4
liars.
In situations such as RSA key generation,
the user generating the prime number is the only one
who must be convinced of the number's primality,
and they have valuable additional knowledge:
specifically that the candidate has been chosen at random
according to some suitable probability distribution.
In this case, one needs many fewer iterations,
and the number of iterations needed
.I decreases
with the size of the candidate being tested.
.PP
But in cases where many users must share some large prime parameter,
each of them must test the proposed prime separately,
and often they must pessimistically assume
that the number was chosen maliciously,
and the worst-case
.IR n /4
bound is the best one can do using the Rabin\(enMiller test.
For large candidates,
this is inconveniently slow.
(Also, many implementations incorrectly use
a number of iterations suitable for randomly chosen primes
for testing candidates of unknown provenance.)
.PP
There
.I are
stronger probabilistic tests.
A combination of Rabin\(enMiller and
Grantham's Frobenius test
is known as the
Baillie\(enPSW test
(after Baillie, Pomerance, Selfridge, and Wagstaff);
there are
.I no
known composites which pass this test,
nor is it known how to construct any.
On the other hand, it's been conjectured that
infinitely many Baillie\(enPSW pseudoprimes exist.
While it may be reasonable to assume
the strength of the Baillie\(enPSW test,
it must be borne in mind that this
.I does
constitute a security assumption.
.PP
By contrast,the
.B pock
program will generate prime numbers
of sizes suitable for use in cryptography,
along with a
.I certificate of primality
which can be independently verified fairly efficiently.
Specifically, verifying a proof takes a little longer
than a single iteration of the Rabin\(enMiller probabilistic test.
It can also verify such certificates.
.PP
Note that the primes selected by
.B pock
are a long way from uniformly distributed.
Indeed, they have somewhat unusual structure,
but it seems unlikely that this structure
renders them unsuitable for e.g., discrete-logarithm cryptography.
.
.SS "Command line"
The following options are recognized.
.TP
.B "\-h, \-\-help"
Write help text to standard output and exit with status 0.
.TP
.B "\-q, \-\-quiet"
Be less verbose during prime generation or certificate verification.
.TP
.B "\-v, \-\-verbose"
Be more verbose during prime generation or certificate verification.
.TP
.BI "\-s, \-\-sievebits " b
When generating certificates,
require that the verifier can check numbers smaller than
.RI 2\*(ss b \*(se
without assistance.
Larger values lead to sightly shorter proofs,
but spend more time at startup constructing a sieve;
smaller values lead to somewhat longer proofs,
but spend less time constructing the sieve.
The default is 32,
which seems to work well in practice.
.
.SS "gen"
The
.B gen
command generates a prime
.I p
which is
.I nbits
long (i.e.,
.RI 2\*(ss nbits \-1\*(se
<
.I p
<
.RI 2\*(ss nbits \*(se,
and writes a certificate to standard output.
By default, mysterious runes are written to standard error
to keep the user amused and informed about the operation's progress;
the
.B \-q
option suppresses the runes;
the
.B \-v
option produces more detailed runes.
.
.SS "ll"
The
.B ll
command generates a Lim\(enLee prime
.I p
=
2
.IR q \*(us0\*(ue
.IR q \*(us1\*(ue
\*(..
.IR q \*(us k \*(ue
+
1
which is
.I nbits
long (i.e.,
.RI 2\*(ss nbits \-1\*(se
<
.I p
<
.RI 2\*(ss nbits \*(se,
such that each
.IR q \*(us i \*(ue
is an
.IR nsubbits -bit
prime, for
0 \(<=
.I i
<
.IR k ,
and
.IR q \*(us k \*(ue
is an
.IR nsubbits -bit
prime,
and writes a certificate to standard output.
By default, mysterious runes are written to standard error
to keep the user amused and informed about the operation's progress;
the
.B \-q
option suppresses the runes;
the
.B \-v
option produces more detailed runes.
.
.SS "check"
The
.B check
command reads a primality certificate from the named
.I file
or from standard input,
and checks it.
By default,
each
.B check
line in the certificate causes a line
.IP
.B ;;
.I label
.B =
.I n
.BI [ b ]
.PP
to be printed to standard output,
listing the prime's
.IR label ,
value
.IR n ,
and length
.I b
in bits;
this behaviour is inhibited by the
.B \-q
option.
.
.SS Runes
The following mysterious runes are printed during prime searches.
This information is provided for diagnostic purposes
and to satisfy idle curiosity:
later versions may print different runes,
or use the same rune characters to mean different things.
.TP
.B !
Started to generate a large prime.
The next step is to generate a number of smaller primes.
Usually, this will only need to be done once.
.TP
.B .
Candidate failed a Fermat test.
.TP
.B *
Candidate passed a Fermat test.
This is usually the last rune for a prime search.
.TP
.B @
A candidate generator failed to generate the necessary subgroup.
This is unusual.
.TP
.B <
For Lim\(enLee primes,
discarding the large prime
because it produces results which are too small.
.TP
.B >
For Lim\(enLee primes,
discarding the large prime
because it produces results which are too large.
.TP
.B [
Starting a subsidiary prime search.
.TP
.B ]
Finished a subsidiary prime search.
.
.\"--------------------------------------------------------------------------
.SH CERTIFICATE FORMAT
.
A certificate consists of a number of lines.
Blank lines,
and lines beginning with a
.RB ` ; ',
are ignored.
Other lines are as follows.
.TP
.BI "sievebits " b
Declares that the verifier is expected to be able to check
primes smaller than
.RI 2\*(ss b \*(se
for primality for itself.
A
.B sievebits
line must appear before the first
.B small
line.
.TP
.BI "small " label " = " p
Asserts that
.I p
is a small prime,
and associates it with the
.IR label .
It is an error if the label has been assigned by a previous line.
It is required that
1 <
.I p
<
.RI 2\*(ss b \*(se
and that
.I p
is prime.
Such small primes constitute the leaves of a proof tree.
.TP
.BI "pock " label " = " a ", " R ", [" i ", " j ", \fR\*(..\fB]"
Asserts that a number
.I n
(defined below) is prime by Pocklington's criterion,
and associates it with the
.IR label .
It is an error if the label has been assigned by a previous line.
.RS
.PP
The strings
.IR i ,
.IR j ,
\*(..
must be labels assigned by earlier lines.
For each such label
.IR i ,
let
.IR q \*(us i \*(ue
be the associated prime.
Let
.I Q
=
.IR q \*(us i \*(ue
.IR q \*(us j \*(ue
\*(..
be the product of these primes.
Let
.I n
=
.RI 2 QR
+
1.
It is required that:
.hP 1.
The
.IR q \*(us i \*(ue
are distinct.
.hP 2.
.IR Q \*(ss2\*(se
\(>=
.IR n .
.hP 3.
.IR a \*(ss n \-1\*(se
\*(==
1
(mod
.IR n ).
.hP 4.
.RI gcd( a \*(ss( n \-1)/ q \*(se
\-
1,
.IR n )
=
1
for each prime
.IR q
dividing
.IR Q .
.PP
To see why this works, let
.I p
be the smallest prime factor of
.IR n .
From
.B 3
we see that
the order of
.I a
in
.RB ( Z /\fIp Z )\*(ss\(**\*(se
divides
.I p
\-
1.
Consider some prime
.I q
dividing
.I Q
and let
.I t
=
.IR a \*(ss( n \-1)/ q \*(se;
then
.I t
has order dividing
.IR q .
From
.BR 4 ,
we have
.I t
\*(/=
1
(mod
.IR p ),
and hence
.I t
has order precisely
.I q
in
.RB ( Z /\fIp Z )\*(ss\(**\*(se.
This implies that
.I q
divides
.I p
\-
1.
Since this holds for each prime
.I q
dividing
.IR Q ,
and,
from
.BR 1 ,
the
.I q
are distinct,
we deduce that
.I Q
divides
.I p
\-
1
and hence that
.I p
>
.IR Q .
Let
.IR p \(fm
be any prime factor of
.IR n / p .
Then
.IR p \(fm
\(>=
.I p
>
.I Q
so,
from
.BR 2 ,
.IR pp \(fm
>
.IR Q \*(ss2\*(se
\(>=
.IR n ;
but
.IR pp \(fm
divides
.I n
so this is a contradiction.
We must conclude that
.IR p \(fm
does not exist,
and
.I n
must be prime.
.RE
.TP
.BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]"
Asserts that the number
.I n
is prime by Goldwasser and Kilian's ECPP method,
and associates it with the
.IR label .
It is an error if the label has been assigned by a previous line.
.RS
.PP
The strings
.IR i ,
.IR j ,
\*..
must be labels assigned by earlier lines.
For each such label
.IR i ,
let
.IR q \*(us i \*(ue
be the associated prime.
Let
.I Q
=
.IR q \*(us i \*(ue
.IR q \*(us j \*(ue
\*(..
be the product of these primes.
Define
.I E\*(usn\*(ue
= {
.RI ( x ", " y )
\*(mo
.RB ( Z /\fIn Z )\*(ss2\*(se
|
.IR y \*(ss2\*(se
=
.IR x \*(ss3\*(se
+
.I Ax
+
.I B
}
\*(cu
{ \*(iy };
if
.I n
is prime and the curve is not singular
then this is the elliptic curve over
.RI GF( n )
with short-Weierstrass coefficients
.I A
and
.IR B .
Let
.I R
=
.RI ( x ,
.IR y ).
It is required that:
.hP 1.
.I g
=
.RI gcd(4 a \*(ss3\*(se
+
.RI 27 b \*(ss2\*(se,
.IR n )
= 1.
.hP 2.
.I R
\*(mo
.IR E\*(usn\*(ue ;
i.e.,
.IR y \*(ss2\*(se
\*(==
.IR x \*(ss3\*(se
+
.I Ax
+
.I B
(mod
.IR n ).
.hP 3. The
.I q\*(usi\*(ue
are distinct.
.hP 4.
.IR QR ,
the elliptic-curve scalar product of the point
.I R
by the integer
.IR Q ,
calculated as if
.I E
is a true elliptic curve,
is the point at infinity.
.hP 5.
.RI ( Q / q ) R
is finite for each prime
.I q
dividing
.IR Q .
.hP 6.
.I Q
>
.RI ( n \*(ss1/4\*(se
+ 1)\*(ss2\*(se.
.PP
To see why this test works, let
.I p
be the smallest prime factor of
.IR n ,
and let
.I E\*(usp\*(ue
= {
.RI ( x ", " y )
\*(mo
.RI GF( p )\*(ss2\*(se
|
.IR y \*(ss2\*(se
=
.IR x \*(ss3\*(se
+
.I Ax
+
.I B
}
\*(cu
{ \*(iy }.
From
.BR 1 ,
.I g
= 1,
.I E\*(usp\*(ue
is an elliptic curve.
(If 1 <
.I g
<
.I n
then
.I g
is a proper factor of
.I n
and
.I n
is certainly not prime;
if
.I g
=
.I n
then the curve will be singular and the test fails.)
From
.BR 2 ,
.I R
is a point on
.IR E\*(usp\*(ue .
From
.BR 4 ,
.I R
has
.IR Q -torsion
in
.IR E\*(usp\*(ue .
Consider some prime
.I q
dividing
.I Q
and let
.I T
=
.RI ( Q/q ) R ;
then
.I T
has torsion dividing
.IR q .
From
.BR 5 ,
.RI ( Q/q ) R
\(!= 0,
and hence
.I T
has order precisely
.I q
in
.IR E\*(usp\*(ue .
This implies that
.I q
divides
.RI # E\*(usp\*(ue .
Since this holds for each prime
.I q
dividing
.IR Q ,
and, from
.BR 3 ,
the
.I q
are distinct,
we deduce that
.I Q
divides
.RI # E\*(usp\*(ue
and hence that
.RI # E\*(usp\*(ue
\(>=
.IR Q .
Hasse's theorem tells us that
.RI | p
+ 1 \-
.RI # E\*(usp\*(ue |
\(<=
.RI 2\*(sr p ,
whence
.I p
+ 1 +
.RI 2\*(sr p
=
.RI (\*(sr p
+ 1)\*(ss2\*(se
\(>=
.RI # E\*(usp\*(ue
\(>=
.IR Q
>
.RI ( n \*(ss1/4\*(se
+ 1)\*(ss2\*(se
(from
.BR 6 );
so
.IR p\*(ss2\*(se
>
.IR n .
Let
.IR p \(fm
be any prime factor of
.IR n / p .
Then
.IR p \(fm
\(>=
.I p
and
.IR pp \(fm
\(>=
.IR p \*(ss2\*(se
>
.IR n ;
but
.IR pp \(fm
divides
.I n
so this is a contradiction.
We must conclude that
.IR p \(fm
does not exist,
and
.I n
must be prime.
.PP
Note that
.B pock
currently cannot generate proofs which use
.BR ecpp ,
though it will verify them.
.RE
.TP
.BI "check " label ", " b ", " p
Verify that the prime associated with the
.I label
is equal to
.I p
and that it is
.I b
bits long;
i.e., that
.RI 2\*(ss b \-1\*(se
\(<=
.I p
<
.RI 2\*(ss b \*(se.
Unless
inhibited by
.BR \-q ,
the label and value are printed to stdout during verification.
.
.\"--------------------------------------------------------------------------
.SH "SEE ALSO"
.BR key (1).
.SH AUTHOR
Mark Wooding, <mdw@distorted.org.uk>
.
.\"----- That's all, folks --------------------------------------------------