The use of ECC-based signature schemes in the postal industry is not new. Because the size of the digital signature affects the overall size of the DPM, ECC-based signatures provide an extremely small, yet highly secure option. In the “Performance Criteria for Information-based Indicia and Security Architecture for Open IBI Postage Evidencing Systems” (2001), the USPS defines support for the use of ECDSA to generate the digital signatures for DPM.
A typical ECDSA signature is a 40 byte appendix added to a signed message. By comparison, the cryptographic overhead of an equivalent DPM using RSA would add 128 bytes. As shown in figure 1, this would take up most of the space on the envelope on a small piece of mail, so a small signature becomes very important.
An even smaller alternative is 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.
Using ECPVS, a plain text message (PD) is essentially split into two parts: parts C and V. Part Crepresents 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.
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.)
For more information about ECPVS, Certicom has posted two white papers. Postal Revenue Collection in the Digital Age (PDF), and Formal Security Proofs for a Signature Scheme with Partial Message Recovery (PDF).
This issue of Code and Cipher focuses on Elliptic Curve Cryptography applied to address specific industry needs.