Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

21.5 Elliptic Curve Cryptosystems

Elliptic curve versions exist for many cryptosystems, in particular those involving discrete logarithms. An advantage of elliptic curves compared to working with integers mod $p$ $p$ is the following. In the integers, it is possible to use the factorization of integers into primes (especially small primes) to attack the discrete logarithm problem. This is known as the index calculus and is described in Section 10.2. There seems to be no good analog of this method for elliptic curves. Therefore, it is possible to use smaller primes, or smaller finite fields, with elliptic curves and achieve a level of security comparable to that for much larger integers mod $p .$ $p .$ This allows great savings in hardware implementations, for example.

In the following, we describe three elliptic curve versions of classical algorithms. Here is a general procedure for changing a classical system based on discrete logarithms into one using elliptic curves:

Nonzero numbers mod $p$ $p$	$⟷$ $⟷$	Points on an elliptic curve
Multiplication mod $p$ $p$	$⟷$ $⟷$	Elliptic curve addition
1 (multiplicative identity)	$⟷$ $⟷$	$∞$ $∞$ (additive identity)
Division mod $p$ $p$	$⟷$ $⟷$	Subtraction of points
Exponentiation: $g^{k}$ $g^{k}$	$⟷$ $⟷$	Integer times a point: $k P = P + \dots + P$ $k P = P + \dots + P$
$p - 1$ $p - 1$	$⟷$ $⟷$	$n =$ $n =$ number of points on the curve
Fermat: $a^{p - 1} \equiv 1$ $a^{p - 1} \equiv 1$	$⟷$ $⟷$	$n P = ∞$ $n P = ∞$ (Lagrange’s theorem)
Discrete log problem:	$⟷$ $⟷$	Elliptic curve discrete log problem:
Solve $g^{k} \equiv h$ $g^{k} \equiv h$ for $k$ $k$		Solve $k P = Q$ $k P = Q$ for $k$ $k$

Notes:

The elliptic curve is an elliptic curve mod some prime, so $n,$ $n,$ the number of points on the curve, including $∞,$ $∞,$ is finite.
Addition and subtraction of points on an elliptic curve are of equivalent complexity (if $Q = (x, y),$ $Q = (x, y),$ then $- Q = (x, - y)$ $- Q = (x, - y)$ and $P - Q$ $P - Q$ is computed as $P + (- Q)$ $P + (- Q)$ ), but multiplication mod $p$ $p$ is much easier than division mod $p$ $p$ (via the extended Euclidean algorithm). Both mod $p$ $p$ operations are usually simpler than the elliptic curve operations.
The elliptic curve discrete log problem is believed to be harder than the mod $p$ $p$ discrete log problem.
If we fix a number $m$ $m$ and look at the set of all integers mod $m,$ $m,$ then the analogues of the above are: addition mod $m,$ $m,$ the additive identity 0, subtraction mod $m,$ $m,$ multiplying an integer times a number mod $m$ $m$ (that is, $k a = a + a + \dots + a (m o d m)$ $k a = a + a + \dots + a (m o d m)$ ), $m =$ $m =$ the number of integers mod $m,$ $m,$ the relation $m a \equiv 0 (m o d m),$ $m a \equiv 0 (m o d m),$ and the additive discrete log problem: Solve $k a \equiv b (m o d m)$ $k a \equiv b (m o d m)$ for $k,$ $k,$ which can be done easily via the Extended Euclidean algorithm. This shows that the difficulty of a discrete log problem depends on the binary operation.

21.5.1 An Elliptic Curve ElGamal Cryptosystem

We recall the non-elliptic curve version. Alice wants to send a message $x$ $x$ to Bob, so Bob chooses a large prime $p$ $p$ and an integer $α mod p .$ $α mod p .$ He also chooses a secret integer $s$ $s$ and computes $β \equiv α^{s} (m o d p) .$ $β \equiv α^{s} (m o d p) .$ Bob makes $p, α, β$ $p, α, β$ public and keeps $s$ $s$ secret. Alice chooses a random $k$ $k$ and computes $y_{1}$ $y_{1}$ and $y_{2},$ $y_{2},$ where

y_{1} \equiv α^{k} and y_{2} \equiv x β^{k} (mod p) .

$y_{1} \equiv α^{k} and y_{2} \equiv x β^{k} (mod p) .$

She sends $(y_{1}, y_{2})$ $(y_{1}, y_{2})$ to Bob, who then decrypts by calculating

x \equiv y_{2} y_{1}^{- s} (m o d p) .

$x \equiv y_{2} y_{1}^{- s} (m o d p) .$

Now we describe the elliptic curve version. Bob chooses an elliptic curve $E (m o d p),$ $E (m o d p),$ where $p$ $p$ is a large prime. He chooses a point $α$ $α$ on $E$ $E$ and a secret integer $s .$ $s .$ He computes

β = s α (= α + α + \dots + α) .

$β = s α (= α + α + \dots + α) .$

The points $α$ $α$ and $β$ $β$ are made public, while $s$ $s$ is kept secret. Alice expresses her message as a point $x$ $x$ on $E$ $E$ (see Section 21.5). She chooses a random integer $k,$ $k,$ computes

y_{1} = k α and y_{2} = x + k β,

$y_{1} = k α and y_{2} = x + k β,$

and sends the pair $y_{1}, y_{2}$ $y_{1}, y_{2}$ to Bob. Bob decrypts by calculating

x = y_{2} - s y_{1} .

$x = y_{2} - s y_{1} .$

A more workable version of this system is due to Menezes and Vanstone. It is described in [Stinson1, p. 189].

Example

We must first generate a curve. Let’s use the prime $p = 8831,$ $p = 8831,$ the point $G = (x, y) = (4, 11),$ $G = (x, y) = (4, 11),$ and $b = 3 .$ $b = 3 .$ To make $G$ $G$ lie on the curve $y^{2} \equiv x^{3} + b x + c (m o d p),$ $y^{2} \equiv x^{3} + b x + c (m o d p),$ we take $c = 45 .$ $c = 45 .$ Alice has a message, represented as a point $P_{m} = (5, 1743),$ $P_{m} = (5, 1743),$ that she wishes to send to Bob. Here is how she does it.

Bob has chosen a secret random number $s_{B} = 3$ $s_{B} = 3$ and has published the point $s_{B} G = (413, 1808) .$ $s_{B} G = (413, 1808) .$

Alice downloads this and chooses a random number $k = 8 .$ $k = 8 .$ She sends Bob $k G = (5415, 6321)$ $k G = (5415, 6321)$ and $P_{m} + k (s_{B} G) = (6626, 3576) .$ $P_{m} + k (s_{B} G) = (6626, 3576) .$ He first calculates $s_{B} (k G) = 3 (5415, 6321) = (673, 146) .$ $s_{B} (k G) = 3 (5415, 6321) = (673, 146) .$ He now subtracts this from $(6626, 3576) :$ $(6626, 3576) :$

(6626, 3576) - (673, 146) = (6626, 3576) + (673, - 146) = (5, 1743) .

$(6626, 3576) - (673, 146) = (6626, 3576) + (673, - 146) = (5, 1743) .$

Note that we subtracted points by using the rule $P - Q = P + (- Q)$ $P - Q = P + (- Q)$ from Section 21.1.

For another example, see Example 47 in the Computer Appendices.

21.5.2 Elliptic Curve Diffie-Hellman Key Exchange

Alice and Bob want to exchange a key. In order to do so, they agree on a public basepoint $G$ $G$ on an elliptic curve $E : y^{2} \equiv x^{3} + b x + c (m o d p) .$ $E : y^{2} \equiv x^{3} + b x + c (m o d p) .$ Let’s choose $p = 7211$ $p = 7211$ and $b = 1$ $b = 1$ and $G = (3, 5) .$ $G = (3, 5) .$ This forces us to choose $c = 7206$ $c = 7206$ in order to have the point on the curve. Alice chooses $N_{A}$ $N_{A}$ randomly and Bob chooses $N_{B}$ $N_{B}$ randomly. Let’s suppose $N_{A} = 12$ $N_{A} = 12$ and $N_{B} = 23 .$ $N_{B} = 23 .$ They keep these private to themselves but publish $N_{A} G$ $N_{A} G$ and $N_{B} G .$ $N_{B} G .$ In our case, we have

N_{A} G = (1794, 6375) and N_{B} G = (3861, 1242) .

$N_{A} G = (1794, 6375) and N_{B} G = (3861, 1242) .$

Alice now takes $N_{B} G$ $N_{B} G$ and multiplies by $N_{A}$ $N_{A}$ to get the key:

N_{A} (N_{B} G) = 12 (3861, 1242) = (1472, 2098) .

$N_{A} (N_{B} G) = 12 (3861, 1242) = (1472, 2098) .$

Similarly, Bob takes $N_{A} G$ $N_{A} G$ and multiplies by $N_{B}$ $N_{B}$ to get the key:

N_{B} (N_{A} G) = 23 (1794, 6375) = (1472, 2098) .

$N_{B} (N_{A} G) = 23 (1794, 6375) = (1472, 2098) .$

Notice that they have the same key.

For another example, see Example 48 in the Computer Appendices.

21.5.3 ElGamal Digital Signatures

There is an elliptic curve analog of the procedure described in Section 13.2. A few modifications are needed to account for the fact that we are working with both integers and points on an elliptic curve.

Alice wants to sign a message $m$ $m$ (which might actually be the hash of a long message). We assume $m$ $m$ is an integer. She fixes an elliptic curve $E (m o d p),$ $E (m o d p),$ where $p$ $p$ is a large prime, and a point $A$ $A$ on $E .$ $E .$ We assume that the number of points $N$ $N$ on $E$ $E$ has been calculated and assume $0 \leq m < N$ $0 \leq m < N$ (if not, choose a larger $p$ $p$ ). Alice also chooses a private integer $a$ $a$ and computes $B = a A .$ $B = a A .$ The prime $p,$ $p,$ the curve $E,$ $E,$ the integer $n,$ $n,$ and the points $A$ $A$ and $B$ $B$ are made public. To sign the message, Alice does the following:

Chooses a random integer $k$ $k$ with $1 \leq k < N$ $1 \leq k < N$ and $gcd (k, N) = 1,$ $gcd (k, N) = 1,$ and computes $R = k A = (x, y)$ $R = k A = (x, y)$
Computes $s \equiv k^{- 1} (m - a x) (m o d N)$ $s \equiv k^{- 1} (m - a x) (m o d N)$
Sends the signed message $(m, R, s)$ $(m, R, s)$ to Bob

Note that $R$ $R$ is a point on $E,$ $E,$ and $m$ $m$ and $s$ $s$ are integers.

Bob verifies the signature as follows:

Downloads Alice’s public information $p, E, A, B$ $p, E, A, B$
Computes $V_{1} = x B + s R$ $V_{1} = x B + s R$ and $V_{2} = m A$ $V_{2} = m A$
Declares the signature valid if $V_{1} = V_{2}$ $V_{1} = V_{2}$

The verification procedure works because

V_{1} = x B + s R = x a A + k^{- 1} (m - a x) (k A) = x a A + (m - a x) A = m A = V_{2} .

$V_{1} = x B + s R = x a A + k^{- 1} (m - a x) (k A) = x a A + (m - a x) A = m A = V_{2} .$

There is a subtle point that should be mentioned. We have used $k^{- 1}$ $k^{- 1}$ in this verification equation as the integer mod $N$ $N$ satisfying $k^{- 1} k \equiv 1 (m o d N) .$ $k^{- 1} k \equiv 1 (m o d N) .$ Therefore, $k^{- 1} k$ $k^{- 1} k$ is not 1, but rather an integer congruent to 1 mod $N .$ $N .$ So $k^{- 1} k = 1 + t N$ $k^{- 1} k = 1 + t N$ for some integer $t .$ $t .$ It can be shown that $N A = ∞ .$ $N A = ∞ .$ Therefore,

k^{- 1} k A = (1 + t N) A = A + t (N A) = A + t ∞ = A .

$k^{- 1} k A = (1 + t N) A = A + t (N A) = A + t ∞ = A .$

This shows that $k^{- 1}$ $k^{- 1}$ and $k$ $k$ cancel each other in the verification equation, as we implicitly assumed above.

The classical ElGamal scheme and the present elliptic curve version are analogs of each other. The integers mod $p$ $p$ are replaced with the elliptic curve $E,$ $E,$ and the number $p - 1$ $p - 1$ becomes $N .$ $N .$ Note that the calculations in the classical scheme work with integers that are nonzero mod $p,$ $p,$ and there are $p - 1$ $p - 1$ such congruence classes. The elliptic curve version works with points on the elliptic curve that are multiples of $A,$ $A,$ and the number of such points is a divisor of $N .$ $N .$

The use of the $x -coordinate$ $x -coordinate$ of $R$ $R$ in the elliptic version is somewhat arbitrary. Any method of assigning integers to points on the curve would work. Using the $x -coordinate$ $x -coordinate$ is an easy choice. Similarly, in the classical ElGamal scheme, the use of the integer $r$ $r$ in the mod $p - 1$ $p - 1$ equation for $s$ $s$ might seem a little unnatural, since $r$ $r$ was originally defined mod $p .$ $p .$ However, any method of assigning integers to the integers mod $p$ $p$ would work (see Exercise 16 in Chapter 13). The use of $r$ $r$ itself is an easy choice.

There is an elliptic curve version of the Digital Signature Algorithm that is similar to the preceding (Exercise 24).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 21.5 Elliptic Curve Cryptosystems

Create new playlist

Sign In

Sign Up

Table of Contents for
21.5 Elliptic Curve Cryptosystems