idnits 2.17.1 draft-hallambaker-threshold-00.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 -- The document date (5 January 2020) is 1573 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'TBS' is mentioned on line 636, but not defined Summary: 1 error (**), 0 flaws (~~), 2 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 Venture Cryptography. 4 Intended status: Informational 5 January 2020 5 Expires: 8 July 2020 7 Threshold Key Generation and Decryption in Ed25519 and Ed448 8 draft-hallambaker-threshold-00 10 Abstract 12 Threshold cryptography schemes are described with application to the 13 Ed25519, Ed448, X25519 and X448 Elliptic Curves. Threshold key 14 generation allows generation of keypairs to be divided between two or 15 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. 21 https://mailarchive.ietf.org/arch/browse/cfrg/ 22 (http://whatever)Discussion of this draft should take place on the 23 CFRG mailing list (cfrg@irtf.org), which is archived at . 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at https://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on 8 July 2020. 42 Copyright Notice 44 Copyright (c) 2020 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 49 license-info) in effect on the date of publication of this document. 50 Please review these documents carefully, as they describe your rights 51 and restrictions with respect to this document. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 56 2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 2.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 58 2.2. Defined Terms . . . . . . . . . . . . . . . . . . . . . . 3 59 2.3. Related Specifications . . . . . . . . . . . . . . . . . 5 60 2.4. Implementation Status . . . . . . . . . . . . . . . . . . 5 61 3. Principles . . . . . . . . . . . . . . . . . . . . . . . . . 5 62 3.1. Application to Diffie Hellman (not normative) . . . . . . 5 63 3.2. Threshold Decryption . . . . . . . . . . . . . . . . . . 7 64 3.2.1. Key Splitting . . . . . . . . . . . . . . . . . . . . 7 65 3.2.2. Decryption . . . . . . . . . . . . . . . . . . . . . 7 66 3.3. Threshold Key Generation . . . . . . . . . . . . . . . . 8 67 3.3.1. Device Provisioning . . . . . . . . . . . . . . . . . 8 68 3.3.2. Key Rollover . . . . . . . . . . . . . . . . . . . . 9 69 3.3.3. Host Activation . . . . . . . . . . . . . . . . . . . 10 70 3.3.4. Separation of Duties . . . . . . . . . . . . . . . . 10 71 3.4. Side Channel Resistance . . . . . . . . . . . . . . . . . 10 72 4. Application to Elliptic Curves . . . . . . . . . . . . . . . 11 73 4.1. Implementation for Ed25519 and Ed448 . . . . . . . . . . 11 74 4.1.1. Ed25519 . . . . . . . . . . . . . . . . . . . . . . . 12 75 4.1.2. Ed448 . . . . . . . . . . . . . . . . . . . . . . . . 12 76 4.2. Implementation for X25519 and X448 . . . . . . . . . . . 13 77 4.2.1. Point Encoding . . . . . . . . . . . . . . . . . . . 14 78 4.2.2. X25519 Point Encoding . . . . . . . . . . . . . . . . 14 79 4.2.3. X448 Point Encoding . . . . . . . . . . . . . . . . . 14 80 4.2.4. Point Addition . . . . . . . . . . . . . . . . . . . 14 81 4.2.5. Montgomery Ladder with Coordinate Recovery . . . . . 15 82 5. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 17 83 5.1. Threshold Key Generation . . . . . . . . . . . . . . . . 17 84 5.1.1. X25519 . . . . . . . . . . . . . . . . . . . . . . . 17 85 5.1.2. X448 . . . . . . . . . . . . . . . . . . . . . . . . 19 86 5.1.3. Ed25519 . . . . . . . . . . . . . . . . . . . . . . . 21 87 5.1.4. Ed448 . . . . . . . . . . . . . . . . . . . . . . . . 22 88 5.2. Threshold Decryption . . . . . . . . . . . . . . . . . . 24 89 5.2.1. Key Splitting X25519 . . . . . . . . . . . . . . . . 24 90 5.2.2. Decryption X25519 . . . . . . . . . . . . . . . . . . 25 91 5.2.3. Key Splitting X448 . . . . . . . . . . . . . . . . . 27 92 5.2.4. Decryption X448 . . . . . . . . . . . . . . . . . . . 29 93 6. Security Considerations . . . . . . . . . . . . . . . . . . . 31 94 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31 95 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 31 96 9. Normative References . . . . . . . . . . . . . . . . . . . . 31 97 10. Informative References . . . . . . . . . . . . . . . . . . . 32 99 1. Introduction 101 Public key cryptography provides greater functionality than symmetric 102 key cryptography by introducing separate keys for separate roles. 103 Knowledge of the public encryption key does not provide the ability 104 to decrypt. Knowledge of the public signature verification key does 105 not provide the ability to sign. Threshold cryptography extends the 106 scope of traditional public key cryptography with further separation 107 of roles. 109 A Threshold scheme is _interchangeable_ if the inputs and outputs of 110 the threshold scheme are identical to those of a conventional scheme. 111 A threshold scheme is _auditable_ if it to verify that the output 112 made use of a particular contribution. 114 This document describes a threshold decryption and an auditable 115 threshold key generation scheme for the elliptic curve scheme 116 described in [RFC7748] and [RFC8032]. Both schemes are 117 interchangeable in their own right but require minor modifications to 118 the underlying elliptic curve systems to encode the necessary 119 information in the public (X25519/X448) or private key (Ed25519/ 120 Ed448). 122 Threshold key agreement and threshold signatures will be specified in 123 future drafts. 125 2. Definitions 127 This section presents the related specifications and standard, the 128 terms that are used as terms of art within the documents and the 129 terms used as requirements language. 131 2.1. Requirements Language 133 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 134 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 135 document are to be interpreted as described in [RFC2119]. 137 2.2. Defined Terms 139 The following terms are used as terms of art in this document. 141 Auditable Whether it is possible (or not) to verify that the output 142 of a threshold scheme made use of a particular contribution. 144 Interchangeable A Threshold scheme is _interchangeable_ if the 145 inputs and outputs of the threshold scheme are identical to those 146 of a conventional scheme 148 Multi-Encryption The use of multiple decryption fields to allow a 149 document encrypted under a session key to be decrypted by multiple 150 parties under different decryption keys. 152 Multi-Encryption allows a document to be shared with multiple 153 recipients but does not allow the decryption role to be divided 154 between multiple parties. 156 Multi-Signatures The use of multiple independently verifiable 157 digital signatures to authenticate a document. 159 Multi-Signatures allow separation of the signing roles and thus 160 achieve a threshold capability. But they are not true threshold 161 signatures as the set of signers is visible to external parties. 163 Onboarding The process by which an embedded device is provisioned 164 for deployment in a local network. 166 Threshold Key Generation An aggregate public, private key pair is 167 constructed from a set of contributions such that the private key 168 is a function of the private key of all the contributions. 170 A Threshold Key Generation function is auditable if and only if 171 the public component of the aggregate key can be computed from the 172 public keys of the contributions alone. 174 Threshold Decryption Threshold decryption divides the decryption 175 role between two or more parties. 177 Threshold Key Agreement A bilateral key agreement exchange in which 178 one or both sides present multiple public keys and the key 179 agreement value is a function of all of them. 181 This approach allows a party to present multiple credentials in a 182 single exchange, a de 184 Threshold Signatures Threshold signatures divide the signature role 185 between two or more parties in such a way that the parties and 186 their roles is not visible to an external observer. 188 2.3. Related Specifications 190 This document extends the elliptic curve cryptography systems 191 described in [RFC7748] and [RFC8032] to provide threshold 192 capabilities. 194 This work was originally motivated by the requirements of the 195 Mathematical Mesh [draft-hallambaker-mesh-architecture] 197 2.4. Implementation Status 199 The implementation status of the reference code base is described in 200 the companion document [draft-hallambaker-mesh-developer]. 202 3. Principles 204 The threshold cryptography mechanisms described in this specification 205 are made possible by the fact that Diffie Hellman key agreement and 206 elliptic curve variants thereof support properties we call the Key 207 Combination Law and the Result Combination Law. 209 Let {_X_, _x_}, {_Y_, _y_}, {_A_, _a_} be {public, private} key pairs 210 and r [.] S represent the Diffie Hellman operation applying the 211 private key r to the public key S. 213 The Key Combination law states that we can define an operator [x] 214 such that there is a keypair {_Z_, _z_} such that: 216 _Z_ = _X_ [x] _Y_ and _z_ = (_x_ + _y_) mod _o_ (where _o_ is the 217 order of the group) 219 The Result Combination Law states that we can define an operator [+] 220 such that: 222 (_x_ [.] _A_) [+] (_y_ [.] _A_) = (_z_ [.] _A_) = (_a_ [.] _Z_) 224 It will be noted that each of these laws is interchangeable. The 225 output of the key combination law to a Diffie Hellman key pair is a 226 Diffie Hellman key pair and the output of the result combination law 227 is a Diffie Hellman result. This allows modular and recursive 228 application of these principles. 230 3.1. Application to Diffie Hellman (not normative) 232 Diffie Hellman in a modular field provides a concise demonstration of 233 the key combination and result combination laws [RFC2631]. The 234 realization of the threshold schemes in a modular field is outside 235 the scope of this document. 237 For the Diffie Hellman system in a modular field p, with exponent e: 239 * r [.] S = S^(r) mod p 241 * o = p-1 243 * _A_[x] _B_ = _A_[.] _B_ = _AB_mod _p_. 245 _Proof:_ 247 Let z = x + y 249 By definition, X = e^(x) mod p, Y = e^(y) mod p, and Z = e^(z)mod p. 251 Therefore, 253 Z = e^(z) mod p = e^(x+y) mod p 255 = (e^(x)e^(y)) mod p 257 = e^(x)mod p.e^(y) mod p 259 = X.Y 261 Moreover, A = e^(a) mod p, 263 Therefore, 265 (A^(x) mod p).(A^(y) mod p) = (A^(x)A^(y)) mod p) 267 = (A^(x+y)) mod p) 269 = A^(z) mod p 271 = e^(az) mod p 273 = (e^(z))^(a) mod p 275 = Z^(a) mod p 277 Since e^(o) mod p = 1, the same result holds for z = (x + y) mod o 278 since e^(x+y+no) = e^(x+y).e^(no) = e^(x+y).1 = e^(x+y). 280 3.2. Threshold Decryption 282 Threshold decryption allows a decryption key to be divided into two 283 or more parts, allowing these roles to be assigned to different 284 parties. This capability can be employed within a machine to divide 285 use of a private key between an implementation running in the user 286 mode and a process running in a privileged mode that is bound to the 287 machine. Alternatively, threshold cryptography can be employed to 289 The key combination law and result combination law provide a basis 290 for threshold decryption. 292 3.2.1. Key Splitting 294 We begin by creating a base key pair { X, x }. The public component X 295 is used to perform encryption operations by means of a key agreement 296 against an ephemeral key in the usual fashion. The private component 297 x may be used for decryption in the normal fashion or to provide the 298 source material for a key splitting operation. 300 To split the base key into n shares { S_(1), s_(1) }, { S_(2), s_(2) 301 }, ... { S_(n), s_(n) }, we begin by generating the first n-1 private 302 keys in the normal fashion. It is not necessary to generate the 303 corresponding public keys as these are not required. 305 The private key of the final key share s_(n) is given by: 307 _s_(n) = (x - s1 - s2 - ... - sn-1) mod o_ 309 Thus, the base private key x is equal to the sum of the private key 310 shares modulo the group order. 312 3.2.2. Decryption 314 To encrypt a document, we first generate an ephemeral key pair { Y, y 315 }. The key agreement value e^(xy) is calculated from the base public 316 key X = e^(x) and the ephemeral private key y. A key derivation 317 function is then used to obtain the session key to be used to encrypt 318 the document under a symmetric cipher. 320 To decrypt a document using the threshold key shares, each key share 321 holder first performs a Diffie Hellman operation using their private 322 key on the ephemeral public key. The key shares are then combined 323 using the result combination law to obtain the key exchange value 324 from which the session key is recovered. 326 The key contribution c_(i) for the holder of the i^(th) key share is 327 calculated as: 329 c_(i) = Y^(si) 331 The key agreement value is thus 333 A = c_(1) . c_(2) . ... . c_(n) 335 This value is equal to the encryption key agreement value according 336 to the group law. 338 3.3. Threshold Key Generation 340 The key combination law allows an aggregate private key to be derived 341 from private key contributions provided by two or more parties such 342 that the corresponding aggregate public key may be derived from the 343 public keys corresponding to the contributions. The resulting key 344 generation mechanism is thus, auditable and interoperable. 346 3.3.1. Device Provisioning 348 Auditable Threshold Key Generation provides a simple and efficient 349 means of securely provisioning keys to devices. This is encountered 350 in the IoT space as a concern in 'onboarding' and in the provisioning 351 of unique keys for use with cryptographic applications (e.g. SSH, S/ 352 MIME, OpenPGP, etc.). 354 Consider the case in which Alice purchases an IoT connected Device D 355 which requires a unique device key pair _{ X , x }_ for its 356 operation. The process of provisioning (aka 'onboarding') is 357 performed using an administration device. Traditional key pair 358 generation gives us three options: 360 * Generate and install a key pair during manufacture. 362 * Generate a new key pair during device provisioning. 364 * Generate a key pair on the administration device and transfer it 365 to the device being provisioned. 367 The first approach has the obvious disadvantage that the manufacturer 368 has knowledge of the private key. This represents a liability for 369 both the user and the manufacturer. Less obvious is the fact that 370 the second approach doesn't actually provide a solution unless the 371 process of generating keys on the device is auditable. The third 372 approach is auditable with respect to the device being provisioned 373 but not with respect to the administration device being used for 374 provisioning. If that device were to be compromised, so could every 375 device it was used to provision. 377 Threshold key generation allows the administration device and the 378 joining device being provisioned to jointly provision a key pair as 379 follows: 381 * The joining device has public, private key pair_{ D, d }_. 383 * A provisioning request is made for the device which includes the 384 joining device public key _D_. 386 * The administration device generates a key pair contribution _{ A, 387 a }_. 389 * The administration device private key is transmitted to the Device 390 by means of a secure channel. 392 * The joining device calculates the aggregate key pair _{ A [x] D, 393 a+d }_. 395 * The administration device authorizes the joining device to 396 participate in the local network using the public key _A [x] D_. 398 The Device key pair MAY be installed during manufacture or generated 399 during provisioning or be derived from a combination of both using 400 threshold key generation recursively. The provisioning request MAY 401 be originated by the device or be generated by a purchasing system. 403 Note that the provisioning protocol does not require either party to 404 authenticate the aggregate key pair. The protocol provides security 405 by ensuring that both parties obtain the correct results if and only 406 if the values each communicated to the other were correct. 408 Out of band authentication of the joining device public key _D_ is 409 sufficient to prevent Man-in-the-Middle attack. This may be achieved 410 by means of a QR code printed on the device itself that discloses or 411 provides a means of obtaining _D._ 413 [Note add serious warning that a party providing a private 414 contribution MUST make sure they see the public key first. Otherwise 415 a rogue key attack is possible. The Mesh protocols ensure that this 416 is the case but other implementations may overlook this detail.] 418 3.3.2. Key Rollover 420 Traditional key rollover protocols in PKIX and other PKIs following 421 the Kohnfelder model, require a multi-step interaction between the 422 key holder and the Certificate Authority. 424 Threshold key generation allows a Certificate Authority to implement 425 key rollover with a single communication: 427 Consider the case in which the service host has a base key pair { B , 428 b }. A CA that has knowledge of the Host public key B may generate a 429 certificate for the time period _t_ with a fresh key as follows: 431 * Generate a key pair contribution { A_(t), a_(t) }. 433 * Generate and sign an end entity certificate C_(t) for the key B 434 [x] A_(t). 436 * Transmit C_(t), a_(t) to the host by means of a secure channel 438 3.3.3. Host Activation 440 Modern Internet service architectures frequently make use of short 441 lived, ephemeral hosts running on virtualized machines. Provisioning 442 cryptographic material in such environments is a significant 443 challenge and especially so when the underlying hardware is a shared 444 resource. 446 The key rollover approach described above provides a means of 447 provisioning short lived credentials to ephemeral hosts that 448 potentially avoids the need to build sensitive keys into the service 449 image or configuration. 451 3.3.4. Separation of Duties 453 Threshold key generation provides a means of separating 454 administration of cryptographic keys between individuals. This 455 allows two or more administrators to control access to a private key 456 without having the ability to use it themselves. This approach is of 457 particular utility when used in combination with threshold 458 decryption. Alice and Bob can be granted the ability to create key 459 contributions allowing a user to decrypt information without having 460 the ability to decrypt themselves. 462 3.4. Side Channel Resistance 464 Side-channel attacks, present a major concern in the implementation 465 of public key cryptosystems. Of particular concern are the timing 466 attacks identified by Paul Kocher [Kocher96] and related attacks in 467 the power and emissions ranges. Performing repeated observations of 468 the use of the same private key material provides an attacker with 469 considerably greater opportunity to extract the private key material. 471 A simple but effective means of defeating such attacks is to split 472 the private key value into two or more random shares for every 473 private key operation and use the result combination law to recover 474 the result. 476 The implementation of this approach is identical to that for 477 Threshold Decryption except that instead of giving the key shares to 478 different parties, they are kept by the party performing the private 479 key operation. 481 While this approach doubles the number of private key operations 482 required, the operations MAY be performed in parallel. Thus avoiding 483 impact on the user experience. 485 4. Application to Elliptic Curves 487 For elliptic curve cryptosystems, the operators [x] and [.] are point 488 addition. 490 Implementing a robust Key Co-Generation for the Elliptic Curve 491 Cryptography schemes described in [RFC7748] and [RFC8032] requires 492 some additional considerations to be addressed. 494 * The secret scalar used in the EdDSA algorithm is calculated from 495 the private key using a digest function. It is therefore 496 necessary to specify the Key Co-Generation mechanism by reference 497 to operations on the secret scalar values rather than operations 498 on the private keys. 500 * The Montgomery Ladder traditionally used to perform X25519 and 501 X448 point multiplication does not require implementation of a 502 function to add two arbitrary points. While the steps required to 503 create such a function are fully constrained by [RFC7748], the 504 means of performing point addition is not. 506 4.1. Implementation for Ed25519 and Ed448 508 [RFC8032] provides all the cryptographic operations required to 509 perform threshold operations and corresponding public keys. 511 The secret scalars used in [RFC8032] private key operations are 512 derived from a private key value using a cryptographic digest 513 function. This encoding allows the inputs to a private key 514 combination to be described but not the output. Contrawise, the 515 encoding allows the inputs to a private key splitting operation to be 516 described but not the output 517 It is therefore necessary to provide an alternative representation 518 for the Ed25519 and Ed448 private keys. Moreover, the signature 519 algorithm requires both a secret scalar and a prefix value as inputs. 521 Since threshold signatures are out of scope for this document and 522 [RFC8032] does not specify a key agreement mechanism, it suffices to 523 specify the data formats required to encode private key values 524 generated by means of threshold key generation. 526 4.1.1. Ed25519 528 Let the inputs to the threshold key generation scheme be a set of 32 529 byte private key values _P_(1), P2 ... Pn. For each private key 530 value i in turn:_ 532 0. Hash the 32-byte private key using SHA-512, storing the digest in 533 a 64-octet large buffer, denoted_h_(i)_. Let n_(i) be the first 534 32 octets of h_(i) and m_(i) be the remaining 32 octets of h_(i). 536 1. Prune n_(i): The lowest three bits of the first octet are 537 cleared, the highest bit of the last octet is cleared, and the 538 second highest bit of the last octet is set. 540 2. Interpret the buffer as the little-endian integer, forming a 541 secret scalar s_(i). 543 The private key values are calculated as follows: 545 The aggregate secret scalar value _s_(a) = s1 + s2 + ... sn mod L, 546 where L is the order of the curve._ 548 The aggregate prefix value is calculated by either 550 * Some function TBS on the values m_(1), m_(2), ... m_(n), or 552 * Taking the SHA256 digest of s_(a). 554 The second approach is the simplest and the most robust. It does 555 however mean that the prefix is a function of the secret scalar 556 rather than both being functions of the same seed. 558 4.1.2. Ed448 560 Let the inputs to the threshold key generation scheme be a set of 57 561 byte private key values _P_(1), P2 ... Pn. For each private key 562 value i in turn:_ 563 0. Hash the 57-byte private key using SHAKE256(x, 114), storing the 564 digest in a 114-octet large buffer, denoted_h_(i)_. Let n_(i) be 565 the first 57 octets of h_(i) and m_(i) be the remaining 57 octets 566 of h_(i). 568 1. Prune n_(i): The two least significant bits of the first octet 569 are cleared, all eight bits the last octet are cleared, and the 570 highest bit of the second to last octet is set. 572 2. Interpret the buffer as the little-endian integer, forming a 573 secret scalar s_(i). 575 The private key values are calculated as follows: 577 The aggregate secret scalar value _s_(a) = s1 + s2 + ... sn mod L, 578 where L is the order of the curve._ 580 The aggregate prefix value is calculated by either 582 * Some function TBS on the values m_(1), m_(2), ... m_(n), or 584 * Taking the SHAKE256(x, 57) digest of s_(a). 586 The second approach is the simplest and the most robust. It does 587 however mean that the prefix is a function of the secret scalar 588 rather than both being functions of the same seed. 590 4.2. Implementation for X25519 and X448 592 [RFC7748] defines all the cryptographic operations required to 593 perform threshold key generation and threshold decryption but does 594 not describe how to implement them. 596 The Montgomery curve described in [RFC7748] allows for efficient 597 scalar multiplication using arithmetic operations on a single 598 coordinate. Point addition requires both coordinate values. It is 599 thus necessary to provide an extended representation for point 600 encoding and provide an algorithm for recovering both coordinates 601 from a scalar multiplication operation and an algorithm for point 602 addition. 604 The notation of [RFC7748] is followed using {u, v} to represent the 605 coordinates on the Montgomery curve and {x, y} for coordinates on the 606 corresponding Edwards curve. 608 4.2.1. Point Encoding 610 The relationship between the u and v coordinates is specified by the 611 Montgomery Curve formula itself: 613 _v^(2)_ = _u^(3) + Au2 + u_ 615 An algorithm for extracting a square root of a number in a finite 616 field is specified in . [RFC8032] 618 Since _v^(2)_ has a positive (_v_) and a negative solution (_-v_), it 619 follows that _v^(2)_ mod p will have the solutions _v_, _p-v_. 620 Furthermore, since _p_ is odd, if _v_ is odd, _p-v_ must be even and 621 vice versa. It is thus sufficient to record whether _v_ is odd or 622 even to enable recovery of the _v_ coordinate from _u_. 624 4.2.2. X25519 Point Encoding 626 The extended point encoding allowing the v coordinate to be recovered 627 is as given in [draft-ietf-lwig-curve-representations] 629 [TBS] 631 4.2.3. X448 Point Encoding 633 The extended point encoding allowing the v coordinate to be recovered 634 is as given in [draft-ietf-lwig-curve-representations] 636 [TBS] 638 4.2.4. Point Addition 640 The point addition formula for the Montgomery curve is defined as 641 follows: 643 Let P_(1) = {u_(1), v_(1)}, P_(2) = {u_(2), v_(2)}, P_(3) = {u_(3), 644 v_(3)} = P_(1) + P_(2) 646 By definition: 648 u_(3) = B(v_(2) - v_(1))^(2) / (u_(2) - u_(1))^(2) - A - u_(1) - 649 u_(2) 651 = B((u_(2)v_(1) - u_(1)v_(2))^(2) ) / u_(1)u_(2) (u_(2) - u_(1))^(2) 653 v_(3) = ((2u_(1) + u_(2) + A)(v_(2) - v_(1)) / (u_(2) - u_(1))) - B 654 (v_(2) - v_(1))^(3) / (u_(2) -u_(1))^(3) - v_(1) 655 For curves X25519 and X448, B = 1 and so: 657 u_(3) = ((v_(2) - v_(1)).(u_(2) - u_(1))^(-1))^(2) - A - u_(1) - 658 u_(2) 660 v_(3) = ((2u_(1) + u_(2) + A)(v_(2) - v_(1)).(u_(2) - u_(1))^(-1)) - 661 ((v_(2) - v_(1)).(u_(2) -u_(1))^(-1))^(3) - v_(1) 663 This may be implemented using the following code: 665 B = v2 - v1 666 C = u2 - u1 667 CINV = C^(p - 2) 668 D = B * CINV 669 DD = D * D 670 DDD = DD * D 672 u3 = DD - A - u1 - u2 673 v3 = ((u1 + u1 + u2 + A) * B * CINV) - DDD - v1 675 Performing point addition thus requires that we have sufficient 676 knowledge of the values v_(1), v_(2). At minimum whether one is odd 677 and the other even or if both are the same. 679 4.2.5. Montgomery Ladder with Coordinate Recovery 681 As originally described, the Montgomery Ladder only provides the u 682 coordinate as output. L?pez and Dahab [Lopez99] provided a formula 683 for recovery of the v coordinate of the result for curves over binary 684 fields. This result was then extended by Okeya and Sakurai [Okeya01] 685 to prime field Montgomery curves such as X25519 and X448. The 686 realization of this result described by Costello and Smith 687 [Costello17] is applied here. 689 The scalar multiplication function specified in [RFC7748] takes as 690 input the scalar value k and the coordinate u_(1) of the point P_(1) 691 = {u_(1), v_(1)} to be multiplied. The return value in this case is 692 u_(2) where P_(2) = {u_(2), v_(2)} = k.P_(1). 694 To recover the coordinate v_(2) we require the values x_2, z_2, x_3, 695 z_3 calculated in the penultimate step: 697 x_1 = u 698 x_2 = 1 699 z_2 = 0 700 x_3 = u 701 z_3 = 1 702 swap = 0 704 For t = bits-1 down to 0: 705 k_t = (k >> t) & 1 706 swap ^= k_t 707 // Conditional swap as specified in RFC 7748 708 (x_2, x_3) = cswap(swap, x_2, x_3) 709 (z_2, z_3) = cswap(swap, z_2, z_3) 710 swap = k_t 712 A = x_2 + z_2 713 AA = A^2 714 B = x_2 - z_2 715 BB = B^2 716 E = AA - BB 717 C = x_3 + z_3 718 D = x_3 - z_3 719 DA = D * A 720 CB = C * B 721 x_3 = (DA + CB)^2 722 z_3 = x_1 * (DA - CB)^2 723 x_2 = AA * BB 724 z_2 = E * (AA + a24 * E) 726 (x_2, x_3) = cswap(swap, x_2, x_3) 727 (z_2, z_3) = cswap(swap, z_2, z_3) 728 Return x_2, z_2, x_3, z_3 730 The values x_2, z_2 give the projective form of the u coordinate of 731 the point P_(2) = {u_(2), v_(2)} = k.P_(1) and the values x_3, z_3 732 give the projective form of the u coordinate of the point P_(3) = 733 {u_(3), v_(3)} = (k+1).P_(1) = P_(1) + k.P_(1) = P_(1) + P_(2). 735 Given the coordinates {u_(1), v_(1)} of the point P1 and the u 736 coordinates of the points P_(2), P_(1) + P_(2), the coordinate v_(2) 737 MAY be recovered by trial and error as follows: 739 v_test = SQRT (u3 + Au2 + u) 740 u_test = ADD_X (u, v, u_2, v_test) 741 if (u_test == u_3) 742 return u_test 743 else 744 return u_test +p 746 Alternatively, the following MAY be used to recover {u_(2), v_(2)} 747 without the need to extract the square root and using a single 748 modular exponentiation operation to convert from the projective 749 coordinates used in the calculation. As with the Montgomery ladder 750 algorithm above, the expression has been modified to be consistent 751 with the approach used in [RFC7748] but any correct formula may be 752 used. 754 x_p = u 755 y_p = v 757 B = x_p * z_2 //v1 758 C = x_2 + B //v2 759 D = X_2 - B //v3 760 DD = D^2 //v3 761 E = DD. X_3 //v3 762 F = 2 * A * z_2 //v1 764 G = C + F //v2 765 H = x_p * x_2 //v4 766 I = H + z_2 //v4 767 J = G * I //v2 768 K = F * z_2 //v1 769 L = J - K //v2 770 M = L * z_3 //v2 772 yy_2 = M - E //Y' 773 N = 2 * y_p //v1 774 O = N * z_2 //v1 775 P = O * z_3 //v1 776 xx_2 = P * x_q //X' 777 zz_2 = P * z_ q //Z' 779 ZINV = (zz_2^(p - 2)) 780 u2 = xx_2 * ZINV 781 v2 = yy_2 * ZINV 783 return u2, v2 785 5. Test Vectors 787 5.1. Threshold Key Generation 789 5.1.1. X25519 791 The key parameters of the first key contribution are: 793 X25519Key1 (X25519) 794 UDF: ZAAA-CTKG-X255-XXKE-YX 795 Scalar: 56751742936444772792970879017152360515706108153669948 796 486190735258502824077920 797 Encoded Private 798 60 2A E2 12 AC 8E C8 86 A1 79 51 7E 79 90 5E C2 799 9B AD 10 01 B9 2D 51 33 65 DB F4 9E 23 59 78 7D 800 U: 25222393324990721517739552691612440154338285166262054281502859 801 684220669343438 802 V: 15622452724514925334849257786951944861130311422605147559630230 803 860481236780294 804 Encoded Public 805 CE 36 B9 F1 56 BD 92 5C F4 B6 F5 E1 E0 BA CA 6A 806 9B 7C 37 7D F8 DC 39 CC 12 2E A6 8F 64 5E C3 37 807 00 809 The key parameters of the second key contribution are: 811 X25519Key2 (X25519) 812 UDF: ZAAA-CTKG-X255-XXKE-Y2 813 Scalar: 30800688691513612134093999707357841640579640775881469 814 593062950189697563564400 815 Encoded Private 816 70 19 5B 38 A4 46 21 79 31 AC 48 83 60 C9 BD F8 817 E1 EE 04 53 67 F2 B5 D8 9E 42 53 66 6F 92 18 44 818 U: 35108630063567318397224393939085269372284744000330218923799041 819 589332061533992 820 V: 13827314478911339710714490558315610168380330915483870499348836 821 357802235649136 822 Encoded Public 823 28 37 F5 39 16 C6 10 C6 8A AC 75 E9 20 EF 67 6D 824 C2 6C AF 2C E4 F6 4F C9 E9 30 6C BD C9 C7 9E 4D 825 00 827 The aggregate private key is: 829 Scalar_A = (Scalar_1 + Scalar_2) mod L 830 = 70836469997123835938663996799427126600035261699252680723027418877 831 4936630452 833 Encoded Aggrgate Private Key: 835 B4 54 B7 EF 13 30 0D DF C6 CB FE 5D 6A A3 A8 C0 836 7C 9C 15 54 20 20 07 0C 04 1E 48 05 93 EB 90 01 838 The aggregate public key is: 840 Point_A = Point_1 + Point_2 842 U: 416454936139914218771704724014904891682742086807613599097165979348 843 46285027335 844 V: 473400233126764321363639652645349333601103100790621508110841442520 845 99552212729 847 Encoded Public 848 07 98 75 38 67 9C 66 21 A3 0A D1 06 CF F5 81 04 849 94 C0 52 C9 9C FD AE 4E 13 3B 43 9D 9A 83 12 5C 851 Note that in this case, the unsigned representation of the key is 852 used as the aggregate key is intended for unsigned CurveX key 853 agreement. If the result is intended for use as a key contribution, 854 the signed representation is required. 856 5.1.2. X448 858 The key parameters of the first key contribution are: 860 X448Key1 (X448) 861 UDF: ZAAA-ETKG-X44X-KEYX 862 Scalar: 68165415229434843487640754974827937311214322558126978 863 8055715553507401814865302008262214951100710804646043741434925 864 630887320553400661768 865 Encoded Private 866 08 77 91 25 66 19 C6 1A 03 C7 60 9A 8C C8 10 9D 867 DE F5 20 E1 A7 7F 3E 83 56 57 FE A6 C9 97 79 FB 868 DC 85 55 6F CE 17 79 70 CA 3E B5 D1 6A B0 50 6A 869 60 F6 BF 3A 88 E5 15 F0 870 U: 60697849609835675975297341597995979787516605306209816088918249 871 8293453953345846660594020472424536065173283947670623780408505 872 23120715561 873 V: 60813500494147049417364978264586877278456315581444885337361828 874 5076034450004202627339591608123302429557097118744860203117206 875 220854848663 876 Encoded Public 877 29 C7 E7 1A ED 85 B5 66 F4 CA 8F 4D 07 72 EC 4B 878 15 42 FA 95 4D A3 25 F6 D2 BF C0 5E 11 C4 27 D3 879 A1 43 D8 74 B6 4C C8 22 7D 64 56 58 A4 8C C6 5D 880 DA F2 AA 75 DE DE 60 15 80 882 The key parameters of the second key contribution are: 884 X448Key2 (X448) 885 UDF: ZAAA-ETKG-X44X-KEY2 886 Scalar: 67824881411761849798195083121628378835623370171088982 887 6937962011129206719268741815680700006802689991287015918654801 888 310197484516725932432 889 Encoded Private 890 90 C1 CE 67 A2 88 20 95 B9 A8 8A E7 5A 12 73 C6 891 4C E3 B0 0E 3A A4 1A 72 03 39 FC 9B 47 D9 6A E0 892 A2 81 63 57 77 EB 97 E5 CE 05 2C CB EE D7 64 F6 893 51 C1 42 E7 FE D9 E2 EE 894 U: 32395912186842981800922536415382601434069282464793284039370624 895 1565981551756628007189667971676177150776689230729229736979561 896 639842244556 897 V: 18056267944998342850921302138832444826477211000541459460301605 898 4105989977716699286334066341414636204710801397092415122728296 899 636211077711 900 Encoded Public 901 CC 67 05 A8 AE D3 8C 6E 17 F8 7F 66 77 14 7F 32 902 D3 F6 12 1C E2 80 A9 BF A9 AA 41 FC 88 EF E3 F9 903 38 C7 1C AA 1A 14 54 EC F0 4D 6D 20 ED 4F 63 24 904 F2 A0 68 F5 1C 09 1A 72 80 906 The aggregate private key is: 908 Scalar_A = (Scalar_1 + Scalar_2) mod L 909 = 87935198894654874397041717160555226349504546089353009501069716070 910 586506403266723929544670861554164189887604126085304951388779109 911 045747 913 Encoded Aggrgate Private Key: 915 F3 55 F6 DD 05 50 99 B7 68 84 84 A1 C5 89 8A 79 916 3A 5B F6 27 DE 24 31 97 F5 94 73 D9 14 71 E4 DB 917 7F 07 B9 C6 45 03 11 56 99 44 E1 9C 59 88 B5 60 918 B2 B7 02 22 87 BF F8 1E 920 The aggregate public key is: 922 Point_A = Point_1 + Point_2 924 U: 611634634479536677984900819195998637894371405676964036939736481366 925 88134799342739585406562158256601376457049422599663606975867088547 926 575 927 V: 547531628982729065710146631050685048629332114514125362339393102647 928 61134803271330580187933395652539791547319114595107754138802418952 929 4364 931 Encoded Public 932 F7 2E 68 4B 64 DC 2E 24 61 B9 28 14 2E 1D D9 41 933 6A 29 4F A2 5F F1 AF 07 24 6C 9B 8A 9E C0 E5 58 935 Note that in this case, the unsigned representation of the key is 936 used as the aggregate key is intended for unsigned CurveX key 937 agreement. If the result is intended for use as a key contribution, 938 the signed representation is required. 940 5.1.3. Ed25519 942 The key parameters of the first key contribution are: 944 ED25519Key1 (ED25519) 945 UDF: ZAAA-GTKG-ED25-5XXK-EYX 946 Scalar: 39507802390720856312219571924476007168388547774368948 947 368537778683821975155688 948 Encoded Private 949 1C C7 DE DF 19 7B 39 5F 82 98 26 62 AA DE 6C 66 950 04 C3 E3 A2 C8 3D 18 58 06 2C 3E EC 7C D4 B4 F2 951 X: 42353721841561159243771574200946096579404715276724838688117248 952 3158919506245796568293273125470706294881250827210288815928170 953 449575540044968280671060652600 954 Y: 14453248808291445687399372639220007070442564445118267751942208 955 0837579501036794314829741330844154033441251810135221340268136 956 7161993702790547954006637246092 957 Encoded Public 958 6D F1 94 33 33 CC 66 4D 93 89 E2 FB 38 61 21 D5 959 C5 6B 29 0F 5C 12 A8 4D 99 06 31 2D 35 32 22 A5 961 The key parameters of the second key contribution are: 963 ED25519Key2 (ED25519) 964 UDF: ZAAA-GTKG-ED25-5XXK-EY2 965 Scalar: 39507802390720856312219571924476007168388547774368948 966 368537778683821975155688 967 Encoded Private 968 1C C7 DE DF 19 7B 39 5F 82 98 26 62 AA DE 6C 66 969 04 C3 E3 A2 C8 3D 18 58 06 2C 3E EC 7C D4 B4 F2 970 X: 42353721841561159243771574200946096579404715276724838688117248 971 3158919506245796568293273125470706294881250827210288815928170 972 449575540044968280671060652600 973 Y: 14453248808291445687399372639220007070442564445118267751942208 974 0837579501036794314829741330844154033441251810135221340268136 975 7161993702790547954006637246092 976 Encoded Public 977 6D F1 94 33 33 CC 66 4D 93 89 E2 FB 38 61 21 D5 978 C5 6B 29 0F 5C 12 A8 4D 99 06 31 2D 35 32 22 A5 980 The aggregate private key is: 982 Scalar_A = (Scalar_1 + Scalar_2) mod L 983 = 66455490081190904847072782185220719282059319549388206770560479847 984 89407801486 986 Encoded Aggrgate Private Key: 988 8E 20 46 06 EE 61 70 82 FA 37 43 E2 5A 68 E7 3C 989 73 4A 36 B7 AC A4 DF 68 A7 95 5C 8E 58 3F B1 0E 991 The aggregate public key is: 993 Point_A = Point_1 + Point_2 995 X: -78285292761951767745666894197721180606214882184104422609189932681 996 69896558088044165355551471001743951239695738047106458517545601916 997 4578961762059345997440 998 Y: 260549350612676062448188625658154114443427558625932490186172625180 999 16179787773477706605100876536271693949174654809503102876480720244 1000 0555166017893772852160 1002 Encoded Public 1003 8E 89 98 D0 2D 7F 76 C3 A7 FF B3 1D 2B 41 7E E9 1004 51 6B 51 B5 F2 84 8D 17 6F 59 9B 5B 6F 01 CF 73 1006 5.1.4. Ed448 1008 The key parameters of the first key contribution are: 1010 ED448Key1 (ED448) 1011 UDF: ZAAA-ITKG-ED44-XKEY-X 1012 Scalar: 53741526827163371875813321995189037002816220481405056 1013 0575131176561199901538761967283817989566517114321868559709090 1014 857214825841130713784 1015 Encoded Private 1016 E5 0F 73 50 27 0A 2F 7D FD D0 96 E5 03 D3 35 2C 1017 99 CB 71 7C 0B D9 49 E0 40 5E C7 FB D1 F5 05 18 1018 18 6B 04 81 8B 4D 81 DC 33 CE DF 81 D5 EA 90 43 1019 D9 E5 D0 A7 F1 EF 9C F3 1020 X: 46070586985722000292864744471871508558334313374829024264732526 1021 0256877451971853613261831326120959789917482766653217856979552 1022 299464523257 1023 Y: 60551781313893332009337150573641968782237423331690407655569563 1024 6098829567124403075067563581124781122484845054468415282443786 1025 254887063867 1026 Encoded Public 1027 B5 B9 3F B5 B2 5B 82 E1 08 F5 6C 79 80 A1 68 5A 1028 5C BB 2A FD 27 B2 9A F8 DF 91 CD CA 60 B8 75 3F 1029 62 96 40 38 78 96 77 0C 21 40 E6 D4 0B 05 8F 24 1030 D6 FD 65 61 A2 6C C1 86 80 1032 The key parameters of the second key contribution are: 1034 ED448Key2 (ED448) 1035 UDF: ZAAA-ITKG-ED44-XKEY-2 1036 Scalar: 53741526827163371875813321995189037002816220481405056 1037 0575131176561199901538761967283817989566517114321868559709090 1038 857214825841130713784 1039 Encoded Private 1040 E5 0F 73 50 27 0A 2F 7D FD D0 96 E5 03 D3 35 2C 1041 99 CB 71 7C 0B D9 49 E0 40 5E C7 FB D1 F5 05 18 1042 18 6B 04 81 8B 4D 81 DC 33 CE DF 81 D5 EA 90 43 1043 D9 E5 D0 A7 F1 EF 9C F3 1044 X: 46070586985722000292864744471871508558334313374829024264732526 1045 0256877451971853613261831326120959789917482766653217856979552 1046 299464523257 1047 Y: 60551781313893332009337150573641968782237423331690407655569563 1048 6098829567124403075067563581124781122484845054468415282443786 1049 254887063867 1050 Encoded Public 1051 B5 B9 3F B5 B2 5B 82 E1 08 F5 6C 79 80 A1 68 5A 1052 5C BB 2A FD 27 B2 9A F8 DF 91 CD CA 60 B8 75 3F 1053 62 96 40 38 78 96 77 0C 21 40 E6 D4 0B 05 8F 24 1054 D6 FD 65 61 A2 6C C1 86 80 1056 The aggregate private key is: 1058 Scalar_A = (Scalar_1 + Scalar_2) mod L 1059 = 16628213117375882432961168004377507211427270876895354579839960414 1060 666978326982600598665720267457234882718565087272340290578290296 1061 3178673 1063 Encoded Aggrgate Private Key: 1065 B1 0C A6 9F 18 5C CE 75 68 CF A3 94 FD 1C 20 DC 1066 08 4A 1A 8D EA 8F ED 45 17 68 B6 9F 55 03 DA 18 1067 5F A8 2E F3 98 92 24 C7 C2 05 8E 86 9E BD 4E A2 1068 6F 38 45 74 67 F6 90 3A 1070 The aggregate public key is: 1072 Point_A = Point_1 + Point_2 1074 X: 577530061094566245645474620282168197911998758313406086914794815409 1075 17246422939462333536659252558650386613682198540830437043888246526 1076 5810 1077 Y: 505836808606768081321267696834164575314792405646755177389264860926 1078 82650383803094471233632502605998926567195957732072433352975006488 1079 1824 1081 Encoded Public 1082 99 67 9B 7C 5E 1C 7E 51 CD 39 A2 41 83 62 73 3E 1083 60 93 17 A9 20 0E E3 BA 25 B3 B5 23 A3 A7 84 2E 1084 9D 67 6F D7 0B 33 02 1D EB 76 83 F8 77 D8 48 F8 1085 8B A3 72 E8 A9 6F 20 18 80 1087 5.2. Threshold Decryption 1089 5.2.1. Key Splitting X25519 1091 The encryption key pair is 1092 X25519KeyA (X25519) 1093 UDF: ZAAA-CTHD-X255-XXKE-YA 1094 Scalar: 36212799908425711450656372795692477094724455418915704 1095 216848228525958587810064 1096 Encoded Private 1097 10 01 D5 D1 E2 D3 DB 42 9E 40 5F D9 DB AE E8 09 1098 DE 43 C3 E6 D1 4F 3A 31 92 BF 19 8A E9 B7 0F 50 1099 U: 14523539712308371644546850739155588238080554014514563739095172 1100 886049239361031 1101 V: 56685060472089790044070522288405984326906734250304251487683593 1102 932889808473139 1103 Encoded Public 1104 07 66 84 48 25 85 F6 4A 3A EE DF B7 69 1B 57 51 1105 EC 18 BE AF 08 BA 0D FE BE F8 74 4E 3C 08 1C 20 1107 To create n key shares we first create n-1 key pairs in the normal 1108 fashion. Since these key pairs are only used for decryption 1109 operations, it is not necessary to calculate the public components: 1111 X25519Key1 (X25519) 1112 UDF: ZAAA-CTHD-X255-XXKE-YX 1113 Scalar: 32951726132685026729149224926255648061071804906258082 1114 061427666995947179849152 1115 Encoded Private 1116 C0 B5 33 D4 F3 D0 16 4F 96 DF C3 AD 97 93 02 EF 1117 B4 25 E2 46 A3 69 1D 22 9B 5B A2 78 1C 04 DA 48 1119 The secret scalar of the final key share is the secret scalar of the 1120 base key minus the sum of the secret scalars of the other shares 1121 modulo the group order: 1123 Scalar_2 = (Scalar_A - Scalar_1) mod L 1124 = 403147584512037825404691865456117698808221309075461782425833707 1125 7336679400315 1126 This is encoded as a binary integer in little endian format: 1128 7B 43 64 61 E9 28 4D 79 AB 9C 6E CC 9F 79 14 3D 1129 92 69 A5 2D 75 B9 57 53 2D 1B BC 02 06 BC E9 08 1131 5.2.2. Decryption X25519 1133 The means of encryption is unchanged. We begin by generating an 1134 ephemeral key pair: 1136 X25519KeyE (X25519) 1137 UDF: ZAAA-CTHD-X255-XXKE-YE 1138 Scalar: 41955577142906312619127105554814681129195921605852142 1139 704362465226652441661496 1140 Encoded Private 1141 38 50 3C 88 22 4F 61 D7 9A 2E 1D 71 F0 31 74 44 1142 A2 3B 2B 35 21 21 CA 19 4B 11 EB F0 DF 03 C2 5C 1143 U: 10080018124246254127076649374753145019412450363156572968151721 1144 892767560820008 1145 V: 43683938787921854603630290352714276342923724280578266457509078 1146 671566344321831 1147 Encoded Public 1148 28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28 1149 8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16 1151 The key agreement result is given by multiplying the public key of 1152 the encryption pair by the secret scalar of the ephemeral key to 1153 obtain the u-coordinate of the result. 1155 U: 247351751388894803426442650867524924086144759194834658830326105266 1156 22202018180 1158 The u-coordinate is encoded in the usual fashion (i.e. without 1159 specifying the sign of v). 1161 84 39 A5 21 13 F9 13 F0 7F F4 44 C0 DF 5D 44 DD 1162 DD F4 9B 87 4C DD E1 AB 64 00 8F A2 ED 9C AF 36 1164 The first decryption contribution is generated from the secret scalar 1165 of the first key share and the public key of the ephemeral. 1167 The outputs from the Montgomery Ladder are: 1169 x_2 57800249527850149046770413207257250301842844049677844025524059085 1170 132359257003 1171 z_2 37229326806761131733056994095424883574786241198535734197174081138 1172 402379671391 1173 x_3 30722194817314627970562030033494699359853137448471883846088158083 1174 361967945513 1175 z_3 29143359268139878301695995826542801325089258636824690596939399658 1176 126254126746 1178 The coordinates of the corresponding point are: 1180 u 2625200443692459084967263034650122583671912028244890150161521677645 1181 8728744244 1182 v 2340339249609928967870268630489687123941624857494487121340604194885 1183 7707717709 1185 The encoding of this point specifies the u coordinate and the sign 1186 (oddness) of the v coordinate: 1188 28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28 1189 8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16 1191 The second decryption contribution is generated from the secret 1192 scalar of the second key share and the public key of the ephemeral in 1193 the same way: 1195 u 2568180775076864300893967221119748767931055928591855851227298301978 1196 9028635830 1197 v 5237624535641756510077423429806596028526835148653096601777403098805 1198 4910628425 1200 28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28 1201 8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16 1203 To obtain the key agreement value, we add the two decryption 1204 contributions: 1206 u 5363809193902384353244842537457427150937755976201184630020143767288 1207 0976727749 1208 v 2576238777948215852102595446870010694371604288066653261024661407554 1209 3602367190 1211 This returns the same u coordinate value as before, allowing us to 1212 obtain the encoding of the key agreement value and decrypt the 1213 message. 1215 5.2.3. Key Splitting X448 1217 The encryption key pair is 1218 X448KeyA (X448) 1219 UDF: ZAAA-ETHD-X44X-KEYA 1220 Scalar: 70596789123829480733485730386174565339013185647363028 1221 6777277621057939099785091228353248522408450794128800398810019 1222 569879502484967206280 1223 Encoded Private 1224 88 2D AF 58 10 66 9E 1E F9 F2 C5 76 A2 00 86 F5 1225 B0 B9 C6 B9 E6 34 12 57 64 E3 63 B7 99 48 01 77 1226 9B A3 49 2D 7C B8 80 D7 63 44 6B C9 CB 83 F0 01 1227 B6 55 E0 92 1C 2A A6 F8 1228 U: 54256629638851994806054576189463839532492460394052748417730874 1229 4299533502601001906894660938607827805200569088593927035891085 1230 28218439174 1231 V: 12640494198304757803713993624351573936804262085795518571061045 1232 0631383333635306581037675004961525698205648857075020359124084 1233 524068583614 1234 Encoded Public 1235 06 FE 38 7A 1B 1E 99 D4 89 00 07 B9 88 6F 97 01 1236 BD 88 BB 9D A9 31 30 CC 47 E6 2F 9C 44 35 AF A4 1238 To create n key shares we first create n-1 key pairs in the normal 1239 fashion. Since these key pairs are only used for decryption 1240 operations, it is not necessary to calculate the public components: 1242 X448Key1 (X448) 1243 UDF: ZAAA-ETHD-X44X-KEYX 1244 Scalar: 63066265672668423343291438147840057172035337936373473 1245 3594300758463732521976388313294665447253881782852832499090049 1246 354258188417511652528 1247 Encoded Private 1248 B0 FC CE 55 87 AA A5 36 D2 5B E5 F2 5C 1B F7 9A 1249 5A 3D 97 D8 BB C0 81 84 98 3B 7C 29 C3 02 FC AE 1250 91 1B EA 67 68 C5 5E 87 7A ED 16 1F CB D0 20 9D 1251 C0 D6 62 BD 0F 35 20 DE 1253 The secret scalar of the final key share is the secret scalar of the 1254 base key minus the sum of the secret scalars of the other shares 1255 modulo the group order: 1257 Scalar_2 = (Scalar_A - Scalar_1) mod L 1258 = 646627804476669823064550215361382899916128546345584148789705309 1259 5564959403070244163454368262048594523846084193642728800427461 1260 1461310355 1261 This is encoded as a binary integer in little endian format: 1263 93 47 14 FF 94 BE F6 5C 77 63 44 89 DD CA 83 A6 1264 1A 79 82 CA 9E F6 6B 7D 98 23 59 77 60 4B FD 25 1265 2D BF 33 95 E4 7D DF 5E DE 31 82 E8 96 54 11 9F 1266 76 2C 43 50 2C 5F C6 16 1268 5.2.4. Decryption X448 1270 The means of encryption is unchanged. We begin by generating an 1271 ephemeral key pair: 1273 X448KeyE (X448) 1274 UDF: ZAAA-ETHD-X44X-KEYE 1275 Scalar: 40831502887772840901106715270468009328116701340228919 1276 4447950742749557088789408677311466089336893170031425082958041 1277 776608657845012501716 1278 Encoded Private 1279 D4 94 79 EE 56 3A 43 D5 FC EB 88 3E F0 63 EF 2F 1280 B0 92 B2 9D FD E1 43 8F 67 70 2A FC 2A AB A3 8B 1281 40 5A C6 D8 DE 8E B8 81 BF AD 17 BA 14 7F A4 B0 1282 D4 B1 9F CE D3 0D D0 8F 1283 U: 41902542857582644710501442087876846551351583947506685319975417 1284 2921931242764163121977613761818608927787788470856012050834001 1285 655292441835 1286 V: 40254626888669687592165362896510117701831215997629302922912638 1287 4107109948063151002535904960734463095918076287222011626898597 1288 213849340021 1289 Encoded Public 1290 EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C 1291 B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB 1293 The key agreement result is given by multiplying the public key of 1294 the encryption pair by the secret scalar of the ephemeral key to 1295 obtain the u-coordinate of the result. 1297 U: 414519841929159382730636919036875317796178034011999213235983537052 1298 30510678702415242441193107876747178183775523375063128358893667955 1299 0233 1301 The u-coordinate is encoded in the usual fashion (i.e. without 1302 specifying the sign of v). 1304 19 ED 3F 7A 63 6D AA 9A 3E 05 29 DE CC BA C7 F1 1305 E0 A7 FA C0 C4 70 E0 E1 A5 FC DA 0A B0 52 EC 8A 1307 The first decryption contribution is generated from the secret scalar 1308 of the first key share and the public key of the ephemeral. 1310 The outputs from the Montgomery Ladder are: 1312 x_2 60087238657789265874539701675840521614326868580285788286550399232 1313 20277081132468800878653228200859196207538481852097024468118288584 1314 83595 1315 z_2 12573140552649037921890899942919440571502561130496393232716617155 1316 24490660805576517881339517005970098784771472127066810694797758409 1317 67645 1318 x_3 40216911160845555507626938485596306260547743077930604703891475599 1319 53207238052152872831803734397389643529057507149471429452955111471 1320 57394 1321 z_3 48671808823760924633626118221453591105199403417491562559814414359 1322 34079336265430685974504655698846599309734305554546571306740770389 1323 79747 1325 The coordinates of the corresponding point are: 1327 u 5310627084956226133549480379012439149584638171147187426442235629260 1328 04186474991811830611467926523417739685244466041108245014409383321 1329 437 1330 v 6480384951984610654865132490606294355962228129695701220316681167173 1331 89634554460437237795204236689985354028508124817314496063921770833 1332 81 1334 The encoding of this point specifies the u coordinate and the sign 1335 (oddness) of the v coordinate: 1337 EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C 1338 B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB 1340 The second decryption contribution is generated from the secret 1341 scalar of the second key share and the public key of the ephemeral in 1342 the same way: 1344 u 2432029307606011854651950642127064534858415441240032460817128643691 1345 02601495764607628214871657677482439232238254450281582409532827123 1346 057 1347 v 3304237495909049135999182737314299324454426462198935317955136317282 1348 40167193898154033571033048069157608137872491595181800632292085611 1349 537 1351 EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C 1352 B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB 1354 To obtain the key agreement value, we add the two decryption 1355 contributions: 1357 u 2259776336573351712090323684006287979378142231675451855263136351631 1358 84627019682834233607456823018602790573389381890060345691088913511 1359 436 1360 v 3356804465434915738990773252496451168197759413718456519751139752920 1361 22788339143143140400339843420207702195408750068698590142923542805 1362 226 1364 This returns the same u coordinate value as before, allowing us to 1365 obtain the encoding of the key agreement value and decrypt the 1366 message. 1368 6. Security Considerations 1370 This section TBS 1372 One concern to be particularly careful of is that when adding two 1373 public keys, a rogue key attack is possible. The security of the 1374 private keys is the maximum of the two inputs but the trustworthiness 1375 of the public keys is the minimum. 1377 7. IANA Considerations 1379 This document requires no IANA actions (yet). 1381 It will be necessary to define additional code points for the signed 1382 version of the X25519 and X448 public key and the threshold 1383 decryption final private keys. 1385 8. Acknowledgements 1387 Rene Struik, Tony Arcieri, Scott Fluhrer, Scott Fluhrer, Dan Brown, 1388 Mike Hamburg 1390 9. Normative References 1392 [draft-ietf-lwig-curve-representations] 1393 Struik, R., "Alternative Elliptic Curve Representations", 1394 Work in Progress, Internet-Draft, draft-ietf-lwig-curve- 1395 representations-08, 24 July 2019, 1396 . 1399 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1400 Requirement Levels", BCP 14, RFC 2119, 1401 DOI 10.17487/RFC2119, March 1997, 1402 . 1404 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1405 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1406 2016, . 1408 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1409 Signature Algorithm (EdDSA)", RFC 8032, 1410 DOI 10.17487/RFC8032, January 2017, 1411 . 1413 10. Informative References 1415 [Costello17] 1416 Costello, C. and B. Smith, "Montgomery curves and their 1417 arithmetic", 2017. 1419 [draft-hallambaker-mesh-architecture] 1420 Hallam-Baker, P., "Mathematical Mesh 3.0 Part I: 1421 Architecture Guide", Work in Progress, Internet-Draft, 1422 draft-hallambaker-mesh-architecture-11, 23 October 2019, 1423 . 1426 [draft-hallambaker-mesh-developer] 1427 Hallam-Baker, P., "Mathematical Mesh: Reference 1428 Implementation", Work in Progress, Internet-Draft, draft- 1429 hallambaker-mesh-developer-09, 23 October 2019, 1430 . 1433 [Kocher96] Kocher, P. C., "Timing attacks on implementations of 1434 Diffie-Hellman, RSA, DSS, and other systems.", 1996. 1436 [Lopez99] L?opez, J. and R. Dahab, "Fast multiplication on elliptic 1437 curves over GF(2m) without precomputation.", 1999. 1439 [Okeya01] Okeya, K. and K. Sakurai, "Efficient elliptic curve 1440 cryptosystems from a scalar multiplication algorithm with 1441 recovery of the y-coordinate on a Montgomeryform elliptic 1442 curve.", 2001. 1444 [RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method", 1445 RFC 2631, DOI 10.17487/RFC2631, June 1999, 1446 .