I was trying to come up with an idea for a short program in Rust that would help me systematize some things that I've already learned and wouldn't be a basic primer. I've decided to refresh my memory on some Elliptic Curve routines, specifically, adding points on EC. This way I am able two kill two birds with one stone, if you excuse my double avicide.

‍

Why to ECC?

What's the deal with EC? What's wrong with the good old RSA? In short, its primarily about the keys.

Symmetric and asymmetric ciphers can be assigned security classes that differentiate how difficult it is to break them. The strength of the algorithm (its resilience to cryptanalysis) and its key length are usually related. Most of the time, the longer the key (measured in bit-length), the stronger the algorithm. You can see several symmetric and asymmetric algorithms classified based on strength in the NIST 800-57 standard:

‍

‍

You can see that ECC algorithm with 256-383 bit key length (to simplify) is classified in the same strength class as RSA with a 3072-bit key. This means that you can you can have the same level of security in your cryptosystem with shorter keys with ECC as you would have with RSA. Shorter keys means less memory needed for key management, key transmission and more efficient execution of the crypto routines (I think :)).

‍

How to ECC?

EC-based algorithms are asymmetric which means that you are dealing with a keypair containing a private and a public key. Private key is your secret, public key you can distribute freely. Your friends can encrypt messages directed to you with the public key and you can decrypt them with the private key. You can sign your message using the private key and your friends can verified that it is you who signed it with the use of your public key. These capabilities are extremely useful in the blockchain world and in fact many blockchains rely on ECC (the secp256k1 curve specifically).

All of these amazing things can be done because the private and public keys in ECC are bound by a mathematical relationship: 

Pub = n * Base,

where:

Pub - public key point

Base - base point

n - your private key

‍

Ok, but how the hell do I multiply points, you might ask. This is actually pretty funny. So, something that not many people know is that you can define your own addition operation. Isn't this exciting? You just need to fulfill two simple requirements:

1. A + B = B + A, meaning, operation should give the same result no matter the component's order

2. (A + B) + C = A + (B + C), meaning that you can execute operations between components in any order and the result should be the same

If you have these two conditions fulfilled, you got yourself an addition my friend. Just be careful not to develop an additive homomorphism! Apologies for the level of jokes, it's Friday afternoon.

The addition of two points that belong to the EC are defined in mathematical formulas but they can be visualized using the EC's plot:

‍

‍

In order to add the points P and Q you need to draw a line through these points. At some point :) you will cut through the curve again. If that happens, take the point from the mirror reflection along the x-axis. This is your P+Q sum. And amazingly, this works as an addition! You can try and test it with various combinations of (A + B) + C, A + (B + C) and you will always arrive at the same result point.

When it comes to implementing all of these routines in the actual it gets a little bit more complicated. But the bottom line is, in order to multiply the base point P by n you just add the P point to itself n times.

If you are curious, feel free to check out my Rust implementation of the point addition on EC here!

‍