Hi James,
It seems like are a few misunderstandings here. Let me start with some background. It is easier to explain what's going on if we abstract a bit: let's start by defining a
group. A group is simply a set with an operation (called +), some set element 0 such that 0 + x = x + 0 = x for all x in the group, and a unary operation - such that x + (-x) = 0 for all x in the group. So, the integers with addition are a group (as are the reals, rationals, etc), the reals with multiplication are a group, the set of invertible nxn matrices are a group under matrix multiplication, etc.
An important group in cryptography is an
elliptic curve group, which is a group whose elements are pairs (x, y) of numbers which satisfy an elliptic curve equation. Addition is defined in a bit of a funny way, but there is a
Wikipedia page on it that is interesting.
What's important about these groups for cryptography is the following: given a group element G, you can "multiply" by an integer n by adding G to itself n times. (If n is negative, add -G to itself -n times.) It turns out that if you fix an element G in some group, then take all the elements {nG} for integers n, this set is itself a group such that (nG) + (mG) = (n + m)G. It's a true statement that given any nonzero elements in this group, say P and Q, there is always some number n such that P = nQ. But for elliptic curve group, there is the so-called "discrete logarithm assumption" which says that actually calculating n is very hard. There is also the "Diffie-Hellman" assumption which says that given nG, mG in the group, it is hard to calculate nmG. (Of course, if you know n or m, it's easy to calculate. This is why the "shared secret" scheme you described is efficiently computable by the participants, and the Diffie-Hellman assumption is why it is a secret.)
So...everywhere you say Curve25519(n, G), you really mean nG, where G is some element in the elliptic curve group defined by djb's curve25519 curve. Where you say Curve25519(A, B) where both A and B are elements .... I don't know what you mean. Can you clarify what you are actually computing here? It is possible you are interpreting curvepoints as numbers without realize it, in which case you should use a better programming language that has a type system. (In particular, C is has a very weak type system and djb's code uses char* for
everything, which is an asinine thing to do in public code with subtle operation. But possibly it compiles to faster code than it would if he'd used wrapper structs..) It is possible to convert a group element to a number, e.g. by choosing a binary encoding, hashing this, and interpreting the hash as a number.
Now, shared secrets are not really useful for building multisignature schemes. They let you build 1-of-N signatures (every party who has the secret is able to sign) but nothing stronger. The reason is that any party who knows the shared secret is able to use this to sign arbitrary messages. As an example of an actual multisig scheme, I will show how to construct a N-of-N multisig Schnorr signature. The semantics will be that as long as
all parties agree to sign a specific message, they are able to form a signature on that message. However, no individual will see enough secret material to form signatures or her own, or even with the cooperation of (fewer than N) other members.
djb's ed25519 signature scheme is based off the standard Schnorr signature, but has some changes to allow efficient batch validation. I don't recall what these changes are (and don't have the paper with me on the bus that I'm typing this from), so I'm not sure if this is directly applicable .... but it is illustrative in any case. So here it is:
Suppose we have a public key P, and let G be a generator of some elliptic curve group, and let H be a hash function. A standard Schnorr signature is a pair (s, e) of numbers which satisfy the following relation: if R = eP + sG then e = H(m || R). It is possible to create such a signature if you know x such that xG = P (so x is the secret key here, and the "discrete logarithm assumption" above is why it is secret even though P is public), by the following mechanism: choose random secret k and compute R = kG; then set e = H(m||R) and s = k - xe. The signature is (s, e). Given some very strong assumptions on the hash function (that it is a opaque mystical source of uniformly random numbers except that it returns the same output when given same input), we can prove that any algorithm which forges Schnorr signatures can be extended to extract the secret key. So given such a hash function, forging Schnorr signatures is as hard as the discrete log problem.
Now, the question is: how can we make a 2-of-2 signature? One idea, as you suggested, is to use a shared secret: users have secret values x and y and form a private key from (a hash of) xyG. The problem with this is as mentioned: both parties knows the whole secret, so they can both form signatures on their own. So this is really a 1-of-2 multisig scheme. To get 2-of-2, we need to be a bit more clever. Here is a protocol:
0. Suppose we have two keypairs (x, xG) and (y, yG) belonging to parties A and B. We will show how to construct a signature with the "2-of-2" key (x + y, (x + y)G).
1. Both parties choose secret random numbers. Call A's secret α and B's secret β. A sends αG to B, and B sends βG to A. Now both parties can compute R = αG + βG = (α + β)G, and they compute e = H(m||R).
2. A computes s' = α - xe and B computes s'' = β - ye, and they send these to each other. Then both compute s = s' + s''.
Now (s, e) is a signature of m on public key (x + y)G, which required both parties' cooperation to form, but neither party gained enough information to produce such a signature alone.
It's a worthwhile exercise to (a) verify that the standard Schnorr signature k - xe actually satisfies the relation (e = H(m||R) where R = sG + eP) that I claimed it did, and (b) so does the 2-of-2 version.
This isn't really an answer to your question, but I hope it sheds some light on things.
Andrew
yes! this makes it a lot clearer, but still struggling to map all these operations to the C code.
I was treating the curve25519 function as a blackbox that I thought was doing a field operation, but it was doing a lot of things with some bytes being polynomials, encoded or not and others being numbers:
curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
limb bp[5], x[5], z[5], zmone[5];
uint8_t e[32];
int i;
for (i = 0;i < 32;++i) e[i] = secret[i];
e[0] &= 248;
e[31] &= 127;
e[31] |= 64;
fexpand(bp, basepoint);
cmult(x, z, e, bp);
crecip(zmone, z);
fmul(z, x, zmone);
fcontract(mypublic, z);
}
It seems curve25519(A,B) makes no sense and it can only be used for nG
So to code your protocol:
0. Suppose we have two keypairs (x, xG) and (y, yG) belonging to parties A and B. We will show how to construct a signature with the "2-of-2" key (x + y, (x + y)G).
1. Both parties choose secret random numbers. Call A's secret α and B's secret β. A sends αG to B, and B sends βG to A.
I believe G is represented by {9}
(x, xG) and (y, yG) are the standard curve25519(x,G) and curve25519(y,G) keypairs
I think I need to use the cmult function to make αG and βG:
/* Calculates nQ where Q is the x-coordinate of a point on the curve
*
* resultx/resultz: the x coordinate of the resulting curve point (short form)
* n: a little endian, 32-byte number
* q: a point of the curve (short form)
*/
static void cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q)
A would generate a random 256 bits -> α and sends cmult(x,z, α,G) to B
B generates his random 256 bits -> β and sends cmult(x,z, β,G) to A
now both A and B can calculate (αG + βG)
Now both parties can compute R = αG + βG = (α + β)G,
, but I am not sure how exactly to do this, there is a "fmonty" function:
/* Input: Q, Q', Q-Q'
* Output: 2Q, Q+Q'
*
* x2 z3: long form
* x3 z3: long form
* x z: short form, destroyed
* xprime zprime: short form, destroyed
* qmqp: short form, preserved
*/
static void
fmonty(limb *x2, limb *z2, /* output 2Q */
limb *x3, limb *z3, /* output Q + Q' */
limb *x, limb *z, /* input Q */
limb *xprime, limb *zprime, /* input Q' */
const limb *qmqp /* input Q - Q' */)
I think Q can be αG and Q' βG, but not sure how to get the third input (Q-Q') or (αG - βG), looking at the code it looks like it could be simply G {9}?
and they compute e = H(m||R).
I assume H can be sha256 and both A and B can compute R = αG + βG
e = sha256(m || (αG + βG))
and m is the signature, but I am totally confused by the following:
2. A computes s' = α - xe and B computes s'' = β - ye, and they send these to each other. Then both compute s = s' + s''.
The signature is two numbers s and e, but m is the signature and it is inside the hash function.
sha256((s,e) || (αG + βG)) ?? have no idea how to do this.
Assuming somehow e can be calculated, then there is the final question of these addition, mult and subtractions:
A (α - xe) = s' -> B
B (β - ye) = s'' -> A
and the s = s' + s''
Maybe these are normal numbers and normal arithmetic can be used?
I apologize for probably super simply misunderstanding, but at least now I see a lot better the type of thing that is going on.
James
P.S. Thank you very much for a super informative post!
