Popularly about key length on elliptic curves

    A key built on an elliptic curve above a finite field is three times shorter than a key built over an integer field. If you read this proposal, then it will seem absurd to any sane person, why is it shorter, and if I want longer, does it have some kind of restriction or something? If we reformulate it and say: a key built on an elliptic curve above a finite field ensures the cryptographic strength of the algorithm comparable to a key three times as long, but over a field of integers this will sound more believable. Let's try to figure out what the “reduction” of the key length is.

    Cryptographic strength is nothing but the complexity of computing the most time-consuming inverse operation of an algorithm. In the theory of one-way functions, on which asymmetric cryptography is built, is the assumption of the complexity of discrete logarithms and is NP difficult task. And so, raising a number to the power of n over a finite field and multiplying a point of an elliptic curve by a number are the pillars of asymmetric encryption.

    The task of a discrete logarithm on an elliptic curve over a finite field is to find m, in the pair mA = P. Where A and P are points on an elliptic curve. Key m and P are respectively private and public.

    Those. all the complexity of the algorithm is based on the assumption that there is no polynomial algorithm for finding
    m, knowing A and P.

    The addition of points on an elliptic curve is easiest to consider in a geometric interpretation. The addition operation in this interpretation is the construction of a secant between two points or a tangent in the case of doubling the points, and the result of the addition will be the third point lying at the intersection of the secant / tangent and the curve.
    Addition of points on an elliptic curve

    Scalar multiplication of a point is realized as mA = A + A + ... + A = P, i.e. the group of points of an elliptic curve over a field is a finitely generated abalian group, i.e. the group of points of an elliptic curve is additive and therefore 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.

    Also popular now: