Are there infinite signatures that i can produce for a given message using a given private key?

Darshan V

6/16/23, 7:11 PM

In the context of ECDSA , given that i have a message and a private key , i can change value of k and i will get different signature , doesn't that mean i can create infinite signatures and all of those will be valid and that means i can forge a signature right as i can assume that random signature that i guessed for a message will also be one of those infinite signatures that can be generated using different value of k.

I know things don't work this way so any help in clearing my misunderstanding would be appreciated.

0 + 0

signature

Score:3

Crypto

meshcollider

6/16/23, 8:49 PM

There are effectively infinite signatures you can produce, yes. Technically not infinite because $k$ must be less than the order of the elliptic curve group you are using. But that's so many options that you'll never possibly be able to use them all.

That definitely doesn't mean you can forge a signature. Just because there are infinite doesn't mean that they're easy to find. The values you use need to satisfy the verification equation. Brute-force generation of random signatures until one validates will take literally forever. That's why these signature schemes are considered secure. Usually such brute forcing would be as difficult as finding the secret key by brute-force.

0 + 0

Darshan V

6/17/23, 4:56 AM

So is it more like for all k's used there won't be k or k/2 signautres (k/2 because reflection of signature about x axis is also valid) , instead it might be that for multiple k it might generate same signature and hence there will be some finite signatures

fgrieu

6/17/23, 8:26 AM

Addition of an analogy: there (most likely) are infinitely many bitstrings which SHA3-256 is all-zero. But we can't find any.

meshcollider

6/17/23, 10:11 AM

Very informally, there are tonnes of valid signatures (one for each choice of $k$), but *many, many, many more* invalid ones. The valid ones are well hidden amongst all the invalid ones.

tylo

6/18/23, 4:32 AM

@meshcollider Actually, I think that statement is not provable and might be false. For fixed input, the hash function could be injective (or very close to it) between the domain of $k$ and the image of the hash, even if unlikely. Of course everyone can check that points are on the curve, so only those have to be considered at all.

meshcollider

6/18/23, 5:24 AM

@tylo what do you mean by injective for a fixed input? For a fixed input, the hash function is fixed :)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Are there infinite signatures that i can produce for a given message using a given private key?

TH: มีลายเซ็นที่ไม่สิ้นสุดที่ฉันสามารถสร้างสำหรับข้อความที่กำหนดโดยใช้รหัสส่วนตัวที่กำหนดหรือไม่

RO: Există semnături infinite pe care le pot produce pentru un anumit mesaj folosind o anumită cheie privată?

RU: Существуют ли бесконечные подписи, которые я могу создать для данного сообщения, используя данный закрытый ключ?

VI: Có vô số chữ ký mà tôi có thể tạo cho một thông báo nhất định bằng khóa riêng đã cho không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.