In the field of mathematics, I tried my best to explain the mathematical principles of cryptographic algorithms, but I failed, leading to the need to write a second version (Did someone not understand? Let’s try explaining the RSA encryption algorithm again).
These are just arithmetic. Something that sounds sophisticated like elliptic curves, I thought I could never understand. However, after self-studying a bit, I found the principles surprisingly easy (as for solving it manually like RSA, I’ll discuss that later when Teacher Xiao Mei teaches me).
Obtaining the Public Key
Let’s assume there is a special method that can only perform multiplication but not division (how to do that will be discussed later; after all, elliptic curves are still waiting in the wings), encryption becomes astonishingly simple.
You can randomly choose a large number k as the secret key (a secret that no one knows), and then select a constant G (just like π, everyone uses the same number). The public key K is simply k times G.
Done. Both the public key K and the private key k are ready.
How to Encrypt?
Randomly pick a number r. If you need to encrypt a message M, others can send you two numbers:
rG and M + rK
G is that constant, rG is r times the constant G, while K is k times the constant G. The two numbers above are actually:
rG and M + rkG
Can you see the difference on both sides? Apart from M, the left and right sides rG and rkG only differ by the secret key k.
During decryption, you just need to multiply the left number rG by the unknown secret key k, which gives you rkG. Subtracting rkG from the right number gives you the original M, right?
Simple, isn’t it? It seems a bit too simple, doesn’t it? What about elliptic curves? The more important question is, since I know the public key K, can’t I just divide by G to find your secret key?
Elliptic Curves
Now elliptic curves can make their entrance. They are essentially a clever construction that can only perform addition and multiplication but cannot reverse to perform division.
Let’s assume we set up a room filled with oddly shaped curved mirrors.
From a fixed, well-known point G, a laser beam is shot out. This laser continuously reflects off the mirrors. Each reflection is defined as one multiplication. For example, the point reached after a million reflections is defined as the original point multiplied by one million. Thus, if we know how the mirrors are arranged in the room, it is possible to calculate the point after a million reflections.
In reality, we don’t actually calculate a million reflections; there are efficient algorithms that can directly compute the 2nd, 4th, 8th, 16th, 32nd, and 64th reflections. Regardless of how large the number is, even for 2 raised to the power of 256, it would take at most 510 calculations because we can continuously double to approach the result.
However, if you are given a final point and asked how many reflections it took to reach that point from the initial one, that becomes problematic. Because you have no rough range, you can only try one by one, and after trying 2 raised to the power of 256, the universe would have already ended.
You might have guessed it; this room filled with mirrors is the elliptic curve. Bitcoin and Ethereum both use the secp256k1 parameters for their room arrangement, where the light reflects back and forth on the curved mirror defined by y^2 = x^3 – 7. G is a fixed number in the secp256k1 specification. The private key k is the number of reflections. Reflecting G k times gives you the public key K. Although I know the starting point of the light G and the endpoint K, I cannot calculate the number of reflections without exhaustive methods.
This constructs a magical multiplication operation that cannot perform division. The multiplication operation defined in this way is the simple and unbelievable encryption algorithm we started with.
Note 1: The most complex part is omitted here, which is that elliptic curves are continuous, and in reality, all point coordinates need to be integers and within a finite range. Therefore, mathematicians take modulo above a certain number (which is also fixed in the specification) to constrain all numbers within a finite possibility.
Note 2: Actually, we only need to transmit a single number m, where M is the point on the elliptic curve that satisfies x = m. After receiving M, the other party only takes x and ignores y.
Note 3: To define an elliptic curve algorithm, six parameters are needed. Passing six parameters each time is too complex, so the SEC organization directly fixed these six parameters, and everyone uses these six parameters, which is called the secp256k1 specification. Among them, the elliptic curve is defined as y^2 = x^3 – 7, and the coordinates of point G are fixed as (x,y):
x=0x79BE667EF9 DCBBAC55A0 6295CE870B0 7029BFCDB2 DCE28D959F 2815B16F817 98
y=0x483ADA7726 A3C4655DA4 FBFC0E1108A 8FD17B448A6 8554199C47D08 FFB10D4B8
Try it out with Python; the cube of x minus 7 equals y squared. The other parameters will be omitted for now (I haven’t figured them out yet).