The Schnorr Signature equation as simple as\u00a0possible<\/p>\n
The Schnorr signature scheme<\/strong><\/a> was introduced by Claus-Peter Schnorr, a German mathematician, in 1989 and patented in 1990. Due to the patent, the scheme was not widely adopted in public cryptography. Schnorr held the patent until 2008, the same year Satoshi Nakamoto<\/strong> introduced Bitcoin. The Digital Signature Algorithm (DSA)<\/a> was published by The National Institute of Standards and Technology (NIST) in 1991. Curiously, DSA algorithm was developed as a workaround to Schnorr\u2019s patent restrictions. While the Schnorr scheme utilizes a straightforward linear equation, DSA involves a more complex equation with division, limiting certain optimizations and applications available in the Schnorr\u00a0scheme.<\/p>\n Without going into deep mathematical details, the Schnorr signature equation for an elliptic curve over an integer field modulo prime (m<\/em><\/strong>) involves two types of elements:<\/p>\n Integer values<\/strong> on a field with a prime modulo (denoted here by lowercase Latin letters, such as r<\/em> or\u00a0x<\/em>)Points on the elliptic curve<\/strong> defined over the same prime modulo field (denoted here by uppercase Latin letters, such as P<\/em> or R<\/em>). An elliptic curve over an integer field has a special point denoted as the generator point (G)<\/strong>. This is a specific point on the curve such that any other point can be derived by multiplying the generator point by an\u00a0integer.<\/p>\n Several basic operations are defined for elliptic curve\u00a0points:<\/p>\n Point Addition: A + B =\u00a0C<\/em>Point Multiplication by an integer: k \u2219 A = kA =\u00a0D<\/em>Point Negation: -A = E<\/em> (where A + (-B) = C<\/em> implies A\u200a\u2014\u200aB =\u00a0C<\/em>)<\/p>\n These operations are similar to standard algebra, with one significant exception: division is not defined in elliptic curve cryptography. The lack of a division operation for the points on an elliptic curve is a fundamental aspect of its security, closely tied to the discrete logarithm problem<\/a>.<\/p>\n The following outlines the Bitcoin implementation of the Schnorr signature scheme<\/a>, which differs slightly from the original.<\/p>\n Let:<\/p>\n x\u200a\u2014\u200a<\/em>the secret key (a random integer less\u00a0m<\/em><\/strong>),P = x<\/em>G<\/em><\/strong>\u200a\u2014\u200athe public key (a point on the elliptic\u00a0curve),r<\/em>\u200a\u2014\u200aan ephemeral secret (another random integer less\u00a0m<\/em><\/strong>),R = r<\/em>G<\/em><\/strong>\u200a\u2014\u200athe ephemeral public key (a point on the\u00a0curve).h(message)<\/em>\u200a\u2014\u200aa hash function applied to some message, producing an integer. Bitcoin uses double sha256 and some additional arguments transformations (see\u00a0BIP340)<\/p>\n The Schnorr signature is generated as\u00a0follows:<\/p>\n s <\/em>= r <\/em>+ h(R,P,m)<\/em>\u22c5x <\/em>(1)<\/p>\n Here, {R<\/em>, s<\/em>} is the signature, and only someone with knowledge of both x<\/em> and r<\/em> can compute\u00a0s<\/em>.<\/p>\n The signature is valid if the following equation is satisfied:<\/p>\n s<\/em>G <\/em><\/strong>= R <\/em>+ h(R,P,d)<\/em>\u22c5P<\/em> (2)<\/p>\n Equation (2) is derived by multiplying equation (1) by G<\/em><\/strong>. In this equation, P<\/em> is the public key, R<\/em> is part of the signature, and d<\/em> is the data being\u00a0signed.<\/p>\n The use of the integer field with a prime modulo<\/strong> is central to this type of cryptography. Although the specifics go beyond the scope of this article, it is important to note that the prime modulo is slightly smaller than the formal integer boundary used in computer calculations. For example, the formal integer boundary for Bitcoin\u2019s secp256k1 curve is the maximum 256-bit integer (32\u00a0bytes):<\/p>\n 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF<\/em>,<\/p>\n and the prime modulo\u00a0is:<\/p>\n 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF<\/em>EFFFFFC2F<\/em><\/strong>.<\/em><\/p>\n At least but not last, it means that the private key, which is greater than m<\/em><\/strong>, is\u00a0invalid.<\/p>\n Each point on an elliptic curve is defined by two coordinates: x<\/em> and y<\/em>. The elliptic curve equation allows the y<\/em>-coordinate to be computed from the x<\/em>-coordinate, but this produces two possible solutions\u200a\u2014\u200aone even and one odd. As a result, each private key in elliptic curve cryptography (ECC) corresponds to two potential public keys. In Bitcoin, this is addressed by discarding point with an odd y<\/em>-coordinate, retaining only the even solution. This approach ensures that public keys have a consistent 256-bit length, matching the 256-bit private\u00a0keys.<\/p>\n Future articles will discuss several interesting and practical operations that stem from this\u00a0scheme.<\/p>\n The Bitcoin Schnorr Signature in a Nutshell<\/a> was originally published in Coinmonks<\/a> on Medium, where people are continuing the conversation by highlighting and responding to this story.<\/p>","protected":false},"excerpt":{"rendered":" The Schnorr Signature equation as simple as\u00a0possible History The Schnorr signature scheme was introduced by Claus-Peter Schnorr, a German mathematician, in 1989 and patented in 1990. Due to the patent, the scheme was not widely adopted in public cryptography. Schnorr held the patent until 2008, the same year Satoshi Nakamoto introduced Bitcoin. The Digital Signature […]<\/p>\n","protected":false},"author":0,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-8148","post","type-post","status-publish","format-standard","hentry","category-interesting"],"_links":{"self":[{"href":"https:\/\/mycryptomania.com\/index.php?rest_route=\/wp\/v2\/posts\/8148"}],"collection":[{"href":"https:\/\/mycryptomania.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mycryptomania.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/mycryptomania.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=8148"}],"version-history":[{"count":0,"href":"https:\/\/mycryptomania.com\/index.php?rest_route=\/wp\/v2\/posts\/8148\/revisions"}],"wp:attachment":[{"href":"https:\/\/mycryptomania.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=8148"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mycryptomania.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=8148"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mycryptomania.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=8148"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Elliptic Curve\u00a0Math<\/h3>\n
The Schnorr Signature<\/h3>\n
More Context<\/h3>\n