Elliptic Curve Digital Signature Algorithm

Third lesson for the Bitcoin and Blockchain Technology course of Milano-Bicocca and Politecnico di Milano

www.ametrano.net/bbt/

Transcript

1. Bitcoin and Blockchain Technology Elliptic Curve Digital Signature Algorithm v2019.04.03 Comments, corrections, and questions: https://drive.google.com/open?id=1MZu_4zbI8khdYhbGJg9SwWkNA5x-Tb_W © 2019 Digital Gold Institute
2. Table of Contents 1. Modular Arithmetic 2. Algebra of Sets: Finite Field 3. Elliptic Curves over Real Numbers 4. Elliptic Curve over 5. Asymmetric Cryptography on Elliptic Curves 6. Digital Signature Protocol 7. Elliptic Curve Digital Signature Algorithm © 2019 Digital Gold Institute 2/69
3. Modular Arithmetic arithmetic for integers: numbers "wrap around" upon reaching the modulo value Example: ▪ 9+4 = 1 mod 12 © 2019 Digital Gold Institute https://commons.wikimedia.org/wiki/File:Clock_group.svg 3/69
4. Congruence and Remainders If 1 ≡ 1 mod and 2 ≡ 2 mod then ▪ 1 + 2 ≡ 1 + 2 (mod ) ▪ 1 − 2 ≡ 1 − 2 (mod ) ▪ 1 2 ≡ 1 2 (mod ) ▪ mod b mod ≡ mod ▪ mod b mod mod = () mod © 2019 Digital Gold Institute 4/69
5. Table of Contents 1. Modular Arithmetic 2. Algebra of Sets: Finite Field 3. Elliptic Curves over Real Numbers 4. Elliptic Curve over 5. Asymmetric Cryptography on Elliptic Curves 6. Digital Signature Protocol 7. Elliptic Curve Digital Signature Algorithm © 2019 Digital Gold Institute 5/69
6. Group {F, +} (1/2) A group is a set F together with a binary operator + (also known as group law) with the following properties: ▪ Closure: for all a and b in F, a+b is also in F; ∀, ∈ , + ∈ ▪ Identity: there exists a unique neutral element 0 in F, such that for every element a in F, the equation 0+a=a+0=a; ∃! 0, ∈ | 0 + = + 0 = , ∀ ∈ ▪ Invertibility: for each a in F, there exists the inverse b in F, commonly denoted -a, such that a+b=b+a=0; ∀ ∈ , ∃ − | + (−) = (−) + = 0 ▪ Associativity: for all a, b and c in F, (a+b)+c=a+(b+c); ∀, , ∈ , + + = + ( + ) The number of elements in a group is the group order © 2019 Digital Gold Institute 6/69
7. Additive or Multiplicative Notation Neutral Element Inverse Additive Notation Zero Opposite Multiplicative Notation Identity Inverse © 2019 Digital Gold Institute 7/69
8. Group {F, +} (2/2) ▪ The set of all integer numbers under addition {ℤ, +} is an infinite order group ▪ The set of all integer numbers under multiplication {ℤ, ∙} is not a group (e.g. multiplicative inverse of 2 is not an integer) ▪ Τ ℤ ℤ : { 0, − 1 , +}, i.e. the set of integer numbers 0, − 1 under addition modulo , is a group of order − 0 is the neutral element (also called zero) − The inverse of any element is − , © 2019 Digital Gold Institute 8/69
9. Commutative Group {F, +} A group {F, +} is commutative if for all a and b in F, a+b = b+a ∀, ∈ , + = + ▪ The set of all integer numbers under addition {ℤ, +} is a commutative group ▪ For any modulo , Τ ℤ ℤ : { 0, − 1 , +} is a commutative group © 2019 Digital Gold Institute 9/69
10. Cyclic Group {F, +} A group {F, +} is cyclic if there is a generator element ∃ ∀ ∈ , ∃ = + ⋯ + ( ) ▪ When the group order is prime, the group is cyclic: starting from any (non-zero) element and adding this element to itself successively, all elements of the set are recovered ▪ For any prime , Τ ℤ ℤ : { 0, − 1 , +} is a cyclic group; e.g. for = 7, { 0, 6 , +}: − starting from 3 the cycle is 3+3 %7=6; 6+3 %7=2; 2+3 %7=5; 5+3 %7=1; 1+3 %7=4; 4+3 %7=0; 0+3 %7=3 − starting from 2 the cycle is 2+2 %7=4; 4+2 %7=6; 6+2 %7=1; 1+2 %7=3; 3+2 %7=5; 5+2 %7=0; 0+2 %7=2 © 2019 Digital Gold Institute 10/69
11. Ring and Field {F, +, ∙} ▪ A ring is a commutative group with a second binary operator that is associative and with distributive properties making the two operators “compatible” ∀, , ∈ , + ∙ = ∙ + ∙ ▪ A field is a ring such that the second operation, after throwing out the identity element of the first operation, satisfies all the commutative group properties ▪ Real numbers ℝ and rational numbers ℚ, with addition and multiplication, are fields of infinite order ▪ In a field you can add, subtract (i.e. add the additive opposite), multiply, and divide (i.e. multiply for the multiplicative inverse) © 2019 Digital Gold Institute 11/69
12. The Finite Field Fp = {[0, p−1], +, ∙} ▪ We already established that for any modulo , { 0, − 1 , +} is a commutative (cyclic) group ▪ For any prime number , { , − 1 , ∙} is also a commutative group − 1 is the identity element − For any element there exist its inverse , such that = 1 . It is crucial here that is prime = { 0, − 1 , +,∙} is a finite field © 2019 Digital Gold Institute 12/69
13. E.g.: The Finite Field F7 {[0, 6], +} is a commutative group ▪ 4+3 %7 = 0 → 3 is the opposite of 4 ▪ Subtraction must be interpreted as addition of the opposite 2-4 %7 = 2+3 %7 = 5 2-4 %7 =-2 %7 = 5 {[1, 6], ∙} is a commutative group ▪ 4 ∙ 2 %7 = 1 → 2 is the inverse of 4 ▪ Division must be interpreted as multiplication by the inverse 5 ÷ 4 %7 = 5 ∙ 2 %7 = 3 © 2019 Digital Gold Institute 13/69
14. Fermat’s Little Theorem When is prime, for each : −1 = 1 e.g. in ([1, 6], ∙ ) with = 3, 36 = 1: 3^2 %7 = 3*3 %7 = 2 3^3 %7 = 2*3 %7 = 6 3^4 %7 = 6*3 %7 = 4 3^5 %7 = 4*3 %7 = 5 3^6 %7 = 5*3 %7 = 1 © 2019 Digital Gold Institute 14/69
15. Inverse Calculation ▪ So, it holds that the inverse of −1 = −1 ∙ 1 = −1 ∙ −1 = −2 ▪ In Python a_inv = pow(a, p-2, p) © 2019 Digital Gold Institute 15/69
16. Square root concept E.g. in 7 : ▪ 2*2 %7 = 4 → 2 is a (even) square root of 4 ▪ 5*5 %7 = 4 → 5 is a (odd) square root of 4 ▪ 5 = -2 %7 → odd root is similar to negative root for integers ▪ 2 + 5 = 7 → even root + odd root = p © 2019 Digital Gold Institute 16/69
17. The Finite Field F7 © 2019 Digital Gold Institute opposite inverse odd sqrt even sqrt 0 0 #N/A 0 0 1 6 1 1 6 2 5 4 3 4 3 4 5 #N/A #N/A 4 3 2 5 2 5 2 3 #N/A #N/A 6 1 6 #N/A #N/A 17/69
18. Homework Calculate the table of opposites, inverses, and square roots for the finite fields 19 and 23 Use mod_inv and mod_sqrt from github.com/dginst/btclib/numbertheory.py or Excel/VBA from github.com/dginst/bbt/excel/FiniteFields.xlsm © 2019 Digital Gold Institute 18/69
19. Table of Contents 1. Modular Arithmetic 2. Algebra of Sets: Finite Field 3. Elliptic Curves over Real Numbers 4. Elliptic Curve over 5. Asymmetric Cryptography on Elliptic Curves 6. Digital Signature Protocol 7. Elliptic Curve Digital Signature Algorithm © 2019 Digital Gold Institute 19/69
20. Elliptic Curves over Real Numbers ▪ A formal definition would require algebraic geometry ▪ Defined by the Weierstrass equation: = + + , , ∈ ℝ ▪ The curve is non-singular if: ∆= −16 43 + 272 ≠ 0 © 2019 Digital Gold Institute 20/69
21. Elliptic Curve = − + a = -7 b = 10 ± = ± 3 − 7 + 10 Negative y roots are in red, positive ones in blue © 2019 Digital Gold Institute -5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 21/69
22. Point Addition P+Q=R © 2019 Digital Gold Institute https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-add.html 22/69
23. Point Doubling Q+Q=R © 2019 Digital Gold Institute https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-add.html 23/69
24. Algebraic Formulae Point Addition P+Q=R ▪ = − − 2 − − ▪ = − − − − Point Doubling Q+Q=R ▪ = 3 2+ 2 2 − 2 ▪ = 3 2+ 2 − − 2 © 2019 Digital Gold Institute 24/69
25. Infinity Point (aka Group Identity or Neutral Element) Adding two points with the same x-coordinate (y-coordinates being the positive/negative roots of the same 3 + + ) “shoots” at the infinity point ∞ Doubling the point (x, 0) also shoots at ∞ ∞ is the group neutral element: ▪ zero in additive notation ▪ identity in multiplicative notation © 2019 Digital Gold Institute https://en.wikipedia.org/wiki/Elliptic_curve#/media/File:ECClines.svg 25/69
26. Opposite of Point Q The infinity point is providing the opposite formula: + = 0 → = − = (, ) and − = (, − ) have the same coordinate. Therefore, their coordinates are the positive/negative roots of: ± = ± 3 + + So − = − and − = , − For every , in the group, , − is also in the group © 2019 Digital Gold Institute 26/69
27. Compressed Point Representation = , For every , given 2 = 3 + + , two roots are possible: ± = ± 3 + + plus one single bit ෤ = 0/1 is enough to describe the point: = (, ෤ ) © 2019 Digital Gold Institute 27/69
28. Elliptic Curve Commutative Group ▪ With the addition operation, the points of an elliptic curve (augmented with ∞) are a commutative group ▪ The ∞ point is the neutral element, implicitly defining the opposite concept ▪ Arbitrarily named addition: it is simply the group law, and it could have been called multiplication instead − In multiplicative notation doubling would have been called squaring © 2019 Digital Gold Institute 28/69
29. Point Multiplication = ▪ Point multiplication = ( ∈ ℕ) is a convenient notation for the repeated application of addition = + ⋯ + ( ) ▪ Elliptic curve multiplication is not a binary operation on the set of curve points: it does not combine two points! ▪ Addition is the only elliptic curve group binary operation © 2019 Digital Gold Institute 29/69
30. Double and Add Algorithm = 947 = 20 + 21 + 24 + 25 + 27 + 28 + 2 9 doublings = 947 = 1 + 2 + 16 + 32 + 128 + 256 + 512 6 additions 9 doublings for the powers of two and 6 additions: polynomial in the number of bits representing m. Point multiplication 947 = + 2 + 16 + 32 + 128 + 256 + 512 6 point additions 9 doublings for the powers of two and 6 point additions: much better than 946 point additions! © 2019 Digital Gold Institute https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication 30/69
31. Discrete Logarithm Problem (DLP) A One Way Function For any ∈ ℕ, double&add provides an efficient computation of: = To infer from {, } is computationally unfeasible ▪ In additive notation, it is easy to “multiply” = , but difficult to “divide” = Τ ▪ It is called logarithm problem because in multiplicative notation it would have been = , so = © 2019 Digital Gold Institute 31/69
32. Table of Contents 1. Modular Arithmetic 2. Algebra of Sets: Finite Field 3. Elliptic Curves over Real Numbers 4. Elliptic Curve over 5. Asymmetric Cryptography on Elliptic Curves 6. Digital Signature Protocol 7. Elliptic Curve Digital Signature Algorithm © 2019 Digital Gold Institute 32/69
33. Elliptic Curves Over Fp For cryptographic use, we consider the curve not over ℝ, but over a finite field : 2 = 3 + + where 43 + 272 ≠ 0 , , , ∈ © 2019 Digital Gold Institute 33/69
34. y2=x3−7x+10 over F263 Symmetric with respect to = Τ 2 = 131.5 © 2019 Digital Gold Institute 34/69
35. ▪ Geometric interpretation (line drawing) for sum still holds ▪ Adding same-x points shoots at infinity y2=x3−7x+10 over F263 © 2019 Digital Gold Institute 35/69 https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/modk-add.html
36. Opposite of Point Q + = 0 → = − = (, ) and − = (, − ) have the same coordinate. Therefore, the coordinates are the modulo even/odd roots of: , = 3 + + , So − = − and − = (, − ) For every , in the group, , − is also in the group © 2019 Digital Gold Institute 36/69
37. SEC Compressed Point Representation = (, ) ▪ Uncompressed = , representation is For every , two roots are possible: ▪ Even root, compressed = , representation is ▪ Odd root, compressed = , representation is e.g. for y2= x3−7x+10 over F263 (118, 192): 118 192 or 118 (118, 71): 118 71 or 118 © 2019 Digital Gold Institute http://www.secg.org/sec1-v2.pdf 37/69
38. Breaking Opposite Point Symmetry The symmetry between opposite points (same x-coordinate) can be resolved with alternative discrimination criteria for the y- coordinate: 1. odd / even 2. high / low The product of two numbers is a quadratic residue, i.e. does have square roots, when either both or none of its factors are quadratic residues. For prime, = 3 mod 4, the number −1 is not a quadratic residue mod . As such, if −1 ∙ is a quadratic residue mod then is not and vice versa. This provide the additional criterium: 3. (when = 3 mod 4) quadratic residue / not a quadratic residue © 2019 Digital Gold Institute 38/69
39. Hasse Theorem Note that the EC group order = # and the finite field’s prime are different numbers. Hasse theorem shows that: + 1 − 2 ≤ ≤ + 1 + 2 e.g. for 263 , = 263 231 ≤ ≤ 296 y2= x3−7x+10 over F263 ▪ 280 points: 279 affine points plus ∞ ▪ Odd number of affine points: = , 0 must be in the group, = −, 2 = ∞ © 2019 Digital Gold Institute 39/69
40. Elliptic Curves Over a Finite Field Fp ▪ The points on an elliptic curve over a finite field can have cyclic subgroups ▪ Starting from a point its associated cyclic subgroup can be explored ▪ If the subgroup has order , then = 0 e.g. y2=x3−7x+10 over F263 ▪ = (3,4) defines a subgroup of order 280 ▪ = 66,233 = 2 ∙ (3,4) subgroup of order 140 ▪ = 251,101 = 14 ∙ (3,4) subgroup of order 20 © 2019 Digital Gold Institute 40/69
41. 0 50 100 150 200 250 0 50 100 150 200 250 y2=x3−7x+10 over F263 © 2019 Digital Gold Institute 20 (19 plus ∞) points subgroup generated by G=(251,101) 41/69
42. Prime Order for Elliptic Curves Over Fp ▪ If the EC group order is a prime we have a cyclic group with no subgroups ▪ Any point is a generator: adding successively, all the points in the group are recovered © 2019 Digital Gold Institute 42/69
43. y2=x3+6x+9 over F263 ▪ Symmetric with respect to = Τ 2 = 131.5 ▪ 269 points: 268 affine points plus ∞ ▪ Even number of affine points: = , 0 is not in the group ▪ Group order = 269 is prime: no subgroups © 2019 Digital Gold Institute 43/69 0 50 100 150 200 250 300 0 50 100 150 200 250 300
44. Bitcoin Curve: Koblitz Curve secp256k1 ▪ SEC: Standards for Efficient Cryptography ▪ p256: number of bits in the prime field ▪ is defined by p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 – 1 p = 2^256 - 2^32 - 997 p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F ▪ The elliptic curve defined over is 2 = 3 + 7 ▪ The generation point G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 ▪ The order of G is prime: n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 © 2019 Digital Gold Institute SECG, SEC 2: Recommended Elliptic Curve Domain Parameters, http://www.secg.org/sec2-v2.pdf https://en.bitcoin.it/wiki/Secp256k1 44/69
45. Homework ▪ 2 = 3 + 2 + 2 over 17 − List all its points − It does not have subgroups, why? ▪ 2 = 3 + 4 + 20 over 29 − List all its points − What is the order of the group with generator (8,10)? Check https://github.com/dginst/btclib/tests/ec.py and/or https://github.com/dginst/bbt/excel/EC*.xlsm © 2019 Digital Gold Institute 45/69
46. Table of Contents 1. Modular Arithmetic 2. Algebra of Sets: Finite Field 3. Elliptic Curves over Real Numbers 4. Elliptic Curve over 5. Asymmetric Cryptography on Elliptic Curves 6. Digital Signature Protocol 7. Elliptic Curve Digital Signature Algorithm © 2019 Digital Gold Institute 46/69
47. Asymmetric Cryptography: Different Families private key → one-way function → public key Different key generation algorithms are based on their own distinguishing one-way function: ▪ Integer factorization (1977), based on the difficulty of factoring large integers (e.g. RSA) ▪ Discrete Logarithm (1976), based on the intractability of the discrete logarithm problem on finite cyclic groups (e.g. Diffie and Hellman) ▪ Elliptic Curve (1985), based on the difficulty of computing the generalized logarithm problem on an elliptic curve (e.g. Bitcoin) © 2019 Digital Gold Institute 47/69
48. Elliptic Curve Public/private Key ▪ A Public Key is one point on the elliptic curve ▪ A private key is the number ∈ [1, − 1] of additive steps from the generator point to arrive at point = ▪ → easy (double and add) → hard (discrete logarithm problem) ▪ In multiplicative notation would be called secret exponent = © 2019 Digital Gold Institute https://en.wikipedia.org/wiki/Elliptic_curve_cryptography 48/69
49. Number of Bitcoin Private Keys ▪ The order of elliptic curves can be determined in polynomial time ▪ secp256k1 has 115 792 089 237 316 195 423 570 985 008 687 907 852 837 564 279 074 904 382 605 163 141 518 161 494 336 ≈ 10⁷⁷ points (i.e. private/public key pairs) ▪ The observable universe contains 10⁸⁰ atoms ▪ Try to find keys with associated bitcoins at https://keys.lol/bitcoin Beware: better not to look for your keys… © 2019 Digital Gold Institute 49/69
50. Break Elliptic Curve Cryptography The best known algorithms to break the EC discrete logarithm problem take steps proportional to 2 where is the number of bits of the key ▪ secp256k1 uses 256bit keys: 2128 steps are needed to break it ▪ An EC computation takes 1 million CPU cycles. A 3GHz CPU is able to process 211.55 EC computations per second ▪ A CPU can break the EC in 2116.45 seconds, or about 291.54 years, i.e. about 3,599,861,590,422,752,583,114,293,248 years ▪ Throwing a million CPUs at the problem would reduce the time by a million, leaving it at 3,599,861,590,422,752,583,114 years, roughly 260,859,535,537 times the age of the universe © 2019 Digital Gold Institute 50/69
51. Key Size At Comparable Security Levels © 2019 Digital Gold Institute Security Levels (bits) Symmetric 80 128 192 256 RSA / DH 1024 3072 7680 15360 ECC 160 256 384 512 51/69
52. Quantum Computing Resistance ▪ Hash functions and symmetric cryptography are resistant to quantum computing (key size doubling is enough). Asymmetric cryptography is not https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm ▪ Real quantum computers are still distant in the future ▪ Quantum computing will impact on the security of financial system and nuclear weapon, not just bitcoin ▪ Quantum resistant cryptography is being developed https://en.wikipedia.org/wiki/Post-quantum_cryptography © 2019 Digital Gold Institute 52/69
53. Table of Contents 1. Modular Arithmetic 2. Algebra of Sets: Finite Field 3. Elliptic Curves over Real Numbers 4. Elliptic Curve over 5. Asymmetric Cryptography on Elliptic Curves 6. Digital Signature Protocol 7. Elliptic Curve Digital Signature Algorithm © 2019 Digital Gold Institute 53/69
54. Digital Signature Protocol ▪ Public-key algorithm + digital signature scheme ▪ Message is only authenticated, not encrypted Source: Pedro Franco, “Understanding Bitcoin”, Wiley © 2019 Digital Gold Institute 54/69
55. Digital Signature Scheme 1. KeyGeneration(entropy) → {q, Q} Usually KeyGeneration(entropy) → q, as q→Q is easy 2. Sign(msg, q) → signature 3. Verify(msg, Q, signature) → True/False ▪ The signed message has not been altered (integrity) ▪ Only someone with the private key q can create a valid signature (authentication) ▪ The signer cannot deny the message signature (non- repudiation) ▪ Everyone can verify using the public key Q © 2019 Digital Gold Institute 55/69
56. Signing the Message Digest ▪ Problem: signature generation/verification is quite slow: message length can be a problem ▪ Solution: sign the hash digest of the message ℎ = ℎℎ , whose length is independent from the message’s size ▪ This can also provides message confidentiality ▪ If the can take only few values (e.g. {tail, head}), it can be concealed using secret salt : sign ℎ = ℎℎ || , later reveal both and © 2019 Digital Gold Institute 56/69
57. Digital Signature Process © 2019 Digital Gold Institute Message Hash Function Message Digest Signature Generation Private Key Public Key Signature Message Hash Function Message Digest Signature Verification Valid/Invalid Signature Generation Signature Verification 57/69
58. Digital Signature Algorithms ▪ RSA, the most widely used ▪ ElGamal signature. It has little use being computationally intensive and having large signature ▪ Schnorr signature: simplest scheme, the best one. Signing and verification are computationally efficient, signature is small. Limited usage because of US Patent 4,995,082 which finally expired in 2008 ▪ Digital Signature Algorithm (DSA), quicker and smaller than RSA, designed to circumvent the Schnorr patent © 2019 Digital Gold Institute 58/69
59. Table of Contents 1. Modular Arithmetic 2. Algebra of Sets: Finite Field 3. Elliptic Curves over Real Numbers 4. Elliptic Curve over 5. Asymmetric Cryptography on Elliptic Curves 6. Digital Signature Protocol 7. Elliptic Curve Digital Signature Algorithm © 2019 Digital Gold Institute 59/69
60. EC DSA: Sign Message 1. Choose a nonce as secret ephemeral key 0 < < 2. = ( , ) = Point symmetry is usually resolved requiring to be odd, low, or quadratic residue; if not ← −. Bitcoin canonical 'low-s' encoding require (step 3) to be low. 1. = mod 2. = ℎ mod = ℎℎ mod 3. = + −1 mod If = 0 or = 0 (extremely unlikely), then restart with a different The signature is (, ). must be secret: else = − −1mod © 2019 Digital Gold Institute 60/69
61. EC DSA: Verify Signature Steps for the verification of (, ): 1. = ℎ mod = ℎℎ mod 2. = −1 mod 3. = mod 4. = mod 5. , = + 6. The signature is valid if = mod Roughly equivalent to: = + Unfortunately, −1 is unavoidable because cannot be recovered from = mod © 2019 Digital Gold Institute 61/69
62. EC DSA: Correctness Proof = mod if = + 1. = + from public key definition 2. = + from signature verification [3] and [4] 3. = + −1 from signature verification [2] 4. = + + −1 from signature generation [5] 5. = © 2019 Digital Gold Institute 62/69
63. Ephemeral Key Used for Signing Reusing for different messages signed by the same = + −1 mod 2 = 2 + −1 mod reveals both and : = Τ − 2 − 2 mod = − −1mod Sony PS3 hack: http://www.bbc.com/news/technology-12116051, Bitcoin Android Wallet 2013 hack: https://bitcoin.org/en/alert/2013-08-11-android Even slight biases in the generation of can reveal , after enough signatures must be a nonce, used only once per private key . Even better: avoid randomness at all and use instead a deterministic for each ℎ with salting (see RFC6979) = ℎℎ || mod © 2019 Digital Gold Institute 63/69
64. EC DSA: Signature Malleability If (, ) is a valid signature, i.e. = mod then also (, − ) is a valid signature − = = + bitcoin canonical 'low-s' encoding solves this issue © 2019 Digital Gold Institute 64/69
65. EC DSA: Public Key Recovery From the signature verification step 3, two implied public keys can be recovered: / = −1 (, / ) − © 2019 Digital Gold Institute 65/69
66. EC DSA: Signature Forgery Attack An attacker can generate a -valid signature for a random message digest ℎ computed from a random signature (, ) 1. Pick , at will 2. = + 3. = mod 4. = −1 mod 5. ℎ = = Anyway, the attacker cannot control the semantics of the preimage message : a signature is relevant only for its , not ℎ © 2019 Digital Gold Institute 66/69
67. Homework ▪ Calculate the Public key(s) from this valid DSA signature: # message m1 and its DSA signature {r, s} msg = "Paolo is afraid of ephemeral random numbers" r = 0xb94483fc4da2d9dd5de1b0999c38ac364c9d60bafe7c5151dade0c1b78cfcbf3 S = 0x894ab8b28fd3400784aba4305b14d5afa5c623a6679ba9683c5ac2799b6edc6e ▪ A second DSA signature is computed in error using the same ephemeral key. Calculate the private key: # another message m2 and its DSA signature {r, s2} msg2 = "and Paolo is right to be afraid" r = 0xb94483fc4da2d9dd5de1b0999c38ac364c9d60bafe7c5151dade0c1b78cfcbf3 s2 = 0x6f721ed1e10c4d41f52f7b5e5c1ed3f5359892695ea8410ccbc0a04038c12756 © 2019 Digital Gold Institute See https://github.com/dginst/btclib/ec.py and https://github.com/dginst/btclib/dsa.py and/or https://colab.research.google.com/drive/1IxL0ecWxAI9lRXYdAXhDdg5BzsCW4MHd and/or see https://github.com/dginst/bbt/py-scripts/dsa_example.py (requires an installed btclib) 67/69
68. Bibliography ▪ Christof Paar and Jan Pelzl, “Understanding Cryptography”, Springer, chapter 8, 9, 10 ▪ Pedro Franco, “Understanding Bitcoin”, Wiley, chapter 5 ▪ Andreas Antonopoulos, “Mastering Bitcoin” 2nd edition, O'Reilly, chapter 4 (https://github.com/bitcoinbook/bitcoinbook) ▪ A. Narayanan et al., “Bitcoin and Cryptocurrencies Technologies”, Princeton, chapter 1 ▪ Standards for Efficient Cryptography (SEC), (http://www.secg.org/) − Elliptic Curve Cryptography, (http://www.secg.org/sec1-v2.pdf) − Recommended Elliptic Curve Domain Parameters (http://www.secg.org/sec2-v2.pdf) ▪ NIST, Digital Signature Standard, (http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf) © 2019 Digital Gold Institute 68/69
69. Takeaways ▪ Elliptic curve multiplication = is the one-way function converting private key → public key − One way is easy because of doble and add − Reverse way is a hard discrete logarithm problem ▪ Digital signatures provide message integrity, authentication, and nonrepudiation ▪ Bitcoin’s transactions are signed using DSA ▪ DSA is malleable, susceptible to signature forgery ▪ Schnorr is technically superior: it has not been used so far because of patent ▪ Never reuse ephemeral key in signature © 2019 Digital Gold Institute 69/69
70. Ferdinando M. Ametrano ferdinando@dgi.io Paolo Mazzocchi paolo@dgi.io www.github.com/dginst www.facebook.com/DigitalGoldInstitute www.twitter.com/DigitalGoldInst www.dgi.org/feed.xml info@dgi.io www.dgi.io www.linkedin.com/company/digital-gold-institute "Scarcity in the Digital Realm"
71. Annex 1. EC Computations 2. Schnorr © 2019 Digital Gold Institute 71/69
72. Double and Add Algorithm def mult(m, Q): if m == 0 or Q.y == 0: # Infinity point in affine coordinates return 1, 0 # return Infinity point if m % 2 == 1: # addition when m is odd return add(Q, mult(m - 1, Q)) else: # doubling when m is even return mult(m//2, add(Q, Q)) Easy… but recursive functions are not optimal… © 2019 Digital Gold Institute 72/69
73. Double and Add Algorithm def mult(m, Q): if m == 0 or Q.y == 0: # Infinity point in affine coordinates return 1, 0 # return Infinity point R = 1, 0 # initialize as infinity point while m > 0: # use binary representation of m if m & 1: # if least significant bit is 1 R = add(R, Q) # then add current Q m = m >> 1 # remove the bit just accounted for Q = add(Q, Q) # double Q for next step return R © 2019 Digital Gold Institute 73/69
74. Annex 1. EC Computations 2. Schnorr © 2019 Digital Gold Institute 74/69
75. Schnorr Identification Protocol ▪ A prover proves to a verifier the knowledge of the discrete logarithm of Q without revealing q ▪ Proof in zero knowledge: the verifier learns nothing about q from the proof (except the fact that the prover knows q) A Zero-Knowledge Proof (ZKP) requires 3 properties: 1. Completeness: the proof convinces a honest verifier 2. Zero-knowledgeness: the proof does not leak information, i.e. verifier can fake transcript 3. Soundness: a proof can only be produced by a prover who knows the private key, i.e. the prover can fake knowledge only with negligible probability © 2019 Digital Gold Institute 75/69
76. ▪ K ▪ Choose random c<|H| ▪ s (aka solution) ▪ K = sG+cQ Zero Knowledge Proof of Discrete Logarithm Prover ▪ Q = qG ▪ Choose random k<|G| ▪ kG = K ▪ c (aka challenge) ▪ s = k-c*q Verifier © 2019 Digital Gold Institute 76/69 kG = K = sG+cQ = sG+cqG = (s+cq)G kG = (s+cq)G k = s+cq
77. ▪ {K, s}; c = hash(K) ▪ K = sG+cQ Non-interactive Proof of Discrete Logarithm Schnorr Identification Protocol Prover ▪ Q = qG ▪ Choose random k<|G| ▪ kG = K ▪ c = hash(K) ▪ s = k-c*q Verifier © 2019 Digital Gold Institute 77/69 kG = K = sG+cQ = sG+cqG = (s+cq)G kG = (s+cq)G k = s+cq
78. ▪ {K, s}; c = hash(K||msg) ▪ K = sG+cQ Non-interactive Proof of Discrete Logarithm Schnorr Signature Algorithm Prover ▪ Q = qG ▪ Choose random k<|G| ▪ kG = K ▪ c = hash(K||msg) ▪ s = k-c*q Verifier © 2019 Digital Gold Institute 78/69 kG = K = sG+cQ = sG+cqG = (s+cq)G kG = (s+cq)G k = s+cq
79. ▪ {K, s}; c = hash(Q||K||msg) ▪ K = sG+cQ Non-interactive Proof of Discrete Logarithm Schnorr Signature Algorithm Prover ▪ Q = qG ▪ Choose random k<|G| ▪ kG = K ▪ c = hash(Q||K||msg) ▪ s = k-c*q Verifier © 2019 Digital Gold Institute 79/69 kG = K = sG+cQ = sG+cqG = (s+cq)G kG = (s+cq)G k = s+cq
80. EC Schnorr SA: Generation 0. ℎ = ℎℎ() 1. Choose a nonce as secret ephemeral key 0 < < 2. = ( , ) = Point symmetry is usually resolved requiring to be odd, low, or quadratic residue; if not ← −. In the bitcoin case must be a quadratic residue 1. = ℎℎ ||||ℎ mod 2. = − mod The ℎ signature is (, ), encodable as , when the simmetry is someway fixed. must be secret: else = − −1 mod © 2019 Digital Gold Institute 80/69
81. EC Schnorr SA: Verification Steps for the verification of ( , ): 1. = ℎℎ ||||ℎ mod 2. The signature is valid if − = © 2019 Digital Gold Institute 81/69
82. EC Schnorr SA: Correctness Proof ▪ = − ▪ − = − ▪ − = − ▪ − = − © 2019 Digital Gold Institute 82/69
83. Schnorr SA Properties ▪ If the discrete logarithm problem is hard, in the random oracle model there is a proof that Schnorr signature cannot be forged ▪ Intuitively, signature forgery attack is impossible because = ℎℎ ||||ℎ mod , differently from DSA where = ℎ = ℎℎ mod ▪ There is no way to malleate the signature, as is fully specified (no y-coordinate ambiguity) ▪ Signature verification does not use modular inverse: fast ▪ Many {, ℎ, ( , )} can be efficiently batch verified at once ▪ Signature verification is linear → additive signature: sum of signatures on the same ℎ is equivalent to single signature with sum of keys ▪ Easier multi-sig and threshold schemes © 2019 Digital Gold Institute 83/69
84. Ephemeral Key Used for Signing For Schnorr too, reusing for different messages signed by the same reveals both and : 1 = − 1 mod 2 = − 2 mod = 1 − 2 2 − 1 −1 mod Even slight biases in the generation of can reveal , after enough signatures must be a nonce, used only once per private key . Even better: avoid randomness at all and use instead a deterministic for each ℎ with salting (see RFC6979) = ℎℎ ||ℎ mod © 2019 Digital Gold Institute 84/69
85. Extra Homework Two Schnorr signatures are computed in error using the same ephemeral key. Calculate the private key: # 32-bytes message h1 and its SSA signature {K.x, s1} h1 = 0x9788fd27b3aafd1bd1591a1158ce2d8bdc37ab4040dddb64e64d17616e69ce2b r = 0x968cc26ddaeadb4a7c573a9f391cf78b955816b0b86a6700ae19a8ae19dc31cf s1 = 0x69c2022c2e1170b9b1ce9d4ccb6271e579800aa4d955ecf7ea183fb620e48322 # another 32-bytes message h2 and its SSA signature {K.x, s2} h2 = 0x7adb91982ec03ef87efcae7f0199aefa231d8855e0bd03319460e58c0bd18049 r = 0x968cc26ddaeadb4a7c573a9f391cf78b955816b0b86a6700ae19a8ae19dc31cf s2 = 0x52d9f94c2538ae4c2ee3fd23e34a3603d10652aef1f2ec5ee4327ec4ea532b6e © 2019 Digital Gold Institute See https://github.com/dginst/btclib/ec.py and https://github.com/dginst/btclib/ssa.py and/or see https://github.com/dginst/bbt/py-scripts/ssa_example.py (requires an installed btclib) 85/69
86. Bibliography ▪ BIP-Schnorr (Bitcoin Schnorr signature standardization) https://github.com/sipa/bips/blob/bip-schnorr/bip- schnorr.mediawiki © 2019 Digital Gold Institute 86/69