The collection consists of 4 components; every half makes use of the ideas found within the earlier components:
- The Magic of Elliptic Curves
- The Magic of Elliptic Curves Mixed with Finite Fields
- Utilizing The Magic of Elliptic Curves to Signal and Confirm Messages
- ECDSA Implementation in Python Utilizing Zero Dependencies [you’re here]
The bottlenecks:
- We’d like to have the ability to carry out primary arithmetical operations on very giant numbers. In programming we will simply function on giant numbers, utilizing bignum arithmetic. Simply google it, and you can see out how simple it’s.
So our programming language should assist it, or we must always use some exterior bundle to work with it.
Within the examples of this half, I’ll use Python, which helps bignum arithmetic out of the field.
For the Dwell Demo, I’ll use JavaScript, and there we’ll want the BigNumber.js bundle. - The opposite bottleneck that we are going to encounter is discovering the multiplicative inverse of a really giant quantity. Clearly, brute drive just isn’t going to work.
The multiplicative inverse could be discovered by the Prolonged Euclidean algorithm, which has the complexity of O(log(n)). Python (3.8+) can do it out of the field with its built-in pow perform:
def find_inverse(quantity, modulus):
return pow(quantity, -1, modulus)
When you want the precise implementation of the algorithm, test my Dwell Demo!
Let’s begin writing our code!
We’d like one easy factor, associated to the elliptic curve: Level. Let’s outline a category Level. In its constructor, we must always make test, whether or not the purpose lies on the curve:
class Level:
def __init__(self, x, y, curve_config):
a = curve_config['a']
b = curve_config['b']
p = curve_config['p']
if (y ** 2) % p != (x ** 3 + a * x + b) % p:
elevate Exception("The purpose just isn't on the curve")
self.x = x
self.y = y
self.curve_config = curve_config
We’d like to have the ability to evaluate two factors, add them collectively, and multiply them by an integer.
Let’s add a technique to test if two factors are equal:
def is_equal_to(self, level):
return self.x == level.x & self.y == level.y
Now let’s implement add technique, which returns a brand new Level as the results of addition:
def add(self, level):
p = self.curve_config['p']
if self.is_equal_to(level):
slope = (3 * level.x ** 2) * find_inverse(2 * level.y, p) % p
else:
slope = (level.y - self.y) * find_inverse(level.x - self.x, p) % p
x = (slope ** 2 - level.x - self.x) % p
y = (slope * (self.x - x) - self.y) % p
return Level(x, y, self.curve_config)
All of the formulation are listed in Half 2.
Now let’s implement the multiply technique:
Probably the most simple implementation can be this:
def multiply(self, occasions):
level = self
for i in vary(occasions - 1):
level = level.add(self)
return level
However let’s say we have to multiply our level by an enormous quantity: 115792089237316195. Even when we had the velocity of 1 billion additions per second, this may take 3.6 years to calculate this level!
And this isn’t even an enormous quantity for us! Here’s a large quantity:
115792089237316195423570985008687907852837564279074904382605163141518161494337
Calculating the purpose on this method would take billions of billions of billions of billions… of years!
We will outline that the effectivity of this algorithm above is O(n), which is of no use for our functions. When you bear in mind, there’s a straightforward technique to obtain O(log2(n)) complexity by constantly doubling our level:
2P = P+P
4P = 2P + 2P
8P = 4P + 4P
16P = 8P + 8P
32P= 16P + 16P
64P = 32P + 32P
And so log2(115792089237316195) = 56
log2(115792089237316195423570985008687907852837564279074904382605163141518161494337) = 256
So we don’t want billions of billions of billions… of years. We simply want 256 operations to get to this massive level!
Only one second: to effectively multiply by values that aren’t a level of two, it’s affordable to retailer all of the earlier values, after which mix the outcomes collectively.
For instance, if we have to get 100P, we will now not double 64P. Neither we will add factors one after the other: probably this may take billions of billions of years on bigger numbers. What’s affordable to do as an alternative, is:
96P = 64P + 32P
100P = 96P + 4P
So for that objective, we have to retailer all of the earlier P’s and afterwards effectively use them.
So right here is an environment friendly implementation:
def multiply(self, occasions):
current_point = self
current_coefficient = 1
pervious_points = []
whereas current_coefficient < occasions:
# retailer present level as a earlier level
pervious_points.append((current_coefficient, current_point))
# if we will multiply our present level by 2, do it
if 2 * current_coefficient <= occasions:
current_point = current_point.add(current_point)
current_coefficient = 2 * current_coefficient
# if we will not multiply our present level by 2, let's discover the most important earlier level so as to add to our level
else:
next_point = self
next_coefficient = 1
for (previous_coefficient, previous_point) in pervious_points:
if previous_coefficient + current_coefficient <= occasions:
if previous_point.x != current_point.x:
next_coefficient = previous_coefficient
next_point = previous_point
current_point = current_point.add(next_point)
current_coefficient = current_coefficient + next_coefficient
return current_point
Thus we’ve obtained an excellent environment friendly implementation! And now we will carry out all of the wanted operations on an elliptic curve.
Let’s outline secp256k1:
secp256k1_curve_config = {
'a': 0,
'b': 7,
'p': 115792089237316195423570985008687907853269984665640564039457584007908834671663
}
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
g_point = Level(x, y, secp256k1_curve_config)
I’m utilizing solely decimal numbers in our examples as a result of they’re intuitive for a human.
To date we’ve carried out every part that we mentioned in Half 2. Now let’s implement the precise digital signature algorithm, described within the Half 3.
Signal technique of ECDSA:
def sign_message(message, private_key):
ok = random.randint(1, n)
r_point = g_point.multiply(ok)
r = r_point.x % n
if r == 0:
return sign_message(message, private_key)
k_inverse = find_inverse(ok, n)
s = k_inverse * (message + r * private_key) % n
return r, s
Confirm technique of ECDSA:
def verify_signature(signature, message, public_key):
(r, s) = signature
s_inverse = find_inverse(s, n)
u = message * s_inverse % n
v = r * s_inverse % n
c_point = g_point.multiply(u).add(public_key.multiply(v))
return c_point.x == r
Let’s decide some random quantity as our non-public key, for instance, 123456789012345.
Let our message be 12345.
Do you bear in mind how one can get PublicKey from PrivateKey?
private_key = 123456789012345 # any random integer
public_key = g_point.multiply(private_key)
message = 12345 # any integer
Now let’s signal and attempt to confirm:
signature = sign_message(message, private_key)
print('Signature: ', signature)
print('Is legitimate: ', verify_signature(signature, message, public_key))
It really works! You’ll be able to attempt to corrupt the signature or the unique message and guarantee that our algorithm works correctly.
Right here is the entire code:
import random
def find_inverse(quantity, modulus):
return pow(quantity, -1, modulus)
class Level:
def __init__(self, x, y, curve_config):
a = curve_config['a']
b = curve_config['b']
p = curve_config['p']
if (y ** 2) % p != (x ** 3 + a * x + b) % p:
elevate Exception("The purpose just isn't on the curve")
self.x = x
self.y = y
self.curve_config = curve_config
def is_equal_to(self, level):
return self.x == level.x and self.y == level.y
def add(self, level):
p = self.curve_config['p']
if self.is_equal_to(level):
slope = (3 * level.x ** 2) * find_inverse(2 * level.y, p) % p
else:
slope = (level.y - self.y) * find_inverse(level.x - self.x, p) % p
x = (slope ** 2 - level.x - self.x) % p
y = (slope * (self.x - x) - self.y) % p
return Level(x, y, self.curve_config)
def multiply(self, occasions):
current_point = self
current_coefficient = 1
pervious_points = []
whereas current_coefficient < occasions:
# retailer present level as a earlier level
pervious_points.append((current_coefficient, current_point))
# if we will multiply our present level by 2, do it
if 2 * current_coefficient <= occasions:
current_point = current_point.add(current_point)
current_coefficient = 2 * current_coefficient
# if we will not multiply our present level by 2, let's discover the most important earlier level so as to add to our level
else:
next_point = self
next_coefficient = 1
for (previous_coefficient, previous_point) in pervious_points:
if previous_coefficient + current_coefficient <= occasions:
if previous_point.x != current_point.x:
next_coefficient = previous_coefficient
next_point = previous_point
current_point = current_point.add(next_point)
current_coefficient = current_coefficient + next_coefficient
return current_point
secp256k1_curve_config = {
'a': 0,
'b': 7,
'p': 115792089237316195423570985008687907853269984665640564039457584007908834671663
}
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
g_point = Level(x, y, secp256k1_curve_config)
def sign_message(message, private_key):
ok = random.randint(1, n)
r_point = g_point.multiply(ok)
r = r_point.x % n
if r == 0:
return sign_message(message, private_key)
k_inverse = find_inverse(ok, n)
s = k_inverse * (message + r * private_key) % n
return r, s
def verify_signature(signature, message, public_key):
(r, s) = signature
s_inverse = find_inverse(s, n)
u = message * s_inverse % n
v = r * s_inverse % n
c_point = g_point.multiply(u).add(public_key.multiply(v))
return c_point.x == r
# check begins right here
private_key = 123456789012345 # any random integer
public_key = g_point.multiply(private_key)
message = 12345 # any integer
signature = sign_message(message, private_key)
print('Signature: ', signature)
print('Is legitimate: ', verify_signature(signature, message, public_key))
So the implementation of all the ECDSA algorithm took simply 100 strains of code! And it’s completely working. That is completely the identical algorithm because the one utilized in Bitcoin!
As I promised at the start of this text, right here is the reside demo utilizing solely the ideas and formulation described within the article. Simply a few notes:
- Initially, we might solely signal integer messages. However within the demo, you may select to use a hash perform (sha256) to your message. Due to it, a message generally is a string.
- Bitcoin makes use of barely totally different codecs of public keys and signatures.
- By no means use it in a manufacturing atmosphere! It’s not protected. For manufacturing, it’s essential to solely use well-tested options.
I hope this collection of articles was very helpful for you. At the least, I did my greatest to make it helpful. Be happy to share it with buddies or use any piece of it wherever. Simply please depart a hyperlink to the unique article.
Be happy to contact me and ask questions:
exemak@gmail.com
t.me/exemak
Mikhail Karavaev
