5 ms·

I'm assuming that given a starting point A and a number of operations n, there's a much faster way of computing the end point than just iterating n times? Othe

I'm assuming that given a starting point A and a number of operations n, there's a much faster way of computing the end point than just iterating n times? Otherwise, determining n given A and an end point would just be a matter of iterating from A until you hit the end point and counting, right? Also, how do you actually use the keys to encrypt/decrypt?

lordnacho 6y ago
> I'm assuming that given a starting point A and a number of operations n, there's a much faster way of computing the end point than just iterating n times? Yes, this is in fact the basis of the cryptographic security. There's a way to iterate the generator whatever number of times, fast. This is called multiplication, just like there's a way to multiply arithmetic numbers in school without adding over and over. The thing is it isn't quite so easy given the starting point and the result what you multiplied by.
- alecbenzer 6y ago
  Right, but while most people understand multiplication, it doesn't seem clear how to efficiently perform repeated application of the dot operation. I'm guessing the operation is associative, which lets you do it fast.
neikos 6y ago
> ould just be a matter of iterating from A until you hit the end point and counting, right? Yes, you could brute-force all the points. The good thing is, ECC is done on fields that are very large, so that actually enumerating them is not practical. Check out Curve25519[1] for some numbers. [1]: https://en.wikipedia.org/wiki/Curve25519 https://en.wikipedia.org/wiki/Curve25519
- alecbenzer 6y ago
  Right, but the point is that doing the transformation in one direction needs to be fast in order of the scheme to be viable. So there must be some faster way of doing n iterations, which the post doesn't mention.
FiloSottile 6y ago
There is, but it's not a special operation: it's called scalar multiplication and it's just a lot of grouped additions. If you want 13P you do 2P = P + P 4P = 2P + 2P 8P = 4P + 4P 12P = 8P + 4P 13P = 12P + P To use this for encryption you do a Diffie-Hellman operation, where A and B pick secrets a and b, send each other a x G and b x G, and compute the shared secret a x b x G = b x a x G. (Where G is a standard point.) You can call "b x G" the public key and do ephemeral-static DH if you are not doing a key exchange between two online peers.
- alecbenzer 6y ago
  Ah ok, so the dot operation is associative I guess? --- I mean, once you have the keys, how do you actually use them to transform data?
  - john_alan 6y ago
    With elliptic curve crypto you don’t encrypt directly with the private key (just a number) or the public key (just an x,y point). Instead we usually multiply our private key by someone else’s public key to get a point. We take that points x value, hash it and use the output as a symmetric key. The other person can take our public key and multiply it by their private key to get the same point. We end up with something like this: OurPrivate * TheirPub == secret point. (TheirPub is actually equal to TheirPrivateG, thus the secret point is really OurPrivateTheirPrivate*G)
    - alecbenzer 6y ago
      Oh, I see, we're just doing Diffie-Hellman but with elliptic curves? Ok, that makes much more sense... it was confusing for the article to compare it with RSA instead of vanilla Diffie-Hellman.
      - john_alan 6y ago
        Yup exactly that! “Encryption” with elliptic curves is just ECDH and then using a symmetric cipher like AES. Signature is a little more complicated. It’s not just “encrypting a hash”
tialaramex 6y ago
> Also, how do you actually use the keys to encrypt/decrypt? One of the changes in modern cryptography compared to stuff from the 1990s is that we rarely have cause to use public key encryption at all. A typical modern design uses a key agreement algorithm to choose a large shared secret known to both parties which is then used to do encryption with symmetric algorithms. The elliptic curves show up in the key agreement algorithm and in a Digital Signature scheme used after the encryption switches on to prove who you really are, but we often don't use them to actually encrypt anything (and so likewise we don't use them to decrypt anything either).
- alecbenzer 6y ago
  Sure, fine, but even in RSA signing there's some message you transform with one of the keys and then undo the transformation with the other key (the transformation is encryption when the first key is the public key, and signing when the first key is the private key). I just mean, given these EC keys, how do you actually apply them to data?
  - tialaramex 6y ago
    I mean, firstly, no. What you're describing is what we call "Textbook RSA" and that's a classroom exercise rather than a technology you should use in practice - it's unsafe. Perhaps more importantly while you can (almost) do this in RSA you really can't do it with something like Curve25519. As a classroom exercise you can use RSA to encrypt the message "I like toast". You turn "I like toast" into a big number. Using a public key you do the (textbook) RSA operation and out comes a different big number. The recipient uses the private key to get the first big number back - and it translates as "I like toast". Nobody did that in real crypto systems, even in the 1990s, and the way you'd do it as a classroom exercise is inherently unsafe, but you can watch it being done and it's somewhat helpful in understanding RSA. Nothing like that is usually done with elliptic curves. Fortunately we didn't want to send a message like "I like toast" with public key crypto anyway, we always actually want to agree symmetric cryptographic keys. And agreeing keys we can do with elliptic curves. Such as https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93... What's the difference? The key agreement protocol doesn't let you choose the message. Alice and Bob will definitely agree on some shared key at the end of the protocol, but neither Alice nor Bob can choose what it is. For a key this doesn't matter, indeed it's arguably desirable to use random keys nobody actually picked, lots of things to like about that outcome. Does that help?
loup-vaillant 6y ago
I have compiled many fast methods in detail here: http://loup-vaillant.fr/tutorials/fast-scalarmult http://loup-vaillant.fr/tutorials/fast-scalarmult Basically, adding point to itself n times requires O(log(n)) operations. That's how you can have n be as big as 2^255 or 2^448. So yeah, you can still count back, but I'm not sure you'll be done before the heat death of the universe. There are better attacks than that, but they're still O(sqrt(n)), which is exponentially bigger than the O(log(n)) required for legitimate uses.
- a1369209993 6y ago
  > I'm not sure you'll be done before the heat death of the universe According to [0], the Stelliferous Era alone will last ~3 zettaseconds, which at a best already achieved clock rate of 12 attoseconds gives ~2^127 cycles, easily enough to break common 128-bit-'secure' cryptography with good probability on a single, serial computer. Checking [1], converting the Virgo Supercluster into sand-grain-sized computer cores would give parallelism on the order of 2^170, enough to break 297-bit security ratings with certainty, and uncomfortably cut into even 384-bit security. > as big as 2^255 or 2^448. 448-bit security (not 448-bit elliptic curves, but 896-bit curves) is probably okay, despite that these are still fairly underestimated[2] limits - you get better (smaller) limits based off dissipating waste heat at CMB temperatures, so even 384-bit security might be safe in practice. These are all rather off-the-cuff estimates (read, I looked up the largest and smallest plausible-sounding numbers and divided them), but it's rather disturbing that most people don't even seem to think to wonder "what if the adversary was willing/able to sink a significant fraction of the mass and lifespan of the universe into breaking this cryptography?", much less keep semi-exact numbers handy when estimating security margins. 0: http://en.wikipedia.org/wiki/Orders_of_magnitude_(time) http://en.wikipedia.org/wiki/Orders_of_magnitude_(time) 1: http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass) http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass) 2: 2^127 and 2^170 are both fairly achieveable (ie underestimated) individually, but dismantling all the stars you can access to build computers raises the question of how you're then going to power those computers, so I'm not sure just multiplying them together to get 2^297 actually works.

lordnacho 6y ago

> I'm assuming that given a starting point A and a number of operations n, there's a much faster way of computing the end point than just iterating n times? Yes, this is in fact the basis of the cryptographic security. There's a way to iterate the generator whatever number of times, fast. This is called multiplication, just like there's a way to multiply arithmetic numbers in school without adding over and over. The thing is it isn't quite so easy given the starting point and the result what you multiplied by.

alecbenzer 6y ago
Right, but while most people understand multiplication, it doesn't seem clear how to efficiently perform repeated application of the dot operation. I'm guessing the operation is associative, which lets you do it fast.

neikos 6y ago

> ould just be a matter of iterating from A until you hit the end point and counting, right? Yes, you could brute-force all the points. The good thing is, ECC is done on fields that are very large, so that actually enumerating them is not practical. Check out Curve25519[1] for some numbers. [1]: https://en.wikipedia.org/wiki/Curve25519 https://en.wikipedia.org/wiki/Curve25519

alecbenzer 6y ago
Right, but the point is that doing the transformation in one direction needs to be fast in order of the scheme to be viable. So there must be some faster way of doing n iterations, which the post doesn't mention.

FiloSottile 6y ago

There is, but it's not a special operation: it's called scalar multiplication and it's just a lot of grouped additions. If you want 13P you do 2P = P + P 4P = 2P + 2P 8P = 4P + 4P 12P = 8P + 4P 13P = 12P + P To use this for encryption you do a Diffie-Hellman operation, where A and B pick secrets a and b, send each other a x G and b x G, and compute the shared secret a x b x G = b x a x G. (Where G is a standard point.) You can call "b x G" the public key and do ephemeral-static DH if you are not doing a key exchange between two online peers.

alecbenzer 6y ago
Ah ok, so the dot operation is associative I guess? --- I mean, once you have the keys, how do you actually use them to transform data?
- john_alan 6y ago
  With elliptic curve crypto you don’t encrypt directly with the private key (just a number) or the public key (just an x,y point). Instead we usually multiply our private key by someone else’s public key to get a point. We take that points x value, hash it and use the output as a symmetric key. The other person can take our public key and multiply it by their private key to get the same point. We end up with something like this: OurPrivate * TheirPub == secret point. (TheirPub is actually equal to TheirPrivateG, thus the secret point is really OurPrivateTheirPrivate*G)
  - alecbenzer 6y ago
    Oh, I see, we're just doing Diffie-Hellman but with elliptic curves? Ok, that makes much more sense... it was confusing for the article to compare it with RSA instead of vanilla Diffie-Hellman.
    - john_alan 6y ago
      Yup exactly that! “Encryption” with elliptic curves is just ECDH and then using a symmetric cipher like AES. Signature is a little more complicated. It’s not just “encrypting a hash”

tialaramex 6y ago

> Also, how do you actually use the keys to encrypt/decrypt? One of the changes in modern cryptography compared to stuff from the 1990s is that we rarely have cause to use public key encryption at all. A typical modern design uses a key agreement algorithm to choose a large shared secret known to both parties which is then used to do encryption with symmetric algorithms. The elliptic curves show up in the key agreement algorithm and in a Digital Signature scheme used after the encryption switches on to prove who you really are, but we often don't use them to actually encrypt anything (and so likewise we don't use them to decrypt anything either).

alecbenzer 6y ago
Sure, fine, but even in RSA signing there's some message you transform with one of the keys and then undo the transformation with the other key (the transformation is encryption when the first key is the public key, and signing when the first key is the private key). I just mean, given these EC keys, how do you actually apply them to data?
- tialaramex 6y ago
  I mean, firstly, no. What you're describing is what we call "Textbook RSA" and that's a classroom exercise rather than a technology you should use in practice - it's unsafe. Perhaps more importantly while you can (almost) do this in RSA you really can't do it with something like Curve25519. As a classroom exercise you can use RSA to encrypt the message "I like toast". You turn "I like toast" into a big number. Using a public key you do the (textbook) RSA operation and out comes a different big number. The recipient uses the private key to get the first big number back - and it translates as "I like toast". Nobody did that in real crypto systems, even in the 1990s, and the way you'd do it as a classroom exercise is inherently unsafe, but you can watch it being done and it's somewhat helpful in understanding RSA. Nothing like that is usually done with elliptic curves. Fortunately we didn't want to send a message like "I like toast" with public key crypto anyway, we always actually want to agree symmetric cryptographic keys. And agreeing keys we can do with elliptic curves. Such as https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93... What's the difference? The key agreement protocol doesn't let you choose the message. Alice and Bob will definitely agree on some shared key at the end of the protocol, but neither Alice nor Bob can choose what it is. For a key this doesn't matter, indeed it's arguably desirable to use random keys nobody actually picked, lots of things to like about that outcome. Does that help?

loup-vaillant 6y ago

I have compiled many fast methods in detail here: http://loup-vaillant.fr/tutorials/fast-scalarmult http://loup-vaillant.fr/tutorials/fast-scalarmult Basically, adding point to itself n times requires O(log(n)) operations. That's how you can have n be as big as 2^255 or 2^448. So yeah, you can still count back, but I'm not sure you'll be done before the heat death of the universe. There are better attacks than that, but they're still O(sqrt(n)), which is exponentially bigger than the O(log(n)) required for legitimate uses.

a1369209993 6y ago
> I'm not sure you'll be done before the heat death of the universe According to [0], the Stelliferous Era alone will last ~3 zettaseconds, which at a best already achieved clock rate of 12 attoseconds gives ~2^127 cycles, easily enough to break common 128-bit-'secure' cryptography with good probability on a single, serial computer. Checking [1], converting the Virgo Supercluster into sand-grain-sized computer cores would give parallelism on the order of 2^170, enough to break 297-bit security ratings with certainty, and uncomfortably cut into even 384-bit security. > as big as 2^255 or 2^448. 448-bit security (not 448-bit elliptic curves, but 896-bit curves) is probably okay, despite that these are still fairly underestimated[2] limits - you get better (smaller) limits based off dissipating waste heat at CMB temperatures, so even 384-bit security might be safe in practice. These are all rather off-the-cuff estimates (read, I looked up the largest and smallest plausible-sounding numbers and divided them), but it's rather disturbing that most people don't even seem to think to wonder "what if the adversary was willing/able to sink a significant fraction of the mass and lifespan of the universe into breaking this cryptography?", much less keep semi-exact numbers handy when estimating security margins. 0: http://en.wikipedia.org/wiki/Orders_of_magnitude_(time) http://en.wikipedia.org/wiki/Orders_of_magnitude_(time) 1: http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass) http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass) 2: 2^127 and 2^170 are both fairly achieveable (ie underestimated) individually, but dismantling all the stars you can access to build computers raises the question of how you're then going to power those computers, so I'm not sure just multiplying them together to get 2^297 actually works.