idnits 2.17.1 draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-06.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 == Line 309 has weird spacing: '... severe attac...' == Line 1765 has weird spacing: '...ries of resea...' == Line 2815 has weird spacing: '...1+5) in multi...' == Line 2855 has weird spacing: '... 1 subs in +2...' == Line 2858 has weird spacing: '... 0 subs in +...' -- The document date (2020-10-02) is 1295 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 ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 2062 -- Looks like a reference, but probably isn't: '2' on line 2062 -- Looks like a reference, but probably isn't: '0' on line 2062 -- Looks like a reference, but probably isn't: '3' on line 2062 -- Looks like a reference, but probably isn't: '4' on line 2062 Summary: 0 errors (**), 0 flaws (~~), 6 warnings (==), 8 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: 2021-04-05 2020-10-02 5 Elliptic curve 2y^2=x^3+x over field size 8^91+5 6 8 Abstract 10 Multi-curve elliptic curve cryptography with curve 11 2y^2=x^3+x/GF(8^91+5) hedges a risk of new curve-specific attacks. 12 This curve features: isomorphism to Miller's curve from 1985; low 13 Kolmogorov complexity (little room for embedded weaknesses of 14 Gordon, Young--Yung, or Teske); similarity to a Bitcoin curve; 15 Montgomery form; complex multiplication by i 16 (Gallant--Lambert--Vanstone); prime field; easy reduction, 17 inversion, Legendre symbol, and square root; five 64-bit-word field 18 arithmetic; string-as-point encoding; and 34-byte keys. 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. Internet-Drafts are working 24 documents of the Internet Engineering Task Force (IETF). Note that 25 other groups may also distribute working documents as 26 Internet-Drafts. The list of current Internet-Drafts is at 27 http://datatracker.ietf.org/drafts/current. 29 Internet-Drafts are draft documents valid for a maximum of six 30 months and may be updated, replaced, or obsoleted by other documents 31 at any time. It is inappropriate to use Internet-Drafts as 32 reference material or to cite them other than as "work in progress." 34 Copyright Notice 36 Copyright (c) 2020 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with 44 respect to this document. 46 This document may not be modified, and derivative works of it may 47 not be created, except to format it for publication as an RFC or to 48 translate it into languages other than English. 50 Internet-Draft 2020-10-02 52 Contents 54 1. Introduction 55 2. Requirements Language (RFC 2119) 56 3. Use ONLY in multi-curve ECC 57 4. Encoding points 58 4.1. Point encoding process 59 4.1.1. Summary 60 4.1.2. Details 61 4.2. Point decoding process 62 4.2.1. Summary 63 4.2.2. Detail 64 5. Point validation 65 5.1. When to validate 66 5.1.1. Mandatory validation 67 5.1.2. Simplified validation 68 5.1.3. Minimal validation 69 5.2. Point validation process 70 6. OPTIONAL encodings 71 6.1. Encoding scalars 72 6.2. Encoding strings as points 73 7. IANA considerations 74 8. Security considerations 75 8.1. Field choice 76 8.2. Curve choice 77 8.3. Encoding choices 78 8.4. General subversion concerns 79 8.5. Concerns about 'aegis' 80 9. References 81 9.1. Normative References 82 9.2. Informative References 83 Internet-Draft 2020-10-02 85 Appendix A. Why 2y^2=x^3+x/GF(8^91+5)? 86 A.1. Not for single-curve ECC 87 A.2. Risks of new curve-specific attacks 88 A.2.1. What would be considered a "new curve-specific" attack? 89 A.2.2.1. What would be considered a "new" attack? 90 A.2.2.2. What is, would be, considered a "curve-specific attack"? 91 A.2.2.3. Rarity of published curve-specific attacks 92 A.2.2.4. Correlation of curve-specific efficiency and attacks 93 A.3. Mitigations against new curve-specific attacks 94 A.3.1. Fixed curve mitigations 95 A.3.1.2. Existing fixed-curve mitigations 96 A.3.1.2. Migitations used by 2y^2=x^3+x/GF(8^91+5) 97 A.3.2. Multi-curve ECC 98 A.3.2.1. Multi-curve ECC is a redundancy strategy 99 A.3.2.2. Whether to use multi-ECC 100 A.3.2.2.1. Benefits of multi-curve ECC 101 A.3.2.2.2. Costs of multi-curve ECC 102 A.3.2.3. Applying multi-curve ECC 103 A.4. General features of curve 2y^2=x^3+x/GF(8^91+5) 104 A.4.1. Field features 105 A.4.3. Equation features 106 A.4.4. Finite curve features 107 A.4.4.1. Curve size and cofactor 108 A.4.4.2. Pollard rho security 109 A.4.4.3. Pohlig--Hellman security 110 A.4.4.2. Menezes--Okamoto--Vanstone security 111 A.4.4.3. Semaev--Araki--Satoh--Smart security 112 A.4.4.4. Edwards and Hessian form 113 A.4.4.5. Bleichenbacher security 114 A.4.4.6. Bernstein's "twist" security 115 A.4.4.7. Cheon security 116 A.4.4.8 Reductionist security assurance for Diffie--Hellman 117 Appendix B. Test vectors 118 Appendix C. Sample code (pseudocode) 119 C.1. Scalar multiplication of 34-byte strings 120 C.1.1. Field arithmetic for GF(8^91+5) 121 C.1.2. Montgomery ladder scalar multiplication 122 C.1.3. Bernstein's 2-dimensional Montgomery ladder 123 C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong) 124 C.2. Sample code for test vectors 125 C.3. Sample code for a command-line demo of Diffie--Hellman 126 C.4. Sample code for public-key validation and curve basics 127 C.5. Elligator i 128 Appendix D. Minimizing trapdoors and backdoors 129 D.1. Decimal exponential complexity 130 D.1.1. A shorter isomorophic curve 131 D.1.2. Other short curves 132 D.1.3. Converting DEC characters to bits 133 D.1.4. Common acceptance of decimal exponential notation 134 Internet-Draft 2020-10-02 136 D.2. General benefits of low Kolmogorov complexity to ECC 137 D.2.1. Precedents of low Komogorov complexity in ECC 138 D.3. Risks of low Kolmogorov complexity 139 D.4. Alternative measures of Kolmogorov complexity 140 Appendix E. Primality proofs and certificates 141 E.1. Pratt certificate for the field size 8^91+5 142 E.2. Pratt certificate for subgroup order 144 1. Introduction 146 Elliptic curve cryptography (ECC) is now part of several IETF 147 protocols. 149 Multi-curve ECC can mitigate the risk of new curve-specific attacks 150 on ECC. 152 This document aims to contribute to multi-curve ECC by describing 153 how to use the curve 155 2y^2=x^3+x / GF(8^91+5) 157 for elliptic curve Diffie--Hellman (ECDH). 159 Appendix A expands on why and when 2y^2=x^3+x/GF(8^91+5) is useful 160 in multi-curve ECC. 162 2. Requirements Language (RFC 2119) 164 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 165 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 166 document are to be interpreted as described in RFC 2119 [BCP14]. 168 3. Use ONLY in multi-curve ECC 170 An implementation using curve 2y^2=x^3+x/GF(8^91+5) in elliptic 171 curve cryptography MUST use it in a combination with other curves, 172 such as Curve25519 or NIST P-256 (as a second layer of defense 173 against unlikely security failures in the other curves). 175 Appendix A expands on why and when 2y^2=x^3+x/GF(8^91+5) is useful 176 in multi-curve ECC. 178 4. Encoding points 180 Elliptic curve cryptography uses points for public keys and raw 181 shared secret keys. 183 Internet-Draft 2020-10-02 185 Abstractly, points are mathematical objects. For curve 2y^2=x^3+x, 186 a point is either a pair (x,y), where x and y are elements of 187 mathematical field, or a special point O (whose x and y coordinates 188 may be deemed as infinity). 190 Note: The special point O should never be used as a key in 191 practice. In theory, point O is needed for the points to form a 192 mathematical group. 194 For curve 2y^2=x^3+x/GF(8^91+5), the coordinates x and y of the 195 point (x,y) are integers modulo 8^91+5, which can be represented as 196 integers in the interval [0,8^91+4]. 198 Note: An implementation will often internally represent the 199 x-coordinate as a ratio [X:Z] of field elements. Each field 200 element has multiple such representations, but [x:1] can viewed as 201 normal representation of x. (Infinity can be then represented by 202 [1:0].) 204 To interoperably communicate, points must be encoded as byte 205 strings. 207 This draft specifies an encoding of finite points (x,y) as strings 208 of 34 bytes, as described in the following sections. 210 Note: The 34-byte encoding is not injective. Each point is 211 generally among a group of four points that share the same byte 212 encoding. 214 Note: The 34-byte encoding is not surjective. Approximately half 215 of 34-byte strings do not encode a point (x,y). 217 Note: In elliptic Diffie--Helman (ECDH), the 34-byte encoding 218 works well, despite being neither injective nor surjective. 220 4.1. Point encoding process 222 4.1.1. Summary 224 A point (x,y) is encoded by the little-endian byte representation of 225 x or -x, whichever fits into 34 bytes. 227 4.1.2. Details 229 A point (x,y) is encoded into 34 bytes, as follows. 231 Internet-Draft 2020-10-02 233 First, ensure that x is fully reduced mod p=8^91+5, so that 235 0 <= x < 8^91+5. 237 Second, further reduce x by a flipping its sign, as explained next. 238 Let 240 x' =: min(x,p-x) mod 2^272. 242 Third, set the byte string b to be the little-endian encoding of the 243 reduced integer x', by finding the unique integers b[i] such that 244 0<=b[i]<256 and 246 (x' mod 2^272) = sum (0<=i<=33, b[i]*256^i). 248 Pseudocode can be found in Appendix C. 250 Note: The loss of information that happens upon replacing x by -x 251 corresponds to applying complex multiplication by i on the curve, 252 because i(x,y) = (-x,iy) is also a point on the curve. (To see 253 this: note 2(iy)^2 = -(2y^2) = -(x^3+x) = (-x)^3+(-x).) In many 254 applications, particularly Diffie--Hellman key agreement, this 255 loss of information is carried through to the final shared secret, 256 which means that Alice and Bob can agree on the same secret 34 257 bytes. 259 In ECC systems where the original x-coordinate and the decoded 260 x-coordinate need to match exactly, the 34-byte encoding is probably 261 not usable unless the following pre-encoding procedure is practical: 263 Given a point x where x is larger than min(x,p-x), first replace x 264 by x'=p-x, on the encoder's side, using the new value x' (instead 265 of x) for any further step in the algorithm. In other words, 266 replace the point (x,y) by the point (x',y')=(-x,iy). Most 267 algorithms will also require a discrete logarithm d of (x,y), 268 meaning (x,y) = [d] G for some point G. Since (x',y') = [i](x,y), 269 we can replace by d' such that [d']=[i][d]. Usually, [i] can be 270 represented by an integer, say j, and we can compute d' = jd (mod 271 ord(G)). 273 4.2. Point decoding process 275 4.2.1. Summary 277 The bytes are little-endian decoded into an integer which becomes 278 the x-coordinate. Public-key validation is done when needed. If 279 needed, the y-coordinate is recovered. 281 Internet-Draft 2020-10-02 283 4.2.2. Detail 285 If byte i is b[i], with an integer value between 0 and 255 286 inclusive, then 288 x = sum( 0<=i<=33, b[i]*256^i) 290 Note: a value of -x (mod p) will also be suitable, and results in 291 a point (-x,y') which might be different from the originally 292 encoded point. However, it will be one of the points [i](x,y) or 293 -[i](x,y) where [i] means complex multiplication by [i]. 295 In many cases, such as Diffie--Hellman key agreement using the 296 Montgomery ladder, neither the original value of coordinate x (among 297 x and -x) nor coordinate y of the point is needed. In these cases, 298 the decoding steps can be considered completed. 300 +-------------------------------------------------------+ 301 | | 302 | \ W / /A\ |R) |N | I |N | /G ! | 303 | \/ \/ / \ |^\ | \| | | \| \_7 0 | 304 | | 305 | | 306 | WARNING: Some byte strings b decode to an invalid | 307 | point (x,y) that does not belong to the curve | 308 | 2y^2=x^3+x. Some applications would suffer from a | 309 | severe attack if they allow use of (x,y) not on | 310 | the curve. Such vulnerable applications MUST | 311 | validate that the decoded point (x,y) is on the | 312 | curve, as described in Section 5. | 313 | | 314 +-------------------------------------------------------+ 316 In cases where a value for at least one of y, -y, iy, or -iy is 317 needed (such as in Diffie--Hellman key agreement using Edwards 318 coordinates), a candidate value for y can be obtained by computing a 319 square root: 321 y = ((x^3+x)/2)^(1/2). 323 In some specialized applications (not Diffie--Hellman), it is 324 important for the decoded value of x to match the original value of 325 x exactly. In that case, the encoder should use the procedure that 326 replaces x by p-x, and adjusts the discrete logarithm appropriately. 327 These steps can be done by the encoder, with the decoder doing 328 nothing. 330 Internet-Draft 2020-10-02 332 5. Point validation 334 In elliptic curve cryptography, scalar multiplying an invalid public 335 key by a private key risks leaking information about the private 336 key. 338 Note: For curve 2y^2=x^3+x over 8^91+5, the underlying attacks are 339 slightly milder than is average for a typical elliptic curve. 341 To avoid leaking information about the private, the public key can 342 be validated, which includes various checks on the public key. 344 5.1. When to validate 346 This section specifies three strategies (mandatory, simplified, and 347 minimal) about deciding when to validate whether a given point (x,y) 348 is on the curve 2y^2=x^3+x/GF(8^91+5). 350 5.1.1. Mandatory validation 352 As a precautionary defense-in-depth, an impelementation MAY opt to 353 apply mandatory validation, meaning every public key (and point) is 354 validated. 356 5.1.2. Simplified validation 358 A small, general-purpose, implementation aiming for high speed might 359 not be able to afford the cost of mandatory validation from Section 360 4.1.1, because each validation costs about 10% of a scalar 361 multiplication. 363 As a practical middle ground, an impelmentation MAY opt to apply 364 simplified validation, which is the rule is that a distrusted public 365 key is validated before being scalar multiplied by a static secret 366 key. 368 +---------------------------------------------------------------+ 369 | STATIC | 370 | SECRET | 371 | KEY ------\ _ ___ | 372 | + ) PUBLIC |\/| | | (_` | | 373 | UNTRUSTED ------/ KEY | | \_/ ._) | BE VALIDATED. | 374 | PUBLIC | 375 | KEY | 376 +---------------------------------------------------------------+ 378 Internet-Draft 2020-10-02 380 Note: Simplified validation implies that when the secret key is 381 ephemeral (for example, used in one Diffie--Hellman transaction), 382 the public key need not be validated. 384 Note: Simplified validation implies that when the point being 385 scalar multiplied is a known valid fixed point, or a previously 386 validated public key (including a public key from a certificate in 387 which the certification authority has a policy to valid public 388 keys), then validation is not needed. 390 5.1.3. Minimal validation 392 An implementation MAY opt to use minimal validation, meaning doing 393 as little point validation as possible, just enough to resist known 394 attack against the implementation. 396 The curve 2y^2=x^3+x is not twist-secure: using the Montgomery 397 ladder for scalar multiplication is not enough to thwart invalid 398 public key attacks. 400 For example, consider a static hashed-ECDH implementation 401 implemented with a Montgomery ladder, such that the static secret 402 key is used in at most ten million times hashed-ECDH transactions. 403 Even if exposed to invalid points on the twist, the security risk is 404 nearly negligible -- so minimal validation would not validate the 405 peer's public keys. 407 5.2. Point validation process 409 Upon decoding a 34-byte string into x, the next step is to compute 410 z=2(x^3+x). Then one checks if z has a nonzero square root (in the 411 field of size 8^91+5). If z has a nonzero square root, then the 412 represented point is valid, otherwise it is not valid. 414 Equivalently, one can check that x^3 + x has no square root (that 415 is, x^3+x is a quadratic non-residue). 417 To check z for a square root, one can compute the Legendre symbol 418 (z/p) and check that is 1. (Equivalently, one can check that 419 ((x^3+x)/p)=-1.) 421 The Legendre symbol can be computed using Gauss' quadratic 422 reciprocity law, but this requires implementing modular integer 423 arithmetic for integral moduli smaller than 8^91+5. 425 Instead, one can compute the Legendre symbol using powering in the 426 field: (z/p) = z^((p-1)/2) = z^(2^272+2). This is much slower than 427 using quadratic reciprocity, but is perhaps simpler. 429 Internet-Draft 2020-10-02 431 More generally, in signature applications (such as [B2]), where the 432 y-coordinate is also needed, the computation of y, which involves 433 computing a square root will generally implicitly include a check 434 that x is valid. 436 OPTIONAL: In some rare situations, it is also necessary to ensure 437 that the point has large order, not just that it is on the curve. 439 For points on this curve, each point has large order, unless it has 440 torsion by 12. In other words, if [12]P != O, then the point P has 441 large order. 443 OPTIONAL: In even rarer situations, it may be necessary to ensure 444 that a point P also has a prime order q = ord(G). The costly method 445 to check this is checking that [q]P = O. An alternative method is 446 to try to solve for R in the equation [12]R=P, which involves 447 methods such as division polynomials. To be completed. 449 6. OPTIONAL encodings 451 The following two encodings are not usually needed to obtain 452 interoperability in the typical ECC applications, such as 453 Diffie--Hellman (or digital signatures). In more specialized 454 application, these encodings can be useful. 456 6.1. Encoding scalar multipliers 458 Scalar (integer point multipliers) sometimes need to be encoding as 459 byte strings. Typical examples are the following applications. 461 - Digital signature in ECC generallly require scalar encodings. 462 This draft does not specify signature algorithms in detail, only 463 providing some general suggestions. 465 - An implementation needs to store scalars, because scalars are 466 used at least twice, and must be stored between these two uses. 467 For example, in elliptic curve Diffie--Hellman, Alice has scalar 468 a, sends Bob point aG, keeps scalar a until she receives point 469 B from Bob, to which she then applies aB. (If a is ephemeral, 470 she then deletes a.) An implementation is free to use any 471 encoding of scalar, but implementation are often constructed in 472 modular pieces, and any pieces handling the same scalar need to 473 be able to convey the scalar. 475 Internet-Draft 2020-10-02 477 In Diffie--Hellman implementations based on G which has prime order 478 q, where q is approximately p/72, the value of scalar s usually only 479 matters mod q. So, one can reduce s, replacing it by s mod q, 480 making sp-y, replace x by x-i. Solve for s = -i - 3/(i-x). Let r = 547 sqrt(s). If r > p-r, replace r by p-r. Write r in little-endian 548 base 256 to get a 34-byte string b. 550 Note: Just to illustrate a constrast between Elligator i encoding 551 and the normal point encoding, consider the useless example of 552 applying both encodings. Start with 34-byte string b. Apply 553 Elligator i encoding to get a point (x,y). Apply the point 554 encoding to (x,y) to get a 34-byte string b'. In summary, 555 b'=encode(encode(b)). The byte string b' has no significant 556 relation to b. The map b->b' from 34-byte strings to themselves 557 is lossy (non-injective) with ratio ~4:1, and the image set is 558 about one quarter of all 34-byte strings. 560 7. IANA considerations 562 This document requires no actions by IANA, yet. 564 8. Security considerations 566 No cryptographic algorithm is without risk. 568 Possible security risks of 2y^2=x^3+x/GF(8^91+5) are listed in this 569 section. 571 Risk is difficult to estimate, especially aginst possible unknown 572 attacks. Relative risk is slightly easier to estimate, if a 573 comparable cryptographic system is available as a benchmark. 575 Internet-Draft 2020-10-02 577 The security risks of 2y^2=x^3+x/GF(8^91+5) are compared to the 578 risks of a typical generic curve in ECC, or to the risks of specific 579 well-established curves in ECC (such as NIST P-256 and Curve25519). 581 Note: Because 2y^2=x^3+x/GF(8^91+5) MUST be used only in 582 multi-curve ECC, comparison to other curves is mainly for the 583 purposes of benchmarking, and for selection among selection of a 584 secondary or tertiary cuve in a multi-curve ECC implementation. 586 Note: For possible security benefits of 2y^2=x^3+x/GF(8^91+5), see 587 Appendix A. 589 8.1. Field choice 591 The field 8^91+5 has the following risks. 593 - 8^91+5 is a special prime. As such, it is perhaps vulnerable to 594 some kind of attack. For example, for some curve shapes, the 595 supersingularity depends on the prime, and the curve size is 596 related in a simple way to the field size, causing a potential 597 correlation between the field size and the effectiveness of an 598 attack, such as the Pohlig--Hellman attack. In summary, field 599 size is positively correlated to some known attacks, and perhaps a 600 special field size is positively correlated to a potential attack. 602 Nonetheless, many other standard curves, such as the NIST P-256 603 and Curve25519, also use special prime field sizes. In this 604 regard, all these special field curves have a similar risk. 606 Yet other standard curves, such as the Brainpool curves, use 607 pseudorandom field sizes, reducing their risk to potential 608 special-field attack. 610 - 8^91+5 arithmetic implementation, while implementable in five 611 64-bit words, has some risk of overflowing, or of not fully 612 reducing properly. A smaller field, such as that used in 613 Curve25519, should simpler reduction and overflow-avoidance 614 properties. 616 - 8^91+5, by virtue of being well-above 256 bits in size, risks its 617 user doing extra, and perhaps unnecessary, computation to protect 618 their 128-bit keys, whereas smaller curves might be faster (as 619 expected) yet still provide enough security. In other words, the 620 extra computational cost for exceeding 256 bits is wasteful, and 621 partially a form of denial of service. 623 Internet-Draft 2020-10-02 625 - 8^91+5 is smaller than some other six-symbol primes: 8^95-9, 626 9^99+4 and 9^87+4. Therefore, arguably, 8^91+5 fails to 627 absolutely maximize field size relative to decimal exponential 628 complexity. In particular, curves defined over larger field size 629 have better Pollard rho resistance (of the ECDLP). 631 Nonetheless, the primes 9^99+4 and 9^87+4 are not close to a power 632 of two, so probably suffer from about two time slower 633 implementation than 8^91+5, which is a significant runtime cost, 634 and perhaps also a security risk (due to implementation bugs). 636 The prime 8^95-9 is, just like 8^91+5, very close to a power of 637 two. It may thus have efficiency comparable to 8^91+5 for basic 638 field arithmetic operations, such as addition, multiplication and 639 reduction. The field 8^95-9 is a little larger, but is likely 640 also implementable using five 64-bit words. Being larger, 8^95-9 641 has a slightly greater risk than 8^91+5 of leading to an 642 arithmetic overflow implementation fault in field arithmetic. 643 Field size 8^95-9 has much less simple powering algorithms for 644 computing field inverses, Legendre symbols, and square roots: so 645 these operations, often important for ECC, may require more code, 646 more runtime, and perhaps more risk of implementation bugs. 648 - 8^91+5 is smaller than 2^283 (the field size for curve sect283k1 649 [SEC2], [Zigbee]), and many other five-symbol and four-symbol 650 prime powers (such as 9^97). It provides less resistance to 651 Pollard rho than such larger prime powers. Recent progress in the 652 elliptic curve discrete logarithm problem, [HPST] and [Nagao], is 653 the main reason to prefer prime fields instead of power of prime 654 fields. A second reason to prefer a prime field (including the 655 field of size 8^91+5) over small characteristic fields is the 656 generally better software speed of large characteristic field. 657 (Better software speed is mainly due to general-purpose hardware 658 often having dedicated fast multiplication circuits: 659 special-purpose hardware should make small characteristic field 660 faster.) 662 - The Kolmogorov complexity of 8^91+5 as six symbols is only minimal 663 for decimal exponential complexity: but it is not minimal if other 664 types of complexity measures are allowed. For example, if we 665 allow the exclamation mark for the factorial operation -- which is 666 quite standard notation! -- primes larger than 8^91+5 expressible 667 in fewer symbols. For example, 94!-1 is a 485-bit prime number, 668 expressible in five symbols. Such numbers, so far as I know, are 669 not close to a power of two, so would have similar inefficiency 670 and implementability defects to primes like 9^99+4 and 9^87+4. 671 Such inefficiencies could resaonably by the curve choice criteria, 672 ruling out such primes. 674 Internet-Draft 2020-10-02 676 Arguably, in traditional mathematical notation, the symbol '^' is 677 not actually written, with operation being marked by the use of 678 superscripts. In this view, using an ASCII character count 679 arguably gives unduly low weight to the factorial operation as 680 compared to exponentiation. 682 See [B1] for further discussion about the relative merits of 8^91+5. 684 8.2. Curve choice 686 A first risk of using 2y^2=x^3+x is the fact that it is a special 687 curve. It is special in having complex multiplication leading 688 to an efficient endomorphism. Miller, in 1985, already suggested 689 exercising prudence when considering such special curves. Gallant, 690 Lambert and Vanstone found ways to slightly speed up Pollard rho 691 given such an endomorphism, but no other attacks have been found. 693 Menezes, Okamoto and Vanstone (MOV) found an attack on special 694 elliptic curves, of low embedding degree. The curve 695 2y^2=x^3+x/GF(8^91+5) is not vulnerable to their attack, but if one 696 changes the underlying to some different primes, say p', the 697 resulting curve 2y^2=x^3+x/GF(p') is vulnerable to their attack for 698 about half of all primes. Because the MOV was later than Miller's 699 caution from 1984, Miller's prudence seems prescient. Perhaps he 700 was also prescient about yet other potential attacks (still 701 unpublished), and these attacks might affect 2y^2=x^3+x/GF(8^91+5). 703 Many other standard curves, NIST P-256 [NIST-P-256], Curve25519, 704 Brainpool [Brainpool], do not have any efficient complex 705 multiplication endomorphisms. Arguably, these curves comply to 706 Miller's advice to be prudent about special curves. 708 Yet other (fairly) standard curves do, such as NIST K-283 (used in 709 [Zigbee]) and secp256k1 (see [SEC2] and [BitCoin]). Furthermore, it 710 is not implausible [KKM] that special curves, including those 711 efficient endomorphisms, may survive an attack on random curves. 713 A second risk of 2y^2=x^3+x over 8^91+5 is the fact that it is not 714 twist-secure. What may happen is that an implementer may use the 715 Montgomery ladder in Diffie--Hellman and re-use private keys. They 716 may think, despite the (ample?) warnings in this document, that 717 public key validation in unnecessary, modeling their implementation 718 after Curve25519 or some other twist-secure curve. This implementer 719 is at risk of an invalid public key attack. Moreover, the 720 implementer has an incentive to skip public-key validation, for 721 better performance. Finally, even if the implementer uses 722 public-key validation, then the cost of public-key validation is 723 non-negligible. 725 Internet-Draft 2020-10-02 727 A third risk is a biased ephemeral private key generation in a 728 digital signature scheme. Most standard curves lack this risk 729 because the field size is close to a power of two, and the cofactor 730 is a power of two. Curve 2y^2=x^3+x over 8^91+5 has a base point 731 order which is approximately a power of two divided by nine (because 732 its cofactor is 72=8*9.) As such, it is more vulnerable than 733 typical curves to biased ephemeral keys in a signature scheme. 735 A fourth risk is a Cheon-type attack. Few standard curves address 736 this risk, and 2y^2=x^3+x over 8^91+5 is not much different. 738 A fifth risk is a small-subgroup confinement attack, which can also 739 leak a few bits of the private key. Curve 2y^2=x^3+x over 8^91+5 740 has 72 elements whose order divides 12. 742 8.3. Encoding choices 744 To be completed. 746 As in all ECC, projective coordinates are not suitable as the final 747 representation of an elliptic curve point, for two reasons. 749 - Projective coordinates for a point are generally not unique: each 750 point can be represented in projective coordinates in multiple 751 different ways. So, projective coordinates are unsuitable for 752 finalizing a shared secret, because the two parties computing the 753 shared secret point may end up with different projective 754 coordinates. 756 - Projective coordinates have been shown to leak information about 757 the scalar multiplier [PSM], which could be the private 758 key. It would be unacceptable for a public key to leak 759 information about the private key. In digital signatures, even a 760 few leaked bits can be fatal, over a few signatures 761 [Bleichenbacher]. 763 Therefore, the final computation of an elliptic curve point, after 764 scalar multiplication, should translate the point to a unique 765 representation, such as the affine coordinates described in this 766 specification. 768 For example, when using a Montgomery ladder, scalar multiplication 769 yields a representation (X:Z) of the point in projective 770 coordinates. Its x-coordinate is then x=X/Z, which can be computed 771 by computing the 1/Z and then multiplying by X. 773 Internet-Draft 2020-10-02 775 The safest, most prudent way to compute 1/Z is to use a side-channel 776 resistant method, in particular at least, a constant-time method. 777 This reduces the risk of leaking information about Z, which might in 778 turn leak information about X or the scalar multiplier. Fermat 779 inversion, computation of Z^(p-2) mod p, is one method to compute 780 the inverse in constant time (if the inverse exists). 782 8.4. General subversion concerns 784 Although the main motivation of curve 2y^2=x^3+x over 8^91+5 is to 785 minimize the risk of subversion via a backdoor ([Gordon], [YY], 786 [Teske]), it is only fair to point out that its appearance in this 787 very document can be viewed with suspicion as an possible effort at 788 subversion (via a front-door). (See [BCCHLV] for some further 789 discussion.) 791 Any other standardized curve can be view with a similar suspicion 792 (except, perhaps, by the honest authors of those standards for whom 793 such suspicion seems absurd and unfair). A skeptic can then examine 794 both (a) the reputation of the (alleged) author of the standard, 795 making an ad hominem argument, and (b) the curve's intrinsic merits. 797 By the very definition of this document, the reader is encouraged to 798 take an especially skeptical viewpoint of curve 2y^2=x^3+x over 799 8^91+5. So, it is expected that skeptical users of the curve will 800 either 802 - use the curve for its other merits (other than its backdoor 803 mitigations), such as efficient endomorphism, field inversion, 804 high Pollard rho resistance within five 64-bit words, meanwhile 805 holding to the evidence-supported belief ECC that is now so mature 806 that worries about subverted curves are just far-fetched nonsense, 807 or 809 - as an additional of layer of security in addition to other 810 algorithms (ECC or otherwise), as an extra cost to address the 811 non-zero probability of other curves being subverted. 813 To paraphrase, consider users seriously worried about subverted 814 curves (or other cryptographic algorithms), either because they 815 estimate as high either the probability of subversion or the value 816 of the data needing protection. These users have good reason to 817 like 2y^2=x^3+x over 8^91+5 for its compact description. 818 Nevertheless, the best way to resist subversion of cryptographic 819 algorithms seems to be combine multiple dissimilar cryptographic 820 algorithms, in a strongest-link manner. Diversity hedges against 821 subversion, and should the first defense against it. 823 Internet-Draft 2020-10-02 825 Note: For any form of ECC, finite field multiplication can be 826 achieved most quickly by using hardware integer multiplication 827 circuits. It is critical that those circuits have no bugs or 828 backdoors. Furthermore, those circuits typically can only 829 multiply integers smaller than the field elements. Larger inputs 830 to the circuits will cause overflows. It is critical to avoid 831 these overflows, not just to avoid interoperability failures, but 832 also to avoid attacks where the attackers supply inputs likely 833 induce overflows [bug attacks], [IT]. 835 8.5. Concerns about 'aegis' 837 The exact curve 2y^2=x^3+x/GF(8^91+5) was (seemingly) first 838 described to the public in 2017 [AB]. So, it has a very low age, at 839 least compare to more established curves. 841 Furthermore, it has not been submitted for a publication with peer 842 review to any formally peer-reviewed academic cryptographer forum 843 such as the IACR conferences like Crypto and Eurocrypt. So, it has 844 most like been reviewed by very few eyes. 846 Arguably, other reviewers have little incentive to study it 847 critically, for several reasons. The looming threat of a quantum 848 computer has diverted many researchers towards studying post-quantum 849 cryptography, such as supersingular isogeny Diffie--Hellman. The 850 past disputes over NIST P-256 and Curve25519 (and several other 851 alternatives) have perhaps tired some reviewers, many of whom 852 reasonably wish to concentrate on deployment of ECC. 854 So, under the metric of aegis, as in age times eyes (times 855 incentive), 2y^2=x^3+x/GF(8^91+5) scores low. Counting myself (but 856 not quantifying incentive) it gets an aegis score of 0.1 (using a 857 rating 0.1 of my eyes factor in the aegis score: I have not 858 discovered any major ECC attacks of my own.) This is far smaller 859 than my estimates (see below) some more well-studied curves. 861 Nonetheless, the curve 2y^2=x^3+x over 8^91+5 at least has some 862 similarities to some of the better-studied curves with much higher 863 aegis: 865 - Curve25519: has field size 8^85-19, which a little similar to 866 8^91+5; has equation of the form by^2=x^3+ax+x, with b and a 867 small, which is similar to 2y^2=x^3+x. Curve25519 has been around 868 for over 10 years, has (presumably) many eyes looking at it, and 869 has been deployed thereby creating an incentive to study. An 870 estimated aegis for Curve25519 is 10000. 872 Internet-Draft 2020-10-02 874 - NIST P-256: has a special field size, and maybe an estimated aegis 875 of 200000. (It is a high-incentive target. Also, it has received 876 much criticism, showing some intent of cryptanalysis. Indeed, 877 there has been incremental progress in finding minor weakness 878 (implementation security flaws), suggestive of actual 879 cryptanalytic effort.) The similarity to 2y^2=x^3+x over 8^91+5 880 is very minor, so very little of the P-256 aegis would be relevant 881 to this document. 883 - secp256k1: has a special field size, though not quite as special 884 as 8^91+5, and has special field equation with an efficient 885 endomorphism by a low-norm complex algebraic integer, quite 886 similar to 2y^2=x^3+x. It is about 17 years old, and though not 887 studied much in academic work, its deployment in Bitcoin has at 888 least created an incentive to attack it. An estimated aegis for 889 secp256k1 is 10000. 891 - Miller's curve: Miller's 1985 paper introducing ECC suggested, 892 among other choices, a curve equation y^2=x^3-ax, where a is a 893 quadratic non-residue. Curve 2y^2=x^3+x is isomorphic to 894 y^2=x^3-x, essentially one of Miller's curves, except that a=1 is 895 a quadratic residue. Miller's curve may not have been studied 896 intensely as other curves, but its age matches that ECC itself. 897 Miller also hinted that it was not prudent to use a special curve 898 y^2=x^3-ax: such a comment may have encouraged some cryptanalysts, 899 but discouraged cryptographers, perhaps balancing out the effect 900 on the eyes factor the aegis. An estimated aegis for Miller's 901 curves is 300. 903 Obvious cautions to the reader: 905 - Small changes in a cryptographic algorithm sometimes cause large 906 differences in security. So security arguments based on 907 similarity in cryptographic schemes should be given low priority. 909 - Security flaws have sometimes remained undiscovered for years, 910 despite both incentives and peer reviews (and lack of hard 911 evidence of conspiracy). So, the eyes-part of the aegis score is 912 very subjective, and perhaps vulnerable false positives by a herd 913 effect. Despite this caveat, it is not recommended to ignore the 914 eyes factor in the aegis score: don't just flip through old books 915 (of say, fiction), looking for cryptographic algorithms that might 916 never have been studied. 918 9. References 919 Internet-Draft 2020-10-02 921 9.1. Normative References 923 [BCP14] Bradner, S., "Key words for use in RFCs to Indicate 924 Requirement Levels", BCP 14, RFC 2119, March 1997, 925 . 927 9.2. Informative References 929 To be completed. 931 [AB] A. Allen and D. Brown. ECC mod 8^91+5, presentation to CFRG, 932 2017. 933 935 [AMPS] Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, and 936 Juraj Somorovsky. Prime and Prejudice: Primality Testing Under 937 Adversarial Conditions, IACR ePrint, 938 2018. 940 [B1] D. Brown. ECC mod 8^91+5. IACR ePrint, 2018. 941 943 [B2] D. Brown. RKHD ElGamal signing and 1-way sums. IACR ePrint, 944 2018. 946 [B3] D. Brown. Rolling up sleeves when subversion's in the field? 947 IACR eprint, 2020. 949 [KKM] A. Koblitz, N. Koblitz and A. Menezes. Elliptic Curve 950 Cryptography: The Serpentine Course of a Paradigm Shift, IACR 951 ePrint, 2008. 953 [BCCHLV] D. Bernstein, T. Chou, C. Chuengsatiansup, A. Hulsing, 954 T. Lange, R. Niederhagen and C. van Vredendaal. How to 955 manipulate curve standards: a white paper for the black hat, IACR 956 ePrint, 2014. 958 [Elligator] (((To do:))) fill in this reference. 960 [NIST-P-256] (((To do:))) NIST recommended 15 elliptic curves for 961 cryptography, the most popular of which is P-256. 963 [Zigbee] (((To do:))) Zigbee allows the use of a 964 small-characteristic special curve, which was also recommended by 965 NIST, called K-283, and also known as sect283k1. These types of 966 curves were introduced by Koblitz. These types of curves were 967 not recommended by NSA in Suite B. 969 Internet-Draft 2020-10-02 971 [Brainpool] (((To do:))) the Brainpool consortium (???) recommended 972 some elliptic curves in which both the field size and the curve 973 equation were derived pseudorandomly from a nothing-up-my-sleeve 974 number. 976 [SEC2] Standards for Efficient Cryptography. SEC 2: Recommended 977 Elliptic Curve Domain Parameters, version 2.0, 2010. 978 980 [IT] T. Izu and T. Takagi. Exceptional procedure attack on elliptic 981 curve cryptosystems, Public key cryptography -- PKC 2003, Lecture 982 Notes in Computer Science, Springer, pp. 224--239, 2003. 984 [PSM] (((To do:))) Pointcheval, Smart, Malone-Lee. Projective 985 coordinates leak. 987 [BitCoin] (((To do:))) BitCoin uses curve secp256k1, which has an 988 efficient endomorphism. 990 [Bleichenbacher] To do: Bleichenbacher showed how to attack DSA 991 using a bias in the per-message secrets. 993 [Gordon] (((To do:))) Gordon showed how to embed a trapdoor in DSA 994 parameters. 996 [HPST] Y. Huang, C. Petit, N. Shinohara and T. Takagi. On 997 Generalized First Fall Degree Assumptions, IACR ePrint 2015. 998 1000 [Nagao] K. Nagao. Equations System coming from Weil descent and 1001 subexponential attack for algebraic curve cryptosystem, IACR 1002 ePrint, 2015. 1004 [Teske] E. Teske. An Elliptic Curve Trapdoor System, IACR ePrint, 1005 2003. 1007 [YY] (((To do:))) Yung and Young, generalized Gordon's ideas into 1008 Secretly-embedded trapdoor ... also known as a backdoor. 1010 Appendix A. Why 2y^2=x^3+x/GF(8^91+5)? 1012 This sections says why curve 2y^2=x^3+x/GF(8^91+5) can improve ECC, 1013 if used properly in multi-curve ECC. 1015 Note: Later sections (especially 4, 5, 6, 8, A, B, C, and D) cover 1016 some relatively routine ECC details about how to use 1017 2y^2=x^3+x/GF(8^91+5). 1019 Internet-Draft 2020-10-02 1021 A.1. Not for single-curve ECC 1023 Curve 2y^2=x^3+x/GF(8^91+5) SHOULD NOT be used in single-curve ECC. 1025 It is riskier than other IETF-approved curves, such as NIST P-256 1026 and Curve25519, for at least the following reasons: 1028 - it is newer, so riskier, all else equal, and 1030 - it is special, with complex multiplication by i: consensus 1031 continues to agree with Miller's original 1985 opinion that 1032 using (such) special curves is not "prudent". 1034 Koblitz, Koblitz and Menezes [KKM] somewhat dissent from the 1035 consensus against special curves. They list several plausible cases 1036 of special curves -- including some with complex multiplication -- 1037 that they argue might well be safer than random curves. (Others go 1038 even further, dismissing prudence against special curves as myth 1039 [ref-tba].) 1041 Despite this dissent, this report adheres to the consensus, which is 1042 to prefer other curves for single-curve ECC. 1044 The relative newness of 2y^2=x^3+x/GF(8^91+5) is not entire. The 1045 curve equation is isomorphic to one proposed by Miller in 1985, 1046 making it older than the isomorphism class of curve equations in 1047 NIST P-256 or Curve25519. The field size, the prime 8^91+5=2^273+5, 1048 is a prime likely to have been considered before the field size 1049 primes NIST P-256 or Curve25519, but probably not in an application 1050 to ECC (i.e. probably in surveys of special primes). 1052 A.2. Risks of new curve-specific attacks 1054 A risk for all ECC is new curve-specific attacks, especially attacks 1055 on the elliptic curve discrete logarithm problem. A new 1056 curve-specific attack could break any ECC using the affected curves. 1058 The main benefit to ECC of curve 2y^2=x^3+x/GF(8^91+5) is to reduce 1059 this risk in multi-curve variant of ECC. 1061 Internet-Draft 2020-10-02 1063 Note: an arguably larger risk, a quantum computer capable of 1064 running Shor's algorithm, looms over all of ECC. The probability 1065 of this risk is basically independent of the probability new 1066 curve-specific attack, but the impacts are heavily dependent, if a 1067 quantum attack impacts ECC, then the new curve-specific attacks 1068 are totally moot. Also, even if no quantum attack on ECC emerges, 1069 but PQC supplements or replaces ECC, then a new curve-specific 1070 attack becomes much more tolerable. For sake of argument, suppose 1071 probabilities 1% for a new curve-specific attack by 2030, and 10% 1072 for a quantum-attack on ECC by 2030. Addressing the 10% 1073 probability risk is more urgent, but there is still a 90% chance 1074 that of no-quantum-attack. Assuming that PQC is combined with ECC 1075 (instead of replacing it) and assuming that the 10% and 1% 1076 probabilities above are formally independent, then there is 0.9% 1077 probability that new-curve specific on ECC by 2030 would affect 1078 PQC+ECC systems, reducing their security to that of PQC only. 1080 A.2.1. What would be considered a "new curve-specific" attack? 1082 The idea of new curve-specific attacks is now discussed. The 1083 purpose is to remind the reader of the risks, by comparison to past 1084 curve-specific attacks, so that a user can estimate the benefits of 1085 addressing the risk. Ultimately, the reader should make an informed 1086 as possible decision whether the extra cost of multi-curve is 1087 warranted. 1089 A.2.2.1. What would be considered a "new" attack? 1091 The "new" in "new curve-specific attack" means hypothetical and not 1092 yet published, and hence, either future or hidden. This 1093 contemplates an adversary with superior cryptanalytic capability 1094 than current state-of-the-art knowledge. 1096 A.2.2.2. What is, would be, considered a "curve-specific attack"? 1098 The "curve-specific" in "new curve-specific attakc" means that the 1099 following conditions on the attack are true 1101 - it affects almost ECC algorithms using the specific curve 1102 (typically, if the discrete logarithm problem is easy for that 1103 curve, or in some cases, the decision Diffie--Hellman problem), 1105 - it does not affect ECC using at least one other curve 1106 (typically, many other curves), and 1108 - it would not affect a generic group of the same size of the 1109 secure ECC group. 1111 Internet-Draft 2020-10-02 1113 Note: For example, the naive Pollard-rho attack is not 1114 "curve-specific" because it fails the second condition and third 1115 condition (it affects all curves and all generic groups of equal 1116 or smaller size than the attacked curve). The Pohlig--Hellman 1117 attack (on smooth order groups) is not curve-specific because it 1118 fails the third condition. 1120 Note: A side-channel attack on an ECC implementation is not 1121 necessarily "curve-specific" in the strict sense above, if 1122 another ECC implementation using the same curve resists the 1123 attack. Some curves may be more prone than others to side-channel 1124 attacks, here we refer to that situtation "curve-specific 1125 implementation-vulnerability". 1127 Prime-field curves were affected by two curve-specific attacks (on 1128 the discrete logarithm): the MOV attacks, and the SASS attack, both 1129 from before 2001. For the decision Diffie--Hellman problem, a 1130 generalization of the MOV attack can be considered as 1131 curve-specific. 1133 For non-prime-field curves, more recent curve-specific attacks have 1134 been discovered, some asymptotically polynomial-time. (To be 1135 completed.) 1137 A.2.2.3. Rarity of published curve-specific attacks 1139 To be completed. 1141 The known curve-specific attacks against prime-field curves are rare 1142 in the sense of having negligible probability of affecting a random 1143 curve (over a given prime-field). 1145 Some of these are attacks are also field-specific too. 1146 These attacks somewhat rare among all possible non-prime-field 1147 curves (though in some cases the probability among certain class of 1148 curves is non-negligible). 1150 If the rarity of the known curve-specific attacks carries over to 1151 any new curve-specific attacks, then truly random curves should 1152 resist the new curve-specific attacks, except with negligible 1153 probability. Honestly generated, non-random curves should also 1154 resist the new curve-specific attacks, except in the unfortunate 1155 case the new curve-specific attack is correlated with the honest 1156 curve generation criteria. 1158 A.2.2.4. Correlation of curve-specific efficiency and attacks 1160 To be completed. 1162 Internet-Draft 2020-10-02 1164 Many of the known curve-specific attacks affected previously 1165 proposed curves, and presumably honestly generated curves. For 1166 example, supersingular curves were proposed for their slightly 1167 greater efficiency over ordinary curves, but then turned out to be 1168 vulnerable to the MOV attack. (Similarly, curves vulnerable to the 1169 SASS attack were proposed for slight efficiencies, before the SASS 1170 attack was published.) So, such correlations are not only 1171 plausible, but the real-world pattern for ECC. Accidents have 1172 already happened for such non-random curves. 1174 Worse yet, if a non-random curve is chosen maliciously, a 1175 correlation between a hidden curve-specific attack and some sensible 1176 curve generation criteria might well make it possible for a 1177 maliciously chosen non-random curve to be made vulnerable to a 1178 hidden curve-specific attack. 1180 A.3. Mitigations against new curve-specific attacks 1182 Because the risk of new curve-specific attack is nonzero, applying 1183 mitigations against the risk potentially improves security, albeit 1184 at some cost. 1186 A.3.1. Fixed curve mitigations 1188 Often, a single fixed curve is used across a system of ECC users, 1189 generally for reasons of efficiency. This exposes the system to the 1190 nonzero risk of new curve-specific attacks. 1192 A.3.1.2. Existing fixed-curve mitigations 1194 Some of the better established fixed curve have sensibly included 1195 mitigations against the nonzero risk of new curve-specific attacks. 1197 - NIST curve P-256 has coefficients derived from the ouptut of 1198 SHA-1, perhaps aiming to avoid any new curve-specific weakness 1199 that would appply rarely to random curves, although inadequately 1200 so, because the seed input to the hash is utterly inexplicable, 1201 and plausibly manipulable. 1203 - Bernstein's Curve25519 results from a "rigid", non-random design 1204 process, favoring efficiency over all else, perhaps eliminating 1205 intentional subversion towards a new curve-specifc weakness. 1207 - Brainpool's curves are derived using hash functions applied to 1208 nothing-up-my-sleeve numbers, perhaps aiming to mitigate both 1209 intentional subversion and accidental rare weakness. 1211 Internet-Draft 2020-10-02 1213 Note: A reasonable inference from these curves is that risk of new 1214 curve-specific attacks warranted the mitigations used (as listed 1215 above). The risk may be less now that further time has passed, 1216 because no other curve-specific attacks against prime-field curves 1217 arose in the interim. The risk is still not zero, so the 1218 mitigations may still be warranted. 1220 A.3.1.2. Migitations used by 2y^2=x^3+x/GF(8^91+5) 1222 The curve 2y^2=x^3+x/GF(8^91+5) includes similar fixed-curve 1223 mitigations against the risk of new curve-specific attacks: 1225 - a short description (low Kolmogorov compelxity), aiming to have 1226 little wiggle for an intentional embedded weakness (somewhat like 1227 a nothing-up-my-sleeve number used in the Brainpool curves), 1229 - a set of special efficiencies, such as a curve endomorphism, 1230 Montgomery form, and fast field operation (somewhat like the 1231 "rigid" properties of Curve25519 favor efficiency as a mitigation 1232 to fight off intentional embedded weakness), 1234 - a prime field, to stay clear of recent curve-specific attacks on 1235 non-prime-field ECC. 1237 These mitigations do not suffice to justify its use in single-curve 1238 ECC (instead of more established non-special curves). 1240 Note: The mitigations above, like those of NIST P-256 and 1241 Curve25519, have a cost which consists mostly of a one-time 1242 computation. The mitigations are somewhat warranted, even if 1243 multi-curve ECC, because the aim of multi-curve is to hedge the 1244 risk of curve-specific attacks, so it makes sense for each 1245 individual curve to include mitigations against this risk. 1247 A.3.2. Multi-curve ECC 1249 This section further motivates the value of multi-curve ECC over 1250 single-curve ECC, but does specify a detailed way to do multi-curve 1251 ECC. 1253 Multi-curve ECC is only really effective if used with a diverse set 1254 of curves. Multi-curve ECC SHOULD use a set of curves including the 1255 three curves: 1257 NIST P-256, Curve25519, and 2y^2=x^3+x/GF(8^91+5). 1259 Internet-Draft 2020-10-02 1261 Multi-curve ECC aims to further mitigate the risk of curve-specific 1262 attack, by securely combining a diverse set of curves. The aim is 1263 that at least one of the curves used in multi-curve ECC resists a 1264 new curve-specific attack (if a new attack ever appears). This aim 1265 is only plausible if the set of curves used is diverse, in features 1266 or in authorship. 1268 This curve contributes to the diversity necessary for multi-curve 1269 ECC, with special technical features distinct from established 1270 curves NIST P-256 and Curve25519 (and Brainpool): 1272 - complex multiplication by i (low discrimiant, rather than high), 1274 - a greater emphasis on low Kolmogorov descriptional complexity 1275 (rather than hashed coefficient or efficiency). 1277 A.3.2.1. Multi-curve ECC is a redundancy strategy 1279 Multi-curve ECC is an instance of a strategy often called 1280 redundancy, applied to ECC. Redundancy is quite general in that it 1281 can be applied to other types of cryptography, to other types of 1282 information security, and even to safety systems. Other names for 1283 redundant strategies include: 1285 strongest-link, defense-in-depth, hybrid, hedged, composite, 1286 fail-safe, diversified, resilient, belt-and-suspenders, fault 1287 tolerant, robust, multi-layer, robustness, compound, combination, 1288 etc. 1290 A.3.2.2. Whether to use multi-ECC 1292 Multi-curve ECC mitigates the risk of new curve-specific attacks, so 1293 ought to be used instead of single-curve ECC if affordable, such as 1294 when 1296 - the privacy of the data being protected has higher value than 1297 the extra cost of multi-curve ECC, which may be the case for at 1298 least financial, medical, or personally-identifying data, and 1300 - ECC is only a tiny portion of the overall system costs, which 1301 would be the case if the data is human-generated or high-volume, 1302 or if ECC is combined with slow or large post-quantum 1303 cryptography (PQC). 1305 A.3.2.2.1. Benefits of multi-curve ECC 1306 Internet-Draft 2020-10-02 1308 The benefit of multi-curve ECC is difficult to quantify. The aimed 1309 benefit over single-curve ECC is extra security, in the event of a 1310 signficant curve-specific attack. 1312 No extra security results if all the curves used are the same. The 1313 curves must be diverse, so that a potential attack on one is somehow 1314 unlikely to affect the other. This diversity is difficult to 1315 assess. Intuitively, a geometric metaphor of a polygon for the 1316 space of all choices might help. Maximally distant points in a 1317 polygon tend to be vertices, the extremities of the polygon. 1318 Translating this intuition suggests choosing curves at the extremes 1319 of features. 1321 Note: By contrast, in a single-curve ECC, the geometric 1322 metaphor suggests a central internal point, on the grounds that 1323 each vertex is more likely to be affected to a special attack. 1324 Carrying this over to multi-curve suggests that a diverse set 1325 ought to include a non-extreme curve too. 1327 As always, the benefit of security is really the negative of the 1328 cost of an attack, including the risk. 1330 The contextual benefit of multi-curve ECC therefore depends very 1331 much on the application, involving the assessing both the 1332 probability of attack, and the impact of the attack. 1334 Higher value private data has greater impact if attacked, and 1335 perhaps also higher probability, if the adversary is more motivated 1336 to attack it. 1338 Low probability of attacks are mostly inferred through failed but 1339 extensive cryptanalysis efforts. Normally, this is only intuited, 1340 but approaches to quantifiably estimate these probabilities is 1341 possible too, under sufficiently strong assumptions. 1343 To be completed. 1345 A.3.2.2.2. Costs of multi-curve ECC 1347 The cost of multi-curve ECC is fairly easy to quantify (easier than 1348 quantifying the benefit). 1350 The cost of multi-curve is meant to be compared to the cost of 1351 single-curve ECC. 1353 Internet-Draft 2020-10-02 1355 The cost ratio is approximately the number of curves used. The cost 1356 difference depends on the devices implementing the ECC. 1358 For example, on a current personal computer, the extra cost per ECC 1359 transaction can include up to 1 millisecond of runtime and sending 1360 an extra 30 bytes or more. In low-end devices, the time may be 1361 higher due to slower processors. 1363 The contextual cost of ECC depends on the application context. In 1364 some applications, such as personal messages between two users, the 1365 cost (milliseconds and a few hundred bytes) is affordable relative 1366 to the time users spent writing and reading the messages. In other 1367 applications, such as automated inter-device communication with 1368 frequent brief messages, single-curve ECC may already be a 1369 bottleneck, costing most of the run-time. 1371 A.3.2.3. Applying multi-curve ECC 1373 For key establishment, NIST recently proposed (in a draft amendment 1374 to Special Publication 800-133 on key derivation) a mechanism to 1375 support deriving a single symmetric key from the result of multiple 1376 key establishments. In summary, the mechansim is that the raw ECDH 1377 shared secrets would be concatenated and fed into a hash-based key 1378 derivation function. 1380 An alternative would be to XOR multiple shared symmetric-key 1381 together. 1383 So, multi-curve elliptic curve Diffie--Hellman (ECDH) key agreement 1384 could use one of these mechanism to derive a single key from 1385 multi-curve ECDH. 1387 A mechanism to support sending more than one ECDH public key 1388 (usually ephemeral), with an indication of the curve for each ECDH 1389 key, would also be needed. 1391 For signatures, the simplest approach is to attach multiple 1392 signatures to each message. (For signatures providing message 1393 recovery, then an approach is to apply the results, with outer 1394 signatures recover the inner signed message, and so on.) 1396 A.4. General features of curve 2y^2=x^3+x/GF(8^91+5) 1398 This subsection describes some general features of the curve 1400 2y^2=x^3+x/GF(8^91+5), 1402 presuming a familiarity with elliptic curve cryptography (ECC). 1404 Internet-Draft 2020-10-02 1406 Each of a set of well-established features, such as Pollard rho 1407 security or Mongtomgery form, for ECC in general are evaluated and 1408 summarized for the specific curve 2y^2=x^3+x/GF(8^91+5). 1410 Note: Interoperable ECC requires a few more details than are 1411 deducible from mathematical description 2y^2=x^3+x/GF(8^91+5) of 1412 the curve, such encoding points as byte strings. These details 1413 are discussed in Sections 4, 5, and 6. 1415 A.4.1. Field features 1417 The curve's field of definition, GF(8^91+5), is a finite field, as 1418 is always the case in ECC. (Finite fields are Galois field, and the 1419 field of size is p is written as GF(p).) 1421 The field size is the prime p=8^91+5. (See the appendix for a 1422 Pratt primality certificate.) 1424 In hexadecimal (base 16, big-endian) notation, the number 8^91+5 is 1426 200000000000000000000000000000000000000000000000000000000000000000005 1428 with with 67 zeros between 2 and 5. 1430 The most recent known curve-specific attacks on 1431 prime-field ECC are from 2000. 1433 Prime fields in ECC tend be more efficient in software than in 1434 hardware. 1436 The prime p is very close to a power of two. Primes very close to a 1437 power of two are sometimes known as Crandall primes. Reduction 1438 modulo p is more efficient for Crandall primes than for most other 1439 primes (or at least random primes). Perhaps Crandall primes are 1440 more resistant to side-channel attacks or implementation faults than 1441 than most other primes. 1443 The fact that p is slightly larger than a power of two -- rather 1444 than slightly lower -- means that powering algorithms to compute 1445 inverses, Legendre symbols, and square roots are simpler and 1446 slightly more efficient (than would be for prime below a 2-power). 1448 A.4.3. Equation features 1450 The curve equation 2y^2=x^3+x has Montgomery form, 1452 by^2=x^3+ax^2+x, 1454 Internet-Draft 2020-10-02 1456 with (a,b) = (0,2). This permits the Montgomery ladder scalar point 1457 multiplication algorithm to be used, which makes it relatively 1458 efficient, and also easier to protect against side channels. 1460 The curve 2y^2=x^3+x has complex multiplication by i, given an 1461 endomorphism 1463 (x,y) -> (-x,iy). 1465 Note: Strictly speaking, over some fields, the curve would be 1466 supersingular, in which the term "complex mutliplication" is not 1467 used, because the curve then has quaternionic multiplication. 1469 The endomorphism permits the Gallant--Lambert--Vanstone (GLV) scalar 1470 multiplication algorithm, which makes it relatively efficient. (The 1471 GLV method can also be combined with Bernstein's two-dimensional 1472 variant of the Montgomery ladder algorithm.) 1474 The curve has j-invariant 1728, because it has complex 1475 multiplication by i. 1477 Note: The j-invariants 0 and 1728 are special in that the curves 1478 with these j-invariants have more than two automorphisms. 1479 (Relatedly, over complex numbers, the moduli space of elliptic 1480 curves is an orbifold, with exactly two non-smooth points, at j=0 1481 and j=1728.) 1483 A.4.4. Finite curve features 1485 This section describes features of 2y^2=x^3+x/GF(8^91+5) as a finite 1486 curve consisting, the points (x,y) for x,y in GF(p), and also the 1487 point at infinity. In other words, these features are specific to 1488 the combination of both the finite field and the curve equation. 1490 Note: In algebraic geometry, these points are said to rational 1491 over k=GF(p), and the set of rational points written as E[k] = 1492 (2y^2=x^3+x)[GF(8^91+5)], to distinguish from points with 1493 coordinates in the alebraic closure of k=GF(p). 1495 Many security properties, and a few performance properties, of ECC 1496 are specific to a finite curve. 1498 A.4.4.1. Curve size and cofactor 1500 The curve (of points rational over GF(8^91+5)) has size (order) 72q 1501 for a large prime q, which is, in hexadecimal, 1503 71C71C71C71C71C71C71C71C71C71C71C7A4ACED12AE9418569B932B8A7B80438A9 1505 Internet-Draft 2020-10-02 1507 NOTE: Appendix E has a Pratt primality certifcate for q. 1509 So, the curve has cofactor 72. 1511 The curve size can verified by implementing the curve's elliptic 1512 curve arithmetic, and scalar multiplying random points on the curve 1513 by the claimed size. It can be partially verified using the complex 1514 multiplication theory, and a little big integer arithmetic. 1516 The prime p=8^91+5 has p=1 mod 4, so a theorem of Fermat says there 1517 exist integers u and v such that p=u^2+v^2. Numbers u and v can 1518 found using a special case of Cornacchia's algorithm, and are listed 1519 further below. 1521 Complex multiplication theory says that a curve with complex 1522 multiplication by i has size s=(u+1)^2+v^2 = p+2u+1. By negation 1523 and swapping u and v, there are four possible sizes, p+2u+1, p-2u+1, 1524 p+2v+1, p-2v+1 (sometimes known as the twist sizes). 1526 Curve 2y^2=x^3+x/GF(8^91+5) has one of these four sizes. In this 1527 case, its size s is divisible by 72, and has large prime factor q = 1528 s / 72. 1530 The following 'bc' program includes values for u and v applicable to 1531 2y^2=x^3+x/GF(8^91+5), verifies these calculations, and outputs q. 1533 p = 8^91+5 1534 u = 104303302790113346778702926977288705144769 1535 v = 65558536801757875228360405858731806281506 1536 if ( p != u^2+v^2 ) { "u and v incorrect" ; halt } 1537 s = (u+1)^2 + v^2 1538 if ( 0 != (s % 72)) { "size not divisible by 72" ; halt} 1539 q = s/72 1540 q 1542 Note: Theory only indicates that s has one of four values, so an 1543 extra step is needed to verify which of the four values is the 1544 size. Scalar multiplication by s is a general method. A faster 1545 method, specific to 2y^2=x^3+x/GF(8^91+5), is to show that only 1546 one of the four candidate sizes is divisible by 3, and then 1547 demostrate a point of order 3 on this curve. Symbolic calculation 1548 with elliptic curve arithmetic show that the point (x,y) has order 1549 3 if 3x^4 + 1 = 0 in GF(p). The big integer calculation 1550 (-(1+2p)/3)^((p-1)/4) = 1 mod p shows that such an x exists in 1551 GF(p). 1553 Internet-Draft 2020-10-02 1555 Note: The Schoof--Elkies--Atkin (SEA) point-counting algorithm can 1556 compute the size of any general curve, but is slower than methods 1557 for some special curves, which is why Miller suggested special 1558 curves 1985. 1560 A.4.4.2. Pollard rho security 1562 The prime q is 267-bit number. The Pollard rho algorithm for 1563 discrete logarithem to the base G (or any order q point) takes 1564 (proportional to) sqrt(q) ~ 2^133 elliptic curve operations. The 1565 curve provides at least 2^128 security against Pollard rho attacks, 1566 with about 5 bits to spare. 1568 Note: Arguably, the fact ECC operations are slower than 1569 symmetric-key operartions (such as hashing or block ciphers), 1570 means that ECC security should be granted a few extra bits, 1571 perhaps 5-10 bits, of security when trying to match ECC security 1572 with symmetric-key security. In this case, one might say that 1573 2y^2=x^3+x/GF(8^91+5) resists Pollard-rho with 2^140 security, 1574 providing 12 bits of extra security. The extra security can be 1575 viewed as a safety margin for error, or as an excessive to the 1576 extent the smaller, and faster curves would more than suffice to 1577 match 2^128 security of SHA-256 and AES-128. 1579 Gallant, Lambert, Vanstone, show how to speed up Pollard rho 1580 algorithms when the group has an extra endormorphism, which would 1581 apply to 2y^2=x^3+x. The speed-up here amounts to a couple of bits 1582 in the security, 1584 A.4.4.3. Pohlig--Hellman security 1586 The small cofactor means the curve effectively resists 1587 Pohlig--Hellman attack (a generic algorithm to solve discrete 1588 logarithms in any group in time sqrt(m) where m is the largest 1589 prime factor of the group size). 1591 Note: Consensus in ECC is to recommend a small factor, such as 1, 1592 2, 4, or 8, despite the fact that, for random curves, the typical 1593 cofactor is approximately p^(1/3), which is much larger. The 1594 small cofactor helps resists Pohlig--Hellman without increasing 1595 the field size. (A larger field size would be less efficient.) 1597 A.4.4.2. Menezes--Okamoto--Vanstone security 1599 The curve has a large embedding degree. More precisely, the curve 1600 size 72q has q with embedding degree (q-1)/2. 1602 Internet-Draft 2020-10-02 1604 This means that the discrete logarithms to base G (a point of order 1605 q) resist Menezes--Okamoto--Vanstone attack. 1607 The large embedding degree also means that that no feasible pairings 1608 exist that could be used solve the decision Diffie--Hellman problem 1609 (for points of order q). Similarly, the larger embedding degree 1610 also means, it cannot be used for pairing-based cryptography (and it 1611 would already too small to be used for pairing-based cryptography). 1613 Note: Intuitively, a near-miss or a close-call could describe this 1614 curve's resistance to the MOV attack. For about half of all primes 1615 P, then curve 2y^2=x^3+x is supersingular over GF(P), with 1616 embedding degree 2, making them vulnerable to the MOV attack 1617 reduces the elliptic curve discrete logarithm to the finite field 1618 discrete logarithm over GF(P^2). Miller suggested in 1985 to use 1619 isomorphic equations, y^2=x^3-ax, without knowing about the 1992 1620 MOV attack. These special curves would then be vulnerable with 1621 ~50% chance of being, depending on the prime P. This curve was 1622 chosen in full knowledge of the MOV attack. 1624 Note: The near-miss or close-call intuition is misleading, because 1625 many cryptographic algorithms become insecure based on the 1626 slightest adjustment to the algorithm. 1628 Note: The non-supersingularity means that the endomorphism ring is 1629 commutative. For this curve the endomorphism ring is isomorphic 1630 to the ring Z[i] of Gaussian integers. 1632 A.4.4.3. Semaev--Araki--Satoh--Smart security 1634 The fact that the curve size 72q does not equal p, means that the 1635 curve resists the Semaev--Araki--Satoh--Smart attack. 1637 A.4.4.4. Edwards and Hessian form 1639 The cofactor 72 is divisible by 4, so the curve isomorphic to a 1640 curve with an Edwards equation, permitting implementation even more 1641 efficient than the Montgomery ladder. 1643 The Edwards form makes possible the Gallant--Lambert--Vanstone 1644 method that used the efficient endomorphism. 1646 The cofactor 72 is also divisible by 3, so the curve is isomorphic 1647 to a curve with a Hessian equation, which is another type of 1648 equation permmitting efficient implementation. 1650 Internet-Draft 2020-10-02 1652 Note: It is probably too optimisitic and speculative to hope that 1653 future research will show how to take advantage by combining the 1654 efficiencies of Edwards and Hessian curve equations. 1656 A.4.4.5. Bleichenbacher security 1658 Bleichenbacher's attack against faulty implementations 1659 discrete-log-based signatures fully affects 2y^2=x^3+x/GF(8^91+5), 1660 because the base point order q is not particularly close to a power 1661 of two. (Some other curves, such as NIST P-256 and Curve25519, have 1662 the base point order is close to a power of two, which provides 1663 built-in resistant to Bleicenbacher's faulty signature attack.) 1665 Note: Bleichenbacher's attack exploits the signature implmentation 1666 fault of naively reducing uniformly random bit strings modulo q, 1667 the order of the base point, which results in a number biased 1668 towards the lower end of the interval [0,q-1]. 1670 So, q-uniformization of the pre-message secret numbers is critical 1671 for signature applications of 2y^2=x^3+x/GF(8^91+5). Various 1672 uniformization methods are known, such as reducing extra large 1673 numbers, repeated sampling, and so on. 1675 A.4.4.6. Bernstein's "twist" security 1677 Unlike Curve25519, curve 2y^2=x^3+x/GF(8^91+5) is not 1678 "twist-secure", so a Montgomery ladder implementation for static 1679 private keys often requires public-key validation, which is 1680 achievable by comptuation of a Legendre symbol related to the 1681 received public key. 1683 In particular, a Montgomery ladder x-only implementation that does 1684 not implement public-key validation will process a value x for which 1685 no y satsifying the equation exists in GF(p). More precsiely, a y 1686 does exist, but it belongs to the extension field GF(p^2). In this 1687 case, the Montgomery ladder treats x as though it were (x,y) where x 1688 is GF(p) but y is not. Such points belong to a "twist" group, and 1689 this group has order: 1691 2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 * 1692 3452464930451677330036005252040328546941 1694 An adversary can exploit this, by finding such invalid x that 1695 correspond to a lower order group element, and thereby try to learn 1696 partial information about a static private key used by a 1697 non-validating Montgomery ladder implementation. 1699 A.4.4.7. Cheon security 1700 Internet-Draft 2020-10-02 1702 Niche applications in ECC involve revealing points [d^e]G for one 1703 secret number d, and many different integer e, or at least one large 1704 e. One way such points could be reveal is in protocols that employ 1705 a static Diffie--Hellman oracle, a function to compute [d]P from any 1706 point P, which might be applied e times, if e is reasonably small. 1708 Typical ECDH, to be clear, would never reveal such points, for at 1709 least two reasons: 1711 - ECDH is ephemeral, so that the same d is never re-used across 1712 ECDH sessions (because d is used to compute [d]G and [d]Q, and 1713 then discarded), 1715 - ECDH is hashed, so though P=[d]G is sent, the point [d]Q is 1716 hashed to get k = H([d]Q), and then [d]Q is discarded, so the 1717 fact that hash is one-way means that k should not reveal [d]Q, 1718 if k is ever somehow revealed. 1720 The Brown--Gallant--Cheon q-1 algorithm finds d, given [d^e]G, if 1721 e|(q-1). It uses approximately sqrt(q/e) elliptic curve operations. 1722 The Cheon q+1 algorithm finds d, given all the points [d]G, [d^2]G, 1723 ..., [d^e]G, if e|(q+1), and takes a similar amount of computation. 1724 These two algorithms rely on factors e of q-1 or q+1, so the 1725 factorization of these numbers affects the security against the 1726 algorithm. 1728 Cheon security refers to the ability to resist these algorithms. 1730 It is possible seek out special curves with relatively high Cheon 1731 security, becasue q-1 and q+1 have no suitable factors e. 1733 The curve 2y^2=x^3+x/GF(8^91+5) has typical Cheon security in terms 1734 of the factorization of q-1 and q+1. Therefore, in the niche 1735 applications that reveal the requisite points, mitigations ought to 1736 be applied, such as limiting the rate of revealing points, or using 1737 different value d as much as possible (one d per recipient). 1739 For 2y^2=x^3+x/GF(8^91+5) the factorization of q-1 and q+1 are: 1741 q-1 = 2^3 * 101203 * 23810182454264420359 * 1742 10934784357463776473342498062299965925956115086976992657 1743 and 1745 q+1 = 2 * 3 * 11 * 21577 * 54829 * 392473 * 854041 * 1746 8054201530811151253753936635581206856381779711451564813041 1748 Internet-Draft 2020-10-02 1750 The q-1 and q+1 algorithms convert an oracle for function P -> [d]P 1751 into a way to find d. This may be viewed as a reduction of the 1752 discrete logarithm problem to the problem of computing the function 1753 P -> [d]P for the target d. In other words, computing P -> [d]P is 1754 almost as difficulty as solving the discrete logartithm problem. In 1755 many systems with a static Diffie--Hellman secret d, computing the 1756 function P -> [d]P needs to be difficult, or the security will be 1757 defeated. In these case, an efficient q-1 or q+1 algorithm provides 1758 a security assurance, that the computing P -> [d]P without knowing d 1759 is about as hard as solving the discrete logarithm problem. 1761 To be completed. 1763 A.4.4.8 Reductionist security assurance for Diffie--Hellman 1765 A series of research work, from den Boer, from Maurer and Wolf, and 1766 from Boneh and Lipton, shows that Diffie--Hellman oracle can be used 1767 to solve a discrete logarithm, under certain conditions. In other 1768 words, the discrete logarithm problem can sometimes be reduced to 1769 the Diffie--Hellman problem. 1771 This can be interpreted as a security assurance that Diffie--Hellman 1772 problem is at least as hard the discrete logarithm problem, albeit 1773 perhaps with some gap in the difficulty. This formalized security 1774 assurance supplements the standard conjecture that the 1775 Diffie--Hellman problem is at least as hard as the discrete 1776 logarithm. (A contrarian view is that special conditions under 1777 which such a reduction algorithm is possible might coincide with 1778 special conditions under which the discrete logarithm problem is 1779 easier.) 1781 The general idea is to consider a Diffie--Hellman oracle in a group 1782 of order q to provide multiplication in a special representation 1783 field of order q. Recovering the ordinary field representation from 1784 the special field representation amounts to solving the discrete 1785 logarithm problem. 1787 To receover the ordinary representation, the idea is to construct an 1788 auxiliary group of smooth order, where the group is an algebraic 1789 groups over the field of size q. Solving a discrete logarithm in 1790 the auxiliary group is possible using the Pohlig--Hellman problem, 1791 and solving the discrete logarithm in the auxiliary reveals the 1792 ordinary representation of the field, which, as already noted 1793 reveals the discrete logarithm in the original group. 1795 Internet-Draft 2020-10-02 1797 The most obvious auxiliary groups have orders q-1 and q+1, but these 1798 are not smooth numbers. The next most obvious auxiliary are 1799 elliptic curve groups with complex multiplication by i, but none of 1800 these four group have smooth orders either. 1802 A peculiar strategy to show the existence of an auxiliary group of 1803 smooth order without having any effective means of constructing the 1804 group. This can be done by finding a smooth number in the Hasse 1805 interval of q. 1807 To be completed. 1809 Appendix B. Test vectors 1811 The following are some test vectors. 1813 000000000000000029352b31395e382846472f782b335e783d325e79322054534554 1814 00000000000000000000000000000000000000000000000000000000000000000117 1815 c8c0f2f404a9fabc91c939d8ea1b9e258d82e21a427b549f05c832cf8d48296ffad7 1816 5f336f56f86de3d52b0eab85e527f2ac7b9d77605c0d5018f5faa4243fd462b1badd 1817 fc023b3f03b469dca32446db80d9b388d753cc77aa4c3ee7e2bb86e99e7bed38f509 1818 8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221 1819 8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221 1821 The test vectors are explained as follows. (Pseudocode generating 1822 them is supplied in Appendix C.2.) 1824 Each line is 34 bytes, representing a non-negative 272-bit integer. 1825 The integer encoding is hexadecimal, with most significant hex 1826 digits on the left, which is to say, big-endian. 1828 Note: Public keys are encoded as 34-byte strings are 1829 little-endian. Encoded public keys reverse the order of the bytes 1830 found in the test vectors. The pseudocode in Appendix C.2 should 1831 make this clear: since bytes are printed in reverse order. 1833 Each integer is either a scalar (a multiplier of curve points), or 1834 the byte representation of a point P through its x-coordinate or the 1835 x-coordinate of iP (which is the the mod 8^91+5 negation of the 1836 x-coordinate of P). 1838 The first line is a scalar integer x. Its nonzero bytes are the 1839 ASCII representation of the string "TEST 2y^2=x^3+x/GF(8^91+5)", 1840 with the byte order reversed. As a private key, this value of x 1841 would be totally insecure, because it is too small, and like any 1842 test vector, it is public. 1844 The second line is a representation of G, a base point on the curve. 1846 Internet-Draft 2020-10-02 1848 The third line is the representation of z = xG. 1850 The fourth and fifth lines represent updated values of x and z, 1851 obtained after application of the following 100000 scalar 1852 multiplications. 1854 A loop of 50000 iterations is performed. Each iteration consists of 1855 two re-assignments: z = xz and x = zG via scalar multiplications. 1856 In the second assignment, the byte representation of the input point 1857 z is used as the byte representation of an scalar. Similarly, the 1858 output x is the byte representation of the point, which is will used 1859 as as the byte representation of the scalar. 1861 The purpose of the large number of iterations is to catch a bug that 1862 has probability larger than 1/100000 of arising on pseudorandom 1863 inputs. The iterations do nothing to find rarer bugs (such as those 1864 that an adversary can invoke), or silent bugs (side channel leaks). 1866 The sixth and seventh lines are equal to each other. As explained 1867 below, the equality of these lines represents the fact the Alice and 1868 Bob can compute the same shared DH secret. The purpose of these 1869 lines is not to catch any more bugs, but rather a sanity check that 1870 Diffie--Hellman is likely to work. 1872 Alice initializes her DH private key to x, as already computed on 1873 the fourth line of the test vectors (which was the result of 100000 1874 iterations). She then replaces this x by x^900 mod q (where q is 1875 the prime which is the order of the order of the base point G). 1877 Bob sets his private key y as follows. He begins with y being the 1878 34-byte ASCII string whose initial characters are "yet another test" 1879 (not including the quotes, of course). He then reverses the order 1880 of bytes, considers this to be a scalar, and reassigns y to yG. 1881 (So, the y on the left is new, the y on the right is old, they are 1882 not the samem, after the assignment.) Another reassignment is done, 1883 as y -> yy, where the on the right side of the equation one y is 1884 treated as a scalar, the other as a point. Finally, Bob's replaces 1885 y by y^900 mod order(G), similarly to Alice's transformation. 1887 The test code in C.2 does not compute x^900 directly. Instead it 1888 uses 900 scalar multiplication by x, to achieve multiplication by 1889 x^900. The same is done for y^900. 1891 Both lines are xyG. The first can be computed as y(xG), and the 1892 second as x(yG). The equality of the two lines can be used to 1893 self-test an implementation, even if the implementation being tested 1894 disagrees with the test vectors above. 1896 Internet-Draft 2020-10-02 1898 Appendix C. Sample code (pseudocode) 1900 This section has sample C code that illustrates well-known elliptic 1901 algorithms, adaptations specific to 2y^2=x^3+x/GF(8^91+5). 1903 As a warning: the sample code has not been fully hardened against 1904 side channels or any other implementation attacks; also, no 1905 independent party has reivewed the sample code. 1907 Note: The quality of the sample code is similar to pseudocode, not 1908 reference code, or software. It compiles and runs on my personal 1909 devices, but has not otherwise been tested for quality. 1911 Note: Non-standard C language extensions are used the sample code: 1912 the type __int128, available as an C language extension in the GNU 1913 C compiler (gcc). 1915 Note: Non-portable C is used (beyond the non-standard C), for 1916 convenience. Two's complement integer representation of integers 1917 is assumed. Bit-shifts negative integers are used, in a way that 1918 considered non-portable under strict C, even though commonly used 1919 elsewhere. 1921 Note: Manually minified C is used: to reduce line and character 1922 counts, and also to (arguably) aid objective code inspection by 1923 cramming as much code into a single screen and by not misleading 1924 reviewers with long comments or variable names. 1926 Note: Automated tools, such as indent (used as in "gcc -E pseudo.c 1927 | indent"), can partially revert the C sample code spacing to a 1928 more conventional style, though other aspects of minification are 1929 not so easy to remove. 1931 Note: The minification is not total. It tries to organize the 1932 code into meaningful units, such as placing single short functions 1933 on one line or placing all variable declarations on the same line 1934 with the function parameters. Python-like indentation is kept. 1935 (Per Lisp styling, the code clumps closing delimiters (that mainly 1936 serve the compilers.)) 1938 Note: Long sequence expressions, using the C comma operator, in 1939 place of multiple expression statements, which would be more 1940 conventional and terminated by semicolons, save some braces in 1941 control statements, such as "for" loops and "if" conditionals, and 1942 enable extra intializations in declarations. 1944 C.1. Scalar multiplication of 34-byte strings 1945 Internet-Draft 2020-10-02 1947 The sample code for scalar multiplication provides an interface for 1948 scalar multiplication. A function "mulch" takes as input 3 pointer 1949 to unsigned character strings. The first input is the location 1950 of the result, the second is the muliplier, and the third is the 1951 base point. 1953 Note: The input ordering follows the convention of C assignment 1954 expressions z=x*y. 1956 Note: The function name "mulch" is short for multiply charcater 1957 strings. 1959 Mulch returns a Boolean value, indicating success or failure. 1960 Failure is returned only if validation is requested, and the base 1961 point is invalid. 1963 Requesting validation is done implicitly, by comparison of pointers. 1964 Validation is requested unless the base point is the known valid 1965 base point G, or if the scalar multiple (2nd input) and the output 1966 (1st input) pointers are equal, meaning that the scalar multiple 1967 will be overwritten. 1969 Note: The motivation here for implicitly requesting validation is 1970 that if the scalar multiple is really ephemeral, the caller should 1971 be willing, and eager, to overwrite it as soon as possible, in 1972 order to achieve forward secrecy. In this case, the need for 1973 input validation is usually negligible. 1975 The sample code is to be considered as a single file, pseudo.c. 1977 The file pseudo.c has two sections. The first section implements 1978 arithmetic for the field GF(8^91+5). The second section implemetns 1979 Montgomery's ladder for curve 2y^2=x^3+x. The two sections are not 1980 entirely independent. In particular, the field arithmetic section 1981 is not general-purpose, and could produce errors if used for 1982 different elliptic curve algorithms, such as Edwards coordinates. 1984 Note: The scalar muliplication sample code pseudo.c file is 1985 included into 3 other sample (using a the C preprocessor directive 1986 #include "pseudo.c"). 1988 Note: Compiler optimizations make a large difference when used on 1989 the field arithmetic (for versions of the sample code where the 1990 field and curve arithmetic are in separate source files). This 1991 suggests that field arithmetic efficiency has room for further 1992 improvement by hand assembly. (The curve arithmetic might be 1993 improved by re-writing the source code.) In case, the sample code 1994 should not be considered to fully optimized. 1996 Internet-Draft 2020-10-02 1998 Note: Montgomery's ladder might not be the fastest scalar 1999 multiplication algorithm for 2y^2=x^3+x/GF(8^91+5). Experimental 2000 C implementations using Bernstein's 2-D ladder algorithm seem 2001 about ~10% faster. The experimental code somewhat more 2002 complicated, and thus more likely to vulnerable to side channels 2003 or overflows. Even more aggressive C code seems about ~20% 2004 faster, using Edwards coordinates, Hisil--Carter--Dawson--Wong, 2005 and Gallant--Lambert--Vanstone, and pre-computed windows. Again, 2006 these faster methods are more complicated, and may be more 2007 vulnerable implementation attacks. The 10% and 20% gains may be 2008 lost upon more thorough hardening against implemenatioon attacks, 2009 or upon more thorough hand-assembly optimizations. 2011 To be completed. 2013 C.1.1. Field arithmetic for GF(8^91+5) 2015 The field arithmetic sample code, is the first part of the file 2016 pseudo.c. It implements the field operations used in the Montgomery 2017 ladder algorithm for elliptic curve 2y^2=x^3+x. For example, point 2018 decompression is not used in Montgomery ladders, so the square root 2019 operation is not included the sample code. (The Legendre symbol 2020 computation is included for validation, and is quite similar to the 2021 square root operation.) 2023 Internet-Draft 2020-10-02 2025 2026 #define RZ return z 2027 #define F4j i j=5;for(;j--;) 2028 #define FIX(j,r,k) q=z[j]>>r, z[j]-=q<b)-(a>55*k&((k<2)*M-1)) 2032 #define MUL(m,E)\ 2033 zz[0]= m(0,0)E(1,4)E(2,3)E(3,2)E(4,1),\ 2034 zz[1]= m(0,1)m(1,0)E(2,4)E(3,3)E(4,2),\ 2035 zz[2]= m(0,2)m(1,1)m(2,0)E(3,4)E(4,3),\ 2036 zz[3]= m(0,3)m(1,2)m(2,1)m(3,0)E(4,4),\ 2037 zz[4]= m(0,4)m(1,3)m(2,2)m(3,1)m(4,0);\ 2038 z[0]=R(0,0)-R(4,1)*20-R(3,2)*20, z[1]=R(1,0)+R(0,1)-R(4,2)*20,\ 2039 z[2]=R(2,0)+R(1,1)+R(0,2), z[3]=R(3,0)+R(2,1)+R(1,2),\ 2040 z[4]=R(4,0)+R(3,1)+R(2,2); z[1]+=z[0]>>55; z[0]&=M-1; 2041 typedef long long i;typedef i*f,F[5];typedef __int128 ii,FF[5]; 2042 i M=((i)1)<<55;F O={0},I={1}; 2043 f fix(f z){i j=0,q; 2044 for(;j<5*2;j++) FIX(j%5,(j%5<4?55:53),(j%5<4?1:-5)); 2045 z[0]+=(q=z[0]<0)*5; z[4]+=q<<53; RZ;} 2046 i cmp(f x,f y){i z=(fix(x),fix(y),0); F4j z+=!z*CMP(x[j],y[j]); RZ;} 2047 f add(f z,f x,f y){F4j z[j]=x[j]+y[j]; RZ;} 2048 f sub(f z,f x,f y){F4j z[j]=x[j]-y[j]; RZ;} 2049 f mal(f z,i s,f y){F4j z[j]=y[j]*s; RZ;} 2050 f mul(f z,f x,f y){FF zz; MUL(+XY,-20*XY); {F4j zz[j]=0;} RZ;} 2051 f squ(f z,f x){mul(z,x,x); RZ;} 2052 i inv(f z){F t;i j=272; for(mul(z,z,squ(t,z));j--;) squ(t,t); 2053 return mul(z,t,z), (sub(t,t,t)), cmp(O,z);} 2054 i leg(f y){F t;i j=270; for(squ(t,squ(y,y));j--;) squ(t,t); 2055 return j=cmp(I,mul(y,y,t)), (sub(y,y,y),sub(t,t,t)), (2-j)%3-1;} 2056 2058 Field elements are stored as five-element of arrays of limbs. Each 2059 limb is an integer, possibly negative, with array z representing 2060 integer 2062 z[0] + z[1]*2^55 + z[2]*2^110 + z[3]*2^165 + z[4]*2^220 2064 In other words, the radix (base) is 2^55. Say that z has m-bit 2065 limbs if each |z[i]| < 2^m. 2067 Internet-Draft 2020-10-02 2069 The field arithmetic function input order follows the C assignment 2070 order, as input z=x*y, so usually the first input is the location 2071 for the result of the operation. The return value is usually just a 2072 pointer to the result's location, the first input, indicated by the 2073 preprocessor macro RZ. The functions, inv, cmp, and leg, also 2074 return an integer, which is not a field element, but usually a 2075 Boolean (or for function leg, a value in {-1,0,1}.) 2077 The utility functions are fix and cmp. They are meant to take 2078 inputs with 58-bit limbs, and produce an output with 55-bit 2079 non-negative limbs, with the highest limb, a 53-bit value. The 2080 purpose of fix is to provide a single array representation of each 2081 field element. The function cmp fixes both its inputs, and then 2082 returns a sigend comparison indicator (in {-1,0,1}). 2084 The multiplicative functions are mul, squ, inv and leg. They are 2085 meant to take inputs with 58-bit limbs, and produce either an output 2086 with 57-bit limbs, or a small integer output. They try to do this 2087 as follows: 2089 1. Some of the input limbs are multiplied by 20, then multiplied 2090 in pairs to 128-bit limbs, and then summed in groups of five 2091 (with at least one of the pairs having both elements not 2092 multiplied by 20). The multiplications by 20 should not cause 2093 64-bit overflow 20*2^58 < 32*2^58=2^63, while the sums of 2094 128-bit numbers should not cause overflow, because 2095 (1+4*20)*2^58*2^58 = 81*2^116 < 2^7*2^116 = 2^123. 2097 2. The five 128-bit limbs are partially reduced to five 57-bit 2098 limbs. Each the five smaller limbs is obtained by summing two 2099 55-bit limbs, extracted from sections of the 128-bit limbs, and 2100 then summing one or two much smaller values summing to less 2101 than a 55-bit limb. So, the final limbs in the multiplication 2102 are a sum of at most three 55-bit sub-limbs, making each final 2103 limb at most a 57-bit limb. 2105 The additive functions are add, sub and mal. They are meant to take 2106 inputs with 57-bit limbs, and product an output with 58-bit limbs. 2108 The utility and multiplicative function can be used repeatedly, 2109 because they do not lengthen the limbs. 2111 Internet-Draft 2020-10-02 2113 The additive functions potentially increase the limb length, because 2114 they do not perform any reduction on the output. The additive 2115 functions should not be applied repeatedly. For example, if the 2116 output of addtive additive function is fed directly as the input to 2117 an additive function, then the final output might have 59-bit 2118 limbs. In this case, if 2nd output might not be evaluated corrected 2119 if given as input to one of the multipilcative functions, an error 2120 due to overflow of 64-bit arithmetic might occur. 2122 The lack of reduction in the additive functions trades generality 2123 for efficiency. The elliptic curve arithmetic code aims to never 2124 send the output of an additive function directly into the input of 2125 another additive function. 2127 Note: Zeroizing temporary field values is attempted by subtracting 2128 them from themselves. Some compilers might remove these 2129 zeroization steps. 2131 Note: The defined types f and F are essentially the equivalent. 2132 The main difference is that type F is an array, so it can be used 2133 to allocate new memory (on the stack) for a field value. 2135 C.1.2. Montgomery ladder scalar multiplication 2137 The second part of the file "pseudo.c" implements Montgomery's 2138 well-known ladder algorithm for elliptic curve scalar point 2139 multiplication, as it applies to the curve 2y^2=x^3+x. 2141 The sample code, as part of the same file, is a continuation of the 2142 sample code for field arithmetic. All previous definitions are 2143 assumed. 2145 Internet-Draft 2020-10-02 2147 2148 #define X z[0] 2149 #define Z z[1] 2150 enum {B=34}; typedef void _;typedef volatile unsigned char *c,C[B]; 2151 typedef F*e,E[2];typedef E*v,V[2]; 2152 f feed(f x,c z){i j=((mal(x,0,x)),B); 2153 for(;j--;) x[j/7]+=((i)z[j])<<((8*j)%55); return fix(x);} 2154 c bite(c z,f x){F t;i j=((fix(mal(x,cmp(mal(t,-1,x),x),x))), B),k=5; 2155 for(;j--;) z[j]=x[j/7]>>((8*j)%55); {(sub(t,t,t));} 2156 for(;--k;) z[7*k-1]+=x[k]<<(8-k); {(sub(x,x,x));} RZ;} 2157 i lift(e z,f x,i t){F y;return mal(X,1,x),mal(Z,1,I),t|| 2158 -1==leg(add(y,x,mul(y,x,squ(y,x))));} 2159 i drop(f x,e z){return inv(Z)&&mul(x,X,Z)&&(sub(X,X,X)&&sub(Z,Z,Z));} 2160 _ let(e z,e y){i j=2;for(;j--;)mal(z[j],1,y[j]);} 2161 _ smv(v z,v y){i j=4;for(;j--;)add(((e)z)[j],((e)z)[j],((e)y)[j]);} 2162 v mav(v z,i a){i j=4;for(;j--;)mal(((e)z)[j],a,((e)z)[j]);RZ;} 2163 _ due(e z){F a,b,c,d; 2164 mul(X,squ(a,add(a,X,Z)),mal(d,2,squ(b,sub(b,X,Z)))); 2165 mul(Z,add(c,a,b),sub(d,a,b));} 2166 _ ade(e z,e u,f w){F a,b,c,d;f ad=a,bc=b; 2167 mul(ad,add(a,u[0],u[1]),sub(d,X,Z)), 2168 mul(bc,sub(b,u[0],u[1]),add(c,X,Z)); 2169 squ(X,add(X,ad,bc)),mul(Z,w,squ(Z,sub(Z,ad,bc)));} 2170 _ duv(v a,e z){ade(a[1],a[0],z[0]);due(a[0]);} 2171 v adv(v z,i b){V t; 2172 let(t[0],z[1]),let(t[1],z[0]);smv(mav(z,!b),mav(t,b));mav(t,0);RZ;} 2173 e mule(e z,c d){V a;E o={{1}};i 2174 b=0,c,n=(let(a[0],o),let(a[1],z),8*B); 2175 for(;n--;) c=1&d[n/8]>>n%8,duv(adv(a,c!=b),z),b=c; 2176 let(z,*adv(a,b)); (due(*mav(a,0))); RZ;} 2177 C G={23,1}; 2178 i mulch(c db,c d,c b){F x;E p; return 2179 lift(p,feed(x,b),(db==d||b==G))&&drop(x,mule(p,d))&&bite(db,x);} 2180 2182 This part of the sample code represents points and scalar 2183 multipliers as character strings of 34 bytes. 2185 Note: Types c and C are used for these 34-byte encodings. 2186 Following the previous pattern for f and F, type C is an array, 2187 used for allocating new memory (on the stack) for these arrays. 2189 The conversion functions feed and bite convert 2190 between a 34-byte string and a field value (recall, stored as five 2191 element array, base 2^55). 2193 Internet-Draft 2020-10-02 2195 The conversion functions lift and drop convert between field 2196 elements and the projective line point, so that x <-> (X:1). The 2197 function lift can also test if x is the x-coordinate of the a point 2198 (x,y) on the curve 2y^2=x^3+x. 2200 Note: Projective line points are stored in defined types e and E 2201 (for extended field element). 2203 Note: The Montgomery ladder can implemented by working with a 2204 pair of extended field elements. 2206 The raw scalar multiplication function "mule" takes a projective 2207 point (with defined type e), multiplies it by a scalar (encoded as 2208 byte string with defined type c), and then replaces the projective 2209 point by the multiple. 2211 The main loop of mule is written a double-and-always-add, acting on 2212 pair projective line points. Basically it acts on the x-coordinates 2213 of the points nB and (n+1)B, for n changing. 2215 Because the Montogomery ladder algorithm is being used, the "adv" 2216 called by mule function does nothing but swap the two values. With 2217 an appropriate isogeny, this can be viewed as addition operation. 2219 The function "duv" called by mule, does the hard work of finding 2220 (2n)B and (2n+1)B from nB and (n+1)B. It does so, using doubling in 2221 the function "due" and differntial addition, in the function "ade". 2223 The functions "due" and "ade" are non-trivial, and use field 2224 arithmetic. They are fairly specific to 2y^2=x^3+x. They try to 2225 avoid repeated application of additive field operations. 2227 The function smv, mav and let are more utilitarian. They are used 2228 for initialization, swapping, and zeroization. 2230 C.1.3. Bernstein's 2-dimensional Montgomery ladder 2232 Bernstein's 2-dimensional ladder is a variant of Montgomery's ladder 2233 that computes aP+bQ, for any two points P and Q, more quickly than 2234 computing aP and bQ separately. 2236 Curve 2y^2=x^3+x has an efficient endomorphism, which allows a point 2237 Q = [i+1]P to compute efficiently. Gallant, Lambert and Vanstone 2238 introduced a method (now called the GLV method), to compute dP more 2239 efficiently, given such an efficient endomorphism. They write d = a 2240 + eb where e is the integer multiplier corresponding to the 2241 efficient endomorphism, and a and b are integers smaller than d. 2242 (For example, 17 bytes each instead of 34 bytes.) 2244 Internet-Draft 2020-10-02 2246 The GLV method can be combined with Bernstein's 2D ladder algorithm 2247 to be applied to compute dP = (a+be)P = aP + beP = aP + bQ, where 2248 e=i+1. 2250 This algorithm is not implemented by any pseudocode in the version 2251 the draft. (Previous versions had it.) 2253 See [B1] for further explanation and example pseudocode. 2255 I have estimate a ~10% speedup of this method compared to the plain 2256 Montgomery ladder. However, the code is more complicated, and 2257 potentially more vulnerable to implementation-based attacks. 2259 C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong) 2261 To be completed. 2263 It is also possible to convert to Edwards coordinates, and then use 2264 the Hisil--Carter--Dawson--Wong (HCDW) elliptic curve arithmetic. 2266 The HCDW arithmetic can be combined with the GLV techniques to 2267 obtain a scalar multiplication potentially more efficient than 2268 Bernstein's 2-dimensional Montgomery. The downside is that it may 2269 require key-dependent array look-ups, which can be a security risk. 2271 I have implemented this, finding ~20% speed-up over my 2272 implementation of the Montgomery ladder. However, this speed-up may 2273 disappear upon further optimization (e.g. assembly), or further 2274 security hardening (safe table lookup code). 2276 C.2. Sample code for test vectors 2278 The following sample code describes the contents of a file "tv.c", 2279 with the purpose of generating the test vectors in Appendix B. 2281 Internet-Draft 2020-10-02 2283 2284 //gcc tv.c -o tv -O3 -flto -finline-limit=200;strip tv;time ./tv 2285 #include 2286 #include "pseudo.c" 2287 #define M mulch 2288 void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");} 2289 int main (void){i n=1e5,j=n/2,wait=/*your mileage may vary*/7000; 2290 C x="TEST 2y^2=x^3+x/GF(8^91+5)",y="yet another test",z; 2291 M(z,x,G); hx(x),hx(G),hx(z); 2292 fprintf(stderr,"%30s(wait=~%ds, ymmv)","",j/wait); 2293 for(;j--;)if(fprintf(stderr,"\r%7d\r",j),!(M(z,x,z)&&M(x,z,G))) 2294 j=0*printf("Mulch fail rate ~%f :(\n",(2*j)/n);//else//debug 2295 fprintf(stderr,"\r%30s \r",""),hx(x),hx(z); 2296 M(y,y,G);M(y,y,y); 2297 for(M(z,G,G),j=900;j--;)M(z,x,z);for(j=900;j--;)M(z,y,z);hx(z); 2298 for(M(z,G,G),j=900;j--;)M(z,y,z);for(j=900;j--;)M(z,x,z);hx(z);} 2299 2301 It includes the previously defined file pseudo.c, and the standard 2302 header file stdio.h. 2304 The first for-loop in main aims to terminate in the event of the bug 2305 such that the output of mulch is an invalid value, not on the curve 2306 2y^2=x^3+x. 2308 Of the 100,000 scalar multiplication in this for-loop, the aim is 2309 that 50,000 include public-key validation. All 100,000 include a 2310 field-inversion, to encode points uniquely as 34-byte strings. 2312 The second and three for-loops aims to test the compatibilty with 2313 Diffie--Hellman, by showing the 900 applications of scalar 2314 multipliers x and y are the same, whether x or y is applied first. 2316 The 1st line comment suggest possible compilation commands, with 2317 some optimization options. The run-time depends on the system, and 2318 should be slower on older and weaker systems. 2320 Anecdotally, on a ~3 year-old personal computer, it runs in time as 2321 low as 5.7 seconds, but these were under totally uncontrolled 2322 conditions (with no objective benchmarking). (Experience has shown 2323 that on a ~10 year-old personal computer, it could be ~5 times 2324 slower.) 2326 C.3. Sample code for a command-line demo of Diffie--Hellman 2328 The next sample code is intended to demonstrate ephemeral (elliptic 2329 curve) Diffie--Hellman: (EC)DHE in TLS terminology. 2331 Internet-Draft 2020-10-02 2333 The code can be considered as a file "dhe.c". It has both C and bash 2334 code, intermixed within comments and strings. It is bilingual: a 2335 valid bash script and valid C source code. The file "dhe.c" can be 2336 made executable (using chmod, for example), so it can be run as a 2337 bash script. 2339 2340 #include "pseudo.c" /* dhe.c (also a bash script) 2341 : demos ephemeral DH, also creates, clobbers files dhba dha dhb 2342 : -- Dan Brown, BlackBerry, '20 */ 2343 #include 2344 _ get(c p,_*f){f&&fread ((_*)p,B,1,f)||mulch(p,p,G);} 2345 _ put(c p,_*f){f&&fwrite((_*)p,B,1,f)&&fflush(f); bite(p,O);} 2346 int main (_){C p="not validated",s="/dev/urandom" "\0"__TIME__; 2347 get(s,fopen((_*)s,"r")), mulch(p,s,G), put(p,stdout); 2348 get(p,stdin), mulch(s,s,p), put(s,stderr);} /*' 2349 [ dhe.c -nt dhe ]&&gcc -O2 dhe.c -o dhe&&strip dhe&&echo "$(/dev/null || ([ ! -p dhba ] && :> dhba) 2351 ./dhe dha | ./dhe >dhba 2>dhb & 2352 sha256sum dha & sha256sum dhb # these should be equal 2353 (for f in dh{a,b,ba} ; do [ -f $f ] && \rm -f $f; done)# '*/ 2354 2356 Run as a bash script, file "dhe.c" will check if it needs compile 2357 its own C code, into an executable named "dhe". Then the bash 2358 script file "dhe.c" runs the compiled executable "dhe" twice. One 2359 run is Alice's, and the other Bob's. 2361 Each run of "dhe" generates an ephemeral secret key, by reading the 2362 file "/dev/urandom". Each run then writes to "stdout", the 2363 ephemeral public key. Each run then reads the peer's ephemeral 2364 public key from "stdin". Each run then writes to "stderr" the 2365 shared Diffie--Hellman secret. (Public-key validation is mostly 2366 unnecessary, because the ephemeral is only used once, so it is 2367 skipped by using the same pointer location for the ephemeral secret 2368 and final shared secret.) 2370 The script "dhe.c" connects the input and output of these two using 2371 pipes. One pipe is generated by the shell command line using the 2372 shell operator "|". The other pipe is a pipe name "dhab", created 2373 with "mkfifo". The script captures the shared secrets from each run 2374 by redirecting "stderr" (as file descriptor 2), to files "dha" and 2375 "dhb", which will be made named pipes if possible. 2377 Internet-Draft 2020-10-02 2379 The scripts fees each shared secret keys into SHA-256. This 2380 demonstrates their equality. It also illusrates a typical way to 2381 use Diffie--Hellman, by deriving symmetric keys using a hash 2382 function. In multi-curve ECC, hashing a concatenation of such 2383 shared secrets (one for each curve used), could be done instead. 2385 C.4. Sample code for public-key validation and curve basics 2387 The next sample code demonstrates the public-key validation issues 2388 specific to 2y^2=x^3+x/GF(8^91+5). It also demonstrates the order 2389 of the curve. It also demonstrates complex multiplication by i, and 2390 the fact the 34-byte representation of points is unaffected by 2391 multiplication by i. 2393 The code can be considered to describe a file "pkv.c". It uses the 2394 "mulch" function by including "pseudo.c". 2396 2397 #include 2398 #include "pseudo.c" 2399 #define M mulch // works with +/- x, so P ~ -P ~ iP ~ -iP 2400 void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");} 2401 int main (void){i j;// sanity check, PKV, twist insecurity demo 2402 C y="TEST 2y^2=x^3+x/GF(8^91+5)",z="zzzzzzzzzzzzzzzzzzzz", 2403 q = "\xa9\x38\x04\xb8\xa7\xb8\x32\xb9\x69\x85\x41\xe9\x2a" 2404 "\xd1\xce\x4a\x7a\x1c\xc7\x71\x1c\xc7\x71\x1c\xc7\x71\x1c" 2405 "\xc7\x71\x1c\xc7\x71\x1c\x07", // q=order(G) 2406 i = "\x36\x5a\xa5\x56\xd6\x4f\xb9\xc4\xd7\x48\x74\x76\xa0" 2407 "\xc4\xcb\x4e\xa5\x18\xaf\xf6\x8f\x74\x48\x4e\xce\x1e\x64" 2408 "\x63\xfc\x0a\x26\x0c\x1b\x04", // i^2=-1 mod q 2409 w5= "\xb4\x69\xf6\x72\x2a\xd0\x58\xc8\x40\xe5\xb6\x7a\xfc" 2410 "\x3b\xc4\xca\xeb\x65\x66\x66\x66\x66\x66\x66\x66\x66\x66" 2411 "\x66\x66\x66\x66\x66\x66\x66"; // w5=(2p+2-72q)/5 2412 for(j=0;j<=3;j++)M(z,(C){j},G),hx(z); // {0,1,2,3}G, but reject 0G 2413 M(z,q,G),hx(z); // reject qG; but qG=O, under hood: 2414 {F x;E p;lift(p,feed(x,G),1);mule(p,q);hx(bite(z,p[1]));} 2415 for(j=0;j<0*25;j++){F x;E p;lift(p,feed(x,(C){j,1}),1);mule(p,q); 2416 printf("%3d ",j),hx(bite(z,p[1]));}// see j=23 for choice of G 2417 for(j=3;j--;)q[0]-=1,M(z,q,G),hx(z);// (q-{1,2,3})G ~ {1,2,3}G 2418 M(z,i,G),hx(z); i[0]+=1,M(z,i,G),M(z,i,z),hx(z);// iG~G,(i+1)^2G~2G 2419 M(w5,w5,(C){5}),hx(w5);// twist, ord(w5)=5, M(z,z,p) skipped PKV(p) 2420 M(G,(C){1},w5),hx(G);// reject w5 (G unch.); but w5 leaks z mod 5: 2421 for(j=10;j--;)M(z,y,G),z[0]+=j,M(z,z,w5),hx(z);} 2422 2424 Internet-Draft 2020-10-02 2426 The sample code demonstrates the need for public-key validation 2427 even when using the Montgomery ladder for scalar multiplication. It 2428 does this by finding points of low order on the twist of the curve. 2429 This invavlid points can leak bits of the secret multiplier. This 2430 is because the curve 2y^2=x^3+x/GF(8^91+5) is not fully "twist 2431 secure". (Its twist security is typical of that of a random curve.) 2433 C.5. Elligator i 2435 To be deleted (or completed). 2437 This pseudocode would show how to implement to the Elligator i map 2438 from byte strings to points. 2440 This is INCOMPATIBLE with previous samples of code above, and is 2441 taken from an earlier version of experimental code. 2443 Pseudocode (to be verified): 2445 2446 typedef f xy[2] ; 2447 #define X p[0] 2448 #define Y p[1] 2449 lift(xy p, f r) { 2450 f t ; i b ; 2451 fix(r); 2452 squ(t,r); // r^2 2453 mul(t,I,t); // ir^2 2454 sub(t,(f){1},t); // 1-ir^2 2455 inv(t,t); // 1/(1-ir^2) 2456 mal(t,3,t); // 3/(1-ir^2) 2457 mul(t,I,t); // 3i/(1-ir^2) 2458 sub(X,I,t); // i-3i/(1-ir^2) 2459 b = get_y(t,X); 2460 mal(t,1-b,I); // (1-b)i 2461 add(X,X,t); // EITHER x OR x + i 2462 get_y(Y,X); 2463 mal(Y,2*b-1,Y); // (-1)^(1-b)"" 2464 fix(X); fix(Y); 2465 } 2467 Internet-Draft 2020-10-02 2469 drop(f r, xy p) 2470 { 2471 f t ; i b,h ; 2472 fix(X); fix(Y); 2473 get_y(t,X); 2474 b=eq(t,Y); 2475 mal(t,1-b,I); 2476 sub(t,X,t); // EITHER x or x-i 2477 sub(t,I,t); // i-x 2478 inv(t,t); // 1/(i-x) 2479 mal(t,3,t); // 3/(i-x) 2480 add(t,I,t); // i+ 3/(i-x) 2481 mal(t,-1,t); // -i-3/(i-x)) = (1-3i/(i-x))/i 2482 b = root(r,t) ; 2483 fix(r); 2484 h = (r[4]<(1LL<<52)) ; 2485 mal(r,2*h-1,r); 2486 fix(r); 2487 } 2489 elligator(xy p,c b) {f r; feed(r,b); lift(p,r);} 2491 crocodile(c b,xy p) {f r; drop(r,p); bite(b,r);} 2492 2494 Appendix D. Minimizing trapdoors and backdoors 2496 The main advantage of curve 2y^2=x^3+x/GF(8^91+5) over almost all 2497 other elliptic curves is its Kolmogorov complexity is almost minimal 2498 among curves of sufficient resistance to the Pollard rho attack on 2499 the discrete logarithm problem. 2501 See [AB] and [B1] for some details. 2503 D.1. Decimal exponential complexity 2505 The curve can be described with 21 characters: 2507 2 y ^ 2 = x ^ 3 + x / G F ( 8 ^ 9 1 + 5 ) 2508 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2510 Those familiar with ECC will recognize that these 21 characters 2511 suffice to specify the curve up to the level of detail needed to 2512 describe the cost of the Pollard rho algorithm, as well as many 2513 other security properties (especially resistance to other known 2514 attacks on the discrete logarithm problem, such as Pohlig--Hellman 2515 and Menezes--Okamoto--Vanstone). 2517 Internet-Draft 2020-10-02 2519 Note: The letters GF mean Galois Field, and are quite traditional 2520 mathematics, and every elliptic curve in cryptographic needs to 2521 use some notation for the finite field. 2523 We may therefore describe the curve's Kolmogorov complexity as 21 2524 characters. 2526 Note: The idea of low Kolmogorov complexity is hard to specify 2527 exactly. Nonetheless, a claim of nearly minimal Kolmogorov 2528 complexity is quite falsifiable. The falsifier need merely 2529 specify several other (secure) elliptic curves using 21 or fewer 2530 characters. (But if the other curves use a different 2531 specificaion language, then a fair comparison should re-specify 2532 2y^2=x^3+x/GF(8^91+5) in this specification language.) 2534 D.1.1. A shorter isomorophic curve 2536 The curve is isomorphic to a curve specifiable in 20 characters: 2538 y^2=x^3-x/GF(8^91+5) 2540 Generally, isomorphic curves have essentially equivalently hard 2541 discrete logarithm problems, so one could argue that curve 2542 2y^2=x^3+x/GF(8^91+5) could be rated as having Kolmogorov complexity 2543 at most 20 characters. 2545 Isomorphic curves, however, may differ slightly in security, due to 2546 issues of efficiency, and implementability. The 21-character 2547 specification uses an equation in Montgomery form, which creates an 2548 incentive to use the Montgomery ladder algorithm, which is both safe 2549 and efficient [Bernstein?]. 2551 D.1.2. Other short curves 2553 Allowing for non-prime fields, then the binary-field curve known as 2554 sect283k1 has a 22-character description: 2556 y^2+xy=x^3+1/GF(2^283) 2558 This curve was formerly one of the fifteen curves recommended by 2559 NIST. Today, a binary curve is curve is considered risky, due to 2560 advances in elliptic curve discrete logarithm problem over extension 2561 fields, such as recent asymptotic advances on discrete logarithms in 2562 low-characteristic fields [HPST] and [Nagao]. According to [Teske], 2563 some characteristic-two elliptic curves could be equipped with a 2564 secretly embedded backdoor (but sect283k1's short description should 2565 help mitigate that risk). 2567 Internet-Draft 2020-10-02 2569 This has a longer overall specification than curve 2570 2y^2=x^3+x/GF(8^91+5), but the field part is shorter field 2571 specification. Perhaps an isomorphic curve can be found (one with 2572 three terms), so that total length is 21 or fewer characters. 2574 A non-prime field tends to be slower in software. A non-prime field 2575 is therefore perhaps riskier due to some recent research on 2576 attacking non-prime field discrete logarithms and elliptic curves, 2578 To be completed. 2580 D.1.3. Converting DEC characters to bits 2582 The units of characters as measuring Kolmogorov complexity is not 2583 calibrated as bits of information. Doing so formally would be very 2584 difficult, but the following approach might be reasonable. 2586 Set the criteria for the elliptic curve. For example, e.g. prime 2587 field, size, resistance (of say 2^128 bit operations) to known 2588 attacks on the discrete logarithm problem (Pollard rho, MOV, etc.). 2589 Then list all the possible ECC curve specification with Kolmogorov 2590 complexity of 21 characters or less. Take the base two logarithm of 2591 this number. This is then an calibrated estimate of the number of 2592 bits needed to specify the curve. It should be viewed as a lower 2593 bound, in case some curves were missed. 2595 To be completed. 2597 D.1.4. Common acceptance of decimal exponential notation 2599 The decimal exponentiation notation used in to measure decimal 2600 exponential complexity is quite commonly accepted, almost standard, 2601 in mathematical computer programming. 2603 For example, as evidence of this commmon acceptance, here is a 2604 slightly edited session of the program "bc" (versions of which are 2605 standardized in POSIX). 2607 Internet-Draft 2020-10-02 2609 2610 $ BC_LINE_LENGTH=71 bc 2611 bc 1.06.95 2612 Copyright ... Free Software Foundation, Inc. 2613 ... 2614 p=8^91+5 ; p; obase=16; p 2616 151771007205135083665582961470587414581438034300948400097797844510851\ 2617 89728165691397 2619 200000000000000000000000000000000000000000000000000000000000000000005 2620 define v(b,e,m){ 2621 auto a; for(a=1;e>0;e/=2){ 2622 if(e%2==1) {a=(a*b)%m;} 2623 b=(b^2)%m;} 2624 return(a);} 2625 v(571,p-1,p) 2626 1 2627 x = (1*256) + (23*1) 2628 v(2*(x^3+x),(p-1)/2,p) 2629 1 2630 y = (((p+1)/2)*v(2*(x^3+x),(p+3)/8,p))%p 2631 (2*y^2)%p == (x^3+x)%p 2632 1 2633 (2*y^2 -(x^3+x))%(8^91+5) 2634 0 2635 2637 Note: Input lines have been indented at least two extra spaces, 2638 and can be pasted into a "bc" session. (Pasting the output lines 2639 causes a few spurious results.) 2641 The sample code demonstrates that "bc" directly accepts the 2642 notations "8^91+5" and "x^3+x": parts parts of the curve 2643 specification "2y^2=x^3+x/GF(8^91+5)", which goes to show how much 2644 of the notation used in this specifcation is commonly accepted. 2646 Internet-Draft 2020-10-02 2648 Note: Defined function "v" implements modular exponentiation, 2649 with returning v(b,e,m) returning (b^e mod m). Then, "v" is used 2650 to show that p=8^91+5 is a Fermat pseudoprime to base 571 2651 (evidence that p is prime). The value x defined is the 2652 x-coordinate of the recommend base point G. Then, another 2653 computation with "v" shows that 2(x^3+x) has Legendre symbol 1, 2654 which implies (assuming p is prime) that there exists y with 2655 2y^2=x^3+x, namely y = (1/2)sqrt(2(x^3+x)). The value of y is 2656 computed, again using "v" (but also a little luck). The curve 2657 equation is then tested twice with two different expressions, 2658 somewhat similar to the mathematical curve specification 2659 2y^2=x^3+x/GF(8^91+5). 2661 D.2. General benefits of low Kolmogorov complexity to ECC 2663 The benefit of low Kolmogorov complexity to cryptography is well 2664 known, but very informal. The general benefit is believed to a form 2665 of subversion-resistance, where the attacker is the designer of the 2666 cryptography. 2668 Often, fixed numbers in cryptographic algorithms with low Kolmogorov 2669 complexity are called "nothing-up-my-sleeve" numbers. (Bernstein et 2670 al. uses terms in "rigid", for a very similar idea, but with an 2671 emphasis on efficiency instead of compressibility.) 2673 For elliptic curves, the informal benefit may be stated as the 2674 following gains. 2676 - Low Kolmogorov complexity defends against insertion of a keyed 2677 trapdoor, meaning the curve can broken using a secret trapdoor, 2678 by an algorithm (eventually discovered by the public at large). 2679 For example, the Dual EC DRBG is known to capable of having such 2680 a trapdoor. Such a trapdoor would information-theoretically 2681 imply an amount of information, comparable the size of the 2682 secret, to be embedded in the curve specification. If the 2683 calibrated estimate for the number of bits is sufficiently 2684 accurate, then such a key cannot be large. 2686 Internet-Draft 2020-10-02 2688 - Low Kolmogorov complexity defends against a secret attack 2689 (presumably difficult to discover), which affects a subset of 2690 curves such that (a) whether or not a specific curve is affected 2691 is a somewhat pseudorandom function of its natural 2692 specification, and (b) the probably of a curve being affected 2693 (when drawn uniformly from some sensible of curve 2694 specification), is low. For an example of real-world attacks 2695 meeting the conditions (a) and (b) consider the MOV attack. 2696 Exhaustively finding curve meeting these two conditions is 2697 likely to prevent low Kolmogorov complexity, essentially by the 2698 low probability of the attack, and the independence of attack's 2699 success from the natural Kolmogorov complexity. 2701 - Even more hypothetically, there may yet exist undisclosed 2702 classes of weak curves, or attacks, for which 2703 2y^2=x^3+x/GF(8^91+5) is lucky enough to avoid. This would be a 2704 fluke. A real-world example is prime-order, or low cofactor 2705 curves, which are are among all curves, but which better resist 2706 the Pohlig--Hellman attack. 2708 Of course, low Kolmogorov complexity is not a panacea. The worst 2709 failure would be attacks that increase in strength as Kolmogorov 2710 complexity gets lower. Two examples illustrate this strongly. 2712 D.2.1. Precedents of low Komogorov complexity in ECC 2714 To be completed. 2716 Basically, the curves sect283k1, Curve25519, and Brainpool curves 2717 can be argued as mitigating the risk of manipulated designed-in 2718 weakness, by virtue of the low Kolmogorov complexity. 2720 To be completed. 2722 D.3. Risks of low Kolmogorov complexity 2724 Low Kolmogorov complexity is not a panacea for cryptography. 2726 Indeed, it may even add its own risks, if some weakness are 2727 positively correleated with low Kolmogorov complexity, making some 2728 attacks stronger. 2730 In other words, choosing low Kolmogorov complexity might just 2731 accidentally weaken the cryptography. Or worse, if attackers find 2732 and hold secret such weaknesses, then attackers can intentionally 2733 include the weakness, by using low Kolmogorov serving as a cover, 2734 thereby subverting the algorithm. 2736 Internet-Draft 2020-10-02 2738 Evidence of positive correlations between curve weakness and low 2739 Kolmogorov complexity might help assess this risk. 2741 In general cryptography (not ECC), the shortest cryptography 2742 algorithms may be the least secure, such as the identity function as 2743 an encryption function. 2745 Within ECC, however, some minimum threshold of complexity must be 2746 met for interoperability. But curve size is positively correlated 2747 with security (via Pollard rho) and negatively correlated with 2748 complexity (at least for fields, larger fields needs larger 2749 specifications). Therefore, there is a somewhat negative correlation 2750 between Pollard rho security of ECC and Kolmogorov complexity of the 2751 field size. 2753 Beyond field size in ECC, there is some negative correlations in the 2754 curve equation. 2756 Singular cubics have equations that look very simlar to those 2757 commonly used elliptic curves. For smooth singular curves 2758 (irreducible cubics) a group can be defined, using more or less the 2759 same arithmetic as for a elliptic curve. For example 2760 y^2=x^3/GF(8^91+5) is such a cubic. The resulting group has an easy 2761 discrete logarithm problem, because it can be mapped to the field. 2763 Supersingular elliptic curves can also be specified with low 2764 Kolmogorov complexity, and these are vulnerable to MOV attack, 2765 another negative correlation. 2767 Combining the above, a low Kolmogorov complexity elliptic curve, 2768 y^2=x^3+1/GF(2^127-1), with 21-character decimal exponential 2769 complexity, suffers from three well-known attacks: 2771 1. The MOV (Menezes--Okamato--Vanstone) attack. 2773 2. The Pohlig--Hellman attack (since it has 2^127 points). 2775 3. The Pollard rho attack (taking 2^63 steps, instead of the 2^126 2776 of exhaustive). 2778 Had all three attacks been unknown, an implementer seeking low 2779 Kolmogorov complexity, might have been drawn to curve 2780 y^2=x^3+1/GF(2^127-1). (This document's curve 2y^2=x^3+x/GF(8^91+5) 2781 uses 1 more character and is much slower since, the field size has 2782 twice as many bits.) 2784 Internet-Draft 2020-10-02 2786 Had an attacker known one of three attacks, the attacker could found 2787 y^2=x^3+1/GF(2^127-1), proposed it, touted its low Kolmogorov 2788 complexity, and maybe successfully subverted the system security. 2790 Note: The curve y^2=x^3+1/GF(2^127-1) not only has low decimal 2791 exponential complexity, it also has high efficiency: fast field 2792 arithmetic and fairly fast curve arithmetic (for its bit lengths). 2793 So high efficiency can also be positively correlated with 2794 weakness. 2796 It can be argued, that pseudorandomized curves, such as NIST P-256 2797 and Brainpool curves, are an effective way mitigate such attacks 2798 positively correlated with low complexity. More precisely, strong 2799 pseudorandomization somewhat mitigates the attacker's subversion 2800 ability, by reducing an easy look up of the weakest curve to an 2801 exhaustive search by trial and error, intuitively implying a 2802 probable high Kolmogorov complexity (proportional the rarity of the 2803 weakness). 2805 It can be further argued that all major known weak classes of curves 2806 in ECC are positively correlated with low complexity, in that the 2807 weakest curves have very low complexity. No major known weak 2808 classes of curves imply an increase in Kolmogorov complexity, except 2809 perhaps Teske's class of curves. 2811 In defense of low complexity, it can be argued that the strongest 2812 way to resist secret attacks is to find the attacks. 2814 For these reasons, this specification suggests to use curve 2815 2y^2=x^3+x/GF(8^91+5) in multi-curve elliptic curve cryptography, 2816 in combination with at least one pseudo-randomized curve. 2818 To be completed. 2820 D.4. Alternative measures of Kolmogorov complexity 2822 Decimal exponential complexity arguably favors decimal and the 2823 exponentiation operators, rather than the arbitrary notion of 2824 compressibility. 2826 Allowing more arbitrary compression schemes introduces another 2827 possible level of complexity, the compression scheme itself, 2828 somewhat defeating the purpose of nothing-up-sleeve number. An 2829 attacker might be able to choose a compression scheme among 2830 many that somehow favors a weak curve. 2832 Internet-Draft 2020-10-02 2834 Despite this potential extra complexity, one can still seek a 2835 measure more objective than decimal complexity. To this end, in 2836 [B3], I adapted the Godel's approach for general recursive 2837 functions, which breaks down all computation into succession, 2838 composition, repetition, and minimization. 2840 The adaption is a miniature programming language called Roll to 2841 describe number-related functions, including constant functions. A 2842 Roll program for the constant function that always return 8^91+5 is: 2844 2845 8^91+5 subs 8^91+1 in +4 2846 8^91+1 subs 2^273 in +1 2847 2^273 subs 273 in 2^ 2848 273 subs 17 in *16+1 2849 17 subs 1 in *16+1 2850 *16+1 roll +16 up 1 2851 +16 subs +8 in +8 2852 +8 subs +4 in +4 2853 +4 subs +2 in +2 2854 2^ roll *2 up 1 2855 1 subs in +2 2856 *2 roll +2 up 0 2857 +2 subs +1 in +1 2858 0 subs in +1 2859 2861 A Roll program has complexity measured in its length in number of 2862 words (space-separated substrings). This program has 68 words. 2863 Constants (e.g. field sizes) can be compared using roll complexity, 2864 the shortest known length of their implementations in Roll. 2866 In [B3], several other ECC field sizes are given programs. The only 2867 prime field size implemented with 68 or fewer words was 2^521-1. 2868 (The non-prime field size (2^127-1)^2 has 58-word "roll" program.) 2869 Further programming effort might produce shorter programs. 2871 Note: Roll programs have a syntax implying some redundancy. 2872 Further work may yet establish a reasonable normalization for roll 2873 programs, resulting in a more calibrated complexity measure in 2874 bits, making the units closed to a universal kind of Kolmogorov 2875 complexity. 2877 Appendix E. Primality proofs and certificates 2879 Recent work of Albrecht and others [AMPS] has shown the combination 2880 of an adversarially chosen prime, and users using improper 2881 probabilistic primality tests can make user vulnerable to an attack. 2883 Internet-Draft 2020-10-02 2885 The adversarial primes in their attack are typically the result of 2886 an exhaustive search. These bad primes would therefore typically 2887 contain an amount of information corresponding to the length of 2888 their search, putting a predictable lower bound on their Kolmogorov 2889 complexity. 2891 The two primes involved for 2y^2=x^3+x/GF(8^91+5) should perhaps 2892 already resist [AMPS] because of the following compact 2893 representation of these primes: 2895 p = 8^91+5 2896 q = #(2y^2=x^3+x/GF(8^91+5))/72 2898 This attack [AMPS] can also be resisted by: 2900 - properly implementing probabilistic primality test, or 2901 - implementing provable primality tests. 2903 Provable primality tests can be very slow, but can be separated into 2904 two steps: 2906 -- a slow certificate generation, and 2908 -- a fast certificate verification. 2910 The certificate is a set of data, representing an intermediate step 2911 in the provable primality test, after which the completion of the 2912 test is quite efficient. 2914 Pratt primality certificate generation for any prime p, involves 2915 factorizing p-1, which can be very slow, and then recursively 2916 generating a Pratt primality certificate for each prime factor of 2917 p-1. Essentially, each prime has a unique Pratt primality 2918 certificate. 2920 Pratt primality certificate verification of (p-1), involves search 2921 for g such that 1 = (g^(p-1) mod p) and 1 < (g^((p-1)/q) mod p) for 2922 each q dividing p-1, and then recursively verifying each Pratt 2923 primality certificate for each prime factor q of p-1. 2925 In this document, we specify a Pratt primality certificate as a 2926 sequence of (candidate) primes each being 1 plus a product of 2927 previous primes in the list, with certificate stating this product. 2929 Although Pratt primality certificate verification is quite 2930 efficient, an ECC implementation can opt to trust 8^91+5 by virtue 2931 of verifying the certificate once, perhaps before deployment or 2932 compile time. 2934 Internet-Draft 2020-10-02 2936 E.1. Pratt certificate for the field size 8^91+5 2938 Define 52 positive integers, a,b,c,...,z,A,...,Z as follows: 2940 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 2941 j=1+aaac k=1+abd l=1+aaf m=1+abf n=1+aacc o=1+abg p=1+al q=1+aaag 2942 r=1+abcc s=1+abbbb t=1+aak u=1+abbbc v=1+ack w=1+aas x=1+aabbi 2943 y=1+aco z=1+abu A=1+at B=1+aaaadh C=1+acu D=1+aaav E=1+aeff F=1+aA 2944 G=1+aB H=1+aD I=1+acx J=1+aaacej K=1+abqr L=1+aabJ M=1+aaaaaabdt 2945 N=1+abdpw O=1+aaaabmC P=1+aabeK Q=1+abcfgE R=1+abP S=1+aaaaaaabcM 2946 T=1+aIO U=1+aaaaaduGS V=1+aaaabbnuHT W=1+abffLNQR X=1+afFW 2947 Y=1+aaaaauX Z=1+aabzUVY. 2949 Note: variable concatenation is used to indicate multiplication. 2950 For example, f = 1+aab = 1+2*2*(1+2) = 13. 2952 Note: One must verify that Z=8^91+5. 2954 Note: The Pratt primality certificate involves finding a generator 2955 g for each the prime (after the initial prime). It is possible to 2956 list these in the certificate, which can speed up verification by 2957 a small factor. 2959 (2,b), (2,c), (3,d), (2,e), (2,f), (3,g), (2,h), (5,i), (6,j), 2960 (3,k), (2,l), (3,m), (2,n), (5,o), (2,p), (3,q), (6,r), (2,s), 2961 (2,t), (6,u), (7,v), (2,w), (2,x), (14,y),(3,z), (5,A), (3,B), 2962 (7,C), (3,D), (7,E), (5,F), (2,G), (2,H), (2,I), (3,J), (2,K), 2963 (2,L),(10,M), (5,N), (10,O),(2,P), (10,Q),(6,R), (7,S), (5,T), 2964 (3,U), (5,V), (2,W), (2,X), (3,Y), (7,Z). 2966 Note: The decimal values for a,b,c,...,Y are given by: a=2, b=3, 2967 c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=41, k=43, l=53, m=79, 2968 n=101, o=103, p=107, q=137, r=151, s=163, t=173, u=271, v=431, 2969 w=653, x=829, y=1031, z=1627, A=2063, B=2129, C=2711, D=3449, 2970 E=3719, F=4127, G=4259, H=6899, I=8291, J=18041, K=124123, 2971 L=216493, M=232513, N=2934583, O=10280113, P=16384237, Q=24656971, 2972 R=98305423, S=446424961, T=170464833767, U=115417966565804897, 2973 V=4635260015873357770993, W=1561512307516024940642967698779, 2974 X=167553393621084508180871720014384259, 2975 Y=1453023029482044854944519555964740294049. 2977 E.2. Pratt certificate for subgroup order 2979 Define 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new 2980 values: 2982 Internet-Draft 2020-10-02 2984 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 2985 j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b 2986 r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e 2987 z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck 2988 G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG 2989 O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ 2990 V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Z=1+ab3oHOT !=1+a3SUX @=1+abNY! 2991 #=1+a4kzF@ $=1+a3QZ# 2993 Note: numeral after variable names represent powers. For example, 2994 f = 1 + a2b = 1 + 2^2 * 3 = 13. 2996 The last variable, $, is the order of the base point, and the order 2997 of the curve is 72$. 2999 Note: Punctuation used for variable names !,@,#,$, would not scale 3000 for larger primes. For larger primes, a similar format might work 3001 by using a prefix-free set of multi-letter variable names. 3002 E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze: 3004 Acknowledgments 3006 Thanks to John Goyo and various other BlackBerry employees for past 3007 technical review, and to Gaelle Martin-Cocher and Takashi Suzuki for 3008 encouraging work on I-D. Thanks to David Jacobson for sending Pratt 3009 primality certificates. 3011 Author's Address 3013 Dan Brown 3014 BlackBerry 3015 4701 Tahoe Blvd., 5th Floor 3016 Mississauga, ON 3017 Canada 3018 danibrown@blackberry.com