T H I C C_C U R V E S pt. 2

In part 1 we saw a basic explaination of the math behind elliptical curves (and some python code). In this part I’ll explain the ECDSA algorithm (Elliptical Curve Digital Signature Algorithm).

Key generation

The keys are based on Diffie-Hellman. It’s actually really simple:

def generate_keypair(self): # Diffie-Hellman
        self.private = randint(1, self.baseorder)
        self.public = self.multiply(self.private, self.base)

A.session_key = A.private*(B.public*base)
B.session_key = B.private*(A.public*base)

This works, because of the abelian property associativeness (maybe an english word?).

a = A.private
b = B.private
A.session_key = a*(b*base) = (a*b)*base = b*(a*base) = B.session_key

ECDSA algorithm

Wikipedia actually explains the algorithm very well, and why it works. Take a look.

Python code for the algorithm look like this:

def sign(self, H):
        z = int("0x"+H, 16)
        k = randint(1,self.baseorder-1)
        P = self.multiply(k,self.base)
        
        if P.x == 0:
            return self.sign(H)
        
        r = P.x
        s = (z+r*self.private)*I_invert(k, self.baseorder)%self.baseorder

        return int(r), int(s)

    def verify_signature(self, signature, pub, H):
        r,s = signature
        if not (1 <= r <= self.baseorder-1 and 1 <= s <= self.baseorder-1):
            raise Exception("Invalid signature")

        z = int("0x"+H, 16)
        u1 = z*I_invert(s,self.baseorder)%self.baseorder
        u2 = r*I_invert(s,self.baseorder)%self.baseorder

        P = self.add(self.multiply(u1,self.base),self.multiply(u2, pub))
        
        if r == P.x:
            return True
        else:
            raise Exception("Invalid signature")

Since I programmed it, I can decide the hashing algorithm, and therefore z. I chose sha1 with regards to the length of the hash.

The complete code can be found at github.

Rust implementation

So I’ve spent the last day to learn basic Rust and implementing ECDSA. Therefore my implementation may be relativaly bad from a speed perspective. But I think it turned out okay for my first time writing Rust.

Rust by default do not support the sizes of our parameters, therefore I needed to implement a big-num library (or crate as Rust calls it).

Rust does not support classes either, but like Go, it supports structs. I think this is fine, but it did change my implementation a bit. It now deviates a bit from my Python implementation.

Here’s the sign and verify_sign functions.

fn sign(h: &str, private: Integer) -> (Integer, Integer) {
    let base = Point{               
        x: hex2int("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012"),
        y: hex2int("07192b95ffc8da78631011ed6b24cdd573f977a11e794811"),
    };
    let baseorder = hex2int("ffffffffffffffffffffffff99def836146bc9b1b4d22831");

    let z = hex2int(h);
    let k = gen_random();
    let P = point_multiply(&k, &base);
    
    if P.x == Integer::from(0) {
        sign(h, private.clone());
    }

    let r = P.x;
    let s = (z+r.clone()*private)*Integer::from(k.invert_ref(&baseorder).unwrap()).rem_floor(&baseorder);

    (r,s)
}

fn verify_signature(signature: (Integer, Integer), public: Point, h: &str) -> bool {
    let base = Point{               
        x: hex2int("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012"),
        y: hex2int("07192b95ffc8da78631011ed6b24cdd573f977a11e794811"),
    };
    let baseorder = hex2int("ffffffffffffffffffffffff99def836146bc9b1b4d22831");

    let r = signature.0;
    let s = signature.1;
    
    if 1 > r && r > baseorder.clone()-Integer::from(1) && 1 > s && s > baseorder.clone()-Integer::from(1) {
        panic!("Invalid signature");
    }
    
    let z = hex2int(h);
    let u1 = z*Integer::from(s.invert_ref(&baseorder).unwrap()).rem_floor(&baseorder);
    let u2 = r.clone()*Integer::from(s.invert_ref(&baseorder).unwrap()).rem_floor(&baseorder);

    let P = point_add(&point_multiply(&u1, &base), &point_multiply(&u2, &public));
    
    if r == P.x {
      return true
    }

    return false
}

The complete code can be found at github.

Speed comparison

For each iteration I generate the keys, sign a message and verify the message. I do this 1000 times on each program.

# ec.py

for i in range(1000):
        ec = EC(a,b,G,n,p)

        ec.generate_keypair()
     
        H = "719609852b46b8ea9a5fcd39eb7bc9088fa36399"    
        r,s = ec.sign(H)
        ec.verify_signature((r,s), ec.public, H)

Here are the results.

$ time python ec.py

real	0m8,314s
user	0m7,358s
sys	0m0,033s

$ time ecRust/target/release/ec_rust

real	0m5,099s
user	0m5,097s
sys	0m0,000s

So Rust was a bit faster, but not by much. This is probably due to my bad Rust skills and only knowing it for about 24 hours :) I suspect that my implementation can be sped up by a factor or two.

Next time

My CAN-buses haven’t arrived yet, but when they do I will take a dive into CAN and some cool stuff!