So, good morning.
This is the last lecture of this year for Algorithms for Internet
Applications.
And it is a novel that I am recording this lecture looking into a
classroom where there are not that many people sitting.
So, welcome to those who are here.
Last time we have looked at cryptographic algorithms again.
And we would like to continue with that.
We have looked at the different notions like cryptology separated into
cryptography and cryptanalysis.
I showed you the separation into different areas like symmetric key
algorithms, public key algorithms.
We have looked already at symmetric key algorithms.
I showed you the very simple examples of a Caesar cipher, of a table
cipher, then the Vigenère cipher, one-time pad.
I showed you the encryption with bit sequences which is actually a
standard method for stream encryption.
And like a typical stream cipher where the key, the secret, is in the
seed for the random number generator.
And then we also looked at the notion of transposition, different from
substitution which we looked at up to that point.
We saw that simple example of reading out a matrix in different order
than having written the text into it.
And then we finally looked at the DES algorithm.
I showed you the principle structure, the 16 rounds of the algorithm.
I showed you the essential part, the Feistel encryption around having
the property that it is easily invertible because it is a Xoring
operation.
That's one of the benefits of the Xoring operation that you can easily
decrypt it or invert it by just applying the same operand twice to the
same other operand.
And that way you can retrieve the previous ciphers from ciphers
further down in this algorithm.
And so in this way invert the encryption which means decipher an
encrypted message.
And then we looked in more detail at the Feistel round within DES.
I showed you that there we have these compression permutations for the
key to extract the round key.
We have the expansion permutation for the right half of the block that
has to be encrypted.
And then I also showed you what's inside the S-box, at least in one.
You can easily look up the other ones in the internet or in documents.
And so here we have a way of transforming a 6-bit entry which is
separated into row and column index.
And by looking up the value there which is a 4-bit value and this way
you get the mapping from 6 to 4 bits.
And we also looked at the tags on DES.
I at least showed you some of the results.
Otherwise we didn't go really into details of the different
approaches.
I showed you some hint on where to look for more information on
cryptanalytic attacks.
We also looked at side-channeled attacks like physical attacks to
cryptographic algorithms which just modify the way you actually access
information on what's being done in the algorithm.
And so it is a really hard job to make statements on the security of
an algorithm because you have to consider all these potential side
-channel attacks which is a very difficult task.
Then we looked also at an alternative, at public-key cryptosystems.
I briefly showed you the requirements that we have and one important
part there is the existence of one-way functions which are easily
computed, like one-way, but the inverse is hard to compute.
I gave you simple examples and the first new slide for today is the
RSA cryptosystem which I showed, which is the standard algorithm for
public -key methods.
There certainly are others around.
I will briefly mention them at the end of today's lecture.
Or within this lecture today.
So what is this algorithm about?
The RSA cryptosystem designed by Rivis, Charmy and Edelman in 1978.
So they have a public key, P for public, which is a pair of integers,
n and c, where c stands for code.
There is a secret key, S, which is again a pair of integers, so the n
is not really the secret, but the d is the secret.
And d stands for decode.
C and d are values which are very large numbers.
They have at most as many bits as n and the standard lengths of this n
are a few thousand bits nowadays.
The RSA encryption works the following way, that you have your message
and you chop your message into segments, which are all less or equal
than n.
And so this is then m1, m2 and so on.
So you have these sequences of blocks smaller than n.
And actually not less or equal, but actually smaller, really smaller
than.
So the operation that you perform now is a numeric operation.
You compute mi to the c modulo n.
So you compute, mi is a value which can be almost as large as n, which
may have a few thousand bits.
And c is a value which can by itself have a few thousand bits.
And so you can imagine that that is a really time-consuming operation
to compute mi to the c.
And so you really have to do something about making that as efficient
as possible.
And then you always compute in the range of numbers less than n,
because you computed modulo this value n.
Now this is the encryption.
You get some new value which again is a value that is less than n by
the modulo operation.
And then the decryption works in a way that you divide the encrypted
message c again into sequences of numbers c1, ck smaller than n.
And you compute mi now from this ci by taking ci to the power d modulo
n.
And again we have very large numbers, may have very large numbers,
certainly not all of these numbers will be large, but most of them.
And so this is a time-consuming operation, violating in some way the
requirement that encryption and decryption should be easy.
So how can we choose, like this looks a bit strange, how is that
possible that you can retrieve the value mi by computing the power of
the original mi to the c and then the result taking the power to the
d.
Now this works because we specifically choose n, c and d.
And so certainly here I say for n having 1024 bits, but this certainly
can be any other value also.
This is just one assumption.
Nowadays you would rather have 2048 or even 4096.
So this is a 2 there.
Now what do we do?
We randomly generate two large prime numbers p and q.
Both having, like if we have 1024 bits, we choose two numbers having
512 bits.
In this way the product has exactly double the number of bits.
And so we want to have that many bits, so the two prime numbers should
be very large.
We will come back to the problem of how we can actually select those
prime numbers.
Now we compute the product of those prime numbers.
This can be done certainly by standard arithmetic, although then it's
quite time consuming.
It should be done more efficiently.
And the product of p and q is our value n.
You see, if you just have n, you actually don't know p and q unless
you manage to factor that number n into those two prime factors, which
I already mentioned is one of those one-way functions.
Now we determine randomly one value c, but the requirement is that c
is prime relative to p-1 times q-1.
I will explain to you in a moment why we have that requirement, that
value p-1 times q-1.
And then we determine a value d such that the product of c times d is
congruent to one modulo p-1 times q-1.
And we have the following lemma.
If we have chosen n, c, and d in this way, then we have for all values
less than n this nice property that m taken to the power cd is
congruent to m modulo n.
And we will go into a little bit into showing why that is the case.
We don't go into the complete depth of that proof.
But first of all, let's briefly look again what actually it means to
say x and y are congruent modulo z.
What does it mean?
That the difference of x minus y is a multiple of z.
So it means that the difference here, the difference of m to the c
times d and m is a multiple of n.
And up here, cd-1 is a multiple of p-1 times q-1.
So this is the essential point.
Or you could also say if you divide the values x and y by z, then you
have the same remainder.
Okay, now the validity of that lemma depends on two essential insights
of number theory.
The first one is the small or the little theorem of Fermat.
And this little theorem is about the following.
It states that if you have a prime number p and another value a which
is not divisible by p, then a to the p minus 1 is congruent to 1
modulo p.
Now this looks similar to what we have up here.
We'll come back to that.
So p prime a not divisible by p means a to the p minus 1 is congruent
to 1 modulo p.
And then there is a generalization of that, which is the following.
For n out of n, we define the following function phi of n, which is
called the Euler function.
And this Euler function counts the number of values m between 1 and n,
which are prime relative to n, which means that they don't have a
common divisor with n.
We'll look at specific examples of that in a moment.
So this is the Euler function.
And the theorem that we utilize for this proof of the correctness of
the RSA algorithm is that if n and a are natural numbers and a is
prime relative to n, that means they don't have common divisors, non
-trivial common divisors, then a to the phi of n is congruent to 1
modulo n.
So another statement like the one we had in the little theorem of
Fermat, but here it states, or it is not a to the p minus 1, where p
is a prime number, but here it is a to the phi of n, which is the
Euler function of that value n.
Now, assume that this little theorem of Fermat and Euler's theorem
hold, then we will show that the RSA algorithm actually is correct.
The corollary of this certainly is that for all a and n, a to the phi
of n minus 1 is the modular inverse of a with respect to n.
Yes, so if you have modular computation for n, then a to the phi of n
minus 1 certainly is the modular inverse, because a to the phi of n
minus 1 times a is congruent to 1 modulo n.
So that's trivial.
Okay, nice little corollary which will be used.
Okay, and now let's briefly look at our situation where we have these
two numbers p and q.
These two prime numbers p and q.
And you know we have computed n, which is the product of p and q, and
now the statement of this lemma is that the Euler function of p and q
is just this value p minus 1 times q minus 1, which also appeared in
the construction of the public and secret keys.
So why is this the case?
This is a rather simple observation.
If p and q are prime, then we can easily see which numbers have a
common divisor with p and q, so which are not prime relative to n.
So which numbers are these?
Well, it's just the multiples, all the multiples of p and all the
multiples of q.
They definitely have a non-trivial common divisor.
In particular, these values here have a non-trivial common divisor p,
and those here have a non-trivial common divisor q.
So how many numbers are these?
Here we have just definitely q values.
Here we have p values, so we have p plus q values there.
p plus q minus 1.
You see here only up to p minus 1.
So this is the number of values which have a common divisor with p
times q, so all the remaining numbers are numbers which are prime
relative to p times q.
So what is that?
p times q are all the numbers, and we subtract p plus q minus 1.
And these are the numbers which are smaller than p times q and have
non -trivial common divisor.
And this is exactly p minus 1 times q minus 1.
So this is easily computed, certainly.
So this is the number of integers which are prime relative to p times
q, which is our value n, the modulus for the RSA computation.
Now, let's go back to the RSA algorithm and see what this means for
getting insights into the correctness of that algorithm.
So if p and q are prime, we now know that the Euler function is p
minus 1 times q minus 1.
Thus, if we multiply, or if we compute m to the p minus 1 times q
minus 1, this is m to the phi of n, this is congruent to 1 modulo n
due to the result from Euler's theorem.
Now, certainly if we multiply both sides with m, then m to the p minus
1 times q minus 1 plus 1 is congruent to m modulo n.
Now, it would be nice if this here actually would be in some way, or
could be related to c times d, because remember that was what we were
looking for, some exponent to m such that m to this exponent is
congruent to m modulo n.
Now, we have chosen c and d such that c times d is congruent to 1
modulo p minus 1 times q minus 1, the Euler function of n.
Now, this is exactly the same as stating that cd minus 1 is a multiple
of that modulus.
So, a multiple of p minus 1 times q minus 1.
There exists a k such that cd minus 1 is k times that modulus.
And now this means, if we compute m to the c times d, this c times d
is, well, a multiple of p minus 1 times q minus 1 plus 1.
And a multiple of p minus 1 times q minus 1, each multiple of p minus
1 times q minus 1 in the exponent of m is, as we have stated here,
congruent to 1.
So, all these cancel out.
The only thing which remains is that m to the c times d is actually
congruent to m.
And so, this is what we wanted to have.
And so, we have shown this is actually a correct algorithm.
And the interesting point is that even if m is not prime relative to
n, so this was the requirement here, m is prime relative to n, now we
assume that m is not prime.
We know that there are p plus q minus 1 values which are not prime
relative to n.
What happens to those values?
Let's assume we have a value m which is a multiple of q.
Now, if we, like t definitely is less than p, and so t is prime with
respect to p, and so t to the p minus 1 is congruent to 1 modulo p
because of the little fama, and also q to the p minus 1 definitely is
congruent to 1 modulo p.
Now, we can compute, we can look at the product of those in a moment.
So, we also know that for all k greater than 0, we have that t to the
k times p minus 1 times q minus 1 is definitely also congruent to 1
because it's just a repetition of what we have seen up here.
And also q to the k times p minus 1 times q minus 1 is congruent to 1
modulo p because this is also a repetition of what we have seen up
here.
And that means if we compute, if we now form the product of those
values, t to this power and q to this power, if we take t times q to
the power k times p minus 1 times q minus 1, we get that that is
congruent to 1 modulo p.
And it's also, if we multiply it with t, it is congruent to t modulo
p.
And now we can also multiply that with q, and an easy check with the
modular arithmetic shows that the product, if we now multiply with q,
then here we have multiplied this power of tq with t times q, so we
have t times q to this power k times p minus 1 times q minus 1 plus 1.
This is t times q, congruent to t times q modulo p times q, and this
is exactly what we wanted to have.
So this shows that even for m, we have this nice relationship that we
can retrieve m by taking it to the power c times d.
So this certainly can be done in an analogous way for all multiples of
p, here this was a multiple of q.
Okay, now we have shown that for all values less than n, we have this
nice property that m to the c times d is congruent to m modulo n.
And we are done with the proof of the correctness.
So let's look now at the efficiency of that algorithm.
What are the costs of the RSA algorithm?
Encryption and decryption, as you have seen, use exponentiation.
We certainly have to do that in a fast way.
Now the problem is, what does it mean if you do it in a naive way, if
you have to compute x to the n, you could say, okay, I just take x
times x times x and so on times x, and this n times, and this
certainly would be n times the effort to multiply two numbers with
increasingly larger numbers.
Now, the interesting observation is that for all x and n, we can
compute x to the n with order of log n arithmetic operations.
The method, the easy method, as we'll see on the next slide, is that
we just continuously square x and multiply the computed powers.
So let's go to the next slide.
And there, now we look at the details of fast exponentiation.
So x is an arbitrary integer, and n, we want to compute x to the n, is
also an arbitrary integer.
And an integer can be represented as a binary number.
So we just represent it as a sequence of like n as a k, a k minus one,
down to a zero.
Now, this is the dual representation or the binary representation of
n.
And if we now compute x to the n, it means that we take x to a sum of
powers of two, which are weighted by these ai.
So that means the ai select the powers of two that are actually needed
here because ai are either zero or one.
Now, if we take x to a sum of values, we can also compute or rearrange
this as a product of powers of x, which are just these x to the ai
times two to the i.
And it means that we now can do exactly what I told you.
We can successively square all the, like square x, certainly to get up
to two to the k, the largest power that may be contained in, or that
is contained in n.
We just need k operations, and k certainly is equal to log n.
Actually, the ceiling of that, no, sorry, floor of that, but it is
order of log n.
And so these are the powers that we need.
And so this was supposed to be k.
And the ai are used to select which powers of x actually have to be
multiplied.
So if ai is zero, this cancels, such a power cancels out.
And those where ai is one are multiplied.
And so this is a simple way of squaring and multiplying with some
intermediate value to get in the end the appropriate product of x to a
powers of two.
Now a different way of representing that would be that we just
rearrange the computation and say, okay, we can also just take x to
the a0, x to the a1, x to the a2, and so on, and actually start here
with x to the ak and square that.
And then multiply with x to the ak-1.
That means if ak-1 or some ai is zero, it is multiplication with one,
which means you don't have to multiply.
If it is one, we have to multiply with x.
And so here we would decide whether we have to multiply with x, and
then we square the resulting value.
And this is exactly the same result as we have up here, so those two
are equal, and immediately shows that we have two different ways of
computing this power x to the n.
So one way would be to start from the least significant bit and go to
the most significant bit of n, so start with a0.
This is what we do here.
And then go to a1, a2, and so on.
And this is what we do in this way, so this is right to left
computation with respect to the ordering of this direction with
respect to the bits of n.
And if we decide for this algorithm, we would start with the most
significant and go to the least significant bit, which means there we
go left to right looking at the bits of n.
And so this is here actually in this formula, we start, we go from
right to left, but referring to the ordering of the bits in the binary
representation of n, it is right to left or left to right.
Least significant or most significant, or most significant or least
significant.
The complexity of both operations is, of both algorithms is the same,
but the arrangement, the way we compute is slightly different.
So we have successive squarings and we have to decide what we do with
the value of those bits of n.
Okay, let's go back to the previous slide.
Here we have to look at what that means for the costs, so we have to
perform multiplication, squaring.
Now we have long integers, the values that we have here have several
thousand bits, or at least a thousand, usually a few thousand bits.
Now this means that our standard arithmetic is not sufficient, we have
operations on long integers.
So if this is the large number, we have to chop it into our root size,
so maybe 32.
If you are lucky you have a 64-bit computer, then you have 64-bit
values, but still this is not sufficient.
So if you have 1024 bits in your number, you need 32 words in that
value, so it will represent 1024 bits.
Okay, so if you just perform naive multiplication, you have order of k
-square single word operations.
That's simple, naive matrix multiplication.
Not matrix multiplication, this is number multiplication.
Now, if you do it in a slightly more efficient way, you use a
recursive approach and you can take that complexity down to k to the 1
.5.
It's an easy exercise to try to do that.
And if you are even more knowledgeable, you would use FFT, the Fast
Fourier Transform, which I don't cover in this course, but in my
course on efficient algorithms.
This FFT approach for multiplication actually leads to a reduction
down to k log k operations on long operations.
So here the approach is that if we have k word integers, that means k
words which make up one value, this is showing the complexity of that,
order of k log k.
Now what does this mean for specific values?
If we have 32-bit arithmetic, an exponent length of 1024 bits, that's
the length of n for the exponent.
Now the exponent is n.
It means that... so actually the number of operations that we have
here, the order of log n it states, it's 2 times log n actually.
And now log n for a 1024-bit value is 1024 bits.
So it's 2 times 1024 operations, and now each operation takes k log k
single word operations.
Now that is k, in this case is 32, and log k is 5, and this product
is, as you see here, 327,680 operations.
Now this is a rather naive approach to do it in this way, although we
already have used here intelligent multiplication, but nevertheless it
can be done in a different way.
You can actually use modular arithmetic, you can use the Chinese
remainder theorem, you can use parallelization, pipelining, construct
a hardware implementation of that algorithm.
Would be a pleasure for me to tell you more about that, but we don't
have the time for that, not in this course.
But in this way you can achieve RSA encryption at quite high data
rates, but nevertheless the costs are still quite high, and so usually
RSA is viewed to be too large to be used on large amounts of data.
The costs of RSA are just too large.
And so we have to do something about that.
At first sight it would mean, well, you don't use RSA at all on the
documents that we would like to communicate, but you will see a little
bit later how we actually get around that.
So we just have to combine RSA with other cryptographic methods which
are computed in an easier way.
Now let's look at how we can disperse fast exponentiation, which we
have looked at already.
Again, let's look now at the cost of cryptanalysis.
The first was the cost of computing the encryption and decryption.
Now what about cryptanalysis?
I briefly mentioned that factorization is a one-way function.
So the problem that we have to look at here is that we are given N, we
are given C, and we would like, like this is the public key, and now
you would like to get P and Q from that.
Now this requires factorization of N, and I mentioned already that it
is a very complex operation, so the currently best-known methods are
in complexity around what I have stated here.
And so B is the number of bits of N.
You see that here you have that in the exponent of E, and then you
have also log B in there.
This is quite a large value, and if you assume or make certain
assumptions on the speed of your computer, and if you just assume that
N is a number having 300 decimal digits, then in a naive over-the
-thumb computation, you get something like a few thousand years to
actually compute the factorization regardless of which number of that
size you have.
Now this is at least true with respect to current knowledge.
There may be some advances in algorithmics which might give us new
insights on how to compute factorization.
In particular, we know of one insight which is valid as soon as we
have quantum computing.
And so if you have a quantum computer, you can actually get
factorization in a very simple way, and this certainly is some kind of
threat to the security of everything which is encrypted using such a
public -key method like RSA.
But to do something against that, if you are interested in having
security over a long period of time, we need very long keys, much
longer than for symmetric methods, because here, as I said, the
strength of the algorithm, the cryptographic strength, depends on the
complexity of factoring the numbers.
And so these have to be very large numbers, whereas for the symmetric
methods, we had other problems that had to be looked at in order to
successfully attack these symmetric methods.
So there the keys could be smaller.
Okay.
One question is, we need these prime numbers.
How do we do that?
How can we actually determine large prime numbers?
So we have to find the largest prime number less than or equal to some
value n.
Like I said, we would like to have prime numbers having 512 or 1024
bits, and so 2 to the 1024 would be that value.
Now one simple method is the sieve of Eratosthenes.
So there we just write down all numbers from 2 to n.
Let me just do that.
22, 23, 24, 25, and so on.
Now, what is this for?
So up to n, so here I can only write down a few numbers, but you just
can see in a moment what the approach actually is about.
Then we repeat the following.
We delete the first number, which is 2, and all its multiples from the
list.
So we delete 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, and so on.
So we delete the first number and all its multiples until the list
consists of a single element.
So we repeat that.
We delete 3, its next multiple is 9, its next multiple is 15, next
multiple is 21, next multiple is, well, not on this list.
We do the same with 5.
We delete 5 multiple.
There's 25.
We delete 7, and see there's no multiple of 7 on this list.
We delete 11, and see there's no multiple of 11 over there.
We delete 17, we delete 19, we delete 23, and so on, and all their
multiples.
And in this way you see that the list is reduced quite fast to fewer
elements, and the largest remaining value on the right-hand side
certainly is the largest prime, which is less or equal to n.
Certainly you only have to go to half the size of the list.
Okay, you don't have to go all the way to the right.
So it is quite an efficient algorithm, but if you imagine you have 2
to the 1024 values, that's a very, very long list and it's still just
unfeasible to do that.
So if you have these large numbers, it's unfeasible.
And so another approach is to use a probabilistic approach.
We just choose a random odd number having 512 bits and test whether x
is prime.
If it is not prime, we just increase x by 2.
Certainly we only have to look at odd numbers.
And then we test it again, and we do that until we finally have found
the next prime which is larger than x.
Now this sounds as being much simpler because there will be some
value, some prime number in that region.
And if we are lucky, the first one is actually a prime number.
But then the question remains, how can we actually test whether x is
prime?
And this looks like an interesting question.
So how can we test whether x actually is prime?
Like in that sieve of Eratosthenes, we knew that the remaining values
were prime because they have not been multiples of any smaller value.
Now, there is a very interesting approach.
It was a seminal paper by Rabban and Miller, and they designed one of
the first probabilistic algorithms by just doing the following.
They first of all checked whether x is divisible by some small prime,
so less than 10,000 for example.
If you have just 10,000 values, you can easily do that using the sieve
of Eratosthenes.
And then you repeat at most r times, so this is a limit on the number
of iterations, you choose a random value less than x until this value
a is a witness of the compositeness of x.
Now, what does it mean?
If a is a value which can show you that a is not a prime number but a
multiple of a smaller value than x.
So, we would like to test whether x is prime, so if we stop by having
found a value a, which is a witness of the compositeness of x, then we
know x is not prime.
If we have repeated that r times without having found such a witness,
we conclude that x must be prime.
Now, this is quite a courageous statement, we will see later that it
is done or is made on quite good grounds.
So, what is this algorithm actually doing?
How can you say that you have a witness for the compositeness of x?
What do we do?
We just exploit again our insights that we had seen before.
The little theorem by Fermat that if x is prime, then a to the x minus
1 is congruent to 1 modulo x.
We have seen that little theorem of Fermat already.
Now, we would like to test whether x is prime, and we know that if x
is prime, then we have this property.
There is another theorem, another insight from number theory, that if
x is prime, and if t square, just some value t, t square is congruent
to 1 modulo x, then t must be 1 or minus 1 congruent to x.
Now, that means if we take the opposite of that, so if we say, okay,
this is statement A, from A we conclude B, now here we just draw B,
not B, then implies the contraposition.
That is, not B implies not A.
So, if t square is congruent to 1 modulo x, and this here does not
hold, that means t is not congruent to 1, and t is not congruent to
minus 1, then x cannot be prime.
Okay, so what we would like to compute, the other thing is that if A
to the x minus 1 is not congruent to 1 modulo x, then x cannot be
prime.
So, those two properties, those two contrapositions actually are used
in this algorithm by Robin and Miller, and to compute this witness
function.
So, the idea is to compute A to the x minus 1 modulo x.
We know this should be 1.
If it is not 1, we know x is not prime.
And on the way to that, we check whether we get values which are
actually congruent to 1 modulo x, while t is not equal to 1 and t is
not equal to minus 1 or not equal to x minus 1 modulo x.
x is not prime, we know that.
So, we compute that value, we start with some value 1, this is our
value t, you see here we have, there we need a value t, this is the
intermediate value.
We compute t and d now is the square of t modulo x.
So, here we have t square, which is d, and there we look at t.
So, now we have t and t square, certainly modulo x.
And if now d is 1, this is this test, if d is 1 and t is not equal to
1 and not equal to x minus 1, this is this test, then we know that x
is not prime, we return true.
That means we have found a witness for the compositeness of x.
Otherwise, we have to continue with our computation of a to the x
minus 1 mod x.
And if now ai is 1, you see here we start with k, go down to a0, that
means we start with the most significant bit, go down to the least
significant bit of our power x minus 1.
So, ak to a0 is the binary representation of x minus 1.
And so, if ai is 1, you know that we have to multiply our value d,
which we just have computed, we have squared.
Now we have to compute it, or we have to multiply it with a.
And in this way, that means we multiply with a to the ai mod x.
That's it.
We just repeat this.
So this is the block here, the inner block of that for statement.
So this is just repeating this computation, successive squarings and
multiplications with a, and in this way we compute a to the x minus 1
modulo x.
Now, if the result d, if we did not jump out of this by returning
true, then we check whether d is actually 1 or not.
If it is not equal to 1, then if this is not equal to 1, we know that
x cannot be prime, we return true.
If it is equal to 1, we return false.
Now, the property that a to the x minus 1 mod x is equal to 1 or
congruent to 1 modulo x does not imply that x is prime.
We just have found in that case, or it may be that we have some value
which has this property without being prime.
Now, there are some rare numbers having that property, and they are
really rare, and we come back to that in the next slide.
Another interesting experience or interesting result is that, or
information, is that this problem of determining the complexity of the
primality test, this has been an open problem.
People did not know whether it is actually a polynomial algorithm or
whether it is an NP-complete problem.
And in 2002, so 12 years ago, the first polynomial time algorithm has
been presented.
And this was remarkable in particular because this algorithm was
designed by students like Professor Agarwal at the IIT, the Indian
Institute of Technology in Kanpur, and two of his students at the
bachelor level.
They just got an assignment where they had to solve a small problem
with respect to number theory, and they actually designed a polynomial
time algorithm for testing primality.
Remarkable, but things like that happen again and again that people
who are not aware of all the interesting theories around an open
problem just have an intuition which leads to a new algorithm.
So, it is a polynomial time problem.
Still, it is expensive, but this algorithm here certainly can be
executed very fast.
So, to compute this iteration is done very fast.
We just have to do that r times, which we can determine beforehand.
Now, the question is, how do we determine that?
How often do we have to repeat that choice of a random value a less x
before we actually can be sure that we have a prime number?
So, the probability of a false result of witness AX, that means
witness AX returns false, but the value is not a prime number.
This probability is smaller than one quarter.
Now, if we repeat that several times, and since these choices are
independent of each other, the probability of a false result of the
Rubin -Miller test, since we repeat that r times, is one over two to
the two r.
Now, this easily gets down to a very, very small probability.
And so, even with a few repetitions, you have a very high probability
than the result that x is actually a prime number.
So, it is a suitable, fast, and sufficiently secure method for
generating prime numbers.
So, as I said, you select a random number with appropriate number of
bits that you are interested in, and then you repeat that test until
you finally have found a number which is, according to that test, a
prime number.
Another question is, we now know how to determine a prime number, so
we can compute p times q, and now we have to find c and d.
So, how do you find those?
So, to find c is not that difficult.
You just take c' with respect to p-1 times q-1.
You just take some prime value.
You can actually choose a not-too-large integer, because this is for
coding, for encryption.
And so, this should be a small number.
Not too small, but you have a choice of just taking any number there.
Any prime number less than n.
Another question is, how do you actually get d?
With this property that c times d is congruent to 1 modulo the Euler
value of the product p times q.
So, the answer is that you use the extended Euclidean algorithm.
Now, you know the Euclidean algorithm, which is the algorithm, the
simple algorithm for determining the largest common divisor of two
values.
So, you test whether the greatest common divisor of c and p-1q-1 is 1.
This is the Euclidean algorithm to test whether two values, x and y,
have only a trivial largest common divisor.
The interesting point is that we use an extended version of that.
So, in the simple version, you just get this answer, well, they are
prime with respect to each other or not.
But, in the extended version, you actually get more.
So, in the extended Euclidean algorithm, what you compute is, for
integers c and e, which you are interested in, so here c and e, you
compute integers x, y, and r, where r is that value.
So, you compute those integers x, y, and r such that e times x plus c
times y is equal to r, the greatest common divisor.
So, this actually gives you the desired result.
If r is 1, you have that e times x plus c times y is equal to 1.
Now, for our problem, it means we take, like c is our prime number,
which we have chosen for the public key, and now e is just this Euler
value of n.
So, the problem is, we look for some d such that c times d is
congruent to 1 modulo e, or we can rephrase that and say that we look
for some value, or we are interested, or we look for some x such that
cd minus 1 is a multiple of e.
That's what we said is like x is congruent to y modulo z if that
difference is a multiple of z.
And here we have c and d and 1.
The difference is a multiple of the modulus e, or you could say e
times minus x plus c times d is equal to 1.
Now, this is exactly what we stated there with respect to e times x
plus c times y equals to r.
Okay, so if we have, if this extended Euclidean algorithm delivers us
x and y, then we have exactly what we need.
We have then found such a value d.
Okay, and so this d is then, as I said, the d is then this value of x
that we, no, sorry, this value of y that we are interested in.
y is what we look for, that will be our d.
Okay, now, what is this method doing?
It is an iterative algorithm.
As you know, the Euclidean algorithm is a simple iterative method.
And so we have that schema, which is indicated here.
We start with e and c.
We have some intermediate values x0, x1, y0, y1.
And we have some quotient qi, which is the integer, use integer
division, ai minus 1 over ai, ai minus 1 over ai, a0, a1 are e and c.
So we compute e over c, we divide e by c, and then take the integer
value.
Then we also look like here, ai minus 2, no, sorry, ai, then is ai
minus 2 minus ai minus 1 times qi minus 1.
And so a2 in this case would be a0, e minus ai minus 1 times qi minus
1, in this case would be just the remainder of that value qi, which is
the integer quotient of e over c in the initial round.
And then we continue that, we just compute the appropriate, here some
appropriate differences, continue that and iterate until the smallest,
or until this ak actually is 0, you remember that from the Euclidean
method.
And then we know that the previous value of that a sequence, ak minus
1, is the greatest common divisor, which certainly should be 1 in this
case.
And we also have for all intermediate values that e times xi plus c
times yi is ai, and so the yi minus 1 would have been the value d that
we are interested in.
And so then if the greatest common divisor of c and e is 1, then y is
the multiplicative inverse of c and modulo e, this is the y in this
statement here.
c times y is congruent to 1 modulo e, that's what we wanted to get.
So this is the simple extended Euclidean algorithm, so you see that c
and d are easily computed as soon as we have computed n, which was
based on the determination of two large prime numbers p and q.
Nevertheless, when I say this is easily computed, we still have all
the operations here are operations on large integers, so they are
expensive.
So y is the required value of d, as I said, and if we apply the RSA
algorithm, certainly we can use it for encryption of messages,
certainly the asymmetry avoids the problem of secure key exchange.
We don't need n squared, like if we have our n partners who would like
to communicate, for every communication that we have here, we don't
need to construct keys for every line in that complete graph here.
These n square keys, but here every person only needs a public key,
and everybody can use the public key to send an encrypted message,
which only the recipient can decrypt.
And so here we only need n public-private key pairs.
So this is much better, and the disadvantage certainly is that the
cost for encryption and decryption is quite significant, and so we
have to consider that.
Another problem is that it is easily broken if you only have few
possible plain text messages.
Why is this the case?
Assume you have somebody who is taking care of a certain, like has a
certain number of values in a bag, and he wants to draw a certain
value, and then send the result to his friend, and this friend would
like to know, and somebody else, you know, Alice, Bob, and Eve.
Now, Eve would like to know what the selection actually is.
Now, she might know that in this box there are values, let's say, A1,
A2, and so on, up to AK.
K different values.
Now, if these are K different values, potential names of participants,
for example, in some draw or whatever you would like to do, maybe you
would have to decide for buying certain assets on a stock market, or
you can easily imagine other situations where you have only a limited
number of plain text messages which are known to Eve, but she doesn't
know which one of those actually is selected.
Now, what she can easily do is, she can just, like Eve can do the
following, she just takes the public key of Alice, no, of Bob, and
like assuming that A will use this algorithm, like use Bob's public
key to send the result of her draw, Eve just computes, uses Bob's
public key, computes PB of A1 down to PB of AK, and then since Alice
will send the encrypted value of some AI which she has chosen, Eve
only has to look at the encrypted values, which can easily determine
which one of those has been selected, because she does not have to
decrypt, she only has to know which message actually has been sent,
and since this is a limited number of messages that can be sent, she
can easily find out what the information is that has been transmitted.
So this is an important insight that you have to be very careful how
you apply such a public key method, because you have this public key
which is used for encryption.
So we have to do something about that.
Whenever you have a limited number of potential alternatives which
have to be encrypted, you can easily circumvent the problem of having
to decrypt the message.
Then there are some alternatives to RSA, which to some extent also
have these problems as all the public key methods, like alternatives
with respect to public key methods, which I don't have the time to go
into more details.
So Diffie-Hellman is a typical algorithm for exchanging keys in a
secure way, like keys for symmetric methods, and elliptic curve
algorithms are another approach to having public keys, and there
actually the length of the keys can be significantly smaller than with
the RSA or Diffie-Hellman algorithm.
So maybe I should include that in future editions of this course.
But I at least wanted to mention that these are practically relevant
algorithms, in particular the elliptic curve algorithms are very
important for secure encryption and decryption, particularly if you
have to perform something like digital signatures and so on, which
will be one of the next topics.
So what we're interested in is secure key exchange for symmetric
methods, because that could be one application of our public key
methods.
But first of all, let's try to find out how could we actually exchange
keys for symmetric methods in a secure way.
So, without making use of public key methods, you could just agree
upon a general key, G, and you have some way of agreeing on that by
phone, by letter, by courier, or whatever you have as a method for
secure communication, a general key.
And then you can transmit that by phone, by letter, by courier, or you
just transfer some segments, so if this here is your value, a simple
way of choosing segments would be to do something like that.
A more sophisticated way would be to just perform some selection, so
just take certain parts of that value and then have some pattern how
you select the keys into those G1 to GK, and then you just have to
know that function for getting the value G from those segments that
you have sent.
So this is some standard approach.
So what you could also do is, for example, you have your value G, you
could also just add some random value, and then you transmit G plus
that random value, and if you know the random value, you can retrieve
G.
If you don't, you don't get it.
But then, again, you have to recombine that R.
So there are methods, there are interesting methods around those
topics.
We'll come back to that a little bit later.
So this would be a way of transmitting some key, and then what you
could do is you just use a new random session key for every exchange
of messages.
And the message M is encrypting using that session key for the
symmetric method, and this session key is encrypted using your general
key, so you have your previously transmitted general key, and then you
only exchange encrypted session keys.
The session keys are used only once, so you cannot perform any of
those typical attacks where you have a range or a collection of
messages which you just try to get encrypted and then analyze what
happens to those messages in order to find out something about the key
that has been used.
If it's just used once, there's no way how you can actually perform
those attacks.
So G is used for short messages only, only for session keys, and S is
used for one message only.
And now certainly an alternative to this scheme would be that you
don't use that general key, but you use asymmetric methods for key
exchange.
So it is definitely an improved protection against cryptanalytic
attacks, and now we transfer that into using public key methods for
key exchange.
So Alice and Bob are wanting to communicate, and Alice would like to
send a letter, and what she can do is she chooses a new session key
for every exchange of messages.
So she selects some random key, she encrypts the message, so now you
have the encrypted message which can only decrypt if you have that
session key.
She has to send that session key to Bob, and she does that by just
using Bob's public key, so the public key of the receiver using some
asymmetric method.
You could use RSA, but also some other method, elliptic curve, or
whatever you like.
And then send the encrypted message together with the encrypted key,
which means that in some way you have a sealed envelope where the key
is put into, and Bob certainly knows how to open that envelope,
because Bob has his secret key, which is used to retrieve the session
key, so he can use that, his secret key, get the session key, and then
he can retrieve the message that Alice has sent.
So this looks like a nice combination of asymmetric and symmetric
methods, because the public key method is only used for encrypting
those short keys.
Certainly short key means something like 128 or 256 bits.
And then the message is encrypted using a symmetric method, which is
done fast.
So this looks like quite a nice approach.
So you don't have the need for secretly transmitting some general key,
as I mentioned on the previous slide.
The high cost of RSA certainly are tolerable for short session keys,
and every key of the symmetric method is used only once, which is very
important.
This definitely increases the security of those messages.
Okay, what's the problem?
So this is almost the method that is used extensively in our secure
communications, for example, in HTTPS and so on.
It's exactly that scheme that is used, but almost, not quite.
What's missing?
The problem is that there might be some man in the middle.
So this would be, in this case, Edgar, the man in the middle.
And if the public key would not be... Alice assumes that the public
key is PB, Bob's public key.
But if that is replaced with the public key of Edgar, this man in the
middle, then Edgar could retrieve that message, modify it on its own
discretion, because he has his secret key to get the session key and
decrypt the message and modify the message and so on.
And then he will send it on using the public key of Bob, and Bob can
decrypt that message.
So that would be an attack, which is quite simple.
And it shows that we need some knowledge about or some statement on,
is that actually a valid public key of the recipient?
Okay, we'll come back to that problem in a moment.
I used to present another symmetric method, the method IDEA, which is
an interesting method.
It was designed at ETH in Zurich, but I don't have time to do that, so
I will just go over that.
Without covering it, you are welcome to look at those slides, but this
will not be relevant for the final exam.
And I rather would like to show you which other internationally
accepted encryption standard is used.
Meanwhile, I mentioned that DES is not the choice.
I did not present IDEA, so I present the Advanced Encryption Standard,
which is the result of a competition, as I mentioned already, to find
a successor for DES.
This was done in the last years of the 19th century.
And there were several finalists.
So here are those five finalists.
And one, actually, Reindahl, was the one which was selected, designed
by Joan Damon and Vincent Ryman.
And so that's how this name, Reindahl, actually appeared.
Now, it's now only known under the name AES, Advanced Encryption
Standard.
You can find a lot of information on that standard on the pages of the
NIST institution in the United States.
And you can also find publicly available codes in different languages
for actually using that AES.
So you can download the algorithm and use it.
The information on the next slides is from the official specification.
And the official specification by those two scientists was a little
bit more general than what was actually put into the standard.
The standard, under the acronym FIPS 197, was published in 2001.
And that's what I use in the presentation of Reindahl in the following
slides.
So, Reindahl has two essential parameters, Nb and Nk, number of
blocks, like that's the block length Nb and the key length Nk.
And you see that the block length means it certainly is a block
-oriented encryption.
And so if Nb, like that, can have the values 4, 6, or 8, and Nk can
have the values 4, 6, and 8, and this results in certain parameters in
that table, what does it mean to have Nb equal 4?
Nb equal 4 means that we multiply 32 by that number Nb.
So if Nb is 4, like 32 bits, now 32 is exactly 4 bytes.
So this is 4 bytes and this is repeated 4 times.
So this is the block length for Nb equals 4.
And in the FIPS 197, we only have Nb equals 4.
Now, this is now the standard, but the algorithm in principle could
also be applied to having something for Nb equals 6 or Nb equals 8.
So, not just 128, but you could also have a block length of 192 or
256.
Now, the key length can be variable, so you can use that either with
128, 192, or 256 bits, so quite a large number of bits for the key.
And so this certainly has implications on the strength of the
algorithm.
And so this is the array of bytes for that key.
And this, as we had for the DS algorithm, we again have a number of
rounds.
So the number that you see in there, for example, for Nk equals 6 and
Nb equals 4 would be 12, which means that we have 12 rounds of
encryption.
And so every round has the following structure.
The state means this is a variable for the current value of our block,
so these four blocks of these four columns of four bytes.
And that's the state.
And then we have the round key, which is some number of some matrix
again.
And what we do is the following.
We modify the state in some way by byte substitution.
We shift the rows of the state, we mix the columns of the state, and
then add the round key to the residing state.
So we modify this state, the current intermediate cipher, and then at
some point add that key.
Okay, the final round of the cipher is slightly different there.
We don't have the mix column part.
And certainly you also have to look at that you have to inverse the
whole thing, and this also works nicely.
So all the operations that I will show you are all invertible
operations.
But you have to know the essential ingredients.
Okay, let me start by showing you the first step, byte substitution.
Now all these operations here are operations on finite fields, so
actually arithmetic in a finite Galois field.
I don't know if you know about Galois.
Galois was a scientist, mathematician, some time ago, quite some time
ago, and he actually went into a duel, into a fight with somebody
else, on some nice lady, and he lost.
And when people went to his room, they found a number of papers which
had some formulas scribbled on them, and it was actually the Galois
theory, the theory of finite fields.
Very ingenious theory, and it is about having a finite set of values,
and you know that if you have some value M, some set M, you have
addition and multiplication, and now this set M has to be a group with
respect to addition and multiplication has to be a field.
And so we also have 0 and 1, and we have all these nice properties,
and so in particular it means that if you have a finite field, we can
compute plus and minus, that means the inverse of addition is also
there, and we can compute multiplication and division, which means
that multiplication is also an inverse operation, every element has an
inverse.
Now, this is done on small sets in this part here, Galois field, of 2
to the 8 values.
2 to the 8 values, why do we have this 8?
We look at arithmetic on bytes.
Every byte is a value of your 2 to the 8 different byte values, and so
we have to look whether we can actually construct field operations on
those values.
So, the plus operation in this case is just bitwise XORing, so if we
have 2 bytes, if we add that, we just perform XORing of that.
Can be done very efficiently, just a bitwise operation, we don't have
any carry that is rippling through.
Multiplication, how can that be done?
The result has to be a byte again, and so this is multiplication,
polynomial multiplication, modulo this polynomial.
Now, polynomial multiplication, modulo that value, how is that done?
You can assume that every byte, you can interpret a byte as being,
like if you have a byte B7, B6, B5 and so on.
B1, B0, sorry that doesn't make sense here, take that out.
B1 and B0, you just say, okay, X to the 7 plus B6, X to the 6 and so
on, B1, X plus B0.
So this is a polynomial, you can interpret a byte as a polynomial of
degree 7.
Now, if you multiply those polynomials, then you get another
polynomial, certainly which has a higher degree, a degree of 14, but
you do that, modulo another polynomial, in this case a degree 8
polynomial, and the remainder of that will be a polynomial of degrees
at most 7.
And so the polynomial multiplication, modulo this polynomial here, is
another degree 7 polynomial, which means that this actually is then
another byte.
The coefficients of that polynomial form the new byte.
And this polynomial has been chosen such that this multiplication is
invertible.
That means every byte has an inverse with respect to that
multiplication.
And this is chosen here, so here you first take the multiplicative
inverse of every byte in that color field, then you apply an affine
transformation like this, so here you have a byte, there you have a
specific value, and if you have a matrix, this is the affine
transformation, which results then in some new byte value, and if you
combine all that, like by taking the multiplicative inverse and
afterwards applying the affine transformation, this corresponds to
taking your byte value, you chop that into x and y, x is the row
index, y the column index, and you just retrieve the values that give
the new byte value.
So this is a hexadecimal, these are pairs of hexadecimal digits, and
so in this case you have the results, so the S-box, which is just
those two steps, transforms every byte of that matrix into a new byte,
so this aij is transformed into bij.
This is the first step, this is byte substitution, and how that
continues will be shown to you next time, and let me just very briefly
show you, so this is the end of this presentation, but I would like to
briefly show you one other thing, as this is the last lecture before
Christmas, I would like to show you one nice, like very briefly, a
nice program which actually utilizes the capabilities of a
touchscreen.
So this is a physics illustrator.
What is a physics illustrator?
It means I can draw some figures like this, or, sorry, I didn't want
to draw that, I can draw this, and now I can say, okay, this should be
moved that way, and I can also say, okay, I would like to turn that in
some way, and I could animate that, and now those objects are moving
according to physical properties.
I could also say, okay, I just draw here something, and make that into
a solid element, and now I do the same again.
You see, now all of a sudden those elements turn around according to
physical properties, so I can, if I look at this here, I can look at
the physical properties here, for example, it could be rubber, steel,
wood, ice, plastic, clay, or rock.
You can imagine that you can play around with that quite nicely.
I would like to show you one pre-generated design, which, like a very
nice one, is this domino effect, which I can show you.
You see here a nicely drawn arrangement, and if we animate that, then
all of a sudden you see how this actually is generated, quite a
complicated domino effect.
You see that many elements are moved around in some way.
They have different properties, some are solid, and even that ball
here will be pushed away again by that element there, you see.
Interesting.
And now if, for example, I would modify the gravitational force, I
could modify it in that way, what would happen, then certainly all of
a sudden everything would be different.
That domino effect would be no longer there.
And the final slide, which I wanted to show you, is now this final
slide for this course.
So I wish you Merry Christmas, Frohe Weihnachten, and we can animate
that also, and here you see that this will now crumble away, because
all these elements will be moved in some way.
So have a nice Christmas, and come back filled with eagerness to
actually come to the lecture and see me in person and follow the
contents of this course.
Okay, it has been nice to teach you this in this year, next year we
will start again.
Okay, that's it for today.