[Community Puzzle] Elliptic curve cryptography

Puzzles
#1

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
#2

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)

#3

(1,1)
(4602044434169447759, 4602044434169447760)

1 Like
#4

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
#5

Thank you! I finally found the bug: it was indeed in the “modulo division” code.

#6

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 :smiley:
Edit: it’s not a performance issue I get an answer, just not the right one.

#7

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
#8

Thanks for the answer, I tried your advice by spamming modulo like a mad man :slight_smile:
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.

#9

I’ve put my code on pastebin in case a good soul has some free time :smiley: I’m feeling stuck tbh.
Edit : solved !

#10

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
#11

@Djoums The point of BigInt is to avoid the limitations of JS numbers, hence BigInt(parseInt(readline(), 16)) is not the best idea :wink: .
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
#12

Thanks a lot :smiley: I totally glanced over that part for some reason.