This Video was Not Encrypted with RSA | Infinite Series
Вставка
- Опубліковано 26 вер 2024
- Viewers like you help make PBS (Thank you 😃) . Support your local PBS Member Station here: to.pbs.org/don...
Learn through active problem-solving at Brilliant: brilliant.org/...
Last episode we discussed Symmetric cryptography • (Almost) Unbreakable C... Here we break down Asymmetric crypto and more.
Tweet at us! @pbsinfinite
Facebook: pbsinfinite series
Email us! pbsinfiniteseries [at] gmail [dot] com
Previous Episode
(Almost) Unbreakable Crypto | Infinite Series
• (Almost) Unbreakable C...
How To Break Cryptography
• How to Break Cryptogra...
Last time, we discussed symmetric encryption protocols, which rely on a user-supplied number called "the key" to drive an algorithm that scrambles messages. Since anything encrypted with a given key can only be decrypted with the same key, Alice and Bob can exchange secure messages once they agree on a key. But what if Alice and Bob are strangers who can only communicate over a channel monitored by eavesdroppers like Eve? How do they agree on a secret key in the first place?
Written and Hosted by Gabe Perez-Giz
Produced by Rusty Ward
Graphics by Ray Lux
Assistant Editing and Sound Design by Mike Petrow and Meah Denee Barrington
Made by Kornhaber Brown (www.kornhaberbrown.com)
Thanks to Matthew O'Connor and Yana Chernobilsky who are supporting us on Patreon at the Identity level!
And thanks to Nicholas Rose and Mauricio Pacheco who are supporting us at the Lemma level!
This guy is so brilliant. When he hosted space and time he did the job. Now at infinite series he is still as clever as usual.
Yep, this dude is a beast. The other hosts were good too though. The PBS team is pretty stacked.
The asymmetric public key private key always blows my mind, its pretty perfect. Considering the brute force method it would take to reverse engineer a public key into a private key is enormous and would take at least hundreds of years under normal circumstances.
It blows my mind every time because I forget the system exists constantly. Then I think, "hey how come people can't just scrub wifi for encryption key agreements?" And then I'm reminded of what I should've remembered from my Net-Centric Computing class.
Oh wow, didn't expect to see a new episode so soon.
Yeah! I hope they keep up the pace!
Nice to have you back. Even if I miss the pure math videos of before. Great work as always
I will be doing plenty of pure math. I just thought getting into the math behind crypto might jump the gun if we didn't first lay out the _procedural_ basics behind crypto. As-is, I've already left a lot out (and many of the comments on this and the prior video from people in-the-know are filling in that gap), but I think we have enough in place now to get into the heavier stuff.
i have seen a lot of explanations of asymmetric cryptography, this is the best one
Thanks for saying that. I think it was the graphics. Ray the animator did a *great* job putting pictures to the spoken text.
Yeah, I'm pretty sure computerphile has done some good videos on this, but the PBS format is a lot more engaging, thorough, and easier to follow.
It also probably has a lot higher budget, well spent.
last time i was this early the universe was still orange
lol I wonder how many people will get this.
Trump?
FINALLY. A video that actually explains how these keys work in conjunction.
Had watched so many videos back when I tried to understand how HTTPS and SSL actually perform the key exchange without an attacker also getting the key and every single one of them failed to give a proper explanation on how they did that as if there was no question left.
So, I guess the next episode is about Diffie-Hellman.
Ceelvain nope it'll be elgamal
or ECDH
which are both variants of Diffie-Hellman
Guess I should find my textbook and reread the DHKE
...meanwhile, I'm just coming over here from Computerphile, so nothing to see here.
I was really intrigued by the video and looking forward to the next one!
I really like to see the math behind the 3 option and the extra way to make a one-way function.
Gabe we have no time to talk about cryptography. We need to focus on colonizing Venus
Actually we need to focus on Net Neutrality.. Then we'll colonize Venus.
Hey so you have a name
it's quite fun that Numberphile just did a video on Option 3
I usually don't like when channels change their host, but you guys are great !
Caution @6:35 This statement is simply wrong for asymmetric keys!
The public key is embedded in the website certificate.
This certificate has the purpose to link a public key to meta data of a website like the url, company name and so on, plus a validity time span, and optionally other data. Certificates are digitally signed by a well-known certification authority. So if anything is changed, the signature does not verify anymore. Depending on security requirements, these certificates are usually valid for a few months or a few years.
The current certificate for youtube, e.g., expires in February 2018, so in about 3 months. That's at least 3 months of communication with the same certificate, and hence the same public key.
What I forgot: Collecting enough random data from HDD spinning data, CPU temperature, etc. takes time, lots of time. Also this data needs to be transformed to give pseudo-random values that are at least approximately uniformly distributed. These transformations are computational expensive. Creating an RSA keypair can take a couple of minutes on a modern laptop.
Hi, Gabe here -- correct me if I'm wrong, but I think UA-cam uses certificates primarily for *authentication*, i.e. digital signing. The *encryption* of the actual *content* uses ephemeral keys for an elliptic-curve-based Diffie-Hellman exchange of an AES key (I don't remember whether 128-bit or 256-bit, but one of those is the AES key size), and I thought even that AES key is also session-specific or that it might linger for a few sessions but expires with a pretty short half-life. No?
Granted, there are several layers to any secure communication protocol -- authentication (digital signing), actual encryption, validation, etc -- and we're not going that far into this stuff... yet (time constraints, production constraints, etc). I was trying to focus here on the encryption per se, as an abstract concept, and I *think* what I said in the paragraph above about UA-cam's choices under the hood are correct. But again, please tell me if I'm mistaken.
And incidentally, we will get into Diffie-Hellman and elliptic-curve cryptography in episodes coming up. So at some point, I plan to tie all this together and try to clarify lingering points of confusion on the audience's part and fix any errors on my part. You may very well know more about this than I do, so any input on the facts is much appreciated.
PBS Infinite Series It depends on what form of TLS specified in the certificate. While UA-cam's certificate specifies ECDH to agree on the key, there are lots TLS certificates that contain a public key and the site will have you generate and send them a key.
It uses AES-128 for encryption, SHA-256 as hashing algorithm.
You're correct, the certificate is used for authentication only on UA-cam. But this is also the only time, that asymmetric keys are involved. The keys for the AES encryption are not really exchanged, but instead a so-called key agreement algorithm is used, that kind of guide Alice and Bob to create the same key. A fancier version of Diffie-Hellman is used, but the basic version goes like this:
Suppose there's two prime numbers *k* and *p* specified in the protocol.
Alice generates random number *a* and sends *k^a mod p* to Bob (k to the power of a modulo p).
Bob generates random number *b* and sends *k^b mod p* to Alice.
Alice calculates *(k^b)^a* and Bob calculates *(k^a)^b* , so they both got *k^ab* , but an eavesdropper Eve, who might know *(k^a)* and *(k^b)* now, cannot compute *k^ab* from these two values, because taking the logarithm is hard in finite fields.
And yes, the AES key is renewed for every session. And when the protocol is correctly implemented, might even change during one session, since its security is broken after approx 2GB of data if I remember correctly (But I'm sure, it's just one digit). So just before this limit is reached, the current AES key is used to transmit a new key.
Ian Roberts -- right, agreed. But I'm not wrong in saying that UA-cam itself uses ECDH to exchange an AES session key, and that all of the above are ephemeral, yes?
this was a beautiful episode.
Now i got ittttttt! Thanks Gabe
It’s one of the best! So disappointing it’s gone :(
Good to see Gabe back
Great video Gabe. Have a better understanding how it works, but it's not still clear for me, how common user can check that his message encrypted.
So, while chatting, I really don't see any keys, and how they work. Messenger app do all the work for me, inside itself. And I have only to trust them (what I'm actually don't, fortunatley I haven't anything to hide).
So, without digging into crypto and safe channels to communicate, common user can't be sure that his message is secured. And not only messages, also financial transactions etc.
[edit: Spoiler alert!!!]
Very importantly, the logarithm is also hard to calculate in finite field arithmetic of that kind.
If it were not, the private key were broken in no time like this:
1) think of a plaintext message m
2) obtain the public key (e,N) corresponding to the private one you want to obtain
3) encrypt plaintext m to get ciphertext c: c=m^e (mod N)
4) We know, that m=c^d (mod N), so d = log_c(m) (mod N)
5) Since we know c, m, and N, we'd get the private key (d,N) if the logarithm were easy to compute.
Ergo the (admittedly brief) disclaimer starting around 4:46. But yes, the DLP is coming up in further episodes (probably predictably). Hang tight for a few weeks, we'll get there. Promise.
And actually, I think this fact is what the "foreshadowing Option 3" in the video is about, since I reckon it is about the algorithm invented by recent Turing Award recipients.
DMSG1981 does log work like that in mod arithmetic too? I feel like the answer is yes lol
Depends on what you mean by 'work like that'. The logarithm is just a sought-after exponent. So in this regard, it 'works like that', but it can't be calculated as easy as for real numbers.
PBS
Sorry, I added a 'spoiler alert'.
If Kelsey could occasionally come to infinite series it would be great. Like if you agree
Unfortunately, that's probably not the way PBS digital studio works.
Also she should concentrate on her PhD. Let her come back after she's done with that.
Kelsey couldn't handle all the disgusting things y'all said about her and I don't blame her
Sebastian Elytron what are you talking about?
Kelsey is synonymous to infinite series for me. So it would be great if she just kind of does a guest appearance thing in future
Thanks for great episode!
SUprisingly good replace for Kelsey
I'm not surprised, he was the host that started pbs space time and was very good.
...a mathematics theory question I posed in ICS455: the DH/RSA/etc. encryption big-bucks arithmetic uses ordinary scalar addition bit-sums+carries {Exor, And} but can also be done with no-carry polynomial arithmetic...so...are there other arithmetics with strange-carries...
Wow, so glad to see you back!
Welcome back, Gabe!
Asymmetric key encryption is gorgeous.
Question: In your explanation of asymmetric encryption, the private key is used to decrypt a message encrypted with the public key. But when you mention authentication, it goes the other way around: the public key decrypts, and the private key encrypts. How do we know that it works both ways? Is it essentially from the fact that (m^e)^d=(m^d)^e, so d and e are not distinguishable?
YOU'RE FINALLY BACK YES
I started studying a "Teach Yourself Mathematical Groups" because of the group theory references in Wikipedia pages on particle physics. Thus video made me think, "hmmm. this looks familiar."
When describing how Alice and Bob are using public and private keys you forgot to mention Eve, she can be man (woman) in the middle.
If she can modify communication on the channel between Alice and Bob instead just observing it, she can generate two key pairs. She could swap Bob's public key on its way to Alice for hers and Alice's public key on its way to Bob. Then Eve can not only read the communication (both ways) but also modify it.
argh it was so mean to divide this topic into 3 parts :D now I have to wait again...
What a Crafty eavesdropper
Hooray ECDHE!
I'd say that the answer to "is there a better option than securing with factoring" is more of a probably than a definite yes. Factoring on elliptical curves seems to be harder but there's not really evidence that it must be.
After Kelsey finish her PhD maybe she will comeback. But not here, maybe next door. In PBS spacetime.
Welcome back bud!
These videos make me want to go back to university to study cryptography.
Please bring back Gabe, Kelsy and the Infinite Series
I have one word for this man: chaptstick
YESSS!!! I missed you since you left space time
@2:26: In principle this is true, but be careful to use different keypairs for encryption and authentication for security reasons. In the animation, Alice had only one and used it for both.
Agreed. But, you know, we're trying to titrate to some level that strikes the right balance among (i) 100% real-world accuracy vs (ii) getting the overall concept across in a digestible way vs (iii) working on a PBS-sized budget. So we settled on the best heuristic animation we could produce within the production schedule that was faithful enough to the general concept. Know what I mean?
I know, and that's totally fine. This was just a little remark for the interested viewers.
Gotcha
Why do you have to? With PGP, people always use the same key pair.
I think PGP uses different keys for signatures and encryption. At least GnuPG does. When you list the keys, you see several keys for each uid, where usually the one marked as "pub" is used for signing, and the one marked as "sub" is used for encryption. There may be more than one subkey, but the listing of the keys shows which ones are used for what with a tag in square brackets.
Example:
pub rsa2048 2017-12-17 [SC]
11E055AE7ED75C18766B61430E69BE8048B50641
uid [ultimate] Test 2017 (-)
sub rsa2048 2017-12-17 [E]
('E'=encryption, 'S'=signing, 'C'=certification, 'A'=authentication)
RSA isn't used for encrypting content in the SSL/TLS suite but for signing and sometimes key exchange, the issue with asymetric encryption for content encryption is it is slower for larger messages so as soon as possible the site will switch to symetric encryption, usually AES but sometimes other supported symetric encryption algorithms (it really depends on the servers config, many use other signing methods like HMAC)
Ok it was mentioned, please do one on Diffie-Hellman Key Exchange (the most common key exchange method)
Will there be a video about attacks on RSA? I've heard only of man in the middle attack and I'd love to see a video about other types of attacks
Foreshadowing! o _ O
I’m so accustomed to how you used to present Space-Time that your slower speaking cadence in this series is throwing me off. Speed it up! 😂
Suggestion: make an infinite playlist on the fast growing hierarchy! It also have infinite ordinal! I really love large numbers
Goodness I wish this video series was around when I was taking cryptography last semester😂
ITS THE SPACETIME GUY!!!!!
I once read in a combinatorics book that generating a specific graph and sending a key corresponding to a Hamiltonian cycle is also a one-way function. (Checking if a given cycle is Hamiltonian is quick but finding a Hamiltonian cycle takes forever) How good is that at encryption?
Also could you talk a bit about P=NP problems and computational power? Things like there is no Turing Machine that returns if a given machine terminates.
Ayyy this guy again!
"This Video was Not Encrypted with RSA"
Technically true but the SSL certificate was signed by the Certificate Authority with RSA (even though ECDHE_ECDSA/X25519 is used for the key exchange). If Eve can break RSA then Eve can generate her own 'valid' certificate, and function as a man-in-the-middle. You go over this in the video itself, but my point is *authentication matters*. Diffie-Hellman key exchange is not secure if you aren't certain Alice and Bob are really Alice and Bob, with nobody repeating messages in between, and CAs are the (crappy) way we do that. Certificate Authorities are themselves also a point of failure even if RSA is secure as the CA's private (signing) key could be compromised by a hacker or nation-state actor.
SSL/TLS actually *has* a mode for certificateless Diffie-Hellman (DH_anon). It is demonstrably not secure and isn't used on typical websites. Have seen it used on internal systems when pentesting though ("we need to encrypt things but we're too lazy to have any proper internal PKI"), and you can use ARP spoofing to get between the two machines, send TCP FIN to cause them to attempt to reconnect, then pretend to be each end, establishing a DH key with each real machine. Now you have the plaintext transmitted between each machine, letting you obtain passwords, etc.
im going to guess that option 3 is something to do with quantum computers because quantum computing can allow you to share a private key and know if somone has intercepted it because due to the observer effect
I can't wait. My body is ready man, don't keep me waiting.
I want more math tho, like what totient is (found it here simple.wikipedia.org/wiki/RSA_(algorithm)), refresh me a bit with congruent, and things like that.
Awesome video!
bring this guy back to space time
Am I right in thinking the quality referred to at 7:00 is perfect forward secrecy?
You should atleast name Diffie-Hellman or Merkle's puzzle.
Almost everyone who learns cryptography has learned Ceaser cipher and Hill Cipher. The interesting part is
Ceaser cipher is message+key
Hill Cipher is key*message
RSA is message^key
and the whole algorithm is derived in a way that this ideas work.
So it takes 2 steps to reach from Ceaser cipher to RSA.
Deep Joshi There should be
message^^key
^^ is tetration
It will be hard to compute large tetrates though
I can smell an Eliptic Curve somewhere...
so smart, i love it
How does Bob get Alice’s public key in practice? Is there a registry for emails?
The whole explanation is flawed, they are not Alice and Bob!
:o)
eve...
eavesdropper...
illuminati comfirmed
Very Good!
Your talking about diffe hellman key exchange right?
It works by using discrete logarithm which although is not definitively proven to be hard to "crack" it has no easy algorithm for solving it currently.
I'm eager to hear #3's answer.
is the 3rd option using entangled particals to generate AES keys?
Elliptical curve baby!!
Hopefully going to do a video on ECDSA?
If one does use a symmetric key, would it hold up against quantum cryptography?
Also, I read a book called “The Sympathizer” where they coded messages using page/row/column coordinates for letters in a book they both had. What type of encryption is this and how does it hold up in computers?
dang it, I want more! :D
So how do produce e and d? say I had 77=N P=7 Q=11 how would I generate e and d?
I don't get it. How Bob can DECRYPT Alice's message with her PUBLIC key at 2.47? Aren't only private key can decrypt the encrypted stuff?
Poor Eve. Nobody _ever_ wants to invite Eve to their parties.
What I'm wondering is how quickly quantum computing (ie computing all possibilities simultaneously and using probability to select the right one) could brute force these encriptions
Modern encryption works because modern comps are bad at algibra, but quantum computers sound like they'd be great at it
Quantum computers don't calculate all possibilities at the same time. They kind of do that but does not give you all the answer because if you look at the answer all other possibilties disappear and you only get one random answer. There are specific problems where you can sort of influence the probabilities so that you get high chance of getting the right answer but the chance of getting the wrong answer is still there. Quantum computers are not magic theys are just sort of like if you're high magic.
Sad that they ended the channel
Hey PBS, it would be nice if you could bring Gabe back to Space Time as a co-host 🙏
Use polarized photons to transmit a one-use-page between Alice and Bob! Boom! Option 3...only physics in the way...
I bet hes going to explore the BB82 protocol next episode
Gabe
What happened to elliptic-curves cryptography? Is it broken?
malporveresto hopefully they won’t shy away from talking about Elliptic Curves in the process
I'm no expert on them, but from what I understand: No, they are currently not broken, but yes, they can be broken by quantum computers which are the biggest threat to RSA.
That's one of the reasons why post-quantum cryptography is such a well-studied and important field. It's basically preparing for the worst case _before_ large quantum computers are actually built.
As @Nixitur said, It will be under scalable quantum computing. The proposed solution is SIDH, or Super-Singular Isogeny Diffie-Hellman which tries to salvage ECC. SIDH presents its own unique challenges, and I don't believe any SIDH schemes were submitted to NIST for PQC standardization.
A I'm not quite following you when you say you can substitute any multiplication based standard with ECC. ECC uses a discrete logarithm problem as the underlying mathematics of its security IIRC. Can you clarify what you mean by "multiplication based standards?" Are you saying you can transform RSA using groups to ECC?
Interesting. I believe the key sizes of ECC are more comparable to AES rather than RSA (I'm shooting from the cuff here, though). You've definitely piqued my curiosity on this. Learning with Errors (LWE) and Ring Learning with Errors (R-LWE) operate by multiplying elements with small noise values and adding them before transmitting approximate coordinates (e.g. New Hope). Schemes relying on LWE and R-LWE *are* being proposed as post-quantum secure, so I'm wondering if you could perform some transformation on the principal ideal ring to derive an elliptic curve group. That could potentially be a weakness in lattice schemes...
So... when do we do quantum cryptography?
I know this does not solve the authentication problem, but just an idea: can Alice use AES on her side, using a key she knows, transfer to Bob, that will use his AES key, than send it back to Alice, that will decrypt with her own key, and than back to bob, that will decrypt with his key? Is this way a safe way to exchange data, Ignoring the authentication problem?
Provided the encryption methods commute, yes, this will work. Eve will be able to see A(m) and B(m) but not m itself. The key to this working is that applying two different encryptions to the same original message should give the same doubly encrypted message whichever way round you do the two encryptions. That isn't true of all encryption methods.
In practice, rather than sending every message back and forth like this, you'd use this to share a key and then proceed from there.
I didn't get only one thing. How is it related to infinity?
Is "bob" the guy who used to host science friction?
I thought he was a physicist.
It would be quite difficult to find a theoretical physicist who is not also basically a mathematician.
AFastidiousCuber not if Sheldon Cooper actually existed.
And he is talking about computer science in a mathematics channel.
They are actually heavily related. There are a lot of mathematics that hasn't been applied to physics, so there are a lot of mathematicians that do not bother themselves with physics. But almost all of theoretical physics are based on maths, so you can't find a theoretical physicist who doesn't know relevant parts of maths.
AFastidiousCuber i think the point of this comment is why is the content not physics-y?
Sebastian Elytron because this is a math channel
Hey Gabe, anyone ever told you you look like Joe from Impractical Jokers/?
Wait.... you're back? I thought this guy left?
This guy left SpaceTime, not InfiniteSeries. He just started to host on this channel.
At 4:10 he sad: 'at leas one of each (PRIME NUMBER) has hundreds of decimal digits'. Primes have decimal digits? ... or I'm just Eve?
The things described here still aren't sufficent to prevent a mitm, eve could intercept the public keys and the messages, create her own key pairs, and send her public keys to alice and bob. Eve could then just decrypt and reencrypt the messages using the appropriate keys. The proposed authentication system can be circumvented similarly, since alice and bob used eves public keys, eve can decrypt the message using her private keys, and since eve intercepted alice and bobs public keys, she can decrypt the second encryption layer with those, and reencrypt the message with the apropriate other keys afterwards. In fact, it is impossible to securely exchange messages if only one insecure communication channel exists. The reason why we can "securely" connect to websites anyway is because certificate authorities (CAs) sign the certificates of websites and other CAs with their private keys, and a copy of most CAs public keys is preinstalled on most OSs, Browsers, etc. Of course, that requires the users to trust the CAs in the chain of trust and the ones who installed the keys. Other secure services just relay on different and hopefully not yet compromised communication channels to exchange keys or shared secrets.
Use eliptic curve crypto, the keys are much better per kb of data
In theory yes, but can you prove that the curve that is proposed hasn't been specially selected to make unauthorised decryption easier for malicious individuals? #backdoor #nothingUpmySleeves
why the infinite hand jestures ... ?
Can you please speak at the rate of factorising numbers so that I can understand you.
What about QKD?
Why did you change host again?
2:40 The private key is shown as leaving the private zone and decrypts the message and leaves it unencrypted. This should not happen. The encrypted message should enter the private zone and only then be decrypted. The private key should never leave the private zone. The message verification seemed confusing, (and may make further reading harder) because you didn't refer to it as signing. Alice can sign her message with her private key and Bob can verify the signature using Alice's public key, (this lets Bob verify that the message has not been changed in transit.)
It WAS however encrypted with RZA
What is RSA
Great job! May I suggest not looking down at your notes as often? Breaking eye contact feels discontinuous.
REPLY
Awesome
Good content, but don't go too far into Computerland. There are other channels for that, and I relied on this channel for pure math edutainment.
did he not know that kelsey already did a video on this that he could have referenced?
Obviously I knew. We'll be referencing her earlier vids on encryption more directly in the next couple of installments we do on crypto. The material from her prior episodes is much more directly related to the stuff we have coming up later.
Bring Kelsey Back!