#tlsnotary-chat

picked this up from #wizards ; looks worth a detailed read, although I haven't yet: https://freedom-to-tinker.com/blog/jbonneau/pro...

Pedersen commitment looks so hot now

.jpg

proslogion: i just realised some basic thing i didn't understand about elliptic curves

(x,y) is a point in the group, the group is order N, but x and y are in the field order p, right?

anyway my short version is, why do we calculate things like x mod N instead of x mod p in the ECDSA algo.

it might be to do with bitlength; if n << p that could be relevant.

waxwing: IIRC n is by all means very close to p

e.g., look at the NIST curves http://csrc.nist.gov/groups/ST/toolkit/document...

proslogion: yes, i know that n is very close to p for secp256k1. i was wondering why the algorithm works like that, in the general case.

waxwing: well the group order vaguely indicates the number of points on the curve right?

group order is the number of points on the curve ... if you mean the elliptic curve group?

or, at least if h=1, like in secp256k1 case

sopresumably it could be that if you select n<k<p, it will just go one full circle, because you exhausted all the points

proslogion: what i'm trying to get at is that (x,y) = P, x could be > n (but less than p)

yes, that's my case as well

i suspect it might be the same reason

so i'm wondering if in ecdsa, do we need to operate with x mod N = r, or could we just use x (i.e. x mod p)

all the numbers are modulo-ed with N, i guess it's to keep all scalar numbers in the algo at the same bitlength

but i may have missed something more fundamental

hmmm, ECDSA is really a pretty funning signing algorithm, the EC private key is not even the one that is signing

*funny

bastardised due to patent right proslogion

so it's automatically forward-secure, good :)

jk

so there is no such thing as a pubkey for ECDSA in the traditional sense, because one d_A corresponds to multiple r

waxwing: https://en.wikipedia.org/wiki/Digital_Signature... look at this for comparison, i strongly suspect it has more to do with security rather than bitlength

proslogion: how do you mean?

waxwing: may i understand first what led you to consider this problem, pure interest or it has to do with implementation?

proslogion: a bit of both

a long story; i was trying to understand the format/serialization that pybitcointools was using for message verification

the format has a weird first byte that acts as a flag for the parity of the R value.

if you read all of this it'll tell the whole story:

today i had to write this ugly thing to account for it: https://github.com/AdamISZ/joinmarket/blob/secp...

"However, this means we need the full R coordinates. There can be up to 4 different points with a given "X coordinate modulo n". (2 because each X coordinate has two possible Y coordinates, and 2 because r+n may still be a valid X coordinate)"

but in short, i just started wondering why "and 2 because r+n may still be a valid X coordinate" in Pieter Wuille's answer, is true.

hmmm

haha

:)

yeah, i mean it *is* true, clearly, but .. i wondered about why.

well, i mean, r+n could like, wrap you around from the infinity point i think?

infinity is only for curve points; it's nG or identity element

my confusion

i think visually it's easier, it's a tangent to the curve when you do point addition.

like, take two points, you get the sum by the third intersection with the curve

but add a point to itself and you're dealing with a tangent

or, subtract, sorry

nah, i just confused it a bit, don't worry

btw if you're interested in such stuff the pubkey recovery algo can be found in sec1-v1.pdf .. you can see the same logic as what sipa described ^ there.

waxwing: note in the wikipedia article, the requirement of n x Q_A=O

yes but that '0' is point at infinity

since when doing verification you will need to multiply rw mod n to Q_A

i guess r cannot be larger than n

proslogion: are you looking at ECDSA on wiki?

yes

ah yes. i *think* you're right, it has to be mod n.

well. 'think' not *think*. guess it must be.

but already we have w = s^-1 mod n so that's in mod n.

Errr...........

waxwing: in RFC6979, the k value appears to be created directly out of hash function? not limited by n-1?

oh, sorry my bad

it's described