Blockchain basics — Elliptic Curve Cryptography
In The Matrix, The Keymaker controls access to key information. Which includes access to the door leading to The Architect. In the video clip above, The Keymaker tries to hand over a key integral for Neo’s path as The One to Niobi. And you might be wondering what does this have to Elliptic Curve Cryptography (ECC)?!
Well, let’s start with the basics of public key cryptography — which means that it is easy to secure information by keys that are based on mathematical functions that have a special property: it is easy to calculate them, but hard to find out how they were calculated. For example, the number 8,018,009 is the product of two prime numbers. It is trivial to generate it if the two prime numbers were known. However, unless one of the numbers (2003)is known, it is more difficult to derive the second (4003). Such functions are called trapdoor functions because they are difficult to reverse without prior knowledge of one piece of secret information.
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. However, in the energy intensive world of blockchain technology, it is not secure enough — RSA is still a trapdoor function and can be compromised without a sufficiently large key chain. Blockchain technology instead uses a more advanced category of mathematical functions based on arithmetic operations on an elliptic curve for which no known trapdoors are currently there.
breaking a 228-bit RSA key requires less energy to than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth.
A comparative view of RSA and ECC is nicely presented here and to visualise how much harder it is to break these encryptions, check out at your leisure the concept of Global Security from Lenstra here — note it is a slightly technical read.
In the section below, we will go a bit more into the details of how private and public key pairs are generated using ECC; and how hash functions are used with the public key as input to support a number of use cases.
The base relationship between a private key (k) and the public key (K) is:
K = k*G
k is any integer of 32 bytes (ie 256 bits). This can be generated for example by flipping a coin 256 times and recording the outcome (1 for Head and 0 for Tail). This serves as the private key and should be kept a secret by who generates it.
G is a point on the Elliptic Curve [y²= (x³+7) over a (finite) field of prime order p, where p = 2²⁵⁶- 2³²- 2⁹-2⁷-2⁶-2⁴-1]
The resulting curve is visually as a collection of points (shown in the image) — it isn’t a continuous curve as the values of x and y to satisfy this equation can only be a series of discrete numbers only. The equation is solved by perfoming modulus division — the equation above can be re written as y² mod p = (x³ + 7) mod p. The operator for this in python is %
One property of elliptic curves is that two points on the curve are added, the result is also another point in the elliptic curve. This means that if an integer k (acting as the private key) is multiplied with a discrete point G on the curve, the result is equal to G+G+…(k times) and it is a point again on the curve. The result K is called the public key and can be shared with others to access relevant encrypted information.
Another property of the elliptic curves is that whereas K = k*G is valid; the reverse operation is not possible — ie k !=K/G. So whereas the same point G is used in all programme implementations (eg OpenSSL, libsecp256k1) and combined with a random number k to generate a user’s public key K; it is not possible for anyone to perform a division of the published public key K with the (known and common value) of G (the generator point) to derive someone’s private key. This is the most important feature which enables the use of Elliptic Curve arithmetic for public key cryoptography.
In Ethereum, public keys are used to generate a number of related features. For example addresses that would seem like IBAN bank accounts (ICAP) and digital signatures. To understand how this happens, it is necessary to understand a feature called hashing. A hash function is loosely speaking a map — it maps an input data of arbitrary size to an output data of fixed size. The hashing function demonstrates a few key properties:
- Determinism -A given input message always produces the same output
- Verifiability — Computing the hash of a message is efficient
- Non correlation — A small change in the input message (even the least significant bit) produces a very different hash output; so it cannot be related to original input
- Irreversibility — Computing a message from its hash is not feasible — ie brute force search is not possible
- Collision protection — It should not be feasible for two input messages to result in the same hash output
Due to these properties, hashing allows a variety of use cases such as data fingerprinting, message integrity, authentication, unique identifiers etc. In Ethereum the keccak-256 algorithm is used to achieve hash outputs.
Now back to The KeyMaker from The Matrix. In the Ethereum world, The KeyMaker would be the wizard of keccak-256 and perform the magic and generate the various addresses — externally owned accounts (ie those that hold Ether) and smart contracts (those that contain business functionality) published on the blockchain. So, were a virtual world be create in the MetaVerse and humans’ consciously transferred over to there; The KeyMaker would be crucial for Neo to extract someone else from there. Or was it why the NSA is alleged to have placed a backdoor in the Dual_EC_DRBG ramdon number generator when the National Institute of Science and Technology attempted to standardise Keccak as part of the Federal Information Processing Standard (FIPS) 202 in 2015?! Read more about it here…
I hope this article has been useful to you — please feel free to leave comments and also what you would like to know more. I will continue with further posts with The Matrix as the inspiration for learning more about blockchain.