New blogpost on building post-quantum pseudorandom functions from isogeny-based cryptography! Click here to see it.

-M x

Skip to content
# Tag: elliptic curves

## Pseudorandom Functions from Isogenies

## Asiacrypt 2020

## Maths Behind Bitcoin

### Algorithms

### Elliptic Curves

### Finite Fields

### ECDSA

### Bitcoin Addressess

### How Bitcoin Actually Works

## Elliptic Curve Cryptography

New blogpost on building post-quantum pseudorandom functions from isogeny-based cryptography! Click here to see it.

-M x

New blogpost on the isogeny-based talks at Asiacrypt 2020! Just short descriptions of each paper for those who couldn’t attend or those interested in the most current research in isogeny-based cryptography.

Hope you enjoy! M x

Bitcoin is a “worldwide cryptocurrency and digital payment system” that works without a central repository or single administrator. This system is *peer-to-peer* meaning that each computer can act as a server for the others, which allows for transactions to take place between users directly without an intermediary (or *central server*).

Bitcoins are not stored centrally, but rather exist as records in the *block chain*, which is a “distributed ledger”. To own a bitcoin simply means to have the ability to transfer control of it to someone else by creating a record of the transfer in the block chain. This ability is granted by access to an ECDSA (Elliptic Curve Digital Signature Algorithm) private and public key pair. What does this mean?

An algorithm is a process to make calculations. They are like machines: data comes in, and the algorithm does some work, and data comes out. ECDSA is the algorithm that creates the Bitcoin key pairs. To create a new key pair the elliptic curve is plotted across a finite field.

An elliptic curve is represented algebraically as an equation of the form:

y^{2} = x^{3} + ax + b

Elliptic curves have useful properties, such as a non-vertical line intersecting two non-tangent points on the curve will **always** intersect a third point on the curve. Furthermore, if the non-vertical line intersects a point tangent to the curve it will intersect **precisely** one other point. Using these properties it is possible to define two operations:

**Point Addition**: P + Q = R is defined as the reflection through the x-axis of the third intersecting point R’ on a line that includes P and Q.

**Point Doubling**: P + P = R is defined by finding the line tangent to the point being doubled and taking a reflection through the x-axis of the intersecting point R’ on the curve.

In relation to ECDSA, a finite field is a predefined range of positive numbers within which every calculation must fall. If a number is outside of this range, it will *wrap around* so that it does fall within this range.

In order to understand, consider taking the modulus operator. For example, mod 7: here the finite field is modulo 7 and all answers in this field lie in the range 0 – 6.

Bitcoin defines the formula for the curve and the parameters of the field so that every user has the same graph. The parameters include:

- the equation used;
- the prime modulo of the field;
- a base point that falls on the curve.

The order of the base point is not independent of the other parameters, and can be thought of graphically as “*the number of times the point can be added to itself until its slope is infinite.”* The base point is selected so that the order is a large prime number.

In the case of bitcoin:

Elliptic Curve Equation:y^{2}= x^{3}+ 7

Prime Modulo:2^{256}– 2^{32}– 2^{9}– 2^{8}– 2^{7}– 2^{6}– 2^{4}– 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Base Point:04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Order:FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141Source: coindesk.com

In ECDSA the private key is chosen as a number between 1 and the order. Then the public key is given by:

**public key = private key * base point**

Practically, the computation of the public key is broken down into point doubling and point addition operations starting from the base point.

This shows that the maximum number of private keys possible is equal to the order. However, Bitcoin has an enormous field:

There are 10^82 atoms in the universe. If you made the entire Universe our finite field and you drew a giant elliptic curve through it, each “point” in the universe would about 300 square atoms.At that size, each cell in your body takes up the space of 1,150,000,000 Bitcoin key pairs.– www.cryptocoinsnews.com

A Bitcoin address is not a public key; it is an RIPEMD-160 hash of an SHA256 hash of a public key. SHA256 and RIPEMD-160 are also algorithms that, unlike ECDSA, generate a hash. I have taken an example from cryptocoinsnews to illustrate a simple example of a hash (SHA256 and RIPEMD-160 are much more complex):

Every letter has a value of its position in the alphabet: A = 1, B = 2, etc.

Our hash algorithm is this:for i=0 to len(word):

h = h + (i + letter_value)So for the word “ABC” using our hash would be:

Loop for ‘A’

h = 0 + (0 + 1)

Loop ‘B’

h = 1 + (1 + 2)

‘C’

h = 4 + (2 + 3)

h = 9‘ABC’ hashes to 9.

Your private key is kept secret. This key allows you to unlock funds that are owed to you in the Bitcoin block chain.

When making a transacting, it contains a script that has your private key’s signature and the matching public key. This is in order to prove that the public key provided matches the private key that was used to make the signature. If the public key hashes with the Bitcoin address in the unclaimed transaction, it can be spent.

Hope you enjoyed this basic explanation of Bitcoin! M x

__What are Elliptic Curves?__

An elliptic curve is a cubic curve whose solutions are confined to a region of space that is topologically equivalent to a torus (doughnut-like shape). It’s defined by an equation in the form:

where

as this ensures that the curve has no singular points (the curve is nice and smooth and doesn’t contain any sharp points or cusps).

They have shown potential as a tool for solving complicated number problems. Additionally, in the last few decades there has been a lot of research into using elliptic curves for encryption instead of RSA encryption to keep data transfer safe online.

__Elliptic Curve Cryptography__

Elliptic Curve Cryptography is an example of public key cryptography. This is when the messages are encrypted using a public key. Decryption is then only possible using a mathematical private key, which is almost impossible to determine if you only know the public key.

Elliptic Curve cryptography is based on the difficulty of solving number problems involving elliptic curves.

Bellow are some examples of elliptic curves:

For uses in cryptography a and b are required to come from special sets of numbers called finite fields (a field that contains a finite number of elements).

__Adding Points__

Let’s consider the curve

and the two points A = (2,1) and B = (-2, -1), both of which lie on the curve. Now, we want to find an answer to A = B, which should also lie on the elliptic curve.

Thus, by joining the points A and B with a straight line, we can see that it intersects the curve in one more place, point C. We then reflect this point in the x – axis and define it as point C’. Therefore,

A + B = C’.

In our example this means that

(2,1) + (-2,-1) = (1/4, -1/8)

The only situation where C’ is not equal to A + B is when B is a reflection of A in the x-axis. In this case, the line we use to define the sum is vertical and there isn’t a third point at which it meets they curve.

Below is an image to depict the different cases which may arise with different points:

It turns out that, given two points A and B on an elliptic curve, finding a number *n* such that **B = nA** can take an enormous amount of computing power, especially when *n* is large. In elliptic curve cryptography points A and B can be used as a public key and the number *n* as the private key. Anyone can encrypt a message using the publicly available public key, but only the person in possession of the private key – the number *n* – can decrypt them.

__Advantages__

Elliptic curve cryptography has some advantages over RSA cryptography, which is based on the difficulty of factorising, as fewer digits are required to create a problem of equal difficulty. Therefore data can be encoded more efficiently and rapidly than using RSA encryption.

However, no one has proved that it has to be difficult to crack elliptic curves, and in fact there may be a novel approach that is able to solve the problem in a much shorter time. Indeed many mathematicians and computer scientists are working in this field.

So what are your thoughts on elliptic curve cryptography? M x