# Basics of Cryptography

In this chapter we will look at the cryptography basics and its use in blockchain. From the previous chapters you are aware that the blockchain is a trustless distributed system. There is no single party that ensures security. In such an environment it becomes critical that the communication between the nodes ensures the right identity. Two important concepts that are used in blockchain are

1\) Cryptographic Hash function

2\) Asymmetric Cryptography

<br>

**Cryptographic Hash function**

&#x20;A hash function is a mathematical function that converts a numerical input value into another compressed numerical value. The input to the hash function is of arbitrary length but output is always of fixed length.&#x20;

<br>

<figure><img src="https://3601662095-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjEiWbDLtVOiXJWwYTIn2%2Fuploads%2FfcRM5f6RErmJbaHjaDPm%2Fimage.png?alt=media&#x26;token=2ac8d96b-b1a6-4eeb-8841-d220b7aa4e32" alt=""><figcaption></figcaption></figure>

<br>

A hash function has following properties

1\) Computationally hard to reverse a hash function

2\) Given an input and its hash it should be hard to find different input with same value

3\) It should be hard to find two input functions of any length that map to same hash

<br>

The basic hash function takes 2 blocks of fixed size and then create a hash. Hashing algorithm takes this basic block and run in multiple rounds to get final value.&#x20;

<br>

<figure><img src="https://3601662095-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjEiWbDLtVOiXJWwYTIn2%2Fuploads%2FK7H6GZn179XG3vUU1cs8%2Fimage.png?alt=media&#x26;token=170782c7-fb5d-4700-9938-aa078102afba" alt=""><figcaption></figcaption></figure>

<br>

Since the first message becomes an input to second one and this continues until block N, this effect is known as avalanche effect

<br>

Message Digest (MD) and Secure Hash Functions (SHA) are popular hash functions. The main usage of Hash function in blockchain is data integrity. So along with the message the corresponding hash is also sent.  The recipient will take the received message re-hash it and then compare this computed hash with the received hash. If both match then the message can be trusted. This is not only useful for data integrity but also block integrity. If the hash of the block is saved along with the block then the blocks become immutable. This is because if someone tries to change the block then they will not be able to get the same hash as original one because of the properties of hash. The other advantage is that the hash always has fixed length.

The hashing is also used in proof of work. In PoW, miner uses partial hash inversions to prove that work was done. The average work that the miner needs to perform in order to find a valid message is exponential in the number of zero bits required in the hash value, while the other miners can verify the validity by executing a single hash function

<br>

**Asymmetric Cryptography**

Cryptography is needed in distributed systems mainly because of the trustless nature. Cryptography is a method of using advanced mathematical principles in storing and transmitting data in a particular form so that only those for whom it is intended can read and process it. Encryption is a key concept in cryptography — It is a process whereby a message is encoded in a format that cannot be read or understood by an eavesdropper. The technique is old and was first used by Caesar to encrypt his messages using Caesar cipher. A plain text from a user can be encrypted to a cipher text, then send through a communication channel and no eavesdropper can interfere with the plain text. When it reaches the receiver end, the cipher text is decrypted to the original plain text.

In symmetric cryptography a single key is used to encrypt and decrypt the message. The sender and receiver share this key and keep it a secret. However in blockchain there are multiple distributed nodes and hence it becomes impossible to use the symmetric cryptography.&#x20;

Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of [keys](https://en.wikipedia.org/wiki/Cryptographic_key). Each pair consists of a public key (which may be known to others) and a private key (which may not be known by anyone except the owner). The generation of such key pairs depends on [cryptographic](https://en.wikipedia.org/wiki/Cryptographic) [algorithms](https://en.wikipedia.org/wiki/Algorithms) which are based on [mathematical](https://en.wikipedia.org/wiki/Mathematical) problems termed [one-way functions](https://en.wikipedia.org/wiki/One-way_function).&#x20;

<br>

<figure><img src="https://3601662095-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjEiWbDLtVOiXJWwYTIn2%2Fuploads%2F9xOD0RNO9DAx6guzhoa3%2Fimage.png?alt=media&#x26;token=8b503638-6bb3-4268-bbd1-c00f83cf5979" alt=""><figcaption></figcaption></figure>

The main idea is to use a large random number and then use a key generation algorithm to get the public and private key. Now lets look at how this is used.<br>

<br>

<figure><img src="https://3601662095-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjEiWbDLtVOiXJWwYTIn2%2Fuploads%2FgvHjbjxaCIFcTFOsAeVm%2Fimage.png?alt=media&#x26;token=38d4dbbd-cbd0-483f-8114-8ef3fd174dab" alt=""><figcaption></figcaption></figure>

<br>

The first scheme of things, message is encrypted using Alice’s public key and this can be decrypted only by Alice with her private key. This is known as public key encryption. Here the main concern is the secrecy of the message itself. Another scheme is Different-Hellman Key exchange.

<br>

<br>

<figure><img src="https://3601662095-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjEiWbDLtVOiXJWwYTIn2%2Fuploads%2F4EvLfFKOMRqCeQOWNwFK%2Fimage.png?alt=media&#x26;token=bf13bef2-2aa0-4d18-ae57-c87b2a2650d0" alt=""><figcaption></figcaption></figure>

<br>

In this case a shared secret is created using public key of one participant and private key of another. This essentially creates a shared secret which can be decrypted. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a [shared secret](https://en.wikipedia.org/wiki/Shared_secret) key over an [insecure channel](https://en.wikipedia.org/wiki/Insecure_channel).

The other important concept is digital signatures. So in the first case we encrypted the message but how to know that in fact the message was send by the correct sender? message is signed with the sender's private key and can be verified by anyone who has access to the sender's public key. This verification proves that the sender had access to the private key, and therefore is very likely to be the person associated with the public key. This also ensures that the message has not been tampered with, as a signature is mathematically bound to the message it originally was made from, and verification will fail for practically any other message, no matter how similar to the original message.&#x20;

<br>

<figure><img src="https://3601662095-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjEiWbDLtVOiXJWwYTIn2%2Fuploads%2FvUSeEYxjSvHcTf92akbN%2Fimage.png?alt=media&#x26;token=2555b309-8221-42f6-b192-04150a816766" alt=""><figcaption></figcaption></figure>

<br>

We talked about generation of keys using a large random number. But which one is suitable for this? The answer is elliptic curve multiplication.

Elliptic curve multiplication is a type of function that cryptographers call a "one-way" function: it is easy to do in one direction (multiplication) and impossible to do in the reverse direction ("division", or finding the discrete logarithm). The owner of the private key can easily create the public key and then share it with the world knowing that no one can reverse the function and calculate the private key from the public key.

Bitcoin uses a specific elliptic curve and set of mathematical constants, as defined in a standard called secp256k1, established by the National Institute of Standards and Technology (NIST). The first and most important step in generating keys is to find a secure source of entropy, or randomness. Creating a bitcoin key is essentially the same as "Pick a number between 1 and 2256." The exact method you use to pick that number does not matter as long as it is not predictable or repeatable. For Cardano ED25519 curve using elliptic curve cryptography is used

Starting with a private key in the form of a randomly generated number *k*, we multiply it by a predetermined point on the curve called the *generator point* *G* to produce another point somewhere else on the curve, which is the corresponding public key *K*. The generator point is specified as part of the secp256k1 standard

K = k \* G

where *k* is the private key, *G* is the generator point, and *K* is the resulting public key, a point on the curve

A private key can be converted into a public key, but a public key cannot be converted back into a private key because the math only works one way.

<br>

<figure><img src="https://3601662095-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjEiWbDLtVOiXJWwYTIn2%2Fuploads%2FSIApPfLkLe2xC6CluvFY%2Fimage.png?alt=media&#x26;token=28406b84-c009-4b18-9bd7-5c0042f584cc" alt=""><figcaption></figcaption></figure>

<br>

To visualize multiplication of a point with an integer, we will use the simpler elliptic curve over real numbers—remember, the math is the same. Our goal is to find the multiple *kG* of the generator point *G*, which is the same as adding *G* to itself, *k* times in a row. In elliptic curves, adding a point to itself is the equivalent of drawing a tangent line on the point and finding where it intersects the curve again, then reflecting that point on the x-axis.

So this forms the basis of wallets and transactions in blockchains. The public private keys forms the basis for the address used in blockchains. The sender will use digital signature to help nodes to validate that the owner of the wallet. If we take Cardano’s example : if Alice wants to send Ada to Bob

1\) Alice creates a transaction with Bob’s public key based address and Ada to be transferred&#x20;

2\) Transaction hash is then created

3\) Alice then uses the private key to sign this hash

4\) This signature and the original transaction is sent.

5\) Bob verifies the received message by first verifying the signature to get the hash and calculates the hash of received message. This way Bob is able to identify the identity and also uncorrupted message from Alice

**CIP49 ECDSA and Schnorr signatures in Plutus Core**

Signature schemes based on the SECP256k1 curve are common in the blockchain industry; a notable user of these is Bitcoin. Supporting signature schemes which are used in other parts of the industry provides an interoperability benefit: we can verify signatures produced by other systems as they are today, without requiring other people to produce signatures specifically for us. This not only provides us with improved interoperability with systems based on Bitcoin, but also compatibility with other interoperability systems, such as Wanchain and Renbridge, which use SECP256k1 signatures for verification. Lastly, if we can verify Schnorr signatures, we can also verify Schnorr-compatible multi or threshold signatures, such as [MuSig2](https://eprint.iacr.org/2020/1261.pdf) or [Frost](https://eprint.iacr.org/2020/852).

CIP 49 adds

* A verification function for ECDSA signatures using the SECP256k1 curve; and
* A verification function for Schnorr signatures using the SECP256k1 curve.

Both functions take parameters of a specific part of the signature scheme

1. A verification key;
2. An input to verify (either the message itself, or a hash);
3. A signature.

Details at <https://github.com/cardano-foundation/CIPs/pull/250/files?short_path=e9938ef#diff-e9938ef08da10d143f6460f6e0bbb82e7c0d7414dd724ff106437f506f782761>

{% embed url="<https://youtu.be/q66kJzjM3To>" %}

{% embed url="<https://youtu.be/QoKN5CdVwOU>" %}
