idnits 2.17.1 draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-07.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 383 has weird spacing: '... severe attac...' == Line 2250 has weird spacing: '...ries of resea...' == Line 3241 has weird spacing: '...1+5) in multi...' == Line 3281 has weird spacing: '... 1 subs in +2...' == Line 3284 has weird spacing: '... 0 subs in +...' -- The document date (2021-04-01) is 1120 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: '34' on line 442 -- Looks like a reference, but probably isn't: '1' on line 2550 -- Looks like a reference, but probably isn't: '2' on line 2550 -- Looks like a reference, but probably isn't: '0' on line 2550 -- Looks like a reference, but probably isn't: '3' on line 2550 -- Looks like a reference, but probably isn't: '4' on line 2550 Summary: 0 errors (**), 0 flaws (~~), 6 warnings (==), 9 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-10-03 2021-04-01 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 2021-04-01 52 Contents 54 1. Introduction 55 2. Requirements Language (RFC 2119) 56 3. Use ONLY in multi-curve ECC 57 4. Representations 58 4.1 Representation points in 34 bytes (compression) 59 4.1.1. Point encoding process 60 4.1.1.1. Summary 61 4.1.1.2. Details 62 4.1.2. Point decoding process 63 4.1.2.1. Summary 64 4.1.2.2. Detail 65 4.2. OPTIONAL: uncompressed point representation 66 4.3. OPTIONAL: Representation of scalar multipliers 67 4.4. OPTIONAL: Representing strings as points using Elligator i 68 5. Point validation 69 5.1. Schedules for point validation 70 5.1.1. Mandatory schedule for point validation 71 5.1.2. Simplified schedule for point validation 72 5.1.3. Minimal schedule for point validation 73 5.2. Point validation process 74 6. IANA considerations 75 Internet-Draft 2021-04-01 77 7. Security considerations 78 7.1. Field choice 79 7.1.1. A special prime 80 7.1.2. Risk of 64-bit integer overflow 81 7.1.3. Excessive size for 128-bit security 82 7.1.4. Non-maximality among six-symbol (DEC) primes 83 7.1.5. Smaller five-symbol field sizes 84 7.1.6. Vulnerability to faulty hardware 85 7.1.7. Other measures of complexity 86 7.2. Curve choice 87 7.2.1. Special curve equation 88 7.2.2. Twist insecurity 89 7.2.3. Point order not near a power of two 90 7.2.4. Vulnerability to Cheon-type attacks 91 7.2.5. Small-subgroup confinement attacks 92 7.3. Encoding choices 93 7.4. General subversion concerns 94 7.5. Risk of low age and eyes (aegis) 95 7.6. Risk of ECC and multi-curve ECC 96 7.6.1. Risk of ECC, overall 97 7.6.1.1. Risk of hidden pre-quantum attacks on ECC 98 7.6.1.2. Risk of quantum computer attacks on forward secrecy 99 7.6.2. Multi-curve ECC might be wasteful 100 8. References 101 8.1. Normative References 102 8.2. Informative References 103 Internet-Draft 2021-04-01 105 Appendix A. Why 2y^2=x^3+x/GF(8^91+5)? 106 A.1. Not for single-curve ECC 107 A.2. Risks of new curve-specific attacks 108 A.2.1. What would be considered a "new curve-specific" attack? 109 A.2.2.1. What would be considered a "new" attack? 110 A.2.2.2. What is, would be, considered a "curve-specific attack"? 111 A.2.2.3. Rarity of published curve-specific attacks 112 A.2.2.4. Correlation of curve-specific efficiency and attacks 113 A.3. Mitigations against new curve-specific attacks 114 A.3.1. Fixed curve mitigations 115 A.3.1.2. Existing fixed-curve mitigations 116 A.3.1.2. Mitigations used by 2y^2=x^3+x/GF(8^91+5) 117 A.3.2. Multi-curve ECC 118 A.3.2.1. Multi-curve ECC is a redundancy strategy 119 A.3.2.2. Whether to use multi-ECC 120 A.3.2.2.1. Benefits of multi-curve ECC 121 A.3.2.2.2. Costs of multi-curve ECC 122 A.3.2.3. Applying multi-curve ECC 123 A.4. General features of curve 2y^2=x^3+x/GF(8^91+5) 124 A.4.1. Field features 125 A.4.3. Equation features 126 A.4.4. Finite curve features 127 A.4.4.1. Curve size and cofactor 128 A.4.4.2. Pollard rho security 129 A.4.4.3. Pohlig--Hellman security 130 A.4.4.2. Menezes--Okamoto--Vanstone security 131 A.4.4.3. Semaev--Araki--Satoh--Smart security 132 A.4.4.4. Edwards and Hessian form 133 A.4.4.5. Bleichenbacher security 134 A.4.4.6. Bernstein's "twist" security 135 A.4.4.7. Cheon security 136 A.4.4.8 Reductionist security assurance for Diffie--Hellman 137 Internet-Draft 2021-04-01 139 Appendix B. Test vectors 140 Appendix C. Sample code (pseudocode) 141 C.1. Scalar multiplication of 34-byte strings 142 C.1.1. Field arithmetic for GF(8^91+5) 143 C.1.2. Montgomery ladder scalar multiplication 144 C.1.3. Bernstein's 2-dimensional Montgomery ladder 145 C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong) 146 C.2. Sample code for test vectors 147 C.3. Sample code for a command-line demo of Diffie--Hellman 148 C.4. Sample code for public-key validation and curve basics 149 Appendix D. Minimizing trapdoors and backdoors 150 D.1. Decimal exponential complexity 151 D.1.1. A shorter isomorphic curve 152 D.1.2. Other short curves 153 D.1.3. Converting DEC characters to bits 154 D.1.4. Common acceptance of decimal exponential notation 155 D.2. General benefits of low Kolmogorov complexity to ECC 156 D.2.1. Precedents of low Kolmogorov complexity in ECC 157 D.3. Risks of low Kolmogorov complexity 158 D.4. Alternative measures of Kolmogorov complexity 159 Appendix E. Primality proofs and certificates 160 E.1. Pratt certificate for the field size 8^91+5 161 E.2. Pratt certificate for subgroup order 163 1. Introduction 165 Elliptic curve cryptography (ECC) is now part of several IETF 166 protocols. 168 Multi-curve ECC can mitigate the risk of new curve-specific attacks 169 on ECC. 171 Note: The risk of new curve-specific attacks is arguably smaller 172 than the risk of quantum attacks breaking all current curves in 173 ECC. The first risk can be addressed by combining ECC with 174 post-quantum cryptography (PQC). Multi-curve ECC would then be 175 added to an ECC+PQC combination. The extra cost of multi-curve 176 over single-curve ECC would less noticeable in an ECC+PQC 177 combination than it would be in an ECC-only implementation. 179 This document aims to contribute to multi-curve ECC by describing 180 how to use the curve 182 2y^2=x^3+x / GF(8^91+5) 184 for elliptic curve Diffie--Hellman (ECDH). 186 Internet-Draft 2021-04-01 188 Appendix A expands on why and when 2y^2=x^3+x/GF(8^91+5) is useful 189 in multi-curve ECC. 191 2. Requirements Language (RFC 2119) 193 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 194 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 195 document are to be interpreted as described in RFC 2119 [BCP14]. 197 3. Use ONLY in multi-curve ECC 199 An implementation using curve 2y^2=x^3+x/GF(8^91+5) in elliptic 200 curve cryptography SHOULD use it multi-curve ECC in a combination 201 with more established, less special, curves, such as Curve25519 or 202 NIST P-256, or even Brainpool curves. 204 The curve 2y^2=x^3+x/GF(8^91+5) belongs to a very special class. 205 Miller in 1985 suggested to exercise prudence around similarly 206 special curves in ECC. This document continues to heed Miller's 207 advice, by considering 2y^2=x^3+x/GF(8^91+5) riskier than less 208 special curves, and hence advising to use it only a second layer of 209 defense in ECC. 211 4. Representations 213 Interoperable communication on most systems involves byte 214 strings. Elliptic curve cryptography needs to use byte strings to 215 work on these systems. Different curves use byte strings in 216 different ways, due to differences in the curves such as the number 217 of points on the curve. 219 This section specifies a default compressed representation of points 220 of 2y^2=x^3+x/GF(8^91+5) as 34-byte strings. The compressed 221 representation SHOULD be used for communication whenever byte string 222 representations are needed. The compressed representation MUST be 223 used when computing an ECDH shared secret. 225 An OPTIONAL uncompressed representation as 70-byte strings is also 226 specified. The uncompressed representation MAY only be used for 227 systems that optimize speed, and are willing to send extra an 35 228 bytes. The uncompressed representation MUST NOT be used to 229 represent an ECDH shared secret. 231 An OPTIONAL representation of scalar multipliers, such as secret 232 keys, as 34-byte strings is also provided. This representation is 233 used for secrets, and is not for public communication. Different 234 components of a single ECC system MAY use this representation to 235 work together. 237 Internet-Draft 2021-04-01 239 An OPTIONAL representation of 34-byte strings as points is also 240 described. This MAY be used in niche applications, such as in 241 deriving a point from the hash of a password, or in steganography, 242 to hide the presence of ECC, by choosing special points such that 243 represented in a way indistinguishable from uniformly random byte 244 strings. This uses the Elligator i method, a variant of the 245 Elligator 2 method. 247 4.1 Representation points in 34 bytes (compression) 249 Elliptic curve cryptography uses points on a curve for its public 250 keys and for it raw shared secret Diffie--Hellman keys. 252 Abstractly, points are mathematical objects. For curve 2y^2=x^3+x, 253 a point is either a pair (x,y), where x and y are elements of 254 mathematical field, or a special point O (whose x and y coordinates 255 may be deemed as infinity). 257 Note: The special point O should never be used as a key, in 258 practice. In theory, point O is needed for the points to form a 259 mathematical group. 261 For curve 2y^2=x^3+x/GF(8^91+5), the coordinates x and y of the 262 point (x,y) are integers modulo 8^91+5, which can be represented as 263 integers in the interval [0,8^91+4]. 265 Note: An implementation will often internally represent the 266 x-coordinate as a ratio [X:Z] of field elements. Each field 267 element has multiple such representations. The ratio [x:1] can 268 viewed as the normalized representation of x. (Infinity can be 269 then represented by [1:0].) 271 This draft specifies an encoding of finite points (x,y) as strings 272 of 34 bytes, as described in the following sections. 274 Note: The 34-byte encoding is not injective. Each point is 275 generally among a group of four points that share the same byte 276 encoding. 278 Note: The 34-byte encoding is not surjective. Approximately half 279 of 34-byte strings do not encode a point (x,y). 281 Note: In elliptic Diffie--Hellman (ECDH), the 34-byte encoding 282 works well, despite being neither injective nor surjective. 284 4.1.1. Point encoding process 285 Internet-Draft 2021-04-01 287 This section takes an abstract point (x,y), and outputs an encoding 288 as a 34-byte string. 290 4.1.1.1. Summary 292 A point (x,y) is encoded by the little-endian byte representation of 293 either x or -x, whichever fits into 34 bytes. 295 4.1.1.2. Details 297 A point (x,y) is encoded into 34 bytes, as follows. 299 First, ensure that x is fully reduced mod p=8^91+5, so that 301 0 <= x < 8^91+5. 303 Note: internal implementations might allow, for efficiency 304 reasons, integer representations of x that are negative, or that 305 are p or larger. Full reduction mod p is needed for interoperable 306 encoding. 308 Second, further reduce x by a flipping its sign, as explained next. 309 Let 311 x' =: min(x,p-x) mod 2^272. 313 Third, set the byte string b to be the little-endian encoding of the 314 reduced integer x', by finding the unique integers b[i] such that 315 0<=b[i]<256 and 317 (x' mod 2^272) = sum (0<=i<=33, b[i]*256^i). 319 Pseudocode can be found in Appendix C. 321 Note: The loss of information that happens upon replacing x by -x 322 corresponds to applying complex multiplication by i on the curve, 323 because i(x,y) = (-x,iy) is also a point on the curve. (To see 324 this: note 2(iy)^2 = -(2y^2) = -(x^3+x) = (-x)^3+(-x).) In many 325 applications, particularly Diffie--Hellman key agreement, this 326 loss of information is carried through to the final shared secret, 327 which means that Alice and Bob can agree on the same secret 34 328 bytes. 330 In ECC systems where the original x-coordinate and the decoded 331 x-coordinate need to match exactly, the 34-byte encoding is probably 332 not usable unless the following pre-encoding procedure is practical: 334 Internet-Draft 2021-04-01 336 Given a point x, where x is larger than min(x,p-x), first replace 337 x by x'=p-x, on the encoder's side, using the new value x' 338 (instead of x) for any further step in the algorithm. In other 339 words, replace the point (x,y) by the point (x',y')=(-x,iy). Most 340 algorithms will also require a discrete logarithm d of (x,y), 341 meaning (x,y) = [d] G for some point G. Since (x',y') = [i](x,y), 342 we can replace by d' such that [d']=[i][d]. Usually, [i] can be 343 represented by an integer, say j, and we can compute d' = jd (mod 344 ord(G)). 346 4.1.2. Point decoding process 348 4.1.2.1. Summary 350 To decode a 34-byte string, interpret the bytes as little-endian 351 represented integer, which becomes the x-coordinate. When needed, 352 public-key validation is done, to ensure that x is valid for a point 353 on the curve. If needed, the y-coordinate is recovered from x. 355 4.1.2.2. Detail 357 If byte i is b[i], with an integer value between 0 and 255 358 inclusive, then 360 x = sum( 0<=i<=33, b[i]*256^i) 362 Note: a value of -x (mod p) will also be suitable, and results in 363 a point (-x,y') which might be different from the originally 364 encoded point. However, it will be one of the points [i](x,y) or 365 -[i](x,y) where [i] means complex multiplication by [i]. 367 In many cases, such as Diffie--Hellman key agreement using the 368 Montgomery ladder, neither the original value of coordinate x (among 369 x and -x) nor coordinate y of the point is needed. In these cases, 370 the decoding steps can be considered completed. 372 Internet-Draft 2021-04-01 374 +-------------------------------------------------------+ 375 | | 376 | \ W / /A\ |R) |N | I |N | /G ! | 377 | \/ \/ / \ |^\ | \| | | \| \_7 0 | 378 | | 379 | | 380 | WARNING: Some byte strings b decode to an invalid | 381 | point (x,y) that does not belong to the curve | 382 | 2y^2=x^3+x. Some applications would suffer from a | 383 | severe attack if they allow use of (x,y) not on | 384 | the curve. Such vulnerable applications MUST | 385 | validate that the decoded point (x,y) is on the | 386 | curve. Validation is described in Section 5. | 387 | | 388 +-------------------------------------------------------+ 390 In cases where a value for at least one of y, -y, iy, or -iy is 391 needed (such as in Diffie--Hellman key agreement using Edwards 392 coordinates), a candidate value for y can be obtained by computing a 393 square root: 395 y = ((x^3+x)/2)^(1/2). 397 Note: Recovery of y can be combined with validation of x. 399 In some applications (but not Diffie--Hellman), it is important for 400 the decoded value of x to match the original value of x exactly. In 401 that case, the encoder should use the procedure that replaces x by 402 p-x, and adjusts the discrete logarithm appropriately. These steps 403 can be done by the encoder, with the decoder doing nothing. 405 4.2. OPTIONAL: uncompressed point representation 407 A speed-optimized version of elliptic curve Diffie--Hellman over 408 curve 2y^2=x^3+x/GF(8^91+5) might be fastest if the peer's public 409 key is supplied as an uncompressed point (x,y), because of methods 410 like twisted Edwards coordinates. 412 In an arbitrary point, each coordinate uses at most 274 bits, in the 413 standard bit representation. These 274 bits can be fit into 35 414 bytes. Little-endian ordering of bytes is used. 416 Both coordinates together fit into a 70-byte string, with the 35 417 bytes of x appearing first in the string. 419 Each point (except the identity point O, point-at-infinity) has 420 exactly one 70-byte uncompressed representation. Each 70-byte 421 string represents at most one point. 423 Internet-Draft 2021-04-01 425 Converting back and forth between uncompressed and compressed 426 representations is straightforward in principle: just decode to a 427 point, and then re-encode with the other format. Each compressed 428 byte string typically represents four different point ((x,y), 429 (-x,iy), (x,-y), (-x,iy)), which have four different uncompressed 430 representations. 432 Given a compressed representation, there exists a point whose 433 uncompressed version shares the first 34 bytes with the given 434 compressed, because the decoding of a compressed representation 435 gives an x < 2^272, meaning x can be encoded in 34 bytes. The next 436 byte (which is the 35th byte, which is also byte 34 in the 0-indexed 437 array) of the uncompressed representation is set to zero. The next 438 35 bytes are compute from a y recovered from x. The most expensive 439 step of computing is the square root operation, since y = 440 ((x^3+x)/2)^(1/2). 442 Given an uncompressed representation (b), if the 35th byte (b[34]) 443 is zero, then the compressed representation is just the first 34 444 bytes of the uncompressed representation. Otherwise, use the fist 445 35 bytes to compute x, then put p-x mod p into little-endian to form 446 the compressed representation. 448 Point validation for uncompressed 70-byte string is more efficient 449 than for compressed points. To check that the point is on the 450 curve, just check that the curve equation 2y^2=x^3+x holds, which is 451 more efficient than computing a Legendre symbol (the most expensive 452 step of the checking that the point is on the curve given only x). 454 4.3. OPTIONAL: Representation of scalar multipliers 456 Scalars (integer point multipliers) sometimes need to be encoded as 457 byte strings. Typical examples are the following applications. 459 - Digital signature in ECC generally require scalar encodings. 460 This draft does not specify signature algorithms in detail, only 461 providing some general suggestions. 463 Internet-Draft 2021-04-01 465 - An ECC implementation needs to store scalars, over at least short 466 time period, because often scalars are used at least twice, and 467 must be stored between these two uses. For example, in elliptic 468 curve Diffie--Hellman, Alice has scalar a, and she sends Bob 469 point aG. Alice keeps scalar a until she receives point B back 470 from Bob. Alice then applies a to B, computing aB. If a is 471 ephemeral, she then deletes a. While waiting for B, Alice must 472 store a. An implementation is free to use any encoding to store 473 scalars. Implementation are often constructed in modular pieces. 474 Any pieces handling the same scalar need to store the scalar in a 475 consistent, interoperable way. 477 In elliptic curve Diffie--Hellman would typically using a base point 478 G of large prime order q. The size of q is approximately p/72. The 479 value of scalar s usually only matters mod q. An implementation can 480 reduce s, by replacing s by s mod q. This ensures that sp-y, replace x by x-i. Compute s = -i - 3/(i-x). Let r = 567 sqrt(s). (If s has no square root, then report an error.) If r > 568 p-r, replace r by p-r. Write r in little-endian base 256 to get a 569 34-byte string b. 571 Note: Just to illustrate a contrast between Elligator i encoding 572 and the normal point encoding, consider the useless example of 573 applying both encodings. Start with 34-byte string b. Apply 574 Elligator i encoding to get a point (x,y). Apply the point 575 encoding to (x,y) to get a 34-byte string b'. In summary, 576 b'=encode(encode(b)). The byte string b' has no significant 577 relation to b. The map b->b' from 34-byte strings to themselves 578 is lossy (non-injective) with ratio ~4:1, and the image set is 579 about one quarter of all 34-byte strings. 581 5. Point validation 583 In elliptic curve cryptography, scalar multiplying an invalid public 584 key by a private key risks leaking information about the private 585 key. 587 To avoid leaking information about a user private key, the user can 588 validate that the peer's public key is a point on the curve, or even 589 that it is point in the correct subgroup. 591 5.1. Schedules for point validation 593 This section specifies three schedules (mandatory, simplified, and 594 minimal) for deciding when to validate whether a given point (x,y) 595 is on the curve 2y^2=x^3+x/GF(8^91+5). 597 5.1.1. Mandatory schedule for point validation 599 As a precaution, an implementation MAY opt to apply a mandatory 600 schedule for point validation, meaning every public key (and point) 601 is validated, before subsequent use. 603 5.1.2. Simplified schedule for point validation 605 A small, general-purpose, implementation aiming for high speed might 606 not be able to afford the cost of the mandatory schedule for 607 validation from Section 5.1.1, because each validation of a 34-byte 608 encoded point costs about 10% of a scalar multiplication. 610 Internet-Draft 2021-04-01 612 As a practical middle ground, an implementation MAY opt to apply 613 simplified validation, which is the rule is that a not-yet-trusted 614 peer's public key is validated before being scalar multiplied by a 615 static secret key. 617 +---------------------------------------------------------------+ 618 | STATIC | 619 | USER SECRET | 620 | KEY ------\ PEER _ ___ | 621 | + ) PUBLIC |\/| | | (_` | | 622 | UNAUTHENTICATED ------/ KEY | | \_/ ._) | BE VALIDATED.| 623 | PEER PUBLIC | 624 | KEY | 625 +---------------------------------------------------------------+ 627 Note: The simplified schedule for validation implies that, when 628 the secret key is ephemeral (for example, used in one 629 Diffie--Hellman transaction), the peer's public key need not be 630 validated. 632 Note: The simplified schedule validation implies that when the 633 point being scalar multiplied is a known valid fixed point, or a 634 previously validated public key (including a public key from a 635 certificate in which the certification authority has a policy to 636 valid public keys), then validation is not needed. 638 5.1.3. Minimal schedule for point validation 640 An implementation MAY opt to use a minimal schedule for point 641 validation, meaning doing as little point validation as possible, 642 just enough to resist known attack against the implementation, 643 reducing the risk to a negligible level. 645 The curve 2y^2=x^3+x is not twist-secure: using the Montgomery 646 ladder for scalar multiplication is not enough to thwart invalid 647 public key attacks. 649 However, consider a static hashed-ECDH implementation implemented 650 with a Montgomery ladder, such that the static secret key is used in 651 at most ten million times hashed-ECDH transactions. Even if exposed 652 to invalid points on the twist, the security risk is nearly 653 negligible. Therefore, the minimal validation would not validate the 654 peer's public keys. 656 Internet-Draft 2021-04-01 658 5.2. Point validation process 660 Upon decoding a 34-byte string into x, the next step is to compute 661 z=2(x^3+x). Then one checks if z has a nonzero square root (in the 662 field of size 8^91+5). If z has a nonzero square root, then the 663 x represents a valid point, otherwise x is invalid. 665 Equivalently, one can check that x^3 + x has no square root (that 666 is, x^3+x is a quadratic non-residue). 668 To check z for a square root, one can compute the Legendre symbol 669 (z/p) and check that is 1. (Equivalently, one can check that 670 ((x^3+x)/p)=-1.) 672 The Legendre symbol can be computed using Gauss' quadratic 673 reciprocity law, but this requires implementing modular integer 674 arithmetic for integral moduli smaller than 8^91+5. 676 Instead, one can compute the Legendre symbol using powering in the 677 field: (z/p) = z^((p-1)/2) = z^(2^272+2). This is much slower than 678 using quadratic reciprocity. 680 More generally, in signature applications (such as [B2]), where the 681 y-coordinate is also needed, the computation of y, which involves 682 computing a square root will generally include an implicit check 683 that x is valid. 685 OPTIONAL: In some situations, it is also necessary to ensure that 686 the point has large order, not just that it is on the curve. For 687 points on this curve, each point has large order, unless it has 688 torsion by 12. In other words, if [12]P != O, then the point P has 689 large order. Most applications of elliptic curve Diffie--Hellman do 690 not require this check. 692 OPTIONAL: In some situations, it may be necessary to ensure that a 693 point P also has a prime order q = ord(G). One method to check this 694 is to compute that [q]P, checking that [q]P = O. An alternative 695 method is to try to solve for R in the equation [12]R=P, which 696 involves methods such as division polynomials. The alternative has 697 potential advantage of being faster than computing [q]P, but the 698 clear disadvantage of requiring extra algorithms (beyond the scalar 699 multiplication already necessary for Diffie--Hellman). Most 700 applications of elliptic curve Diffie--Hellman do not require this 701 check. 703 6. IANA considerations 705 This document requires no actions by IANA, yet. 707 Internet-Draft 2021-04-01 709 7. Security considerations 711 No cryptographic algorithm is without risk. 713 Potential security risks of 2y^2=x^3+x/GF(8^91+5) are listed in this 714 section. These risks are worth considering, before deciding to use 715 2y^2=x^3+x/GF(8^91+5). 717 This section aims to thoroughly describe the risks, perhaps erring 718 on the side over-stating many of the risks. 720 Absolute risk is difficult to quantify, especially against unknown, 721 potential attacks. Relative risk is slightly easier to qualify, if 722 a comparable cryptographic system is available as a benchmark. 724 (Relative risk comparison to no cryptography is sometimes sensible. 725 In a less exposed system, such as inter-process communication, 726 perhaps, cryptography, especially ECC, might not provide enough 727 benefit to justify the cost. In this case, the risk of ECC is the 728 wasted runtime. Conversely, in over-exposed systems, all data gets 729 made public quickly, or attacked easily, so securing data-in-transit 730 with ECC might only provide a false sense of security.) 732 Most of the security risks of 2y^2=x^3+x/GF(8^91+5) listed are 733 compared to the risks of a typical generic curve in ECC, or to the 734 risks of specific well-established curves in ECC (such as NIST P-256 735 and Curve25519). 737 Note: Because 2y^2=x^3+x/GF(8^91+5) MUST be used only in 738 multi-curve ECC, comparison to other curves is mainly for 739 selection of curves in a multi-curve ECC implementation, from a 740 pool of curves. 742 Note: For possible security benefits of 2y^2=x^3+x/GF(8^91+5), see 743 Appendix A. This section and Appendix A are not entirely 744 independent, since they discuss two sides of the same coin. 746 7.1. Field choice 748 The field size 8^91+5 has the following risks. 750 See [B1] for further discussion about the relative merits of 8^91+5. 752 7.1.1. A special prime 753 Internet-Draft 2021-04-01 755 8^91+5 is a special prime that might lead a mathematical attack 756 speeding up the elliptic curve discrete logarithm problem (ECDLP). 757 Known correlations between ECC field size and ECDLP attacks are 758 evidence of this risk. For some curve equations, the 759 supersingularity, and thus security due to vulnerability to MOV 760 attack, depends on the prime of the field size. For some curve 761 equations, the curve size is related in a simple way to the field 762 size, causing a potential correlation between the field size and the 763 effectiveness of an attack, such as the Pohlig--Hellman attack. The 764 curve 2y^2=x^3+x/GF(8^91+5) resists these well-known 765 field-size-dependent ECDLP attacks. The risk is that unpublished 766 field-size-dependent ECDLP attacks might yet exist, and might then 767 apply to 2y^2=x^3+x/GF(8^91+5). 769 Other special field sizes are used by some other standard curves. 770 The standard curves NIST P-256 and Curve25519 use special prime 771 field sizes, with specialness quite similar to the specialness of 772 8^91+5. Arguably, these other standards with special field curves 773 suffer a risk similar to that of 2y^2=x^3+x/GF(8^91+5) from 774 unpublished field-size-dependent ECDLP attacks. 776 Other standard curves, such as the Brainpool curves, somewhat 777 mitigate this risk of unpublished field-size-dependent ECDLP attacks 778 by using pseudorandom field sizes. 780 7.1.2. Risk of 64-bit integer overflow 782 8^91+5 arithmetic implementation, while implementable in five 64-bit 783 words, has some risk of overflowing, or of not fully reducing 784 properly. A smaller field, such as that used in Curve25519, support 785 simpler modular reduction and overflow-avoidance properties, if 786 using five 64-bit words for field arithmetic. 788 7.1.3. Excessive size for 128-bit security 790 8^91+5 is well-above 256 bits in size. A user aiming to resist 791 2^128 step attacks, could use a smaller, and presumably faster, 792 curve, and still have Pollard rho attacks taking 2^128 elliptic 793 curve operations. Such a user of ECC field size 8^91+5 therefore 794 uses unnecessary communication and computation to protect their 795 128-bit keys. In other words, the extra cost for exceeding 256 bits 796 is wasteful, and arguably a form of denial of service, if the user 797 had opportunity to devote the cost to other security protections. 799 7.1.4. Non-maximality among six-symbol (DEC) primes 800 Internet-Draft 2021-04-01 802 8^91+5 is smaller than three other primes: 8^95-9, 9^99+4 and 9^87+4 803 that share the same decimal exponential complexity as 8^91+5: six 804 symbols. Curves defined over larger field size have better Pollard 805 rho security (against ECDLP attacks), but 8^91+5 has better security 806 than these curves, against other types of attacks. 808 The primes 9^99+4 and 9^87+4 are not close to a power of two. This 809 makes implementing them in software almost twice as slow as 8^91+5. 810 The extra runtime is a weak denial-of-service attack. A more 811 generic form of modular reduction is needed. Generic modular 812 reduction might be more prone to implementation attacks such as side 813 channel attacks. 815 The prime p'=8^95-9 is quite similar to p=8^91+5 in many aspects. 816 Being larger than p, the prime p'=8^95-9 has a slightly greater risk 817 than p=8^91+5 has of an arithmetic overflow implementation fault in 818 field arithmetic. Field size 8^95-9 has more complicated powering 819 algorithms for computing field inverses, Legendre symbols, and 820 square roots, because the binary expansion of numbers like p'-2 have 821 many 1-bits, unlike p-2. This discrepancy arises because p'=8^95-9 822 is just a little above of power of two, while p=8^91+5 is just a 823 little below a power of two. The more complicated powering 824 algorithms might make an implementation a little slower. Worse, 825 they may require more complicated code, adding to the burden of 826 debugging, and increasing the chance of implementation error. 828 7.1.5. Smaller five-symbol field sizes 830 8^91+5 is smaller than field size 2^283 (used in ECC, for curve 831 sect283k1 [SEC2], [Zigbee]). Several other five-symbol and 832 four-symbol field sizes (such as 9^97) are also larger than 8^91+5. 833 When used in ECC, 8^91+5 therefore provides less Pollard rho 834 security than such larger field sizes. 836 These larger field sizes are not primes, they are composite prime 837 powers. Composite field sizes in ECC have two security risks: 839 - Recent progress in ECDLP attacks over composite fields [HPST] and 840 [Nagao] is a major red flag against ECC over composite fields, 841 suggesting that ECC over composite fields is riskier, and much 842 closer to being broken. 844 Internet-Draft 2021-04-01 846 - Software speed for large-characteristic field arithmetic is 847 typically much higher than small-characteristic field arithmetic. 848 Actually, the speed advantage is for software that runs on 849 general-purpose hardware with dedicated 64-bit integer 850 multiplication circuits. The composite field sizes larger than 851 8^91+5 have small characteristic. Software for 852 small-characteristic 853 field sizes is not only slower, but more complicated, and 854 therefore more prone to implementation faults. 856 7.1.6. Vulnerability to faulty hardware 858 Efficient software implementation of 8^91+5, and other 859 large-characteristic fields, has security that relies of hardware 860 for 64-bit integer arithmetic. 862 Corrupted hardware might produce incorrect results for a single pair 863 of inputs. Detecting such a hardware error by exhaustive search 864 would be infeasible, because there are 2^128 possible pairs of 865 inputs. An attacker might be able to find this hardware error by 866 examining the hardware directly. Yet, a typical user might not be 867 able to detect this hardware error, or to prevent it. 869 In this case, the attacker might be able to induce the hardware 870 user, by supplying the user with a maliciously crafted the public 871 key. In this case, the public key would cause the provide the 872 faulty input values into the hardware. The resulting error might 873 cause the user to leak their secret key to the attacker, as in [bug 874 attacks] and [IT]. 876 7.1.7. Other measures of complexity 878 Decimal exponential complexity means the minimum number of the 879 symbols from the set 881 0 1 2 3 4 5 6 7 8 9 + - * ^ ( ) 883 to specify a number, with the usual meanings of the symbols. (The 884 symbols * and ^ are ASCII adaptations of traditional mathematical 885 notations, and their meaning has become fairly standard in 886 mathematical programming.) 888 Decimal exponential complexity is only one way to measure Kolmogorov 889 complexity of a non-negative integer. Other measures of complexity 890 measures allow larger primes to be expressed in six or even fewer 891 symbols. 893 Internet-Draft 2021-04-01 895 The factorial operation is often notated with an exclamation mark! 896 Primes larger than 8^91+5 are then expressible in five symbols: 897 94!-1 is a 485-bit prime number, expressible in five symbols. Such 898 numbers -- so far as I know -- are not close to a power of two. 899 Therefore, they are likely have similar inefficiency and 900 implementability defects to the primes 9^99+4 and 9^87+4, which are 901 also far from a powers of two. 903 At some point, increasing the size of the symbol set should be 904 regarded as an increase in the Kolmogorov complexity. Arguably, the 905 exclamation mark notation favors the factorial operation over 906 exponentiation: 5040=7! seems no simpler than 128=2^7. 908 It is generally understood that there can be no absolutely objective 909 and best measure of Kolmogorov complexity. 911 However, in [B3], an alternative measure of Kolmogorov complexity is 912 considered, that aims to be somewhat objective. It follows Godel's 913 ideas for the most fundamental definition computable functions, 914 which Turing later proved to be equivalent in computing power to his 915 tape machines. 917 Unlike decimal exponential complexity, the system in [B3] has no 918 built-in preference for decimal, or even for standard arithmetic 919 operations like addition, multiplication, and exponentiation. 920 Instead, all computations must be built up from the successor 921 function and primitive recursion (or minimization recursion, but 922 that should be avoided). 924 The absolute complexity measure in [B3] is difficult to determine 925 for a given prime. Upper bounds are easy to find, by exhibiting 926 descriptions, but it is difficult to determine the shortest 927 description. So far, it seems that the prime 2^521-1 has lower 928 complexity than 8^91+5, because, among the descriptions found so 929 far, 2^521-1 currently has shorter description than the shortest yet 930 found for 931 8^91+5. 933 The main downside of 2^521-1 compared to 8^91+5 is its larger size 934 (almost twice the bit length), and also more complicated powering 935 algorithms for inversion, Legendre symbols and square roots. 937 7.2. Curve choice 939 There are several security risks that might be associated with 940 specific curve 2y^2=x^3+x/GF(8^91+5). 942 7.2.1. Special curve equation 943 Internet-Draft 2021-04-01 945 The curve equation 2y^2=x^3+x is special, among elliptic curve 946 equations. To see how special it is, we list some of its features. 948 - Its elliptic curve discriminant is low, at 4, whereas random curves 949 have discriminants that average around p/2. 951 - Its j-invariant is 1728, whereas random curves have j-invariants 952 that average around p/2. 954 - Its automorphism group has size 4, whereas random curves have 955 automorphism group of size 2, with overwhelming probability. 957 - Its curve equation has three monomial terms, whereas random 958 curves, have (all isomorphic) curve equations with at least 4 959 terms, 960 with overwhelming probability. 962 - It has complex multiplication by i, with [i] being a linear 963 isogeny. 965 The specialness of 2y^2=x^3+x is well understood in elliptic curve 966 theory. 968 Miller, in 1985, already suggested exercising prudence when 969 considering such special curves. More precisely, Miller suggested 970 using curve equation y^2=x^3-ax, because if a is a quadratic 971 non-residue, then the curve has p+1 point, because it is 972 supersingular. This saves the trouble of point-counting. But 973 Miller predicted -- correctly! -- that this convenience is not free, 974 it may be correlated with a risk. Indeed, two attacks were 975 subsequently found. 977 The two published attacks do not impact 2y^2=x^3+x/GF(8^91+5). The 978 risk is that similar unpublished attacks might affect 979 2y^2=x^3+x/GF(8^91+5). 981 Menezes, Okamoto and Vanstone (MOV) found an attack on elliptic 982 curves of low embedding degree. The curve 2y^2=x^3+x/GF(8^91+5) is 983 not vulnerable to the MOV attack, because it has high embedding 984 degree. The concern is that 2y^2=x^3+x/GF(p') for different primes 985 p', is vulnerable to the MOV attack. It is known to be 986 supersingular, for about half of all primes p'. 988 Internet-Draft 2021-04-01 990 Note: To repeat, because the MOV attack was several years later 991 than Miller's origin caution from 1985, Miller's prudence seems 992 prescient. Perhaps he was also prescient about yet other 993 potential attacks (still unpublished), and these attacks might 994 affect 2y^2=x^3+x/GF(8^91+5). Perhaps, we continues to Miller's 995 prudence. 997 Gallant, Lambert and Vanstone found ways to slightly speed up 998 Pollard rho attacks against ECDLP, when the curve has an efficient 999 endomorphism. This attack makes a modest speed-up for binary 1000 Koblitz curves (2^7 times speed-up), but for 2y^2=x^3+x/GF(8^91+5) 1001 makes only a minor speed-up in the ECDLP attack (2 times speed-up), 1002 not much more than the speed-up from from efficient arithmetic. 1004 Many other standard curves, including NIST P-256 [NIST-P-256], 1005 Curve25519, Brainpool [Brainpool], do not have complex 1006 multiplication endomorphism by i, or any other low-degree 1007 endomorphism. Essentially, these curves adhere more fully to 1008 Miller's 1985 advice to be prudent about special curves. 1010 Yet other (fairly) standard curves do, such as NIST K-283 (used in 1011 [Zigbee]) and secp256k1 (see [SEC2] and [BitCoin]). Furthermore, it 1012 is not implausible [KKM] that special curves, including those 1013 efficient endomorphisms, may survive an attack on random curves. 1015 7.2.2. Twist insecurity 1017 The curve 2y^2=x^3+x over 8^91+5 is not twist-secure. 1019 An implementer might use the Montgomery ladder in Diffie--Hellman 1020 and might also re-use private keys. An implementer might imitate an 1021 implementation of a twist-secure curve like Curve25519. The 1022 twist-secure implementation would use a Montgomery ladder, and skip 1023 public-key validation. 1025 Skipping public-key validation with a re-used secret scalar in a 1026 Montgomery ladder implementation might leak information about the 1027 re-used secret scalar, and severely weaken its security. 1029 This document provides ample warnings, but an implementer might be 1030 too busy to read the document, or might only given a small excerpt 1031 of this document, excluding the warnings about public-key 1032 validation. An implementer might accidentally implement public-key 1033 validation with a bug that does public-key validation incorrectly. 1035 Several other standardized curves, such as NIST P-256, are also not 1036 twist-secure. The risk from being twist-insecure for these curves 1037 to quite similar to the risk for 2y^2=x^3+x/GF(8^91+5). 1039 Internet-Draft 2021-04-01 1041 Curves like NIST P-256 might have less risk from being 1042 twist-insecure, because they not Montgomery curves (and not even 1043 isomorphic to Montgomery curves). An implementer has less incentive 1044 to use a Montgomery ladder for these curves, because there is less 1045 efficiency gain compared to more conventional scalar multiplication 1046 algorithms. Conventional scalar multiplication algorithms are 1047 already well-known to require public-key validation. 1049 Actually, the Montgomery ladder might not be the fastest scalar 1050 multiplication algorithm for 2y^2=x^3+x/GF(8^91+5). So, it is 1051 unclear how the risk of twist-insecurity really compares between it 1052 and NIST P-256. 1054 7.2.3. Point order not near a power of two 1056 The base point G has prime order q which is not close to a power of 1057 two. 1059 Note: Its leading hexadecimal expansion 71C71C... and half of 1060 leading digits (or hex-nibbles) match that of floor((8^90)/9), and 1061 q/2^266 is approximately 1.7778. See A.4.4.1. for the exact value 1062 of q. 1064 Digital signature scheme, such as ECDSA, have a known security 1065 vulnerability, first discovered by Bleichenbacher in the case of 1066 DSA, when q is not close to a power of two. An per-message secret 1067 k, essentially an ephemeral secret scalar, is computed when 1068 generating a signature. If the probability distribution k is not 1069 uniform in [0,q-1], in the sense that some large sub-intervals are 1070 about twice as likely as others, then the signatures leak 1071 information about the static signing key d. A leak in k means a 1072 leak in d. With enough signatures with a leaky k, eventually the 1073 leaks in d are enough to reveal the whole of d. Once d is revealed, 1074 the attacker can forge arbitrary signatures. 1076 A typical implementer generates secret scalar k by generating a 1077 uniformly random byte string b, with b will be uniformly distributed 1078 in an interval [0,2^m-1], and then setting k = b mod q. (Sometimes, 1079 the computation b mod q is delayed until the signing equation, but 1080 in all cases b mod q is the effective value for k.) If 2^m is 1081 chosen as the power of two nearest to q, then the effective k will 1082 have a bias, unless q is very close to 2^m. For 1083 2y^2=x^3+x/GF(8^91+5), the number q is not very close to 2^m. 1085 Internet-Draft 2021-04-01 1087 Signature standards mitigate this attack by several methods. 1088 Choosing longer byte string b, with max value 2^m > 2^64*q, reduces 1089 the bias of k to a negligible amount. For shorter byte strings, it 1090 is possible to re-generate b until it belongs to an an interval 1091 [0,uq-1] for some small integer u. 1093 By contrast, many standard curves, including NIST P-256 and 1094 Curve25519, already have q close to a power of two. The reason for 1095 this is that the field size is close to a power of two, and the 1096 cofactor is also a power of two (usually 1,2,4, or 8). 1098 7.2.4. Vulnerability to Cheon-type attacks 1100 The Brown--Gallant--Cheon attack can find d in q^(1/3) computations 1101 using q^(1/3) queries to an oracle that compute [d]P from any given 1102 input point P. 1104 The attack is not very serious because of large number of queries it 1105 requires. Variations of the attack work with fewer queries but use 1106 more computation. As the number of queries approaches 0, then the 1107 computation approaches q^(1/2), matching the cost of Pollard rho. 1109 The attack is also not very serious, because only a few 1110 applications of ECC provide such an oracle to compute [d]P. Static 1111 elliptic curve Diffie--Hellman usually hashes [d]P, so does not 1112 provide such an oracle (unless the hash fails to be one-way). 1114 The details of attack include making u queries to the oracle, where 1115 u is a factor of q-1 or q+1. The computation phase then takes about 1116 (q/u)^(1/2) steps. Putting u ~ q^(1/3), if possible, approximately 1117 minimizes the sum of the number of queries and off-line computation 1118 steps. 1120 A general mitigation to the attack is to choose q such q-1 and q+1 1121 have no factors u in a range that makes the attack impactful. Such 1122 a curve could be called Cheon-resistant. A Cheon-resistant curve 1123 can be used in protocols that provide the static Diffie--Hellman 1124 oracle, without worrying about degrading security from a large 1125 number of queries. 1127 Most standardized curves, including NIST P-256, Curve25519 and the 1128 Brainpool curves, are not Cheon-resistant. Curve 1129 2y^2=x^3+x/GF(8^91+5) is not Cheon-resistant either. 1131 7.2.5. Small-subgroup confinement attacks 1132 Internet-Draft 2021-04-01 1134 A fifth risk is a small-subgroup confinement attack, which can also 1135 leak a few bits of the private key. Curve 2y^2=x^3+x over 8^91+5 1136 has 72 elements whose order divides 12. 1138 7.3. Encoding choices 1140 As in all ECC, projective coordinates are not suitable as the final 1141 representation of an elliptic curve point, for two reasons. 1143 - Projective coordinates for a point are generally not unique: each 1144 point can be represented in projective coordinates in multiple 1145 different ways. So, projective coordinates are unsuitable for 1146 finalizing a shared secret, because the two parties computing the 1147 shared secret point may end up with different projective 1148 coordinates. 1150 - Projective coordinates have been shown to leak information about 1151 the scalar multiplier [PSM], which could be the private 1152 key. It would be unacceptable for a public key to leak 1153 information about the private key. In digital signatures, even a 1154 few leaked bits can be fatal, over a few signatures 1155 [Bleichenbacher]. 1157 Therefore, the final computation of an elliptic curve point, after 1158 scalar multiplication, should translate the point to a unique 1159 representation, such as the affine coordinates described in this 1160 specification. 1162 For example, when using a Montgomery ladder, scalar multiplication 1163 yields a representation (X:Z) of the point in projective 1164 coordinates. Its x-coordinate is then x=X/Z, which can be computed 1165 by computing the 1/Z and then multiplying by X. 1167 The safest, most prudent way to compute 1/Z is to use a side-channel 1168 resistant method, in particular at least, a constant-time method. 1169 This reduces the risk of leaking information about Z, which might in 1170 turn leak information about X or the scalar multiplier. 1172 Fermat inversion, computation of Z^(p-2) mod p, is one method to 1173 compute the inverse in constant time (if the inverse exists). 1175 7.4. General subversion concerns 1177 The main motivation of curve 2y^2=x^3+x over 8^91+5 is to minimize 1178 the risk of curve subversion via a backdoor ([Gordon], [YY], 1179 [Teske]). 1181 Internet-Draft 2021-04-01 1183 A security skeptic ought to consider any security technology's 1184 appearance in a standards development organization document with 1185 suspicion, as an possible effort at subversion. (See [BCCHLV] for 1186 some detailed analysis.) This document, despite its intended 1187 experimental status, can be seen as possible subversion. Other 1188 standards for curves could be also seen as even more successful 1189 efforts a subversion. 1191 Note: A skeptic needs to be careful not to become paranoid. 1192 Interoperable ECC has a strong need for standardized curves. If 1193 there is a non-subverted secure curve, standardizing it is good 1194 for security. 1196 A skeptic needing to choose between standardized curves can then 1197 objectively examine the curve's intrinsic merits both or, failing 1198 that, perhaps objectively examine reputation of the (alleged) author 1199 of the standard, making an ad hominem argument. 1201 This document asks all users, including skeptics, to prefer 1202 mainstream curves like NIST P-256 or Curve25519, to this document's 1203 curve 2y^2=x^3+x/GF(8^91+5). This document invites users to use two 1204 or more curves in ECC, with 2y^2=x^3+x/GF(8^91+5) as a second line 1205 of defense. 1207 The reader is encouraged to take a skeptical viewpoint of curve 1208 2y^2=x^3+x/GF(8^91+5), and of other curves. Skeptical users of the 1209 curve are expected to make a rational as possible decision to add 1210 2y^2=x^3+x/GF(8^91+5) to the list of curves used in multi-curve 1211 ECC. 1213 To paraphrase, users seriously worried about subverted curves (or 1214 other cryptographic algorithms), either because they estimate as 1215 high either the probability of subversion or the value of the data 1216 needing protection, have good reason to like 2y^2=x^3+x/GF(8^91+5) 1217 for its compact description. 1219 Nevertheless, the best way to resist subversion of cryptographic 1220 algorithms seems to be combine multiple dissimilar cryptographic 1221 algorithms, in a strongest-link manner. Diversity hedges against 1222 subversion, and should the first defense against it. 1224 7.5. Risk of low age and eyes (aegis) 1226 The exact curve 2y^2=x^3+x/GF(8^91+5) was (seemingly) first 1227 described to the public in 2017 [AB]. So, it has a very low age, at 1228 least compare to more established curves, like NIST P-256 (from 1229 1999) and Curve25519 (from 2005). 1231 Internet-Draft 2021-04-01 1233 The curve 2y^2=x^3+x/GF(8^91+5) it has not been submitted for a 1234 publication to any formally peer-reviewed academic cryptographer 1235 forum, such as the IACR conferences like Crypto and Eurocrypt. It 1236 has most like been reviewed by very few eyes. 1238 Arguably, other reviewers have little incentive to study it 1239 critically, for a couple reasons: 1241 - The looming threat of a quantum computer has diverted many 1242 researchers towards studying post-quantum cryptography, such as 1243 supersingular isogeny Diffie--Hellman. 1245 - Past CFRG disputes over NIST P-256 and Curve25519 (and other ECC 1246 alternatives) have perhaps tired some reviewers, many of whom 1247 would to prefer to concentrate on deployment of ECC, seeing 1248 disputes as delay. 1250 The simplistic metric of aegis, meaning in age times eyes (times 1251 incentive), 2y^2=x^3+x/GF(8^91+5), scores low. Counting myself (but 1252 not quantifying incentive) it gets an aegis score of 0.1 (using a 1253 rating 0.1 of my eyes factor in the aegis score: I have not 1254 discovered any major ECC attacks of my own.) This is far smaller 1255 than my estimates (see below) some more well-studied curves. 1257 Nonetheless, the curve 2y^2=x^3+x/GF(8^91+5) has some similarities 1258 to some of the better-studied curves with much higher aegis: 1260 - Curve25519: has field size 8^85-19, which a little similar to 1261 8^91+5; has equation of the form by^2=x^3+ax+x, with b and a 1262 small, which is similar to 2y^2=x^3+x. Curve25519 has been around 1263 for over 10 years, has (presumably) many eyes looking at it, and 1264 has been deployed thereby creating an incentive to study. An 1265 estimated aegis for Curve25519 is 10000. 1267 - NIST P-256: has a special field size, and maybe an estimated aegis 1268 of 200000. (It is a high-incentive target. Also, it has received 1269 much criticism, showing some intent of cryptanalysis. Indeed, 1270 there has been incremental progress in finding minor weakness 1271 (implementation security flaws), suggestive of actual 1272 cryptanalytic effort.) The similarity to 2y^2=x^3+x over 8^91+5 1273 is very minor, so very little of the P-256 aegis would be relevant 1274 to this document. 1276 Internet-Draft 2021-04-01 1278 - secp256k1: has a special field size, though not quite as special 1279 as 8^91+5, and has special field equation with an efficient 1280 endomorphism by a low-norm complex algebraic integer, quite 1281 similar to 2y^2=x^3+x. It is about 17 years old, and though not 1282 studied much in academic work, its deployment in Bitcoin has at 1283 least created an incentive to attack it. An estimated aegis for 1284 secp256k1 is 10000. 1286 - Miller's curve: Miller's 1985 paper introducing ECC suggested, 1287 among other choices, a curve equation y^2=x^3-ax, where a is a 1288 quadratic non-residue. Curve 2y^2=x^3+x is isomorphic to 1289 y^2=x^3-x, essentially one of Miller's curves, except that a=1 is 1290 a quadratic residue. Miller's curve may not have been studied 1291 intensely as other curves, but its age matches that ECC itself. 1292 Miller also hinted that it was not prudent to use a special curve 1293 y^2=x^3-ax: such a comment may have encouraged some cryptanalysts, 1294 but discouraged cryptographers, perhaps balancing out the effect 1295 on the eyes factor the aegis. An estimated aegis for Miller's 1296 curves is 300. 1298 Some of the direct estimates of aegis for the similar curves could 1299 be counted towards to 2y^2=x^3+x/GF(8^91+5), as an indirect form of 1300 aegis. Some obvious cautions to the reader: 1302 - Small changes in a cryptographic algorithm can cause large 1303 differences in security. Security arguments based on 1304 similarity in cryptographic schemes should be given low priority. 1306 - Security flaws have sometimes remained undiscovered for years, 1307 despite both incentives and peer reviews (and lack of hard 1308 evidence of conspiracy). The eyes factor of the aegis score is 1309 very subjective. It is vulnerable to false positives via a herd 1310 effect. Despite this caveat, it is not sensible to completely 1311 ignore the eyes factor in the aegis score. Otherwise, one might 1312 deploy for cryptographic schemes that might never have been 1313 studied, which might include many insecure schemes. 1315 7.6. Risk of ECC and multi-curve ECC 1317 This document argues for continued use of ECC, and also for 1318 multi-curve ECC. 1320 There is large consensus to use ECC for the time-being, but not yet 1321 much consensus for multi-curve ECC. 1323 7.6.1. Risk of ECC, overall 1324 Internet-Draft 2021-04-01 1326 Some critics do not consider ECC safe to use, even the CFRG curves 1327 like Curve25519. Two criticisms are discussed below. 1329 7.6.1.1. Risk of hidden pre-quantum attacks on ECC 1331 Extreme skeptics might consider all (or most) ECC to be insecure, 1332 vulnerable to some unpublished attack, runnable today using 1333 conventional pre-quantum computers. 1335 These skeptics are outliers, given how much ECC is used today. 1337 Nonetheless, they have arguments with some merit. They could argue 1338 that ECC is too sophisticated, in that only a few elite can claim to 1339 have truly contributed to its security analysis. Indeed, ECC is so 1340 sophisticated, that nobody can truly claim to fully understand it, 1341 especially its security. 1343 These skeptics might prefer RSA or finite-field Diffie--Hellman. 1345 These skeptics ought to be willing to use a hybrid of ECC in a 1346 combination with some other form of public-key cryptography. 1348 7.6.1.2. Risk of quantum computer attacks on forward secrecy 1350 Some users believe that the two probabilities below are so high, 1351 that ECC can no longer provide much security (in terms of secrecy). 1353 - The probability that an attacker records their ECC-protected 1354 ciphertext. 1356 - The probability that an attacker has, or will soon have, a quantum 1357 computer capable of breaking ECC. 1359 These users are optimistic about quantum computers. These 1360 quantum-optimists might think that we should stop bother to ECC, 1361 maybe even right now, and take our chances with some post-quantum 1362 cryptography. 1364 The general consensus seems to be address this quantum threat by 1365 using ECC combined with a post-quantum cryptography. 1367 7.6.2. Multi-curve ECC might be wasteful 1369 Milder skeptics might argue that multi-curve ECC does not add enough 1370 benefit over single-curve ECC to justify its cost. 1372 Internet-Draft 2021-04-01 1374 These skeptics might infer the risk of curve-specific attacks is 1375 already low enough. Major current curves, such as NIST P-256, 1376 Curve25519 and Brainpool, already include mitigations against 1377 subversive curve-specific attacks. The existing mitigation might be 1378 enough for milder skeptics. After all, the latest curve-specific 1379 ECDLP attacks are from 2000, at least for prime-field curves, which 1380 might convince milder skeptics that curve-specific ECDLP attacks 1381 have been exhausted for prime-field curves. The skeptics might also 1382 feel that curves like Curve25519 have resolved the risk of 1383 implementation attacks to the lowest possible for ECC. 1385 8. References 1387 8.1. Normative References 1389 [BCP14] Bradner, S., "Key words for use in RFCs to Indicate 1390 Requirement Levels", BCP 14, RFC 2119, March 1997, 1391 . 1393 8.2. Informative References 1395 To be completed. 1397 [AB] A. Allen and D. Brown. ECC mod 8^91+5, presentation to CFRG, 1398 2017. 1399 1401 [AMPS] Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, and 1402 Juraj Somorovsky. Prime and Prejudice: Primality Testing Under 1403 Adversarial Conditions, IACR ePrint, 1404 2018. 1406 [B1] D. Brown. ECC mod 8^91+5. IACR ePrint, 2018. 1407 1409 [B2] D. Brown. RKHD ElGamal signing and 1-way sums. IACR ePrint, 1410 2018. 1412 [B3] D. Brown. Rolling up sleeves when subversion's in the field? 1413 IACR eprint, 2020. 1415 [B4] D. Brown. GLV+HWCD for 2y^2=x^3+x/GF(8^91+5). IACR ePrint, 1416 2021. 1418 [KKM] A. Koblitz, N. Koblitz and A. Menezes. Elliptic Curve 1419 Cryptography: The Serpentine Course of a Paradigm Shift, IACR 1420 ePrint, 2008. 1422 Internet-Draft 2021-04-01 1424 [BCCHLV] D. Bernstein, T. Chou, C. Chuengsatiansup, A. Hulsing, 1425 T. Lange, R. Niederhagen and C. van Vredendaal. How to 1426 manipulate curve standards: a white paper for the black hat, IACR 1427 ePrint, 2014. 1429 [Elligator] (((To do:))) fill in this reference. 1431 [NIST-P-256] (((To do:))) NIST recommended 15 elliptic curves for 1432 cryptography, the most popular of which is P-256. 1434 [Zigbee] (((To do:))) Zigbee allows the use of a 1435 small-characteristic special curve, which was also recommended by 1436 NIST, called K-283, and also known as sect283k1. These types of 1437 curves were introduced by Koblitz. These types of curves were 1438 not recommended by NSA in Suite B. 1440 [Brainpool] (((To do:))) the Brainpool consortium (???) recommended 1441 some elliptic curves in which both the field size and the curve 1442 equation were derived pseudorandomly from a nothing-up-my-sleeve 1443 number. 1445 [SEC2] Standards for Efficient Cryptography. SEC 2: Recommended 1446 Elliptic Curve Domain Parameters, version 2.0, 2010. 1447 1449 [IT] T. Izu and T. Takagi. Exceptional procedure attack on elliptic 1450 curve cryptosystems, Public key cryptography -- PKC 2003, Lecture 1451 Notes in Computer Science, Springer, pp. 224--239, 2003. 1453 [PSM] (((To do:))) Pointcheval, Smart, Malone-Lee. Projective 1454 coordinates leak. 1456 [BitCoin] (((To do:))) BitCoin uses curve secp256k1, which has an 1457 efficient endomorphism. 1459 [Bleichenbacher] To do: Bleichenbacher showed how to attack DSA 1460 using a bias in the per-message secrets. 1462 [Gordon] (((To do:))) Gordon showed how to embed a trapdoor in DSA 1463 parameters. 1465 [HPST] Y. Huang, C. Petit, N. Shinohara and T. Takagi. On 1466 Generalized First Fall Degree Assumptions, IACR ePrint 2015. 1467 1469 [Nagao] K. Nagao. Equations System coming from Weil descent and 1470 subexponential attack for algebraic curve cryptosystem, IACR 1471 ePrint, 2015. 1473 Internet-Draft 2021-04-01 1475 [Teske] E. Teske. An Elliptic Curve Trapdoor System, IACR ePrint, 1476 2003. 1478 [YY] (((To do:))) Yung and Young, generalized Gordon's ideas into 1479 Secretly-embedded trapdoor ... also known as a backdoor. 1481 Appendix A. Why 2y^2=x^3+x/GF(8^91+5)? 1483 This section says why curve 2y^2=x^3+x/GF(8^91+5) can improve ECC, 1484 if used properly in multi-curve ECC. 1486 Note: Other sections (especially 4, 5, 6, B, C, and D) cover 1487 some relatively routine ECC details about how to use 1488 2y^2=x^3+x/GF(8^91+5). Section 8 covers some reasons why one 1489 might not want to use 2y^2=x^3+x/GF(8^91+5). 1491 A.1. Not for single-curve ECC 1493 Curve 2y^2=x^3+x/GF(8^91+5) is riskier than other IETF-approved 1494 curves, such as NIST P-256 and Curve25519, for at least the 1495 following reasons: 1497 - it is newer, so riskier, all else equal, and 1499 - it is special, with complex multiplication by i: consensus 1500 continues to agree with Miller's original 1985 opinion that 1501 using (such) special curves is not "prudent". 1503 Koblitz, Koblitz and Menezes [KKM] somewhat dissent from the 1504 consensus against special curves. They list several plausible cases 1505 of special curves -- including some with complex multiplication -- 1506 that they argue might well be safer than random curves. (Others go 1507 even further, dismissing prudence against special curves as myth 1508 [ref-tba].) 1510 Despite this dissent, this report adheres to the consensus, which is 1511 to prefer other curves for single-curve ECC. 1513 The relative newness of 2y^2=x^3+x/GF(8^91+5) is not entire. The 1514 curve equation is isomorphic to one proposed by Miller in 1985, 1515 making it older than the isomorphism class of curve equations in 1516 NIST P-256 or Curve25519. The field size, the prime 8^91+5=2^273+5, 1517 is a prime likely to have been considered before the field size 1518 primes NIST P-256 or Curve25519, but probably not in an application 1519 to ECC (i.e. probably in surveys of special primes). 1521 A.2. Risks of new curve-specific attacks 1522 Internet-Draft 2021-04-01 1524 A risk for all ECC is new curve-specific attacks, especially attacks 1525 on the elliptic curve discrete logarithm problem. A new 1526 curve-specific attack could break any ECC using the affected curves. 1528 The main benefit to ECC of curve 2y^2=x^3+x/GF(8^91+5) is to reduce 1529 this risk in multi-curve variant of ECC. 1531 Note: an arguably larger risk, a quantum computer capable of 1532 running Shor's algorithm, looms over all of ECC. The probability 1533 of this risk is basically independent of the probability new 1534 curve-specific attack, but the impacts are heavily dependent, if a 1535 quantum attack impacts ECC, then the new curve-specific attacks 1536 are totally moot. Also, even if no quantum attack on ECC emerges, 1537 but PQC supplements or replaces ECC, then a new curve-specific 1538 attack becomes much more tolerable. For sake of argument, suppose 1539 probabilities 1% for a new curve-specific attack by 2030, and 10% 1540 for a quantum-attack on ECC by 2030. Addressing the 10% 1541 probability risk is more urgent, but there is still a 90% chance 1542 that of no-quantum-attack. Assuming that PQC is combined with ECC 1543 (instead of replacing it) and assuming that the 10% and 1% 1544 probabilities above are formally independent, then there is 0.9% 1545 probability that new-curve specific on ECC by 2030 would affect 1546 PQC+ECC systems, reducing their security to that of PQC only. 1548 A.2.1. What would be considered a "new curve-specific" attack? 1550 The idea of new curve-specific attacks is now discussed. The 1551 purpose is to remind the reader of the risks, by comparison to past 1552 curve-specific attacks, so that a user can estimate the benefits of 1553 addressing the risk. Ultimately, the reader should make an informed 1554 as possible decision whether the extra cost of multi-curve is 1555 warranted. 1557 A.2.2.1. What would be considered a "new" attack? 1559 The "new" in "new curve-specific attack" means hypothetical and not 1560 yet published, and hence, either future or hidden. This 1561 contemplates an adversary with superior cryptanalytic capability 1562 than current state-of-the-art knowledge. 1564 A.2.2.2. What is, would be, considered a "curve-specific attack"? 1566 The "curve-specific" in "new curve-specific attack" means that the 1567 following conditions on the attack are true 1569 - it affects almost ECC algorithms using the specific curve 1570 (typically, if the discrete logarithm problem is easy for that 1571 curve, or in some cases, the decision Diffie--Hellman problem), 1573 Internet-Draft 2021-04-01 1575 - it does not affect ECC using at least one other curve 1576 (typically, many other curves), and 1578 - it would not affect a generic group of the same size of the 1579 secure ECC group. 1581 Note: For example, the naive Pollard-rho attack is not 1582 "curve-specific" because it fails the second condition and third 1583 condition (it affects all curves and all generic groups of equal 1584 or smaller size than the attacked curve). The Pohlig--Hellman 1585 attack (on smooth order groups) is not curve-specific because it 1586 fails the third condition. 1588 Note: A side-channel attack on an ECC implementation is not 1589 necessarily "curve-specific" in the strict sense above, if 1590 another ECC implementation using the same curve resists the 1591 attack. Some curves may be more prone than others to side-channel 1592 attacks, here we refer to that situation "curve-specific 1593 implementation-vulnerability". 1595 Prime-field curves were affected by two curve-specific attacks (on 1596 the discrete logarithm): the MOV attacks, and the SASS attack, both 1597 from before 2001. For the decision Diffie--Hellman problem, a 1598 generalization of the MOV attack can be considered as 1599 curve-specific. 1601 For non-prime-field curves, more recent curve-specific attacks have 1602 been discovered, some asymptotically polynomial-time. (To be 1603 completed.) 1605 A.2.2.3. Rarity of published curve-specific attacks 1607 To be completed. 1609 The known curve-specific attacks against prime-field curves are rare 1610 in the sense of having negligible probability of affecting a random 1611 curve (over a given prime-field). 1613 Some of these are attacks are also field-specific too. 1614 These attacks somewhat rare among all possible non-prime-field 1615 curves (though in some cases the probability among certain class of 1616 curves is non-negligible). 1618 Internet-Draft 2021-04-01 1620 If the rarity of the known curve-specific attacks carries over to 1621 any new curve-specific attacks, then truly random curves should 1622 resist the new curve-specific attacks, except with negligible 1623 probability. Honestly generated, non-random curves should also 1624 resist the new curve-specific attacks, except in the unfortunate 1625 case the new curve-specific attack is correlated with the honest 1626 curve generation criteria. 1628 A.2.2.4. Correlation of curve-specific efficiency and attacks 1630 To be completed. 1632 Many of the known curve-specific attacks affected previously 1633 proposed curves, and presumably honestly generated curves. For 1634 example, supersingular curves were proposed for their slightly 1635 greater efficiency over ordinary curves, but then turned out to be 1636 vulnerable to the MOV attack. (Similarly, curves vulnerable to the 1637 SASS attack were proposed for slight efficiencies, before the SASS 1638 attack was published.) So, such correlations are not only 1639 plausible, but the real-world pattern for ECC. Accidents have 1640 already happened for such non-random curves. 1642 Worse yet, if a non-random curve is chosen maliciously, a 1643 correlation between a hidden curve-specific attack and some sensible 1644 curve generation criteria might well make it possible for a 1645 maliciously chosen non-random curve to be made vulnerable to a 1646 hidden curve-specific attack. 1648 A.3. Mitigations against new curve-specific attacks 1650 Because the risk of new curve-specific attack is nonzero, applying 1651 mitigations against the risk potentially improves security, albeit 1652 at some cost. 1654 A.3.1. Fixed curve mitigations 1656 Often, a single fixed curve is used across a system of ECC users, 1657 generally for reasons of efficiency. This exposes the system to the 1658 nonzero risk of new curve-specific attacks. 1660 A.3.1.2. Existing fixed-curve mitigations 1662 Some of the better established fixed curve have sensibly included 1663 mitigations against the nonzero risk of new curve-specific attacks. 1665 Internet-Draft 2021-04-01 1667 - NIST curve P-256 has coefficients derived from the output of 1668 SHA-1, perhaps aiming to avoid any new curve-specific weakness 1669 that would apply rarely to random curves, although inadequately 1670 so, because the seed input to the hash is utterly inexplicable, 1671 and plausibly manipulable. 1673 - Bernstein's Curve25519 results from a "rigid", non-random design 1674 process, favoring efficiency over all else, perhaps eliminating 1675 intentional subversion towards a new curve-specific weakness. 1677 - Brainpool's curves are derived using hash functions applied to 1678 nothing-up-my-sleeve numbers, perhaps aiming to mitigate both 1679 intentional subversion and accidental rare weakness. 1681 Note: A reasonable inference from these curves is that risk of new 1682 curve-specific attacks warranted the mitigations used (as listed 1683 above). The risk may be less now that further time has passed, 1684 because no other curve-specific attacks against prime-field curves 1685 arose in the interim. The risk is still not zero, so the 1686 mitigations may still be warranted. 1688 A.3.1.2. Mitigations used by 2y^2=x^3+x/GF(8^91+5) 1690 The curve 2y^2=x^3+x/GF(8^91+5) includes similar fixed-curve 1691 mitigations against the risk of new curve-specific attacks: 1693 - a short description (low Kolmogorov complexity), aiming to have 1694 little wiggle for an intentional embedded weakness (somewhat like 1695 a nothing-up-my-sleeve number used in the Brainpool curves), 1697 - a set of special efficiencies, such as a curve endomorphism, 1698 Montgomery form, and fast field operation (somewhat like the 1699 "rigid" properties of Curve25519 favor efficiency as a mitigation 1700 to fight off intentional embedded weakness), 1702 - a prime field, to stay clear of recent curve-specific attacks on 1703 non-prime-field ECC. 1705 These mitigations do not suffice to justify its use in single-curve 1706 ECC (instead of more established non-special curves). 1708 Note: The mitigations above, like those of NIST P-256 and 1709 Curve25519, have a cost which consists mostly of a one-time 1710 computation. The mitigations are somewhat warranted, even if 1711 multi-curve ECC, because the aim of multi-curve is to hedge the 1712 risk of curve-specific attacks, so it makes sense for each 1713 individual curve to include mitigations against this risk. 1715 Internet-Draft 2021-04-01 1717 A.3.2. Multi-curve ECC 1719 This section further motivates the value of multi-curve ECC over 1720 single-curve ECC, but does specify a detailed way to do multi-curve 1721 ECC. 1723 Multi-curve ECC is only really effective if used with a diverse set 1724 of curves. Multi-curve ECC SHOULD use a set of curves including the 1725 three curves: 1727 NIST P-256, Curve25519, and 2y^2=x^3+x/GF(8^91+5). 1729 Multi-curve ECC aims to further mitigate the risk of curve-specific 1730 attack, by securely combining a diverse set of curves. The aim is 1731 that at least one of the curves used in multi-curve ECC resists a 1732 new curve-specific attack (if a new attack ever appears). This aim 1733 is only plausible if the set of curves used is diverse, in features 1734 or in authorship. 1736 This curve contributes to the diversity necessary for multi-curve 1737 ECC, with special technical features distinct from established 1738 curves NIST P-256 and Curve25519 (and Brainpool): 1740 - complex multiplication by i (low discriminant, rather than high), 1742 - a greater emphasis on low Kolmogorov descriptional complexity 1743 (rather than hashed coefficient or efficiency). 1745 A.3.2.1. Multi-curve ECC is a redundancy strategy 1747 Multi-curve ECC is an instance of a strategy often called 1748 redundancy, applied to ECC. Redundancy is quite general in that it 1749 can be applied to other types of cryptography, to other types of 1750 information security, and even to safety systems. Other names for 1751 redundant strategies include: 1753 strongest-link, defense-in-depth, hybrid, hedged, composite, 1754 fail-safe, diversified, resilient, belt-and-suspenders, fault 1755 tolerant, robust, multi-layer, robustness, compound, combination, 1756 etc. 1758 A.3.2.2. Whether to use multi-ECC 1760 Multi-curve ECC mitigates the risk of new curve-specific attacks, so 1761 ought to be used instead of single-curve ECC if affordable, such as 1762 when 1764 Internet-Draft 2021-04-01 1766 - the privacy of the data being protected has higher value than 1767 the extra cost of multi-curve ECC, which may be the case for at 1768 least financial, medical, or personally-identifying data, and 1770 - ECC is only a tiny portion of the overall system costs, which 1771 would be the case if the data is human-generated or high-volume, 1772 or if ECC is combined with slow or large post-quantum 1773 cryptography (PQC). 1775 A.3.2.2.1. Benefits of multi-curve ECC 1777 The benefit of multi-curve ECC is difficult to quantify. The aimed 1778 benefit over single-curve ECC is extra security, in the event of a 1779 significant curve-specific attack. 1781 No extra security results if all the curves used are the same. The 1782 curves must be diverse, so that a potential attack on one is somehow 1783 unlikely to affect the other. This diversity is difficult to 1784 assess. Intuitively, a geometric metaphor of a polygon for the 1785 space of all choices might help. Maximally distant points in a 1786 polygon tend to be vertices, the extremities of the polygon. 1787 Translating this intuition suggests choosing curves at the extremes 1788 of features. 1790 Note: By contrast, in a single-curve ECC, the geometric 1791 metaphor suggests a central internal point, on the grounds that 1792 each vertex is more likely to be affected to a special attack. 1793 Carrying this over to multi-curve suggests that a diverse set 1794 ought to include a non-extreme curve too. 1796 As always, the benefit of security is really the negative of the 1797 cost of an attack, including the risk. 1799 The contextual benefit of multi-curve ECC therefore depends very 1800 much on the application, involving the assessing both the 1801 probability of attack, and the impact of the attack. 1803 Higher value private data has greater impact if attacked, and 1804 perhaps also higher probability, if the adversary is more motivated 1805 to attack it. 1807 Low probability of attacks are mostly inferred through failed but 1808 extensive cryptanalysis efforts. Normally, this is only intuited, 1809 but approaches to quantifiably estimate these probabilities is 1810 possible too, under sufficiently strong assumptions. 1812 To be completed. 1814 Internet-Draft 2021-04-01 1816 A.3.2.2.2. Costs of multi-curve ECC 1818 The cost of multi-curve ECC is fairly easy to quantify (easier than 1819 quantifying the benefit). 1821 The cost of multi-curve is meant to be compared to the cost of 1822 single-curve ECC. 1824 The cost ratio is approximately the number of curves used. The cost 1825 difference depends on the devices implementing the ECC. 1827 For example, on a current personal computer, the extra cost per ECC 1828 transaction can include up to 1 millisecond of runtime and sending 1829 an extra 30 bytes or more. In low-end devices, the time may be 1830 higher due to slower processors. 1832 The contextual cost of ECC depends on the application context. In 1833 some applications, such as personal messages between two users, the 1834 cost (milliseconds and a few hundred bytes) is affordable relative 1835 to the time users spent writing and reading the messages. In other 1836 applications, such as automated inter-device communication with 1837 frequent brief messages, single-curve ECC may already be a 1838 bottleneck, costing most of the run-time. 1840 A.3.2.3. Applying multi-curve ECC 1842 For key establishment, NIST recently proposed (in a draft amendment 1843 to Special Publication 800-133 on key derivation) a mechanism to 1844 support deriving a single symmetric key from the result of multiple 1845 key establishments. In summary, the mechanism is that the raw ECDH 1846 shared secrets would be concatenated and fed into a hash-based key 1847 derivation function. 1849 An alternative would be to XOR multiple shared symmetric-key 1850 together. 1852 So, multi-curve elliptic curve Diffie--Hellman (ECDH) key agreement 1853 could use one of these mechanism to derive a single key from 1854 multi-curve ECDH. 1856 A mechanism to support sending more than one ECDH public key 1857 (usually ephemeral), with an indication of the curve for each ECDH 1858 key, would also be needed. 1860 For signatures, the simplest approach is to attach multiple 1861 signatures to each message. (For signatures providing message 1862 recovery, then an approach is to apply the results, with outer 1863 signatures recover the inner signed message, and so on.) 1865 Internet-Draft 2021-04-01 1867 A.4. General features of curve 2y^2=x^3+x/GF(8^91+5) 1869 This subsection describes some general features of the curve 1871 2y^2=x^3+x/GF(8^91+5), 1873 presuming a familiarity with elliptic curve cryptography (ECC). 1875 Each of a set of well-established features, such as Pollard rho 1876 security or Montgomery form, for ECC in general are evaluated and 1877 summarized for the specific curve 2y^2=x^3+x/GF(8^91+5). 1879 Note: Interoperable ECC requires a few more details than are 1880 deducible from mathematical description 2y^2=x^3+x/GF(8^91+5) of 1881 the curve, such encoding points as byte strings. These details 1882 are discussed in Sections 4, 5, and 6. 1884 A.4.1. Field features 1886 The curve's field of definition, GF(8^91+5), is a finite field, as 1887 is always the case in ECC. (Finite fields are Galois field, and the 1888 field of size is p is written as GF(p).) 1890 The field size is the prime p=8^91+5. (See the appendix for a 1891 Pratt primality certificate.) 1893 In hexadecimal (base 16, big-endian) notation, the number 8^91+5 is 1895 200000000000000000000000000000000000000000000000000000000000000000005 1897 with with 67 zeros between 2 and 5. 1899 The most recent known curve-specific attacks on 1900 prime-field ECC are from 2000. 1902 Prime fields in ECC tend be more efficient in software than in 1903 hardware. 1905 The prime p is very close to a power of two. Primes very close to a 1906 power of two are sometimes known as Crandall primes. Reduction 1907 modulo p is more efficient for Crandall primes than for most other 1908 primes (or at least random primes). Perhaps Crandall primes are 1909 more resistant to side-channel attacks or implementation faults than 1910 than most other primes. 1912 Internet-Draft 2021-04-01 1914 The fact that p is slightly larger than a power of two -- rather 1915 than slightly lower -- means that powering algorithms to compute 1916 inverses, Legendre symbols, and square roots are simpler and 1917 slightly more efficient (than would be for prime below a 2-power). 1919 A.4.3. Equation features 1921 The curve equation 2y^2=x^3+x has Montgomery form, 1923 by^2=x^3+ax^2+x, 1925 with (a,b) = (0,2). This permits the Montgomery ladder scalar point 1926 multiplication algorithm to be used, which makes it relatively 1927 efficient, and also easier to protect against side channels. 1929 The curve 2y^2=x^3+x has complex multiplication by i, meaning an 1930 endomorphism 1932 (x,y) -> (-x,iy). 1934 Note: Strictly speaking, over some fields, the curve the curve has 1935 quaternionic multiplication (where it is said to be 1936 supersingular), in which case, the term "complex multiplication" 1937 is not the best fit. 1939 The endomorphism permits the Gallant--Lambert--Vanstone (GLV) scalar 1940 multiplication algorithm, which makes it relatively efficient. See 1941 [B4] for a discussion of combining GLV with 1942 Hisil--Wong--Carter--Dawson arithmetic for twisted Edwards 1943 coordinates, as it applies to 2y^2=x^3+x/GF(8^91+5). 1945 The GLV method can also be combined with Bernstein's two-dimensional 1946 variant of the Montgomery ladder algorithm. See [B1] for some 1947 discussion. 1949 The curve has j-invariant 1728, because it has complex 1950 multiplication by i. 1952 Note: The j-invariants 0 and 1728 are special in that the curves 1953 with these j-invariants have more than two automorphisms. 1954 (Relatedly, over complex numbers, the moduli space of elliptic 1955 curves is an orbifold, with exactly two non-smooth points, at j=0 1956 and j=1728.) 1958 A.4.4. Finite curve features 1959 Internet-Draft 2021-04-01 1961 This section describes features of 2y^2=x^3+x/GF(8^91+5) as a finite 1962 curve consisting, the points (x,y) for x,y in GF(p), and also the 1963 point at infinity. In other words, these features are specific to 1964 the combination of both the finite field and the curve equation. 1966 Note: In algebraic geometry, these points are said to rational 1967 over k=GF(p), and the set of rational points written as E[k] = 1968 (2y^2=x^3+x)[GF(8^91+5)], to distinguish from points with 1969 coordinates in the algebraic closure of k=GF(p). 1971 Many security properties, and a few performance properties, of ECC 1972 are specific to a finite curve. 1974 A.4.4.1. Curve size and cofactor 1976 The curve (of points rational over GF(8^91+5)) has size (order) 72q 1977 for a large prime q, which is, in hexadecimal, 1979 71C71C71C71C71C71C71C71C71C71C71C7A4ACED12AE9418569B932B8A7B80438A9 1981 NOTE: Appendix E has a Pratt primality certificate for q. 1983 So, the curve has cofactor 72. 1985 The curve size can verified by implementing the curve's elliptic 1986 curve arithmetic, and scalar multiplying random points on the curve 1987 by the claimed size. 1989 The size can also be partially verified with the complex 1990 multiplication theory and a little big integer arithmetic, as 1991 reviewed below. 1993 The prime p=8^91+5 has p=1 mod 4, so a theorem of Fermat says there 1994 exist integers u and v such that p=u^2+v^2. Numbers u and v can 1995 found using a special case of Cornacchia's algorithm, and are listed 1996 further below. 1998 Complex multiplication theory says that a curve with complex 1999 multiplication by i has size s=(u+1)^2+v^2 = p+2u+1. By negation of 2000 u, and by swapping u and v, there are four possible sizes, p+2u+1, 2001 p-2u+1, p+2v+1, p-2v+1. These are known as the (quadratic) twist 2002 sizes. 2004 Curve 2y^2=x^3+x/GF(8^91+5) has one of these four sizes. In this 2005 case, its size s is divisible by 72, and has large prime factor q = 2006 s / 72. 2008 Internet-Draft 2021-04-01 2010 The following 'bc' program includes values for u and v applicable to 2011 2y^2=x^3+x/GF(8^91+5), verifies these calculations, and outputs q. 2013 p = 8^91+5 2014 u = 104303302790113346778702926977288705144769 2015 v = 65558536801757875228360405858731806281506 2016 if ( p != u^2+v^2 ) { "u and v incorrect" ; halt } 2017 s = (u+1)^2 + v^2 2018 if ( 0 != (s % 72)) { "size not divisible by 72" ; halt} 2019 q = s/72 2020 q 2022 Note: Theory only indicates that s has one of four values, so an 2023 extra step is needed to verify which of the four values is the 2024 size. Scalar multiplication by s is a general method. A faster 2025 method, which happens to work for 2y^2=x^3+x/GF(8^91+5), is to 2026 show that only one of the four candidate sizes is divisible by 3, 2027 and then demonstrate a point of order 3 on this curve. Symbolic 2028 calculation with elliptic curve arithmetic show that the point 2029 (x,y) has order 3 if 3x^4 + 1 = 0 in GF(p). The big integer 2030 calculation (-(1+2p)/3)^((p-1)/4) = 1 mod p shows that such an x 2031 exists in GF(p). 2033 Note: The Schoof--Elkies--Atkin (SEA) point-counting algorithm can 2034 compute the size of any general curve, but is slower than methods 2035 for some special curves, which is why Miller had already suggested 2036 in 1985 to use special curves with equation y^2=x^3-ax. Miller 2037 suggested using supersingular curves, but restriction of the 2038 coefficient a, but those curves are insecure. Instead, we have 2039 chosen a different a (in this case a=-1 is isomorphic to 2040 2y^2=x^3+x), which is not supersingular, but still has much easier 2041 point counting than the generic SEA algorithm. 2043 A.4.4.2. Pollard rho security 2045 The prime q is 267-bit number. The Pollard rho algorithm for 2046 discrete logarithm to the base G (or any order q point) takes 2047 (proportional to) sqrt(q) ~ 2^133 elliptic curve operations. The 2048 curve provides at least 2^128 security against Pollard rho attacks, 2049 with about 5 bits to spare. 2051 Internet-Draft 2021-04-01 2053 Note: Arguably, the fact ECC operations are slower than 2054 symmetric-key operations (such as hashing or block ciphers), 2055 means that ECC security should be granted a few extra bits, 2056 perhaps 5-10 bits, of security when trying to match ECC security 2057 with symmetric-key security. In this case, one might say that 2058 2y^2=x^3+x/GF(8^91+5) resists Pollard-rho with 2^140 security, 2059 providing 12 bits of extra security. The extra security can be 2060 viewed as a safety margin for error, or as an excessive to the 2061 extent the smaller, and faster curves would more than suffice to 2062 match 2^128 security of SHA-256 and AES-128. 2064 Gallant, Lambert, Vanstone, show how to speed up Pollard rho 2065 algorithms when the group has an extra endomorphism, which would 2066 apply to 2y^2=x^3+x. The speed-up here amounts to a couple of bits 2067 in the security, 2069 A.4.4.3. Pohlig--Hellman security 2071 The small cofactor means the curve effectively resists 2072 Pohlig--Hellman attack (a generic algorithm to solve discrete 2073 logarithms in any group in time sqrt(m) where m is the largest 2074 prime factor of the group size). 2076 Note: Consensus in ECC is to recommend a small factor, such as 1, 2077 2, 4, or 8, despite the fact that, for random curves, the typical 2078 cofactor is approximately p^(1/3), which is much larger. The 2079 small cofactor helps resists Pohlig--Hellman without increasing 2080 the field size. (A larger field size would be less efficient.) 2082 A.4.4.2. Menezes--Okamoto--Vanstone security 2084 The curve has a large embedding degree. More precisely, the curve 2085 size 72q has q with embedding degree (q-1)/2. 2087 This means that the discrete logarithms to base G (a point of order 2088 q) resist Menezes--Okamoto--Vanstone attack. 2090 The large embedding degree also means that that no feasible pairings 2091 exist that could be used solve the decision Diffie--Hellman problem 2092 (for points of order q). Similarly, the larger embedding degree 2093 also means, it cannot be used for pairing-based cryptography (and it 2094 would already too small to be used for pairing-based cryptography). 2096 Internet-Draft 2021-04-01 2098 Note: Intuitively, a near-miss or a close-call could describe this 2099 curve's resistance to the MOV attack. For about half of all primes 2100 P, then curve 2y^2=x^3+x is supersingular over GF(P), with 2101 embedding degree 2, making them vulnerable to the MOV attack 2102 reduces the elliptic curve discrete logarithm to the finite field 2103 discrete logarithm over GF(P^2). Miller suggested in 1985 to use 2104 isomorphic equations, y^2=x^3-ax, without knowing about the 1992 2105 MOV attack. These special curves would then be vulnerable with 2106 ~50% chance of being, depending on the prime P. This curve was 2107 chosen in full knowledge of the MOV attack. 2109 Note: The near-miss or close-call intuition is misleading, because 2110 many cryptographic algorithms become insecure based on the 2111 slightest adjustment to the algorithm. 2113 Note: The non-supersingularity means that the endomorphism ring is 2114 commutative. For this curve the endomorphism ring is isomorphic 2115 to the ring Z[i] of Gaussian integers. 2117 A.4.4.3. Semaev--Araki--Satoh--Smart security 2119 The fact that the curve size 72q does not equal p, means that the 2120 curve resists the Semaev--Araki--Satoh--Smart attack. 2122 A.4.4.4. Edwards and Hessian form 2124 The cofactor 72 is divisible by 4, so the curve isomorphic to a 2125 curve with an Edwards equation, permitting implementation even more 2126 efficient than the Montgomery ladder. 2128 The Edwards form makes possible the Gallant--Lambert--Vanstone 2129 method that used the efficient endomorphism. 2131 The cofactor 72 is also divisible by 3, so the curve is isomorphic 2132 to a curve with a Hessian equation, which is another type of 2133 equation permitting efficient implementation. 2135 Note: It is probably too optimistic and speculative to hope that 2136 future research will show how to take advantage by combining the 2137 efficiencies of Edwards and Hessian curve equations. 2139 A.4.4.5. Bleichenbacher security 2140 Internet-Draft 2021-04-01 2142 Bleichenbacher's attack against faulty implementations 2143 discrete-log-based signatures fully affects 2y^2=x^3+x/GF(8^91+5), 2144 because the base point order q is not particularly close to a power 2145 of two. (Some other curves, such as NIST P-256 and Curve25519, have 2146 the base point order is close to a power of two, which provides 2147 built-in resistant to Bleichenbacher's faulty signature attack.) 2149 Note: Bleichenbacher's attack exploits the signature implementation 2150 fault of naively reducing uniformly random bit strings modulo q, 2151 the order of the base point, which results in a number biased 2152 towards the lower end of the interval [0,q-1]. 2154 So, q-uniformization of the pre-message secret numbers is critical 2155 for signature applications of 2y^2=x^3+x/GF(8^91+5). Various 2156 uniformization methods are known, such as reducing extra large 2157 numbers, repeated sampling, and so on. 2159 A.4.4.6. Bernstein's "twist" security 2161 Unlike Curve25519, curve 2y^2=x^3+x/GF(8^91+5) is not 2162 "twist-secure", so a Montgomery ladder implementation for static 2163 private keys often requires public-key validation, which is 2164 achievable by computation of a Legendre symbol related to the 2165 received public key. 2167 In particular, a Montgomery ladder x-only implementation that does 2168 not implement public-key validation will process a value x for which 2169 no y satisfying the equation exists in GF(p). More precisely, a y 2170 does exist, but it belongs to the extension field GF(p^2). In this 2171 case, the Montgomery ladder treats x as though it were (x,y) where x 2172 is GF(p) but y is not. Such points belong to a "twist" group, and 2173 this group has order: 2175 2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 * 2176 3452464930451677330036005252040328546941 2178 An adversary can exploit this, by finding such invalid x that 2179 correspond to a lower order group element, and thereby try to learn 2180 partial information about a static private key used by a 2181 non-validating Montgomery ladder implementation. 2183 A.4.4.7. Cheon security 2185 Niche applications in ECC involve revealing points [d^e]G for one 2186 secret number d, and many different integer e, or at least one large 2187 e. One way such points could be reveal is in protocols that employ 2188 a static Diffie--Hellman oracle, a function to compute [d]P from any 2189 point P, which might be applied e times, if e is reasonably small. 2191 Internet-Draft 2021-04-01 2193 Typical ECDH, to be clear, would never reveal such points, for at 2194 least two reasons: 2196 - ECDH is ephemeral, so that the same d is never re-used across 2197 ECDH sessions (because d is used to compute [d]G and [d]Q, and 2198 then discarded), 2200 - ECDH is hashed, so though P=[d]G is sent, the point [d]Q is 2201 hashed to get k = H([d]Q), and then [d]Q is discarded, so the 2202 fact that hash is one-way means that k should not reveal [d]Q, 2203 if k is ever somehow revealed. 2205 The Brown--Gallant--Cheon q-1 algorithm finds d, given [d^e]G, if 2206 e|(q-1). It uses approximately sqrt(q/e) elliptic curve operations. 2207 The Cheon q+1 algorithm finds d, given all the points [d]G, [d^2]G, 2208 ..., [d^e]G, if e|(q+1), and takes a similar amount of computation. 2209 These two algorithms rely on factors e of q-1 or q+1, so the 2210 factorization of these numbers affects the security against the 2211 algorithm. 2213 Cheon security refers to the ability to resist these algorithms. 2215 It is possible seek out special curves with relatively high Cheon 2216 security, because q-1 and q+1 have no suitable factors e. 2218 The curve 2y^2=x^3+x/GF(8^91+5) has typical Cheon security in terms 2219 of the factorization of q-1 and q+1. Therefore, in the niche 2220 applications that reveal the requisite points, mitigations ought to 2221 be applied, such as limiting the rate of revealing points, or using 2222 different value d as much as possible (one d per recipient). 2224 For 2y^2=x^3+x/GF(8^91+5) the factorization of q-1 and q+1 are: 2226 q-1 = 2^3 * 101203 * 23810182454264420359 * 2227 10934784357463776473342498062299965925956115086976992657 2228 and 2230 q+1 = 2 * 3 * 11 * 21577 * 54829 * 392473 * 854041 * 2231 8054201530811151253753936635581206856381779711451564813041 2233 Internet-Draft 2021-04-01 2235 The q-1 and q+1 algorithms convert an oracle for function P -> [d]P 2236 into a way to find d. This may be viewed as a reduction of the 2237 discrete logarithm problem to the problem of computing the function 2238 P -> [d]P for the target d. In other words, computing P -> [d]P is 2239 almost as difficulty as solving the discrete logarithm problem. In 2240 many systems with a static Diffie--Hellman secret d, computing the 2241 function P -> [d]P needs to be difficult, or the security will be 2242 defeated. In these case, an efficient q-1 or q+1 algorithm provides 2243 a security assurance, that the computing P -> [d]P without knowing d 2244 is about as hard as solving the discrete logarithm problem. 2246 To be completed. 2248 A.4.4.8 Reductionist security assurance for Diffie--Hellman 2250 A series of research work, from den Boer, from Maurer and Wolf, and 2251 from Boneh and Lipton, shows that Diffie--Hellman oracle can be used 2252 to solve a discrete logarithm, under certain conditions. In other 2253 words, the discrete logarithm problem can sometimes be reduced to 2254 the Diffie--Hellman problem. 2256 This can be interpreted as a security assurance that Diffie--Hellman 2257 problem is at least as hard the discrete logarithm problem, albeit 2258 perhaps with some gap in the difficulty. This formalized security 2259 assurance supplements the standard conjecture that the 2260 Diffie--Hellman problem is at least as hard as the discrete 2261 logarithm. (A contrarian view is that special conditions under 2262 which such a reduction algorithm is possible might coincide with 2263 special conditions under which the discrete logarithm problem is 2264 easier.) 2266 The general idea is to consider a Diffie--Hellman oracle in a group 2267 of order q to provide multiplication in a special representation 2268 field of order q. Recovering the ordinary field representation from 2269 the special field representation amounts to solving the discrete 2270 logarithm problem. 2272 To recover the ordinary representation, the idea is to construct an 2273 auxiliary group of smooth order, where the group is an algebraic 2274 groups over the field of size q. Solving a discrete logarithm in 2275 the auxiliary group is possible using the Pohlig--Hellman problem, 2276 and solving the discrete logarithm in the auxiliary reveals the 2277 ordinary representation of the field, which, as already noted 2278 reveals the discrete logarithm in the original group. 2280 Internet-Draft 2021-04-01 2282 The most obvious auxiliary groups have orders q-1 and q+1, but these 2283 are not smooth numbers. The next most obvious auxiliary are 2284 elliptic curve groups with complex multiplication by i, but none of 2285 these four group have smooth orders either. 2287 A peculiar strategy to show the existence of an auxiliary group of 2288 smooth order without having any effective means of constructing the 2289 group. This can be done by finding a smooth number in the Hasse 2290 interval of q. 2292 To be completed. 2294 Appendix B. Test vectors 2296 The following are some test vectors, with values explained further 2297 below. 2299 000000000000000029352b31395e382846472f782b335e783d325e79322054534554 2300 00000000000000000000000000000000000000000000000000000000000000000117 2301 c8c0f2f404a9fabc91c939d8ea1b9e258d82e21a427b549f05c832cf8d48296ffad7 2302 5f336f56f86de3d52b0eab85e527f2ac7b9d77605c0d5018f5faa4243fd462b1badd 2303 fc023b3f03b469dca32446db80d9b388d753cc77aa4c3ee7e2bb86e99e7bed38f509 2304 8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221 2305 8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221 2307 The test vectors are explained as follows. (Pseudocode generating 2308 them is supplied in Appendix C.2.) 2310 Each line is 34 bytes, representing a non-negative 272-bit integer. 2311 The integer encoding is hexadecimal, with most significant hex 2312 digits on the left, which is to say, big-endian. 2314 Note: Public keys are encoded as 34-byte strings are 2315 little-endian. Encoded public keys reverse the order of the bytes 2316 found in the test vectors. The pseudocode in Appendix C.2 should 2317 make this clear: since bytes are printed in reverse order. 2319 Each integer is either a scalar (a multiplier of curve points), or 2320 the byte representation of a point P through its x-coordinate or the 2321 x-coordinate of iP (which is the the mod 8^91+5 negation of the 2322 x-coordinate of P). 2324 The first line is a scalar integer x. Its nonzero bytes are the 2325 ASCII representation of the string "TEST 2y^2=x^3+x/GF(8^91+5)", 2326 with the byte order reversed. As a private key, this value of x 2327 would be totally insecure, because it is too small, and like any 2328 test vector, it is public. 2330 Internet-Draft 2021-04-01 2332 The second line is a representation of G, a base point on the curve. 2334 The third line is the representation of z = xG. 2336 The fourth and fifth lines represent updated values of x and z, 2337 obtained after application of the following 100000 scalar 2338 multiplications. 2340 A loop of 50000 iterations is performed. Each iteration consists of 2341 two re-assignments: z = xz and x = zG via scalar multiplications. 2342 In the second assignment, the byte representation of the input point 2343 z is used as the byte representation of an scalar. Similarly, the 2344 output x is the byte representation of the point, which is will used 2345 as as the byte representation of the scalar. 2347 The purpose of the large number of iterations is to catch a bug that 2348 has probability larger than 1/100000 of arising on pseudorandom 2349 inputs. The iterations do nothing to find rarer bugs (such as those 2350 that an adversary can invoke), or silent bugs (side channel leaks). 2352 The sixth and seventh lines are equal to each other. As explained 2353 below, the equality of these lines represents the fact the Alice and 2354 Bob can compute the same shared DH secret. The purpose of these 2355 lines is not to catch any more bugs, but rather a sanity check that 2356 Diffie--Hellman is likely to work. 2358 Alice initializes her DH private key to x, as already computed on 2359 the fourth line of the test vectors (which was the result of 100000 2360 iterations). She then replaces this x by x^900 mod q (where q is 2361 the prime which is the order of the order of the base point G). 2363 Bob sets his private key y as follows. He begins with y being the 2364 34-byte ASCII string whose initial characters are "yet another test" 2365 (not including the quotes, of course). He then reverses the order 2366 of bytes, considers this to be a scalar, and reassigns y to yG. 2367 (So, the y on the left is new, the y on the right is old, they are 2368 not the same, after the assignment.) Another reassignment is done, 2369 as y -> yy, where the on the right side of the equation one y is 2370 treated as a scalar, the other as a point. Finally, Bob's replaces 2371 y by y^900 mod order(G), similarly to Alice's transformation. 2373 The test code in C.2 does not compute x^900 directly. Instead it 2374 uses 900 scalar multiplication by x, to achieve multiplication by 2375 x^900. The same is done for y^900. 2377 Internet-Draft 2021-04-01 2379 Both lines are xyG. The first can be computed as y(xG), and the 2380 second as x(yG). The equality of the two lines can be used to 2381 self-test an implementation, even if the implementation being tested 2382 disagrees with the test vectors above. 2384 Appendix C. Sample code (pseudocode) 2386 This section has sample C code that illustrates well-known elliptic 2387 algorithms, with adaptations specific to 2y^2=x^3+x/GF(8^91+5). 2389 Warning: the sample code has not been fully hardened against 2390 side channels or any other implementation attacks; also, no 2391 independent party has reviewed the sample code. 2393 Note: The quality of the sample code is similar to pseudocode, not 2394 reference code, or software. It compiles and runs on my personal 2395 devices, but has not otherwise been tested for quality. 2397 Note: Non-standard C language extensions are used the sample code: 2398 the type __int128, available as an C language extension in the GNU 2399 C compiler (gcc). 2401 Note: Non-portable C is used (beyond the non-standard C), for 2402 convenience. Two's complement integer representation of integers 2403 is assumed. Bit-shifts negative integers are used, in a way that 2404 considered non-portable under strict C, even though commonly used 2405 elsewhere. 2407 Note: Manually minified C is used: to reduce line and character 2408 counts, and also to (arguably) aid objective code inspection by 2409 cramming as much code into a single screen and by not misleading 2410 reviewers with long comments or variable names. 2412 Note: Automated tools, such as indent (used as in "gcc -E pseudo.c 2413 | indent"), can partially revert the C sample code spacing to a 2414 more conventional style, though other aspects of minification are 2415 not so easy to remove. 2417 Note: The minification is not total. It tries to organize the 2418 code into meaningful units, such as placing single short functions 2419 on one line or placing all variable declarations on the same line 2420 with the function parameters. Python-like indentation is kept. 2421 (Per Lisp styling, the code clumps closing delimiters (that mainly 2422 serve the compilers.)) 2424 Internet-Draft 2021-04-01 2426 Note: Long sequence expressions, using the C comma operator, in 2427 place of multiple expression statements, which would be more 2428 conventional and terminated by semicolons, save some braces in 2429 control statements, such as "for" loops and "if" conditionals, and 2430 enable extra initializations in declarations. 2432 C.1. Scalar multiplication of 34-byte strings 2434 The sample code for scalar multiplication provides an interface for 2435 scalar multiplication. A function "mulch" takes as input 3 pointer 2436 to unsigned character strings. The first input is the location 2437 of the result, the second is the multiplier, and the third is the 2438 base point. 2440 Note: The input ordering follows the convention of C assignment 2441 expressions z=x*y. 2443 Note: The function name "mulch" is short for multiply character 2444 strings. 2446 Mulch returns a Boolean value, indicating success or failure. 2447 Failure is returned only if validation is requested, and the base 2448 point is invalid. 2450 Requesting validation is done implicitly, by comparison of pointers. 2451 Validation is requested unless the base point is the known valid 2452 base point G, or if the scalar multiple (2nd input) and the output 2453 (1st input) pointers are equal, meaning that the scalar multiple 2454 will be overwritten. 2456 Note: The motivation here for implicitly requesting validation is 2457 that if the scalar multiple is really ephemeral, the caller should 2458 be willing, and eager, to overwrite it as soon as possible, in 2459 order to achieve forward secrecy. In this case, the need for 2460 input validation is usually negligible. 2462 The sample code is to be considered as a single file, pseudo.c. 2464 The file pseudo.c has two sections. The first section implements 2465 arithmetic for the field GF(8^91+5). The second section implements 2466 Montgomery's ladder for curve 2y^2=x^3+x. The two sections are not 2467 entirely independent. In particular, the field arithmetic section 2468 is not general-purpose, and could produce errors if used for 2469 different elliptic curve algorithms, such as Edwards coordinates. 2471 Note: The scalar multiplication sample code pseudo.c file is 2472 included into 3 other sample (using a the C preprocessor directive 2473 #include "pseudo.c"). 2475 Internet-Draft 2021-04-01 2477 Note: Compiler optimizations make a large difference when used on 2478 the field arithmetic (for versions of the sample code where the 2479 field and curve arithmetic are in separate source files). This 2480 suggests that field arithmetic efficiency has room for further 2481 improvement by hand assembly. (The curve arithmetic might be 2482 improved by re-writing the source code.) In case, the sample code 2483 should not be considered to fully optimized. 2485 Note: Montgomery's ladder might not be the fastest scalar 2486 multiplication algorithm for 2y^2=x^3+x/GF(8^91+5). Experimental 2487 C implementations using Bernstein's 2-D ladder algorithm (see 2488 [B1]) seem about ~10% faster . The experimental code somewhat 2489 more complicated, and thus more likely to vulnerable to side 2490 channels or overflows. Even more aggressive C code seems about 2491 ~20% faster, using Edwards coordinates, 2492 Hisil--Carter--Dawson--Wong, and Gallant--Lambert--Vanstone, and 2493 pre-computed windows (see [B4]). Again, these faster methods are 2494 more complicated, and may be more vulnerable implementation 2495 attacks. The 10% and 20% gains may be lost upon more thorough 2496 hardening against implementation attacks, or upon more thorough 2497 hand-assembly optimizations. 2499 To be completed. 2501 C.1.1. Field arithmetic for GF(8^91+5) 2503 The field arithmetic sample code, is the first part of the file 2504 pseudo.c. It implements the field operations used in the Montgomery 2505 ladder algorithm for elliptic curve 2y^2=x^3+x. For example, point 2506 decompression is not used in Montgomery ladders, so the square root 2507 operation is not included the sample code. (The Legendre symbol 2508 computation is included for validation, and is quite similar to the 2509 square root operation.) 2511 Internet-Draft 2021-04-01 2513 2514 #define RZ return z 2515 #define F4j i j=5;for(;j--;) 2516 #define FIX(j,r,k) q=z[j]>>r, z[j]-=q<b)-(a>55*k&((k<2)*M-1)) 2520 #define MUL(m,E)\ 2521 zz[0]= m(0,0)E(1,4)E(2,3)E(3,2)E(4,1),\ 2522 zz[1]= m(0,1)m(1,0)E(2,4)E(3,3)E(4,2),\ 2523 zz[2]= m(0,2)m(1,1)m(2,0)E(3,4)E(4,3),\ 2524 zz[3]= m(0,3)m(1,2)m(2,1)m(3,0)E(4,4),\ 2525 zz[4]= m(0,4)m(1,3)m(2,2)m(3,1)m(4,0);\ 2526 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,\ 2527 z[2]=R(2,0)+R(1,1)+R(0,2), z[3]=R(3,0)+R(2,1)+R(1,2),\ 2528 z[4]=R(4,0)+R(3,1)+R(2,2); z[1]+=z[0]>>55; z[0]&=M-1; 2529 typedef long long i;typedef i*f,F[5];typedef __int128 ii,FF[5]; 2530 i M=((i)1)<<55;F O={0},I={1}; 2531 f fix(f z){i j=0,q; 2532 for(;j<5*2;j++) FIX(j%5,(j%5<4?55:53),(j%5<4?1:-5)); 2533 z[0]+=(q=z[0]<0)*5; z[4]+=q<<53; RZ;} 2534 i cmp(f x,f y){i z=(fix(x),fix(y),0); F4j z+=!z*CMP(x[j],y[j]); RZ;} 2535 f add(f z,f x,f y){F4j z[j]=x[j]+y[j]; RZ;} 2536 f sub(f z,f x,f y){F4j z[j]=x[j]-y[j]; RZ;} 2537 f mal(f z,i s,f y){F4j z[j]=y[j]*s; RZ;} 2538 f mul(f z,f x,f y){FF zz; MUL(+XY,-20*XY); {F4j zz[j]=0;} RZ;} 2539 f squ(f z,f x){mul(z,x,x); RZ;} 2540 i inv(f z){F t;i j=272; for(mul(z,z,squ(t,z));j--;) squ(t,t); 2541 return mul(z,t,z), (sub(t,t,t)), cmp(O,z);} 2542 i leg(f y){F t;i j=270; for(squ(t,squ(y,y));j--;) squ(t,t); 2543 return j=cmp(I,mul(y,y,t)), (sub(y,y,y),sub(t,t,t)), (2-j)%3-1;} 2544 2546 Field elements are stored as five-element of arrays of limbs. Each 2547 limb is an integer, possibly negative, with array z representing 2548 integer 2550 z[0] + z[1]*2^55 + z[2]*2^110 + z[3]*2^165 + z[4]*2^220 2552 In other words, the radix (base) is 2^55. Say that z has m-bit 2553 limbs if each |z[i]| < 2^m. 2555 Internet-Draft 2021-04-01 2557 The field arithmetic function input order follows the C assignment 2558 order, as input z=x*y, so usually the first input is the location 2559 for the result of the operation. The return value is usually just a 2560 pointer to the result's location, the first input, indicated by the 2561 preprocessor macro RZ. The functions, inv, cmp, and leg, also 2562 return an integer, which is not a field element, but usually a 2563 Boolean (or for function leg, a value in {-1,0,1}.) 2565 The utility functions are fix and cmp. They are meant to take 2566 inputs with 58-bit limbs, and produce an output with 55-bit 2567 non-negative limbs, with the highest limb, a 53-bit value. The 2568 purpose of fix is to provide a single array representation of each 2569 field element. The function cmp fixes both its inputs, and then 2570 returns a signed comparison indicator (in {-1,0,1}). 2572 The multiplicative functions are mul, squ, inv and leg. They are 2573 meant to take inputs with 58-bit limbs, and produce either an output 2574 with 57-bit limbs, or a small integer output. They try to do this 2575 as follows: 2577 1. Some of the input limbs are multiplied by 20, then multiplied 2578 in pairs to 128-bit limbs, and then summed in groups of five 2579 (with at least one of the pairs having both elements not 2580 multiplied by 20). The multiplications by 20 should not cause 2581 64-bit overflow 20*2^58 < 32*2^58=2^63, while the sums of 2582 128-bit numbers should not cause overflow, because 2583 (1+4*20)*2^58*2^58 = 81*2^116 < 2^7*2^116 = 2^123. 2585 2. The five 128-bit limbs are partially reduced to five 57-bit 2586 limbs. Each the five smaller limbs is obtained by summing two 2587 55-bit limbs, extracted from sections of the 128-bit limbs, and 2588 then summing one or two much smaller values summing to less 2589 than a 55-bit limb. So, the final limbs in the multiplication 2590 are a sum of at most three 55-bit sub-limbs, making each final 2591 limb at most a 57-bit limb. 2593 The additive functions are add, sub and mal. They are meant to take 2594 inputs with 57-bit limbs, and product an output with 58-bit limbs. 2596 The utility and multiplicative function can be used repeatedly, 2597 because they do not lengthen the limbs. 2599 Internet-Draft 2021-04-01 2601 The additive functions potentially increase the limb length, because 2602 they do not perform any reduction on the output. The additive 2603 functions should not be applied repeatedly. For example, if the 2604 output of additive additive function is fed directly as the input to 2605 an additive function, then the final output might have 59-bit 2606 limbs. In this case, if 2nd output might not be evaluated corrected 2607 if given as input to one of the multiplicative functions, an error 2608 due to overflow of 64-bit arithmetic might occur. 2610 The lack of reduction in the additive functions trades generality 2611 for efficiency. The elliptic curve arithmetic code aims to never 2612 send the output of an additive function directly into the input of 2613 another additive function. 2615 Note: Zeroizing temporary field values is attempted by subtracting 2616 them from themselves. Some compilers might remove these 2617 zeroization steps. 2619 Note: The defined types f and F are essentially the equivalent. 2620 The main difference is that type F is an array, so it can be used 2621 to allocate new memory (on the stack) for a field value. 2623 C.1.2. Montgomery ladder scalar multiplication 2625 The second part of the file "pseudo.c" implements Montgomery's 2626 well-known ladder algorithm for elliptic curve scalar point 2627 multiplication, as it applies to the curve 2y^2=x^3+x. 2629 The sample code, as part of the same file, is a continuation of the 2630 sample code for field arithmetic. All previous definitions are 2631 assumed. 2633 Internet-Draft 2021-04-01 2635 2636 #define X z[0] 2637 #define Z z[1] 2638 enum {B=34}; typedef void _;typedef volatile unsigned char *c,C[B]; 2639 typedef F*e,E[2];typedef E*v,V[2]; 2640 f feed(f x,c z){i j=((mal(x,0,x)),B); 2641 for(;j--;) x[j/7]+=((i)z[j])<<((8*j)%55); return fix(x);} 2642 c bite(c z,f x){F t;i j=((fix(mal(x,cmp(mal(t,-1,x),x),x))), B),k=5; 2643 for(;j--;) z[j]=x[j/7]>>((8*j)%55); {(sub(t,t,t));} 2644 for(;--k;) z[7*k-1]+=x[k]<<(8-k); {(sub(x,x,x));} RZ;} 2645 i lift(e z,f x,i t){F y;return mal(X,1,x),mal(Z,1,I),t|| 2646 -1==leg(add(y,x,mul(y,x,squ(y,x))));} 2647 i drop(f x,e z){return inv(Z)&&mul(x,X,Z)&&(sub(X,X,X)&&sub(Z,Z,Z));} 2648 _ let(e z,e y){i j=2;for(;j--;)mal(z[j],1,y[j]);} 2649 _ smv(v z,v y){i j=4;for(;j--;)add(((e)z)[j],((e)z)[j],((e)y)[j]);} 2650 v mav(v z,i a){i j=4;for(;j--;)mal(((e)z)[j],a,((e)z)[j]);RZ;} 2651 _ due(e z){F a,b,c,d; 2652 mul(X,squ(a,add(a,X,Z)),mal(d,2,squ(b,sub(b,X,Z)))); 2653 mul(Z,add(c,a,b),sub(d,a,b));} 2654 _ ade(e z,e u,f w){F a,b,c,d;f ad=a,bc=b; 2655 mul(ad,add(a,u[0],u[1]),sub(d,X,Z)), 2656 mul(bc,sub(b,u[0],u[1]),add(c,X,Z)); 2657 squ(X,add(X,ad,bc)),mul(Z,w,squ(Z,sub(Z,ad,bc)));} 2658 _ duv(v a,e z){ade(a[1],a[0],z[0]);due(a[0]);} 2659 v adv(v z,i b){V t; 2660 let(t[0],z[1]),let(t[1],z[0]);smv(mav(z,!b),mav(t,b));mav(t,0);RZ;} 2661 e mule(e z,c d){V a;E o={{1}};i 2662 b=0,c,n=(let(a[0],o),let(a[1],z),8*B); 2663 for(;n--;) c=1&d[n/8]>>n%8,duv(adv(a,c!=b),z),b=c; 2664 let(z,*adv(a,b)); (due(*mav(a,0))); RZ;} 2665 C G={23,1}; 2666 i mulch(c db,c d,c b){F x;E p; return 2667 lift(p,feed(x,b),(db==d||b==G))&&drop(x,mule(p,d))&&bite(db,x);} 2668 2670 This part of the sample code represents points and scalar 2671 multipliers as character strings of 34 bytes. 2673 Note: Types c and C are used for these 34-byte encodings. 2674 Following the previous pattern for f and F, type C is an array, 2675 used for allocating new memory (on the stack) for these arrays. 2677 The conversion functions feed and bite convert 2678 between a 34-byte string and a field value (recall, stored as five 2679 element array, base 2^55). 2681 Internet-Draft 2021-04-01 2683 The conversion functions lift and drop convert between field 2684 elements and the projective line point, so that x <-> (X:1). The 2685 function lift can also test if x is the x-coordinate of the a point 2686 (x,y) on the curve 2y^2=x^3+x. 2688 Note: Projective line points are stored in defined types e and E 2689 (for extended field element). 2691 Note: The Montgomery ladder can implemented by working with a 2692 pair of extended field elements. 2694 The raw scalar multiplication function "mule" takes a projective 2695 point (with defined type e), multiplies it by a scalar (encoded as 2696 byte string with defined type c), and then replaces the projective 2697 point by the multiple. 2699 The main loop of mule is written a double-and-always-add, acting on 2700 pair projective line points. Basically it acts on the x-coordinates 2701 of the points nB and (n+1)B, for n changing. 2703 Because the Montgomery ladder algorithm is being used, the "adv" 2704 called by mule function does nothing but swap the two values. With 2705 an appropriate isogeny, this can be viewed as addition operation. 2707 The function "duv" called by mule, does the hard work of finding 2708 (2n)B and (2n+1)B from nB and (n+1)B. It does so, using doubling in 2709 the function "due" and differential addition, in the function "ade". 2711 The functions "due" and "ade" are non-trivial, and use field 2712 arithmetic. They are fairly specific to 2y^2=x^3+x. They try to 2713 avoid repeated application of additive field operations. 2715 The function smv, mav and let are more utilitarian. They are used 2716 for initialization, swapping, and zeroization. 2718 C.1.3. Bernstein's 2-dimensional Montgomery ladder 2720 Bernstein's 2-dimensional ladder is a variant of Montgomery's ladder 2721 that computes aP+bQ, for any two points P and Q, more quickly than 2722 computing aP and bQ separately. 2724 Curve 2y^2=x^3+x has an efficient endomorphism, which allows a point 2725 Q = [i+1]P to compute efficiently. Gallant, Lambert and Vanstone 2726 introduced a method (now called the GLV method), to compute dP more 2727 efficiently, given such an efficient endomorphism. They write d = a 2728 + eb where e is the integer multiplier corresponding to the 2729 efficient endomorphism, and a and b are integers smaller than d. 2730 (For example, 17 bytes each instead of 34 bytes.) 2732 Internet-Draft 2021-04-01 2734 The GLV method can be combined with Bernstein's 2D ladder algorithm 2735 to be applied to compute dP = (a+be)P = aP + beP = aP + bQ, where 2736 e=i+1. 2738 This algorithm is not implemented by any pseudocode in the version 2739 the draft. (Previous versions had it.) 2741 See [B1] for further explanation and example pseudocode. 2743 I have estimate a ~10% speedup of this method compared to the plain 2744 Montgomery ladder. However, the code is more complicated, and 2745 potentially more vulnerable to implementation-based attacks. 2747 C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong) 2749 To be completed. 2751 It is also possible to convert to Edwards coordinates, and then use 2752 the Hisil--Wong--Carter--Dawson (HWCD) elliptic curve arithmetic. 2754 The HWCD arithmetic can be combined with the GLV techniques to 2755 obtain a scalar multiplication potentially more efficient than 2756 Bernstein's 2-dimensional Montgomery. The downside is that it may 2757 require key-dependent array look-ups, which can be a security risk. 2759 My implementation of this (see [B4]) gives a ~20% speed-up over my 2760 implementation of the Montgomery ladder. Of course, this speed-up 2761 may disappear upon further optimization (e.g. assembly), or further 2762 security hardening (safe table lookup code). 2764 C.2. Sample code for test vectors 2766 The following sample code describes the contents of a file "tv.c", 2767 with the purpose of generating the test vectors in Appendix B. 2769 Internet-Draft 2021-04-01 2771 2772 //gcc tv.c -o tv -O3 -flto -finline-limit=200;strip tv;time ./tv 2773 #include 2774 #include "pseudo.c" 2775 #define M mulch 2776 void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");} 2777 int main (void){i n=1e5,j=n/2,wait=/*your mileage may vary*/7000; 2778 C x="TEST 2y^2=x^3+x/GF(8^91+5)",y="yet another test",z; 2779 M(z,x,G); hx(x),hx(G),hx(z); 2780 fprintf(stderr,"%30s(wait=~%ds, ymmv)","",j/wait); 2781 for(;j--;)if(fprintf(stderr,"\r%7d\r",j),!(M(z,x,z)&&M(x,z,G))) 2782 j=0*printf("Mulch fail rate ~%f :(\n",(2*j)/n);//else//debug 2783 fprintf(stderr,"\r%30s \r",""),hx(x),hx(z); 2784 M(y,y,G);M(y,y,y); 2785 for(M(z,G,G),j=900;j--;)M(z,x,z);for(j=900;j--;)M(z,y,z);hx(z); 2786 for(M(z,G,G),j=900;j--;)M(z,y,z);for(j=900;j--;)M(z,x,z);hx(z);} 2787 2789 It includes the previously defined file pseudo.c, and the standard 2790 header file stdio.h. 2792 The first for-loop in main aims to terminate in the event of the bug 2793 such that the output of mulch is an invalid value, not on the curve 2794 2y^2=x^3+x. 2796 Of the 100,000 scalar multiplication in this for-loop, the aim is 2797 that 50,000 include public-key validation. All 100,000 include a 2798 field-inversion, to encode points uniquely as 34-byte strings. 2800 The second and three for-loops aims to test the compatibility with 2801 Diffie--Hellman, by showing the 900 applications of scalar 2802 multipliers x and y are the same, whether x or y is applied first. 2804 The 1st line comment suggest possible compilation commands, with 2805 some optimization options. The run-time depends on the system, and 2806 should be slower on older and weaker systems. 2808 Anecdotally, on a ~3 year-old personal computer, it runs in time as 2809 low as 5.7 seconds, but these were under totally uncontrolled 2810 conditions (with no objective benchmarking). (Experience has shown 2811 that on a ~10 year-old personal computer, it could be ~5 times 2812 slower.) 2814 C.3. Sample code for a command-line demo of Diffie--Hellman 2816 The next sample code is intended to demonstrate ephemeral (elliptic 2817 curve) Diffie--Hellman: (EC)DHE in TLS terminology. 2819 Internet-Draft 2021-04-01 2821 The code can be considered as a file "dhe.c". It has both C and bash 2822 code, intermixed within comments and strings. It is bilingual: a 2823 valid bash script and valid C source code. The file "dhe.c" can be 2824 made executable (using chmod, for example), so it can be run as a 2825 bash script. 2827 2828 #include "pseudo.c" /* dhe.c (also a bash script) 2829 : demos ephemeral DH, also creates, clobbers files dhba dha dhb 2830 : -- Dan Brown, BlackBerry, '20 */ 2831 #include 2832 _ get(c p,_*f){f&&fread ((_*)p,B,1,f)||mulch(p,p,G);} 2833 _ put(c p,_*f){f&&fwrite((_*)p,B,1,f)&&fflush(f); bite(p,O);} 2834 int main (_){C p="not validated",s="/dev/urandom" "\0"__TIME__; 2835 get(s,fopen((_*)s,"r")), mulch(p,s,G), put(p,stdout); 2836 get(p,stdin), mulch(s,s,p), put(s,stderr);} /*' 2837 [ dhe.c -nt dhe ]&&gcc -O2 dhe.c -o dhe&&strip dhe&&echo "$(/dev/null || ([ ! -p dhba ] && :> dhba) 2839 ./dhe dha | ./dhe >dhba 2>dhb & 2840 sha256sum dha & sha256sum dhb # these should be equal 2841 (for f in dh{a,b,ba} ; do [ -f $f ] && \rm -f $f; done)# '*/ 2842 2844 Run as a bash script, file "dhe.c" will check if it needs compile 2845 its own C code, into an executable named "dhe". Then the bash 2846 script file "dhe.c" runs the compiled executable "dhe" twice. One 2847 run is Alice's, and the other Bob's. 2849 Each run of "dhe" generates an ephemeral secret key, by reading the 2850 file "/dev/urandom". Each run then writes to "stdout", the 2851 ephemeral public key. Each run then reads the peer's ephemeral 2852 public key from "stdin". Each run then writes to "stderr" the 2853 shared Diffie--Hellman secret. (Public-key validation is mostly 2854 unnecessary, because the ephemeral is only used once, so it is 2855 skipped by using the same pointer location for the ephemeral secret 2856 and final shared secret.) 2858 The script "dhe.c" connects the input and output of these two using 2859 pipes. One pipe is generated by the shell command line using the 2860 shell operator "|". The other pipe is a pipe name "dhab", created 2861 with "mkfifo". The script captures the shared secrets from each run 2862 by redirecting "stderr" (as file descriptor 2), to files "dha" and 2863 "dhb", which will be made named pipes if possible. 2865 Internet-Draft 2021-04-01 2867 The scripts feeds each shared secret keys into SHA-256. This 2868 demonstrates their equality. It also illustrates a typical way to 2869 use Diffie--Hellman, by deriving symmetric keys using a hash 2870 function. In multi-curve ECC, hashing a concatenation of such 2871 shared secrets (one for each curve used), could be done instead. 2873 C.4. Sample code for public-key validation and curve basics 2875 The next sample code demonstrates the public-key validation issues 2876 specific to 2y^2=x^3+x/GF(8^91+5). It also demonstrates the order 2877 of the curve. It also demonstrates complex multiplication by i, and 2878 the fact the 34-byte representation of points is unaffected by 2879 multiplication by i. 2881 The code can be considered to describe a file "pkv.c". It uses the 2882 "mulch" function by including "pseudo.c". 2884 2885 #include 2886 #include "pseudo.c" 2887 #define M mulch // works with +/- x, so P ~ -P ~ iP ~ -iP 2888 void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");} 2889 int main (void){i j;// sanity check, PKV, twist insecurity demo 2890 C y="TEST 2y^2=x^3+x/GF(8^91+5)",z="zzzzzzzzzzzzzzzzzzzz", 2891 q = "\xa9\x38\x04\xb8\xa7\xb8\x32\xb9\x69\x85\x41\xe9\x2a" 2892 "\xd1\xce\x4a\x7a\x1c\xc7\x71\x1c\xc7\x71\x1c\xc7\x71\x1c" 2893 "\xc7\x71\x1c\xc7\x71\x1c\x07", // q=order(G) 2894 i = "\x36\x5a\xa5\x56\xd6\x4f\xb9\xc4\xd7\x48\x74\x76\xa0" 2895 "\xc4\xcb\x4e\xa5\x18\xaf\xf6\x8f\x74\x48\x4e\xce\x1e\x64" 2896 "\x63\xfc\x0a\x26\x0c\x1b\x04", // i^2=-1 mod q 2897 w5= "\xb4\x69\xf6\x72\x2a\xd0\x58\xc8\x40\xe5\xb6\x7a\xfc" 2898 "\x3b\xc4\xca\xeb\x65\x66\x66\x66\x66\x66\x66\x66\x66\x66" 2899 "\x66\x66\x66\x66\x66\x66\x66"; // w5=(2p+2-72q)/5 2900 for(j=0;j<=3;j++)M(z,(C){j},G),hx(z); // {0,1,2,3}G, but reject 0G 2901 M(z,q,G),hx(z); // reject qG; but qG=O, under hood: 2902 {F x;E p;lift(p,feed(x,G),1);mule(p,q);hx(bite(z,p[1]));} 2903 for(j=0;j<0*25;j++){F x;E p;lift(p,feed(x,(C){j,1}),1);mule(p,q); 2904 printf("%3d ",j),hx(bite(z,p[1]));}// see j=23 for choice of G 2905 for(j=3;j--;)q[0]-=1,M(z,q,G),hx(z);// (q-{1,2,3})G ~ {1,2,3}G 2906 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 2907 M(w5,w5,(C){5}),hx(w5);// twist, ord(w5)=5, M(z,z,p) skipped PKV(p) 2908 M(G,(C){1},w5),hx(G);// reject w5 (G unch.); but w5 leaks z mod 5: 2909 for(j=10;j--;)M(z,y,G),z[0]+=j,M(z,z,w5),hx(z);} 2910 2912 Internet-Draft 2021-04-01 2914 The sample code demonstrates the need for public-key validation 2915 even when using the Montgomery ladder for scalar multiplication. It 2916 does this by finding points of low order on the twist of the curve. 2917 This invalid points can leak bits of the secret multiplier. This 2918 is because the curve 2y^2=x^3+x/GF(8^91+5) is not fully "twist 2919 secure". (Its twist security is typical of that of a random curve.) 2921 Appendix D. Minimizing trapdoors and backdoors 2923 The main advantage of curve 2y^2=x^3+x/GF(8^91+5) over almost all 2924 other elliptic curves is its Kolmogorov complexity is almost minimal 2925 among curves of sufficient resistance to the Pollard rho attack on 2926 the discrete logarithm problem. 2928 See [AB] and [B1] for some details. 2930 D.1. Decimal exponential complexity 2932 The curve can be described with 21 characters: 2934 2 y ^ 2 = x ^ 3 + x / G F ( 8 ^ 9 1 + 5 ) 2935 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2937 Those familiar with ECC will recognize that these 21 characters 2938 suffice to specify the curve up to the level of detail needed to 2939 describe the cost of the Pollard rho algorithm, as well as many 2940 other security properties (especially resistance to other known 2941 attacks on the discrete logarithm problem, such as Pohlig--Hellman 2942 and Menezes--Okamoto--Vanstone). 2944 Note: The letters GF mean Galois Field, and are quite traditional 2945 mathematics, and every elliptic curve in cryptographic needs to 2946 use some notation for the finite field. 2948 We may therefore describe the curve's Kolmogorov complexity as 21 2949 characters. 2951 Note: The idea of low Kolmogorov complexity is hard to specify 2952 exactly. Nonetheless, a claim of nearly minimal Kolmogorov 2953 complexity is quite falsifiable. The falsifier need merely 2954 specify several other (secure) elliptic curves using 21 or fewer 2955 characters. (But if the other curves use a different 2956 specification language, then a fair comparison should re-specify 2957 2y^2=x^3+x/GF(8^91+5) in this specification language.) 2959 D.1.1. A shorter isomorphic curve 2961 The curve is isomorphic to a curve specifiable in 20 characters: 2963 Internet-Draft 2021-04-01 2965 y^2=x^3-x/GF(8^91+5) 2967 Generally, isomorphic curves have essentially equivalently hard 2968 discrete logarithm problems, so one could argue that curve 2969 2y^2=x^3+x/GF(8^91+5) could be rated as having Kolmogorov complexity 2970 at most 20 characters. 2972 Isomorphic curves, however, may differ slightly in security, due to 2973 issues of efficiency, and implementability. The 21-character 2974 specification uses an equation in Montgomery form, which creates an 2975 incentive to use the Montgomery ladder algorithm, which is both safe 2976 and efficient [Bernstein?]. 2978 D.1.2. Other short curves 2980 Allowing for non-prime fields, then the binary-field curve known as 2981 sect283k1 has a 22-character description: 2983 y^2+xy=x^3+1/GF(2^283) 2985 This curve was formerly one of the fifteen curves recommended by 2986 NIST. Today, a binary curve is curve is considered risky, due to 2987 advances in elliptic curve discrete logarithm problem over extension 2988 fields, such as recent asymptotic advances on discrete logarithms in 2989 low-characteristic fields [HPST] and [Nagao]. According to [Teske], 2990 some characteristic-two elliptic curves could be equipped with a 2991 secretly embedded backdoor (but sect283k1's short description should 2992 help mitigate that risk). 2994 This has a longer overall specification than curve 2995 2y^2=x^3+x/GF(8^91+5), but the field part is shorter field 2996 specification. Perhaps an isomorphic curve can be found (one with 2997 three terms), so that total length is 21 or fewer characters. 2999 A non-prime field tends to be slower in software. A non-prime field 3000 is therefore perhaps riskier due to some recent research on 3001 attacking non-prime field discrete logarithms and elliptic curves, 3003 D.1.3. Converting DEC characters to bits 3005 The units of characters as measuring Kolmogorov complexity is not 3006 calibrated as bits of information. Doing so formally would be very 3007 difficult, but the following approach might be reasonable. 3009 Internet-Draft 2021-04-01 3011 Set the criteria for the elliptic curve. For example, e.g. prime 3012 field, size, resistance (of say 2^128 bit operations) to known 3013 attacks on the discrete logarithm problem (Pollard rho, MOV, etc.). 3014 Then list all the possible ECC curve specification with Kolmogorov 3015 complexity of 21 characters or less. Take the base two logarithm of 3016 this number. This is then an calibrated estimate of the number of 3017 bits needed to specify the curve. It should be viewed as a lower 3018 bound, in case some curves were missed. 3020 To be completed. 3022 D.1.4. Common acceptance of decimal exponential notation 3024 The decimal exponentiation notation used in to measure decimal 3025 exponential complexity is quite commonly accepted, almost standard, 3026 in mathematical computer programming. 3028 For example, as evidence of this common acceptance, here is a 3029 slightly edited session of the program "bc" (versions of which are 3030 standardized in POSIX). 3032 3033 $ BC_LINE_LENGTH=71 bc 3034 bc 1.06.95 3035 Copyright ... Free Software Foundation, Inc. 3036 ... 3037 p=8^91+5 ; p; obase=16; p 3039 151771007205135083665582961470587414581438034300948400097797844510851\ 3040 89728165691397 3041 200000000000000000000000000000000000000000000000000000000000000000005 3042 define v(b,e,m){ 3043 auto a; for(a=1;e>0;e/=2){ 3044 if(e%2==1) {a=(a*b)%m;} 3045 b=(b^2)%m;} 3046 return(a);} 3047 v(571,p-1,p) 3048 1 3049 x = (1*256) + (23*1) 3050 v(2*(x^3+x),(p-1)/2,p) 3051 1 3052 y = (((p+1)/2)*v(2*(x^3+x),(p+3)/8,p))%p 3053 (2*y^2)%p == (x^3+x)%p 3054 1 3055 (2*y^2 -(x^3+x))%(8^91+5) 3056 0 3057 3059 Internet-Draft 2021-04-01 3061 Note: Input lines have been indented at least two extra spaces, 3062 and can be pasted into a "bc" session. (Pasting the output lines 3063 causes a few spurious results.) 3065 The sample code demonstrates that "bc" directly accepts the 3066 notations "8^91+5" and "x^3+x": parts parts of the curve 3067 specification "2y^2=x^3+x/GF(8^91+5)", which goes to show how much 3068 of the notation used in this specification is commonly accepted. 3070 Note: Defined function "v" implements modular exponentiation, 3071 with returning v(b,e,m) returning (b^e mod m). Then, "v" is used 3072 to show that p=8^91+5 is a Fermat pseudoprime to base 571 3073 (evidence that p is prime). The value x defined is the 3074 x-coordinate of the recommend base point G. Then, another 3075 computation with "v" shows that 2(x^3+x) has Legendre symbol 1, 3076 which implies (assuming p is prime) that there exists y with 3077 2y^2=x^3+x, namely y = (1/2)sqrt(2(x^3+x)). The value of y is 3078 computed, again using "v" (but also a little luck). The curve 3079 equation is then tested twice with two different expressions, 3080 somewhat similar to the mathematical curve specification 3081 2y^2=x^3+x/GF(8^91+5). 3083 D.2. General benefits of low Kolmogorov complexity to ECC 3085 The intuitive benefit of low Kolmogorov complexity to cryptography 3086 is well known, but very informal and heuristic. The general benefit 3087 is believed to be a form of subversion-resistance, where the 3088 attacker is the designer of the cryptography. The idea is that low 3089 Kolmogorov complexity thwarts that type of subversion which causes 3090 high Kolmogorov complexity. Exhaustive searches for weaknesses 3091 would seem to require relatively high Kolmogorov complexity, 3092 compared to lowest complexity non-weak examples in the search. 3094 Often, fixed numbers in cryptographic algorithms with low Kolmogorov 3095 complexity are called "nothing-up-my-sleeve" numbers. (Bernstein et 3096 al. uses terms in "rigid", for a very similar idea, but with an 3097 emphasis on efficiency instead of compressibility.) 3099 For elliptic curves, the informal benefit may be stated as the 3100 following gains. 3102 Internet-Draft 2021-04-01 3104 - Low Kolmogorov complexity defends against insertion of a keyed 3105 trapdoor, meaning the curve can broken using a secret trapdoor, 3106 by an algorithm (eventually discovered by the public at large). 3107 For example, the Dual EC DRBG is known to capable of having such 3108 a trapdoor. Such a trapdoor would information-theoretically 3109 imply an amount of information, comparable the size of the 3110 secret, to be embedded in the curve specification. If the 3111 calibrated estimate for the number of bits is sufficiently 3112 accurate, then such a key cannot be large. 3114 - Low Kolmogorov complexity defends against a secret attack 3115 (presumably difficult to discover), which affects a subset of 3116 curves such that (a) whether or not a specific curve is affected 3117 is a somewhat pseudorandom function of its natural 3118 specification, and (b) the probably of a curve being affected 3119 (when drawn uniformly from some sensible of curve 3120 specification), is low. For an example of real-world attacks 3121 meeting the conditions (a) and (b) consider the MOV attack. 3122 Exhaustively finding curve meeting these two conditions is 3123 likely to result in relatively high Kolmogorov complexity. 3124 The supply of low Kolmogorov complexity curves is so low that 3125 the probability of any falling into the weak class is low. 3127 - Even more hypothetically, there may yet exist undisclosed 3128 classes of weak curves, or attacks, which 2y^2=x^3+x/GF(8^91+5) 3129 avoids somehow. A real-world example is prime-order, or low 3130 cofactor curves, which are rare among all curves, but which 3131 better resist the Pohlig--Hellman attack. If this happens, then 3132 it should be considered a fluke. 3134 Low Kolmogorov complexity is not a panacea. The worst failure would 3135 be attacks that increase in strength as Kolmogorov complexity gets 3136 lower. Two examples illustrate this strongly. 3138 D.2.1. Precedents of low Kolmogorov complexity in ECC 3140 To be completed. 3142 Basically, the curves sect283k1, Curve25519, and Brainpool curves 3143 can be argued as mitigating the risk of manipulated designed-in 3144 weakness, by virtue of the low Kolmogorov complexity. 3146 To be completed. 3148 D.3. Risks of low Kolmogorov complexity 3150 Low Kolmogorov complexity is not a panacea for cryptography. 3152 Internet-Draft 2021-04-01 3154 Indeed, it may even add its own risks, if some weakness are 3155 positively correlated with low Kolmogorov complexity, making some 3156 attacks stronger. 3158 In other words, choosing low Kolmogorov complexity might just 3159 accidentally weaken the cryptography. Or worse, if attackers find 3160 and hold secret such weaknesses, then attackers can intentionally 3161 include the weakness, by using low Kolmogorov serving as a cover, 3162 thereby subverting the algorithm. 3164 Evidence of positive correlations between curve weakness and low 3165 Kolmogorov complexity might help assess this risk. 3167 In general cryptography (not ECC), the shortest cryptography 3168 algorithms may be the least secure, such as the identity function as 3169 an encryption function. 3171 Within ECC, however, some minimum threshold of complexity must be 3172 met for interoperability. But curve size is positively correlated 3173 with security (via Pollard rho) and negatively correlated with 3174 complexity (at least for fields, larger fields needs larger 3175 specifications). Therefore, there is a somewhat negative correlation 3176 between Pollard rho security of ECC and Kolmogorov complexity of the 3177 field size. 3179 Beyond field size in ECC, there is some negative correlations in the 3180 curve equation. 3182 Singular cubics have equations that look very similar to those 3183 commonly used elliptic curves. For smooth singular curves 3184 (irreducible cubics) a group can be defined, using more or less the 3185 same arithmetic as for a elliptic curve. For example 3186 y^2=x^3/GF(8^91+5) is such a cubic. The resulting group has an easy 3187 discrete logarithm problem, because it can be mapped to the field. 3189 Supersingular elliptic curves can also be specified with low 3190 Kolmogorov complexity, and these are vulnerable to MOV attack, 3191 another negative correlation. 3193 Combining the above, a low Kolmogorov complexity elliptic curve, 3194 y^2=x^3+1/GF(2^127-1), with 21-character decimal exponential 3195 complexity, suffers from three well-known attacks: 3197 1. The MOV (Menezes--Okamato--Vanstone) attack. 3199 2. The Pohlig--Hellman attack (since it has 2^127 points). 3201 Internet-Draft 2021-04-01 3203 3. The Pollard rho attack (taking 2^63 steps, instead of the 2^126 3204 of exhaustive). 3206 Had all three attacks been unknown, an implementer seeking low 3207 Kolmogorov complexity, might have been drawn to curve 3208 y^2=x^3+1/GF(2^127-1). (This document's curve 2y^2=x^3+x/GF(8^91+5) 3209 uses 1 more character and is much slower since, the field size has 3210 twice as many bits.) 3212 Had an attacker known one of three attacks, the attacker could found 3213 y^2=x^3+1/GF(2^127-1), proposed it, touted its low Kolmogorov 3214 complexity, and maybe successfully subverted the system security. 3216 Note: The curve y^2=x^3+1/GF(2^127-1) not only has low decimal 3217 exponential complexity, it also has high efficiency: fast field 3218 arithmetic and fairly fast curve arithmetic (for its bit lengths). 3219 So high efficiency can also be positively correlated with 3220 weakness. 3222 It can be argued, that pseudorandomized curves, such as NIST P-256 3223 and Brainpool curves, are an effective way mitigate such attacks 3224 positively correlated with low complexity. More precisely, strong 3225 pseudorandomization somewhat mitigates the attacker's subversion 3226 ability, by reducing an easy look up of the weakest curve to an 3227 exhaustive search by trial and error, intuitively implying a 3228 probable high Kolmogorov complexity (proportional the rarity of the 3229 weakness). 3231 It can be further argued that all major known weak classes of curves 3232 in ECC are positively correlated with low complexity, in that the 3233 weakest curves have very low complexity. No major known weak 3234 classes of curves imply an increase in Kolmogorov complexity, except 3235 perhaps Teske's class of curves. 3237 In defense of low complexity, it can be argued that the strongest 3238 way to resist secret attacks is to find the attacks. 3240 For these reasons, this specification suggests to use curve 3241 2y^2=x^3+x/GF(8^91+5) in multi-curve elliptic curve cryptography, 3242 in combination with at least one pseudo-randomized curve. 3244 To be completed. 3246 D.4. Alternative measures of Kolmogorov complexity 3248 Decimal exponential complexity arguably favors decimal and the 3249 exponentiation operators, rather than the arbitrary notion of 3250 compressibility. 3252 Internet-Draft 2021-04-01 3254 Allowing more arbitrary compression schemes introduces another 3255 possible level of complexity, the compression scheme itself, 3256 somewhat defeating the purpose of nothing-up-sleeve number. An 3257 attacker might be able to choose a compression scheme among 3258 many that somehow favors a weak curve. 3260 Despite this potential extra complexity, one can still seek a 3261 measure more objective than decimal complexity. To this end, in 3262 [B3], I adapted the Godel's approach for general recursive 3263 functions, which breaks down all computation into succession, 3264 composition, repetition, and minimization. 3266 The adaption is a miniature programming language called Roll to 3267 describe number-related functions, including constant functions. A 3268 Roll program for the constant function that always return 8^91+5 is: 3270 3271 8^91+5 subs 8^91+1 in +4 3272 8^91+1 subs 2^273 in +1 3273 2^273 subs 273 in 2^ 3274 273 subs 17 in *16+1 3275 17 subs 1 in *16+1 3276 *16+1 roll +16 up 1 3277 +16 subs +8 in +8 3278 +8 subs +4 in +4 3279 +4 subs +2 in +2 3280 2^ roll *2 up 1 3281 1 subs in +2 3282 *2 roll +2 up 0 3283 +2 subs +1 in +1 3284 0 subs in +1 3285 3287 A Roll program has complexity measured in its length in number of 3288 words (space-separated substrings). This program has 68 words. 3289 Constants (e.g. field sizes) can be compared using roll complexity, 3290 the shortest known length of their implementations in Roll. 3292 In [B3], several other ECC field sizes are given programs. The only 3293 prime field size implemented with 68 or fewer words was 2^521-1. 3294 (The non-prime field size (2^127-1)^2 has 58-word "roll" program.) 3295 Further programming effort might produce shorter programs. 3297 Note: Roll programs have a syntax implying some redundancy. 3298 Further work may yet establish a reasonable normalization for roll 3299 programs, resulting in a more calibrated complexity measure in 3300 bits, making the units closed to a universal kind of Kolmogorov 3301 complexity. 3303 Internet-Draft 2021-04-01 3305 Appendix E. Primality proofs and certificates 3307 Recent work of Albrecht and others [AMPS] has shown the combination 3308 of an adversarially chosen prime, and users using improper 3309 probabilistic primality tests can make user vulnerable to an attack. 3311 The adversarial primes in their attack are typically the result of 3312 an exhaustive search. These bad primes would therefore typically 3313 contain an amount of information corresponding to the length of 3314 their search, putting a predictable lower bound on their Kolmogorov 3315 complexity. 3317 The two primes involved for 2y^2=x^3+x/GF(8^91+5) should perhaps 3318 already resist [AMPS] because of the following compact 3319 representation of these primes: 3321 p = 8^91+5 3322 q = #(2y^2=x^3+x/GF(8^91+5))/72 3324 This attack [AMPS] can also be resisted by: 3326 - properly implementing probabilistic primality test, or 3327 - implementing provable primality tests. 3329 Provable primality tests can be very slow, but can be separated into 3330 two steps: 3332 -- a slow certificate generation, and 3334 -- a fast certificate verification. 3336 The certificate is a set of data, representing an intermediate step 3337 in the provable primality test, after which the completion of the 3338 test is quite efficient. 3340 Pratt primality certificate generation for any prime p, involves 3341 factorizing p-1, which can be very slow, and then recursively 3342 generating a Pratt primality certificate for each prime factor of 3343 p-1. Essentially, each prime has a unique Pratt primality 3344 certificate. 3346 Pratt primality certificate verification of (p-1), involves search 3347 for g such that 1 = (g^(p-1) mod p) and 1 < (g^((p-1)/q) mod p) for 3348 each q dividing p-1, and then recursively verifying each Pratt 3349 primality certificate for each prime factor q of p-1. 3351 Internet-Draft 2021-04-01 3353 In this document, we specify a Pratt primality certificate as a 3354 sequence of (candidate) primes each being 1 plus a product of 3355 previous primes in the list, with certificate stating this product. 3357 Although Pratt primality certificate verification is quite 3358 efficient, an ECC implementation can opt to trust 8^91+5 by virtue 3359 of verifying the certificate once, perhaps before deployment or 3360 compile time. 3362 E.1. Pratt certificate for the field size 8^91+5 3364 Define 52 positive integers, a,b,c,...,z,A,...,Z as follows: 3366 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 3367 j=1+aaac k=1+abd l=1+aaf m=1+abf n=1+aacc o=1+abg p=1+al q=1+aaag 3368 r=1+abcc s=1+abbbb t=1+aak u=1+abbbc v=1+ack w=1+aas x=1+aabbi 3369 y=1+aco z=1+abu A=1+at B=1+aaaadh C=1+acu D=1+aaav E=1+aeff F=1+aA 3370 G=1+aB H=1+aD I=1+acx J=1+aaacej K=1+abqr L=1+aabJ M=1+aaaaaabdt 3371 N=1+abdpw O=1+aaaabmC P=1+aabeK Q=1+abcfgE R=1+abP S=1+aaaaaaabcM 3372 T=1+aIO U=1+aaaaaduGS V=1+aaaabbnuHT W=1+abffLNQR X=1+afFW 3373 Y=1+aaaaauX Z=1+aabzUVY. 3375 Note: variable concatenation is used to indicate multiplication. 3376 For example, f = 1+aab = 1+2*2*(1+2) = 13. 3378 Note: One must verify that Z=8^91+5. 3380 Note: The Pratt primality certificate involves finding a generator 3381 g for each the prime (after the initial prime). It is possible to 3382 list these in the certificate, which can speed up verification by 3383 a small factor. 3385 (2,b), (2,c), (3,d), (2,e), (2,f), (3,g), (2,h), (5,i), (6,j), 3386 (3,k), (2,l), (3,m), (2,n), (5,o), (2,p), (3,q), (6,r), (2,s), 3387 (2,t), (6,u), (7,v), (2,w), (2,x), (14,y),(3,z), (5,A), (3,B), 3388 (7,C), (3,D), (7,E), (5,F), (2,G), (2,H), (2,I), (3,J), (2,K), 3389 (2,L),(10,M), (5,N), (10,O),(2,P), (10,Q),(6,R), (7,S), (5,T), 3390 (3,U), (5,V), (2,W), (2,X), (3,Y), (7,Z). 3392 Internet-Draft 2021-04-01 3394 Note: The decimal values for a,b,c,...,Y are given by: a=2, b=3, 3395 c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=41, k=43, l=53, m=79, 3396 n=101, o=103, p=107, q=137, r=151, s=163, t=173, u=271, v=431, 3397 w=653, x=829, y=1031, z=1627, A=2063, B=2129, C=2711, D=3449, 3398 E=3719, F=4127, G=4259, H=6899, I=8291, J=18041, K=124123, 3399 L=216493, M=232513, N=2934583, O=10280113, P=16384237, Q=24656971, 3400 R=98305423, S=446424961, T=170464833767, U=115417966565804897, 3401 V=4635260015873357770993, W=1561512307516024940642967698779, 3402 X=167553393621084508180871720014384259, 3403 Y=1453023029482044854944519555964740294049. 3405 E.2. Pratt certificate for subgroup order 3407 Define 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new 3408 values: 3410 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 3411 j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b 3412 r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e 3413 z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck 3414 G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG 3415 O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ 3416 V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Z=1+ab3oHOT !=1+a3SUX @=1+abNY! 3417 #=1+a4kzF@ $=1+a3QZ# 3419 Note: numeral after variable names represent powers. For example, 3420 f = 1 + a2b = 1 + 2^2 * 3 = 13. 3422 The last variable, $, is the order of the base point, and the order 3423 of the curve is 72$. 3425 Note: Punctuation used for variable names !,@,#,$, would not scale 3426 for larger primes. For larger primes, a similar format might work 3427 by using a prefix-free set of multi-letter variable names. 3428 E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze: 3430 Acknowledgments 3432 Thanks to John Goyo and various other BlackBerry employees for past 3433 technical review, and to Gaelle Martin-Cocher and Takashi Suzuki for 3434 encouraging work on this I-D. Thanks to David Jacobson for sending 3435 Pratt primality certificates. 3437 Internet-Draft 2021-04-01 3439 Author's Address 3441 Dan Brown 3442 BlackBerry 3443 4701 Tahoe Blvd., 5th Floor 3444 Mississauga, ON 3445 Canada 3446 danibrown@blackberry.com