ECDSS Signature Suite - Version 1.0

Elliptic Curve Cryptography (ECC) can be used to implement public-key cryptosystems. The ECDSS signature suite specifies how ECC is used with the SHA-1 hash function and DSA (FIPS Digital Signature Algorithm) to sign a PICS label per the DSig 1.0 Specification.

ECC Overview

ECC can be used to implement a public-key cryptosystem that can be used for digital signature, Diffie-Hellman key-exchange, and ElGamal encryption; it was proposed in 1985 independently by N. Koblitz and V. Miller. It works as follows: Given a well know generator point P on an elliptic curve in a Galois field, compute Q = kP, where kP represents the operation (P+P+P...) k times, and where (P+P) represents an operation of "point addition" on two points on the elliptic curve which yields a unique third point. Thus Q is some point resulting from k repeated "point additions" of P. The public key is the point Q, and the private key is k. The Abelian group formed by the field and the operation (point addition) is the basis for the elliptic curve discrete log problem.

It is difficult (presumably) to obtain the private key k from the public key Q. If one could solve the discrete log problem for elliptic curves in a finite field, one could derive k from Q. Thus the security of ECC relies on the difficulty of solving the discrete log problem for elliptic curves in a finite field. Due to the intractability of ECC's discrete log problem when subjected to known attacks, ECC key lengths are dramatically shorter that those for systems based on either the conventional discrete log problem or on the difficulty of factoring large integers. A 160 bit ECC key is estimated to be equivalent to 1024 bit keys in those other systems.

ECC can be used for authentication as follows:

Suppose Alice wishes to send a signed message to Bob in such a way that Bob is assured that the message is authentic and is from Alice. She applies a hash function to the message to create a message digest, which serves as a "digital fingerprint" of the message. She then computes 2 values, r and s from the message digest with her ECC private key; this is the DSS digital signature, which she sends to Bob along with the message itself. Bob, upon receiving the message and signature, verifies the signature, by combining the values r and s, Alice's public key, and Bob's hash of the message, to compute the value v. Bob compares r to v. If they are exactly equal, the signature has been successfully verified and he can be confident that the message did indeed come from Alice. If they are not equal, then the message either originated elsewhere or was altered after it was signed, and he rejects the message. With the method just described, anybody can read the message and verify the signature.

Thus authentication take place without any sharing of private keys: each person uses only other people's public keys and his or her own private key. Anyone can verify a signed message, using only public keys, but only someone in possession of the correct private key can sign a message.

ECC is combined with the SHA-1 hashing function to sign a message in this signature suite. It must be infeasible for anyone to either find a message that hashes to a given value or to find two messages that hash to the same value. If either were feasible, an intruder could attach a false message onto Alice's signature. The hash functions SHA-1 has been designed specifically to have the property that finding a match is infeasible, and is therefore considered suitable for use in this role.

The signature section of the DSig 1.0 Signature Block Extension is defined in the DSig 1.0 Specification. For the ECDSS signature suite, the signature section has the following required and optional fields.

Required Fields

"ByKey" - key value for validating a signature: The token "ByKey" identifies the value that follows as the key that should be used to validate the signature (or sufficient information to generate that key locally).; Within the ECDSS signature suite, the key value is:
"SigCrypto" - signature cryptographic data: The "SigCrypto" token identifies the SigData field that contains the cryptographic data that is the signature itself. The format and contents of this field are:; Within the ECDSS signature suite, the signature values are:

Optional Fields

"On" - Time of Signature generation: The token "On" identifies the value that follows as the time the label's signature was generated. (This option is distinct from the PICS 1.1 label option "on" which indicates the time at which the label itself was created.) We recommend using this standard element in all signature suites.; The time that the signature was created is encoded as a quoted-ISO-Date. The format of a quoted-ISO-Date is defined in the PICS 1.1 specifications.; Notice that the "on" time is advisory only to applications verifying the digital signature; as this section is part of the entire sigblock extension it is not cryptographically protected by the signature itself. (The contents of the sigblock do not contribute to the hash of the label that is signed by the signature.) If a cryptographically protected date is desired, the correct way to implement it is to include the date within another PICS label extension; that extension may then contribute to the hash of the canonicalized label.

"include" and "exclude" - modifying the canonicalized form of the label: If an application wishes to transmit both signed and unsigned information in a label the suggested method for doing so is to generate two labels (one signed, one unsigned) and send both labels as a PICS label list. However, some PICS 1.1 protocols, including the protocol for requesting labels from a PICS label bureau, require that exactly one PICS label be returned in response to a request, and thus it may be necessary for a signing application to sign only a subset of a PICS label. If the signature suite permits signatures over partial contents of labels, the "include" and "exclude" tokens provide that functionality:; The "include" and "exclude" SigData fields modify the default behavior of the label canonicalizer. Before a label is signed, it is put into canonical form; the section "Creating an equivalent standalone label" below describes in detail the canonicalization process. PICS labels have many semantically-equivalent forms yet these forms yield distinct hashes, so it is important that signing and verifying applications canonicalize labels in the same way. After the equivalent standalone label has been generated following the default canonicalization rules, individual label options may be dropped if an "include" or "exclude" option is present. If an "include" option is present, any field not listed in the field-list is removed from the canonicalized label. If an "exclude" option is present, all fields listed in the field-list are removed from the canonicalized label. At most one "include" or "exclude"; field may appear; it is an error to have both an "include" and an "exclude" option.; The value associated with an "include" or "exclude" option (the "field-list") is a list of label fields to be included or excluded in the canonicalized form. There are three types of fields in PICS 1.1 labels: options, ratings transmit/value pairs, and extensions. The format of a field-list is as follows:; A field-list is simply a collections of at most one of each an option-list, ratings-list and extension-list. An option-list is a list of PICS 1.1 label option names (e.g. "for" or "by"). A ratings-list is a list of PICS 1.1 ratings service transmit-names (e.g. "suds" in the example "Good Clean Fun" rating service). An extension-list is a list of quotes-URLs where each quoted-URL uniquely identifies a particular PICS 1.1 label extension.

Example

("Signature" "http://www.w3.org/PICS/DSig/ECDSS_1_0.html" 



     ("byKey"  ("K" "08b69b2fc371820a83766cfa033a8b3cca2ef3b"))



     ("SigCrypto" (("R" "012471e8d76e2a4a0b9df06cac891754e2cf297")



                 ("S" "02a64095130f9152d3b77a56675547441505cf7")))



     ("on" "1996.12.02T22:20-0000")



     ("exclude" ("extensions" "http://foo/badextension.html")))