Nice article! I have a question about the base point, "G":
First, we have Alice. Alice has chosen a random private key (scalar) a from our group [1, l-1]. Her public key is A = aG.
Similarly, Bob chooses random private key b. His public key is B = bG.
- How do Bob & Alice agree on a base point G?
- If G is publicly known, and Bob & Alice's public keys are publicly known, isn't it easy to derive the private key? e.g.
A=aG, and A and G are known, so we can easily derive a.
This is known as the ECDLP (Elliptic Curve Discrete Logarithm) problem/assumption. Security of all elliptic curve crypto systems depend on the intractability of finding such x that P = xG given P and G (at least beyond brute-forcing x's -- curve points cannot be divided).
Consider in the case of Monero, roughly 50% of potential x's are between 2^251 and 2^252. Brute-forcing takes an impossible amount of time (and space if you want to store your results for future use); you must add G to itself over and over until you reach P. I believe some algorithms are faster than this simple brute-force, but not so significantly to cause security to be in question.
Imagine if you could brute-force additions are the rate that the Bitcoin network produces SHA256 hashes. That is approximately 1.5 exahashes / sec. 1,500,000,000,000,000,000 hashes / sec
To add until you get to the size of an "average" x would then take 2^251 / 1.5 quintillion operations.
2.41 x 10^57 seconds
2.79 x 10^52 days
76,494,647,147,516,723,891,987,850,531,064,965,339,393,857,196,035 years
Now to store these for future use you need 2^252 * 32 (bytes) of storage space. That's:
231,584,178,474,632,390,847,141,970,017,380,000,000,000,000,000,000,000,000,000,000,000 1 TB hard drives.
If each hard drive was 1mm cubed, we'd need roughly:
2.31 x 10^47 cubic kilometers of hard drives, which is roughly:
273,479,829 cubic light-years.
Let me know when you want to get started. ^_^