2
$\begingroup$

In the RSA algorithm it's the the integer factorisation problem, it's easy to multiply the two large primes to generate n, but given just n it's very difficult to find the constitutent primes.

In the Diffie Hellman key exchange it's the discrete logarithm problem with the same principles.

Maybe it's just because it's maths I don't entirely understand but what is the one-way-ness of ECC, you 'dot' points together repeatedly to generate your key (in essence I'm sure it's more complicated than that (if I'm wrong please correct me)). But what is it that Alice and Bob both know that allows them to generate the key, quicker than Eve can?

I hope this question makes sense, thanks in advance.

$\endgroup$
1
3
$\begingroup$

In typical ECC-based cryposystems, the one-way function is based on the Discrete Logarithm problem as in classical Diffie-Hellman key exchange; only working in a different finite group, built with the help of some Elliptic Curve over a finite field, rather than in the group obtained directly by multiplication modulo a prime.


In classical Diffie-Hellman key exchange with parameters a large prime $p$ and generator some integer $g$, the private key is some integer $x$, and the public key is $y=g^x\bmod p$. This is equivalent to multiplying $g$ by itself $x$ times in the multiplicative group $\mathbb Z_p^*$; though actually, this is done with $\mathcal O(\log(x))$ such modular multiplications, using e.g. exponentiation according to the binary representation of $x$.

In ECC, we just use a different group, and typically note the group law $+$ and the generator $G$ (uppercase is used for members of the group, while lowercase denotes integers). The private key is some integer $x$, and the public key is $Y=x\times G$. This is equivalent to adding the generator $G$ to itself $x$ times per the group law; though actually, this is done using $\mathcal O(\log(x))$ such additions in the group, using techniques as above.

In both cases, obtaining $y$ or $Y$ from $x$ is easy, but obtaining $x$ from $y$ or $Y$ is believed intractable (for proper choice of group and generator, and $x$ random in $[0,n)$ where $n$ is the order of the generator).

Elliptic Curve Diffie-Hellman works essentially identically as its classical counterpart in $\mathbb Z_p^*$, except that the Elliptic Curve group allows shorter public key and more efficient calculation for the same security level. The same transposition from $\mathbb Z_p^*$ to Elliptic Curve group works for ElGamal encryption (which becomes the basis of ECIES) and various signature algorithms including Schnorr and DSA (becoming EC-Schnorr and ECDSA).

$\endgroup$
3
  • $\begingroup$ Do you mean $[0,n]$? $\endgroup$ – forest Jun 19 '18 at 4:38
  • $\begingroup$ @forest: my $[0,n)$ means (integers in) $[0,n-1]$, with the convention that $g^0\bmod p=1$ or $0\times G=\infty$ where $1$ or $\infty$ is the group's neutral, and $n$ the order of $g$, that is the lowest positive $n$ with $g^n\bmod p=1$ or $n\times G=\infty$. $\endgroup$ – fgrieu Jun 19 '18 at 4:59
  • $\begingroup$ Ah thanks for pointing that out. Math is not my strong suite. :) $\endgroup$ – forest Jun 19 '18 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.