OpenSSL эллиптические кривые
У меня есть эллиптическая кривая EC, и мне нужно найти такую точку G EC, координата которой является наименьшим неотрицательным целым числом из всех точек на кривой. Мне это нужно для реализации алгоритма хеширования ECOH.
Я пытался использовать openssl для достижения этой цели, но до сих пор я не понял, как найти такую точку. Я пытался сделать это:
EC_POINT *G = EC_POINT_new(ec);
for(int i = 1; i < 1024; i++)
{
itoa(i, str, 10);
BN_dec2bn(&x, str);
EC_POINT_set_affine_coordinates_GFp(ec, G, x, y, ctx);
if(EC_POINT_is_on_curve(ec, G, ctx))
printf("%s\n", str);
}
Но он только проверяет, находится ли точка с координатами (x, y) на кривой или нет.
Как я могу найти это?
Решение
Во-первых, найти генератор, если ec не предоставил один. Я полагаю, вы хотите генератор с наименьшей координатой х. Вы можете сделать что-то вроде этого:
// Suppose you've found a generator point G, and a BIGNUM context bn_ctx
// has been created and initialized
BIGNUM x, y, x_min, y_min;
BN_init(&x); BN_init(&x_min);
BN_init(&y); BN_init(&y_min);
EC_POINT *P = EC_POINT_new(ec);
EC_POINT_copy(P,G);
EC_POINT_get_affine_coordinates_GFp(ec,P,x_min,y_min,bn_ctx);
do{
EC_POINT_add(ec,P,P,G,bn_ctx);
EC_POINT_get_affine_coordinates_GFp(ec,P,x,y,bn_ctx);
if (x < x_min) {
BN_copy(x_min, x);
BN_copy(y_min, y);
}
}while(!EC_POINT_is_at_infinity(ec,P));
Тогда у вас будет свой генератор (x, y) с наименьшей x-координатой.
Что касается того, как найти генератор, то это уже другая история.
Другие решения
Вместо того, чтобы использовать EC_POINT_set_affine_coordinates_GFp, что требует как x а также yиспользовать EC_POINT_set_compressed_coordinates_GFpкоторый вместо y занимает y_bit обозначая, какой из двух y значения (четные или нечетные), чтобы использовать для данного x (если x находится в области кривой).
Тогда вы сможете просто просмотреть первые несколько x найти координату с наименьшим xтак же, как вы пытаетесь сделать.