Monero 백서

Monero

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 19쪽 중 3쪽

of some of the other points in EC using multiples of itself. For example, some point P ’s subgroup might have order 5 and 8 Notation: The phrase a∈ F means a is some element in the field F. 9 Typically elliptic curve points are converted into projective coordinates src/crypto/ crypto ops builder/ ref10Comm- entedComb- ined/ ge.h prior to curve operations like point addition, in order to avoid performing field inversions for efficiency. [142] CHAPTER 2. BASIC CONCEPTS 14 contain the points (0,P, 2P, 3P, 4P ), each of which is in EC. At 5 P the so-called point-at-infinity appears, which is like the ‘zero’ position on an EC, and has coordinates (0 , 1).10 Conveniently, 5P +P = P . This means the subgroup is cyclic.11 All P in EC generate a cyclic subgroup. If P generates a subgroup whose order is prime, then all the included points (except for the point-at-infinity) generate that same subgroup. In our example, take multiples of point 2 P : 2P, 4P, 6P, 8P, 10P→ 2P, 4P, 1P, 3P, 0 Another example: a subgroup with order 6 (0 ,P, 2P, 3P, 4P, 5P ). Multiples of point 2 P : 2P, 4P, 6P, 8P, 10P, 12P→ 2P, 4P, 0, 2P, 4P, 0 Here 2P has order 3. Since 6 is not prime, not all of its member points recreate the original subgroup. Each EC has an order N equal to the total number of points in the curve (including the point- at-infinity), and the orders of all subgroups generated by points are divisors of N (by Lagrange’s theorem). We can imagine a set of all EC points {0,P 1,...,P N−1}. If N isn’t prime, some points will make subgroups with orders equal to divisors of N. To find the order, u, of any given point P ’s subgroup: 1. Find N (e.g. use Schoof’s algorithm ). 2. Find all the divisors of N. 3. For every divisor n of N, compute nP . 4. The smallest n such that nP = 0 is the order u of the subgroup. ECs ge: group element selected for cryptography typically have N = hl, where l is some sufficiently large (such as 160 bits) prime number and h is the so-called cofactor which could be as small as 1 or 2. 12 One point in the subgroup of size l is usually selected to be the generator G as a convention. For every other point P in that subgroup there exists an integer 0 <n ≤l satisfying P =nG. Let’s expand our understanding. Say there is a point P′ with order N, where N = hl. Any other point Pi can be found with some integer ni such that Pi =niP′. If P1 =n1P′ has order l, any P2 = n2P′ with order l must be in the same subgroup as P1 because lP1 = 0 = lP2, and if l(n1P′)≡l(n2P′)≡NP′ = 0, then n1 &n2 must both be multiples of h. Since N =hl, there are only l multiples of h, implying only one subgroup of size l is possible. 10 It turns out elliptic curves have abelian group structure under the addition operation described, since their point-at-infinity’s are identity elements. A concise definition of this notion can be found under https://brilliant. org/wiki/abelian-group/. 11 Cyclic subgroup means, for P ’s subgroup with order u, and with any integer n, nP = [n (mod u)]P . We can imagine ourselves standing on a point on a globe some distance from a ‘zero’th position, and each step we take moves us that distance. After a while, we will wind up back where we started, although it may take many revolutions before we land exactly on the original spot again. The number of steps it takes to land on the exact same spot is the ‘order’ of the ‘stepping group’, and all our footprints are unique points in that group. We recommend applying this concept to other ideas discussed here. 12 EC with small cofactors allow relatively faster point addition, etc. [38]. CHAPTER 2. BASIC CONCEPTS 15 Put simply, the subgroup formed by multiples of ( hP′) always contains P1 and P2. Furthermore, h(n′P′) = 0 when n′ is a multiple of l, and there are only h such variations of n′ (mod N) (including the point at infinity for n′ = hl) because when n′ = hl it cycles back to 0: hlP′ = 0. So, there are only h points P in EC where hP will equal 0. A similar argument could be applied to any subgroup of size u. Any two points P1 and P2 with order u are in the same subgroup, which is composed of multiples of ( N/u)P′. With this new understanding it is clear we can use the following algorithm to find (non-point-at- infinity) points in the subgroup of order l: 1. Find N of the elliptic curve EC, choose subgroup order l, compute h =N/l. 2. Choose a random point P′ in EC. 3. Compute P =hP′. 4. If P = 0 return to step 2, else P is in the subgroup of order l. Calculating sc: scalarthe scalar product between any integern and any pointP ,nP , is not difficult, whereas finding n such that P1 = nP2 is thought to be computationally hard. By analogy to modular arithmetic, this is often called the discrete logarithm problem (DLP). Scalar multiplication can be seen as a one-way function, which paves the way for using elliptic curves for cryptography. 13 The scalar product nP is equivalent to (((P +P ) + (P +P ))... ). Though not always the most efficient approach, we can use double-and-add like in Section 2.2.1. To get the sum R = nP , remember we use the + point operation discussed in Section 2.3.1. 1. Define nscalar→nbinary; A = [nbinary]; R = 0, the point-at-infinity; S =P 2. Iterate through: i = (0,...,A size− 1) (a) If A[i] == 1, then R += S. (b) Compute S += S. 3. Use the final R as result. Note that EC scalars for points in the subgroup of size l (which we will be using henceforth) are members of the finite field Fl. This means arithmetic between scalars is mod l. 13 No known equation or algorithm can efficiently (based on available technology) solve forn inP1 =nP2, meaning it would take many many years to unravel just one scalar product. CHAPTER 2. BASIC CONCEPTS 16 2.3.2 Public key cryptography with elliptic curves Public key cryptography algorithms can be devised in a way analogous to modular arithmetic. Let k be a randomly selected number satisfying 0 < k < l, and call it a private key.14 Calculate the corresponding public key K (an EC point) with the scalar product kG =K. Due to the discrete logarithm problem (DLP) we cannot easily deduce k from K alone. This property allows us to use the values ( k,K ) in standard public key cryptography algorithms. 2.3.3 Diffie-Hellman key exchange with elliptic curves A basic Diffie-Hellman [52] exchange of a shared secret between Alice and Bob could take place in the following manner: 1. Alice and Bob generate their own private/public keys ( kA,KA) and (kB,KB). Both publish or exchange their public keys, and keep the private keys for themselves. 2. Clearly, it holds that S =kAKB =kAkBG =kBkAG =kBKA Alice could privately calculate S = kAKB, and Bob S = kBKA, allowing them to use this single value as a shared secret. For example, if Alice has a message m to send Bob, she could hash the shared secret h = H(S), compute x = m +h, and send x to Bob. Bob computes h′ = H(S), calculates m =x−h′, and learns m. An external observer would not be able to easily calculate the shared secret due to the ‘Diffie- Hellman Problem’ (DHP), which says finding S fromKA andKB is very difficult. Also, the DLP prevents them from finding kA or kB.15 2.3.4 Schnorr signatures and the Fiat-Shamir transform In 1989 Claus-Peter Schnorr published a now-famous interactive authentication protocol [121], generalized by Maurer in 2009 [87], that allowed someone to prove they know the private key k of a given public key K without revealing any information about it [89]. It goes something like this: 1. The prover generates a random integer α ∈R Zl,16 computes αG, and sends αG to the verifier. 14 The private key is sometimes known as a secret key. This lets us abbreviate: pk = public key, sk = secret key. 15 The DHP is thought to be of at least similar difficulty to the DLP, although it has not been proven. [31] 16 Notation: The R in α∈R Zl means α is randomly selected from {1, 2, 3,...,l − 1}. src/crypto/ crypto.cpp random32 unbiased() In other words, Zl is all integers (mod l). We exclude ‘l’ since the point-at-infinity is not useful here. CHAPTER 2. BASIC CONCEPTS 17 2. The verifier generates a random challenge c∈R Zl and sends c to the prover. 3. The prover computes the responser =α +c∗k and sends r to the verifier. 4. The verifier computes R =rG and R′ =αG +c∗K, and checks R ?=R′. The verifier can compute R′ = αG +c∗K before the prover, so providing c is like saying, “I challenge you to respond with the discrete logarithm of R′.” A challenge the prover can only overcome by knowing k (except with negligible probability). Ifα was chosen randomly by the prover thenr is randomly distributed [122] and k is information- theoretically secure within r (it can still be found by solving the DLP for K orαG).17 However, if the prover reusesα to prove his knowledge ofk, anyone who knows both challenges inr =α+c∗k and r′ =α +c′∗k can compute k (two equations, two unknowns).18 k = r−r′ c−c′ If the prover knew c from the beginning (e.g. if the verifier secretly gave it to her), she could generate a random response r and computeαG =rG−cK. When she later sends r to the verifier, she ‘proves’ knowledge of k without ever having to know it. Someone observing the transcript of events between prover and verifier would be none the wiser. The scheme is not publicly verifiable. [89] In his role as challenger, the verifier spits out a random number after receiving αG, making him equivalent to a random function. Random functions, such as hash functions, are known as random oracles because computing one is like requesting a random number from someone [89]. 19 Using a hash function, instead of the verifier, to generate challenges is known as a Fiat-Shamir transform [60], because it makes an interactive proof non-interactive and publicly verifiable [89].20,21 Non-interactive proof 1. Generate random number α∈R Zl, and compute αG. 17 A cryptosystem with information-theoretic security is one where even an adversary with infinite computing power could not break it, because they simply wouldn’t have enough information. 18 If the prover is a computer, you could imagine someone ‘cloning’/copying the computer after it generates α, then presenting each copy with a different challenge. 19 More generally, “[i]n cryptography... an oracle is any system which can give some extra information on a system, which otherwise would not be available.”[3] 20 The output of a cryptographic hash function H is uniformly distributed across the range of possible outputs. That is to say, for some inputA,H(A)∈DR SH where SH is the set of possible outputs fromH. We use∈DR to indicate the function is deterministically random. H(A) produces the same thing every time, but its output is equivalent to a random number. 21 Note that non-interactive Schnorr-like proofs (and signatures) require either use of a fixed generator G, or inclusion of the generator in the challenge hash. Including it that way is known as key prefixing, which we discuss a bit more later (Sections 3.4 and 9.2.3). CHAPTER 2. BASIC CONCEPTS 18 2. Calculate the challenge using a cryptographically secure hash function, c =H([αG]). 3. Define the response r =α +c∗k. 4. Publish the proof pair ( αG,r ). Verification 1. Calculate the challenge: c′ =H([αG]). 2. Compute R =rG and R′ =αG +c′∗K. 3. If R =R′ then the prover must know k (except with negligible probability). Why it works rG = (α +c∗k)G = (αG) + (c∗kG) =αG +c∗K R =R′ An important part of any proof/signature scheme is the resources required to verify them. This includes space to store proofs, and time spent verifying. In this scheme we store one EC point and one integer, and need to know the public key - another EC point. Since hash functions are comparatively fast to compute, keep in mind that verification time is mostly a function of elliptic curve operations src/ringct/ rctOps.cpp . 2.3.5 Signing messages Typically, a cryptographic signature is performed on a cryptographic hash of a message rather than the message itself, which facilitates signing messages of varying size. However, in this report we will loosely use the term ‘message’, and its symbol m, to refer to the message properly speaking and/or its hash value, unless specified. Signing messages is a staple of Internet security that lets a message’s recipient be confident its content is as intended by the signer. One common signature scheme is called ECDSA. See [72], ANSI X9.62, and [69]. The signature scheme we present here is an alternative formulation of the transformed Schnorr proof from before. Thinking of signatures in this way prepares us for exploring ring signatures in the next chapter. CHAPTER 2. BASIC CONCEPTS 19 Signature Assume Alice has the private/public key pair (kA,KA). To unequivocally sign an arbitrary message m, she could execute the following steps: 1. Generate random number α∈R Zl, and compute αG. 2. Calculate the challenge using a cryptographically secure hash function, c =H(m, [αG]). 3. Define the response r such that α =r +c∗kA. In other words, r =α−c∗kA. 4. Publish the signature ( c,r ). Verification Any third party who knows the EC domain parameters (specifying which elliptic curve was used), the signature ( c,r ) and the signing method, m and the hash function, and KA can verify the signature: 1. Calculate the challenge: c′ =H(m, [rG +c∗KA]). 2. If c =c′ then the signature passes. In this signature scheme we store two scalars, and need one public EC key. Why it works This stems from the fact that rG = (α−c∗kA)G =αG−c∗KA αG =rG +c∗KA Hn(m, [αG]) =Hn(m, [rG +c∗KA]) c =c′ Therefore the owner of kA (Alice) created (c,r ) for m: she signed the message. The probability someone else, a forger withoutkA, could have made (c,r ) is negligible, so a verifier can be confident the message was not tampered with. CHAPTER 2. BASIC CONCEPTS 20 2.4 Curve Ed25519 Monero uses a particular Twisted Edwards elliptic curve for cryptographic operations, Ed25519, the birational equivalent22 of the Montgomery curve Curve25519. Both Curve25519 and Ed25519 were released by Bernstein et al. [38, 39, 40]. 23 The src/crypto/ crypto ops builder/ ref10Comm- entedComb- ined/ ge.h curve is defined over the prime field F2255−19 (i.e. q = 2255− 19) by means of the following equation: −x2 +y2 = 1− 121665121666x2y2 This curve addresses many concerns raised by the cryptography community. 24 It is well known that NIST25 standard algorithms have issues. For example, it has recently become clear the NIST standard random number generation algorithm PNRG (the version based on elliptic curves) is flawed and contains a potential backdoor [68]. Seen from a broader perspective, standardization authorities like NIST lead to a cryptographic monoculture, introducing a point of centralization. A great example of this was illustrated when the NSA used its influence over NIST to weaken an international cryptographic standard [18]. Curve Ed25519 is not subject to any patents (see [79] for a discussion on this subject), and the team behind it has developed src/crypto/ crypto ops builder/ and adapted basic cryptographic algorithms with efficiency in mind [40]. Twisted Edwards curves have order expressible as N = 2cl, where l is a prime number and c a positive integer. In the case of curve Ed25519, its order is a 76 digit number ( l is 253 bits): 26 23· 7237005577332262213973186563042994240857116359379907606001950938285454250989 src/ringct/ rctOps.h curve- Order()2.4.1 Binary representation Elements of F2255−19 are encoded as 256-bit integers, so they can be represented using 32 bytes. Since each element only requires 255 bits, the most significant bit is always zero. Consequently, any point in Ed25519 could be expressed using 64 bytes. By applying point com- pression techniques, described here below, however, it is possible to reduce this amount by half, to 32 bytes. 22 Without giving further details, birational equivalence can be thought of as an isomorphism expressible using rational terms. 23 Dr. Bernstein also developed an encryption scheme known as ChaCha [37, 100], which the primary Monero implementation uses to encrypt src/wallet/ ringdb.cpp certain sensitive information related to users’ wallets. 24 Even if a curve appears to have no cryptographic security problems, it’s possible the person/organization that created it knows a secret issue that only crops up in very rare curves. Such a person may have to randomly generate many curves in order to find one with a hidden weakness and no known weaknesses. If reasonable explanations are required for curve parameters, then it becomes even more difficult to find weak curves that will be accepted by the cryptographic community. Curve Ed25519 is known as a ‘fully rigid’ curve, which means its generation process was fully explained. [120] 25 National Institute of Standards and Technology, https://www.nist.gov/ 26 This means private EC keys in Ed25519 are 253 bits. CHAPTER 2. BASIC CONCEPTS 21 2.4.2 Point compression The Ed25519 curve has the property that its points can be easily compressed, so that representing a point will consume only the space of one coordinate. We will not delve into the mathematics necessary to justify this, but we can give a brief insight into how it works [74]. Point compression for the Ed25519 curve was first described in [39], while the concept was first introduced in [94]. This point compression scheme follows from a transformation of the Twisted Edwards curve equa- tion (assuminga =−1, which is true for Monero): x2 = (y2−1)/(dy2 +1), 27 which indicates there are two possible x values (+ or−) for each y. Field elements x and y are calculated (mod q), so there are no actual negative values. However, taking (mod q) of –x will change the value between odd and even since q is odd. For example: 3 (mod 5) = 3, −3 (mod 5) = 2. In other words, the field elements x and –x have different odd/even assignments. If we have a curve point and know its x is even, but given its y value the transformed curve equation outputs an odd number, then we know negating that number will give us the right x. One bit can convey this information, and conveniently the y coordinate has an extra bit. Assume we want to compress a point (x,y ). Encoding We src/crypto/ crypto ops builder/ ref10Comm- entedComb- ined/ ge to- bytes.c set the most significant bit of y to 0 if x is even, and 1 if it is odd. The resulting valuey′ will represent the curve point. Decoding 1. Retrieve ge from- bytes.c the compressed point y′, then copy its most significant bit to the parity bit b before setting it to 0. Now it is the original y again. 2. Let u =y2− 1 (mod q) and v =dy2 + 1 (mod q). This means x2 =u/v (mod q). 3. Compute 28 z =uv3(uv7)(q−5)/8 (mod q). (a) If vz 2 =u (mod q) then x′ =z. (b) If vz 2 =−u (mod q) then calculate x′ =z∗ 2(q−1)/4 (mod q). 4. Using the parity bit b from the first step, if b⁄= the least significant bit of x′ then x =−x′ (mod q), otherwise x =x′. 5. Return the decompressed point ( x,y ). Implementations of Ed25519 (such as Monero) typically use the generatorG = (x, 4/5) [39], where x is the ‘even’, or b = 0, variant based on point decompression of y = 4/5 (mod q). 27 Here d =− 121665121666.28 Since q = 2255− 19≡ 5 (mod 8), (q− 5)/8 and (q− 1)/4 are integers. CHAPTER 2. BASIC CONCEPTS 22 2.4.3 EdDSA signature algorithm Bernstein and his team have developed a number of basic algorithms based on curve Ed25519. 29 For illustration purposes we will describe a highly optimized and secure alternative to the ECDSA signature scheme which, according to the authors, allows producing over 100 000 signatures per second using a commodity Intel Xeon processor [39]. The algorithm can also be found described in Internet RFC8032 [75]. Note this is a very Schnorr-like signature scheme. Among other things, instead of generating random integers every time, it uses a hash value derived from the private key of the signer and the message itself. This circumvents security flaws related to the implementation of random number generators. Also, another goal of the algorithm is to avoid accessing secret or unpredictable memory locations to prevent so-
프로젝트로 돌아가기