Discussion :

[selmagsi]

Salut les développeurs help !!!
Je réalise une petite application java qui sert à générer la clé de cryptage dans le cas du protocole ECC.
je commence par la multiplication scalaire tout d'abord
L’algorithme que j’implémente est ci-joint.

Et voila ce que j’ai implémenté

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Point  multiScalaire(Point p, int a, int k){
//p point a additionner
//k combien de fois l'aditionner      
//Q point resultant  
 Point Q; 
         int j = 0,n;
        String S;
        ConvertDecimal c=new ConvertDecimal();
      S=c.convert(k, 2);
 
      double inf=Double.POSITIVE_INFINITY;
       Q=new Point(inf, inf);
 
       for(int i=0;i<S.length();i++){
          if(S.charAt(i)=='1'){
//addition de deux point définie a part testée et fiable          
    Q= addition(p, Q);
 
          } 
//addition de deux point égaux définie a part testée et fiable           
p=doublement(p, a);       return Q;}
       }

Le problème c’est que j’ai des valeur du x et y de mon point Q indéfini parce que dans mon implémentation l’infini n’est pas considéré comme l’élément neutre par rapport à l’addition.
j'ai trouvé pour solution:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Point  multiScalaire(Point p, int a, int k){
//p point a additionner
//k combien de fois l'aditionner      
//Q point resultant  
 Point Q; 
         int j = 0,n;
        String S;
        ConvertDecimal c=new ConvertDecimal();
      S=c.convert(k, 2);
 
      double inf=Double.POSITIVE_INFINITY;
       Q=new Point(inf, inf);
 
       for(int i=0;i<S.length();i++){
   if(S.charAt(i)=='1' && Q.getX=Infinity && Q.getY=Infinity){
Q=p; //premiére addition de l'algorithme donne comme résultat p puisque Q=p+Q; ET Q et infini et l'infini et l'element neutre par rapport a l'addition
 
          }        
   if(S.charAt(i)=='1' && Q.getX!=Infinity && Q.getY!=Infinity){
//addition de deux point définie a part testée et fiable          
    Q= addition(p, Q);
 
          } 
//addition de deux point égaux définie a part testée et fiable           
p=doublement(p, a);       return Q;}
       }

mais toujours le même problème des valeurs indéfinies à cause du fameux infini .
quelqu'un aurait une idée sur la solution de mon probléme??
merci d'avance de l'aide

[joel.drigo]

Salut,

Depuis quand l'infini est-il l'élément neutre de l'addition ? Ce n'est pas 0, l'élément neutre de l'addition ? (Remarque : au début de l'algorithme, on voit P ← 0)

[selmagsi]

O est le symbole de l'infini dans les courbe elliptique et oué c'est la vie dans les courbe elliptique l'élément neutre est bel et bien l'infini ,j'ai beau essayé la démontrer mais sans succès

[joel.drigo]

Il n'est pas question de courbes elliptiques mais de double, type Java. Ta méthode addition doit implémenter l'addition de 2 points au sens courbe elliptique (sens mathématique), ce qui ne peut être directement appliqué avec des doubles. Déjà, il y a une infinité de réels, mais pas une infinité de double, et Double.POSITIVE_INFINITY-Double.POSITIVE_INFINITY donne Double.NaN. Donc les formules d'addition de points ne pourront jamais fonctionner directement (somme de 2 points infinis par exemple) avec des doubles.
Tes tests sur "Infinity" devraient être dans la méthode addition. Quel est le code de ton addition (le vrai code Java, pas cette espèce de pseudo java que tu as mis — d'ailleurs cette méthode devrait être une méthode de la classe Point) ? Par ailleurs, tu n'es pas obligé d'utiliser Double.POSITIVE_INFINITY pour représenter une coordonnée de point à l'infini, tu peux aussi bien le faire avec un attribut qui signifie que ton point est à l'infini, en codant toutes les méthodes utiles pour que leur comportements soient conforme à cet état (comme P+0 = P).

[selmagsi]

voila comment effectuer l'addition de deux point:


voila le code java de l'addition

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static Point addition(Point p1, Point p2){
 
        Point p3;
 
        double x1,x2,x3,y1,y2,y3;
        double a1,a2;
        double fra1;
 
        x1=p1.getX();
        x2=p2.getX();
 
        y1=p1.getY();
        y2=p2.getY();
 
 
 
        a1=y2-y1;
        a2=x2-x1;
 
        fra1=a1/a2;
 
 
        x3=(Math.pow(fra1, 2)-x1-x2)%11;
 
        y3=(Math.pow(fra1, 2)*(x1-x3)-y1)%11;
 
        p3=new Point(x3,y3);
 
 
        return p3;
    }

voila doublement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
static Point doublement(Point p, int a){
        double a1,a2;
        double fra1,fra2,fra3;
        double x,y,x1,y1;
        x=p.getX();
        y=p.getY();
        Point Q = null;
 
 
        a1=3* Math.pow(x, 2)+a;
        fra1=a1/(2*y);
        fra2=Math.pow(fra1, 2);
 
        fra3=fra2-(2*x);
 
        x1=fra3%11;
        y1=(fra1*(x-x1)-y)%11;
 
 
      Q=new Point(x1,y1);
 
        return Q;
    }

certainement j'ai la classe point.

[joel.drigo]

C'est bien ce que je te dis : tu ne peux pas appliquer des formules de calcul sur des doubles telles quelles, sans traiter le cas du O à part.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Point {
 
    private final double x;
    private final double y;
    private final boolean infinity;
 
    public Point(double x, double y) {
         infinity = ( x==Double.POSITIVE_INFINITY || y==Double.POSITIVE_INFINITY );
         this.x=x;
         this.y=y;
    }
 
    public double getX() {
        return x;
    }
 
    public double getY() {
        return y;
    }
 
    public boolean isInfinity() {
        return infinity;
    }
 
    public Point add(Point p) {
        if ( this.isInfinity() ) {
             return p;
        }
        else if ( p.isInfinity() ) {
             return this;
        }
        else { 
              // ... ici l'application des formules qui peuvent fonctionner avec des doubles
        }
    }
 
}

Attention également à l'égalité entre doubles : tu ne peux pas toujours écrire if ( d1==d2 ), il vaut mieux comparer la valeur absolue de la différence avec un EPSILON (un double proche de 0).

Je vois un autre problème dans ton programme par rapport à l'algorithme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

p=doublement(p, a);       return Q;}

Le return Q est en dehors du for dans l’algorithme.