--- 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