The elliptic curve encryption algorithm, namely: Elliptic Curve Cryptography, referred to as ECC, is an asymmetric encryption algorithm based on the mathematical theory of elliptic curves. Compared with RSA, the advantage of ECC is that it can use shorter keys to achieve security equivalent to or higher than RSA. According to research, the security of 160-bit ECC encryption is equivalent to 1024-bit RSA encryption, and the security of 210-bit ECC encryption is equivalent to 2048-bit RSA encryption.
The general elliptic curve equation is expressed as: (where a, b, c, d are coefficients)
> y2=ax3+ bx2+cx+d
Typical The elliptic curve is such as: y2=x3?4x2+16
Let’s give a chestnut first:
The number that is difficult for Xiaomi to calculate is the private key in the public key cryptography algorithm ( A necessary (but not sufficient) condition for the security of a public key cryptographic algorithm is that "the private key cannot be deduced from the public key"). The most fundamental principle of the public key cryptographic algorithm is to take advantage of the asymmetry of information: that is, the person who holds the private key has complete control over the entire Get the most information during the communication process.
The elliptic curve encryption algorithm is a cryptographic scheme based on the hard-to-find addition order problem. For elliptic curves, the base point of the elliptic curve is 5 in the example, and the private key is the addition order of the base point (11 in the example). The public key is the base point (5) and the corresponding order of addition (11 times) is obtained. The result (55).
The simple description is: G * k = K (G, K are public, k is confidential)
The above example is relatively simple. The addition in the elliptic curve encryption algorithm is based on the "finite field" "points on the binary cubic curve" form a "finite additive cyclic group". Specifically, the geometric definition of this addition is as shown below. The addition result of two points refers to the mirror image of the intersection of the line connecting the two points and the curve about the x-axis.
If we start from a certain point (the so-called unit element, such as 1 in the positive integer field, represents the most basic unit in a space), continue to perform self-increment operations (the so-called group operations, such as ++ ), enumerate the collection elements of the entire space. As shown in the figure:
Therefore, given a certain point G of the elliptic curve, starting from G, keep making tangents, find symmetry points, and get -2G, 2G, -4G, 4G, -8G, 8G in sequence. .. . That is: when point G is given and x is known, it is not difficult to find point xG. On the contrary, if the xG point is known, it is very difficult to find x. That is, Q = NG, N is our private key, and Q is our public key.
Now that we know the principle of generating public key (Q) and private key (N), we are looking at the process of Elliptic Curve Digital Signature Algorithm (ECDSA), Elliptic Curve Digital Signature Algorithm (ECDSA) It is an emulation of the Digital Signature Algorithm (DSA) using Elliptic Curve Cryptography (ECC). ECDSA became an ANSI standard in 1999 and an IEEE and NIST standard in 2000.
The private key is mainly used for signature and decryption; the public key is mainly used for signature verification and encryption. The public key can be calculated through the private key, but not vice versa.
Public key encryption: Content encrypted with the public key can be decrypted with the private key - only the holder of the private key can decrypt it.
Private key signature: The content of the private key signature can be verified with the public key. Any signature that can be verified by the public key can be regarded as signed by the holder of the private key.
Usually six parameters are needed to describe a specific elliptic curve: T = (p, a, b, G, n, h).
p: represents the finite field Fp The prime number a, b: the parameter G of the elliptic equation: a base point on the elliptic curve G = (xG, yG) n: the sequence number of G specified in Fp, a prime number. h: cofactor, controls the density of selected points. h = #E(Fp)/n.
Here we take the secp256k1 curve (the curve used for Bitcoin signatures) as an example to introduce the process of generating public and private key pairs.
The parameters of secp256k1 are:
Essentially, the private key of ECDSA is a random number that satisfies the nth order of curve G and k∈(0,n), according to Q=kG The public key can be calculated, the generated private key is generally 32 bytes in size, and the public key is usually 64 bytes in size. For example:
The input of the ECDSA signature algorithm is the hash value of the data, not the data itself. We assume that the user’s key pair: (d, Q); (d is the private key, Q is the public key) Key) Information to be signed: M; e = Hash(M); Signature: Signature(e) = (r, s).
Signature interface:
Verification interface:
An example: