Encryption and HUGE numbers – Numberphile

Encryption and HUGE numbers – Numberphile


DR. JAMES GRIME: So I’ve got a
very big number to show you
today used by NatWest Bank so
that you can send them your
secret bank details.
It starts 2 3 4 5
3 6 7 6 2 8–
[MULTIPLE CLIPS OF
NUMBERS BEING
COUNTED AT THE SAME TIME]

–7.
Did you get that, or do you
want me to repeat it?

So this number that
we are reading out
is 617 digits long.
All banks have similar numbers
when you want to send them
your credit card details.
This is not a secret number.
In fact, your computer will
download this number when it
wants to send your credit
card details.
It’s there to find.
This is public.
So this code that they use on
the internet is called RSA.
It’s named after the three
people who came up with it,
who were Rivest, Shamir,
Adleman.
Should I show you
how it works?
BRADY HARAN: Please.
DR. JAMES GRIME: All right.
Imagine if you had a secret
that you wanted
to send to the bank.
So the bank provides you with
a box, and it provides you
with a key to lock the box.
So you can put your secret
inside and you can lock it,
and then you can send the
secret to the bank.
That’s good, isn’t it?
But the problem is that the bank
is giving everyone one of
these boxes and a key that goes
with it, and that means
that, well, one person could
steal someone else’s box and
use the key to unlock it
and read their secrets.
That would be terrible.
We can’t do that.
So what the banks do, same sort
of idea but instead of
giving out keys, they
give out padlocks.
So they give everyone a box.
You’ve got a secret.
Put it inside the box.
Lock it not with a key
but with a padlock.
It goes click.
It’s snapped shut.
Once it’s locked and snapped
shut, you don’t have the
padlock key, so you
can’t reverse it.
You can’t open it up.
So if someone steals your
box, they don’t
have the key either.
They’ve got padlock, but
they don’t have the
key to open the padlock.
The only person that does
is the bank themselves.
And it’s a way to send secret
messages without having to
send out the keys.
It’s easy to lock the
code, but it’s hard
to unlock the code.
First of all, I have to explain
this with the smallest
example I can, and then I’ll
show you why we use that
massive number.
Let’s say you’re the bank and
you give out two numbers.
They’re public, so everyone
can know them.
They’re not secret numbers.
I’m going to choose the number
3 and the number 10.
The bank also has
a secret number.
The bank secret number,
for now, you don’t
know what it is.
No one knows what it is.
Only the bank knows what
that secret number is.
I had a very bad breakfast this
morning, so I’m going to
send the message BAD CHEF.
The first thing you do if you
have a message like that is to
turn the letters into numbers.
That’s quite simple.
A is 1, B is 2, and Z is 26.
Simple stuff.
C is 3, D is 4.
Now I’m going to turn it into
a code, and I’m going to use
the number 3.
Now there are some codes that
would just add 3, or there are
some codes that would
multiply by 3.
What we’re going to do is raise
to the power 3, so we’re
going to cube these
numbers here.
Let’s do that.
So I get 2 cubed, which is 8.
1 cubed, which is 1.
5 cubed is 125.
And 6 cubed, 216.
The final step is to use the
second number, the number 10.
I’m going to divide by
10, and I’m going
to look at the remainder.
So if I take something like 512,
when I divide by 10, it
would be 51 10’s
and 2 leftover.
So that’s just 2.
5 here, 1 and 4.
And that’s your code.
And that’s what you
would send.
The bank, or the person who is
going to decode this message,
has a secret number.
Now the secret number in this
example is going to be 3.
There’s a formula to work
out the secret number.
I’m going to gloss over that for
a second, but I’m going to
show you what to do next
to decode the message.
This is my code.
I’ll write it out again.
I’m going to do the same
thing I did before.
This time I’m going to
use my secret number.
It doesn’t have to be the same
as 3, but it just happens to
be the same as the
3 we used before.
But nevermind, it doesn’t
have to be.
But I’m going to cube again.
So I cube these numbers.
We do like we did before.
We divide by 10, and
find the remainder.
And then the decoder will turn
that into letters, which is B,
and he gets the message
back again, BAD CHEF.
Now that’s just a taste
of how it works.
That’s the process that your
computer does every time you
buy something on
Amazon or eBay.
One of the important numbers
in this code was this 10.
Now this 10 was made
by multiplying two
prime numbers together–
2 times 5 are prime numbers.
Multiply them together
and you get 10.
Now that massive number that I
showed you that NatWest uses
is the same idea.
It’s two massive prime numbers
multiplied together.
That’s what it is.
If you want work out the decode
key, the secret key,
you need to know the original
prime numbers.
Now the only way a spy, someone
who wants to break the
code, could work out the
original prime numbers is to
take that massive number and
factorize it– turn it back,
break it up into the original
two prime numbers.
This is really hard.
So hard that it’s impractical
to break with modern
technology.
The massive number I showed you
was a 2,048-bit number.
That means it’s about 2
to the power 2,048.
Now about a decade ago,
we did manage to
break 512-bit numbers.
We were able to take that number
and factorize it into
its original primes.
A few years ago, a team of
academics managed to break the
768-bit number.
It took this team of academics
with all their resources two
years to break at 768-bit key.
And they said that to break
what we use now, which is
about 1,024, would take
thousands of times longer.
But given the speed of
technology, they reckon that
this sort of code, 1,024-bit,
could be broken within a few
years, they said.
They said that a
few years ago.
So this should now start
to be replaced.
Gmail still uses this, but
this should be replaced.
And as you can see, NatWest
have done that.
All the banks have done that.
They are now using 2,048-bit
number, which again would take
computers–
and I mean even with
a proper attack–
big computers, it would still
take them thousands of years
to factorize that number into
its original prime number.
Now hidden in the details for
this code is a mathematical
fact that was worked out
in the 17th century
by Pierre de Fermat.
He’s famous for Fermat’s
Last Theorem.
Well, this was Fermat’s
Little Theorem.
If I take a number,
a whole number, an
integer, any number–
call it x.
I’m going to raise
it to a power.
And it’s going to be a prime
number, so p for prime.
I’m going to raise it to a
power, and I’m going to
takeaway x.
This is a multiple of
p, the prime number.
Let me do an example.
What I mean is if you took a
number like 4, and then I took
a prime number like 5, and then
I takeaway 4, I would get
4 to the power 5,
which is 1,024,
takeaway 4, which is 1,020.
And that is a multiple of 5, but
that would be guaranteed.
You’re guaranteed to have
a multiple of 5.
Now you can imagine that in the
17th century when Fermat
came up with this factor, people
said, well, very nice
mathematical fact, but that’s
pretty useless.
What use are you going
to have for that?
And then suddenly the internet
comes along, and it’s
massively useful.
In fact, our whole modern world
depends on this fact.
So to use this code, the public
key has two numbers.
I’ve shown you the massively
long one that NatWest uses.
The other number that we need,
which is the power that you
have to raise, that
is not as big.
That is 65,537.
Quite a big number.
When you compare it to the
second number, it’s small.
BRADY HARAN: If you’re in the
mood for even more about banks
and really big numbers, then
check out my latest video from
the Chemistry Channel Periodic
Videos, where we’ve been
inside the Bank of England gold
bullion vault, where they
have a couple hundred
billion pounds worth
of gold lying around.
That’s not something
you see every day.
The link is here on the screen
and below the video.

100 comments

  1. So let me get this straight….if anyone figure out p and q, then they can decrypt the message, even if they dont know the "e" correct?

  2. Could anyone please explain to me how the "secret number doesn't have to be the same as the number we used to raise the the original values to the power of.." ?

    How do you work out the same message if the encryption uses "3" but then the decryption uses "2" ?

    Or did I misinterpret what he said and the numbers do have to be the same number both ways, it just doesn't necessarily have to be 3? That would make more sense…

    Please help!

  3. Couldnt you just take all the known prime numbers and multiply then till u got the pretended number instead? or just get at least 1 similar or close result and work from there to be faster

  4. if someone want the google number is…

    138705158280867732416635127130627673556488876515656590166689092086246347644731574778771006622896662331093030013154294032773452102956420363690503874704615393265080730427822471001570447529822652491203733378840926364918036459019776407319842826754254624804376257149749341626108612910963459523602040911042453032381

  5. Does this mean the usable prime numbers are going to keep growing in size, and 'therefore' need more and more energy to generate?

  6. I protect my secrets with exponential semiprimes c = a^b… factoring should get easier as b increases, but a is large as well so hackers are SOL.

  7. I dont understand why you need the original prime numbers (2 and 5) when in the example you just used the 10 to decode the message?

  8. I still don't really understand. So the server has the key to decrypt the client's message, but how is the client supposed to decrypt the server's message? I mean only the server has the key and, therefore, the way to decrpyt it, but the client doesn't have access to that key. How are any of the messages from the server to the client supposed to be encrypted with the intent that the client can unencrypt them?

  9. By GCD method factoring a semi prime is easy if it is easy to factor all the numbers lesser or equal to the square root of the given semi prime.

  10. But, what hapens when you use the letter "J" number 10? The remander would be 0, how do you decode back to 10, I mean, it´s OK from 1 to 9, what hapens when the remander repeats it self?

  11. So solving the Riemann hypothesis would break all encryption systems, since we'd have a direct formula for calculating the prime numbers.

  12. My public key: 31415926535897932103417896096814579404275163
    Public exponent: 65537

    Ciphertext: 2713631666392455034339462966592841433809892
    Can you decipher it?

  13. What about you cubed the number by 1? And then if you see the remainder, the code will be ruined…… But you said that any number is Ok!

  14. I don't quite get it. Isn't RSA used alone too slow? and how does Twitter or Barclays apply the RSA algorithm?

  15. How is this secure at all? 3 is public. 10 is public. The individual uses 3 and 10 to perform the operation on BADCHEF and sends the result to the bank… am I missing something. Couldn't a hacker just intercept their message and perform the reverse???

  16. The part where he said we will gloss over how he found the secret number 3 is the reason why we cannot complete the process

  17. but these two prime numbers are at least known by Rivest, Shamir and Adeleman. Than why arent they the richest peopole in the world instead of bill gates?

  18. Math should be treated as not a study but an entertainment. That is why these people loves math so much.

  19. "That's an intersting mathematical fact but what will you ever use it for."

    People tell me this all the time 😂

  20. Why do they use the prime factors of a large number to keep the key secure? Couldn’t they just as well use any random number known only to the bank to secure the key?

  21. well I'm guessing the secret numbers used for raising powers are all Fermat numbers ie 3(in this example), 5,17,65 and then 65537…must be some mathematical reasoning behind it

  22. Please take this video down and re-do it in a way that makes sense. This is exactly why mathematics is "hard", lecturers either don't understand what they are teaching or have no theory of mind.

  23. I bet you that there is some North Korean Hackers who developed Crypto Mining Algorithms, which use the Computing Power of all miners combined as a Supercomputer build out of seperate nodes to crack some of those encryptions.

  24. check out the ssl encryption and certificates…This is where its used, each time you type password its turned into massive 2048 bit number.2048 bit elliptical curve..4096-bit encryption are available…its very interesting…if you were to break this number manually it would take billions of years…

  25. You do make a lot of great videos, but this one leaves us with so many questions and unexplained aspects of the problem, not to mention that this algorithm does not work for most strings, it just happens to do for the string used here. How 3 was calculated as the secret number was not explained, and it's just generally very un-mathematical. I would love to see this video remade with more detail and a more carefully thought-out example!

  26. This is an incomplete explanation! This does not explain what is the relation between the secret number and the prime factors of the public key.

  27. Dear Dr. Grime, I oh so wish you were my Math-teacher back in the days! Understanding math would be so much easier for me back then… Because you can explain those contexts (?, dt.: Zusammenhänge) perfectly!
    Greetings from Germany

  28. Why is it so hard to factories numbers with only two prime factors?? Could you not list every such number in a binary tree?
    Well, I suppose that you won't get up there quickly enough, because since now, it seems, everybody could try to factor that entirely public number….

  29. But he uses characters which codes are <10. In his example you cannot encode say M (13). 13^ 3 = 2197; 2197 mod 10 = 7; 7^3 = 343; 343 mod 10 = 3.

  30. "…so they lock it with a padlock, and you can't open it up."
    over on another channel…
    "This is the LockPickingLawyer, and what I have for you today is a padlock…"

  31. According to your example? where B is converted to 2 and then raised to the power of 3 and then the mod of 10 taken and the result is 8. What is preventing a spy from always assuming an 8 represents B? And it seems it would. There must be more to the RSA than this power/mod thing.

  32. I feel like a math whiz knowing it took James long enough to remember that H was the 8th letter in the alphabet that he had to skip over and come back to it when I already had that letter locked down.

  33. It frustrates me that whenever people talk about encryption they almost always say that it involves really complex, confusing math, when that's not true at all. Admittedly, why they work is complicated, but the formulas themselves are very simple.

  34. Gmail and Google: = idiot's mail. Google regularly parses and searches people's email accounts and cloud storage, selling what can be sold, using anything they can for themselves.. and the 1024-bit security is protecting no one.
    Facebook: The least secure company on earth, so this number is useless considering your info is being sold from the "secure" side of the encryption.
    Twitter: A 2048-bit key protecting useless dribble.

Add a Comment

Your email address will not be published. Required fields are marked *