tim welcome back to computer files slightly
different circumstances we were doing mega fave numbers in the last one right
that's right yes i was talking about my favorite number um which many people
were disappointed i didn't know by heart um but it is still my favorite topic to talk
about big numbers um in the video i mentioned uh prime numbers in particular and the big
number i selected for that video was a prime number and i said i'll come back and talk
about how they relate to computer science prime numbers in computer science
are interesting for various reasons one of them is it's not always easy to find
whether something is a prime number or not and if i give you a number not like 91 can you
instantly tell whether it's a prime number or not um then again if i tell you that 7 times 13 is 91
you can quite quickly verify that that's right and therefore 91 is not a prime number um so there's
various shortcuts that people found to quickly be able to determine whether something is a prime
number but no one has found a shortcut to be able to find the actual prime factors so telling
that 91 is not a prime number is fairly easy for a computer to do finding the number 7 and 13 is
relatively difficult of course i say relatively here because for a computer it's peanuts to
find seven and thirteen um so that makes it interesting for computer science um but what
makes it even more interesting is its application its application is mostly in cryptography
if i want to communicate in secret with you then i want to be able to do that so one example
of where prime numbers are used in cryptography is the diffie-hellman key
exchange which is something that mike pound was spoke about about three years
ago on this channel a very interesting video watch it but another important application that
uses prime numbers is rsa which stands for revest shamir edelman the three developers of the
algorithm and it's heavily based on prime numbers we see rsa everywhere don't we it's
connecting to the internet we are almost always using rsa at some point is that would i be right
in saying that exactly right yes thank you um so public key cryptography is the general class
that rsa is in there was a video about this a long time ago by robert miles and he explains
what public key crypto is but one of the most important modern applications i would say crucial
to the internet is the fact that https is built on top of this kind of technology now there are
two main flavors to implement it there's rsa which is the older more established algorithm
and there's elliptic curve cryptography again a topic of a different video and those are basically
the two competing algorithms and of the two rsas based on prime numbers which is why i'm talking
about those today in fact i would like to give a quick demonstration of how rsa is used by going
to our university's website so the browser i'm using is firefox but all browsers will have
this functionality what you can see is this little padlock in the top left next to the
address which means that your connection is secure now you can actually investigate how the
connection is set up by clicking on the padlock clicking on the right buttons and then here's a
button that says more information and then there's the option to view the certificate which is what
we're going to do now and here we see information about these certificates and the relevant
information that i want to talk about is right here public key info and so it says the algorithm
is rsa which is the algorithm i want to talk about it says something about the key size being 2048
bits then it says exponent which is roughly 65 000 and then there is this number which is the modulus
which is a massive number it's cut off here in hexadecimal and if we translate this to
a decimal number the number we end up with is this number so what you end up with is this
600 digit decimal number it's a massive number and it's not a prime number actually but it is
the product of two very very large prime numbers and two 300 digit prime numbers now the idea is
that nobody knows what these two prime numbers are if you can figure out what these two big
300 digit prime numbers are that make up this larger number i will offer you a fully funded
phd and a guaranteed spot in the newspapers and perhaps even a big prize here and there and on
top of that you get to hack the nottingham website but how come then this idea that it's difficult
to find prime factors actually lays the foundation for a cryptographic protocol in order to explain
how it works we need to talk about a slightly different topic first it's called modular
arithmetic now it sounds complicated but it's actually very easy in fact we do it every day if
we're using an analog clock because a clock every 12 hours it goes back to its original position
so if i ask you what is 15 hours on the clock you will know it's three hours because it's the
remainder after division by 12.
We do it often for 24 hour to 12 hour clock conversions but you can
even do things like minus one hour which would be 11 on the clock or 25 hours which would be one
on the clock now the clock we are going to be talking about is not a 12 hour clock but a 91
hour clock because 91 is the product of the two prime numbers we're interested in the magic
that actually happens is that if you think of a magic number between 0 and 90 then i can
instruct you to take that number and raise it to the fifth power so can you think of any number
should we go for let's go for number 18.
Okay 18. so what i instruct you to do is to take the
number 18 raise it to the fifth power but do that on a 91 hour clock so this is like 18 times
80 five times and then so it will always be a number between 0 and 90. for a human this is a bit
complicated i don't expect you to know the answer but the answer will be 44 which is you know it's
a normal number between 0 and 19. and then what i do is i take that number 44 and i raise it to the
29th power so i multiply it with itself 29 times on the clock and the number i end up with is
18. so i know in normal arithmetic you have this idea of inverse operations is that a bit like
that have we got back to the start doing that yes that's exactly right so 29 is a magical number
that we found that will reverse you're doing the power to the s taking the number to the power five
so whenever you take a number to the power of five if i take that result to the power 29 the result i
end up with is the original and it will always be the case on a 91 hour clock so that's something
special about 91 hour clocks and i know they're different numbers for different clocks that's
right so it's a special property of 5 and 29 and if you can figure out that the number in question
is number 29 you can read the secret messages so it is important that no one knows the number
29.
Um so let's there's three questions we can ask ourselves when when we see this equation the
first one is where did the magic number 29 come from how do we get that the second one is how
does the computation work why does it reverse the operation and number three is is this secure
why is this secure let's answer question one so question one is where does the magic number 29
come from now to see where it comes from we need to construct a different clock so we had a 91 hour
clock which was constructed by multiplying the two prime numbers 7 and 13. we're going to construct
the different clock by taking the number before the prime number so 6 because it's 7 minus
1 and 12 because it's 13 minus 1. multiply them to get 72. so we're going to work now in
a 72 hour clock and then we're going to pick a prime number which does not divide 72 so we're
not allowed to pick two of three because they divide 72 but 5 is allowed so let's say we pick
the number 5 that is our encryption value e and that is the 5 that we saw before we took 18
to the power 5.
So that's an arbitrarily chosen number to some extent but the number 29 is not
arbitrarily chosen because what we want to do is we want to valid find a value d such that e in our
case 5 times d is equal to 1 on our 72-hour clock now finding that by computer is very easy it
uses an algorithm called the extended euclidean algorithm i'm going to give you the answer because
we know what the answer is going to be it's 29 a computer can find it quickly and indeed if we
multiply 5 times 29 what we get is 145 which is one more than 144 and 144 is a multiple of 72 in
other words 5 times 29 is indeed equal to 1 on a 72 hour clock and this is where that magic value
29 that we used before comes from so that brings us then to the second question how does it work
we came up with this magic value 29 and and it it has a property that five times 29 is equal to
1 on our 72 hour clock right um so what this means is that if we subtract 1 from 5 times 29
what we end up with is a multiple of 72. now let me just tell you what e times d is without
any clocks it's 145.
So on a 72 hour clock okay we go once around we go second time around and
then we have one hour more okay works perfectly so if we subtract one we end up with the
number 144 so 5 times 29 minus 1 is a multiple of 72 but that also means it's a multiple
of this number six which is seven minus one and it's a multiple of uh 12 which is 13
minus one so eb minus 1 is a multiple of both our left prime number minus 1 and our right prime
number minus 1 7 and 13 respectively now because it is a multiple uh of both of those numbers for
each of them individually we can apply a theorem known as fermat's little theorem fermat was a
famous mathematician living hundreds of years ago never having heard of cryptography of course yet
his results are very useful today so using that we can actually deduce that this value m to the
power e d minus one simplifies to one on our clock now because we have this minus one we have
one little m left over so what we end up with is one times m which is m uh which is how
it cancels out in the end okay so that's quite difficult to to follow i would say but it's
quite elegant like things that are not clear somehow fit together as puzzle pieces and they all
cancel out and what we end up with is exactly our original value now there's one remaining question
is it secure so we know that it works we know why our magic numbers are chosen the way they are but
the question is is is it secure so how come that i as in this case the university of nottingham am
able to deduce this value d but strangers cannot now if we look at the way in which the magic
numbers were chosen remember that we found the number 72 by taking one prime number seven
subtracting one and the other part number thirteen subtracting one and multiplying them how will you
do that if you don't know the prime factors of 91 so you cannot find number 72 simply because
you don't know the prime factors of 91 and we established the very beginning that finding prime
factors was a difficult problem but computing a number which consists of two prime factors is an
easy problem so the university of nottingham came up with two 300 digit prime numbers multiplied
them which was relatively easy found the numbers e and d the magic numbers and then forgot about the
prime numbers because they are no longer relevant and then it's secure because only people that
have the numbers p and q will be able to deduce the secret magic numbers and nobody else can know
the magic numbers if i go to the site will i see those same magic numbers do you see what i mean
so you will see two of the three magic numbers which is the product p times q but you won't
know what the original values p and q were you will see the number e which in our little
problem was in number five but you will not see the other magic value which in
our example was the number 29 so the number e is usually a small number and
the number d is usually quite a large number so that's why we found for nottingham that the
number e was 65 500 something but the number d which is a secret number could really be
any number that is roughly 300 digits long we have no idea which number it is you're
not going to be able to search them all quite quickly 2 to the 16 operations 65 000
operations even on a laptop not going to take very long so i go through and i find all the
possible x's that means that any device which is keeping track of time in that way will get really
confused and we basically get the millennium [MANUAL PUBLISH]
