# Diffie-Hellman Key Exchange

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.

• What have you done so far? Dec 22, 2020 at 1:43
• 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. Dec 22, 2020 at 1:47
• 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. Dec 22, 2020 at 2:37

• 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.
• 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.