commit cca5bc5812fc93ac4be70c55527747c67a6486b1
parent c9ca0ccd45c8a866a3bbad0cb15c53c8a66beab8
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Wed, 10 Jul 2024 20:35:09 +0200
minor test improvements
Diffstat:
1 file changed, 33 insertions(+), 25 deletions(-)
diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
@@ -224,49 +224,57 @@
<section anchor="KeyGen" numbered="true" toc="default">
<name>Key generation</name>
<t>
- Let "KeyGenEd25519() -> (x,X)" be a function that produces an Ed25519 key pair as defined in <xref target="RFC8032"/>.
+ Let "KeyGenEd25519() -> (x,X)" denote a function that produces an Ed25519 key pair as defined in <xref target="RFC8032"/>.
+ Let "KeyGenElligator() -> (x,X)" denote a function that produces a Curve25519 key pair suitable for Elligator obfuscations which we will define in the following.
</t>
<t>
GNUnet communicators utilize Elligator for the encoding and decoding of the ephemeral public keys
described in Section 5 of <xref target="BHKL13"/>.
- Accordingly, let "KeyGenElligator() -> (x,X)" denote a function that produce a Curve25519 key pair suitable for Elligator obfuscations which we
- will define in the following.
The general idea when generating an Elligator key pair is is to create both a random high-order curve point and a low-order curve point.
- Adding them together results in a curve point
- that is evenly distributed on the whole Curve25519.
- Not all Curve25519 points are eligible to be used with Elligator for a key exchange. In
- particular, not all points will have the property that the encoding and subsequent decoding result in the original point. The mathematical reasoning is elaborated in <xref target="security_elligator"/>.
- To create a valid Curve25519 point that can be used as an
- ephemeral key, one needs to generate as many curve points until the desired property holds.
- Let G be the generator of the prime order group of Ed25519, H the generator of the low order subgroup of Ed25519 and EdToCurve() a function
- which converts Ed25519 points to their corresponding Curve25519 points, we define:
- An Elligator key pair is generated as follows.
+ Adding them together results in a curve point that is evenly distributed on the whole Curve25519.
+ Not all Curve25519 points are suitable for use with Elligator.
+ In particular, not all Curve25519 points have the property that the Elligator encoding and subsequent
+ decoding result in the original point (See <xref target="security_elligator"/> for details).
+ To create a Curve25519 point that can be used with Elligator, one needs to find a curve point
+ for which this property holds.
+ One heurisitic is to generate random key pairs until one such point is found.
+ </t>
+ <t>
+ Let G be the generator of the prime order group of Ed25519, H the generator of the low order subgroup of
+ Ed25519 and EdToCurve() a function which converts Ed25519 points to their corresponding Curve25519 points.
+ We define "KeyGenElligator" as follows:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
KeyGenElligator():
VALID := 0
while(!VALID):
x := random(256)
- ED_high := clamps(x) * G
- ED_low := (x mod 8) * H
- ED := ED_high + ED_low
- X := EdToCurve(ED)
+ x[0] &= 248
+ x[31] &= 127
+ x[31] |= 64
+ E_high := x * G
+ E_low := (x mod 8) * H
+ E := E_high + E_low
+ X := EdToCurve(E)
if ElligatorDec(ElligatorEnc(X)) == X:
- VALID := 1
- return (x, X)
+ return (x,X)
]]></artwork>
<t>
- "Enc" and "Dec" are the required encoding and decoding functions to obfuscate the public key and are are defined as follows:
+ "ElligatorEnc()" and "ElligatorDec()" are the required encoding and decoding functions to obfuscate a curve
+ point and are are defined in the following.
+ The obfuscated curve point is called the Elligator "Representative".
Let A be the parameter for Curve25519 as specified in section 4.1 of <xref target="RFC7748"/>.
- Further, let X be a valid x-coordinate of a Curve25519 point, sqrt() a function which calculates the square root of the finite field element, U the number
- sqrt(-1) which is a non-quadratic number in the finite field, and legendre() a function which computes the legendre symbol of a field element.
- As each of the field elements have two roots, we need to define the notion of negative and non-negative numbers. This is especially important for the
- sqrt() function. A straightforward choice is to define the set {0,..., (P - 1) / 2} as set of all non-negative numbers.
+ Further, let X be any valid x-coordinate of a Curve25519 point, sqrt() a function which calculates the
+ square root of the finite field element, U the number sqrt(-1) which is a non-quadratic number in the finite field,
+ and L() a function which computes the legendre symbol of a field element.
+ As each of the field elements have two roots, we need to define the notion of negative and non-negative numbers.
+ This is especially important for the sqrt() function.
+ A straightforward choice is to define the set {0,..., (P - 1) / 2} as set of all non-negative numbers.
The encoding function algorithm is:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
ElligatorEnc(X):
- B := rand(1)
+ B := random(1)
if B == 1:
REPR := sqrt(-X / ((X + A) * U))
else:
@@ -279,7 +287,7 @@ ElligatorEnc(X):
<artwork name="" type="" align="left" alt=""><![CDATA[
ElligatorDec(REPR):
V := -A / (1 + U * REPR^2)
- E := legendre(V^3 + A * V^2 + V)
+ E := L(V^3 + A * V^2 + V)
X := E * V - (1 - E)(A / 2)
return X
]]></artwork>
