If however, you know the number of hops you can use an exponentiation trick to find the ending point quite quickly. For example, and omitting the details of elliptic curve operations: 2P = P dot P and then 4P = 2P dot 2P. This allows you to get up to those crazy high calculations exponentially faster.
===
One big difficulty in ECC vs RSA is how to do the math required for the operations. With RSA choosing the keys is the part where dragons lie and you need to make sure the numbers chosen satisfy various criteria. The algorithms for working with keys in RSA are well defined. The opposite is true for ECC. It is easier to choose numbers but depending on the curve used as well as how it is implemented there can be information leaked about the key in timings and other behavior.
If you want to read more check out the Wikipedia article on the Montgomery Ladder ( https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic...) as well as DJB's comparison chart of curves that don't support the Montgomery Lader: https://safecurves.cr.yp.to/ladder.html . The real kicker here is that the NIST P-### curves are what ends up in official US government requirements.. and they are vulnerable to side channel attacks due to their design.
This post leaves out a key difference between something like RSA and EC, which is that EC doesn’t actually provide an encryption function. You end up using an integrated encryption scheme.
This is intuitively similar to how TLS works, in which asymmetric concepts are used in conjunction with a KDF and hashing algorithm to agree upon a per-session symmetric key.
This way of proceeding was introduced earlier, but wasn't the only option until TLS 1.3, in TLS 1.2 for example, even though chances are any TLS 1.2 sites you run offer a more modern Elliptic curve scheme, it was mandatory to implement
TLS_RSA_WITH_AES_128_CBC_SHA.
For TLS_RSA_WITH_AES_128_CBC_SHA (and many other schemes) RSA is being used to transport the session keys chosen by the client (and thus implicitly authenticate the server). This means if an adversary gains possession of the server's RSA private key, even perhaps several years later, that's enough to decrypt the session key and thus decrypt all messages that adversary might have captured before.
Whereas with the schemes using Ephemeral Diffie Hellman (whether conventional or elliptic curve) once those ephemeral values are discarded going forward the only way to decrypt the messages secured by them would be something like Shor's algorithm to break DH, hence the term "Forward Secrecy".
The fact that ECC doesn't provide an encryption function is actually a feature, in my opinion:
It's impossible to accidentally encrypt a message with the asymmetric cryptographic primitive in the ECC case, but not in the RSA case. This makes ECC misuse-resistant in a way that RSA isn't.
(Although, strictly speaking, you can "encrypt directly" with elliptic curve schemes if you use ElGamal--which might even be desirable in weird systems. Fortunately, most high-level cryptography libraries that offer ECC don't expose the APIs to facilitate this.)
I appreciate that this post focuses on the key element that I hadn't understood about ECC: how it replaces factoring as a 'easy to do, difficult to undo' algorithm. This is a great example of a post that has enough information to be able to explain it in plain language without giving the impression that you know enough to implement it.
It’s maybe good that the post doesn’t really have to talk about group theory, but for the record, the standard way to answer this question is:
1. Integers modulo a prime form a (cyclic) group
2. Cryptographic algorithms like Diffie–Hellman group exchange don’t really care about the integers modulo a prime and can be translated to other groups
3. The security of these algorithms rely on the discrete logarithm (computing a given g and g^a) being hard. For Diffie–Hellman, it is a related problem of computing g^{ab} given g, g^a, and g^b, which might be easier.
4. For integers modulo a prime discrete log is hard but not that hard. Security is measured in the number of bits of one-time-pad the security is equivalent to. It is generally believed that discrete log is harder in elliptic curves, such that a shorter elliptic curve problem (which also gives faster computation) is the same difficulty (ie security) as a larger mod p problem. This is the promise of elliptic curves.
Note here that factoring in general is not replaced: RSA, for which factoring is the important problem, relies on specific properties of modular arithmetic that aren’t really the case for general groups.
Cool intro, I had no idea about ECC. However something is a bit lost on me: if the number of hops is the "private key" in this scenario, couldn't you just hop until you've found the endpoint? What makes this particularly difficult?
The number may be very large (think: much bigger than 2^64). The reason it’s possible to compute these in logarithmic time (ie linear in the number of bits of the key) is the same reason that it is possible to compute a^b (mod c) even when b is very large: there are operations in elliptic curves akin to multiplying and squaring so a^(2b_1 + b_2) = a^(b_2) (a^2)^(b_1) can have the cost of computing a^(b_1) (say b_1 is 0 or 1, so this is constant), the cost of a multiply (constant), the cost of a square (constant), and the cost of an exponentiation of a number with one less bit, hence by induction the cost is linear in the number of bits.
I am also puzzled by this, and if the number is hops is so large that it’s unfeasible to enumerate, how does the key generator know many hops it should be...
You can generate new curve parameters, but nobody does, and you shouldn't (you will perish in flames). The popular curves, probably in order of popularity, are the NIST P-Curves (like P-256), Curve25519 (and Ed25519 for signing), Bitcoin's secp256k1 (originally from Certicom), and then higher-security-margin curves like E-521.
It was never mentioned in the article so I just looked it up on Wikipedia, but Elliptic curve cryptography is not secure against future quantum computers.
So with bitcoin and some other uses the actual public ecdsa key is hidden behind some hashing such that you gotta invert the hash function to get to the ecdsa public key before cracking. Also that's not a one to one but... Can you crack sha256 with quantum computing too?
Neither is RSA. Most present day asymmetric crypto has its strength (amount of computing required to break it) significantly reduced by quantum computers. The solution is quantum safe algorithms which are a developing field.
Symmetric algorithms such as AES can have their strength reduced as well, but (I have no sources to cite) I believe this reduces it from 256-bit to 128-bit. At 128 bits of security it is still widely considered safe to use.
Yeah and the currently known quantum resistant algorithms have huge keys. Much larger than RSA. So we shouldn't get too dependent on short keys when designing protocols...
A high level overview on why different curves like 25519 are chosen would be awesome. The Wikipedia article on it is probably very intuitive to a cryptographer, yet its just a bunch of letters to me.
Does the EC function provide any guarantees around how often a given endpoint can be hit? e.g. over the course of infinite hops starting at point a, how frequently will point b be landed upon?
Disregarding the quibbling about what is waste and what isn't, there's a difference between the work done to validate blocks and work done for the PoW based Nakamoto consensus. You want block validation to be as fast as possible which is a separate concern from deciding on a chain which is where you want lots of work.
Bitcoin wants to waste resources for a specific operation - which is to prove that work was performed. The other aspects of bitcoin, such as sending transactions and validating transactions, have no need to waste resources and are designed to be efficient.
A good analogy is password hashes. If you have a hashed value, it is expensive to find the original input. If you want to check that an input is equal to the hashed value, that is a cheap operation.
> But bitcoin is a waste of resources by design. The whole point is to waste resources.
The miners run POW (i.e. waste resources), and requires specialist hardware (ASICs). Validating blocks is done by "nodes" and is within the capabilities of typical consumer hardware. Both operations serve different purposes in securing the network.
[+] [-] er4hn|5 years ago|reply
===
If however, you know the number of hops you can use an exponentiation trick to find the ending point quite quickly. For example, and omitting the details of elliptic curve operations: 2P = P dot P and then 4P = 2P dot 2P. This allows you to get up to those crazy high calculations exponentially faster.
===
One big difficulty in ECC vs RSA is how to do the math required for the operations. With RSA choosing the keys is the part where dragons lie and you need to make sure the numbers chosen satisfy various criteria. The algorithms for working with keys in RSA are well defined. The opposite is true for ECC. It is easier to choose numbers but depending on the curve used as well as how it is implemented there can be information leaked about the key in timings and other behavior.
If you want to read more check out the Wikipedia article on the Montgomery Ladder ( https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic...) as well as DJB's comparison chart of curves that don't support the Montgomery Lader: https://safecurves.cr.yp.to/ladder.html . The real kicker here is that the NIST P-### curves are what ends up in official US government requirements.. and they are vulnerable to side channel attacks due to their design.
[+] [-] ragona|5 years ago|reply
https://en.m.wikipedia.org/wiki/Integrated_Encryption_Scheme
This is intuitively similar to how TLS works, in which asymmetric concepts are used in conjunction with a KDF and hashing algorithm to agree upon a per-session symmetric key.
[+] [-] tialaramex|5 years ago|reply
How TLS 1.3 works.
This way of proceeding was introduced earlier, but wasn't the only option until TLS 1.3, in TLS 1.2 for example, even though chances are any TLS 1.2 sites you run offer a more modern Elliptic curve scheme, it was mandatory to implement TLS_RSA_WITH_AES_128_CBC_SHA.
For TLS_RSA_WITH_AES_128_CBC_SHA (and many other schemes) RSA is being used to transport the session keys chosen by the client (and thus implicitly authenticate the server). This means if an adversary gains possession of the server's RSA private key, even perhaps several years later, that's enough to decrypt the session key and thus decrypt all messages that adversary might have captured before.
Whereas with the schemes using Ephemeral Diffie Hellman (whether conventional or elliptic curve) once those ephemeral values are discarded going forward the only way to decrypt the messages secured by them would be something like Shor's algorithm to break DH, hence the term "Forward Secrecy".
[+] [-] some_furry|5 years ago|reply
It's impossible to accidentally encrypt a message with the asymmetric cryptographic primitive in the ECC case, but not in the RSA case. This makes ECC misuse-resistant in a way that RSA isn't.
(Although, strictly speaking, you can "encrypt directly" with elliptic curve schemes if you use ElGamal--which might even be desirable in weird systems. Fortunately, most high-level cryptography libraries that offer ECC don't expose the APIs to facilitate this.)
[+] [-] bjoli|5 years ago|reply
[+] [-] aeturnum|5 years ago|reply
[+] [-] dan-robertson|5 years ago|reply
1. Integers modulo a prime form a (cyclic) group
2. Cryptographic algorithms like Diffie–Hellman group exchange don’t really care about the integers modulo a prime and can be translated to other groups
3. The security of these algorithms rely on the discrete logarithm (computing a given g and g^a) being hard. For Diffie–Hellman, it is a related problem of computing g^{ab} given g, g^a, and g^b, which might be easier.
4. For integers modulo a prime discrete log is hard but not that hard. Security is measured in the number of bits of one-time-pad the security is equivalent to. It is generally believed that discrete log is harder in elliptic curves, such that a shorter elliptic curve problem (which also gives faster computation) is the same difficulty (ie security) as a larger mod p problem. This is the promise of elliptic curves.
Note here that factoring in general is not replaced: RSA, for which factoring is the important problem, relies on specific properties of modular arithmetic that aren’t really the case for general groups.
[+] [-] ddoolin|5 years ago|reply
[+] [-] dan-robertson|5 years ago|reply
[+] [-] hoppla|5 years ago|reply
[+] [-] LennyWhiteJr|5 years ago|reply
[+] [-] tptacek|5 years ago|reply
[+] [-] bannerts|5 years ago|reply
For example with bitcoin
[+] [-] layoutIfNeeded|5 years ago|reply
[+] [-] outlace|5 years ago|reply
[+] [-] bannerts|5 years ago|reply
[+] [-] er4hn|5 years ago|reply
Symmetric algorithms such as AES can have their strength reduced as well, but (I have no sources to cite) I believe this reduces it from 256-bit to 128-bit. At 128 bits of security it is still widely considered safe to use.
[+] [-] upofadown|5 years ago|reply
[+] [-] andy_ppp|5 years ago|reply
[+] [-] marcodiego|5 years ago|reply
[+] [-] runeks|5 years ago|reply
[+] [-] qorrect|5 years ago|reply
[+] [-] ACAVJW4H|5 years ago|reply
[+] [-] nathanfig|5 years ago|reply
[+] [-] speedgoose|5 years ago|reply
But bitcoin is a waste of resources by design. The whole point is to waste resources.
[+] [-] tylersmith|5 years ago|reply
[+] [-] er4hn|5 years ago|reply
A good analogy is password hashes. If you have a hashed value, it is expensive to find the original input. If you want to check that an input is equal to the hashed value, that is a cheap operation.
[+] [-] matvore|5 years ago|reply