Hello and welcome to this fundamentals of cryptography.
Course, the previous couple of videos we've been talking about, public key encryption algorithms,
talking about how they work and some of the mathematically hard problems that they rely upon for security.
In this video, we're going to talk about two common asymmetric encryption algorithms and how they work
and a little bit more detailed them, the high level discussion we've had so far.
And so in this video, we're going to be looking at Rivette, Shamir, Adleman, more commonly known
as RSA and the Diffie Helmund Key Exchange algorithm.
Both of these use public key cryptography, but they're used for very different purposes.
And so we'll start out with Rivette, Jamir Adleman or RSA.
So RSA was created by a team of cryptographers, as you might have guessed from the name included Rúnar
Best, Adi Shamir and Leonhard Adelman in 1977.
However, they weren't actually the first ones to discover it in previously.
Clifford Cox of G.S. HQ.
British intelligence had discovered the algorithm that is now known as RSA.
However, it was currently classified and so it wasn't declassified until well after RSA was created,
published and publicized by Rivette, Shamir and Adelman.
As a result, it bears their name, even though Clifford Cox got to it first.
And so we talked in the previous video of about a couple of mathematically hard problems.
The security of RSA relies on the hardness of the factoring problem.
And so this means that when Shor's algorithm comes into play with quantum computing, RSA will be trivial
to break.
And now let's take a look at the right side of the screen at an example of how RSA algorithm works.
And so on the far left of this image, we have the message.
Hello.
And in this case, rather than trying to encode the entire message in ASCII as a binary string, we're
simply assuming that hallo maps to a certain value, like two.
So maybe you have a dictionary of possible messages.
And the second option is hello.
And so if you send a number two, it means you're saying hello.
What we're going to do with that message is use it in a discrete logarithm exponent or discrete exponentiation.
So we take that value to and raise it to the power of the user's public key.
We're also going to be using a publicly shared value for the modulus.
Remember, in the first video in this series, we talked about how some asymmetric encryption algorithms
used additional public values and beyond the public key.
This is an example of one of them.
And so everyone in the environment, the sender of the message, the recipient, anyone eavesdropping
on their communications, knows that the modules we're using is a 14.
And so if you calculate to the fifth power divided by 14 and take the remainder, you're going to get
the number four.
And so this four is our ciphertext in this example.
And so that four is sent over a public channel to the recipient.
The owner of the private and public key pair.
And the assumption here is that anyone can view this number.
Anyone can intercept it.
But you need certain information to go from four.
Back to our original message of two.
And how you do this is by performing the exact same operation as encryption, but using the private
key instead of the public key you calculate for to the 11th power and take the result Mod 14 and the
number you'll get is two.
We use our handy dictionary mapping numbers to messages.
We'll see that the person sending the message says hello.
And so this is a very simplified example of how the RSA encryption algorithm works.
Nothing's wrong about this except for the size of the numbers that we're using.
So we talked about in the previous video, key length is really important for the security of asymmetric
cryptography.
And so using a public private key pair of five and 14 with a mock sorry, five and eleven with a modulus
of 14 makes it pretty easy for an attacker to search through the possible space of public keys and private
keys and find the right one.
And so insecure example of a secure protocol.
The other example we're going to look at here is Diffee Helmund Key Exchange.
So Diffie Helmund was created by Whitfield Diffie and Martin Hellman and Knight and by Martin Hellman
in nineteen seventy six.
Previously, Robert Merkel had conceived the idea of public key protocols.
So actually there's some push from the creators, the algorithm to call it Diffee Helmund Merkel.
However, once again, they didn't get their first James H.
Ellis Clifford Cox and Malcolm J.
Williamson of GC HQ had previously demonstrated that protocols like this were possible back in 1969,
beating Diffie and Hellman by seven years.
However, once again, classification process meant that the this information was held as secret until
after the algorithm was publicized and created by Diffie and Hellman and took their name.
And so, unlike RSA, the security of Diffie Hellman is based off of the discreet logarithm problem.
And so let's take a look at the image on the right here and how this algorithm works.
So we have Allison, Bob, and in this case, Allison, Bob, both have their own private key.
And the reason for this is that Alice and Bob want to agree on a shared secret key over a public channel.
And so what they do is they take two public values, PMG.
This is similar to the modulus that we used previously.
And they calculate G to be a mod P and Alliss case or G to the B mod P in Bob's case.
So they raise our generator G to the power of their private key and then apply the modulus P.
The result there is then sent over the public channel to one another.
So Alice sends the value capital A to Bob and Bob sends the value capital B to Alice.
Each of them then performs the exact same operation again.
Except so they'll take the value they received, raise it to the power of their private key once again,
and then apply mod P.
And the reason why this works and why they end up with a shared secret is that if you, for example,
take X to the power, Y to the power Z, what you're calculating is X up to the power Y times Z.
Similarly, if you take X too busy to the Y, you're calculating X to the Z times, Y and X to the Y
times Z and X to the Z times Y are the same thing.
And so even applying a modulus, the order of the operations that you're performing doesn't matter whether
you go G to be A to B or G to the B to the A mod P, you still end up with our shared secret.
S However, Charlie, our eavesdropper here, doesn't have the information that he needs to break the
system.
What he has access to is PMG and he knows at Capital A. and capital B.
And so because of the discrete log problem, he can't take, for example, Capital A. and his knowledge
of GMP and derive Alice's private key a lower case.
Similarly, he can't use his knowledge of G and Capital B to learn Bob's public key or private key.
However, given capital A, capital B, he doesn't have any way to get to S.
There's no mathematical operation where you can combine G to be a mod P and G to the B Mod P and produce
G to the eight times B mod P without knowledge of A and B..
So in the end, Alice and Bob end up with a shared secret.
And Charlie is stuck without being able to derive that secret.
And so this is an example of a key exchange protocol and protocols like this are in common use today.
And so as a quick recap, this video we were just talking about, two of the more well-known asymmetric
encryption algorithms.
We looked at RSA, which bases its security off of the factoring problem, and Diffie helming key exchange,
which uses the discrete log problem for its security.
Both of these have particular applications.
RSA is for providing confidentiality while Diffie Hellman is using key exchange.
But they have the same philosophy under the hood using that mathematically hard problem and related
private and public keys to achieve their goal.
Thank you.