Safe Elliptic curves of prime order according to "safecurves" I am currently trying to implement a cryptographic scheme. For this purpose I need a group of prime order in which the discrete logarithm problem is hard. 

For now, I have been using a subgroup of prime order q over the Integers mod p, where p=2q+1, p prime, q prime. (p about 2048-4096 bits) The parameters for the groups are based on the primes given in RFC3526. 

I would like to also try the scheme over elliptic curves. I'm aware of https://safecurves.cr.yp.to which lists and classifies a lot of different curves. However the information of whether the curve is of prime order is missing there. I've tried some of the popular curves like Curve25519 with Sagemath, however e. g. Curve25519 appears not to be of prime order, only the NIST curve (which have uncertain seed origin) are working. 

So my question is basically: Are there any 'safe' and well-established elliptic curves of prime order? (If the answer is yes then where to find them? And if the answer is no, then why not and what's so special about the NIST curves then). 

Thanks for your help in advance. I'm quite new to the topic, please don't hesitate asking if anything is unclear.
Are there any 'safe' and well-established elliptic curves of prime order?


Depends on what you mean by 'safe'.  If you use Dan Bernstein's definition of "safe curve", no; the curves they list as safe are Edwards curve, which always have a point of order 2 (and hence can't be of prime order).

As for proposed curves that are of prime order, there's the NIST curves that you know about, there's the Brainpool curves, and there are the Weierstrass flavor of the NUMS curves.  Whether they are 'well-established' is questionable; they each certainly have their proponents.

Also, it's not clear that you really need a prime order curve. The multiplicative group $Z^*_p$ you're using isn't of prime order either, you manage to work in a prime order subgroup.  The elliptic curves we use for cryptography have large prime order subgroups (to make the discrete log program hard), perhaps you can use the same trick to use, say, Curve25519.