## Key terms

**Hashing**: uses a mathematical algorithm that takes a string as input and outputs a universally unique hash

**Data Integrity**: data is not modified or corrupted

## Key idea

- A public key and private key’s function can be reversed: a public key can be used to decrypt a message encrypted by its corresponding private key.
- A hashing algorithm must in principle:
- produce a fixed-length output hash
- produce a completely different output even for the slightest change in the input
- be impossible to reverse (derive the input from the output hash)

## Digital signature

Because of the reversible nature of the public-private key pair, a private key can be used as a proof of identity. Only the sender owns the private key, so, if a message encrypted by the private key is successfully decrypted by the corresponding public key, that verifies the identity of the sender.

Note left of Sender: encrypt message\n with private key

Sender->Receiver: encrypted message

Note right of Receiver: decrypt message\n with public key

However it can take a long time to encrypt longer messages, so, a one-way hash function is used. The body of the message is taken as input by the hash function and it outputs a hash that can be encrypted much more quickly. The output is called a message **digest**. The message digest encrypted by a private key is called the **digital signature**.

Note left of Sender: hash message to produce digest

Note left of Sender: encrypt digest with private key\n to produce digital signature

Sender->Receiver: message

Sender->Receiver: digital signature

Note right of Receiver: hash message to produce digest

Note right of Receiver: use public key to decrypt\n digital signature

The receiver receives the **message** and the **encrypted digest**. Then, the receiver:

- runs the
**message**through the hash function and produce the message digest - decrypts the
**encrypted digest**with the public key to produce the message digest - compares the two message digests, if they are the same, it proves:
- the sender’s identity (otherwise, the public key would be able to decrypt the message)
- the message’s integrity after the transmission (otherwise, the digest produced by the receiver would not be the same as the digest encrypted by the sender)

## Digital Certificate

However, the receiver might not even have the public key of the real sender. Someone else might have claimed to be the real sender and given the receiver his/her own public key.

The **digital certificate** is designed for this very reason. A trusted Certification Authority or CA acts as the middle man between the sender and the receiver:

- It verifies the identify of the sender and takes his/her public key.
- It creates the digital certificate containing the sender’s public key.
- It encrypts the digital certificate with its private key

Now the senders can use the digital certificate as the proof of identity.