idnits 2.17.1 draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- -- The document has an IETF Trust Provisions (28 Dec 2009) Section 6.c(i) Publication Limitation clause. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (2020-04-03) is 1484 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 982 -- Looks like a reference, but probably isn't: '2' on line 982 Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 5 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: 2020-10-05 2020-04-03 5 Elliptic curve 2y^2=x^3+x over field size 8^91+5 6 8 Abstract 10 Multi-curve elliptic curve cryptography with 2y^2=x^3+x/GF(8^91+5) 11 hedges a risk of new curve-specific attacks. The curve features: 12 isomorphism to Miller's curve from 1985; low Kolmogorov complexity 13 (little room for embedded weaknesses of Gordon, Young--Yung, or 14 Teske); prime field; Montgomery ladder or Edwards unified arithmetic 15 (Hisil--Carter--Dawson--Wong); complex multiplication by i 16 (Gallant--Lambert--Vanstone); 34-byte keys; five 64-bit-word field 17 arithmetic; easy reduction, inversion, Legendre symbol, and square 18 root; similarity to a Bitcoin curve; and string-as-point encoding. 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) 2019 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with 44 respect to this document. 46 This document may not be modified, and derivative works of it may 47 not be created, except to format it for publication as an RFC or to 48 translate it into languages other than English. 50 Internet-Draft 2020-04-03 52 Table of contents 53 1. Introduction 54 2. Requirements Language (RFC 2119) 55 3. Overview 56 3.1. Not for single-curve ECC 57 3.2. Risks of new curve-specific attacks 58 3.3. Multi-curve ECC 59 3.3.1. Multi-curve ECC is a redundancy strategy 60 3.3.2. Whether to use multi-ECC 61 3.3.2.1. Benefits of multi-curve ECC 62 3.3.2.2. Costs of multi-curve ECC 63 3.3.3. Applying multi-curve ECC 64 3.4. Curve features 65 3.4.1. Field features 66 3.4.3. Equation features 67 3.4.4. Finite curve feature 68 3.4.4.1. Curve size and cofactor 69 3.4.4.2. Pollard rho security 70 3.4.4.3. Pohlig--Hellman security 71 3.4.4.2. Menezes--Okamoto--Vanstone security 72 3.4.4.3. Semaev--Araki--Satoh--Smart security 73 3.4.4.4. Edwards and Hessian form 74 3.4.4.5. Bleichenbacher security 75 3.4.4.6. Bernstein's "twist" security 76 3.4.4.7. Cheon security 77 4. Encoding points 78 4.1. Point encoding process 79 4.1.1. Summary 80 4.1.2. Details 81 4.2. Point decoding process 82 4.2.1. Summary 83 4.2.2. Detail 84 5. Point validation 85 5.1. When to validate 86 5.1.1. Mandatory validation 87 5.1.2. Simplified validation 88 5.1.4. Minimal validation 89 5.2. Point validation process 90 6. OPTIONAL encodings 91 6.1. Encoding scalars 92 6.2. Encoding strings as points 93 7. IANA Considerations 94 8. Security considerations 95 8.1. Field choice 96 8.2. Curve choice 97 8.3. Encoding choices 98 8.4. General subversion concerns 99 8.5. Concerns about 'aegis' 100 9. References 102 Internet-Draft 2020-04-03 104 9.1. Normative References 105 9.2. Informative References 106 Appendix A. Test vectors 107 Appendix B. Minimizing trapdoors and backdoors 108 Appendix C. Pseudocode 109 C.1. Scalar multiplication of 34-byte strings 110 C.1.1. Field arithmetic for GF(8^91+5) 111 C.1.2. Montgomery ladder scalar multiplication 112 C.1.3. Bernstein's 2-dimensional Montgomery ladder 113 C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong) 114 C.2 Pseudocode for test vectors 115 C.3. Pseudocode for a command-line demo of Diffie--Hellman 116 C.4 Pseudocode for public-key validation and twist insecurity 117 C.5. Elligator i 118 D. Primality proofs and certificates 119 D.1. Pratt certificate for the field size 8^91+5 120 D.2. Pratt certificate for subgroup order 122 1. Introduction 124 Elliptic curve cryptography (ECC) is now part of several IETF 125 protocols. 127 Multi-curve ECC mitigates the risk of new curve-specific attacks on 128 ECC. This document aims to contribute to multi-curve ECC by 129 describing how to use the curve 131 2y^2=x^3+x / GF(8^91+5). 133 2. Requirements Language (RFC 2119) 135 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 136 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 137 document are to be interpreted as described in RFC 2119 [BCP14]. 139 3. Overview 141 This sections how curve 2y^2=x^3+x/GF(8^91+5) improves ECC. 143 3.1. Not for single-curve ECC 145 Curve 2y^2=x^3+x/GF(8^91+5) SHOULD NOT be used in single-curve ECC, 146 because it is is riskier than other IETF-approved curves, such as 147 NIST P-256 and Curve25519, for at least two reasons: 149 Internet-Draft 2020-04-03 151 - it is newer: common sense says newer is riskier, all else equal, 152 and 154 - it is special, with complex multiplication by i: consensus 155 continues to agree with Miller's original 1985 opinion that 156 using (such) special curves is not prudent. 158 Koblitz, Koblitz and Menezes [KKM] somewhat dissent from the latter 159 consensus by listing several plausible cases of special curves -- 160 including some with complex multiplication -- that they argue might 161 well be safer than random curves. (Others go even further, 162 dismissing prudence against special curves as myth). Despite this 163 dissent, this report adheres to the consensus. 165 3.2. Risks of new curve-specific attacks 167 A risk for ECC is new curve-specific attacks --- "new" meaning 168 hypothetical and not yet published, so either future or hidden. 170 Prime-field curves were affected by two curve-specific attacks on 171 the discrete logarithm: the MOV attacks the SASS attack, both from 172 before 2001. For non-prime-field curves, more recent curve-specific 173 attacks have been discovered. The rarity of the attacks is evidence 174 that the probability of new curve-specific attacks is low, but is 175 not proof. 177 Sensible curves include mitigations against the nonzero risk of new 178 curve-specific attacks. 180 - NIST curve P-256 has coefficients derived from the ouptut of 181 SHA-1, perhaps aiming to avoid any new curve-specific weakness 182 that would appply rarely to random curves. 184 - Bernstein's Curve25519 results from a "rigid" design process, 185 favoring efficiency over all else, perhaps eliminating intentional 186 subversion towards a new curve-specifc weakness. 188 - Brainpool's curve are derived using hash functions to 189 number-up-my-sleeve numbers, perhaps aiming to mitigate both 190 intential subversion and accidental rare weakness. 192 A reasonable inference from these curves is that risk of new 193 curve-specific attacks warranted the mitigations used. The 194 risk may be less now that further time has passed, yet the 195 mitigations may still be warranted. 197 Internet-Draft 2020-04-03 199 The curve 2y^2=x^3+x/GF(8^91+5) includes mitigations against the 200 risk of new curve-specific attacks: 202 - a short description (low Kolmogorov compelxity), aiming to have 203 little wiggle for an intentional embedded weakness, much like a 204 nothing-up-my-sleeve number, 206 - a set of special efficiencies, such as a curve endomorphism, 207 Montgomery form, and fast field operation, much like a "rigid" 208 favors efficiency to fight off intentional embedded weakness, 210 - a prime field, to stay clear of recent curve-specific attacks on 211 non-prime-field ECC. 213 These mitigations do not suffice to justify its use in single-curve 214 ECC (instead of more established non-special curves). 216 Multi-curve ECC aims to further mitigate the risk of curve-specific 217 attack, by securely combining a diverse set of curves. The aim is 218 that at least one of the curves used in multi-curve ECC resists the 219 new curve-specific attack (if a new attack ever appears). This aim 220 is only plausible if the set of curves used is diverse. 222 This curve contributes to the diversity necessary for multi-curve 223 ECC, with special features distinct from established curves NIST 224 P-256 and Curve25519: 226 - complex multiplication by i (low discrimiant, rather than high), 228 - a greater emphasis on low Kolmogorov descriptional complexity 229 (rather than hashed coefficient or efficiency). 231 3.3. Multi-curve ECC 233 This section further motivates the value of multi-curve ECC over 234 single-curve ECC, but does specify a detailed way to do multi-curve 235 ECC. 237 Multi-curve ECC is only really effective if used with a diverse set 238 of curves. Multi-curve ECC SHOULD use a set of curves including the 239 three curves: 241 NIST P-256, Curve25519, and 2y^2=x^3+x/GF(8^91+5). 243 3.3.1. Multi-curve ECC is a redundancy strategy 244 Internet-Draft 2020-04-03 246 Multi-curve ECC is an instance of a strategy often called 247 redundancy, applied to ECC. Redundancy is quite general in that it 248 can be applied to other types of cryptography, to other types of 249 information security, and even to safety systems. Other names for 250 redundant strategies include: 252 strongest-link, defense-in-depth, hybrid, hedged, composite, 253 fail-safe, diversified, resilient, belt-and-suspenders, fault 254 tolerant, robust, multi-layer, robustness, compound, combination, 255 etc. 257 3.3.2. Whether to use multi-ECC 259 Multi-curve ECC mitigates the risk of new curve-specific attacks, so 260 ought to be used instead of single-curve ECC if affordable, such as 261 when 263 - the privacy of the data being protected has higher value than 264 the extra cost of multi-curve ECC, which may well be the case 265 for at least financial, medical, or personally-identifying data, 266 and 268 - ECC is only a tiny portion of the overall system costs, which 269 would be the case if the data is human-generated or high-volume, 270 or if ECC is combined with slow or large post-quantum 271 cryptography (PQC). 273 3.3.2.1. Benefits of multi-curve ECC 275 The benefit of multi-curve ECC over single-curve ECC, its extra 276 security, is difficult to quantify. 278 No extra security results if all the curves used are the same. The 279 curves must be diverse, so that a potential attack on one is somehow 280 unlikely to affect the other. This diversity is difficult to 281 assess. Intuitively, a geometric metaphor of a polygon for the 282 space of all choices might help. Maximally distant points in a 283 polygon tend to be vertices, the extremities of the polygon. 284 Translating this inuition suggests choosing curves at the extremes 285 of features. 287 Note: By contrast, in a single-curve ECC, the geometric 288 metaphor suggests a central internal point, on the grounds that 289 each vertex is more likely to be affected to a special attack. 290 Carrying this over to multi-curve suggests that a diverse set 291 ought to include a non-extreme curve too. 293 Internet-Draft 2020-04-03 295 As always, the benefit of security is really the negative of the 296 cost of an attack, including the risk. 298 The contextual benefit of multi-curve ECC therefore depends very 299 much on the application, involving the assessing both the 300 probability of attack, and the impact of the attack. 302 Higher value private data has greater impact if attacked, and 303 perhaps also higher probability, if the adversary is more motivated 304 to attack it. 306 Low probability of attacks are mostly inferred through failed but 307 extensive cryptanalysis efforts. Normally, this is only intuited, 308 but approaches to quantifiably estimate these probabilities is 309 possible too, under sufficiently strong assumptions. 311 To be completed. 313 3.3.2.2. Costs of multi-curve ECC 315 The cost of multi-curve ECC can be cost compared to single-curve 316 ECC. The cost ratio is approximately the number of curves used. 317 The cost difference depends on the devices implementing the ECC. 319 For example, on a current personal computer, the extra cost per ECC 320 transaction can include up to 1 millisecond of runtime and sending 321 an extra 30 bytes or more. In low-end devices, the time may be 322 higher due to slower processors. 324 The contextual cost of ECC depends on the application context. In 325 some applications, such as personal messages between two users, the 326 cost (milliseconds and a few hundred bytes) is affordable relative 327 to the time users spent writing and reading the messages. In other 328 applications, such as automated inter-device communication with 329 frequent brief messages, single-curve ECC may already be a 330 bottleneck, costing most of the run-time. 332 3.3.3. Applying multi-curve ECC 334 For key establishment, NIST recently proposed in a draft amendment 335 to Special Publication 800-133 on key derivation a mechanism to 336 support derive one symmetric key from the result of multiple key 337 establishments. In essense, the raw ECDH shared secrets would be 338 concatenated and fed into a hash-based key derivation function. 340 An alternative would be to XOR multiple shared symmetric-key 341 together. 343 Internet-Draft 2020-04-03 345 So, multi-curve elliptic curve Diffie--Hellman (ECDH) key agreement 346 could use one of these mechanism to derive a single key from 347 multi-curve ECDH. One would still need to a mechanism to support 348 sending more than one ECDH public key (usually ephemeral), with an 349 indication of the curve for each ECDH key. 351 For signatures, the simplest approach is to attach multiple 352 signatures to each message. (For signatures providing message 353 recovery, then an approach is to apply the results, with outer 354 signatures recover the inner signed message, and so on.) 356 3.4. Curve features 358 This subsection describes some general features of the curve 360 2y^2=x^3+x/GF(8^91+5), 362 presuming a familiarity with elliptic curve cryptography (ECC). 364 Each of a set of well-established features, such as Pollard rho 365 security or Mongtomgery form, for ECC in general are evaluated and 366 summarized for the specific curve 2y^2=x^3+x/GF(8^91+5). 368 Note: Interoperable ECC requires a few more details than are 369 deducible from mathematical description 2y^2=x^3+x/GF(8^91+5) of 370 the curve, such encoding points as byte strings. These details 371 are discussed in Section 3,4, and 5. 373 3.4.1. Field features 375 The curve's field of definition, GF(8^91+5), is a finite field, as 376 is always the case in ECC. (Finite fields are Galois field, and the 377 field of size is p is written as GF(p).) 379 The field size is the prime p=8^91+5. (See the appendix for a 380 Pratt primality certificate.) 382 In hexadecimal (base 16, big-endian) notation, the number 8^91+5 is 384 200000000000000000000000000000000000000000000000000000000000000000005 386 with with 67 zeros between 2 and 5. 388 Prime fields in ECC tend be more efficient in software than in 389 hardware. The most recent known curve-specific attacks on 390 prime-field ECC are from 2000. 392 Internet-Draft 2020-04-03 394 The prime p is very close to a power of two. Primes very cloe to a 395 power of two are sometimes known as a Crandall prime. Reduction 396 modulo p is more efficient for Crandall primes than for most other 397 primes (or at least random primes). Perhaps Crandall primes more 398 resistant to side-channel attacks or implementation faults than than 399 most other primes. 401 The fact that p is slightly larger than a power of two -- rather 402 than slightly lower -- means that powering algorithms to compute 403 inverses, Legendre symbols, and square roots are simpler and 404 slightly more efficient (than would be for prime below a 2-power). 406 3.4.3. Equation features 408 The curve equation 2y^2=x^3+x has Montgomery form, 410 by^2=x^3+ax^2+x, 412 with (a,b) = (0,2). This permits the Montgomery ladder scalar point 413 multiplication algorithm to be used, which makes it relatively 414 efficient, and also easier to protect against side channels. 416 The curve 2y^2=x^3+x has complex multiplication by i, given an 417 endomorphism 419 (x,y) -> (-x,iy). 421 Note: Strictly speaking, over some fields, the curve would be 422 supersingular, in which the term "complex mutliplication" is not 423 longer used, perhaps because quaternionic multiplication is 424 applicable. 426 This permits the Gallant--Lambert--Vanstone (GLV) scalar 427 multiplication algorithm, which makes it relatively efficient. (The 428 GLV method can also be combined with Bernstein's two-dimensional 429 variant of the Montgomery ladder algorithm.) 431 The curve has j-invariant 1728 (because it has complex 432 multiplication by i). 434 Note: The j-invariants 0 and 1728 are special in that they have 435 more than two automorphisms. Over complex numbers, the moduli 436 space of elliptic curves is an orbifold, with two non-smooth 437 points, at j=0 and j=1728, which is yet another reason these 438 j-invariants are special. 440 3.4.4. Finite curve feature 441 Internet-Draft 2020-04-03 443 This section describes features of 2y^2=x^3+x/GF(8^91+5) as a finite 444 curve consisting, the points (x,y) for x,y in GF(p), and also the 445 point at infinity. In other words, these features are specific to 446 the combination of both the finite field and the curve equation. 448 Note: In algebraic geometry, these points are said to rational 449 over k=GF(p), and the set of rational points written as E[k] = 450 (2y^2=x^3+)[GF(8^91+5)], to distinguish from points with 451 coordinates in the alebraic closure of k=GF(p). 453 Many security properties, and a few performance properties, of ECC 454 are specific to the finite curve. 456 3.4.4.1. Curve size and cofactor 458 The curve (of points rational over GF(8^91+5) has size (order) 72q 459 for a large prime q. (See Appendix for a Pratt primality certifcate 460 for q.) 462 In other words, the curve has cofactor 72. 464 Note: The curve size 72q can be found using the CM method and 465 Cornacchia's algorithm, instead of the more costly 466 Schoo--Elkies--Atkin algorithm(s). For this curve, this method 467 amounts to finding integers (a,b) such that a^2 + b^2 = p, and 468 then putting 72q = a^2 + (b-1)^2. 470 3.4.4.2. Pollard rho security 472 The prime q is 267-bit number, so the Pollard rho algorithm takes 473 (proportional to) sqrt(q) ~ 2^133 elliptic curve operations. So, it 474 seems to provide well over 2^128 security against Pollard rho 475 attacks, with about 5 bits to spare. 477 Note: Arguably, the fact ECC operations are slower than 478 symmetric-key operartions (such as hashing or block ciphers), 479 means that ECC security should be granted a few extra bits, 480 perhaps 5-10 bits, of security when trying to match ECC security 481 with symmetric-key security. In this case, one might say that 482 2y^2=x^3+x/GF(8^91+5) resists Pollard-rho with 2^140 security, 483 providing 12 bits of extra security. The extra security can be 484 viewed as a safety margin for error, or as an excessive to the 485 extent the smaller, and faster curves would more than suffice to 486 match 2^128 security of SHA-256 and AES-128. 488 Internet-Draft 2020-04-03 490 Gallant, Lambert, Vanstone, show how to speed up Pollard rho 491 algorithms when the group has an extra endormorphism, which would 492 apply to 2y^2=x^3+x. The speed-up here amounts to a couple of bits 493 in the security, 495 3.4.4.3. Pohlig--Hellman security 497 The small cofactor means the curve effectively resists 498 Pohlig--Hellman attack (a generic algorithm to solve discrete 499 logarithms in any group in time sqrt(m) where m is the largest 500 prime factor of the group size). 502 Note: Consensus in ECC is to recommend a small factor, such as 1, 503 2, 4, or 8, despite the factor for random curves, the typical 504 cofactor is approximately p^(1/3), which is much larger. The 505 small cofactor helps resists Pohlig--Hellman without increasing 506 the field size. (A larger field size would be less efficient.) 508 3.4.4.2. Menezes--Okamoto--Vanstone security 510 The curve has a large embedding degree, so it resists the 511 Menezes--Okamoto--Vanstone attack. The curve 2y^2=x^3+x / 512 GF(8^91+5) is not supersingular. 514 Note: For about half of all primes q, then curve 2y^2=x^3+x is 515 supersingular over GF(q). Supersingular curves have q+1 points, 516 and are vulnerable to the MOV attack, which reduces the elliptic 517 curve discrete logarithm to the finite field discrete logarithm 518 over GF(q^2). This is one of the sense in which the curve 519 2y^2=x^3+x / GF(8^91+5) is close to being insecure. To be clear, 520 this curve was chosen after, and with full knowledge of, the MOV 521 attack. 523 Note: The non-supersingularity means that the endomorphism ring is 524 commutative. For this curve the endomorphism ring is isomorphic 525 to the ring Z[i] of Gaussian integers. 527 The large embedding degree also means that it has no efficient 528 pairing operation, so it cannot be used for pairing-based 529 cryptography. 531 3.4.4.3. Semaev--Araki--Satoh--Smart security 533 The fact that the curve size 72q is not p, means that the curve 534 resists the Semaev--Araki--Satoh--Smart attack. 536 3.4.4.4. Edwards and Hessian form 537 Internet-Draft 2020-04-03 539 The cofactor 72 is divisible by 4, so the curve isomorphic to a 540 curve with an Edwards equation, permitting implementation even more 541 efficient than the Montgomery ladder. 543 The Edwards form makes possible the Gallant--Lambert--Vanstone 544 method that used the efficient endomorphism. 546 The cofactor 72 is also divisible by 3, so the curve is isomorphic 547 to a curve with a Hessian equation, which is another type of 548 equation permmitting efficient implementation. 550 Note: It is probably too optimisitic and speculative to hope that 551 future research will show how to take advantage by combining the 552 efficiencies of Edwards and Hessian curve equations. 554 3.4.4.5. Bleichenbacher security 556 The prime q is not particularly close to a power of two. 558 This means that for faulty implementations of digital signatures may 559 be more vulnerable to Bleichenbacher's attack, which would exploits 560 the non-uniformity in secret numbers obtained by reducing uniformly 561 random bit strings modulo q. 563 Therefore, q-uniformization of the secret numbers is critical for 564 signature applications of 2y^2=x^3+x/GF(8^91+5). 566 3.4.4.6. Bernstein's "twist" security 568 Unlike Curve25519, curve 2y^2=x^3+x/GF(8^91+5) is not 569 "twist-secure", so a Montgomery ladder implementation for static 570 private keys often requires public-key validation, which is 571 achievable by comptuation of Legendre symbol. 573 In particular, a Montgomery ladder x-only implementation that does 574 not implement public-key validation will process a value x for which 575 no y satsifying the equation exists in GF(p). More precsiely, a y 576 does exist, but it belongs to the extension field GF(p^2). In this 577 case, the Montgomery ladder treats x as though it were (x,y) where x 578 is GF(p) but y is not. Such points belong to a "twist" group, and 579 this group has order: 581 2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 * 582 3452464930451677330036005252040328546941 584 Internet-Draft 2020-04-03 586 An adversary can exploit this, by finding such invalid x that 587 corresond to a lower order group element, and thereby try to learn 588 partial information about a static private key used by a 589 non-validating Montgomery ladder implementation. 591 3.4.4.7. Cheon security 593 Niche applications in ECC involve revealing points [d^e]G for one 594 secret number d, and many different integer e, or at least one large 595 e. One way such points could be reveal is in protocols that employ 596 a static Diffie--Hellman oracle, a function to compute [d]P from any 597 point P, which might be applied e times, if e is reasonably small. 599 Typical ECDH, to be clear, would never reveal such points, for at 600 least two reasons: 602 - ECDH is ephemeral, with d not re-used across ECDH sessions, so 603 that d is used to compute [d]G and [d]Q, and then discarded, 605 - ECDH is hashed, so though P=[d]G is sent, the point [d]Q is 606 hashed to get k = H([d]Q), and then [d]Q is discarded, so the 607 fact that hash is one-way means that k should not reveal [d]Q. 609 The Brown--Gallant--Cheon q-1 algorithm, finds d given [d^e]G if 610 e|q-1, with approximately sqrt(q/e) elliptic curve operations. The 611 Cheon q+1 algorithm finds d given all the points [d]G, [d^2]G, 612 ... [d^e]G if e|q+1. These algorithm rely on factors e of q-1 or 613 q+1, so the factorization of these numbers affects the security 614 against the algorithm. Cheon security refers to the ability to 615 render these algoirthms unusable. 617 It is possible seek out curves such that q-1 and q+1 have no small 618 factors e. 620 The curve 2y^2=x^3+x/GF(8^91+5) has typical Cheon security in terms 621 of the factorization of q-1 and q+1. Therefore, in the niche 622 applications that reveal the requisite points, mitigations ought to 623 be applied, such as limiting the rate of revealing points, or using 624 different value d as much as possible (one d per recipient). 626 For 2y^2=x^3+x/GF(8^91+5) the factorization of q-1 and q+1 are: 628 To be completed. 630 Internet-Draft 2020-04-03 632 4. Encoding points 634 Elliptic curve cryptography uses points for public keys and raw 635 shared secrets. 637 Abstractly, points are mathematical objects. For curve 2y^2=x^3+x, 638 a point is either a pair (x,y), where x and y are elements of 639 mathematical field, or a special point O, both of whose coordinates 640 may be deemed as infinity. 642 For curve 2y^2=x^3+x/GF(8^91+5), the coordinates x and y of the 643 point (x,y) are integers modulo 8^91+5, which can be represented as 644 integers in the interval [0,8^91+4]. 646 Note: for practicality, an implementation will often internally 647 represent the x-coordinate as a ratio [X:Z] of field elements. 648 Each field element has multiple representations, but [x:1] can 649 viewed as normal representation of x. (Infinity can be then 650 represented by [1:0], though one must be careful.) 652 To interoperably communicate, points must be encoded as byte 653 strings. 655 This draft specifies an encoding of finite points (x,y) as strings 656 of 34 bytes, as described in the following sections. 658 Note: The 34-byte encoding is not injective. Each point is 659 generally among a group of four points that share the same byte 660 encoding. 662 Note: The 34-byte encoding is not surjective. Approximately half 663 of 34-byte strings do not encode a point (x,y). 665 Note: In many typical ECC schemes, the 34-byte encoding works 666 well, despite being neither injective nor surjective. 668 4.1. Point encoding process 670 4.1.1. Summary 672 A point (x,y) is encoded by the little-endian byte representation of 673 x or -x, whichever fits into 34 bytes. 675 4.1.2. Details 677 A point (x,y) is encoded into 34 bytes, as follows. 679 Internet-Draft 2020-04-03 681 First, ensure that x is fully reduced mod p=8^91+5, so that 683 0 <= x < 8^91+5. 685 Second, further reduce x by a flipping its sign, as explained next. 686 Let 688 x' =: min(x,p-x) mod 2^272. 690 Third, set the byte string b to be the little-endian encoding of the 691 reduced integer x', by finding the unique integers b[i] such that 692 0<=b[i]<256 and 694 (x' mod 2^272) = sum (0<=i<=33, b[i]*256^i). 696 Pseudocode can be found in Appendix C. 698 Note: The loss of information that happens upon replacing x by -x 699 corresponds to applying complex multiplication by i on the curve, 700 because i(x,y) = (-x,iy) is also a point on the curve. (To see 701 this: note 2(iy)^2 = -(2y^2) = -(x^3+x) = (-x)^3+(-x).) In many 702 applications, particularly Diffie--Hellman key agreement, this 703 loss of information is carried through the final shared secret, 704 which means that Alice and Bob can agree on the same secret 34 705 bytes. 707 In ECC systems where the original x-coordinate and the decoded 708 x-coordinate need to match exactly, then the 34-byte encoding is 709 probably not usable unless the following pre-encoding procedure is 710 practical: 712 Given a point x where x is larger than min(x,p-x), first replace x 713 by x'=p-x, on the encoder's side, using the new value x' (instead of 714 x) for any further step in the algorithm. In other words, replace 715 the point (x,y) by the point (x',y')=(-x,iy). Most algorithms will 716 also require a discrete logarithm d of (x,y), meaning (x,y) = [d] G 717 for some point G. Since (x',y') = [i](x,y), we can replace by d' 718 such that [d']=[i][d]. Usually, [i] can be represented by an 719 integer, say j, and we can compute d' = jd (mod ord(G)). 721 4.2. Point decoding process 723 4.2.1. Summary 725 The bytes are little-endian decoded into an integer which 726 becomes the x-coordinate. Public-key validation done if needed. If 727 needed, the y-coordinate is recovered. 729 Internet-Draft 2020-04-03 731 4.2.2. Detail 733 If byte i is b[i], with an integer value between 0 and 255 734 inclusive, then 736 x = sum( 0<=i<=33, b[i]*256^i) 738 Note: a value of -x (mod p) will also be suitable, and results in 739 a point (-x,y') which might be different from the originally 740 encoded point. However, it will be one of the points [i](x,y) or 741 -[i](x,y) where [i] means complex multiplication by [i]. 743 In many cases, such as Diffie--Hellman key agreement using the 744 Montgomery ladder, neither the original value of x or -x nor 745 coordinate y of the point is needed. In these cases, the decoding 746 steps can be considered completed. 748 +-------------------------------------------------------+ 749 | | 750 | \ W / /A\ |R) |N | I |N | /G ! | 751 | \/ \/ / \ |^\ | \| | | \| \_7 0 | 752 | | 753 | | 754 | WARNING: Some byte strings b decode to an invalid | 755 | point (x,y) that does not belong to the curve | 756 | 2y^2=x^3+x. In some situations, such invalid b can | 757 | lead to a severe attack. In these situations, the | 758 | decoded point (x,y) MUST be validated, as described | 759 | below in Section 4. | 760 | | 761 +-------------------------------------------------------+ 763 In cases where a value for at least one of y, -y, iy, or -iy is 764 needed such as Diffie--Hellman key agreement using some other 765 coordinate system (such as one might need when converting to Edwards 766 coordinates), the candidate value can be obtained by computing a 767 square root: 769 y = ((x^3+x)/2)^(1/2). 771 In some cases, it is important for the decoded value of x to match 772 the original value of x exactly. In that case, the encoder should 773 use the procedure that replace x by p-x, and adjusts the discrete 774 logarithm appropriately. These steps can be done by the encoder, 775 with the decoder doing nothing. 777 Internet-Draft 2020-04-03 779 5. Point validation 781 In elliptic curve cryptography, scalar multiplying an invalid public 782 key by a private key risks leaking information about the private 783 key. 785 Note: For curve 2y^2=x^3+x over 8^91+5, the underlying attacks are 786 a little milder than the average a typical elliptic curve. 788 To avoid leaking information about the private, the public key can 789 be validated, which includes various checks on the public key. 791 5.1. When to validate 793 This section specifies several strategies. 795 5.1.1. Mandatory validation 797 As a precautionary defense-in-depth, an impelementation MAY opt to 798 apply mandatory validation, meaning every public key (and point) is 799 validated. 801 5.1.2. Simplified validation 803 A small, general-purpose, implementation aiming for high speed might 804 not be able to afford the cost of mandatory validation from Section 805 4.1.1, because each validation costs about 10% of a scalar 806 multiplication. 808 As a practical middle groun, an impelmentatio MAY opt to apply 809 simplified validation, which is the rule is that a distrusted public 810 key is validated before being scalar multiplied by a static secret 811 key. 813 +---------------------------------------------------------------+ 814 | STATIC | 815 | SECRET | 816 | KEY ------\ _ ___ | 817 | + ) PUBLIC |\/| | | (_` | | 818 | UNTRUSTED ------/ KEY | | \_/ ._) | BE VALIDATED. | 819 | PUBLIC | 820 | KEY | 821 +---------------------------------------------------------------+ 823 Note: Simplified validation implies that when the secret key is 824 ephemeral (for example, used in one Diffie--Hellman transaction), 825 the public key need not be validated. 827 Internet-Draft 2020-04-03 829 Note: Simplified validation implies that when the point being 830 scalar multiplied, is a known valid fixed point, or a previously 831 validated public key (including a public key from a certificate in 832 which the certification authority has a policy to valid public 833 keys), then validation is not needed. 835 5.1.4. Minimal validation 837 An implementation MAY opt to use minimal validation, meaning doing 838 as little point validation as possible, just enough to resist known 839 attack against the implementation. 841 The curve 2y^2=x^3+x is not twist-secure: using the Montgomery 842 ladder for scalar multiplication is not enough to thwart invalid 843 public key attacks. 845 For example, consider a static hashed-ECDH implementation 846 implemeneted with a Montgomery ladder, such that the static secret 847 key is used at most ten million times hashed-ECDH transactions. 848 Even if exposed to invalid points on the twist, the secruity risk is 849 nearly negligible. 851 5.2. Point validation process 853 Upon decoding a 34-byte string into x, the next step is to compute 854 z=2(x^3+x). Then one checks if z has a nonzero square root (in the 855 field of size 8^91+5). If z has a nonzero square root, then the 856 represented point is valid, otherwise it is not valid. 858 Equivalently, one can check that x^3 + x has no square root (that 859 is, x^3+x is a quadratic non-residue). 861 To check z for a square root, one can compute the Legendre symbol 862 (z/p) and check that is 1. (Equivalently, one can check that 863 ((x^3+x)/p)=-1.) 865 The Legendre symbol can be computed using Gauss' quadratic 866 reciprocity law, but this requires implementing modular integer 867 arithmetic for moduli smaller than 8^91+5. 869 More slowly, but perhaps more simply, one can compute the Legendre 870 symbol using powering in the field: (z/p) = z^((p-1)/2) = 871 z^(2^272+2). This will have value 0,1 or p-1 (which is equivalent 872 to -1). 874 Internet-Draft 2020-04-03 876 More generally, in signature applications (such as [B2]), where the 877 y-coordinate is also needed, the computation of y, which involves 878 computing a square root will generally include a check that x is 879 valid. 881 OPTIONAL: In some rare situations, it is also necessary to ensure 882 that the point has large order, not just that it is on the curve. 884 For points on this curve, each point has large order, unless it has 885 torsion by 12. In other words, if [12]P != O, then the point P has 886 large order. 888 OPTIONAL: In even rarer situations, it may be necessary to ensure 889 that a point P also has a prime order n = ord(G). The costly method 890 to check this is checking that [n]P = O. An alternative method is 891 to try to solve for Q in the equation [12]Q=P, which involves 892 methods such a division polynomials. 894 To be completed. 896 6. OPTIONAL encodings 898 The following two encodings are not usually required to obtain 899 interoperability in the typical ECC applications, but can sometimes 900 be useful. 902 6.1. Encoding scalars 904 Scalar (integer point multipliers) sometimes needed to be encoding 905 as byte strings, at least internally to an implementation. 907 Basically, little-endian byte encoding of integers is recommended. 909 In Diffie--Hellman only implementations, the scalars s and p-s 910 really have not significant distinction, so all scalars can be 911 represented with 34 bytes. 913 Applications: 915 - Digital signature in ECC generallly require scalar encodings. 916 This draft does not specify signature algorithms in detail, only 917 providing some general suggestions. 919 Internet-Draft 2020-04-03 921 - An implementation needs to store scalars, because scalars are 922 used at least twice, and must be stored between these two uses. 923 For example, in elliptic curve Diffie--Hellman, Alice has scalar 924 a, sends Bob point aG, keeps scalar a until she receives point 925 B from Bob, to which she then applies aB. (If a is ephemeral, 926 she then deletes a.) An implementation is free to use any 927 encoding of scalar, but implementation are often constructed in 928 modular pieces, and any pieces handling the same scalar need to 929 be able to convey the scalar. 931 6.2. Encoding strings as points 933 In niche applications, it may be desired to encode an arbtirary 934 string as a point on a curve. Example reasons to encode arbitrary 935 34-byte strings include: 937 - Encoding passwords (or their hashes) for use in 938 password-authenticated key exchange. 940 - Hiding the fact that ECC is being used. 942 To this end, this section sketches a method to reversibly encode 943 any 34-byte string as a point. 945 Note: To encode variable-length strings as points, one can first 946 compute a 34-byte hash of the variable-length string, and then 947 encode the hash. Encoding of variable-length strings is not, and 948 cannot be, reversible. 950 Note: The point decoding scheme of Section 3.2 does not suffice to 951 encode strings, becausse only about half of all 34-byte strings 952 are decodable. 954 Note: The string-as-point encoding has the the property that only 955 about half of all points are decodable as 34-bytes strings. 956 Encoding a uniformly distributed 34-byte string as a point yields 957 non-uniformly distributed points. 959 The encoding is called Elligator i. 961 Note: The Elligator i encoding is a minor variation of the 962 Elligator 2 construction [Elligator], introduced in [B1]. The 963 variation is necessary because Elligator 2 fails for curves with 964 j-invariant 1728, and curve 2y^2=x^3+x has j-invariant 1728. 966 Fix a square root i of -1 in the field in GF(8^91+5). For example, 967 2^(8^89+1) mod 8^91+5. 969 Internet-Draft 2020-04-03 971 To encode a 34-byte string b, 973 1. Let b represent a field element r, using little-endian base 974 256. 976 2. Compute x = i-3i/(1-ir^2). Let j=1. 978 3. If 2y^2=x^3+x has no solution y, then replace x by x+i and j by 979 j+1. 981 4. Find two solutions y[1] and y[2] to 2y^2=x^3+x, such that 982 y[1]p-y, replace x by x-i. Solve for s = -i - 3/(i-x). Let r = 992 sqrt(s). If r > p-r, replace r by p-r. Write r in little-endian 993 base 256 to get a 34-byte string b. 995 Note: Just to illustrate a constrast between Elligator i encoding 996 and the normal point encoding, consider the useless example of 997 applying both encodings. Start with 34-byte string b. Apply 998 Elligator i encoding to get a point (x,y). Apply the point 999 encoding to (x,y) to get a 34-byte string b'. In summary, 1000 b'=encode(encode(b)). The byte string b' has no significant 1001 relation to b. The map b->b' from 34-byte strings to themselves 1002 is lossy (non-injective) with ratio ~4:1, and the image set is 1003 about one quarter of all 34-byte strings. 1005 7. IANA Considerations 1007 This document requires no actions by IANA, yet. 1009 8. Security considerations 1011 No cryptographic algorithm is without risk, but risk is difficult to 1012 quantify. 1014 This section lists the most plausible threats against 1015 2y^2=x^3+x/GF(8^91+5), comparing their risk to a typical generic 1016 curve in ECC, or in some cases, to specific well-established 1017 curves in ECC. 1019 Internet-Draft 2020-04-03 1021 8.1. Field choice 1023 The field 8^91+5 has the following risks. 1025 - 8^91+5 is a special prime. As such, it is perhaps vulnerable to 1026 some kind of attack. For example, for some curve shapes, the 1027 supersingularity depends on the prime, and the curve size is 1028 related in a simple way to the field size, causing a potential 1029 correlation between the field size and the effectiveness of an 1030 attack, such as the Pohlig--Hellman attack. In summary, field 1031 size is positively correlated to some known attacks, and perhaps a 1032 special field size is positively correlated to a potential attack. 1034 Nonetheless, many other standard curves, such as the NIST P-256 1035 and Curve25519, also use special prime field sizes. In this 1036 regard, all these special field curves have a similar risk. 1038 Yet other standard curves, such as the Brainpool curves, use 1039 pseudorandom field sizes, reducing their risk to potential 1040 special-field attack. 1042 - 8^91+5 arithmetic implementation, while implementable in five 1043 64-bit words, has some risk of overflowing, or of not fully 1044 reducing properly. Perhaps a smaller field, such as that used in 1045 Curve25519, has a simpler reduction and overflow-avoidance 1046 properties. 1048 - 8^91+5, by virtue of being well-above 256 bits in size, risks its 1049 user doing extra, and perhaps unnecessary, computation to protect 1050 their 128-bit keys, whereas smaller curves might be faster (as 1051 expected) yet still provide enough security. In other words, the 1052 extra computational cost for exceeding 256 bits is wasteful, and 1053 partially a form of denial of service. 1055 - 8^91+5 is smaller than some other six-symbol primes: 8^95-9, 1056 9^99+4 and 9^87+4. Therefore, arguably, 8^91+5 fails to 1057 absolutely maximize field size relative to Kolmogorov complexity. 1058 In particular, curves defined over larger field size have better 1059 Pollard rho resistance (of the ECDLP). 1061 Nonetheless, the primes 9^99+4 and 9^87+4 are not close to a power 1062 of two, so probably suffer from much slower implementation than 1063 8^91+5, which is a significant runtime cost, and perhaps also a 1064 security risk (due to implementation bugs). 1066 Internet-Draft 2020-04-03 1068 The prime 8^95-9 is, just like 8^91+5, very close to a power of 1069 two. So should have comparable efficiency for basic field 1070 arithmetic operations, such as addition, multiplication and 1071 reduction. The field 8^95-9 is a little larger, but can still be 1072 implemented using five 64-bit words. Being larger, 8^95-9, it has 1073 a slightly greater risk than 8^91+5 of leading to an arithmetic 1074 overflow implementation fault in field arithmetic. Field size 1075 8^95-9 has much less simple powering algorithms for computing 1076 field inverses, Legendre symbols, and square roots: so these 1077 operations, often important for ECC, may require more code, more 1078 runtime, and perhaps more risk of implementation bug. 1080 - 8^91+5 is smaller than 2^283 (the field size for curve sect283k1 1081 [SEC2], [Zigbee]), and many other five-symbol and four-symbol 1082 prime powers (such as 9^97). It provides less resistance to 1083 Pollard rho than such larger prime powers. Recent progress in the 1084 elliptic curve discrete logarithm problem, [HPST] and [Nagao], is 1085 the main reason to prefer prime fields instead of power of prime 1086 fields. A second reason to prefer a prime field (including the 1087 field of size 8^91+5) over small characteristic fields is the 1088 generally better software speed of large characteristic field. 1089 (Better software speed is mainly due to general-purpose hardware 1090 often having dedicated fast multiplication circuits: 1091 special-purpose hardware should make small characteristic field 1092 faster.) 1094 - The Kolmogorov complexity of 8^91+5 as six symbols is only minimal 1095 for decimal exponential complexity: but it is not minimal if other 1096 types of complexity measures are allowed. For example, if we 1097 allow the exclamation mark for the factorial operation -- which is 1098 quite standard notation! -- primes larger than 8^91+5 expressible 1099 in fewer symbols. For example, 94!-1 is a 485-bit prime number, 1100 expressible in five symbols. Such numbers, so far as I know, are 1101 not close to a power of two, so would have similar inefficiency 1102 and implementability defects to primes like 9^99+4 and 9^87+4. 1103 Such inefficiencies could resaonably by the curve choice criteria, 1104 ruling out such primes. 1106 Arguably, in traditional mathematical notation, the symbol '^' is 1107 not actually written, with operation being marked by the use of 1108 superscripts. In this view, using an ASCII character count 1109 arugably gives unduly low weight to the factorial operation as 1110 compared to exponentiation. 1112 See [B1] for further discussion about the relative merits of 8^91+5. 1114 Internet-Draft 2020-04-03 1116 Note: For any form of ECC, finite field multiplication can be 1117 achieved most quickly by using hardware integer multiplication 1118 circuits. It is critical that those circuits have no bugs or 1119 backdoors. Furthermore, those circuits typically can only 1120 multiply integers smaller than the field elements. Larger inputs 1121 to the circuits will cause overflows. It is critical to avoid 1122 these overflows, not just to avoid interoperability failures, but 1123 also to avoid attacks where the attackers supply inputs likely 1124 induce overflows [bug attacks], [IT]. 1126 To be completed: 1128 Projective coordinates are not suitable as the final representation 1129 of an elliptic curve point, for two reasons. 1131 - Projective coordinates for a point are generally not unique: each 1132 point can be represented in projective coordinates in multiple 1133 different ways. So, projective coordinates are unsuitable for 1134 finalizing a shared secret, because the two parties computing the 1135 shared secret point may end up with different projective 1136 coordinates. 1138 - Projective coordinates have been shown to leak information about 1139 the scalar multiplier [PSM], which could be the private 1140 key. It would be unacceptable for a public key to leak 1141 information about the private key. In digital signatures, even a 1142 few leaked bits can be fatal, over a few signatures 1143 [Bleichenbacher]. 1145 Therefore, the final computation of an elliptic curve point, after 1146 scalar multiplication, should translate the point to a unique 1147 representation, such as the affine coordinates described in this 1148 report. 1150 For example, when using a Montgomery ladder, scalar multiplication 1151 yields a representation (X:Z) of the point in projective 1152 coordinates. Its x-coordinate is then x=X/Z, which can be computed 1153 by computing the 1/Z and then multiplying by X. 1155 The safest, most prudent way to compute 1/Z is to use a side-channel 1156 resistant method, in particular at least, a constant-time method. 1157 This reduces the risk of leaking information about Z, which might in 1158 turn leak information about X or the scalar multiplier. Fermat 1159 inversion, computation of Z^(p-2) mod p, is one method to compute 1160 the inverse in constant time (if the inverse exists). 1162 Internet-Draft 2020-04-03 1164 8.2. Curve choice 1166 A first risk of using 2y^2=x^3+x is the fact that it is a special 1167 curve. It is special in having complex multiplication leading 1168 to an efficient endomorphism. Miller, in 1985, already suggested 1169 exercising prudence when considering such special curves. Gallant, 1170 Lambert and Vanstone found ways to slightly speed up Pollard rho 1171 given such an endomorphism, but no other attacks have been found. 1173 Menezes, Okamoto and Vanstone (MOV) found an attack on special 1174 elliptic curves, of low embedding degree. The curve 1175 2y^2=x^3+x/GF(8^91+5) is not vulnerable to their attack, but if one 1176 changes the underlying to some different primes, say p', the 1177 resulting curve 2y^2=x^3+x/GF(p') is vulnerable to their attack for 1178 about half of all primes. Because the MOV was later than Miller's 1179 caution from 1984, Miller's prudence seems prescient. Perhaps he 1180 was also prescient about yet other potential attacks (still 1181 unpublished), and these attacks might affect 2y^2=x^3+x/GF(8^91+5). 1183 Many other standard curves, NIST P-256 [NIST-P-256], Curve25519, 1184 Brainpool [Brainpool], do not have any efficient complex 1185 multiplication endomorphisms. Arguably, these curves comply to 1186 Miller's advice to be prudent about special curves. 1188 Yet other (fairly) standard curves do, such as NIST K-283 (used in 1189 [Zigbee]) and secp256k1 (see [SEC2] and [BitCoin]). Furthermore, it 1190 is not implausible [KKM] that special curves, including those 1191 efficient endomorphisms, may survive an attack on random curves. 1193 A second risk of 2y^2=x^3+x over 8^91+5 is the fact that it is not 1194 twist-secure. What may happen is that an implementer may use the 1195 Montgomery ladder in Diffie--Hellman and re-use private keys. They 1196 may think, despite the (ample?) warnings in this document, that 1197 public key validation in unnecessary, modeling their implementation 1198 after Curve25519 or some other twist-secure curve. This implementer 1199 is at risk of an invalid public key attack. Moreover, the 1200 implementer has an incentive to skip public-key validation, for 1201 better performance. Finally, even if the implementer uses 1202 public-key validation, then the cost of public-key validation is 1203 non-negligible. 1205 Internet-Draft 2020-04-03 1207 A third risk is a biased ephemeral private key generation in a 1208 digital signature scheme. Most standard curves lack this risk 1209 because the field size is close to a power of two, and the cofactor 1210 is a power of two. Curve 2y^2=x^3+x over 8^91+5 has a base point 1211 order which is approximately a power of two divided by nine (because 1212 its cofactor is 72=8*9.) As such, it is more vulnerable than 1213 typical curves to biased ephemeral keys in a signature scheme. 1215 A fourth risk is a Cheon-type attack. Few standard curves address 1216 this risk, and 2y^2=x^3+x over 8^91+5 is not much different. 1218 A fifth risk is a small-subgroup confinement attack, which can also 1219 leak a few bits of the private key. Curve 2y^2=x^3+x over 8^91+5 1220 has 72 elements whose order divides 12. 1222 8.3. Encoding choices 1224 To be completed. 1226 8.4. General subversion concerns 1228 Although the main motivation of curve 2y^2=x^3+x over 8^91+5 is to 1229 minimize the risk of subversion via a backdoor ([Gordon], [YY], 1230 [Teske]), it is only fair to point out that its appearance in this 1231 very document can be viewed with suspicion as an possible effort at 1232 subversion (via a front-door). (See [BCCHLV] for some further 1233 discussion.) 1235 Any other standardized curve can be view with a similar suspicion 1236 (except, perhaps, by the honest authors of those standards for whom 1237 such suspicion seems absurd and unfair). A skeptic can then examine 1238 both (a) the reputation of the (alleged) author of the standard, 1239 making an ad hominem argument, and (b) the curve's intrinsic merits. 1241 By the very definition of this document, the reader is encouraged to 1242 take an especially skeptical viewpoint of curve 2y^2=x^3+x over 1243 8^91+5. So, it is expected that skeptical users of the curve will 1244 either 1246 - use the curve for its other merits (other than its backdoor 1247 mitigations), such as efficient endomorphism, field inversion, 1248 high Pollard rho resistance within five 64-bit words, meanwhile 1249 holding to the evidence-supported belief ECC that is now so mature 1250 that worries about subverted curves are just far-fetched nonsense, 1251 or 1253 Internet-Draft 2020-04-03 1255 - as an additional of layer of security in addition to other 1256 algorithms (ECC or otherwise), as an extra cost to address the 1257 non-zero probability of other curves being subverted. 1259 To paraphrase, consider users seriously worried about subverted 1260 curves (or other cryptographic algorithms), either because they 1261 estimate as high either the probability of subversion or the value 1262 of the data needing protection. These users have good reason to 1263 like 2y^2=x^3+x over 8^91+5 for its compact description. 1264 Nevertheless, the best way to resist subversion of cryptographic 1265 algorithms seems to be combine multiple dissimilar cryptographic 1266 algorithms, in a strongest-link manner. Diversity hedges against 1267 subversion, and should the first defense against it. 1269 8.5. Concerns about 'aegis' 1271 The exact curve 2y^2=x^3+x/GF(8^91+5) was (seemingly) first 1272 described to the public in 2017 [AB]. So, it has a very low age, at 1273 least compare to more established curves. 1275 Furthermore, it has not been submitted for a publication with peer 1276 review to any cryptographic forum such as the IACR conferences like 1277 Crypto and Eurocrypt. So, it has only been reviewed by very few 1278 eyes. 1280 Arguably, other reviewers have little incentive to study it 1281 critically, for several reasons. The looming threat of a quantum 1282 computer has diverted many researchers towards studying post-quantum 1283 cryptography, such as supersingular isogeny Diffie--Hellman. The 1284 past disputes over NIST P-256 and Curve25519 (and several other 1285 alternatives) have perhaps tired some reviewers, many of whom 1286 reasonably wish to concentrate on deployment of ECC. 1288 So, under the metric of aegis, as in age times eyes (times 1289 incentive), 2y^2=x^3+x/GF(8^91+5) scores low. Counting myself (but 1290 not quantifying incentive) it gets an aegis score of 0.1 (using a 1291 rating 0.1 of my eyes factor in the aegis score: I have not 1292 discovered any major ECC attacks of my own.) This is far smaller 1293 than my estimates (see below) some more well-studied curves. 1295 Nonetheless, the curve 2y^2=x^3+x over 8^91+5 at least has some 1296 similarities to some of the better-studied curves with much higher 1297 aegis: 1299 Internet-Draft 2020-04-03 1301 - Curve25519: has field size 8^85-19, which a little similar to 1302 8^91+5; has equation of the form by^2=x^3+ax+x, with b and a 1303 small, which is similar to 2y^2=x^3+x. Curve25519 has been around 1304 for over 10 years, has (presumably) many eyes looking at it, and 1305 has been deployed thereby creating an incentive to study. An 1306 estimated aegis for Curve25519 is 10000. 1308 - NIST P-256: has a special field size, and maybe an estimated aegis 1309 of 200000. (It is a high-incentive target. Also, it has received 1310 much criticism, showing some intent of cryptanalysis. Indeed, 1311 there has been incremental progress in finding minor weakness 1312 (implementation security flaws), suggestive of actual 1313 cryptanalytic effort.) The similarity to 2y^2=x^3+x over 8^91+5 1314 is very minor, so very little of the P-256 aegis would be relevant 1315 to this document. 1317 - secp256k1: has a special field size, though not quite as special 1318 as 8^91+5, and has special field equation with an efficient 1319 endomorphism by a low-norm complex algebraic integer, quite 1320 similar to 2y^2=x^3+x. It is about 17 years old, and though not 1321 studied much in academic work, its deployment in Bitcoin has at 1322 least created an incentive to attack it. An estimated aegis for 1323 secp256k1 is 10000. 1325 - Miller's curve: Miller's 1985 paper introducing ECC suggested, 1326 among other choices, a curve equation y^2=x^3-ax, where a is a 1327 quadratic non-residue. Curve 2y^2=x^3+x is isomorphic to 1328 y^2=x^3-x, essentially one of Miller's curves, except that a=1 is 1329 a quadratic residue. Miller's curve may not have been studied 1330 intensely as other curves, but its age matches that ECC itself. 1331 Miller also hinted that it was not prudent to use a special curve 1332 y^2=x^3-ax: such a comment may have encouraged some cryptanalysts, 1333 but discouraged cryptographers, perhaps balancing out the effect 1334 on the eyes factor the aegis. An estimated aegis for Miller's 1335 curves is 300. 1337 Obvious cautions to the reader: 1339 - Small changes in a cryptographic algorithm sometimes cause large 1340 differences in security. So security arguments based on 1341 similarity in cryptographic schemes should be given low priority. 1343 Internet-Draft 2020-04-03 1345 - Security flaws have sometimes remained undiscovered for years, 1346 despite both incentives and peer reviews (and lack of hard 1347 evidence of conspiracy). So, the eyes-part of the aegis score is 1348 very subjective, and perhaps vulnerable false positives by a herd 1349 effect. Despite this caveat, it is not recommended to ignore the 1350 eyes factor in the aegis score: don't just flip through old books 1351 (of say, fiction), looking for cryptographic algorithms that might 1352 never have been studied. 1354 9. References 1356 9.1. Normative References 1358 [BCP14] Bradner, S., "Key words for use in RFCs to Indicate 1359 Requirement Levels", BCP 14, RFC 2119, March 1997, 1360 . 1362 9.2. Informative References 1364 To be completed. 1366 [AB] A. Allen and D. Brown. ECC mod 8^91+5, presentation to CFRG, 1367 2017. 1368 1370 [AMPS] Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, and 1371 Juraj Somorovsky. Prime and Prejudice: Primality Testing Under 1372 Adversarial Conditions, IACR ePrint, 1373 2018. 1375 [B1] D. Brown. ECC mod 8^91+5, IACR ePrint, 2018. 1376 1378 [B2] D. Brown. RKHD ElGamal signing and 1-way sums, IACR ePrint, 1379 2018. 1381 [KKM] A. Koblitz, N. Koblitz and A. Menezes. Elliptic Curve 1382 Cryptography: The Serpentine Course of a Paradigm Shift, IACR 1383 ePrint, 2008. 1385 [BCCHLV] D. Bernstein, T. Chou, C. Chuengsatiansup, A. Hulsing, 1386 T. Lange, R. Niederhagen and C. van Vredendaal. How to 1387 manipulate curve standards: a white paper for the black hat, IACR 1388 ePrint, 2014. 1390 [Elligator] (((To do:))) fill in this reference. 1392 Internet-Draft 2020-04-03 1394 [NIST-P-256] (((To do:))) NIST recommended 15 elliptic curves for 1395 cryptography, the most popular of which is P-256. 1397 [Zigbee] (((To do:))) Zigbee allows the use of a 1398 small-characteristic special curve, which was also recommended by 1399 NIST, called K-283, and also known as sect283k1. These types of 1400 curves were introduced by Koblitz. These types of curves were 1401 not recommended by NSA in Suite B. 1403 [Brainpool] (((To do:))) the Brainpool consortium (???) recommended 1404 some elliptic curves in which both the field size and the curve 1405 equation were derived pseudorandomly from a nothing-up-my-sleeve 1406 number. 1408 [SEC2] Standards for Efficient Cryptography. SEC 2: Recommended 1409 Elliptic Curve Domain Parameters, version 2.0, 2010. 1410 1412 [IT] T. Izu and T. Takagi. Exceptional procedure attack on elliptic 1413 curve cryptosystems, Public key cryptography -- PKC 2003, Lecture 1414 Notes in Computer Science, Springer, pp. 224--239, 2003. 1416 [PSM] (((To do:))) Pointcheval, Smart, Malone-Lee. Projective 1417 coordinates leak. 1419 [BitCoin] (((To do:))) BitCoin uses curve secp256k1, which has an 1420 efficient endomorphism. 1422 [Bleichenbacher] To do: Bleichenbacher showed how to attack DSA 1423 using a bias in the per-message secrets. 1425 [Gordon] (((To do:))) Gordon showed how to embed a trapdoor in DSA 1426 parameters. 1428 [HPST] Y. Huang, C. Petit, N. Shinohara and T. Takagi. On 1429 Generalized First Fall Degree Assumptions, IACR ePrint 2015. 1430 1432 [Nagao] K. Nagao. Equations System coming from Weil descent and 1433 subexponential attack for algebraic curve cryptosystem, IACR 1434 ePrint, 2015. 1436 [Teske] E. Teske. An Elliptic Curve Trapdoor System, IACR ePrint, 1437 2003. 1439 [YY] (((To do:))) Yung and Young, generalized Gordon's ideas into 1440 Secretly-embedded trapdoor ... also known as a backdoor. 1442 Internet-Draft 2020-04-03 1444 Appendix A. Test vectors 1446 The following are some test vectors. 1448 000000000000000029352b31395e382846472f782b335e783d325e79322054534554 1449 00000000000000000000000000000000000000000000000000000000000000000117 1450 c8c0f2f404a9fabc91c939d8ea1b9e258d82e21a427b549f05c832cf8d48296ffad7 1451 5f336f56f86de3d52b0eab85e527f2ac7b9d77605c0d5018f5faa4243fd462b1badd 1452 fc023b3f03b469dca32446db80d9b388d753cc77aa4c3ee7e2bb86e99e7bed38f509 1453 8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221 1454 8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221 1456 The test vectors are explained as follows. (Pseudocode generating 1457 them is supplied in Appendix C.2.) 1459 Each line is 34 bytes, representing a non-negative 272-bit integer. 1460 The integer encoding is hexadecimal, with most significant hex 1461 digits on the left: which is big-endian. 1463 Note: Public keys are encoded as 34-byte strings are little, so 1464 one reverses the order of the bytes found in the test vectors. 1465 The pseudocode in Appendix C.2 should make this clear. 1467 Each integer is either a scalar (a multiplier of curve points), or 1468 the byte representation of a point P through its x-coordinate or the 1469 x-coordinate of iP (which is the the mod 8^91+5 negation of the 1470 x-coordinate of P). 1472 The first line is a scalar integer x, which would serve as a very 1473 insecure private key. Its nonzero bytes are the ASCII 1474 representation of the string "TEST 2y^2=x^3+x/GF(8^91+5)", with the 1475 byte order reversed. 1477 The second line is a representation of G, a base point on the curve. 1479 The third line is the representation of z = xG. 1481 The fourth and fifth lines represent updated values of x and z, 1482 obtained after application of the following 100000 scalar 1483 multiplications. 1485 A loop of 50000 iterations is performed. Each iteration consists of 1486 two re-assignments: z = xz and x = zG via scalar multiplications. 1487 In the second assignment, the byte representation of the input point 1488 z is used as the byte representation of an scalar. Similarly, the 1489 output x is the byte representation of the point, which is will used 1490 as as the byte representation of the scalar. 1492 Internet-Draft 2020-04-03 1494 The purpose of the large number of iterations is to catch a bug that 1495 has probability larger than 1/100000 of arising on pseudorandom 1496 inputs. The iterations do nothing to find rarer bugs (that an 1497 adversary can invoke), or silent bugs (side channel leaks). 1499 The sixth and seventh lines are equal to each other. As explained 1500 below, the equality of these lines represents the fact the Alice and 1501 Bob can compute the same shared DH secret. The purpose of these 1502 lines is not catch any more bugs, but simply a sanity check that 1503 Diffie--Hellman is likely to work. 1505 Alice initializes her DH private key to x, as already computed on 1506 the fourth line of the test vectors (which was the result of 100000 1507 iterations). She then replaces this x by x^900 mod q (where q is 1508 the prime which is the order of the order of the base point G). 1510 Bob sets his private key y as follows. He begins with y being the 1511 34-byte ASCII string whose initial characters are "yet another test" 1512 (not including the quotes, of course). He then reverses the order 1513 of bytes, considers this to be a scalar, and reassigning y with the 1514 equation y = yG. (So, the y on the left is new, the y on the right 1515 is old, they are not the same.) Then another reassignment is done, 1516 as y = yy, where the on the right side of the equation one y is 1517 treated as a scalar, the other as a point. The left side is the new 1518 value of y. Finally, Bob's replaces y by y^900 mod order(G), just 1519 as Alice did. 1521 Both lines are xyG. The first can be computed as y(xG), and the 1522 second as x(yG). The equality of the two lines can be used to 1523 self-test an implementation, even if the implementation being tested 1524 disagrees with the test vectors above. 1526 Appendix B. Minimizing trapdoors and backdoors 1528 To main advantage of curve 2y^2=x^3+x/GF(8^91+5) over almost all 1529 other elliptic curves is that its almost minimal Kolmogorov 1530 complexity among curves of sufficient resistance to the Pollard rho 1531 attack on the discrete logarithm problem. 1533 See [AB] and [B1] for some details. 1535 The curve can be described with 21 characters: 1537 2 y ^ 2 = x ^ 3 + x / G F ( 8 ^ 9 1 + 5 ) 1538 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1540 Internet-Draft 2020-04-03 1542 Those familiar with ECC will recognize that these 21 characters 1543 suffice to specify the curve up to the level of detail needed to 1544 describe the cost of the Pollard rho algorithm, as well as many 1545 other security properties (especially resistance to other known 1546 attacks on the discrete logarithm problem, such as Pohlig--Hellman 1547 and Menezes--Okamoto--Vanstone). 1549 Note: The letters GF mean Galois Field, and are quite traditional 1550 mathematics, and every elliptic curve in cryptographic needs to 1551 use some notation for the finite field. 1553 We may therefore describe the curve's Kolmogorov complexity as 21 1554 characters. 1556 Note: The idea of low Kolmogorov complexity is hard to specify 1557 exactly. Nonetheless, a claim of nearly minimal Kolmogorov 1558 complexity is quite falsifiable. The falsifier need merely 1559 specify several (secure) elliptic curves using 21 or fewer 1560 characters. (But if the specification new interpretations, then 1561 new interpretation might also be used to further compress the 1562 specification of 2y^2=x^3+x/GF(8^91+5) to below 21 characters.) 1564 The curve is actually isomorphic to a curve specifiable in 20 1565 characters: 1567 y^2=x^3-x/GF(8^91+5) 1569 Generally, isomorphic curves have essentially equivalently hard 1570 discrete logarithm problems, so one could argue that curve 1571 2y^2=x^3+x/GF(8^91+5) could be rated as having Kolmogorov complexity 1572 at most 20 characters. Isomorphic curves, however, may differ 1573 slightly in security, due to issues of efficiency, and 1574 implementability. The 21-character specification uses an equation 1575 in Montgomery form, which creates an incentive to use the Montgomery 1576 ladder algorithm, which is both safe and efficient [Bernstein?]. 1578 Allowing for non-prime fields, then the binary-field curve known 1579 sect283k1 has a 22-character description: 1581 y^2+xy=x^3+1/GF(2^283) 1583 This has a longer overall specification, but the field part is 1584 shorter field specification. Perhaps an isomorphic curve can be 1585 found (one with three terms), so that total length is 20 or fewer 1586 characters. 1588 Internet-Draft 2020-04-03 1590 However, a non-prime field tends to be slower in software, and is 1591 perhaps riskier due to some recent research on attacking non-prime 1592 field discrete logarithms and elliptic curves, such as recent 1593 asymptotic advances on discrete logarithms in low-characteristic 1594 fields [HPST] and [Nagao]. According to [Teske], some 1595 characteristic-two elliptic curves could be equipped with a secretly 1596 embedded backdoor. 1598 The units of characters as measuring Kolmogorov complexity is not 1599 calibrated as bits of information. Doing so formally would be very 1600 difficult, but the following approach might be reasonable. 1602 Set the criteria for the elliptic curve. For example, e.g. prime 1603 field, size, resistance (of say 2^128 bit operations) to known 1604 attacks on the discrete logarithm problem (Pollard rho, MOV, etc.). 1605 Then list all the possible ECC curve specification with Kolmogorov 1606 complexity of 21 characters or less. Take the base two logarithm of 1607 this number. This is then an calibrated estimate of the number of 1608 bits needed to specify the curve. It should be viewed as a lower 1609 bound, in case some curves were missed. To be completed. 1611 Low Kolmogorov complexity is not directly correlated with security 1612 of the curve. 1614 Note: Indeed, as shown further below, the very insecure examples 1615 exist with lower complexity, by choosing a defective curve 1616 equation. 1618 The benefit of low Kolmogorov complexity is an idea, which general 1619 to cryptography, sometimes called nothing-up-my-sleeve, or 1620 subversion-resistance, or similar. For elliptic curves, the benefit 1621 may be stated as the two following gains. 1623 - Low Kolmogorov complexity defends against insertion of a keyed 1624 trapdoor, meaning the curve can broken using a secret trapdoor, 1625 by an algorithm (eventually discovered by the public at large). 1626 For example, the Dual EC DRBG is known to capable of having such 1627 a trapdoor. Such a trapdoor would information-theoretically 1628 imply an amount of information, comparable the size of the 1629 secret, to be embedded in the curve specification. If the 1630 calibrated estimate for the number of bits is sufficiently 1631 accurate, then such a key cannot be large. 1633 Internet-Draft 2020-04-03 1635 - Low Kolmogorov complexity defends against a secret attack 1636 (presumably difficult to discover), which affects a subset of 1637 curves such that (a) whether or not a specific curve is affected 1638 is a somewhat pseudorandom function of its natural 1639 specification, and (b) the probably of a curve being affected 1640 (when drawn uniformly from some sensible of curve 1641 specification), is low. For an example of real-world attacks 1642 meeting the conditions (a) and (b) consider the MOV attack. 1643 Exhaustively finding curve meeting these two conditions is 1644 likely to prevent low Kolmogorov complexity, essentially by the 1645 low probability of the attack, and the independence of attack's 1646 success from the natural Kolmogorov complexity. 1648 - Even more hypothetically, there may yet exist undisclosed 1649 classes of weak curves, or attacks, for which 1650 2y^2=x^3+x/GF(8^91+5) is lucky enough to avoid. This would be a 1651 fluke. A real-world example is prime-order, or low cofactor 1652 curves, which are are among all curves, but which better resist 1653 the Pohlig--Hellman attack. 1655 Of course, low Kolmogorov complexity is not a panacea. The worst 1656 failure would be attacks that increase in strength as Kolmogorov 1657 complexity gets lower. Two examples illustrate this strongly. 1659 Singular cubics, though not formally elliptic curves, are arguably 1660 among the same class of object, and can be described similarly, 1661 using equations and so. For smooth singular curves (irreducible 1662 cubics) a group can be define, using more or less the same 1663 arithmetic as for a elliptic curve. For example y^2=x^3/GF(8^91+5) 1664 is such a cubic. The resulting group has an easy discrete logarithm 1665 problem, because it can be mapped to the field. 1667 Supersingular elliptic curves can also be specified with low 1668 Kolmogorov complexity, and these are vulnerable to MOV attack. 1669 Worse, a low Kolmogorov complexity curve can be described that 1670 suffers from three attacks simultaneously: y^2=x^3+1/GF(2^127-1). 1671 To be completed. 1673 Of course, the weak cubics are vulnerable to extremely well-known 1674 attacks, so when estimating the bits of information in the 1675 Kolmogorov complexity of curves that resist known attacks, we can 1676 ignore such examples. The point of these examples, however, is to 1677 demonstrate that there exists known attacks that affect curves of 1678 low Kolmogorov complexity, and therefore secret attacks might have 1679 the same property. 1681 Internet-Draft 2020-04-03 1683 So, it is sensible to disclaim any resistance to secret attacks of 1684 such a nature. For this reason, 2y^2=x^3+x/GF(8^91+5) should be 1685 used with other elliptic curves. 1687 Appendix C. Pseudocode 1689 This section uses a C-like pseudocode to demonstrate both the 1690 well-known algorithms one can use implement this curve, and some 1691 details particular to this curve. 1693 Note: Some implementers, such as C programmers, may prefer such 1694 pseudocode over the wordy and formulaic specifications given 1695 earlier in this draft. Besides the principles and algorithms are 1696 well-known, so I have opted to put the pseudocode in a more 1697 runnable form than traditional language-agnostic pseudocode. 1699 Note: The pseudocode is not standard C (e.g., it uses non-standard 1700 C type __int128), not portable, not thoroughly hardened against 1701 side channels or any other implementation attacks. 1703 Note: The pseudocode is highly constricted to minimize line and 1704 character counts, with Python-like indentation and Lisp-like 1705 clumping of closing delimiters. Tools may exist that can put 1706 transform the pseudocode into more conventional C indentation. 1707 The pseudocode borrows various yet further C brevities: some 1708 idiomatic and conventional, some altogether peculiar. Anything 1709 too indecipherable deserves explanation in a future revision of 1710 this draft. 1712 Note: this pseudocode has not yet received any independent review. 1714 C.1. Scalar multiplication of 34-byte strings 1716 The pseudocode for scalar multiplication provides an interface for 1717 scalar multiplication. A function takes as input 3 pointer to 1718 unsigned character strings; it also returns a Boolean value, 1719 indicating success or failure. 1721 The pseudocode is to be consider to form a single file, pseudo.c, 1722 which is then include into other 3 pieces pseudocode: one to 1723 generate test vectors, one to demo a command-line Diffie--Hellman, 1724 one to demo public-key validation and twist insecurity of the curve. 1726 The file pseudo.c has two sections, one for field arithmetic, and 1727 one form scalar multiplication using Montgomery's ladder. 1729 Internet-Draft 2020-04-03 1731 Note: I have been able to improve the speed of Montgomery's ladder 1732 by ~10% using Bernstein's 2-D ladder. I have also been to improve 1733 the speed by ~20% using Gallant--Lambert--Vanstone and Edwards 1734 coordinates. These improvements are not likely to carry through 1735 to a proper optimization regime, since I never used any assembly 1736 optimizations. Also these improvements involve more complex 1737 algorithms, which may suffer higher risk of implementation 1738 attacks. 1740 To be completed. 1742 C.1.1. Field arithmetic for GF(8^91+5) 1744 The field arithmetic pseudocode, is the first part of the file 1745 pseudo.c, implements all the necessary field operations to implement 1746 a Montgomery for elliptic curve 2y^2=x^3+x. This means that it does 1747 not include a square computation: instead it has a Legendre symbol 1748 computation. 1750 Note: The Legendre symbol is used for public-key validation. The 1751 pseudocode implements field inversion and the Legendre symbol 1752 using exponentiation, with the aim of being simple and 1753 constant-time. Alternative algorithms for these tasks are known 1754 to experts. 1756 Internet-Draft 2020-04-03 1758 1759 #define RZ return z 1760 #define B 34 1761 #define F4j i j=5;for(;j--;) 1762 #define FIX(j,r,k) q=z[j]>>r, z[j]-=q<b)-(a>55*k&((k<2)*M-1)) 1766 #define MUL(m,E)\ 1767 zz[0]=m(0,0)E(1,4)E(2,3)E(3,2)E(4,1),\ 1768 zz[1]=m(0,1)m(1,0)E(2,4)E(3,3)E(4,2),\ 1769 zz[2]=m(0,2)m(1,1)m(2,0)E(3,4)E(4,3),\ 1770 zz[3]=m(0,3)m(1,2)m(2,1)m(3,0)E(4,4),\ 1771 zz[4]=m(0,4)m(1,3)m(2,2)m(3,1)m(4,0);\ 1772 z[0]=R(0,0)-R(4,1)*20-R(3,2)*20,\ 1773 z[1]=R(1,0)+R(0,1)-R(4,2)*20,\ 1774 z[2]=R(2,0)+R(1,1)+R(0,2),\ 1775 z[3]=R(3,0)+R(2,1)+R(1,2),\ 1776 z[4]=R(4,0)+R(3,1)+R(2,2);\ 1777 z[1]+=z[0]>>55; z[0]&=M-1; 1778 typedef long long i;typedef i*f,F[5];typedef __int128 ii,FF[5]; 1779 i M=((i)1)<<55;F O={0},I={1}; 1780 f fix(f z){i j=0,q; 1781 for(;j<5*2;j++) FIX(j%5,(j%5<4?55:53),(j%5<4?1:-5)); 1782 z[0]+=(q=z[0]<0)*5; z[4]+=q<<53; RZ;} 1783 i cmp(f x,f y){i z=(fix(x),fix(y),0); F4j z+=!z*CMP(x[j],y[j]); RZ;} 1784 f add(f z,f x,f y){F4j z[j]=x[j]+y[j]; RZ;} 1785 f sub(f z,f x,f y){F4j z[j]=x[j]-y[j]; RZ;} 1786 f mal(f z,i s,f y){F4j z[j]=y[j]*s; RZ;} 1787 f mul(f z,f x,f y){FF zz; MUL(+XY,-20*XY); {F4j zz[j]=0;} RZ;} 1788 f squ(f z,f x){mul(z,x,x); RZ;} 1789 i inv(f z){F t;i j=272; for(mul(z,z,squ(t,z));j--;) squ(t,t); 1790 return mul(z,t,z), (sub(t,t,t)), cmp(O,z);} 1791 i leg(f y){F t;i j=270; for(squ(t,squ(y,y));j--;) squ(t,t); 1792 return j=cmp(I,mul(y,y,t)), (sub(y,y,y),sub(t,t,t)), !j;} 1793 1795 This pseudocode makes uses of some extra C-like pseudocode features: 1797 - #define is used to create macros, which expand within the source 1798 code (as in C pre-processing). 1800 - type ii is 128-bit integer 1802 - multiplying a type i by a type ii variable yields a type ii 1803 variable. If both inputs can fit into a type i variable, then 1804 the result has no overflow or reduction: it is exact as a product 1805 of integers. 1807 Internet-Draft 2020-04-03 1809 - type ff is array of five type ii values. It is used to represent 1810 a field in a radix expansion, except the limbs (digits) can be 1811 128-bits instead of 64-bits. The variable zz has type ff and is 1812 used to intermediately store the product of two field element 1813 variables x and y (of type f). 1815 - function mod takes an ff variable and produce f variable 1816 representing the same field element. A pseudocode example may be 1817 defined further below. 1819 TO DO: Add some notes (answer these questions): 1821 - How small the limbs of the inputs to function mul and squ must be 1822 to ensure no overflow occurs? 1824 - How small are the limbs of the output of functions mul and squ? 1826 TO DO: add notes answering these questions: 1828 - How small must be the input limbs to avoid overflow? 1830 - How small are the output limbs (to know how to safely use of 1831 output in further calculations). 1833 Note: The partial reduction technique used in the multiplication 1834 pseudocode is sometimes known as lazy reduction. It aims to do 1835 just enough calculation to avoid overflow errors, and thus it may be 1836 regarded as attempt at optimization. 1838 To be completed. 1840 The input variable is x and the output variable is b. The declared 1841 types and functions are as follows: 1843 - type c: curve representative, length-34 array of non-negative 1844 8-bit integers ("characters"), 1846 - type f: field element, a length-5 array of 64-bit integers 1847 (negatives allowed), representing a field element as an integer in 1848 base 2^55, 1850 - type i: 64-bit integers (e.g. entries of f), 1852 - function mal: multiply a field element by a small integer (result 1853 stored in 1st argument), 1855 - function fix: fully reduce an integer modulo 8^91+5, 1857 Internet-Draft 2020-04-03 1859 - function cmp: compare two field element (after fixing), returning 1860 -1, 0 or 1. 1862 Note: The two for-loops in the pseudocode are just radix 1863 conversion, from base 2^55 to base 2^8. Because both bases are 1864 powers of two, this amount to moving bits around. The entries of 1865 array b are compute modulo 256. The second loop copies the bits 1866 that the first loop misses (the bottom bits of each entry of f). 1868 Note: Encoding is lossy, several different (x,y) may encode to the 1869 same byte string b. Usually, if (x,y) generated as a part of 1870 Diffie--Hellman key exchange, this lossiness has no effect. 1872 Note: Encoding should not be confused with encryption. Encoding 1873 is merely a conversion or representation process, whose inverse is 1874 called decoding. 1876 - the expression (i)b[j] means that 8-bit integer b[j] is converted 1877 to a 64-bit integer (so is no longer treated modulo 256). (In C, 1878 this is operation is called casting.) 1880 Note: the decode function 'feed' only has 1 for-loop, which is the 1881 approximate inverse of the first of the 2 for-loops in the encode 1882 function 'bite'. The reason the 'bite' needs the 2nd for-loop is 1883 due to the lossy conversion from integers to bytes, whereas in the 1884 other direction the conversion is not lossy. The second loop 1885 recovers the lost information. 1887 C.1.2. Montgomery ladder scalar multiplication 1889 The pseudocode below, the second part of the file pseudo.c, 1890 implements Montgomery's well-known ladder algorithm for elliptic 1891 curve scalar point multiplication, as it applies to the curve 1892 2y^2=x^3+x. 1894 Again, the pseudocode is a continuation of the pseudocode for field 1895 arithmetic, and all previous definitions are assumed. 1897 Internet-Draft 2020-04-03 1899 1900 #define X z[0] 1901 #define Z z[1] 1902 typedef void _;typedef volatile unsigned char *c,C[B]; 1903 typedef F*e,E[2];typedef E*v,V[2]; 1904 f feed(f x,c z){i j=((mal(x,0,x)),B); 1905 for(;j--;) x[j/7]+=((i)z[j])<<((8*j)%55); return fix(x);} 1906 c bite(c z,f x){F t;i j=((fix(mal(x,cmp(mal(t,-1,x),x),x))), B),k=5; 1907 for(;j--;) z[j]=x[j/7]>>((8*j)%55); {(sub(t,t,t));} 1908 for(;--k;) z[7*k-1]+=x[k]<<(8-k); {(sub(x,x,x));} RZ;} 1909 i lift(e z,f x,i t){F y;return mal(X,1,x),mal(Z,1,I),t|| 1910 leg(mal(y,2,add(y,x,mul(y,x,squ(y,x)))));} 1911 i drop(f x,e z){return 1912 inv(Z)&&mul(x,X,Z)&&(sub(X,X,X)&&sub(Z,Z,Z));} 1913 _ let(e z,e y){i j=2;for(;j--;)mal(z[j],1,y[j]);} 1914 _ smv(v z,v y){i j=4;for(;j--;)add(((e)z)[j],((e)z)[j],((e)y)[j]);} 1915 v mav(v z,i a){i j=4;for(;j--;)mal(((e)z)[j],a,((e)z)[j]);RZ;} 1916 _ due(e z){F a,b,c,d; 1917 mal(X,2,mul(X,squ(a,add(a,X,Z)),squ(b,sub(b,X,Z)))); 1918 mul(Z,add(c,a,b),sub(d,a,b));} 1919 _ ade(e z,e u,f w){F a,b,c,d;f ad=a,bc=b; 1920 mul(ad,add(a,u[0],u[1]),sub(d,X,Z)), 1921 mul(bc,sub(b,u[0],u[1]),add(c,X,Z)); 1922 squ(X,add(X,ad,bc)),mul(Z,w,squ(Z,sub(Z,ad,bc)));} 1923 _ duv(v a,e z){ade(a[1],a[0],z[0]);due(a[0]);} 1924 v adv(v z,i b){V t; 1925 let(t[0],z[1]),let(t[1],z[0]);smv(mav(z,!b),mav(t,b));mav(t,0);RZ;} 1926 e mule(e z,c d){V a;E o={{1}};i 1927 b=0,c,n=(let(a[0],o),let(a[1],z),8*B); 1928 for(;n--;) c=1&d[n/8]>>n%8,duv(adv(a,c!=b),z),b=c; 1929 let(z,*adv(a,b)); (due(*mav(a,0))); RZ;} 1930 C G={23,1}; 1931 i mulch(c db,c d,c b){F x;E p; return 1932 lift(p,feed(x,b),(db==d||b==G))&&drop(x,mule(p,d))&&bite(db,x);} 1933 1935 The pseudocode function mulch -- which multiplies byte string 1936 (character) representations of point b by the byte string 1937 representation of integer d -- omits public key validation of the 1938 input point b if the base of scalar multiplication is the chosen 1939 fixed base, or if the input integer d and output point db have the 1940 same location. 1942 The reason for the latter omission of public key validation is the 1943 integer d is overwritten presumably the caller of mulch intended to 1944 use d only once, so that d is likely to be an ephemeral secret, 1945 largely obviating the need to validate b. 1947 Internet-Draft 2020-04-03 1949 In other words, the caller of mulch can control whether public key 1950 validation is done by choosing the locations of db, b, b 1951 appropriately. (An alternative would be for mulch to include a flag 1952 to indicate whether b needs to be validated. Instead, the 1953 pseudocode tries to make mulch do the sensible choice for 1954 Diffie--Hellman if the caller forgets whether public key validation 1955 is necessary.) 1957 The pseudocode files tv.c, dhe.c and pkv.c, define in the sections 1958 below, demonstrate the use of mulch, and its features regarding 1959 public key validation. 1961 In case, mulch returns a Boolean-valued integer indicating whether b 1962 was valid. If validation was requested by the interface, and b is 1963 invalid, then mulch return false (0), and the memory location db 1964 should remain unaltered. 1966 Note: the pseudocode makes types c and C volatile, with the aim 1967 that the C compiler will preserve attempts to zeroize values of 1968 this type. Such zeroization steps in the pseudocode do add 1969 clutter to the code, but have usually been delimited by 1970 parentheses or braces to indicate their implementation-specific 1971 purpose. 1973 C.1.3. Bernstein's 2-dimensional Montgomery ladder 1975 Bernstein's 2-dimensional ladder is a variant of Montgomery's ladder 1976 that computes aP+bQ, for any two points P and Q, more quickly than 1977 computing aP and bQ separately. 1979 Curve 2y^2=x^3+x has an efficient endomorphism, which allows a point 1980 Q = [i+1]P to compute efficiently. Gallant, Lambert and Vanstone 1981 introduced a method (now called the GLV method), to compute dP more 1982 efficiently, given such an efficient endomorphism. They write d = a 1983 + eb where e is the integer multiplier corresponding to the 1984 efficient endomorphism, and a and b are integers smaller than d. 1985 (For example, 17 bytes each instead of 34 bytes.) 1987 The GLV method can be combined with Bernstein's 2D ladder algorithm 1988 to be applied to compute dP = (a+be)P = aP + beP = aP + bQ, where 1989 e=i+1. 1991 This algorithm is not implemented by any pseudocode in the version 1992 the draft. (Previous versions had it.) 1994 See [B1] for further explanation and example pseudocode. 1996 Internet-Draft 2020-04-03 1998 I have estimate a ~10% speedup of this method compared to the plain 1999 Montgomery ladder. However, the code is more complicated, and 2000 potentially more vulnerable to implementation-based attacks. 2002 C.1.4. GLV in Edwards coordinates (Hisil--Carter--Dawson--Wong) 2004 To be completed. 2006 It is also possible to convert to Edwards coordinates, and then use 2007 the Hisil--Carter--Dawson--Wong (HCDW) elliptic curve arithmetic. 2009 The HCDW arithmetic can be combined with the GLV techniques to 2010 obtain a scalar multiplication potentially more efficient than 2011 Bernstein's 2-dimensional Montgomery. The downside is that it may 2012 require key-dependent array look-ups, which can be a security risk. 2014 I have implemented this, finding ~20% speed-up over my 2015 implementation of the Montgomery ladder. However, this speed-up may 2016 disappear upon further optimization (e.g. assembly), or further 2017 security hardening (safe table lookup code). 2019 C.2 Pseudocode for test vectors 2021 The following pseudocode, describing the contents of a file tv.c, 2022 includes the previously defined file pseudo.c, and stdio.h, and then 2023 generates some test vectors. 2025 2026 #include 2027 #include "pseudo.c" 2028 #define M mulch 2029 void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");} 2030 int main (void){i j=1e5/2,wait=/*your mileage may vary*/7000; 2031 C x="TEST 2y^2=x^3+x/GF(8^91+5)",y="yet another test",z; 2032 M(z,x,G); hx(x),hx(G),hx(z); 2033 fprintf(stderr,"%30s(wait=~%ds, ymmv)","",j/wait); 2034 for(;j--;)if(fprintf(stderr,"\r%7d\r",j),!(M(z,x,z)&&M(x,z,G))) 2035 j=0*printf("Mulch fail rate ~%f :(\n",(2*j)/1e5);//else//debug 2036 hx(x),hx(z); 2037 M(y,y,G);M(y,y,y); 2038 for(M(z,G,G),j=900;j--;)M(z,x,z);for(j=900;j--;)M(z,y,z);hx(z); 2039 for(M(z,G,G),j=900;j--;)M(z,y,z);for(j=900;j--;)M(z,x,z);hx(z);} 2040 2042 To be completed: Explain this properly, if possible. 2044 The test vectors should output this: 2046 Internet-Draft 2020-04-03 2048 000000000000000029352b31395e382846472f782b335e783d325e79322054534554 2049 00000000000000000000000000000000000000000000000000000000000000000117 2050 c8c0f2f404a9fabc91c939d8ea1b9e258d82e21a427b549f05c832cf8d48296ffad7 2051 5f336f56f86de3d52b0eab85e527f2ac7b9d77605c0d5018f5faa4243fd462b1badd 2052 fc023b3f03b469dca32446db80d9b388d753cc77aa4c3ee7e2bb86e99e7bed38f509 2053 8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221 2054 8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221 2056 C.3. Pseudocode for a command-line demo of Diffie--Hellman 2058 The following code, representing a file dhe.c, is a bilingual: being 2059 valid C and bash script. 2061 As a bash script, it will compile the C code as dhe, then run it 2062 twice, once as Alice and once as Bob, piping the ephemeral public 2063 keys, and writing the resulting Diffie--Hellman agreed secret keys 2064 into pipes. The agreed secret keys are fed into SHA-256 to 2065 demonstrate their equality, but also to show the typical way to use 2066 DH agree keys (to hash them rather than use them directly). 2068 This pseudocode assumes a Linux-like system. 2070 2071 #include "pseudo.c" /* dhe.c (also a bash script) 2072 : demos ephemeral DH, also creates, clobbers files dhba dha dhb 2073 : -- Dan Brown, BlackBerry, '19 */ 2074 #include 2075 _ get(c p,_*f){if(f)while(!fread((_*)p,B,1,f));} 2076 _ put(c p,_*f){if(f)fwrite((_*)p,B,1,f),fflush(f); bite(p,O);} 2077 int main (_){C s="/dev/urandom",p="EPHEMERAL s => OK if p INVALID"; 2078 get(s,fopen((_*)s,"r")), mulch(p,s,G), put(p,stdout); 2079 get(p,stdin), mulch(s,s,p), put(s,stderr);} /*' 2080 [ dhe.c -nt dhe ] && gcc -O3 dhe.c -o dhe && echo "$(/dev/null || ([ ! -p dhba ] && :> dhba) 2082 ./dhe dha | ./dhe >dhba 2>dhb & 2083 sha256sum dha & sha256sum dhb # these should be equal 2084 (for f in dh{a,b,ba} ; do [ -f $f ] && \rm -f $f; done)# '*/ 2085 2087 C.4 Pseudocode for public-key validation and twist insecurity 2089 The following pseudocode, describing a file pkv.c, demonstrates the 2090 public-key validation features of mulch from pseudo.c, by 2091 deliberately supplying invalid points to mulch. It also 2092 demonstrates how to turn PKV on and off using the mulch interface. 2094 Internet-Draft 2020-04-03 2096 It also demonstrates the need for PKV despite using the Montgomery 2097 by finding points of low order on the twist of the curve, and 2098 showing that such points can leak bits of the secret multiplier. 2100 It further demonstrates the order of the curve, and complex 2101 multiplication by i, and the fact the 34-byte representation of 2102 points is unaffected by multiplication by i. 2104 2105 #include 2106 #include "pseudo.c" 2107 #define M mulch // works with +/- x, so P ~ -P ~ iP ~ -iP 2108 void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");} 2109 int main (void){i j;// sanity check, PKV, twist insecurity demo 2110 C y="TEST 2y^2=x^3+x/GF(8^91+5)",z="zzzzzzzzzzzzzzzzzzzz", 2111 q = "\xa9\x38\x04\xb8\xa7\xb8\x32\xb9\x69\x85\x41\xe9\x2a" 2112 "\xd1\xce\x4a\x7a\x1c\xc7\x71\x1c\xc7\x71\x1c\xc7\x71\x1c" 2113 "\xc7\x71\x1c\xc7\x71\x1c\x07", // q=order(G) 2114 i = "\x36\x5a\xa5\x56\xd6\x4f\xb9\xc4\xd7\x48\x74\x76\xa0" 2115 "\xc4\xcb\x4e\xa5\x18\xaf\xf6\x8f\x74\x48\x4e\xce\x1e\x64" 2116 "\x63\xfc\x0a\x26\x0c\x1b\x04", // i^2=-1 mod q 2117 w5= "\xb4\x69\xf6\x72\x2a\xd0\x58\xc8\x40\xe5\xb6\x7a\xfc" 2118 "\x3b\xc4\xca\xeb\x65\x66\x66\x66\x66\x66\x66\x66\x66\x66" 2119 "\x66\x66\x66\x66\x66\x66\x66"; // w5=(2p+2-72q)/5 2120 for(j=0;j<=3;j++)M(z,(C){j},G),hx(z); // {0,1,2,3}G, but reject 0G 2121 M(z,q,G),hx(z); // reject qG; but qG=O, under hood: 2122 {F x;E p;lift(p,feed(x,G),1);mule(p,q);hx(bite(z,p[1]));} 2123 for(j=0;j<0*25;j++){F x;E p;lift(p,feed(x,(C){j,1}),1);mule(p,q); 2124 printf("%3d ",j),hx(bite(z,p[1]));}// see j=23 for choice of G 2125 for(j=3;j--;)q[0]-=1,M(z,q,G),hx(z);// (q-{1,2,3})G ~ {1,2,3}G 2126 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 2127 M(w5,w5,(C){5}),hx(w5);// twist, ord(w5)=5, M(z,z,p) skipped PKV(p) 2128 M(G,(C){1},w5),hx(G);// reject w5 (G unch.); but w5 leaks z mod 5: 2129 for(j=10;j--;)M(z,y,G),z[0]+=j,M(z,z,w5),hx(z);} 2130 2132 C.5. Elligator i 2134 To be deleted (or completed). 2136 This pseudocode would show how to implement to the Elligator i map 2137 from byte strings to points. This is INCOMPATIBLE with pseudocode 2138 above. 2140 Pseudocode (to be verified): 2142 Internet-Draft 2020-04-03 2144 2145 typedef f xy[2] ; 2146 #define X p[0] 2147 #define Y p[1] 2148 lift(xy p, f r) { 2149 f t ; i b ; 2150 fix(r); 2151 squ(t,r); // r^2 2152 mul(t,I,t); // ir^2 2153 sub(t,(f){1},t); // 1-ir^2 2154 inv(t,t); // 1/(1-ir^2) 2155 mal(t,3,t); // 3/(1-ir^2) 2156 mul(t,I,t); // 3i/(1-ir^2) 2157 sub(X,I,t); // i-3i/(1-ir^2) 2158 b = get_y(t,X); 2159 mal(t,1-b,I); // (1-b)i 2160 add(X,X,t); // EITHER x OR x + i 2161 get_y(Y,X); 2162 mal(Y,2*b-1,Y); // (-1)^(1-b)"" 2163 fix(X); fix(Y); 2164 } 2166 drop(f r, xy p) 2167 { 2168 f t ; i b,h ; 2169 fix(X); fix(Y); 2170 get_y(t,X); 2171 b=eq(t,Y); 2172 mal(t,1-b,I); 2173 sub(t,X,t); // EITHER x or x-i 2174 sub(t,I,t); // i-x 2175 inv(t,t); // 1/(i-x) 2176 mal(t,3,t); // 3/(i-x) 2177 add(t,I,t); // i+ 3/(i-x) 2178 mal(t,-1,t); // -i-3/(i-x)) = (1-3i/(i-x))/i 2179 b = root(r,t) ; 2180 fix(r); 2181 h = (r[4]<(1LL<<52)) ; 2182 mal(r,2*h-1,r); 2183 fix(r); 2184 } 2186 Internet-Draft 2020-04-03 2188 elligator(xy p,c b) {f r; feed(r,b); lift(p,r);} 2190 crocodile(c b,xy p) {f r; drop(r,p); bite(b,r);} 2191 2193 D. Primality proofs and certificates 2195 Recent work of Albrecht and others [AMPS] has shown the combination 2196 of an adversarially chosen prime, and users using improper 2197 probabilistic primality tests can make user vulnerable to an attack. 2199 The adversarial primes in this attack are typically the result of an 2200 exhaustive search. They therefore contain an amount of information 2201 corresponding to the length of their search, putting a predictable 2202 lower bound on their Kolmogorov complexity. 2204 The two primes involved for 2y^2=x^3+x/GF(8^91+5) should perhaps 2205 already resist [AMPS] because of the following compact 2206 representation of these primes: 2208 p = 8^91+5 2209 q = #(2y^2=x^3+x/GF(8^91+5))/72 2211 This attack [AMPS] can also be resisted by: 2213 - properly implementing probabilistic primality test, or 2214 - implementing provable primality tests. 2216 Provable primality tests can be very slow, but can be separated into 2217 two steps: 2219 -- a slow certificate generation, and 2221 -- a fast certificate verification. 2223 The certificate is a set of data, representing an intermediate step 2224 in the provable primality test, after which the completion of the 2225 test is quite efficient. 2227 Pratt primality certificate generation for any prime p, involves 2228 factorizing p-1, which can be very slow, and then recursively 2229 generating a Pratt primality certificate for each prime factor of 2230 p-1. Essentially, each prime has a unique Pratt primality 2231 certificate. 2233 Internet-Draft 2020-04-03 2235 Pratt primality certificate verification of (p-1), involves search 2236 for g such that 1 = (g^(p-1) mod p) and 1 < (g^((p-1)/q) mod p) for 2237 each q dividing p-1, and then recursively verifying each Pratt 2238 primality certificate for each prime factor q of p-1. 2240 In this document, we specify a Pratt primality certificate as a 2241 sequence of (candidate) primes each being 1 plus a product of 2242 previous primes in the list, with certificate stating this product. 2244 Although Pratt primality certificate verification is quite 2245 efficient, an ECC implementation can opt to trust 8^91+5 by virtue 2246 of verifying the certificate once, perhaps before deployment or 2247 compile time. 2249 D.1. Pratt certificate for the field size 8^91+5 2251 Define 52 positive integers, a,b,c,...,z,A,...,Z as follows: 2253 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 2254 j=1+aaac k=1+abd l=1+aaf m=1+abf n=1+aacc o=1+abg p=1+al q=1+aaag 2255 r=1+abcc s=1+abbbb t=1+aak u=1+abbbc v=1+ack w=1+aas x=1+aabbi 2256 y=1+aco z=1+abu A=1+at B=1+aaaadh C=1+acu D=1+aaav E=1+aeff F=1+aA 2257 G=1+aB H=1+aD I=1+acx J=1+aaacej K=1+abqr L=1+aabJ M=1+aaaaaabdt 2258 N=1+abdpw O=1+aaaabmC P=1+aabeK Q=1+abcfgE R=1+abP S=1+aaaaaaabcM 2259 T=1+aIO U=1+aaaaaduGS V=1+aaaabbnuHT W=1+abffLNQR X=1+afFW 2260 Y=1+aaaaauX Z=1+aabzUVY. 2262 Note: variable concatenation is used to indicate multiplication. 2263 For example, f = 1+aab = 1+2*2*(1+2) = 13. 2265 Note: One must verify that Z=8^91+5. 2267 Note: The Pratt primality certificate involves finding a generator 2268 g for each the prime (after the initial prime). It is possible to 2269 list these in the certificate, which can speed up verification by 2270 a small factor. 2272 (2,b), (2,c), (3,d), (2,e), (2,f), (3,g), (2,h), (5,i), (6,j), 2273 (3,k), (2,l), (3,m), (2,n), (5,o), (2,p), (3,q), (6,r), (2,s), 2274 (2,t), (6,u), (7,v), (2,w), (2,x), (14,y),(3,z), (5,A), (3,B), 2275 (7,C), (3,D), (7,E), (5,F), (2,G), (2,H), (2,I), (3,J), (2,K), 2276 (2,L),(10,M), (5,N), (10,O),(2,P), (10,Q),(6,R), (7,S), (5,T), 2277 (3,U), (5,V), (2,W), (2,X), (3,Y), (7,Z). 2279 Internet-Draft 2020-04-03 2281 Note: The decimal values for a,b,c,...,Y are given by: a=2, b=3, 2282 c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=41, k=43, l=53, m=79, 2283 n=101, o=103, p=107, q=137, r=151, s=163, t=173, u=271, v=431, 2284 w=653, x=829, y=1031, z=1627, A=2063, B=2129, C=2711, D=3449, 2285 E=3719, F=4127, G=4259, H=6899, I=8291, J=18041, K=124123, 2286 L=216493, M=232513, N=2934583, O=10280113, P=16384237, Q=24656971, 2287 R=98305423, S=446424961, T=170464833767, U=115417966565804897, 2288 V=4635260015873357770993, W=1561512307516024940642967698779, 2289 X=167553393621084508180871720014384259, 2290 Y=1453023029482044854944519555964740294049. 2292 D.2. Pratt certificate for subgroup order 2294 Define 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new 2295 values: 2297 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 2298 j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b 2299 r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e 2300 z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck 2301 G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG 2302 O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ 2303 V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Z=1+ab3oHOT !=1+a3SUX @=1+abNY! 2304 #=1+a4kzF@ $=1+a3QZ# 2306 Note: numeral after variable names represent powers. For example, 2307 f = 1 + a2b = 1 + 2^2 * 3 = 13. 2309 The last variable, $, is the order of the base point, and the order 2310 of the curve is 72$. 2312 Note: Punctuation used for variable names !,@,#,$, would not scale 2313 for larger primes. For larger primes, a similar format might work 2314 by using a prefix-free set of multi-letter variable names. 2315 E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze: 2317 Acknowledgments 2319 Thanks to John Goyo and various other BlackBerry employees for past 2320 technical review, to Gaelle Martin-Cocher for encouraging submission 2321 of this I-D. Thanks to David Jacobson for sending Pratt primality 2322 certificates. 2324 Internet-Draft 2020-04-03 2326 Author's Address 2328 Dan Brown 2329 4701 Tahoe Blvd. 2330 BlackBerry, 5th Floor 2331 Mississauga, ON 2332 Canada 2333 danibrown@blackberry.com