Quantum Computing and Other Extras (with Ron Rivest) - Numberphile
Вставка
- Опубліковано 5 вер 2024
- This follows on from our RSA-129 interview with cryptography legend Ron Rivest.
Previous video: • RSA-129 - Numberphile
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
Videos by Brady Haran
Support us on Patreon: / numberphile
Brady's videos subreddit: / bradyharan
A run-down of Brady's channels: www.bradyharan.com
Sign up for (occasional) emails: eepurl.com/YdjL9
Dang it quantum computers! I wanted to use 15 as my public key!
Christopher King that'd literally only take one pass of a prime factorisation algorithm! But you'd still probably be fine! It's so simple no one would ever guess it! *maniacal laugh*
Ofc people would "guess" it. It's the freaking _PUBLIC_ key ^^
Send me your private key, I won't tell anyone. You can count on my name.
Nothing speaks against 15 as your public key...
I know your private key.
Whatever be. no one ever appreciates how concise, relevant and necessary Brady's questions are.
Thanks for the videos and the great questions!
Agreed! He manages to keep the conversation comprehensible without becoming trivial.
Well, I was just about to comment that this was perhaps the video with the best questions from Brady I've seen so far. Might just be that he asked exactly what I was wanting to ask :p
Brady definitely does a good job at asking questions viewers probably have. He seems to have gotten really good at interviews, especially this particular type, over the years
True, in almost every interview there's a question that makes everyone laugh..
Sometimes I have different questions than Brady, but I still can't think of another interviewer that would have more relevant questions for the average viewer. He is generally very good at asking the right questions. He never presents himself as a very intelectual guy, but judging by his questions he must be quite a smart individual.
I love how he said "I invented this hash function called md5 a while ago" like it's no big deal
he also invented md5. shii
TheSymboz Also RC5
Last sentence was truly relevant, with IOT techs coming into play.
Dabendra Singh once IOT hits mainstream, it will be a nightmare for security engineers. There is a lot to brace for before diving into it.
anyone else notice P=NP on the chalkboard at 3:29
Nice catch!
Of course, since RSA is in NP, if it turns out that P = NP it means there is an easy way to decrypt any encryption. So it's an important question for them.
Not to mention, if P = NP quantum computers would have no benefit over classical ones, since we know P ⊆ BQP ⊆ NP.
i don't know what those are, but i love it. I don't even feel supset. ¿ɥnɹq əp0ɔıun uəʌə noʎ op
P / NP, essentially, "Is our math still just too weak, or are some problems just exponentially harder to deal with?"
Yes........just after I read this ; p
you should've asked him if he believes in P=NP
This was an absolutely fantastic interview, thanks so much! Probably one of my favourites on the Numberphile channel in a long time.
What Rivest said about building platforms from the ground up with security in mind is _so_ true. Just this week, the Security Now! podcast I listen to posited an idea, that really every project should be developed with _every_ developed involved doing their best to pay attention to security at all stages, but in addition to that having at least one person whose full-time job it is to ensure the platform is secure. Unlikely to happen in most cases, unfortunately, but in an ideal world something like that would be really nice to see.
Him lamenting quantum computers would be like Boltzmann lamenting the invention of the internal combustion engine. Just because your invention is made obsolete, does not lessen its importance!
I think he's thinking of it more in the "oh crap, now a huge amount of the internet, banking system, and global communication structure is broken" kind of way and not "oh no, now my invention is obsolete ".
Well quantum computers would give a great deal of power to whoever owns one. And that's only to be expected from a great invention like that. Whoever manages to create fully functional one will reap the rewards
Loved watching these interviews with such a legend. a+
If quantum computers of the future will be able to resolve prime factors quickly, doesn't that mean that any historically secure (RSA-based) data transmissions could be easily decrypted? So technically, if someone sniffs any WiFi signal and stores the data, in some years time, they will be able to decode all the secure data transmitted over that connection.
Yes, but most likely it will be by breaking the Diffie Hellman Key Exchange by quantum computers rather than because of RSA being broken. RSA in TLS is generally only used to authenticate the communication using signatures and the key exchange is made using (EC)Diffie-Hellman
100% that is a concern. If the book Spycatcher is to be believed, British intelligence were still cracking messages from WWII decades later. I guess there were still somewhat useful secrets to learn
at 03:30 P=NP QED
"That it's solvable in... quickly" just say polynomial time cmon
"I don't have a security clearance." - Ron Rivest.
"How hard is this problem?"
The correct answer for P vs nP: "Currently intractable."
Ron is one of the nicest guys anywhere, a true intellect and gentleman.
One must remember that most cryptosystems normal people use is authentication to various parties: banks, social ceurity, pharmacies etc. Those are transient things that are not valid after the one session so breaking them after the transaction compromises just that transactions information which might not even exist anymore. And bulk cyptrography is not done by the RSA algorithm.
I'm not sure how helpful what he said about determining the hardness of problems will be for an uninformed audience... saying that something grows in difficulty at a 'greater than polynomial rate' probably doesn't help many people. Here is my attempt at maybe explaining it a bit more simply:
'Difficulty' in a computational sense is usually concerned with how many operations you have to do to solve something, and how that number gets bigger as the input gets bigger. So, for example, if you are looking at a sorting algorithm, you know that if you are sorting twice as many items, you have to, at a bare minimum, compare twice as many items. For some problems, if you go to solve it on an input that is twice as big, you will have to square the number of operations you do. That would be an 'exponential' problem whether you square or cube or use an even higher power to find the number of operations needed.
Since you're only worried about how fast something is growing compared to how fast the size of the input is growing, you can throw out a lot of stuff. It is usually possible to get an exact number of operations you will need and make a formula to determine exactly how many calculations will be performed for an input. But if your formula looks like "4x^2 + 7x + 18" with x being the size of the input, you can actually throw away everything except the x^2. When dealing with bigger and bigger numbers, the value of x^2 will grow so much faster than x (or 18 which doesn't grow at all, it just stays the same) that you can ignore the rest. The exponent is the important part, because it's going to dominate what is making the number of operations grow quickly. So you would generally say an algorithm where the number of operations increases at least as fast as "4x^2 + 7x + 18" or similar, regardless of how big the "18" or "7" or "4" or even the power "2" is, grows 'polynomially'. If you have another algorithm that grows like "x!" or "x^x", those are 'worse' than polynomial because they grow even faster than ANY polynomial would when you are considering how they behave on huge numbers.
+Dustin Rodriguez What complexity would 2^logn be?
SirCutRy Just n because 2^n and log n cancel out (for log base 2 which is usually used to specify complexity)
Base doesn't matter for complexity because all log bases vary by a constant factor which is exactly what big O ignores.
Peter Bell That's right what I meant is that then they cancel out perfectly to n, of course for O notation it's always O(n) no matter what base although base 2 is usually used
Very remarkable man
I hope there's a Numberphile 2 video coming.
Brady,
if
pi = numberphile
should
tau = numberphile2?
Next please do an Adi Shamir video on Ring signature
There's really no way to know FOR SURE whether the PTBs (powers that be - it's an Angel reference) have a practical quantum computer hidden somewhere.
Around 6:50 Mr. Rivest says that we should study security, which I myself think is a great idea. Question is where would one have to go to learn?
i loved this.
Does numberphile/computerphile have a primality checker video? What is the quickest way to check if a 100 digit number is prime?
Theo Gehling
probably checking for divisibility by 2 and 3 and if that's not true, then do
for i = 0; i
Fantastic!
This video was super quite.
Interesting that he doesn't seem to talk about the berkeley stable qubit that with massive funding could potentially lead to 1000+ qubit quantum computers. I believe the benchmark for how large a quantum computer is required for 1024 bit prime factorization was 10,000 qubits, so in my mind it's possible (albeit unlikely) that an intelligence organization has access to a system that can break RSA private keys within a few days.
I would have asked how he felt when he found out that RSA was invented before he and his friends re-discovered it.
On the subject of security, the problem is largely this argument, a lot of ignorant people have:
"I have nothing to hide..."
Go ahead and give up your privacy.
Place a streaming camera in your bathroom, post your identification keys online, why don't you.
Don't know if he did elsewhere, but he needs to explain why efforts to ban encryption, or to have "backdoors" are idiotic.
And didn't you guys do that in the UK recently?
How did they decide on RSA and not ASR, SAR, etc?
It's explained in Simon Singh's excellent 'The Code Book'. If I remember correctly, they started off listing their names alphabetically (ARS), but Adleman didn't want to be considered the main author of the paper, so they moved his initial to the end.
Bonus, ARS sounds offensive.
Quantum computers will definitely break RSA challenge as they will factor the RSA numbers easily...
There is a new method for breaking RSA in the works
Whats the smallest BrainFuck (a more serious thing than its name suggests) program that yields a given number sequence as an output would for the right choice of said sequence, would be nice and hard to find and nice and easy to test.
☆○ what is the purpose of a quantum computer in real time ~ real life? ☆° is it to "bound-bind" large areas of infinite "pi" non-fielded ~ non-perimetered space into tiny areas of space? ☆° how do quantum computers affect crypt -ography> is it by hiding codes~ messages in inumerable number schemes? ☆•°
Wait, now exactly a hacker would determine exact P and Q? If my password is random gibberish that looks like RSA encrypted message that was then decrypted with wrong P and Q, then, even if he has the right P and Q, my password would still be gibberish that would make that hacker think that these P and Q are wrong so he will keep looking for the "right" ones... Or I just made up a great way of protecting my password?
It's not whether the password looks right, it's whether the password works.
*****
But if a hacker would try out my password with each P and Q he has, he would have to send every password to the server - and when you type a wrong password in, for example, google, it takes some time for that password to reach their server and for it to check that password out, then return if it's right or wrong, so if a hacker would have a big machine that could do heck a load of calculations to find these P and Q, he would have to test decrypted password for each P and Q, and after 15 attempts some sites say "You have tried too many times. Try again later."
True. I mean, maybe people who do these brute force attempts, to speed things up, are looking for a result that looks more like a human-typed password and less like badly unhashed gibberish instead of sending every result to the server, and having more chances to speed things up.
Also just saying, with a bit of work you can make an AI that by itself analyzes a string and tells if it's keymashing(which is something closer to a password created by a human) or a completely random string. If you're interested, search for a video named _🎶The AI Sees When You're Key Mashing🎶_
(which is made by asian kid, obviously :v :v :v :v :v :v :v :v)
Quantum computing = death of rsa, but will also offer their own absolutely impossible to break security, so i dont see any downside.
where does SHA come into this?
SHA is hashing algorithm.
SHA is currently a good replacement for MD5, (which was mentioned in this video.) Both of which are hashing functions. There was only one MD5 but there are a few variations of SHA (two major versions and different hash sizes.)
It doesn't. SHA is not cryptography, it's a pseudo-random generator. You can think of it as one-way crypto: encryption is easy, but decryption is utterly impossible, because there is no key.
RSA is a cleverly locked box, SHA is a box welded shut, covered in linex and dropped into the pacific, there is no way anybody is going to get anything out.
Tony Taco Quantum computers would break that as well.
+icedragon769
SHA is not a random number generator.
It's a class of hashing algorithms. Well, the output of a cryptographically secure hashing algorithm might (should) look random, but it's still not a RNG.
Great videos. Also, first.
Computers are like a maze to me. Why couldn't you make equations out of wires?
Because that is even more confusing. Software is slower than hardware, but it is more flexible and with enough abstraction it can be readable.
Computers are made up of wires. They are tiny electric circuits. Billions and billions of them.