FACTOID # 103: The ten most generous countries are all in Europe.
 
 Home   Encyclopedia   Statistics   Countries A-Z   Flags   Maps   Education   Forum   FAQ   About 
 
 
 
WHAT'S NEW
RECENT ARTICLES
More Recent Articles »
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Elliptic Curve DSA

Elliptic Curve DSA (ECDSA) is a variant of the Digital Signature Algorithm (DSA) which operates on elliptic curve groups. The EC variant provides smaller key sizes for (supposedly) similar security level. On the other hand, the execution time is roughly the same and the signature size is exactly the same: 4t, where t is the security parameter. For example, DSA with 1024-bit p and 160-bit q and ECDSA over the 160-bit prime field both produce 320-bits signatures and need only few milliseconds [1] for execution on a 2 GHz Pentium. The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. ... In mathematics, an elliptic curve is a plane curve defined by an equation of the form y2 = x3 + a x + b, which is non-singular; that is, its graph has no cusps or self-intersections. ... This picture illustrates how the hours in a clock form a group. ...

Contents

Signature generation algorithm

Suppose Alice wants to send a signed message to Bob. Initially, the curve parameters (q,FR,a,b,G,n,h) must be agreed upon. Also, Alice must have a key pair suitable for elliptic curve cryptography, consisting of a private key dA (a randomly selected integer in the interval [1,n − 1]) and a public key QA (where QA = dAG). The names Alice and Bob are commonly used placeholders for archetypal characters in fields such as cryptography and physics. ... The names Alice and Bob are commonly used placeholders for archetypal characters in fields such as cryptography and physics. ...


For Alice to sign a message m, she follows these steps:

  1. Calculate e = HASH(m), where HASH is a cryptographic hash function, such as SHA-1.
  2. Select a random integer k from [1,n − 1].
  3. Calculate r = x1(mod n), where (x1,y1) = kG. If r = 0, go back to step 2.
  4. Calculate s = k − 1(e + rdA)(mod n). If s = 0, go back to step 2.
  5. The signature is the pair (r,s).

In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ... The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions designed by the National Security Agency (NSA) and published by the National Institute of Standards and Technology (NIST). ...

Signature verification algorithm

For Bob to authenticate Alice's signature, he must have a copy of her public key QA. He follows these steps:

  1. Verify that r and s are integers in [1,n − 1]. If not, the signature is invalid.
  2. Calculate e = HASH(m), where HASH is the same function used in the signature generation.
  3. Calculate w = s − 1(mod n).
  4. Calculate u1 = ew(mod n) and u2 = rw(mod n).
  5. Calculate (x1,y1) = u1G + u2QA.
  6. The signature is valid if x1 = r(mod n), invalid otherwise.

Note that using Straus's algorithm (also known as Shamir's trick) a sum of two scalar multiplications u1G + u2QA can be calculated faster than with two scalar multiplications.


References

  • Accredited Standards Committee X9, American National Standard X9.62-2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), November 16, 2005.
  • Certicom Research, Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography, Version 1.0, September 20, 2000.
  • López, J. and Dahab, R. An Overview of Elliptic Curve Cryptography, Technical Report IC-00-10, State University of Campinas, 2000.
  • Daniel J. Bernstein, Pippenger's exponentiation algorithm, 2002.
  • Daniel R. L. Brown, Generic Groups, Collision Resistance, and ECDSA, Designs, Codes and Cryptography, 35, 119-152, 2005. ePrint version
  • Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart, editors, Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
  • Darrel Hankerson, Alfred Menezes and Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer, Springer, 2004.

External links

See also

Public-key cryptography
v • d • e
Algorithms: Cramer-Shoup | DH | DSA | ECDH | ECDSA | EKE | ElGamal | GMR | IES | Lamport | MQV | NTRUEncrypt | NTRUSign | Paillier | Rabin | RSA | Schnorr | SPEKE | SRP | XTR
Theory: Discrete logarithm | Elliptic curve cryptography | RSA problem
Standardization: ANS X9F1 | CRYPTREC | IEEE P1363 | NESSIE | NSA Suite B   Misc: Digital signature | Fingerprint | PKI | Web of trust | Key size
Cryptography
v • d • e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers

  Results from FactBites:
 
Elliptic curve - Wikipedia, the free encyclopedia (1278 words)
One finds that elliptic curves correspond to embeddings of the torus into the complex projective plane; such embeddings generalize to arbitrary fields, and so it is said that elliptic curves are non-singular projective algebraic curves of genus 1 over a field K, together with a distinguished point defined over K.
Elliptic curves are especially important in number theory, and constitute a major area of current research; for example, they were used in the proof of Fermat's last theorem.
Elliptic curves can be defined over any field K; the formal definition of an elliptic curve is a non-singular projective algebraic curve over K with genus 1 with a given point defined over K.
Elliptic curve cryptography - Wikipedia, the free encyclopedia (1054 words)
Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the mathematics of elliptic curves.
There are several slightly different versions of elliptic curve cryptography, all of which rely on the widely believed difficulty of solving the discrete logarithm problem for the group of an elliptic curve over some finite field.
Given an elliptic curve E, and a field GF(q), we consider the abelian group of rational points E(q) of the form (x, y), where both x and y are in GF(q), and where the group operation "+" is defined on this curve as described in the article elliptic curve.
  More results at FactBites »


 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:
 


Lesson Plans | Student Area | Student FAQ | Reviews | Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m