How to generate a random point on curve efficiently?

16 views
Skip to first unread message

Po-Chu Hsu

unread,
Jan 7, 2022, 6:40:15 AMJan 7
to Crypto++ Users
I have an application that needs to use a random number generator to generate a point on an elliptic curve.

The typical way is
1. generate random integer x.
2. Calculate Y = xG.
Integer x(prg, Integer::One(), group.GetMaxExponent());
ECP::Point Y = group.ExponentiateBase(x);
However, in my application, this takes too much time, and I don't need to know x.

I tried another approach.
1. generate random integer x.
2. calculate the corresponding y by using the function of the curve.
3. if y doesn't exist, find x + 1 until there's a valid y.
Integer x(prg, Integer::One(), this->p_);
ECP::Point Y;
bool v = x.GetBit(0);
while (true) {
Integer r = (a_exp_b_mod_c(x, Integer("3"), p) + (a * x) % p + b) % p;
Integer y = a_exp_b_mod_c(r, q, p);
if (a_exp_b_mod_c(y, Integer::Two(), p) == r) {
if (v) {
Y = ECP::Point(x, y);
} else {
Y = ECP::Point(x, this->p_ - y);
}
break;
}
x += 1;
}
This method is much faster than the first approach.
However, it is still slower than my expectation.

Does anyone have good advice?
Reply all
Reply to author
Forward
0 new messages