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
517 these primes are distinct,
530 be any prime factor of
550 so this is a contradiction.
551 We must conclude that
559 .BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]"
560 Asserts that the number
562 is prime by Goldwasser and Kilian's ECPP method,
563 and associates it with the
565 It is an error if the label has been assigned by a previous line.
572 must be labels assigned by earlier lines.
577 be the associated prime.
584 be the product of these primes.
590 .RB ( Z /\fIn Z )\*(ss2\*(se
604 is prime and the curve is not singular
605 then this is the elliptic curve over
607 with short-Weierstrass coefficients
620 .RI gcd(4 a \*(ss3\*(se
622 .RI 27 b \*(ss2\*(se,
644 the elliptic-curve scalar product of the point
650 is a true elliptic curve,
651 is the point at infinity.
654 is finite for each prime
661 .RI ( n \*(ss1/4\*(se
664 To see why this test works, let
666 be the smallest prime factor of
673 .RI GF( p )\*(ss2\*(se
690 is an elliptic curve.
697 is a proper factor of
701 is certainly not prime;
706 then the curve will be singular and the test fails.)
745 Since this holds for each prime
762 Hasse's theorem tells us that
787 .RI ( n \*(ss1/4\*(se
797 be any prime factor of
813 so this is a contradiction.
814 We must conclude that
823 currently cannot generate proofs which use
825 though it will verify them.
828 .BI "check " label ", " b ", " p
829 Verify that the prime associated with the
837 .RI 2\*(ss b \-1\*(se
845 the label and value are printed to stdout during verification.
847 .\"--------------------------------------------------------------------------
851 Mark Wooding, <mdw@distorted.org.uk>
853 .\"----- That's all, folks --------------------------------------------------