idnits 2.17.1 draft-hallambaker-threshold-03.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 (September 4, 2020) is 1328 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'TBS' is mentioned on line 1701, 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 September 4, 2020 5 Expires: March 8, 2021 7 Threshold Modes in Elliptic Curves 8 draft-hallambaker-threshold-03 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 March 8, 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: 56751742936444772792970879017152360515706108153669948 1040 486190735258502824077920 1041 Encoded Private 1042 60 2A E2 12 AC 8E C8 86 A1 79 51 7E 79 90 5E C2 1043 9B AD 10 01 B9 2D 51 33 65 DB F4 9E 23 59 78 7D 1044 U: 25222393324990721517739552691612440154338285166262054281502859 1045 684220669343438 1046 V: 15622452724514925334849257786951944861130311422605147559630230 1047 860481236780294 1048 Encoded Public 1049 CE 36 B9 F1 56 BD 92 5C F4 B6 F5 E1 E0 BA CA 6A 1050 9B 7C 37 7D F8 DC 39 CC 12 2E A6 8F 64 5E C3 37 1051 00 1053 The key parameters of the second key contribution are: 1055 X25519Key2 (X25519) 1056 UDF: ZAAA-CTKG-X255-XXKE-Y2 1057 Scalar: 30800688691513612134093999707357841640579640775881469 1058 593062950189697563564400 1059 Encoded Private 1060 70 19 5B 38 A4 46 21 79 31 AC 48 83 60 C9 BD F8 1061 E1 EE 04 53 67 F2 B5 D8 9E 42 53 66 6F 92 18 44 1062 U: 35108630063567318397224393939085269372284744000330218923799041 1063 589332061533992 1064 V: 13827314478911339710714490558315610168380330915483870499348836 1065 357802235649136 1066 Encoded Public 1067 28 37 F5 39 16 C6 10 C6 8A AC 75 E9 20 EF 67 6D 1068 C2 6C AF 2C E4 F6 4F C9 E9 30 6C BD C9 C7 9E 4D 1069 00 1071 The composite private key is: 1073 Scalar_A = (Scalar_1 + Scalar_2) mod L 1074 = 70836469997123835938663996799427126600035261699252680723027418877 1075 4936630452 1077 Encoded Composite Private Key: 1079 B4 54 B7 EF 13 30 0D DF C6 CB FE 5D 6A A3 A8 C0 1080 7C 9C 15 54 20 20 07 0C 04 1E 48 05 93 EB 90 01 1082 The composite public key is: 1084 Point_A = Point_1 + Point_2 1086 U: 416454936139914218771704724014904891682742086807613599097165979348 1087 46285027335 1088 V: 473400233126764321363639652645349333601103100790621508110841442520 1089 99552212729 1091 Encoded Public 1092 07 98 75 38 67 9C 66 21 A3 0A D1 06 CF F5 81 04 1093 94 C0 52 C9 9C FD AE 4E 13 3B 43 9D 9A 83 12 5C 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: 68165415229434843487640754974827937311214322558126978 1107 8055715553507401814865302008262214951100710804646043741434925 1108 630887320553400661768 1109 Encoded Private 1110 08 77 91 25 66 19 C6 1A 03 C7 60 9A 8C C8 10 9D 1111 DE F5 20 E1 A7 7F 3E 83 56 57 FE A6 C9 97 79 FB 1112 DC 85 55 6F CE 17 79 70 CA 3E B5 D1 6A B0 50 6A 1113 60 F6 BF 3A 88 E5 15 F0 1114 U: 60697849609835675975297341597995979787516605306209816088918249 1115 8293453953345846660594020472424536065173283947670623780408505 1116 23120715561 1117 V: 60813500494147049417364978264586877278456315581444885337361828 1118 5076034450004202627339591608123302429557097118744860203117206 1119 220854848663 1120 Encoded Public 1121 29 C7 E7 1A ED 85 B5 66 F4 CA 8F 4D 07 72 EC 4B 1122 15 42 FA 95 4D A3 25 F6 D2 BF C0 5E 11 C4 27 D3 1123 A1 43 D8 74 B6 4C C8 22 7D 64 56 58 A4 8C C6 5D 1124 DA F2 AA 75 DE DE 60 15 80 1126 The key parameters of the second key contribution are: 1128 X448Key2 (X448) 1129 UDF: ZAAA-ETKG-X44X-KEY2 1130 Scalar: 67824881411761849798195083121628378835623370171088982 1131 6937962011129206719268741815680700006802689991287015918654801 1132 310197484516725932432 1133 Encoded Private 1134 90 C1 CE 67 A2 88 20 95 B9 A8 8A E7 5A 12 73 C6 1135 4C E3 B0 0E 3A A4 1A 72 03 39 FC 9B 47 D9 6A E0 1136 A2 81 63 57 77 EB 97 E5 CE 05 2C CB EE D7 64 F6 1137 51 C1 42 E7 FE D9 E2 EE 1138 U: 32395912186842981800922536415382601434069282464793284039370624 1139 1565981551756628007189667971676177150776689230729229736979561 1140 639842244556 1141 V: 18056267944998342850921302138832444826477211000541459460301605 1142 4105989977716699286334066341414636204710801397092415122728296 1143 636211077711 1144 Encoded Public 1145 CC 67 05 A8 AE D3 8C 6E 17 F8 7F 66 77 14 7F 32 1146 D3 F6 12 1C E2 80 A9 BF A9 AA 41 FC 88 EF E3 F9 1147 38 C7 1C AA 1A 14 54 EC F0 4D 6D 20 ED 4F 63 24 1148 F2 A0 68 F5 1C 09 1A 72 80 1150 The composite private key is: 1152 Scalar_A = (Scalar_1 + Scalar_2) mod L 1153 = 87935198894654874397041717160555226349504546089353009501069716070 1154 586506403266723929544670861554164189887604126085304951388779109 1155 045747 1157 Encoded Composite Private Key: 1159 F3 55 F6 DD 05 50 99 B7 68 84 84 A1 C5 89 8A 79 1160 3A 5B F6 27 DE 24 31 97 F5 94 73 D9 14 71 E4 DB 1161 7F 07 B9 C6 45 03 11 56 99 44 E1 9C 59 88 B5 60 1162 B2 B7 02 22 87 BF F8 1E 1164 The composite public key is: 1166 Point_A = Point_1 + Point_2 1168 U: 611634634479536677984900819195998637894371405676964036939736481366 1169 88134799342739585406562158256601376457049422599663606975867088547 1170 575 1171 V: 547531628982729065710146631050685048629332114514125362339393102647 1172 61134803271330580187933395652539791547319114595107754138802418952 1173 4364 1175 Encoded Public 1176 F7 2E 68 4B 64 DC 2E 24 61 B9 28 14 2E 1D D9 41 1177 6A 29 4F A2 5F F1 AF 07 24 6C 9B 8A 9E C0 E5 58 1178 E6 8C ED BE DD C3 34 11 59 B6 DC 64 03 1A 1E BC 1179 D4 B7 88 21 60 DA 8A 15 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: 39507802390720856312219571924476007168388547774368948 1193 368537778683821975155688 1194 Encoded Private 1195 1C C7 DE DF 19 7B 39 5F 82 98 26 62 AA DE 6C 66 1196 04 C3 E3 A2 C8 3D 18 58 06 2C 3E EC 7C D4 B4 F2 1197 X: 42353721841561159243771574200946096579404715276724838688117248 1198 3158919506245796568293273125470706294881250827210288815928170 1199 449575540044968280671060652600 1200 Y: 14453248808291445687399372639220007070442564445118267751942208 1201 0837579501036794314829741330844154033441251810135221340268136 1202 7161993702790547954006637246092 1203 Encoded Public 1204 6D F1 94 33 33 CC 66 4D 93 89 E2 FB 38 61 21 D5 1205 C5 6B 29 0F 5C 12 A8 4D 99 06 31 2D 35 32 22 A5 1207 The key parameters of the second key contribution are: 1209 ED25519Key2 (ED25519) 1210 UDF: ZAAA-GTKG-ED25-5XXK-EY2 1211 Scalar: 39507802390720856312219571924476007168388547774368948 1212 368537778683821975155688 1213 Encoded Private 1214 1C C7 DE DF 19 7B 39 5F 82 98 26 62 AA DE 6C 66 1215 04 C3 E3 A2 C8 3D 18 58 06 2C 3E EC 7C D4 B4 F2 1216 X: 42353721841561159243771574200946096579404715276724838688117248 1217 3158919506245796568293273125470706294881250827210288815928170 1218 449575540044968280671060652600 1219 Y: 14453248808291445687399372639220007070442564445118267751942208 1220 0837579501036794314829741330844154033441251810135221340268136 1221 7161993702790547954006637246092 1222 Encoded Public 1223 6D F1 94 33 33 CC 66 4D 93 89 E2 FB 38 61 21 D5 1224 C5 6B 29 0F 5C 12 A8 4D 99 06 31 2D 35 32 22 A5 1226 The composite private key is: 1228 Scalar_A = (Scalar_1 + Scalar_2) mod L 1229 = 66455490081190904847072782185220719282059319549388206770560479847 1230 89407801486 1232 Encoded Composite Private Key: 1234 8E 20 46 06 EE 61 70 82 FA 37 43 E2 5A 68 E7 3C 1235 73 4A 36 B7 AC A4 DF 68 A7 95 5C 8E 58 3F B1 0E 1237 The composite public key is: 1239 Point_A = Point_1 + Point_2 1241 X: -78285292761951767745666894197721180606214882184104422609189932681 1242 69896558088044165355551471001743951239695738047106458517545601916 1243 4578961762059345997440 1244 Y: 260549350612676062448188625658154114443427558625932490186172625180 1245 16179787773477706605100876536271693949174654809503102876480720244 1246 0555166017893772852160 1248 Encoded Public 1249 8E 89 98 D0 2D 7F 76 C3 A7 FF B3 1D 2B 41 7E E9 1250 51 6B 51 B5 F2 84 8D 17 6F 59 9B 5B 6F 01 CF 73 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: 53741526827163371875813321995189037002816220481405056 1259 0575131176561199901538761967283817989566517114321868559709090 1260 857214825841130713784 1261 Encoded Private 1262 E5 0F 73 50 27 0A 2F 7D FD D0 96 E5 03 D3 35 2C 1263 99 CB 71 7C 0B D9 49 E0 40 5E C7 FB D1 F5 05 18 1264 18 6B 04 81 8B 4D 81 DC 33 CE DF 81 D5 EA 90 43 1265 D9 E5 D0 A7 F1 EF 9C F3 1266 X: 46070586985722000292864744471871508558334313374829024264732526 1267 0256877451971853613261831326120959789917482766653217856979552 1268 299464523257 1269 Y: 60551781313893332009337150573641968782237423331690407655569563 1270 6098829567124403075067563581124781122484845054468415282443786 1271 254887063867 1272 Encoded Public 1273 B5 B9 3F B5 B2 5B 82 E1 08 F5 6C 79 80 A1 68 5A 1274 5C BB 2A FD 27 B2 9A F8 DF 91 CD CA 60 B8 75 3F 1275 62 96 40 38 78 96 77 0C 21 40 E6 D4 0B 05 8F 24 1276 D6 FD 65 61 A2 6C C1 86 80 1278 The key parameters of the second key contribution are: 1280 ED448Key2 (ED448) 1281 UDF: ZAAA-ITKG-ED44-XKEY-2 1282 Scalar: 53741526827163371875813321995189037002816220481405056 1283 0575131176561199901538761967283817989566517114321868559709090 1284 857214825841130713784 1285 Encoded Private 1286 E5 0F 73 50 27 0A 2F 7D FD D0 96 E5 03 D3 35 2C 1287 99 CB 71 7C 0B D9 49 E0 40 5E C7 FB D1 F5 05 18 1288 18 6B 04 81 8B 4D 81 DC 33 CE DF 81 D5 EA 90 43 1289 D9 E5 D0 A7 F1 EF 9C F3 1290 X: 46070586985722000292864744471871508558334313374829024264732526 1291 0256877451971853613261831326120959789917482766653217856979552 1292 299464523257 1293 Y: 60551781313893332009337150573641968782237423331690407655569563 1294 6098829567124403075067563581124781122484845054468415282443786 1295 254887063867 1296 Encoded Public 1297 B5 B9 3F B5 B2 5B 82 E1 08 F5 6C 79 80 A1 68 5A 1298 5C BB 2A FD 27 B2 9A F8 DF 91 CD CA 60 B8 75 3F 1299 62 96 40 38 78 96 77 0C 21 40 E6 D4 0B 05 8F 24 1300 D6 FD 65 61 A2 6C C1 86 80 1302 The composite private key is: 1304 Scalar_A = (Scalar_1 + Scalar_2) mod L 1305 = 16628213117375882432961168004377507211427270876895354579839960414 1306 666978326982600598665720267457234882718565087272340290578290296 1307 3178673 1309 Encoded Composite Private Key: 1311 B1 0C A6 9F 18 5C CE 75 68 CF A3 94 FD 1C 20 DC 1312 08 4A 1A 8D EA 8F ED 45 17 68 B6 9F 55 03 DA 18 1313 5F A8 2E F3 98 92 24 C7 C2 05 8E 86 9E BD 4E A2 1314 6F 38 45 74 67 F6 90 3A 1316 The composite public key is: 1318 Point_A = Point_1 + Point_2 1320 X: 577530061094566245645474620282168197911998758313406086914794815409 1321 17246422939462333536659252558650386613682198540830437043888246526 1322 5810 1323 Y: 505836808606768081321267696834164575314792405646755177389264860926 1324 82650383803094471233632502605998926567195957732072433352975006488 1325 1824 1327 Encoded Public 1328 99 67 9B 7C 5E 1C 7E 51 CD 39 A2 41 83 62 73 3E 1329 60 93 17 A9 20 0E E3 BA 25 B3 B5 23 A3 A7 84 2E 1330 9D 67 6F D7 0B 33 02 1D EB 76 83 F8 77 D8 48 F8 1331 8B A3 72 E8 A9 6F 20 18 80 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: 36212799908425711450656372795692477094724455418915704 1341 216848228525958587810064 1342 Encoded Private 1343 10 01 D5 D1 E2 D3 DB 42 9E 40 5F D9 DB AE E8 09 1344 DE 43 C3 E6 D1 4F 3A 31 92 BF 19 8A E9 B7 0F 50 1345 U: 14523539712308371644546850739155588238080554014514563739095172 1346 886049239361031 1347 V: 56685060472089790044070522288405984326906734250304251487683593 1348 932889808473139 1349 Encoded Public 1350 07 66 84 48 25 85 F6 4A 3A EE DF B7 69 1B 57 51 1351 EC 18 BE AF 08 BA 0D FE BE F8 74 4E 3C 08 1C 20 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: 32951726132685026729149224926255648061071804906258082 1360 061427666995947179849152 1361 Encoded Private 1362 C0 B5 33 D4 F3 D0 16 4F 96 DF C3 AD 97 93 02 EF 1363 B4 25 E2 46 A3 69 1D 22 9B 5B A2 78 1C 04 DA 48 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 = 403147584512037825404691865456117698808221309075461782425833707 1371 7336679400315 1372 This is encoded as a binary integer in little endian format: 1374 7B 43 64 61 E9 28 4D 79 AB 9C 6E CC 9F 79 14 3D 1375 92 69 A5 2D 75 B9 57 53 2D 1B BC 02 06 BC E9 08 1377 6.2.2. Direct Decryption X25519 1379 The means of encryption is unchanged. We begin by generating an 1380 ephemeral key pair: 1382 X25519KeyE (X25519) 1383 UDF: ZAAA-CTHD-X255-XXKE-YE 1384 Scalar: 41955577142906312619127105554814681129195921605852142 1385 704362465226652441661496 1386 Encoded Private 1387 38 50 3C 88 22 4F 61 D7 9A 2E 1D 71 F0 31 74 44 1388 A2 3B 2B 35 21 21 CA 19 4B 11 EB F0 DF 03 C2 5C 1389 U: 10080018124246254127076649374753145019412450363156572968151721 1390 892767560820008 1391 V: 43683938787921854603630290352714276342923724280578266457509078 1392 671566344321831 1393 Encoded Public 1394 28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28 1395 8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16 1397 The key agreement result is given by multiplying the public key of 1398 the encryption pair by the secret scalar of the ephemeral key to 1399 obtain the u-coordinate of the result. 1401 U: 247351751388894803426442650867524924086144759194834658830326105266 1402 22202018180 1404 The u-coordinate is encoded in the usual fashion (i.e. without 1405 specifying the sign of v). 1407 84 39 A5 21 13 F9 13 F0 7F F4 44 C0 DF 5D 44 DD 1408 DD F4 9B 87 4C DD E1 AB 64 00 8F A2 ED 9C AF 36 1410 The first decryption contribution is generated from the secret scalar 1411 of the first key share and the public key of the ephemeral. 1413 The outputs from the Montgomery Ladder are: 1415 x_2 57800249527850149046770413207257250301842844049677844025524059085 1416 132359257003 1417 z_2 37229326806761131733056994095424883574786241198535734197174081138 1418 402379671391 1419 x_3 30722194817314627970562030033494699359853137448471883846088158083 1420 361967945513 1421 z_3 29143359268139878301695995826542801325089258636824690596939399658 1422 126254126746 1424 The coordinates of the corresponding point are: 1426 u 2625200443692459084967263034650122583671912028244890150161521677645 1427 8728744244 1428 v 2340339249609928967870268630489687123941624857494487121340604194885 1429 7707717709 1431 The encoding of this point specifies the u coordinate and the sign 1432 (oddness) of the v coordinate: 1434 28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28 1435 8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16 1437 The second decryption contribution is generated from the secret 1438 scalar of the second key share and the public key of the ephemeral in 1439 the same way: 1441 u 2568180775076864300893967221119748767931055928591855851227298301978 1442 9028635830 1443 v 5237624535641756510077423429806596028526835148653096601777403098805 1444 4910628425 1446 28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28 1447 8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16 1449 To obtain the key agreement value, we add the two decryption 1450 contributions: 1452 u 5363809193902384353244842537457427150937755976201184630020143767288 1453 0976727749 1454 v 2576238777948215852102595446870010694371604288066653261024661407554 1455 3602367190 1457 This returns the same u coordinate value as before, allowing us to 1458 obtain the encoding of the key agreement value and decrypt the 1459 message. 1461 6.2.3. Direct Key Splitting X448 1463 The encryption key pair is 1464 X448KeyA (X448) 1465 UDF: ZAAA-ETHD-X44X-KEYA 1466 Scalar: 70596789123829480733485730386174565339013185647363028 1467 6777277621057939099785091228353248522408450794128800398810019 1468 569879502484967206280 1469 Encoded Private 1470 88 2D AF 58 10 66 9E 1E F9 F2 C5 76 A2 00 86 F5 1471 B0 B9 C6 B9 E6 34 12 57 64 E3 63 B7 99 48 01 77 1472 9B A3 49 2D 7C B8 80 D7 63 44 6B C9 CB 83 F0 01 1473 B6 55 E0 92 1C 2A A6 F8 1474 U: 54256629638851994806054576189463839532492460394052748417730874 1475 4299533502601001906894660938607827805200569088593927035891085 1476 28218439174 1477 V: 12640494198304757803713993624351573936804262085795518571061045 1478 0631383333635306581037675004961525698205648857075020359124084 1479 524068583614 1480 Encoded Public 1481 06 FE 38 7A 1B 1E 99 D4 89 00 07 B9 88 6F 97 01 1482 BD 88 BB 9D A9 31 30 CC 47 E6 2F 9C 44 35 AF A4 1483 6C B8 3B EE 89 C0 99 6B E4 7C 75 33 94 85 BC B8 1484 54 36 AF D9 C0 17 1C 13 1486 To create n key shares we first create n-1 key pairs in the normal 1487 fashion. Since these key pairs are only used for decryption 1488 operations, it is not necessary to calculate the public components: 1490 X448Key1 (X448) 1491 UDF: ZAAA-ETHD-X44X-KEYX 1492 Scalar: 63066265672668423343291438147840057172035337936373473 1493 3594300758463732521976388313294665447253881782852832499090049 1494 354258188417511652528 1495 Encoded Private 1496 B0 FC CE 55 87 AA A5 36 D2 5B E5 F2 5C 1B F7 9A 1497 5A 3D 97 D8 BB C0 81 84 98 3B 7C 29 C3 02 FC AE 1498 91 1B EA 67 68 C5 5E 87 7A ED 16 1F CB D0 20 9D 1499 C0 D6 62 BD 0F 35 20 DE 1501 The secret scalar of the final key share is the secret scalar of the 1502 base key minus the sum of the secret scalars of the other shares 1503 modulo the group order: 1505 Scalar_2 = (Scalar_A - Scalar_1) mod L 1506 = 646627804476669823064550215361382899916128546345584148789705309 1507 5564959403070244163454368262048594523846084193642728800427461 1508 1461310355 1509 This is encoded as a binary integer in little endian format: 1511 93 47 14 FF 94 BE F6 5C 77 63 44 89 DD CA 83 A6 1512 1A 79 82 CA 9E F6 6B 7D 98 23 59 77 60 4B FD 25 1513 2D BF 33 95 E4 7D DF 5E DE 31 82 E8 96 54 11 9F 1514 76 2C 43 50 2C 5F C6 16 1516 6.2.4. Direct Decryption X448 1518 The means of encryption is unchanged. We begin by generating an 1519 ephemeral key pair: 1521 X448KeyE (X448) 1522 UDF: ZAAA-ETHD-X44X-KEYE 1523 Scalar: 40831502887772840901106715270468009328116701340228919 1524 4447950742749557088789408677311466089336893170031425082958041 1525 776608657845012501716 1526 Encoded Private 1527 D4 94 79 EE 56 3A 43 D5 FC EB 88 3E F0 63 EF 2F 1528 B0 92 B2 9D FD E1 43 8F 67 70 2A FC 2A AB A3 8B 1529 40 5A C6 D8 DE 8E B8 81 BF AD 17 BA 14 7F A4 B0 1530 D4 B1 9F CE D3 0D D0 8F 1531 U: 41902542857582644710501442087876846551351583947506685319975417 1532 2921931242764163121977613761818608927787788470856012050834001 1533 655292441835 1534 V: 40254626888669687592165362896510117701831215997629302922912638 1535 4107109948063151002535904960734463095918076287222011626898597 1536 213849340021 1537 Encoded Public 1538 EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C 1539 B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB 1540 D7 3D EC 20 0B 70 82 A6 38 FC 23 24 AD 98 86 35 1541 4C 99 AD 4D 0E C4 95 93 1543 The key agreement result is given by multiplying the public key of 1544 the encryption pair by the secret scalar of the ephemeral key to 1545 obtain the u-coordinate of the result. 1547 U: 414519841929159382730636919036875317796178034011999213235983537052 1548 30510678702415242441193107876747178183775523375063128358893667955 1549 0233 1551 The u-coordinate is encoded in the usual fashion (i.e. without 1552 specifying the sign of v). 1554 19 ED 3F 7A 63 6D AA 9A 3E 05 29 DE CC BA C7 F1 1555 E0 A7 FA C0 C4 70 E0 E1 A5 FC DA 0A B0 52 EC 8A 1556 36 9B 35 6D BE FE 0A 95 22 A3 1F 8A C0 89 0F 19 1557 9A 01 8C CB 17 84 FF 91 00 1559 The first decryption contribution is generated from the secret scalar 1560 of the first key share and the public key of the ephemeral. 1562 The outputs from the Montgomery Ladder are: 1564 x_2 60087238657789265874539701675840521614326868580285788286550399232 1565 20277081132468800878653228200859196207538481852097024468118288584 1566 83595 1567 z_2 12573140552649037921890899942919440571502561130496393232716617155 1568 24490660805576517881339517005970098784771472127066810694797758409 1569 67645 1570 x_3 40216911160845555507626938485596306260547743077930604703891475599 1571 53207238052152872831803734397389643529057507149471429452955111471 1572 57394 1573 z_3 48671808823760924633626118221453591105199403417491562559814414359 1574 34079336265430685974504655698846599309734305554546571306740770389 1575 79747 1577 The coordinates of the corresponding point are: 1579 u 5310627084956226133549480379012439149584638171147187426442235629260 1580 04186474991811830611467926523417739685244466041108245014409383321 1581 437 1582 v 6480384951984610654865132490606294355962228129695701220316681167173 1583 89634554460437237795204236689985354028508124817314496063921770833 1584 81 1586 The encoding of this point specifies the u coordinate and the sign 1587 (oddness) of the v coordinate: 1589 EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C 1590 B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB 1591 D7 3D EC 20 0B 70 82 A6 38 FC 23 24 AD 98 86 35 1592 4C 99 AD 4D 0E C4 95 93 1594 The second decryption contribution is generated from the secret 1595 scalar of the second key share and the public key of the ephemeral in 1596 the same way: 1598 u 2432029307606011854651950642127064534858415441240032460817128643691 1599 02601495764607628214871657677482439232238254450281582409532827123 1600 057 1601 v 3304237495909049135999182737314299324454426462198935317955136317282 1602 40167193898154033571033048069157608137872491595181800632292085611 1603 537 1605 EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C 1606 B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB 1607 D7 3D EC 20 0B 70 82 A6 38 FC 23 24 AD 98 86 35 1608 4C 99 AD 4D 0E C4 95 93 1610 To obtain the key agreement value, we add the two decryption 1611 contributions: 1613 u 2259776336573351712090323684006287979378142231675451855263136351631 1614 84627019682834233607456823018602790573389381890060345691088913511 1615 436 1616 v 3356804465434915738990773252496451168197759413718456519751139752920 1617 22788339143143140400339843420207702195408750068698590142923542805 1618 226 1620 This returns the same u coordinate value as before, allowing us to 1621 obtain the encoding of the key agreement value and decrypt the 1622 message. 1624 6.2.5. Shamir Secret Sharing X448 1626 [TBS] 1628 6.2.6. Lagrange Decryption X448 1630 [TBS] 1632 7. Security Considerations 1634 All the security considerations of [RFC7748] and [RFC8032] apply and 1635 are hereby incorporated by reference. 1637 7.1. Complacency Risk 1639 Separation of duties can lead to a reduction in overall security 1640 through complacency and lack of oversight. 1642 Consider the case in which a role that was performed by A alone is 1643 split into two roles B and C. If B and C each do their job with the 1644 same diligence as A did alone, risk should be reduced but if B and C 1645 each decide they can be careless because security is the 1646 responsibility of the other, the risk of a breach may be 1647 substantially increased. 1649 It is therefore important that each of the participants in a 1650 threshold scheme perform their responsibilities with the same degree 1651 of diligence as if they were the sole control and for those 1652 responsible for oversight to treat single point failures that do not 1653 lead to an actual breach with the same degree of concern as if a 1654 breach had occurred. 1656 Use of threshold operation modes mitigates but does not eliminate 1657 security considerations relating to private key operations of the 1658 underlying algorithm. For example, use of threshold key generation 1659 to generate a composite keypair {b+c, B+C} from key contributions {b, 1660 B} and {c, C} produces a strong composite private key if either of 1661 the key contributions _a_, _b_ are strong. But the composite key 1662 will be weak if neither contribution is strong. 1664 7.2. Rogue Key Attack 1666 In general, threshold modes of operation provide a work factor that 1667 is at least as high as that of the work factor of the strongest 1668 private key share. The karmic tradeoff for this benefit is that the 1669 trustworthiness of a composite public key is that of the least 1670 trustworthy input. 1672 For example, consider the case in which a client with keypair {c, C} 1673 generates an ephemeral keypair {e, E} for use in an authentication 1674 algorithm. We might decide to create an 'efficient' proof of 1675 knowledge of c and e by using the composite public key A = C+E to 1676 test for knowledge of both at the same time. 1678 This approach fails because an attacker with knowledge of C can 1679 generate a keypair {a, A} and calculate the corresponding public key 1680 E = A-C. The attacker can then use the value a in the authentication 1681 protocol. 1683 8. IANA Considerations 1685 This document requires no IANA actions (yet). 1687 It will be necessary to define additional code points for the signed 1688 version of the X25519 and X448 public key and the threshold 1689 decryption final private keys. 1691 9. Acknowledgements 1693 Rene Struik, Tony Arcieri, Scott Fluhrer, Scott Fluhrer, Dan Brown, 1694 Mike Hamburg 1696 10. Appendix A: Calculating Lagrange coefficients 1698 The following C# code calculates the Lagrange coefficients used to 1699 recover the secret from a set of shares. 1701 [TBS] 1703 11. Normative References 1705 [draft-ietf-lwig-curve-representations] 1706 Struik, R., "Alternative Elliptic Curve Representations", 1707 Work in Progress, Internet-Draft, draft-ietf-lwig-curve- 1708 representations-12, August 24, 2020, 1709 . 1712 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1713 Requirement Levels", BCP 14, RFC 2119, 1714 DOI 10.17487/RFC2119, March 1997, 1715 . 1717 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1718 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1719 2016, . 1721 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1722 Signature Algorithm (EdDSA)", RFC 8032, 1723 DOI 10.17487/RFC8032, January 2017, 1724 . 1726 12. Informative References 1728 [Costello17] 1729 Costello, C. and B. Smith, "Montgomery curves and their 1730 arithmetic", 2017. 1732 [draft-hallambaker-mesh-architecture] 1733 Hallam-Baker, P., "Mathematical Mesh 3.0 Part I: 1734 Architecture Guide", Work in Progress, Internet-Draft, 1735 draft-hallambaker-mesh-architecture-14, July 27, 2020, 1736 . 1739 [draft-hallambaker-mesh-developer] 1740 Hallam-Baker, P., "Mathematical Mesh: Reference 1741 Implementation", Work in Progress, Internet-Draft, draft- 1742 hallambaker-mesh-developer-10, July 27, 2020, 1743 . 1746 [draft-hallambaker-threshold-sigs] 1747 Hallam-Baker, P., "Threshold Signatures in Elliptic 1748 Curves", Work in Progress, Internet-Draft, draft- 1749 hallambaker-threshold-sigs-03, July 28, 2020, 1750 . 1753 [Kocher96] Kocher, P. C., "Timing attacks on implementations of 1754 Diffie-Hellman, RSA, DSS, and other systems.", 1996. 1756 [Lopez99] L?opez, J. and R. Dahab, "Fast multiplication on elliptic 1757 curves over GF(2m) without precomputation.", 1999. 1759 [Okeya01] Okeya, K. and K. Sakurai, "Efficient elliptic curve 1760 cryptosystems from a scalar multiplication algorithm with 1761 recovery of the y-coordinate on a Montgomeryform elliptic 1762 curve.", 2001. 1764 [RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method", 1765 RFC 2631, DOI 10.17487/RFC2631, June 1999, 1766 . 1768 [Shamir79] Shamir, A., "How to share a secret.", 1979.