Introduction

Greetings! At Symbiosis, we come across the fact that in the world of cryptocurrencies, where lots of cryptographic primitives and tools are heavily used, there is a limited number of really tech-savvy people who understand the underlying principles of how it’s all working. Others either understand very vaguely or simply do not know about the existence of such tools.And so here we start a series of articles where we’re making an endeavor to explain those concepts in a friendly manner.

We begin with one of the main mechanisms used in our protocol: MPC (Multi-party Computation). MPC allows a group of parties to create a digital signature in such a way that none of the parties have access to the secret needed to create the signature. Only a quorum (a part of parties) participates in signing.

In the case of MPC, the parties create a signature off-chain that makes it possible to sign any data, including transactions. For the protocol, such a signature is indistinguishable from a signature created by a single user.The MPC is a very young mechanism by the standards of cryptography. However, it is based on cryptographic algorithms that have been tested for decades.In a series of articles, we will explain how MPC works. We will talk about what a digital signature is, how to share private keys between parties, and how to sign data without having an entire private key in one place.

In the first article, we’ll start with the basics: a digital signature.

Digital Signature Standard Scheme

What problems does a common signature or a digital signature solve? Historically, there are two problems:

Signer authenticity: to ensure that the message is signed by exactly that person who introduced themselves as the signer.Document integrity: to ensure that the message has not changed since the signature was created.

And historically, every time you sign, you draw the same symbol: your common signature. The security of such a system is based on the fact that no one but you can reproduce this symbol in the right way.

Consequently, one just has to look at the signature to ensure its veracity. Thus, the signed document contains the following information: the document itself, the public identifier of the signer (usually it’s a name), and the signature itself. There are weak points of the common signature. The signature looks always the same, and it doesn’t change whatever you sign with it. Additionally, anyone who has a signature sample can reproduce the signature.So, the common signature does not solve the problems perfectly. The digital signature is a way to solve problems using modern computing technology.

A different approach is used in the case of digital signatures. The message, the signature, and the public identifier of the signer are numbers¹ linked by a mathematical formula². The formula allows to unambiguously establish that for the given message, only the one who possesses the given public identifier created the given signature. And there is no other way. Please note that a digital signature changes depending on the message signed with it.

We should have one more number to have the mathematical formula mentioned above working. Only the one who creates the signature knows this number. This secret number allows the owner to create a digital signature that guarantees the connection between the message and the signer’s public identifier. Public-Key Cryptography (or sometimes called Asymmetric Cryptography) studies such mathematical primitives.Thus, when you create a digital signature, two positive numbers are associated with you as the signer. One is called the private key*** (or secret key), and the other is called the public key. There is a one-way bond between these numbers: you can derive the public key from the private key using a mathematical formula, but never vice versa.The public key is a semblance of your name in a document signed with a common signature. This information about you is publicly known. On the other hand, only you should know the private key.A private key is used to create a digital signature, so the digital signature shows the signer’s authenticity. In its turn, the authentication is based on whether or not the correct private key was used. For authentication, one should have the signer’s public key, the signed message, the signature, and the formula binding the signed message and the private key.Thus, a digital signature routing consists of three parts:

The KeyGen algorithm is used to create a pair of numbers: a public key and a private key; the Sig algorithm is used to create a signature, using a message and the private key; and the Ver algorithm is used to verify the signature using the signature, the signed message, and the public key.

Next, we will look at all three parts in detail.

Key Generation With the KeyGen Algorithm

The key generation algorithm creates a pair of keys sk, pk=KeyGen( ). where sk stands for the private key (secret key), and pk stands for the public key. Whenever you use the algorithm, you get a new pair of keys.

A private key is just a random number. A public key can be easily obtained by applying a pre-defined one-way compression function to the private key. The one-way compression function does not allow recovery of the input parameters by output results. So, we can safely share our public key without risking compromising our private key.

Modular exponentiation is a classic example of a one-way transformation. Common exponentiation pk=askis reversible (a is a fixed number). If we know pk and a, we can derive that sk=loga pk. Figure 1 illustrates this one-to-one correspondence: each value of sk corresponds to a single value of pk and vice versa.You will get a one-way transformation if you expand exponentiation with a modulo operation. The resulting algorithm would be pk=ask mod q, where q is a positive integer number. Modulo (denoted by mod in the formula above) is an operation that returns the remainder when divided by q. For example, 25 mod 10=5. This operation is irreversible, which is illustrated by Figure 2.Let us consider an example where pk=4, a=2, q=7. If we try to solve the equation 4=2sk mod 7 we will realize that it has multiple solutions. sk can be equal to 2, because 22=4, 4 mod 7=4. But it also can be equal to 5, because 25=32 32 mod 7=(28+4) mod 7=(47+4) mod 7=4 (Figure 2).Another example is a clock face. We measure hours by modulo 12, and seconds by modulo 60. Imagine someone saying, “when I looked at my clock, it was 1 PM, and the next time it was 3 PM”. Can you derive how much time exactly passed between these two events? It could be two hours, 14 hours (2+12=14), 26 hours (14+12=26), or infinitely more. Operation mod 12 erases this information.Modulo operation is the simplest computational operation that effectively screens the initial parameters. It is widely used in all common one-way transformations combined with other functions. In the example above, we combined it with a power function. We will get more complicated and interesting examples when covering the ECDSA algorithm.

Signature Generation With Sig Algorithm

The signature generation requires two components: the private key sk and the message we want to sign. The message can be of arbitrary length, and this might be inconvenient. Cryptographic hash functions can help us with this.A cryptographic hash function transforms a sequence of symbols into a number within some range. For example, it can be a number that can be encoded with only 256 bits. This number is called a hash, and the transformation process is called hashing. The hash function always returns the same output for the same input sequence. However, the slightest change in the message changes its hash so much that it becomes impossible to associate changes in the message with changes in the hash. The usage of hash functions not only simplifies the process but also guarantees the integrity of the signed message that the message has not been changed since the signature creation.For example, the cryptographic hash function sha256 returns numbers in the range from 0 to 2256–1.

For the input string, “I promise to give you $5,000”, sha256 will return be657fcad7933b87869835c571b60ff1444f68179326e7754c3d99babf919995 (this is a number in hex format). If we add an extra 0 to the message like this: “I promise to give you $50,000”, the hash will change to 90222db12a4a59f8d083e3cf88bf22dab15385c9946f4526a67855e6a5ff0737.

To sum it up: the signature creation algorithm takes a private key sk and a number m (the message hash) for input and returns a number s. This number is a signature s=Sigsk, m. In the following chapters, we will continue covering the details of the cornerstone of cryptocurrencies — the ECDSA signature algorithm.

Signature Verification with Ver Algorithm

Algorithms KeyGen and Sig generate digital signatures. Algorithm Ver is used for signature validation.

This algorithm requires the public key pk of the signer, the message hash m that was signed, and the signature s.

The Ver algorithm returns 1 (TRUE) if the signature is correct and 0 (FALSE) otherwise.

Successful verification can guarantee thatThe public key pk matches the private key sk used for the signature generation. This means that the person claiming to be the signer is the actual signer of the transaction.The message that was signed (the hash) was not changed.Correspondingly, failed signature verification means that at least one of the following two facts comes true:The private key sk does not match the public key pk. Someone is impersonating the message signer.The message does not match. The signer did not sign this exact message.

There is no way to figure out what exactly is invalidating the signature with the Ver algorithm.

The algorithm does not determine which of these conditions caused the invalidity of the signature.

In our next article, we will talk about the algorithm ECDSA and elliptic curves.

Authors:

• Alexey Troshichev — Main concept
• Artem Fomichev — Mathematician 
• Inga Pashentseva — Editor
• Alexander Polovian — Fact Checking

— — — — — — — — — — — — — — — -
[1],[2]: we will explore these concepts further in our publications.

Catch up with us on social media |  |  |  |  |