Elliptic Curve Cryptography (ECC) and ECDSA

Elliptic Curve Cryptography (ECC)

Elliptic curve (EC) was first introduced by Neal Kobiltz and Victor Miller in 1985. Elliptic curve is a non-singular curve that is operated on a finite field Zq (where q is the order of elliptic curve). EC consists of set of points that satisfies the following equation as follows. 

                                                    Y2 = X3 + aX + b

Where {X,Y,a,b} ∈ Zq, and 4a3 + 27b2 ≠ 0.


Next, we discuss the encryption and decryption mechanism between two parties (Say α and γ ).


Remark 1: Elements selected from party α is represented by capital letters whereas elements selected from party γ is represented by small letters.


i) Key Generation:

1. Secret key: Each party α and γ selects secret keys S ∈ Zq and s ∈ Zq.

2. Public key: P = Sδ and p = sδ (where δ is base point generator of elliptic curve).

3. Secret nonce (where nonce is random value): N = SP, and n = sp.


Remark 2: Most common setting is N=n.


ii) Encryption (by party α) :

Let M ∈ Zq be a message. First, α encodes M on elliptic curve, that is, M'. Party γ receives ciphertext as follows.

                                                    CT = {Nδ, M'+Np}


iii) Decryption (by party γ):

On receiving CT, party γ decrypts the message M'. For decryption, party γ first multiplies the x-coordinate of CT with secret key of party γ, that is, Nδs. Then, it subtracts this from y-coordinate of CT as follows.

                                                        ={M' + Np - Nδs}

                                                        ={M'}

(where p=δs).

Finally, party γ will convert the encoded message M' into M.


Elliptic Curve Digital Signature Algorithm (ECDSA)

The digital signature over message with the help of EC is termed as ECDSA. Mathematically ECDSA can be represented as follows.

                                                    σ=N-1(h(M) + SQ)

(where σ is ECDSA signature, h(M) is hash of message M, S is secret key, and Q is public nonce (such that the x-coordinate of Nδ)).

Here, we note the two important notion as follows.
1. P = Sδ mod q
2. Q = Nδ mod q

Figure 1 demonstrates the functionality of ECDSA signature generation algorithm.

Figure 1. ECDSA signature generation over message passing. 

Miscellaneous Key Points

1. Elliptic curve cryptography provides high level of security with smaller key size as compared to RSA algorithm. That's why it is widely used in large scale industry.
2. ECDSA is widely used in cryptocurrency and blockchain. 
2. Finite field: A finite field is a field having finite number of elements. 
3. ECC is secure because the construction of EC is based on elliptic curve discrete logarithmic problem (ECDLP), that is, cryptographically hard. 
                        P = Sδ mod q
Given the value of S and δ, computation of P is easy. Given the knowledge of P and δ, computation of S is hard due to the inadequate knowledge of q.


We thanks to...

1. Neal Kobiltz. Elliptic Curve Cryptosystem. Mathematics of computation, 48(177):203–209, 1985.
2. Don Johnson, Alfred Menezes, and Scott Vanstone. "The Elliptic Curve Digital Signature Algorithm (ECDSA). International journal of information security 1 (2001): 36-63.


Comments

Post a Comment

Popular posts from this blog

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more

NP-Hardness vs Cryptographic Hardness

To understand the gap between these two terms, we divide this blog into two parts. In first part, we discuss complexity theory, and in second part, we explore cryptographical perspective.  Complexity Theory:  For a better understanding of complexity theory, we refer readers to [1] Language L : A language L is a set of strings defined over an alphabet set Σ. Class P  (polynomial time) : A language L is in P if L is decidable in polynomial time by a deterministic Turing machine. Example: Language = Reachability. Input: Graph G(V,E), and s,t ∊ V(G). Question: Does their exist a path from s to t ?  The above Language is an example of Class P  (hint: can be easily solved by BFS/DFS algorithm).  Class NP (non deterministic polynomial time) : A language L  ∊  NP  if the certificate for L can be verified by a non-deterministic Turing machine in polynomial time.   A certificate for a language L is an instance of the solution ...
Read more