Having Fun With BN-curves

A demonstration of key sharing BN-curves is here.

Elliptic curves are used fairly extensively in public key encryption (such as in Bitcoin and Tor). A BN-curve (Barreto-Naehrig curve) [paper] defines an elliptic curve which can be used for pairings that allow for a high security and efficiency level. This article uses pairings over a 256-bit BN curve and derives a signature for a message, and also outlines a method for where Bob, Alice and Carol can generate a shared key.

Elliptic Curve key pairing is also used with zk-SNARKs and zero-knowledge proofs. It can be used for “encrypted multiplication”.

For an Elliptic Curve Cryptography (ECC) we generate a 256-bit random number for the private key (p), and then take a point (G) [x,y] on the Elliptic Curve and then multiply it by the private key to get another point (p×x,p×y). In this way we get P=p×G, and where G is a known point on the Elliptic Curve, P is our public key and p is our private key.

With pairings we can derive more complex relationships between the points, such as if P=G×p, Q=G×q and R=G×r, we can check to see if r=p×q, but where we only know P, Q and R (the public values). At the current time we cannot compute p from P=p×G, even if we know P and G. The exposure of the values is limited as we can calculate R=G×p×q, and where it is not possible to determine p or q.

The following code integrates the BN-256 code. Let’s test the code by simply creating a signature for a message. Bob will take a message and create a signature with his private key, and Alice will prove it with his public key.

First we take the message and hash it to a point on the elliptic curve (pt). Next we take the private key (priv) — a random 256-bit value — and multiple the point to give priv×pt. This is the signature. Bob then generates his public key by multiplying his private key (priv) by G to give priv×G. Alice will then take the message and hashes it to a point on the elliptic curve (pt). Next she multiplies this by Bob’s public key to get pub×pt. She also takes the signature (sig) and multiples it by G to get sig×G. If the signature is correct, the two values generated should match.

In the following we take a message of “hello”:

Message:	hello======================
Private key: 30004356452222922383849933778039944452315749064290473682127167271568896730865
Public key: ((51034946685813001170817435102353414123470700731734176493660185826748147116266,64210743524728530290185905551942812616400571488225773882109119010482573127691), (15434778760021406666927668640057214805094329177828734336347158339868964471406,1645883428099392092679734410866463344800887723192890577720280731380716208522))
======================Point for message (Pt): (16401638554737542226905570806322043806622525723234854083744567922111527431480, 25777301830215238716230693428646242503120247217966455808892851140680930083168)
Signature (p x Pt): (40232397439089775236199104399906464299782864194117440302779943704748308206467L, 0L)
Signature verified

So how do we generate a shared key between three parties? For this we can use a tripartite Diffie-Hellman algorithm [Paper] and what Bob (B), Alice (A) and Carol ( C) share their key pairings and then can calculate a shared secret key. In this case a, b and c are the private keys generated by Alice, Bob and Carol, respectively. Bob, Alice and Carol then generate key public keys from curves G1 and G2. In this case we show the keys for Alice, which are pa (pa=a×G1), and qa (qa=a×G2). Alice then calculate the shared key by taking the public values passed from Bob and Alice, and then multiplying it by her secret key (a).

For an Elliptic Curve we generate a 256-bit random number for the private key (p), and then take a point (G) [x,y] on the Elliptic Curve and then multiply it by the private key to get another point (p×x,p×y). In this way we get P=p×G, and where G is a known point on the Elliptic Curve, P is our public key and p is our private key.

With pairings we can derive more complex relationships between the points, such as if P=G×p, Q=G×q and R=G×r, we can check to see if r=p×q, but where we only know P, Q and R (the public values). At the current time we cannot compute p from P=p×G, even if we know P and G. The exposure of the values is limited as we can calculate R=G×p×q, and where it is not possible to determine p or q.

So let’s say I want to prove to you that I know the proof for:

2p+3q=5r

I can then give you p×G+q×G and r×G.

These values will be P, Q and R. Next you can check:

I can then give you 2P+3Q and 5R.

If it is correct, I have proven that I know p, q and r.

The values we have used are defined for the pairing are defined as a bilinear map, and following this:

e(P,Q+R)=e(P,Qe(P,R)

e(P+S,Q)=e(P,Qe(S,Q)

Our focus for this is to be able to add, subtract, multiply and divide encrypted values. With elliptic curve pairing we map GG1 to Gt using:

  • G1 and which is an elliptic curve for the equation y²=x³+b and includes the modulus of a prime number (N).
  • G2 and which is an elliptic curve which have the same points as G1 and which fit values of w - a “magic number” — for w¹²−18w⁶+82=0. I will describe this in another article.
  • Gt and which is the resulting object.

We will use the BN-256 code for the generation of a shared key between three parties (Bob, Alice and Carol). The pairings use two elliptic curves: G1 and G2. Each person will generate their public key from each of these curves. First Bob (B), Alice (A) and Carol (C ) generate their private keys (a, b and c) and which are random numbers. Next they create their pairings (qa, pa), (qb, pb) and (qc, pc). These will be:

pa=a×G1

qa=a×G2

pb=b×G1

qb=b×G2

pc=c×G1

qc=c×G2

If we take the example of Bob, then he will receive qa from Alice and pc from Carol, and then create a pairing and multiple by his private key (b). The result is the shared key:

In the following we show a sample run, where we have a, b and c, and then pa and qa shows the public key pairs generate from G1 and G2:

a: 15585509137055634653780920267499867667749383347757192778923961339942569565299
b: 60029002774682465108254798277591280438244150223969298935903764219550489193802
c: 15846580295924217287752788258479701128219354354539978050513156490847959205501
Pa (generated from G1): (4708197392703193344247672360038686476109976322859924235581151462879080669290, 50852043133057324279435698774966651150091574836400845774377671571284848642323)
Qa: (generated from G2) ((18550919239013274850405873281649705829864625210340015668056956170187622823852,29939050784041140151952967503521541817782995171721716111150020682300965837256), (7870327398054445275115241718819404091897514595081283555129878600498426440436,37380741146205866794231005458176633292045700231096747438290289256470956760655))
Key1: ((64519728215748815546320400599933073940888794114608194643996191938904339061488,11298349215645541740070246504033284004339276121397040899701028814946742258327),(42478464615339926194548095494486254912791792185847857967896310653258684412203,52940598857537364946198901656782904109873251325164604998888343385841150129112),(39138597081061029785267965076258561901836783687557610195665683807254820496817,9296877843963015660457920046710820674225439039191297383320574626179514619859))
Success. All keys are the same.
=====G1 and G2 used===========
G1= (1, 65000549695646603732796438742359905742825358107623003571877145026864184071781)
G2= ((21167961636542580255011770066570541300993051739349375019639421053990175267184,64746500191241794695844075326670126197795977525365406531717464316923369116492), (20666913350058776956210519119118544732556678129809273996262322366050359951122,17778617556404439934652658462602675281523610326338642107814333856843981424549))

A demonstration of this is here.

Go have some fun with BN-curves.

Coinmonks

Coinmonks is a non-profit Crypto educational publication.

Sign up for Coinmonks

By Coinmonks

A newsletter that brings you week's best crypto and blockchain stories and trending news directly in your inbox, by CoinCodeCap.com Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store