Differing S values from test vector

[luv2drnkbr]

I'm verifying a signing function I've written against DeathAndTaxes test vectors here.  I'm getting the correct K values, but somehow different S values, and yet all the signatures my function spits out are valid.  (I've tested them against other verification functions that I didn't write.)

The function is:  sign_hash( hash, privkey ), and you can view the code (minus some input format checks and other misc error checking) here.

Here's my doctests:

(As you may have guessed, I like my hexstrs)

Code:

    >>> sign_hash(sha256(bytearray("Satoshi Nakamoto",'utf-8')),"0000000000000000000000000000000000000000000000000000000000000001")
    '3046022100934b1ea10a4b3c1757e2b0c017d0b6143ce3c9a7e6a4a49860d7a6ab210ee3d8022100dbbd3162d46e9f9bef7feb87c16dc13b4f6568a87f4e83f728e2443ba586675c'

    >>> sign_hash(sha256(bytearray("All those moments will be lost in time, like tears in rain. Time to die...",'utf-8')),"0000000000000000000000000000000000000000000000000000000000000001")
    '30460221008600dbd41e348fe5c9465ab92d23e3db8b98b873beecd930736488696438cb6b022100ab8019bbd8b6924cc4099fe625340ffb1eaac34bf4477daa39d0835429094520'

    >>> sign_hash(sha256(bytearray("Satoshi Nakamoto",'utf-8')),"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140")
    '3046022100fd567d121db66e382991534ada77a6bd3106f0a1098c231e47993447cd6af2d002210094c632f14e4379fc1ea610a3df5a375152549736425ee17cebe10abbc2a2826c'

    >>> sign_hash(sha256(bytearray("Alan Turing",'utf-8')),"f8b8af8ce3c7cca5e300d33939540c10d45ce001b8f252bfbc57ba0342904181")
    '304502207063ae83e7f62bbb171798131b4a0564b956930092b33b07b395615d9ec7e15c022100a72033e1ff5ca1ea8d0c99001cb45f0272d3be7525d3049c0d9e98dc7582b857'

    >>> sign_hash(sha256(bytearray("There is a computer disease that anybody who works with computers knows about. It's a very serious disease and it interferes completely with the work. The trouble with computers is that you 'play' with them!",'utf-8')),"e91671c46231f833a6406ccbea0e3e392c76c167bac1cb013f6f1013980455c2")
    '3045022100b552edd27580141f3b2a5463048cb7cd3e047b97c9f98076c32dbdf85a68718b0220279fa72dd19bfae05577e06c7c0c1900c371fcd5893f7e1d56a37d30174671f6'

    >>> sign_hash(sha256(bytearray("Everything should be made as simple as possible, but not simpler.",'utf-8')),"0000000000000000000000000000000000000000000000000000000000000001")
    '3045022033a69cd2065432a30f3d1ce4eb0d59b8ab58c74f27c41a7fdb5696ad4e6108c9022100907f867d799087a2c09be72dbe9c2250a9335f31d94ab034a1f1f4927c021edf'

    >>> sign_hash(sha256(bytearray("Equations are more important to me, because politics is for the present, but an equation is something for eternity.",'utf-8')),"fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140")
    '3045022054c4a33c6423d689378f160a7ff8b61330444abb58fb470f96ea16d99d4a2fed022100f8f7dcfbbef10594d6bceee495b1f5543f31278ca75f1a1ea01e936d8e25fc9c'

    >>> sign_hash(sha256(bytearray("Not only is the Universe stranger than we think, it is stranger than we can think.",'utf-8')),"fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140")
    '3045022100ff466a9f1b7b273e2f4c3ffe032eb2e814121ed18ef84665d0f515360dab3dd002206fc95f5132e5ecfdc8e5e6e616cc77151455d46ed48f5589b7db7771a332b283'

As you can see from the signature, the R values correspond to the correct deterministic K values, but my S values do not match the test vectors from the link above.  I'm hoping somebody could give a potential reason for that.  (Or rather, I'm hoping somebody will tell me DeathAndTaxes' S value is wrong, since I've actually validated these signatures I've made.)

[johoe]

I'm verifying a signing function I've written against DeathAndTaxes test vectors here.  I'm getting the correct K values, but somehow different S values, and yet all the signatures my function spits out are valid.  (I've tested them against other verification functions that I didn't write.)

As you can see from the signature, the R values correspond to the correct deterministic K values, but my S values do not match the test vectors from the link above.  I'm hoping somebody could give a potential reason for that.  (Or rather, I'm hoping somebody will tell me DeathAndTaxes' S value is wrong, since I've actually validated these signatures I've made.)

If the R values are identical and the S value differ then the S value is probably negated (corresponds to negated K value).

A standard signature should have S < N/2, see here.
So as a last step of your signature algorithm you should negate it (modulo N, i.e. S := N - S) if it is larger than N/2.

[luv2drnkbr]

I'm verifying a signing function I've written against DeathAndTaxes test vectors here.  I'm getting the correct K values, but somehow different S values, and yet all the signatures my function spits out are valid.  (I've tested them against other verification functions that I didn't write.)

As you can see from the signature, the R values correspond to the correct deterministic K values, but my S values do not match the test vectors from the link above.  I'm hoping somebody could give a potential reason for that.  (Or rather, I'm hoping somebody will tell me DeathAndTaxes' S value is wrong, since I've actually validated these signatures I've made.)

If the R values are identical and the S value differ then the S value is probably negated (corresponds to negated K value).

A standard signature should have S < N/2, see here.
So as a last step of your signature algorithm you should negate it (modulo N, i.e. S := N - S) if it is larger than N/2.

Holy shit that's the transaction malleability issue.  Thank you for that explanation.  I'm a relatively new programming, learning Python to learn Bitcoin, and vice versa, so I don't know the ins and outs of EC math.  The properties of EC math are truly fascinating, and I keep learning more interesting stuff about it all the time.  I will make sure my function always spits out the lower S value.