Lesson 1, Topic 1
In Progress

Introduction to Public Key Encryption

digitalscotland July 13, 2021
Lesson Progress
0% Complete

In this video, Professor Bill Buchanan talks about one of the most popular algorithms, ‘Public Key Encryption.

The foundations of public-key encryption were laid in a famous classic paper by Diffie and Hellman on a key exchange method.

Bill states the proposal that was made in the paper. It was proposed that a trapdoor method could be set up which will allow us to create a function where if the secret is known, information can be revealed.

He adds that in the year 1977, Shamir and Adleman came up with the RSA (Rivest, Shamir, Adleman) method which is still commonly used by many people.

At 1:02, Bill begins to talk about the main methods that are available for public-key encryption. If the secret is unknown, it would be impossible to solve the problem in a reasonable amount of time. It becomes very expensive to solve in cases where the secret is unknown. With secrets, it becomes fairly easy to solve the puzzle.

Methods involved in the encryption process

Bill adds that with public-key encryption, we will be having a key pair, one of which will be a private key while the other would be a public key. Bob and Alice can have their own key pairs. Everyone can know Bob’s public key but he keeps his private key secret. At 3:00, Bill mentions the three main puzzles that need to be solved.

They are integer factorization, discrete logs, and elliptic curve methods. The discrete log method is hardly used as it is quite difficult to compute. He mentions that the underlying difficulty with the integer factorization is to find two prime numbers that created a given modulus.

At 6:02, Bill describes that the elliptic curve methods use a curve that looks like y^2 = x^3 +a + b (mod p). This would give us much better performance compared to the integer factorization method or the discrete logs method.

He then talks about the three major things that can be done with public-key encryption. First is where we can encrypt data through public and private key pairs. However, the downside of this is that due to the maths and the complexity of the methods involved in this process, computing large amounts of data would be extremely difficult.

At 10:16 Bill states that it is not recommended to use this method to encrypt large amounts of data. In cases where a large amount of data needs to be encrypted, a symmetric key is used.

We can share a secret key that can be used. Encrypting using the symmetric key method is also commonly referred to as the key exchange. The third usage is in the proof of identity. Here, identity can be processed by signing his private key. In the third usage, encryption is done with hash.

Digital certificate and the working of RSA algorithm

At 14:17, Bill talks about the ‘Digital Certificate’. A digital certificate is one that has been signed by a trusted entity but contains the keys that would require private and public keys. This is a secret digital certificate and is only used when there is a need to sign for something. He adds that typically the certificate would be exported into a form that contained only the public key and this will be in a distributable form.

At 17:00, he begins to explain the RSA method. In the RSA method, we start off with two prime numbers p and q and we create a modulus from that. Modulus is defined as n which is p times q.

The difficulty lies in finding p and q if they are large. These might be a thousand-bit prime number. Next, encryption keys should be found. RSA is an exponential cipher. Here, a message is taken and raised to the power of an encryption key. Then take the modulus of n for the cipher. In order to get the message back, we will need to take the cipher to the power of d and mod N. Modulus N is the remainder of the division by n. The values of e and d need to be found.

We will then need to select a value of e that does not share any factors with PHI. We would often write the GCD of PHI and e equals as 1. The calculation of d is an inverse of e mod n. This will be a standard calculation that is often done in public-key encryption.In this video, the speaker talks about public-key encryption, its usages, the different methods involved in the encryption process.

Bill also talks about digital certificates and how encryption methods can be used to protect data from malicious threats.