Hello and welcome to this fundamentals of cryptography.
Course, in the previous video, we introduced asymmetric or public key encryption algorithms in this
video.
We're going to be talking about hard problems in public, key cryptography.
For once, hard problems are actually a good thing.
In the case of asymmetric or public key cryptography, hard problems are what makes the system both
usable and secure.
In this video, we're going to talk about four main topics.
We're going to start out by discussing why we need these hard problems in asymmetric cryptography.
Then we're going to look at two of the hard problems we use in asymmetric cryptography, the factoring
problem and the discrete logarithm problem.
Finally, we'll look at the only bad problem in this video, talking about quantum computers and their
impact on the good hard problems we use otherwise.
And public key cryptography.
So why do we need hard problems?
We talked about in the previous video the private and public keys in asymmetric cryptography are related.
In fact, the public key is derived from the private key.
And so it's good to be able to easily derive your public key from your private key, however you want
that to be a one way function.
If you're able to reverse the mathematical operation that generates a public key from a private key,
you're able to derive a private key from a public key.
And since you're publicly sharing, your public key makes it a lot harder to keep her private, key,
private.
And so for asymmetric encryption to work, we need a mathematical operation that is asymmetric, meaning
that it's easy to perform in one way.
And very difficult to reverse.
And these are the mathematically, quote, quote, hard problems we're going to be talking about in
this video for public key cryptography.
So the first example of one of these hard problems is the factoring problem.
And so the premise of the factoring problem is that you have two very large prime numbers.
Legitimate users are going to multiply these prime numbers together.
And in order to break the crypto system, an attacker would have to take the product of these two prime
numbers and break them out into the original numbers using factoring.
And so in this example, factoring is an example of a mathematically hard problem, because multiplication
is relatively easy.
In fact, the difficulty of multiplication is related polynomial to the length of our two prime numbers
that we're using.
If you think about it, if you have two five digit numbers and you multiply them together, it's going
to take a certain amount of time and effort.
However, if you take those five digit numbers and you switch to six digit numbers and multiply.
It's only a little bit harder than five digit numbers.
It's not twice as hard or anything like that.
So there's a marginal cost in addition to what it took to do the five digit multiplication.
Factoring is a different story with factoring.
The difficulty is related exponentially to the lengths of the numbers used.
And the reason for this is that the best option for factoring the product of two primes is brute force
guessing.
You start at zero, you work your way up to the square root of their product, and you're guaranteed
to find one of the two factors in there somewhere.
However, it could take you a very long time and the length of time it takes you is dependent on the
length of the numbers used.
The larger the numbers, the larger the product, the larger that square root maximum value that you
have to check.
And when you're increasing the length of the numbers with factoring, it gets much harder with every
increase.
For example, take the multiplication of two binary numbers.
You're familiar with binary.
It's all ones and zeros.
There's two options for every digit.
If I add an additional digit to a binary number, I'm not.
It's just minor league increasing the range of numbers that I can contain.
I'm doubling it.
And so with multiplication, you add a single digit to binary multiplication.
Not a big deal.
You add a single digit to factoring a binary number.
Twice as hard.
And so this asymmetry between legitimate operations like multiplication and fact during which is a malicious
operation, is the basis for the security of public key cryptography.
It's a usable system because you can perform a legitimate operation for a certain key length.
It's a secure system because trying to perform a malicious operation for that key length is computationally
infeasible.
With the modern computers, another example of a mathematically hard problem we use and public key cryptography
fee is the discrete log problem.
So discrete logarithm problem is based off of the relationship between exponentiation and discrete lock
exponentiation is relatively easy.
If you think about it, exponentiation is just repeated multiplication.
And so if you increase the length of the exponent, you do a few additional multiplications.
Discreet logarithms, on the other hand, are hard.
If you're performing a discreet logarithm operation, your best option once again is guessing.
You start out with it up at Exponent of zero and work your way up until you find something that solves
the equation.
And so this additional complexity makes it much more difficult to perform malicious operations with
larger numbers.
Again, like with the factoring problem, it's possible to find a key length where legitimate operations
are doable and malicious ones are not.
And so one of the issues with the hard problems we use today, factoring in the discrete log problem,
is that the security of these classical encryption algorithms that use these problems depend upon the
fact that these problems are hard, that you have that asymmetric relationship between legitimate and
malicious operations.
This becomes a problem when we get to quantum computing.
And the reason why is that these problems are not hard anymore for quantum computers.
There's an algorithm called Shor's algorithm that can perform factoring of two prime numbers in polynomial
time.
So the same complexity as performing multiplication of two prime numbers.
And so this destroys the asymmetry that we're relying on.
And there's no advantage for legitimate operations over malicious ones.
This means we can't find the balance between usability and security that we need if we have a key link
that's long enough to be secure.
We can't perform the operations that we need to use the algorithm.
So it's no longer usable.
The algorithms usable.
It's no longer secure.
And so this is a problem, but it's not an insurmountable one.
And the reason why is that currently, as quantum computers are being developed, we're also working
on developing post quantum encryption algorithms.
And these encryption algorithms are using new hard problems.
And these are problems that remain hard for quantum computers.
So currently, there's no equivalent of Shor's algorithm that allows you to break the asymmetry there.
And so in a few years or decades or whenever quantum computers get good enough and big enough to break
the asymmetric encryption algorithms we're using today.
By then we should have transitioned over to the new post quantum encryption algorithms, meaning that
communications and cryptography can continue in a secure fashion.
So as a brief recap, this video, we were talking about the mathematically hard problems used in asymmetric
cryptography.
We started out by talking about why we need them, essentially, that we need that asymmetric relationship
between legitimate operations and illegitimate ones to make sure that someone with a public key can't
derive the corresponding private key by reversing the operation used to derive the public key from the
private one.
Two examples of these hard problems are the factoring problem and the discrete logarithm problem, where
legitimate operations have polynomial complexity and illegitimate or malicious ones are exponentially
difficult.
And for these two examples, this assumption of hardness is only valid until quantum computers come
into play.
The existence of Shor's algorithm breaks the hardness assumption, however.
Currently, post quantum encryption algorithms are in development and testing that are hard for quantum
computers as well, making usable but secure asymmetric cryptography possible.
Even after quantum computers are reality.
Thank you.