Nice! Helped me a lot understanding the graphical view of this exchange. It's one thing to see the equations, another to see the points visually. Thanks for the great explanation!
Dude you are simply the best. Clean and simple explanation
7 ปีที่แล้ว +7
It would also be nice if you'd talk about why it is easy to create the public key, but hard for an attacker to compute it... Which is the main reason why a cryptographic system should be used.
It would be also nice if you have really took a "String" and take some parameters and show the whole process like you have done in the previous video "Intro to Cryptography"
"It's obvious that it's computationally infeasible..." It's not obvious because, as you mentioned, after decades of thoughts, no one has found a good solution, but also no one has proved any degree of difficulty.
One thing I can't understand. How is it feasible to multiply generator point by private key (P = d x G), considering `d` is a very large number? Do you need to calculate it step by step with point addition or is there any shortcut to do the multiplication?
I think that's the point: there is no efficient way to find out the private key without manually adding the generator point by hand until you hit upon a match.
Nice, so the difference between DH and ECDH is in DH we are using the exponential function to produce a public key but in ECDH we are using the multiplication function. Still not understandable how ECDH is having a significance.
Is there a known fact with regards to Eve and Alice in terms of the difficulty to obtain Bob's private key? All lectures always mention that Eve cannot do this and that. But since Alice possessed more information than Eve, is there a proof whether Eve's difficulty is greater than Alice in getting Bob's private key? Or that, Alice and Eve have equal difficulty. Or that Alice has lesser difficulty because she has more information.
10:43 I understood how they secretly passed each other value R, but this value depends only on their private keys, I don't understand how this can be used to pass some kind of message or even just a number. Anyone?
At the end of the process they both have a secret point R. Then you can model and use it as you want, you can use it as a key for a symmetrical encryption algorithm.
With random private and public keys (as far as I understood), how can you make sure that Alice is talking to Bob and not Trudy (man in the middle)? In RSA there is a CA, but with random keys, how can Alice/Bob verify he/she is talking to Alice/Bob?
The DSA "digital signature algorithm" - basically it works the same way but opposite direction as the encryption. For encryption, the sending party uses the public key to encrypt the plaintext - only the holder of the private key can decrypt it. For Digital Signatures, the holder of the private key signs the payload with their private key, and anyone with the public key can see if the message is authentic, as the only way that public key and that message will generate the signature is if the signer had possession of the private key for that pair. Generally one would want to use both at the same time... Sender signs the plaintext using the sender's private key, then encrypts it using the receiver's public key. Receiver decrypts the message with their private key, then confirms the message was not tampered with by verifying the plaintext+signature using the sender's public key. Same thing done the other way to establish a shared secret. It's important to note that even though public key encryption like ECC and RSA are "relatively good" for setting up a secure communication, they are computationally more expensive than a stream cipher like Salsa or ChaCha, or a block cipher like AES or Blowfish. For that reason one would use the the public key encryption to setup a secure link with attribution/authentication, then use the stream or block cipher from then out, using a one time use session key unique to that certain communication. Usually one would not let the other completely control the encryption session - so they would do something like each generate a random number and send that as the plaintext to each other then cryptographically hash the two random numbers to generate a common session key. What you were saying about CA (certificate authorities) for RSA isn't exclusive to RSA. Essentially you can't know you're talking to the person you think you are unless you either get the public key from the person you want to talk to - or a person checks and guarantees the information and you trust them because they have a good reputation. The second case is what a CA is. A Certificate Authority will provide a certificate with a chain of custody - you say you are you, you give your public key, and you sign the statement saying you are you with your private key. Then you go to a CA to get a certificate from them - they verify that you are who you say you are and then they also sign your statement and your public key, with their private key. Eventually the user wants to verify who you are, so they retrieve your certificate - which has a chain of CA's that signed all the way to a "root of trust". At every step along that signature you can use that CA's public key to verify the signature and statement of truth is valid. Your browser for example will just have a list of Root CAs it knows to trust, and if your certificate chain ends at one of those roots of trust, the browser will trust you are who you say you are.
Hey! I would like to know more about the importance of the cofactor h, but when I google it most of the sources make reference to ECC D-H with cofactor (as an improved algorithm). Could anyone explain it to me or give some source of trustable information? Thanks:)
I dont understand why the log problem is difficult here... I dont understand why finding the private keys is hard. I understand why it is in standard DHKE, but not in ECC DHKE. Its the ECC thats bothering me here. The starting point G on the curve is public knowledge, right? Each party chooses a random positive integer n and finds n*G, right? So since each party does this anyway, the computation must be relatively easy to achieve relatively quickly, right? And it must be a simple enough computation for any eavesdropper to also do, since they also have G. So why cant an eavesdropper simply repeatedly add G to its previous sum until it finds a sum that works? The eavesdropper is systematically bound to find an n that works. I know that "Alice and Bob" randomly choose an integer n for themselves. So what? We know the upper bound on what n can be because its public knowledge, and because generator G will eventually lead to infinity anyway. Alice and Bob do NOT computer n*G directly.... rather they systematically add G+G+G+G... n times. An attacker doesnt have to guess at n. They just go through the same arithmetical process that Alice and Bob both have to go through anyway, which means its a very linear process. A process that anyone can do. Just stop when you find an n*G that works. If all an attacker has to do is add G+G+G+G+.... = P, in this linear process that Alice and Bob were both perfectly capable of doing themselves, then finding n is a triviality. And you know that n is small enough to be computationally feasible and within the bounds set by p and G. Who said you had to find n directly using some inverse operation? No, you find it indirectly by going through the same direct, forward process. The benefit of standard DHKE is that it involves large primes and the difficulty of factor checking to be so effective. I dont see the benefit of ECC DHKE.
Nice! Helped me a lot understanding the graphical view of this exchange. It's one thing to see the equations, another to see the points visually. Thanks for the great explanation!
Dude you are simply the best. Clean and simple explanation
It would also be nice if you'd talk about why it is easy to create the public key, but hard for an attacker to compute it...
Which is the main reason why a cryptographic system should be used.
it is hard to find the public key because addition and multiplication in elliptic curves is different and is hard to reverse.
logarythm discrete problem for eliptic curves
It would be also nice if you have really took a "String" and take some parameters and show the whole process like you have done in the previous video "Intro to Cryptography"
"It's obvious that it's computationally infeasible..." It's not obvious because, as you mentioned, after decades of thoughts, no one has found a good solution, but also no one has proved any degree of difficulty.
The beginning explanation of point additions makes rest of the presentation easy to understand. Amazingly explained. thanks to you.
very good explanation, helped me remember it since I didn't used it for a while
Amazing work, thank u
This is a very well done and informative video. Thanks a lot!
Question: Since each point such as A represent a point in plane, say (x,y), what does A+B represent?
Where does they exchanged message? I dont see any message was exchanged.... All I can see that they just computed same point R.
One thing I can't understand. How is it feasible to multiply generator point by private key (P = d x G), considering `d` is a very large number? Do you need to calculate it step by step with point addition or is there any shortcut to do the multiplication?
I think that's the point: there is no efficient way to find out the private key without manually adding the generator point by hand until you hit upon a match.
Amazing explanation... Thanks :)
Amazing work
Nice, so the difference between DH and ECDH is in DH we are using the exponential function to produce a public key but in ECDH we are using the multiplication function. Still not understandable how ECDH is having a significance.
super helpful, thanks!
Very good explanation !!
Is there a known fact with regards to Eve and Alice in terms of the difficulty to obtain Bob's private key? All lectures always mention that Eve cannot do this and that. But since Alice possessed more information than Eve, is there a proof whether Eve's difficulty is greater than Alice in getting Bob's private key? Or that, Alice and Eve have equal difficulty. Or that Alice has lesser difficulty because she has more information.
Thanks for making this
10:43 I understood how they secretly passed each other value R, but this value depends only on their private keys, I don't understand how this can be used to pass some kind of message or even just a number. Anyone?
At the end of the process they both have a secret point R. Then you can model and use it as you want, you can use it as a key for a symmetrical encryption algorithm.
Everything made sense, but the process of encrypting and decrypting the message seems to be mostly missing.
Hey, that was a great explanation, is there any way u could help me, in order to Know more about that generator point (G),
How can sum of two positive points A and B result in negative value C??/
The best explaination
Does G require to be regenerate every time Bob and Alice want to exchange key, or G is fixed number.?
Neat and Clear ! :) Thanks
Thankyou
What will be the public key if G is (2, 3).Plz explain.
How R is calculated at each end. Will Alice keep Q as generator point and compute d*Q. Can someone please explain this part
how are Bob and Alice agree on point G if they have never even communicated in the first place?
Very nice.
The Top Encryption Method.
With random private and public keys (as far as I understood), how can you make sure that Alice is talking to Bob and not Trudy (man in the middle)? In RSA there is a CA, but with random keys, how can Alice/Bob verify he/she is talking to Alice/Bob?
The DSA "digital signature algorithm" - basically it works the same way but opposite direction as the encryption. For encryption, the sending party uses the public key to encrypt the plaintext - only the holder of the private key can decrypt it. For Digital Signatures, the holder of the private key signs the payload with their private key, and anyone with the public key can see if the message is authentic, as the only way that public key and that message will generate the signature is if the signer had possession of the private key for that pair.
Generally one would want to use both at the same time...
Sender signs the plaintext using the sender's private key, then encrypts it using the receiver's public key.
Receiver decrypts the message with their private key, then confirms the message was not tampered with by verifying the plaintext+signature using the sender's public key.
Same thing done the other way to establish a shared secret.
It's important to note that even though public key encryption like ECC and RSA are "relatively good" for setting up a secure communication, they are computationally more expensive than a stream cipher like Salsa or ChaCha, or a block cipher like AES or Blowfish. For that reason one would use the the public key encryption to setup a secure link with attribution/authentication, then use the stream or block cipher from then out, using a one time use session key unique to that certain communication. Usually one would not let the other completely control the encryption session - so they would do something like each generate a random number and send that as the plaintext to each other then cryptographically hash the two random numbers to generate a common session key.
What you were saying about CA (certificate authorities) for RSA isn't exclusive to RSA. Essentially you can't know you're talking to the person you think you are unless you either get the public key from the person you want to talk to - or a person checks and guarantees the information and you trust them because they have a good reputation. The second case is what a CA is.
A Certificate Authority will provide a certificate with a chain of custody - you say you are you, you give your public key, and you sign the statement saying you are you with your private key. Then you go to a CA to get a certificate from them - they verify that you are who you say you are and then they also sign your statement and your public key, with their private key. Eventually the user wants to verify who you are, so they retrieve your certificate - which has a chain of CA's that signed all the way to a "root of trust". At every step along that signature you can use that CA's public key to verify the signature and statement of truth is valid.
Your browser for example will just have a list of Root CAs it knows to trust, and if your certificate chain ends at one of those roots of trust, the browser will trust you are who you say you are.
hey can i use some pictures of your video as pictures for my work in university?
Ill give credit of course
Hey! I would like to know more about the importance of the cofactor h, but when I google it most of the sources make reference to ECC D-H with cofactor (as an improved algorithm). Could anyone explain it to me or give some source of trustable information? Thanks:)
what is n which is the prime order??
Thank You :)
hello there, can I use ECC for enhancing the Tiny Encryption Algo(TEA)?
COFFEE would be better mate!
I dont understand why the log problem is difficult here... I dont understand why finding the private keys is hard. I understand why it is in standard DHKE, but not in ECC DHKE. Its the ECC thats bothering me here.
The starting point G on the curve is public knowledge, right?
Each party chooses a random positive integer n and finds n*G, right?
So since each party does this anyway, the computation must be relatively easy to achieve relatively quickly, right?
And it must be a simple enough computation for any eavesdropper to also do, since they also have G.
So why cant an eavesdropper simply repeatedly add G to its previous sum until it finds a sum that works?
The eavesdropper is systematically bound to find an n that works.
I know that "Alice and Bob" randomly choose an integer n for themselves. So what? We know the upper bound on what n can be because its public knowledge, and because generator G will eventually lead to infinity anyway.
Alice and Bob do NOT computer n*G directly.... rather they systematically add G+G+G+G... n times.
An attacker doesnt have to guess at n. They just go through the same arithmetical process that Alice and Bob both have to go through anyway, which means its a very linear process.
A process that anyone can do.
Just stop when you find an n*G that works.
If all an attacker has to do is add G+G+G+G+.... = P, in this linear process that Alice and Bob were both perfectly capable of doing themselves, then finding n is a triviality. And you know that n is small enough to be computationally feasible and within the bounds set by p and G. Who said you had to find n directly using some inverse operation? No, you find it indirectly by going through the same direct, forward process.
The benefit of standard DHKE is that it involves large primes and the difficulty of factor checking to be so effective. I dont see the benefit of ECC DHKE.
Awesome.
How to draw these curves like y^2=x^3-2x+2 at 0:55.
WolframAlpha
What happened to eve?
Elliptic curve equation 00:42
Diffier-Hellman algorithm: 05:14
i need the ppt or any manual on ECC
Do you have it?
Dear Sir please send me your paper or website reference so that i can add it into my paper. Kind regards.
I still don't get it.
Thank u 😭
Addition 1:25
Point doubling 3:07
Gud
Isabella Swan
can't stop a quantum computer though :D