Elliptic curve discrete logarithm problem and mini example [closed]

Question

Consider the group E23(9,17), this the group defined by the equation y2 mod 23 = x3 + 9x + 17 mod 23. What is the discrete logarithm k of Q = (4,5) to the base P = (16,5)?

the solution is: 2P = (20,20), 3P = (14,14), 4P = (19,20), 5P = (13,10), 6P = (7,3), 7P = (8,7), 8P = (12,17), 9P = (4,5) = Q k = 9

i need the detail arithmetic method that explain this result please

Answer 1

Thanks every body the idea is completed By refer To the reference Cryptography and Network security first edition page 196 --- 198

The solution is: We have to compute additive multiple of P until Q is founded thus we should calculate 2P,3p,4P,5P….. until Q is founded.

p(16,5) First I compute 2p=R(X_r,Y_r)

S=(3〖〖*X〗_p〗^2+a)/(2Y_p )=(3〖*16〗^2+9)/(2*5) Modulo 23= 777/10 modulo 23

1/10 modulo 23=7

S=777*7 modulo 23=11

X_r=S^2-2*X_p=〖11〗^2-2*16=121-32=89 modulo 23=20

Y_r=S(X_p-X_r )-Y_p=11(16-20)-5=-49 modulo 23=20

We can compute 3p by add p(16,5)To 2p(20,20)

but I will compute 4p by duplicate 2p(20,20)

S=(3〖〖*X〗_p〗^2+a)/(2Y_p ) =(3〖*20〗^2+9)/(2*20) Modulo 23 = 1209/40 modulo 23=1209*1/4*〖10〗^(-1) modulo 23

1/10 modulo 23=7

1/4 modulo 23=6

S=1209*7*6 modulo 23=17

X_r=S^2-2*X_p=〖17〗^2-2*20=289-40=249 modulo 23=19

Y_r=S(X_p-X_r )-Y_p=17(20-19)-20=-3 modulo 23=20

Also We can compute 5p by add p(16,5)To 4p(19,20)

but I will compute 8p by duplicate 4p(19,20)

S=(3〖〖*X〗_p〗^2+a)/(2Y_p ) =(3〖*19〗^2+9)/(2*20) Modulo 23 = 1092/40 modulo 23 =1092*1/4*1/10 modulo 23

1/10 modulo 23=7 1/4 modulo 23=6

S=1092*7*6 modulo 23=2

X_r=S^2-2*X_p=2^2-2*19 =4-38=-34 modulo 23=12

Y_r=S(X_p-X_r )-Y_p =2(19-12)-20=-6 modulo 23=17

Now I will compute 9 P by add P(16,5) To 8p(12,17)

S=(Y_q-Y_p)/(X_q-X_p ) =(17-5)/(12-16)=12/(-4) =-12*1/4 modulo 23=-12*6 modulo 23=20 1/4 modulo 23=6

X_r= S^2-X_p-X_q =〖20〗^2-16-12=400-28 =372 modulo 23=4

Y_r=S(X_p-X_r )-Y_p =20(16-4)-5 =235 modulo 23=5

9P=(4,5)=Q So the discrete logarithm of Q(4,5) based on P (16,5) over Elliptic curve E_23=(17,9) is Q=9P

Answer 2

Here an example using c++:

#include <iostream>

struct Point {
    int x;
    int y;
};

// Elliptic curve parameters
const int a = 9;
const int p = 23;

// Addition of two points on the elliptic curve
Point addPoints(const Point& p1, const Point& p2) {
    int lambda, x3, y3;
    
    if (p1.x == p2.x && p1.y == p2.y) {
        // Doubling a point
        lambda = (3 * p1.x * p1.x + a) * inverseMod(2 * p1.y, p) % p;
    } else {
        // Adding two different points
        lambda = (p2.y - p1.y) * inverseMod(p2.x - p1.x, p) % p;
    }
    
    x3 = (lambda * lambda - p1.x - p2.x + 2 * p) % p;
    y3 = (lambda * (p1.x - x3) - p1.y + 2 * p) % p;
    
    return {x3, y3};
}

// Scalar multiplication of a point on the elliptic curve
Point scalarMultiply(const Point& p, int scalar) {
    Point result = {0, 0};
    
    while (scalar > 0) {
        if (scalar & 1) {
            result = addPoints(result, p);
        }
        
        p = addPoints(p, p);
        scalar >>= 1;
    }
    
    return result;
}

// Calculate the inverse of a number modulo p
int inverseMod(int num, int p) {
    int t = 0, r = p, new_t = 1, new_r = num;
    
    while (new_r != 0) {
        int quotient = r / new_r;
        int temp_t = t;
        t = new_t;
        new_t = temp_t - quotient * new_t;
        
        int temp_r = r;
        r = new_r;
        new_r = temp_r - quotient * new_r;
    }
    
    if (t < 0) {
        t += p;
    }
    
    return t;
}

int main() {
    Point P = {16, 5};
    Point Q = {4, 5};
    int k = 1;
    
    while (true) {
        Point kP = scalarMultiply(P, k);
        
        if (kP.x == Q.x && kP.y == Q.y) {
            break;
        }
        
        k++;
    }
    
    std::cout << "Discrete logarithm of Q to the base P is: " << k << std::endl;
    
    return 0;
}