Popular about the key length on elliptic curves
A key constructed on an elliptic curve over a finite field is three times shorter than a key constructed over an integer field. If you get a glimpse into this sentence, then any sensible person will find this absurd, why is it shorter, and if I want longer, that he has some kind of restriction or what? If we reformulate it and say: a key built on an elliptic curve over a finite field provides the cryptographic strength of the algorithm comparable to a key three times as long but over the field of integers it will sound more likely. Let's try to understand what is the "reduction" of the key length.
Crypto-resistance is nothing more than the complexity of the calculation of the most time-consuming inverse operation of the algorithm. In the theory of one-way functions, on which asymmetric cryptography is built, the assumption of the discrete logarithm complexity is NP and is a difficult task. And so, raising the number a to the power n over a finite field and multiplying the point of the elliptic curve by the number are pillars of asymmetric encryption.
The discrete logarithm problem on an elliptic curve over a finite field is to find m, in a pair mA = . Where A and P are points on an elliptic curve. The key m and P are respectively private and public.
Those. the entire complexity of the algorithm is based on the assumption that there is no polynomial algorithm for finding
m, knowing A and R.
')
The addition of points on an elliptic curve is easiest to consider in a geometric interpretation. The operation of addition in this interpretation is the construction of a secant between two points or a tangent in case of doubling of points and the result of the addition will be the third point lying at the intersection of the secant / tangent and the curve.
Scalar point multiplication is implemented as mA = A + A + ... + A = P, i.e. the group of points of an elliptic curve over a field is a finitely generated abalic group, i.e. the group of points of an elliptic curve is additive and therefore the group operations of addition and multiplication based on the induction of addition are defined on it. Those. it is easy enough to get the point P knowing n and A and it is algorithmically difficult to find the number m knowing only the “end” points.
Crypto-resistance is nothing more than the complexity of the calculation of the most time-consuming inverse operation of the algorithm. In the theory of one-way functions, on which asymmetric cryptography is built, the assumption of the discrete logarithm complexity is NP and is a difficult task. And so, raising the number a to the power n over a finite field and multiplying the point of the elliptic curve by the number are pillars of asymmetric encryption.
The discrete logarithm problem on an elliptic curve over a finite field is to find m, in a pair mA = . Where A and P are points on an elliptic curve. The key m and P are respectively private and public.
Those. the entire complexity of the algorithm is based on the assumption that there is no polynomial algorithm for finding
m, knowing A and R.
')
The addition of points on an elliptic curve is easiest to consider in a geometric interpretation. The operation of addition in this interpretation is the construction of a secant between two points or a tangent in case of doubling of points and the result of the addition will be the third point lying at the intersection of the secant / tangent and the curve.
Scalar point multiplication is implemented as mA = A + A + ... + A = P, i.e. the group of points of an elliptic curve over a field is a finitely generated abalic group, i.e. the group of points of an elliptic curve is additive and therefore the group operations of addition and multiplication based on the induction of addition are defined on it. Those. it is easy enough to get the point P knowing n and A and it is algorithmically difficult to find the number m knowing only the “end” points.
Source: https://habr.com/ru/post/100998/
All Articles