chiark - git - mdw - 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.
 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 The
 168 .B pock
 169 program will generate prime numbers
 170 of sizes suitable for use in cryptography,
 171 along with a
 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.
 177 .PP
 178 Note that the primes selected by
 179 .B pock
 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.
 184 .
 185 .SS "Command line"
 186 The following options are recognized.
 187 .TP
 188 .B "\-h, \-\-help"
 189 Write help text to standard output and exit with status 0.
 190 .TP
 191 .B "\-q, \-\-quiet"
 192 Be less verbose during prime generation or certificate verification.
 193 .TP
 194 .B "\-v, \-\-verbose"
 195 Be more verbose during prime generation or certificate verification.
 196 .TP
 197 .BI "\-s, \-\-sievebits " b
 198 When generating certificates,
 199 require that the verifier can check numbers smaller than
 200 .RI 2\*(ss b \*(se
 201 without assistance.
 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.
 206 The default is 32,
 207 which seems to work well in practice.
 208 .
 209 .SS "gen"
 210 The
 211 .B gen
 212 command generates a prime
 213 .I p
 214 which is
 215 .I nbits
 216 long (i.e.,
 217 .RI 2\*(ss nbits \-1\*(se
 218 <
 219 .I p
 220 <
 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;
 225 the
 226 .B \-q
 227 option suppresses the runes;
 228 the
 229 .B \-v
 230 option produces more detailed runes.
 231 .
 232 .SS "ll"
 233 The
 234 .B ll
 235 command generates a Lim\(enLee prime
 236 .I p
 237 =
 238 2
 239 .IR q \*(us0\*(ue
 240 .IR q \*(us1\*(ue
 241 \*(..
 242 .IR q \*(us k \*(ue
 243 +
 244 1
 245 which is
 246 .I nbits
 247 long (i.e.,
 248 .RI 2\*(ss nbits \-1\*(se
 249 <
 250 .I p
 251 <
 252 .RI 2\*(ss nbits \*(se,
 253 such that each
 254 .IR q \*(us i \*(ue
 255 is an
 256 .IR nsubbits -bit
 257 prime, for
 258 0 \(<=
 259 .I i
 260 <
 261 .IR k ,
 262 and
 263 .IR q \*(us k \*(ue
 264 is an
 265 .IR nsubbits -bit
 266 prime,
 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;
 270 the
 271 .B \-q
 272 option suppresses the runes;
 273 the
 274 .B \-v
 275 option produces more detailed runes.
 276 .
 277 .SS "check"
 278 The
 279 .B check
 280 command reads a primality certificate from the named
 281 .I file
 282 or from standard input,
 283 and checks it.
 284 By default,
 285 each
 286 .B check
 287 line in the certificate causes a line
 288 .IP
 289 .B ;;
 290 .I label
 291 .B =
 292 .I n
 293 .BI [ b ]
 294 .PP
 295 to be printed to standard output,
 296 listing the prime's
 297 .IR label ,
 298 value
 299 .IR n ,
 300 and length
 301 .I b
 302 in bits;
 303 this behaviour is inhibited by the
 304 .B \-q
 305 option.
 306 .
 307 .SS Runes
 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.
 313 .TP
 314 .B !
 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.
 318 .TP
 319 .B .
 320 Candidate failed a Fermat test.
 321 .TP
 322 .B *
 323 Candidate passed a Fermat test.
 324 This is usually the last rune for a prime search.
 325 .TP
 326 .B @
 327 A candidate generator failed to generate the necessary subgroup.
 328 This is unusual.
 329 .TP
 330 .B <
 331 For Lim\(enLee primes,
 332 discarding the large prime
 333 because it produces results which are too small.
 334 .TP
 335 .B >
 336 For Lim\(enLee primes,
 337 discarding the large prime
 338 because it produces results which are too large.
 339 .TP
 340 .B [
 341 Starting a subsidiary prime search.
 342 .TP
 343 .B ]
 344 Finished a subsidiary prime search.
 345 .
 346 .\"--------------------------------------------------------------------------
 347 .SH CERTIFICATE FORMAT
 348 .
 349 A certificate consists of a number of lines.
 350 Blank lines,
 351 and lines beginning with a
 352 .RB ` ; ',
 353 are ignored.
 354 Other lines are as follows.
 355 .TP
 356 .BI "sievebits " b
 357 Declares that the verifier is expected to be able to check
 358 primes smaller than
 359 .RI 2\*(ss b \*(se
 360 for primality for itself.
 361 A
 362 .B sievebits
 363 line must appear before the first
 364 .B small
 365 line.
 366 .TP
 367 .BI "small " label " = " p
 368 Asserts that
 369 .I p
 370 is a small prime,
 371 and associates it with the
 372 .IR label .
 373 It is an error if the label has been assigned by a previous line.
 374 It is required that
 375 1 <
 376 .I p
 377 <
 378 .RI 2\*(ss b \*(se
 379 and that
 380 .I p
 381 is prime.
 382 Such small primes constitute the leaves of a proof tree.
 383 .TP
 384 .BI "pock " label " = " a ", " R ", [" i ", " j ", \fR\*(..\fB]"
 385 Asserts that a number
 386 .I n
 387 (defined below) is prime by Pocklington's criterion,
 388 and associates it with the
 389 .IR label .
 390 It is an error if the label has been assigned by a previous line.
 391 .RS
 392 .PP
 393 The strings
 394 .IR i ,
 395 .IR j ,
 396 \*(..
 397 must be labels assigned by earlier lines.
 398 For each such label
 399 .IR i ,
 400 let
 401 .IR q \*(us i \*(ue
 402 be the associated prime.
 403 Let
 404 .I Q
 405 =
 406 .IR q \*(us i \*(ue
 407 .IR q \*(us j \*(ue
 408 \*(..
 409 be the product of these primes.
 410 Let
 411 .I n
 412 =
 413 .RI 2 QR
 414 +
 415 1.
 416 It is required that:
 417 .hP 1.
 418 The
 419 .IR q \*(us i \*(ue
 420 are distinct.
 421 .hP 2.
 422 .IR Q \*(ss2\*(se
 423 \(>=
 424 .IR n .
 425 .hP 3.
 426 .IR a \*(ss n \-1\*(se
 427 \*(==
 428 1
 429 (mod
 430 .IR n ).
 431 .hP 4.
 432 .RI gcd( a \*(ss( n \-1)/ q \*(se
 433 \-
 434 1,
 435 .IR n )
 436 =
 437 1
 438 for each prime
 439 .IR q
 440 dividing
 441 .IR Q .
 442 .PP
 443 To see why this works, let
 444 .I p
 445 be the smallest prime factor of
 446 .IR n .
 447 From
 448 .B 3
 449 we see that
 450 the order of
 451 .I a
 452 in
 453 .RB ( Z /\fIp Z )\*(ss\(**\*(se
 454 divides
 455 .I p
 456 \-
 457 1.
 458 Consider some prime
 459 .I q
 460 dividing
 461 .I Q
 462 and let
 463 .I t
 464 =
 465 .IR a \*(ss( n \-1)/ q \*(se;
 466 then
 467 .I t
 468 has order dividing
 469 .IR q .
 470 From
 471 .BR 4 ,
 472 we have
 473 .IR t \*(ss q \*(se
 474 \*(/=
 475 1
 476 (mod
 477 .IR p ),
 478 and hence
 479 .I t
 480 has order precisely
 481 .I q
 482 in
 483 .RB ( Z /\fIp Z )\*(ss\(**\*(se.
 484 This implies that
 485 .I q
 486 divides
 487 .I p
 488 \-
 489 1.
 490 Since this holds for each prime
 491 .I q
 492 dividing
 493 .IR Q ,
 494 and,
 495 from
 496 .BR 1 ,
 497 the
 498 .I q
 499 are distinct,
 500 we deduce that
 501 .I Q
 502 divides
 503 .I p
 504 \-
 505 1
 506 and hence that
 507 .I p
 508 >
 509 .IR Q .
 510 Let
 511 .IR p \(fm
 512 be any prime factor of
 513 .IR n / p .
 514 Then
 515 .IR p \(fm
 516 \(>=
 517 .I p
 518 >
 519 .I Q
 520 so,
 521 from
 522 .BR 2 ,
 523 .IR pp \(fm
 524 >
 525 .IR Q \*(ss2\*(se
 526 \(>=
 527 .IR n ;
 528 but
 529 .IR pp \(fm
 530 divides
 531 .I n
 532 so this is a contradiction.
 533 We must conclude that
 534 .IR p \(fm
 535 does not exist,
 536 and
 537 .I n
 538 must be prime.
 539 .RE
 540 .TP
 541 .BI "ecpp " label " = " n ", " A ", " B ", " x ", " y ", [" i ", " j ", \fR\*(..\fB]"
 542 Asserts that the number
 543 .I n
 544 is prime by Goldwasser and Kilian's ECPP method,
 545 and associates it with the
 546 .IR label .
 547 It is an error if the label has been assigned by a previous line.
 548 .RS
 549 .PP
 550 The strings
 551 .IR i ,
 552 .IR j ,
 553 \*..
 554 must be labels assigned by earlier lines.
 555 For each such label
 556 .IR i ,
 557 let
 558 .IR q \*(us i \*(ue
 559 be the associated prime.
 560 Let
 561 .I Q
 562 =
 563 .IR q \*(us i \*(ue
 564 .IR q \*(us j \*(ue
 565 \*(..
 566 be the product of these primes.
 567 Define
 568 .I E\*(usn\*(ue
 569 = {
 570 .RI ( x ", " y )
 571 \*(mo
 572 .RB ( Z /\fIn Z )\*(ss2\*(se
 573 |
 574 .IR y \*(ss2\*(se
 575 =
 576 .IR x \*(ss3\*(se
 577 +
 578 .I Ax
 579 +
 580 .I B
 581 }
 582 \*(cu
 583 { \*(iy };
 584 if
 585 .I n
 586 is prime and the curve is not singular
 587 then this is the elliptic curve over
 588 .RI GF( n )
 589 with short-Weierstrass coefficients
 590 .I A
 591 and
 592 .IR B .
 593 Let
 594 .I R
 595 =
 596 .RI ( x ,
 597 .IR y ).
 598 It is required that:
 599 .hP 1.
 600 .I g
 601 =
 602 .RI gcd(4 a \*(ss3\*(se
 603 +
 604 .RI 27 b \*(ss2\*(se,
 605 .IR n )
 606 = 1.
 607 .hP 2.
 608 .I R
 609 \*(mo
 610 .IR E\*(usn\*(ue ;
 611 i.e.,
 612 .IR y \*(ss2\*(se
 613 \*(==
 614 .IR x \*(ss3\*(se
 615 +
 616 .I Ax
 617 +
 618 .I B
 619 (mod
 620 .IR n ).
 621 .hP 3. The
 622 .I q\*(usi\*(ue
 623 are distinct.
 624 .hP 4.
 625 .IR QR ,
 626 the elliptic-curve scalar product of the point
 627 .I R
 628 by the integer
 629 .IR Q ,
 630 calculated as if
 631 .I E
 632 is a true elliptic curve,
 633 is the point at infinity.
 634 .hP 5.
 635 .RI ( Q / q ) R
 636 is finite for each prime
 637 .I q
 638 dividing
 639 .IR Q .
 640 .hP 6.
 641 .I Q
 642 >
 643 .RI ( n \*(ss1/4\*(se
 644 + 1)\*(ss2\*(se.
 645 .PP
 646 To see why this test works, let
 647 .I p
 648 be the smallest prime factor of
 649 .IR n ,
 650 and let
 651 .I E\*(usp\*(ue
 652 = {
 653 .RI ( x ", " y )
 654 \*(mo
 655 .RI GF( p )\*(ss2\*(se
 656 |
 657 .IR y \*(ss2\*(se
 658 =
 659 .IR x \*(ss3\*(se
 660 +
 661 .I Ax
 662 +
 663 .I B
 664 }
 665 \*(cu
 666 { \*(iy }.
 667 From
 668 .BR 1 ,
 669 .I g
 670 = 1,
 671 .I E\*(usp\*(ue
 672 is an elliptic curve.
 673 (If 1 <
 674 .I g
 675 <
 676 .I n
 677 then
 678 .I g
 679 is a proper factor of
 680 .I n
 681 and
 682 .I n
 683 is certainly not prime;
 684 if
 685 .I g
 686 =
 687 .I n
 688 then the curve will be singular and the test fails.)
 689 From
 690 .BR 2 ,
 691 .I R
 692 is a point on
 693 .IR E\*(usp\*(ue .
 694 From
 695 .BR 4 ,
 696 .I R
 697 has
 698 .IR Q -torsion
 699 in
 700 .IR E\*(usp\*(ue .
 701 Consider some prime
 702 .I q
 703 dividing
 704 .I Q
 705 and let
 706 .I T
 707 =
 708 .RI ( Q/q ) R ;
 709 then
 710 .I T
 711 has torsion dividing
 712 .IR q .
 713 From
 714 .BR 5 ,
 715 .RI ( Q/q ) R
 716 \(!= 0,
 717 and hence
 718 .I T
 719 has order precisely
 720 .I q
 721 in
 722 .IR E\*(usp\*(ue .
 723 This implies that
 724 .I q
 725 divides
 726 .RI # E\*(usp\*(ue .
 727 Since this holds for each prime
 728 .I q
 729 dividing
 730 .IR Q ,
 731 and, from
 732 .BR 3 ,
 733 the
 734 .I q
 735 are distinct,
 736 we deduce that
 737 .I Q
 738 divides
 739 .RI # E\*(usp\*(ue
 740 and hence that
 741 .RI # E\*(usp\*(ue
 742 \(>=
 743 .IR Q .
 744 Hasse's theorem tells us that
 745 .RI | p
 746 + 1 \-
 747 .RI # E\*(usp\*(ue |
 748 \(<=
 749 .RI 2\*(sr p ,
 750 whence
 751 .I p
 752 + 1 +
 753 .RI 2\*(sr p
 754 =
 755 .RI (\*(sr p
 756 + 1)\*(ss2\*(se
 757 \(>=
 758 .RI # E\*(usp\*(ue
 759 \(>=
 760 .IR Q
 761 >
 762 .RI ( n \*(ss1/4\*(se
 763 + 1)\*(ss2\*(se
 764 (from
 765 .BR 6 );
 766 so
 767 .IR p\*(ss2\*(se
 768 >
 769 .IR n .
 770 Let
 771 .IR p \(fm
 772 be any prime factor of
 773 .IR n / p .
 774 Then
 775 .IR p \(fm
 776 \(>=
 777 .I p
 778 and
 779 .IR pp \(fm
 780 \(>=
 781 .IR p \*(ss2\*(se
 782 >
 783 .IR n ;
 784 but
 785 .IR pp \(fm
 786 divides
 787 .I n
 788 so this is a contradiction.
 789 We must conclude that
 790 .IR p \(fm
 791 does not exist,
 792 and
 793 .I n
 794 must be prime.
 795 .PP
 796 Note that
 797 .B pock
 798 currently cannot generate proofs which use
 799 .BR ecpp ,
 800 though it will verify them.
 801 .RE
 802 .TP
 803 .BI "check " label ", " b ", " p
 804 Verify that the prime associated with the
 805 .I label
 806 is equal to
 807 .I p
 808 and that it is
 809 .I b
 810 bits long;
 811 i.e., that
 812 .RI 2\*(ss b \-1\*(se
 813 \(<=
 814 .I p
 815 <
 816 .RI 2\*(ss b \*(se.
 817 Unless
 818 inhibited by
 819 .BR \-q ,
 820 the label and value are printed to stdout during verification.
 821 .
 822 .\"--------------------------------------------------------------------------
 823 .SH "SEE ALSO"
 824 .BR key (1).
 825 .SH AUTHOR
 826 Mark Wooding, <mdw@distorted.org.uk>
 827 .
 828 .\"----- That's all, folks --------------------------------------------------