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.

Improve this question
0

2 Answers 2

Reset to default
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.

Improve this answer
7
  • 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.
    – Claris
    Jul 10, 2015 at 15:53
  • 1
    Nothing is "serious". Everything is just a "game".
    – amaclin
    Jul 10, 2015 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).
    – Claris
    Jul 10, 2015 at 19:50
  • 1
    FYI: blockchain.info/tx/… rlen=0x15
    – amaclin
    Jul 11, 2015 at 21:12
  • 1
    @PieterWuille there are points on secp256k1 with x=1,2,3,4,6,... but not x=0,5,7,.... The other Answer gives an on-chain example for x=1. Curiously though there is no point with x=7, there is one with r=7 (since r = x mod n, and x=n+7 does have points).
    – Mark Lundeberg
    Mar 28, 2019 at 17:19
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

Improve this answer
5

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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