# 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? – mentallurg Dec 22 '20 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. – Reina Dec 22 '20 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. – dave_thompson_085 Dec 22 '20 at 2:37

## 1 Answer

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.