ECC Example

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