--- Day changed Sun Feb 25 2018
00:23 -!- jtimon_ [~quassel@41.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 240 seconds]     
01:29 -!- Apocalyptic [~Apocalypt@unaffiliated/apocalyptic] has quit [Ping timeout: 256 seconds]     
01:30 -!- Apocalyptic [~Apocalypt@unaffiliated/apocalyptic] has joined #secp256k1     
01:34 -!- Netsplit *.net <-> *.split quits: roconnor, indutny, eragmus, Madars
01:36 -!- roconnor [~roconnor@host-192.252-166-159.dyn.295.ca] has joined #secp256k1     
01:36 -!- indutny [~indutny@188.226.143.86] has joined #secp256k1     
01:36 -!- Madars [~null@unaffiliated/madars] has joined #secp256k1     
01:36 -!- eragmus [sid136308@gateway/web/irccloud.com/x-ehywxaykfciongys] has joined #secp256k1     
01:36 -!- instagibbs [~instagibb@pool-100-15-116-35.washdc.fios.verizon.net] has quit [Ping timeout: 240 seconds]     
01:37 -!- Apocalyptic [~Apocalypt@unaffiliated/apocalyptic] has quit [Ping timeout: 240 seconds]     
01:40 -!- instagibbs [~instagibb@pool-100-15-116-35.washdc.fios.verizon.net] has joined #secp256k1     
01:42 -!- Apocalyptic [~Apocalypt@unaffiliated/apocalyptic] has joined #secp256k1     
01:48 -!- roconnor [~roconnor@host-192.252-166-159.dyn.295.ca] has quit [Ping timeout: 256 seconds]     
01:48 -!- roconnor_ [~roconnor@host-192.252-166-159.dyn.295.ca] has joined #secp256k1     
03:32 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has joined #secp256k1     
04:16 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 256 seconds]     
09:40 -!- jtimon [~quassel@41.31.134.37.dynamic.jazztel.es] has joined #secp256k1     
12:52 -!- roconnor_ [~roconnor@host-192.252-166-159.dyn.295.ca] has quit [Ping timeout: 260 seconds]     
16:00 -!- weez17 [~isaac@unaffiliated/weez17] has quit [Remote host closed the connection]     
16:00 -!- weez17 [~isaac@unaffiliated/weez17] has joined #secp256k1     
16:16 < kallewoof> I'm reading the schnorr paper (the 1990 one) and am wondering about the two primes p and q. The paper says p >= 2^512, and that pubkeys are <number> mod p. Doesn't that mean pubkeys are 64 bytes, not 32?
16:17 < kallewoof> Link: https://pdfs.semanticscholar.org/8d69/c06d48b618a090dd19185aea7a13def894a5.pdf (page 240; though pages start at page 239, so "second page")
16:17 < kallewoof> s/pubkeys are 64 bytes/pubkeys are *at minimum* 64 bytes/
16:19 < gmaxwell> kallewoof: that is talking about using integers mod p as the discrete-log-hard group rather than ECC.  Not of interest to us because secure groups like that are very very large. (512 bits is completely insecure now)
16:21 < gmaxwell> which partitcular discrete log hard group a cryptosystem is initilized over doesn't matter for the operation of the cryptosystem itself... other than the fact that the cpu and space efficiency and security of different groups is different.
16:24 < sipa> also, using integers of size 512 bits would give around 50 bits of security
16:25 < kallewoof> gmaxwell: I guess I'm confused over the requirement that p >= 2^512, where in implementations (I think?) it isn't
16:26 < sipa> kallewoof: i think you misunderstand
16:26 < kallewoof> sipa: So do I...
16:26 < gmaxwell> kallewoof: What you are reading about is not using ECC.
16:26 < kallewoof> Wait. So the schnorr being used in (future) secp256k1 will be schnorr on ECC?
16:26 < sipa> IF yiu're using an integer multiplication group, you should really use integers larger than 512 bits (and these days the advice is more around 2048 or larger)
16:26 < kallewoof> I totally did not realize that.
16:26 < sipa> kallewoof: yes, EC dchnorr
16:27 < gmaxwell> All these sorts of cryptosystems are generalized algebraic techniques that can work on arbritary abelian groups, so long as the discrete log problem is hard in the group.
16:27 < kallewoof> sipa: I suppose there is no such thing as a decent paper describing EC schnorr?
16:27 < sipa> but it would be totally doable to use a multiplication mod a 3000 or 4000 bits prime
16:27 < sipa> it woukd just be much slower and larger
16:28 < sipa> kallewoof: thank ed25519 :)
16:28 < gmaxwell> For the most part the choice of the group is irrelevant to the understanding of the algorithim, it only changes sizes speeds and securities.
16:28 < sipa> (which is effectively schnorr over a nonstandard EC group)
16:29 < gmaxwell> Also old crypto papers are totally useless in reasoning about group security in any case.. as you see, that paper talks about groups with |P| around 512 bits, which I could easily crack at home using state of the art techniques and computers.
16:29 < kallewoof> gmaxwell: Right. I assumed that was the case. I was just surprised that p was so big. But with EC, I guess the situation changes. Or I'm misunderstanding p used in practice
16:30 < gmaxwell> the group we'd use for bitcoin would be secp256k1, same as is used for ecdsa in bitcoin.
16:30 < kallewoof> sipa: I'll read up on ed25519 (but I think it's just the parameters for a curve, IIRC)
16:30 < kallewoof> gmaxwell: Ah, all right.
16:30 < sipa> kallewoof: no, ed25519 is really a fully specified signature scheme
16:30 < sipa> kallewoof: for EC the rule of thumb is that N bit integers (for the coordinates of the field) give you N/2 bits of security
16:30 < kallewoof> sipa: Oh, okay!
16:30 < gmaxwell> (assuming the ECC group is well selected)
16:31 < sipa> kallewoof: for integer modulo a prime groups, the rule is more complicated but 3000 bits corresponds to around 128 bit of security
16:31 < sipa> 1000 bits corresponds to 80 bits of security
16:31 < sipa> 15000 bits corresponds to 256 bits of security
16:31 < kallewoof> Wow.. how many bits are in secp256k1 then?
16:31 < sipa> 256     
16:31 < sipa> so 128 bit security
16:32 < kallewoof> *nod*
16:32 < kallewoof> *pause* didn't you just say 1000 bits = 80 bit security?
16:32 < sipa> for integer multiplication mod a prime groups
16:32 < sipa> not for EC groups
16:32 < kallewoof> Got it. So EC groups it's N/2, but for integer mul mod a it's much less
16:33 < sipa> yup     
16:33 < sipa> 512 bits integers give you 50 bits of security or so
16:33 < sipa> which was apparently considered ok in 1990
16:34 < gmaxwell> sipa: your rule of thumb also only applies to well selected P, with more criteria, e.g. than the schnorr paper provides.
16:34 < gmaxwell> e.g. P-1 is prime*2 and some other criteria.
16:34 < sipa> yes, this is all a simplification
16:34 < sipa> Schnorr needs a group in which the discrete logarithm is hard
16:35 < sipa> how you construct that group is up to you
16:35 < sipa> i guess the rule of thumbs i gave are for optimal situations
16:35 < sipa> you also can't just pick a random elliptic curve with a certain size
16:36 < gmaxwell> and other than the concrete size, speed, security the choice of DL-hard group is irrelevant, and basically independant from how schnorr works.
16:36 < kallewoof> Is the group chosen by secp256k1 defined by secp256k1 then? (p and q I mean)
16:36 < sipa> yes     
16:36 < kallewoof> OK     
16:36 < sipa> p is 2^256 - 2^32 - 977
16:37 < gmaxwell> hhh careful, p and q with secp256k1 have very little to do with the p and q in integer schnorr.
16:37 < sipa> well, p and q don't really have the same meaning
16:37 < sipa> right
16:37 < kallewoof> gmaxwell: Oh, okay.
16:37 < gmaxwell> kallewoof: the right mental framework to think about this stuff is that the cryptosystem has two modules  [discrete log hard group] and [schnorr signature].
16:38 < gmaxwell> ECC and integers-mod-p are totally different discrete log hard groups that have very little relationship with each other.
16:38 < gmaxwell> (though there are prime numbers involved in both and such.. thats kind of like saying "both use math")
16:38 < kallewoof> I didn't realize they were unrelated to that extent.
16:39 < sipa> what you get from the group is: a neutral element, a generator, and a function that combines two group elements
16:39 < gmaxwell> Yes, a high performance implementation may sometimes bend abstranction boundaries a bit to extract a bit more performance, but conceptually they are _very_ isolated.
16:39 < kallewoof> So reading the original schnorr paper is pretty much not gonna get me anywhere on EC schnorr, and there's no good description of how EC schnorr works.
16:39 < sipa> in case of integers modulo a prime your neutral element is 1, your generator is 2, and the function to combine them is multiplication modulo p
16:40 < sipa> in the case of an EC group the neutral element is the EC point at infinity, the generator is some random chosen point, and the function to combine is EC addition
16:41 < gmaxwell> I think 95% of the crypto tutorials on the internet stink because they waste the readers time telling you about the mechnics of computing the group operations, which is conceptually the most opaque and least interesting... and then exacerbate the problem by not drawing clear conceptual boundaries.  Almost all the fancy things we've done with ECC (CT, bulletproofs, schnorr signatures) can pretty much be
16:41 < gmaxwell>  done with _no_ understanding of the ECC part at all-- just treating it as a black box.
16:41 < sipa> kallewoof: there are also other differences between modern EC schnorr and Schnorr as it was formulated back then
16:42 < sipa> the (e,s) vs (R,s) formulation
16:42 < sipa> both are possible either way
16:42 < gmaxwell> schnorr is usually described in e,s formulation; which is more space efficient for integer-group schnorr because hashes are smaller than group elements. ... but it cannot be batch verified... and for ECC hashes and group elements are the same size.
16:42 < kallewoof> gmaxwell: I've been going with the black box model mindset for awhile but realize that sometimes I don't know why I don't understand something; because I treat the core as a black box or because I don't understand the concept itself
16:43 < gmaxwell> with a black box it's important to have a correctly chosen boundary for it. :)
16:43 < kallewoof> sipa: I can imagine there's been some progress since then, yeah. 1990 is nearly 30 years ago. Yikes.
16:44 < sipa> kallewoof: so if you want to know the black box, read up on what a group means in the mathematical sense
16:44 < kallewoof> gmaxwell: Heh, yeah. By not understanding it, I think it's hard to draw the boundary. That's why I decided to try to understand the core concepts as well. But I'm hitting some big road bumps. I think the "do not roll your own crypto" mindset may be a part of it. There's no REASON to write a clear easy to understand in depth document, because that only encourages people to shoot thmselves in the foot.
16:45 < sipa> kallewoof: https://en.m.wikipedia.org/wiki/Group_(mathematics)
16:45 < kallewoof> sipa: I would love to. I'm gonna read the ed25519 pdf and I looked up secp256k1 (that's a weird looking p btw). I don't even know what to google to read about groups but I'll give it a shot.
16:45 < gmaxwell> well thats why I'm telling where I think a good boundary is instead of expecting you to figure it out on your own. :P
16:45 < kallewoof> sipa: Thanks for link (that was more straightforward than I expected)
16:46 < gmaxwell> I can tell you that I was basically useless with this stuff until really getting this boundary and then I immediately went on to design a bunch of useful cryptosystems which we can prove secure. :)
16:46 < sipa> kallewoof: schnorr *works* on any group (as in signing and verifying will work), but it needs a group with specific properties to be secure
16:47 < kallewoof> gmaxwell: Thanks, that's really encouraging. :)
16:48 < sipa> maybe it's useful for understanding to see what schnorr would boil down to if applied to very common groups, like addition over real numbers
16:48 < sipa> it would be utterly insecure, but maybe it makes things more graspable
16:48 < kallewoof> sipa: I wanted to try it on really tiny primes just to get a feel for how it works, but not even sure it works on tiny primes.
16:48 < sipa> kallewoof: i would not do that
16:49 < kallewoof> Haha
16:49 < sipa> they'll teach you mechanism that don't matter
16:49 < sipa> and not the big pictire
16:49 < sipa> *mechanics
16:49 < kallewoof> Right..
16:49 < gmaxwell> The operation of the group itself is irrelevant to understanding the higher level... or well 99.9% irrelevant. :)
16:50 < sipa> kallewoof: all you have to know is this: there exists this weird kind of thing, and you can add these things together to get other things. and if i give you to things a and b, you can't easily figure out how many times i added a to itself to get b
16:50 < sipa> *two things a and b
16:51 < kallewoof> sipa: Yeah, I kind of feel like that's a hindrance sometimes, but I think gmaxwell is right that I dont have the boundaries firmly defined in my mind.
16:52 < sipa> but to understand *Schnorr* you'll get lost when trying to think of these things as numbers, or points, ...
16:52 < kallewoof> sipa: that = the limited understanding. only recently did I finally realize you can combine privkeys and pubkeys separately to get a new key pair. that should be obvious to someone who actually understands the things you are talking about. i assume.
16:52 < sipa> because really all that matters is that you can add them, and can't figure out how many times one was combinsd to get another
16:53 < kallewoof> sipa: that makes sense.
16:53 < sipa> kallewoof: the fact that you can do these things on *group elements* will be obvious to anyone who knows group theory
16:54 < sipa> the fact that it's possible to use those as public keys is a wholly different matter
16:54 < sipa> and not at all obvious (exemplified by the fact that doing it naively is insecure)
16:54 < kallewoof> that's a good point, yeah.
16:55 < kallewoof> though there are cases where it's secure, i think. for example if an external oracle presents two pubkeys 'rain' and 'sunshine' for feb 27 2018, i can make a key pair and add the pubkey for 'rain' to my pubkey and later (when oracle publishes privkey for right answer) i can add the privkey to mine. that doesn't suffer from the a=x-b thing for multisig
16:56 < kallewoof> (^ slightly off topic, but been meaning to ask)
16:56 < sipa> yes, that's approximately the pay to contract scheme
16:56 < sipa> and also what allows outsourcing vanitygen :)
16:57 < kallewoof> sipa: oh, didn't think about that
16:57 < sipa> if you want to understand elliptic curves there is a lot more to say about them, but none of the properties of curves really matter to Schnorr, except for the facy that they result in a group in which the DLP is hard ("you can't figure out how many times something was added to itself to obtain something else")
16:58 < sipa> and there is nothing inherent to elliptic curves that will help you see that; the real answer is that many people have tried to solve the DLP for elliptic curves and failed to do it efficiently
16:59 < kallewoof> sipa: So to understand the modern EC schnorr I should basically just read up on EC. I still don't know where to figure out how schnorr works in EC, though.
16:59 < sipa> no     
17:00 < sipa> schnorr is this:
17:00 < sipa> generate a private key x, the public key is X=x*G
17:01 < sipa> a signature on message m with private key x is (R,s) where R=k*G and s=k+H(R,X,m)*x
17:01 < kallewoof> that looks an awful lot like the MuSig paper..
17:01 < sipa> verifying a signature is testing whether s*G = R+H(R,X,m)*X
17:02 < sipa> MuSig uses exponential notation
17:02 < sipa> so it would write G^s = R*X^H(R,X,m)
17:02 < sipa> to mean the same thing
17:03 < sipa> but in bitcoin context we're more used to the add/multiply notation than multiply/exponentiate
17:03 < kallewoof> sipa: I wish people would not write the same thing in two different ways.
17:03 < sipa> again, because it doesn't matter what the group is, it's hard to give a notation
17:04 < sipa> in some cases the group operation is denoted by addition, and repeated apllication is multiplication
17:04 < sipa> something the group operation is denoted by multiplocation, and repeated application is exponentiation
17:04 < kallewoof> sipa: Confusing
17:05 < gmaxwell> this is just a dumb artifact of math history.
17:05 < kallewoof> I've gotten used to it but I thought there was a third operator there for awhile (exponentiation)
17:05 < Apocalyptic> I've often found that the additive notation is used for abelian groups
17:05 < sipa> yes, but it's important to realize that it doesn't matter what this operation is
17:05 < sipa> it could be called blah and repeatedblah
17:06 < sipa> G repeatedblah s = R blah (X repeatedblah H(R,X,m))
17:06 < kallewoof> lol     
17:07  * sipa dinner
17:10 < sipa> or maybe better: G blah G blah ... (repeat s times) = R blah (X blah X blah ... (repeat H(R,X,m) times))
17:11 < gmaxwell> Apocalyptic: in random math lit it's pretty random.
17:11 < gmaxwell> it basically depends on the particular subfield.
17:12 < gmaxwell> integers mod P is one of the best known abelian groups, and its kinda natural to write it using exp notation since that is actually the calculations you're performing.
17:13 < gmaxwell> Personally I think thats unfortunate because it gets in the way of understanding the abstraction.
17:13 < Apocalyptic> integers mod P is a group only for addition though (if you substract zero it's a multiplicative group yeah)
17:14 < sipa> gmaxwell: i wonder if that's because early on that abstraction wasn't realized
17:16 < gmaxwell> Apocalyptic: integers mod p is a group for multiplication with appropriate choice of generator.
17:16 < sipa> gmaxwell: no, it's not
17:16 < Apocalyptic> gmaxwell, no
17:16 < sipa> a group requires every element to have an inverse
17:17 < Apocalyptic> you most certainly meant F_p, which is what you said minus the zero-element
17:17 < gmaxwell> Apocalyptic: yes
17:17 < Apocalyptic> "integers mod p" implies you have a zero class, sorry to be pedantic
17:19 < sipa> it's a monoid, though :)
17:20 < Apocalyptic> it's all kind of nice things :)
19:12 -!- droark [~droark@c-24-22-123-27.hsd1.or.comcast.net] has quit [Ping timeout: 256 seconds]     
23:09 -!- andytoshi [~apoelstra@wpsoftware.net] has quit [Ping timeout: 256 seconds]