NIST algorithms include ECDH and ECDSA. NIST also specifies curves. Is the use of NIST curves required for FIPS certification or could other curves theoretically be certified if someone were willing to do the work?
Could a C25519/ED25519 cryptographic module be FIPS certified?
Likely yes in the near future—although ‘near’ is measured relative to the pace of a US federal government bureaucracy.
On 2019-10-31, NIST submitted a request for comments to the Federal Register on drafts for FIPS 186-5 and NIST SP 800-186 that include the Montgomery and Edwards curve shapes; the particular curves Curve25519, Curve448, edwards25519, and edwards448; and the EdDSA signature scheme instantiated with them, as defined in RFC 7748 and RFC 8032. Comments are due by 2020-01-20.
(The updates do not cover the X25519/X448 DH functions, but NIST's late 2017 announcement of the upcoming changes also mentioned future updates to NIST SP 800-56A, which covers key agreement.)