Editor's note: This article is from Lanhubiji (ID: lanhubiji), author: Lane Wager, from medium, translated by "Wang Zelong" of the "Blue Fox Notes" public account community, and reprinted by Odaily with authorization.
Preface: This article is a very basic introduction to elliptic curve cryptography. Although the content is basic, it is easy to understand for laymen of elliptic curve encryption and suitable for beginners.
image description
secondary title
What does it do?
Elliptic curve encryption is a method of encrypting data so that only certain people can decrypt it. It has many application scenarios in real life, but its main application is to encrypt data and traffic on the Internet. For example, elliptic cryptographic curves can be used to ensure that when an email is sent, no one can read it except the recipient.
Elliptic curve cryptography is public key cryptography
There are many styles of public key encryption, and elliptic curve encryption is just one of them. Other encryption algorithms include RSA, DiffieHelman, and so on. I will briefly explain the general background of public key encryption as the beginning, and then expand our follow-up explanations to gain a deeper understanding of elliptic curve encryption. When you have time, you can spend some time delving into public key cryptography.
image description
http://itlaw.wikia.com/wiki/Key_pair
The diagram above shows two keys, a public key and a private key. These keys are used to encrypt and decrypt data, which makes it possible for anyone in the world to see the encrypted data while it is in transit, but not to read the information.
Let's assume Facebook will receive private posts from Trump. Facebook needs to be able to ensure that when Trump posts online, no one, including the NSA or Internet service providers, can read the message there. After using public key encryption, the entire data transmission process presents the following status:
l Trump told Facebook he was sending it a private post
l Facebook sends its public key to Trump
l Trump uses a public key to encrypt his posts:
"I love Fox and friends" + public key = "s80s1s9sadjds9s"
l Trump only sends encrypted messages to Facebook
l Facebook decrypts the message using their private key:
"s80s1s9sadjds9s" + public key = "I love Fox and friends"
As you can see, this is a very useful technique. Here are some of the highlights:
l The public key can be sent to anyone, it is public
l The private key must be kept safe, because if someone obtains the private key, they can decrypt the information
l Computers can quickly encrypt messages with the public key and decrypt messages with the private key
l Without the private key, it may take a computer an extremely long time (millions of years) to decipher the encrypted message
How it works: Trapdoor function
The key to all public-key encryption algorithms is that each has its own unique trapdoor function. Trapdoor functions can only be computed one way, or at least easily one way (with modern computers in less than a few million years)
Not a trapdoor function: A+B=C
Trapdoor function:
Trapdoor function:
"I love Fox and friends" + public key = "s80s1s9sadjds9s"
If I'm given "I love Fox and friends" + public key, I can get "s80s1s9sadjds9s", but if I'm given "s80s1s9sadjds9s" and public key, I can't get the message: "I Love Fox & Friends".
In RSA (probably the most popular public-key system), the trapdoor function depends primarily on the difficulty of factoring large numbers into its prime.
Public key: 944,871,836,856,449,473
Private key: 961,748,941 and 982,451,653
In the above example, the public key is a very large number and the private key is the two prime factors of the public key. This is a good example of a trapdoor function, because in the private key it's easy to multiply numbers together to get the public key, but if all you have is the public key, it would take a computer a long time to reconstruct private key.
secondary title
What Makes Elliptic Curve Cryptography Different
People use elliptic curve cryptography for exactly the same reasons as RSA. It generates public-private key pairs and allows two parties to communicate securely. However, elliptic curve cryptography has one advantage over RSA. A 256-bit key in elliptic curve encryption provides the same security as a 3072-bit key in the RSA algorithm. This means that in systems with limited resources, such as smartphones, embedded computers, and encrypted networks, elliptic curve encryption uses less than 10% of the hard disk space and bandwidth of the RSA algorithm compared to the RSA encryption algorithm. (Blue Fox Note: That is to say, elliptic curve encryption is more resource-efficient and more feasible than RSA algorithm in the case of limited resources.)
Trapdoor function for elliptic curve encryption
image description
https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/2/
l Start from point A;
l A point B=-C (draw a line from A to B point and finally fall on -C point)
l Reflect across the X axis from -C to C;
l Point A C=-D (draw a line from point A to point C and finally fall on -D)
l Reflect across the X axis from -D to D;
l A point D=-E (draw a line from A to D and finally fall on -E)
l Reflection across the X axis from -E to E
This is a great trapdoor function because finding the end point is easy if you know where the start point (A) is and how many hops it takes to get to the end point E. On the other hand, if all you know is where the start and end points are, it's nearly impossible to find out how many hops it takes to get there.
Public key: start point A, end point E;
Private key: number of hops from A to E
Is there a problem?
The following are related questions that arose when I first learned about elliptic curve cryptography. Hope I can solve them properly.
How to discover the second point? If the dot function just draws a line between two points, wouldn't a second dot be needed to help get started?
Answer: No need. The second point (let's call it the -R point in the diagram below) is actually a function P of the point P (let's assume the first point is called P)
P point function P=-R
image description
https://devcentral.f5.com/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832
What happens if the point function produces a line that goes to a certain extreme?
image description
https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/2/
I understand the trapdoor function, but how are public and private keys created in practice? How are they used with the data to be encrypted?
This is a good question, but it demands a deeper answer. In this article I give a more general explanation of RSA and elliptic curve encryption. However, there are many more technical resources, and I urge you to research them.
