| 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 -------------------------------------------------- |