|
Title: how is "s" kept as an integer in ECDSA? Post by: Anonymous Kid on October 09, 2018, 01:15:06 PM from wikipedia
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). But how can s be an integer since k^-1 will yield a decimal amount (e.g. 123.12347)? Title: Re: how is "s" kept as an integer in ECDSA? Post by: Anonymous Kid on October 09, 2018, 01:31:03 PM 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. 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 Title: Re: how is "s" kept as an integer in ECDSA? Post by: achow101 on October 10, 2018, 12:48:27 AM 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. |