0
$\begingroup$

I apologize if this is in the wrong section. I am completely new to Cryptography. I was presented with the following problem and I am trying to find something that will explain to me how to proceed.

Demonstrate the Diffie-Hellman key exchange using an elliptic curve y^2 = x^3 + ax + 9 mod p, where p = 223. Use XA = 8, XB = 15. Find a perfect generator point or a generator point with the highest order if a perfect generator cannot be found for the first 30 points. List the values of the order of both the elliptic curve and generator point.

$\endgroup$
3
  • $\begingroup$ What have you done so far? $\endgroup$ – mentallurg Dec 22 '20 at 1:43
  • $\begingroup$ I have gone over the slides provided to us but nothing that explains how something like will be solved. I have also looked online for video tutorials but no luck. I don't know if maybe I am approaching this the wrong way, I mean I can't believe that there is nothing out there that explains an example like this. $\endgroup$ – Reina Dec 22 '20 at 1:47
  • 2
    $\begingroup$ Although it mentions DH, your homework isn't really about DH, but the basics of (short-Weierstrass) elliptic curves which are used for multiple cryptographic schemes including ECDSA, ECDH, ECMQV. wikipedia has a good summary and (unsurprisingly) lots of references. In practice people use only much larger and standardized curves, which is why you don't find many examples of toy nonstandard curves. $\endgroup$ – dave_thompson_085 Dec 22 '20 at 2:37
2
$\begingroup$

This homework is about constructing a tiny finite Elliptic Curve group over a prime finite field, then showing Diffie-Hellman key exchange on that.

It's needed to understand

  • Modular arithmetic$\pmod p$, that is computation (including division) in the finite field of integers modulo $p$ (here $p=223$ but the same techniques apply for any prime $p$).
  • The notion of set of pairs $(x,y)$ matching an equation $y^2 = x^3 + a\,x + b $ in that finite field.
  • Under some conditions on constants $a$ and $b$, construction of a finite Elliptic Curve group on that set (with one extra identity element added). With the problem as we get it, it must be used $b=9$, and $a$ is left at the discretion of the reader.
  • The notion of order of a group/curve, and of order of an element in the group (a perfect generator is to be understood as an element of order the order of the group; equivalently, adding the element to itself repeatedly reaches every element of the group).
  • Diffie-Hellman key exchange on an arbitrary finite group with a states generator. That's the easy part. "Use $X_A = 8, X_B = 15$" is to be used in that part only; that would be the values chosen by parties.

Because $p$ is so small, it's possible to get away with explicitly finding the points $(x,y)$ forming the (non-neutral) elements of the group. In actual cryptography, we'd get say $p\approx2^{256}$ and about as many points, thus point counting would probably use the Schoof–Elkies–Atkin algorithm, that many users of crypto, including me, have never actually studied.

$\endgroup$

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.