k = (c mod (n − 1)) + 1, without using `math/big`

nsareduce.go

// Copyright (c) 2023 Yawning Angel. All Rights Reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
// COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
// OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
// TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
// DAMAGE.

package main

import (
	"encoding/hex"
	"errors"
	"fmt"
	"math/big"

	"gitlab.com/yawning/secp256k1-voi"
)

var (
	scOne            = secp256k1.NewScalarFromUint64(1)
	scTwo            = secp256k1.NewScalarFromUint64(2)
	errInvalidScalar = errors.New("invalid raw scalar bytes")
)

func NSAReduceScalar(b []byte) (*secp256k1.Scalar, error) {
	if len(b) != secp256k1.ScalarSize {
		return nil, errInvalidScalar
	}

	// The NSA's prefered method for converting random raw bytes to
	// a scalar per "Suite B Implementer’s Guide to FIPS 186-3", A.2.1
	// is `k = (c mod (n − 1)) + 1`, but the scalar implementation
	// only provides "reduce mod N".
	//
	// Assuming `reducedSc` is `c % N`:
	// - c in [0, N-2]     -> reducedSc + 1
	// - c in [N-1, 2^256) -> reducedSc + 2

	sc, didReduce := secp256k1.NewScalarFromBytes((*[secp256k1.ScalarSize]byte)(b))
	addend := secp256k1.NewScalar().ConditionalSelect(scOne, scTwo, didReduce)
	sc.Add(sc, addend)

	// We are left with one exceptional case to check for, which is if
	// c originally was `N-1`, as `didReduce` would be `0` since we
	// reduced mod N.
	//
	// This is trivial to detect as `((N-1) % N) + 1 = 0`, so a final
	// conditional select handles this case.

	sc.ConditionalSelect(sc, scOne, sc.IsZero())

	return sc, nil
}

func NSAReduceBig(b []byte) *big.Int {
	// Cribbed from:
	// https://github.com/golang/go/blob/0380c9ad38843d523d9c9804fe300cb7edd7cd3c/src/crypto/ecdsa/ecdsa.go#L89-L101

	var (
		one  = new(big.Int).SetInt64(1)
		N, _ = new(big.Int).SetString(
			"0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
			0,
		)
	)

	k := new(big.Int).SetBytes(b)
	n := new(big.Int).Sub(N, one)
	k.Mod(k, n)
	k.Add(k, one)

	return k
}

func main() {
	for idx, tc := range []struct {
		n  string
		c  string
		sc string
	}{
		{
			"0",
			"0000000000000000000000000000000000000000000000000000000000000000",
			"0000000000000000000000000000000000000000000000000000000000000001",
		},
		{
			"N-2",
			"fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413f",
			"fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
		},
		{
			"N-1",
			"fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140",
			"0000000000000000000000000000000000000000000000000000000000000001",
		},
		{
			"N",
			"fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
			"0000000000000000000000000000000000000000000000000000000000000002",
		},
		{
			"N+1",
			"fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142",
			"0000000000000000000000000000000000000000000000000000000000000003",
		},
		{
			"2^-256-1",
			"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
			"000000000000000000000000000000014551231950b75fc4402da1732fc9bec0",
		},
	} {
		b, err := hex.DecodeString(tc.c)
		if err != nil {
			panic(err)
		}
		sc, err := NSAReduceScalar(b)
		if err != nil {
			panic(err)
		}

		scBig := NSAReduceBig(b)
		bigBytes := make([]byte, 32)
		bigBytes = scBig.FillBytes(bigBytes)

		scStr := hex.EncodeToString(sc.Bytes())
		scBigStr := hex.EncodeToString(bigBytes)

		fmt.Printf("case [%d] - '%s'\n", idx, tc.n)
		fmt.Printf("      expected: %s\n", tc.sc)
		fmt.Printf(" scalar reduce: %s\n", scStr)
		fmt.Printf("    big reduce: %s\n", scBigStr)
		if scStr != scBigStr || scStr != tc.sc {
			panic("mismatch!")
		}
	}
}