111 lines
5.4 KiB
Plaintext
111 lines
5.4 KiB
Plaintext
;Elliptic curves.
|
|
|
|
An [[wp:Elliptic_curve|elliptic curve]] E over ℤp (p ≥ 5) is defined by an equation of the form
|
|
'''y²= x³ + ax + b''', where a, b ∈ ℤp and the discriminant ≢ 0 (mod p),
|
|
together with a special point 𝒪 called the point at infinity.
|
|
The set '''E(ℤp)''' consists of all points (x, y), with x, y ∈ ℤp,
|
|
which satisfy the above defining equation, together with 𝒪.
|
|
|
|
There is a rule for adding two points on an elliptic curve to give a third point.
|
|
This addition operation and the set of points E(ℤp) form a group with identity 𝒪.
|
|
It is this group that is used in the construction of elliptic curve cryptosystems.
|
|
|
|
The addition rule — which can be explained geometrically — is summarized as follows:
|
|
<pre>
|
|
1. P + 𝒪 = 𝒪 + P = P for all P ∈ E(ℤp).
|
|
|
|
2. If P = (x, y) ∈ E(ℤp), then inverse -P = (x,-y), and P + (-P) = 𝒪.
|
|
|
|
3. Let P = (xP, yP) and Q = (xQ, yQ), both ∈ E(ℤp), where P ≠ -Q.
|
|
Then R = P + Q = (xR, yR), where
|
|
|
|
xR = λ^2 - xP - xQ
|
|
yR = λ·(xP - xR) - yP,
|
|
|
|
with
|
|
|
|
λ = (yP - yQ) / (xP - xQ) if P ≠ Q,
|
|
(3·xP·xP + a) / 2·yP if P = Q (point doubling).
|
|
</pre>
|
|
Remark: there already is a task page requesting “a simplified (without modular 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.
|
|
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 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.
|
|
|
|
'''ECDSA key generation.''' Party A does the following:<br />
|
|
1. Select an elliptic curve E defined over ℤp.<br />
|
|
The number of points in E(ℤp) should be divisible by a large prime r.<br />
|
|
2. Select a base point G ∈ E(ℤp) of order r (which means that rG = 𝒪).<br />
|
|
3. Select a random integer s in the interval [1, r - 1].<br />
|
|
4. Compute W = sG.<br />
|
|
The public key is (E, G, r, W), the private key is s.
|
|
|
|
'''ECDSA signature computation.''' To sign a message m, A does the following:<br />
|
|
1. Compute message representative f = H(m), using a
|
|
[[wp:Cryptographic_hash_function|cryptographic hash function]].<br />
|
|
Note that f can be greater than r but not longer (measuring bits).<br />
|
|
2. Select a random integer u in the interval [1, r - 1].<br />
|
|
3. Compute V = uG = (xV, yV) and c ≡ xV mod r (goto (2) if c = 0).<br />
|
|
4. Compute d ≡ u^-1·(f + s·c) mod r (goto (2) if d = 0).<br />
|
|
The signature for the message m is the pair of integers (c, d).
|
|
|
|
'''ECDSA signature verification.''' To verify A's signature, B should do the following:<br />
|
|
1. Obtain an authentic copy of A's public key (E, G, r, W).<br />
|
|
Verify that c and d are integers in the interval [1, r - 1].<br />
|
|
2. Compute f = H(m) and h ≡ d^-1 mod r.<br />
|
|
3. Compute h1 ≡ f·h mod r and h2 ≡ c·h mod r.<br />
|
|
4. Compute h1G + h2W = (x1, y1) and c1 ≡ x1 mod r.<br />
|
|
Accept the signature if and only if c1 = c.
|
|
|
|
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,
|
|
determine an integer k such that W = kG and 0 ≤ k < r.
|
|
|
|
|
|
;Task.
|
|
|
|
The task is to write a '''toy version''' of the ECDSA, quasi the equal of a real-world
|
|
implementation, but utilizing parameters that fit into standard arithmetic types.
|
|
To keep things simple there's no need for key export or a hash function (just a sample
|
|
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).<br />
|
|
Toy ECDSA is of course completely useless for its cryptographic purpose.
|
|
If this bothers you, please add a multiple-precision version.
|
|
|
|
|
|
;Reference.
|
|
|
|
Elliptic curves are in the [https://perso.telecom-paristech.fr/guilley/recherche/cryptoprocesseurs/ieee/00891000.pdf IEEE Std 1363-2000] (Standard Specifications for Public-Key Cryptography), see:
|
|
|
|
7. Primitives based on the elliptic curve discrete logarithm problem (p. 27ff.)
|
|
|
|
7.1 The EC setting<br />
|
|
7.1.2 EC domain parameters<br />
|
|
7.1.3 EC key pairs
|
|
|
|
7.2 Primitives<br />
|
|
7.2.7 ECSP-DSA (p. 35)<br />
|
|
7.2.8 ECVP-DSA (p. 36)
|
|
|
|
Annex A. Number-theoretic background<br />
|
|
A.9 Elliptic curves: overview (p. 115)<br />
|
|
A.10 Elliptic curves: algorithms (p. 121)
|
|
|
|
|
|
|
|
__TOC__
|
|
|