Elliptic Curve Cryptography
Most of the products and standards that use public-key cryptography for encryption and digital signatures use RSA. As we have seen, the key length for secure RSA use has increased over recent years, and this has put a heavier processing load on applications using RSA. This burden has ramifications, especially for electronic commerce sites that conduct large numbers of secure transactions. A competing system challenges RSA: elliptic curve cryptography (ECC). ECC is showing up in standardisation efforts, including the IEEE P1363 Standard for Public-Key Cryptography.
The principal attraction of ECC, compared to RSA, is that it appears to offer equal security for a far smaller key size, thereby reducing processing overhead.
Abelian Group
An abelian group $G$, sometimes denoted by $\{G, \cdot \}$, is a set of elements with a binary operation, denoted by $\cdot$, that associates to each ordered pair $(a, b)$ of elements in $G$ an element $(a \cdot b)$ in $G$, such that the following axioms are obeyed:
For elliptic curve cryptography, an operation over elliptic curves, called addition, is used. Multiplication is defined by repeated addition. For example,
$$a \times k = (a + a + \cdots + a) \quad k \; times$$
where the addition is performed over an elliptic curve. Cryptanalysis involves determining $k$ given $a$ and $(a \times k)$
An elliptic curve is defined by an equation in two variables with coefficients. For cryptography, the variables and coefficients are restricted to elements in a finite field, which results in the definition of a finite abelian group.
Elliptic curves are not ellipses. They are so named because they are described by cubic equations, similar to those used for calculating the circumference of an ellipse. In general, cubic equations for elliptic curves take the following form, known as a Weierstrass equation:
where $a, b, c, d, e$ are real numbers and $x$ and $y$ take on values in the real numbers.For our purpose, it is sufficient to limit ourselves to equations of the form
$$y^2 =x^3 +ax+b$$
Such equations are said to be cubic, or of degree 3, because the highest exponent they contain is a 3. Also included in the definition of an elliptic curve is a single element denoted $O$ and called the point at infinity or the zero point, which we discuss subsequently. To plot such a curve, we need to compute
$$y=\sqrt{x^3 +ax+b}$$
For given values of $a$ and $b$, the plot consists of positive and negative values of $y$ for each value of $x$. Thus, each curve is symmetric about $y = 0.$ Figure below shows two examples of elliptic curves. As you can see, the formula sometimes produces weird looking curves.
Now, consider the set of points $E(a, b)$ consisting of all of the points $(x, y)$ that satisfy Equation together with the element $O$. Using a different value of the pair $(a, b)$ results in a different set $E(a, b).$ Using this terminology, the two curves in Figure below depict the sets $E(-1, 0)$ and $E(1, 1)$, respectively.
Geometric Description of Addition:It can be shown that a group can be defined based on the set $E(a, b) $ for specific values of $a$ and $b$ in Equation $y^2=x^3+ax+b$, provided the following condition is met:
$$4a^3 + 27b^2 \ne 0$$
To define the group, we must define an operation, called addition and denoted by +, for the set $E(a, b)$,where $a$ and $b$ satisfy the above Equation.In geometric terms, the rules for addition can be stated as follows:If three points on an elliptic curve lie on a straight line, their sum is $O$. From this definition, we can define the rules of addition over elliptic curve.
1. $O$ serves as the additive identity. Thus $O = - O$; for any point $P$ on the elliptic curve, $P + O = P.$ In what follows, we assume $P ≠ O$ and $Q ≠ O.$
2.The negative of a point $P$ is the point with the same $x$ coordinate but the negative of the $y$ coordinate; that is, if $P = (x, y)$, then $-P = (x, -y)$. Note that these two points can be joined by a vertical line. Note that $P + ( -P) = P - P = O.$
3.To add two points $P$ and $Q$ with different $x$ coordinates, draw a straight line between them and find the third point of intersection $R$. It is easily seen that there is a unique point $R$ that is the point of intersection (unless the line is tangent to the curve at either $P$ or $Q$, in which case we take $R = P$ or $R = Q$, respectively). To form a group structure, we need to define addition on these three points: $P + Q = -R$. That is, we define $P + Q$ to be the mirror (with respect to the $x$ axis) of the third point of intersection.Figure 10.4 illustrates this construction.
4. The geometric interpretation of the preceding item also applies to two points, $P$ and $- P$, with the same $x$ coordinate. The points are joined by a vertical line, which can be viewed as also intersecting the curve at the infinity point. We therefore have $P + (-P) = O$, which is consistent with item (2).
5. To double a point $Q$, draw the tangent line and find the other point of intersection $S$.Then $Q + Q = 2Q = -S.$
With the preceding list of rules, it can be shown that the set $E(a, b)$ is an abelian group.
Addition over Elliptic Curve
In this subsection, we present some results that enable calculation of additions over elliptic curves.For two distinct points, $P = (x_P, y_P)$ and $Q = (x_Q, y_Q),$ that are not negatives of each other, the slope of the line $l$ that joins them is $∆ = (y_Q - y_P)/(x_Q - x_P)$. There is exactly one other point where $l$ intersects the elliptic curve, and that is the negative of the sum of $P$ and $Q$. After some algebraic manipulation, we can express the sum $R = P + Q$ as
Elliptic Curve Over $Z_p$
Elliptic curve cryptography makes use of elliptic curves in which the variables and coefficients are all restricted to elements of a finite field. Two families of elliptic curves are used in cryptographic applications: prime curves over $Z_p$ and binary curves over $GF(2^m)$. For a prime curve over $Z_p$, we use a cubic equation in which the variables and coefficients all take on values in the set of integers from 0 through $p - 1$ and in which calculations are performed modulo $p.$ For a binary curve defined over $GF(2^m)$, the variables and coefficients all take on values in $GF(2^m)$ and in calculations are performed over $GF(2^m)$. Fernandes, points out that prime curves are best for software applications, because the extended bit-fiddling operations needed by binary curves are not required; and that binary curves are best for hardware applications, where it takes remarkably few logic gates to create a powerful, fast crypto system.
There is no obvious geometric interpretation of elliptic curve arithmetic over finite fields. The algebraic interpretation used for elliptic curve arithmetic over real numbers does readily carry over, and this is the approach we take.
For elliptic curves over $Z_p$, as with real numbers, we limit ourselves to equation with coefficients and variables limited to $Z_p$:
$$y^2 \pmod{p} = (x^3 + ax + b) \pmod{p}$$
For example, consider $a = 1, b = 1, x = 9, y = 7, p = 23$:
$$7^2 \pmod{23}= (9^3 + 9 + 1) \pmod{23}$$
$$ 49 \pmod{23} = 739 \pmod{23}$$
$$3=3$$
$$3=3$$
Now consider the set $E_p(a, b)$ consisting of all pairs of integers $(x, y)$ that satisfy Equation $y^2 \pmod{p} = (x^3 + ax + b) \pmod{p}$, together with a point at infinity $O.$ The coefficients $a$ and $b$ and the variables $x$ and $y$ are all elements of $Z_p.$
For example, let $p = 23$ and consider the elliptic curve $y^2 = x^3 + x + 1$. In this case, $a = b = 1.$
For the set $E_{23}(1, 1)$, we are only interested in the nonnegative integers in the quadrant from $(0, 0)$ through $(p - 1, p - 1)$ that satisfy the equation $\pmod p$. Table 10.1 lists the points (other than $O$) that are part of $E_{23}(1, 1)$.
Figure 10.5 plots the points of $E_{23}(1, 1)$; note that the points, with one exception, are symmetric about $y = 11.5$.It can be shown that a finite abelian group can be defined based on the set $E_p(a, b)$ provided that $(x^3 + ax + b) \pmod p$ has no repeated factors. This is equivalent to the condition.
$$4a^3+27b^2 \pmod p \ne 0 \pmod p$$
The rules for addition over $E_p(a, b)$, correspond to the algebraic technique described for elliptic curves defined over real numbers. For all points $P, Q ∈ E_p(a, b):$
1. $P + O = P.$
If $P = (x_P,y_P)$, then $P + (x_P, -y_P) = O$. The point $(x_P, -y_P)$ is the negative of $P,$ denoted as $-P$. For example, in $E_{23}(1, 1)$, for $P = (13, 7)$, we have $-P = (13, -7)$. But $-7 \pmod {23} = 16$. Therefore, $-P = (13, 16)$, which is also in $E_{23}(1, 1)$.
If $P = (x_p,y_p)$ and $Q = (x_Q,y_Q)$ with $P ≠ -Q,$ then $R = P + Q = (x_R,y_R)$
is determined by the following rules:
Refer Appendix Below for derivation
4. Multiplication is defined as repeated addition; for example, $4P =P + P + P + P.$
Discrete Logarithm Problem - Elliptic Curve
The addition operation in ECC is the counterpart of modular multiplication in RSA, and multiple addition is the counterpart of modular exponentiation. To form a cryptographic system using elliptic curves, we need to find a “hard problem” corresponding to factoring the product of two primes or taking the discrete logarithm.
Consider the equation $Q = kP$ where $Q, P ∈ E_P(a, b)$ and $k < p$. It is relatively easy to calculate $Q$ given $k$ and $P$ but it is hard to determine $k$ given $Q$ and $P$. This is called the discrete logarithm problem for elliptic curves.
For Example consider the group $E_{23}(9,17)$. This is the group defined by the equation $y^2 \; mod \; 23 = (x^3 + 9x + 17) \; mod \;23$. What is the discrete logarithm $k$ of $Q = (4, 5)$ to the base $P = (16, 5)$.The brute-force method is to compute multiples of $P$ until $Q $ is found. Thus,
8P = (12,17);9P = (4,5)$
Because $9P = (4, 5) = Q$, the discrete logarithm $Q = (4, 5)$ to the base $P = (16, 5)$ is $k = 9$. In a real application, $k$ would be so large as to make the brute- force approach infeasible.
Diffie-Hellman Key Exchange
Key exchange using elliptic curves can be done in the following manner. First pick a large integer $q$, which is either a prime number $p$ or an integer of the form $2^m$, and elliptic curve parameters $a$ and $b$. This defines the elliptic group of points $E_q(a, b)$.Next, pick a base point $G = (x_1, y_1)$ in $E_p(a, b)$ whose order is a very large value $n$. The order $n$ of a point $G$ on an elliptic curve is the smallest positive integer $n$ such that $nG = 0$. $E_q(a, b)$ and $G$ are parameters of the cryptosystem known to all participants.
1. A selects an integer $n_A$ less than $n$. This is A’s private key. A then generates a public key $P_A = n_A * G$; the public key is a point in $E_q(a, b).$
2. B similarly selects a private key $n_B$ and computes a public key $P_B$.
3. A generates the secret key $k = n_A * P_B$. B generates the secret key $k = n_B * P_A$.
The two calculations in step 3 produce the same result because
$$n_A *P_B =n_A *(n_B *G)=n_B *(n_A *G)=n_B *P_A$$
To break this scheme, an attacker would need to be able to compute $k$ given $G$ and $kG$, which is assumed to be hard.
As an example, take $p = 211$; $E_p(0, -4),$ which is equivalent to the curve $y^2 = x^3 - 4$; and $G = (2, 2)$. One can calculate that $240G = O$. A’s private key is $n_A = 121$, so A’s public key is $P_A = 121(2, 2) = (115, 48).$ B’s private key is $n_B = 203$, so B’s public key is $203(2, 2)= (130, 203)$. The shared secret key is $121(130, 203) = 203(115, 48) = (161, 69).$
Note that the secret key is a pair of numbers. If this key is to be used as a session key for conventional encryption, then a single number must be generated. We could simply use the $x$ coordinates or some simple function of the $x$ coordinate.
Elliptic Curve Encryption/Decryption
Several approaches to encryption/decryption using elliptic curves have been analyzed in the literature. In this subsection, we look at perhaps the simplest. The first task in this system is to encode the plaintext message $m$ to be sent as an $(x, y)$ point $P_m.$
It is the point $P_m$ that will be encrypted as a ciphertext and subsequently decrypted. Note that we cannot simply encode the message as the $x$ or $y$ coordinate of a point, because not all such coordinates are in $E_q(a, b);$
As with the key exchange system, an encryption/decryption system requires a point $G$ and an elliptic group $E_q(a, b)$ as parameters. Each user A selects a private key $n_A$ and generates a public key $P_A = n_A * G.$
To encrypt and send a message $P_m$ to B, A chooses a random positive integer $k$ and produces the ciphertext $C_m$ consisting of the pair of points:
Note that A has used B’s public key $P_B$. To decrypt the ciphertext, B multiplies the first point in the pair by B’s private key and subtracts the result from the second point:
Note that A has used B’s public key $P_B$. To decrypt the ciphertext, B multiplies the first point in the pair by B’s private key and subtracts the result from the second point:
$$P_m +kP_B -n_B(kG)=P_m +k(nB_G)-n_B(kG)=P_m$$
A has masked the message $P_m$ by adding $kP_B$ to it. Nobody but A knows the value of $k$, so even though $P_b$ is a public key, nobody can remove the mask $kP_B$. However, A also includes a “clue,” which is enough to remove the mask if one knows the private key $nB$. For an attacker to recover the message, the attacker would have to compute $k$ given $G$ and $kG$, which is assumed to be hard.
Let us consider a simple example. The global public elements are $q = 257; E_q(a, b) = E_{257}(0, -4),$ which is equivalent to the curve $y^2 = x^3 - 4;$ and $G = (2, 2). $
Bob’s private key is $n_B = 101$, and his public key is $P_B = n_BG = 101(2, 2) = (197, 167).$
Alice wishes to send a message to Bob that is encoded in the elliptic point $P_m = (112, 26)$.
Alice chooses random integer $k = 41$ and computes $kG = 41(2, 2) = (136, 128), kP_B = 41(197, 167) = (68, 84)$ and $P_m + kP_B = (112, 26) + (68, 84) = (246, 174).$
Alice sends the ciphertext $C_m = (C_1, C_2) =\{kG,P_m+kP_B\}= \{(136, 128), (246, 174)\}$ to Bob.
Security of Elliptic Curve Cryptography
The security of ECC depends on how difficult it is to determine $k$ given $kP$ and $P$. This is referred to as the elliptic curve logarithm problem. The fastest known technique for taking the elliptic curve logarithm is known as the Pollard rho method. Table 10.3, from NIST SP 800-57 (Recommendation for Key Management—Part 1: General, September 2015), compares various algorithms by showing comparable key sizes in terms of computational effort for cryptanalysis. As can be seen, a considerably smaller key size can be used for ECC compared to RSA.
Based on this analysis, SP 800-57 recommends that at least through 2030, acceptable key lengths are from 3072 to 14,360 bits for RSA and 256 to 512 bits for ECC. Similarly, the European Union Agency for Network and Information Security (ENISA) recommends in their 2014 report (Algorithms, Key Size and Parameters report—2014, November 2014) minimum key lengths for future system of 3072 bits and 256 bits for RSA and ECC, respectively.
Analysis indicates that for equal key lengths, the computational effort required for ECC and RSA is comparable. Thus, there is a computational advantage to using ECC with a shorter key length than a comparably secure RSA.
Python Code - Elliptic Curve Diffie-Hellman Key Exchange
Here’s a simple toy example of Elliptic Curve Diffie-Hellman (ECDH) key exchange using the Python library
cryptography. If you don't have this library installed, you can install it using.pip install cryptography
alice_shared_key and bob_shared_key) should be identical if the exchange is successful.from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import serialization
# Alice generates her private and public keys
alice_private_key = ec.generate_private_key(ec.SECP256R1(), default_backend())
alice_public_key = alice_private_key.public_key()
# Bob generates his private and public keys
bob_private_key = ec.generate_private_key(ec.SECP256R1(), default_backend())
bob_public_key = bob_private_key.public_key()
# Alice computes the shared key using Bob's public key
alice_shared_key = alice_private_key.exchange(ec.ECDH(), bob_public_key)
# Bob computes the shared key using Alice's public key
bob_shared_key = bob_private_key.exchange(ec.ECDH(), alice_public_key)
# Now both shared keys should be identical
print("Alice's shared key:", alice_shared_key)
print("Bob's shared key: ", bob_shared_key)
# Check if both shared keys are identical
if alice_shared_key == bob_shared_key:
print("Key exchange successful!")
else:
print("Key exchange failed!")
Python Code - Elliptic Curve Encryption/ Decryption
import os
from ecdsa import SigningKey, SECP256k1
# Function to convert bytes to integer
def bytes_to_int(b):
return int.from_bytes(b, byteorder='big')
# Function to convert integer to bytes
def int_to_bytes(i, length):
return i.to_bytes(length, byteorder='big')
# Encrypt with ECC public key
def ecc_encrypt(public_key, plaintext):
# Step 1: Convert plaintext to an integer
plaintext_int = bytes_to_int(plaintext)
# Step 2: Generate ephemeral private key
ephemeral_private_key = SigningKey.generate(curve=SECP256k1)
ephemeral_public_key = ephemeral_private_key.get_verifying_key()
# Step 3: Compute the shared secret: ephemeral_private_key * public_key
shared_secret = ephemeral_private_key.privkey.secret_multiplier * public_key.pubkey.point
# Step 4: Encrypt the message by adding the shared secret's x-coordinate
shared_secret_int = shared_secret.x()
ciphertext_int = plaintext_int + shared_secret_int
return ephemeral_public_key, ciphertext_int
# Decrypt with ECC private key
def ecc_decrypt(private_key, ephemeral_public_key, ciphertext_int):
# Step 1: Compute the shared secret: private_key * ephemeral_public_key
shared_secret = private_key.privkey.secret_multiplier * ephemeral_public_key.pubkey.point
# Step 2: Decrypt the message by subtracting the shared secret's x-coordinate
shared_secret_int = shared_secret.x()
plaintext_int = ciphertext_int - shared_secret_int
# Step 3: Convert the plaintext integer back to bytes
plaintext_length = (plaintext_int.bit_length() + 7) // 8
plaintext = int_to_bytes(plaintext_int, plaintext_length)
return plaintext
# Main demonstration
if __name__ == "__main__":
# Step 1: Generate ECC key pair for the recipient (Bob)
bob_private_key = SigningKey.generate(curve=SECP256k1)
bob_public_key = bob_private_key.get_verifying_key()
# Step 2: Alice wants to send an encrypted message to Bob
plaintext = b"Hello Bob, this is a secret message."
# Alice encrypts the message using Bob's public key
ephemeral_public_key, ciphertext_int = ecc_encrypt(bob_public_key, plaintext)
# Step 3: Bob receives the encrypted message and decrypts it using his private key
decrypted_message = ecc_decrypt(bob_private_key, ephemeral_public_key, ciphertext_int)
# Output results
print(f"Original Message: {plaintext}")
print(f"Decrypted Message: {decrypted_message}")
Appendix
The derivation of the formulas for adding two points on an elliptic curve follows from basic algebra and geometry. The elliptic curve equation we're working with is in Weierstrass form:
Let's derive the formulas for the addition of two points and and doubling a point on the curve.
1. Addition of Two Distinct Points and
To find the sum of two points and on the elliptic curve, the idea is to:
- Draw a straight line through the two points.
- The line will intersect the elliptic curve at a third point.
- The reflection of this third point across the x-axis gives the result of the addition
Step 1: Find the equation of the line through and
The slope of the line passing through and
The equation of this line in point-slope form is:
Step 2: Substituting the line equation into the elliptic curve equation
To find the third point of intersection, substitute the expression for into the elliptic curve equation
This expands into:
Simplify this expression to form a cubic equation in :
This cubic equation in has three solutions corresponding to the x-coordinates of the points of intersection: , , and .
Step 3: Use algebraic properties of elliptic curves
The sum of the x-coordinates of the three intersection points must equal the sum of the slopes of the tangents at those points (from algebraic geometry). Therefore, the sum of the x-coordinates is:
Solving for , we get:
Step 4: Find
Now that we have , substitute it back into the line equation to find :
Thus, the coordinates of the resulting point are:
2. Doubling a Point:
When , we are dealing with the point doubling operation. The line through is now the tangent line to the curve at .
Step 1: Slope of the tangent line
To compute the slope of the tangent line at , we take the derivative of the curve equation with respect to .
Differentiating implicitly, we get:
So, the slope of the tangent line at is:
Step 2: Find and
With the slope , we can now use the same procedure as before to find the new coordinates The x-coordinate is:
And the y-coordinate is:
Thus, the point is given by:
3. Special Cases
- Point at Infinity (Identity Element): The point at infinity acts as the identity element for elliptic curve addition. For any point , we have:
- Vertical Line (P + (-P) = O): If and , then the points lie on a vertical line. In this case, their sum is the point at infinity:
Summary of the Derived Formulas
For (distinct points):
For (point doubling):
These formulas form the basis of elliptic curve arithmetic and are used in elliptic curve cryptography (ECC) for operations like key exchange, encryption, and digital signatures.
Comments
Post a Comment