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]