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 these primes are distinct,
 518 we deduce that
 519 .I Q
 520 divides
 521 .I p
 522 \-
 523 1
 524 and hence that
 525 .I p
 526 >
 527 .IR Q .
 528 Let
 529 .IR p \(fm
 530 be any prime factor of
 531 .IR n / p .
 532 Then
 533 .IR p \(fm
 534 \(>=
 535 .I p
 536 >
 537 .I Q
 538 so,
 539 from
 540 .BR 2 ,
 541 .IR pp \(fm
 542 >
 543 .IR Q \*(ss2\*(se
 544 \(>=
 545 .IR n ;
 546 but
 547 .IR pp \(fm
 548 divides
 549 .I n
 550 so this is a contradiction.
 551 We must conclude that
 552 .IR p \(fm
 553 does not exist,
 554 and
 555 .I n
 556 must be prime.
 557 .RE
 558 .TP
 559 .BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]"
 560 Asserts that the number
 561 .I n
 562 is prime by Goldwasser and Kilian's ECPP method,
 563 and associates it with the
 564 .IR label .
 565 It is an error if the label has been assigned by a previous line.
 566 .RS
 567 .PP
 568 The strings
 569 .IR i ,
 570 .IR j ,
 571 \*..
 572 must be labels assigned by earlier lines.
 573 For each such label
 574 .IR i ,
 575 let
 576 .IR q \*(us i \*(ue
 577 be the associated prime.
 578 Let
 579 .I Q
 580 =
 581 .IR q \*(us i \*(ue
 582 .IR q \*(us j \*(ue
 583 \*(..
 584 be the product of these primes.
 585 Define
 586 .I E\*(usn\*(ue
 587 = {
 588 .RI ( x ", " y )
 589 \*(mo
 590 .RB ( Z /\fIn Z )\*(ss2\*(se
 591 |
 592 .IR y \*(ss2\*(se
 593 =
 594 .IR x \*(ss3\*(se
 595 +
 596 .I Ax
 597 +
 598 .I B
 599 }
 600 \*(cu
 601 { \*(iy };
 602 if
 603 .I n
 604 is prime and the curve is not singular
 605 then this is the elliptic curve over
 606 .RI GF( n )
 607 with short-Weierstrass coefficients
 608 .I A
 609 and
 610 .IR B .
 611 Let
 612 .I R
 613 =
 614 .RI ( x ,
 615 .IR y ).
 616 It is required that:
 617 .hP 1.
 618 .I g
 619 =
 620 .RI gcd(4 a \*(ss3\*(se
 621 +
 622 .RI 27 b \*(ss2\*(se,
 623 .IR n )
 624 = 1.
 625 .hP 2.
 626 .I R
 627 \*(mo
 628 .IR E\*(usn\*(ue ;
 629 i.e.,
 630 .IR y \*(ss2\*(se
 631 \*(==
 632 .IR x \*(ss3\*(se
 633 +
 634 .I Ax
 635 +
 636 .I B
 637 (mod
 638 .IR n ).
 639 .hP 3. The
 640 .I q\*(usi\*(ue
 641 are distinct.
 642 .hP 4.
 643 .IR QR ,
 644 the elliptic-curve scalar product of the point
 645 .I R
 646 by the integer
 647 .IR Q ,
 648 calculated as if
 649 .I E
 650 is a true elliptic curve,
 651 is the point at infinity.
 652 .hP 5.
 653 .RI ( Q / q ) R
 654 is finite for each prime
 655 .I q
 656 dividing
 657 .IR Q .
 658 .hP 6.
 659 .I Q
 660 >
 661 .RI ( n \*(ss1/4\*(se
 662 + 1)\*(ss2\*(se.
 663 .PP
 664 To see why this test works, let
 665 .I p
 666 be the smallest prime factor of
 667 .IR n ,
 668 and let
 669 .I E\*(usp\*(ue
 670 = {
 671 .RI ( x ", " y )
 672 \*(mo
 673 .RI GF( p )\*(ss2\*(se
 674 |
 675 .IR y \*(ss2\*(se
 676 =
 677 .IR x \*(ss3\*(se
 678 +
 679 .I Ax
 680 +
 681 .I B
 682 }
 683 \*(cu
 684 { \*(iy }.
 685 From
 686 .BR 1 ,
 687 .I g
 688 = 1,
 689 .I E\*(usp\*(ue
 690 is an elliptic curve.
 691 (If 1 <
 692 .I g
 693 <
 694 .I n
 695 then
 696 .I g
 697 is a proper factor of
 698 .I n
 699 and
 700 .I n
 701 is certainly not prime;
 702 if
 703 .I g
 704 =
 705 .I n
 706 then the curve will be singular and the test fails.)
 707 From
 708 .BR 2 ,
 709 .I R
 710 is a point on
 711 .IR E\*(usp\*(ue .
 712 From
 713 .BR 4 ,
 714 .I R
 715 has
 716 .IR Q -torsion
 717 in
 718 .IR E\*(usp\*(ue .
 719 Consider some prime
 720 .I q
 721 dividing
 722 .I Q
 723 and let
 724 .I T
 725 =
 726 .RI ( Q/q ) R ;
 727 then
 728 .I T
 729 has torsion dividing
 730 .IR q .
 731 From
 732 .BR 5 ,
 733 .RI ( Q/q ) R
 734 \(!= 0,
 735 and hence
 736 .I T
 737 has order precisely
 738 .I q
 739 in
 740 .IR E\*(usp\*(ue .
 741 This implies that
 742 .I q
 743 divides
 744 .RI # E\*(usp\*(ue .
 745 Since this holds for each prime
 746 .I q
 747 dividing
 748 .IR Q ,
 749 and, from
 750 .BR 3 ,
 751 the
 752 .I q
 753 are distinct,
 754 we deduce that
 755 .I Q
 756 divides
 757 .RI # E\*(usp\*(ue
 758 and hence that
 759 .RI # E\*(usp\*(ue
 760 \(>=
 761 .IR Q .
 762 Hasse's theorem tells us that
 763 .RI | p
 764 + 1 \-
 765 .RI # E\*(usp\*(ue |
 766 \(<=
 767 .RI 2\*(sr p ,
 768 so, in particular,
 769 .RI # E\*(usp\*(ue
 770 \-
 771 .I p
 772 \- 1
 773 \(<=
 774 .RI 2\*(sr p ,
 775 whence
 776 .I p
 777 + 1 +
 778 .RI 2\*(sr p
 779 =
 780 .RI (\*(sr p
 781 + 1)\*(ss2\*(se
 782 \(>=
 783 .RI # E\*(usp\*(ue
 784 \(>=
 785 .IR Q
 786 >
 787 .RI ( n \*(ss1/4\*(se
 788 + 1)\*(ss2\*(se
 789 (from
 790 .BR 6 );
 791 so
 792 .IR p\*(ss2\*(se
 793 >
 794 .IR n .
 795 Let
 796 .IR p \(fm
 797 be any prime factor of
 798 .IR n / p .
 799 Then
 800 .IR p \(fm
 801 \(>=
 802 .I p
 803 and
 804 .IR pp \(fm
 805 \(>=
 806 .IR p \*(ss2\*(se
 807 >
 808 .IR n ;
 809 but
 810 .IR pp \(fm
 811 divides
 812 .I n
 813 so this is a contradiction.
 814 We must conclude that
 815 .IR p \(fm
 816 does not exist,
 817 and
 818 .I n
 819 must be prime.
 820 .PP
 821 Note that
 822 .B pock
 823 currently cannot generate proofs which use
 824 .BR ecpp ,
 825 though it will verify them.
 826 .RE
 827 .TP
 828 .BI "check " label ", " b ", " p
 829 Verify that the prime associated with the
 830 .I label
 831 is equal to
 832 .I p
 833 and that it is
 834 .I b
 835 bits long;
 836 i.e., that
 837 .RI 2\*(ss b \-1\*(se
 838 \(<=
 839 .I p
 840 <
 841 .RI 2\*(ss b \*(se.
 842 Unless
 843 inhibited by
 844 .BR \-q ,
 845 the label and value are printed to stdout during verification.
 846 .
 847 .\"--------------------------------------------------------------------------
 848 .SH "SEE ALSO"
 849 .BR key (1).
 850 .SH AUTHOR
 851 Mark Wooding, <mdw@distorted.org.uk>
 852 .
 853 .\"----- That's all, folks --------------------------------------------------