Popular Science | Read the Bitcoin Schnorr signature in one article

Public-private key pairs are the cornerstone of cryptocurrency security, from secure web browsing to cryptocurrency financial services. The public-private key pair is asymmetric, which means that given a string of numbers (private keys), another string (public key) can be derived. However, the opposite is not feasible. It is this asymmetry that allows people to share public keys publicly, and publicly can be sure that no one can deduce a private key (a private key needs to be kept secretly and securely).

Asymmetric key pairs are mainly used for two applications:

· In authentication, you need to prove that you have a private key;

· In the encryption process, information can be encoded, and only those with a private key can decrypt and read the message.

• Plasma: Ethereum chain scalability framework combat part 1
• Technical Guide | Web3.js is based on the Ethereum Javascript API
• Some science about Ethereum 2.0

In the introduction of this digital signature, we will discuss a specific type of key: the key derived from the elliptic curve, and other asymmetric schemes, the most important of which is based on the prime product scheme, including the RSA key [1] .

We assume that you understand the basics of Elliptic Curve Cryptography. If you don't understand it, you can go to the previous chapter of the original text.

·Into the title

This is an interactive introduction to digital signatures, using Rust code to demonstrate some of the ideas mentioned in this article, so you can see how they work. The code presented in this article uses the libsecp256k-rs sub-library.

The name is a bit sloppy, but secp256k1 is the name of an elliptic curve that protects many cryptocurrency transactions, including bitcoin.

This particular library provides some nice features. We rewrote the addition and multiplication operators so that the Rust code looks more like a math formula, which makes it easier for us to experiment with the ideas we want to implement.

friendly reminder! Don't use this library while writing code, it's not validated, you can use this sub-library instead if you need to.

· The basics of Schnorr signature

· public and private keys

The first thing we have to do is to create the public and private keys from the elliptic curve.

In secp256k1, the private key is only a scalar integer value between 0 and 2256, and the number is equivalent to the number of atoms in the entire universe, so there is endless possibilities.

There is a special point on the secp256k1 curve called G, which acts as the "origin". The public key is obtained by adding G on the curve to itself and multiplying it by "Ka", which is the definition of scalar multiplication, written as:

Pa=KaG

For example, when writing in uncompressed format, the public key of 1 is 0479BE667 … C47D08FFB10D4B8, the following code demonstrates this:

 

· Create a signature

Adoption method

Inverted ECC mathematical multiplication (ie, division) is almost infeasible when using properly chosen random values ​​for scalars ([5], [6]). This property is called the Discrete Log Problem and is used as the principle behind many cryptocurrencies and digital signatures. A valid digital signature is evidence that the signature provider knows the public/private key associated with the message, or that the discrete log problem has been resolved.

The method of creating a signature always follows the following methods: 1. Generate a secret one-time number r (called a random number). 2. Create a public key R from r, where (R=rG). 3. Send the following to your recipient Bob – your message (m), R and your public key (P = kG).

Create a real signature by hashing all of the above common information to create a problem, e:

e=H(R||P||m)

Select the hash function so that e has the same range as the private key. In our case, the information we want to return is 256-bit numbers, so SHA256 is a good choice.

Now build your signature with your private information: s=r+ke

Bob can now also calculate e because he already knows m, R, and P, but he doesn't know your private key or random number.

Note: Creating such a signature is called a Schnorr signature, which we will discuss later, and other methods for creating s, such as ECDSA [2] used in Bitcoin.

Look at this example: sG=(r+ke)G

Multiply the right side: sG=rG+(kG)e

Instead of R=rG and P=kG, you can get: sG=R+Pe

So Bob must calculate the public key corresponding to the signature (sG) and check if it is equal to the right side of the equation (R+Pe). These messages are known to Bob.

 

· The necessity of random number Nonce , why do random numbers need to be used in standard signatures?

Suppose we just signed a message m:

e=H(P||m)

Signature is s=ek

Can we verify that the signature is valid as usual?

It's normal right now, but now anyone can read your private key, because s is a scalar, so k=s/e is not difficult. As for random numbers, you must solve k=(sr)/e, but r is unknown. , so as long as r is randomly chosen, this is not a viable calculation.

We can prove that no random number is really very unsafe:

 

·What is ECDH?

How do parties who want to implement secure communication generate a shared key for encrypting messages? One method is called the Elliptic Curve Diffie-Hellmam exchange, which is a simple method.

ECDH is used in many places, including lightning networks during channel negotiation [3].

This is how it works. Alice and Bob want to communicate securely. An easy way is to use each other's public key and do the calculation:

For security reasons, the private key is usually chosen randomly for each session (this involves the use of the term "temporary key"), but the problem we have is that we are not sure if the other party matches their claimed identity (may It is a middleman attack [4]).

Other authentication steps can be used to resolve this issue and will not be detailed here.

 

·Schnorr signature

If you are constantly concerned about cryptocurrency news, you will know how popular the Bitcoin Schnorr signature is.

But in fact, this is already an old news. Schnorr signature is regarded as the simplest secure digital signature scheme in the random prediction model. It is very efficient and generates short signatures. It has obtained US patent 4995082, which expired in February 2008. [7].

 

· Why does the Schnorr signature cause concern?

The reason why the Schnorr signature is so fascinating and dangerous is simplicity. The Schnorr signature is linear and therefore has some excellent properties.

Elliptic curves have multiplicative properties, so if there are two corresponding points X, Y and the corresponding scalar x, y, then:

(x+y)G=xG+yG=X+Y

The Schnorr signature is of the form s=r+ek. This structure is also linear, so it is very suitable for the linearity of elliptic curve mathematics.

Linearity has been introduced in the previous section, and the linearity of the Schnorr signature makes it very attractive when we verify signatures, including: 1. signature aggregation; 2. atomic exchange; 3. "no script" script

 

·Naïve signature aggregation

Let's see how the linear properties of the Schnorr signature are used to construct multiple signatures.

Alice and Bob want to sign something (like the Tari transaction) without having to trust each other, that is, they need to prove ownership of their respective keys, and the aggregated signature is only valid if both Alice and Bob provide their signature parts.

Suppose the private key is represented as ki and the public key is represented as Pi. If we ask Alice and Bob to each provide a random number, try:

So Alice and Bob can provide R by themselves. Anyone can build two signatures from R's total public key. This is indeed possible:

But this framework is not safe!

 

·Key elimination attack

This is still the above scenario, but this time, after Alice announced, Bob knew Alice's public key and random number in advance.

Bob now lie and says his public key is P'b=Pb-Pa and the public random number is R'b=Rb-Ra.

Bob doesn't know the private key of the fake value, but it doesn't matter much.

According to the aggregation scheme, everyone assumes Sagg=Ra+R'b+e(Pa+P'b).

But Bob can create this signature himself:

 

· Better polymerization method

In the key cancellation attack, Bob does not know the private key of the published R and P values. We can ask him to sign a message to prove that he does know the private key and let the Bob attack fail.

This is effective, but it requires another round of messaging between the parties, which is not good for a good user experience.

A better approach is to include one or more of the following methods: • It only needs to prove safe in a normal public key model, without having to prove the key-related message, because we can ask Bob to prove it in naïve mode . · It should satisfy the conventional Schnorr equation, ie the signature can be verified with an expression in the form of R+eX. · It allows for interactive aggregate signatures (IAS) that signers need to work with. · It allows non-interactive aggregated signatures (NAS) where aggregation can be done by anyone. · It allows each signer to sign the same message, m. · It allows each signer to sign his own message, mi.

 

·Multiple signature

Multi-signature is a recently proposed ([8], [9]) simple signature aggregation scheme that satisfies all the attributes in the previous section.

·Multi-signature demo

We will demonstrate an interactive multi-signature scheme here, with each signer signing the same message. The plan works as follows: 1. As mentioned earlier, each signer has a public-private key pair. 2. Each signer shares a commitment to their public random number (skip this step in this demo), which is necessary to prevent certain types of malicious key attacks [10]. 3. Each signer publishes their random number, Ri's public key. 4. Everyone calculates the same “shared public key”, X is as follows:

Note that in the above public key ordering, certain established rules should be followed, such as serializing keys in lexicographic order. 1. Each person also calculates the shared random number, R = ∑Ri. 2. Problem, e is H(R||X||m). 3. Each signer needs to contribute to the signature:

Note that the only starting point for a standard Schnorr signature is to include the factor ai.

The aggregated total signature is generally the sum, s=∑si.

Verify verification by: sG=R+eX

prove:

Let us demonstrate with a triple signature:

 

·Security demonstration

As a final demonstration, let's show how multiple signatures can defend against attack attacks from the naïve signature scheme. In the same way as the key elimination attack, Bob provides false values ​​in his random number and public key:

This led Alice and Bob to perform the following calculations together:

Bob then builds a one-sided signature after multiple signatures:

We now assume that ks does not need to be Bob's private key, but he can use his known information to derive that to make it a valid signature, R+eX must be verified, so:

In the previous attack, Bob obtained the right information of all the equations needed from similar calculations. In the multi-signature, Bob must know Alice's private key and forged private key in some way (these terms are no longer canceled) In order to create a one-sided signature, his elimination attack failed.

 

·Replay attack

It is important to choose a new random number for each signing ceremony. The best way is to use the Secure Security (Pseudo) Random Number Generator (CSPRNG).

But even in this case, the attacker can trick us into signing a new message by "rewinding" the signing ceremony to the point in time when the partial signature is generated. At this point, the attacker provides a different message, e'=H(. ..||m') to sign without any doubt, each party will calculate their partial signature again:

The attacker can still access the first set of signatures, simply by doing the subtraction:

All the messages on the right side of the final equation are taken by the attacker, so he can easily extract everyone's private key, which is difficult to defend. One way is to increase the difficulty of terminating and restarting the signing ceremony. If the multi-signature ceremony is interrupted, then you need to start again from the first step, which is quite ergonomic, and it may be the most current before a more powerful solution emerges. Good solution!

Reference materials:

[1] "RSA (Cryptosystem)" [OL]. https://en.wikipedia.org/wiki/RSA_ (cryptosystem). Access date: 2018-10-11. [2] "Elliptic curve digital signature algorithm", Wikipedia [OL]. https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm. Access Date: 2018-10-11. [3] "BOLT#8: Encryption and Authentication Transmission, Lightning RFC", Github [OL] .https://github.com/lightningnetwork/lightning-rfc/blob/master/08-transport.md. Visit Date: 2018-10-11. [4] "Middleman Attack", Wikipedia [OL].https: //en.wikipedia.org/wiki/Man-in-the-middle_attack. Visit Date: 2018-10-11. [5] "How does the cryptographically secure random number generator work?" StackOverflow"[OL]. https:/ /stackoverflow.com/questions/2449594/how-does-a-cryptographically-secure-random-number-generator-work. Visit Date: 2018-10-11. [6] "Cryptographic Security Pseudo Random Number Generator", Wikipedia [OL]. https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator. Access Date: 2018-10-11. [7] "Schnorr Signature", Wikipedia [OL] ] https://en.wikipedia.org/wiki/Schnorr_signature. Visit Date: 2018-09-19. [8] "Schnorr Signed Key Aggregation", Blockstream [OL]. https://blockstream.com/ 2018/01/23/musig-key-aggregation-schnorr-signatures.html_. Date: 2018-09-19. [9] Gregory Maxwell, Andrew Poelstra, Yannick Seurin and Pieter Wuille, "Simple Schnorr Multi-Signature Application Bits Currency"[OL].https://eprint.iacr.org/2018/068.pdf. Visit Date: 2018-09-19. [10] Manu Drijvers, Kasra Edalatnejad, Bryan Ford, Eike Kiltz, Julian Loss, Gregory Neven and Igors Stepanovs, “On the Security of Two-Way Multi-Signatures”, Cryptographic ePrint Archives, Report 2018/417 [OL]. https://eprint.iacr.org/2018/417.pdf. Access Date: 2019- 02-21.

Contributors:

· CjS77 · SWvHeerden · Hansieodendaal · neonknight64 · anselld

This article Source: First Class Warehouse is an information and information service company specializing in information collection, project analysis and project progress tracking of blockchain projects at home and abroad. It provides blockchain investors' due diligence for domestic and foreign blockchain investors. Analysis services.

Original source: https://tlu.tarilabs.com/cryptography/digital_signatures/introduction_schnorr_signatures.html

For reprint, please indicate the source.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!