Good morning.
Next session on Algorithms for Internet Applications.
Hope you had a nice Christmas break.
And came well into the new year.
I wish you all a happy new year.
And we will have a few more lectures on Algorithms for Internet
Applications.
Currently we are in the chapter on cryptographic algorithms.
Hope that you all had time to work on the assignment, the programming
assignment.
I don't know how you got around to that.
You know that the registration for the exam, for the final exam, is
starting now.
So if you want to take part in the final exam at the end of the term,
you should register for the exam as in the usual locations where you
have to register depending on the type of studies you are in.
Okay, and also the bonus exam, the registration for that ended at the
end of last year.
So I hope that you all registered and that you will pass all these
exams in a very good way.
So, what did we do in this chapter?
We looked at all kinds of scenarios for secure communication or all
kinds of potential attacks on security in communication active and
passive.
Passive and active attacks.
We looked at, well, the cryptographic approaches to make the
communication channels more secure.
Showed you the simple methods for encryption.
CaesarCypher, TableCypher, VisionaireCypher, OneTimeTab, and the
encryption using random number generators using storing of a binary
sequence with a binary method.
And then simple storing again to have the original, to get the
original plain text.
So that's a very simple approach.
And then we also looked at the transposition scheme.
I showed you the BES algorithm, how that's working.
And the major part there is the Feistel round, which has the nice
property that you can use both ways for encryption and decryption.
Again, due to the properties, certainly of the structure, but also of
the storing operations.
And we looked more closely into the particular ingredients of that
Feistel round.
And there the S-box is a particular important part.
Showed you how that has been designed.
I made a few remarks on cryptanalytic attacks on BES.
And then this, I think that was the last lecture last time, or the
last slide last time.
So I showed you that certainly you can try to attack cryptographic
algorithms.
In particular, there have been massive attacks on BES because it was
the standard cryptographic algorithm.
And the important point is that there are so-called side-channel
attacks, where you have possibilities just by looking at, for example,
power consumption or things like that, you can find out what kind of
information is processed internally.
And so that way you can find out information that was supposed to be
secret.
So, things have to be modified and the consequence was that there were
a few more... that other algorithms have been designed.
I will show you later today the new algorithm AES, the advanced
cryptic standard that has been selected in a competitive round of
elections in the beginning of this century.
BES is not completely phased out.
Triple DES is still there.
And the problem is that symmetric methods have some inherent problems
that have to be considered if you look at cryptographic methods.
One of the problems is that if you look at the requirements that you
have, you have many persons who would like to communicate.
And if you have just communication between all those different
persons, if you have n persons, then you need n different, or n-1
different keys just to communicate between one person and all the
others.
So, if you have communication between all of them, then obviously you
need all of n keys, if you would like to have secure communication
between each pair of persons that are there.
Then you have to find out how to actually exchange the keys, and it's
obviously a problem to do that in a secure way.
And in particular, you would use the key for a longer time.
And if you use the key for a longer time on a cryptographic method, it
means that there are many possibilities to try to attack the
communication, because you have many choices of looking at encrypted
text to find out the original plain text.
So, these are things that have to be considered.
And so, there is an alternative approach for the public key
cryptosystem, which at first sight is strange, because how can
something that's supposed to be private and secure be done in a public
way?
So, public key looks like a contradiction in itself.
So, the idea is that every person has her own public key to be used
for sending her encrypted messages.
So, if somebody wants to send a message from some person to another
this is person A and that's person B, then person A has to know the
public key of person B in order to send the message that is encrypted,
and only person B can decrypt that.
So, that's a different approach.
You have a public key for encrypting that everybody can encrypt, but
only by using secret information you can decrypt.
And this is a nice idea, and the naive idea would be to just put all
those public keys inside something which is similar to a telephone
book, and then you can just look up the public key of some person and
send the message and you're fine.
But this is naive, and we will see later on that that is too naive and
will not work.
Nevertheless, public key methods are very important.
The point is you have to know the public key of that person B.
You have to make sure that it is exactly the public key of that person
and not of somebody else, otherwise there would be attacks, which I
will show you a bit later on.
So, every person has their own secret key for decrypting, and the
requirements are that if you have a message which you encrypt using
the public key, then you will decrypt that with the secret key.
So, certainly if you apply the secret key on the encrypted message,
you should be able to retrieve the original message M.
Those pairs S and T should be different for different persons,
different users, so you have to make sure that.
It should not be too expensive to work with such a public key system,
and it should be secure.
That means if you have some information, what kind of information do
you have publicly?
You have the public key, you have the message, and you can see the
encrypted message.
Because if you have a public key, you want to encrypt the message, you
can see how that is transferred, or how that is changed.
So, by knowing the public key, the original message, and the encrypted
message, you should not be able to find out what the secret key is.
And also to derive the secret key S from T should be as hard, or has
to be as hard as decrypting the encrypted message without knowing the
secret key.
So this has to be ensured that it is hard to actually find out the
secret key information.
And then certainly to compute the, or to perform the encrypting, the
decryption, should not be too expensive, because you don't want to
spend too much time for encrypting, for making the communication
secure.
So this looks like quite some difficult list of requirements, and you
will see that this is that this is not, it's really hard.
I just noticed that I explained this requirement for like inadequately
I explained requirement 5, decryption should be simple or should not
be too expensive, and also the key should be generated in a way that
should not be too expensive.
So, although the keys are computed once, then you will use them for
quite some time, and so that should not be too expensive to do that,
and then the encryption and decryption certainly also should not be
too expensive.
So these are reasonable requirements, but it looks as if that would be
almost impossible to actually satisfy.
And the background on that is, so what we have to do here is, we have
some ways of easily encrypting something, like if you look at this
lock here, it's very simple to lock, to close such a lock.
You just push it, but in order to open it again you need some secret
key.
If you don't have that key that you can insert here, it's very hard to
open that.
So, the background is that you need a way of some kind of function,
which you can easily compute, but although it is very difficult to
retrieve the original argument to invert that.
And simple examples, so if you have a telephone number, if you know
the...
or if you would like to find a person's phone number in a phone book,
that's easy.
You just look up the person, but if you would like to find the person
for a phone number, if you don't have an inverted list, then it is
hard to find that.
Although, certainly we know how you would do that in that example.
It's just to invert the list.
But if you don't have the inverted list, it's quite an effort to do
that.
Then the more practical example, factorization.
Now we come closer to what we're actually heading at.
If, for example, you have something like the problem of multiplying
two prime numbers, this is easy.
Multiplying two numbers, we know how to do that.
Then we have some number which is the product of two prime numbers.
But then, in order to find out what have been those prime numbers, you
need to factorize the number n.
And certainly that's not really simple to find out which prime numbers
are the divisors of such a number.
So the problem of factorization is believed to be hard.
The known methods are still very expensive.
So this is the problem which seems to be very hard to factorize a
number, in particular if you have a very large number.
Certainly if you have small numbers, this is easily found out.
But if you have very large numbers, very large means, several hundred
or thousand bits, then it is a really hard problem.
And we will look at that problem in a moment.
For cryptography, certainly a one-way function should have a backdoor
that means if you have some additional information, it should be easy
to invert it.
And this additional information usually is key information, as we have
here in that lock system.
If you have the key, you can easily open it again, but without that
it's very hard.
It should be very hard.
One-way functions are an important part in that.
Easy to compute, but hard to invert.
And the system that is one of the standard public key systems is the
RFA cryptosystem by Rivers, Adelman, has been designed at the end of
the 70's.
And here you have, certainly, you have the public key, you have the
secret key, and the public key is a pair of integers N and C.
C is standing for code.
And you have a secret key, a pair of integers N comma D, where only D
is secret, N is known, D is secret, and D stands for decode.
Although we will see that this just refers to the application that I
initially mentioned.
You would like to encode something with a public key and then decode
with a secret key.
And C and D have at most as many bits as N.
And you will see how this actually is used.
The standard lengths are well, this is almost not used anymore.
Usually you have something like 2,048 bits.
You can use any number of bits, but usually it's powers of two, what
you have there.
And the number of bits is the basis for the security or the strength
of the photographic system that you get from that.
How is it actually done?
You have a message.
The message is just some sequence of zeros and ones.
You could say, okay, it's just a sequence of just one large number.
Now you have that value N.
You just chop the sequence into individual paths with some kind of
block cipher, you could say.
The message, chop it into paths M1, M2, M3, and so on, such that all
these values M1 to Mk are smaller than N.
You could just take one bit less than N.
Then you always have the value that is in that range.
So you just divide the message into such a sequence of blocks, and
then you compute the following.
You take all the individual paths there, the Mi, take them to the
power c, and compute the modulo...it says that modulo N.
So you divide by N and take the remainder of that.
Then you have some part or some value Ci which is less than N.
Now you have that value, and then you have a sequence of c1, c2, and
so on.
And the decryption then just works that way that you get the encrypted
message.
You just divide that message again into those parts c1 to ck, and now
you take Ci to the power d, modulo N.
And
magically, here, we get the value Mi again.
That's the claim that N, c, and d are chosen such that this works.
So that you can take a message, the value Mi, take it to the power c,
modulo N, and then if you take that to the power d again, you get the
original value there.
Looks like magic, this is just number theory as we will see in a
moment.
And so, this is all about that RFA cryptosystem, that you just have to
do that.
Or, just is a bit unfair, because just means, well, we have to compute
Mi to the power c.
Mi are values that have as many bits as N.
So something like 2000 bits.
And c and d are values which have at most as many bits as N, but may
have as many bits as N.
Usually they are, or at least one of them will be smaller, but they
will have several hundred bits.
And that means you have very, very large numbers.
And so it means you have arithmetic of very large numbers, and
modification of very large numbers is... takes quite some time.
So it's a naive way to take the length of the numbers so you need
multiple arithmetic here, which is expensive.
And it's not just modification, it's Mi to the power c.
Mi to a value, to an exponent, which is a very large number.
So that really is an extensive computation, contradicting the
requirement that encryption and decryption should be done in an
efficient way.
So this is a challenge.
If you would like to use that, how can you make sure that this can be
done efficiently?
So there are many, many ways of actually performing those computations
in more efficient ways than the naive ways.
I will indicate just very simple ways of doing that, but there are
more sophisticated ways of computing these powers using modular
arithmetic.
Using Chinese remainder theorem and things like that, but I will not
go into the details of Chinese remainder theorem.
So, the important thing, the basic thing, is how can we actually make
sure that this works?
How can we choose n, c, and d such that this works?
And to assume 1024 bits, although the number of bits here is
completely irrelevant at the moment, we just look at those values.
And we want to have a number having around 1000 bits, so we just
randomly generate two large prime numbers, p and q, both having half
as many bits.
If we multiply those two prime numbers, then we know that the product
will have twice the number of bits.
And so, in this way we can get a number n, which is the product of p
and q.
And I just mentioned when I talked about one-way functions, that
factorization is such a one-way function that means it's easy to
compute, but hard to invert.
And so, if you only know n, if you have a very large number, it's very
hard to actually find out what p and q are.
So this is one thing that is used there, so that's how we get n.
Now, how do we choose c and d?
So we just randomly choose some c such that c is prime relative to p-1
times q-1.
What does it mean that a is prime with respect to b, if and only if
the greatest common divisor of a and b equals 1.
Yeah?
Simple.
There's no non-trivial common divisor.
So, we just choose such a value.
Now, since we have a number like p-1 times q-1, if we just choose a
prime number c, then that is simple.
We won't have a non-trivial common divisor, and c should be prime
relative to not p times q, but p-1 times q-1.
We'll see in a moment why we choose exactly that value.
So, c should be prime relative to p-1 times q-1, and then we determine
a value d, such that the product of c and d is congruent to 1 modulo p
-1 times q-1.
What does it mean that value like, if you have a congruent to b modulo
x, for example, write that in a better way, modulo x means that if and
only if there exists c such that a minus b equals c times x.
So, a and b have the same remainder with respect to division by x.
And so, that's the definition of cd is congruent to 1 modulo p-1 times
q -1 They have the same remainder of that, so cd is a value that is a
multiple of p-1 times q-1 plus 1.
Very simple.
Now, the interesting fact is that if we have chosen those values
having those, satisfying those requirements, we have chosen them in
this way, then the claim is that for these n, c, and d, we have that
for all values m less than n, m to the c times d is congruent to m
modulo n.
Now, remember that we had computed in the RSA algorithm, first m to
the c that was the encryption, and then the encrypted value to the
power d, which means that well, it's essentially taking m to the c to
the power d and that is, as it claims, c is congruent to m modulo n,
and so this is what we need.
If that lemma holds true, then we know that the RSA algorithm works
correctly.
The validity of that lemma is due to some results of number theory.
I will not go into those results, but just use them.
The first one is Fermat's little theorem which is saying that if p is
a prime number and if you have another value a which is not divisible
by p, then a to the p minus one is congruent to one modulo p.
That is the first important point.
That would mean in this case, a to the p would be congruent to a
modulo p.
Multiply the number times a, then you would have something a to the p
congruent to a.
Or a to the p minus one congruent to one modulo p.
So this is something which will be used in showing that this actually
holds true.
The other thing is that this has been generalized by Euler, and Euler
used a particular value for any integer value n or any natural number
n.
He looked at the number of values that are prime relative to such a
value n.
So all the values m that are smaller than n, but not divisors of which
don't have a common divisor with x.
And this value phi is called, or phi of n is called the Euler
function, because Euler designed that.
The theorem that we are using here is that for any values n and a,
such that a is prime relative to n, so they have a greatest common
divisor with one, we have the result that a to the phi of n is
congruent to one modulo n.
So here we had a to the p minus one is congruent to one modulo p, and
now we have here a to the phi of n is congruent to one modulo n.
And what we're interested in is certainly something where we can get
this statement that something taken for some exponent is, or this is
taken for some value is the identity function.
And as I said, if you would take that a to the phi of n plus one, then
that would be congruent to a modulo n.
And then you would have exactly what you need for that lemma.
So the corollary is that for all a, n out of n a to the phi of n minus
one is the modulo inverse of a with respect to that modulo n, and
these facts are used in showing that lemma holds true.
And I will show you that this actually holds.
I will not go into those theorems, but just show how we use those
results of number theory in order to show that the basic method of the
RSA algorithm actually is correct.
And the first thing that we have to look at for that is what the Euler
function actually is for this value capital N, which is p times q.
So if p and q are prime, then phi of pq, the Euler function of p times
q, is the product p minus one times q minus one.
And if you look back at the previous slide, you see that here we had
chosen c such that c is prime relative to p minus one times q minus
one, so this has something to do with that.
Then let's go again to this slide.
So how can you prove that?
We have a value which is the product of two prime numbers, p and q.
Now if they are prime, then we can immediately say, or can list a
certain number of values which are not prime with respect to p times
q.
They have a common, a non-trivial common divisor with p times q.
Now what are these non-trivial common divisors of p times q over the
value having a factor p or a factor q?
We have a non-trivial common divisor, so these values, p times one, p
times two, up to p times q, are values that are less or equal to p
times q, which has a greatest common divisor which is not equal to
one.
And the same is true for multiples of q, and for how many multiples do
we have here, these are q multiples, and these are p minus one
multiples, so in sum we have p plus q minus one numbers, and these are
exactly those numbers which are not prime with respect to the product
of p times q.
And so, how many numbers are there in total less or equal to p times
q?
These are just p times two different values.
We know that p plus q minus one of those are not prime with respect to
p times q, so if we subtract that, this is just the product of p to
minus one times q minus one.
As you can easily see that if you multiply that out, then you have
exactly that equation.
So, this is just this number of integers which are prime with respect
to p times q, and now we use that fact for the following.
We know that p minus one times q minus one is the Euler function of p
times q.
So that's what's stated here again, and we know because of the Euler
theorem that if m is prime relative to that value n, then m to the
Euler function of p minus one times n.
m to the Euler function of n is congruent to one modulo n.
That is the statement of the Euler theorem, and we certainly also know
from that that if we multiply both values of m, then we have m to the
p minus one times q minus one plus one is equal to m modulo n.
So this is a simple thing.
If you have problems with this modular arithmetic just put up your
hand and I can explain it to you.
So, from that, we also know that now c times d d is chosen such that
the product of c and d is congruent to one modulo p minus one times q
minus one.
And that means that cd minus one is a multiple of p minus one times q
minus one.
This is what we know, this is just the same statement.
And so m to the c times d c times d therefore is congruent to one
modulo p minus one times q minus one.
So it means that m to the c times d is congruent to m modulo n.
Here we have we know that m to the... so c times d is a multiple of p
minus one times q minus one we know that m to the p minus one times q
minus one there, this statement is congruent to one modulo n.
And so it means c times d is just a multiple of p minus one times q
minus one plus one.
So we know that we have here exactly that equation.
This is what is stated here again.
c times d is such a value such an exponent such that we have m there
again.
And certainly here we only have in the exponent p minus one times q
minus one.
Here we have that k times, but if that if m to the x is congruent to
one modulo n, then m to the k times x certainly is also congruent to
one modulo n.
So this is simple.
And so that means for all those values that are prime relative to n,
we have exactly the equation that we are looking for, that m times m
to the c times d is congruent to m modulo n.
Now this is just because of that choice of values and the fact that we
have the Euler theorem.
Now the question is what happens if such a value m is not prime with
respect to that value.
We know that there are p minus, or p plus q minus one values which are
not prime relative to n.
Now these values we know are for example of the type multiples of q we
have multiples of p and multiples of q, so if this value m is just
some multiple of q what's happening in this case?
We have to show that even for those values, m to the c times d will be
congruent to m modulo n.
And so t definitely is less than p.
Otherwise it wouldn't be such a value.
And since t is less than p t is a prime number, we know because of the
little theorem of Fermat, that t to the p minus oops, that t to the p
minus one is congruent to one modulo n.
And we also know that q to the p minus one is congruent to one modulo
q.
Because q definitely is also, q is a prime number, p is a prime
number, so this is just due to the little Fermat theorem.
Now we can use that result, we certainly notice that if we have this
for every k greater than zero, certainly if we just square those
values if we take that k times p to the k times now p minus one times
q minus one we can just take a multiple of that, it's still congruent
to one modulo p.
The same is true for q to the k times p minus one times q minus one.
Also congruent to one modulo p.
So this is just a simple consequence of the fact that those powers
here are congruent to one modulo p.
These are just multiples of those powers, and so this is again just
congruent to one.
And now, since both are congruent to one, we can just multiply those
values.
So as a product of those two values here are also, so if we have for
example, the following holds true if a is congruent to b modulo p and
c is congruent to d modulo p, then certainly a times c is congruent to
c times d.
Modulo modulo p, yes.
Okay.
So this is around that.
So this is just simple fact from number theory.
Are these facts known to you?
Modular arithmetic?
No response?
Or new number theory?
This is something which is standard mathematics.
But it is really not that difficult.
If you just use that basic definition that a is congruent to b, modulo
x means a minus b is a modulo of x, then you can easily find that out.
This is simple.
So we have that, so we have the product of those t, power of t, power
of q, product of those two is congruent to the product of the right
-hand side, product of the right-hand side is still one, and we just
multiply that with t, and then we have t times tq to that power is
then congruent to t, modulo t.
Both sides multiply to t.
And it's also true that, like if we multiply that with q, this is also
congruent then to tq, modulo t times t.
This is also, again, another simple result, like if we multiply both
sides with the same value, then those values are congruent again,
modulo the original modulus, but also to the modulus that is
multiplied to that value q.
So this is another simple fact of, or simple implication of modular
arithmetic, and so what we have now is that tq to the power k times t
minus one times q minus one plus one is congruent to t times q, modulo
t times q.
But that is exactly what we are looking for, t times q is the value of
m, and so we had to show that m to the t times d is congruent to m
again, modulo n, but this is exactly what it stated.
Because k times t minus one, q minus one, plus one is our product of t
times d, and so we are done.
And the same can be done for modulus of p, just in a symmetric way,
and so in this way we have shown that for every value, for any value
that is less than capital N, we have this result that m to the t times
d is congruent to m modulo n.
So if we just use the Euler Theorem and the Lim-Savart, both are the
major two ingredients of that result.
So, number theory gives us that nice result, we can just compute it in
this way, and so we don't need all these structures like in the
symmetric algorithm, we have these storing and table permutations and
things like that.
This is just done here by using number theory.
And so we now have that result and now the question is, what about the
requirements that we had, what about the cost of that algorithm?
And one of the major points here is, well we have this exponent, like
we have to take the power take it to a very large power, and it's very
large numbers, very large numbers computing these exponentiation is
expensive.
So the naive way would be that if you have to compute a to the 4, for
example, that is a times a times a times a, so that would mean you
would have three modifications for that, which certainly would mean
that for a to the x or x to the n, you would have something like n
operations which would be a very, very, very large number.
And you can easily see now that this can be done in a more easy way so
if we go to the next slide I can briefly show you how that can be
done.
How can we compute x to the n in a more efficient way.
I don't know whether you have seen that algorithm or those algorithms
before it's a simple observation.
You have an arbitrary integer and you have an arbitrary integer n and
this n is supposed to be the exponent of x so if we compute x to the n
n can be written certainly as a binary number, sum of ai 2 to the i.
And now that means if we compute x to the n, this is just x to the n,
n is the sum of those powers of 2 that means we can either write that
as x to the sum of certain values or as a product of those powers.
And so we have this equation here and we have to look at such a
structure.
Now if we look at that the product of powers of x and every power,
like the ai, are either 0 or 1.
That means we have certain powers x to the 2 to the i only those are
in that product where the ai is not equal to 0, which is why.
Now there are different ways of computing that.
One way would be just take those powers.
They're written in a slightly different way.
So definitely you know it as x to the a times b that can be either
written as x to the a to the b or x to the b to the a.
Now this is also simple arithmetic so we could write here we take x to
a0, which is binary that means we either take that or not.
0 or 1.
And then we have x squared and we decide whether we need that or not.
We have to use x to the 4 and we look at whether we need that or not.
Or x to the 2 to the k in the end.
So all these powers of x where the exponent is a power of 2 and the
bits tell us whether we need that power of x or not.
And obviously we can get all those factors here by just squaring by
successive squaring of the individual values.
So we take x squared, x to the 4, x to the 8 and so on, x to the 2 to
the i.
So this is just successive squaring and deciding whether you need
those powers or not.
And if you have a number having k bits you need exactly k of those
algorithms or k of those steps, so you have to square that value k
times and while you are doing that you just multiply the immediate
value with the additional power of x.
This is one way of doing that.
The other way would be a different way of looking at that product of x
values is, well, to look at x to the 8k.
That means do we need x or not?
And then we need to know 8k times 2 to the k.
Now, there is the 2 to the k, that's successive squaring, but we just
multiply that with x to the 8k-1 and form this number of squarings and
so on.
So this is a nested way of doing it.
And in the end we would have x to the a0 times that where that
intermediate value x to the a1 times that value and so on.
That means if we compute that here, we could compute it this way
starting with x to the a0, compute x squared decide whether we need
something here, whether it is 1 or, like, if a1 is 0, we have here the
value that would be 1, or otherwise it is that power, and so on.
We can do it starting from the least significant bit, going to the
highest significant bit, or you could start with the highest
significant bit, take x to the 8k, that means use that x, or put 1
there, square that value, multiply with x if the appropriate bit is 1,
square it again, multiply with x if the appropriate bit is 1, square
again, and so on, until you finally get that value, because this is
computed that way.
Two different ways of computing the power x to the n, and obviously
the number of operations that you need is the order of k.
So both ways we have the order of k operations, in the worst case, 2k
minus 1 operations, and it means that it is the logarithm of n, so we
have a fast way of computing here, okay, so we have this fast
exponentiation using logarithm of n arithmetic operations for taking x
to the power n.
So this is a simple way, now we know how to do that.
Still, if we have an exponent having 1000 bits, we still need 1000
operations for that.
Not just 1000, but maybe more, at most two times that value.
But it's a large number of individual operations, but still much less
than in the naive way of computing them.
And obviously these operations are all operations on large integers,
so it is still quite expensive.
So if we have naive multiplication of k word integers, we would need k
squared single word operations.
If you just take the school method for doing that, like multiplying
two values, you know that we do it like having multiples of that
value, and then summing all those up.
And this is just something where you have k squared operations.
Every operation here needs time k, linear time, and then you have k of
those operations, times k squared, the naive school method.
If you do that in a recursive way, you can easily reduce that to k to
the 1.5.
And if you do it with even more sophisticated approach, you can
actually reduce that to k times log 6.
For that you would need the past Fourier transform.
Do you know the past Fourier transform?
Who of you knows the past Fourier transform?
None of you, if you would like to get to know how that works, come to
my course on addition algorithms.
I will not go into details of that in this course.
So this is past Fourier transform, is that it's a way of... it allows
you to perform that multiplication of k word numbers in that time k
time log 6.
Okay.
So that means that we can reduce the time, but still if we look at 32
-bit arithmetic, and we have exponent length of 1024 bits, we need
something like, like in a simple way to compute that, something like
327 operations per plaintext block of 1024 bits.
So this is quite a large number of operations, but we have to pay
something for getting security.
And there are ways of even speeding that up, using using as I
mentioned the sinus remainder theorem, and using a more sophisticated
way, modern arithmetic, but I don't have the time here in this course
to go into the details of that.
That would be the topic of a different course where we would look more
into fast arithmetic.
Okay.
Now you can implement that in hardware, and if you do that, just use
those methods, if you use certain algorithms for performing those
operations, you can actually perform RSA encryption in time, or in the
high frequency.
It's like you use modular arithmetic, use parallelization, use
pipelining, and then you can support the data rates that are necessary
currently.
And you can easily actually do that online without slowing down the
communication.
You know that if we talk about communication, we are talking about
data rates that are not that high, 100 megabits or things like that,
100 megabits per second, and we know that we can perform many
operations inside, the clock frequency is several magnitudes higher,
so we can perform quite a number of operations internally compared to
the communication speed, the communication bandwidth, and you can also
use parallelization, and so we can actually use RSA without slowing
down significantly the communication.
And another point is that if you don't want to use that sophisticated
method, then we can actually make our communication secure by not just
using such a public key method like RSA, but by combining that with
other methods which are much more efficiently computed, like symmetric
methods, and in this combination get around the problems that we had
with symmetric cryptographic methods.
We will see how we do that in a moment.
So this is the RSA algorithm that was passed for communication, as I
showed you already.
The question is, again, cryptanalysis, how expensive is it to actually
attack that algorithm?
The attack would mean as soon as you know the prime numbers, which are
the factors of N, then certainly by knowing the public key, you
immediately have D.
Because if you know the prime number P and Q, you can compute P-1
times Q-1 and then you can compute D which corresponds to C.
But the problem, or the nice fact, is that currently the best known
methods need a lot of time to factor large numbers, like this is
showing the current upper bound on doing that, the best known upper
bound with respect to my current knowledge of those factorization
methods, and like D in that formula is the number of bits of N.
That means if you just use that and disregard the constant values that
are always in those big O locations, if we assume that we have 10 to
the 12 operations per second, that means one operations per second,
and we have this value having 300 decimal digits.
300 decimal digits means around 1000 binary digits.
Then, if we would just use that algorithm we would still need several
thousand years for factorizing.
So, this is still quite expensive, and the we always had the
requirement that it should be more expensive to decrypt the encrypted
value without knowing the secret keys and the value of that
information.
Well, if it takes several thousand years, that could be the case.
So, this is just with respect to current knowledge, it means you
certainly can decrypt that, but you need information that you can
compute, but it takes some time to do that.
Now, certainly, there would be ways of attacking it, which are
different from just using exact methods for or deterministic methods
for factorization.
You could, for example, use probabilistic methods.
You could just guess the value.
Take some arbitrary values, guess methods, or guess factors, check
whether they are factors or not, and then you are done.
Or you could use random computing.
Random computing is a completely different way of computing.
Here, it has been shown that with random computing, factorization is
easy.
So, it would like to factor two numbers that can be done in very
little time using random computing.
Random computing is something which is working in theory.
Certain progress has been made with respect to actually building
random components for computing, but we are far away from actually
having practical random computing devices which can be applied in
practice to this problem.
So, up to current knowledge, it is sufficiently secure to have those
values or to use RSA using, well, it would like to be conservative,
take 2048 bits for the keys, and then, or for the modulus, and then
you are quite safe.
So, we need very long keys, definitely, because the length of the keys
is determining the strength of the cryptographic method, and these
keys have to be much longer than for symmetric key algorithms, because
in symmetric key algorithms, the strength of the algorithm was based
on different things.
There was information hiding and all kinds of these things that I
showed you.
Here, the major point is, if you are able to factor a number, or if
you can do that efficiently, you have immediately a way of efficiently
attacking that algorithm.
Okay.
So, this is just this remark on cryptanalysis, but there are still
some problems remaining.
We said we should be able to easily determine the public key and the
secret key.
Now, how would we do that?
Just two prime numbers having 500, 1000 bits.
Now, how do we know that a certain sequence of 1000 bits is a prime
number?
How can we actually determine that?
We would like to find, for example, the largest prime number less than
or equal to some value.
So, less than 2 to the n, where n is a very large value.
The simple way of doing that is a very old one, this book called Seed
of Eratosthenes, and it works in the following way.
You just write down all the numbers from 2 to n.
So, we write down 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, and so on.
It takes some time to do that on the tablet, but well, it doesn't take
that long if you just do that on your computer, just write up all the
numbers.
But if it did well, if the value of n is a number having 1000 bits,
this is quite a long sequence.
Yeah?
And then, what do you do in the next step?
You delete the first number and all the multiples.
Well, that's easy.
If we delete 2, we delete all the like, half of the value disappears.
Obviously.
Even numbers cannot be prime.
You know that.
So, all the multiples of 2 are deleted.
We would like to have the largest value that is prime, which is less
than or equal to n.
It shouldn't be the product of values that are smaller.
So we take the next value.
This is just done until the list consists of a single element only.
So, we do that all the values from 2 to n and if, by crossing out all
those values that are multiples of some other value and in the end we
have only one value, this value has not been a multiple of any of the
values that are smaller.
So it must be a prime number, which is less than or equal to n.
So we have 3, now the next multiple of 3 is there, the 9, then we have
the 15, then we have the 21, that's it.
And then we have the 5, multiple of that is not in that list anymore.
We have to take out the 7 multiple of that, we don't find one there.
Take out the 11, there's none over there.
So, in this way, we just cross out all those values.
You see that this list is getting smaller very fast, but still we have
to do that for all those values.
So this is very efficient very fast if you have small values of n, but
if you have values having thousands of numbers, a thousand bits, it
just takes too long.
So it's unfeasible for those values, and so a different approach would
be to just use a probabilistic approach.
Certainly, just back to factorization.
If you use a probabilistic approach, and you are lucky, and just
guessed a correct prime value, then you have done factorization with
almost no effort.
You just guessed such a value, but you cannot guarantee that you find
that with very few attempts.
Now, I say, well, we just do or take that approach, the probabilistic
approach, for finding that prime number, having a large number of
bits.
So we would like to find a prime value, so we just choose some random
odd number, certainly not an even number, just a random odd number,
having, for example, 512 bits, or 1024, or whatever you like.
And now, while x is not prime, we just increase that value by two.
So we just selected one arbitrary value, and then if we were unlucky,
it was not prime, we just go to the next potential candidate, and
certainly looking at the next odd value would be increase that value
by two.
Now this could be fine, but the question is, how do we actually
determine whether a value is prime?
The first thing, what I looked at here, was how do I find the largest
prime number less than or equal to n?
Now I say, okay, I just take some arbitrary value, now I have to test
whether it is a prime number or not.
So I have to check whether this is a potential value having no non
-trivial factors.
So the question is, how can we test whether it's prime?
And there actually is a probabilistic method for doing that.
So, this is a very important algorithm, because this has been the
start of a new area of algorithmics, looking at randomized algorithms.
Because, like, primality tests have always drawn some interest, and
probabilistic algorithms always have been very extensive, although for
a long time, it was not clear whether it was possible to find a
polynomial time algorithm for primality testing.
It was assumed that it is not a polynomial time algorithm, but a
polynomial -type problem, but actually, as I will show you a little
bit later, there has been some algorithm just recently, or some years
ago, which shows that you can actually find a polynomial time
algorithm for doing that.
But this probabilistic time algorithm is really fast, and the
interesting point is that the probability that it produces an
incorrect result is marginally small.
It can be made as small as you like.
So, how does this work?
Raban and Miller designed an algorithm where, first of all, you check
the probability for just some initial small value, just take all
primes less than 10,000, check whether your value that you have is
divisible by that value.
You can do that quite fast.
And then, you look like if this did not lead to some prime factor,
that for a composite value, if that value x that you would like to
check is a composite number, very often you find then a value less
than or equal to 10,000 which is a factor of that number.
In most cases, this will already show you that this is not a prime
number.
But if this is not showing you, or giving you an indication that x is
not prime, but a composite number, then you perform the second step.
And in the second step, you repeat at most all times the following.
You choose an arbitrary value that is less than x.
Random value.
Less than x.
It's certainly larger than 10,000.
That's just an arbitrary value.
Until this function, witness of a and x, is true.
Now, what is witness of a and x?
Witness of a and x is a function which is one if a is a witness to the
compositeness of x.
That means if a is indicating that x is not, or showing that x is not
a prime number.
Now, what is this function doing?
Witness of a and x.
Witness of a and x works like this.
If you want to get a witness of the compositeness of x, or a witness
of the non-primality of x.
Now, we know something about prime numbers.
So we know, for example, that we know the theorem by Fermat.
So if x is prime, then a to the x minus one should be congruent to one
modulo x.
So assume that we can show, like we have this arbitrary value a less
than x.
Then we should have the fact that a to the x minus one is congruent to
one modulo x.
If we just compute a to the x minus one, and find out that it is not
congruent to one modulo x, then we would see that, okay, obviously, we
have a witness to the compositeness.
Now, we only know that, so we know that if this is not equal to one
modulo x, then x is not prime.
It does not mean that if a to the x minus one is congruent to one
modulo x, x is prime.
We don't have that indication.
We only have the indication in the opposite way.
If x is prime, then we know that.
But there may be numbers which actually satisfy that equality, or that
relationship, a to the x minus one is congruent to one modulo x, and
they need not be prime.
There are actually numbers like that, so-called Carmichael numbers,
which have that value.
But they are very rare.
And so the idea is, if you just take an arbitrary value here, you
should have that property.
So, how does that work?
We would like to compute a to the x minus one modulo x in order to
find out whether that is congruent to one modulo x, whether it resides
in the value one.
And we know how to compute the power of the value a to the x minus
one.
We look at the binary representation of x minus one, and then do, or
perform fast exponentiation following the scheme where we start with
the most significant value, so we take this value and then perform
successive squaring and modification.
So, how do we start?
The initial value b here is one.
Then we compute what we said is the immediate term t, so b.
And we square this value, take t times t, modulo x.
And if now d is one, so this is essentially what we are interested in,
a to the x minus one modulo x.
We have one such power if d is one.
Now this is something which we have not looked at.
This is a different, or another theorem that we are actually using
here.
What we are finally interested in is whether the final value, after we
have computed a to the x minus one mod x, that final value d, if that
in the end here is not equal to one, we can conclude that x cannot
have been a prime number.
And then that is a firm statement, x has not been prime.
If we don't have, or if d is actually one, so if a to the x minus one
is equal to one, then we return false, we have not found a witness of
the composedness of x, but then we can try it again.
And in the intermediate step we look for a different property which
also holds true for prime numbers, and this is stated here.
If x is prime, and t squared is congruent to one modulo x, then t must
be either one or minus one.
Now this is something which can be derived by methods of number
theory, and the corollary of that is, if you look at that statement,
if t squared is congruent to one modulo x, so this here holds true,
and this here is not true, t is not equal to one and t is not equal to
minus one, then x cannot be prime.
So we just take the contraposition of that, so this is just the
contraposition of that.
So here we have the statement a implies b, and here we have the
statement not b implies
not a.
Contraposition.
So this is exactly the same statement as in the theorem, just written
in this way.
Not b is t is not equal to one and t is not equal to minus one, and
this would imply that x is not prime, or t squared is not equal to one
modulo x, but since we assume that t squared is congruent to one
modulo x, x cannot be prime.
So this is a simple corollary, and this is just checked now while we
are computing those squares here.
t times t modulo x.
Successive squaring of values is performing something like this, where
as soon as we have found a value such that t squared which is the b in
the moment here, is one, and t is not equal to one, t is not equal to
x minus one which is congruent to minus one modulo x, then we have
found a witness of the compositeness of x, a witness of the non
-primality of x, on the way while we are computing a to the x minus
one modulo x.
And if we have not found such a value within that loop here, in the
end we can check whether b is one or not, and we have this value.
And this can be computed efficiently, just computing one this value,
and maybe that on the path already we find such a value.
Then we have at least one such value a, found out whether witness of
ax is true or false, and so if witness of ax is false it does not mean
that x actually is a prime number.
It only means we have not found a witness of the compositeness.
And, yeah, just this remark here, the complexity of primality testing
has been, as I mentioned already, has been an open problem.
And again, an indication of, or another occurrence of this interesting
fact that quite often young students are ingenious in finding new
methods because they are spoiled by standard methods.
And so the polynomial time algorithm has been found by bachelor
students at IIT Cantor, Indian Institute of Technology at Cantor.
This problem having been stated as some assignment in some course on
number theory, and those students found a nice method.
So there are quite a few examples of events like that where unspoiled
students found ingenious, or in an ingenious way, nice results.
So, the probability of a false result of witness ax can be shown to be
smaller than one quarter.
Yeah, you select an arbitrary value, and you can show that the
probability that you get a false result is less than one quarter.
Now if you repeat that, the next choice, the next selection is
independent of the first selection.
Again, the probability of a false result is just one quarter.
And so, repetition of that, we said we repeat that r times, up to r
times, means that the probability of an incorrect result can be made
less than two to the minus two r.
And just increase the number of r, and you have marginally small
remaining probability of a false result.
And so, in this way, you can actually test primality.
This is the important algorithm by Robin and Miller.
It was one of the first randomized algorithms that was applied to a
very significant problem, which was supposed to be very hard before.
And the randomized algorithm, the randomized approach actually led to
quite an improvement in the method, or in the complexity.
And this is something which is done to a large extent in many
different applications.
Meanwhile, randomization is a very important technology or technique
in algorithm design, algorithm engineering.
Which could be the topic of another lecture or another course on
randomized algorithms.
Very sophisticated insights have been achieved there in that area,
proving the way we can actually argue about complexity of algorithms.
Okay.
The remaining question now that we have not looked at is how do we
actually find out those two numbers, c and d, such that c is prime
with respect to the Euler number of n, and the product of c and d is
congruent to one modulo that Euler number.
Is that simple?
Is that difficult?
Well, actually it is quite simple.
The first thing is that we can choose an arbitrary c, which is less
than t minus one times q minus one, and it should be a small value in
order to reduce the complexity of taking m, i, c.
Just take a small value.
And then you need to find that value d.
How can we do that?
The nice thing is that there is a simple algorithm, the Euclidean
algorithm, which you know, like in the initial example for
programming, very often you have the Euclidean algorithm for testing
or finding the greatest common divisor of two values.
Very simple algorithm.
Here we use the extended algorithm.
Somehow, like this, the green is sensitive to touching and also to
using the pen.
If I use both, then the purple also gets, sometimes doesn't know
anymore which one to follow.
I just have to make sure that I get the right touch here on the
screen.
Okay.
Now, what is the extended Euclidean algorithm about?
Here it is.
There is some explanation of that.
In the extended Euclidean algorithm we take two integers, c and e, and
we would like to compute integers x, y, and r such that we find out
the greatest common divisor of c and e.
This is what the normal standard Euclidean algorithm does.
But at the same time, we would like to find out also those values x
and y such that ex plus cy is exactly that greatest common divisor.
Normally, we just look at r.
Why are we interested in those x and y?
So, for our problem, what we are interested in is, that was the
statement we have in the RSA algorithm, for integers c and e, and e in
this case is t minus one times t minus one, the Euler value of the
Euler number of n, and we know that c is prime with respect to e, that
means we know that gcd of c and e is one, so we actually don't have to
compute something here to find out the greatest common divisor.
But if we have that, we would like to find...
our problem is to find a d such that c times d is congruent to one
modulo e.
That's what we are interested in.
We can write that equivalently such that cd minus one is equal to a
multiple of x.
Yeah, that was the definition of cd is congruent to one modulo e, so
cd minus one is a multiple of x.
No, not a multiple of x, certainly also a multiple of x, but a
multiple of e.
Or I could say if I rewrite that, e times minus x plus c times d is
equal to one.
That's the same equation.
And this is what we have written up there.
Yeah, so what we're interested in is this value d, which is the value
y of that result of applying the extended Euclidean algorithm that
we're interested in.
We have to find out what that value is, the value y.
This is the value d that we're interested in in our problem.
Okay.
So, the method that we use for the definition of the extended
Euclidean algorithm looks like this.
We have an iterative approach.
We start with some initial values, have a sequence of values a, x, y.
a0 is e, a1 is c, x0 is 1, x1 is 0, y0 is 0, y1 is 1.
Then we have to compute ui, which is just the floor of the division of
ai minus 1 over ai.
In the first case, that would be e over c.
Take the floor of that.
And then we have to compute ai from ai minus 2 and ai minus 1.
So just take the remainder that we have in the ai minus 1 over ai.
So we just take the remainder of that division of ai minus 2 by ai
minus 1.
And then we have, for xi we have the same type of equation.
For yi we have the same type of equation.
And we can show that we have the following statements here.
These values ai are getting smaller and smaller.
And so if we look at the first index where ak gets 0, and then the
greatest common divisor of this ak minus 1, then is exactly the
greatest common divisor of those values.
This is exactly what is done by the Euclidean algorithm.
And in all the intermediate stages, we have this relationship between
xi, yi, and ai.
E times xi plus c times yi is ai.
That means that if ak minus 1 is that greatest common divisor, then yi
minus 1 is that value that we are interested in.
So the moment where we have ak is 0, we have actually computed the
value d that we are interested in.
And so this is the extended Euclidean algorithm.
It works very fast, so we can easily compute the value d such that
here we have c times d congruent 1 modulo e.
But when I say very easily, very fast, it certainly means division of
quite large values.
E is this product of t minus 1 and q minus 1.
We know that these are very large numbers.
So the numbers that we have here are very long, are multiple worth
numbers, so it is a little more arithmetic, but it is reasonably fast.
So consequently, then if the greatest common divisor of c and e is 1,
then y is the multiplicative inverse of c modulo e and means that y is
the required value of d, what I just indicated.
So this is the RSA algorithm.
The application of that would be to just encrypt messages.
You don't have the problem of key transfer.
You just have to know the public key.
You can encrypt using the public key.
You can decrypt using the secret key.
The secret key need not be distributed.
It must not be distributed.
So the only thing is that you have to get to know the public key, and
we will see later that that still becomes a problem, because you have
to know that this is actually the appropriate public key of the person
that you are sending the message to.
So you have fewer number of keys, you only have k key pairs for k
partners and not k squared and so forth.
The disadvantages are that you have high computational costs, and if
you have only few possible messages, then it is very simple to find
out the plaintext message.
Because, like, if you have only very few messages, m1 to mk, you would
just encrypt them using the public key so we would have p of m1, p for
mk, and if you observe the communication, which is encrypted, you just
check whether one of those encrypted values is communicated, and you
know what the original value was.
Because if you know the plaintext messages, and you encrypt it with
just a small number of values, for example, certain shares and certain
assets in the stock market, if you know the values, like you would
like to find out what are the recommendations, what kind of assets
could you actually buy, and this is kept secret in communication, you
know the possible values can be communicated, you can easily find out
what's communicated if you just use that simple method.
And this looks quite disappointing, because it shows that it's not
that secure, really.
Because you can easily compute those encrypted values, and then check
for occurrence of those encrypted values, and there's no security
anymore.
And how to deal with that will be the topic of next week.
Okay, thank you, that's it for today.