<|start_filename|>go/vrf/ecvrf_p256_sha256_tai.go<|end_filename|>
// Copyright 2020 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package vrf

import (
	"bytes"
	"crypto"
	"crypto/elliptic"
	"crypto/hmac"
	"fmt"
	"math"
	"math/big"

	_ "crypto/sha256"
)

type (
	p256SHA256TAISuite struct{ *ECVRFParams }
	p256SHA256TAIAux   struct{ params *ECVRFParams }
)

var p256SHA256TAI p256SHA256TAISuite

func initP256SHA256TAI() {
	// https://tools.ietf.org/html/draft-irtf-cfrg-vrf-06#section-5.5
	p := &ECVRFParams{
		suite:    0x01,            // int_to_string(1, 1)
		ec:       elliptic.P256(), // NIST P-256 elliptic curve, [FIPS-186-4] (Section D.1.2.3).
		fieldLen: 32,              // Params().BitSize / 8 = 2n. Must be a multiple of 2.
		qLen:     32,              // Params().N.BitLen
		ptLen:    33,              // Size of encoded EC point
		cofactor: big.NewInt(1),
		hash:     crypto.SHA256,
	}
	p.aux = p256SHA256TAIAux{params: p}
	p256SHA256TAI.ECVRFParams = p
}

// Params returns the parameters for the ECVRF.
func (s p256SHA256TAISuite) Params() *ECVRFParams {
	return s.ECVRFParams
}

// PointToString converts an EC point to an octet string according to
// the encoding specified in Section 2.3.3 of [SECG1] with point
// compression on.  This implies ptLen = 2n + 1 = 33.
func (a p256SHA256TAIAux) PointToString(Px, Py *big.Int) []byte {
	return marshalCompressed(a.params.ec, Px, Py)
}

// String2Point converts an octet string to an EC point according to the
// encoding specified in Section 2.3.4 of [SECG1].  This function MUST output
// INVALID if the octet string does not decode to an EC point.
// http://www.secg.org/sec1-v2.pdf
func (a p256SHA256TAIAux) StringToPoint(s []byte) (x, y *big.Int, err error) {
	x, y, err = unmarshalCompressed(a.params.ec, s)
	if err != nil {
		return nil, nil, err
	} else if x == nil {
		return nil, nil, errInvalidPoint
	}
	return x, y, nil
}

func (a p256SHA256TAIAux) IntToString(x *big.Int, xLen uint) []byte {
	return i2osp(x, xLen) // RFC8017 Section 4.1 (big endian representation)
}

// ArbitraryString2Point returns StringToPoint(0x02 || h).
// Attempts to interpret an arbitrary string as a compressed elliptic code point.
// The input h is a 32-octet string.  Returns either an EC point or "INVALID".
func (a p256SHA256TAIAux) ArbitraryStringToPoint(h []byte) (Px, Py *big.Int, err error) {
	if got, want := len(h), 32; got != want {
		return nil, nil, fmt.Errorf("len(s): %v, want %v", got, want)
	}
	return a.StringToPoint(append([]byte{0x02}, h...))
}

// GenerateNonce implements RFC 6979 section 3.2
//    Input:
//       sk - an ECVRF secret key
//       h  - an octet string
//
//    Output:
//       k - an integer between 1 and q-1
func (a p256SHA256TAIAux) GenerateNonce(sk *PrivateKey, h []byte) (k *big.Int) {
	m := h    // Input m is set equal to h_string
	x := sk.d // The secret key x is set equal to the VRF secret scalar x

	// The "suitable for DSA or ECDSA" check in step h.3 is omitted
	// The hash function H is Hash and its output length hlen is set as hLen*8
	hash := a.params.hash

	// The prime q is the same as in this specification
	q := sk.Params().N

	// qlen is the binary length of q, i.e., the smallest integer such that 2^qlen > q
	// All the other values and primitives as defined in [RFC6979]
	//
	// N, also known as q, is the order of the base point, which generates subgroup Gi.
	qlen := q.BitLen()

	//
	// RFC 6979 section 3.2
	//

	// a.  Process m through the hash function H, yielding: h1 = H(m)
	h1 := hash.New()
	h1.Write(m) // (h1 is a sequence of hlen bits).
	h1Digest := h1.Sum(nil)

	// b.  Set: V = 0x01 0x01 0x01 ... 0x01
	//     such that the length of V, in bits, is equal to 8*ceil(hlen/8).
	//     For instance, on an octet-based system, if H is SHA-256, then V
	//     is set to a sequence of 32 octets of value 1.
	V := bytes.Repeat([]byte{0x01}, hash.Size())

	// c.  Set: K = 0x00 0x00 0x00 ... 0x00
	//     such that the length of K, in bits, is equal to 8*ceil(hlen/8).
	K := make([]byte, hash.Size())

	// d.  Set: K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
	//     where '||' denotes concatenation.  In other words, we compute
	//     HMAC with key K, over the concatenation of the following, in
	//     order: the current value of V, a sequence of eight bits of value
	//     0, the encoding of the (EC)DSA private key x, and the hashed
	//     message (possibly truncated and extended as specified by the
	//     bits2octets transform).  The HMAC result is the new value of K.
	//     Note that the private key x is in the [1, q-1] range, hence a
	//     proper input for int2octets, yielding rlen bits of output, i.e.,
	//     an integral number of octets (rlen is a multiple of 8).
	hm := hmac.New(hash.New, K)
	hm.Write(V)
	hm.Write([]byte{0x00})
	hm.Write(int2octets(x, qlen))
	hm.Write(bits2octets(h1Digest, q))
	K = hm.Sum(nil)

	// e.  Set:
	//     V = HMAC_K(V)
	vm := hmac.New(hash.New, K)
	vm.Write(V)
	V = vm.Sum(nil)

	// f.  Set:
	//     K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
	//     Note that the "internal octet" is 0x01 this time.
	hm = hmac.New(hash.New, K)
	hm.Write(V)
	hm.Write([]byte{0x01})
	hm.Write(int2octets(x, qlen))
	hm.Write(bits2octets(h1Digest, q))
	K = hm.Sum(nil)

	// g.  Set:
	//     V = HMAC_K(V)
	vm = hmac.New(hash.New, K)
	vm.Write(V)
	V = vm.Sum(nil)

	// h.  Apply the following algorithm until a proper value is found for k:
	for {
		// 1.  Set T to the empty sequence.  The length of T (in bits) is
		//     denoted tlen; thus, at that point, tlen = 0.
		T := make([]byte, 0, qlen/8)
		//  2.  While tlen < qlen, do the following:
		for len(T) < qlen/8 {
			//         V = HMAC_K(V)
			vm = hmac.New(hash.New, K)
			vm.Write(V)
			V = vm.Sum(nil)
			//         T = T || V
			T = append(T, V...)
		}
		//  3.  Compute: k = bits2int(T)
		k := bits2int(T, qlen)
		one := big.NewInt(1)
		// If that value of k is within the [1,q-1] range, then the generation of k is finished.
		// (The "suitable for DSA or ECDSA" check in step h.3 is omitted.)
		if k.Cmp(one) >= 0 && k.Cmp(q) < 0 {
			return k
		}

		// Otherwise, compute:
		//    K = HMAC_K(V || 0x00)
		km := hmac.New(hash.New, K)
		km.Write(V)
		km.Write([]byte{0x00})
		K = km.Sum(nil)

		//    V = HMAC_K(V)
		km = hmac.New(hash.New, K)
		km.Write(V)
		V = km.Sum(nil)

		// and loop (try to generate a new T, and so on).
	}
}

var zero big.Int
var one = big.NewInt(1)

// HashToCurve implements the HashToCurveTryAndIncrement algorithm from section 5.4.1.1.
//
// The running time of this algorithm depends on alpha. For the ciphersuites
// specified in Section 5.5, this algorithm is expected to find a valid curve
// point after approximately two attempts (i.e., when ctr=1) on average.
//
// However, because the running time of algorithm depends on alpha, this
// algorithm SHOULD be avoided in applications where it is important that the
// VRF input alpha remain secret.
//
// Inputs:
// - `pub`   - public key, an EC point
// - `alpha` - value to be hashed, an octet string
// Output:
// - `H` - hashed value, a finite EC point in G
// - `ctr` - integer, number of suite byte, attempts to find a valid curve point
func (a p256SHA256TAIAux) HashToCurve(pub *PublicKey, alpha []byte) (Hx, Hy *big.Int) {
	Hx, Hy, _ = a.hashToCurve(pub, alpha)
	return
}

func (a p256SHA256TAIAux) hashToCurve(pub *PublicKey, alpha []byte) (Hx, Hy *big.Int, ctr uint8) {
	// 1.  ctr = 0
	ctr = 0
	// 2.  PK_string = point_to_string(pub)
	pkStr := a.PointToString(pub.X, pub.Y)

	// 3.  one_string = 0x01 = int_to_string(1, 1), a single octet with value 1

	// 4.  H = "INVALID"
	h := a.params.hash.New()

	// 5.  While H is "INVALID" or H is EC point at infinity:
	var err error
	for Hx == nil || err != nil || (zero.Cmp(Hx) == 0 && zero.Cmp(Hy) == 0) {
		// A. ctr_string = int_to_string(ctr, 1)
		// B.  hash_string = Hash(suite_string || one_string ||
		//     PK_string || alpha_string || ctr_string)
		h.Reset()
		h.Write([]byte{a.params.suite, 0x01})
		h.Write(pkStr)
		h.Write(alpha)
		h.Write([]byte{ctr}) // ctr_string = int_to_string(ctr, 1)
		hashString := h.Sum(nil)
		// C.  H = arbitrary_string_to_point(hash_string)
		Hx, Hy, err = a.ArbitraryStringToPoint(hashString)
		// D.  If H is not "INVALID" and cofactor > 1, set H = cofactor * H
		// Cofactor for prime ordered curves is 1.
		if err == nil && a.params.cofactor.Cmp(one) > 0 {
			Hx, Hy = a.params.ec.ScalarMult(Hx, Hy, a.params.cofactor.Bytes())
		}
		if ctr == math.MaxUint8 {
			panic("HashToCurveTAI ctr overflow")
		}
		ctr++
	}
	ctr--
	// 6.  Output H
	return Hx, Hy, ctr
}


<|start_filename|>go/vrf/conversion_test.go<|end_filename|>
// Copyright 2020 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package vrf

import (
	"bytes"
	"fmt"
	"math/big"
	"testing"
)

func TestI2OSP(t *testing.T) {
	for i, tc := range []struct {
		x         int64
		xLen      uint
		want      []byte
		wantPanic bool
	}{
		{x: 1, xLen: 1, want: []byte{0x01}},
		{x: 2, xLen: 1, want: []byte{0x02}},
		{x: 2, xLen: 2, want: []byte{0, 2}},
		{x: 256, xLen: 8, want: []byte{0, 0, 0, 0, 0, 0, 1, 0}},
		{x: 256, xLen: 1, wantPanic: true},
		{x: 255, xLen: 1, want: []byte{0xff}},
	} {
		t.Run(fmt.Sprintf("%v", i), func(t *testing.T) {
			defer func() {
				r := recover()
				if panicked := r != nil; panicked != tc.wantPanic {
					t.Errorf("Panicked: %v, wantPanic %v", r, tc.wantPanic)
				}
			}()
			if got := i2osp(big.NewInt(tc.x), tc.xLen); !bytes.Equal(got, tc.want) {
				t.Errorf("I2OSP(%v, %v): %v, want %v", tc.x, tc.xLen, got, tc.want)
			}
		})
	}
}

func TestBits2int(t *testing.T) {
	for _, tc := range []struct {
		b    []byte
		qlen int
		want *big.Int
	}{
		{b: []byte{0x01}, qlen: 1, want: big.NewInt(0)},
		{b: []byte{0x80}, qlen: 1, want: big.NewInt(1)}, // 1 leftmost bit is kept.
		{b: []byte{0x01}, qlen: 8, want: big.NewInt(1)},
		{b: []byte{0x01, 0x00}, qlen: 8, want: big.NewInt(1)}, // 8 leftmost bits are kept.
		{b: []byte{0x01, 0x00}, qlen: 16, want: big.NewInt(256)},
	} {
		if got := bits2int(tc.b, tc.qlen); got.Cmp(tc.want) != 0 {
			t.Errorf("bits2int(0x%x, %v): %v, want %v", tc.b, tc.qlen, got, tc.want)
		}
	}
}

func TestInt2octets(t *testing.T) {
	for _, tc := range []struct {
		x    *big.Int
		qlen int
		want []byte
	}{
		{x: big.NewInt(1), qlen: 0, want: []byte{}},
		{x: big.NewInt(1), qlen: 8, want: []byte{0x01}},
		{x: big.NewInt(1), qlen: 16, want: []byte{0x00, 0x01}},
	} {
		if got := int2octets(tc.x, tc.qlen); !bytes.Equal(got, tc.want) {
			t.Errorf("int2octets(%v, %d):0x%x, want 0x%x", tc.x, tc.qlen, got, tc.want)
		}
	}
}


<|start_filename|>go/vrf/eccmarshal_pre_go115.go<|end_filename|>
// Copyright 2020 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// +build !go1.15

// This file implements compressed point unmarshaling.
// This code will be in go 1.15
// Code borrowed from: https://github.com/golang/go/pull/35110

package vrf

import (
	"crypto/elliptic"
	"errors"
	"math/big"
)

// marshalCompressed converts an EC point to an octet string according to
// the encoding specified in Section 2.3.3 of [SECG1] with point compression
// on. If fieldLen = ceil(log_2(q) / 8) then ptLen = fieldLen + 1 = 33.
//
// SECG1 Section 2.3.3 https://www.secg.org/sec1-v1.99.dif.pdf
func marshalCompressed(curve elliptic.Curve, x, y *big.Int) []byte {
	byteLen := (curve.Params().BitSize + 7) >> 3
	compressed := make([]byte, 1+byteLen)
	compressed[0] = 2 // compressed point
	compressed[0] += byte(y.Bit(0))
	i := byteLen + 1 - len(x.Bytes())
	copy(compressed[i:], x.Bytes())
	return compressed
}

var errInvalidPoint = errors.New("invalid point")

// unmarshalCompressed decodes a EC point, given as a compressed string.
// If the decoding fails x and y will be nil.
//
// http://www.secg.org/sec1-v2.pdf
// https://tools.ietf.org/html/rfc8032#section-5.1.3
// Section 4.3.6 of ANSI X9.62.
func unmarshalCompressed(curve elliptic.Curve, data []byte) (x, y *big.Int, err error) {
	byteLen := (curve.Params().BitSize + 7) >> 3
	if data[0] != 2 && data[0] != 3 { // compressed form
		return nil, nil, errors.New("unrecognized point encoding")
	}
	if len(data) != 1+byteLen {
		return nil, nil, errors.New("invalid length for curve")
	}

	// Based on Routine 2.2.4 in NIST Mathematical routines paper
	x = new(big.Int).SetBytes(data[1:])
	y2 := polynomial(curve.Params(), x)
	y = new(big.Int).ModSqrt(y2, curve.Params().P)
	if y == nil {
		return nil, nil, errInvalidPoint // "y^2" is not a square
	}
	if !curve.IsOnCurve(x, y) {
		return nil, nil, errInvalidPoint
	}
	if y.Bit(0) != uint(data[0]&0x01) {
		y.Sub(curve.Params().P, y)
	}

	return x, y, nil // valid point: return x,y
}

// polynomial returns x³ - 3x + b.
func polynomial(curve *elliptic.CurveParams, x *big.Int) *big.Int {
	x3 := new(big.Int).Mul(x, x)
	x3.Mul(x3, x)

	threeX := new(big.Int).Lsh(x, 1)
	threeX.Add(threeX, x)
	x3.Sub(x3, threeX)

	x3.Add(x3, curve.B)
	x3.Mod(x3, curve.P)
	return x3
}


<|start_filename|>go/vrf/eccmarshal_pre_go115_test.go<|end_filename|>
// Copyright 2020 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// +build !go1.15

package vrf

import (
	"bytes"
	"crypto/elliptic"
	"crypto/rand"
	"crypto/x509/pkix"
	"encoding/asn1"
	"encoding/hex"
	"errors"
	"fmt"
	"testing"
)

func TestCompressedMarshalUnmarshal(t *testing.T) {
	c := elliptic.P256()
	_, Ax, Ay, err := elliptic.GenerateKey(c, rand.Reader)
	if err != nil {
		t.Fatal(err)
	}

	b := marshalCompressed(c, Ax, Ay)
	Bx, By, err := unmarshalCompressed(c, b)
	if err != nil {
		t.Fatal(err)
	}
	if Bx.Cmp(Ax) != 0 {
		t.Fatalf("Bx: %v, want %v", Bx, Ax)
	}
	if By.Cmp(Ay) != 0 {
		t.Fatalf("By: %v, want %v", By, Ay)
	}
}

func hexd(t testing.TB, h string) []byte {
	t.Helper()
	b, err := hex.DecodeString(h)
	if err != nil {
		t.Fatal(err)
	}
	return b
}

// https://github.com/google/wycheproof/blob/master/testvectors/ecdh_secp256r1_test.json
func TestWycheproof(t *testing.T) {
	curve := elliptic.P256() //secp256r1
	for _, tc := range []struct {
		tcID    int
		comment string
		public  []byte
		private []byte
		shared  []byte
		result  error
	}{

		{
			tcID:    2,
			comment: "compressed public key",
			public:  hexd(t, "3039301306072a8648ce3d020106082a8648ce3d0301070322000362d5bd3372af75fe85a040715d0f502428e07046868b0bfdfa61d731afe44f26"),
			private: hexd(t, "<KEY>"),
			shared:  hexd(t, "<KEY>"),
			result:  nil,
		},
		{
			tcID:    243,
			comment: "invalid public key",
			public:  hexd(t, "3039301306072a8648ce3d020106082a8648ce3d03010703220002fd4bf61763b46581fd9174d623516cf3c81edd40e29ffa2777fb6cb0ae3ce535"),
			private: hexd(t, "<KEY>"),
			result:  errInvalidPoint,
		},
		{
			tcID:    244,
			comment: "public key is a low order point on twist",
			public:  hexd(t, "3039301306072a8648ce3d020106082a8648ce3d03010703220003efdde3b32872a9effcf3b94cbf73aa7b39f9683ece9121b9852167f4e3da609b"),
			private: hexd(t, "00d27edf0ff5b6b6b465753e7158370332c153b468a1be087ad0f490bdb99e5f02"),
			result:  errInvalidPoint,
		},
		{
			tcID:    245,
			comment: "public key is a low order point on twist",
			public:  hexd(t, "3039301306072a8648ce3d020106082a8648ce3d03010703220002efdde3b32872a9effcf3b94cbf73aa7b39f9683ece9121b9852167f4e3da609b"),
			private: hexd(t, "00d27edf0ff5b6b6b465753e7158370332c153b468a1be087ad0f490bdb99e5f03"),
			result:  errInvalidPoint,
		},
		{
			tcID:    246,
			comment: "public key is a low order point on twist",
			public:  hexd(t, "3039301306072a8648ce3d020106082a8648ce3d03010703220002c49524b2adfd8f5f972ef554652836e2efb2d306c6d3b0689234cec93ae73db5"),
			private: hexd(t, "0095ead84540c2d027aa3130ff1b47888cc1ed67e8dda46156e71ce0991791e835"),
			result:  errInvalidPoint,
		},
		{
			tcID:    247,
			comment: "public key is a low order point on twist",
			public:  hexd(t, "3039301306072a8648ce3d020106082a8648ce3d0301070322000318f9bae7747cd844e98525b7ccd0daf6e1d20a818b2175a9a91e4eae5343bc98"),
			private: hexd(t, "00a8681ef67fb1f189647d95e8db00c52ceef6d41a85ba0a5bd74c44e8e62c8aa4"),
			result:  errInvalidPoint,
		},
		{
			tcID:    248,
			comment: "public key is a low order point on twist",
			public:  hexd(t, "3039301306072a8648ce3d020106082a8648ce3d0301070322000218f9bae7747cd844e98525b7ccd0daf6e1d20a818b2175a9a91e4eae5343bc98"),
			private: hexd(t, "00a8681ef67fb1f189647d95e8db00c52ceef6d41a85ba0a5bd74c44e8e62c8aa5"),
			result:  errInvalidPoint,
		},
		{
			tcID:    249,
			comment: "public key is a low order point on twist",
			public:  hexd(t, "3039301306072a8648ce3d020106082a8648ce3d03010703220003c49524b2adfd8f5f972ef554652836e2efb2d306c6d3b0689234cec93ae73db5"),
			private: hexd(t, "0095ead84540c2d027aa3130ff1b47888cc1ed67e8dda46156e71ce0991791e834"),
			result:  errInvalidPoint,
		},
	} {
		t.Run(fmt.Sprintf("%d", tc.tcID), func(t *testing.T) {
			t.Logf("comment: %s", tc.comment)

			// parse public key as x509 ASN.1
			var pki struct {
				Raw       asn1.RawContent
				Algorithm pkix.AlgorithmIdentifier
				PublicKey asn1.BitString
			}
			if _, err := asn1.Unmarshal(tc.public, &pki); err != nil {
				t.Fatal(err)
			}
			asn1Data := pki.PublicKey.RightAlign()
			t.Logf("public key: %x", asn1Data)

			x, y, err := unmarshalCompressed(curve, asn1Data)
			if !errors.Is(err, tc.result) {
				t.Errorf("got err %q, want %q", err, tc.result)
			}
			if err != nil {
				return
			}

			// Compute ECDH shared secret to complete the test
			Sx, _ := curve.ScalarMult(x, y, tc.private)
			if got := Sx.Bytes(); !bytes.Equal(got, tc.shared) {
				t.Errorf("shared secret: %x, want %x", got, tc.shared)
			}
		})
	}
}


<|start_filename|>go/vrf/conversion.go<|end_filename|>
// Copyright 2020 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package vrf

import (
	"bytes"
	"math/big"
)

// i2osp converts a nonnegative integer to an octet string of a specified length.
// RFC8017 section-4.1 (big endian representation)
func i2osp(x *big.Int, rLen uint) []byte {
	// 1.  If x >= 256^rLen, output "integer too large" and stop.
	upperBound := new(big.Int).Lsh(big.NewInt(1), rLen*8)
	if x.Cmp(upperBound) >= 0 {
		panic("integer too large")
	}
	// 2.  Write the integer x in its unique rLen-digit representation in base 256:
	//     x = x_(rLen-1) 256^(rLen-1) + x_(rLen-2) 256^(rLen-2) + ...  + x_1 256 + x_0,
	//     where 0 <= x_i < 256
	//     (note that one or more leading digits will be zero if x is less than 256^(rLen-1)).
	// 3.  Let the octet X_i have the integer value x_(rLen-i) for 1 <= i <= rLen.
	//     Output the octet string X = X_1 X_2 ... X_rLen.

	var b bytes.Buffer
	xLen := (uint(x.BitLen()) + 7) >> 3
	if rLen > xLen {
		b.Write(make([]byte, rLen-xLen)) // prepend 0s
	}
	b.Write(x.Bytes())
	return b.Bytes()[uint(b.Len())-rLen:] // The rightmost rLen bytes.
}

// bits2int takes as input a sequence of blen bits and outputs a non-negative
// integer that is less than 2^qlen.  bits2int operates on byte boundaries,
// meaning blen = 8*len(b). Returns the integer value of the qlen leftmost bits.
// https://tools.ietf.org/html/rfc6979#section-2.3.2
func bits2int(b []byte, qlen int) *big.Int {
	blen := len(b) * 8
	v := new(big.Int).SetBytes(b)
	// 1.  The sequence is first truncated or expanded to length qlen:
	if qlen < blen {
		// Truncate:
		// If qlen < blen, then the qlen leftmost bits are kept, and
		// subsequent bits are discarded;
		v = new(big.Int).Rsh(v, uint(blen-qlen))
	}
	// Expand: fill the high order bits with zeros. Happens by default.
	// otherwise, qlen-blen bits (of value zero) are added to the
	// left of the sequence (i.e., before the input bits in the
	// sequence order).

	// 2.  The resulting sequence is then converted to an integer value
	//     using the big-endian convention: if input bits are called b_0
	//     (leftmost) to b_(qlen-1) (rightmost), then the resulting value
	//     is: b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0
	return v
}

// int2octets returns x as a sequence of rlen bits.
// int2octets deviates from x.Bytes() by returning a byte slice of exact length.
//
// x is an integer value less than q (and, in particular, a value that has been
// taken modulo q) as sequence of rlen bits, where rlen = 8*ceil(qlen/8).  This
// is the sequence of bits obtained by big-endian encoding.  In other words,
// the sequence bits x_i (for i ranging from 0 to rlen-1) are such that:
//
//   x = x_0*2^(rlen-1) + x_1*2^(rlen-2) + ... + x_(rlen-1)
//
// Since rlen is a multiple of 8 (the smallest multiple of 8 that is not
// smaller than qlen), then the resulting sequence of bits is also a sequence
// of octets, hence the name int2octets.
//
// https://tools.ietf.org/html/rfc6979#section-2.3.3
func int2octets(x *big.Int, qlen int) []byte {
	rlen := 8 * ((qlen + 7) >> 3) // rlen = 8*ceil(qlen/8)
	b := x.Bytes()
	blen := len(b) * 8
	if blen < rlen {
		// left pad with rlen - blen bits
		b = append(make([]byte, (rlen-blen)/8), b...)
	}
	if blen > rlen {
		// truncate to blen bits
		b = b[:rlen/8]
	}
	return b
}

//  bits2octets takes as input a sequence of blen bits and outputs a sequence
//  of rlen = 8*ceil(qlen/8) bits.
//
// https://datatracker.ietf.org/doc/html/rfc6979#section-2.3.4
func bits2octets(b []byte, q *big.Int) []byte {
	//  1.  The input sequence b is converted into an integer value z1 through the bits2int transform:
	z1 := bits2int(b, q.BitLen())
	//  2.  z1 is reduced modulo q, yielding z2 (an integer between 0 and q-1, inclusive):
	z2 := new(big.Int).Mod(z1, q)

	// Note that since z1 is less than 2^qlen, that modular reduction
	// can be implemented with a simple conditional subtraction:
	// z2 = z1-q if that value is non-negative; otherwise, z2 = z1.

	// 3.  z2 is transformed into a sequence of octets (a sequence of rlen bits) by applying int2octets.
	return int2octets(z2, q.BitLen())
}
