Topic: how is "s" kept as an integer in ECDSA? (Read 147 times)
how is ECDSA?
The integer operations are modulo n. So yes, the inverse of an integer a mod n is a number b = a^-1 mod n such that a * b = 1 mod n.
There are efficient algorithms for finding such an inverse which is why ECDSA (and other cryptosystems) can use inverses modulo n.
There are efficient algorithms for finding such an inverse which is why ECDSA (and other cryptosystems) can use inverses modulo n.
Oh wait. I just realised that all integers belong to a finite integer field of [1, n-1].
So you have to do finite field math or whatever its called.
so thats how k^-1 is calculated. someone please correct me if im wrong... or tell me if im right lol. im still not sure if thats correct
So you have to do finite field math or whatever its called.
Quote
The tricky one is division; that is not division on the field of integers followed by a modulus operation. Instead, it involves finding the multiplicative inverse of a number; that is, given b, we find the field member b^−1 such that b×b^−1=1. Then, a/b=a×b^−1
so thats how k^-1 is calculated. someone please correct me if im wrong... or tell me if im right lol. im still not sure if thats correct
from wikipedia
But how can s be an integer since k^-1 will yield a decimal amount (e.g. 123.12347)?
Quote
G is a basepoint on a curve.
Alice picks a key; d_{A} and a corresponding pub key; Q_{A} = d_{A} * G
Calculate e = HASH(m), where HASH is a cryptographic hash function, such as SHA-2.
Let z be the L_{n} leftmost bits of e, where L_{n} is the bit length of the group order n.
Select a cryptographically secure random integer k from [1,n-1].
Calculate the curve point (x_1, y_1) = k * G.
Calculate r = x_1 mod n. If r = 0, go back to step 3.
Calculate s=k^-1(z+rd_{A}) mod n. If s=0, go back to step 3.
The signature is the pair (r,s).
Alice picks a key; d_{A} and a corresponding pub key; Q_{A} = d_{A} * G
Calculate e = HASH(m), where HASH is a cryptographic hash function, such as SHA-2.
Let z be the L_{n} leftmost bits of e, where L_{n} is the bit length of the group order n.
Select a cryptographically secure random integer k from [1,n-1].
Calculate the curve point (x_1, y_1) = k * G.
Calculate r = x_1 mod n. If r = 0, go back to step 3.
Calculate s=k^-1(z+rd_{A}) mod n. If s=0, go back to step 3.
The signature is the pair (r,s).
But how can s be an integer since k^-1 will yield a decimal amount (e.g. 123.12347)?
Jump to: