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 coworker. |  | She will use RSA algorithm and PubEncryptKey to encrypt the document.  |
She will email me this 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 with certainty who is the person who sent me the document. |  |
How my Coworker Can Prove Her Identity?
In this case, we won't be doing any encryption. This time, we're looking for a way to authenticate Anna when she sends the document.
| My colleague will create hash code of the document using SHA algorithm. |  | Our goal is to somehow bind that hash code with the identity of the person sending the document. '8a12' + "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. |  | Anna will use PrivIdentKey to encrypt "hash+identity". She is using RSA algorithm. The result of encryption is a signature. Anna signed document hash code.  |
| 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 code and her identity. |  |
| We now know that Anna signed the hash code. The last step is to prove that the document Anna have sent to me, is connected to that hash code. | I will now calculate the hash code of the document using the same SHA algorithm. If that result is the same as the hash code from the signature, that will tell me that this document was sent by Anna. |  |
Visible Sign on a Document
| 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. |  |
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, but just like I said, it is easer if we have a separate pair of keys for each function.
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 key, thus proving its authenticity.
| Each key, including PubEncryptKey, is one big hexadecimal number. That is why we can treat PubEncryptKey as a file. |  | Inside of that file we will add identity data. We want to bind public key of a person with his identity data. |  | We can now calculate a hash code that includes the public key and identity data. |
| CA organization has its own private and public key. |  | CA will do the binding. CA will use its private key to encrypt hash code. That will give us a guarantee that the public key is genuine. |  |
 | Certification is the same as signing. Instead of some business document, this time we are signing combination of a person's public key and his identity information. |  | Public key, identity and signature together make a Certificate. |  |
 | The CA will use its private key to make the certificate. It will also securely deliver its own public key to the remote person safely. The validation process is now a two-step process: – 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, standards, professional associations 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 already 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, so they really need this hybrid cryptography. 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 |
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 23 = 8 |