Alice and Bob are two parties in a network communication, and they have decided to use the Elliptic Curve based ElGamal Encryption Scheme to communicate securely over a public channel. Consider Alice as the sender and Bob as the receiver. In non-mathematical terms, we can list the steps involved in achieving a secure communication between Alice and Bob as follows:
- Alice and Bob choose an Elliptic Curve. Let’s name this curve as E.
- Alice setup her Public Key P_A and Secret Key S_A. Alice publishes her Public Key so that Bob can download it later.
- Similarly, Bob setup his Public Key P_B and Secret Key S_B. Bob publishes his Public Key so Alice can use it.
- When Alice wants to send a message to Bob, she downloads Bob’s Public Key P_B. Let M be the message. M is known as Plaintext
- Alice uses Bob’s public key P_B and her secret key S_A to convert the plaintext message M into a codeword knows as Ciphertext. Let C be the ciphertext. This process is called encryption. Alice sends C to Bob.
- Upon receiving the codeword C from Alice, Bob uses his secret key S_B and Alice’s public key P_A to convert C back into the plaintext message M. This process is called decryption
SECG (Standards for Efficient Cryptography Group) has approved a list of pre-defined Elliptic Curves, such as secp192k1, secp224r1, etc., for use in PKI (Public Key Cryptography). We could use a curve from this set to implement ElGamal Encryption Scheme, but as our goal is to learn about elliptic curves, we will look into how we can generate an elliptic curve for our use.
In order to generate an elliptic curve to be used as a cryptographic primitive, we first need a very large prime number. How do we find a prime number? It’s easy to search for smaller prime numbers. We could use the trial division method. It’s a brute force method and the time complexity is in the order of O(2^{n/2}) for an n-bit integer. Sieve of Eratosthenes performs better with a worst-case complexity of O(n \log \log n). These primality testing algorithms are infeasible when considering the magnitude of numbers used in cryptography. Almost all cryptographic applications, such as OpenSSL, GMP, GnuPG, etc use a probabilistic primality testing algorithm knows as the Miller-Rabin Test.
We will go through some mathematical preliminaries required to understand searching of large prime numbers and generation of elliptic curves.
Modular Arithmetic
Definition 1.1 (Division Algorithm) Let a \in \mathbb{Z} and m \in \mathbb{Z^+}, there exists unique integers q, \space r \in \mathbb{Z} and 0 \le r < m such that a = mq + r. In this equation, a is the dividend, m is the divisor, q is the quotient and r is the remainder.
We can rewrite the above equation as a \equiv r \mod m where m | (a\mathord{-}r). We say that a is congruent to r modulo m and m is the modulus of the congruence.
Addition: a \hspace{-0.15cm}\pmod m + b \hspace{-0.15cm}\pmod m = (a + b) \hspace{-0.15cm}\pmod m
Negative: -a \hspace{-0.15cm}\pmod m = (m\mathord{-}a) \hspace{-0.15cm}\pmod m
Subtraction: a \hspace{-0.15cm}\pmod m\mathord{-} b \hspace{-0.15cm}\pmod m = a\mathord{-}b \hspace{-0.15cm}\pmod m
Multiplication: a \hspace{-0.15cm}\pmod m \cdot b \hspace{-0.15cm}\pmod m = a \cdot b \hspace{-0.15cm}\pmod m
Division
In order to divide one integer by another in modular arithmetic, we need to familiarise with a concept called inverse of an element. Let b \in \mathbb{Z}, m \in \mathbb{Z^+} and gcd(b, m) = 1, we define inverse of b as the existence of the element b^{-1} \in \mathbb{Z} such that
b \cdot b^{-1} = 1 \hspace{-0.15cm}\mod m
Inverse of b exists only if gcd(b, m) = 1. Hence if we want to calculate a \div b (\hspace{-0.15cm}\mod m):
\begin{aligned} a \div b\hspace{-0.15cm}\pmod m = a \cdot b^{\mathord{-}1}\hspace{-0.15cm}\pmod m \end{aligned}
Inverse Modulo Calculation
Theorem 1.2 (Bezout’s Identity) Let a,\space b \in \mathbb{Z} and gcd(a, m) = d, then we can write gcd as a linear combination of a and m as:
d = mx + by; where x, y are unique integers.
As it’s mentioned above, b^{\mathord{-}1}\hspace{-0.15cm}\pmod m exists, if gcd(b, m) = 1 and hence we can rewrite the Bezout’s Identity as:
mx + by = 1
The value of y will be b^{-1} and we can use Extended Euclidian Algorithm1 to solve for x and y.
Extended Euclidian Algorithm
- Initialise vectors U, V as U = [m, 1, 0] and V = [b, 0, 1]
- Calculate W = U - \text{\(\lfloor\frac{U[0]}{V[0]}\rfloor\)}V
- Set U = V
- Set V = W
- If V[0] \gt 0, go to step 2, else x = U[1], y = U[2]
Modular Exponentiation
Question.Calculate 21^{47} \hspace{-0.15cm}\pmod{71}
We can compute 21^{47} \hspace{-0.15cm}\pmod{71} using repeated squaring as below:
\begin{aligned} & \text{We can write }21^{47} \hspace{-0.15cm}\pmod{71} = 21^{40} \times 21^7 \hspace{-0.15cm}\pmod{71}\\ &\text{ We will first calculate }21^{40} \hspace{-0.15cm}\pmod{71} \text{using repeated squaring}\\ &\text{ and then use a different method for calculating }21^{7} \hspace{-0.15cm}\pmod{71}\\ & 21^{2} \equiv 15\hspace{-0.20cm}\pmod{71} \\ & \therefore 21^4 = (21^2)^2 = 15^2 \hspace{-0.20cm}\pmod{71} \equiv 12\hspace{-0.20cm}\pmod{71} \\ & \implies 21^8 = (21^4)^2 = 12^2 \equiv 2\hspace{-0.20cm}\pmod{71} \\ & \implies 21^{16} = (21^8)^2 = 2^2 \equiv 4 \hspace{-0.20cm}\pmod{71} \\ & \implies 21^{32} = (21^{16})^2 = 4^2 \equiv 16\hspace{-0.20cm}\pmod{71} \\ & \implies 21^{40} = 21^{32}\times21^{8}\hspace{-0.20cm}\pmod{71} \equiv 16\times2\hspace{-0.20cm}\pmod{71}\equiv32\hspace{-0.20cm}\pmod{71} \\ \\ & \text{We will calculate now }21^7\hspace{-0.20cm}\pmod{71} \text{using the below steps:}\\ & \text{(We could calculate }21^7\hspace{-0.20cm}\pmod{71} \text{ using repeated squaring, but I want to show}\\ &\text{you a different method for fast modular exponentiation. We have formalised latter }\\ &\text{method as a computer algorithm below}.\\ \\ & \text{The binary representation for }7 = [111] \sim [d_2d_1d_0] \\ & \text{Let } a = 1 \text{ and } s = 21 \\ & k = 0: \text{Since } d_k = 1, a = a \times s = 21\hspace{-0.20cm}\pmod{71}, s = s^2 = 15\hspace{-0.20cm}\pmod{71} \\ & k = 1: \text{Since } d_k = 1, a = a \times s = 31\hspace{-0.20cm}\pmod{71}, s = s^2 = 12\hspace{-0.20cm}\pmod{71} \\ & k = 2: \text{Since } d_k = 1, a = a \times s = 17\hspace{-0.20cm}\pmod{71}, \\ & \implies 21^7 \equiv 17 \hspace{-0.20cm}\pmod{71} \\ & \therefore 21^{47} = 21^{40} \times 21^{7} = 32 \times 17 \equiv 47\hspace{-0.20cm}\pmod{71} \text{ and hence the answer} \end{aligned}
Algorithm: Fast Modular Exponentiation
Input: b \in \mathbb{Z}, \space e \in \mathbb{Z}, \space m \in \mathbb{Z}
Output: a \lt m \in \mathbb{Z} \text{ such that } b^e \equiv a \hspace{-0.10cm}\pmod{m}
Initialise a \leftarrow 1
Initialise b \leftarrow b \mathbin{\%} m be the lower bound for the message value
While e \gt 0\space Do
/*Logical AND operation of integer n with integer 1 */
/*will extract the LSB of n*/
If e \land 1 = 1\space Then
a \leftarrow (a \times s) \mathbin{\%} m
End If
s \leftarrow (s \times s) \mathbin{\%} m
e \leftarrow e \div 2
End While
Ring Of Integers Modulo m
The congruence modulo m is an equivalence relation(reflexive, symmetric and transitive) and hence we can group the set of integers into m equivalance classes also known as congruence classes. A congruence class of a\hspace{-0.05cm}\pmod m is defined as:
[a] = \{x\space |\space x \equiv a \hspace{-0.05cm}\pmod m\}
Example 1.1 Let m = 3. The congruence classes \mod 3 are:
\begin{aligned} [0] &= \{\cdots,-6,-3, 0, 3, 6,\cdots\}\\ [1] &= \{\cdots,-5,-2, 1, 4, 7,\cdots\}\\ [2] &= \{\cdots,-4,-1, 2, 5, 8,\cdots\} \end{aligned}
The set of congruence classes \pmod m are represented as \mathbb{Z}/m\mathbb{Z} or \mathbb{Z}_m.
\begin{aligned} \mathbb{Z}_m &= \{0, 1, 2, \cdots, m - 1\}\\ &= \text{Set of remainders when dividing by }m. \end{aligned}
The set \mathbb{Z}_m is a commutative ring with unity and it has addition(+) and multiplication(\cdot) modulo m defined on it satisfying the following properties:
- Associativity for addition: a + (b + c) = (a + b) + c \space\space \forall a, b, c \in \mathbb{Z}_m
- Commutativity of addition: a + b = b + a \space\space \forall a, b \in \mathbb{Z}_m
- Additive Identity: \exists 0 \in \mathbb{Z}_m\space \text{such that}\space 0 + a = a + 0 = a \space\space \forall a \in \mathbb{Z}_m
- Additive Inverses: \forall a \in \mathbb{Z}_m, \\ \space \exists \mathord{-}a \in \mathbb{Z}_m\space \text{known as the additive inverse of }a\space \text{such that}\\ a + (-a) = (-a) + a = 0; (-a) = (m\mathord{-}a) \text{ in } \mathbb{Z}_m
- Associativity for multiplication: a\cdot(b\cdot c) = (a\cdot b)\cdot c \space\space \forall a, b, c \in \mathbb{Z}_m
- Multiplicative Identity: \exists 1 \not = 0 \in \mathbb{Z}_m\space \text{such that}\\ 1 \cdot a = a \cdot 1 = a \space\space \forall a \in \mathbb{Z}_m. \\ \text{Element 1 is called the unity element.}
Prime Field
A field is a commutative ring with unity with every non-zero elements have a unique multiplicative inverse. i.e., \forall a \not = 0 \in \mathbb{Z}_m, \exists a^{-1} \in \mathbb{Z}_m \text{ such that } a \cdot a^{-1} = 1 \in \mathbb{Z}_m. As we have seen in Extended Euclidean Algorithm, multiplicative inverse modulo m exists if and only if gcd(a, m) = 1. When the modulus value m is composite, not all elements of \mathbb{Z}_m satisfies gcd = 1. Hence \mathbb{Z}_m is not a field when m is composite. When m \ge 2 is a prime, gcd(a, m) = 1\space \forall a \in \mathbb{Z}_m and hence there exists a unique inverse element for each a \in \mathbb{Z}_m. This implies that \mathbb{Z}_m is a field when m is a prime. We usually use the letter p to denote a prime and the prime field is denoted as \mathbb{Z}/p\mathbb{Z} or \mathbb{Z}_p or \mathbb{F}_p.
Prime Number Generation
Theorem 1.1 (Fermat’s Little Theorem) Let p be any positive integer. If p is a prime, then
a^{p-1} \equiv 1\hspace{-0.15cm}\pmod p for any integer a \not\equiv 0\hspace{-0.15cm}\pmod p. Note that when p is a prime, gcd(a,p) = 1.
Question.Suppose for any integer a \not\equiv 0 \hspace{-0.15cm}\pmod p, gcd(a, p) = 1 and a^{p-1} \equiv 1 \hspace{-0.15cm}\pmod p. Is p a prime?
Not always. As an example, n = 2821 which has a prime factorisation of 7 × 13 × 31. Let a = 2, gcd(2, 2821) = 1 and 2^{2820} = 1 \hspace{-0.15cm}\pmod 2821.
If p is a composite number and for some a \not\equiv 0 \hspace{-0.15cm}\pmod p, if a^{p-1} \equiv 1 \hspace{-0.15cm}\pmod p, we call p a Fermat pseudoprime to the base a. Those numbers which fails Fermat’s primality test for all a \not\equiv 0 \hspace{-0.15cm}\pmod p, are knows as Carmichael Numbers
Miller-Rabin Test
Miller-Rabin test is a probabilistic primality test, which tries to find the square roots of 1\hspace{-0.15cm}\pmod n to determine the primality of an integer. When n is a prime there exists at most 2 distinct square roots modulo n. (Square roots modulo a composite number is a computational problem like integer factorisation). This means that if n is a prime, 1\hspace{-0.15cm}\pmod n has exactly two square roots and they are \pm 1\hspace{-0.15cm}\pmod n.
Suppose we want to check if n is prime or not. We will follow the below setps:
- Write n - 1 = 2^s.m, where m is odd.
- Choose a random a in the range [2, n-1]
- Check if a^m \equiv \pm1 \mod n, declare n as probably prime and stop. (We call n a Miller-Rabin Witness)
- If a^m \not\equiv \pm1 \hspace{-0.15cm}\pmod n, we will calculate a^{2^m}\hspace{-0.15cm}\pmod n, a^{2^{2}m}\hspace{-0.15cm}\pmod n, a^{2^{3}m}\hspace{-0.15cm}\pmod n, …, a^{2^{s-1}m}\hspace{-0.15cm}\pmod n. If any of a^{2^{i}m} \equiv 1 \hspace{-0.15cm}\pmod n, then a^{2^{i-1}m}\hspace{-0.15cm}\pmod n is a square root of a^{2^{i}m} and hence we declare n as composite and stop. Here a is called a Miller-Rabin Witness for n
- If any of the a^{2^{i}m} \equiv -1 \hspace{-0.15cm}\pmod n, then a^{2^{i-1}m}\hspace{-0.15cm}\pmod n is not a square root of a^{2^{i}m} and hence we declare n as probably prime and stop.
- If any of the above steps have declared n as probably prime, then we go to step 1, pick a different base a and repeat the steps to ensure that n is in fact a prime.
The choices of a for which a composite n is declared as probably prime are called Miller-Rabin Liars and a is called as Strong Pseudoprime. The probability of success that the Miller-Rabin test correctly identifying a composite number is more than 75%. It can be improved again by adding more trials to the test.
Question. How do we use Miller-Rabin test to generate a large N-bit prime number?
In order to generate an N-bit prime number, we need to carry out a prime number search in the range [2^{N-1}, 2^N]. The steps are as follows:
- Let randp is a random integer in the range [2^{N-1}, 2^N]. We can verify if randp is N-bit or not by checking \log_2(randp)
- Use Miller-Rabin test to check if randp is a prime or not. If randp is a prime, we stop.
- If randp is composite, we will try to search for the next smallest prime larger than randp.
- Let B = log_{10}(randp)
- Let U = randp + B \cdot B
- Foreach p \in [randp + 1, U]
- Check if p is prime using Miller-Rabin test. If p is prime, we stop.
Let p be the N-bit prime number we generated using the above steps. We will now focus on elliptic curves and how do we generate an elliptic curve \pmod p
Elliptic Curves
Definition 1.2 (Elliptic Curve) An elliptic curve over a prime field \mathbb{F}_p is a cubic curve with coordinates in \mathbb{F}_p. The general form of the curve equation is:
\begin{aligned} E:\space y^2 = x^3 + Ax + B;\space \text{where } A, B \in \mathbb{F}_p \end{aligned}
Elliptic curves of this form are called Short Weierstrass equation.
The value \Delta = 4A^3 + 27B^2 is called the “discriminant” of the curve. The curve is called singular if \Delta = 0 and it is called non-singular if \Delta \ne 0. Elliptic Curves under our consideration have a non-zero discriminant. The discrete logarithm problem is easy solve when \Delta = 0.
The points on an elliptic curve3 together with a special point known as “point at infinity” forms a abelian group under addition. Let \mathcal{O} represents the point at infinity. We can represent the curve E as a set of points as below:
\begin{aligned} E = \{ (x, y) : y^2 = x^3 + Ax + B \hspace{-0.30cm}\pmod p \} \cup \{\mathcal{O}\} \end{aligned}
The group laws under addition are below:
P + \mathcal{O} = P \space \forall \space P \in E
P + (-P) = \mathcal{O} \space \forall \space P \in E, \text{Also } -(x,y) = (x,-y)
P + (Q + R) = (P + Q) + R \space \forall \space P, Q, R \in E
P + Q = Q + P \space \forall \space P, Q \in E
Arithmetic of Curve Points in \bold{\mathbb{F}_p}
Before we dive into deriving formulas for addition, subtraction and scaling of points, we will look into it geometrically.
Adding two points
Let P_1 and P_2 be two points on curve E. We get P_3 = P_1 + P_2 by following the below steps:
- Draw a straight line connecting P_1 and P_2 until it intersects a third point (-P_3) on the curve. Refer Figure 1 below.
- The point of reflection of (-P_3) across the x-axis is the sum P_3 = P_1 + P_2.
Doubling of a point
Let P a point on the curve E. We get P + P = 2P by following the below steps:
- Draw a tangent line to the point P until it intersects a second point (-2P) on the curve. Refer Figure 2 below.
- The point of reflection of (-2P) across the x-axis is the sum 2P = P + P.
Formulas for addition and doubling in \bold{\mathbb{F}_p}
Let P_1 = (x_1, y_1) and P_2 = (x_2, y_2) be two points on the curve
E: y^2 = x^3 + Ax + B \hspace{-0.10cm}\pmod p
Let y = mx + b be the secant line connecting P_1 and P_2. Let’s derive a formula for obtaining a third point P_3 = (x_3, y_3) such that P_3 = P_1 + P_2
Slope of the line is given by:
\begin{aligned} m &= \frac{(y_2 \space\mathord{-} \space y_1)}{(x_2 \space\mathord{-} \space x_1)} \hspace{-0.30cm}\pmod p\\ &= (y_2 \space\mathord{-} \space y_1) \cdot (x_2 \space\mathord{-} \space x_1)^{-1} \hspace{-0.30cm}\pmod p\\ \end{aligned}
This implies that when P_1 \ne P_2, if x_1 = x_2, slope is not defined
When P_1 = P_2, we use the tangent line method to find the third point P_3. We find the slope of the tangent line by differentiating the curve with respect to x:
\begin{aligned} &y^2 = x^3 + Ax + B\\ &2y\frac{dy}{dx} = 3x^2 + A\\ &\implies m = \frac{dy}{dx} = (3x^2 + A)/2y \\ &\implies m = (3x^2 + A) \cdot (2y)^{-1} \hspace{-0.30cm}\pmod p \\ &\text{Substituting the values for $x$ and $y$:} \\ &m = (3x_1^2 + A)(2y_1)^{-1} \hspace{-0.30cm}\pmod p \end{aligned}
This implies that when P_1 = P_2, if y_1 = 0, slope is not defined.
We can find the third point of intersection between the line y = mx + b and the curve y^2 = x^3 + Ax + B \hspace{-0.10cm}\pmod p by solving (mx + b)^2 = x^3 + Ax + B. Let
(-P_3) = (x_3, y_3) be the intersection point.
\begin{aligned} &(mx + b)^2 = x^3 + Ax + B \\ &\implies x^3 + Ax + B \space\mathord{-}\space (mx + b)^2 = 0 \\ \end{aligned}
Now we got an polynomial cubic equation in one variable. Fundamental theorem of algebra states that a polynomial of degree n has n roots. Hence we have three roots and we already know the first two roots: x_1 and x_2.
\begin{aligned} \therefore x^3 + Ax + B \space\mathord{-}\space (mx + b)^2 &= (x \space\mathord{-}\space x_1)(x \space\mathord{-}\space x_2)(x \space\mathord{-}\space x_3) \\ \implies x^3 \space\mathord{-}\space m^2x^2 + (A \space\mathord{-}\space 2mb)x &+ (B \space\mathord{-}\space b^2)\\ = x^3 \space\mathord{-}\space (x_1 + x_2 + x_ 3)x^2 &+ (x_1x_2 + x_1x_3 + x_2x_3)x \space\mathord{-}\space x_1x_2x_3 \\ \end{aligned}
Equating the coefficients of x^2, we get:
\begin{aligned} -m^2 &= -(x_1 + x_2 + x_3)\\ \implies x_3 &= m^2 \space\mathord{-}\space x_1 \space\mathord{-}\space x_2\\ \therefore y_3 &= mx_3 + b \\ \text{but,} b = y_1 \space\mathord{-}\space mx_1\\ \implies y_3 &= mx_3 + y_1 \space\mathord{-}\space mx_1\\ \implies y_3 &= m(x_3 \space\mathord{-}\space x_1) + y_1 \end{aligned}
Hence our point of third point obtained by intersecting the curve by the line is: (-P_3) = (x_3, y_3) where x_3 = m^2 \space\mathord{-}\space x_1 \space\mathord{-}\space x_2 and \space y_3 = m(x_3 \space\mathord{-}\space x_1) + y_1. We get P_3 = P_1 + P_2 by reflecting the point (-P_3) across the x-axis and \therefore P_3 = -(-P_3) = (x_3, -y_3) = (m^2 \space\mathord{-}\space x_1 \space\mathord{-}\space x_2,\space m(x_1 \space\mathord{-}\space x_3) \space\mathord{-}\space y_1)
\boxed{ \begin{aligned} \text{If}\space P_1 = P_2\space & \text{and}\space y_1 \ne 0, \\ m &= (3x_1^2 + A)(2y_1)^{-1} \hspace{-0.30cm}\pmod p \\ \text{If}\space P_1 \ne P_2\space & \text{and}\space x_1 \ne x_2, \\ m &= (y_2 \space\mathord{-}\space y_1) \cdot (x_2 \space\mathord{-}\space x_1)^{-1} \hspace{-0.30cm}\pmod p\\ x_3 &= m^2 \space\mathord{-}\space x_1 \space\mathord{-}\space x_2 \hspace{-0.30cm}\pmod p\\ y_3 &= m(x_1 \space\mathord{-}\space x_3) \space\mathord{-}\space y_1 \hspace{-0.30cm}\pmod p \end{aligned}}
Hence the third point obtained by intersecting the curve by the line is: (-P_3) = (x_3, y_3) where x_3 = m^2 \space\mathord{-}\space x_1 \space\mathord{-}\space x_2 and y_3 = m(x_3 \space\mathord{-}\space x_1) + y_1. We get P_3 = P_1 + P_2 by reflecting the point (-P_3) across the x-axis and we get P_3 = -(-P_3) = (x_3, -y_3) = (m^2 \space\mathord{-}\space x_1 \space\mathord{-}\space x_2,\space m(x_1 \space\mathord{-}\space x_3) \space\mathord{-}\space y_1)
Quadratic Residue Modulo Prime
Definition 1.3 (Quadratic Residue) Let p be an odd prime and \mathbb{F}_p be the prime field defined by p. Let a \in \mathbb{F}_p \implies gcd(a, p) = 1. We say that a \in \mathbb{F}_p is a quadratic residue of p if there exists x \in \mathbb{F}_p such that the congruence x^2 \equiv a \pmod p is true. Otherwise we say that a is a quadratic non-residue of p.
Example 1.2 Let p = 13.
\begin{aligned} \text{We have }& x^2 \equiv a \hspace{-0.30cm}\pmod {13} \text{ and } a \in \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}\\ \\ 1^2 \equiv &1 \hspace{-0.30cm}\pmod {13}; \space 12^2 \equiv 1 \hspace{-0.30cm}\pmod {13}\\ 2^2 \equiv &4 \hspace{-0.30cm}\pmod {13}; \space 11^2 \equiv 4 \hspace{-0.30cm}\pmod {13}\\ 3^2 \equiv &9 \hspace{-0.30cm}\pmod {13}; \space 10^2 \equiv 9 \hspace{-0.30cm}\pmod {13}\\ 4^2 \equiv &3 \hspace{-0.30cm}\pmod {13}; \space 9^2 \equiv 3 \hspace{-0.30cm}\pmod {13}\\ 5^2 \equiv &12 \hspace{-0.30cm}\pmod {13}; \space 8^2 \equiv 12 \hspace{-0.30cm}\pmod {13}\\ 6^2 \equiv &10 \hspace{-0.30cm}\pmod {13}; \space 7^2 \equiv 10 \hspace{-0.30cm}\pmod {13} \\ &\\ \therefore \text{quadratic }& \text{residues } \hspace{-0.30cm}\pmod {13} = \{1, 3, 4, 9, 10, 12\}\\ \text{quadratic }& \text{non-residues } \hspace{-0.30cm}\pmod {13} = \{2, 5, 6, 7, 8, 11\} \end{aligned}
Euler’s Criteria to check a is a quadratic residue \hspace{-0.30cm}\pmod p
\boxed{
\begin{aligned}
\text{Let}\space p&\space \text{is an odd prime and}\space gcd(a, p) = 1, \\
&\text{then}\space a \space \text{is a quadratic residue}\space \hspace{-0.30cm}\pmod p \space \text{iff}\space a^\frac{p \space\mathord{-}\space 1}{2} \equiv 1 \hspace{-0.30cm}\pmod p\\
a \space \text{is a}& \space \text{quadratic non-residue}\space \hspace{-0.30cm}\pmod p \space \text{if}\space a^\frac{p \space\mathord{-}\space 1}{2} \equiv -1 \hspace{-0.30cm}\pmod p
\end{aligned}}
Elliptic curves over \mathbb{F}_p are quadratic congruences. This means that if (x,\space y) \in E(\mathbb{F}_q) then y is a square-root of x^3 + Ax + B \hspace{-0.10cm}\pmod p.
Tonelli-Shanks Algorithm
Tonelli-shanks algorithm4 computes the square root of an integer modulo prime. It cannot compute the square root when modulus is a composite number. Calculating the square root modulo a composite number is a computational problem like integer factorisation. Steps below illustrates the Tonelli-Shanks procedure.
Algorithm: Tonelli-Shanks
Input: a \hspace{-0.10cm}\pmod p
Output: \sqrt{a} \equiv v \hspace{-0.10cm}\pmod p
If a^\frac{p \space\mathord{-}\space 1}{2} \not\equiv 1 \hspace{-0.10cm}\pmod p then
Return(a is a quadratic non-residue)
End If
If p \equiv 3 \hspace{-0.10cm}\pmod 4 then
\sqrt{a} \equiv a^\frac{p + 1}{4} \hspace{-0.10cm}\pmod p
End If
If p \equiv 1 \hspace{-0.10cm}\pmod 4 then
Let \space p \space\mathord{-}\space 1 \leftarrow 2^s \cdot m, where m is odd.
Let c \leftarrow a quadratic non-residue in the range [2,\space p \space\mathord{-}\space 1]
Let u \leftarrow a^m \hspace{-0.10cm}\pmod p
Let v \leftarrow a^\frac{m + 1}{2} \hspace{-0.10cm}\pmod p
While u \not = 1 \hspace{-0.10cm}\pmod p
Let k \leftarrow 0
Let l \leftarrow 0
While c^{2^k} \not\equiv p \space\mathord{-}\space 1
k \leftarrow k + 1
End While
While u^{2^l} \not\equiv p \space\mathord{-}\space 1
l \leftarrow l + 1
End While
Let r \leftarrow l + 1
Update u \leftarrow u \cdot c^{2^{s \space\mathord{-}\space r}} \hspace{-0.10cm}\pmod p
Update v \leftarrow v \cdot c^{2^{s \space\mathord{-}\space r \space\mathord{-}\space 1}} \hspace{-0.10cm}\pmod p
End While
Return(v)
End If
In the preceding sections, we saw how to add two points on a curve and double a point. Doubling a point can be rephrased as multiplying it by two. i.e, P + P = 2P. How do we find 3P,\space 4P, \space 5P,\cdot\cdot\cdot\space. The below table illustrates the manual process:
\boxed{ \begin{aligned} 2P &= P + P\\ 3P &= P + P + P = (P + P) + P = 2P + P\\ 4P &= P + P + P + P = (p + P) + (P + P) = 2P + 2P = 3P + P\\ 5P &= 4P + P\\ &\cdot\\ &\cdot\\ &\cdot\\ nP &= (n - 1)P + P \end{aligned}}
It’s not practical to do this process when n is very large. The below algorithm performs fast integer multiplication of a point on an elliptic curve. We will first convert n into (base 2) format. Then we iterate over the bits from the LSB performing an addition only if the bit is 1 and doubling at every step.
Algorithm: Fast Integer Multiplication of
P(x, \space y) \in\space E: y^2 = x^3 + Ax + B\hspace{-0.10cm}\pmod p
Input: n \in \mathbb{Z}\in , \space P(x, \space y) \in E(\mathbb{F}_p).
Output: Q = n\cdot P \in E(\mathbb{F}_p)
Initialise Q \leftarrow \mathcal{O} /*point at infinity*/
While n \gt 0\space Do
/*Logical AND operation of integer n with integer 1 */
/*will extract the LSB of n*/
If n \land 1 = 1\space Then
Q \leftarrow Q + P
End If
P \leftarrow P + P\space
n \leftarrow n \div 2
End While
Elliptic Curve Discrete Logarithm Problem (ECDLP)
Definition 1.4 (ECDLP) Let E: y^2 = x^3 + Ax + B be an elliptic curve defined over the prime field \mathbb{F}_p. Let P and Q be two points on the curve E(\mathbb{F}_p). ECDLP is defined as finding a scalar value n \in \mathbb{F}_p such that Q = nP
ECDLP is a tough problem and the fastest algorithm to solve it is the Pollard’s \rho Method. The time complexity of this algorithm is O(\sqrt{p}).
Diffie-Hellman Key Exchange algorithm and ElGamal Encryption scheme are based on the computational complexity in solving ECDLP.
Elliptic Curve Generation
The first step in generating a curve2 is the computation of coefficient values A,\space B and the discriminant, \Delta = 4A^3 + 27B^2 calculation. All these parameters will be \pmod p. The below steps are used to calculate the curve parameters.
- Let A \leftarrow a random number in the range [0, p \space\mathord{-}\space 1]
- Let B \leftarrow a random number in the range [0, p \space\mathord{-}\space 1]
- Compute discriminant \Delta \leftarrow 4A^3 + 27B^2 \hspace{-0.10cm}\pmod p
- If \Delta = 0, go to Step 1 and repeat (we need non-singular curves), else stop.
The next step in setting up the public key cryptosystem is to find a point G on the curve called the generator point(or the initial point).
- Let x \leftarrow a random integer the range [0,\space p \space\mathord{-}\space 1]
- Let z \leftarrow x^3 + Ax + B \hspace{-0.10cm}\pmod p
- If z is a quadratic residue \hspace{-0.10cm}\pmod p, then compute y = \sqrt{z} using Tonelli-Shanks. (x, \space y) \in E(\mathbb{F}_p)\space is the generator point, G.
- If z is a quadratic non-residue \hspace{-0.10cm}\pmod p, then go to Step 1 and repeat.
Calculation Of Private and Public Keys
Private Keys randomly chosen integers in the range \sqrt{p} \lt key \lt p\space \mathord{-} \space \sqrt{p}. As we have seen earlier, Pollard’s Rho Algorithm solves ECDLP in \sqrt{p}steps for a prime field of size p. This means a 256-bits curve provides a 128-bits security6 if we choose a key size of 256-bits. It implies that our bound provides a security of 64-bits to 128-bits
Public Keys are points on the curve. We use the generator point G and the private key to calculate the public key. Hence, if k \hspace{-0.10cm}\pmod p is the private key, our public key is k\cdot G \in E(\mathbb{F}_p).
ElGamal Public Key Encryption
At the beginning of this article, we saw a non-mathematical description of the ElGamal Encryption Scheme. We then covered the mathematical preliminaries needed to understand the system in depth. Still, one might wonder how we encrypt and decrypt our regular communication messages using numbers because all we have learned so far deals with numbers. Since we are using elliptic curves, the trick is to encode our plaintext messages into points on the curve before encrypting. Neal Koblitz developed a probabilistic encoding algorithm to convert a plaintext message into a point on an elliptic curve. His thinking was that if we have an odd prime p, nearly half of the numbers less than p are quadratic-residue \hspace{-0.10cm}\pmod p. This means that we have a 50% chance to represent a message M as the x-coordinate of a point on the curve. Koblitz’s Algorithm for encoding plaintext messages into elliptic curve points is given below:
Algorithm: Koblitz’s Plaintext Encoding Method on
E: y^2 = x^3 + Ax + B\hspace{-0.10cm}\pmod p
Input: A Big-Ending byte stream of the plaintext message.
Output: (x, \space y) \in E(\mathbb{F}_p)
Let K \leftarrow 1000 be the error tolerance parameter
Let L \leftarrow 0 be the lower bound for the message value
Let U \leftarrow \frac{p}{1000} - 1 message upper bound value
Let M \leftarrow be the integer \hspace{-0.10cm}\pmod p constructed from the input byte stream
If not (M \gt L) \space \land \space (M \lt U) then
Message size is not in the range. Error!
End If
ForEach i \in [0,\space 1000]
Calculate x \leftarrow K \cdot M + i \hspace{-0.10cm}\pmod p
Calculate r \leftarrow x^3 + Ax + B \hspace{-0.10cm}\pmod p
If r is a quadratic residue \hspace{-0.10cm}\pmod p then
Calculate y \leftarrow r^\frac{1}{2} \hspace{-0.10cm}\pmod p
End If
End ForEach
In order to decode a message from an elliptic curve point, divide the x-coordinate by the K value above and convert the resulting number to byte stream and then to the plaintext. We are now ready to implement the ElGamal Encryption Scheme mathematically. The ElGamal Scheme works as follows:
- Initial setup. These information are publicly available:
- Let p be a n-bit prime number.
For SEC2, \lceil{log_{2}(p)}\rceil \in \{192, 224, 256, 384, 521\} - Let E: y^2 = x^3 + Ax + B \hspace{-0.10cm}\pmod p be and elliptic curve.
- Let G be a point on E with high order.
- Configuration at Alice’s side:
- Alice chooses a her Secret Key n_A \space\text{such that}\space \sqrt{p} \lt n_A \lt p \space\mathord{-} \space \sqrt{p}.
- Alice calculates her Public Key A \equiv n_A \cdot G \hspace{-0.10cm}\pmod p and publishes it.
- Configuration at Bob’s side:
- Bob chooses a his Secret Key n_B.\space \sqrt{p} \lt n_B \lt p \space\mathord{-} \space \sqrt{p}.
- Bob calculates his Public Key B \equiv n_B \cdot G \hspace{-0.10cm}\pmod p and publishes it.
- Suppose Alice wants to send the message M = “Hello World!” to Bob.
- Alice encodes M to a point P on the curve. She uses Koblitz Algorithm for this encoding.
- Alice downloads Bob’s Public Key B \equiv n_B \cdot G \hspace{-0.10cm}\pmod p
- Alice calculates ciphertext C as:
C \equiv P + n_A \cdot B \hspace{-0.10cm}\pmod p \equiv P + n_A(n_B \cdot G) \hspace{-0.10cm}\pmod p. - Bob once receives Alice’s message, downloads Alice’s Public Key A.
- Bob decrypts C as:
P \equiv C \space\mathord{-} \space n_B \cdot A \hspace{-0.10cm}\pmod p \equiv C \space\mathord{-} \space n_B(n_A \cdot G) \hspace{-0.10cm}\pmod p. - Bob decodes the message M from P by reversing Koblitz method.
An implementation of the ElGamal Encryption Scheme in Rust is available in my GitHub repository.
Bibliography
- Alexander Stanoyevitch. Introduction to Cryptography with Mathematical Foundations and Computer Implementations. Chapman & Hall/CRC, 2010.↩
@book{stanoyevitch2010introduction, title={Introduction to Cryptography with Mathematical Foundations and Computer Implementations}, author={Stanoyevitch, Alexander}, publisher={Chapman \& Hall/CRC}, year={2010}, edition={1st}, isbn={1439817634} } - Nur Azman Abu Nur Azman. The Simulation of 256-bit Elliptic Curve Cryptosystem. , 2000.↩
@inproceedings{nur azman2000simulation, title={The Simulation of 256-bit Elliptic Curve Cryptosystem}, author={Nur Azman, Nur Azman Abu, Ida Zuraida Zahari, Zakaria}, booktitle={}, year={2000} } - J.H. Silverman. The Arithmetic of Elliptic Curves. Springer New York, 2009.↩
@book{silverman2009arithmetic, title={The Arithmetic of Elliptic Curves}, author={Silverman, J.H.}, publisher={Springer New York}, year={2009}, series={Graduate Texts in Mathematics}, edition={2nd}, isbn={9780387094939} } - Robin Chapman. Square roots modulo a prime. 2003.↩
@unpublished{robin chapman2003square, title={Square roots modulo a prime}, author={Robin Chapman}, year={2003} } - Certicom Research. SEC 2: Recommended Elliptic Curve Domain Parameters. 2010.↩
@unpublished{certicom research2010sec, title={SEC 2: Recommended Elliptic Curve Domain Parameters}, author={Certicom Research}, year={2010} } - Svetlin Nakov. Practical Cryptography For Developers. open-source, 2018.↩
@book{svetlin nakov2018practical, title={Practical Cryptography For Developers}, author={Svetlin Nakov}, publisher={open-source}, year={2018}, isbn={9786190008705} }
Copyright © 2024 Ajeesh T. Vijayan
You must be logged in to post a comment.