This page derives a point for the Ristretto prime-order group built from the Edwards curve (Edwards25519), and derived from SHA512. A scalar value has eight 32-bit unsigned integer values, and where the hash fills the first four integer values. For Dalek, we derive from SHA512 and Elligator2. The order of the Ristretto group is \(l = 2^{252} + 27742317777372353535851937790883648493\). The Rust version is [here], and it is defined in RFC 9496 [2].
Deriving a point for Ristretto prime-order group built from Edwards25519 using Golang |
Theory
Ed25519 is now used in many areas and provides a simpler and more scalable signature than ECDSA. The signature is typically known as EdDSA. But there’s a possible attack on it. Overall, Ed25519 uses Curve 25519 and which has an order of 8q and where q is a prime number — and where the order of the curve is the number of valid elliptic curve points that can be produced. The attack involves the possibility of creating a small subgroup of order q and creating a confinement attack.
Overall, Curve 25519 have a Montgomery curve that is defined with:
\( y^2=x^3 + 486662 x^2 + x\)
The prime number is:
\(p=2^{255}-19\)
and where we have a base point at \(x = 9\).
The order is then a prime number of:
\(l =2^{252} + 27742317777372353535851937790883648493\)
and which has a co-factor of 8 which means there are 1/8th of the elements of elliptic curve group. This prime order subgroup defends against the Pohlig-Hellman attack. Within X25519, the subgroup problem is removed by clearing the lower three bits of the private key, and which makes sure it is divisible by 8.
Here is the clamp applied in X25519 [here]:
def clamp(n): n &= ~7 n &= ~(128 << 8 * 31) n |= 64 << 8 * 31 return n# Return nP def multscalar(n, p): n = clamp(decodeScalar25519(n)) p = unpack2(p) return pack(X25519(n, p))
This feature is not part of Ed25519. The conversion of Curve 25519 into a safe prime ordered curve was initially defined by Mike Hamburg with the Decaf method [1]:
This can then be applied to Curve 25519 with Ristretto255.
Ristretto255
Ristretto255 encodes group elements using 255 bits and provides a prime-order group of size 2252, and implemented with Curve25519. We use a prime of 2255−19. In this case, we will hash a string with SHA-512, and then map this to a point on the curve. This will be computed for Ristretto255 and an Edwards curve. In this case we will use Rust to hash a string with SHA-512, and then map this hash to Ristretto255 and also to Ed25519.
And, so, we can see that this works for the string of “Ristretto is traditionally a short shot of espresso coffee”, and which gives a point of “3066f82a1a747d45120d1740f14358531a8f04bbffe6a819f86dfe50f44a0a46”. Note in Curve 25519, we only define the x-axis point.
Coding
The coding is:
package main import ( "encoding/hex" "fmt" "os" "github.com/bwesterb/go-ristretto" ) func main() { // Dalek uses SHA512 and Elligator2 in the form of curve25519-dalek var p1 ristretto.Point var p2 ristretto.Point label:="Ristretto is traditionally a short shot of espresso coffee" argCount := len(os.Args[1:]) if argCount > 0 { label = os.Args[1] } p1.DeriveDalek([]byte(label)) p2.Derive([]byte(label)) res1 := hex.EncodeToString(p1.Bytes()) res2 := hex.EncodeToString(p2.Bytes()) fmt.Printf("Input string\t\t%v\nDerived (Dalek):\t%s\nDerived:\t\t%s",label, res1,res2) }
and a sample run is:
Input string Ristretto is traditionally a short shot of espresso coffee Derived (Dalek): 3066f82a1a747d45120d1740f14358531a8f04bbffe6a819f86dfe50f44a0a46 Derived: 4606cc789c3da8e81fd52a9ad8d850e76437477048c0b1b10a2cad7737fcaf0c
The Rust version is [here].
References
[1] Hamburg, M. (2015). Decaf: Eliminating cofactors through point compression. In Advances in Cryptology--CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I 35 (pp. 705-723). Springer Berlin Heidelberg.
[2] de Valence, H., Grigg, J., Hamburg, M., Lovecruft, I., Tankersley, G., & Valsorda, F. (2023). RFC 9496: The ristretto255 and decaf448 Groups., https://dl.acm.org/doi/book/10.17487/RFC9496