Elliptic Curve Digital Signature Algorithm: Difference between revisions

Line 3:

;Elliptic curves.

An [[wp:Elliptic_curve|elliptic curve]] E over ℤp (p ≥ 5) is defined by an equation of the form

'''y^2 = x^3 + ax + b''', where a, b ∈ ℤp and the discriminant ≢ 0 (mod p),

together with a special point 𝒪 called the point at infinity.

Line 32:

Remark: there already is a task page requesting “a simplified (without modular arithmetic)

version of the [[Elliptic_curve_arithmetic|elliptic curve arithmetic]]”.

~~This~~ ~~new~~ ~~page~~ ~~is added because~~ modulo operations ~~are~~ ~~precisely~~ ~~essential~~ ~~for~~ ~~implementing~~

Here we do add modulo operations. If also the domain is changed from reals to rationals,

the elliptic curves are no longer continuous but break up into a finite number of distinct points.

[[wp:Elliptic_Curve_Digital_Signature_Algorithm|ECDSA]]: ~~we need a discrete, finite field to play in.~~

In that form we use them to implement [[wp:Elliptic_Curve_Digital_Signature_Algorithm|ECDSA]]:

;Elliptic curve digital signature algorithm.

A [[wp:Digital_signature|digital signature]] is the electronic analogue of a hand-written signature ~~that~~

A [[wp:Digital_signature|digital signature]] is the electronic analogue of a hand-written signature

convinces the recipient that a message has been sent intact by the presumed sender.

that convinces the recipient that a message has been sent intact by the presumed sender.

Anyone with access to the public key of the signer may verify this signature.

Changing even a single bit of a signed message will cause the verification procedure to fail.

Line 52:

Line 53:

'''ECDSA signature computation.''' To sign a message m, A does the following:

1. Compute message representative f = H(m), using a

[[wp:Cryptographic_hash_function|cryptographic hash function]].

Note that f can be greater than r but not longer (measuring bits).

Line 69:

Line 70:

To be cryptographically useful, the parameter r should have at least 250 bits.

The basis for the security of [[wp:Elliptic-curve_cryptography|elliptic curve cryptosystems]]

is the intractability of the elliptic curve discrete logarithm problem (ECDLP) in a group of this size:

given two points G, W ∈ E(ℤp), where W lies in the subgroup of order r generated by G,

Line 82:

Line 83:

hash value and a way to tamper with it). The program should be lenient where possible

(for example: if it accepts a composite modulus N it will either function as expected,

or demonstrate the principle of [[wp:Lenstra_elliptic-curve_factorization|elliptic curve factorization]]) ~~— but strict where required (a point G that is not on E will always cause failure). ~~

or demonstrate the principle of [[wp:Lenstra_elliptic-curve_factorization|elliptic curve factorization]])

— but strict where required (a point G that is not on E will always cause failure).

Toy ECDSA is of course completely useless for its cryptographic purpose.

If this bothers you, please add a multiple-precision version.