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.
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 program will generate prime numbers
170 of sizes suitable for use in cryptography,
172 .I certificate of primality
173 which can be independently verified fairly efficiently.
174 Specifically, verifying a proof takes a little longer
175 than a single iteration of the Rabin\(enMiller probabilistic test.
176 It can also verify such certificates.
178 Note that the primes selected by
180 are a long way from uniformly distributed.
181 Indeed, they have somewhat unusual structure,
182 but it seems unlikely that this structure
183 renders them unsuitable for e.g., discrete-logarithm cryptography.
186 The following options are recognized.
189 Write help text to standard output and exit with status 0.
192 Be less verbose during prime generation or certificate verification.
194 .B "\-v, \-\-verbose"
195 Be more verbose during prime generation or certificate verification.
197 .BI "\-s, \-\-sievebits " b
198 When generating certificates,
199 require that the verifier can check numbers smaller than
202 Larger values lead to sightly shorter proofs,
203 but spend more time at startup constructing a sieve;
204 smaller values lead to somewhat longer proofs,
205 but spend less time constructing the sieve.
207 which seems to work well in practice.
212 command generates a prime
217 .RI 2\*(ss nbits \-1\*(se
221 .RI 2\*(ss nbits \*(se,
222 and writes a certificate to standard output.
223 By default, mysterious runes are written to standard error
224 to keep the user amused and informed about the operation's progress;
227 option suppresses the runes;
230 option produces more detailed runes.
235 command generates a Lim\(enLee prime
248 .RI 2\*(ss nbits \-1\*(se
252 .RI 2\*(ss nbits \*(se,
267 and writes a certificate to standard output.
268 By default, mysterious runes are written to standard error
269 to keep the user amused and informed about the operation's progress;
272 option suppresses the runes;
275 option produces more detailed runes.
280 command reads a primality certificate from the named
282 or from standard input,
287 line in the certificate causes a line
295 to be printed to standard output,
303 this behaviour is inhibited by the
308 The following mysterious runes are printed during prime searches.
309 This information is provided for diagnostic purposes
310 and to satisfy idle curiosity:
311 later versions may print different runes,
312 or use the same rune characters to mean different things.
315 Started to generate a large prime.
316 The next step is to generate a number of smaller primes.
317 Usually, this will only need to be done once.
320 Candidate failed a Fermat test.
323 Candidate passed a Fermat test.
324 This is usually the last rune for a prime search.
327 A candidate generator failed to generate the necessary subgroup.
331 For Lim\(enLee primes,
332 discarding the large prime
333 because it produces results which are too small.
336 For Lim\(enLee primes,
337 discarding the large prime
338 because it produces results which are too large.
341 Starting a subsidiary prime search.
344 Finished a subsidiary prime search.
346 .\"--------------------------------------------------------------------------
347 .SH CERTIFICATE FORMAT
349 A certificate consists of a number of lines.
351 and lines beginning with a
354 Other lines are as follows.
357 Declares that the verifier is expected to be able to check
360 for primality for itself.
363 line must appear before the first
367 .BI "small " label " = " p
371 and associates it with the
373 It is an error if the label has been assigned by a previous line.
382 Such small primes constitute the leaves of a proof tree.
384 .BI "pock " label " = " a ", " R ", [" i ", " j ", \fR\*(..\fB]"
385 Asserts that a number
387 (defined below) is prime by Pocklington's criterion,
388 and associates it with the
390 It is an error if the label has been assigned by a previous line.
397 must be labels assigned by earlier lines.
402 be the associated prime.
409 be the product of these primes.
426 .IR a \*(ss n \-1\*(se
432 .RI gcd( a \*(ss( n \-1)/ q \*(se
443 To see why this works, let
445 be the smallest prime factor of
453 .RB ( Z /\fIp Z )\*(ss\(**\*(se
465 .IR a \*(ss( n \-1)/ q \*(se;
483 .RB ( Z /\fIp Z )\*(ss\(**\*(se.
490 Since this holds for each prime
512 be any prime factor of
532 so this is a contradiction.
533 We must conclude that
541 .BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]"
542 Asserts that the number
544 is prime by Goldwasser and Kilian's ECPP method,
545 and associates it with the
547 It is an error if the label has been assigned by a previous line.
554 must be labels assigned by earlier lines.
559 be the associated prime.
566 be the product of these primes.
572 .RB ( Z /\fIn Z )\*(ss2\*(se
586 is prime and the curve is not singular
587 then this is the elliptic curve over
589 with short-Weierstrass coefficients
602 .RI gcd(4 a \*(ss3\*(se
604 .RI 27 b \*(ss2\*(se,
626 the elliptic-curve scalar product of the point
632 is a true elliptic curve,
633 is the point at infinity.
636 is finite for each prime
643 .RI ( n \*(ss1/4\*(se
646 To see why this test works, let
648 be the smallest prime factor of
655 .RI GF( p )\*(ss2\*(se
672 is an elliptic curve.
679 is a proper factor of
683 is certainly not prime;
688 then the curve will be singular and the test fails.)
727 Since this holds for each prime
744 Hasse's theorem tells us that
762 .RI ( n \*(ss1/4\*(se
772 be any prime factor of
788 so this is a contradiction.
789 We must conclude that
798 currently cannot generate proofs which use
800 though it will verify them.
803 .BI "check " label ", " b ", " p
804 Verify that the prime associated with the
812 .RI 2\*(ss b \-1\*(se
820 the label and value are printed to stdout during verification.
822 .\"--------------------------------------------------------------------------
826 Mark Wooding, <mdw@distorted.org.uk>
828 .\"----- That's all, folks --------------------------------------------------