--- Day changed Thu Oct 22 2015 04:05 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has joined #secp256k1 05:10 < jonasschnelli> can anyone explain what the 2nd byte in the DER encoded ec sig is? Sometimes i get 0x30,0x44, sometimes 0x30,0x45. 05:19 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has quit [Ping timeout: 272 seconds] 05:24 < waxwing> jonasschnelli: length of the rest 05:25 < jonasschnelli> waxwing:... ah. Right. This makes sense. 05:25 < jonasschnelli> thanks 05:47 < sipa> jonasschnelli: you can just go read the X.690-0207 standard, it's a freely available pdf! 05:47 < sipa> :p 05:48 < jonasschnelli> yeah.. after the trivial answer this was also coming to my mind. :) I definitively should! 06:10 < sipa> of course, few people know that 0x30 0x00 [data] 0x00 0x00 is also valid 06:11 < sipa> or 0x30 0x81 [len] [data] 06:11 < sipa> sorry, 0x30 0x80 [data] 0x00 0x00 07:05 < jonasschnelli> would it make sense to expose (SECP256K1_API) secp256k1's sha256 and sha256hmac functions? 07:06 < jonasschnelli> We could save serval bytes on the MCU code while not providing over own sha2 functions... 07:06 < jonasschnelli> s/over/ower 07:07 < sipa> imho, no 07:07 < sipa> but exposing the ability to not compile any sha256 inside, and provide host-provided ones instead 07:08 < sipa> *use 07:08 < jonasschnelli> yes. this could also make sense. I just like to avoid to have a stack where we see multiple implementations of sha256 / aes (other context), etc. 07:08 < sipa> understandably 07:09 < jonasschnelli> especially on a 256k flash / 64 ram device. :) 07:10 < sipa> yeah 07:11 < sipa> i think we can help making the code size smaller 07:11 < sipa> like not having 5 different normalization functions 07:13 < jonasschnelli> sipa: okay. Would be great. dbitbox (working next to me) is ready to help with things like this (https://github.com/bitcoin/secp256k1/pull/337) 07:15 < sipa> jonasschnelli: there is an alternative way of building the ecmult_gen table that is 4 times smaller but is a bit slower 07:17 < jonasschnelli> okay... not very deep into this topic. The only thing that i'm worried is to have a tiny ec signature verification stack in the bootloader (approx 32k)... 07:18 < jonasschnelli> but i think needs to be discussed with dbitbox (reminds me that i have to convince him to use IRC). 07:21 < sipa> oh, verification, right --- Log closed Thu Oct 22 08:00:37 2015 --- Log opened Thu Oct 22 08:01:18 2015 08:01 -!- kanzure_ [~kanzure@unaffiliated/kanzure] has joined #secp256k1 08:01 -!- Irssi: #secp256k1: Total of 27 nicks [1 ops, 0 halfops, 0 voices, 26 normal] 08:06 -!- Netsplit *.net <-> *.split quits: cfields_, kanzure, Luke-Jr 08:10 -!- Irssi: Join to #secp256k1 was synced in 560 secs 08:24 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has joined #secp256k1 08:48 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has quit [Ping timeout: 240 seconds] 09:55 < sipa> gmaxwell: can you ack 334? 10:33 -!- jtimon [~quassel@74.29.134.37.dynamic.jazztel.es] has joined #secp256k1 11:53 < gmaxwell> Sizes of objects in a -m32 -Os no-asm build: http://0bin.net/paste/zs2jIiW97dy4tIy-#1DSIBhXVKRfi-pNs1cALncn2C/caIiLdIbrdTIGeEXP 12:24 -!- luke-jr_ is now known as Luke-Jr 12:26 < TD-Linux> wow the sha256 is pretty dominant 12:27 < TD-Linux> sadly the stm32 series only has sha-1 in hardware :/ 12:31 < gmaxwell> TD-Linux: macro unrolled sha256 implementation, a fully rolled one would be much smaller. 12:39 -!- You're now known as kanzure 16:26 < gmaxwell> sipa: FWIW, where I am on static vectors for tests.c. (1) I have a collection of signature parsing vectors that I think are probably ready, created using coverage directed fuzzing on several other implementations instead of the current one. I need to go through and annotate them with certantly flags. 16:27 < gmaxwell> (2) I have been trying to get all the carry conditionals in the scalar mul and reduce; AFL was too slow for this and so last night I wrote custom instrumentation (and since then reached four more conditions than ever before)... my intention is to have a small table (<20) of field element pairs and their products, computed in sage that will be statically checked. 16:28 < gmaxwell> Plan on doing the same for the field code. 16:28 < gmaxwell> Then the same for signatures, though I need to find an indenpendant 6979 implementation that is actually correct. 16:28 < gmaxwell> Some others ... are not. 16:40 -!- sipa [~pw@2a02:348:86:3011::1] has quit [Ping timeout: 256 seconds] 16:42 -!- sipa [~pw@2a02:348:86:3011::1] has joined #secp256k1 16:56 -!- sipa [~pw@2a02:348:86:3011::1] has quit [Changing host] 16:56 -!- sipa [~pw@unaffiliated/sipa1024] has joined #secp256k1 18:17 < sipa> andytoshi: how fast is the legendre symbol check? 18:17 < sipa> given a field element, how fast is it to determine whether it has a square root 18:18 < sipa> specifically, is it faster than computing the inverse of that field element 18:40 < sipa> if so, i think i have an inversion-free schnorr scheme that is batch-verifiable 18:40 < sipa> (it would require computing a legendre symbol instead of an inverse when not using batch validation) 18:59 < sipa> hmmm... this i don't understand 19:00 < sipa> a^((p+1)/4) computes a square root mod p 19:00 < sipa> so a(((p+1)/4)^2) computes a quartic root mod p 19:01 < sipa> so a^(((p+1)/4)^2 * 2) should compute the square of a quartic root, or a square root 19:01 < sipa> however, ((p+1)/4)^2 * 2 is only half of (p+1)/4 19:08 < gmaxwell> sipa: what you're describing only works when there is a quartic root. 19:08 < sipa> assuming there is one 19:08 < sipa> even then, this doesn't make sense 19:08 < sipa> it would imply the result is always its own square root 19:09 < sipa> oh! 19:10 < sipa> you can't just take powers mod p 19:11 < gmaxwell> oh you were assuming the exponent was reduced mod P? 19:11 < sipa> yeah 19:12 < sipa> gmaxwell: assuming a number has a square root, i believe that taking the quartic root and squaring it will always result in a square root 19:12 < sipa> even if the number doesn't actually have a quartic root 19:12 < gmaxwell> I don't think so. 19:13 < sipa> taking the square root of a non-square x actually computes the square root of (-x), no? 19:13 < gmaxwell> yes. 19:14 < sipa> so if you take non-square x, and square root it + square the result, you get (-x) 19:15 < sipa> supstitute x now with sqrt(y), assuming y has a sqrt 19:15 < sipa> the statement becomes 19:15 < gmaxwell> sage: F 19:15 < gmaxwell> Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663 19:15 < gmaxwell> sage: F(9).sqrt() 19:15 < gmaxwell> 3 19:15 < gmaxwell> sage: (xx^int(((p+1)/4)^2*2)) == xx.sqrt() 19:15 < gmaxwell> False 19:16 < gmaxwell> er thats confusing (xx = F(9)) just misedited my paste. 19:16 < sipa> so if you take non-square sqrt(y), and square root it + square the result, you get -sqrt(y) 19:17 < sipa> so if you take non-quart y, and quartic root it + square the result, you get -sqrt9y) 19:18 < gmaxwell> yes. okay that follows for me. 19:23 < sipa> so i tried with non-quart squares and quarts, and it works 19:24 < sipa> taking a number to the power ((p+1)/4)^2, and then squaring it, always results in a square root that itself is a perfect square 19:24 < sipa> assuming the number has a square root in the first place 19:24 < sipa> if not, it's a perfect square sqrt of its negative 22:26 -!- maaku [~quassel@botbot.xen.prgmr.com] has quit [Remote host closed the connection] 22:28 -!- maaku [~quassel@botbot.xen.prgmr.com] has joined #secp256k1