Digital signatures are increasingly pervasive as organizations and end-users strive to ensure the integrity of information and the non-repudiation of commitments. Digital signatures are particularly useful for e-commerce, e-passports, smart cards, and other applications that require authentication.

The Elliptic Curve Digital Signature Algorithm (ECDSA) was first proposed in 1992 by Scott Vanstone in response to a National Institute of Standards and Technology (NIST) request for public comments on their first proposal for the Digital Signature Standard (DSS).

These ECC-based signatures are smaller and faster to create that aging RSA-based algorithms. As a result, the public key that the certificate holds is smaller and more agile as well. Verification is also faster using ECC-based certificates, especially at higher key strengths. For this reason, ECDSA is included as part of the NSA Suite B standard, helps secure the postal system, has been adopted by key standards, and used by leading Check 21 vendors.

Certicom also provides an even smaller, more efficient alternative to ECDSA, the Elliptic Curve Pintsov Vanstone Signature (ECPVS) scheme. ECPVS is a signature scheme that provides partial message recovery. At the same security level and elliptic curve, an ECPVS signature can add as little as 20 bytes to the original message length, which is a six times smaller than RSA and makes ECPVS more efficient.

ECPVS is also unique because all or part of the message can be embedded in and recovered from the signature. This partial message recovery makes ECPVS ideal for use with digital postal marks. Certain data elements, such as the date and the postage amount, are able to be read by humans, while other data elements, such as the address of the sender or a confirmation of the recipient's address, are restricted to being read only by machines. Furthermore, if the terminal's signature verification key is secret, rather than public, then the hidden part of the message is difficult to obtain, even by machine.

Another feature specific to ECPVS is the ability to adjust the level of security, depending on the requirements. In ECPVS, the length of the recovered part of the message is not tied to any other parameters of the scheme. Redundancy, the duplication added to an encrypted message, is one of these parameters. The amount of redundancy in a message determines the level of security. Only ECPVS enables tradeoffs between security level and bandwidth availability: if very short signatures are required due to bandwidth constraints, the amount of redundancy added by padding can be lowered, thereby decreasing the size of the signature component e, with a controlled impact on the security offered by the scheme.

ECDSA Fast Verify

Reduce time needed to verify digital signatures by 40%
Researchers at Certicom have developed a new implementation for ECDSA - Fast ECDSA Verify - that reduces the time needed to verify a digital signature by 40 percent - making it significantly more efficient than Open Source and other legacy systems.

This new implementation is especially relevant for applications - like Check 21, e-passports, and smart cards - that must be able to process large quantities of information efficiently. In addition, Fast ECDSA Verify has positive implications for organizations using ECC-based technology.

Key Fast ECDSA Verify Benchmarks*

  • Signature generation time--100 ms (millisecond)
  • Traditional ECDSA verification time--221 ms original cost
  • Fast ECDSA verification time --158 ms 40% speed-up

(*Platform ARM7TDMI 50 MHz; curve: secp384r1)

ECDSA Accepted In The Standards

1992 - NIST requests response to DSS
1998 - ISO 14888-3
1999 - ANSI X9.62
2000 - IEEE 1363-2000
2000 - FIPS 186-2 (approved for FIPS 140-2)
2005 - Check 21

Using ECDSA For Digital Signing Provides Many Critical Advantages, Including:

Using ECDSA for digital signing provides many critical advantages, including:

  • High-performance leading to significantly faster signing and verification
  • Stronger security that doesn't bog down application performance
  • Signatures that can protect information beyond archive requirements
  • Competitive differentiation and meeting emerging security requirements
  • Security that meets government and industry standards
  • Support and backing from an industry-leader

The chart below demonstrates the performance of ECDSA over RSA for signing and verifying. ECDSA and RSA-based signatures are compared at equivalent strength. The chart measures the number of digital signatures applied to a data block per minute.

Table 1 ECDSA versus RSA

As can be seen from the chart above, ECDSA provides incredible performance benefits to both signing and verification operations. The benefits of ECC-based digital certificates become even more apparent when applied to applications in the real world. ECDSA minimizes the overall footprint of the data authenticated and enables dramatic storage cost-savings.

How ECPVS Works

Using ECPVS, a plain text message (PD) is essentially split into two parts: parts C and V. Part C represents data elements that require confidentiality protection, such as the sender information, value of a serial piece count, or the value of the ascending register. These can be recovered during the verification process from the signature and allow for proof of deposit and mail tracing. Part V contains data elements presented in the plaintext within the DPM, such as the date, the sender's and recipient's postal codes, or the amount of the postage. Both C and V are signed.

The ECPVS uses a fixed elliptic curve with a generator G of order n. Terminal A has public key QA and identity A.

To generate a signature, the mailer terminal A begins by generating a random positive integer k < n.

The terminal then takes the mailing information and performs a number of computations in order to encrypt the message. First, it calculates a point R on the curve (R = kG), to be used as a key for the transformation of C. This elliptic curve point R is then used in a bijective transformation (TR)— typically a symmetric encryption algorithm—to destroy any algebraic structure C might have, with the result being e. The secrecy of e is based on the difficulty of the discrete log problem and on the randomness of k.

The variable d is calculated using a hash function H, the encrypted message part e, and the identity of the mailer's terminal IA, as follows: d = H (e || I A || V).

Finally, s (the other part of the signature pair), is calculated using d, k, and a, which is the private key of the terminal A as follows: s= a d + k (mod n).

The signature pair (s, e) is then put into the DPM together with the portion V of the plain text PD.

To verify the DPM of an incoming mail piece, a postage verifier on the other end of the postal process parses the DPM into IA, the signature (s,e), and the verification data V. Using these and the public key of terminal A, the postage verifier recovers C and subjects it to a redundancy test. If the redundancy check fails, the DPM is rejected; if the redundancy check passes, the plaintext message is recovered.

ECPVS in the Real World

Pitney Bowes, a global provider of informed mail and messaging management, introduced digital mailing systems in 2002 that use ECPVS to provide security for the digital postage marks.

ECPVS is also being adopted into a number of standards, including I EEE P1363a, ANSI X9.92, and ISO 9796-3.

The relative benefits of ECPVS (size, flexibility and efficiency) also make it ideal for use in applications beyond the postal service such as cheque imaging and verification, or to sign short 1-byte messages (i.e. yes/no, buy/hold/sell, etc.)