Network Working Group P. M. Hallam-Baker
Internet-Draft ThresholdSecrets.com
Intended status: Informational September 4, 2020
Expires: March 8, 2021
Threshold Modes in Elliptic Curves
draft-hallambaker-threshold-03
Abstract
Threshold cryptography operation modes are described with application
to the Ed25519, Ed448, X25519 and X448 Elliptic Curves. Threshold
key generation allows generation of keypairs to be divided between
two or more parties with verifiable security guaranties. Threshold
decryption allows elliptic curve key agreement to be divided between
two or more parties such that all the parties must co-operate to
complete a private key agreement operation. The same primitives may
be applied to improve resistance to side channel attacks. A
Threshold signature scheme is described in a separate document.
https://mailarchive.ietf.org/arch/browse/cfrg/
(http://whatever)Discussion of this draft should take place on the
CFRG mailing list (cfrg@irtf.org), which is archived at .
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on March 8, 2021.
Copyright Notice
Copyright (c) 2020 IETF Trust and the persons identified as the
document authors. All rights reserved.
Hallam-Baker Expires March 8, 2021 [Page 1]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Applications . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1. Cloud control of decryption . . . . . . . . . . . . . 4
1.1.2. Device Onboarding . . . . . . . . . . . . . . . . . . 5
1.1.3. Cryptographic co-processor . . . . . . . . . . . . . 5
1.1.4. Side Channel Resistance . . . . . . . . . . . . . . . 6
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Requirements Language . . . . . . . . . . . . . . . . . . 6
2.2. Defined Terms . . . . . . . . . . . . . . . . . . . . . . 6
2.3. Related Specifications . . . . . . . . . . . . . . . . . 7
2.4. Implementation Status . . . . . . . . . . . . . . . . . . 7
3. Threshold Cryptography in Diffie-Hellman . . . . . . . . . . 8
3.1. Application to Diffie Hellman (not normative) . . . . . . 8
3.2. Threshold decryption . . . . . . . . . . . . . . . . . . 9
3.2.1. Direct Key Splitting . . . . . . . . . . . . . . . . 9
3.2.2. Direct Decryption . . . . . . . . . . . . . . . . . . 10
3.3. Direct threshold key generation . . . . . . . . . . . . . 10
3.3.1. Device Provisioning . . . . . . . . . . . . . . . . . 11
3.3.2. Key Rollover . . . . . . . . . . . . . . . . . . . . 12
3.3.3. Host Activation . . . . . . . . . . . . . . . . . . . 13
3.3.4. Separation of Duties . . . . . . . . . . . . . . . . 13
3.4. Side Channel Resistance . . . . . . . . . . . . . . . . . 13
4. Shamir Secret Sharing . . . . . . . . . . . . . . . . . . . . 14
4.1. Shamir secret share generation . . . . . . . . . . . . . 14
4.2. Lagrange basis recovery . . . . . . . . . . . . . . . . . 15
4.3. Verifiable Secret Sharing . . . . . . . . . . . . . . . . 15
4.4. Distributed Key Generation . . . . . . . . . . . . . . . 16
5. Application to Elliptic Curves . . . . . . . . . . . . . . . 16
5.1. Implementation for Ed25519 and Ed448 . . . . . . . . . . 16
5.1.1. Ed25519 . . . . . . . . . . . . . . . . . . . . . . . 17
5.1.2. Ed448 . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2. Implementation for X25519 and X448 . . . . . . . . . . . 18
5.2.1. Point Encoding . . . . . . . . . . . . . . . . . . . 18
5.2.2. X25519 Point Encoding . . . . . . . . . . . . . . . . 19
5.2.3. X448 Point Encoding . . . . . . . . . . . . . . . . . 19
5.2.4. Point Addition . . . . . . . . . . . . . . . . . . . 19
5.2.5. Montgomery Ladder with Coordinate Recovery . . . . . 20
6. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 22
6.1. Threshold Key Generation . . . . . . . . . . . . . . . . 22
6.1.1. X25519 . . . . . . . . . . . . . . . . . . . . . . . 22
Hallam-Baker Expires March 8, 2021 [Page 2]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
6.1.2. X448 . . . . . . . . . . . . . . . . . . . . . . . . 24
6.1.3. Ed25519 . . . . . . . . . . . . . . . . . . . . . . . 26
6.1.4. Ed448 . . . . . . . . . . . . . . . . . . . . . . . . 27
6.2. Threshold Decryption . . . . . . . . . . . . . . . . . . 29
6.2.1. Direct Key Splitting X25519 . . . . . . . . . . . . . 29
6.2.2. Direct Decryption X25519 . . . . . . . . . . . . . . 30
6.2.3. Direct Key Splitting X448 . . . . . . . . . . . . . . 32
6.2.4. Direct Decryption X448 . . . . . . . . . . . . . . . 34
6.2.5. Shamir Secret Sharing X448 . . . . . . . . . . . . . 36
6.2.6. Lagrange Decryption X448 . . . . . . . . . . . . . . 36
7. Security Considerations . . . . . . . . . . . . . . . . . . . 36
7.1. Complacency Risk . . . . . . . . . . . . . . . . . . . . 36
7.2. Rogue Key Attack . . . . . . . . . . . . . . . . . . . . 37
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 37
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 38
10. Appendix A: Calculating Lagrange coefficients . . . . . . . . 38
11. Normative References . . . . . . . . . . . . . . . . . . . . 38
12. Informative References . . . . . . . . . . . . . . . . . . . 38
1. Introduction
Public key cryptography provides greater functionality than symmetric
key cryptography by introducing separate keys for separate roles.
Knowledge of the public encryption key does not provide the ability
to decrypt. Knowledge of the public signature verification key does
not provide the ability to sign. Threshold cryptography extends the
scope of traditional public key cryptography with further separation
of roles by splitting the private key. This allows greater control
of (e.g.) decryption operations by requiring the use of two
decryption key shares rather than just the decryption key.
This document describes threshold modes for decryption and key
generation for the elliptic curves described in [RFC7748] and
[RFC8032]. Both schemes are interchangeable in their own right but
require minor modifications to the underlying elliptic curve systems
to encode the necessary information in the public (X25519/X448) or
private key (Ed25519/Ed448). The companion document
[draft-hallambaker-threshold-sigs] describes a threshold mode for
[RFC8032] signatures.
In its most general form, threshold cryptography allows a private key
to be divided between (_n_, _t_) shares such that _n_ is the total
number of shares created and _t_ is the threshold number of shares
required to perform the operation. For most applications however,
the number of shares is the same as the threshold (_n_ = _t_) and the
most common case is (_n_ = _t_ = 2).
Hallam-Baker Expires March 8, 2021 [Page 3]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
This document sets out the principles that support the definition
threshold modes in elliptic curve Diffie Hellman system first using
simple additive key sharing, an approach which is limited to the case
(_n_ = _t_). The use of Shamir secret sharing [Shamir79] is then
described to support the case (_n_ > _t_). For convenience, we refer
to the non Shamir secret sharing case as 'direct key sharing'.
1.1. Applications
Development of the threshold modes described in this document and the
companion document [draft-hallambaker-threshold-sigs] were motivated
by the following applications.
1.1.1. Cloud control of decryption
The security of data at rest is of increasing concern in enterprises
and for individual users. Transport layer security such as TLS and
SSH provide effective confidentiality controls for data in motion but
not for data at rest.
Of particular concern is the case in which a large store of
confidential data is held on a server. Encryption provides a simple
and effective means of protecting the confidentiality of such data.
But the real challenge is how to effect decryption of the data on
demand for the parties authorized to access it.
Storing the decryption keys on the server that holds the data
provides no real security advantage as any compromise that affects
the server is likely to result in disclosure of the keys. Use of
end-to-end security in which each document is encrypted under the
public key of each person authorized to access it provides the
desired security but introduces a complex key management problem and
provides no effective means of revoking access after it is granted.
Threshold encryption allows a key service to control decryption of
stored data without having the ability to decrypt. The data
decryption key is split into two (or more) parts with a different
split being created for each user. One decryption share is held at
the server allowing it to control access to the data without being
able to decrypt. The other decryption share is encrypted under the
public encryption key of the corresponding user allowing them to
decrypt the stored data but only with the co-operation of the key
service.
Hallam-Baker Expires March 8, 2021 [Page 4]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
1.1.2. Device Onboarding
The term 'onboarding' is used to refer to the configuration of a
device for use by a particular user or within a particular
enterprise. One of the typical concerns of onboarding is to
initialize the device with a set of public key pairs for various
purposes and to issue credentials (e.g. PKIX certificates) to enable
their use.
One of the concerns that arises in such cases is whether keys should
be generated on the device on which they are to be used or on another
device administering the onboarding process.
Both approaches are unsatisfactory. While generation of keys on the
device on which they are to be used is generally preferred,
experience has shown that many devices, particularly IoT devices use
insufficiently random processes to generate such keys and this has
led to numerous cases of duplicate and otherwise weak keys being
discovered in running systems.
Generation of keys on an administration device and transferring them
to the device on which they are to be used means that the
administration device used for key generation represents a single
point of failure. Compromise of this device or of the means used to
install the keys will lead to compromise of the device.
Threshold key generation allows the advantages of both approaches to
be realized avoiding dependence on either the target device or the
administration device.
1.1.3. Cryptographic co-processor
Most real-world compromises of cryptographic security systems involve
the disclosure of a private key. Common means of disclosure being
inadvertent inclusion in backup tapes, keys being stored on public
file shares and (increasingly) keys being inadvertently uploaded to
source code management systems.
A new and emerging set of key disclosure threats come from the recent
generation of hardware vulnerabilities being discovered in CPUs
including ROWHAMMER and SPECTRE.
The advantages of Hardware Security Modules (HSMs) for storing and
using private keys are well established. An HSM allows a private key
to be used in an isolated environment that is designed to be
resistant to side channel attacks.
Hallam-Baker Expires March 8, 2021 [Page 5]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Regrettably, the 'black box' nature of HSMs means that their use
introduces a new security concern - the possibility that the device
itself has been compromised during manufacture or in the supply
chain.
Threshold approaches allows a key exchange or signature operation to
be divided between two private keys, one of which is generated by the
application that is to use it and the other of which is tightly bound
to a specific host such that it cannot be extracted.
1.1.4. Side Channel Resistance
The same techniques that make threshold cryptography possible are the
basis for Kocher's side-channel resistance technique [Kocher96].
Differential side channel attacks are a powerful tool capable of
revealing a private key value that is used repeatedly in practically
any algorithm. The claims made with respect to 'constant time'
algorithms such as the Montgomery ladder depend upon the actual
implementation performing operations in constant time.
2. Definitions
This section presents the related specifications and standard, the
terms that are used as terms of art within the documents and the
terms used as requirements language.
2.1. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
2.2. Defined Terms
The following terms are used as terms of art in this document and the
accompanying specification [draft-hallambaker-threshold-sigs].
Dealer A party that coordinates the actions of a group of
participants performing a threshold operation.
Multi-Encryption The use of multiple decryption fields to allow a
document encrypted under a session key to be decrypted by multiple
parties under different decryption keys.
Multi-Encryption allows a document to be shared with multiple
recipients but does not allow the decryption role to be divided
between multiple parties.
Hallam-Baker Expires March 8, 2021 [Page 6]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Multi-Signatures The use of multiple independently verifiable
digital signatures to authenticate a document.
Multi-Signatures allow separation of the signing roles and thus
achieve a threshold capability. But they are not true threshold
signatures as the set of signers is visible to external parties.
Onboarding The process by which an embedded device is provisioned
for deployment in a local network.
Threshold Key Generation An aggregate public, private key pair is
constructed from a set of contributions such that the private key
is a function of the private key of all the contributions.
A Threshold Key Generation function is auditable if and only if
the public component of the aggregate key can be computed from the
public keys of the contributions alone.
Threshold Decryption Threshold decryption divides the decryption
role between two or more parties.
Threshold Key Agreement A bilateral key agreement exchange in which
one or both sides present multiple public keys and the key
agreement value is a function of all of them.
This approach allows a party to present multiple credentials in a
single exchange, a de
Threshold Signatures Threshold signatures divide the signature role
between two or more parties in such a way that the parties and
their roles is not visible to an external observer.
2.3. Related Specifications
This document extends the elliptic curve cryptography systems
described in [RFC7748] and [RFC8032] to provide threshold
capabilities.
This work was originally motivated by the requirements of the
Mathematical Mesh [draft-hallambaker-mesh-architecture].
Threshold modes for generating signatures compatible with [RFC8032]
are described in [draft-hallambaker-threshold-sigs].
2.4. Implementation Status
The implementation status of the reference code base is described in
the companion document [draft-hallambaker-mesh-developer].
Hallam-Baker Expires March 8, 2021 [Page 7]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
3. Threshold Cryptography in Diffie-Hellman
The threshold modes described in this specification are made possible
by the fact that Diffie Hellman key agreement and elliptic curve
variants thereof support properties we call the Key Combination Law
and the Result Combination Law.
Let {_X_, _x_}, {_Y_, _y_}, {_A_, _a_} be {public, private} key pairs
and r [.] S represent the Diffie Hellman operation applying the
private key r to the public key S.
The Key Combination law states that we can define an operator [x]
such that there is a keypair {_Z_, _z_} such that:
_Z_ = _X_ [x] _Y_ and _z_ = (_x_ + _y_) mod _o_ (where _o_ is the
order of the group)
The Result Combination Law states that we can define an operator [+]
such that:
(_x_ [.] _A_) [+] (_y_ [.] _A_) = (_z_ [.] _A_) = (_a_ [.] _Z_)
It will be noted that each of these laws is interchangeable. The
output of the key combination law to a Diffie Hellman key pair is a
Diffie Hellman key pair and the output of the result combination law
is a Diffie Hellman result. This allows modular and recursive
application of these principles.
3.1. Application to Diffie Hellman (not normative)
Diffie Hellman in a modular field provides a concise demonstration of
the key combination and result combination laws [RFC2631]. The
realization of the threshold schemes in a modular field is outside
the scope of this document.
For the Diffie Hellman system in a modular field p, with exponent e:
* r [.] S = S^(r) mod p
* o = p-1
* _A_[x] _B_ = _A_[.] _B_ = _AB_mod _p_.
_Proof:_
Let z = x + y
By definition, X = e^(x) mod p, Y = e^(y) mod p, and Z = e^(z)mod p.
Hallam-Baker Expires March 8, 2021 [Page 8]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Therefore,
Z = e^(z) mod p = e^(x+y) mod p
= (e^(x)e^(y)) mod p
= e^(x)mod p.e^(y) mod p
= X.Y
Moreover, A = e^(a) mod p,
Therefore,
(A^(x) mod p).(A^(y) mod p) = (A^(x)A^(y)) mod p)
= (A^(x+y)) mod p)
= A^(z) mod p
= e^(az) mod p
= (e^(z))^(a) mod p
= Z^(a) mod p
Since e^(o) mod p = 1, the same result holds for z = (x + y) mod o
since e^(x+y+no) = e^(x+y).e^(no) = e^(x+y).1 = e^(x+y).
3.2. Threshold decryption
Threshold decryption allows a decryption key to be divided into two
or more parts, allowing these roles to be assigned to different
parties. This capability can be employed within a machine to divide
use of a private key between an implementation running in the user
mode and a process running in a privileged mode that is bound to the
machine. Alternatively, threshold cryptography can be employed to
The key combination law and result combination law provide a basis
for threshold decryption.
3.2.1. Direct Key Splitting
We begin by creating a base key pair { X, x }. The public component X
is used to perform encryption operations by means of a key agreement
against an ephemeral key in the usual fashion. The private component
x may be used for decryption in the normal fashion or to provide the
source material for a key splitting operation.
Hallam-Baker Expires March 8, 2021 [Page 9]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
To split the base key into n shares { S_(1), s_(1) }, { S_(2), s_(2)
}, ... { S_(n), s_(n) }, we begin by generating the first n-1 private
keys in the normal fashion. It is not necessary to generate the
corresponding public keys as these are not required.
The private key of the final key share s_(n) is given by:
_s_(n) = (x - s1 - s2 - ... - sn-1) mod o_
Thus, the base private key x is equal to the sum of the private key
shares modulo the group order.
3.2.2. Direct Decryption
To encrypt a document, we first generate an ephemeral key pair { Y, y
}. The key agreement value e^(xy) is calculated from the base public
key X = e^(x) and the ephemeral private key y. A key derivation
function is then used to obtain the session key to be used to encrypt
the document under a symmetric cipher.
To decrypt a document using the threshold key shares, each key share
holder first performs a Diffie Hellman operation using their private
key on the ephemeral public key. The key shares are then combined
using the result combination law to obtain the key exchange value
from which the session key is recovered.
The key contribution c_(i) for the holder of the i^(th) key share is
calculated as:
c_(i) = Y^(si)
The key agreement value is thus
A = c_(1) . c_(2) . ... . c_(n)
This value is equal to the encryption key agreement value according
to the group law.
3.3. Direct threshold key generation
The key combination law allows an aggregate private key to be derived
from private key contributions provided by two or more parties such
that the corresponding aggregate public key may be derived from the
public keys corresponding to the contributions. The resulting key
generation mechanism is thus, auditable and interoperable.
Hallam-Baker Expires March 8, 2021 [Page 10]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
3.3.1. Device Provisioning
Auditable Threshold Key Generation provides a simple and efficient
means of securely provisioning keys to devices. This is encountered
in the IoT space as a concern in 'onboarding' and in the provisioning
of unique keys for use with cryptographic applications (e.g. SSH, S/
MIME, OpenPGP, etc.).
Consider the case in which Alice purchases an IoT connected Device D
which requires a unique device key pair _{ X , x }_ for its
operation. The process of provisioning (aka 'onboarding') is
performed using an administration device. Traditional key pair
generation gives us three options:
* Generate and install a key pair during manufacture.
* Generate a new key pair during device provisioning.
* Generate a key pair on the administration device and transfer it
to the device being provisioned.
The first approach has the obvious disadvantage that the manufacturer
has knowledge of the private key. This represents a liability for
both the user and the manufacturer. Less obvious is the fact that
the second approach doesn't actually provide a solution unless the
process of generating keys on the device is auditable. The third
approach is auditable with respect to the device being provisioned
but not with respect to the administration device being used for
provisioning. If that device were to be compromised, so could every
device it was used to provision.
Threshold key generation allows the administration device and the
joining device being provisioned to jointly provision a key pair as
follows:
* The joining device has public, private key pair_{ D, d }_.
* A provisioning request is made for the device which includes the
joining device public key _D_.
* The administration device generates a key pair contribution _{ A,
a }_.
* The administration device private key is transmitted to the Device
by means of a secure channel.
* The joining device calculates the aggregate key pair _{ A [x] D,
a+d }_.
Hallam-Baker Expires March 8, 2021 [Page 11]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
* The administration device authorizes the joining device to
participate in the local network using the public key _A [x] D_.
The Device key pair MAY be installed during manufacture or generated
during provisioning or be derived from a combination of both using
threshold key generation recursively. The provisioning request MAY
be originated by the device or be generated by a purchasing system.
Note that the provisioning protocol does not require either party to
authenticate the aggregate key pair. The protocol provides security
by ensuring that both parties obtain the correct results if and only
if the values each communicated to the other were correct.
Out of band authentication of the joining device public key _D_ is
sufficient to prevent Man-in-the-Middle attack. This may be achieved
by means of a QR code printed on the device itself that discloses or
provides a means of obtaining _D._
[Note add serious warning that a party providing a private
contribution MUST make sure they see the public key first. Otherwise
a rogue key attack is possible. The Mesh protocols ensure that this
is the case but other implementations may overlook this detail.]
3.3.2. Key Rollover
Traditional key rollover protocols in PKIX and other PKIs following
the Kohnfelder model, require a multi-step interaction between the
key holder and the Certificate Authority.
Threshold key generation allows a Certificate Authority to implement
key rollover with a single communication:
Consider the case in which the service host has a base key pair { B ,
b }. A CA that has knowledge of the Host public key B may generate a
certificate for the time period _t_ with a fresh key as follows:
* Generate a key pair contribution { A_(t), a_(t) }.
* Generate and sign an end entity certificate C_(t) for the key B
[x] A_(t).
* Transmit C_(t), a_(t) to the host by means of a secure channel
Hallam-Baker Expires March 8, 2021 [Page 12]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
3.3.3. Host Activation
Modern Internet service architectures frequently make use of short
lived, ephemeral hosts running on virtualized machines. Provisioning
cryptographic material in such environments is a significant
challenge and especially so when the underlying hardware is a shared
resource.
The key rollover approach described above provides a means of
provisioning short lived credentials to ephemeral hosts that
potentially avoids the need to build sensitive keys into the service
image or configuration.
3.3.4. Separation of Duties
Threshold key generation provides a means of separating
administration of cryptographic keys between individuals. This
allows two or more administrators to control access to a private key
without having the ability to use it themselves. This approach is of
particular utility when used in combination with threshold
decryption. Alice and Bob can be granted the ability to create key
contributions allowing a user to decrypt information without having
the ability to decrypt themselves.
3.4. Side Channel Resistance
Side-channel attacks, present a major concern in the implementation
of public key cryptosystems. Of particular concern are the timing
attacks identified by Paul Kocher [Kocher96] and related attacks in
the power and emissions ranges. Performing repeated observations of
the use of the same private key material provides an attacker with
considerably greater opportunity to extract the private key material.
A simple but effective means of defeating such attacks is to split
the private key value into two or more random shares for every
private key operation and use the result combination law to recover
the result.
The implementation of this approach is identical to that for
Threshold Decryption except that instead of giving the key shares to
different parties, they are kept by the party performing the private
key operation.
While this approach doubles the number of private key operations
required, the operations MAY be performed in parallel. Thus avoiding
impact on the user experience.
Hallam-Baker Expires March 8, 2021 [Page 13]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
4. Shamir Secret Sharing
The direct threshold modes described above may be extended to support
the case (_n_ > _t_) through application of Shamir secret sharing and
the use of the Lagrange basis to recover the secret value.
Shamir Secret Sharing makes use of the fact that a polynomial of
degree t-1 is defined by t points on the curve. To share a secret
_s_, we construct a polynomial of degree _t-1_ in the modular field
_L_ where _L_ > _s_.
_f_(_x_) = _s_ + _a_(1)_._x_ + _a_(2)_._x^(2)_ + ...
_a_(t-1)_._x^(t-1)_ mod _L_
The shares _p_(1)_, _p_(2)_ ... _p_(n)_ are given by the values
_f_(_x_(1)_), _f_(_x_(2)_), ... ,_f_(_x_(n)_) where _x_(1)_, _x_(2)_
... _x_(n)_ are in the range 1 _x_(i)_ _L_.
We can use the Lagrange basis function to construct a set of
coefficients l_(1), l_(2), ... l_(t) from a set of _t_ shares p_(1),
p_(2) ... p_(t) such that:
_s_ = l_(1)p_(1) + l_(2)p_(2) + ... + l_(t)p_(t) mod _L_
Thus, if we choose the sub-group order of the curve as the value of
_L_, the formula used to recover the secret _s_ is a sum of terms as
was used for the case where _n_ = _t_. We can thus apply a set of
Lagrange coefficients provided by the dealer to the secret shares to
extend the threshold operations to the case where _n_ > _t_.
4.1. Shamir secret share generation
To create _n_ shares for the secret _s_ with a threshold of _t_, the
dealer constructs a polynomial of degree _t_ in the modular field
_L_, where _L_ is the order of the curve sub-group:
f(x) = a_(0) + a_(1).x + a_(2).x^(2) + ... a_(t).x^(t-1) mod L
where a_(0) = s
a_(1) ... a_(t) are randomly chosen integers in the range 1 a_(i)
L
The values of the key shares are the values _f_(x_(1)), _f_(x_(2)),
... ,_f_(x_(n)). That is
p_(i) = _f_(x_(i))
Hallam-Baker Expires March 8, 2021 [Page 14]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
where p_(1) ... p_(n) are the private key shares
x_(1) ... x_(n) are distinct integers in the range 1 x_(i) L
The means of constructing distinct values x_(1) ... x_(n) is left to
the implementation. It is not necessary for these values to be
secret.
4.2. Lagrange basis recovery
Given _n_ shares (_x_(0)_, _y_(0)_), (_x_(1)_, _y_(1)_), ...
(_x_(n-1)_, _y_(n-1)_), The corresponding the Lagrange basis
polynomials _l_(0)_, _l_(1)_, .. _l_(n-1)_ are given by:
l_(m) = ((_x_ - _x_(m0)_) / (_x_(m)_ - x__(m0)_)) . ((_x_ - _x_(m1)_)
/ (_x_(m)_ - x__(m1)_)) . ... . ((_x_ - _x_(mn-2)_) / (_x_(m)_ -
_x_(mn-)_2))
Where the values _m_(0)_, _m_(1)_, ... _m_(n-2)_, are the integers 0,
1, .. _n_-1, excluding the value _m_.
These can be used to compute _f(x)_ as follows:
_f_(_x_) = _y_(0)l0 + y1l1 + ... yn-1ln-1_
Since it is only the value of _f(_0_)_ that we are interested in, we
compute the Lagrange basis for the value _x_ = 0:
_lz_(m)_ = ((_x_(m1)_) / (_x__(m) - _x_(m1)_)) . ((_x_(m2)_) /
(_x_(m)_ - _x_(m2)_))
Hence,
_a_(0)_ = _f_(_0_) = _y_(0)lz0 + y1lz1 + ... yn-1ln-1_
4.3. Verifiable Secret Sharing
The secret share generation mechanism described above allows a
private key to be split into _n_ shares such that _t_ shares are
required for recovery. While this supports a wide variety of
applications, there are many cases in which it is desirable for
generation of the private key to be distributed.
Feldman's Verifiable Secret Sharing (VSS) Scheme provides a mechanism
that allows the participants in a distributed generation scheme to
determine that their share has been correctly formed by means of a
commitment.
Hallam-Baker Expires March 8, 2021 [Page 15]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
To generate a commitment the dealer generates the polynomial _f_(_x_)
as before and in addition selects a generator _g_
[TBS]
4.4. Distributed Key Generation
[TBS]
5. Application to Elliptic Curves
For elliptic curve cryptosystems, the operators [x] and [.] are point
addition.
Implementing a robust Key Co-Generation for the Elliptic Curve
Cryptography schemes described in [RFC7748] and [RFC8032] requires
some additional considerations to be addressed.
* The secret scalar used in the EdDSA algorithm is calculated from
the private key using a digest function. It is therefore
necessary to specify the Key Co-Generation mechanism by reference
to operations on the secret scalar values rather than operations
on the private keys.
* The Montgomery Ladder traditionally used to perform X25519 and
X448 point multiplication does not require implementation of a
function to add two arbitrary points. While the steps required to
create such a function are fully constrained by [RFC7748], the
means of performing point addition is not.
5.1. Implementation for Ed25519 and Ed448
[RFC8032] provides all the cryptographic operations required to
perform threshold operations and corresponding public keys.
The secret scalars used in [RFC8032] private key operations are
derived from a private key value using a cryptographic digest
function. This encoding allows the inputs to a private key
combination to be described but not the output. Contrawise, the
encoding allows the inputs to a private key splitting operation to be
described but not the output
It is therefore necessary to provide an alternative representation
for the Ed25519 and Ed448 private keys. Moreover, the signature
algorithm requires both a secret scalar and a prefix value as inputs.
Hallam-Baker Expires March 8, 2021 [Page 16]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Since threshold signatures are out of scope for this document and
[RFC8032] does not specify a key agreement mechanism, it suffices to
specify the data formats required to encode private key values
generated by means of threshold key generation.
5.1.1. Ed25519
Let the inputs to the threshold key generation scheme be a set of 32
byte private key values _P_(1), P2 ... Pn. For each private key
value i in turn:_
0. Hash the 32-byte private key using SHA-512, storing the digest in
a 64-octet large buffer, denoted_h_(i)_. Let n_(i) be the first
32 octets of h_(i) and m_(i) be the remaining 32 octets of h_(i).
1. Prune n_(i): The lowest three bits of the first octet are
cleared, the highest bit of the last octet is cleared, and the
second highest bit of the last octet is set.
2. Interpret the buffer as the little-endian integer, forming a
secret scalar s_(i).
The private key values are calculated as follows:
The aggregate secret scalar value _s_(a) = s1 + s2 + ... sn mod L,
where L is the order of the curve._
The aggregate prefix value is calculated by either
* Some function TBS on the values m_(1), m_(2), ... m_(n), or
* Taking the SHA256 digest of s_(a).
The second approach is the simplest and the most robust. It does
however mean that the prefix is a function of the secret scalar
rather than both being functions of the same seed.
5.1.2. Ed448
Let the inputs to the threshold key generation scheme be a set of 57
byte private key values _P_(1), P2 ... Pn. For each private key
value i in turn:_
0. Hash the 57-byte private key using SHAKE256(x, 114), storing the
digest in a 114-octet large buffer, denoted_h_(i)_. Let n_(i) be
the first 57 octets of h_(i) and m_(i) be the remaining 57 octets
of h_(i).
Hallam-Baker Expires March 8, 2021 [Page 17]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
1. Prune n_(i): The two least significant bits of the first octet
are cleared, all eight bits the last octet are cleared, and the
highest bit of the second to last octet is set.
2. Interpret the buffer as the little-endian integer, forming a
secret scalar s_(i).
The private key values are calculated as follows:
The aggregate secret scalar value _s_(a) = s1 + s2 + ... sn mod L,
where L is the order of the curve._
The aggregate prefix value is calculated by either
* Some function TBS on the values m_(1), m_(2), ... m_(n), or
* Taking the SHAKE256(x, 57) digest of s_(a).
The second approach is the simplest and the most robust. It does
however mean that the prefix is a function of the secret scalar
rather than both being functions of the same seed.
5.2. Implementation for X25519 and X448
[RFC7748] defines all the cryptographic operations required to
perform threshold key generation and threshold decryption but does
not describe how to implement them.
The Montgomery curve described in [RFC7748] allows for efficient
scalar multiplication using arithmetic operations on a single
coordinate. Point addition requires both coordinate values. It is
thus necessary to provide an extended representation for point
encoding and provide an algorithm for recovering both coordinates
from a scalar multiplication operation and an algorithm for point
addition.
The notation of [RFC7748] is followed using {u, v} to represent the
coordinates on the Montgomery curve and {x, y} for coordinates on the
corresponding Edwards curve.
5.2.1. Point Encoding
The relationship between the u and v coordinates is specified by the
Montgomery Curve formula itself:
_v^(2)_ = _u^(3) + Au2 + u_
Hallam-Baker Expires March 8, 2021 [Page 18]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
An algorithm for extracting a square root of a number in a finite
field is specified in . [RFC8032]
Since _v^(2)_ has a positive (_v_) and a negative solution (_-v_), it
follows that _v^(2)_ mod p will have the solutions _v_, _p-v_.
Furthermore, since _p_ is odd, if _v_ is odd, _p-v_ must be even and
vice versa. It is thus sufficient to record whether _v_ is odd or
even to enable recovery of the _v_ coordinate from _u_.
5.2.2. X25519 Point Encoding
The extended point encoding allowing the v coordinate to be recovered
is as given in [draft-ietf-lwig-curve-representations]
A curve point (u, v), with coordinates in the range 0 = u,v p, is
coded as follows. First, encode the u-coordinate as a little-endian
string of 57 octets. The final octet is always zero. To form the
encoding of the point, copy the least significant bit of the
v-coordinate to the most significant bit of the final octet.
5.2.3. X448 Point Encoding
The extended point encoding allowing the v coordinate to be recovered
is as given in [draft-ietf-lwig-curve-representations]
A curve point (u, v), with coordinates in the range 0 = u,v p, is
coded as follows. First, encode the u-coordinate as a little-endian
string of 57 octets. The final octet is always zero. To form the
encoding of the point, copy the least significant bit of the
v-coordinate to the most significant bit of the final octet.
5.2.4. Point Addition
The point addition formula for the Montgomery curve is defined as
follows:
Let P_(1) = {u_(1), v_(1)}, P_(2) = {u_(2), v_(2)}, P_(3) = {u_(3),
v_(3)} = P_(1) + P_(2)
By definition:
u_(3) = B(v_(2) - v_(1))^(2) / (u_(2) - u_(1))^(2) - A - u_(1) -
u_(2)
= B((u_(2)v_(1) - u_(1)v_(2))^(2) ) / u_(1)u_(2) (u_(2) -
u_(1))^(2)
Hallam-Baker Expires March 8, 2021 [Page 19]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
v_(3) = ((2u_(1) + u_(2) + A)(v_(2) - v_(1)) / (u_(2) - u_(1))) - B
(v_(2) - v_(1))^(3) / (u_(2) -u_(1))^(3) - v_(1)
For curves X25519 and X448, B = 1 and so:
u_(3) = ((v_(2) - v_(1)).(u_(2) - u_(1))^(-1))^(2) - A - u_(1) -
u_(2)
v_(3) = ((2u_(1) + u_(2) + A)(v_(2) - v_(1)).(u_(2) - u_(1))^(-1)) -
((v_(2) - v_(1)).(u_(2) -u_(1))^(-1))^(3) - v_(1)
This may be implemented using the following code:
B = v2 - v1
C = u2 - u1
CINV = C^(p - 2)
D = B * CINV
DD = D * D
DDD = DD * D
u3 = DD - A - u1 - u2
v3 = ((u1 + u1 + u2 + A) * B * CINV) - DDD - v1
Performing point addition thus requires that we have sufficient
knowledge of the values v_(1), v_(2). At minimum whether one is odd
and the other even or if both are the same.
5.2.5. Montgomery Ladder with Coordinate Recovery
As originally described, the Montgomery Ladder only provides the u
coordinate as output. L?pez and Dahab [Lopez99] provided a formula
for recovery of the v coordinate of the result for curves over binary
fields. This result was then extended by Okeya and Sakurai [Okeya01]
to prime field Montgomery curves such as X25519 and X448. The
realization of this result described by Costello and Smith
[Costello17] is applied here.
The scalar multiplication function specified in [RFC7748] takes as
input the scalar value k and the coordinate u_(1) of the point P_(1)
= {u_(1), v_(1)} to be multiplied. The return value in this case is
u_(2) where P_(2) = {u_(2), v_(2)} = k.P_(1).
To recover the coordinate v_(2) we require the values x_2, z_2, x_3,
z_3 calculated in the penultimate step:
Hallam-Baker Expires March 8, 2021 [Page 20]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
x_1 = u
x_2 = 1
z_2 = 0
x_3 = u
z_3 = 1
swap = 0
For t = bits-1 down to 0:
k_t = (k >> t) & 1
swap ^= k_t
// Conditional swap as specified in RFC 7748
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
swap = k_t
A = x_2 + z_2
AA = A^2
B = x_2 - z_2
BB = B^2
E = AA - BB
C = x_3 + z_3
D = x_3 - z_3
DA = D * A
CB = C * B
x_3 = (DA + CB)^2
z_3 = x_1 * (DA - CB)^2
x_2 = AA * BB
z_2 = E * (AA + a24 * E)
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
Return x_2, z_2, x_3, z_3
The values x_2, z_2 give the projective form of the u coordinate of
the point P_(2) = {u_(2), v_(2)} = k.P_(1) and the values x_3, z_3
give the projective form of the u coordinate of the point P_(3) =
{u_(3), v_(3)} = (k+1).P_(1) = P_(1) + k.P_(1) = P_(1) + P_(2).
Given the coordinates {u_(1), v_(1)} of the point P1 and the u
coordinates of the points P_(2), P_(1) + P_(2), the coordinate v_(2)
MAY be recovered by trial and error as follows:
v_test = SQRT (u3 + Au2 + u)
u_test = ADD_X (u, v, u_2, v_test)
if (u_test == u_3)
return u_test
else
return u_test +p
Hallam-Baker Expires March 8, 2021 [Page 21]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Alternatively, the following MAY be used to recover {u_(2), v_(2)}
without the need to extract the square root and using a single
modular exponentiation operation to convert from the projective
coordinates used in the calculation. As with the Montgomery ladder
algorithm above, the expression has been modified to be consistent
with the approach used in [RFC7748] but any correct formula may be
used.
x_p = u
y_p = v
B = x_p * z_2 //v1
C = x_2 + B //v2
D = X_2 - B //v3
DD = D^2 //v3
E = DD. X_3 //v3
F = 2 * A * z_2 //v1
G = C + F //v2
H = x_p * x_2 //v4
I = H + z_2 //v4
J = G * I //v2
K = F * z_2 //v1
L = J - K //v2
M = L * z_3 //v2
yy_2 = M - E //Y'
N = 2 * y_p //v1
O = N * z_2 //v1
P = O * z_3 //v1
xx_2 = P * x_q //X'
zz_2 = P * z_ q //Z'
ZINV = (zz_2^(p - 2))
u2 = xx_2 * ZINV
v2 = yy_2 * ZINV
return u2, v2
6. Test Vectors
6.1. Threshold Key Generation
6.1.1. X25519
The key parameters of the first key contribution are:
Hallam-Baker Expires March 8, 2021 [Page 22]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
X25519Key1 (X25519)
UDF: ZAAA-CTKG-X255-XXKE-YX
Scalar: 56751742936444772792970879017152360515706108153669948
486190735258502824077920
Encoded Private
60 2A E2 12 AC 8E C8 86 A1 79 51 7E 79 90 5E C2
9B AD 10 01 B9 2D 51 33 65 DB F4 9E 23 59 78 7D
U: 25222393324990721517739552691612440154338285166262054281502859
684220669343438
V: 15622452724514925334849257786951944861130311422605147559630230
860481236780294
Encoded Public
CE 36 B9 F1 56 BD 92 5C F4 B6 F5 E1 E0 BA CA 6A
9B 7C 37 7D F8 DC 39 CC 12 2E A6 8F 64 5E C3 37
00
The key parameters of the second key contribution are:
X25519Key2 (X25519)
UDF: ZAAA-CTKG-X255-XXKE-Y2
Scalar: 30800688691513612134093999707357841640579640775881469
593062950189697563564400
Encoded Private
70 19 5B 38 A4 46 21 79 31 AC 48 83 60 C9 BD F8
E1 EE 04 53 67 F2 B5 D8 9E 42 53 66 6F 92 18 44
U: 35108630063567318397224393939085269372284744000330218923799041
589332061533992
V: 13827314478911339710714490558315610168380330915483870499348836
357802235649136
Encoded Public
28 37 F5 39 16 C6 10 C6 8A AC 75 E9 20 EF 67 6D
C2 6C AF 2C E4 F6 4F C9 E9 30 6C BD C9 C7 9E 4D
00
The composite private key is:
Scalar_A = (Scalar_1 + Scalar_2) mod L
= 70836469997123835938663996799427126600035261699252680723027418877
4936630452
Encoded Composite Private Key:
B4 54 B7 EF 13 30 0D DF C6 CB FE 5D 6A A3 A8 C0
7C 9C 15 54 20 20 07 0C 04 1E 48 05 93 EB 90 01
The composite public key is:
Hallam-Baker Expires March 8, 2021 [Page 23]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Point_A = Point_1 + Point_2
U: 416454936139914218771704724014904891682742086807613599097165979348
46285027335
V: 473400233126764321363639652645349333601103100790621508110841442520
99552212729
Encoded Public
07 98 75 38 67 9C 66 21 A3 0A D1 06 CF F5 81 04
94 C0 52 C9 9C FD AE 4E 13 3B 43 9D 9A 83 12 5C
Note that in this case, the unsigned representation of the key is
used as the composite key is intended for unsigned CurveX key
agreement. If the result is intended for use as a key contribution,
the signed representation is required.
6.1.2. X448
The key parameters of the first key contribution are:
X448Key1 (X448)
UDF: ZAAA-ETKG-X44X-KEYX
Scalar: 68165415229434843487640754974827937311214322558126978
8055715553507401814865302008262214951100710804646043741434925
630887320553400661768
Encoded Private
08 77 91 25 66 19 C6 1A 03 C7 60 9A 8C C8 10 9D
DE F5 20 E1 A7 7F 3E 83 56 57 FE A6 C9 97 79 FB
DC 85 55 6F CE 17 79 70 CA 3E B5 D1 6A B0 50 6A
60 F6 BF 3A 88 E5 15 F0
U: 60697849609835675975297341597995979787516605306209816088918249
8293453953345846660594020472424536065173283947670623780408505
23120715561
V: 60813500494147049417364978264586877278456315581444885337361828
5076034450004202627339591608123302429557097118744860203117206
220854848663
Encoded Public
29 C7 E7 1A ED 85 B5 66 F4 CA 8F 4D 07 72 EC 4B
15 42 FA 95 4D A3 25 F6 D2 BF C0 5E 11 C4 27 D3
A1 43 D8 74 B6 4C C8 22 7D 64 56 58 A4 8C C6 5D
DA F2 AA 75 DE DE 60 15 80
The key parameters of the second key contribution are:
Hallam-Baker Expires March 8, 2021 [Page 24]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
X448Key2 (X448)
UDF: ZAAA-ETKG-X44X-KEY2
Scalar: 67824881411761849798195083121628378835623370171088982
6937962011129206719268741815680700006802689991287015918654801
310197484516725932432
Encoded Private
90 C1 CE 67 A2 88 20 95 B9 A8 8A E7 5A 12 73 C6
4C E3 B0 0E 3A A4 1A 72 03 39 FC 9B 47 D9 6A E0
A2 81 63 57 77 EB 97 E5 CE 05 2C CB EE D7 64 F6
51 C1 42 E7 FE D9 E2 EE
U: 32395912186842981800922536415382601434069282464793284039370624
1565981551756628007189667971676177150776689230729229736979561
639842244556
V: 18056267944998342850921302138832444826477211000541459460301605
4105989977716699286334066341414636204710801397092415122728296
636211077711
Encoded Public
CC 67 05 A8 AE D3 8C 6E 17 F8 7F 66 77 14 7F 32
D3 F6 12 1C E2 80 A9 BF A9 AA 41 FC 88 EF E3 F9
38 C7 1C AA 1A 14 54 EC F0 4D 6D 20 ED 4F 63 24
F2 A0 68 F5 1C 09 1A 72 80
The composite private key is:
Scalar_A = (Scalar_1 + Scalar_2) mod L
= 87935198894654874397041717160555226349504546089353009501069716070
586506403266723929544670861554164189887604126085304951388779109
045747
Encoded Composite Private Key:
F3 55 F6 DD 05 50 99 B7 68 84 84 A1 C5 89 8A 79
3A 5B F6 27 DE 24 31 97 F5 94 73 D9 14 71 E4 DB
7F 07 B9 C6 45 03 11 56 99 44 E1 9C 59 88 B5 60
B2 B7 02 22 87 BF F8 1E
The composite public key is:
Hallam-Baker Expires March 8, 2021 [Page 25]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Point_A = Point_1 + Point_2
U: 611634634479536677984900819195998637894371405676964036939736481366
88134799342739585406562158256601376457049422599663606975867088547
575
V: 547531628982729065710146631050685048629332114514125362339393102647
61134803271330580187933395652539791547319114595107754138802418952
4364
Encoded Public
F7 2E 68 4B 64 DC 2E 24 61 B9 28 14 2E 1D D9 41
6A 29 4F A2 5F F1 AF 07 24 6C 9B 8A 9E C0 E5 58
E6 8C ED BE DD C3 34 11 59 B6 DC 64 03 1A 1E BC
D4 B7 88 21 60 DA 8A 15
Note that in this case, the unsigned representation of the key is
used as the composite key is intended for unsigned CurveX key
agreement. If the result is intended for use as a key contribution,
the signed representation is required.
6.1.3. Ed25519
The key parameters of the first key contribution are:
ED25519Key1 (ED25519)
UDF: ZAAA-GTKG-ED25-5XXK-EYX
Scalar: 39507802390720856312219571924476007168388547774368948
368537778683821975155688
Encoded Private
1C C7 DE DF 19 7B 39 5F 82 98 26 62 AA DE 6C 66
04 C3 E3 A2 C8 3D 18 58 06 2C 3E EC 7C D4 B4 F2
X: 42353721841561159243771574200946096579404715276724838688117248
3158919506245796568293273125470706294881250827210288815928170
449575540044968280671060652600
Y: 14453248808291445687399372639220007070442564445118267751942208
0837579501036794314829741330844154033441251810135221340268136
7161993702790547954006637246092
Encoded Public
6D F1 94 33 33 CC 66 4D 93 89 E2 FB 38 61 21 D5
C5 6B 29 0F 5C 12 A8 4D 99 06 31 2D 35 32 22 A5
The key parameters of the second key contribution are:
Hallam-Baker Expires March 8, 2021 [Page 26]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
ED25519Key2 (ED25519)
UDF: ZAAA-GTKG-ED25-5XXK-EY2
Scalar: 39507802390720856312219571924476007168388547774368948
368537778683821975155688
Encoded Private
1C C7 DE DF 19 7B 39 5F 82 98 26 62 AA DE 6C 66
04 C3 E3 A2 C8 3D 18 58 06 2C 3E EC 7C D4 B4 F2
X: 42353721841561159243771574200946096579404715276724838688117248
3158919506245796568293273125470706294881250827210288815928170
449575540044968280671060652600
Y: 14453248808291445687399372639220007070442564445118267751942208
0837579501036794314829741330844154033441251810135221340268136
7161993702790547954006637246092
Encoded Public
6D F1 94 33 33 CC 66 4D 93 89 E2 FB 38 61 21 D5
C5 6B 29 0F 5C 12 A8 4D 99 06 31 2D 35 32 22 A5
The composite private key is:
Scalar_A = (Scalar_1 + Scalar_2) mod L
= 66455490081190904847072782185220719282059319549388206770560479847
89407801486
Encoded Composite Private Key:
8E 20 46 06 EE 61 70 82 FA 37 43 E2 5A 68 E7 3C
73 4A 36 B7 AC A4 DF 68 A7 95 5C 8E 58 3F B1 0E
The composite public key is:
Point_A = Point_1 + Point_2
X: -78285292761951767745666894197721180606214882184104422609189932681
69896558088044165355551471001743951239695738047106458517545601916
4578961762059345997440
Y: 260549350612676062448188625658154114443427558625932490186172625180
16179787773477706605100876536271693949174654809503102876480720244
0555166017893772852160
Encoded Public
8E 89 98 D0 2D 7F 76 C3 A7 FF B3 1D 2B 41 7E E9
51 6B 51 B5 F2 84 8D 17 6F 59 9B 5B 6F 01 CF 73
6.1.4. Ed448
The key parameters of the first key contribution are:
Hallam-Baker Expires March 8, 2021 [Page 27]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
ED448Key1 (ED448)
UDF: ZAAA-ITKG-ED44-XKEY-X
Scalar: 53741526827163371875813321995189037002816220481405056
0575131176561199901538761967283817989566517114321868559709090
857214825841130713784
Encoded Private
E5 0F 73 50 27 0A 2F 7D FD D0 96 E5 03 D3 35 2C
99 CB 71 7C 0B D9 49 E0 40 5E C7 FB D1 F5 05 18
18 6B 04 81 8B 4D 81 DC 33 CE DF 81 D5 EA 90 43
D9 E5 D0 A7 F1 EF 9C F3
X: 46070586985722000292864744471871508558334313374829024264732526
0256877451971853613261831326120959789917482766653217856979552
299464523257
Y: 60551781313893332009337150573641968782237423331690407655569563
6098829567124403075067563581124781122484845054468415282443786
254887063867
Encoded Public
B5 B9 3F B5 B2 5B 82 E1 08 F5 6C 79 80 A1 68 5A
5C BB 2A FD 27 B2 9A F8 DF 91 CD CA 60 B8 75 3F
62 96 40 38 78 96 77 0C 21 40 E6 D4 0B 05 8F 24
D6 FD 65 61 A2 6C C1 86 80
The key parameters of the second key contribution are:
ED448Key2 (ED448)
UDF: ZAAA-ITKG-ED44-XKEY-2
Scalar: 53741526827163371875813321995189037002816220481405056
0575131176561199901538761967283817989566517114321868559709090
857214825841130713784
Encoded Private
E5 0F 73 50 27 0A 2F 7D FD D0 96 E5 03 D3 35 2C
99 CB 71 7C 0B D9 49 E0 40 5E C7 FB D1 F5 05 18
18 6B 04 81 8B 4D 81 DC 33 CE DF 81 D5 EA 90 43
D9 E5 D0 A7 F1 EF 9C F3
X: 46070586985722000292864744471871508558334313374829024264732526
0256877451971853613261831326120959789917482766653217856979552
299464523257
Y: 60551781313893332009337150573641968782237423331690407655569563
6098829567124403075067563581124781122484845054468415282443786
254887063867
Encoded Public
B5 B9 3F B5 B2 5B 82 E1 08 F5 6C 79 80 A1 68 5A
5C BB 2A FD 27 B2 9A F8 DF 91 CD CA 60 B8 75 3F
62 96 40 38 78 96 77 0C 21 40 E6 D4 0B 05 8F 24
D6 FD 65 61 A2 6C C1 86 80
The composite private key is:
Hallam-Baker Expires March 8, 2021 [Page 28]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Scalar_A = (Scalar_1 + Scalar_2) mod L
= 16628213117375882432961168004377507211427270876895354579839960414
666978326982600598665720267457234882718565087272340290578290296
3178673
Encoded Composite Private Key:
B1 0C A6 9F 18 5C CE 75 68 CF A3 94 FD 1C 20 DC
08 4A 1A 8D EA 8F ED 45 17 68 B6 9F 55 03 DA 18
5F A8 2E F3 98 92 24 C7 C2 05 8E 86 9E BD 4E A2
6F 38 45 74 67 F6 90 3A
The composite public key is:
Point_A = Point_1 + Point_2
X: 577530061094566245645474620282168197911998758313406086914794815409
17246422939462333536659252558650386613682198540830437043888246526
5810
Y: 505836808606768081321267696834164575314792405646755177389264860926
82650383803094471233632502605998926567195957732072433352975006488
1824
Encoded Public
99 67 9B 7C 5E 1C 7E 51 CD 39 A2 41 83 62 73 3E
60 93 17 A9 20 0E E3 BA 25 B3 B5 23 A3 A7 84 2E
9D 67 6F D7 0B 33 02 1D EB 76 83 F8 77 D8 48 F8
8B A3 72 E8 A9 6F 20 18 80
6.2. Threshold Decryption
6.2.1. Direct Key Splitting X25519
The encryption key pair is
Hallam-Baker Expires March 8, 2021 [Page 29]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
X25519KeyA (X25519)
UDF: ZAAA-CTHD-X255-XXKE-YA
Scalar: 36212799908425711450656372795692477094724455418915704
216848228525958587810064
Encoded Private
10 01 D5 D1 E2 D3 DB 42 9E 40 5F D9 DB AE E8 09
DE 43 C3 E6 D1 4F 3A 31 92 BF 19 8A E9 B7 0F 50
U: 14523539712308371644546850739155588238080554014514563739095172
886049239361031
V: 56685060472089790044070522288405984326906734250304251487683593
932889808473139
Encoded Public
07 66 84 48 25 85 F6 4A 3A EE DF B7 69 1B 57 51
EC 18 BE AF 08 BA 0D FE BE F8 74 4E 3C 08 1C 20
To create n key shares we first create n-1 key pairs in the normal
fashion. Since these key pairs are only used for decryption
operations, it is not necessary to calculate the public components:
X25519Key1 (X25519)
UDF: ZAAA-CTHD-X255-XXKE-YX
Scalar: 32951726132685026729149224926255648061071804906258082
061427666995947179849152
Encoded Private
C0 B5 33 D4 F3 D0 16 4F 96 DF C3 AD 97 93 02 EF
B4 25 E2 46 A3 69 1D 22 9B 5B A2 78 1C 04 DA 48
The secret scalar of the final key share is the secret scalar of the
base key minus the sum of the secret scalars of the other shares
modulo the group order:
Scalar_2 = (Scalar_A - Scalar_1) mod L
= 403147584512037825404691865456117698808221309075461782425833707
7336679400315
This is encoded as a binary integer in little endian format:
7B 43 64 61 E9 28 4D 79 AB 9C 6E CC 9F 79 14 3D
92 69 A5 2D 75 B9 57 53 2D 1B BC 02 06 BC E9 08
6.2.2. Direct Decryption X25519
The means of encryption is unchanged. We begin by generating an
ephemeral key pair:
Hallam-Baker Expires March 8, 2021 [Page 30]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
X25519KeyE (X25519)
UDF: ZAAA-CTHD-X255-XXKE-YE
Scalar: 41955577142906312619127105554814681129195921605852142
704362465226652441661496
Encoded Private
38 50 3C 88 22 4F 61 D7 9A 2E 1D 71 F0 31 74 44
A2 3B 2B 35 21 21 CA 19 4B 11 EB F0 DF 03 C2 5C
U: 10080018124246254127076649374753145019412450363156572968151721
892767560820008
V: 43683938787921854603630290352714276342923724280578266457509078
671566344321831
Encoded Public
28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28
8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16
The key agreement result is given by multiplying the public key of
the encryption pair by the secret scalar of the ephemeral key to
obtain the u-coordinate of the result.
U: 247351751388894803426442650867524924086144759194834658830326105266
22202018180
The u-coordinate is encoded in the usual fashion (i.e. without
specifying the sign of v).
84 39 A5 21 13 F9 13 F0 7F F4 44 C0 DF 5D 44 DD
DD F4 9B 87 4C DD E1 AB 64 00 8F A2 ED 9C AF 36
The first decryption contribution is generated from the secret scalar
of the first key share and the public key of the ephemeral.
The outputs from the Montgomery Ladder are:
x_2 57800249527850149046770413207257250301842844049677844025524059085
132359257003
z_2 37229326806761131733056994095424883574786241198535734197174081138
402379671391
x_3 30722194817314627970562030033494699359853137448471883846088158083
361967945513
z_3 29143359268139878301695995826542801325089258636824690596939399658
126254126746
The coordinates of the corresponding point are:
u 2625200443692459084967263034650122583671912028244890150161521677645
8728744244
v 2340339249609928967870268630489687123941624857494487121340604194885
7707717709
Hallam-Baker Expires March 8, 2021 [Page 31]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
The encoding of this point specifies the u coordinate and the sign
(oddness) of the v coordinate:
28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28
8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16
The second decryption contribution is generated from the secret
scalar of the second key share and the public key of the ephemeral in
the same way:
u 2568180775076864300893967221119748767931055928591855851227298301978
9028635830
v 5237624535641756510077423429806596028526835148653096601777403098805
4910628425
28 E5 5E 1D DD 1D 93 71 24 53 0A 83 B3 68 0D 28
8F 37 AC 53 B6 65 97 7E C1 54 44 41 8C 16 49 16
To obtain the key agreement value, we add the two decryption
contributions:
u 5363809193902384353244842537457427150937755976201184630020143767288
0976727749
v 2576238777948215852102595446870010694371604288066653261024661407554
3602367190
This returns the same u coordinate value as before, allowing us to
obtain the encoding of the key agreement value and decrypt the
message.
6.2.3. Direct Key Splitting X448
The encryption key pair is
Hallam-Baker Expires March 8, 2021 [Page 32]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
X448KeyA (X448)
UDF: ZAAA-ETHD-X44X-KEYA
Scalar: 70596789123829480733485730386174565339013185647363028
6777277621057939099785091228353248522408450794128800398810019
569879502484967206280
Encoded Private
88 2D AF 58 10 66 9E 1E F9 F2 C5 76 A2 00 86 F5
B0 B9 C6 B9 E6 34 12 57 64 E3 63 B7 99 48 01 77
9B A3 49 2D 7C B8 80 D7 63 44 6B C9 CB 83 F0 01
B6 55 E0 92 1C 2A A6 F8
U: 54256629638851994806054576189463839532492460394052748417730874
4299533502601001906894660938607827805200569088593927035891085
28218439174
V: 12640494198304757803713993624351573936804262085795518571061045
0631383333635306581037675004961525698205648857075020359124084
524068583614
Encoded Public
06 FE 38 7A 1B 1E 99 D4 89 00 07 B9 88 6F 97 01
BD 88 BB 9D A9 31 30 CC 47 E6 2F 9C 44 35 AF A4
6C B8 3B EE 89 C0 99 6B E4 7C 75 33 94 85 BC B8
54 36 AF D9 C0 17 1C 13
To create n key shares we first create n-1 key pairs in the normal
fashion. Since these key pairs are only used for decryption
operations, it is not necessary to calculate the public components:
X448Key1 (X448)
UDF: ZAAA-ETHD-X44X-KEYX
Scalar: 63066265672668423343291438147840057172035337936373473
3594300758463732521976388313294665447253881782852832499090049
354258188417511652528
Encoded Private
B0 FC CE 55 87 AA A5 36 D2 5B E5 F2 5C 1B F7 9A
5A 3D 97 D8 BB C0 81 84 98 3B 7C 29 C3 02 FC AE
91 1B EA 67 68 C5 5E 87 7A ED 16 1F CB D0 20 9D
C0 D6 62 BD 0F 35 20 DE
The secret scalar of the final key share is the secret scalar of the
base key minus the sum of the secret scalars of the other shares
modulo the group order:
Hallam-Baker Expires March 8, 2021 [Page 33]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Scalar_2 = (Scalar_A - Scalar_1) mod L
= 646627804476669823064550215361382899916128546345584148789705309
5564959403070244163454368262048594523846084193642728800427461
1461310355
This is encoded as a binary integer in little endian format:
93 47 14 FF 94 BE F6 5C 77 63 44 89 DD CA 83 A6
1A 79 82 CA 9E F6 6B 7D 98 23 59 77 60 4B FD 25
2D BF 33 95 E4 7D DF 5E DE 31 82 E8 96 54 11 9F
76 2C 43 50 2C 5F C6 16
6.2.4. Direct Decryption X448
The means of encryption is unchanged. We begin by generating an
ephemeral key pair:
X448KeyE (X448)
UDF: ZAAA-ETHD-X44X-KEYE
Scalar: 40831502887772840901106715270468009328116701340228919
4447950742749557088789408677311466089336893170031425082958041
776608657845012501716
Encoded Private
D4 94 79 EE 56 3A 43 D5 FC EB 88 3E F0 63 EF 2F
B0 92 B2 9D FD E1 43 8F 67 70 2A FC 2A AB A3 8B
40 5A C6 D8 DE 8E B8 81 BF AD 17 BA 14 7F A4 B0
D4 B1 9F CE D3 0D D0 8F
U: 41902542857582644710501442087876846551351583947506685319975417
2921931242764163121977613761818608927787788470856012050834001
655292441835
V: 40254626888669687592165362896510117701831215997629302922912638
4107109948063151002535904960734463095918076287222011626898597
213849340021
Encoded Public
EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C
B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB
D7 3D EC 20 0B 70 82 A6 38 FC 23 24 AD 98 86 35
4C 99 AD 4D 0E C4 95 93
The key agreement result is given by multiplying the public key of
the encryption pair by the secret scalar of the ephemeral key to
obtain the u-coordinate of the result.
U: 414519841929159382730636919036875317796178034011999213235983537052
30510678702415242441193107876747178183775523375063128358893667955
0233
The u-coordinate is encoded in the usual fashion (i.e. without
specifying the sign of v).
Hallam-Baker Expires March 8, 2021 [Page 34]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
19 ED 3F 7A 63 6D AA 9A 3E 05 29 DE CC BA C7 F1
E0 A7 FA C0 C4 70 E0 E1 A5 FC DA 0A B0 52 EC 8A
36 9B 35 6D BE FE 0A 95 22 A3 1F 8A C0 89 0F 19
9A 01 8C CB 17 84 FF 91 00
The first decryption contribution is generated from the secret scalar
of the first key share and the public key of the ephemeral.
The outputs from the Montgomery Ladder are:
x_2 60087238657789265874539701675840521614326868580285788286550399232
20277081132468800878653228200859196207538481852097024468118288584
83595
z_2 12573140552649037921890899942919440571502561130496393232716617155
24490660805576517881339517005970098784771472127066810694797758409
67645
x_3 40216911160845555507626938485596306260547743077930604703891475599
53207238052152872831803734397389643529057507149471429452955111471
57394
z_3 48671808823760924633626118221453591105199403417491562559814414359
34079336265430685974504655698846599309734305554546571306740770389
79747
The coordinates of the corresponding point are:
u 5310627084956226133549480379012439149584638171147187426442235629260
04186474991811830611467926523417739685244466041108245014409383321
437
v 6480384951984610654865132490606294355962228129695701220316681167173
89634554460437237795204236689985354028508124817314496063921770833
81
The encoding of this point specifies the u coordinate and the sign
(oddness) of the v coordinate:
EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C
B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB
D7 3D EC 20 0B 70 82 A6 38 FC 23 24 AD 98 86 35
4C 99 AD 4D 0E C4 95 93
The second decryption contribution is generated from the secret
scalar of the second key share and the public key of the ephemeral in
the same way:
Hallam-Baker Expires March 8, 2021 [Page 35]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
u 2432029307606011854651950642127064534858415441240032460817128643691
02601495764607628214871657677482439232238254450281582409532827123
057
v 3304237495909049135999182737314299324454426462198935317955136317282
40167193898154033571033048069157608137872491595181800632292085611
537
EB 34 D3 9E 92 3E 82 CC E6 EC 77 9F 3D 11 83 3C
B6 5B 5C 04 E8 1F D6 E1 07 C0 62 FE F8 F6 34 BB
D7 3D EC 20 0B 70 82 A6 38 FC 23 24 AD 98 86 35
4C 99 AD 4D 0E C4 95 93
To obtain the key agreement value, we add the two decryption
contributions:
u 2259776336573351712090323684006287979378142231675451855263136351631
84627019682834233607456823018602790573389381890060345691088913511
436
v 3356804465434915738990773252496451168197759413718456519751139752920
22788339143143140400339843420207702195408750068698590142923542805
226
This returns the same u coordinate value as before, allowing us to
obtain the encoding of the key agreement value and decrypt the
message.
6.2.5. Shamir Secret Sharing X448
[TBS]
6.2.6. Lagrange Decryption X448
[TBS]
7. Security Considerations
All the security considerations of [RFC7748] and [RFC8032] apply and
are hereby incorporated by reference.
7.1. Complacency Risk
Separation of duties can lead to a reduction in overall security
through complacency and lack of oversight.
Hallam-Baker Expires March 8, 2021 [Page 36]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
Consider the case in which a role that was performed by A alone is
split into two roles B and C. If B and C each do their job with the
same diligence as A did alone, risk should be reduced but if B and C
each decide they can be careless because security is the
responsibility of the other, the risk of a breach may be
substantially increased.
It is therefore important that each of the participants in a
threshold scheme perform their responsibilities with the same degree
of diligence as if they were the sole control and for those
responsible for oversight to treat single point failures that do not
lead to an actual breach with the same degree of concern as if a
breach had occurred.
Use of threshold operation modes mitigates but does not eliminate
security considerations relating to private key operations of the
underlying algorithm. For example, use of threshold key generation
to generate a composite keypair {b+c, B+C} from key contributions {b,
B} and {c, C} produces a strong composite private key if either of
the key contributions _a_, _b_ are strong. But the composite key
will be weak if neither contribution is strong.
7.2. Rogue Key Attack
In general, threshold modes of operation provide a work factor that
is at least as high as that of the work factor of the strongest
private key share. The karmic tradeoff for this benefit is that the
trustworthiness of a composite public key is that of the least
trustworthy input.
For example, consider the case in which a client with keypair {c, C}
generates an ephemeral keypair {e, E} for use in an authentication
algorithm. We might decide to create an 'efficient' proof of
knowledge of c and e by using the composite public key A = C+E to
test for knowledge of both at the same time.
This approach fails because an attacker with knowledge of C can
generate a keypair {a, A} and calculate the corresponding public key
E = A-C. The attacker can then use the value a in the authentication
protocol.
8. IANA Considerations
This document requires no IANA actions (yet).
It will be necessary to define additional code points for the signed
version of the X25519 and X448 public key and the threshold
decryption final private keys.
Hallam-Baker Expires March 8, 2021 [Page 37]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
9. Acknowledgements
Rene Struik, Tony Arcieri, Scott Fluhrer, Scott Fluhrer, Dan Brown,
Mike Hamburg
10. Appendix A: Calculating Lagrange coefficients
The following C# code calculates the Lagrange coefficients used to
recover the secret from a set of shares.
[TBS]
11. Normative References
[draft-ietf-lwig-curve-representations]
Struik, R., "Alternative Elliptic Curve Representations",
Work in Progress, Internet-Draft, draft-ietf-lwig-curve-
representations-12, August 24, 2020,
.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
.
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, .
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017,
.
12. Informative References
[Costello17]
Costello, C. and B. Smith, "Montgomery curves and their
arithmetic", 2017.
[draft-hallambaker-mesh-architecture]
Hallam-Baker, P., "Mathematical Mesh 3.0 Part I:
Architecture Guide", Work in Progress, Internet-Draft,
draft-hallambaker-mesh-architecture-14, July 27, 2020,
.
Hallam-Baker Expires March 8, 2021 [Page 38]
Internet-Draft Threshold Modes in Elliptic Curves September 2020
[draft-hallambaker-mesh-developer]
Hallam-Baker, P., "Mathematical Mesh: Reference
Implementation", Work in Progress, Internet-Draft, draft-
hallambaker-mesh-developer-10, July 27, 2020,
.
[draft-hallambaker-threshold-sigs]
Hallam-Baker, P., "Threshold Signatures in Elliptic
Curves", Work in Progress, Internet-Draft, draft-
hallambaker-threshold-sigs-03, July 28, 2020,
.
[Kocher96] Kocher, P. C., "Timing attacks on implementations of
Diffie-Hellman, RSA, DSS, and other systems.", 1996.
[Lopez99] L?opez, J. and R. Dahab, "Fast multiplication on elliptic
curves over GF(2m) without precomputation.", 1999.
[Okeya01] Okeya, K. and K. Sakurai, "Efficient elliptic curve
cryptosystems from a scalar multiplication algorithm with
recovery of the y-coordinate on a Montgomeryform elliptic
curve.", 2001.
[RFC2631] Rescorla, E., "Diffie-Hellman Key Agreement Method",
RFC 2631, DOI 10.17487/RFC2631, June 1999,
.
[Shamir79] Shamir, A., "How to share a secret.", 1979.
Hallam-Baker Expires March 8, 2021 [Page 39]