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-프로젝트로 돌아가기