idnits 2.17.1 draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- -- The document has an IETF Trust Provisions (28 Dec 2009) Section 6.c(i) Publication Limitation clause. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (2019-04-04) is 1848 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Unused Reference: 'B2' is defined on line 752, but no explicit reference was found in the text Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet-Draft D. Brown 2 Intended status: Experimental BlackBerry 3 Expires: 2019-10-06 2019-04-04 5 Elliptic curve 2y^2=x^3+x over field size 8^91+5 6 8 Abstract 10 This document recommends using a special elliptic curve alongside 11 dissimilar curves, such as NIST P-256, Curve25519, sect283k1, 12 Brainpool, and random curves, as a cryptographic defense against an 13 unlikely, undisclosed attack against mainstream curves. Features of 14 this curve 2y^2=x^3+x/GF(8^91+5) are: isomorphism to Miller curves 15 from 1985; Montgomery form mappable to Edwards; simple field 16 powering for inversion, Legendre symbol, and square roots; efficient 17 endomorphism to speed up Diffie--Hellman with Bernstein's 2-D 18 ladder; 34-byte keys; similarity to Bitcoin curve; hashing-to-point; 19 low Kolmogorov complexity (low risk of backdoor). 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. Internet-Drafts are working 25 documents of the Internet Engineering Task Force (IETF). Note that 26 other groups may also distribute working documents as 27 Internet-Drafts. The list of current Internet-Drafts is at 28 http://datatracker.ietf.org/drafts/current. 30 Internet-Drafts are draft documents valid for a maximum of six 31 months and may be updated, replaced, or obsoleted by other documents 32 at any time. It is inappropriate to use Internet-Drafts as 33 reference material or to cite them other than as "work in progress." 35 Copyright Notice 37 Copyright (c) 2019 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with 45 respect to this document. 47 Internet-Draft 2019-04-04 49 This document may not be modified, and derivative works of it may 50 not be created, except to format it for publication as an RFC or to 51 translate it into languages other than English. 53 Internet-Draft 2019-04-04 55 Table of Contents 57 1. Introduction 58 1.1. Background 59 1.1.1. Notation 60 1.2. Motivation 61 2. Requirements Language (RFC 2119) 62 3. Encoding a point into 34 bytes 63 3.1. Encoding a point into bytes 64 3.2. Decoding bytes into a point 65 4. Point validation 66 4.1. When a public key MAY, SHOULD or MUST be validated 67 4.1.1. Precautionary mandatory validation 68 4.1.2. Simplified validation 69 4.1.3. Relatively safe cases of non-validation 70 4.1.4. Minimal validation 71 4.2. How to validate a point (given only x) 72 5. OPTIONAL encodings 73 5.1. Encoding scalar multipliers as 34 bytes 74 5.2. Encoding 34 bytes into a point (sketch) 75 6. IANA Considerations 76 7. Security considerations 77 7.1. Field choice 78 7.2. Curve choice 79 7.3. Encoding choices 80 7.4. General subversion concerns 81 7.5. Concerns about 'aegis' 82 8. References 83 8.1. Normative References 84 8.2. Informative References 85 Appendix A. Test vectors 86 Appendix B. Motivation: minimizing the room for backdoors 87 Appendix C. Pseudocode 88 C.1. Byte encoding 89 C.2. Byte decoding 90 C.3. Fermat inversion 91 C.4. Branchless Legendre symbol computation 92 C.5. Field multiplication and squaring 93 C.6. Field element partial reduction 94 C.7. Field element final reduction 95 C.8. Scalar point multiplication 96 C.9. Diffie--Hellman pseudocode 97 C.10. Elligator i 98 D. Primality proofs and certificates 99 D.1. Pratt certificate for the field size 8^91+5 100 D.2. Pratt certificate for subgroup order 102 Internet-Draft 2019-04-04 104 1. Introduction 106 This document relates to elliptic curve cryptography (ECC). It 107 specifies methods for using the elliptic curve 2y^2=x^3+x over the 108 field of size 8^91+5. It recommends using this curve in combination 109 with a diverse set of curves, as a strongest-link multi-layer 110 defense-in-depth against undisclosed attacks against some subset of 111 curves. 113 1.1. Background 115 This document presumes that its reader already has familiarity with 116 elliptic curve cryptography (ECC). 118 1.1.1. Notation 120 The symbol '^', as used in '2y^2=x^3+x' and '8^91+5' means 121 exponentiation, also known as powering. For example, y^3=yyy, or 122 y*y*y, if * is used for multiplication, and 8^91 = 8*8*...*8, with 123 91 eights in the product on the right. 125 Note: This document does not use '^' the way that C (and similar 126 programming languages) use it as bit-wise exclusive-or. 128 In hexadecimal (base 16, big-endian) notation, the number 8^91+5 is 130 200000000000000000000000000000000000000000000000000000000000000000005 132 with with 67 zeros between 2 and 5. 134 1.2. Motivation 136 The main motivation is that the description of the curve is very 137 short (for an otherwise secure elliptic curve), thereby reducing the 138 room for a secretly embedded trapdoor, as in [Teske]. 140 The best countermeasure against a secretly embedded trapdoor in an 141 elliptic curve is to use a diverse combination of elliptic curves. 142 So, this curve is only recommended for use in such a combination. 144 The detailed motivations for curve 2y^2=x^3+x over field 8^91+5 are 145 discussed in Appendix B (and in [B1]). 147 Internet-Draft 2019-04-04 149 2. Requirements Language (RFC 2119) 151 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 152 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 153 document are to be interpreted as described in RFC 2119 [BCP14]. 155 3. Encoding a point into 34 bytes 157 Elliptic curve cryptography uses points for public keys and raw 158 shared secrets. 160 Abstractly, points are mathematical objects. For curve 2y^2=x^3+x, 161 a point is either a pair (x,y), where x and y are elements of 162 mathematical field, or a special point O, both of whose coordinates 163 may be deemed as infinity. 165 For 2y^2=x^3+x, the coordinates are x and y are field elements for 166 this curve are integers modulo 8^91+5. 168 Note: for practicality, an implementation will often represented 169 the x-coordinate as a ratio [X:Z] of field elements. Each field 170 element has multiple representations, but [x:1] can viewed as 171 normal representation of x. (Infinity can be then represented by 172 [1:0], though one must be careful.) 174 To interoperably communicate, points must be encoded as byte 175 strings. 177 This draft specifies an encoding of finite points (x,y) as strings 178 of 34 bytes, as described in the following sections. 180 Note: The 34-byte encoding is not injective. Each point is 181 generally among a group of four points that share the same byte 182 encoding. 184 Note: The 34-byte encoding is not surjective. Approximately half 185 of 34-byte strings do not encode a finite point (x,y). 187 Note: In many typical ECC schemes, the 34-byte encoding works 188 well, despite being neither injective nor surjective. 190 3.1. Encoding a point into bytes 192 In short: a finite point (x,y) is encoded by the little-endian byte 193 representation of x or -x, whichever fits into 34 bytes. 195 Internet-Draft 2019-04-04 197 In detail: a point (x,y) is encoded into 34 bytes, as follows. 199 First, ensure that x is fully reduced mod p=8^91+5, so that 201 0 <= x < 8^91+5. 203 Second, further reduce x by a flipping its sign. Let 205 x' =: min(x,p-x) mod 2^272. 207 Third, set the byte string b to be the little-endian encoding of the 208 reduced integer x', by finding the unique integers b[i] such that 209 0<=b[i]<256 and 211 (x' mod 2^272) = sum (0<=i<=33, b[i]*256^i). 213 Pseudocode can be found in Appendix C. 215 Note: the loss of information that happens upon replacing x by -x 216 represents applying a complex multiplication by i on the curve, 217 since [i](x,y) = (-x,iy) = (u,v) is also a point on the curve, 218 because 2u^2 = 2(iy)^2 = -2y^2 = -(x^3+x) = (-x)^3 + (-x) = v^3 + 219 v. In many application, particularly Diffie--Hellman key 220 agreement, this loss of information is carried through the final 221 shared secret, which means that Alice and Bob can agree on the 222 same secret 34 bytes. 224 In elliptic curve algorithms where the original x coordinate and the 225 decoded x coordinate need to match exactly, then the 34-byte 226 encoding is probably not usable unless the following pre-encoding 227 procedure is practical: 229 Given a point x where x is larger than min(x,p-x), first replace x 230 by x'=p-x, on the encoder's side, using the new value x' (instead of 231 x) for any further step in the algorithm. In other words, replace 232 the point (x,y) by the point (x',y')=(-x,iy). Most algorithms will 233 also require a discrete logarithm d of (x,y), meaning (x,y) = [d] G 234 for some point G. Since (x',y') = [i](x,y), we can replace by d' 235 such that [d']=[i][d]. Usually, [i] can be represented by an 236 integer, say j, and we can compute d' = jd (mod ord(G)). 238 3.2. Decoding bytes into a point 240 In short: the bytes are little-endian decoded into an integer which 241 becomes the x-coordinate. Public-key validation done if needed. If 242 needed, the y-coordinate is recovered. 244 Internet-Draft 2019-04-04 246 In greater detail: if byte i is b[i], with an integer value 247 between 0 and 255 inclusive, then 249 x = sum( 0<=i<=33, b[i]*256^i) 251 Note: a value of -x (mod p) will also be suitable, and results in 252 a point (-x,y') which might be different from the originally 253 encoded point. However, it will be one of the points [i](x,y) or 254 -[i](x,y) where [i] means complex multiplication by [i]. 256 In many cases, such as Diffie--Hellman key agreement using the 257 Montgomery ladder, neither the original value of x or -x nor 258 coordinate y of the point is needed. In these cases, the decoding 259 steps can be considered completed. 261 +-------------------------------------------------------+ 262 | | 263 | \ W / /A\ |R) |N | I |N | /G ! | 264 | \/ \/ / \ |^\ | \| | | \| \_7 0 | 265 | | 266 | | 267 | WARNING: Some byte strings b decode to an invalid | 268 | point (x,y) that does not belong to the curve | 269 | 2y^2=x^3+x. In some situations, such invalid b can | 270 | lead to a severe attack. In these situations, the | 271 | decoded point (x,y) MUST be validated, as described | 272 | below in Section 4. | 273 | | 274 +-------------------------------------------------------+ 276 In cases, where a value for at least of y, -y, iy, or -iy is needed 277 such as Diffie--Hellman key agreement using some other coordinate 278 system (such as one might need when converting to Edwards 279 coordinates), the candidate value can be obtained by computing a 280 square root: 282 y = ((x^3+x)/2)^(1/2). 284 In some cases, it is important for the decoded value of x to match 285 the original value of x exactly. In that case, the encoder should 286 use the procedure that replace x by p-x, and adjusts the discrete 287 logarithm appropriately. These steps can be done by the encoder, 288 with the decoder doing nothing. 290 Internet-Draft 2019-04-04 292 4. Point validation 294 In elliptic curve cryptography, scalar multiplying an invalid public 295 key by a private key risks leaking information about the private 296 key. 298 Note: For curve 2y^2=x^3+x over 8^91+5, the underlying attacks are 299 a little milder than the average a typical elliptic curve. 301 4.1. When a public key MAY, SHOULD or MUST be validated 303 4.1.1. Precautionary mandatory validation 305 Every public key (and point) MAY be validated, as an extra 306 precaution (i.e., defense in depth. 308 4.1.2. Simplified validation 310 If small but general implementation aims for high speed, then the 311 implementation might not be able to the cost mandatory public key 312 validation. 314 It SHOULD follow at least the rule that an distrusted public key is 315 validated before combination with a static secret key. 317 +---------------------------------------------------------------+ 318 | STATIC | 319 | SECRET | 320 | KEY ------\ _ ___ | 321 | + ) PUBLIC |\/| | | (_` | | 322 | UNPROVEN ------/ KEY | | \_/ ._) | BE VALIDATED. | 323 | PUBLIC | 324 | KEY | 325 +---------------------------------------------------------------+ 327 4.1.3. Relatively safe cases of non-validation 329 In some application an implementation of ECC seem not to suffer an 330 invalid curve attack. This section lists these situations. 332 Note: The main reason to omit public key validation is save 333 time. 335 Internet-Draft 2019-04-04 337 We classify these situations at two levels: safe, if it seems that 338 no harm is possible, and relatively safe, if it there the attack is 339 both no worse than another attack and requires something else to be 340 broken. 342 To be verified. 344 If the secret key is ephemeral, the public key is trusted (signed) 345 and a Montgomery ladder is used, then omitting validation of the 346 public key seems relatively safe. This is mostly because if the 347 holder of the public key is the attacker, then the trust system has 348 been broken. Furthermore, the attacker, as the intended recipient 349 in a typical communication, should already be able to receive any 350 data hidden by the secret key. 352 To be extended. 354 4.1.4. Minimal validation 356 To maximize efficiency, an implementation may wish to minimize the 357 amount of validation done down to the point of only resisting a 358 known 359 attack. 361 To be completed. 363 Note: a given point need only be validated once, if the 364 implementation can track validation state. 366 The curve 2y^2=x^3+x is not twist-secure: using the Montgomery 367 ladder for scalar multiplication is not enough to thwart invalid 368 public key attacks. 370 Note: the twist of 2y^2=x^3+x/GF(8^91+5) curve has order: 372 2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 * 373 3452464930451677330036005252040328546941 375 4.2. How to validate a point (given only x) 377 Upon decoding the 34 bytes into x, the next step is to compute 378 z=2(x^3+x). Then one checks if z has a nonzero square root (in the 379 field of size 8^91+5). If z has a nonzero square root, then the 380 represented point is valid, otherwise it is not valid. 382 Equivalently, one can check that x^3 + x has no square root (that 383 is, x^3+x is a quadratic non-residue). 385 Internet-Draft 2019-04-04 387 To check z for a square root, one can compute the Legendre symbol 388 (z/p) and check that is 1. (Equivalently, one can check that 389 ((x^3+x)/p)=-1.) 391 The Legendre symbol can be computed using Gauss' quadratic 392 reciprocity law, but this requires implementing modular integer 393 arithmetic for moduli smaller than 8^91+5. 395 More slowly, but perhaps more simply, one compute the Legendre 396 symbol using powering in the field: (z/p) = z^((p-1)/2) = 397 z^(2^272+2). This will have value 0,1 or p-1 (which is equivalent 398 to -1). 400 More generally, in signature applications, where the y-coordinate is 401 also needed, the computation of y, which involves computing a square 402 root will generally include a check that x is valid. 404 OPTIONAL: In some rare situations, it is also necessary to ensure 405 that the point has large order, not just that it is on the curve. 407 For points on this curve, each point has large order, unless it has 408 torsion by 12. In other words, if [12]P != O, then the point P has 409 large order. 411 OPTIONAL: In even rarer situations, it may be necessary to ensure 412 that a point P also has a prime order n = ord(G). The costly method 413 to check this is checking that [n]P = O. An alternative method is 414 to try to solve for Q in the equation [12]Q=P, which involves 415 methods such a division polynomials. 417 To be completed. 419 5. OPTIONAL encodings 421 The following two encodings are not usually required to obtain 422 interoperability in the typical ECC applications, but can sometimes 423 be useful. 425 5.1. Encoding scalar multipliers as 34 bytes 427 To be completed. 429 Basically, little-endian byte encoding of integers is recommended. 431 The main application is to signatures. 433 Internet-Draft 2019-04-04 435 Another application is for test vectors (to be completed). 437 5.2. Encoding 34 bytes into a point (sketch) 439 In niche applications, it may be desired to encode arbitrary bytes 440 as 441 points. 443 Note: This type of encoding is sometimes called hashing to a 444 curve. 446 Note: Diffie--Hellman key exchange or digital signatures do not 447 require encoding of arbitrary byte strings. 449 Example reasons are anonymity, or hiding the presence of a key 450 exchange. 452 Note: the point encoding described earlier does a different job. 453 It encodes every point as a byte string. The task here is the 454 opposite: to encode every byte string as a point. 456 Note: Encoding a byte string as a point yields biased elliptic 457 curve points, but has the advantage that the byte-strings are 458 unbiased. 460 The encoding is called Elligator i, (see also [B1]), and is just a 461 minor variation of the Elligator 2 construction [Elligator]. 462 Elligator 2 fails for curves with j-invariant 1728, which includes 463 2y^2=x^3+x, so a minor tweak is made, obtain Elligator i. 465 Fix a square root i of -1 in the field. 467 Given any random field element r, compute 469 x=i- 3i/(1-ir^2) 471 If there is no y solving 2y^2=x^3+x for this x, then replace x by 472 x+i and try to solve for y once again. 474 If the first x fails, then the second x succeeds. 476 So, now r determines a unique x. To determine y, solve it per the 477 equation, getting two roots. Label the 2 roots y0 and y1 according 478 to a deterministic rule. Then choose y0 if the first x works, else 479 choose y2. This ensures that the map from r^2 to (x,y) is 480 injective. 482 Internet-Draft 2019-04-04 484 Finally, to encode a byte string b, just let it represent a field 485 element r. Note that -r will be require more than 34 bytes. So the 486 map from b to (x,y) is now injective. 488 The Elligator i map is reversible. 490 To be completed. 492 6. IANA Considerations 494 This document requires no actions by IANA, yet. 496 7. Security considerations 498 No cryptographic algorithms is without risks. Consequently, risks 499 are comparative. This section will not fully list the risks of all 500 other forms of elliptic curve cryptography. Instead it will list 501 the most plausible risks of this curve, and only to a limited degree 502 contrast these to a few other standardized curves. 504 7.1. Field choice 506 The field 8^91+5 has the following risks. 508 - 8^91+5 is a special prime. As such, it is perhaps vulnerable to 509 some kind of attack. For example, for some curve shapes, the 510 supersingularity depends on the prime, and the curve size is 511 related in a simple way to the field size, causing a potential 512 correlation between the field size and the effectiveness of an 513 attack, such as the Pohlig--Hellman attack. 515 Many other standard curves, such as the NIST P-256 and 516 Curve25519, also use special prime field sizes, so have a similar 517 risk. Yet other standard curves, such as the Brainpool, use 518 pseudorandom field sizes, so have less risk to this threat. 520 - 8^91+5, while implementable in five 64-bit words, has some risk of 521 overflowing, or of not fully reducing properly. Perhaps a smaller 522 field, such as that used in Curve25519, has a simpler reduction 523 and overflow-avoidance properties. 525 - 8^91+5, by virtue of being well-above 256 bits in size, risks its 526 user doing extra, and perhaps unnecessary, computation to protect 527 their 128-bit keys, whereas smaller curves might be faster (as 528 expected) yet still provide enough security. In other words, the 529 extra cost is wasteful, and partially a form of denial of service. 531 Internet-Draft 2019-04-04 533 - 8^91+5 is smaller than some other six-symbol primes: 8^95-9, 534 9^99+4 and 9^87+4. Arguably, 8^91+5 fails to maximize field size, 535 and thus potential Pollard rho resistance of the ECDLP, among 536 six-symbol primes. The primes 9^99+4 and 9^87+4 are not close to 537 a power of two, so probably suffer from much slower implementation 538 than 8^91+5, which is a significant cost. The prime 8^95-9 is 539 just a little below a power of two, so should have comparable 540 efficiency for basic field arithmetic. The field 8^95-9 is a 541 little larger, but can still be implemented using five 64-bit 542 words. Being larger, 8^85-9, it has a slightly greater risk than 543 8^91+5 of leading to an arithmetic overflow implementation fault 544 in field arithmetic. Also, field size 8^91+5 has very simple 545 powering algorithms for computing field inverses, Legendre 546 symbols, and square roots, all because it is just slightly above a 547 power of two. For field size 8^85-9, these powering algorithms 548 require more complicated algorithms. 550 - 8^91+5 is smaller than 2^283 (the field size for curve sect283k1 551 [SEC2], [Zigbee]), and many other five-symbol and four-symbol 552 prime powers (such as 9^97). It provides less resistance to 553 Pollard rho than such larger prime powers. Recent progress in the 554 elliptic curve discrete logarithm problem, [HPST] and [Nagao], is 555 the main reason to prefer prime fields instead of power of prime 556 fields. A second reason to prefer a prime field (including the 557 field of size 8^91+5) over small characteristic fields is the 558 generally better software speed of large characteristic field. 559 (Better software speed is mainly due to general-purpose hardware 560 often having dedicated fast multiplication circuits: 561 special-purpose hardware should make small characteristic field 562 faster.) 564 See [B1] for further discussion. 566 7.2. Curve choice 568 A first risk of using 2y^2=x^3+x is the fact that it is a special 569 curve, with complex multiplication leading to an efficient 570 endomorphism. Many other standard curves, NIST P-256 [NIST-P-256], 571 Curve25519, Brainpool [Brainpool], do not have any efficient 572 endomorphisms. Yet some standard curves do, NIST K-283 and 573 secp256k1 (see [SEC2] and [BitCoin]). Furthermore, it is not 574 implausible [KKM] that special curves, including those efficient 575 endomorphisms, may survive an attack on random curves. 577 Internet-Draft 2019-04-04 579 A second risk of 2y^2=x^3+x over 8^91+5 is the fact that it is not 580 twist-secure. What may happen is that an implementer may use the 581 Montgomery ladder in Diffie--Hellman and re-use private keys. They 582 may think, despite the (ample?) warnings in this document, that 583 public key validation in unnecessary, modeling their implementation 584 after Curve25519 or some other twist-secure curve. This implementer 585 is at risk of an invalid public key attack. Moreover, the 586 implementer has an incentive to skip public-key validation, for 587 better performance. Finally, even if the implementer uses 588 public-key validation, then the cost of public-key validation is 589 non-negligible. 591 A third risk is a biased ephemeral private key generation in a 592 digital signature scheme. Most standard curves lack this risk 593 because the field size is close to a power of two, and the cofactor 594 is a power of two. Curve 2y^2=x^3+x over 8^91+5 has a base point 595 order which is approximately a power of two divided by nine (because 596 its cofactor is 72=8*9.) As such, it is more vulnerable than 597 typical curves to biased ephemeral keys in a signature scheme. 599 A fourth risk is a Cheon-type attack. Few standard curves address 600 this risk, and 2y^2=x^3+x over 8^91+5 is not much different. 602 A fifth risk is a small-subgroup confinement attack, which can also 603 leak a few bits of the private key. Curve 2y^2=x^3+x over 8^91+5 604 has 72 elements whose order divides 12. 606 7.3. Encoding choices 608 To be completed. 610 7.4. General subversion concerns 612 Although the main motivation of curve 2y^2=x^3+x over 8^91+5 is to 613 minimize the risk of subversion via a backdoor ([Gordon], [YY], 614 [Teske]), it is only fair to point out that its appearance in this 615 very document can be viewed with suspicion as an possible effort at 616 subversion (via a front-door). (See [BCCHLV] for some further 617 discussion.) 619 Any other standardized curve can be view with a similar suspicion 620 (except, perhaps, by the honest authors of those standards for whom 621 such suspicion seems absurd and unfair). A skeptic can then examine 622 both (a) the reputation of the (alleged) author of the standard, 623 making an ad hominem argument, and (b) the curve's intrinsic merits. 625 Internet-Draft 2019-04-04 627 By the very definition of this document, the reader is encouraged to 628 take an especially skeptical viewpoint of curve 2y^2=x^3+x over 629 8^91+5. So, it is expected that skeptical users of the curve will 630 either 632 - use the curve for its other merits (other than its backdoor 633 mitigations), such as efficient endomorphism, field inversion, 634 high Pollard rho resistance within five 64-bit words, meanwhile 635 holding to the evidence-supported belief ECC that is now so mature 636 that worries about subverted curves are just far-fetched nonsense, 637 or 639 - as an additional of layer of security in addition to other 640 algorithms (ECC or otherwise), as an extra cost to address the 641 non-zero probability of other curves being subverted. 643 To paraphrase, consider users seriously worried about subverted 644 curves (or other cryptographic algorithms), either because they 645 estimate as high either the probability of subversion or the value 646 of the data needing protection. These users have good reason to 647 like 2y^2=x^3+x over 8^91+5 for its compact description. 648 Nevertheless, the best way to resist subversion of cryptographic 649 algorithms seems to be combine multiple dissimilar cryptographic 650 algorithms, in a strongest-link manner. Diversity hedges against 651 subversion, and should the first defense against it. 653 7.5. Concerns about 'aegis' 655 The exact curve 2y^2=x^3+x over 8^91+5 was (seemingly) first 656 described to the public in 2017 [AB]. So, it has a very low age. 658 Furthermore, it has not been submitted for a publication with peer 659 review to any cryptographic forum such as the IACR conferences like 660 Crypto and Eurocrypt. So, it has only been reviewed by very few 661 eyes, most of which had little incentive to study it critically. 663 Under the metric of aegis, as in age * eyes, it scores low. 664 Counting myself (but not quantifying incentive) it gets an aegis 665 score of 0.1 (using a rating 0.1 of my eyes factor in the aegis 666 score: I have not discovered any major ECC attacks of my own.) This 667 is far smaller than some more well-studied curves. 669 However, in its defense, the curve 2y^2=x^3+x over 8^91+5 has 670 similarities to some of the better-studied curves with much higher 671 aegis: 673 Internet-Draft 2019-04-04 675 - Curve25519: has field size 8^85-19, which a little similar to 676 8^91+5; has equation of the form by^2=x^3+ax+x, with b and a 677 small, which is similar to 2y^2=x^3+x. Curve25519 has been around 678 for over 10 years, has (presumably) many eyes looking at it, and 679 has been deployed thereby creating an incentive to study. An 680 estimated aegis for Curve25519 is 10000. 682 - P-256: has a special field size, and maybe an estimated aegis of 683 200000. (It is a high-incentive target. Also, it has received 684 much criticism, showing some intent of cryptanalysis. Indeed, 685 there has been incremental progress in finding minor weakness 686 (implementation security flaws), suggestive of actual 687 cryptanalytic effort.) The similarity to 2y^2=x^3+x over 8^91+5 688 is very minor, so very little of the P-256 aegis would be relevant 689 to this document. 691 - secp256k1: has a special field size, though not quite as special 692 as 8^91+5, and has special field equation with an efficient 693 endomorphism by a low-norm complex algebraic integer, quite 694 similar to 2y^2=x^3+x. It is about 17 years old, and though not 695 studied much in academic work, its deployment in Bitcoin has at 696 least created an incentive to attack it. An estimated aegis for 697 secp256k1 is 10000. 699 - Miller's curve: Miller's 1985 paper introducing ECC suggested, 700 among other choices, a curve equation y^2=x^3-ax, where a is a 701 quadratic non-residue. Curve 2y^2=x^3+x is isomorphic to 702 y^2=x^3-x, essentially one of Miller's curves, except that a=1 is 703 a quadratic residue. Miller's curve may not have been studied 704 intensely as other curves, but its age matches that ECC itself. 705 Miller also hinted that it was not prudent to use a special curve 706 y^2=x^3-ax: such a comment may have encouraged some cryptanalysts, 707 but discouraged cryptographers, perhaps balancing out the effect 708 on the eyes factor the aegis. An estimated aegis for Miller's 709 curves is 300. 711 Obvious cautions to the reader: 713 - Small changes in a cryptographic algorithm sometimes cause large 714 differences in security. So security arguments based on 715 similarity in cryptographic schemes should be given low priority. 717 Internet-Draft 2019-04-04 719 - Security flaws have sometimes remained undiscovered for years, 720 despite both incentives and peer reviews (and lack of hard 721 evidence of conspiracy). So, the eyes-part of the aegis score is 722 very subjective, and perhaps vulnerable false positives by a herd 723 effect. Despite this caveat, it is not recommended to ignore the 724 eyes factor in the aegis score: don't just flip through old books 725 (of say, fiction), looking for cryptographic algorithms that might 726 never have been studied. 728 8. References 730 8.1. Normative References 732 [BCP14] Bradner, S., "Key words for use in RFCs to Indicate 733 Requirement Levels", BCP 14, RFC 2119, March 1997, 734 . 736 8.2. Informative References 738 To be completed. 740 [AB] A. Allen and D. Brown. ECC mod 8^91+5, presentation to CFRG, 741 2017. 742 744 [AMPS] Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, and 745 Juraj Somorovsky. Prime and Prejudice: Primality Testing Under 746 Adversarial Conditions, IACR ePrint, 747 2018. 749 [B1] D. Brown. ECC mod 8^91+5, IACR ePrint, 2018. 750 752 [B2] D. Brown. RKHD ElGamal signing and 1-way sums, IACR ePrint, 753 2018. 755 [KKM] A. Koblitz, N. Koblitz and A. Menezes. Elliptic Curve 756 Cryptography: The Serpentine Course of a Paradigm Shift, IACR 757 ePrint, 2008. 759 [BCCHLV] D. Bernstein, T. Chou, C. Chuengsatiansup, A. Hulsing, 760 T. Lange, R. Niederhagen and C. van Vredendaal. How to 761 manipulate curve standards: a white paper for the black hat, IACR 762 ePrint, 2014. 764 [Elligator] (((To do:))) fill in this reference. 766 Internet-Draft 2019-04-04 768 [NIST-P-256] (((To do:))) NIST recommended 15 elliptic curves for 769 cryptography, the most popular of which is P-256. 771 [Zigbee] (((To do:))) Zigbee allows the use of a 772 small-characteristic 773 special curve, which was also recommended by NIST, called K-283, 774 and also known as sect283k1. These types of curves were 775 introduced by Koblitz. These types of curves were not 776 recommended by NSA in Suite B. 778 [Brainpool] (((To do:))) the Brainpool consortium (???) recommended 779 some elliptic curves in which both the field size and the curve 780 equation were derived pseudorandomly from a nothing-up-my-sleeve 781 number. 783 [SEC2] Standards for Efficient Cryptography. SEC 2: Recommended 784 Elliptic Curve Domain Parameters, version 2.0, 2010. 785 787 [IT] T. Izu and T. Takagi. Exceptional procedure attack on elliptic 788 curve cryptosystems, Public key cryptography -- PKC 2003, Lecture 789 Notes in Computer Science, Springer, pp. 224--239, 2003. 791 [PSM] (((To do:))) Pointcheval, Smart, Malone-Lee. Projective 792 coordinates leak. 794 [BitCoin] (((To do:))) BitCoin uses curve secp256k1, which has an 795 efficient endomorphism. 797 [Bleichenbacher] To do: Bleichenbacher showed how to attack DSA 798 using a bias in the per-message secrets. 800 [Gordon] (((To do:))) Gordon showed how to embed a trapdoor in DSA 801 parameters. 803 [HPST] Y. Huang, C. Petit, N. Shinohara and T. Takagi. On 804 Generalized First Fall Degree Assumptions, IACR ePrint 2015. 805 807 [Nagao] K. Nagao. Equations System coming from Weil descent and 808 subexponential attack for algebraic curve cryptosystem, IACR 809 ePrint, 2015. 811 [Teske] E. Teske. An Elliptic Curve Trapdoor System, IACR ePrint, 812 2003. 814 Internet-Draft 2019-04-04 816 [YY] (((To do:))) Yung and Young, generalized Gordon's ideas 817 [Gordon] into 818 Secretly-embedded trapdoor ... also known as a backdoor. 820 Appendix A. Test vectors 822 To be completed. 824 Appendix B. Motivation: minimizing the room for backdoors 826 To be completed. 828 See [AB] and [B1] for some details. 830 The field and curve are described with very few symbols, while 831 retaining many basic security and speed features. 833 A prime field was chosen due to recent asymptotic advances on 834 discrete logarithms in low-characteristic fields [HPST] and 835 [Nagao]. According to [Teske], some characteristic-two elliptic 836 curves could be equipped with a secretly embedded backdoor. 838 Note: this curve is isomorphic to the non-Montgomery curve 839 y^2=x^3-x, which requires just 9 symbols in its description, 1 840 fewer than required by 2y^2=x^3+x. 842 Appendix C. Pseudocode 844 This section uses a C-like pseudocode to describe some of the 845 algorithms useful for implementing this curve. 847 Real-world implementations adapting this pseudocode had better 848 harden this pseudocode against real-world implementation issues. 849 Better yet, real-world code could start from scratch, using the 850 pseudocode only for comparison. 852 Note: the pseudocode relies on some C idioms (hacks?), which might 853 make the pseudocode unclear to those unfamiliar with these idioms. 855 Note: this pseudocode was adapted from a few different 856 experimental prototypes of the author, (which might not be 857 consistent). The pseudocode has not yet received any independent 858 review. 860 Internet-Draft 2019-04-04 862 Note: this pseudocode uses a terse non-conventional coding style, 863 partly as an exercise in arbitrary source code compression (code 864 golf), but also in the mathematics tradition of using many 865 single-letter variable names, which enables seeing an entire 866 formula in a single view and emphasizes the essential mathematical 867 operations rather than the variable's purpose. 869 Note: the pseudocode does not use the C operator ^ for bitwise XOR 870 of integers, which (luckily) avoid possible confusion with the use 871 of ^ as exponentiation operator in the rest of this document. 873 C.1. Byte encoding 875 Pseudocode for byte representation encoding process is 877 878 bite(c b,f x) { 879 i j=34,k=5; f t; 880 mal(t,-1,x); 881 mal(x,cmp(t,x),x); 882 fix(x); 883 for(;j--;) b[j]=x[j/7]>>((8*j)%55); 884 for(;--k;) b[7*k-1]+=x[k]<<(8-k); 885 } 886 888 The input variable is x and the output variable is b. The declared 889 types and functions are as follows: 891 - type c: curve representative, length-34 array of non-negative 892 8-bit integers ("characters"), 894 - type f: field element, a length-5 array of 64-bit integers 895 (negatives allowed), representing a field element as an integer in 896 base 2^55, 898 - type i: 64-bit integers (e.g. entries of f), 900 - function mal: multiply a field element by a small integer (result 901 stored in 1st argument), 903 - function fix: fully reduce an integer modulo 8^91+5, 905 - function cmp: compare two field element (after fixing), returning 906 -1, 0 or 1. 908 Internet-Draft 2019-04-04 910 Note: The two for-loops in the pseudocode are just radix 911 conversion, from base 2^55 to base 2^8. Because both bases are 912 powers of two, this amount to moving bits around. The entries of 913 array b are compute modulo 256. The second loop copies the bits 914 that the first loop misses (the bottom bits of each entry of f). 916 Note: Encoding is lossy, several different (x,y) may encode to the 917 same byte string b. Usually, if (x,y) generated as a part of 918 Diffie--Hellman key exchange, this lossiness has no effect. 920 Note: Encoding should not be confused with encryption. Encoding 921 is merely a conversion or representation process, whose inverse is 922 called decoding. 924 C.2. Byte decoding 926 Pseudocode for decoding is: 928 929 feed(f x,c b) { 930 i j=34; 931 mal(x,0,x); 932 for(;j--;) x[j/7]+=((i)b[j])<<((8*j)%55); 933 fix(x); 934 } 935 937 with similar conventions as used in the pseudocode function bite 938 (defined in the section on encoding), and some extra conventions: 940 - the expression (i)b[j] means that 8-bit integer b[j] is converted 941 to a 64-bit integer (so is no longer treated modulo 256). (In C, 942 this is operation is called casting.) 944 Note: the decode function 'feed' only has 1 for-loop, which is the 945 approximate inverse of the first of the 2 for-loops in the encode 946 function 'bite'. The reason the 'bite' needs the 2nd for-loop is 947 due to the lossy conversion from integers to bytes, whereas in the 948 other direction the conversion is not lossy. The second loop 949 recovers the lost information. 951 C.3. Fermat inversion 953 Projective coordinates help avoid costly inversion steps during 954 scalar multiplication. 956 Internet-Draft 2019-04-04 958 Projective coordinates are not suitable as the final representation 959 of an elliptic curve point, for two reasons. 961 - Projective coordinates for a point are generally not unique: each 962 point can be represented in projective coordinates in multiple 963 different ways. So, projective coordinates are unsuitable for 964 finalizing a shared secret, because the two parties computing the 965 shared secret point may end up with different projective 966 coordinates. 968 - Projective coordinates have been shown to leak information about 969 the scalar multiplier [PSM], which could be the private 970 key. It would be unacceptable for a public key to leak 971 information about the private key. In digital signatures, even a 972 few leaked bits can be fatal, over a few signatures 973 [Bleichenbacher]. 975 Therefore, the final computation of an elliptic curve point, after 976 scalar multiplication, should translate the point to a unique 977 representation, such as the affine coordinates described in this 978 report. 980 For example, when using a Montgomery ladder, scalar multiplication 981 yields a representation (X:Z) of the point in projective 982 coordinates. Its x-coordinate is then x=X/Z, which can be computed 983 by computing the 1/Z and then multiplying by X. 985 The safest, most prudent way to compute 1/Z is to use a side-channel 986 resistant method, in particular at least, a constant-time method. 987 This reduces the risk of leaking information about Z, which might in 988 turn leak information about X or the scalar multiplier. Fermat 989 inversion, computation of Z^(p-2) mod p, is one method to compute 990 the inverse in constant time (if the inverse exists). 992 Pseudocode for Fermat inversion is: 994 Internet-Draft 2019-04-04 996 997 i inv(f y,f x) { 998 i j=272;f z; 999 squ(z,x); 1000 mul(y,x,z); 1001 for(;j--;) squ(z,z); 1002 mul(y,z,y); 1003 return !!cmp(y,(f){}); 1004 } 1005 1007 Other inversion techniques, such as the binary extended GCD, may be 1008 faster, but generally run in variable-time. 1010 When field elements are sometimes secret keys, using a variable-time 1011 algorithm risk leaking these secrets, and defeating security. 1013 C.4. Branchless Legendre symbol computation 1015 Pseudocode for branchlessly computing if a field element x has a 1016 square root: 1018 1019 i has_root(f x) { 1020 i j=270;f y,z; 1021 squ(y,x);squ(z,y); 1022 for(;j--;)squ(z,z); 1023 mul(y,y,z); 1024 return 0==cmp(y,(f){1}); 1025 } 1026 1028 Note: Legendre symbol is usually most appropriately applied to 1029 public keys, which mostly obviates the need for side-channel 1030 resistance. In this case, the implementer can use quadratic 1031 reciprocity for greater speed. 1033 C.5. Field multiplication and squaring 1035 To be completed. 1037 Internet-Draft 2019-04-04 1039 Note (on security): Field multiplication can be achieved most 1040 quickly by using hardware integer multiplication circuits. It is 1041 critical that those circuits have no bugs or backdoors. 1042 Furthermore, those circuits typically can only multiple integers 1043 smaller than the field elements. Larger inputs to the circuits 1044 will cause overflows. It is critical to avoid these overflows, 1045 not just to avoid interoperability failures, but also to avoid 1046 attacks where the attackers supplies inputs likely induce 1047 overflows [bug attacks], [IT]. The following pseudocode 1048 should therefore be considered only for illustrative purposes. 1049 The implementer is responsible for ensuring that inputs cannot 1050 cause overflows or bugs. 1052 The pseudocode below for multiplying and squaring: uses unrolled 1053 loops for efficiency, uses refactoring for source code compression, 1054 relies on a compiler optimizer to detect common sub-expressions (in 1055 squaring). 1057 1058 #define TRI(m,_)\ 1059 zz[0]=m(0,0)_(1,4)_(2,3)_(3,2)_(4,1);\ 1060 zz[1]=m(0,1)_(1,0)_(2,4)_(3,3)_(4,2);\ 1061 zz[2]=m(0,2)_(1,1)_(2,0)_(3,4)_(4,3);\ 1062 zz[3]=m(0,3)_(1,2)_(2,1)_(3,0)_(4,4);\ 1063 zz[4]=m(0,4)_(1,3)_(2,2)_(3,1)_(4,0); 1064 #define CYC(M) ff zz; TRI(+M,-20*M); mod(z,zz); 1065 #define MUL(j,k) x[j]*(ii)y[k] 1066 #define SQR(j,k) x[j]*(ii)x[k] 1067 #define SQU(j,k) SQR(j>k?j:k,j 1072 This pseudocode makes uses of some extra C-like pseudocode features: 1074 - #define is used to create macros, which expand within the source 1075 code (as in C pre-processing). 1077 - type ii is 128-bit integer 1079 - multiplying a type i by a type ii variable yields a type ii 1080 variable. If both inputs can fit into a type i variable, then 1081 the result has no overflow or reduction: it is exact as a product 1082 of integers. 1084 Internet-Draft 2019-04-04 1086 - type ff is array of five type ii values. It is used to represent 1087 a field in a radix expansion, except the limbs (digits) can be 1088 128-bits instead of 64-bits. The variable zz has type ff and is 1089 used to intermediately store the product of two field element 1090 variables x and y (of type f). 1092 - function mod takes an ff variable and produce f variable 1093 representing the same field element. A pseudocode example may be 1094 defined further below. 1096 TO DO: Add some notes (answer these questions): 1098 - How small the limbs of the inputs to function mul and squ must be 1099 to ensure no overflow occurs? 1101 - How small are the limbs of the output of functions mul and squ? 1103 C.6. Field element partial reduction 1105 To be completed. 1107 The function mod used by pseudocode function mul and squ above is 1108 defined below. 1110 1111 #define QUO(x)(x>>55) 1112 #define MOD(x)(x&((((i)1)<<5)-1)) 1113 #define Q(j) QUO(QUO(zz[j])) 1114 #define P(j) MOD(QUO(zz[j])) 1115 #define R(j) MOD(zz[j]) 1116 mod(f z,ff zz){ 1117 z[0]=R(0)-P(4)*20-Q(3)*20; 1118 z[1]=R(1)-P(0)-Q(4)*20; 1119 z[2]=R(2)-P(1)-Q(0); 1120 z[3]=R(3)-P(2)-Q(1); 1121 z[4]=R(4)-P(3)-Q(2); 1122 z[1]+=QUO(z[0]); 1123 z[0]=MOD(z[0]); 1124 } 1125 1127 TO DO: add notes answering these questions: 1129 - How small must be the input limbs to avoid overflow? 1131 - How small are the output limbs (to know how to safely use of 1132 output in further calculations). 1134 Internet-Draft 2019-04-04 1136 C.7. Field element final reduction 1138 To be completed. 1140 The partial reduction technique is sometimes known as lazy 1141 reduction. It is an optimization technique. It aims to do only 1142 enough calculation to avoid overflow errors. 1144 For interoperability, field elements need to be fully reduced, 1145 because partial reduction means the elements still have multiple 1146 different representations. 1148 Pseudocode that aims for final reduction is the following: 1150 1151 #define FIX(j,r,k) {q=x[j]>>r;\ 1152 x[j]-=q<>53; 1158 } 1159 1161 C.8. Scalar point multiplication 1163 Work in progress. 1165 A recommended method of scalar point multiplication is the 1166 Montgomery ladder. However, the curve 2y^2=x^3+x has an efficient 1167 endomorphism. So, this can be used to speed-up scalar point 1168 multiplication, as suggested by Gallant, Lambert and Vanstone. 1170 Combining both GLV and Montgomery is also possible, such as 1171 suggested as by Bernstein. 1173 Note: The following pseudocode is not entirely consistent with 1174 previous pseudocode examples. 1176 Note and Warning: The following pseudocode uses secret indices to 1177 access (small) arrays. This has a risk of cache-timing attacks. 1179 Internet-Draft 2019-04-04 1181 1182 typedef f p[2]; 1183 typedef struct rung {i x0; i x1; i y; i z;} k[137]; 1184 monty_2d (f ps,k sk,f px) { 1185 i j,h; f z; p w[3],x[3],y[2]={{{},{1}}},z[2]; 1186 fix(px);mal(y[0][0],1,px); 1187 endomorphism_1_plus_i(z[0],px); 1188 endo_i(y[1],y[0]); endo_i(z[1],z[0]); 1189 copy(x[1],y[0]); copy(x[2],z[0]); 1190 double_xz(x[0],y[0]); 1191 for(j=0;j<137;j+=){ 1192 double_xz(w[0], x[sk[j].x0 /* cache attack here? */ ]); 1193 diff_add (w[1],x[1],x[sk[j].x1],y[sk[j].y]); 1194 diff_add (2[2],x[2],x[0], z[sk[j].z]); 1195 for(h=0;h<3;h++) {copy(x[h],w[h]);} 1196 } 1197 inv(ps,x[1][1]); 1198 mul(ps,x[1][0],ps); 1199 fix(ps); 1200 } 1201 1203 Note: The pseudocode uses some other functions not defined here, 1204 but whose meaning can be inferred by ECC experts. 1206 Note: The pseudocode uses a specialized format for the scalar. 1207 Normal scalars would have to be re-coded into this format, and 1208 re-coding has non-negligible run-time. Perhaps in 1209 Diffie--Hellman, re-coding is not necessary if one can ensure that 1210 uniformly selection of coded scalars is not a security risk. 1212 TO DO: 1213 - Define the functions used by monty_2d. 1214 - Prove that these function avoid overflow. 1215 - Define functions to re-code scalars for monty_2d. 1217 C.9. Diffie--Hellman pseudocode 1219 To be completed. 1221 This pseudocode would show how to use to scalar multiplication, 1222 combined with point validation, and so on. 1224 C.10. Elligator i 1226 To be completed. 1228 Internet-Draft 2019-04-04 1230 This pseudocode would show how to implement to the Elligator i map 1231 from byte strings to points. 1233 Pseudocode (to be verified): 1235 1236 typedef f xy[2] ; 1237 #define X p[0] 1238 #define Y p[1] 1239 lift(xy p, f r) { 1240 f t ; i b ; 1241 fix(r); 1242 squ(t,r); // r^2 1243 mul(t,I,t); // ir^2 1244 sub(t,(f){1},t); // 1-ir^2 1245 inv(t,t); // 1/(1-ir^2) 1246 mal(t,3,t); // 3/(1-ir^2) 1247 mul(t,I,t); // 3i/(1-ir^2) 1248 sub(X,I,t); // i-3i/(1-ir^2) 1249 b = get_y(t,X); 1250 mal(t,1-b,I); // (1-b)i 1251 add(X,X,t); // EITHER x OR x + i 1252 get_y(Y,X); 1253 mal(Y,2*b-1,Y); // (-1)^(1-b)"" 1254 fix(X); fix(Y); 1255 } 1257 drop(f r, xy p) 1258 { 1259 f t ; i b,h ; 1260 fix(X); fix(Y); 1261 get_y(t,X); 1262 b=eq(t,Y); 1263 mal(t,1-b,I); 1264 sub(t,X,t); // EITHER x or x-i 1265 sub(t,I,t); // i-x 1266 inv(t,t); // 1/(i-x) 1267 mal(t,3,t); // 3/(i-x) 1268 add(t,I,t); // i+ 3/(i-x) 1269 mal(t,-1,t); // -i-3/(i-x)) = (1-3i/(i-x))/i 1270 b = root(r,t) ; 1271 fix(r); 1272 h = (r[4]<(1LL<<52)) ; 1273 mal(r,2*h-1,r); 1274 fix(r); 1275 } 1277 Internet-Draft 2019-04-04 1279 elligator(xy p,c b) {f r; feed(r,b); lift(p,r);} 1281 crocodile(c b,xy p) {f r; drop(r,p); bite(b,r);} 1282 1284 D. Primality proofs and certificates 1286 Recent work of Albrecht and others [AMPS] has shown the combination 1287 of adversarially chosen prime and improper probabilistic primality 1288 tests can result in attacks. 1290 The two primes involved for 2y^2=x^3+x/GF(8^91+5) should already 1291 resist [AMPS] because compact representation of these primes. 1293 For further assurance, this section provides Pratt primality 1294 certificates for the two primes. 1296 Note: Recall that every prime p has a unique Pratt certificate, 1297 which consists of the factorization of p into primes, and, 1298 recursively, Pratt primality certificates for each of those 1299 primes. Verification of a Pratt certificates is also recursive: 1300 it uses the factorization data to conduct Fermat and Lehmer 1301 tests, which together verify primality. 1303 D.1. Pratt certificate for the field size 8^91+5 1305 Define 52 positive integers, a,b,c,...,z,A,...,Z as follows: 1307 a=2 b=1+a c=1+aa d=1+ab e=1+ac f=1+aab g=1+aaaa h=1+abb i=1+ae 1308 j=1+aaac k=1+abd l=1+aaf m=1+abf n=1+aacc o=1+abg p=1+al q=1+aaag 1309 r=1+abcc s=1+abbbb t=1+aak u=1+abbbc v=1+ack w=1+aas x=1+aabbi 1310 y=1+aco z=1+abu A=1+at B=1+aaaadh C=1+acu D=1+aaav E=1+aeff F=1+aA 1311 G=1+aB H=1+aD I=1+acx J=1+aaacej K=1+abqr L=1+aabJ M=1+aaaaaabdt 1312 N=1+abdpw O=1+aaaabmC P=1+aabeK Q=1+abcfgE R=1+abP S=1+aaaaaaabcM 1313 T=1+aIO U=1+aaaaaduGS V=1+aaaabbnuHT W=1+abffLNQR X=1+afFW 1314 Y=1+aaaaauX Z=1+aabzUVY. 1316 Note: variable concatenation is used to indicate multiplication. 1317 For example, f = 1+aab = 1+2*2*(1+2) = 13. 1319 Note: Writing % for modular reduction (with lower precedence than 1320 exponentiation ^), a first step in verifying the Pratt certificate 1321 is a Fermat pseudoprime test for each prime in the list, meaning 1322 the all the numbers below are 1: 1324 Internet-Draft 2019-04-04 1326 2^(b-1)%b, 2^(c-1)%c, 3^(d-1)%d, 2^(e-1)%e, 2^(f-1)%f, 3^(g-1)%g, 1327 2^(h-1)%h, 5^(i-1)%i, 6^(j-1)%j, 3^(k-1)%k, 2^(l-1)%l, 3^(m-1)%m, 1328 2^(n-1)%n, 5^(o-1)%o, 2^(p-1)%p, 3^(q-1)%q, 6^(r-1)%r, 2^(s-1)%s, 1329 2^(t-1)%t, 6^(u-1)%u, 7^(v-1)%v, 2^(w-1)%w, 2^(x-1)%x, 14^(y-1)%y, 1330 3^(z-1)%z, 5^(A-1)%A, 3^(B-1)%B, 7^(C-1)%C, 3^(D-1)%D, 7^(E-1)%E, 1331 5^(F-1)%F, 2^(G-1)%G, 2^(H-1)%H, 2^(I-1)%I, 3^(J-1)%J, 2^(K-1)%K, 1332 2^(L-1)%L, 10^(M-1)%M, 5^(N-1)%N, 10^(O-1)%O, 2^(P-1)%P, 1333 10^(Q-1)%Q, 6^(R-1)%R, 7^(S-1)%S, 5^(T-1)%T, 3^(U-1)%U, 5^(V-1)%V, 1334 2^(W-1)%W, 2^(X-1)%X, 3^(Y-1)%Y, 7^(Z-1)%Z. 1336 Note: Each Fermat base above was chosen as the minimal possible 1337 value. These bases can be deduced from b,c,...,Z by searching 1338 bases 2,3,4,... until a Fermat is found. The results of these 1339 search are included above for convenience. 1341 Note: A second step to verifying a Pratt certificate is to apply 1342 Lehmer's theorem to each Fermat psuedoprime. To prove b,c,d,...,Z 1343 are prime, it now suffices to verify that all of following 154 1344 modular exponentiations result in a value different from 1. 1346 Internet-Draft 2019-04-04 1348 2^((b-1)/a)%b, 2^((c-1)/a)%c, 3^((d-1)/a)%d, 3^((d-1)/b)%d, 1349 2^((e-1)/a)%e, 2^((e-1)/c)%e, 3^((f-1)/a)%f, 3^((f-1)/b)%f, 1350 3^((g-1)/a)%g, 2^((h-1)/a)%h, 2^((h-1)/b)%h, 5^((i-1)/a)%i, 1351 5^((i-1)/e)%i, 6^((j-1)/a)%j, 6^((j-1)/c)%j, 3^((k-1)/a)%k, 1352 2^((l-1)/a)%l, 2^((l-1)/f)%l, 3^((m-1)/a)%m, 3^((m-1)/b)%m, 1353 3^((m-1)/f)%m, 2^((n-1)/a)%n, 2^((n-1)/c)%n, 5^((o-1)/a)%o, 1354 5^((o-1)/b)%o, 5^((o-1)/f)%o, 2^((p-1)/a)%p, 2^((p-1)/l)%p, 1355 3^((q-1)/a)%q, 3^((q-1)/g)%q, 6^((r-1)/a)%r, 6^((r-1)/a)%r, 1356 2^((s-1)/a)%s, 2^((s-1)/b)%s, 2^((t-1)/a)%t, 2^((t-1)/k)%t, 1357 6^((u-1)/a)%u, 6^((u-1)/b)%u, 6^((u-1)/c)%u, 7^((v-1)/a)%v, 1358 7^((v-1)/c)%v, 7^((v-1)/k)%v, 2^((w-1)/a)%w, 2^((w-1)/s)%w, 1359 2^((x-1)/a)%x, 2^((x-1)/b)%x, 2^((x-1)/i)%x, 14^((y-1)/a)%y, 1360 14^((y-1)/c)%y, 14^((y-1)/o)%y, 3^((z-1)/a)%z, 3^((z-1)/b)%z, 1361 3^((z-1)/u)%z, 5^((A-1)/a)%A, 5^((A-1)/t)%A, 3^((B-1)/a)%B, 1362 3^((B-1)/d)%B, 3^((B-1)/h)%B, 7^((C-1)/a)%C, 7^((C-1)/c)%C, 1363 7^((C-1)/u)%C, 3^((D-1)/a)%D, 3^((D-1)/v)%D, 7^((E-1)/a)%E, 1364 7^((E-1)/e)%E, 7^((E-1)/f)%E, 5^((F-1)/a)%F, 5^((F-1)/A)%F, 1365 2^((G-1)/a)%G, 2^((G-1)/B)%G, 2^((H-1)/a)%H, 2^((H-1)/D)%H, 1366 2^((I-1)/a)%I, 2^((I-1)/c)%I, 2^((I-1)/x)%I, 3^((J-1)/a)%J, 1367 3^((J-1)/c)%J, 3^((J-1)/e)%J, 3^((J-1)/j)%J, 2^((K-1)/a)%K, 1368 2^((K-1)/b)%K, 2^((K-1)/q)%K, 2^((K-1)/r)%K, 2^((L-1)/a)%L, 1369 2^((L-1)/b)%L, 2^((L-1)/J)%L, 10^((M-1)/a)%M, 10^((M-1)/b)%M, 1370 10^((M-1)/d)%M, 10^((M-1)/t)%M, 5^((N-1)/a)%N, 5^((N-1)/b)%N, 1371 5^((N-1)/d)%N, 5^((N-1)/p)%N, 5^((N-1)/w)%N, 10^((O-1)/a)%O, 1372 10^((O-1)/b)%O, 10^((O-1)/m)%O, 10^((O-1)/C)%O, 2^((P-1)/a)%P, 1373 2^((P-1)/b)%P, 2^((P-1)/e)%P, 2^((P-1)/K)%P, 10^((Q-1)/a)%Q, 1374 10^((Q-1)/b)%Q, 10^((Q-1)/c)%Q, 10^((Q-1)/f)%Q, 10^((Q-1)/g)%Q, 1375 10^((Q-1)/E)%Q, 6^((R-1)/a)%R, 6^((R-1)/b)%R, 6^((R-1)/P)%R, 1376 7^((S-1)/a)%S, 7^((S-1)/b)%S, 7^((S-1)/c)%S, 7^((S-1)/M)%S, 1377 5^((T-1)/a)%T, 5^((T-1)/I)%T, 5^((T-1)/O)%T, 3^((U-1)/a)%U, 1378 3^((U-1)/d)%U, 3^((U-1)/u)%U, 3^((U-1)/G)%U, 3^((U-1)/S)%U, 1379 5^((V-1)/a)%V, 5^((V-1)/b)%V, 5^((V-1)/n)%V, 5^((V-1)/u)%V, 1380 5^((V-1)/H)%V, 5^((V-1)/T)%V, 2^((W-1)/a)%W, 2^((W-1)/b)%W, 1381 2^((W-1)/f)%W, 2^((W-1)/L)%W, 2^((W-1)/N)%W, 2^((W-1)/Q)%W, 1382 2^((W-1)/R)%W, 2^((X-1)/a)%X, 2^((X-1)/f)%X, 2^((X-1)/F)%X, 1383 2^((X-1)/W)%X, 3^((Y-1)/a)%Y, 3^((Y-1)/u)%Y, 3^((Y-1)/X)%Y, 1384 7^((Z-1)/a)%Z, 7^((Z-1)/b)%Z, 7^((Z-1)/z)%Z, 7^((Z-1)/U)%Z, 1385 7^((Z-1)/V)%Z, 7^((Z-1)/Y)%Z. 1387 Note: The verifier should verify that each base in the Fermat and 1388 Lehmer test are equal. For example, the Fermat base for Z was 7, 1389 and the factorization of Z-1 was aabzUVY, so the Lehmer theorem 1390 test 7^((Z-1)/a)%Z, 7^((Z-1)/b)%Z, ..., 7^((Z-1)/Y)%Z. 1392 Note: The final step is to verify that Z=8^91+5. 1394 Internet-Draft 2019-04-04 1396 Note: The decimal values for a,b,c,...,Y are given by: a=2, b=3, 1397 c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=41, k=43, l=53, m=79, 1398 n=101, o=103, p=107, q=137, r=151, s=163, t=173, u=271, v=431, 1399 w=653, x=829, y=1031, z=1627, A=2063, B=2129, C=2711, D=3449, 1400 E=3719, F=4127, G=4259, H=6899, I=8291, J=18041, K=124123, 1401 L=216493, M=232513, N=2934583, O=10280113, P=16384237, Q=24656971, 1402 R=98305423, S=446424961, T=170464833767, U=115417966565804897, 1403 V=4635260015873357770993, W=1561512307516024940642967698779, 1404 X=167553393621084508180871720014384259, 1405 Y=1453023029482044854944519555964740294049. 1407 D.2. Pratt certificate for subgroup order 1409 Define 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new 1410 values: 1412 a=2 b=1+a c=1+a2 d=1+ab e=1+ac f=1+a2b g=1+a4 h=1+ab2 i=1+ae 1413 j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b 1414 r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e 1415 z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck 1416 G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG 1417 O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ 1418 V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Z=1+ab3oHOT !=1+a3SUX @=1+abNY! 1419 #=1+a4kzF@ $=1+a3QZ# 1421 Note: numeral after variable names represent powers. For example, 1422 f = 1 + a2b = 1 + 2^2 * 3 = 13. 1424 Note: The same process (Fermat and Lehmer tests) verifies that $ 1425 is prime. This process includes search for bases for each of the 1426 prime. These bases have not been included in the certificate. 1428 The last variable, $, is the order of the base point, and the order 1429 of the curve is 72$. 1431 Note: Punctuation used for variable names !,@,#,$, would not scale 1432 for larger primes. For larger primes, a similar format might work 1433 by using a prefix-free set of multil-letter variable names. 1434 E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze: 1436 Internet-Draft 2019-04-04 1438 a=2 b=1+a c=1+a2 d=1+ab e=1+ac f=1+a2b g=1+a4 h=1+ab2 i=1+ae 1439 j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b 1440 r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e 1441 z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck 1442 G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG 1443 O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ 1444 V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Za=1+ab3oHOT Zb=1+a3SUX 1445 Zc=1+abNYZb Zd=1+a4kzFZc Ze=1+a3QZaZd 1447 When parsing this, say 2nd last item Zd=1+a4kzFZc, the string Zd on 1448 the left of = defines a new variables, while the string on the 1449 right = gives its value. The string a4kzFZc can be unambiguously 1450 parsed as a^4*k*z*F*Zc, scanning from left to right for previous 1451 variables, or integers as powers. 1453 Acknowledgments 1455 Thanks to John Goyo and various other BlackBerry employees for past 1456 technical review, to Gaelle Martin-Cocher for encouraging submission 1457 of this I-D. Thanks to David Jacobson for sending Pratt primality 1458 certificates. 1460 Author's Address 1462 Dan Brown 1463 4701 Tahoe Blvd. 1464 BlackBerry, 5th Floor 1465 Mississauga, ON 1466 Canada 1467 danibrown@blackberry.com