mdw@git.distorted.org.uk Git - catacomb-python/blob - pock.1

   1 .\" -*-nroff-*-
   2 .\"
   3 .\" Describe the primality certificate generator and checker
   4 .\"
   5 .\" (c) 2016 Straylight/Edgeware
   6 .\"
   7 .
   8 .\"----- Licensing notice ---------------------------------------------------
   9 .\"
  10 .\" This file is part of the Python interface to Catacomb.
  11 .\"
  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.
  16 .\"
  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.
  21 .\"
  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.
  25 .
  26 .ie t \{\
  27 .  if \n(.g \{\
  28 .    fam P
  29 .  \}
  30 .  ds o \(bu
  31 .  ds ss \s7\v'-4p'
  32 .  ds se \v'4p'\s0
  33 .  ds us \s7\v'2p'
  34 .  ds ue \v'-2p'\s0
  35 .  ds *e \(*e
  36 .  ds mo \(mo
  37 .  ds sr \(sr
  38 .  ds cu \(cu
  39 .  ds ca \(ca
  40 .  ds iy \(if
  41 .  ds == \(==
  42 .  ds .. \&.\h'2p'.\h'2p'.\&
  43 .  ds /= \h'(\w'\*(=='-\w'/')/2'/\h'-(\w'\*(=='+\w'/')/2'\*(==
  44 .\}
  45 .el \{\
  46 .  ds o o
  47 .  ds ss ^
  48 .  ds se
  49 .  ds us _
  50 .  ds ue
  51 .  ds *e \fIepsilon\fP
  52 .  ds mo in
  53 .  ds sr sqrt
  54 .  ds cu union
  55 .  ds ca isect
  56 .  ds iy infty
  57 .  ds == ==
  58 .  ds .. \&...\&
  59 .  ds /= /==
  60 .\}
  61 .de hP
  62 .IP
  63 \h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
  64 ..
  65 .
  66 .TH pock 1 "28 May 2017" "Straylight/Edgeware" "Catacomb cryptographic library"
  67 .SH NAME
  68 pock \- generate and verify primality certificates
  69 .
  70 .\"--------------------------------------------------------------------------
  71 .SH SYNOPSIS
  72 .
  73 .B pock
  74 .RB [ \-qv ]
  75 .I command
  76 .IR [ arguments ...]
  77 .PP
  78 Subcommands:
  79 .RS
  80 .br
  81 .B gen
  82 .I nbits
  83 .br
  84 .B ll
  85 .I nbits
  86 .I nsubbits
  87 .br
  88 .B check
  89 .RI [ file ]
  90 .RE
  91 .
  92 .\"--------------------------------------------------------------------------
  93 .SH DESCRIPTION
  94 .
  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.
  98 Given a candidate
  99 .I n
 100 and a
 101 .I witness
 102 2 \(<=
 103 .I a
 104 <
 105 .IR n ,
 106 the test answers either `composite' or `unknown'.
 107 If
 108 .I n
 109 is prime then the test answers `unknown' for every witness
 110 .IR a ;
 111 if
 112 .I n
 113 is in fact composite
 114 then the test answers `composite'
 115 for at least three quarters of the possible witnesses.
 116 If
 117 .I n
 118 is a composite,
 119 then the witnesses
 120 .I a
 121 for which the test reports `unknown'
 122 are called
 123 .IR liars .
 124 .PP
 125 Naively, then,
 126 to reduce the probability of falsely accepting a composite
 127 below some bound \*(*e,
 128 one must perform
 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.
 136 .PP
 137 The above is a worst-case bound:
 138 very few composite numbers
 139 .I n
 140 have anywhere near
 141 .IR n /4
 142 liars.
 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
 151 .I decreases
 152 with the size of the candidate being tested.
 153 .PP
 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,
 158 and the worst-case
 159 .IR n /4
 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.)
 166 .PP
 167 There
 168 .I are
 169 stronger probabilistic tests.
 170 A combination of Rabin\(enMiller and
 171 Grantham's Frobenius test
 172 is known as the
 173 Baillie\(enPSW test
 174 (after Baillie, Pomerance, Selfridge, and Wagstaff);
 175 there are
 176 .I no
 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
 184 .I does
 185 constitute a security assumption.
 186 .PP
 187 By contrast,the
 188 .B pock
 189 program will generate prime numbers
 190 of sizes suitable for use in cryptography,
 191 along with a
 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.
 197 .PP
 198 Note that the primes selected by
 199 .B pock
 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.
 204 .
 205 .SS "Command line"
 206 The following options are recognized.
 207 .TP
 208 .B "\-h, \-\-help"
 209 Write help text to standard output and exit with status 0.
 210 .TP
 211 .B "\-q, \-\-quiet"
 212 Be less verbose during prime generation or certificate verification.
 213 .TP
 214 .B "\-v, \-\-verbose"
 215 Be more verbose during prime generation or certificate verification.
 216 .TP
 217 .BI "\-s, \-\-sievebits " b
 218 When generating certificates,
 219 require that the verifier can check numbers smaller than
 220 .RI 2\*(ss b \*(se
 221 without assistance.
 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.
 226 The default is 32,
 227 which seems to work well in practice.
 228 .
 229 .SS "gen"
 230 The
 231 .B gen
 232 command generates a prime
 233 .I p
 234 which is
 235 .I nbits
 236 long (i.e.,
 237 .RI 2\*(ss nbits \-1\*(se
 238 <
 239 .I p
 240 <
 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;
 245 the
 246 .B \-q
 247 option suppresses the runes;
 248 the
 249 .B \-v
 250 option produces more detailed runes.
 251 .
 252 .SS "ll"
 253 The
 254 .B ll
 255 command generates a Lim\(enLee prime
 256 .I p
 257 =
 258 2
 259 .IR q \*(us0\*(ue
 260 .IR q \*(us1\*(ue
 261 \*(..
 262 .IR q \*(us k \*(ue
 263 +
 264 1
 265 which is
 266 .I nbits
 267 long (i.e.,
 268 .RI 2\*(ss nbits \-1\*(se
 269 <
 270 .I p
 271 <
 272 .RI 2\*(ss nbits \*(se,
 273 such that each
 274 .IR q \*(us i \*(ue
 275 is an
 276 .IR nsubbits -bit
 277 prime, for
 278 0 \(<=
 279 .I i
 280 <
 281 .IR k ,
 282 and
 283 .IR q \*(us k \*(ue
 284 is an
 285 .IR nsubbits -bit
 286 prime,
 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;
 290 the
 291 .B \-q
 292 option suppresses the runes;
 293 the
 294 .B \-v
 295 option produces more detailed runes.
 296 .
 297 .SS "check"
 298 The
 299 .B check
 300 command reads a primality certificate from the named
 301 .I file
 302 or from standard input,
 303 and checks it.
 304 By default,
 305 each
 306 .B check
 307 line in the certificate causes a line
 308 .IP
 309 .B ;;
 310 .I label
 311 .B =
 312 .I n
 313 .BI [ b ]
 314 .PP
 315 to be printed to standard output,
 316 listing the prime's
 317 .IR label ,
 318 value
 319 .IR n ,
 320 and length
 321 .I b
 322 in bits;
 323 this behaviour is inhibited by the
 324 .B \-q
 325 option.
 326 .
 327 .SS Runes
 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.
 333 .TP
 334 .B !
 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.
 338 .TP
 339 .B .
 340 Candidate failed a Fermat test.
 341 .TP
 342 .B *
 343 Candidate passed a Fermat test.
 344 This is usually the last rune for a prime search.
 345 .TP
 346 .B @
 347 A candidate generator failed to generate the necessary subgroup.
 348 This is unusual.
 349 .TP
 350 .B <
 351 For Lim\(enLee primes,
 352 discarding the large prime
 353 because it produces results which are too small.
 354 .TP
 355 .B >
 356 For Lim\(enLee primes,
 357 discarding the large prime
 358 because it produces results which are too large.
 359 .TP
 360 .B [
 361 Starting a subsidiary prime search.
 362 .TP
 363 .B ]
 364 Finished a subsidiary prime search.
 365 .
 366 .\"--------------------------------------------------------------------------
 367 .SH CERTIFICATE FORMAT
 368 .
 369 A certificate consists of a number of lines.
 370 Blank lines,
 371 and lines beginning with a
 372 .RB ` ; ',
 373 are ignored.
 374 Other lines are as follows.
 375 .TP
 376 .BI "sievebits " b
 377 Declares that the verifier is expected to be able to check
 378 primes smaller than
 379 .RI 2\*(ss b \*(se
 380 for primality for itself.
 381 A
 382 .B sievebits
 383 line must appear before the first
 384 .B small
 385 line.
 386 .TP
 387 .BI "small " label " = " p
 388 Asserts that
 389 .I p
 390 is a small prime,
 391 and associates it with the
 392 .IR label .
 393 It is an error if the label has been assigned by a previous line.
 394 It is required that
 395 1 <
 396 .I p
 397 <
 398 .RI 2\*(ss b \*(se
 399 and that
 400 .I p
 401 is prime.
 402 Such small primes constitute the leaves of a proof tree.
 403 .TP
 404 .BI "pock " label " = " a ", " R ", [" i ", " j ", \fR\*(..\fB]"
 405 Asserts that a number
 406 .I n
 407 (defined below) is prime by Pocklington's criterion,
 408 and associates it with the
 409 .IR label .
 410 It is an error if the label has been assigned by a previous line.
 411 .RS
 412 .PP
 413 The strings
 414 .IR i ,
 415 .IR j ,
 416 \*(..
 417 must be labels assigned by earlier lines.
 418 For each such label
 419 .IR i ,
 420 let
 421 .IR q \*(us i \*(ue
 422 be the associated prime.
 423 Let
 424 .I Q
 425 =
 426 .IR q \*(us i \*(ue
 427 .IR q \*(us j \*(ue
 428 \*(..
 429 be the product of these primes.
 430 Let
 431 .I n
 432 =
 433 .RI 2 QR
 434 +
 435 1.
 436 It is required that:
 437 .hP 1.
 438 The
 439 .IR q \*(us i \*(ue
 440 are distinct.
 441 .hP 2.
 442 .IR Q \*(ss2\*(se
 443 \(>=
 444 .IR n .
 445 .hP 3.
 446 .IR a \*(ss n \-1\*(se
 447 \*(==
 448 1
 449 (mod
 450 .IR n ).
 451 .hP 4.
 452 .RI gcd( a \*(ss( n \-1)/ q \*(se
 453 \-
 454 1,
 455 .IR n )
 456 =
 457 1
 458 for each prime
 459 .IR q
 460 dividing
 461 .IR Q .
 462 .PP
 463 To see why this works, let
 464 .I p
 465 be the smallest prime factor of
 466 .IR n .
 467 From
 468 .B 3
 469 we see that
 470 the order of
 471 .I a
 472 in
 473 .RB ( Z /\fIp Z )\*(ss\(**\*(se
 474 divides
 475 .I n
 476 \-
 477 1.
 478 Consider some prime
 479 .I q
 480 dividing
 481 .I Q
 482 and let
 483 .I t
 484 =
 485 .IR a \*(ss( n \-1)/ q \*(se;
 486 then
 487 .I t
 488 has order dividing
 489 .IR q .
 490 From
 491 .BR 4 ,
 492 we have
 493 .I t
 494 \*(/=
 495 1
 496 (mod
 497 .IR p ),
 498 and hence
 499 .I t
 500 has order precisely
 501 .I q
 502 in
 503 .RB ( Z /\fIp Z )\*(ss\(**\*(se.
 504 This implies that
 505 .I q
 506 divides
 507 .I p
 508 \-
 509 1.
 510 Since this holds for each prime
 511 .I q
 512 dividing
 513 .IR Q ,
 514 and,
 515 from
 516 .BR 1 ,
 517 the
 518 .I q
 519 are distinct,
 520 we deduce that
 521 .I Q
 522 divides
 523 .I p
 524 \-
 525 1
 526 and hence that
 527 .I p
 528 >
 529 .IR Q .
 530 Let
 531 .IR p \(fm
 532 be any prime factor of
 533 .IR n / p .
 534 Then
 535 .IR p \(fm
 536 \(>=
 537 .I p
 538 >
 539 .I Q
 540 so,
 541 from
 542 .BR 2 ,
 543 .IR pp \(fm
 544 >
 545 .IR Q \*(ss2\*(se
 546 \(>=
 547 .IR n ;
 548 but
 549 .IR pp \(fm
 550 divides
 551 .I n
 552 so this is a contradiction.
 553 We must conclude that
 554 .IR p \(fm
 555 does not exist,
 556 and
 557 .I n
 558 must be prime.
 559 .RE
 560 .TP
 561 .BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]"
 562 Asserts that the number
 563 .I n
 564 is prime by Goldwasser and Kilian's ECPP method,
 565 and associates it with the
 566 .IR label .
 567 It is an error if the label has been assigned by a previous line.
 568 .RS
 569 .PP
 570 The strings
 571 .IR i ,
 572 .IR j ,
 573 \*..
 574 must be labels assigned by earlier lines.
 575 For each such label
 576 .IR i ,
 577 let
 578 .IR q \*(us i \*(ue
 579 be the associated prime.
 580 Let
 581 .I Q
 582 =
 583 .IR q \*(us i \*(ue
 584 .IR q \*(us j \*(ue
 585 \*(..
 586 be the product of these primes.
 587 Define
 588 .I E\*(usn\*(ue
 589 = {
 590 .RI ( x ", " y )
 591 \*(mo
 592 .RB ( Z /\fIn Z )\*(ss2\*(se
 593 |
 594 .IR y \*(ss2\*(se
 595 =
 596 .IR x \*(ss3\*(se
 597 +
 598 .I Ax
 599 +
 600 .I B
 601 }
 602 \*(cu
 603 { \*(iy };
 604 if
 605 .I n
 606 is prime and the curve is not singular
 607 then this is the elliptic curve over
 608 .RI GF( n )
 609 with short-Weierstrass coefficients
 610 .I A
 611 and
 612 .IR B .
 613 Let
 614 .I R
 615 =
 616 .RI ( x ,
 617 .IR y ).
 618 It is required that:
 619 .hP 1.
 620 .I g
 621 =
 622 .RI gcd(4 a \*(ss3\*(se
 623 +
 624 .RI 27 b \*(ss2\*(se,
 625 .IR n )
 626 = 1.
 627 .hP 2.
 628 .I R
 629 \*(mo
 630 .IR E\*(usn\*(ue ;
 631 i.e.,
 632 .IR y \*(ss2\*(se
 633 \*(==
 634 .IR x \*(ss3\*(se
 635 +
 636 .I Ax
 637 +
 638 .I B
 639 (mod
 640 .IR n ).
 641 .hP 3. The
 642 .I q\*(usi\*(ue
 643 are distinct.
 644 .hP 4.
 645 .IR QR ,
 646 the elliptic-curve scalar product of the point
 647 .I R
 648 by the integer
 649 .IR Q ,
 650 calculated as if
 651 .I E
 652 is a true elliptic curve,
 653 is the point at infinity.
 654 .hP 5.
 655 .RI ( Q / q ) R
 656 is finite for each prime
 657 .I q
 658 dividing
 659 .IR Q .
 660 .hP 6.
 661 .I Q
 662 >
 663 .RI ( n \*(ss1/4\*(se
 664 + 1)\*(ss2\*(se.
 665 .PP
 666 To see why this test works, let
 667 .I p
 668 be the smallest prime factor of
 669 .IR n ,
 670 and let
 671 .I E\*(usp\*(ue
 672 = {
 673 .RI ( x ", " y )
 674 \*(mo
 675 .RI GF( p )\*(ss2\*(se
 676 |
 677 .IR y \*(ss2\*(se
 678 =
 679 .IR x \*(ss3\*(se
 680 +
 681 .I Ax
 682 +
 683 .I B
 684 }
 685 \*(cu
 686 { \*(iy }.
 687 From
 688 .BR 1 ,
 689 .I g
 690 = 1,
 691 .I E\*(usp\*(ue
 692 is an elliptic curve.
 693 (If 1 <
 694 .I g
 695 <
 696 .I n
 697 then
 698 .I g
 699 is a proper factor of
 700 .I n
 701 and
 702 .I n
 703 is certainly not prime;
 704 if
 705 .I g
 706 =
 707 .I n
 708 then the curve will be singular and the test fails.)
 709 From
 710 .BR 2 ,
 711 .I R
 712 is a point on
 713 .IR E\*(usp\*(ue .
 714 From
 715 .BR 4 ,
 716 .I R
 717 has
 718 .IR Q -torsion
 719 in
 720 .IR E\*(usp\*(ue .
 721 Consider some prime
 722 .I q
 723 dividing
 724 .I Q
 725 and let
 726 .I T
 727 =
 728 .RI ( Q/q ) R ;
 729 then
 730 .I T
 731 has torsion dividing
 732 .IR q .
 733 From
 734 .BR 5 ,
 735 .RI ( Q/q ) R
 736 \(!= 0,
 737 and hence
 738 .I T
 739 has order precisely
 740 .I q
 741 in
 742 .IR E\*(usp\*(ue .
 743 This implies that
 744 .I q
 745 divides
 746 .RI # E\*(usp\*(ue .
 747 Since this holds for each prime
 748 .I q
 749 dividing
 750 .IR Q ,
 751 and, from
 752 .BR 3 ,
 753 the
 754 .I q
 755 are distinct,
 756 we deduce that
 757 .I Q
 758 divides
 759 .RI # E\*(usp\*(ue
 760 and hence that
 761 .RI # E\*(usp\*(ue
 762 \(>=
 763 .IR Q .
 764 Hasse's theorem tells us that
 765 .RI | p
 766 + 1 \-
 767 .RI # E\*(usp\*(ue |
 768 \(<=
 769 .RI 2\*(sr p ,
 770 whence
 771 .I p
 772 + 1 +
 773 .RI 2\*(sr p
 774 =
 775 .RI (\*(sr p
 776 + 1)\*(ss2\*(se
 777 \(>=
 778 .RI # E\*(usp\*(ue
 779 \(>=
 780 .IR Q
 781 >
 782 .RI ( n \*(ss1/4\*(se
 783 + 1)\*(ss2\*(se
 784 (from
 785 .BR 6 );
 786 so
 787 .IR p\*(ss2\*(se
 788 >
 789 .IR n .
 790 Let
 791 .IR p \(fm
 792 be any prime factor of
 793 .IR n / p .
 794 Then
 795 .IR p \(fm
 796 \(>=
 797 .I p
 798 and
 799 .IR pp \(fm
 800 \(>=
 801 .IR p \*(ss2\*(se
 802 >
 803 .IR n ;
 804 but
 805 .IR pp \(fm
 806 divides
 807 .I n
 808 so this is a contradiction.
 809 We must conclude that
 810 .IR p \(fm
 811 does not exist,
 812 and
 813 .I n
 814 must be prime.
 815 .PP
 816 Note that
 817 .B pock
 818 currently cannot generate proofs which use
 819 .BR ecpp ,
 820 though it will verify them.
 821 .RE
 822 .TP
 823 .BI "check " label ", " b ", " p
 824 Verify that the prime associated with the
 825 .I label
 826 is equal to
 827 .I p
 828 and that it is
 829 .I b
 830 bits long;
 831 i.e., that
 832 .RI 2\*(ss b \-1\*(se
 833 \(<=
 834 .I p
 835 <
 836 .RI 2\*(ss b \*(se.
 837 Unless
 838 inhibited by
 839 .BR \-q ,
 840 the label and value are printed to stdout during verification.
 841 .
 842 .\"--------------------------------------------------------------------------
 843 .SH "SEE ALSO"
 844 .BR key (1).
 845 .SH AUTHOR
 846 Mark Wooding, <mdw@distorted.org.uk>
 847 .
 848 .\"----- That's all, folks --------------------------------------------------