How can my private key be revealed if I use the same nonce while generating the signature?How can I use message signing to prove that I have private keys for many different accounts?Step by Step - how does sending 1 bitcoin work?Can same private key generate multiple addresses?How a private key can be invalid?Multi signature wallet I'll know the private keyGenerating private/public key and using ECC and EC_POINT_mul() functionDigital Signature and private/public keyWhat does a bitcoin transaction contain?generating private key from bip39 seedHow can you calculate the inverse of S component of signature, while you cannot do it in ECC to calculate private key from public key?
Why "be dealt cards" rather than "be dealing cards"?
Finding all intervals that match predicate in vector
How can a jailer prevent the Forge Cleric's Artisan's Blessing from being used?
Implement the Thanos sorting algorithm
Is it okay / does it make sense for another player to join a running game of Munchkin?
Ways to speed up user implemented RK4
Can I use my Chinese passport to enter China after I acquired another citizenship?
What is the intuitive meaning of having a linear relationship between the logs of two variables?
Bash method for viewing beginning and end of file
Curses work by shouting - How to avoid collateral damage?
How can I get through very long and very dry, but also very useful technical documents when learning a new tool?
What is difference between behavior and behaviour
How was Earth single-handedly capable of creating 3 of the 4 gods of chaos?
voltage of sounds of mp3files
How do I keep an essay about "feeling flat" from feeling flat?
Cynical novel that describes an America ruled by the media, arms manufacturers, and ethnic figureheads
Do I need a multiple entry visa for a trip UK -> Sweden -> UK?
Go Pregnant or Go Home
Irreducibility of a simple polynomial
What is the oldest known work of fiction?
Can somebody explain Brexit in a few child-proof sentences?
What are the ramifications of creating a homebrew world without an Astral Plane?
Coordinate position not precise
Is there any reason not to eat food that's been dropped on the surface of the moon?
How can my private key be revealed if I use the same nonce while generating the signature?
How can I use message signing to prove that I have private keys for many different accounts?Step by Step - how does sending 1 bitcoin work?Can same private key generate multiple addresses?How a private key can be invalid?Multi signature wallet I'll know the private keyGenerating private/public key and using ECC and EC_POINT_mul() functionDigital Signature and private/public keyWhat does a bitcoin transaction contain?generating private key from bip39 seedHow can you calculate the inverse of S component of signature, while you cannot do it in ECC to calculate private key from public key?
I know it is well understood that it is not a good practice to use the same nonce while generating the signatures, but I am not getting the math right.
Assume I have some UTXOs that are controlled by my private key Q. Say I have spent two of the UTXOs using nonce 'N' to generate my signature. Now the (R,S) components of the signature are public and the transactions are public so everyone has access to them.
S1 = N^(-1)*[hash(m1) + Q*R] mod p
S2 = N^(-1)*[hash(m2) + Q*R] mod p
S1 - S2 = N^(-1)*[hash(m1) - hash(m2)] mod p
Even though we know S1, S2, m1 and m2, isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
private-key signature cryptography
asked 7 hours ago
Ugam KamatUgam Kamat
42112
add a comment |
I know it is well understood that it is not a good practice to use the same nonce while generating the signatures, but I am not getting the math right.
Assume I have some UTXOs that are controlled by my private key Q. Say I have spent two of the UTXOs using nonce 'N' to generate my signature. Now the (R,S) components of the signature are public and the transactions are public so everyone has access to them.
S1 = N^(-1)*[hash(m1) + Q*R] mod p
S2 = N^(-1)*[hash(m2) + Q*R] mod p
S1 - S2 = N^(-1)*[hash(m1) - hash(m2)] mod p
Even though we know S1, S2, m1 and m2, isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
private-key signature cryptography
asked 7 hours ago
Ugam KamatUgam Kamat
42112
add a comment |
I know it is well understood that it is not a good practice to use the same nonce while generating the signatures, but I am not getting the math right.
Assume I have some UTXOs that are controlled by my private key Q. Say I have spent two of the UTXOs using nonce 'N' to generate my signature. Now the (R,S) components of the signature are public and the transactions are public so everyone has access to them.
S1 = N^(-1)*[hash(m1) + Q*R] mod p
S2 = N^(-1)*[hash(m2) + Q*R] mod p
S1 - S2 = N^(-1)*[hash(m1) - hash(m2)] mod p
Even though we know S1, S2, m1 and m2, isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
private-key signature cryptography
asked 7 hours ago
Ugam KamatUgam Kamat
42112
I know it is well understood that it is not a good practice to use the same nonce while generating the signatures, but I am not getting the math right.
Assume I have some UTXOs that are controlled by my private key Q. Say I have spent two of the UTXOs using nonce 'N' to generate my signature. Now the (R,S) components of the signature are public and the transactions are public so everyone has access to them.
S1 = N^(-1)*[hash(m1) + Q*R] mod p
S2 = N^(-1)*[hash(m2) + Q*R] mod p
S1 - S2 = N^(-1)*[hash(m1) - hash(m2)] mod p
Even though we know S1, S2, m1 and m2, isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
private-key signature cryptography
private-key signature cryptography
asked 7 hours ago
Ugam KamatUgam Kamat
42112
asked 7 hours ago
Ugam KamatUgam Kamat
42112
asked 7 hours ago
Ugam KamatUgam Kamat
42112
asked 7 hours ago
Ugam KamatUgam Kamat
42112
asked 7 hours ago
Ugam KamatUgam Kamat
42112
42112
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
No, it is not. This does not require finding the discrete logarithm at all. Solving the discrete logarithm is finding the exponent to a known base. However in this problem we are trying to find the base and know what the exponent is. Furthermore, this known exponent is -1 for which finding the base of something raise to -1 is to raise the result to -1 again, i.e. taking the inverse of the inverse.
There are algorithms that exist to find the modular inverse of a number which is how N^(-1) is found in the first place. To find N, you just need to take the inverse of N^(-1) because of the identity that an inverse an inverse is the element itself.
answered 6 hours ago
Andrew Chow♦Andrew Chow
33k42462
Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?
– Ugam Kamat
5 hours ago
1
No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.
– Andrew Chow♦
5 hours ago
That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.
– Ugam Kamat
5 hours ago
add a comment |
Let me rewrite your question in a different notation, where all lowercase values are integers and uppercase values are points.
- The group generator is G (a known constant).
- The private key is q, its corresponding public key is Q = qG.
- The nonce is n, its corresponding point is R = nG.
- The X coordinate of R is r.
- The hash function is h(x).
- A signature is (r,s), where s is computed as n-1(h(m) + qr).
- A signature is valid iff r = x(s-1(h(m)G + rQ)).
Now for the two signatures it holds that:
- s1 = n-1(h(m1) + qr)
- s2 = n-1(h(m2) + qr)
- s1 - s2 = n-1(h(m1) - h(m2))
- n = (s1 - s2)-1(h(m1) - h(m2))
As s1 and s2 are just integers, (s1 - s2)-1 can be trivially computed using a modular inverse; there are no elliptic curve points involved here (over which this problem would be hard).
Once you know n, you can find q by rewriting the first equation:
- ns1 = h(m1) + qr
- ns1 - h(m1) = qr
- q = r-1(ns1 - h(m1))
answered 5 hours ago
Pieter WuillePieter Wuille
47.7k399160
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "308"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fbitcoin.stackexchange.com%2fquestions%2f85638%2fhow-can-my-private-key-be-revealed-if-i-use-the-same-nonce-while-generating-the%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
No, it is not. This does not require finding the discrete logarithm at all. Solving the discrete logarithm is finding the exponent to a known base. However in this problem we are trying to find the base and know what the exponent is. Furthermore, this known exponent is -1 for which finding the base of something raise to -1 is to raise the result to -1 again, i.e. taking the inverse of the inverse.
There are algorithms that exist to find the modular inverse of a number which is how N^(-1) is found in the first place. To find N, you just need to take the inverse of N^(-1) because of the identity that an inverse an inverse is the element itself.
answered 6 hours ago
Andrew Chow♦Andrew Chow
33k42462
Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?
– Ugam Kamat
5 hours ago
1
No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.
– Andrew Chow♦
5 hours ago
That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.
– Ugam Kamat
5 hours ago
add a comment |
isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
No, it is not. This does not require finding the discrete logarithm at all. Solving the discrete logarithm is finding the exponent to a known base. However in this problem we are trying to find the base and know what the exponent is. Furthermore, this known exponent is -1 for which finding the base of something raise to -1 is to raise the result to -1 again, i.e. taking the inverse of the inverse.
There are algorithms that exist to find the modular inverse of a number which is how N^(-1) is found in the first place. To find N, you just need to take the inverse of N^(-1) because of the identity that an inverse an inverse is the element itself.
answered 6 hours ago
Andrew Chow♦Andrew Chow
33k42462
Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?
– Ugam Kamat
5 hours ago
1
No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.
– Andrew Chow♦
5 hours ago
That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.
– Ugam Kamat
5 hours ago
add a comment |
isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
No, it is not. This does not require finding the discrete logarithm at all. Solving the discrete logarithm is finding the exponent to a known base. However in this problem we are trying to find the base and know what the exponent is. Furthermore, this known exponent is -1 for which finding the base of something raise to -1 is to raise the result to -1 again, i.e. taking the inverse of the inverse.
There are algorithms that exist to find the modular inverse of a number which is how N^(-1) is found in the first place. To find N, you just need to take the inverse of N^(-1) because of the identity that an inverse an inverse is the element itself.
answered 6 hours ago
Andrew Chow♦Andrew Chow
33k42462
isn't solving for N^(-1), and hence N, becomes equivalent to finding the solution to the discrete logarithm?
No, it is not. This does not require finding the discrete logarithm at all. Solving the discrete logarithm is finding the exponent to a known base. However in this problem we are trying to find the base and know what the exponent is. Furthermore, this known exponent is -1 for which finding the base of something raise to -1 is to raise the result to -1 again, i.e. taking the inverse of the inverse.
There are algorithms that exist to find the modular inverse of a number which is how N^(-1) is found in the first place. To find N, you just need to take the inverse of N^(-1) because of the identity that an inverse an inverse is the element itself.
answered 6 hours ago
Andrew Chow♦Andrew Chow
33k42462
answered 6 hours ago
Andrew Chow♦Andrew Chow
33k42462
answered 6 hours ago
Andrew Chow♦Andrew Chow
33k42462
answered 6 hours ago
Andrew Chow♦Andrew Chow
33k42462
33k42462
Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?
– Ugam Kamat
5 hours ago
1
No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.
– Andrew Chow♦
5 hours ago
That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.
– Ugam Kamat
5 hours ago
add a comment |
Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?
– Ugam Kamat
5 hours ago
1
No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.
– Andrew Chow♦
5 hours ago
That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.
– Ugam Kamat
5 hours ago
Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?
– Ugam Kamat
5 hours ago
Isn't the order of how the equation is written same as the public key generation? You have [hash(m1) - hash(m2)] as the base and N^(-1) as the exponent?
– Ugam Kamat
5 hours ago
1
1
No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.
– Andrew Chow♦
5 hours ago
No. [hash(m1) - hash(m2)] is an integer, not a elliptic curve point. N^(-1) is also an integer. So this formula is just integer multiplication. It is not exponentiation nor is it curve point multiplication (the two things that have discrete log problems). Thus it is not solving any discrete logarithm.
– Andrew Chow♦
5 hours ago
That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.
– Ugam Kamat
5 hours ago
That's what I was looking for. So since N^(-1)*[hash(m1) - hash(m2)] is just integer multiplication modulo p vs curve point addition.
– Ugam Kamat
5 hours ago
add a comment |
Let me rewrite your question in a different notation, where all lowercase values are integers and uppercase values are points.
- The group generator is G (a known constant).
- The private key is q, its corresponding public key is Q = qG.
- The nonce is n, its corresponding point is R = nG.
- The X coordinate of R is r.
- The hash function is h(x).
- A signature is (r,s), where s is computed as n-1(h(m) + qr).
- A signature is valid iff r = x(s-1(h(m)G + rQ)).
Now for the two signatures it holds that:
- s1 = n-1(h(m1) + qr)
- s2 = n-1(h(m2) + qr)
- s1 - s2 = n-1(h(m1) - h(m2))
- n = (s1 - s2)-1(h(m1) - h(m2))
As s1 and s2 are just integers, (s1 - s2)-1 can be trivially computed using a modular inverse; there are no elliptic curve points involved here (over which this problem would be hard).
Once you know n, you can find q by rewriting the first equation:
- ns1 = h(m1) + qr
- ns1 - h(m1) = qr
- q = r-1(ns1 - h(m1))
answered 5 hours ago
Pieter WuillePieter Wuille
47.7k399160
add a comment |
Let me rewrite your question in a different notation, where all lowercase values are integers and uppercase values are points.
- The group generator is G (a known constant).
- The private key is q, its corresponding public key is Q = qG.
- The nonce is n, its corresponding point is R = nG.
- The X coordinate of R is r.
- The hash function is h(x).
- A signature is (r,s), where s is computed as n-1(h(m) + qr).
- A signature is valid iff r = x(s-1(h(m)G + rQ)).
Now for the two signatures it holds that:
- s1 = n-1(h(m1) + qr)
- s2 = n-1(h(m2) + qr)
- s1 - s2 = n-1(h(m1) - h(m2))
- n = (s1 - s2)-1(h(m1) - h(m2))
As s1 and s2 are just integers, (s1 - s2)-1 can be trivially computed using a modular inverse; there are no elliptic curve points involved here (over which this problem would be hard).
Once you know n, you can find q by rewriting the first equation:
- ns1 = h(m1) + qr
- ns1 - h(m1) = qr
- q = r-1(ns1 - h(m1))
answered 5 hours ago
Pieter WuillePieter Wuille
47.7k399160
add a comment |
Let me rewrite your question in a different notation, where all lowercase values are integers and uppercase values are points.
- The group generator is G (a known constant).
- The private key is q, its corresponding public key is Q = qG.
- The nonce is n, its corresponding point is R = nG.
- The X coordinate of R is r.
- The hash function is h(x).
- A signature is (r,s), where s is computed as n-1(h(m) + qr).
- A signature is valid iff r = x(s-1(h(m)G + rQ)).
Now for the two signatures it holds that:
- s1 = n-1(h(m1) + qr)
- s2 = n-1(h(m2) + qr)
- s1 - s2 = n-1(h(m1) - h(m2))
- n = (s1 - s2)-1(h(m1) - h(m2))
As s1 and s2 are just integers, (s1 - s2)-1 can be trivially computed using a modular inverse; there are no elliptic curve points involved here (over which this problem would be hard).
Once you know n, you can find q by rewriting the first equation:
- ns1 = h(m1) + qr
- ns1 - h(m1) = qr
- q = r-1(ns1 - h(m1))
answered 5 hours ago
Pieter WuillePieter Wuille
47.7k399160
Let me rewrite your question in a different notation, where all lowercase values are integers and uppercase values are points.
- The group generator is G (a known constant).
- The private key is q, its corresponding public key is Q = qG.
- The nonce is n, its corresponding point is R = nG.
- The X coordinate of R is r.
- The hash function is h(x).
- A signature is (r,s), where s is computed as n-1(h(m) + qr).
- A signature is valid iff r = x(s-1(h(m)G + rQ)).
Now for the two signatures it holds that:
- s1 = n-1(h(m1) + qr)
- s2 = n-1(h(m2) + qr)
- s1 - s2 = n-1(h(m1) - h(m2))
- n = (s1 - s2)-1(h(m1) - h(m2))
As s1 and s2 are just integers, (s1 - s2)-1 can be trivially computed using a modular inverse; there are no elliptic curve points involved here (over which this problem would be hard).
Once you know n, you can find q by rewriting the first equation:
- ns1 = h(m1) + qr
- ns1 - h(m1) = qr
- q = r-1(ns1 - h(m1))
answered 5 hours ago
Pieter WuillePieter Wuille
47.7k399160
edited 5 hours ago
answered 5 hours ago
Pieter WuillePieter Wuille
47.7k399160
answered 5 hours ago
Pieter WuillePieter Wuille
47.7k399160
answered 5 hours ago
Pieter WuillePieter Wuille
47.7k399160
47.7k399160
add a comment |
add a comment |
Thanks for contributing an answer to Bitcoin Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fbitcoin.stackexchange.com%2fquestions%2f85638%2fhow-can-my-private-key-be-revealed-if-i-use-the-same-nonce-while-generating-the%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
