ECC Example

396 days ago by jimlb

We start by picking a secure elliptic curve.  This one is known as the 2013 Aranha–Barreto–Pereira–Ricardini Elliptic curve. It is given by $y^2 = x^3 + 117050x^2 + x$ defined over $\mathbb{Z}/(2^{221}-3)\mathbb{Z}$.

E=EllipticCurve(GF( 2^221 - 3),[0,117050,0,1,0]);E
 Elliptic Curve defined by y^2 = x^3 + 117050*x^2 + x over Finite Field of size 3369993333393829974333376885877453834204643052817571560137951281149 Elliptic Curve defined by y^2 = x^3 + 117050*x^2 + x over Finite Field of size 3369993333393829974333376885877453834204643052817571560137951281149
E.count_points()
 3369993333393829974333376885877457343415160655843170439554680423128 3369993333393829974333376885877457343415160655843170439554680423128

We now choose a point $P$.

P=E.gens()[0];P
 (1868095183606742538701435617698957211251810735713795112730238517387 : 1432401617868315471469241676678456314840808294315547381535466705153 : 1) (1868095183606742538701435617698957211251810735713795112730238517387 : 1432401617868315471469241676678456314840808294315547381535466705153 : 1)

The curve $E$ and point $P$ are public information for anyone to use.

Now Alice chooses her value $n_{A}$ and Bob chooses his value $n_{B}$.  They do not share these with each other or anyone else; $n_A$ is known only to Alice and $n_{B}$ is known only to Bob.

nA = 57; nB= 33718;nA; nB
 57 33718 57 33718

Alice computes $n_A P$ where $n_A P$ means $P$ added to itself $n_A$ times with elliptic curve addition.

QA = nA*P;QA
 (834563627127303790685975678053568676262249255365313011816986450875 : 2542773158243544588315226189616494365834003672489999487566995121426 : 1) (834563627127303790685975678053568676262249255365313011816986450875 : 2542773158243544588315226189616494365834003672489999487566995121426 : 1)

Alice now sends the point $Q_A$ to Bob over a public channel.  She can e-mail it, rent a billboard, run a commercial on TV, it doesn't matter.  It does not need to remain secret because the elliptic curve discrete logarithm problem says even if people know $P$ and $Q_A$, they cannot figure out $n_A$ from that information.

Bob computes $Q_B = n_B P$ and sends that to Alice.

QB = nB *P; QB
 (2886921535351916655416840363293190027932292275571972232770002735983 : 220388186157463434189363814060065157617702917957700613111275698967 : 1) (2886921535351916655416840363293190027932292275571972232770002735983 : 220388186157463434189363814060065157617702917957700613111275698967 : 1)

Once Bob receives the point $Q_A$, he computes $n_B Q_A$.  Alice receives the point $Q_B$ and computes $n_A Q_B$.

nB*QA;
 (1571090913228531175331750896159134780257063047826849902568683951702 : 1041500934751541413049387867604346233832745746882165650507938708155 : 1) (1571090913228531175331750896159134780257063047826849902568683951702 : 1041500934751541413049387867604346233832745746882165650507938708155 : 1)
nA*QB;
 (1571090913228531175331750896159134780257063047826849902568683951702 : 1041500934751541413049387867604346233832745746882165650507938708155 : 1) (1571090913228531175331750896159134780257063047826849902568683951702 : 1041500934751541413049387867604346233832745746882165650507938708155 : 1)

Bob and Alice now share the secret $2571462759950963338623653560522804306295245557988914858290462099836$.  They can use this as a key for AES to set up secure communication.