Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Trap-Door functions
3.
Elliptic Curve
3.1.
Properties of Elliptic Curve
3.2.
Elliptic curve modulo prime
3.3.
Encryption and Decryption using Elliptic Curve
3.4.
Advantages
4.
Frequently Asked Questions
4.1.
What is a trap door function?
4.2.
How many points can be intersected on an elliptic curve?
4.3.
Which one uses the large key size for encryption, elliptic curve or RSA?
4.4.
What type of cryptography is applied in the elliptic curve?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Not just in mathematics but here as well Elliptic Curves

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Modern-day cryptographic solutions are based on public key cryptography, where the encryption key is public, and the decryption key is secret. Various organizations apply this method of modern cryptography to secure their communication channels or information.

These modern cryptography solutions are generally based on mathematical theories and expressions, so attackers cannot easily break them. Multiple examples of modern cryptography are available, like RSA, DES AES, and many more. These techniques are well-researched and widely used to provide system security.
 

Elliptic Curves

This blog will discuss a mathematical concept commonly used in modern cryptography: Elliptic Curves. But first, we need to understand why these mathematical concepts are used in cryptography.

Trap-Door functions

There is a trap door mechanism that is easy to enter from a trap door but difficult to get out. The trap-door function is based on this mechanism. In a trap function, it is easy to implement in one direction, but it is challenging to inverse the implementation.

Even with considerable computational resources, it should be challenging to break a trap-down function.

With the help of the elliptic curve, we can achieve this trap door function mechanism.

Let's get into the elliptic curve.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Elliptic Curve

In mathematics, the elliptic curve is a vast topic with many factors, so we will not be diving deep into the elliptic curve in general; instead, we will go through its properties and how we can use these properties to implement cryptography.

In simple terms, any curve satisfying the following equation is called an elliptic curve.

 elliptic curve expression

Here, a and b are any constant points on the 2-d graph. A non-singular elliptic curve is the set E of solutions (x, y) ∈ R × R to the equation. Here R = real numbers.

Example

Elliptic Curve

The above image is an elliptic curve on the 2-d graph having an x and y-axis. This elliptic curve is created with values a = -1.9 and b=2.

Properties of Elliptic Curve

You can observe the symmetry of the curve in the fig1. This elliptical curve symmetry plays an important role in the elliptical curve used in cryptography.
 

  • In an elliptical curve, any vertical line can intersect the curve at most three points. In fig1 P and Q are the points of intersection.
     
  • Another property of an elliptic curve is that any point on the elliptical curve can be reflected on the X-axis and remain on the same curve. In fig1, the point below Q labeled P+Q is the reflected point.
     

We will use the reflected property to demonstrate why an elliptic curve can be used to implement a trap door function.

In the elliptic curve, the reflected property can go on infinitely unless you set the maximum finite field on the elliptic curve. So how can we use this property? You can set a prime number r on the elliptic curve, which will work as the maximum number to generate the points on the elliptic curve.
 

We can take a message m and generate this message as a point on the elliptical curve and convert it into plaintext. Then we can use a private number generated on the elliptical curve with plaintext can convert it into ciphertext.

Elliptic curve modulo prime

Let's see an example of an. With modulo prime p where p > 3, the elliptical curve can be defined as

elliptic curve with modulo prime

We can do the addition operation on the elliptic curve with the following formulas.

Assume P =(x1,y1) and Q(x2,y2) are points on curve. If x1 =x2 and y1 = -y2 then P+Q = O else P + Q = (x3,y3) where,

Elliptic curve modulo prime
Elliptic curve modulo prime

Example

Let a = 1 , b=2 and prime p = 13.

The elliptic curve will generate, and the graphs' points will look like the following.

elliptic curve graph

Each of these points is generated using the addition operation on the starting points P and Q.

You can check out the table of additional points below.

elliptic curve point of generations

Encryption and Decryption using Elliptic Curve

Let Eq(a,b)  be the elliptic curve with parameters a and b where q is the prime modulo.

And G is a point on the curve.
 

Sender Key Generation

Select a private key or point on elliptic curve ns where ns <n <G. Here n on the curve is set as the limiter.

Public key Ps = ns*G.
 

Receiver Key Generation

Select a private key or point on the elliptic curve nr, where nr <n <G.

Public key Pr = nr* G
 

Secret key Generation

For sender: K = ns*Pr

For receiver: K = nr*Ps
 

Let’s perform encryption.

Let the message M be the plaintext. First, we will generate this message m on the elliptic curve as points.

Let the message point be Pm
 

Now cipher text Cm = {K*G, Pm+ K*Pr).

{K*G, Pm+ K*Pr} will be the coordinates of our cipher text Cm.
 

The decryption of cipher text

Keeps in mind that the only K will be the secret key during this encryption and decryption.

Take the K*G from the cipher text Cm and multiply it with the receiver secret key nr

KG*nr.
 

Subtract the above expression from the ciphertext Cm's second coordinate, Pm + K*Pr.

= Pm + K*Pr - (K*G*nr.)
 

We know Pr =  nr*G

= Pm + K*Pr - K*Pr

We can cancel out the K*Pr, and we get the plaintext Pm.

We can decode this point on the elliptic curve and see the message M.

Advantages

  • We can perform elliptic curve cryptography even with the smaller key size compared to other modern cryptography methods.
     
  • The elliptic curve discrete logarithm is difficult to compute compared to the other discrete logarithm methods.
     
  • Various organizations widely use elliptic curve cryptography to better information security.

Frequently Asked Questions

What is a trap door function?

 In a trap function, it is easy to implement in one direction, but it is challenging to inverse the implementation.

How many points can be intersected on an elliptic curve?

At most, three points can be intersected on an elliptic curve.

Which one uses the large key size for encryption, elliptic curve or RSA?

RSA uses a large key size to perform encryption compared to an elliptic curve.

What type of cryptography is applied in the elliptic curve?

Public key cryptography is used in elliptic curve cryptography.

Conclusion

In this blog, we discussed the elliptic curve and trap door functions. We have also discussed elliptical curve cryptography and how we can implement it.

To learn more about cryptography, check out the following articles.

 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Joux’s Index Calculus for Fields of Small Characteristic
Next article
Let’s practice some Discrete Logarithms
Live masterclass