3 .\" Describe the primality certificate generator and checker
5 .\" (c) 2016 Straylight/Edgeware
8 .\"----- Licensing notice ---------------------------------------------------
10 .\" This file is part of the Python interface to Catacomb.
12 .\" Catacomb/Python is free software; you can redistribute it and/or modify
13 .\" it under the terms of the GNU General Public License as published by
14 .\" the Free Software Foundation; either version 2 of the License, or
15 .\" (at your option) any later version.
17 .\" Catacomb/Python is distributed in the hope that it will be useful,
18 .\" but WITHOUT ANY WARRANTY; without even the implied warranty of
19 .\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 .\" GNU General Public License for more details.
22 .\" You should have received a copy of the GNU General Public License
23 .\" along with Catacomb/Python; if not, write to the Free Software Foundation,
24 .\" Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
42 . ds .. \&.\h'2p'.\h'2p'.\&
43 . ds /= \h'(\w'\*(=='-\w'/')/2'/\h'-(\w'\*(=='+\w'/')/2'\*(==
63 \h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
66 .TH pock 1 "28 May 2017" "Straylight/Edgeware" "Catacomb cryptographic library"
68 pock \- generate and verify primality certificates
70 .\"--------------------------------------------------------------------------
92 .\"--------------------------------------------------------------------------
95 Many cryptographic protocols make use of large prime numbers.
96 The usual way of determining primality in such circumstances
97 is due to Rabin and Miller.
106 the test answers either `composite' or `unknown'.
109 is prime then the test answers `unknown' for every witness
114 then the test answers `composite'
115 for at least three quarters of the possible witnesses.
121 for which the test reports `unknown'
126 to reduce the probability of falsely accepting a composite
127 below some bound \*(*e,
129 \-(log\*(us2\*(ue \*(*e)/2
130 iterations of the test,
131 with independent, uniformly distributed witnesses.
132 This is especially slow when high security levels are wanted,
133 both because tests take longer on larger candidate numbers,
134 and because one must do more tests
135 to reach the necessary higher confidence level.
137 The above is a worst-case bound:
138 very few composite numbers
143 In situations such as RSA key generation,
144 the user generating the prime number is the only one
145 who must be convinced of the number's primality,
146 and they have valuable additional knowledge:
147 specifically that the candidate has been chosen at random
148 according to some suitable probability distribution.
149 In this case, one needs many fewer iterations,
150 and the number of iterations needed
152 with the size of the candidate being tested.
154 But in cases where many users must share some large prime parameter,
155 each of them must test the proposed prime separately,
156 and often they must pessimistically assume
157 that the number was chosen maliciously,
160 bound is the best one can do using the Rabin\(enMiller test.
161 For large candidates,
162 this is inconveniently slow.
163 (Also, many implementations incorrectly use
164 a number of iterations suitable for randomly chosen primes
165 for testing candidates of unknown provenance.)
169 stronger probabilistic tests.
170 A combination of Rabin\(enMiller and
171 Grantham's Frobenius test
174 (after Baillie, Pomerance, Selfridge, and Wagstaff);
177 known composites which pass this test,
178 nor is it known how to construct any.
179 On the other hand, it's been conjectured that
180 infinitely many Baillie\(enPSW pseudoprimes exist.
181 While it may be reasonable to assume
182 the strength of the Baillie\(enPSW test,
183 it must be borne in mind that this
185 constitute a security assumption.
189 program will generate prime numbers
190 of sizes suitable for use in cryptography,
192 .I certificate of primality
193 which can be independently verified fairly efficiently.
194 Specifically, verifying a proof takes a little longer
195 than a single iteration of the Rabin\(enMiller probabilistic test.
196 It can also verify such certificates.
198 Note that the primes selected by
200 are a long way from uniformly distributed.
201 Indeed, they have somewhat unusual structure,
202 but it seems unlikely that this structure
203 renders them unsuitable for e.g., discrete-logarithm cryptography.
206 The following options are recognized.
209 Write help text to standard output and exit with status 0.
212 Be less verbose during prime generation or certificate verification.
214 .B "\-v, \-\-verbose"
215 Be more verbose during prime generation or certificate verification.
217 .BI "\-s, \-\-sievebits " b
218 When generating certificates,
219 require that the verifier can check numbers smaller than
222 Larger values lead to sightly shorter proofs,
223 but spend more time at startup constructing a sieve;
224 smaller values lead to somewhat longer proofs,
225 but spend less time constructing the sieve.
227 which seems to work well in practice.
232 command generates a prime
237 .RI 2\*(ss nbits \-1\*(se
241 .RI 2\*(ss nbits \*(se,
242 and writes a certificate to standard output.
243 By default, mysterious runes are written to standard error
244 to keep the user amused and informed about the operation's progress;
247 option suppresses the runes;
250 option produces more detailed runes.
255 command generates a Lim\(enLee prime
268 .RI 2\*(ss nbits \-1\*(se
272 .RI 2\*(ss nbits \*(se,
287 and writes a certificate to standard output.
288 By default, mysterious runes are written to standard error
289 to keep the user amused and informed about the operation's progress;
292 option suppresses the runes;
295 option produces more detailed runes.
300 command reads a primality certificate from the named
302 or from standard input,
307 line in the certificate causes a line
315 to be printed to standard output,
323 this behaviour is inhibited by the
328 The following mysterious runes are printed during prime searches.
329 This information is provided for diagnostic purposes
330 and to satisfy idle curiosity:
331 later versions may print different runes,
332 or use the same rune characters to mean different things.
335 Started to generate a large prime.
336 The next step is to generate a number of smaller primes.
337 Usually, this will only need to be done once.
340 Candidate failed a Fermat test.
343 Candidate passed a Fermat test.
344 This is usually the last rune for a prime search.
347 A candidate generator failed to generate the necessary subgroup.
351 For Lim\(enLee primes,
352 discarding the large prime
353 because it produces results which are too small.
356 For Lim\(enLee primes,
357 discarding the large prime
358 because it produces results which are too large.
361 Starting a subsidiary prime search.
364 Finished a subsidiary prime search.
366 .\"--------------------------------------------------------------------------
367 .SH CERTIFICATE FORMAT
369 A certificate consists of a number of lines.
371 and lines beginning with a
374 Other lines are as follows.
377 Declares that the verifier is expected to be able to check
380 for primality for itself.
383 line must appear before the first
387 .BI "small " label " = " p
391 and associates it with the
393 It is an error if the label has been assigned by a previous line.
402 Such small primes constitute the leaves of a proof tree.
404 .BI "pock " label " = " a ", " R ", [" i ", " j ", \fR\*(..\fB]"
405 Asserts that a number
407 (defined below) is prime by Pocklington's criterion,
408 and associates it with the
410 It is an error if the label has been assigned by a previous line.
417 must be labels assigned by earlier lines.
422 be the associated prime.
429 be the product of these primes.
446 .IR a \*(ss n \-1\*(se
452 .RI gcd( a \*(ss( n \-1)/ q \*(se
463 To see why this works, let
465 be the smallest prime factor of
473 .RB ( Z /\fIp Z )\*(ss\(**\*(se
485 .IR a \*(ss( n \-1)/ q \*(se;
503 .RB ( Z /\fIp Z )\*(ss\(**\*(se.
510 Since this holds for each prime
532 be any prime factor of
552 so this is a contradiction.
553 We must conclude that
561 .BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]"
562 Asserts that the number
564 is prime by Goldwasser and Kilian's ECPP method,
565 and associates it with the
567 It is an error if the label has been assigned by a previous line.
574 must be labels assigned by earlier lines.
579 be the associated prime.
586 be the product of these primes.
592 .RB ( Z /\fIn Z )\*(ss2\*(se
606 is prime and the curve is not singular
607 then this is the elliptic curve over
609 with short-Weierstrass coefficients
622 .RI gcd(4 a \*(ss3\*(se
624 .RI 27 b \*(ss2\*(se,
646 the elliptic-curve scalar product of the point
652 is a true elliptic curve,
653 is the point at infinity.
656 is finite for each prime
663 .RI ( n \*(ss1/4\*(se
666 To see why this test works, let
668 be the smallest prime factor of
675 .RI GF( p )\*(ss2\*(se
692 is an elliptic curve.
699 is a proper factor of
703 is certainly not prime;
708 then the curve will be singular and the test fails.)
747 Since this holds for each prime
764 Hasse's theorem tells us that
782 .RI ( n \*(ss1/4\*(se
792 be any prime factor of
808 so this is a contradiction.
809 We must conclude that
818 currently cannot generate proofs which use
820 though it will verify them.
823 .BI "check " label ", " b ", " p
824 Verify that the prime associated with the
832 .RI 2\*(ss b \-1\*(se
840 the label and value are printed to stdout during verification.
842 .\"--------------------------------------------------------------------------
846 Mark Wooding, <mdw@distorted.org.uk>
848 .\"----- That's all, folks --------------------------------------------------