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).
( "ByKey" <Key-Value, Signature-Suite dependent> )
-
Within the ECDSS signature suite, the key value is:
( "ByKey" ( "K" "ascii-hex-encoded-field-element" ))
-
"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:
("SigCrypto" <Signature-Value, Signature-Suite dependent>)
-
Within the ECDSS signature suite, the signature values are:
(( "R" "ascii-hex-encoded-field-element" )
( "S" "ascii-hex-encoded-field-element" ))
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.
("on" quoted-ISO-Date)
-
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:
( "exclude" field-list )
( "include" field-list )
-
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:
field-list ::= '(' option-list*1 ratings-list*1 extension-list*1 ')'
option-list ::= '(' "options" <options>* ')'
ratings-list ::= '(' "ratings" <ratings>* ')'
extension-list ::= '(' "extensions" <quoted-URL>* ')'
-
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")))