Understanding the elliptic curve cryptography (Part 1) by Manuel Pérez.
INTRODUCTION
Nowadays we live surrounded by technology, and the need for communication and shared content has taken over our lives. But there is one kind of content that we are more reluctant to share, our confidential information. ID, passwords, bank account number, transactions, etc. Information that we need to share securely and, sometimes, anonymously. To achieve this, we use encryption.
To work with this kind of data Cryptography is the key. This post wants to be a gentle introduction to the mathematical part of one of the most critical cryptography methods: ECC, elliptic curve cryptography.
1.INTRODUCTORY EXAMPLE
Let’s start with a simple example to introduce the operation of ECC: The clock. Starting with the graphics of the function x²+y²=1, which is the circle of radius 1, we will treat the points as hours. In this way, the point (0,1) will be 12 o’clock, the point (1,0) represents 3 o’clock, and so on.
In this picture we represent the partition of the circle.
In the first quadrant, we can identify, in addition to the point we said, the 1 o’clock (the point (1/2,√3/2)), 2 o’clock (√3/2,1/2). And what about the point (√2/2, √2/2)? This is one and a half, 1:30.
Note that the points represented have the form (sinαα, cosαα). For this reason, and using the trygonometric formulas, we can consider the addition of two points.
If we symplificate the notation (sinα,cosα)=(x,y), we can rewrite the previous formulas:
that is equal to say that 2:00+3:00=5:00.
We can also double an hour, thats it’s:
or 2(1:00)=2:00.
PROPERTIES
With this two properties, we say that (0,1) is the neutral element for addition (apparently the 12 hours ‘is the 0’ of the clock), and we found a different component for each point, that is, a point for which, if we use that, we can obtain the neutral element.
Note that the addition is a binary and internal operation. So, the sum of two elements of the clock, resulting in an element of the clock. For this reason, the clock is an additive system.
CLOCK OVER FINITE FIELD
Now we consider the clock modulus a prime. This is:
Example with p=7:
In this case, the points that has the property to pertain at C(F_7)are:
(0,1),(0,6)=(0,−1),(1,0),(2,2),(2,5)=(2,−2),(5,2)=(−2,2),
(5,5)=(−2,−2),(6,0)=(−1,0)
We find it with the definition of the field. We need to prove that all of this points fulfill that x²+y²≡1(mod7). For example:
(2,5)∈C(F_7)⇔2²+5²=29≡1(mod7)
The addition works exactly as before, using (F1):
(2,2)+(2,5)=(10+4,10−4)=(14,6)=(0,6)=(0,−1)
Let’s take now a bigger p, like p=1000003, and let’s compute some additions with a point P∈C(F_1000003) (the reader could proof that effectively the point P pertains to C(F_1000003)):
P=(1000,2)
2P=P+P=(2000+2000,4−1000000)=(4000,−999996)=(4000,7)
3P=P+2P=……..=(15000,6)
.
.
.
6P=5P+P=……..=(780000,1351)
An easy exercise could be proving that we don’t need to make five additions to obtain 6P. We need 3, because of 6P=2(3P).
At the practice, we consider a huge prime p. Imagine that somebody tell us that nP=(947472,736284). Can we find nn, then? This is extremely difficult. That’s known as the Discrete Logarithm Problem (DLP).
CLOCK CRYPTOGRAPHY
Once we have established the principles of the computation of the point addition in the clock, let’s see how Clock Cryptography works:
Alice and Bob want to share a secret. So both must agree in the same prime number pp and the same point P=(x,y)∈C(F_p). So:
PROBLEMS
1.This isn’t ellyptic.
2.To equal RSA-3072 we need p≈21536
3.Some p values can make it not safe. An attacker can see the time implemented to generate the product.
2.FIRST EXAMPLES IN ECC
EDWARD’S CURVES
Edward’s curves are:
where d is not quadratic over F_p.
The additive formulas are similar to F1. We only have to divide between the module:
And whenever we have a formula in the denominator, we have to ask ourselves if it can be canceled in any case. Here concretely no, because the condition that d is non-quadratic about the finite body.
The way to operate is identical to the previous case: choose a prime, a non-quadratic d, a point P=(x,y)∈E(F_p). Alice choose the number nA, Bob nB and both apply symmetric encryption.
MONTGOMERY’S CURVES
This expression defines these curves:
To explain the functionality of these curves, we will use the existence of an isomorphism that converts all of Montgomery’s curve into one of Edward’s curve:
As an exercice you can prove that ψ is the inverse of φ.
WEIERSTRASS’ CURVES:
Weierstrass’ are curves that fulfil the formula y²=x³+ax+b, and are the most interest curves to us, since Bitcoin and Ethereum work on this type of curves. Note that Montgomery curves are a particular case of Weierstrass curves. We will explain this type of curves and the cryptography built with them in the next post.
REFERENCES
[1] https://www.youtube.com/watch?v=y_YxRUTI-xU.
[2] Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and
Christiane Peters: “Twisted Edward Curves”.
[3] Daniel J. Bernstein, Tanja Lange: Faster addition and doubling on elliptic curves.
[4] Ian F. Blake, Gadiel Seroussi, Nigel P. Smart: Elliptic curves in cryptography, Cambridge University Press, 2000. ISBN 0–521–65374–6. MR 1 771 549.
[5] http://www.allmathwords.org/es/u/unitcircle.html
Follow Manuel
Twitter: @Manupp94
Follow Caelum Labs
Twitter @caelumLabs
Linkedin
Newsletter #DecentralCafe
