3

I want to create ECDSA signature {r,s} where r is very low (for example 1) and can be encoded in DER-format in one byte.

How to calculate k value? Seems to me that it does not depend of anything. What is the value of k which produces r=1 ?

Note: I do not worry for the safety of my private key while publishing this signature.

6

What is the value of k which produces r=1 ?

It's impossible to know that, if you could derive r for arbitrary values then ECDSA would be fundamentally broken. The best you can do is grind k until you get an r that happens to have a short encoding.

For the sake of the exercise:

k: 55573144136627188774517374788342221967869962622835886499477787746883063622036
r: 771676860789419846973923839003663416737624455477806040640071960112246091

This nonce will be slightly smaller than most when encoded, but of course if you attempt to use it in a signature you have exposed your private key. If you generate this secretly you can only use the k value once and the result might be at best a couple of bytes difference in the encoded transaction.

It hardly seems worth it to be honest.

  • 1
    Finding r=1 is "Impossible" in the same context as most cryptographic assumptions regarding search spaces. It might be possible to find that value if you turned every piece of matter in the near universe into a computer, but the effort to do so is so unreasonably large that it is unpractical for anyone to attempt. It is also possible to create a wallet that reuses a single k as much as possible (and it would have a non trivial speedup signing transactions), but this is far too dangerous to ever use and is therefor never suggested in a serious conversation. – Anonymous Jul 10 '15 at 15:53
  • 1
    Nothing is "serious". Everything is just a "game". – amaclin Jul 10 '15 at 19:41
  • Serious enough that describing it as an answer is not appropriate. It would additionally be a privacy leak, as each signature would uniquely and irrefutably identify the wallet which signed it. I doubt signing speed has ever been a consideration in a wallet either, a single CPU would be enough to re-sign every transaction in the entire Bitcoin network history in a couple of hours (even faster than verifying them). – Anonymous Jul 10 '15 at 19:50
  • 4
    There exists no valid signature with r=1, as there is no point on the secp256k1 curve with x=1. You could look for r=4 though! – Pieter Wuille Jul 11 '15 at 11:02
  • 1
    FYI: blockchain.info/tx/… rlen=0x15 – amaclin Jul 11 '15 at 21:12
3

the shortest ecdsa secp256k1 outputs I've ever seen have

x value = 3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 --> 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63, 0x3f3979bf72ae8202983dc989aec7f2ff2ed91bdd69ce02fc0700ca100e59ddf3
0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 --> 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63, 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

in your ecdsa function, if you use

p = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

then you can derive the above results using

((p-1)/2) = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0

or

((p+1)/2) = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1

if there is anything smaller, i'd be curious to see it.

Edit

due to comments, I have been directed to a testnet tx that suggests maybe you can get R=1. thanks to amaclin.

testnet tx c6c232a36395fa338da458b86ff1327395a9afc28c5d2daa4273e410089fd433

this tx appears to validate, there are also others, c42bea01f1387072772759f32ad860a680e0eea5664732bf2057a66780e7a25d 23202c2534be0567d4b339142f8a9a53545123eb61f61717fdedbef8effc53e0

maybe even more, please add to comments if so.

if I validate the public key signature

026d2204a9535443657a88a0724fbd49a0e78d305f50a82f2cc9dd9bea10a6c5cd

taken from the testnet tx

c6c232a36395fa338da458b86ff1327395a9afc28c5d2daa4273e410089fd433

it gives this point where the x = 1

(0x01, 0xbde70df51939b94c9c24979fa7dd04ebd9b3572da7802290438af2a681895441)

while I can't verify that this point is actually on the sep256k1 curve, it seems to behave like it is, so this is a very interesting one.

if I multiply this point several times by 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72 (lambda value from here)

it produces this cycle of points (3 points with same Y)

(0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee, 0xbde70df51939b94c9c24979fa7dd04ebd9b3572da7802290438af2a681895441)

(0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40, 0xbde70df51939b94c9c24979fa7dd04ebd9b3572da7802290438af2a681895441)

(0x01, 0xbde70df51939b94c9c24979fa7dd04ebd9b3572da7802290438af2a681895441)

if I do the same with the inverse of the point, I get these (inverses of above)

(0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee, 0x4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee)

(0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40, 0x4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee)

(0x1, 0x4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee)

The X value

0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee 

in some of those results, also happens to be the beta value from here

  • testnet.smartbit.com.au/tx/… - the signature in this transaction is 30060201010201 (R=1, S=1) and is valid :) – amaclin Sep 18 '17 at 6:19
  • 1
    I was unable to find the rawtx for this tx from anywhere. I suspect the tx doesn't actually verify, and the generator that generated r=1, most likely wasn't ecdsa secp256k1. but I think you might be able to modify the p value and other variables in the ecdsa function to output a 1. this tx was probably created using a custom ecdsa function, or just hard coded straight into it. – Sean Bradley Sep 19 '17 at 8:36
  • imgur.com/a/GpuSS – amaclin Sep 19 '17 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.