Fast implementation of the ECDSA

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue of the Digital Signature Algorithm (DSA). It was accepted in 1999 as an ANSI standard, and was accepted in 2000 as IEEE and NIST standards. It was also accepted in 1998 as an ISO standard, and is under consideration for inclusion in some other ISO standards. Unlike the ordinary discrete logarithm problem and the integer factorization problem, no subexponential-time algorithm is known for the elliptic curve discrete logarithm problem. For this reason, the strength-per-key-bit is substantially greater in an algorithm that uses elliptic curves. The implementation is based on the ANSI X9.62 ECDSA.

Digital signature schemes are designed to provide the digital counterpart to handwritten signatures (and more). A digital signature is a number dependent on some secret known only to the signer (the signer’s private key), and, additionally, on the contents of the message being signed. Signatures must be verifiable. With the signer’s public key authentizity of the signature can be verified.
Elliptic Curve Digital Signature is an asymmetric digital signature schema with appendix. “Asymmetric” means that each entity selects a key pair consisting of a private key and a related public key. The entity maintains the secrecy of the private key which it uses for signing messages, and makes authentic copies of its public key available to other entities which use it to verify signatures. “Appendix” means that a cryptographic hash function is used to create a message digest of the message, and the signing transformation is applied to the message digest rather than to the message itself.

SECURITY. Ideally, a digital signature scheme should be existentially unforgeable under chosen-message attack. This notion of security was introduced by Goldwasser, Micali and Rivest. Informally, it asserts that an adversary who is able to obtain entity A’s signatures for any messages of its choice is unable to successfully forge A’s signature on a single other message.

APPLICATIONS. Digital signature schemes can be used to provide the following basic cryptographic services: data integrity (the assurance that data has not been altered by unauthorized or unknown means), data origin authentication (the assurance that the source of data is as claimed), and non-repudiation (the assurance that an entity cannot deny previous actions or commitments).

IMPLEMENTATION. The Elliptic Curve Digital Signature Algorithm has been implemented in Java. Through the Speed Optimization of the Projective Elliptic Scalar Multiplication and the needed Field Operations a major speedup of the ECDSA at all has been achieved.