mercredi, février 20, 2019

ECC backdoors for dummies in 5 steps

It will be explained in the most simple and pragmatic way, what possible ECC backdoors look like and why choosing the right curve and the right prime number to build the cryptographic curve is important.

1st step: understand how ecc cryptography works

Read and meditate https://www.coindesk.com/math-behind-bitcoin/


2nd step: Understand graphically how a scalar multiplication looks like when choosing the right base point with a good prime number on a good curve 


We first takes a random base point (2,22) and scalar multiply from 1 to n until it reaches infinity or point (0,0), then we look for the next base point that was not part of previous loop and multiply it, and so on until there are no free untouched base points.

For [y2 = x3 + 0x + 7  Ordre 67  size 78] curve whatever base point you start with, the loop contains all points of the curve (plus(0,0)), Thus there is only one curve.

To decrypt some data, without knowing the key, using these parameters you have to do 78 tests.


3rd step: choose a wrong prime number on a good curve


We first takes a random base point (1,9) and scalr multiply from 1 to n until it reaches infinity or point (0,0), then we look for the next base point that was not part of previous loop (6,2) and multiply it, and so on until there are no free untouched base points.

For [y2 = x3 + 0x + 7  Ordre 73  size 63] curve, loop sizes are 8 or 4.  

To decrypt some data, without knowing the key, using these parameters you have to do only a maximum of 8 tests.

What makes the [y2 = x3 + 0x + 7  Ordre 73  size 63] curve a bad choice is that at least one base point is on the x axis here zero_base_points are (42,0), (44,0) & (60,0)

4th step: choose a wrong curve

Some curves do not show any prime number without any zero_base_points:

(y2 = x3 + 0x + 1,TreeSet())
(y2 = x3 + 0x + 2,TreeSet(13, 37, 67, 139, 379, 541))
(y2 = x3 + 0x + 3,TreeSet(7, 31, 43, 79, 163, 199, 223, 463))
(y2 = x3 + 0x + 4,TreeSet())
(y2 = x3 + 0x + 5,TreeSet(43, 73, 193, 223, 277, 307, 397, 433))
(y2 = x3 + 0x + 6,TreeSet(31, 199, 223, 271, 367))
(y2 = x3 + 0x + 7,TreeSet(67, 229, 241, 499))
(y2 = x3 + 0x + 8,TreeSet())


5th step: going further open points

https://www.coindesk.com/math-behind-bitcoin/
https://crypto.stackexchange.com/questions/44304/understanding-elliptic-curve-point-addition-over-a-finite-field
https://fr.wikipedia.org/wiki/Courbe_elliptiquehttps://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition

The code to draw these curves : https://github.com/emariacher/kebra/blob/master/elliptique_sbt/core/src/main/scala/FaisGaffeAuxBackDoors.scala

Aucun commentaire: