Statement: reprint with clear indication of oneself or source, please inform as far as possible at your convenience.

Respect originality and make progress together.

The profile

Elliptic Curve Digital Signature Algorithm (ECDSA) : a Digital Signature Algorithm using Elliptic Curve encryption Algorithm. Reference 3

Security level (bit indicates the maximum number of possible decryption operations). For example, an 80bit public key means that it may take up to 2^80 operations to find the private key.

At the 80-bit security level, the public key length of the ECDSA is 160 bits, while the public key length of the DSA is 320 bits, which is greatly reduced in size.

The basic flow

  • The basic idea of the algorithm:

  1. Pick a curve
  2. Choose a point on the curve as your origin
  3. Generate a random number for your private key
  4. Take the origin and random number, and go through a bunch of magical math to get your public key

  • After generating the public key, the basic logic for your signature is:

  1. Gets the Hash of the data (or file) to be signed
  2. Use the private key to pair thisHashSignature and generateRandS Detailed instructions

  • After completing the signature, the basic logic for others to verify the signature is as follows:

  1. useSAnd the public key, through a magical mathematical operation, is generatedR'
  2. contrastRandR', if the two are the same, the signature is valid. Otherwise, illegalDetailed instructions

The public key, with modern computing power, is virtually impossible to reverse, so it is safe for the most part (see security level). For convenience, the public key length of ECDSA is set to 160 bits, that is, 20 bytes

Brief introduction of algorithm Principle

  1. HashIt’s a summary of the data. It’s standardECDSAIt’s using the Hash algorithmSHA1But this can be replaced, such as availableSHA3Algorithm for data summarization. The larger the length of this abstract, the more computation, the higher the theoretical security.
  2. Elliptic curve formulay^2 = (x^3 + a * x + b) mod pAnd some additionpoint additionIt is the basis of ECDSA.Reference 2.
  3. A secret functiontrapdoor function, one-way operation is simple, reverse operation is difficult.ECDSAIt belongs to a kind of secret door function of discrete logarithm class. It belongs to the encryption algorithm with mature theory and relatively high security factor.Reference 4
  4. ECDSAParameters to be set in the algorithm include:y^2 = (x^3 + a * x + b) mod pIn thea.b, specify the curve.pIs a prime number. There’s moreN, the number of points on the elliptic curve,0 < N < pAnd,Nisperfect square. AndGThe point on any curve, as the origin of your operation.
  5. The existence of public key alone cannot prove whether the signature of private key is legal or not, and the operation needs to use the same parameter.

Some details

Create a signature

The 40-byte signature is divided into two parts. R and S, 20 bytes each

Generation of R:

  • To generate, a random algorithm is used to generate a 20-bytek
  • To usePoint multiplicationI get point P,P=k*G
  • The x coordinate value of point P is, thenR

Generation of S:

  • Gets the Hash value of the data, which is z
  • S = k^-1 (z + dA * R) mod p.dAThe private key

Verify the signature

  • P = S^-1*z*G + S^-1 * R * Qa.QaThe public key
  • If the x coordinate of P is equal to R, the signature is legal, otherwise it is illegal.

Algorithmic risk point

  • kRandom value. The value must be a random number of encryption strength. If its pseudo-random value can be guessed/reproduced, it means it has been hacked. The existing cases areSONY PLAYSTATION 3 was hacked

The specific implementation

  • C version
  • Go version

Expand the implementation

  • secp256k1The realization of bitcoinsStandards for Efficient Cryptography(SEC). The realization of this algorithm was gradually paid attention to and adopted by the industry after Bitcoin became popular. The root cause is that it is about 30% faster than other implementations.

Reference documentation

  1. By snifikino UNDERSTANDING HOW ECDSA PROTECTS YOUR DATA www.instructables.com/id/Understa…
  2. Security level En.wikipedia.org/wiki/Securi…
  3. Elliptic Curve Digital Signature Algorithm En.wikipedia.org/wiki/Ellipt…
  4. Trapdoor function En.wikipedia.org/wiki/Trapdo…
  5. Discrete logarithm En.wikipedia.org/wiki/Discre…
  6. Perfect square(Square number) En.wikipedia.org/wiki/Square…
  7. Secp256k1 En. Bitcoins. It/wiki/Secp25…