Authentication Problem
How to Encrypt a Document with Asymmetric Keys?
| Using RSA algorithm, I will create private and public key. I will call them PrivEncryptKey and PubEncryptKey. |  | I will personaly deliver my PubEncryptKey to my coworker. She will use RSA algorithm and PubEncryptKey to encrypt the document. |  She will be able to send me encrypted document. |
The only person who can decrypt this document is the one with the PrivEncryptKey. If I receive this document, I will be able to decrypt it.
| This solved the privacy problem, but what about authentication? When I receive an encrypted document, I want to know who is the person who sent me that document. |  |
How my Coworker Can Prove Her Identity?
In this case, the document will not be encrypted, but I will know that this document was signed by Anna.
| My colleague will create hash of the document using SHA algorithm. SHA algorithm is not using any keys. |  | Our goal is to somehow bind that hash with the identity of the person sending the document. 'bk8q' + "Anna" |
| My coworker will create another pair of keys. I will call them PrivIdentKey and PubIdentKey. | Anna now has two keys. She will personally give me her PubIdentKey. I will use this key to validate her identity. | PrivIdentKey will be used to encrypt the certificate. |
| Anna will use PrivIdentKey to encrypt "hash+identity". She is using RSA algorithm. This process is called signing. The result of encryption is a signature. |  | She will now send me 2 things: the document, and the signature. |
| I already have Annas PubIdentKey. I will use that key to decrypt her signature. This will give me document hash and her identity. | | I will now calculate the hash of the document using the same SHA algorithm. If that result is the same as the hash from the signature, that will tell me that this document was sent by Anna. |  |
Two-side Communication, Encrypted and Authenticated
To achieve both Encryption and Authentication we need two pairs of keys. One pair belongs to receiver and is used for encryption ( PrivEncrypKey, PubEncryptKey ). The other pair belongs to sender and is used for authentication ( PrivIdentKey , PubIdentKey ). This is enough for one-side communication. In the real world, for two side-communication 4 pairs of keys are used. Having separate pair of keys for each function, makes key management much easier.
You can notice that there is no real need for 4 pair of keys. Two pairs would do the job, because Encryption keys can also be used for Authentication.
What is Wrong with the Simple Example?
There is a problem with this simple example that will occur when the other person is far away. We cannot deliver our public keys in person. If we send those keys by email, that defeats the purpose. Then the communication will be insecure again, the other person will have no guarantee that the public key is authentic. To solve this problem, we need Certification Authority. A CA is a "mutual friend" who is trusted by both parties.
Certification Authority ( CA )
A certification authority is an organization that is large, reputable, and trustworthy. It can be a government, a private company, or the organization we work for. The certification authority will sign our public keys, thus proving their authenticity.
| CA has its own private and public key. |  | We will create a certificate that contains the hash of the person's public key and their identity information. | Certification is the same as signing. Only instead of signing a document, we sign a certificate. Signature contains a document, but certificate contains public key. |
 | The CA will use its private key to sign the certificate. It will also securely deliver its public key to the remote person safely. The public key validation process is now a two-step process (or more, if multiple certificate authorities are connected): – First, use the CA's public key to verify the person's certificate. – Use the public key, which was contained within the certificate, for encryption/authentication.  |
| CA, together with their clients makes PKI. PKI is "Public Key Infrastructure". | PKI includes software, hardware, policies, and everything else that is needed to manage digital certificates. |
Symmetric Keys vs Asymmetric Keys
We can't use symmetric keys for authentication, but this is not the biggest drawback. The biggest drawback of symmetric keys is their scalability. If we have 100 people who need to communicate securely, and any two of them need to have their own unique key pair, then the number of keys needed is astronomical.
If we were to use the same key for 100 people, then the probability that the key will be compromised is high. Asymmetric keys scale much better. Each person needs to have their own key pair, and that is enough for communication between any two people.
But, on the other side, there are two important advantages of the symmetric keys.
1) Encryption and Decryption with symmetric keys is much faster.
2) Encrypted files have the same size as unencrypted files. This is not true for asymmetric cryptography where encryption enlarge the file size.
Hybrid Cryptography
The solution to "Symmetric vs Asymmetric" conflict is to combine Symmetric and Asymmetric cryptography:
| 1) Use symmetric encryption when you want to share a lot of data, especially if you have a secure way to share symmetric key between people. |
| 2) Use asymmetric encryption for sending small but highly sensitive pieces of data. You can see that these two methods complement each other. |
This is especially true when dealing with servers. Servers are made to provide huge quantities of data. This is how secure client-server communication works:
| Server uses asymmetric cryptography for initial exchange of the symmetric keys. After that, data is exchanged using more efficient symmetric cryptography. This combination is called "hybrid encryption". The process is like this: |  |
| 1. Client asks Server for its certificate. 2. Server sends the Client the signed certificate. 3. Client use CA public key to check that certificate. 4. Client creates random symmetric key. | 5. Client encrypts that key using the server public key. 6. Client sends that encrypted symmetric key to server. 7. Both sides now have the same key and they continue communicating by using symmetric cryptography. |
How Does the Client Check Server Certificate?
| Inside the server certificate we have a lot of different information. Client will compare them: – Is IP/domain of the server the same as in the certificate. – Is certificate valid. Certificate is valid only between the dates written inside of the certificate. – Is certificate prematurely revoked. Revoked certificates are listed in online registries. The client must check online if our certificate is revoked. | Owner: db.company.localSerial number: 883 |
If we download some documents from the server then another piece of information can be important:
| Identity information is not just about cyber security. Identity is important for classification, organization, and storage of documents. So, it's nice to visibly tag documents with some identity information. Sometimes, the people are the one who will notice that something is wrong with the document. |  |
Key Exchange
Symmetric cryptography does not have a secure way to exchange keys between two parties. Asymmetric cryptography is great at this. We saw that the RSA algorithm can be used to exchange keys (the key is just another document). Today we have an even better algorithm for this purpose. The Diffie-Hellman algorithm is another asymmetric cryptographic algorithm that is based on a private and a public key. This algorithm is special because it allows users to decide on a shared symmetric key, without ever sending that key over the network. This is great because no network hacker can steal our symmetric key.
Diffie-Hellman Algorithm ( DF )
Prime Number "P" and Generator "G"
| First, we must choose one prime number. I will choose 23. When we divide random number X with this number 23, the reminder will be one of the numbers 0,1,2…20,21,22. | 0 <= MOD( X, 23 ) <= 22 |
Next, we need "Generator" number. This number can generate all of these numbers 1-22 ( zero is always excluded ). I will use number 5. Let's test:
5^1MOD23 | 5^2MOD23 | 5^3MOD23 | 5^4MOD23 | 5^5MOD23 | 5^6MOD23 | 5^7MOD23 | 5^8MOD23 | 5^9MOD23 | 5^10MOD23 | 5^11MOD23 |
5^12MOD23 | 5^13MOD23 | 5^14MOD23 | 5^15MOD23 | 5^16MOD23 | 5^17MOD23 | 5^18MOD23 | 5^19MOD23 | 5^20MOD23 | 5^21MOD23 | 5^22MOD23 |
We will get results 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22. We got each number 1-22 exactly once.
In production, we need huge numbers for "P" and "G". It is hard to find numbers that match requested criteria. That is why today we use modern version of DF algorithm that is called "Elliptic-curve Diffie-Hellman". This algorithm always uses the same predefined numbers for "P" and "G".
Numbers "P" and "G" are public numbers. We don't have to hide them. Both parties know what are those numbers, and both parties are using the same pair of these numbers.
Private Numbers
The next step is that each party must choose their private key. That should be a number between 1 and ( P – 2 ). I will choose numbers 4 and 7, both of those numbers are less then 21 ( 23 -2 ). Parties must keep these numbers hidden.
Public Numbers
Each party will now independently calculate their public numbers using the formula "G ^ Private MOD P".
Party A: 5 ^ 4 MOD 23 = 4 | Party B: 5 ^ 7 MOD 23 = 17 Parties will exchange their public numbers. Only private numbers are hidden, everything else is shared => |  |
Calculating Symmetric Key
| Each party will now calculate the same symmetric key. For calculation they need their private key, public key of the opposite party, and "P". | Party A: ( Public B ^ Private A ) MOD P | Party B: ( Public A ^ Private B ) MOD P |
| Let's confirm that shared keys will be the same. | ( 17 ^ 4 ) MOD 23 = 8 | ( 4 ^ 7 ) MOD P = 8 |