In ECC (Elliptic Curve Cryptography) we often have to hash our data to a scalar value or to a point on the curve. Once hashed, it is difficult to reverse the operation (unless we did a brute force search for it). The method defined here is proposed an an Internet-Draft standard by the Internet Engineering Task Force (IETF)[here] related to "Hashing to Elliptic Curves". In this case we hash a value into a scalar value, and also into a point using the Krytology Golang library:
Hash to Scalar and to Point using Kryptology |
Outline
For the hashing of our data to a scalar, we use the ExpandMessageXmd function. This produces a uniformly random byte string using a cryptographic hash function \(H()\) that outputs \(b\) bits. Overall we typically use SHA-256 or SHA-512 for the hashing function. As an input we use a message string and a DST (Domain Separation Tag) string. The method defined [here]:
expand_message_xmd(msg, DST, len_in_bytes) Parameters: - H, a hash function (see requirements above). - b_in_bytes, b / 8 for b the output size of H in bits. For example, for b = 256, b_in_bytes = 32. - s_in_bytes, the input block size of H, measured in bytes (see discussion above). For example, for SHA-256, s_in_bytes = 64. Input: - msg, a byte string. - DST, a byte string of at most 255 bytes. See below for information on using longer DSTs. - len_in_bytes, the length of the requested output in bytes, not greater than the lesser of (255 * b_in_bytes) or 2^16-1. Output: - uniform_bytes, a byte string. Steps: 1. ell = ceil(len_in_bytes / b_in_bytes) 2. ABORT if ell > 255 3. DST_prime = DST || I2OSP(len(DST), 1) 4. Z_pad = I2OSP(0, s_in_bytes) 5. l_i_b_str = I2OSP(len_in_bytes, 2) 6. msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime 7. b_0 = H(msg_prime) 8. b_1 = H(b_0 || I2OSP(1, 1) || DST_prime) 9. for i in (2, ..., ell): 10. b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime) 11. uniform_bytes = b_1 || ... || b_ell 12. return substr(uniform_bytes, 0, len_in_bytes)
The DST is selected which is unique to the domain, and which will include the Suite ID. The format for this is:
// Suite ID: CURVE_ID || "_" || HASH_ID || "_" || MAP_ID || "_" || ENC_VAR || "_"
and where:
HASH_ID is EXP_TAG || ":" || HASH_NAME EXP_TAG, we have "XMD" for expand_message_xmd MAP_ID - "SSWU" for Simplified SWU (Map-to-curve method) ENC_VAR is "RO" for hash_to_curve, and "NU", is encode_to_curve..
Using a DST string of "P256_XMD:SHA-256_SSWU_RO_", the Golang call for the Kryptography library, and for 48 byte output is:
xmd, _ := core.ExpandMessageXmd(sha256.New, msg, []byte("P256_XMD:SHA-256_SSWU_RO_"), 48)
After this, we convert xmd into a Big Integer:
v := new(big.Int).SetBytes(xmd)
And then calculate this value modulo of the order of the curve:
res := v.Mod(v, elliptic.P256().Params().N)
Coding
We can use the Kryptology library developed by Coinbase to implement the matching:
package main import ( "crypto/elliptic" "crypto/sha256" "fmt" "math/big" "os" "strings" "github.com/btcsuite/btcd/btcec" "github.com/coinbase/kryptology/pkg/core" "github.com/coinbase/kryptology/pkg/core/curves" ) func getCurve(s string) (*curves.Curve, *big.Int, string) { if strings.Contains(s, "p256") { return curves.P256(), elliptic.P256().Params().N, "P256_XMD:SHA-256_SSWU_RO_" } else if strings.Contains(s, "k256") { return curves.K256(), btcec.S256().N, "secp256k1_XMD:SHA-256_SSWU_RO_" } else if strings.Contains(s, "25519") { return curves.ED25519(), nil, "" } else if strings.Contains(s, "G1") { return curves.BLS12381G1(), nil, "" } else if strings.Contains(s, "G2") { return curves.BLS12381G2(), nil, "" } else if strings.Contains(s, "PALLAS") { return curves.PALLAS(), nil, "" } return curves.K256(), btcec.S256().N, "secp256k1_XMD:SHA-256_SSWU_RO_" // Suite ID: CURVE_ID || "_" || HASH_ID || "_" || MAP_ID || "_" || ENC_VAR || "_" // where: HASH_ID is EXP_TAG || ":" || HASH_NAME // With EXP_TAG, we have "XMD" for expand_message_xmd // MAP_ID - "SSWU" for Simplified SWU (Map-to-curve method) // ENC_VAR is "RO" for hash_to_curve, and "NU", is encode_to_curve. } func main() { m := "abc" ctype := "k256" argCount := len(os.Args[1:]) if argCount > 0 { m = os.Args[1] } if argCount > 1 { ctype = strings.ToLower(os.Args[2]) } msg := []byte(m) curve, N, DST := getCurve(ctype) toPoint := curve.Point.Hash(msg[:]) fmt.Printf("Curve type: [%s]\n", curve.Name) fmt.Printf("Message: [%s]\n", msg) fmt.Printf("\n=== Hash to scalar ===\n") toScalar := curve.Scalar.Hash(msg[:]) fmt.Printf("Scalar: %x\n", toScalar.Bytes()) fmt.Printf(" Scalar: %s\n", toScalar.BigInt()) if strings.Contains(ctype, "256") { fmt.Printf("=== Checking answer with Xmd ===\n") xmd, _ := core.ExpandMessageXmd(sha256.New, msg[:], []byte(DST), 48) v := new(big.Int).SetBytes(xmd) res := v.Mod(v, N) fmt.Printf("xmd: %x\n", xmd) fmt.Printf("Scalar: %x\n", res.Bytes()) fmt.Printf(" Scalar: %s\n", res) } fmt.Printf("\n=== Hash to point ===\n") fmt.Printf("Point: %x\n", toPoint.ToAffineUncompressed()) if strings.Contains(ctype, "256") { fmt.Printf("X: %x\n", toPoint.ToAffineUncompressed()[1:33]) fmt.Printf("Y: %x\n", toPoint.ToAffineUncompressed()[33:]) } else { lenb := len(toPoint.ToAffineUncompressed()) fmt.Printf("X: %x\n", toPoint.ToAffineUncompressed()[0:lenb/2]) fmt.Printf("Y: %x\n", toPoint.ToAffineUncompressed()[lenb/2:lenb]) } }
A sample run:
Curve type: [P-256] Message: [abc] === Hash to scalar === Scalar: a9c116c8ec12c43020380c1fb94df0d230031a3eae63c91bee6bb0d99e5c7144 Scalar: 76782030149344631499467647523783879996886697622068133520146022456512145551684 === Checking answer with Xmd === Scalar: a9c116c8ec12c43020380c1fb94df0d230031a3eae63c91bee6bb0d99e5c7144 Scalar: 76782030149344631499467647523783879996886697622068133520146022456512145551684 === Hash to point === Point: 04caf6a25d6ef35978898e2e3e8ba602deac6ca818a1fc1c96976f87a6fe24e002c0ae4e1e7baa98bbd3fc7eaccd42e965920f58acda1f8152426ab501f72625d8 X: caf6a25d6ef35978898e2e3e8ba602deac6ca818a1fc1c96976f87a6fe24e002 Y: c0ae4e1e7baa98bbd3fc7eaccd42e965920f58acda1f8152426ab501f72625d8