idnits 2.17.1 draft-hallambaker-threshold-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. 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 : ---------------------------------------------------------------------------- ** The document seems to lack an Authors' Addresses Section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 652 has weird spacing: '... where a_(0)...' == Line 661 has weird spacing: '... where p_(1)...' -- The document date (2 November 2020) is 1271 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'TBS' is mentioned on line 1703, but not defined Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group P. M. Hallam-Baker 3 Internet-Draft ThresholdSecrets.com 4 Intended status: Informational 2 November 2020 5 Expires: 6 May 2021 7 Threshold Modes in Elliptic Curves 8 draft-hallambaker-threshold-04 10 Abstract 12 Threshold cryptography operation modes are described with application 13 to the Ed25519, Ed448, X25519 and X448 Elliptic Curves. Threshold 14 key generation allows generation of keypairs to be divided between 15 two or more parties with verifiable security guaranties. Threshold 16 decryption allows elliptic curve key agreement to be divided between 17 two or more parties such that all the parties must co-operate to 18 complete a private key agreement operation. The same primitives may 19 be applied to improve resistance to side channel attacks. A 20 Threshold signature scheme is described in a separate document. 22 https://mailarchive.ietf.org/arch/browse/cfrg/ 23 (http://whatever)Discussion of this draft should take place on the 24 CFRG mailing list (cfrg@irtf.org), which is archived at . 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at https://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on 6 May 2021. 43 Copyright Notice 45 Copyright (c) 2020 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 50 license-info) in effect on the date of publication of this document. 51 Please review these documents carefully, as they describe your rights 52 and restrictions with respect to this document. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 57 1.1. Applications . . . . . . . . . . . . . . . . . . . . . . 4 58 1.1.1. Cloud control of decryption . . . . . . . . . . . . . 4 59 1.1.2. Device Onboarding . . . . . . . . . . . . . . . . . . 5 60 1.1.3. Cryptographic co-processor . . . . . . . . . . . . . 5 61 1.1.4. Side Channel Resistance . . . . . . . . . . . . . . . 6 62 2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 6 63 2.1. Requirements Language . . . . . . . . . . . . . . . . . . 6 64 2.2. Defined Terms . . . . . . . . . . . . . . . . . . . . . . 6 65 2.3. Related Specifications . . . . . . . . . . . . . . . . . 7 66 2.4. Implementation Status . . . . . . . . . . . . . . . . . . 7 67 3. Threshold Cryptography in Diffie-Hellman . . . . . . . . . . 8 68 3.1. Application to Diffie Hellman (not normative) . . . . . . 8 69 3.2. Threshold decryption . . . . . . . . . . . . . . . . . . 9 70 3.2.1. Direct Key Splitting . . . . . . . . . . . . . . . . 9 71 3.2.2. Direct Decryption . . . . . . . . . . . . . . . . . . 10 72 3.3. Direct threshold key generation . . . . . . . . . . . . . 10 73 3.3.1. Device Provisioning . . . . . . . . . . . . . . . . . 11 74 3.3.2. Key Rollover . . . . . . . . . . . . . . . . . . . . 12 75 3.3.3. Host Activation . . . . . . . . . . . . . . . . . . . 13 76 3.3.4. Separation of Duties . . . . . . . . . . . . . . . . 13 77 3.4. Side Channel Resistance . . . . . . . . . . . . . . . . . 13 78 4. Shamir Secret Sharing . . . . . . . . . . . . . . . . . . . . 14 79 4.1. Shamir secret share generation . . . . . . . . . . . . . 14 80 4.2. Lagrange basis recovery . . . . . . . . . . . . . . . . . 15 81 4.3. Verifiable Secret Sharing . . . . . . . . . . . . . . . . 15 82 4.4. Distributed Key Generation . . . . . . . . . . . . . . . 16 83 5. Application to Elliptic Curves . . . . . . . . . . . . . . . 16 84 5.1. Implementation for Ed25519 and Ed448 . . . . . . . . . . 16 85 5.1.1. Ed25519 . . . . . . . . . . . . . . . . . . . . . . . 17 86 5.1.2. Ed448 . . . . . . . . . . . . . . . . . . . . . . . . 17 87 5.2. Implementation for X25519 and X448 . . . . . . . . . . . 18 88 5.2.1. Point Encoding . . . . . . . . . . . . . . . . . . . 18 89 5.2.2. X25519 Point Encoding . . . . . . . . . . . . . . . . 19 90 5.2.3. X448 Point Encoding . . . . . . . . . . . . . . . . . 19 91 5.2.4. Point Addition . . . . . . . . . . . . . . . . . . . 19 92 5.2.5. Montgomery Ladder with Coordinate Recovery . . . . . 20 93 6. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 22 94 6.1. Threshold Key Generation . . . . . . . . . . . . . . . . 22 95 6.1.1. X25519 . . . . . . . . . . . . . . . . . . . . . . . 22 96 6.1.2. X448 . . . . . . . . . . . . . . . . . . . . . . . . 24 97 6.1.3. Ed25519 . . . . . . . . . . . . . . . . . . . . . . . 26 98 6.1.4. Ed448 . . . . . . . . . . . . . . . . . . . . . . . . 27 99 6.2. Threshold Decryption . . . . . . . . . . . . . . . . . . 29 100 6.2.1. Direct Key Splitting X25519 . . . . . . . . . . . . . 29 101 6.2.2. Direct Decryption X25519 . . . . . . . . . . . . . . 30 102 6.2.3. Direct Key Splitting X448 . . . . . . . . . . . . . . 32 103 6.2.4. Direct Decryption X448 . . . . . . . . . . . . . . . 34 104 6.2.5. Shamir Secret Sharing X448 . . . . . . . . . . . . . 36 105 6.2.6. Lagrange Decryption X448 . . . . . . . . . . . . . . 36 106 7. Security Considerations . . . . . . . . . . . . . . . . . . . 36 107 7.1. Complacency Risk . . . . . . . . . . . . . . . . . . . . 36 108 7.2. Rogue Key Attack . . . . . . . . . . . . . . . . . . . . 37 109 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 37 110 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 38 111 10. Appendix A: Calculating Lagrange coefficients . . . . . . . . 38 112 11. Normative References . . . . . . . . . . . . . . . . . . . . 38 113 12. Informative References . . . . . . . . . . . . . . . . . . . 38 115 1. Introduction 117 Public key cryptography provides greater functionality than symmetric 118 key cryptography by introducing separate keys for separate roles. 119 Knowledge of the public encryption key does not provide the ability 120 to decrypt. Knowledge of the public signature verification key does 121 not provide the ability to sign. Threshold cryptography extends the 122 scope of traditional public key cryptography with further separation 123 of roles by splitting the private key. This allows greater control 124 of (e.g.) decryption operations by requiring the use of two 125 decryption key shares rather than just the decryption key. 127 This document describes threshold modes for decryption and key 128 generation for the elliptic curves described in [RFC7748] and 129 [RFC8032]. Both schemes are interchangeable in their own right but 130 require minor modifications to the underlying elliptic curve systems 131 to encode the necessary information in the public (X25519/X448) or 132 private key (Ed25519/Ed448). The companion document 133 [draft-hallambaker-threshold-sigs] describes a threshold mode for 134 [RFC8032] signatures. 136 In its most general form, threshold cryptography allows a private key 137 to be divided between (_n_, _t_) shares such that _n_ is the total 138 number of shares created and _t_ is the threshold number of shares 139 required to perform the operation. For most applications however, 140 the number of shares is the same as the threshold (_n_ = _t_) and the 141 most common case is (_n_ = _t_ = 2). 143 This document sets out the principles that support the definition 144 threshold modes in elliptic curve Diffie Hellman system first using 145 simple additive key sharing, an approach which is limited to the case 146 (_n_ = _t_). The use of Shamir secret sharing [Shamir79] is then 147 described to support the case (_n_ > _t_). For convenience, we refer 148 to the non Shamir secret sharing case as 'direct key sharing'. 150 1.1. Applications 152 Development of the threshold modes described in this document and the 153 companion document [draft-hallambaker-threshold-sigs] were motivated 154 by the following applications. 156 1.1.1. Cloud control of decryption 158 The security of data at rest is of increasing concern in enterprises 159 and for individual users. Transport layer security such as TLS and 160 SSH provide effective confidentiality controls for data in motion but 161 not for data at rest. 163 Of particular concern is the case in which a large store of 164 confidential data is held on a server. Encryption provides a simple 165 and effective means of protecting the confidentiality of such data. 166 But the real challenge is how to effect decryption of the data on 167 demand for the parties authorized to access it. 169 Storing the decryption keys on the server that holds the data 170 provides no real security advantage as any compromise that affects 171 the server is likely to result in disclosure of the keys. Use of 172 end-to-end security in which each document is encrypted under the 173 public key of each person authorized to access it provides the 174 desired security but introduces a complex key management problem and 175 provides no effective means of revoking access after it is granted. 177 Threshold encryption allows a key service to control decryption of 178 stored data without having the ability to decrypt. The data 179 decryption key is split into two (or more) parts with a different 180 split being created for each user. One decryption share is held at 181 the server allowing it to control access to the data without being 182 able to decrypt. The other decryption share is encrypted under the 183 public encryption key of the corresponding user allowing them to 184 decrypt the stored data but only with the co-operation of the key 185 service. 187 1.1.2. Device Onboarding 189 The term 'onboarding' is used to refer to the configuration of a 190 device for use by a particular user or within a particular 191 enterprise. One of the typical concerns of onboarding is to 192 initialize the device with a set of public key pairs for various 193 purposes and to issue credentials (e.g. PKIX certificates) to enable 194 their use. 196 One of the concerns that arises in such cases is whether keys should 197 be generated on the device on which they are to be used or on another 198 device administering the onboarding process. 200 Both approaches are unsatisfactory. While generation of keys on the 201 device on which they are to be used is generally preferred, 202 experience has shown that many devices, particularly IoT devices use 203 insufficiently random processes to generate such keys and this has 204 led to numerous cases of duplicate and otherwise weak keys being 205 discovered in running systems. 207 Generation of keys on an administration device and transferring them 208 to the device on which they are to be used means that the 209 administration device used for key generation represents a single 210 point of failure. Compromise of this device or of the means used to 211 install the keys will lead to compromise of the device. 213 Threshold key generation allows the advantages of both approaches to 214 be realized avoiding dependence on either the target device or the 215 administration device. 217 1.1.3. Cryptographic co-processor 219 Most real-world compromises of cryptographic security systems involve 220 the disclosure of a private key. Common means of disclosure being 221 inadvertent inclusion in backup tapes, keys being stored on public 222 file shares and (increasingly) keys being inadvertently uploaded to 223 source code management systems. 225 A new and emerging set of key disclosure threats come from the recent 226 generation of hardware vulnerabilities being discovered in CPUs 227 including ROWHAMMER and SPECTRE. 229 The advantages of Hardware Security Modules (HSMs) for storing and 230 using private keys are well established. An HSM allows a private key 231 to be used in an isolated environment that is designed to be 232 resistant to side channel attacks. 234 Regrettably, the 'black box' nature of HSMs means that their use 235 introduces a new security concern - the possibility that the device 236 itself has been compromised during manufacture or in the supply 237 chain. 239 Threshold approaches allows a key exchange or signature operation to 240 be divided between two private keys, one of which is generated by the 241 application that is to use it and the other of which is tightly bound 242 to a specific host such that it cannot be extracted. 244 1.1.4. Side Channel Resistance 246 The same techniques that make threshold cryptography possible are the 247 basis for Kocher's side-channel resistance technique [Kocher96]. 248 Differential side channel attacks are a powerful tool capable of 249 revealing a private key value that is used repeatedly in practically 250 any algorithm. The claims made with respect to 'constant time' 251 algorithms such as the Montgomery ladder depend upon the actual 252 implementation performing operations in constant time. 254 2. Definitions 256 This section presents the related specifications and standard, the 257 terms that are used as terms of art within the documents and the 258 terms used as requirements language. 260 2.1. Requirements Language 262 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 263 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 264 document are to be interpreted as described in [RFC2119]. 266 2.2. Defined Terms 268 The following terms are used as terms of art in this document and the 269 accompanying specification [draft-hallambaker-threshold-sigs]. 271 Dealer A party that coordinates the actions of a group of 272 participants performing a threshold operation. 274 Multi-Encryption The use of multiple decryption fields to allow a 275 document encrypted under a session key to be decrypted by multiple 276 parties under different decryption keys. 278 Multi-Encryption allows a document to be shared with multiple 279 recipients but does not allow the decryption role to be divided 280 between multiple parties. 282 Multi-Signatures The use of multiple independently verifiable 283 digital signatures to authenticate a document. 285 Multi-Signatures allow separation of the signing roles and thus 286 achieve a threshold capability. But they are not true threshold 287 signatures as the set of signers is visible to external parties. 289 Onboarding The process by which an embedded device is provisioned 290 for deployment in a local network. 292 Threshold Key Generation An aggregate public, private key pair is 293 constructed from a set of contributions such that the private key 294 is a function of the private key of all the contributions. 296 A Threshold Key Generation function is auditable if and only if 297 the public component of the aggregate key can be computed from the 298 public keys of the contributions alone. 300 Threshold Decryption Threshold decryption divides the decryption 301 role between two or more parties. 303 Threshold Key Agreement A bilateral key agreement exchange in which 304 one or both sides present multiple public keys and the key 305 agreement value is a function of all of them. 307 This approach allows a party to present multiple credentials in a 308 single exchange, a de 310 Threshold Signatures Threshold signatures divide the signature role 311 between two or more parties in such a way that the parties and 312 their roles is not visible to an external observer. 314 2.3. Related Specifications 316 This document extends the elliptic curve cryptography systems 317 described in [RFC7748] and [RFC8032] to provide threshold 318 capabilities. 320 This work was originally motivated by the requirements of the 321 Mathematical Mesh [draft-hallambaker-mesh-architecture]. 323 Threshold modes for generating signatures compatible with [RFC8032] 324 are described in [draft-hallambaker-threshold-sigs]. 326 2.4. Implementation Status 328 The implementation status of the reference code base is described in 329 the companion document [draft-hallambaker-mesh-developer]. 331 3. Threshold Cryptography in Diffie-Hellman 333 The threshold modes described in this specification are made possible 334 by the fact that Diffie Hellman key agreement and elliptic curve 335 variants thereof support properties we call the Key Combination Law 336 and the Result Combination Law. 338 Let {_X_, _x_}, {_Y_, _y_}, {_A_, _a_} be {public, private} key pairs 339 and r [.] S represent the Diffie Hellman operation applying the 340 private key r to the public key S. 342 The Key Combination law states that we can define an operator [x] 343 such that there is a keypair {_Z_, _z_} such that: 345 _Z_ = _X_ [x] _Y_ and _z_ = (_x_ + _y_) mod _o_ (where _o_ is the 346 order of the group) 348 The Result Combination Law states that we can define an operator [+] 349 such that: 351 (_x_ [.] _A_) [+] (_y_ [.] _A_) = (_z_ [.] _A_) = (_a_ [.] _Z_) 353 It will be noted that each of these laws is interchangeable. The 354 output of the key combination law to a Diffie Hellman key pair is a 355 Diffie Hellman key pair and the output of the result combination law 356 is a Diffie Hellman result. This allows modular and recursive 357 application of these principles. 359 3.1. Application to Diffie Hellman (not normative) 361 Diffie Hellman in a modular field provides a concise demonstration of 362 the key combination and result combination laws [RFC2631]. The 363 realization of the threshold schemes in a modular field is outside 364 the scope of this document. 366 For the Diffie Hellman system in a modular field p, with exponent e: 368 * r [.] S = S^(r) mod p 370 * o = p-1 372 * _A_[x] _B_ = _A_[.] _B_ = _AB_mod _p_. 374 _Proof:_ 376 Let z = x + y 378 By definition, X = e^(x) mod p, Y = e^(y) mod p, and Z = e^(z)mod p. 380 Therefore, 382 Z = e^(z) mod p = e^(x+y) mod p 384 = (e^(x)e^(y)) mod p 386 = e^(x)mod p.e^(y) mod p 388 = X.Y 390 Moreover, A = e^(a) mod p, 392 Therefore, 394 (A^(x) mod p).(A^(y) mod p) = (A^(x)A^(y)) mod p) 396 = (A^(x+y)) mod p) 398 = A^(z) mod p 400 = e^(az) mod p 402 = (e^(z))^(a) mod p 404 = Z^(a) mod p 406 Since e^(o) mod p = 1, the same result holds for z = (x + y) mod o 407 since e^(x+y+no) = e^(x+y).e^(no) = e^(x+y).1 = e^(x+y). 409 3.2. Threshold decryption 411 Threshold decryption allows a decryption key to be divided into two 412 or more parts, allowing these roles to be assigned to different 413 parties. This capability can be employed within a machine to divide 414 use of a private key between an implementation running in the user 415 mode and a process running in a privileged mode that is bound to the 416 machine. Alternatively, threshold cryptography can be employed to 418 The key combination law and result combination law provide a basis 419 for threshold decryption. 421 3.2.1. Direct Key Splitting 423 We begin by creating a base key pair { X, x }. The public component X 424 is used to perform encryption operations by means of a key agreement 425 against an ephemeral key in the usual fashion. The private component 426 x may be used for decryption in the normal fashion or to provide the 427 source material for a key splitting operation. 429 To split the base key into n shares { S_(1), s_(1) }, { S_(2), s_(2) 430 }, ... { S_(n), s_(n) }, we begin by generating the first n-1 private 431 keys in the normal fashion. It is not necessary to generate the 432 corresponding public keys as these are not required. 434 The private key of the final key share s_(n) is given by: 436 _s_(n) = (x - s1 - s2 - ... - sn-1) mod o_ 438 Thus, the base private key x is equal to the sum of the private key 439 shares modulo the group order. 441 3.2.2. Direct Decryption 443 To encrypt a document, we first generate an ephemeral key pair { Y, y 444 }. The key agreement value e^(xy) is calculated from the base public 445 key X = e^(x) and the ephemeral private key y. A key derivation 446 function is then used to obtain the session key to be used to encrypt 447 the document under a symmetric cipher. 449 To decrypt a document using the threshold key shares, each key share 450 holder first performs a Diffie Hellman operation using their private 451 key on the ephemeral public key. The key shares are then combined 452 using the result combination law to obtain the key exchange value 453 from which the session key is recovered. 455 The key contribution c_(i) for the holder of the i^(th) key share is 456 calculated as: 458 c_(i) = Y^(si) 460 The key agreement value is thus 462 A = c_(1) . c_(2) . ... . c_(n) 464 This value is equal to the encryption key agreement value according 465 to the group law. 467 3.3. Direct threshold key generation 469 The key combination law allows an aggregate private key to be derived 470 from private key contributions provided by two or more parties such 471 that the corresponding aggregate public key may be derived from the 472 public keys corresponding to the contributions. The resulting key 473 generation mechanism is thus, auditable and interoperable. 475 3.3.1. Device Provisioning 477 Auditable Threshold Key Generation provides a simple and efficient 478 means of securely provisioning keys to devices. This is encountered 479 in the IoT space as a concern in 'onboarding' and in the provisioning 480 of unique keys for use with cryptographic applications (e.g. SSH, S/ 481 MIME, OpenPGP, etc.). 483 Consider the case in which Alice purchases an IoT connected Device D 484 which requires a unique device key pair _{ X , x }_ for its 485 operation. The process of provisioning (aka 'onboarding') is 486 performed using an administration device. Traditional key pair 487 generation gives us three options: 489 * Generate and install a key pair during manufacture. 491 * Generate a new key pair during device provisioning. 493 * Generate a key pair on the administration device and transfer it 494 to the device being provisioned. 496 The first approach has the obvious disadvantage that the manufacturer 497 has knowledge of the private key. This represents a liability for 498 both the user and the manufacturer. Less obvious is the fact that 499 the second approach doesn't actually provide a solution unless the 500 process of generating keys on the device is auditable. The third 501 approach is auditable with respect to the device being provisioned 502 but not with respect to the administration device being used for 503 provisioning. If that device were to be compromised, so could every 504 device it was used to provision. 506 Threshold key generation allows the administration device and the 507 joining device being provisioned to jointly provision a key pair as 508 follows: 510 * The joining device has public, private key pair_{ D, d }_. 512 * A provisioning request is made for the device which includes the 513 joining device public key _D_. 515 * The administration device generates a key pair contribution _{ A, 516 a }_. 518 * The administration device private key is transmitted to the Device 519 by means of a secure channel. 521 * The joining device calculates the aggregate key pair _{ A [x] D, 522 a+d }_. 524 * The administration device authorizes the joining device to 525 participate in the local network using the public key _A [x] D_. 527 The Device key pair MAY be installed during manufacture or generated 528 during provisioning or be derived from a combination of both using 529 threshold key generation recursively. The provisioning request MAY 530 be originated by the device or be generated by a purchasing system. 532 Note that the provisioning protocol does not require either party to 533 authenticate the aggregate key pair. The protocol provides security 534 by ensuring that both parties obtain the correct results if and only 535 if the values each communicated to the other were correct. 537 Out of band authentication of the joining device public key _D_ is 538 sufficient to prevent Man-in-the-Middle attack. This may be achieved 539 by means of a QR code printed on the device itself that discloses or 540 provides a means of obtaining _D._ 542 [Note add serious warning that a party providing a private 543 contribution MUST make sure they see the public key first. Otherwise 544 a rogue key attack is possible. The Mesh protocols ensure that this 545 is the case but other implementations may overlook this detail.] 547 3.3.2. Key Rollover 549 Traditional key rollover protocols in PKIX and other PKIs following 550 the Kohnfelder model, require a multi-step interaction between the 551 key holder and the Certificate Authority. 553 Threshold key generation allows a Certificate Authority to implement 554 key rollover with a single communication: 556 Consider the case in which the service host has a base key pair { B , 557 b }. A CA that has knowledge of the Host public key B may generate a 558 certificate for the time period _t_ with a fresh key as follows: 560 * Generate a key pair contribution { A_(t), a_(t) }. 562 * Generate and sign an end entity certificate C_(t) for the key B 563 [x] A_(t). 565 * Transmit C_(t), a_(t) to the host by means of a secure channel 567 3.3.3. Host Activation 569 Modern Internet service architectures frequently make use of short 570 lived, ephemeral hosts running on virtualized machines. Provisioning 571 cryptographic material in such environments is a significant 572 challenge and especially so when the underlying hardware is a shared 573 resource. 575 The key rollover approach described above provides a means of 576 provisioning short lived credentials to ephemeral hosts that 577 potentially avoids the need to build sensitive keys into the service 578 image or configuration. 580 3.3.4. Separation of Duties 582 Threshold key generation provides a means of separating 583 administration of cryptographic keys between individuals. This 584 allows two or more administrators to control access to a private key 585 without having the ability to use it themselves. This approach is of 586 particular utility when used in combination with threshold 587 decryption. Alice and Bob can be granted the ability to create key 588 contributions allowing a user to decrypt information without having 589 the ability to decrypt themselves. 591 3.4. Side Channel Resistance 593 Side-channel attacks, present a major concern in the implementation 594 of public key cryptosystems. Of particular concern are the timing 595 attacks identified by Paul Kocher [Kocher96] and related attacks in 596 the power and emissions ranges. Performing repeated observations of 597 the use of the same private key material provides an attacker with 598 considerably greater opportunity to extract the private key material. 600 A simple but effective means of defeating such attacks is to split 601 the private key value into two or more random shares for every 602 private key operation and use the result combination law to recover 603 the result. 605 The implementation of this approach is identical to that for 606 Threshold Decryption except that instead of giving the key shares to 607 different parties, they are kept by the party performing the private 608 key operation. 610 While this approach doubles the number of private key operations 611 required, the operations MAY be performed in parallel. Thus avoiding 612 impact on the user experience. 614 4. Shamir Secret Sharing 616 The direct threshold modes described above may be extended to support 617 the case (_n_ > _t_) through application of Shamir secret sharing and 618 the use of the Lagrange basis to recover the secret value. 620 Shamir Secret Sharing makes use of the fact that a polynomial of 621 degree t-1 is defined by t points on the curve. To share a secret 622 _s_, we construct a polynomial of degree _t-1_ in the modular field 623 _L_ where _L_ > _s_. 625 _f_(_x_) = _s_ + _a_(1)_._x_ + _a_(2)_._x^(2)_ + ... 626 _a_(t-1)_._x^(t-1)_ mod _L_ 628 The shares _p_(1)_, _p_(2)_ ... _p_(n)_ are given by the values 629 _f_(_x_(1)_), _f_(_x_(2)_), ... ,_f_(_x_(n)_) where _x_(1)_, _x_(2)_ 630 ... _x_(n)_ are in the range 1 _x_(i)_ _L_. 632 We can use the Lagrange basis function to construct a set of 633 coefficients l_(1), l_(2), ... l_(t) from a set of _t_ shares p_(1), 634 p_(2) ... p_(t) such that: 636 _s_ = l_(1)p_(1) + l_(2)p_(2) + ... + l_(t)p_(t) mod _L_ 638 Thus, if we choose the sub-group order of the curve as the value of 639 _L_, the formula used to recover the secret _s_ is a sum of terms as 640 was used for the case where _n_ = _t_. We can thus apply a set of 641 Lagrange coefficients provided by the dealer to the secret shares to 642 extend the threshold operations to the case where _n_ > _t_. 644 4.1. Shamir secret share generation 646 To create _n_ shares for the secret _s_ with a threshold of _t_, the 647 dealer constructs a polynomial of degree _t_ in the modular field 648 _L_, where _L_ is the order of the curve sub-group: 650 f(x) = a_(0) + a_(1).x + a_(2).x^(2) + ... a_(t).x^(t-1) mod L 652 where a_(0) = s 654 a_(1) ... a_(t) are randomly chosen integers in the range 1 a_(i) 655 L 657 The values of the key shares are the values _f_(x_(1)), _f_(x_(2)), 658 ... ,_f_(x_(n)). That is 660 p_(i) = _f_(x_(i)) 661 where p_(1) ... p_(n) are the private key shares 663 x_(1) ... x_(n) are distinct integers in the range 1 x_(i) L 665 The means of constructing distinct values x_(1) ... x_(n) is left to 666 the implementation. It is not necessary for these values to be 667 secret. 669 4.2. Lagrange basis recovery 671 Given _n_ shares (_x_(0)_, _y_(0)_), (_x_(1)_, _y_(1)_), ... 672 (_x_(n-1)_, _y_(n-1)_), The corresponding the Lagrange basis 673 polynomials _l_(0)_, _l_(1)_, .. _l_(n-1)_ are given by: 675 l_(m) = ((_x_ - _x_(m0)_) / (_x_(m)_ - x__(m0)_)) . ((_x_ - _x_(m1)_) 676 / (_x_(m)_ - x__(m1)_)) . ... . ((_x_ - _x_(mn-2)_) / (_x_(m)_ - 677 _x_(mn-)_2)) 679 Where the values _m_(0)_, _m_(1)_, ... _m_(n-2)_, are the integers 0, 680 1, .. _n_-1, excluding the value _m_. 682 These can be used to compute _f(x)_ as follows: 684 _f_(_x_) = _y_(0)l0 + y1l1 + ... yn-1ln-1_ 686 Since it is only the value of _f(_0_)_ that we are interested in, we 687 compute the Lagrange basis for the value _x_ = 0: 689 _lz_(m)_ = ((_x_(m1)_) / (_x__(m) - _x_(m1)_)) . ((_x_(m2)_) / 690 (_x_(m)_ - _x_(m2)_)) 692 Hence, 694 _a_(0)_ = _f_(_0_) = _y_(0)lz0 + y1lz1 + ... yn-1ln-1_ 696 4.3. Verifiable Secret Sharing 698 The secret share generation mechanism described above allows a 699 private key to be split into _n_ shares such that _t_ shares are 700 required for recovery. While this supports a wide variety of 701 applications, there are many cases in which it is desirable for 702 generation of the private key to be distributed. 704 Feldman's Verifiable Secret Sharing (VSS) Scheme provides a mechanism 705 that allows the participants in a distributed generation scheme to 706 determine that their share has been correctly formed by means of a 707 commitment. 709 To generate a commitment the dealer generates the polynomial _f_(_x_) 710 as before and in addition selects a generator _g_ 712 [TBS] 714 4.4. Distributed Key Generation 716 [TBS] 718 5. Application to Elliptic Curves 720 For elliptic curve cryptosystems, the operators [x] and [.] are point 721 addition. 723 Implementing a robust Key Co-Generation for the Elliptic Curve 724 Cryptography schemes described in [RFC7748] and [RFC8032] requires 725 some additional considerations to be addressed. 727 * The secret scalar used in the EdDSA algorithm is calculated from 728 the private key using a digest function. It is therefore 729 necessary to specify the Key Co-Generation mechanism by reference 730 to operations on the secret scalar values rather than operations 731 on the private keys. 733 * The Montgomery Ladder traditionally used to perform X25519 and 734 X448 point multiplication does not require implementation of a 735 function to add two arbitrary points. While the steps required to 736 create such a function are fully constrained by [RFC7748], the 737 means of performing point addition is not. 739 5.1. Implementation for Ed25519 and Ed448 741 [RFC8032] provides all the cryptographic operations required to 742 perform threshold operations and corresponding public keys. 744 The secret scalars used in [RFC8032] private key operations are 745 derived from a private key value using a cryptographic digest 746 function. This encoding allows the inputs to a private key 747 combination to be described but not the output. Contrawise, the 748 encoding allows the inputs to a private key splitting operation to be 749 described but not the output 751 It is therefore necessary to provide an alternative representation 752 for the Ed25519 and Ed448 private keys. Moreover, the signature 753 algorithm requires both a secret scalar and a prefix value as inputs. 755 Since threshold signatures are out of scope for this document and 756 [RFC8032] does not specify a key agreement mechanism, it suffices to 757 specify the data formats required to encode private key values 758 generated by means of threshold key generation. 760 5.1.1. Ed25519 762 Let the inputs to the threshold key generation scheme be a set of 32 763 byte private key values _P_(1), P2 ... Pn. For each private key 764 value i in turn:_ 766 0. Hash the 32-byte private key using SHA-512, storing the digest in 767 a 64-octet large buffer, denoted_h_(i)_. Let n_(i) be the first 768 32 octets of h_(i) and m_(i) be the remaining 32 octets of h_(i). 770 1. Prune n_(i): The lowest three bits of the first octet are 771 cleared, the highest bit of the last octet is cleared, and the 772 second highest bit of the last octet is set. 774 2. Interpret the buffer as the little-endian integer, forming a 775 secret scalar s_(i). 777 The private key values are calculated as follows: 779 The aggregate secret scalar value _s_(a) = s1 + s2 + ... sn mod L, 780 where L is the order of the curve._ 782 The aggregate prefix value is calculated by either 784 * Some function TBS on the values m_(1), m_(2), ... m_(n), or 786 * Taking the SHA256 digest of s_(a). 788 The second approach is the simplest and the most robust. It does 789 however mean that the prefix is a function of the secret scalar 790 rather than both being functions of the same seed. 792 5.1.2. Ed448 794 Let the inputs to the threshold key generation scheme be a set of 57 795 byte private key values _P_(1), P2 ... Pn. For each private key 796 value i in turn:_ 798 0. Hash the 57-byte private key using SHAKE256(x, 114), storing the 799 digest in a 114-octet large buffer, denoted_h_(i)_. Let n_(i) be 800 the first 57 octets of h_(i) and m_(i) be the remaining 57 octets 801 of h_(i). 803 1. Prune n_(i): The two least significant bits of the first octet 804 are cleared, all eight bits the last octet are cleared, and the 805 highest bit of the second to last octet is set. 807 2. Interpret the buffer as the little-endian integer, forming a 808 secret scalar s_(i). 810 The private key values are calculated as follows: 812 The aggregate secret scalar value _s_(a) = s1 + s2 + ... sn mod L, 813 where L is the order of the curve._ 815 The aggregate prefix value is calculated by either 817 * Some function TBS on the values m_(1), m_(2), ... m_(n), or 819 * Taking the SHAKE256(x, 57) digest of s_(a). 821 The second approach is the simplest and the most robust. It does 822 however mean that the prefix is a function of the secret scalar 823 rather than both being functions of the same seed. 825 5.2. Implementation for X25519 and X448 827 [RFC7748] defines all the cryptographic operations required to 828 perform threshold key generation and threshold decryption but does 829 not describe how to implement them. 831 The Montgomery curve described in [RFC7748] allows for efficient 832 scalar multiplication using arithmetic operations on a single 833 coordinate. Point addition requires both coordinate values. It is 834 thus necessary to provide an extended representation for point 835 encoding and provide an algorithm for recovering both coordinates 836 from a scalar multiplication operation and an algorithm for point 837 addition. 839 The notation of [RFC7748] is followed using {u, v} to represent the 840 coordinates on the Montgomery curve and {x, y} for coordinates on the 841 corresponding Edwards curve. 843 5.2.1. Point Encoding 845 The relationship between the u and v coordinates is specified by the 846 Montgomery Curve formula itself: 848 _v^(2)_ = _u^(3) + Au2 + u_ 849 An algorithm for extracting a square root of a number in a finite 850 field is specified in . [RFC8032] 852 Since _v^(2)_ has a positive (_v_) and a negative solution (_-v_), it 853 follows that _v^(2)_ mod p will have the solutions _v_, _p-v_. 854 Furthermore, since _p_ is odd, if _v_ is odd, _p-v_ must be even and 855 vice versa. It is thus sufficient to record whether _v_ is odd or 856 even to enable recovery of the _v_ coordinate from _u_. 858 5.2.2. X25519 Point Encoding 860 The extended point encoding allowing the v coordinate to be recovered 861 is as given in [draft-ietf-lwig-curve-representations] 863 A curve point (u, v), with coordinates in the range 0 = u,v p, is 864 coded as follows. First, encode the u-coordinate as a little-endian 865 string of 57 octets. The final octet is always zero. To form the 866 encoding of the point, copy the least significant bit of the 867 v-coordinate to the most significant bit of the final octet. 869 5.2.3. X448 Point Encoding 871 The extended point encoding allowing the v coordinate to be recovered 872 is as given in [draft-ietf-lwig-curve-representations] 874 A curve point (u, v), with coordinates in the range 0 = u,v p, is 875 coded as follows. First, encode the u-coordinate as a little-endian 876 string of 57 octets. The final octet is always zero. To form the 877 encoding of the point, copy the least significant bit of the 878 v-coordinate to the most significant bit of the final octet. 880 5.2.4. Point Addition 882 The point addition formula for the Montgomery curve is defined as 883 follows: 885 Let P_(1) = {u_(1), v_(1)}, P_(2) = {u_(2), v_(2)}, P_(3) = {u_(3), 886 v_(3)} = P_(1) + P_(2) 888 By definition: 890 u_(3) = B(v_(2) - v_(1))^(2) / (u_(2) - u_(1))^(2) - A - u_(1) - 891 u_(2) 893 = B((u_(2)v_(1) - u_(1)v_(2))^(2) ) / u_(1)u_(2) (u_(2) - 894 u_(1))^(2) 896 v_(3) = ((2u_(1) + u_(2) + A)(v_(2) - v_(1)) / (u_(2) - u_(1))) - B 897 (v_(2) - v_(1))^(3) / (u_(2) -u_(1))^(3) - v_(1) 899 For curves X25519 and X448, B = 1 and so: 901 u_(3) = ((v_(2) - v_(1)).(u_(2) - u_(1))^(-1))^(2) - A - u_(1) - 902 u_(2) 904 v_(3) = ((2u_(1) + u_(2) + A)(v_(2) - v_(1)).(u_(2) - u_(1))^(-1)) - 905 ((v_(2) - v_(1)).(u_(2) -u_(1))^(-1))^(3) - v_(1) 907 This may be implemented using the following code: 909 B = v2 - v1 910 C = u2 - u1 911 CINV = C^(p - 2) 912 D = B * CINV 913 DD = D * D 914 DDD = DD * D 916 u3 = DD - A - u1 - u2 917 v3 = ((u1 + u1 + u2 + A) * B * CINV) - DDD - v1 919 Performing point addition thus requires that we have sufficient 920 knowledge of the values v_(1), v_(2). At minimum whether one is odd 921 and the other even or if both are the same. 923 5.2.5. Montgomery Ladder with Coordinate Recovery 925 As originally described, the Montgomery Ladder only provides the u 926 coordinate as output. L?pez and Dahab [Lopez99] provided a formula 927 for recovery of the v coordinate of the result for curves over binary 928 fields. This result was then extended by Okeya and Sakurai [Okeya01] 929 to prime field Montgomery curves such as X25519 and X448. The 930 realization of this result described by Costello and Smith 931 [Costello17] is applied here. 933 The scalar multiplication function specified in [RFC7748] takes as 934 input the scalar value k and the coordinate u_(1) of the point P_(1) 935 = {u_(1), v_(1)} to be multiplied. The return value in this case is 936 u_(2) where P_(2) = {u_(2), v_(2)} = k.P_(1). 938 To recover the coordinate v_(2) we require the values x_2, z_2, x_3, 939 z_3 calculated in the penultimate step: 941 x_1 = u 942 x_2 = 1 943 z_2 = 0 944 x_3 = u 945 z_3 = 1 946 swap = 0 948 For t = bits-1 down to 0: 949 k_t = (k >> t) & 1 950 swap ^= k_t 951 // Conditional swap as specified in RFC 7748 952 (x_2, x_3) = cswap(swap, x_2, x_3) 953 (z_2, z_3) = cswap(swap, z_2, z_3) 954 swap = k_t 956 A = x_2 + z_2 957 AA = A^2 958 B = x_2 - z_2 959 BB = B^2 960 E = AA - BB 961 C = x_3 + z_3 962 D = x_3 - z_3 963 DA = D * A 964 CB = C * B 965 x_3 = (DA + CB)^2 966 z_3 = x_1 * (DA - CB)^2 967 x_2 = AA * BB 968 z_2 = E * (AA + a24 * E) 970 (x_2, x_3) = cswap(swap, x_2, x_3) 971 (z_2, z_3) = cswap(swap, z_2, z_3) 972 Return x_2, z_2, x_3, z_3 974 The values x_2, z_2 give the projective form of the u coordinate of 975 the point P_(2) = {u_(2), v_(2)} = k.P_(1) and the values x_3, z_3 976 give the projective form of the u coordinate of the point P_(3) = 977 {u_(3), v_(3)} = (k+1).P_(1) = P_(1) + k.P_(1) = P_(1) + P_(2). 979 Given the coordinates {u_(1), v_(1)} of the point P1 and the u 980 coordinates of the points P_(2), P_(1) + P_(2), the coordinate v_(2) 981 MAY be recovered by trial and error as follows: 983 v_test = SQRT (u3 + Au2 + u) 984 u_test = ADD_X (u, v, u_2, v_test) 985 if (u_test == u_3) 986 return u_test 987 else 988 return u_test +p 990 Alternatively, the following MAY be used to recover {u_(2), v_(2)} 991 without the need to extract the square root and using a single 992 modular exponentiation operation to convert from the projective 993 coordinates used in the calculation. As with the Montgomery ladder 994 algorithm above, the expression has been modified to be consistent 995 with the approach used in [RFC7748] but any correct formula may be 996 used. 998 x_p = u 999 y_p = v 1001 B = x_p * z_2 //v1 1002 C = x_2 + B //v2 1003 D = X_2 - B //v3 1004 DD = D^2 //v3 1005 E = DD. X_3 //v3 1006 F = 2 * A * z_2 //v1 1008 G = C + F //v2 1009 H = x_p * x_2 //v4 1010 I = H + z_2 //v4 1011 J = G * I //v2 1012 K = F * z_2 //v1 1013 L = J - K //v2 1014 M = L * z_3 //v2 1016 yy_2 = M - E //Y' 1017 N = 2 * y_p //v1 1018 O = N * z_2 //v1 1019 P = O * z_3 //v1 1020 xx_2 = P * x_q //X' 1021 zz_2 = P * z_ q //Z' 1023 ZINV = (zz_2^(p - 2)) 1024 u2 = xx_2 * ZINV 1025 v2 = yy_2 * ZINV 1027 return u2, v2 1029 6. Test Vectors 1031 6.1. Threshold Key Generation 1033 6.1.1. X25519 1035 The key parameters of the first key contribution are: 1037 X25519Key1 (X25519) 1038 UDF: ZAAA-CTKG-X255-XXKE-YX 1039 Scalar: 324858804843944019775357777134446830499336694251 1040 10150162410603197194664525072 1041 Encoded Private 1042 10 BD E5 52 D6 AF 62 BE E4 5B F3 30 B8 FC 1C 51 1043 B3 1B 10 9D 1E E9 D7 8D 04 23 39 08 55 5B D2 47 1044 U: 394710109806205653786046834135930103397328759791 1045 49327589691528787260753559967 1046 V: 356194396126197144337653540363972416928636805167 1047 03007342935403505222303874766 1048 Encoded Public 1049 9F C1 03 BF A0 E6 6F C7 F1 98 4F 11 99 6E 35 E8 1050 E0 12 0A 0A D0 0D 79 97 4E 8A 1C 08 EF CC 43 57 1051 00 1053 The key parameters of the second key contribution are: 1055 X25519Key2 (X25519) 1056 UDF: ZAAA-CTKG-X255-XXKE-Y2 1057 Scalar: 411580799970764177643732652839689210097433579803 1058 82961631181135147895746569008 1059 Encoded Private 1060 30 A3 31 35 93 F6 AD C9 AC 13 1C 27 15 83 C8 1B 1061 00 EF 48 B9 52 14 8D 4D 3C F0 A3 C1 D2 A5 FE 5A 1062 U: 459625327459773177107083316486045330014029630693 1063 84886488666639114650950362503 1064 V: 257984254735960195350757294576288849253536777584 1065 92280923754924184339462178503 1066 Encoded Public 1067 87 E5 CC DD 1D AA 42 EA 6F E8 6F 70 71 EE CF 86 1068 45 52 48 50 9D B2 6A 76 3B 7A 21 A0 23 DF 9D 65 1069 80 1071 The composite private key is: 1073 Scalar_A = (Scalar_1 + Scalar_2) mod L 1074 =127390470814819760217717736698366165110586381169403573357222896 1075 2235868584190 1077 Encoded Composite Private Key: 1079 FE 18 7D E6 61 C7 58 17 32 4F 63 FA 1A BD 2F 9C 1080 B2 0A 59 56 71 FD 64 DB 40 13 DD C9 27 01 D1 02 1082 The composite public key is: 1084 Point_A = Point_1 + Point_2 1086 U: 150135516006055775898023592854502286813423441552 1087 78788763949643404481150980325 1088 V: 415138854802975146804397164494309448482487190852 1089 96478905918078322266869330796 1091 Encoded Public 1092 E5 10 7A CA 6D 63 5F 0B 96 8D C1 FF 03 88 6A 9F 1093 5E 39 FB C7 7D 4E 0C 8F B9 BE 02 68 7B 5E 31 21 1095 Note that in this case, the unsigned representation of the key is 1096 used as the composite key is intended for unsigned CurveX key 1097 agreement. If the result is intended for use as a key contribution, 1098 the signed representation is required. 1100 6.1.2. X448 1102 The key parameters of the first key contribution are: 1104 X448Key1 (X448) 1105 UDF: ZAAA-ETKG-X44X-KEYX 1106 Scalar: 481994585826426647968618231378947367458943870175 1107 360121942970840151506728554061197387112897908361553737348667 1108 886278259299907241847731316 1109 Encoded Private 1110 74 B4 D2 F1 12 CC E7 DD F8 1A 30 80 1F 2C 19 EA 1111 EF E2 B3 8A 84 AF 60 11 0C 12 ED C3 B7 59 AE CC 1112 C9 B4 E4 9D 39 26 7C 61 5F 18 F1 24 FE 63 D6 4B 1113 BB 90 58 16 43 6E C3 A9 1114 U: 394700438080601820949554957897111201031639217153 1115 649316073420498416350673492846326387358441405527682364389676 1116 084099279128049619119543974 1117 V: 444540392869323915210590844990511294596507999517 1118 821659576820658489772434608466545900017841967298236181114781 1119 72629203404123869477697007 1120 Encoded Public 1121 A6 96 1A 77 DC 39 41 5F D7 DA A5 07 45 AC 8E A4 1122 3E AE 8C 77 BD 50 4A B0 24 64 CD EA 58 0A A3 C7 1123 A7 80 BA A6 10 BD 57 9A FA 0C E3 EB 2F C8 BB 52 1124 36 42 B2 58 C3 7B 04 8B 80 1126 The key parameters of the second key contribution are: 1128 X448Key2 (X448) 1129 UDF: ZAAA-ETKG-X44X-KEY2 1130 Scalar: 511754555230466033071173155845990436633003100190 1131 696628114856620555834938157360893794661792647517417178355617 1132 271188892590944570884738624 1133 Encoded Private 1134 40 CE 77 E2 F2 EC 9B 7D 3E F4 62 C6 F9 99 81 B4 1135 19 E5 4B 18 48 54 13 C9 79 D4 FF 3C ED 3B 9C A1 1136 FE 10 7E DC 1F 56 BD 4D 27 7F 9C 70 4B 30 BE 0A 1137 86 2A 01 3D 2A C3 3E B4 1138 U: 150272226357947871808446816866811163361018047865 1139 977226556625643162666620657310046951510401422900774703631401 1140 927908349274354369426223715 1141 V: 366137359317179726859107301681665650104046728426 1142 432019544955478508004916807825041417161908471339553361130707 1143 683387754680120674193097983 1144 Encoded Public 1145 63 F2 0D 66 B0 F9 43 1C 58 AD 56 2B C7 9A D5 83 1146 B0 B5 B1 73 9A BE B9 1E 72 5D 4A F7 8D 45 00 A6 1147 B3 7F AA 27 BE B4 72 44 EE D6 AA 24 5B BE B9 92 1148 F8 8D 63 CC A1 6A ED 34 80 1150 The composite private key is: 1152 Scalar_A = (Scalar_1 + Scalar_2) mod L 1153 =852007356873840678531366273649321361498952695069091747059647117 1154 316116469037241626007959140974170910991528166120088403669830 1155 33434221045 1157 Encoded Composite Private Key: 1159 F5 29 91 7B 28 EC 27 AA 8D 42 B7 81 DC F9 7A F7 1160 38 B7 D0 38 5C BB E9 04 F5 32 FA 90 A7 95 4A 6E 1161 C8 C5 62 7A 59 7C 39 AF 86 97 8D 95 49 94 94 56 1162 41 BB 59 53 6D 31 02 1E 1164 The composite public key is: 1166 Point_A = Point_1 + Point_2 1168 U: 992302561314692402358105531637482692313485564268 1169 012269312838533303200135230457785976232221579845336021490878 1170 11249911833804897105796187 1171 V: 456075089062293144799088747749397731190530292504 1172 203343525695648243447672023318462080397566120195617049762303 1173 280841894269351301464260878 1175 Encoded Public 1176 5B DC 74 39 94 08 79 2C D5 F0 F1 E0 5F 7F 87 4D 1177 4D 3B 92 96 AB 62 FF EC CB 3C 74 42 48 D2 D0 30 1178 95 45 37 89 5E 53 5D 47 72 DD D8 1A 24 2C 65 76 1179 1F 7A FB 2E 15 2D F3 22 1181 Note that in this case, the unsigned representation of the key is 1182 used as the composite key is intended for unsigned CurveX key 1183 agreement. If the result is intended for use as a key contribution, 1184 the signed representation is required. 1186 6.1.3. Ed25519 1188 The key parameters of the first key contribution are: 1190 ED25519Key1 (ED25519) 1191 UDF: ZAAA-GTKG-ED25-5XXK-EYX 1192 Scalar: 566707288876750955042011684517553468890396806254 1193 32020135051411766560411209648 1194 Encoded Private 1195 1D 04 C0 18 98 F0 31 CA 3B A1 F0 C3 AD 2B FC 3B 1196 CF F1 DC DC 07 FC 61 5F B1 63 75 35 CE C4 EA B4 1197 X: 102242812372232316143929541945425934190366349837 1198 479493246432658075153118475011602747352787206173426322413798 1199 12049009970952489882776094157952001361119144 1200 Y: 789031640540855004178762236065881312872127689877 1201 983340977132004355159711145586361923666616187290905159854593 1202 272855769333002825303166428484255810207910288 1203 Encoded Public 1204 D8 4E 98 3E F7 21 87 CC C6 47 CB 6E 5A 57 1F 79 1205 F5 B9 22 D9 A8 00 D3 69 91 E1 B6 E6 10 FF 59 08 1207 The key parameters of the second key contribution are: 1209 ED25519Key2 (ED25519) 1210 UDF: ZAAA-GTKG-ED25-5XXK-EY2 1211 Scalar: 566707288876750955042011684517553468890396806254 1212 32020135051411766560411209648 1213 Encoded Private 1214 1D 04 C0 18 98 F0 31 CA 3B A1 F0 C3 AD 2B FC 3B 1215 CF F1 DC DC 07 FC 61 5F B1 63 75 35 CE C4 EA B4 1216 X: 102242812372232316143929541945425934190366349837 1217 479493246432658075153118475011602747352787206173426322413798 1218 12049009970952489882776094157952001361119144 1219 Y: 789031640540855004178762236065881312872127689877 1220 983340977132004355159711145586361923666616187290905159854593 1221 272855769333002825303166428484255810207910288 1222 Encoded Public 1223 D8 4E 98 3E F7 21 87 CC C6 47 CB 6E 5A 57 1F 79 1224 F5 B9 22 D9 A8 00 D3 69 91 E1 B6 E6 10 FF 59 08 1226 The composite private key is: 1228 Scalar_A = (Scalar_1 + Scalar_2) mod L 1229 =478637411536625779880453845786578016522261586016542618007355945 1230 8839008654461 1232 Encoded Composite Private Key: 1234 7D 34 94 4B 39 80 D9 34 DB EB E1 7C 6C 7E BB FA 1235 77 03 B0 DC 59 BD DB 30 E9 EC 02 15 E3 FD 94 0A 1237 The composite public key is: 1239 Point_A = Point_1 + Point_2 1241 X: 156803891315589086286215914260988096641777056734 1242 949191292807298262090581551508321205906817723758419038014448 1243 221785557483058278412455441230622087321788265 1244 Y: 797171707400790781155409731019930644260359827339 1245 627382830182820599849038258772654275070450097319504001761725 1246 123426865448110684459259776487353068850001481 1248 Encoded Public 1249 7B 1C 48 02 66 17 79 32 B3 02 7B 21 8E D8 FD 6C 1250 A1 D5 EC 8E 28 5D E8 D3 E2 08 1A F9 EB FA AC 32 1252 6.1.4. Ed448 1254 The key parameters of the first key contribution are: 1256 ED448Key1 (ED448) 1257 UDF: ZAAA-ITKG-ED44-XKEY-X 1258 Scalar: 627183439506120484725959826569914487299049496696 1259 595523009635802846606657882532934711603764178690431435900965 1260 134411043888412886366713268 1261 Encoded Private 1262 03 81 D6 5A 17 53 20 CB F4 02 40 66 C8 28 A5 E7 1263 85 C6 87 7D 41 3A 33 CD 5B 09 9F E5 DF 1A 80 4D 1264 4F 6E B1 35 F7 46 8B 1C 46 99 6E 6D A4 B5 23 EC 1265 FD 9C DF A4 9A E5 17 C6 1266 X: 583262368398068306064924227289526726945089383036 1267 870654148794281596473976374037255611400384372179423639836667 1268 405050261630569976923704901 1269 Y: 394808842674474575092248856523729981587605779158 1270 130628847253048358283876706462306075444313878262092034880682 1271 915931230840640589150609812 1272 Encoded Public 1273 BB 4B F3 61 B5 1F 95 1E 88 04 A8 5E 48 77 4C A5 1274 25 F0 D6 49 41 07 12 C1 15 05 25 78 60 FC D9 A8 1275 CC DB F9 6D 63 6B C3 F7 63 F2 BB 00 A0 7C 13 E1 1276 C6 4B 72 08 EA C8 87 11 00 1278 The key parameters of the second key contribution are: 1280 ED448Key2 (ED448) 1281 UDF: ZAAA-ITKG-ED44-XKEY-2 1282 Scalar: 627183439506120484725959826569914487299049496696 1283 595523009635802846606657882532934711603764178690431435900965 1284 134411043888412886366713268 1285 Encoded Private 1286 03 81 D6 5A 17 53 20 CB F4 02 40 66 C8 28 A5 E7 1287 85 C6 87 7D 41 3A 33 CD 5B 09 9F E5 DF 1A 80 4D 1288 4F 6E B1 35 F7 46 8B 1C 46 99 6E 6D A4 B5 23 EC 1289 FD 9C DF A4 9A E5 17 C6 1290 X: 583262368398068306064924227289526726945089383036 1291 870654148794281596473976374037255611400384372179423639836667 1292 405050261630569976923704901 1293 Y: 394808842674474575092248856523729981587605779158 1294 130628847253048358283876706462306075444313878262092034880682 1295 915931230840640589150609812 1296 Encoded Public 1297 BB 4B F3 61 B5 1F 95 1E 88 04 A8 5E 48 77 4C A5 1298 25 F0 D6 49 41 07 12 C1 15 05 25 78 60 FC D9 A8 1299 CC DB F9 6D 63 6B C3 F7 63 F2 BB 00 A0 7C 13 E1 1300 C6 4B 72 08 EA C8 87 11 00 1302 The composite private key is: 1304 Scalar_A = (Scalar_1 + Scalar_2) mod L 1305 =164108792568830633627933941307822173067636952362213955597036306 1306 922337291995828355126032996607226607091940168014272113948183 1307 237575527862 1309 Encoded Composite Private Key: 1311 B6 4D CF FC C2 D8 08 4F 08 3C 03 5E C5 68 95 D2 1312 65 F8 1D F2 C6 DC 4D 2E 23 B5 D5 02 AC 7A C5 A8 1313 77 E9 D0 6E A2 1D 3D 11 91 49 AC 00 BF 0A 5B 95 1314 59 BD 0D 94 6E 00 CD 39 1316 The composite public key is: 1318 Point_A = Point_1 + Point_2 1320 X: 397684546797270425386442556916724605113037846866 1321 341266059847555740358632067326446186925590144430667066483990 1322 646036946928867316187394724 1323 Y: 408779958726533701154676738846429933260841277918 1324 126357328937237395286337382114316760480663335443832148985549 1325 99820255282659972439867001 1327 Encoded Public 1328 39 DE 52 BB 22 79 72 DD 40 82 BB 45 7B FA 61 AD 1329 D0 BA 02 FF 8A FB 62 62 39 C6 C0 46 6B 35 93 E4 1330 CD 1B 5F 79 FB D7 68 87 4C E7 D8 09 B1 3C ED 5A 1331 DE 61 5A D2 DC 19 C6 D3 00 1333 6.2. Threshold Decryption 1335 6.2.1. Direct Key Splitting X25519 1337 The encryption key pair is 1338 X25519KeyA (X25519) 1339 UDF: ZAAA-CTHD-X255-XXKE-YA 1340 Scalar: 326889380688366386055157824948497405399138729191 1341 89762489343300449845480879296 1342 Encoded Private 1343 C0 74 51 B1 0A 11 F3 AA E9 E8 5C 99 A2 29 2F 78 1344 88 A8 FC 3D 09 69 06 60 C2 B4 95 71 85 48 45 48 1345 U: 298393977624490693814310584567182927861271505374 1346 9632477801696949179285366587 1347 V: 469514996865823666093464626932614325688577702009 1348 92824380735949162568370305003 1349 Encoded Public 1350 3B E7 D1 11 EA 09 02 81 C7 88 E9 59 7A 44 D1 D5 1351 34 AE 12 E2 3C 59 32 99 41 D1 99 B6 9D D9 98 06 1353 To create n key shares we first create n-1 key pairs in the normal 1354 fashion. Since these key pairs are only used for decryption 1355 operations, it is not necessary to calculate the public components: 1357 X25519Key1 (X25519) 1358 UDF: ZAAA-CTHD-X255-XXKE-YX 1359 Scalar: 312348810422743662022326371802074910867528782383 1360 29365764492453739245942799272 1361 Encoded Private 1362 A8 FB C2 FD 62 20 CA 30 DA 44 87 38 BA 30 BE 5E 1363 FD 71 8F 48 33 E2 D2 9E 3F 28 AA C7 F0 50 0E 45 1365 The secret scalar of the final key share is the secret scalar of the 1366 base key minus the sum of the secret scalars of the other shares 1367 modulo the group order: 1369 Scalar_2 = (Scalar_A - Scalar_1) mod L 1370 =602777449245290709596292717071327769980982028247986740582014668 1371 2807789670656 1373 This is encoded as a binary integer in little endian format: 1375 00 D1 65 C7 9A 18 2A 1B 11 47 27 BA 67 8B F5 2F 1376 85 1A 8C 86 3C 4B D9 FE 01 DD 3F 39 76 99 53 0D 1378 6.2.2. Direct Decryption X25519 1380 The means of encryption is unchanged. We begin by generating an 1381 ephemeral key pair: 1383 X25519KeyE (X25519) 1384 UDF: ZAAA-CTHD-X255-XXKE-YE 1385 Scalar: 493149316568141341116267515722816577238360781396 1386 63006284230452497981236822048 1387 Encoded Private 1388 20 C0 8B F4 BA DB D2 9A 69 47 45 73 4F 34 8E 35 1389 B5 78 24 AB F6 85 29 51 37 0A CB 38 1E 43 07 6D 1390 U: 262957444446660172926134873812719769018477396438 1391 13954077731613449391499377029 1392 V: 275785345363973047453636076008194379259667671218 1393 204709190728344437212344040 1394 Encoded Public 1395 85 F9 AB 1E 1F 07 0F F9 9A 61 9F 3A C8 34 C5 A2 1396 44 20 2A 92 7C 06 D8 54 E7 56 83 4F 2A DD 22 3A 1398 The key agreement result is given by multiplying the public key of 1399 the encryption pair by the secret scalar of the ephemeral key to 1400 obtain the u-coordinate of the result. 1402 U: 288787781548525369610061893837025332891029237654 1403 14471063569609087123262768472 1405 The u-coordinate is encoded in the usual fashion (i.e. without 1406 specifying the sign of v). 1408 58 85 FB 70 25 DB ED FB F4 3F C2 11 65 A7 B6 FA 1409 1B 2F 02 B7 36 34 A3 7B F3 A0 2B 90 27 CF D8 3F 1411 The first decryption contribution is generated from the secret scalar 1412 of the first key share and the public key of the ephemeral. 1414 The outputs from the Montgomery Ladder are: 1416 x_2: 492098238905847779621612291688488017809049229602 1417 94749204467459229896958710447 1418 z_2: 429527757883227955375237456769123024739869368263 1419 91347354499451449213467668091 1420 x_3: 116605272267998449524192895707557114882629363798 1421 86482562941790223923418840285 1422 z_3: 195732355890349962819915384747512066302779899283 1423 35607999800289560050872569334 1425 The coordinates of the corresponding point are: 1427 u: 536730894304808282930528988436660517867298128709 1428 04753433533361766729625453382 1429 v: 421632078600697821949748757382882309748636068616 1430 05021486709890742236074210497 1432 The encoding of this point specifies the u coordinate and the sign 1433 (oddness) of the v coordinate: 1435 85 F9 AB 1E 1F 07 0F F9 9A 61 9F 3A C8 34 C5 A2 1436 44 20 2A 92 7C 06 D8 54 E7 56 83 4F 2A DD 22 3A 1438 The second decryption contribution is generated from the secret 1439 scalar of the second key share and the public key of the ephemeral in 1440 the same way: 1442 u: 315780533103181510115520285714808517940341134033 1443 73677773373235419322267220550 1444 v: 182446295500312360012159151093139263903764865208 1445 52094490828880182704089261185 1447 85 F9 AB 1E 1F 07 0F F9 9A 61 9F 3A C8 34 C5 A2 1448 44 20 2A 92 7C 06 D8 54 E7 56 83 4F 2A DD 22 3A 1450 To obtain the key agreement value, we add the two decryption 1451 contributions: 1453 u: 400218389629441160369977262251603578789352483113 1454 44007312711045713754930418024 1455 v: 365543819982499491694061844647668737870082451479 1456 1236363503671566229693675370 1458 This returns the same u coordinate value as before, allowing us to 1459 obtain the encoding of the key agreement value and decrypt the 1460 message. 1462 6.2.3. Direct Key Splitting X448 1464 The encryption key pair is 1465 X448KeyA (X448) 1466 UDF: ZAAA-ETHD-X44X-KEYA 1467 Scalar: 513061070451628243040038974375191143450906600896 1468 180328078543208371170428980692680538107843349213517810077524 1469 748539797940481719097207576 1470 Encoded Private 1471 18 AB BD 69 F6 B7 16 23 72 4E B5 28 7E F8 F1 4E 1472 DB B5 6C EF 00 CD 51 4A AD F6 24 AF 73 0B CC 37 1473 E4 66 01 C0 B4 35 18 99 CA 31 D0 7E 5D C6 86 9F 1474 4F 33 33 95 BB 90 B4 B4 1475 U: 193313388884413202154350037477490868937254022660 1476 936368668113777978992235566230625856064905970782804480638718 1477 961661755983597338734305565 1478 V: 632512063264494610095455928921278058920338770152 1479 331221019494393225431601640040112765612198296012844171344559 1480 006776860014410518640582570 1481 Encoded Public 1482 1D 21 53 89 F7 D8 78 AD F5 4F 66 AE F6 E4 35 57 1483 A4 2D 0F 29 D7 ED 64 13 5A 15 5D 0C 5A 9D 78 8E 1484 30 AA D7 ED 94 D3 0A FD 5F C9 EB C4 6E 78 CB EC 1485 67 10 DE 1A F7 41 16 44 1487 To create n key shares we first create n-1 key pairs in the normal 1488 fashion. Since these key pairs are only used for decryption 1489 operations, it is not necessary to calculate the public components: 1491 X448Key1 (X448) 1492 UDF: ZAAA-ETHD-X44X-KEYX 1493 Scalar: 584733191291060171614515657474831905352900996815 1494 538008733617256668598608739673264046230908386003505289747870 1495 068686374821834248930905564 1496 Encoded Private 1497 DC CD 9E 38 94 A1 EA CA 7D 41 FA B5 FB D3 01 43 1498 4A FB F9 1D AE 73 82 3B 4C 11 A8 F2 2A 36 87 AB 1499 3F EB EE E8 DC AB A7 30 5E 26 9C BC 4C FC D0 C8 1500 48 F1 D3 78 A1 F0 F2 CD 1502 The secret scalar of the final key share is the secret scalar of the 1503 base key minus the sum of the secret scalars of the other shares 1504 modulo the group order: 1506 Scalar_2 = (Scalar_A - Scalar_1) mod L 1507 =753617529927807883056892001801624727334555668074124638992516626 1508 889301395112843028716421998506276731996363256267619893367343 1509 2870214466 1511 This is encoded as a binary integer in little endian format: 1513 42 DB 4A 9E 1A CA 2C 19 F1 33 0E 8C CA 3D 67 C9 1514 C4 69 61 F4 F4 1C FB EB 7E 30 10 B5 A1 41 53 E3 1515 23 52 F0 A8 91 E1 BF C9 28 58 6C 3B AA C2 57 68 1516 98 24 07 0E 5D 81 A7 02 1518 6.2.4. Direct Decryption X448 1520 The means of encryption is unchanged. We begin by generating an 1521 ephemeral key pair: 1523 X448KeyE (X448) 1524 UDF: ZAAA-ETHD-X44X-KEYE 1525 Scalar: 375092101281685084138772040470324089521485504818 1526 151786170217259465369930000693812877111168523934570244151290 1527 043203531788355356164832452 1528 Encoded Private 1529 C4 3C 47 59 CD E7 17 95 B4 7B 93 AA 69 B8 B6 B7 1530 ED FE 18 D7 F4 7F 60 65 F1 89 C7 35 8D B5 43 37 1531 1B 7F 29 3E C2 DE EF 30 B6 C6 B5 53 17 C5 53 34 1532 E1 86 A9 88 60 7B 1C 84 1533 U: 563581233819606639218664767140161390782939076635 1534 909204332105344559772692562144684584035704830171693935746990 1535 510749935485351255733775569 1536 V: 361864251157310605646771236064439317468860292821 1537 265311098908535377847605233578670208219924720551821972711559 1538 36724947885353521079579125 1539 Encoded Public 1540 D1 2C A9 6B 5E 97 F8 F0 18 2A BF 33 E8 14 65 23 1541 A9 F1 06 9B D5 F0 DB 06 01 E5 1F 87 07 7D 69 63 1542 0A FD 05 FB 7A 65 4C D5 81 FC 63 11 5B D6 40 A1 1543 40 2F A5 FE B3 C1 7F C6 1545 The key agreement result is given by multiplying the public key of 1546 the encryption pair by the secret scalar of the ephemeral key to 1547 obtain the u-coordinate of the result. 1549 U: 467011616546325364170545331693527825162957894564 1550 752019329166269756954567903847269575078419988391203956276277 1551 502444715801151733990260662 1553 The u-coordinate is encoded in the usual fashion (i.e. without 1554 specifying the sign of v). 1556 B6 7F 79 43 2A 13 43 58 EB A5 F5 7E 0E 58 9B AA 1557 BB D7 B1 7E 07 3E 42 F1 ED F4 C0 09 0C 5C 4E 88 1558 C9 81 21 E5 31 53 40 2F DE 7B 91 FE E4 47 A2 A7 1559 9B F8 E8 B0 AC 7A 7C A4 00 1561 The first decryption contribution is generated from the secret scalar 1562 of the first key share and the public key of the ephemeral. 1564 The outputs from the Montgomery Ladder are: 1566 x_2: 506558348563097978312390313048113345168022212711 1567 849349435150224631183990403335052324912391443123499702764248 1568 849278356671151441957790278 1569 z_2: 213125180906412917064601709491242258781796680209 1570 496987386274744929820708257576147081840825053136082223498470 1571 326539519004870996749115274 1572 x_3: 203497752532008592529275846876889307392855130050 1573 266584525256476121907823114215626360048014875021016264668899 1574 873822741730779444877210235 1575 z_3: 571082612271586102575474047974979930626798015601 1576 680732025993048573542014881343408880669710315066232049715159 1577 504508304710290054762104158 1579 The coordinates of the corresponding point are: 1581 u: 612112921160648939091711280397522831608649375644 1582 855484627685573574796097573324948060246221854728690332168796 1583 528561330174015687677222868 1584 v: 201043408411452768324992701951900381185869686931 1585 750056109757993947816262634088142979592355613308839469219652 1586 899581533430916970635983432 1588 The encoding of this point specifies the u coordinate and the sign 1589 (oddness) of the v coordinate: 1591 D1 2C A9 6B 5E 97 F8 F0 18 2A BF 33 E8 14 65 23 1592 A9 F1 06 9B D5 F0 DB 06 01 E5 1F 87 07 7D 69 63 1593 0A FD 05 FB 7A 65 4C D5 81 FC 63 11 5B D6 40 A1 1594 40 2F A5 FE B3 C1 7F C6 1596 The second decryption contribution is generated from the secret 1597 scalar of the second key share and the public key of the ephemeral in 1598 the same way: 1600 u: 290543592387303668402000444540573819834556168336 1601 146133899156492196788195733788135568819938481333767701019721 1602 625502303783518942583538850 1603 v: 545084635544186338165791882421333945771369831404 1604 654834318355031722653832417877619017774120725462178582001609 1605 731098147709911715676858744 1607 D1 2C A9 6B 5E 97 F8 F0 18 2A BF 33 E8 14 65 23 1608 A9 F1 06 9B D5 F0 DB 06 01 E5 1F 87 07 7D 69 63 1609 0A FD 05 FB 7A 65 4C D5 81 FC 63 11 5B D6 40 A1 1610 40 2F A5 FE B3 C1 7F C6 1612 To obtain the key agreement value, we add the two decryption 1613 contributions: 1615 u: 654406645663157043297342343331709836245150043735 1616 702788665901049252553535973169012625989449576860527067131717 1617 971914114816832035824532119 1618 v: 104146947548847304025795777575846818531726293762 1619 244429364569547834686063656820529540685030846449787127578128 1620 365084621097748733067553687 1622 This returns the same u coordinate value as before, allowing us to 1623 obtain the encoding of the key agreement value and decrypt the 1624 message. 1626 6.2.5. Shamir Secret Sharing X448 1628 [TBS] 1630 6.2.6. Lagrange Decryption X448 1632 [TBS] 1634 7. Security Considerations 1636 All the security considerations of [RFC7748] and [RFC8032] apply and 1637 are hereby incorporated by reference. 1639 7.1. Complacency Risk 1641 Separation of duties can lead to a reduction in overall security 1642 through complacency and lack of oversight. 1644 Consider the case in which a role that was performed by A alone is 1645 split into two roles B and C. If B and C each do their job with the 1646 same diligence as A did alone, risk should be reduced but if B and C 1647 each decide they can be careless because security is the 1648 responsibility of the other, the risk of a breach may be 1649 substantially increased. 1651 It is therefore important that each of the participants in a 1652 threshold scheme perform their responsibilities with the same degree 1653 of diligence as if they were the sole control and for those 1654 responsible for oversight to treat single point failures that do not 1655 lead to an actual breach with the same degree of concern as if a 1656 breach had occurred. 1658 Use of threshold operation modes mitigates but does not eliminate 1659 security considerations relating to private key operations of the 1660 underlying algorithm. For example, use of threshold key generation 1661 to generate a composite keypair {b+c, B+C} from key contributions {b, 1662 B} and {c, C} produces a strong composite private key if either of 1663 the key contributions _a_, _b_ are strong. But the composite key 1664 will be weak if neither contribution is strong. 1666 7.2. Rogue Key Attack 1668 In general, threshold modes of operation provide a work factor that 1669 is at least as high as that of the work factor of the strongest 1670 private key share. The karmic tradeoff for this benefit is that the 1671 trustworthiness of a composite public key is that of the least 1672 trustworthy input. 1674 For example, consider the case in which a client with keypair {c, C} 1675 generates an ephemeral keypair {e, E} for use in an authentication 1676 algorithm. We might decide to create an 'efficient' proof of 1677 knowledge of c and e by using the composite public key A = C+E to 1678 test for knowledge of both at the same time. 1680 This approach fails because an attacker with knowledge of C can 1681 generate a keypair {a, A} and calculate the corresponding public key 1682 E = A-C. The attacker can then use the value a in the authentication 1683 protocol. 1685 8. IANA Considerations 1687 This document requires no IANA actions (yet). 1689 It will be necessary to define additional code points for the signed 1690 version of the X25519 and X448 public key and the threshold 1691 decryption final private keys. 1693 9. Acknowledgements 1695 Rene Struik, Tony Arcieri, Scott Fluhrer, Scott Fluhrer, Dan Brown, 1696 Mike Hamburg 1698 10. Appendix A: Calculating Lagrange coefficients 1700 The following C# code calculates the Lagrange coefficients used to 1701 recover the secret from a set of shares. 1703 [TBS] 1705 11. Normative References 1707 [draft-ietf-lwig-curve-representations] 1708 Struik, R., "Alternative Elliptic Curve Representations", 1709 Work in Progress, Internet-Draft, draft-ietf-lwig-curve- 1710 representations-12, 24 August 2020, 1711 . 1714 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1715 Requirement Levels", BCP 14, RFC 2119, 1716 DOI 10.17487/RFC2119, March 1997, 1717 . 1719 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1720 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1721 2016, . 1723 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1724 Signature Algorithm (EdDSA)", RFC 8032, 1725 DOI 10.17487/RFC8032, January 2017, 1726 . 1728 12. Informative References 1730 [Costello17] 1731 Costello, C. and B. Smith, "Montgomery curves and their 1732 arithmetic", 2017. 1734 [draft-hallambaker-mesh-architecture] 1735 Hallam-Baker, P., "Mathematical Mesh 3.0 Part I: 1736 Architecture Guide", Work in Progress, Internet-Draft, 1737 draft-hallambaker-mesh-architecture-14, 27 July 2020, 1738 . 1741 [draft-hallambaker-mesh-developer] 1742 Hallam-Baker, P., "Mathematical Mesh: Reference 1743 Implementation", Work in Progress, Internet-Draft, draft- 1744 hallambaker-mesh-developer-10, 27 July 2020, 1745 . 1748 [draft-hallambaker-threshold-sigs] 1749 Hallam-Baker, P., "Threshold Signatures in Elliptic 1750 Curves", Work in Progress, Internet-Draft, draft- 1751 hallambaker-threshold-sigs-04, 3 September 2020, 1752 . 1755 [Kocher96] Kocher, P. C., "Timing attacks on implementations of 1756 Diffie-Hellman, RSA, DSS, and other systems.", 1996. 1758 [Lopez99] L?opez, J. and R. Dahab, "Fast multiplication on elliptic 1759 curves over GF(2m) without precomputation.", 1999. 1761 [Okeya01] Okeya, K. and K. Sakurai, "Efficient elliptic curve 1762 cryptosystems from a scalar multiplication algorithm with 1763 recovery of the y-coordinate on a Montgomeryform elliptic 1764 curve.", 2001. 1766 [RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method", 1767 RFC 2631, DOI 10.17487/RFC2631, June 1999, 1768 . 1770 [Shamir79] Shamir, A., "How to share a secret.", 1979.