0
$\begingroup$

I have come up with the following rudimentary example of how ECC relates to asymmetric keys.

Is this a valid explanation of ECC and its relationship to asymmetry?

To only be deciphered by the person with the private key, it is necessary to use methods nontrivial in cryptography. To randomize the key, a set would be required to contain multiple solutions of which only one is the key. Primes are also used in ECC, so a useful approximation for implementation would be Gauss' approximation to primes.

$ x^2+xy+x−y^3$ will be used as the basis for this example.

A random point may be selected from within the area of the curve, generated by a set of functions and a rotating exchange of variables.

The shake in the cipher would be:

$k(n)+(−y^3)+x+xy+x^2=kG$ for:

$k(n)+(−y^3)+x+xy+x^2=k$

There are four solutions for $y$ which allows one to be a random key in this example. The asymmetry comes from the rotation of solutions to $y$, coupled with having to know that $y$ is the variable to be solved for.

Is this a good basic example of ECC?

For proof let Alice create the message $k$, and then create $kG$. Bob receives $kG$ and has been told by Alice in a separate message that the key is negative and a solution for $y$. Thus Bob knows to decipher $kG$ he must use:

$$y = -\frac{2^{1/3} x}{(\sqrt{(-27 k(n)+27 k-27 x^2-27 x)^2-108 x^3}-27 k(n)+27 k-27 x^2-27 x)^{1/3}} - \frac{(\sqrt{(-27 k(n)+27 k-27 x^2-27 x)^2-108 x^3}-27 k(n)+27 k-27 x^2-27 x)^{1/3}}{32^{1/3}}$$

Curve

To summarize and make my question as explicit as possible, is this a workable example for how asymmetry relates to ECC?

$\endgroup$
4
$\begingroup$

In short: the question does not explain well the notion of asymmetry in ECC; and the exposition is not how Elliptic Curve Cryptography works. A reasoning sidestepping the notion of Discrete Logarithm Problem over a finite group can not really explain asymmetry as meant in ECC.

Asymmetry is in the knowledge Alice and Bob have about the key, not asymmetry of a curve, or even asymmetry in variables in the equation, or different forms of the curve's equation. Foremost, ECC does not work as explained. Among discrepancies:

  1. The variables in the "curve" are on discrete sets like $\mathbb Z_p$ or $\mathbb Z_{2^k}$, not real numbers $\mathbb R$; that makes a hell of a difference to the appearance of the "plot" of a curve with a given equation. A plot using real variables is traditionally used to illustrate how the group law is built; but (since a curve is with real variables, and it is used discrete ones in actual use) this is not how things are actually being used in ECC. Update: The Ars Technica article (page 2) quoted in comment does a good job explaining this.
  2. The curve/equation is there to define an appropriate finite group (typically: where the Discrete Logarithm Problem is hard), and the actual crypto is built on top of that. There's no viable exposition of ECC (that I know) short of building that finite group structure. Update: the Ars Technica article does not even mention group, or associativity of the "dot" law.
  3. Typically, the asymmetry lies in the difficulty of
    • computing $G+G+\dots+G$ repeated $k$ times in the group defined by the curve, which is easy;
    • finding $k$ from $kG$ (that is, $G+G+\dots+G$ repeated $k$ times), which is believed intractable.
  4. ECC encryption schemes (that I know) do not work as stated in the question. In particular $k$ is not a message, but is the private key; $kG$ is the public key, and is unrelated to the message. That's perhaps because the Ars Technica article does not explain ECC encryption (it introduces asymmetric encryption using RSA in a very naive setup, but there's no viable transposition of that to ECC).

In order to introduce "how ECC relates to asymmetric keys" to a classroom (if that must be done for some reason), I suggest:

  • introducing post-symmetric cryptography with Diffie-Hellman key exchange, defined on a finite group initially illustrated by the relatively familiar $\mathbb Z_p^*$, because that's by far the simplest example;
  • probably, using as the defining problem for asymmetric cryptography signature (illustrated by El Gamal signature or its common variant DSA) rather than encryption (illustrated by El Gamal encryption), because the former is simpler;
  • showing that an appropriate Elliptic Curve equation over a (finite commutative field) can be be used to define a finite group usable for the above purposes;
  • stating that this is computationally attractive for a given security level, hence the growing interest in ECC (a true justification requires examining the running time of various known algorithms for solving the DLP, as well as introducing as competitor factorization-based asymmetric cryptography, probably RSA).
$\endgroup$
  • $\begingroup$ My example is based on the following ArsTechnica article: arstechnica.com/security/2013/10/… $\endgroup$ – user21742 Feb 9 '15 at 12:24
  • $\begingroup$ Although, I'm curious why you don't consider the set ${x,y,k}$ in $G$ a finite group given that it satisfies membership of $Z_2k$ given the solutions to $y$. Also, only Bob knows which one of the solutions to $y$ to use after calculating it and this seems to satisfy both being discrete as well as being asymmetric. $\endgroup$ – user21742 Feb 9 '15 at 12:31
  • $\begingroup$ I am confused now @fgriue, you stated the public key is the coordinate of kG, which I can understand is not the same as a coordinate (x,y) but the solutions of $y$ are elements of (kG) are they not? And in your last comment you said a point on the curve is not the encoded message, which I understand, but if in my rudimentary example (this will be used to teach undergraduates once I hammer out the details) one of the solutions of y is used to extract the key and only Bob knows which solution is capable of this wouldn't that be asymmetric? $\endgroup$ – user21742 Feb 9 '15 at 18:36

Your Answer

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