c - elliptic curve discrete logarithm -
i trying solve elliptic curve discrete logarithm using pollard rho (find k g=kp), searched implementation in c , found 1 after adding problem specific data in main
function got segmentation fault (core dumped)
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <gmp.h> #include <limits.h> #include <sys/time.h> #include <openssl/ec.h> #include <openssl/bn.h> #include <openssl/obj_mac.h> // nid_secp256k1 #define pollard_set_count 16 #if defined(win32) || defined(_win32) #define export __declspec(dllexport) #else #define export #endif #define max_restart 100 int ec_point_partition(const ec_group *ecgrp, const ec_point *x) { size_t len = ec_point_point2oct( ecgrp, x, point_conversion_uncompressed, null, 0, null ); unsigned char ret[len]; ec_point_point2oct( ecgrp, x, point_conversion_uncompressed, ret, len, null ); int id = ( ret[len - 1] & 0xff ) % pollard_set_count; return id; } // p generator // q result*p // order of curve // result //reference: j. sattler , c. p. schnorr, "generating random walks in groups" int elliptic_pollard_rho_dlog(const ec_group *group, const ec_point *p, const ec_point *q, const bignum *order, bignum *res) { printf("pollard rho discrete log algorithm... \n"); bn_ctx* ctx; ctx = bn_ctx_new(); int i, j; int iterations = 0; if ( !ec_point_is_on_curve(group, p, ctx ) || !ec_point_is_on_curve(group, q, ctx ) ) return 1; ec_point *x1 = ec_point_new(group); ec_point *x2 = ec_point_new(group); bignum *c1 = bn_new(); bignum *d1 = bn_new(); bignum *c2 = bn_new(); bignum *d2 = bn_new(); bignum* a[pollard_set_count]; bignum* b[pollard_set_count]; ec_point* r[pollard_set_count]; bn_zero(c1); bn_zero(d1); bn_zero(c2); bn_zero(d2); (i = 0; < pollard_set_count; i++) { a[i] = bn_new(); b[i] = bn_new(); r[i] = ec_point_new(group); bn_rand_range(a[i], order); bn_rand_range(b[i], order); // r = ap + bq ec_point_mul(group, r[i], a[i], q, b[i], ctx); //ep_norm(r[i], r[i]); } bn_rand_range(c1, order); bn_rand_range(d1, order); // x1 = c1*p + d1*q ec_point_mul(group, x1, c1, q, d1, ctx); //ep_norm(x1, x1); bn_copy(c2, c1); bn_copy(d2, d1); ec_point_copy(x2, x1); double work_time = (double) clock(); { j = ec_point_partition(group, x1); ec_point_add(group, x1, x1, r[j], ctx); bn_mod_add(c1, c1, a[j], order, ctx); bn_mod_add(d1, d1, b[j], order, ctx); (i = 0; < 2; i++) { j = ec_point_partition(group, x2); ec_point_add(group, x2, x2, r[j], ctx); bn_mod_add(c2, c2, a[j], order, ctx); bn_mod_add(d2, d2, b[j], order, ctx); } iterations++; printf("iteration %d \r",iterations ); } while ( ec_point_cmp(group, x1, x2, ctx) != 0 ) ; printf("\n "); work_time = ( (double) clock() - work_time ) / (double)clocks_per_sec; printf("number of iterations %d %f\n",iterations, work_time ); bn_mod_sub(c1, c1, c2, order, ctx); bn_mod_sub(d2, d2, d1, order, ctx); if (bn_is_zero(d2) == 1) return 1; //d1 = d2^-1 mod order bn_mod_inverse(d1, d2, order, ctx); bn_mod_mul(res, c1, d1, order, ctx); (int k = 0; k < pollard_set_count; ++k) { bn_free(a[k]); bn_free(b[k]); ec_point_free(r[k]); } bn_free(c1); bn_free(d1); bn_free(c2); bn_free(d2); ec_point_free(x1); ec_point_free(x2); bn_ctx_free(ctx); return 0; } int main(int argc, char *argv[]) { unsigned char *p_str="134747661567386867366256408824228742802669457"; unsigned char *a_str="-1"; unsigned char *b_str="0"; bignum *p = bn_bin2bn(p_str, sizeof(p_str), null); bignum *a = bn_bin2bn(a_str, sizeof(a_str), null); bignum *b = bn_bin2bn(b_str, sizeof(b_str), null); bn_ctx* ctx; ctx = bn_ctx_new(); ec_group* g = ec_group_new(ec_gfp_simple_method()); ec_group_set_curve_gfp(g,p,a,b,ctx); unsigned char *xp_str="18185174461194872234733581786593019886770620"; unsigned char *yp_str="74952280828346465277451545812645059041440154"; bn_ctx* ctx1; ctx1 = bn_ctx_new(); bignum *xp = bn_bin2bn(xp_str, sizeof(xp_str), null); bignum *yp = bn_bin2bn(yp_str, sizeof(yp_str), null); ec_point* p = ec_point_new(g); ec_point_set_affine_coordinates_gfp(g,p,xp,yp,ctx1); unsigned char *xq_str="76468233972358960368422190121977870066985660"; unsigned char *yq_str="33884872380845276447083435959215308764231090"; bignum* xq = bn_bin2bn(xq_str, sizeof(xq_str), null); bignum* yq = bn_bin2bn(yq_str, sizeof(yq_str), null); ec_point *q = ec_point_new(g); bn_ctx* ctx2; ctx2 = bn_ctx_new(); ec_point_set_affine_coordinates_gfp(g,q,xq,yq,ctx2); char * str; unsigned char *n_str="2902021510595963727029"; bignum *n = bn_bin2bn(n_str, sizeof(n_str), null); bignum *res; elliptic_pollard_rho_dlog (g,p,q,n,res); bn_bn2mpi(res,str); printf("%s\n", str); return 0; }
this statement cause segmentation fault
bn_bn2mpi(res,str);
Comments
Post a Comment