Hashing Data To A Scalar and to a Point in ECC

Hashing Data To A Scalar and to a Point in ECC

One of the great advancements with the Internet has been RFC (Request For Comment) documents and Internet Engineering Task Force (IETF) Internet-Drafts. The classics of such as RFC791 (IPv6) and RFC793 (TCP) brought a level of conformity that broke the dominance of large companies and countries in defining standards.

A new Internet-Draft [here] brings a new standardization for hashing data values into curves. This can be in the form of hashing a value to a scalar — which might then be used to multiply a point — or onto a curve:

Its importance is due to the increasing usage of elliptic curve methods and their application into zero-knowledge proofs (ZKPs) and multiparty computation (MPC).

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 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)

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)

We can use the Kryptology library developed by Coinbase to implement the matching [here]:

package main

import (
	"crypto/elliptic"
	"crypto/sha256"
	"fmt"
	"math/big"
	"os"
	"strings"

	"github.com/coinbase/kryptology/pkg/core"
	"github.com/coinbase/kryptology/pkg/core/curves"
)

func getCurve(s string) *curves.Curve {

	if strings.Contains(s, "p256") {
		return curves.P256()
	} else if strings.Contains(s, "k256") {
		return curves.K256()
	} else if strings.Contains(s, "pallas") {
		return curves.PALLAS()
	} else if strings.Contains(s, "ed25519") {
		return curves.ED25519()
	} else if strings.Contains(s, "bls12381g1") {
		return curves.BLS12381G1()
	} else if strings.Contains(s, "bls12381g2") {
		return curves.BLS12381G2()
	}
	return curves.K256()
} 

func main() {

	m := "abc"
	ctype := "secp256k1"

	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 := 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())

	fmt.Printf("=== Checking answer with Xmd ===\n")
	xmd, _ := core.ExpandMessageXmd(sha256.New, msg, []byte("P256_XMD:SHA-256_SSWU_RO_"), 48)

	v := new(big.Int).SetBytes(xmd)
	res := v.Mod(v, elliptic.P256().Params().N)
	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 [here]:

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

Conclusions

So, say thank you to RFCs and Internet-Drafts for the ability for systems to intercommunicate. The new hashing standard for hashing to scalars and curves is interesting, especially in their applications to privacy and resilience.