Elliptic Curve Cryptography
Introduction
With the fast growth of information technology, networks have become a significant part of everyone’s lives. In the network confidentiality and authenticity of information must be secured against unauthorized access, interruption and modification. Encryption and Decryption, Digital Signature are some of the effective techniques that is used to secure the information of the user and confirm his/her authenticity. Yet, the overheads related with communication and its security must be minimal.
In 1985, Neil Koblitz and Victor Miller independently proposed the Elliptic Curve Cryptosystem (ECC). It is a kind of public key cryptosystem which is based on the Elliptic Curve Discrete Logarithm Problem (ECDLP) for its security. ECC is being accepted as an alternative to other cryptosystems like RSA and ElGamal as ECC provides much more security with its highest strength-per-bit of any other cryptosystem known today and the creation faster, smaller, and more efficient cryptographic keys. ECC point of multiplication operation has quicker evolving capacity and is found to be computationally more efficient than RSA exponentiation. The length of cryptographic keys in ECC is reasonably much smaller than other public key cryptographic systems. (E.g. The 1024-bit security strength of a RSA could be obtainable by 163-bit security strength of ECC). As ECC helps to establish equivalent security with lower computing power and battery resource usage, it is widely used for mobile applications.
Mathematics in Elliptic Curve Cryptography
ECC generates keys through the properties of the elliptic curve equation rather than the traditional method of generation as the product of very large prime numbers. An elliptic curve is not an ellipse (oval shape), but is denoted as a looping line interconnecting two axes (lines on a graph used to represent the position of a point). ECC is based on properties of a particular type of equation formed from the mathematical group (a set of values for which operations can be performed on any two members of the group to produce a third member) derivative from points where the line intersects the axes. Multiplying a point on the curve by a number will produce another point on the curve, but it is very hard to find what number was used, even if you know the original point and the result. Equations based on elliptic curves have a characteristic that is very valuable for cryptography purposes: they are fairly easy to perform, and enormously hard to reverse.
In Elliptic Curve Cryptography we will be using the curve equation of the form;
y2 = x3 + ax + b
which is known as Weierstrass equation, where a and b are the constant with
4a3 + 27b2 = 0
Examples:
Cryptographic operation on elliptic curve over finite field are done using the coordinate points of the elliptic curve.
Elliptic curve over finite field equation is given by:
y2 = {x3 + ax + b} mod {p}
Certain formula is defined for operation with the points
Key Addition
The two-point P (x1, y1) and Q (x2, y2) are distinct. P + Q = R (x3, y3) is given by the following calculation.
The following figure shows graphical representation of Point Addition operation.
x3 = {λ2 − x1 − x2} mod p
y3 = {λ (x1 − x3) − y1} mod p
where
λ = {(y2 − y1) / (x2 − x1)} mod p
Key Doubling
The two-point P (x1, y1) and Q (x1, y1) overlap. P + Q = R (x3, y3) is given by the following calculation.
The following figure shows graphical representation of Point Doubling operation.
x3 = {λ2 − 2x1} mod p
y3 = {λ (x1 − x3) − y1} mod p
where
λ = {(3x12+ a) / 2y1} mod p
Key Multiplication
Let P be any point on the elliptic curve. Multiplication operation over P is defined by the repeated addition.
k P = P + P + P +···+ k times.
Point at Infinity
If x1 = x2 and y1 = y2 = 0 or x1 = x2 and y1 = −y2, the points are said to intersect at infinity denoted by O.
The following figure shows graphical representation of Point at Infinity.
Key Generation
Key generation is the most significant part where we have to generate both public key and private key. Consider Alice and Bob are the two communicating parties and Alice wants to send a message to Bob. Alice will be encrypting the message with Bob’s public key and the Bob will decrypt the message with Bob’s private key.
Now, Bob has to select a number ‘d’ within the range of ‘n’.
Using the following equation, Bob can generate the public key.
Q = d * P
d = the random number that Bob has selected within the range of (1 to n-1).
P is the point on the curve.
‘Q’ is the public key and ‘d’ is the private key.
Encryption
Let ‘m’ be the message that Alice is sending. We have to represent this message on the curve.
Consider ‘m’ has the point ‘M’ on the curve ‘E’.
Randomly select ‘k’ from [1 - (n-1)].
Two cipher texts will be generated let it be C1 and C2.
C1 = k*P
C2 = M + k*Q
C1 and C2 will be sending
Decryption
Bob has to get back the message ‘m’ that was send to Bob,
M = C2 – d * C1
M is the original message that Alice has send.
Proof
How do Bob get back the message?
M = C2 – d * C1
‘M’ can be represented as ‘C2 – d * C1′
C2 – d * C1 = (M + k * Q) – d * (k * P) (C2 = M + k * Q and C1 = k * P)
= M + k * d * P – d * k *P (canceling out k * d * P)
= M (Original Message)
Comments
Post a Comment