10

On the last paragraph of page 7 of Monero Research Lab's paper about RingCT, the author makes some statements to the effect that it is possible to pick a random point on the base curve ED25519 that is on the subgroup generated by its base point G, for example by computing H(G) or H(123456*G), and checking somehow that those points do indeed belong to this group; that is, checking that those points are of the form Q = q*G for some unknown q.

Question: How is it possible to check that a random point belongs to the group generated by the base point, and how costly is this process?

  • Interestingly, if an adversary could calculate the discrete log of H relative to G, they could counterfeit Monero without anyone knowing after RingCT is implemented. – PyRulez Oct 28 '16 at 20:10
4

You can check if a point is on the curve by attempting to decode it (it is checked as part of that). In c this is here, but that doesn't make a lot of sense.

In python (ctrl+f "isoncurve", which is called by "decodepoint"), it's laid out pretty succinctly. It doesn't cost much.

Now, I realize this isn't the answer to your question, but I think it might be useful for other readers.

Now, to answer your question: (...why did this get so long?)

After doing some research and playing around with things, I believe there is only one subgroup of curve Ed25519 of size l (2^252 + 27742317777372353535851937790883648493).

There are really two answers:

1. How it is done in practice: take any valid curve point (via the above) and multiply it by 8 (3 doubles). As long as your starting point isn't a member of one of the small subgroups, you will end up with a point in the G subgroup. Now, note that this doesn't actually check whether your point is in the G subgroup, it only returns a point in G subgroup. Since 3 doublings is cheap, and knowing the subgroup of the point you started with isn't very useful, this is the usual method.

2. How to actually check: Multiply your point by l. If the result is the identity point ("0100000000000000000000000000000000000000000000000000000000000000"), your point is in the G subgroup. The reason for this is multiplying a point by its subgroup order (or a multiple since they are inclusive, or 0) always returns the identity element. I think of it as if the starting point is "1", and you are multiplying it by the modular order, meaning of course that you end up at 0.

To try to illustrate this, I made up some stuff:

curve points

Of course the real curve looks nothing like this; that's not the point. Ed25519's l subgroup has a cofactor of 8. That means l * 8 is the total number of points on the curve (57896044618658097711785492504343953926856930875039260848015607506283634007912).

Entering "divisors of 57896044618658097711785492504343953926856930875039260848015607506283634007912" into WolphramAlpha, I get: 1 2 4 8 7237005577332262213973186563042994240857116359379907606001950938285454250989 <- "l" 14474011154664524427946373126085988481714232718759815212003901876570908501978 <- "l" * 2 28948022309329048855892746252171976963428465437519630424007803753141817003956 <- "l" * 4 57896044618658097711785492504343953926856930875039260848015607506283634007912 <- "l" * 8

There is (I believe) one cyclical subgroup for each of these divisors. The above image has 40 "points" listed. The construction logic was something like this:

  1. Small subgroup points (divisors 1-8; all points are listed) are shown as numbers 0-7. 0 denotes the identity element, which is a member of every subgroup.
  2. 32 other points are shown as x,y,z, or G in increasing exclusivity as an example of the large subgroups.
  3. Pipe symbols show what points are in what subgroup.
  4. The list "wraps" around at the end (though it might make more modular sense if 0 was at the end, but whatever).

Remarks:

  1. You can superimpose the small subgroups on top of the large ones, with the corresponding large group having all small points as members.
  2. The points in the small and large subgroups are all members of the next larger subgroup, with a demarcation between 8 and l (the superimposition above).
  3. A "generator point" chosen from any subgroup will only produce points in that subgroup, never points exclusive to a larger one (remember that they are inclusive of smaller subgroups).
  4. For example, choose the first x in the above picture as a generator. Doubling it once gets us a point in the second subgroup (which is also of course in the subgroup). Adding x to that y will get us a point back exclusively in the big group, but if we instead start to double y (choose it as our new generator point), we can never return to an exclusively big group point. So if we choose a generator in subgroup G, we'll never "break out" of that group, as it's the smallest (big one) there is (the only "bad point" in it is the identity point, of subgroup size 1). Any point in subgroup G multiplied by any integer is guaranteed to be another point in subgroup G. While this is also true for the "upstream" subgroups, landing on a particular point and using that as a new generator (i.e., ECDH) would cause...inconsistent results.
  5. The numbered points are the only ones that really make math sense (mod 8). If you select point 1 as your generator, you are in the small order subgroup 8, and will generate all points: 1->2->3->4->5->6->7->0->1. Number 2 will generate points in subgroup 4: 2->4->6->0->2. Number 3 will generate all points again: 3->6->1->4->5->0->3. Number 4 will only generate two points: 4->0->4. Number 0 will only generate one: 0->0->0, and so on.
  6. The smallest large subgroup has order l, which is a prime number. This basically means that any point (except identity) will be able to generate every other point, whereas in the other subgroups this isn't true.
  7. This graphic doesn't show it (it's a crappy illustration), but basically every 8th point is a member of l subgroup, and you can't "break out" of your subgroup, so multiplying by 8 guarantees you are in l subgroup, no matter which one your point started in (unless it's one of the small subgroup points, in which case you'll end up at the identity point). Of course in roughly half the cases, you would only need to multiply by 4, in 1/4th the cases by 2, and in 1/8th the cases by 1 (your point is already in subgroup G), but multiplying it by 8 ensures it in "all" cases.

P.S. I don't know if this answer makes any sense, but it's been a fun study for me. I'm sure it's technically not correct in many places, but I think it's still educational. Playing around with points in Python or the Javascript at my site has been interesting.

P.P.S. Note hash_to_ec (for creating key images) includes a "mul_8" to ensure the point is in the right subgroup.

  • Wow, that was so much more than I was hoping for, thanks! Indeed, now that you mentioned it, just multiplying by the order seems obvious... Also, it makes sense to get the generator from the group of order the largest prime divisor. Now, I am curious to how the hashing to a point works. Do you know if it hashes a point to a number and then uses that output to generate one coordinate of a point on the curve and then goes on to deduce its other coordinate? That would depend on finding y, given x (or vice-versa), using the curve equation being easy to compute. – user141 Oct 1 '16 at 0:03
  • 1
    It's...complicated. The python is somewhat readable. See here as well. I haven't tried to understand it. :) – Luigi Oct 3 '16 at 17:44
  • @user141 For hash inputs, it doesn't matter to much. Hashing will have the same security properties regardless of how you represent the input (as long as two equal things don't have the same representation). – PyRulez Oct 28 '16 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.