Reference article
[Contents]
Mathematically, an elliptic curve is an algebraic curve that looks like
$$y^2 = x^3 + ax + b$$
And the curve has no singularity (cusp or selfing), and the discriminant $\Delta =-16(4a 3+27b 2)$ is not 0.
An infinite point o is added to the elliptic curve. Since the curve is symmetrical about the Y axis, let's assume that P is a point on the curve, and the symmetry point of P about the Y axis is defined as-P. The symmetry point at infinity is itself, so O = -O O o.
Define+operation, assuming that p, q and -R are all on the curve, then p+q =-r-> P+Q+R = O where -R and p, Q*** lines.
Define number multiplication *
$$
nP = \ under brace { P+P+\ cdots+P } _ { n \ \ text { times } }
$$
$$y^2 = x^3 + ax+ b \bmod{p}$$
The following figure is the point set when the curve $ y 2 = x 3-7x+10 \ bmod {p}, where p is19,97,127,487. It can be seen that the point set is symmetrical about y = p/2.
Define the straight line $ax+bx+c \equiv 0 \bmod{p}$ It is a family of straight lines with equal spacing.
If p, q and -r in the point set are on the same straight line, then p+q+r = o.
$(9 9^{- 1})\ mod \ 23 = 1 =(9 18)mod \ 23 $)
$P = (x_p，y_p)$
$Q = (x_q，y_q)$
$R = (x_r，y_r)$
$$P+Q = -R$$
formula
$$
x_r = (m^2-x_p-x_q) \bmod{p}
$$
$$
y_r = [y_p+m(x_r-x_p)]\bmod{p}
$$
If $P \neq Q $，$ m =(y _ P-y _ Q)(x _ P-x _ Q){- 1 } \ b mod { P } $
If $P = Q$, $ m = (3x _ p2+a) (2y _ p) {-1} \ bmod {p} $
The number of points in a point set is called the order of elliptic curve, and there is a fast algorithm Schoof algorithm.
$ $ nP = \ under brace { P+P+\ cdots+P } _ { n \ \ text { times } } $ $
For example, the point $ p = (3,6) $ of the curve $ y 2 \ equiv x 3+2x+3 \ bmod {97} $
As can be seen from the above example, when p is multiplied by a number, only a few results of finite cycles $kP = (k\bmod{5})P$ are closed under the addition operation. These five points form a cyclic subgroup, where p is called the generating base point of the cyclic subgroup.
Cyclic subgroups are the basis of elliptic curve cryptosystems and other cryptosystems.
The order of is the smallest positive integer $n$ so that $nP = 0$. In fact, if you look at the previous example, our subgroup contains five points, and we have $5P = 0$.
The order of $P$ is related to the order of elliptic curve by Lagrange theorem, which points out that the order of subgroup is the divisor of the order of parent group.
In other words, if an elliptic curve contains $N$ points and one of its subgroups contains $n$ points, then $n$ is the divisor of $N$, so $N\ mod\ n \equiv 0$
For example, the order of the curve $ y 2 = x 3-x+3 $ over the field $ ＄f _ {37 }＄ $ is $ ＄n = 42＄ $. Its subgroups can have the order of 1, 2, 3, 6, 7, 14, 2 1 and 42. If we try $ p = (2,3) $,we can see that $ 1P\neq0, 2P\neq0, 3P\neq0, 6P\neq0, 7P=0, $ so the order is 7.
For ECC algorithm, we hope that the order of subgroups is high enough. So we usually choose an elliptic curve, calculate its order, choose a larger factor as the order of the subgroup, and finally find a base point.
Let $h =N/n$ in Lagrange theorem call $h$ the cofactor of subgroups.
Because $nP = 0$, $h(nP) = 0 = n(hP)$
Now consider that $n$ is a prime number, and let $G =hP$, then an n-order subgroup based on $G$ is generated.
Now that PQ is on the elliptic curve, how to determine the integer $k$ so that $Q =kP$? This problem is called the discrete logarithm problem of elliptic curve, which is considered to be a difficult problem. At present, there is no polynomial time solution.
In cryptography, digital signature algorithm (DSA), differential -hellman key exchange (D-H) and elgamal algorithm are all related to this problem.
ECC problem is more difficult to solve than other problems.
Our elliptic curve algorithm will work in the cyclic subgroup of elliptic curves over finite fields.
The algorithm sextuple $(p, a, b, g, n, h)$ is obtained.
The discrete logarithm problem mentioned above is difficult, but not all of them are difficult. Some types of elliptic curves are very fragile and have very quick solutions. For example, when $p = hn$, there is a polynomial time solution.
How to ensure the safety of corners?
To solve this problem, we need to add another parameter seed $S$, which is a random number to generate parameters A and B, or base point G or all parameters. These parameters are generated by hash function, which is easy to calculate but difficult to reverse.
Elliptic curves are generated by random numbers, which makes the curves random enough.
If we know $d$ and $G$, it is very easy to calculate $H$. But if only $H$ and $G$ are known, it will be very difficult to calculate $d$ because it is a discrete logarithm problem.
ECDH is a variant of Diffie-Hellman algorithm, which is more like key exchange negotiation than encryption. Application scenario: both parties need to exchange information safely, even if it is intercepted by a third party, it cannot be deciphered. This is the principle behind TSL.
$ $ S = d _ AH _ B = d _ A(d _ BG)= d _ B(d _ AG)= d _ BH _ A $ $
Alice uses the private key $d_A$ to sign the file, and Bob uses Alice's * * * key $H_A$ to confirm.
ECDSA acts on the hash of the message, not directly on the message. Hash functions can be cryptographically secure. The hash needs to be truncated to the same length as the bits occupied by the subgroup order $n$. For example, if the previous n is 256 bits, then the hash also needs to be 256 bits, and the truncated hash is defined as the integer $z$.
$(r, s)$ is the signature.
Alice signed the hash $z$ with the private key $d_A$ and the random number $j$. Bob uses Alice's * * * key $H_A$ for authentication.
To verify the signature, the hash $z$ is truncated by Alice's * * * key $H_A$ and signature $(r, s)$.
If $r=x_P\bmod{n}$ is legal.
$$
\begin{array}{rl}
Procter & gamble company. = u_ 1 G + u_2 H_A \
& amp= u_ 1 G + u_2 d_A G \
& amp= (u_ 1 + u_2 d_A) G
\end{array}
$$
Then the definitions of $ u _ 1 and u _ 2 $ are introduced.
$$
\begin{array}{rl}
Procter & gamble company. = (u_ 1 + u_2 d_A) G \
& amp=(s^{- 1} z+s^{- 1} r d a)g \
& amp= s^{- 1}(z+r d a)g
\end{array}
$$
The $mod\ n$ is omitted here, because the order in the subgroup is $n$, so it is equivalent to automatically modulo n. Deduce $ k = s {-1} (z+rd _ a) \ bmod {n} $ (z+rd _ a) \ bmod {n} $.
$$
\begin{array}{rl}
Procter & gamble company. = s^{- 1}(z+RDA)g \
& amp= k G
\end{array}
$$
This is the same point p generated in the second step of the signature algorithm, and then the signature can be verified by verifying whether it meets the third step of the generation algorithm.
When using ECDSA for digital signature, k should be quite full. If each signature uses the same k, or k is predictable, the private key is found. This is the kind that Sony shot a few years ago. The PS3 can only run programs signed by Sony with ECDSA, but the problem is that Sony uses a fixed K ..
So you can easily find Sony's private key $d_S$. Just buy two signature games and take out their hash ($z_ 1 z_2$) and two signatures $ (r _ 1, s _ 1), (r _ 2, s _ 2) $.
$$
s = k^{- 1}(z+rd_s)\bmod{n}\rightarrow d _ s = r^{- 1}(sk-z)\bmod{n}
$$
We think the discrete logarithm problem is very difficult, but it has never been proved mathematically. At present, there are three methods to solve the discrete logarithm problem. Suppose $Q=xP$ and find x.
Assume at will that $x=am+b$
$$
\begin{array}{rl}
Ask and answer. = xP \
Ask and answer. = (am + b) P \
Ask and answer. = am P + b P \
q-am P & amp； = b P
\end{array}
$$
Select a standard curve element 192v 1, $ n $ = 0xffffffff99d ef 836146bc9b1b4d22831,$ \ sqrt {n} \ is about 7.9 \ Cdot 10 {28}$ each point needs 32 bytes of storage, which is about $2.5 \ cdot 10 {0 and prime 192v 1 is a low-order curve.
Using quantum algorithm can reduce the complexity by $ o ((\ log {n}) 3) $
$ y 2+xy = x 3+ax 2+1 $ a is 0 or1,with $2 m $ points, where m is a prime number.
$ x 2+xy = x 3+x 2+b $ b is a randomly generated integer.
These two curves are faster to calculate.