Welcome to our comprehensive guide on implementing the Elliptic Curve Korean Certificate-based Digital Signature Algorithm or shortly EC-KCDSA using Python from scratch. In the realm of cryptography, the EC-KCDSA has emerged as a prominent algorithm, specifically designed for secure digital signatures based on elliptic curves. Elliptic curve-based algorithms have gained significant popularity due to their robustness and efficiency, making KCDSA a powerful tool for ensuring data integrity and authenticity. In this tutorial, we will explore the fundamentals of elliptic curve cryptography and walk you through the step-by-step process of building an Elliptic Curve KCDSA implementation in Python, starting from the ground up. Whether you’re a cryptography enthusiast or a developer seeking to understand the inner workings of this algorithm, join us on this exciting journey as we unlock the secrets of the Korean Certificate-based Digital Signature Algorithm.
Curve Form
Firstly, we are going to decide the elliptic curve form because we will have different addition laws according to the curve. Weierstrass, Koblitz, Edwards and Twisted Edwards are the most common elliptic curve forms. We will adopt Weierstrass curves in this experiment. This curve satisfies y2 = x3 + ax + b equation and it comes with the following addition law.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
def add_points(P, Q, p):
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == y2:
beta = (3*x1*x2 + a) * pow(2*y1, -1, p)
else:
beta = (y2 - y1) * pow(x2 - x1, -1, p)
x3 = (beta*beta - x1 - x2) % p
y3 = (beta * (x1 - x3) - y1) % p
return x3, y3
Independent from the curve type, we can do scalar multiplication fast with double and add method.
def apply_double_and_add_method(G, k, p):
target_point = G
k_binary = bin(k)[2:] #0b1111111001
for i in range(1, len(k_binary)):
current_bit = k_binary[i: i+1]
# doubling - always
target_point = add_points(target_point, target_point, p)
if current_bit == "1":
target_point = add_points(target_point, G, p)
return target_point
Curve Configuration
In this experiment, we will adopt secp256k1 curve which is adopted by the bitcoin protocol. This specific curve has the equation y2 = x3 + 7. Fixed base point G, modulo p, order n and cofactor h values are mentioned in the following snippet. Notice that these values are totally public.
a = 0; b = 7
G = (55066263022277343669578718895168534326250603453777594175500187360389116729240,
32670510020758816978083085130507043184471273380659243275938904335757337482424)
p = pow(2, 256) - pow(2, 32) - pow(2, 9) - pow(2, 8) - pow(2, 7) - pow(2, 6) - pow(2, 4) - pow(2, 0)
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Calculating Public Key
Alice will pick a large integer as her private key. 256-bit elliptic curve keys are thought to be secure. Then, she will calculate her public key. Notice that she will find the multiplicative inverse of her private key first, then find the corresponding point to calculate public key. This is an anti-pattern in elliptic curve cryptography. Because we are always finding private key times base point to find public key except EC-KCDSA!
import random # Alice's private key d = random.getrandbits(256) # public key of Alice Qa = apply_double_and_add_method(G = G, k = pow(d, -1, n), p = p)
If private key and base point pair are known, then it is easy to find the public key with double and add method. On the other hand, restoring private key from known base point and public key is computationally hard. This is called elliptic curve discrete logarithm problem.
Calculating Random Point
Alice will send a message and signature to Bob. EC-KCDSA requires Alice to pick a large integer as random key. Then, she will find the corresponding random point. Notice that this random key generation must be done for each signing.
# Alice picks a random key (secret) k = random.getrandbits(256) # Alice calculates random point (public) K = apply_double_and_add_method(G = G, k = k, p = p)
Hashing a point
Hash functions are way functions and we are going to find the hash value of a point on our curve. To do this, we will just consider its x coordinate. Any hash function can be used for this purpose. In this experiment, I will use sha-256 in this experiment. This function will be used by sender and recipient and its logic will be public.
from typing import Tuple
import hashlib
def find_hash(P: Tuple[int, int]) -> int:
x, y = P
# to bytes
m = str.encode(str(x))
hash_value = hashlib.sha256(m).digest()
# Convert the hash value to an integer
return int.from_bytes(hash_value, 'big')
Signature
Alice will send (r, s) pair with the plain message as a signature. Let’s have a look how we will calculate these values. The first argument r will be calculated by hashing the random point K. To find the 2nd argument s, we will firstly digest the plain message, secondly sum the hash of random point and hash of plain message, and finally calculate Alice’s private key times subtraction of random key k and sum of hash values.
message = "Hello, World!" # 1st part of the signature r = find_hash(K) # 2nd part of the signature e = find_hash(message) w = ( r + e ) % n s = ( d * (k - w) ) % n
Alice will send plain message and (r, s) pair to Bob.
Verification
When Bob receives plain message and (r, s) pair, he will find the hash value of the message first. Then, he will be able to calculate w because it is the sum of r and e pair. r is coming from the signature already and e is the hash of the message.
e = find_hash(message) w = ( r + e ) % n
Then, Bob will perform the following operation
s x Q + w x G
Here, Q is the public key of Alice, G is the base point on our curve, s is the 2nd part of the signature. We will use double and add method to find s x Q and w x G. Then, we will use add points function we implemented in the curve form section in this post.
x = add_points(
P = apply_double_and_add_method(G = Qa, k = s, p = p),
Q = apply_double_and_add_method(G = G, k = w, p = p),
p = p
)
Finally, he will find the hash value of this calculation and compare it to the r in the signature. If this condition satisfied, then signature is valid.
assert find_hash(x) == r
The math behind EC-KCDSA
Signature is consisting of (r, s) pair. Let’s remember how s was calculated.
s = ( d x (k – w) ) mod n
Let’s leave k alone in this equation
s x d-1 = k – w
k = (s x d-1) + w
Now, let’s remember how Bob calculated x to verify signature
x = s x Q + w x G
Here, public key Q was calculated by multiplicative inverse of Alice’s private key times base point
x = s x d-1 x G + w x G
The both statements have base point G multiplier. We can represent it with common base point G multiplier.
x = (s x d-1 + w) x G
The term in the parenthesis is exactly equal to the k we found above in this section.
x = k x G
Lower k was the random key and its corresponding point was represented as upper K.
x = K
The r part of the signature was the hash value of the K. Similarly, Bob calculated x and it is exactly equal to the K, too. When he verifies signature, he finds the hash value of x. This is actually equal to the hash value of K. So, hash value of x must be equal to r in the signature always.
Conclusion
Congratulations on completing this exciting journey into the world of the Korean Certificate-based Digital Signature Algorithm (KCDSA) implemented in Python from scratch! We’ve explored the fundamentals of elliptic curve cryptography, witnessed the power of KCDSA in ensuring data integrity and authenticity, and even had a little fun along the way. By building our own implementation, you’ve gained a deeper understanding of the inner workings of this cryptographic superhero. Now armed with this knowledge, you can confidently wield KCDSA to protect your digital assets and contribute to the world of secure communications. Remember, cryptography is an ever-evolving field, and there’s always more to learn and explore. So keep coding, stay curious, and may your digital signatures always be secure! Happy coding!
I pushed the source code of this study into GitHub. You can support this work if you star⭐ its repo.
Like this blog? Support me on Patreon
