https://www.codingame.com/training/hard/elliptic-curve-cryptography
Send your feedback or ask for help here!
Created by @Coni,validated by @_CG_Nick,@Fireball0923 and @Niako.
If you have any issues, feel free to ping them.
1 Like
This puzzle is very hard to debug, because only the final result is known and there are many steps where things can go wrong.
I have a nasty bug that I cannot find for weeks.
I fail even simplest test case #01. Here k = 2, so I assume I need to find ā2 * Gā.
Could anyone please write what is the expected L in this operation? (Maybe my modulo arithmethics functions are wrong.)
Or could you please give what is the result of
point(0, 0) + point(1, 1)
and of
point(1, 1) + point(1, 1)
(1,1)
(4602044434169447759, 4602044434169447760)
1 Like
Actually the operation + only makes sense on the elliptic curve (y^2 = x^3 + 7 mod P in this puzzle), while points (0,0) and (1,1) are not on this curve, so there is no right answer to your questionā¦
The first answer given by @nicola1 seems to imply that (0,0) is the neutral element of the group, which is not the case (and actually itās not even in the group).
That said, for the operation G+G, we have L = 2032944238605471208 and the result is (2685467149996858908, 1223440626623933451).
2 Likes
Thank you! I finally found the bug: it was indeed in the āmodulo divisionā code.
My code passes the first 3 tests (short and medium), but fails on the nexts (long).
Any idea what the cause could be ? I have no clue how to debug my code in this scenario 
Edit: itās not a performance issue I get an answer, just not the right one.
my advise: be careful with your modular arithmethic code - avoid any possibility of a 64-bit integer overflow at EVERY step of the calculation.
1 Like
Thanks for the answer, I tried your advice by spamming modulo like a mad man 
But to no avail unfortunately, my wrong answer didnāt change in the process. The BigInt js library can handle huge numbers so I kinda expected this.
Iāve put my code on pastebin in case a good soul has some free time Iām feeling stuck tbh.
Edit : solved !
I am not a good human debugger in a language I donāt knowā¦ But my modular arithmetics code is slightly different from yours. I can send you my solution in PM if that can help for your own debugging.
1 Like
@Djoums The point of BigInt is to avoid the limitations of JS numbers, hence BigInt(parseInt(readline(), 16)) is not the best idea 
.
BigInt(readline()) is simpler and will solve your issue (the "0x" prefix is good enough to indicate an hex input).
Please delete the link to your code once itās solved.
2 Likes
Thanks a lot I totally glanced over that part for some reason.
Hello, Iāve been working for days on this puzzle. My code (C) is working form small values but as soon as I have to calculate 3*xA^2 to compute 2*G, I am going over 64 bits. Is there any solution in C without using the GMP library ? Did you use any tip to compute the modular square values without bypassing 64 bit numbers? thank you!
You donāt need to go over 64 bits, modulo arithmethics is enough.
However you need to avoid any possible overflow at every step of the calculation.
For example I calculate (a + b) % P as ((a % P) + (b % P)) % P, because a + b might be over 64 bits. Similarly, modular multiplication implementation needs some extra consideration.
1 Like
At least N constraints are wrong:
this
1 < N ā¤ 50
should at least be
1 ā¤ N ā¤ 50
Example input:
1
0x2
1 Like
Updated. Thanks for reporting!
1 Like
Itās also a bit confusing to see different notations for exponentiation near each other:
Xs = LĀ² - Xc - Xd mod P
L = (3Xc^2 + A) / (2Yc) mod P
I think Xc^2 should be written as XcĀ² for consistency
BTW, other such cases in the statement can be replaced too
- YĀ² = X^3 + AX + B => YĀ² = XĀ³ + AX + B
- YĀ² = X^3 + 7 => YĀ² = XĀ³ + 7
- 2^200 => 2Ā²ā°ā°
I liked the puzzle, but I struggled in the beginning. It would be great if there was an even easier first test case, which could be solved with unoptimized modular inverse logic. We could read G and P to support it.
Xs = LĀ² - Xc - Xd mod P
Ys = L * (Xc - Xs) - Yc mod P
If the new coordinates are negative, should it be changed into positive values (by abs() or +P)? Or it was just overflow of the 64-bit data? Hard to debug.
Finally overcome it.
Negative coordinates were caused by data overflow. Finally the whole program was rewritten using BigInteger. Originally I thought it could be slow and clumsy. In practice the result was felt to be faster than pure long int operations, more elegant in the code and most importantly the built-in operations are bug free.