Discussion :

[selmagsi]

bonjours les développeurs
je fais une étude approfondi sur la cryptographie à base de courbe elliptique (ECC) et je n'arrive pas à trouver l'algorithme qui génère la clé de cryptage si quelqu'un peut me le donner je lui serai très reconnaissante
merci d'avance pour votre aide
cordialement

[anapurna]

salut ,

as tu lu cette article il est je pense assez clair pour comprendre comment fonctionne ce type de cryptography

[Flodelarab]

Bonjour

Excellent article.
Ce qui est troublant est de penser que P est publique, d*P est publique, et pourtant d est privé et introuvable.

[selmagsi]

c'est génial
merci bcp

[anapurna]

salut

oui je suis comme toi je trouve ça pas tres logique
sachant

que tu recupere Q P C1,C2
que Q = P*d
donc d = Q/P
et que M = C2-d*C1

je comprend pas comment on ne peut pas retrouver le message

j'ai fait un exemple numerique simple

Code :

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

1
2
3
4
5
6
7
8
 
Q  = 15 (Publique)
P  = 5  (Publique)
d = 15 div 3 = 5 (Privé)
C1   =  k * P        => C1 = 6*3 = 18 (Publique)
CLE  =  k*Q         => CLE = 6*15 = 90; (Privé)
C2   =  M + CLE   => C2 = 65 + 90 = 155;(Publique) 
M    = C2-d*C1    => M  = 155 - 5*18 = 155-90 = 65 (Privé)

j'ai surement raté quelque chose mais je vois pas encore quoi

[Flodelarab]

C'est toute la question.

On n'est pas dans mais dans

C'est à dire pas dans :
0 1 2 3 4 5 6 7 8 9 10 11 12 ...
mais
0 1 2 0 1 2 0 1 2 0 1 2 0 ... (si c'est modulo 3).

Les additions, multiplications, exposants sont toujours modulo quelque chose, même si ce n'est pas précisé (c'est tellement évident ) car on est toujours dans le même groupe cyclique.

Et c'est pour cela qu'on peut donner P, d*P (officiellement Q) sans que d ne puisse être déduit. Car si on était dans il suffirait de faire d=Q/P ...

Du moins, c'est ce que j'ai compris.

[edit] il ne marche pas bien votre module latex.
la première formule était pour N, l'ensemble des nombres entiers
la seconde Z\nZ, le groupe cyclique.
et la troisième N, l'ensemble des nombres entiers
[/edit]

[dourouc05]

Du moins, c'est ce que j'ai compris.

En effet, travailler avec des modulos apporte des propriétés très spéciales : on travaille dans un corps fini (modulo quelque chose) plutôt qu'infini (mais dénombrable). Ainsi, il est possible de définir un inverse multiplicatif : pour a, un b tel que a \times b \mod n = 1 (calculable par une extension de l'algorithme d'Euclide). Ces principes sont aussi à la base de RSA.

(Maintenant, je dois bien avouer ne pas avoir vraiment exploré ce type de cryptographie…)

[anapurna]

salut,

bon c'est la ou je veut comprendre ^^
si j'ai bien compris j'ai un nombre P (c'est le nombre d’itération du modulo)
j'ai un modulo d
j'ai une clé public Q

prenons la lettre C = 67
imaginons que d=91 P=29

donc on crypte avec la clé privé

1 67
2 30 = 67*67 mod 91
3 08 = 30*67 mod 91
4 81 = 08*67 mod 91
5 58 = 81*67 mod 91
...
28 81 = 08*67 mod 91
29 58 = 81*67 mod 91

pour le décryptage on a
une clé public Q=5

1 58
2 88 = 58*58 mod 91
3 08 = 88*58 mod 91
4 09 = 08*58 mod 91
5 67 = 09*58 mod 91

en fait ce que je ne comprend pas c'est comment on passe de P à Q
si quelqu'un peut m'expliquer avec des nombre et formule complète se serait sympa

[dourouc05]

en fait ce que je ne comprend pas c'est comment on passe de P à Q

À mon avis, mieux vaut repartir des bases avec un article comme https://www.certicom.com/pdfs/WP-ECCprimer_login.pdf (détails gore à partir de la page 13, même si le vraiment gore ne semble pas y être…) ou http://link.springer.com/chapter/10....-642-04101-3_9 (semble limité à l'échange des clés). Si j'ai bien compris, le passage de P à Q se fait par la multiplication par un nombre choisi aléatoirement (et de préférence très grand).

De manière générale, ce qui m'interpelle dans ton raisonnement, c'est que tu ne tiens pas compte de la notion de courbe elliptique .

(D'ailleurs, si tu explores le problème plus en détail, je pense que ça intéressera pas mal de gens d'avoir un article à ce sujet .)

[Flodelarab]

@Admin:
Merci pour la correction LaTeX

@anapurna:

d n'est pas le modulo. Le modulo est élément du décor, sous-entendu en permanence.
d est un nombre choisi comme clé privée par le récipiendaire.

P est un point de la courbe elliptique connu publiquement.

Imaginons un modulo 100, un point P à 23 et un nombre d à13.
Q= P.d [100] = 13x23 [100] = 299 [100] = 99 [100]

99 est transmis comme valeur de Q.

Un être malfaisant interceptant 99 et 23 ne peut pas retrouver 13. Trop compliqué pour des grands nombres.

[dinobogan]

Attention, l'addition est une loi de composition sur les points de la courbe elliptique.
Ce n'est pas 13x23 qu'il faut faire, mais 13 fois l'addition des coordonnées du point P sur la courbe elliptique définit sur les nombres réelles avec ses coefficients 'a', 'b' et le modulo. Alice et Bob se sont mis d'accord publiquement sur ces coefficients donc sont connus de tous.

[anapurna]

salut,

je crois que je vient de comprendre ^^

imaginons les donnée suivante

Modulo 11 Public
d 05 Privé
p 25 Public
Q 04 Public MOD(P*d;Modulo)
k 06 Privé
C1 07 Public
CLE 02 Privé MOD(K*Q;Modulo)
C2 67 Public C2+CLE
M 65 resultat M=C2-MOD(d*C1;Modulo)

en fais a programmer c'est super simple ^^
PS : et flute c'est pas encore ça merci pour la precision de l'adition et non pas la mutiplication

[dinobogan]

De plus P est un point définit par l'équation de la courbe elliptique. Il est défini par une abscisse et une ordonnée.
Prenons le cas des courbes elliptiques spécifiques utilisées pour la cryptographie :
y² = x³ + ax + b mod m
Les coordonnées du point P doivent satisfaire cette équation. Si par exemple, a=4, b=3 et m=6, choisissons x_p=5. Alors y_p=2 (ou -2, mais le choix du point P est arbitraire, tant qu'Alice et Bob sont d'accord sur ce point).

La définition de l'addition pour les courbes elliptiques sur les réels est très bien expliquée sur la page Wikipédia en français. Elle décrit l'addition de deux points sur la courbe. Ces deux points possèdent chacun une abscisse et une ordonnée. Il y a le cas ou les abscisses sont différentes, les abscisses sont identiques mais les ordonnées différentes, les abscisses identiques et les ordonnées identiques différentes de zéro et enfin les abscisses identiques et les ordonnées identiques à zéro.
Avec ces 4 cas, il devient facile de déterminer la multiplication d'un point de la courbe par un entier naturel : c'est une simple suite d'additions. Les équations sont un peu longues mais restent de niveau collège pour la mises en oeuvre.

Maintenant, Alice choisit un entier secret d_a, le multiplie par P et l'envoie en clair à Bob. C'est un point de la courbe avec abscisse et ordonnée.
Bob fait de même avec d_b, qu'il multiplie par P et l'envoie à Alice. C'est aussi un point de la courbe avec abscisse et ordonnée.
Alice et Bob, chacun de leur côté, sont capable de calculer d_a*d_b*P, qui devient la clé secrète. Cette clé est composée d'une abscisse et d'une ordonnée puisque c'est un point sur la courbe elliptique. Alice et Bob peuvent discuter librement sur la façon d'arranger ces deux valeurs (concaténation, utiliser uniquement l'abscisse, ou l'ordonnée...) ou d'une technique de codage utilisant ces deux valeurs séparées.

Il n'existe pas de moyen simple ou rapide pour retrouver d_a et/ou d_b facilement.

[anapurna]

salut

on peut res bien prendre des entier quelconque
je suppose que l'on a réussi a le démontrer grâce a une courbe elliptique mais pour notre problème de crypto on se fou un peu de la courbe on a juste à connaitre le modulo et le point P
je me suis fait un test a l'aide d'ecxel de recherchev dans une table pré-calculé avec le modulo et les différentes équations qui vont bien

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
Modulo	89	Public
d	10	Privé
p	74	Public
Q	28	Public
k	21	privé
C1	41	Public
CLE	54	privé
M	65	privé
C2	119	Public
Res	65	
 
// mon tableau pré-calculé
 
Q  (d*p)	C1  (k*P)	CLE (k*Q)	d*C1
1	74	74	28	41
2	59	59	56	82
3	44	44	84	34
4	29	29	23	75
5	14	14	51	27
6	88	88	79	68
7	73	73	18	20
8	58	58	46	61
9	43	43	74	13
10	28	28	13	54
11	13	13	41	6
12	87	87	69	47
13	72	72	8	88
14	57	57	36	40
15	42	42	64	81
16	27	27	3	33
17	12	12	31	74
18	86	86	59	26
19	71	71	87	67
20	56	56	26	19
21	41	41	54	60
22	26	26	82	12
23	11	11	21	53
24	85	85	49	5
25	70	70	77	46
26	55	55	16	87
27	40	40	44	39
28	25	25	72	80
29	10	10	11	32
30	84	84	39	73
31	69	69	67	25
32	54	54	6	66
33	39	39	34	18
34	24	24	62	59
35	9	9	1	11
36	83	83	29	52
37	68	68	57	4
38	53	53	85	45
39	38	38	24	86
40	23	23	52	38
41	8	8	80	79
42	82	82	19	31
43	67	67	47	72
44	52	52	75	24
45	37	37	14	65
46	22	22	42	17
47	7	7	70	58
48	81	81	9	10
49	66	66	37	51
50	51	51	65	3
51	36	36	4	44
52	21	21	32	85
53	6	6	60	37
54	80	80	88	78
55	65	65	27	30
56	50	50	55	71
57	35	35	83	23
58	20	20	22	64
59	5	5	50	16
60	79	79	78	57
61	64	64	17	9
62	49	49	45	50
63	34	34	73	2
64	19	19	12	43
65	4	4	40	84
66	78	78	68	36
67	63	63	7	77
68	48	48	35	29
69	33	33	63	70
70	18	18	2	22
71	3	3	30	63
72	77	77	58	15
73	62	62	86	56
74	47	47	25	8
75	32	32	53	49
76	17	17	81	1
77	2	2	20	42
78	76	76	48	83
79	61	61	76	35
80	46	46	15	76
81	31	31	43	28
82	16	16	71	69
83	1	1	10	21
84	75	75	38	62
85	60	60	66	14
86	45	45	5	55
87	30	30	33	7
88	15	15	61	48
89	0	0	0	0
90	74	74	28	41
91	59	59	56	82
92	44	44	84	34
93	29	29	23	75
94	14	14	51	27
95	88	88	79	68
96	73	73	18	20
97	58	58	46	61
98	43	43	74	13
99	28	28	13	54
100	13	13	41	6
101	87	87	69	47
102	72	72	8	88
103	57	57	36	40
104	42	42	64	81
105	27	27	3	33
106	12	12	31	74
107	86	86	59	26
108	71	71	87	67
109	56	56	26	19
110	41	41	54	60
111	26	26	82	12
112	11	11	21	53
113	85	85	49	5
114	70	70	77	46
115	55	55	16	87
116	40	40	44	39
117	25	25	72	80
118	10	10	11	32
119	84	84	39	73
120	69	69	67	25
121	54	54	6	66
122	39	39	34	18
123	24	24	62	59
124	9	9	1	11
125	83	83	29	52

je me suis limité a 125 volontairement c’était juste pour voir le fonctionnement
selon que je change les paramètre et les différent éléments tout ceci se recalcule
a aucun moment je ne vérifie que mon point p fait parti d'une courbe.

[dinobogan]

@anapurna, peux-tu détailler et expliquer clairement ta méthode ? Car je n'ai rien compris à ce que tu faisais...

[anapurna]

salut,

pas de soucis
pour les calcul

j'ai simplement additionné le résultat du modulo par le premier chiffre

par exemple pour Q(d*p)

la premiere ligne on applique pas de modulo
donc la valeur est P => 74
Pour la 2 ligne => (74+74) modulo 89 = 59
Pour la 3 ligne => (59+74) modulo 89 = 44
...
Pour la 111 lignes => (41+74) modulo 89 = 26
donc q = 26
pourquoi 111 car d = 111

on fait a peut pres le meme type d'operation pour C1
la valeur est P => 74
Pour la 2 ligne => (74+74) modulo 89 = 59
Pour la 3 ligne => (59+74) modulo 89 = 44
...
Pour la 87 ligne => (45+74) modulo 89 = 30
pourquoi 87 car k = 87

Pour le calcul de la cle la valeur du debut correspond a la cle public
=> 26
2 => (26+26) modulo 89 = 52
3 => (52+26) modulo 89 = 78
...
87 => (11+26) = 37
pourquoi 87 car k = 87

le message c'est A = 65
donc C2 = M+CLE
=> C2 = (65+37) = 105
pour décrypter
d*C1
on applique la même méthode
1 = C1 = 30
2= (30+30) modulo 89 = 60
3= (60+30) modulo 89 = 1
....
111 = (7+30) modulo 89 = 37

voila le raisonnement que j'ai compris pour pouvoir générer mon fichier ecxel et ainsi
ébaucher un début d’algorithmie afin de mettre en place une cryptographie de type EEC

[dinobogan]

C'est un peu plus clair mais je suis encore perdu sur qui envoie quoi et perdu aussi dans toutes tes valeurs numériques.

Reprenons le formalisme classique en cryptographie. Supposons un dialogue entre Alice et Bob. Ce dialogue est considéré comme public :
Alice et Bob se mettent d'accord publiquement sur la valeur P (=74) et le modulo M (=89).
Alice choisit en secret d_a, effectue Q_a=(d_a*P)modulo M et l'envoie à Bob.
Bob fait de même avec d_b, effectue Q_b=(d_b*P)modulo M et l'envoie à Alice.
Jusque là j'ai bon ?
Alice effectue en secret cle=(Q_b*P)modulo M
Bob effectue en secret cle=(Q_a*P)modulo M
Alice et Bob possède maintenant une clé identique.
C'est ça ?

[anapurna]

C'est un peu plus clair mais je suis encore perdu sur qui envoie quoi et perdu aussi dans toutes tes valeurs numériques.

Reprenons le formalisme classique en cryptographie. Supposons un dialogue entre Alice et Bob. Ce dialogue est considéré comme public :
Alice et Bob se mettent d'accord publiquement sur la valeur P (=74) et le modulo M (=89).
Alice choisit en secret da(d), effectue Qa(Q)=(da*P) modulo M et l'envoie à Bob.
Bob fait de même avec db (k),effectue Qb(C1) =(db*P)modulo M et l'envoie à Alice.
Jusque là j'ai bon ? presque ^^
Alice effectue en secret cle =(Qb*P) modulo M
Bob effectue en secret cle =(Qa*P) modulo M // oui bob crée sa propre clé a partir de la clé public
bob envois le texte crypté a l'aide de sa clé
Alice peut alors décrypter avec sa propre clé (da*Qb) modulo M
Alice et Bob possède maintenant une clé identique.// non deux clé différentes mais toutes les deux sont capable de décoder le texte
C'est ça ?
j’espère avoir été plus clair

[dinobogan]

J'avance, mais je trouve toujours un problème...

Je reprends avec un peu de rigueur pour être sûr qu'on parle de la même chose
Alice et Bob se mettent d'accord sur P et M.
Alice choisit en secret d et effectue Q=(d*P) mod M. Q est envoyé à Bob.
Bob choisit en secret k et effectue C1=(k*P) mod M. C1 est envoyé à Alice.

Bob calcule en secret la clé de cryptage cle=(Q*P) mod M.
Alice calcule en secret la clé de décryptage decrypt=(d*C1) mod M.

Jusque là, c'est ok ?

Faisons une application numérique.
P=74, M=89, d=50, k=48
alors Q=51, C1=81, cle=36, decrypt=45

Je ne vois aucun lien entre la clé de cryptage de Bob et la clé de décryptage d'Alice. Comment Bob fait-il pour coder un message avec sa clé ? Comment Alice fait pour décrypter le message avec sa clé ?

[anapurna]

J'avance, mais je trouve toujours un problème...

Je reprends avec un peu de rigueur pour être sûr qu'on parle de la même chose
Alice et Bob se mettent d'accord sur P et M.
Alice choisit en secret d et effectue Q=(d*P) mod M. Q est envoyé à Bob.
Bob choisit en secret k et effectue C1=(k*P) mod M. C1 est envoyé à Alice.

Bob calcule en secret la clé de cryptage cle=(k*Q) mod M.
Alice calcule en secret la clé de décryptage decrypt=(d*C1) mod M.

Jusque là, c'est ok ?
non vous vous êtes trompé sur la clé de cryptage de bob

Faisons une application numérique.
P=74, M=89, d=50, k=48
alors Q=51, C1=81, cle=36, decrypt=45

Je ne vois aucun lien entre la clé de cryptage de Bob et la clé de décryptage d'Alice. Comment Bob fait-il pour coder un message avec sa clé ? Comment Alice fait pour décrypter le message avec sa clé ?
le liens c'est Q

PS : effectivement j'ai laissé passer une coquille sur le message précédent pour la construction de la cle de BOB