Why does a 256-bit elliptic curve key provide equivalent security to a 3072-bit RSA key? What fundamental difference in attack complexity explains this?
Think about your answer, then reveal below.
Model answer: The best known attack on the elliptic curve discrete logarithm problem (ECDLP) in well-chosen curves is Pollard's rho algorithm, which runs in O(sqrt(n)) = O(2^{128}) time for a 256-bit curve. No sub-exponential algorithm analogous to the Number Field Sieve exists for ECDLP. For RSA, the GNFS runs in sub-exponential time L(1/3), so a 3072-bit modulus is needed to reach the same 2^{128} operation threshold. The absence of sub-exponential attacks on curves means shorter keys achieve the same security.
This efficiency gap exists because elliptic curve groups lack the special algebraic structure (smooth element orders, index calculus) that enables sub-exponential factoring and discrete logarithm algorithms in integer groups. The curves commonly used in cryptography are chosen specifically to resist all known structural attacks, leaving generic algorithms as the best approach.
Question 2 Multiple Choice
Points on an elliptic curve form a group under 'point addition.' What is the geometric intuition for this operation?
ATwo points are added by averaging their coordinates
BTo add points P and Q, draw the line through them. It intersects the curve at a third point R. The sum P + Q is the reflection of R across the x-axis
CPoints are added by concatenating their coordinate representations
DPoint addition is matrix multiplication of the coordinate vectors
This geometric construction defines an abelian group: the operation is commutative, associative, has an identity element (the 'point at infinity'), and every point has an inverse (its reflection across the x-axis). Cryptography uses this in the 'scalar multiplication' operation: computing nP = P + P + ... + P (n times). Given P and nP, finding n is the elliptic curve discrete logarithm problem. Over finite fields, the visual geometry no longer applies but the algebraic formulas derived from it are identical.
Question 3 Multiple Choice
NIST P-256 and Curve25519 are both widely used elliptic curves. Curve25519 was designed to be 'safe by default.' What design choices make it safer to implement?
ACurve25519 uses a larger field size, providing more security bits
BCurve25519 is a Montgomery curve designed for constant-time scalar multiplication, has no special points requiring edge-case handling, and uses a prime (2^255 - 19) that enables simple, fast modular arithmetic. NIST P-256 requires careful implementation to avoid timing side channels and has more complex formulas with edge cases
CCurve25519 uses post-quantum algorithms while NIST P-256 does not
DCurve25519 encrypts data directly while P-256 is only for key exchange
Curve25519 was designed by Daniel Bernstein with implementation safety as a primary goal. The Montgomery ladder for scalar multiplication naturally runs in constant time (no branches on secret data). The prime 2^255 - 19 is close to a power of 2, simplifying field arithmetic. The curve has cofactor 8, which is handled cleanly in the X25519 protocol. By contrast, NIST P-256's random-looking parameters have fueled suspicion of backdoors, and its Weierstrass form requires careful handling of the point at infinity and exceptional cases in addition formulas. Both curves are believed secure, but Curve25519 is much harder to implement incorrectly.
Question 4 True / False
Elliptic curve cryptography is vulnerable to Shor's quantum algorithm, just like RSA and classical DH.
TTrue
FFalse
Answer: True
Shor's algorithm solves the discrete logarithm problem in any finite abelian group, including elliptic curve groups, in polynomial time on a quantum computer. ECC's shorter key lengths actually make it slightly easier to attack with quantum computers than RSA (a 256-bit curve requires fewer logical qubits than a 3072-bit RSA modulus). This is why post-quantum cryptography research focuses on mathematical problems that resist quantum attacks: lattices, codes, multivariate polynomials, and isogenies. Current recommendations call for hybrid schemes using both ECC and post-quantum algorithms during the transition.
Question 5 True / False
The 'scalar multiplication' operation kP (adding a curve point P to itself k times) can be computed in O(log k) group operations using the double-and-add algorithm, even though it involves k additions.
TTrue
FFalse
Answer: True
Double-and-add is the elliptic curve analog of fast modular exponentiation (square-and-multiply). To compute kP, write k in binary. Scan bits from most significant to least: for each bit, double the current accumulator; if the bit is 1, also add P. A 256-bit scalar requires at most 256 doublings and 256 additions — O(log k) group operations. Without this, computing kP would require k - 1 additions, which for a 256-bit k is astronomically infeasible. This logarithmic cost is what makes ECC practical.