fors.go

package slhdsa

// See FIPS 205 -- Section 8
// Forest of Random Subsets (FORS) is a few-time signature scheme that is
// used to sign the digests of the actual messages.

type (
	forsPublicKey  []byte     // n bytes
	forsPrivateKey []byte     // n bytes
	forsSignature  []forsPair // k*forsPairSize() bytes
	forsPair       struct {
		sk   forsPrivateKey // forsSkSize() bytes
		auth [][]byte       // a*n bytes
	} // forsSkSize() + a*n bytes
)

func (p *params) forsMsgSize() uint32  { return (p.k*p.a + 7) / 8 }
func (p *params) forsPkSize() uint32   { return p.n }
func (p *params) forsSkSize() uint32   { return p.n }
func (p *params) forsSigSize() uint32  { return p.k * p.forsPairSize() }
func (p *params) forsPairSize() uint32 { return p.forsSkSize() + p.a*p.n }

func (fs *forsSignature) fromBytes(p *params, c *cursor) {
	*fs = make([]forsPair, p.k)
	for i := range *fs {
		(*fs)[i].fromBytes(p, c)
	}
}

func (fp *forsPair) fromBytes(p *params, c *cursor) {
	fp.sk = c.Next(p.forsSkSize())
	fp.auth = make([][]byte, p.a)
	for i := range fp.auth {
		fp.auth[i] = c.Next(p.n)
	}
}

// See FIPS 205 -- Section 8.1 -- Algorithm 14.
func (s *statePriv) forsSkGen(addr address, idx uint32) forsPrivateKey {
	s.PRF.address.Set(addr)
	s.PRF.address.SetTypeAndClear(addressForsPrf)
	s.PRF.address.SetKeyPairAddress(addr.GetKeyPairAddress())
	s.PRF.address.SetTreeIndex(idx)

	return s.PRF.Final()
}

// See FIPS 205 -- Section 8.2 -- Algorithm 15 -- Iterative version.
//
// This is a stack-based implementation that computes the tree leaves
// in order (from the left to the right).
// Its recursive version can be found at fors_test.go file.
func (s *statePriv) forsNodeIter(
	stack stackNode, root []byte, i, z uint32, addr address,
) {
	if !(z <= s.a && i < s.k<<(s.a-z)) {
		panic(ErrTree)
	}

	s.F.address.Set(addr)
	s.F.address.SetTreeHeight(0)

	s.H.address.Set(addr)

	twoZ := uint32(1) << z
	iTwoZ := i << z
	for k := range twoZ {
		li := iTwoZ + k
		lz := uint32(0)

		sk := s.forsSkGen(addr, li)
		s.F.address.SetTreeIndex(li)
		s.F.SetMessage(sk)
		node := s.F.Final()

		for !stack.isEmpty() && stack.top().z == lz {
			left := stack.pop()
			li = (li - 1) >> 1
			lz = lz + 1

			s.H.address.SetTreeHeight(lz)
			s.H.address.SetTreeIndex(li)
			s.H.SetMsgs(left.node, node)
			node = s.H.Final()
		}

		stack.push(item{node, lz})
	}

	copy(root, stack.pop().node)
}

// See FIPS 205 -- Section 8.3 -- Algorithm 16.
func (s *statePriv) forsSign(sig forsSignature, digest []byte, addr address) {
	stack := s.NewStack(s.a - 1)
	defer stack.Clear()

	in, bits, total := 0, uint32(0), uint32(0)
	maskA := (uint32(1) << s.a) - 1

	for i := range s.k {
		for bits < s.a {
			total = (total << 8) + uint32(digest[in])
			in++
			bits += 8
		}

		bits -= s.a
		indicesI := (total >> bits) & maskA
		treeIdx := (i << s.a) + indicesI
		forsSk := s.forsSkGen(addr, treeIdx)
		copy(sig[i].sk, forsSk)

		for j := range s.a {
			shift := (indicesI >> j) ^ 1
			s.forsNodeIter(stack, sig[i].auth[j], (i<<(s.a-j))+shift, j, addr)
		}
	}
}

// See FIPS 205 -- Section 8.4 -- Algorithm 17.
func (s *state) forsPkFromSig(
	sig forsSignature, digest []byte, addr address,
) (pk forsPublicKey) {
	pk = make([]byte, s.forsPkSize())

	s.F.address.Set(addr)
	s.F.address.SetTreeHeight(0)

	s.H.address.Set(addr)

	s.T.address.Set(addr)
	s.T.address.SetTypeAndClear(addressForsRoots)
	s.T.address.SetKeyPairAddress(addr.GetKeyPairAddress())
	s.T.Reset()

	in, bits, total := 0, uint32(0), uint32(0)
	maskA := (uint32(1) << s.a) - 1

	for i := range s.k {
		for bits < s.a {
			total = (total << 8) + uint32(digest[in])
			in++
			bits += 8
		}

		bits -= s.a
		indicesI := (total >> bits) & maskA
		treeIdx := (i << s.a) + indicesI
		s.F.address.SetTreeIndex(treeIdx)
		s.F.SetMessage(sig[i].sk)
		node := s.F.Final()

		for j := range s.a {
			if (indicesI>>j)&0x1 == 0 {
				treeIdx = treeIdx >> 1
				s.H.SetMsgs(node, sig[i].auth[j])
			} else {
				treeIdx = (treeIdx - 1) >> 1
				s.H.SetMsgs(sig[i].auth[j], node)
			}

			s.H.address.SetTreeHeight(j + 1)
			s.H.address.SetTreeIndex(treeIdx)
			node = s.H.Final()
		}

		s.T.WriteMessage(node)
	}

	copy(pk, s.T.Final())
	return pk
}