-
yanmaani
Is there any primer on what you can do with curves? For example, in Bitcoin I know you can add two public keys together.
-
yanmaani
I've always thought of these things as opaque blobs. Is there some list of primitives out there, e.g. "you have public key K and private key k, you can do X, Y, and Z with it"
-
moneromooo
You can add too with monero's curve. That's what multisig address creation does.
-
moneromooo
src/ringct/rctOps.h has a few useful ops on keys.
-
moneromooo
It uses the same type for scalars and points though.
-
moneromooo
But scalars are lowercase and points are uppercase.
-
yanmaani
What is a point? 2 scalars?
-
UkoeHB_
yanmaani: I discuss it in chapter 2
web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf; there are a lot of resources out there if you search, although none are ideal (even ztm)
-
yanmaani
What is a scalar? like a private/public key?
-
moneromooo
Here, scalar === secret key, point == public key
-
yanmaani
So what can you do with this? Anything you can do with a public key, you can do with a private key also?
-
moneromooo
Doubt it, but I'm not a crypto geek so I'll let you peruse ECC primers.
-
yanmaani
what's the difference to normal addition?
-
yanmaani
If I control key x, and I want to hijack key Y
-
yanmaani
how come I can't compute x + (Y-X) = y?
-
yanmaani
Is the result of an addition unpredictable, like when you take the public/private key and add somethign to it? Is addition to public key fundamentally different from to private key?
-
moneromooo
Addition for public keys is more like multiplication.
-
moneromooo
Scalars is really modular addition.
-
yanmaani
So what's multiplication of public keys then? UB?
-
moneromooo
I'm likely just confusing things so I'll shut up now ^_^
-
yanmaani
UkoeHB_: This is helpful but some of the stuff seems a bit handwavey. It has version numbers, so is there anywhere you can send in patches?
-
yanmaani
specifically, 2.2.4: "Now we have a way to do modular subtraction.". If it's for any operation, then why can't you just do ((A mod 9) - (B mod 9)) mod 9?
-
yanmaani
should be "a commutative operation °," right?
-
yanmaani
OK, so "addition" of points is just arbitrary, and from that the rest of arithmetic follows.
-
yanmaani
Because there's nothing like defining addition as repeated succession
-
yanmaani
It would be helpful to have some indication of what's logical or a definition (e.g. how to go from addition to multiplication, or what a finite field is) and what's just arbitrary (e.g. the formulae for the curves, point multiplication)
-
jtgrassie
yanmaani: I suggest you read some primer on elliptic curve cryptography. This is a good start:
blog.cloudflare.com/a-relatively-ea…imer-on-elliptic-curve-cryptography
-
yanmaani
in 2.3.1 just before 1st equation, (a,b) are constant params across the curve, whereas (x, y) are what's being iterated over?
-
yanmaani
jtgrassie: thanks
-
jtgrassie
np. the chapter you reference is a little handwaivy but it's also trying to condense a lot of information in a short space!
-
jtgrassie
(a,b) are curve constants
-
yanmaani
Oh yeah, I don't mind the handwaves, but it'd be nice if they were clearly marked
-
jtgrassie
(x,y) are any x,y that satisfy the curve equation (so are a point on the curve)
-
yanmaani
"this is just arbitrary, no need to think about it"
-
jtgrassie
yeah, that's why I sent you the link. if your starting out, some fundamentals are useful.
-
UkoeHB_
well you could define a new subtraction operation, but (a - b) = (a + (-b)) uses fewer fundamental ops
-
yanmaani
UkoeHB_: Define? Isn't a-b already defined by maths? (a-b) + b = a
-
UkoeHB_
not modular subtraction
-
UkoeHB_
section 2.2.0 we define addition and negation
-
UkoeHB_
2.2.0 and 2.2.1*
-
UkoeHB_
there are various ways to do it, the chapter just shows what made sense to me at the time, so yes a bit handwavy
-
yanmaani
Well yes, but isn't it a premature optimization? Is (a + -b) mod n == ((a mod n) - (b mod n)) mod n?
-
UkoeHB_
what if you have an unsigned int?
-
UkoeHB_
I think that's why I avoided real negatives
-
UkoeHB_
since all crypto uses unsigned integrals
-
yanmaani
If I have an unsigned int, subtraction works fine
-
yanmaani
as if it's two's complement
-
UkoeHB_
overflow is the issue
-
UkoeHB_
we also have the finite field issue, where elliptic curve scalars are in the finite field q, which is positive integers [0,q-1]
-
UkoeHB_
so you can't 'create' a negative number from an op, which subtraction would do; you can only 'negate' a number
-
yanmaani
doesn't negating a number create a negative number? (which is immediately turned positive by taking q-1 - n)?
-
yanmaani
just so, subtraction "temporarily creates" a neg number which then overflows back
-
UkoeHB_
I believe it's more like 'a + -a = 0', rather than creating a negative number you are creating its negation
-
yanmaani
a + -a - 1 = q-1?
-
UkoeHB_
that's right
-
yanmaani
(is there a repo for you book where you can send in PRs?)
-
yanmaani
uh, so why the -a phrasing then? Won't a-b (for b>a) overflow just the same?
-
UkoeHB_
-
yanmaani
thanks
-
UkoeHB_
however, conceptually there is no 'negative number', negation isn't the same thing
-
yanmaani
oh jesus, github are starting to do the cookie nonsense now
-
UkoeHB_
-a means 'the negation of a'
-
yanmaani
I think of it like a "negative" number in two's complement cast to uint
-
yanmaani
so -1 == UINT_MAX - 1
-
UkoeHB_
yes, however it should be constrained to the field order q; it can get a bit messy with overflow...
-
yanmaani
What do you mean 'can get messy'? Don't you just do mod n on each op, conceptually?
-
yanmaani
like doing addition or whatever with uint's
-
yanmaani
(with multiplication needing special care because not defined)
-
moneromooo
-1 is UINT_MAX.
-
UkoeHB_
yes mod n; it's conceptually analogous to uint overflow
-
UkoeHB_
I mean messy if you try to subtract field scalars when n < UINT_MAX
-
UkoeHB_
since (-1 mod n) != (n - 1)
-
UkoeHB_
so it's much simpler to just use the binary+ and unary- ops
-
yanmaani
UkoeHB_: Wait, what? Isn't -1 mod n == n - 1?
-
UkoeHB_
not if you are allowing uint overflow
-
yanmaani
Oh, yeah, if you have the two at the same time
-
yanmaani
then, sure, but that's an impl detail
-
yanmaani
Would you accept a PR changing the (a + -b) to a separate equation, something like "this can be optimized as ..."?
-
UkoeHB_
it's not really an optimization, I am basically defining subtraction as adding an element's negation (or inverse); see
uotechnology.edu.iq/dep-eee/lecture…nication/Information%20theory/8.pdf for example
-
yanmaani
Does your definition change things from the normal definition you have in normal maths, though?
-
yanmaani
like is there some edge case further down the line where "my" mental model causes problems?
-
UkoeHB_
well we have the same issue in curve point arithmetic, where only addition and negation are defined
-
UkoeHB_
and there it's more rigorous
-
yanmaani
So what does P + -P get you when working with points?
-
UkoeHB_
it's P + inversion(P)
-
UkoeHB_
page 13
-
yanmaani
Is modular multiplicative inverse defined for points?
-
UkoeHB_
no
-
UkoeHB_
it's an inversion of one coordinate
-
UkoeHB_
you can't multiply points together
-
yanmaani
So P1 + inversion(P1) = (0, new_y)?
-
UkoeHB_
well, check out page 13 there is a lot of stuff going on
-
yanmaani
oh right, because you can't "subtract 1"
-
yanmaani
yeah I overlooked that bit
-
yanmaani
but in x3 you get x1y2 + y1x2 = xy2 + y1x = xy2 + xy1 = xy + x(-y) = x0 = 0, right?
-
yanmaani
at the end of p13, is the order u intrinsic or chosen?
-
UkoeHB_
for P - P? yes the point at infinite has coordinate (0, 1); page 14 :p
-
yanmaani
oh, the other term comes to 1
-
UkoeHB_
it is intrinsic
-
yanmaani
oh, intrinsic for the curve?
-
UkoeHB_
intrinsic for the point on the curve; every point belongs to one or more subgroups
-
yanmaani
Oh, so the EC having order N is something different?
-
UkoeHB_
all points are members of the group with order N, and if N is non-prime some points also belong to subgroups with orders that are divisors of N
-
yanmaani
If EC doesn't have multiplication on points, how can a point have "multiples of itself"?
-
UkoeHB_
5*P is a multiple of P
-
yanmaani
Oh, so it's not like a certain point P has a given order? It's more like a set of orders?
-
yanmaani
so like "P has order 10, 5, and 2"
-
UkoeHB_
I suppose that's correct; typically you only talk about a point in the context of its smallest subgroup
-
UkoeHB_
since by implication it's also in the larger subgroups
-
yanmaani
I think the language there is a little confusing. It might make more sense to describe the pattern first (P*N = 0, 0*P = P), and then describe subgroups, and point out how they can repeat given common factors.
-
yanmaani
But for cryptography, N is prime => order = N always?
-
UkoeHB_
it definitely could be better; that section is probably the most difficult in the entire book
-
UkoeHB_
both to understand and explain succinctly
-
UkoeHB_
usually N is not prime (curves selected for use in cryptography don't have prime N), although they do have a large prime factor (page 14)
-
yanmaani
yeah but if N = hl, and l = 1, then h is prime?
-
UkoeHB_
not sure why you would choose l = 1
-
UkoeHB_
do you mean h = 1? l is always prime by convention afaik
-
yanmaani
h = 1, yes
-
UkoeHB_
well, convention and also you need a big prime group for EC crypto
-
yanmaani
So could you write the phrase "If $P_1 = n_1*P$ has order l' as 'If P_1 has order l'?
-
yanmaani
Like, the phrasing of pg. 14 gives rise to a mental model like "if (order(P) == X)", whereas it's more like "if (X ∈ order(P))", I found this confusing
-
UkoeHB_
saying 'P has order N' is meant to mean 'N' is the smallest subgroup of which it's a member
-
UkoeHB_
put another way, N*P is the soonest you will cycle back to 0
-
UkoeHB_
I may be making a mistake here actually
-
UkoeHB_
yeah, it's best to say a point only has one order, even if it is a member of 'multiple' subgroups; the order of a point is the size of the subgroup creatable out of multiples of itself
-
sarang
Group element order is defined as the smallest multiple-to- identity if this number is finite
-
kenshamir[m]
yanmaani: there are curve points with this property such as those defined by secp256r1. The math does change however, because you need a different curve representation called a weierstrass curve, unlike the one you have been looking at currently called a Twisted Edwards curve.
-
kenshamir[m]
I believe there is a formula which states that h must be a multiple of 4, for it to be represented as an Edwards curve, so if h=1, then you cannot represent it as an Edwards curve
-
kenshamir[m]
For group order, checking out Lagrange theorem would probably be the most helpful
-
yanmaani
If you publish nG somewhere, is it impossible to calculate n = (nG)/G?
-
UkoeHB_
Try it with the curve equation :) seems pretty tough
-
yanmaani
Is it possible to do multisig in a non-interactive fashion, like in Bitcoin?
-
UkoeHB_
if there is, I have not heard of it
-
needmoney90
-
yanmaani
Is the shared secret rG used for anything else but the one-time addresses?
-
yanmaani
Put differently, could you pre-compute K_v = r*K_v and then set r = 1?
-
UkoeHB_
it's used with output commitments too
-
UkoeHB_
ch 5