| // Copyright 2025 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package mldsa |
| |
| import ( |
| "bytes" |
| "crypto/internal/fips140" |
| "crypto/internal/fips140/drbg" |
| "crypto/internal/fips140/sha3" |
| "crypto/internal/fips140/subtle" |
| "crypto/internal/fips140deps/byteorder" |
| "errors" |
| ) |
| |
| type parameters struct { |
| k, l int // dimensions of A |
| η int // bound for secret coefficients |
| γ1 int // log₂(γ₁), where [-γ₁+1, γ₁] is the bound of y |
| γ2 int // denominator of γ₂ = (q - 1) / γ2 |
| λ int // collison strength |
| τ int // number of non-zero coefficients in challenge |
| ω int // max number of hints in MakeHint |
| } |
| |
| var ( |
| params44 = parameters{k: 4, l: 4, η: 2, γ1: 17, γ2: 88, λ: 128, τ: 39, ω: 80} |
| params65 = parameters{k: 6, l: 5, η: 4, γ1: 19, γ2: 32, λ: 192, τ: 49, ω: 55} |
| params87 = parameters{k: 8, l: 7, η: 2, γ1: 19, γ2: 32, λ: 256, τ: 60, ω: 75} |
| ) |
| |
| func pubKeySize(p parameters) int { |
| // ρ + k × n × 10-bit coefficients of t₁ |
| return 32 + p.k*n*10/8 |
| } |
| |
| func sigSize(p parameters) int { |
| // challenge + l × n × (γ₁+1)-bit coefficients of z + hint |
| return (p.λ / 4) + p.l*n*(p.γ1+1)/8 + p.ω + p.k |
| } |
| |
| const ( |
| PrivateKeySize = 32 |
| |
| PublicKeySize44 = 32 + 4*n*10/8 |
| PublicKeySize65 = 32 + 6*n*10/8 |
| PublicKeySize87 = 32 + 8*n*10/8 |
| |
| SignatureSize44 = 128/4 + 4*n*(17+1)/8 + 80 + 4 |
| SignatureSize65 = 192/4 + 5*n*(19+1)/8 + 55 + 6 |
| SignatureSize87 = 256/4 + 7*n*(19+1)/8 + 75 + 8 |
| ) |
| |
| const maxK, maxL, maxλ, maxγ1 = 8, 7, 256, 19 |
| const maxPubKeySize = PublicKeySize87 |
| |
| type PrivateKey struct { |
| seed [32]byte |
| pub PublicKey |
| s1 [maxL]nttElement |
| s2 [maxK]nttElement |
| t0 [maxK]nttElement |
| k [32]byte |
| } |
| |
| func (priv *PrivateKey) Equal(x *PrivateKey) bool { |
| return priv.pub.p == x.pub.p && subtle.ConstantTimeCompare(priv.seed[:], x.seed[:]) == 1 |
| } |
| |
| func (priv *PrivateKey) Bytes() []byte { |
| seed := priv.seed |
| return seed[:] |
| } |
| |
| func (priv *PrivateKey) PublicKey() *PublicKey { |
| // Note that this is likely to keep the entire PrivateKey reachable for |
| // the lifetime of the PublicKey, which may be undesirable. |
| return &priv.pub |
| } |
| |
| type PublicKey struct { |
| raw [maxPubKeySize]byte |
| p parameters |
| a [maxK * maxL]nttElement |
| t1 [maxK]nttElement // NTT(t₁ ⋅ 2ᵈ) |
| tr [64]byte // public key hash |
| } |
| |
| func (pub *PublicKey) Equal(x *PublicKey) bool { |
| size := pubKeySize(pub.p) |
| return pub.p == x.p && subtle.ConstantTimeCompare(pub.raw[:size], x.raw[:size]) == 1 |
| } |
| |
| func (pub *PublicKey) Bytes() []byte { |
| size := pubKeySize(pub.p) |
| return bytes.Clone(pub.raw[:size]) |
| } |
| |
| func (pub *PublicKey) Parameters() string { |
| switch pub.p { |
| case params44: |
| return "ML-DSA-44" |
| case params65: |
| return "ML-DSA-65" |
| case params87: |
| return "ML-DSA-87" |
| default: |
| panic("mldsa: internal error: unknown parameters") |
| } |
| } |
| |
| func GenerateKey44() *PrivateKey { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| var seed [32]byte |
| drbg.Read(seed[:]) |
| priv := newPrivateKey(&seed, params44) |
| fipsPCT(priv) |
| return priv |
| } |
| |
| func GenerateKey65() *PrivateKey { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| var seed [32]byte |
| drbg.Read(seed[:]) |
| priv := newPrivateKey(&seed, params65) |
| fipsPCT(priv) |
| return priv |
| } |
| |
| func GenerateKey87() *PrivateKey { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| var seed [32]byte |
| drbg.Read(seed[:]) |
| priv := newPrivateKey(&seed, params87) |
| fipsPCT(priv) |
| return priv |
| } |
| |
| var errInvalidSeedLength = errors.New("mldsa: invalid seed length") |
| |
| func NewPrivateKey44(seed []byte) (*PrivateKey, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| if len(seed) != 32 { |
| return nil, errInvalidSeedLength |
| } |
| return newPrivateKey((*[32]byte)(seed), params44), nil |
| } |
| |
| func NewPrivateKey65(seed []byte) (*PrivateKey, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| if len(seed) != 32 { |
| return nil, errInvalidSeedLength |
| } |
| return newPrivateKey((*[32]byte)(seed), params65), nil |
| } |
| |
| func NewPrivateKey87(seed []byte) (*PrivateKey, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| if len(seed) != 32 { |
| return nil, errInvalidSeedLength |
| } |
| return newPrivateKey((*[32]byte)(seed), params87), nil |
| } |
| |
| func newPrivateKey(seed *[32]byte, p parameters) *PrivateKey { |
| k, l := p.k, p.l |
| |
| priv := &PrivateKey{pub: PublicKey{p: p}} |
| priv.seed = *seed |
| |
| ξ := sha3.NewShake256() |
| ξ.Write(seed[:]) |
| ξ.Write([]byte{byte(k), byte(l)}) |
| ρ, ρs := make([]byte, 32), make([]byte, 64) |
| ξ.Read(ρ) |
| ξ.Read(ρs) |
| ξ.Read(priv.k[:]) |
| |
| A := priv.pub.a[:k*l] |
| computeMatrixA(A, ρ, p) |
| |
| s1 := priv.s1[:l] |
| for r := range l { |
| s1[r] = ntt(sampleBoundedPoly(ρs, byte(r), p)) |
| } |
| s2 := priv.s2[:k] |
| for r := range k { |
| s2[r] = ntt(sampleBoundedPoly(ρs, byte(l+r), p)) |
| } |
| |
| // ˆt = Â ∘ ŝ₁ + ŝ₂ |
| tHat := make([]nttElement, k, maxK) |
| for i := range tHat { |
| tHat[i] = s2[i] |
| for j := range s1 { |
| tHat[i] = polyAdd(tHat[i], nttMul(A[i*l+j], s1[j])) |
| } |
| } |
| // t = NTT⁻¹(ˆt) |
| t := make([]ringElement, k, maxK) |
| for i := range tHat { |
| t[i] = inverseNTT(tHat[i]) |
| } |
| // (t₁, _) = Power2Round(t) |
| // (_, ˆt₀) = NTT(Power2Round(t)) |
| t1, t0 := make([][n]uint16, k, maxK), priv.t0[:k] |
| for i := range t { |
| var w ringElement |
| for j := range t[i] { |
| t1[i][j], w[j] = power2Round(t[i][j]) |
| } |
| t0[i] = ntt(w) |
| } |
| |
| // The computations below (and their storage in the PrivateKey struct) are |
| // not strictly necessary and could be deferred to PrivateKey.PublicKey(). |
| // That would require keeping or re-deriving ρ and t/t1, though. |
| |
| pk := pkEncode(priv.pub.raw[:0], ρ, t1, p) |
| priv.pub.tr = computePublicKeyHash(pk) |
| computeT1Hat(priv.pub.t1[:k], t1) // NTT(t₁ ⋅ 2ᵈ) |
| |
| return priv |
| } |
| |
| func computeMatrixA(A []nttElement, ρ []byte, p parameters) { |
| k, l := p.k, p.l |
| for r := range k { |
| for s := range l { |
| A[r*l+s] = sampleNTT(ρ, byte(s), byte(r)) |
| } |
| } |
| } |
| |
| func computePublicKeyHash(pk []byte) [64]byte { |
| H := sha3.NewShake256() |
| H.Write(pk) |
| var tr [64]byte |
| H.Read(tr[:]) |
| return tr |
| } |
| |
| func computeT1Hat(t1Hat []nttElement, t1 [][n]uint16) { |
| for i := range t1 { |
| var w ringElement |
| for j := range t1[i] { |
| // t₁ <= 2¹⁰ - 1 |
| // t₁ ⋅ 2ᵈ <= 2ᵈ(2¹⁰ - 1) = 2²³ - 2¹³ < q = 2²³ - 2¹³ + 1 |
| z, _ := fieldToMontgomery(uint32(t1[i][j]) << 13) |
| w[j] = z |
| } |
| t1Hat[i] = ntt(w) |
| } |
| } |
| |
| func pkEncode(buf []byte, ρ []byte, t1 [][n]uint16, p parameters) []byte { |
| pk := append(buf, ρ...) |
| for _, w := range t1[:p.k] { |
| // Encode four at a time into 4 * 10 bits = 5 bytes. |
| for i := 0; i < n; i += 4 { |
| c0 := w[i] |
| c1 := w[i+1] |
| c2 := w[i+2] |
| c3 := w[i+3] |
| b0 := byte(c0 >> 0) |
| b1 := byte((c0 >> 8) | (c1 << 2)) |
| b2 := byte((c1 >> 6) | (c2 << 4)) |
| b3 := byte((c2 >> 4) | (c3 << 6)) |
| b4 := byte(c3 >> 2) |
| pk = append(pk, b0, b1, b2, b3, b4) |
| } |
| } |
| return pk |
| } |
| |
| func pkDecode(pk []byte, t1 [][n]uint16, p parameters) (ρ []byte, err error) { |
| if len(pk) != pubKeySize(p) { |
| return nil, errInvalidPublicKeyLength |
| } |
| ρ, pk = pk[:32], pk[32:] |
| for r := range t1 { |
| // Decode four at a time from 4 * 10 bits = 5 bytes. |
| for i := 0; i < n; i += 4 { |
| b0, b1, b2, b3, b4 := pk[0], pk[1], pk[2], pk[3], pk[4] |
| t1[r][i+0] = uint16(b0>>0) | uint16(b1&0b0000_0011)<<8 |
| t1[r][i+1] = uint16(b1>>2) | uint16(b2&0b0000_1111)<<6 |
| t1[r][i+2] = uint16(b2>>4) | uint16(b3&0b0011_1111)<<4 |
| t1[r][i+3] = uint16(b3>>6) | uint16(b4&0b1111_1111)<<2 |
| pk = pk[5:] |
| } |
| } |
| return ρ, nil |
| } |
| |
| var errInvalidPublicKeyLength = errors.New("mldsa: invalid public key length") |
| |
| func NewPublicKey44(pk []byte) (*PublicKey, error) { |
| return newPublicKey(pk, params44) |
| } |
| |
| func NewPublicKey65(pk []byte) (*PublicKey, error) { |
| return newPublicKey(pk, params65) |
| } |
| |
| func NewPublicKey87(pk []byte) (*PublicKey, error) { |
| return newPublicKey(pk, params87) |
| } |
| |
| func newPublicKey(pk []byte, p parameters) (*PublicKey, error) { |
| k, l := p.k, p.l |
| |
| t1 := make([][n]uint16, k, maxK) |
| ρ, err := pkDecode(pk, t1, p) |
| if err != nil { |
| return nil, err |
| } |
| |
| pub := &PublicKey{p: p} |
| copy(pub.raw[:], pk) |
| computeMatrixA(pub.a[:k*l], ρ, p) |
| pub.tr = computePublicKeyHash(pk) |
| computeT1Hat(pub.t1[:k], t1) // NTT(t₁ ⋅ 2ᵈ) |
| |
| return pub, nil |
| } |
| |
| var ( |
| errContextTooLong = errors.New("mldsa: context too long") |
| errMessageHashLength = errors.New("mldsa: invalid message hash length") |
| errRandomLength = errors.New("mldsa: invalid random length") |
| ) |
| |
| func Sign(priv *PrivateKey, msg []byte, context string) ([]byte, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| var random [32]byte |
| drbg.Read(random[:]) |
| μ, err := computeMessageHash(priv.pub.tr[:], msg, context) |
| if err != nil { |
| return nil, err |
| } |
| return signInternal(priv, &μ, &random), nil |
| } |
| |
| func SignDeterministic(priv *PrivateKey, msg []byte, context string) ([]byte, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| var random [32]byte |
| μ, err := computeMessageHash(priv.pub.tr[:], msg, context) |
| if err != nil { |
| return nil, err |
| } |
| return signInternal(priv, &μ, &random), nil |
| } |
| |
| func TestingOnlySignWithRandom(priv *PrivateKey, msg []byte, context string, random []byte) ([]byte, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| μ, err := computeMessageHash(priv.pub.tr[:], msg, context) |
| if err != nil { |
| return nil, err |
| } |
| if len(random) != 32 { |
| return nil, errRandomLength |
| } |
| return signInternal(priv, &μ, (*[32]byte)(random)), nil |
| } |
| |
| func SignExternalMu(priv *PrivateKey, μ []byte) ([]byte, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| var random [32]byte |
| drbg.Read(random[:]) |
| if len(μ) != 64 { |
| return nil, errMessageHashLength |
| } |
| return signInternal(priv, (*[64]byte)(μ), &random), nil |
| } |
| |
| func SignExternalMuDeterministic(priv *PrivateKey, μ []byte) ([]byte, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| var random [32]byte |
| if len(μ) != 64 { |
| return nil, errMessageHashLength |
| } |
| return signInternal(priv, (*[64]byte)(μ), &random), nil |
| } |
| |
| func TestingOnlySignExternalMuWithRandom(priv *PrivateKey, μ []byte, random []byte) ([]byte, error) { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| if len(μ) != 64 { |
| return nil, errMessageHashLength |
| } |
| if len(random) != 32 { |
| return nil, errRandomLength |
| } |
| return signInternal(priv, (*[64]byte)(μ), (*[32]byte)(random)), nil |
| } |
| |
| func computeMessageHash(tr []byte, msg []byte, context string) ([64]byte, error) { |
| if len(context) > 255 { |
| return [64]byte{}, errContextTooLong |
| } |
| H := sha3.NewShake256() |
| H.Write(tr) |
| H.Write([]byte{0}) // ML-DSA / HashML-DSA domain separator |
| H.Write([]byte{byte(len(context))}) |
| H.Write([]byte(context)) |
| H.Write(msg) |
| var μ [64]byte |
| H.Read(μ[:]) |
| return μ, nil |
| } |
| |
| func signInternal(priv *PrivateKey, μ *[64]byte, random *[32]byte) []byte { |
| p, k, l := priv.pub.p, priv.pub.p.k, priv.pub.p.l |
| A, s1, s2, t0 := priv.pub.a[:k*l], priv.s1[:l], priv.s2[:k], priv.t0[:k] |
| |
| β := p.τ * p.η |
| γ1 := uint32(1 << p.γ1) |
| γ1β := γ1 - uint32(β) |
| γ2 := (q - 1) / uint32(p.γ2) |
| γ2β := γ2 - uint32(β) |
| |
| H := sha3.NewShake256() |
| H.Write(priv.k[:]) |
| H.Write(random[:]) |
| H.Write(μ[:]) |
| nonce := make([]byte, 64) |
| H.Read(nonce) |
| |
| κ := 0 |
| sign: |
| for { |
| // Main rejection sampling loop. Note that leaking rejected signatures |
| // leaks information about the private key. However, as explained in |
| // https://pq-crystals.org/dilithium/data/dilithium-specification-round3.pdf |
| // Section 5.5, we are free to leak rejected ch values, as well as which |
| // check causes the rejection and which coefficient failed the check |
| // (but not the value or sign of the coefficient). |
| |
| y := make([]ringElement, l, maxL) |
| for r := range y { |
| counter := make([]byte, 2) |
| byteorder.LEPutUint16(counter, uint16(κ)) |
| κ++ |
| |
| H.Reset() |
| H.Write(nonce) |
| H.Write(counter) |
| v := make([]byte, (p.γ1+1)*n/8, (maxγ1+1)*n/8) |
| H.Read(v) |
| |
| y[r] = bitUnpack(v, p) |
| } |
| |
| // w = NTT⁻¹(Â ∘ NTT(y)) |
| yHat := make([]nttElement, l, maxL) |
| for i := range y { |
| yHat[i] = ntt(y[i]) |
| } |
| w := make([]ringElement, k, maxK) |
| for i := range w { |
| var wHat nttElement |
| for j := range l { |
| wHat = polyAdd(wHat, nttMul(A[i*l+j], yHat[j])) |
| } |
| w[i] = inverseNTT(wHat) |
| } |
| |
| H.Reset() |
| H.Write(μ[:]) |
| for i := range w { |
| w1Encode(H, highBits(w[i], p), p) |
| } |
| ch := make([]byte, p.λ/4, maxλ/4) |
| H.Read(ch) |
| |
| // sampleInBall is not constant time, but see comment above about |
| // leaking rejected ch values being acceptable. |
| c := ntt(sampleInBall(ch, p)) |
| |
| cs1 := make([]ringElement, l, maxL) |
| for i := range cs1 { |
| cs1[i] = inverseNTT(nttMul(c, s1[i])) |
| } |
| cs2 := make([]ringElement, k, maxK) |
| for i := range cs2 { |
| cs2[i] = inverseNTT(nttMul(c, s2[i])) |
| } |
| |
| z := make([]ringElement, l, maxL) |
| for i := range y { |
| z[i] = polyAdd(y[i], cs1[i]) |
| |
| // Reject if ||z||∞ ≥ γ1 − β |
| if coefficientsExceedBound(z[i], γ1β) { |
| if testingOnlyRejectionReason != nil { |
| testingOnlyRejectionReason("z") |
| } |
| continue sign |
| } |
| } |
| |
| for i := range w { |
| r0 := polySub(w[i], cs2[i]) |
| |
| // Reject if ||LowBits(r0)||∞ ≥ γ2 − β |
| if lowBitsExceedBound(r0, γ2β, p) { |
| if testingOnlyRejectionReason != nil { |
| testingOnlyRejectionReason("r0") |
| } |
| continue sign |
| } |
| } |
| |
| ct0 := make([]ringElement, k, maxK) |
| for i := range ct0 { |
| ct0[i] = inverseNTT(nttMul(c, t0[i])) |
| |
| // Reject if ||ct0||∞ ≥ γ2 |
| if coefficientsExceedBound(ct0[i], γ2) { |
| if testingOnlyRejectionReason != nil { |
| testingOnlyRejectionReason("ct0") |
| } |
| continue sign |
| } |
| } |
| |
| count1s := 0 |
| h := make([][n]byte, k, maxK) |
| for i := range w { |
| var count int |
| h[i], count = makeHint(ct0[i], w[i], cs2[i], p) |
| count1s += count |
| } |
| // Reject if number of hints > ω |
| if count1s > p.ω { |
| if testingOnlyRejectionReason != nil { |
| testingOnlyRejectionReason("h") |
| } |
| continue sign |
| } |
| |
| return sigEncode(ch, z, h, p) |
| } |
| } |
| |
| // testingOnlyRejectionReason is set in tests, to ensure that all rejection |
| // paths are covered. If not nil, it is called with a string describing the |
| // reason for rejection: "z", "r0", "ct0", or "h". |
| var testingOnlyRejectionReason func(reason string) |
| |
| // w1Encode implements w1Encode from FIPS 204, writing directly into H. |
| func w1Encode(H *sha3.SHAKE, w [n]byte, p parameters) { |
| switch p.γ2 { |
| case 32: |
| // Coefficients are <= (q − 1)/(2γ2) − 1 = 15, four bits each. |
| buf := make([]byte, 4*n/8) |
| for i := 0; i < n; i += 2 { |
| b0 := w[i] |
| b1 := w[i+1] |
| buf[i/2] = b0 | b1<<4 |
| } |
| H.Write(buf) |
| case 88: |
| // Coefficients are <= (q − 1)/(2γ2) − 1 = 43, six bits each. |
| buf := make([]byte, 6*n/8) |
| for i := 0; i < n; i += 4 { |
| b0 := w[i] |
| b1 := w[i+1] |
| b2 := w[i+2] |
| b3 := w[i+3] |
| buf[3*i/4+0] = (b0 >> 0) | (b1 << 6) |
| buf[3*i/4+1] = (b1 >> 2) | (b2 << 4) |
| buf[3*i/4+2] = (b2 >> 4) | (b3 << 2) |
| } |
| H.Write(buf) |
| default: |
| panic("mldsa: internal error: unsupported γ2") |
| } |
| } |
| |
| func coefficientsExceedBound(w ringElement, bound uint32) bool { |
| // If this function appears in profiles, it might be possible to deduplicate |
| // the work of fieldFromMontgomery inside fieldInfinityNorm with the |
| // subsequent encoding of w. |
| for i := range w { |
| if fieldInfinityNorm(w[i]) >= bound { |
| return true |
| } |
| } |
| return false |
| } |
| |
| func lowBitsExceedBound(w ringElement, bound uint32, p parameters) bool { |
| switch p.γ2 { |
| case 32: |
| for i := range w { |
| _, r0 := decompose32(w[i]) |
| if constantTimeAbs(r0) >= bound { |
| return true |
| } |
| } |
| case 88: |
| for i := range w { |
| _, r0 := decompose88(w[i]) |
| if constantTimeAbs(r0) >= bound { |
| return true |
| } |
| } |
| default: |
| panic("mldsa: internal error: unsupported γ2") |
| } |
| return false |
| } |
| |
| var ( |
| errInvalidSignatureLength = errors.New("mldsa: invalid signature length") |
| errInvalidSignatureCoeffBounds = errors.New("mldsa: invalid signature") |
| errInvalidSignatureChallenge = errors.New("mldsa: invalid signature") |
| errInvalidSignatureHintLimits = errors.New("mldsa: invalid signature encoding") |
| errInvalidSignatureHintIndexOrder = errors.New("mldsa: invalid signature encoding") |
| errInvalidSignatureHintExtraIndices = errors.New("mldsa: invalid signature encoding") |
| ) |
| |
| func Verify(pub *PublicKey, msg, sig []byte, context string) error { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| μ, err := computeMessageHash(pub.tr[:], msg, context) |
| if err != nil { |
| return err |
| } |
| return verifyInternal(pub, &μ, sig) |
| } |
| |
| func VerifyExternalMu(pub *PublicKey, μ []byte, sig []byte) error { |
| fipsSelfTest() |
| fips140.RecordApproved() |
| if len(μ) != 64 { |
| return errMessageHashLength |
| } |
| return verifyInternal(pub, (*[64]byte)(μ), sig) |
| } |
| |
| func verifyInternal(pub *PublicKey, μ *[64]byte, sig []byte) error { |
| p, k, l := pub.p, pub.p.k, pub.p.l |
| t1, A := pub.t1[:k], pub.a[:k*l] |
| |
| β := p.τ * p.η |
| γ1 := uint32(1 << p.γ1) |
| γ1β := γ1 - uint32(β) |
| |
| z := make([]ringElement, l, maxL) |
| h := make([][n]byte, k, maxK) |
| ch, err := sigDecode(sig, z, h, p) |
| if err != nil { |
| return err |
| } |
| |
| c := ntt(sampleInBall(ch, p)) |
| |
| // w = Â ∘ NTT(z) − NTT(c) ∘ NTT(t₁ ⋅ 2ᵈ) |
| zHat := make([]nttElement, l, maxL) |
| for i := range zHat { |
| zHat[i] = ntt(z[i]) |
| } |
| w := make([]ringElement, k, maxK) |
| for i := range w { |
| var wHat nttElement |
| for j := range l { |
| wHat = polyAdd(wHat, nttMul(A[i*l+j], zHat[j])) |
| } |
| wHat = polySub(wHat, nttMul(c, t1[i])) |
| w[i] = inverseNTT(wHat) |
| } |
| |
| // Use hints h to compute w₁ from w(approx). |
| w1 := make([][n]byte, k, maxK) |
| for i := range w { |
| w1[i] = useHint(w[i], h[i], p) |
| } |
| |
| H := sha3.NewShake256() |
| H.Write(μ[:]) |
| for i := range w { |
| w1Encode(H, w1[i], p) |
| } |
| computedCH := make([]byte, p.λ/4, maxλ/4) |
| H.Read(computedCH) |
| |
| for i := range z { |
| if coefficientsExceedBound(z[i], γ1β) { |
| return errInvalidSignatureCoeffBounds |
| } |
| } |
| |
| if !bytes.Equal(ch, computedCH) { |
| return errInvalidSignatureChallenge |
| } |
| |
| return nil |
| } |
| |
| func sigEncode(ch []byte, z []ringElement, h [][n]byte, p parameters) []byte { |
| sig := make([]byte, 0, sigSize(p)) |
| sig = append(sig, ch...) |
| for i := range z { |
| sig = bitPack(sig, z[i], p) |
| } |
| sig = hintEncode(sig, h, p) |
| return sig |
| } |
| |
| func sigDecode(sig []byte, z []ringElement, h [][n]byte, p parameters) (ch []byte, err error) { |
| if len(sig) != sigSize(p) { |
| return nil, errInvalidSignatureLength |
| } |
| ch, sig = sig[:p.λ/4], sig[p.λ/4:] |
| for i := range z { |
| length := (p.γ1 + 1) * n / 8 |
| z[i] = bitUnpack(sig[:length], p) |
| sig = sig[length:] |
| } |
| if err := hintDecode(sig, h, p); err != nil { |
| return nil, err |
| } |
| return ch, nil |
| } |
| |
| func hintEncode(buf []byte, h [][n]byte, p parameters) []byte { |
| ω, k := p.ω, p.k |
| out, y := sliceForAppend(buf, ω+k) |
| var idx byte |
| for i := range k { |
| for j := range n { |
| if h[i][j] != 0 { |
| y[idx] = byte(j) |
| idx++ |
| } |
| } |
| y[ω+i] = idx |
| } |
| return out |
| } |
| |
| func hintDecode(y []byte, h [][n]byte, p parameters) error { |
| ω, k := p.ω, p.k |
| if len(y) != ω+k { |
| return errors.New("mldsa: internal error: invalid signature hint length") |
| } |
| var idx byte |
| for i := range k { |
| limit := y[ω+i] |
| if limit < idx || limit > byte(ω) { |
| return errInvalidSignatureHintLimits |
| } |
| first := idx |
| for idx < limit { |
| if idx > first && y[idx-1] >= y[idx] { |
| return errInvalidSignatureHintIndexOrder |
| } |
| h[i][y[idx]] = 1 |
| idx++ |
| } |
| } |
| for i := idx; i < byte(ω); i++ { |
| if y[i] != 0 { |
| return errInvalidSignatureHintExtraIndices |
| } |
| } |
| return nil |
| } |
