5 ms·

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' algori

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.

dan-robertson 6y ago
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.
- dan-robertson 6y ago
  Let me add to this by talking about cyclic groups. All cyclic groups are equivalent to addition modulo an integer, but they can be different computationally: to go from an element of your cyclic group to the equivalent integer may be very difficult. For addition modulo n, the computational Diffie-Hellman problem is effectively: Given integers 1, a, and b, compute ab. This is obviously easy. The problem of translating from an arbitrary cyclic group to addition mod n is the discrete log problem, so perhaps that explains why it is important to cryptography that it be hard for your group.

dan-robertson 6y ago

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.

dan-robertson 6y ago
Let me add to this by talking about cyclic groups. All cyclic groups are equivalent to addition modulo an integer, but they can be different computationally: to go from an element of your cyclic group to the equivalent integer may be very difficult. For addition modulo n, the computational Diffie-Hellman problem is effectively: Given integers 1, a, and b, compute ab. This is obviously easy. The problem of translating from an arbitrary cyclic group to addition mod n is the discrete log problem, so perhaps that explains why it is important to cryptography that it be hard for your group.