Could somebody please explain how this function works step by step?

Why: I am programming the Monero wallet functions on a quite limited platform with only some inbuilt cryptographic primitives. I need to implement ge_fromfe_frombytes_vartime because this function is needed for computing key images.

What I have available:

// Keccak hash function
keccak256( ... )

// This routine performs an elliptic curve 
// scalar point multiple using the Elliptic Curve 25519
ec25519_point_multiply( ... );

// Multiply point by a scalar for Elliptic Curve 25519
ed25519_scalar_multiply( ... );

// This routine recovers X-coordinate given Y-coordinate
ec25519_xrecover( ... );

// Check signature (point) against message string (hash)
ed25519_valid_sig( ... );

// Functions for modular arithmetics, operands could be 32B integers
C = (A+B) mod P
C = (A-B) mod P
C = (A*B) mod P (P odd)
C = B mod P (P odd), A is ignored
C = (A/B) mod P (P odd)
C = (1/B) mod P (P odd)
C = (A * B) F(p) only, P is ignored
C = (1/B) mod P (P even), A is ignored
C = B mod P (P even), A is ignored

Thanks a lot for any help!

  • 1
    If you're trying to understand the mathematics behind it, see github.com/monero-project/research-lab/blob/master/whitepaper/… If you're confused about all of the complex shifts in the C code, I'm not clear on what is preventing you from simply porting the hashToPointCN method from Mininero instead. That hashToPointCN method looks like it does mostly use modular arithmetic. – knaccc Dec 17 '19 at 20:19

ge_fromfe_frombytes_vartime takes as input a field element (as a string of bytes) and outputs a point (a group element), on the ed25519 curve. The precise implementation is detailed in Shen Noether's paper on the subject.

As @knaccc commented above, a better example for porting the implementation is probably Mininero's implementation of hashToPointCN.

| improve this answer | |
  • 1
    Are you saying you should be able to just do G.scalarmult(fashHash(x))? I've just tried that, and that does not provide the same result as hash_to_ec/hashToPointCN. I can't see how that could work, because an fe is in the range 0->2^255-19 and a scalar is in the approximate range 0->2^252. Also, although I don't think it matters for key images, you'd probably want to implement a hash_to_ec function such that the private key of the output wrt G remains unknown, which would not be the case if you just multiplied by G. – knaccc Dec 18 '19 at 0:24
  • 1
    My understanding of ge_fromfe_frombytes_vartime is that it simply takes a single field element coordinate and recovers the entire EC point in P2 coordinate space, but has modifications to take into account that only 50% of 32 byte sequences will result in a valid coordinate of an EC point. This is entirely different than treating the field element as a scalar and then doing a scalar multiplication. – knaccc Dec 18 '19 at 2:38

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.