Introduction to the

  • 1. Different from traditional encryption methods based on the difficulty of decomposition of large prime factors,ECC generates key through the properties of elliptic Curve equations.
  • 2. The ECC164-bit key generates a security level, which is equivalent to the security level provided by RSA 1024-bit key. In addition, the calculation level is smaller, the processing speed is faster, and the storage space and transmission bandwidth consumption are smaller. At present, China’s second-generation ID cards are using 256-bit elliptic curve passwords, and the virtual currency Bitcoin also chooses ECC as its encryption algorithm.
  • 3. Elliptic curve cryptography is an algorithm for establishing public-key encryption, also known as asymmetric encryption. Similar to RSA,EIGamal algorithm and so on. ECC is recognized as the most secure encryption algorithm for a given key length.

Public key encryption

Public key encryption, also known as asymmetric encryption. It is the foundation of modern network security or network trust chain. The most important feature of public key encryption is that each communication party has a pair of public and private keys, and each person saves his or her own private key and discloses his or her own public key. The advantage of this method is that the communication line is not afraid of being eavesdropped, because the attacker can not solve the ciphertext with the public key. The public and private keys can be used in the following scenarios: Assume that the communication parties are Tom(public key A, private key A) and Bob(public key B, private key B).

  • 1. Encrypt the public key and decrypt the private key
  • Tom wrote a letter. She didn’t want others to know, so she encrypted the plaintext of the letter with Bob’s public key B, and the ciphertext was M. And then sent it to Bob.
  • Bob receives the ciphertext M, decrypts the ciphertext with his private key, and correctly reads the message.

In the process, even if the eavesdropper had access to the ciphertext M, the public keys A and B of the two men were useless, unable to decrypt anything. In fact, only someone with private key B can decrypt this information. To put it another way, everyone can own Bob’s public key B, that is, everyone can create a piece of information that only Bob can use, or is only valid for Bob.

  • 2. Encrypt the private key and decrypt the public key
  • Tom wrote a public statement file, she used her private key A to encrypt the file, generated an encrypted file M, published on her website.
  • Bob downloads the declaration file, decrypts it using Tom’s public key A, and reads the file correctly.

The main purpose here is not to decrypt, but to verify the provenance of this document, proving that it must be a claim made by Tom. Even if the file is maliciously tampered with, then decrypting the file with public key A at this time will be invalid, which can prove that the information has been changed and is not Tom’s original file. Using public and private keys in this way proves the source of information and has undeniable properties.

The above are the basic scenarios for using public key encryption algorithms. However, in fact, the above methods are far from enough for communication. For example, to improve the encryption speed, files need to be hash first. If you cannot defend against a man-in-the-middle attack, you need to import a certificate (that is, the public key obtained may not be correct).

Elliptic curve

  • 1. An elliptic curve is the set of all points satisfying the Weierstrass equation on the projective plane:

  • The elliptic curve equation is a homogeneous equation
  • Each point on the curve are singular (smooth), partial derivative FX (X, Y, Z), FY (X, Y, Z), FZ (X, Y, Z) is 0.
  • The shape of an elliptic curve is not elliptical. It’s just that the equation that describes an elliptic curve is similar to the equation that calculates the circumference of an ellipse.

In general, an elliptic curve can be represented by the following equation, where a,b,c, and d are coefficients (a≠0, ax^3+bx^2+cx+d=0 with no repeated roots)

E: y ^ 2 = ax ^ 3 + bx ^ 2 + cx + d, for example, when a = 1, b = 0, c = 2, d = 4, the resulting elliptic curve as follows:

E_1:y^2=x^3-2x+4 The elliptic curve is shown below.

Addition of elliptic curves

A group is an algebraic structure consisting of a set and a binary operation. The known set and operation (G,*) must satisfy the following requirements if it is a group:

  • Closure: ∀ A, B ∈G, A * B ∈G
  • Synthetic: ∀ A, B, C ∈G, there is (A * B) * C = A * (b * C).
  • The identity element: ョ E ∈G, ∀ A ∈G, has E * A = A * E = a
  • Inverse element: ∀ A ∈G, ョb∈G such that A * b = B * a = E has a special group called an Abelian group, which, in addition to the above properties, satisfies the commutation law axiomatic: The addition operation of A * B = B * A over the integer range is an Abelian group (Z,+).
  • Closure: IF a and B are integers, then a+b must be integers.
  • Associativity: (a+b)+ C = A + (b + C)
  • Identity element: 0 is the identity element, because for all integers A, a + 0 = 0 + a = a.
  • Inverse element: The inverse element of A is -a because a + (-a)=0, the identity element. So Z plus is an Abelian group.

Define addition on an elliptic curve. Now we have the elliptic curve y^2 = x ^ 3 – x, the points P and Q on the curve. Let’s draw a line through P and Q, the intersecting elliptic curve is R prime, and let’s draw a line perpendicular to the X-axis through R prime, the other intersecting curve is R, and let’s define P + Q = R. As shown in the figure below.

If P=Q, then the tangent line crossing P intersects the elliptic curve is R prime. As shown in the figure below.

In this case, R is equal to 2P. Similarly, 3P = P + P + P = P + 2P = P + R. In other words, when given a point P, it is not difficult to “calculate the point xG of the known number x”, because of the property of addition, the operation can be relatively fast. On the other hand, “the problem of finding x at a given point xG” is very difficult, because you can only do the operation through every x. This is the “discrete logarithm problem on an elliptic curve” used in elliptic curve cryptography.

For this operation to satisfy the property of an Abelian group, we also introduce an infinity point O, which can be thought of as the intersection of parallel lines (see the definition of infinity if this is difficult to understand), and we use this O point as the identity element. (Easy to understand, you can think of all lines parallel to the Y-axis that intersect at O).

The addition on an elliptic curve is an Abelian group

Discrete logarithm problems on elliptic curves

Elliptic curve cryptography exploits the complexity of the “discrete logarithm problem on elliptic curves” of the above “operations”, just as RSA exploits the complexity of the “prime factorization of large numbers”, and the Diffie-Hellman key exchange of EIGamal cryptography exploits the complexity of the “discrete logarithm problem on finite fields”

Discrete logarithm problem on elliptic curve: given point G (base point) on elliptic curve E and point xG (x times G) on elliptic curve E, the difficulty of solving the problem x guarantees the security of elliptic curve cryptography.

Elliptic curves over a finite field

Elliptic curve encryption

Consider K=kG, where K and G are points on the elliptic curve Ep(a,b), n is the order of G (nG=O∞), and K is an integer less than n. Given k and G, it’s easy to calculate k by the rule of addition but the other way around, given k and G, it’s very difficult to find k. Because in principle, THE ECC in practical use can obtain a large p and a large N, it is impossible to calculate the N solution points one by one and list them in the table above. That’s the math behind the elliptic curve encryption algorithm. The point G is called the base point. K (k<n) is the private key, and k is the public key.

ECC secure communication algorithm

1.Alice selects an elliptic curve E and takes a point on the elliptic curve as base point G. Assume that E29(4,20) and base point G(13,23) are selected, and the order n of base point G is 37

2.Alice selects a private key k (k<n) and generates a public key k =kG, for example, 25, k =kG = 25G = (14,6)

3.Alice passes E and points K and G to Bob

4. After receiving the information, Bob will encode the plaintext to be transmitted to the point M above (the encoding method is omitted), and generate a random integer r (r<n,n is the order of G). Assume that r=6, the information to be encrypted is 3, because M also needs to be at E29(4,20), so M=(3,28).

5. Bob calculation point C1 = M + fairly rK and C2 = rG C1 = = M + 625 M + 6 k g = = (3 p) + M + 2 g (27, 27) = (6, 12) C2 = 6 g = (5, 7)

6.Bob sends C1 and C2 to Alice

7. Alice after receiving the information, computing C1 – kC2, as a result, it should be point M C1 – kC2 = (6, 12) – 25 c2 = (6, 12) – 25 * 6 g = (6, 12) – 2 g = (6, 12) – (27, 27) = (6, 12) + (27, 2) = (3 p)

C1-kc2 =M+ rk-krg =M+ rkg-krg-m

ECC Technical requirements

An elliptic curve on Fp is usually described as T=(p,a,b,G,n,h)p, A,b determine an elliptic curve (p is prime number, (mod p) operation) G is the basis point,n is the order of point G, h is the integer part of the quotient of all points on the elliptic curve m divided by n

Parameter selection requirements:

The larger p is, the safer it is, but it will slow down the calculation speed. About 200-bit can meet the general safety requirements. N should be a prime number h≤4. P indicates n * h; Pt ≠1(mod n) (1≤t < 20) 4A3 + 27B2 ≠0 (mod p)

The application of ECC

P = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFFFE FFFFFC2F= 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2 ^ 4-1

A is equal to 0, b is equal to 7

G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

h = 01

ECC vs. RSA – Pros and cons

advantages

Higher safety performance

160-bit ECC has the same security strength as 1024-bit RSA and DSA

Faster processing speed

ECC is much faster than RSA and DSA in processing private keys

Lower bandwidth requirements

Less storage space

The key size and system parameters of ECC are much smaller than those of RSA and DSA

disadvantages

Design is difficult and implementation is complex

If the serial number is designed to be too short, the security is not as good as expected

References:

Elliptic curve encryption algorithm

ECC elliptic curve details (with specific examples)