Solana/Private Key, Public Key and Address/A Cryptographic Explanation of Private Key (Part 7)

Eddsa is a variation of Schnorr signature using a twisted Edwards curve. It aims to be faster than existing digital signature schemes without sacrificing security.

EDDSA Points Encoding

In ed25519, we need to use a special algorithm for encoding points on a curve. Intuitively, a point on a curve consists of two values, x and y, both are in the range 0 <= x,y < p, so we need to use 64 bytes to represent it. But there is a way to compress the space to 32 bytes, as follows:

  1. Since y < p, the most significant bit of y is always 0.
  2. Copy the least significant bit of x to the most significant bit of y, and encode the result in 32 bytes in little-endian order.

In this way, we know the exact value of y and the parity of x. The code is realized as follows.

def pt_encode(pt: pxsol.ed25519.Pt) -> bytearray:
    # A curve point (x,y), with coordinates in the range 0 <= x,y < p, is coded as follows. First, encode the
    # y-coordinate as a little-endian string of 32 octets. The most significant bit of the final octet is always zero.
    # To form the encoding of the point, copy the least significant bit of the x-coordinate to the most significant bit
    # of the final octet.
    # See https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.2
    n = pt.y.x | ((pt.x.x & 1) << 255)
    return bytearray(n.to_bytes(32, 'little'))

EDDSA Points Decoding

Point decoding is the inverse of point encoding. The steps are as follows:

  1. First, the 32-byte array is interpreted as an integer with little endian. The 255th bit of this number is the least significant bit of the x-coordinate, indicating the parity of the x-value. Simply clearing this bit restores the y-coordinate. If y >= p, the decoding fails.
  2. To recover the x-coordinate means that the curve equation x² = (y² - 1) / (d * y² + 1) holds. Let u = y² - 1, v = d * y² + 1, and compute its candidate root x = (u / v)^((p + 3) / 8).
  3. Now there are three cases:
    1. if x * x == u / v, do nothing.
    2. if x * x == u / v * -1, then x = x * 2^((p - 1) / 4).
    3. Decoding fails, the point is not on the curve.
  4. Finally, determine the parity of x. If the parity does not match, then x = -x.

The implementation looks like this:

def pt_decode(pt: bytearray) -> pxsol.ed25519.Pt:
    # Decoding a point, given as a 32-octet string, is a little more complicated.
    # See https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.3
    #
    # First, interpret the string as an integer in little-endian representation. Bit 255 of this number is the least
    # significant bit of the x-coordinate and denote this value x_0. The y-coordinate is recovered simply by clearing
    # this bit. If the resulting value is >= p, decoding fails.
    uint = int.from_bytes(pt, 'little')
    bit0 = uint >> 255
    yint = uint & ((1 << 255) - 1)
    assert yint < pxsol.ed25519.P
    # To recover the x-coordinate, the curve equation implies x^2 = (y^2 - 1) / (d y^2 + 1) (mod p). The denominator is
    # always non-zero mod p.
    y = pxsol.ed25519.Fq(yint)
    u = y * y - pxsol.ed25519.Fq(1)
    v = pxsol.ed25519.D * y * y + pxsol.ed25519.Fq(1)
    w = u / v
    # To compute the square root of (u/v), the first step is to compute the candidate root x = (u/v)^((p+3)/8).
    x = w ** ((pxsol.ed25519.P + 3) // 8)
    # Again, there are three cases:
    # 1. If v x^2 = +u (mod p), x is a square root.
    # 2. If v x^2 = -u (mod p), set x <-- x * 2^((p-1)/4), which is a square root.
    # 3. Otherwise, no square root exists for modulo p, and decoding fails.
    if x*x != w:
        x = x * pxsol.ed25519.Fq(2) ** ((pxsol.ed25519.P - 1) // 4)
        assert x*x == w
    # Finally, use the x_0 bit to select the right square root. If x = 0, and x_0 = 1, decoding fails. Otherwise, if
    # x_0 != x mod 2, set x <-- p - x.  Return the decoded point (x,y).
    assert x != pxsol.ed25519.Fq(0) or not bit0
    if x.x & 1 != bit0:
        x = -x
    return pxsol.ed25519.Pt(x, y)

Private Key

As mentioned earlier, Ed25519's private key is a 32-byte random number, usually generated by a secure random number generator. The private key is central to the user's identity and must be kept strictly confidential. In the implementation of Ed25519, the private key is not used for direct signing, but is expanded into a 64-byte seed by a hash function (sha-512), part of which is used as a scalar for generating the public key, and part of which is used as a secret scalar for signing. This design enhances the security of the private key and prevents the risk of exposure due to the direct use of the original private key.

Private key generation is simple, but its security depends on the quality of the random numbers. If the random numbers are predictable, an attacker may threaten the system by brute-force cracking or forging signatures. Therefore, the use of a cryptographically secure random number generator (such as /dev/urandom or a hardware random number generator) is essential for private key generation.

import secrets

prikey = bytearray(secrets.token_bytes(32))

Public Key

The length of the public key for Ed25519 is also 32 bytes. The 32-byte public key is generated by the following steps.

  1. Use sha-512 to hash the 32-byte private key to generate a 64-byte hash result. Only the first 32 bytes are used to generate the public key.
  2. Clear the lowest three bits of the first byte, clear the highest bit of the last octet, and set the second highest bit of the last byte.
  3. Interpret the above data as little end-order integers to form the secret scalar a. Perform the scalar multiplication g * a, the public key is the encoding of the point.
def pubkey(prikey: bytearray) -> bytearray:
    assert len(prikey) == 32
    h = hash(prikey)
    a = int.from_bytes(h[:32], 'little')
    a &= (1 << 254) - 8
    a |= (1 << 254)
    a = pxsol.ed25519.Fr(a)
    return pt_encode(pxsol.ed25519.G * a)

The public key generation process of Ed25519 is unidirectional: the public key can be quickly computed from the private key, but the private key cannot be inverted from the public key, and this irreversibility is the central guarantee of the elliptic curve discrete logarithm problem. The role of the public key is to publicize the identity, and anyone can use the public key to verify the signature. Due to the efficient design of Ed25519, public key generation and usage are very fast, which is very suitable for high-performance scenarios.

EDDSA Signing

Signatures are used to prove the authenticity and integrity of messages. The signature generation process takes a 32-byte private key (an array) and any-sized message m as input:

  1. The private key (32 bytes) is hashed using sha-512. As described in the previous section, construct the secret scalar a from the first half of the hash, and the corresponding public key. Denote the second half of the hash digest as prefix.
  2. Compute sha-512(prefix + m), where m is the message to be signed. Interpret the resulting 64-byte hash as a little-endian integer r.
  3. Compute point g * r, and encode the result in points, denoted digest.
  4. Compute sha-512(digest + pubkey + m), and interpret the resulting 64-byte digest as a little-endian integer h.
  5. Compute s = r + a * h.
  6. Concatenate digest with the little-endian encoding of s to form a 64-byte signature.
def sign(prikey: bytearray, m: bytearray) -> bytearray:
    # The inputs to the signing procedure is the private key, a 32-octet string, and a message M of arbitrary size.
    # See https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.6
    assert len(prikey) == 32
    h = hash(prikey)
    a = int.from_bytes(h[:32], 'little')
    a &= (1 << 254) - 8
    a |= (1 << 254)
    a = pxsol.ed25519.Fr(a)
    A = pxsol.ed25519.G * a
    pubkey = pt_encode(A)
    prefix = h[32:]
    r = pxsol.ed25519.Fr(int.from_bytes(hash(prefix + m), 'little'))
    R = pxsol.ed25519.G * r
    digest = pt_encode(R)
    h = pxsol.ed25519.Fr(int.from_bytes(hash(digest + pubkey + m), 'little'))
    s = r + a * h
    return digest + bytearray(s.x.to_bytes(32, 'little'))

EDDSA Verification

Signature verification is the process of verifying that a message has not been tampered with and has indeed been signed by the person holding the corresponding private key. The Ed25519 signature verification requires message m, signature v, and public key pubkey, in the following steps.

  1. Split the signature v into two 32-byte arrays. Record the first half as digest, decode it as point r, and decode the second half as integer s. Decode the public key pubkey as point a. If any of the decoding fails (including s being out of range), the signature is invalidated.
  2. Compute sha-512(digest + pubkey + m), and interpret the 64-bit byte digest as a low-end integer h.
  3. Check that the group equation g * s == r + a * h is satisfied.
def verify(pubkey: bytearray, m: bytearray, g: bytearray) -> bool:
    # Verify a signature on a message using public key.
    # See https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.7
    assert len(pubkey) == 32
    assert len(g) == 64
    A = pt_decode(pubkey)
    digest = g[:32]
    R = pt_decode(digest)
    s = pxsol.ed25519.Fr(int.from_bytes(g[32:], 'little'))
    h = pxsol.ed25519.Fr(int.from_bytes(hash(digest + pubkey + m), 'little'))
    return pxsol.ed25519.G * s == R + A * h

Q: Assuming you have the private key 833fe62409237b9d62ec77587520911e9a759cec1d19755b7da901b96dca3d42, please sign the message sha-512('abc') and verify the signature.

A:

import pxsol
import hashlib

prikey = bytearray.fromhex('833fe62409237b9d62ec77587520911e9a759cec1d19755b7da901b96dca3d42')
pubkey = pxsol.eddsa.pubkey(prikey)
msg = hashlib.sha512(b'abc').digest()
sig = pxsol.eddsa.sign(prikey, msg)
assert sig[:32].hex() == 'dc2a4459e7369633a52b1bf277839a00201009a3efbf3ecb69bea2186c26b589'
assert sig[32:].hex() == '09351fc9ac90b3ecfdfbc7c66431e0303dca179c138ac17ad9bef1177331a704'
assert pxsol.eddsa.verify(pubkey, msg, sig)