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.

amaclin
  • 6,718
  • 1
  • 20
  • 32

2 Answers2

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.

Elliot Cameron
  • 103
  • 3
Claris
  • 15,323
  • 2
  • 26
  • 43
  • 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 '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). – Claris Jul 10 '15 at 19:50
  • I have a right to do with my private key/ my funds/ my money whatever I want. Right now I want to use specific `k` value to sign my transactions – amaclin Jul 10 '15 at 20:18
  • @PieterWuille Oh thanks, I completely missed that. – Claris Jul 11 '15 at 16:16
  • 1
    FYI: https://blockchain.info/tx/b698b58d32f27abf8a89637d60573c7069b199ac8efbd17eb3853c0264942133 rlen=0x15 – amaclin Jul 11 '15 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 '19 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

Sean Bradley
  • 401
  • 4
  • 5
  • https://testnet.smartbit.com.au/tx/c6c232a36395fa338da458b86ff1327395a9afc28c5d2daa4273e410089fd433 - the signature in this transaction is 30060201010201 (R=1, S=1) and is valid :) – amaclin Sep 18 '17 at 06: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 08:36
  • https://imgur.com/a/GpuSS – amaclin Sep 19 '17 at 08:43
  • https://bitcointalk.org/index.php?topic=1729534.0 – amaclin Sep 19 '17 at 08:44
  • Working link: https://blockstream.info/testnet/tx/c6c232a36395fa338da458b86ff1327395a9afc28c5d2daa4273e410089fd433?expand – shuckc Jun 29 '22 at 20:23