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!

598 Words

2019-08-27 20:16 +0200