Introduction to Blockchain’s Bedrock:- The Elliptic Curve secp256k1

The Curve That Keep The Bitcoin Secure

Saif Rehman

Published in

Coinmonks

8 min readSep 22, 2018

Disclaimer

I am the Jon Snow of Blockchain

This means that “I know nothing about Blockchain”. If there is any mistake please feel free to point out

AND ….. WE HAVE …..

Lots of math involved :)

Objectives

Understand the maths behind secp256k1’s Elliptic Curve Cryptography
Learn how to derive public keys with private key using Elliptic Curve Cryptography
Learn about PRNS (Pseudo Random Number Generator)
Sign and verify digital signatures mathematically
Implementing secp256k1’s Elliptic Curve Cryptography in Ruby

Prerequisites

Functional human brain :)
Ruby Basics
Basic mathematics concepts

Introduction

Bitcoin, a highly resilient technology, lives on the dirt of open internet for almost 10 years, and yet no one have successfully penetrated this network. The essence of this unbreachable security comes from various factors such as massive decentralization, proof of work consensus, and cryptography. In this article, we will cover cryptography aspect of Bitcoin. Bitcoin uses secp256k1’s Elliptic Curve as its bedrock cryptography.

Bitcoin Trust System vs Centralised Trust Systems

“Bitcoin fundamentally inverts the trust mechanism of a distributed system. Traditionally, as we see in payment and banking systems, trust is achieved through access control, by carefully vetting participants and excluding bad actors. This method of trust requires encryption, firewalls, strong authentication and careful vetting. The network requires investing trust in those gaining access.” — Andreas M. Antonopoulos

Bitcoin trust model is based mathematical computation which works game theoretical reward system rather than trusted access control which we find in traditional centralised systems. Trust in Bitcoin is achieved by solving a complex mathematical problems through Proof of Work Consensus. The difficulty of the mathematical computation grows extensively as the network grows to become more decentralised, this ensures that no bad actors or many bad actors combined can cheat, as they lack the computation to override the trust.

Let’s talk EEC in Layman’s Term

Let’s suppose you have Alice and Bob. Alice wants to send a transaction to Bob. In a case of a centralised system Alice needs to trust a middle man (Authorities) to validate and successfully send a transaction to Bob. The Authorities or Middleman needs to be very secure to make the system fool proof from the malicious actors (Hackers). However, centralised security is not a smooth honkey donkey kumbaya, where things remain safe and sound. We have seen a lot of times malicious hackers pranking these authorities to steal millions of dollars from their safe and sound security system. These systems also exploit your privacy as a basis of validation and security purposes.

HUH! Can we have a secure system without trusting third parties or intermediaries and without compromising our privacy?

So let’s us see how transaction happens in Bitcoin :)

In this case there is no third part involved. Also, Bob who is receiving the funds doesn’t need to have validation detail about Alice to prove the transaction. Transaction verifiability is done through mathematics not through central authorities. Alice has a secret key (Private key: which he knows only), he uses this secret key to encrypt the message and send the document to Bob along with his open secret key (Public key: which he can send to anyone). Bob decrypts the message with Alice’s public key to retrieve the original message.

For anyone to make transaction on a Bitcoin network, he/she should have a unique signature, this signature formed through pair of Public Key and Private Key. The Public Key is the shared key who anyone can see. Private Key is the secret key which shouldn’t be shared with anyone except the owner of that account. Bitcoin uses ECC to generate public key from private key. Elliptic curve uses a trap door function to make the function irreversible. In layman’s term, you can generate public key through private key, but not vice versa. A trapdoor function is a function that can only be computed one way. However, it is reversible if you have infinite computation resources, and you manage to live thousand of years

Elliptic curve uses Big Number mathematics that makes it impossible to bruteforce private keys with all the computational resources you can have right now :)

Bitcoin’s private and public key are so big that you need special libraries in Javascript such as BigNumberjs to handle them

So let’s dive a bit deeper :)

Elliptic Curve: Building blocks of a better Trapdoor

ECC is based on Private-Public Key Cryptography, such as RSA. However, ECC offers same security as RSA offers but with smaller key sizes. Since ECC has smaller key sizes it is less computationally intensive, hence it is ideal for mobile devices and networks

Elliptic Curve by defination

In mathematics, an elliptic curve is a plane algebraic curve defined by an equation of the form. that is non-singular; that is, it has no cusps or self-intersections.

In simple words Elliptic curve is set of point represented by a cubic equation on an imaginary grid that map out the solutions to a certain equation

Equation:- y2 = x3 + ax + b

This is how the curve looks [Credit: “Mastering Bitcoin 2nd Edition”]

Let’s walk through the algorithm

Assume there is a point “a”, and a point “b”
Note: If you are starting with “a”, point a is also known as seed
If a linear line is drawn from point “a”, and point “b”, it will intersect with a point “c”
Reflection of point “c” along with x axis will give another point called, which will equate to “a+b”, which is “-c”. “a+b” represent “a.b”
“a+b” actually represent ECC maths.
Draw another linear line from point “-c” to “a”. This will give you another intersection. Reflect it over x axis, this will generate another point
Also, there is a concept about max value in elliptic curve. Max value is determined by the key size and it represent a value in x axis in EC. If you increase the max value that is your key size, you increase the amount of values that can be used by intersecting linear lines through ECC curve.

ECC helps you to build a excellent trap door function. If you know the initial point “a” and “number of hops” to reach point “x”. it is very easy to find the point “x”. If you point “a”, and point “x”, it is impossible to “number of hops”

Public Key: Starting Point “a”, Ending Point “x”

Private Key: Number of hops from point “a” to “x”

Interesting characteristic of ECC

Any point on the curve can be reflected over the x axis and remain the same curve
Any non-vertical line will intersect the curve in at most three places
Domain parameters affect various attributes of a given curve

Implementing state of art secp256k1 ECC in Ruby

secp256k1 ECC Domain Parameters

The proven prime number p that specifies the size of the finite field

p = (2^256)-(2^32)–(2^9)–(2^8)–(2^7)–(2^6)–(2^4) -(1)

The coefficients a and b of the elliptic curve equation.

a = 0, b=7

The base point GG that generates our subgroup. This is also called the generator point

GG =(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)

The order n, which represent number of points in the field.

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

$point = GG, as mentioned above
$privKey = private key

Get more details about these parameters from here

Equation

publicKey = privateKey*generatorPoint

Helper functions

Function dectobin:- converts decimal to binary
Function dectohex:- converts decimal to hex
Function hextodec:- converts hex to decimal
Function stringtoint:- convert string to integer
Function generateSHA256:- generate sha256 hash of a given string

Function randomNumberGeneration:- The following implementation is Linear Congruential Generator xn = (a xn−1 + c) (mod m),
un = xn/m

$m = 2**32
$a = 1103515245
$c = 12345

These m,a,c values are the parameters of the Linear Congruential Generator

ECC Inverse, Add, Double, and Multiply function

Function modInverse:- This is Extended Euclidean algorithm. Pseudocode:-

function modInverse(a, b)
    s := 0;    old_s := 1
    t := 1;    old_t := 0
    r := b;    old_r := a
    while r ≠ 0
        quotient := old_r div r
        (old_r, r) := (r, old_r - quotient * r)
        (old_s, s) := (s, old_s - quotient * s)
        (old_t, t) := (t, old_t - quotient * t)

Function ECadd:- Add 2 points in the curve. This represent Elliptic Curve addition of two points . Pseudocode:-

function ECadd(a, b)lamAdd := ((b[1]-a[1]) * modInverse(b[0]-a[0],provePrimeNumber)) % provePrimeNumberx := (lamAdd*lamAdd-a[0]-b[0]) % provePrimeNumbery := (lamAdd*(a[0]-x)-a[1]) % provePrimeNumberreturn [x,y]

Function ECdouble:- squaring of a point. This represent Elliptic Curve’s square function. Pseudocode:-

function ECdouble(a)lam = ((3*a[0]*a[0] * modInverse((2*a[1])provePrimeNumber)) % provePrimeNumberx = (lam*lam-2*a[0]) % provePrimeNumbery = (lam*(a[0]-x)-a[1]) % provePrimeNumberreturn [x,y]

Function ECmultiply:- This represent Elliptic Curve’s Multiply Function which represent (Generator Point * privateKey)

function ECmultiply()N := privateKeyinBinary
Q := generatorPoint
m:= totalBitsInPrivateKeyfor i from 1 to m do
     N := ECdouble(N)
     if Q[0] := 1 then
         Q :=ECadd(Q, N)
  return Q

ECmultiply will get you the public key derived from private key. ECadd, ECdouble, and modInverse are the helper functions used in ECmultiply

Signature Generation and verification

Function SignatureGeneration function:- This function helps you create digital signed signature with private key

(x1,y1) := EccMultiply(genPoint,randomNumber)
r := x1 % numberOfPointInFeild
s := ((sha256HashOfMessage + r) * privKey) * modInverse(randomNumber)) % numberOfPointInFeild

Function SignatureVerificaion function:- This function helps you to verify if the document is sent and signed by the owner of the public key.

w := modInverse(s, numberOfPointsInFeild)point1 := EccMultiply(point,((hashOfThingToSign * w) % numberOfPointsInFeild))point2 = EccMultiply(publicKey,((r*w) % $numberOfPointsInFeild))x,y  = ECadd(point1,point2)if(x === r)return true ## it is validatedelsereturn false ## not validatedend

Full Code and Implementation in Ruby

SaifRehman/bitcoin-elliptic-curve

Contribute to SaifRehman/bitcoin-elliptic-curve development by creating an account on GitHub.

github.com

Future Work

Implementing segwits, multisig, and ZSNARKs. Also, login systems that uses elliptic curve cryptography

Conclusion

Other than ECC being used in Bitcoin as a mechanism to prove ownership and verify transactions, it is being used in various other application.

The U.S. government uses it to protect internal communications
The Tor project uses it to help assure anonymity
ECC provides signatures in Apple’s iMessage service
ECC is used to encrypt DNS information with DNSCurve
ECC is the preferred method for authentication for secure web browsing over SSL/TLS
And many other applications

Follow me for more: https://www.engineerability.com

Resources

Get Best Software Deals Directly In Your Inbox