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?

What would be the benefits of having both a state and local currencies?

What are the ramifications of creating a homebrew world without an Astral Plane?

Is it okay / does it make sense for another player to join a running game of Munchkin?

Should my PhD thesis be submitted under my legal name?

Why are on-board computers allowed to change controls without notifying the pilots?

HashMap containsKey() returns false although hashCode() and equals() are true

Hostile work environment after whistle-blowing on coworker and our boss. What do I do?

Was Spock the First Vulcan in Starfleet?

How will losing mobility of one hand affect my career as a programmer?

Why is delta-v is the most useful quantity for planning space travel?

Is there a good way to store credentials outside of a password manager?

voltage of sounds of mp3files

Do I need a multiple entry visa for a trip UK -> Sweden -> UK?

Where in the Bible does the greeting ("Dominus Vobiscum") used at Mass come from?

How can a jailer prevent the Forge Cleric's Artisan's Blessing from being used?

Invariants between two isomorphic vector spaces

What is the oldest known work of fiction?

The One-Electron Universe postulate is true - what simple change can I make to change the whole universe?

Using parameter substitution on a Bash array

What does the word "foliage" mean here?

Can I Retrieve Email Addresses from BCC?

What will be the benefits of Brexit?

How can I use the arrow sign in my bash prompt?

Time travel short story where a man arrives in the late 19th century in a time machine and then sends the machine back into the past



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?













2















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?










share|improve this question


























    2















    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?










    share|improve this question
























      2












      2








      2








      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?










      share|improve this question














      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






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked 3 hours ago









      Ugam KamatUgam Kamat

      42112




      42112




















          2 Answers
          2






          active

          oldest

          votes


















          1















          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.






          share|improve this answer























          • 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
            1 hour 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
            1 hour 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
            58 mins ago


















          2














          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))





          share|improve this answer
























            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
            );



            );













            draft saved

            draft discarded


















            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









            1















            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.






            share|improve this answer























            • 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
              1 hour 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
              1 hour 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
              58 mins ago















            1















            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.






            share|improve this answer























            • 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
              1 hour 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
              1 hour 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
              58 mins ago













            1












            1








            1








            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.






            share|improve this answer














            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.







            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered 1 hour ago









            Andrew ChowAndrew 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
              1 hour 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
              1 hour 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
              58 mins 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
              1 hour 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
              1 hour 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
              58 mins 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
            1 hour 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
            1 hour 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
            1 hour 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
            1 hour 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
            58 mins 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
            58 mins ago











            2














            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))





            share|improve this answer





























              2














              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))





              share|improve this answer



























                2












                2








                2







                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))





                share|improve this answer















                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))






                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited 53 mins ago

























                answered 1 hour ago









                Pieter WuillePieter Wuille

                47.7k399160




                47.7k399160



























                    draft saved

                    draft discarded
















































                    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.




                    draft saved


                    draft discarded














                    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





















































                    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







                    Popular posts from this blog

                    名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

                    格濟夫卡 參考資料 导航菜单51°3′40″N 34°2′21″E / 51.06111°N 34.03917°E / 51.06111; 34.03917ГезівкаПогода в селі 编辑或修订