4:07 PM

Definition of Elliptic curve cryptography:

Given an elliptic curve E, and a field GF(q), we consider the abelian group of rational points E(q) of the form (x, y), where both x and y are in GF(q), and where the group operation “+” is defined on this curve as described in the article elliptic curve. We then define a second operation “*” | Z×E(q) → E(q): if P is some point in E(q), then we define 2*P = P + P, 3*P = 2*P + P = P + P + P, and so on. Note that given integers j and k, j*(k*P) = (j*k)*P = k*(j*P). The elliptic curve discrete logarithm problem (ECDLP) is then to determine the integer k, given points P and Q, and given that k*P = Q.

It is believed that the usual discrete logarithm problem over the multiplicative group of a finite field (DLP) and ECDLP are not equivalent problems; and that ECDLP is significantly more difficult than DLP.

In cryptographic use, a specific base point G is selected and published for use with the curve E(q). A private key k is selected as a random integer; and then the value P = k*G is published as the public key (note that the purported difficulty of ECDLP implies that k is hard to determine from P). If Alice and Bob have private keys k_A and k_B, and public keys P_A and P_B, then Alice can calculate k_A*P_B = (k_A*k_B)*G; and Bob can compute the same value as k_B*P_A = (k_B*k_A)*G.

This allows the establishment of a “secret” value that both Alice and Bob can easily compute, but which is difficult for any third party to derive. In addition, Bob does not gain any new knowledge about k_A during this transaction, so that Alice’s private key remains private.