The elliptic-curve discrete logarithm problem (ECDLP) asks for the scalar k given a public base point G and its multiple A = kG. Elliptic-curve key exchange relies on the difficulty of recovering a private scalar from these public points. section 4.1.1
Its cryptographic role follows this sequence:
- Choose private integers k_A and k_B, then publish A = k_A G and B = k_B G. section 4.1.1
- Compute the shared point S from either k_A B or k_B A; both equal k_A k_B G. section 4.1.1
- Use the x-component of S, or selected bits from it, as input to a symmetric cipher such as AES. section 4.1.1
- Estimate security from the square-root attack cost: a 128-bit symmetric target requires about 256 bits in the relevant curve order or cardinality. section 4.1.1 section 14.1
For curves over prime fields, difficulty is governed by the size of the base-point order. Pairing-based systems must also account for attacks against the field extension, whose required sizes can grow faster because subexponential algorithms are considered relevant there. section 14.1
Alice and Bob
Alice publishes A = k_A G and Bob publishes B = k_B G. Alice computes k_A B, while Bob computes k_B A; each obtains the same point S without revealing either private scalar. section 4.1.1
