Understanding the Elliptic Curve Digital Signature Algorithm

Just like the RSA, the Elliptic Curve Digital Signature Algorithm (ECDSA) has been added to the FIPS186-2 ( http://cscr.nist.gov/ publications /fips/fips186-2/fips186-2-change1.pdf ).

Cross-Reference

The ECC for key exchange was discussed in Chapter 4. The ECC provides a key exchange for the key pair.

The ECDSA generates a signature with a private key and verifies the signature with a public key. The ECDSA starts by selecting an integer value k to be multiplied by a Point P = (x ₁ , y ₁ ) along the elliptic curve. Just like the DSS algorithm, an r and s variable is calculated and saved for the signature. Since x ₁ is an integer point on the x coordinate system, r can be computed by the following equation:

r = x ₁ mod n

The variable s is calculated by the SHA-1 hash on the message represented by h(m) and the private key d . The s equation becomes

s = k ^-1 (h(m) + dr) mod n

The signature is the r and s variable. To verify the signature, the ECDSA needs the r , s , the message for the digest, and the public key (E, P, n, Q) . The verify method is initialized with the public key. Then the message needs to be passed through the algorithm's update method to store the hashed message. The verify method is then called, passing in the signature containing the r and s . The verify method hashes the message and converts the digest into an integer m . Just like the DSA algorithm the ESDSA contains multiple calculations. The next variable after m to be calculated is the variable w , which is calculated using the equation

w = s -1 mod n

The next two variables are u1 and u2 calculated by

u1 = mw mod n and u2 is u2 = rw mod n

The point along the elliptic curve is computed from these calculations. Taking the public key variables P and Q , the additive property is used from u1 and u2 to form u1P + u2Q . The point from u1P + u2Q is computed in the x-y coordinate system as the point (x0, y0). The x0 coordinate along the x-axis is used to find the result in v = x0 mod n . If the variable v in the verify method equals the variable r in the signature generator, the message and keys used are valid.

Some of the equations between the ECDSA and DSA appear similar because both algorithms are based on the ElGamal signature algorithm by signing the equation

s = k ^-1 {h(m) + dr} mod m

Both the ECDSA and DSA use the SHA-1 message digest as the defined digest to use. The ECDSA uses public variables from the public key (E, P, n, Q) that are used to compute the intermediate variables w , u1 , and u2 . Looking at DSA, similar calculations were accomplished using public variables p , q , and g . These values are needed to produce the algorithms without the private key. Both of these algorithms share the complexity of trying to generate the checks with just the public variables. The biggest difference that exists between these two algorithms is the type of equations. The ECDSA is elliptical and uses geometric properties. In other words, checks consist of checking if points fall on a curve as opposed to checking if the values are greater than 0 and less than q, as in the DSA.

Note

The DSA is easier from a computational standpoint in that numbers can be checked to be less than, greater than, or equal to. The computational complexity of ECDSA makes the algorithms more secure. Also, because the numbers that can be used in ECDSA are limited to the points along a curve (versus the DSA using prime numbers that must fit together), the ECDSA is computationally faster.

Table of content

Java Security Solutions

ISBN: 0764549286
EAN: 2147483647

Year: 2001
Pages: 222

Authors: Rich Helton, Johennie Helton

BUY ON AMAZON

Absolute Beginner[ap]s Guide to Project Management

The Complete Cisco VPN Configuration Guide

101 Microsoft Visual Basic .NET Applications

Pocket Guide to the National Electrical Code(R), 2005 Edition (8th Edition)

Microsoft VBScript Professional Projects

Lean Six Sigma for Service : How to Use Lean Speed and Six Sigma Quality to Improve Services and Transactions