[FEATURE REQUEST] Add Merkle Signature Scheme (MSS) #7628

What would you like to Propose?

I would like to add an educational implementation of the Merkle Signature Scheme (MSS) to the ciphers package.

MSS turns a one-time signature scheme into a many-time scheme: it generates 2^h one-time key pairs and authenticates all of them under a single public key (the root of a Merkle tree). It builds directly on the recently merged WinternitzSignature and is the core construction behind XMSS (RFC 8391) and the hash-based post-quantum standards.

Issue details

Algorithm: Merkle Signature Scheme (Merkle, 1979)

Problem statement: One-time signatures such as Lamport and Winternitz are insecure if a key is used more than once. MSS solves this by committing to 2^h one-time public keys with a binary hash tree, so a single public key (the root) can verify up to 2^h signatures.

How it works:

• Key generation: create 2^h WinternitzSignature instances. Each leaf is SHA-256 of the concatenated WOTS public key. Parent nodes are SHA-256(left || right), and the root is the MSS public key.
• Signing: sign with the next unused WOTS key and attach the authentication path (the sibling hash at each level, h elements). An IllegalStateException is thrown once all 2^h keys are used.
• Verification: verify the WOTS signature, hash the WOTS public key into a leaf, then recompute the root using the auth path (the leaf index bit decides left/right order at each level) and compare it with the public key.

Proposed API (com.thealgorithms.ciphers.MerkleSignatureScheme):

• MerkleSignatureScheme() / MerkleSignatureScheme(int h, int w), with 2 ≤ h ≤ 10
• byte[] getPublicKey()
• MerkleSignature sign(byte[] message)
• static boolean verify(byte[] message, MerkleSignature signature, byte[] publicKey, int w)
• int remainingSignatures()

Scope:

• Reuses the existing WinternitzSignature class (no duplicated hashing/chain logic)
• No external dependencies; only java.security.MessageDigest
• JUnit 5 tests: signing and verifying all 2^h leaves, capacity exhaustion, tampered message/signature/auth path/leaf index, wrong public key, parameterized h and w, input validation, and immutability
• Only two new files (implementation + test)

Additional Information

This is a follow-up to the Winternitz OTS contribution and continues the hash-based signature series (Lamport → WOTS → MSS).

For simplicity, the WOTS public key is included in the signature instead of being recomputed from it; this is documented in the Javadoc. The implementation is intended for educational purposes only and is not a production-grade XMSS.

References:

• https://en.wikipedia.org/wiki/Merkle_signature_scheme
• RFC 8391 (XMSS): https://datatracker.ietf.org/doc/html/rfc8391