Elliptic Curve Digital Signature Algorithm: Difference between revisions
Content added Content deleted
(Added Go) |
m (remark rephrased) |
||
Line 3: | Line 3: | ||
;Elliptic curves. |
;Elliptic curves. |
||
An [[wp:Elliptic_curve|elliptic curve]] E over ℤp (p ≥ 5) is defined by an equation of the form |
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), |
'''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. |
together with a special point 𝒪 called the point at infinity. |
||
Line 32: | Line 32: | ||
Remark: there already is a task page requesting “a simplified (without modular arithmetic) |
Remark: there already is a task page requesting “a simplified (without modular arithmetic) |
||
version of the [[Elliptic_curve_arithmetic|elliptic curve arithmetic]]”. |
version of the [[Elliptic_curve_arithmetic|elliptic curve arithmetic]]”. |
||
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]]: |
In that form we use them to implement [[wp:Elliptic_Curve_Digital_Signature_Algorithm|ECDSA]]: |
||
;Elliptic curve digital signature algorithm. |
;Elliptic curve digital signature algorithm. |
||
A [[wp:Digital_signature|digital signature]] is the electronic analogue of a hand-written signature |
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. |
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. |
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:<br /> |
'''ECDSA signature computation.''' To sign a message m, A does the following:<br /> |
||
1. Compute message representative f = H(m), using a |
1. Compute message representative f = H(m), using a |
||
[[wp:Cryptographic_hash_function|cryptographic hash function]].<br /> |
[[wp:Cryptographic_hash_function|cryptographic hash function]].<br /> |
||
Note that f can be greater than r but not longer (measuring bits).<br /> |
Note that f can be greater than r but not longer (measuring bits).<br /> |
||
Line 69: | Line 70: | ||
To be cryptographically useful, the parameter r should have at least 250 bits. |
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]] |
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: |
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, |
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 |
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, |
(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]]) |
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).<br /> |
|||
Toy ECDSA is of course completely useless for its cryptographic purpose. |
Toy ECDSA is of course completely useless for its cryptographic purpose. |
||
If this bothers you, please add a multiple-precision version. |
If this bothers you, please add a multiple-precision version. |