-1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ What issue is there applying the point doubling and point addition formulas? $\endgroup$ – fgrieu May 16 '18 at 17:26
  • 3
    $\begingroup$ Which part of the solution do you not understand? Do you not know what a discrete log is? Or do you not know how point addition works? $\endgroup$ – Alex May 16 '18 at 17:27
  • $\begingroup$ This looks like homework/test preparation on which not enough effort has been spent. In fact, I am giving a class test tonight covering elliptic curve arithmetic where this type of question is typical :-) $\endgroup$ – kodlu May 16 '18 at 21:43
  • $\begingroup$ exactly Alex I did not know how point addition t work $\endgroup$ – mhmad nkrash May 17 '18 at 11:33
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.