In this video we see in detail the RSA crypto
system.
RC is probably the most
popular public key cryptographic algorithm.
RC algorithm provides us with method for public encryption
and method for digital signature.
So it's very useful algorithm.
As we did for different element key agreement
protocol in the previous video will first cover
the mathematical background. We need to understand the
algorithm.
Then we'll detail the cryptographic algorithm and how
we can use it.
Currency was proposed in a publication
by Ronald reversed addition year
and learned admin.
And that publication appeared in 1978. So two
years after the invention of
public key cryptography by defiant hermit.
And RSA is today the
oldest public key crypto system that
is still secure. So between 1976
when the public key
cryptography was invented in 1978. They
were other proposals of encryption systems.
But all of them were broken or
were found out with a strong variabilities,
but RSA is
today still considered secure.
RC was widely adopted and transformed into several
standards today. It is used in
browsers in iot mobile
applications and in many other systems and
services.
Okay, so now let's look together at the
mathematics of RSA.
the next three slides will introduce all the mathematical
Concepts that we need to understand our say
These concepts are not a very straightforward
or easy to understand. So please
take the time to stop the video
if needed or to watch it
a few times to to understand
this Concepts.
We have seen with different element protocol that
we need to define a prime field
to Define such field. We choose prime number
P.
With RSA, we will work modulo a
number and that is semi Prime.
So first, what does it need to be surprised?
Semi Prime member is a number that is the product of two
prime numbers.
So here the N is written as P
times q and both p and Q are prime
numbers.
So for example 15 is a semi Prime
because 15 is written as 3 times 5.
Both 3 and 5 are prime numbers.
While 42 is not the semi Prime because 42
is written as 2 times
3 times 7 and the so it's the product of three
prime numbers.
Like we did with different animal protocol.
We will work modulo this number.
So we will Define what is called the ring.
So the ring is just the integers module.
This number n so all the integers from 0
to n minus 1.
For example, is it 15?
Corresponds to all the integers between 0 and
14 and we would like
to have arithmetic module this number
n so we need operations such as
addition subtraction, which
is the inverse of addition, but we
also need multiplication.
And the inverse of multiplication is usually the
operation called inversion when we
worked on a prime field all the numbers support
the inversion module
composite number or semi prime
number like here for RSA. We don't always support
inversion. Not all the numbers can
support inversion.
So we need to identify a
subset.
from The Ring
subset of the invertible
elements. So let's first review formerly what
this mean to be invertible.
So number is invertible number
of the ring is invertible if
there exists another value of the
Ring such that the product.
Their product is equal to one module 1
so for example in z15.
4 is invertible
because 4 times 4 module 15
is equal to 16 module of 15, which is
equal to 1 while 6
in the same ring inside 15 is not invertible. You can
stop the video and try yourself to multiply
6 by all the integers from 0 to
14. But of course 0 and 1 they cannot be
good candidates, but you can start from 2
to 14 and you will find yourself that six
multiplied by all of these numbers is
always different from one.
And the reason we kind of expected from
the mathematics because six is
multiple of three so six cannot be
invertible why this statement actually we
know that
this composite number that is defining the
ring is the product as we said
of p and Q. So 15 is the product of 3 and
5.
So we know that to be invertible. You should
not be multiple of neither three or five.
And 6 is a multiple of 3, so 6 is
not invertible.
We know this result from the mathematic. That's why
when we worked with prime fields. We didn't
have this problem of invertible elements.
All the elements were invertible.
Because the p of the Prime field does
not have any factors that that's exactly definition of
prime number. That's why all the
elements from 0 to P. Minus
1 if we are working module P. They don't share
any factors with B. So
that's why they are all invertible while
for working module in
we need to remove for this card
the elements that are multiples of
P or Q.
So we will Define formally this subset. This
subset is called the multiplicative group
and the notation is set and
star like here.
So this Z and star it contains all the
invertible elements.
Which means all the elements that are not multiples of
P or Q. We can Define that
using the gcd function. So this is
the greatest common divisor.
so if an element has gcd
equal to 1 with another element means
they don't have any common factor greater
than 1
so X here is cannot be multiple of b or
multiple of Q.
So for example, let's go back to Z 15.
And Z 15 let's try to remove all the multiples
of three and five. So
zero is of course multiple of them.
Free is multiple of 3.
5 is multiple of 5 6 is
multiple of 3 9 is multiple of 3.
10 is multiple of 5 12
is multiple of 3.
So all these are numbers that
are not invertible all the
others that we write here are invertible
elements.
So whenever we need to use the
inversion operation, we have
to work in this multiplicative group
that end star and not in ZN.
Let's now summarize the arithmetic operations
that we can have in the ring of
residuous module n
So there are some operations arithmetic operations
which are very efficient to apply. Even when
the modulo N is large
enough so large it can
be like thousands of bits or even larger. These operations
are still very efficient.
So we have the addition the addition is just
the regular addition followed by a reduction module
n
so for example 9 plus 13 is equal
to 22 or 0
15 that's equal to 7.
We also have the multiplication which is
also a regular multiplication for rule by
reduction module n for instance 9 times
13 is equal to 100
17 that we
reduce module 15 and 117 is
can be written as 12 plus 7 times
15. That's the largest multiple of
15 that is close to 117. So
the reduction gives
exactly 12. So 9 times 13 is equal
to 12 in Z50.
And as we have seen in the
previous slide we can do the inverse operation on
certain Elements which are invertible.
So we inset 15 we have exactly 8
Elements which are invertible for instance.
Four four. We have seen it's invertible
and it's inverse is itself because
4 times 4 module 15
is equal to of course 16 module
of 10 is equal to 1 so for is the
inverse of 4 in Z 15 star.
And 7 for example is
also invertible and it's inverse
is 13 because 7 times 13 is
equal to 1 as well, as we
Define multiplication. We can also Define power or
exponentiation. So for
an element X we can raise it to exponent
e and then we reduce module
n so seven, for example the cube
of seven in Z 15 is
equal to 300 43 module
15, which
Is written as 13 plus 22 times 15. So module
of 15 is equal to 30.
All these operations can be computed very efficiently.
And there are some operation that is competitionally
hard to apply when n is
big enough. That's the inverse of
the power.
So given an element Y,
which is X raised to
power e finding X from X
power e which is
called finding the eth root for E, which
is public is computationally hard operation.
And as you know for public key cryptography, we
always need an operation that is easy
to apply and hard to inverse. That's
the one-way function and the power and
the finding e throughout will be the one-way function
that we need for RSA.
We need one more mathematical concept
before looking at the details of
our secret to system. That's the earlier tuition
function.
The older potion function is just the
number of invertible elements module M
and the mathematics the gigas
of formula to compute this alert
ocean function. We denoted by
the Greek letter Phi so
Phi of n
The mathematics tell us that for semi
Prime n so which is written as
P times Q the file then is p
minus 1 times Q minus 1.
We can verify it for our example of
n equal to 15.
So this is the this the set of
invertible elements z15 star.
It contains eight elements.
And we can check that the formulas correct.
For 15 the p is equal
to 3 and the Q is equal to 5. So 5 of
15 is equal to 3 minus 1 times
5 minus 1 and that's eight. So
the formula is correct and
it is correct. Not only for n equal
15. It's correct for any assembly Prime
and
another important result about earlier tuition
function is the following for every invertible
element or any element of the
zden star when it is raised to
fire then
it is equal to 1 actually we can verify it
in our example of n equal to 15. Maybe
the easiest to verify is for two two power
eight module 15. That's 256 module
15 and 256 can be written as
one plus 255 which is multiple of
15. So the result is one as expected
by the math.
And you can also do it on 13.
Of course. We cannot like do it manually, but
you can check or using the calculator that the result
of 13 Power 8 module 15
is exactly 1. This is very important result
that every invertible element when it's
raised to the fire van is equal to 1
and we will use this result to understand the
mathematics of RSA.
Okay, a reminder of the scheme of
public encryption.
So we have two parties a decent
pop.
And there is a generator that provides Bob with
a pair of public key that
he can share with everyone and
a private key or secret key
SK here.
So Alice will use the public key of Pop
to encrypt some message X.
That's how she obtains a ciphertext y.
And up uses his secret key to decrypt
the ciphertext and
retrieve the plaintext.
And of course the adversary who is intercepting their
messages is unable to retrieve the plaintext
from the ciphertext without having
access to the secret key.
first step
are secure to system is to generate
public key and the secret key for
Bob.
So the generator will do it as
follows.
It will pick two prime numbers p and
Q.
And compute their multiplication as an
N is the product of P times Q.
then we as we know the factorization of
n we can compute the fire
n
As using the formula that we have seen a
couple of slides ago, then the generator chooses
some e which is
what we call Co Prime with fire event
Co prime. It just means that the E
does not have
Any other diseaser with fire van except
one?
This is a very important you'll see why.
because
the E will be the the end
end will be the public key of Bob.
And his private key will be
the inverse of e module 5
event not modular n but module 5n.
So to be able to compute these inverse operation,
we need e and 5 1 to be Co
prime or to not share any common
divisors. So at this
step we have distributed the public key and private key D
to pop.
And of course his public key can be
shared with anyone including Alice here.
so to encrypt some element X which
is represented as an integer
module n
this is missing in slime, but let's keep
that in mind.
to encrypt
Alice has to raise her plain
text X.
Power e so she will compute X
power e on Julian.
And that will be her ciphertext. Why?
To decrypt Bob will need to
raise the ciphertext Y
power is secret key or
private key to retrieve X.
Okay.
Two important questions here why this
is correct and why this is secure this are
the questions that we need to focus on
first why it is correct to
understand that let's first look
at how we computed the D
from E. What's the relationship between D and
D?
so the D is the inverse of e module five
n
which means that e times D
or D times e is equal to one module five n
So this means that
their product the times e is equal
to 1 plus some multiple of 5.
Let's keep this result first and let's look
at how a computed the
how Bob computed the plain text
from the ciphertext.
So this is what Bob did
erased y to D. Would you
go ahead?
And the Y is actually the power of x.
To the exponent e which you n so I just plugged that
value here.
And because we are we have here we have two module n
we can just keep one of them and this
x power E power D.
I just write it as x times a power
e times d
This is just I mean regular result about
powers.
And as we have seen here.
E times D or D times e is equal to 1 plus
some multiple of five n so we will plug
this into this e
times D to obtain this result.
So and now we have X
power 1 plus some multiple of five n
we will break this.
into x and x power five
n times k
and that X power five n
times K can be written as X power 5 5
1
and everything is our case.
and this is where we will use the
important result about alert ocean function, which is
that X power 5 n is
equal to 1
so all this is equal to 1 so
the whole result is equal to X modular n
and as we said X is chosen to
be z n so X module n is
equal to X. So that's why the R6
description is correct and gives
us back the original plane text.
Important question is why this is secure.
Okay, what the adversary will see
the adversary will see the power
of the plaintext to the public
key. So these three forward
operation that the adversary would like
to do to retrieve X is to compute the year
throat. So to extract the X from this
power.
And as we have seen a few slides cool,
this is a computationally difficult operation
if n is big enough.
So this way is not possible for adversary unless
he has the deal. Of course if he has
the D he can do exactly what Bob did here.
So the second approach for the
adversary would be first to compute the D. And once
he computes the D. He can do what Bob has
done.
To compute the D the adversary of course knows e
has to use that e to compute the T.
But in order to do that, he needs
the fire van.
And that's why I said it's very important to keep
the factorization of n
Secret.
So the secret key here is the D.
but we need also to
not reveal the factorization of
n because if we do that.
Then the adversary can compute fire
n very easily and then can retrieve
the D.
So these are the two
main approaches of attack that
the adversary can do.
And until today our say
is secure because there is no other way to break the
system. The adversary has either to
compute the EF root or two factorize n
and a factorizing n
when n is big enough is also a
heart problem. So these are two hard
problems that keep our say
secure. If one of these problems is
found out to not be hard enough like
we find an efficient algorithm either
to factorize or to compute or to
extract eighth Roots. Then RSA is
no longer secure.
Okay to get used to the mechanics of
RSA. Let's take an example
but keep in mind. This is a toy
example. This is definitely not secure. It should
not be used in real life. We use bigger values
of primes and this is
just to illustrate which kind of operations that
we have.
So let's assume that the generator choose the
primes 3 and 5 then the
N is equal to 15.
The file 15 is as we computed before is equal
to 8.
Then the generator chooses the
value 3 as the exponent of
the public key.
As three and eight are copyright.
They don't share any cover divisor rather
than accept one.
so the public key will be composed
of the exponent 3 and
the module n equal to 15 and the
private key is the inverse of three module 515
which is 8
the inverse of 3 module eight is actually 3
because 3 times 3 that's equal to
9 0 8 that's equal to 1.
You might be surprised to see that the pub exponent of
the public key is 3 and the private
key is also three. This is just because
we are working on the small example.
In real life when we have large modular. This
is unlikely to happen.
So to encrypt a value 7 at
least reads that seven to
the power to the two
to three.
So she computes 7 power 3 module
15, which is equal to 13. We
have seen this example a few slides ago.
The several text is then 13.
And 2 decrypt Bob raises 13 power
3 module 15 and he
can obtain 7.
So this is a small example test for
you to get used to this kind of
operations.
the security of RSA crypto system relies on
the hardness of integer factorization
if an adversary invents method to factor integers
efficiently.
Then he or she will be able to break RC to be
secure.
You have to use today you
have to use an module for RSA, which
is at least 1024 bitlock.
On February 2020 a
team of researchers computed or
broke the record of
integer factorization and they
managed to factorize a semi prime number which
was 829 bit
long.
But obviously they didn't know the factorization of
this integer.
This is this integer is part of the
challenges that RSA company published.
So RC company choose
this list of SUNY Prime
members and they never disclosed their factorizations
and it's up to the community of
research to try to factorize this
Embers. That's how we increased out
trust in our secret to
system. And these are the intentary 29 was
a factored by
this team of researchers using an open source
tool and some servers. So any
attacker that is motivated enough
to allocate resources can
repeat this attack.
That's why.
even 1,024-bit is still
considered secure, but maybe for just
A few more years after that it want to
be considered secure anymore.
We rather recommend lands that are 2K 3K
and 4K long for RC.
So on this video, we covered the
arithmetics in the ring of
residues module Sony Prime
and we also discussed the details
of RSL crypto system why it
is correct. White is also
secure.
And this is the last video of the
section in the next section. We
will continue with the public key
cryptography and we'll revisit our say in
particular to see how we can derive digital
signatures from the RSA one-way
function.
So stay tuned see you on the next video.