Implémentation de l'algorithme de génération de clé (ECC) probléme du point a l'infini

Version imprimable

1 pièce(s) jointe(s)

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.
Pièce jointe 194990
Et voila ce que j’ai implémenté

Code:

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:

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

11/12/2015, 08h56
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)
11/12/2015, 10h02
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
11/12/2015, 10h44
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).

1 pièce(s) jointe(s)

voila comment effectuer l'addition de deux point:
Pièce jointe 195034

voila le code java de l'addition

Code:

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:

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.

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:

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:

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

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

11/12/2015, 12h07
selmagsi

bonne solution pour le point à l'infinie merci infiniment.
normalement pas de probléme avec le RETURN et je crois etre obligée de passer en résolu la parce que je vois que mon problème est avec l’arithmétique modulaire,par exemple j'ai pas compris pourquoi (5/20)mod 23= 6 et pourquoi -34 mod 23= 12 et non pas 11 !!!! 8O
11/12/2015, 12h16
joel.drigo

Citation:

Envoyé par selmagsi

pourquoi (5/20)mod 23= 6 et pourquoi -34 mod 23= 12 et non pas 11 !!!! 8O

De quoi tu parles ? De -34 % 23 ? çà fait -11 (ni 12 ni 11 donc). Quand à (5/20)% 23, ça fait 0. Si mod a une signification particulière dans ton contexte autre que "reste de la division entière par", il faut le dire)
11/12/2015, 12h28
Flodelarab

Bonjour :coucou:

Le reste de la division est positive! Donc si on divise par b, le reste est entre 0 (inclus) et b (exclu).

-34+23=-11
-11+23=12

-34 = 12 [23]
11/12/2015, 12h31
selmagsi

1 pièce(s) jointe(s)

j'ai jamais étudié les courbes elliptiques j'ai juste pris les notions de base juste pour le ECC ,dans chaque opération sur les courbe on fait mod p (tel que p est l'ordre du corps sur lequel est défini la courbe) au début mod p j'ai compris que c'était le reste de la division entiére mais la quand j'ai tiré des exemple j'ai trouvé que c'était pas ca,voila je vous ci joint un petit exemple(cas du doublement ,en utilisant les formule que j'ai laissé dans un autre poste avec mod p dans l'exemple p=23)

Pièce jointe 195044

merci
11/12/2015, 12h36
selmagsi

@Flodelarab merci mais je n'ai rien compris de ce que vous avez dit :roll:
11/12/2015, 13h21
Flodelarab

58 = 23 * 2 + 12 donc 58 = 12 modulo 23
35 = 23 * 1 + 12 donc 35 = 12 modulo 23
12 = 23 * 0 + 12 donc 12 = 12 modulo 23
-11 = 23 * (-1) + 12 donc -11 = 12 modulo 23
-34 = 23 * (-2) + 12 donc -34 = 12 modulo 23

La division de -34 par 23 donne -2 et il reste 12.

Pareil pour l'inverse de 4. Quel est le nombre qui multiplié par 4 donne 1 ? Réponse: 6. Pourquoi ?
Car :
6*4=24=23+1=23*1+1 Donc 6*4=1 modulo 23. Et l'inverse de 4 est égal à 6 modulo 23.

Il est très important de comprendre qu'on tourne en rond. Si on comptait modulo 23, on dirait:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Là où classiquement 5 fois 7 fait 35, ici le résultat fait 12, à cause du modulo
11/12/2015, 13h50
selmagsi

je commence à voir clair maintenant grace à vous,merci
maintenant est ce que qu'il y a des méthode de modulo pour le negatif et l'inverse en java ou bien je dois les définir moi mem??
merci bcp

Citation:

Envoyé par selmagsi

maintenant est ce que qu'il y a des méthode de modulo pour le negatif et l'inverse en java ou bien je dois les définir moi mem??

En Java 8, il Math.floorMod(), pour des int ou des longs. Dont pour Java<=7 l'équivalent serait :

Code:

1
2
3
4
5
6
7
8
9
public static int modulo(int a, int b) {
    final int reste = a % b;
    if ( (b < 0 && reste > 0) || (b > 0 && reste < 0)) {
	    return reste + b;
    }
    else {
	  return reste;
    }
}

Pour le modulo sur un rationnel, je dirais ça (mais je suis moins sûr de moi) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static float modulo(int a1, int a2, int b) {
	  if( a2>a1 && a2%a1==0 ) {
 
		  float q = ((float)a2)/a1;
 
		  q = (b+1)/q;
 
		  final float reste = q % b;
		  if ( (b < 0 && reste > 0) || (b > 0 && reste < 0)) {
		    return reste + b;
		  }
		  else {
			  return reste;
		  }
 
	  }
	  throw new IllegalArgumentException();
	}

11/12/2015, 19h29
selmagsi

merci Joel merci bcp ,cette méthode Math.floorMod(long,long) marche super bien avec les nombre négatif mais avec l'inverse ca me donne des zero a chaque fois!!!
11/12/2015, 19h44
joel.drigo

Citation:

Envoyé par selmagsi

merci Joel merci bcp ,cette méthode Math.floorMod(long,long) marche super bien avec les nombre négatif mais avec l'inverse ca me donne des zero a chaque fois!!!

Avec l'inverse ? Tu veux dire 5/20 (4^-1) ? C'est normal : on ne peut pas utiliser cette méthode pour ce cas. Parce que, en Java, un int divisé par un int, donne un int. 5/20 vaut donc 0, et donc après le modulo vaut 0. Et si tu calcules 5/20 en float, donc 0.25f, tu ne peux plus utiliser Math.floor(), parce qu'elle n'est prévu que pour int et long.
11/12/2015, 20h36
selmagsi

merci Joel,donc il faut que je teste la méthode que vous m'avez donnée si non je l’implémente merci infiniment
11/12/2015, 20h49
selmagsi

Joel et Flodelarab vous m'avez sauvée,je vous remercie infiniment!!!!
13/12/2015, 00h16
selmagsi

Comment calculer a/b mod p en java sachant que b%a!=0 exemple 3/5 mod p ? :calim2:
13/12/2015, 13h49
Flodelarab

Je ne sais pas quoi te dire d'autre que de trouver une bibliothèque java qui donne le résultat de l'algorithme d'Euclide étendu, ou de coder cet algorithme toi-même.

Le point d'entrée est dans Wikipedia:
https://fr.wikipedia.org/wiki/Inverse_modulaire
13/12/2015, 14h31
joel.drigo

Le problème c'est que a/b mod n est égale à ((a mod b)*(b^-1 mod n)) mod n, si ((a mod b)*(b^-1 mod n)) est défini, et il est défini si (b^-1 mod n) est défini. Et (b^-1 mod n) est défini que si b et n sont copremiers (donc déjà il faudrait modifier ma méthode "naive" pour tester ce cas). Si tu as l'assurance que p est premier (il me semble que c'est le cas dans ton contexte), et que b ne divise pas p, ça devrait suffire, sinon il faut chercher un algorihme performant (voir cette discussion). Mais tout ça n'est plus vraiment un problème de Java, mais un problème algorithmique : c'est plutôt dans la section correspondante que tu pourras avoir des réponses, que tu encoderas ensuite en Java.
13/12/2015, 18h10
selmagsi

joel et Flodelarab merci pour votre aide...
oui le p est toujours premier mais pour éviter tout exception je vais voir avec l'Algorithme d’Euclide étendu comme a dit Flodelarab c'est la solution de mon problème ,je crois pas qu'il est prédéfini en java je vais l'implémenter moi meme ,et comme vous avez dit Joel le probléme ne réside pas en java mais le bon algorithme me manqué et surtout les notion de base sur l'arithmétique modulaire...
encore merci de suivre mon probléme
14/12/2015, 21h50
selmagsi

bon les développeur c'est résolu pour calculer (a/b)mod p ac (b mod a !=0) on calcule tout simplement (( a mod p) *( b^-1 mod p))mod p
merci Flodelarab et joel encors merci :)