Elliptic curve cryptography basics
This is my first post about cryptography. Recently I learnt basics about public key encryption and the TLS handshake. But the key exhange in the TLS handshake inspected by Wireshark, i.e. ECDH(Elliptic-curve Diffie–Hellman) troubled me for a while. This this the first time I knew Elliptic curve. After some investigation, I’m recording those knowledges in case that I forget them.
Note: in the following several posts, I would record more things I learnt about cryptography and its application in the computer network and Internet.
A elliptic curve could be defined as:
Some examples of elliptic curves are like:
equation for red line is , equation for purple line is
Now lets review the Group) concept.
A set is a group if a binary operation could be defined on it, and 4 conditions are met. Usually we denote the operation as addition and denoted as , then the 4 conditions are:
- Closure: is always in as long as and in .
- Associativity: for any , and in , .
- Identity element: there is an element in such that for any in .
- Inverse element: for any in , there is an element in such that , and we say .
A group is a Abelian group if the follwoing condition is also met:
commutation: for any and in , there is
Aparently the set of all real numbers could be an Abelian group with the arithmetic adding operation.
A finite group is a group with limited elements. For any element in a group , if you repeatly add to itself, you would get . I.e. there is a number such that .
Why? Lets say the group has elements, then the list would have same elements in it. Assume they are , then you see .
First, the set consists of all points in a elliptic curve.
The Identity element would be a little special, it’s defined as the infinitely far points of the curve.
Now, lets define the operation. For any points and in the curve:
- if and , then
- if and , then is the other intersection of the curve and the line tangent to the curve in .
- if and , then
- if and , then is the 3rd intersection of the curve and the line cross and .
From the 3rd and 4th cases above, we know the relation between and , would be like:
It can be proved that such a group is an Abelian group.
We can also defin a scalar multiplication based on the plus operation upon the elliptic curve groups:
where is a positive integer and is a element in the group.
The above expression could be calculated in time complexity of by disassembling the into factors that are powers of 2.
In last section, we see given and , it’s easy to get . However, given the and result of , with some cleverly constructed instances it would be very hard to know the value of , i.e. the times of operation performed to get the . And this hard problem is called logrithm problem.
An Abelian Group is a Ring if multiplication denoted as could also be defined and:
- associative: for any , , in the set.
- distributive: and .
- multiplicative identity 1: .
Note, a ring is a commutative ring if multiplication commutative is is satisfied.
A Field) is a commutative ring which also satisfies:
- additive identity is different from multiplicative identity .
- multiplicative inverse element, for any , there is such that , in which we mark , hence division could be defined: .
For a prime , the set of integers from 0 to could be a field. And the addition and multiplication are defined as:
Besides, assume the number 0 and 1 are and respectively. Then apparently is since:
But the multipilicative inverse is not that easy, actually the extended Euclidean algorithm tell us this could be done in time complexity of . As an example, 4 and 2 are mutual multipilicative inverse when is 7 since .
Previously the elliptic curves consist of points with coordinates of real numbers. But now we restrict the curve upon a finite field which only contains integers betwen 0 and .
Where is a prime number, , , and are integers, and .
Here is an example graph of :
Note that most of the points in the above graph are symmetrical over the line except the points on line .
To define a group, firstly we need to define the plus operation on the elliptic curve over finite fields. The plus operation is similar to the operation we defined previously for elliptic curve over real numbers.
The identity element is same as before. The reverse pair of elements are symmectircal over the line .
For any pointers and on the discrete curve and , is the reverse proint of the 3rd intersection between the discrete curve points and the lines denoted by:
when one of the lines cross and , and , and are inetger constants.
The following is an example, where the discrete elliptic curve equation is , and the lines equation is :
In above diagram, and are and respectively, while is . So this is a general example, how about when is just ? What’s the is this group?
The is still the infinitely far point. Well, this seems strange becase the infinitely far point is not in the discrete elliptic curve. And there has when .
When is just , we can also get the tangent line whose slope value is the derivative of the elliptic curve equation at the point .
It could be proved with such a plus operation defined, a group is generated on the discrete elliptic curve over a finite field from prime .
The number of points (including the ) in such a group is called the order of the group. The Schoof’s algorithm is an efficient algorithm to calculate the number of points.
Similar with previous continuous elliptic curve, we can perform scalar multipilication:
where is a positive integer and is an element in the group.
For any in such a group , the smallest integer such that equals is called the order of the subgroup which consists of , , , , …, . The subgroup is cyclic. And the number of elements in a subgroup is called order of the subgroup.
Let’s say the order of the parent group is . According to Lagrange’s theorem), the order of a subgroup is a diviser of .
As an example, lets use the and assum3 is . It could be calculated that are . Show as below:
In above diagram, the order of the parent group is 24. The order of the subgroup is 8, which is a diviser of 24. Also for the point , its inverse point is itself (actually the slope value here is infinity).
Note that different subgroups might share points. For instance, in the above example any subgroup whose base point is order is an even number , then is the point .
Hence for any in the parent group, we can check the divisers of one by one to find out the order of subgroup based on .
On the contrary, for any prime diviser of , any element point such that not equal the is the base point to form a subgroup whose order is . (Hint: is always the .)
Given and in such a group G, getting a such that is also very hard for some instances of discrete elliptic curve, just like the logrithm problem we mentioned previously.
To leverage elliptic curve group over finite fileds on primes, there are some parameters called domain parameters to determine the concrete elliptic curve instances.
- and , real numbers to determine the equation.
- , a prime that determine the finite field of 0, 1, 2, 3, …, .
- , a base point in the discrete elliptic curve to form a cyclic subgroup of , , , …, .
- , which is order of the subgroup based on , hence is the .
- , called cofactor, which is result of divides the order of the parent group.
The above consists the domain parameters that determine the concrete instances. Thoso domain parameters are public to everyone.
In the Elliptic curve cryptography, The private key is a random number such that . The public key is the result of .
In EC Diffie-Hellman key exchange algorithm. Alice and Bob have their private keys and . With the public domain parameters, they would compute and and exchange these two values (public keys). Finally, they would compute and respectively as the secret key for symmetric encryption. Of course .
The EC Diffie-Hellman key exchange is based on that given the domain parameters, it’s hard to know given and , and same for and .
While the original Diffie-Hellman key exchange algorithm is based on exponential modular. Assume is a prime and is a primitive root modulo and both of them are public. Private keys are random numbers and , public keys are and , and the secret key for symmectric encryption is .
The shared secret key in EC Diffie-Hellman key exchange algorithm are coordinates of the point , which could be used to perform symmectirc encryption just like TLS does.
Actually in TLS, we often see ECDHE in which the ending E means ephemeral which means the shared secret key is temporary. Actually when TLS uses ECDHE, during the handshake procedure, the public and private keys generated in ECDHE won’t be used for encryption. TLS just want both sides to generate a shared private symmectric encryption key, which is really for encryption of application data.
EC digital signature algorithm is a signature algorithm like RSA. Alice could use her private key to generate a signature for digest of a message. Bob would be able to verify the signature by using public key of Alice, i.e. .
ECC(clliptic curve cryptography) is better than RSA in that key size of ECC is smaller to achieve same security level. Moreover, the security level improved by doubling key size of RSA is less than ECC.