Echange d'une clé cryptographique entre deux correspondants

[akntn]

Bonjour, je soumets ici un protocole inédit d'échange de clé cryptographique entre deux correspondants. Merci d'avance pour vos commentaires et critiques.

CRYPTO

Description
Echange d'une clé cryptographique entre deux correspondants.
1) Théorie
Exploiter l'imprécision présente dans l'approximation d'un résultat, ici une partie d'un très grand nombre décimal transformé en entier.
2) Protocole pour Alice et Bob
Choisir un nombre de 30 chiffres (ou plus), impair (pourquoi pas premier, ce qui limite la friabilité)
DIVISER par une puissance de 2 (publique) de telle façon que le résultat soit un nombre décimal tronqué (correspondant à un peu plus que la moitié, dans la pratique 60 décimales après la virgule pour g = 2^128).
Changer en nombre entier et multiplier par 2 (clé secrète)
Ajouter le nombre initial (publique).
Le nombre obtenu n'est divisible ni par X (nombre initial) ni par K (K étant une constante liée au choix de g, qui apparaît lorsque la division de X par g est exacte).
X = nombre initial d'Alice (secret)
A = clé secrète
(X + A) = publique, envoyé à l'adresse e-mail de Bob
Y = nombre initial de Bob (secret)
B = clé secrète
(Y + B) = publique, envoyé à l'adresse e-mail d'Alice

CLE PARTAGEE :
A * (Y + B)
B * (X + A)
Comme la division n'est pas juste, les deux nombres obtenus ne sont pas totalement identiques.
La clé est constituée par la partie commune à Alice et Bob, qui doivent s'entendre sur un nombre de chiffres déterminé à l'avance (par ex 60).

Exemple :
X = 709810552740327708793540951763
Y = 639900413154483921407570692127
g = 2^128

Calcul d'Alice :
X / g =
2.0859457372507514734450205306 584126456400490565602890113262 481957147717879011688396628798 614074185024946928024291992187 5 × 10^-9
On retire 61 décimales :
2.0859457372507514734450205306 584126456400490565602890113262 ...
on change en entier :
E = 208594573725075147344502053065 84126456400490565602890113262
On calcule A = E * 2 :
417189147450150294689004106131 68252912800981131205780226524
X + A =
417189147450150294689004106138 78063465541308839999321178287

Calcul de Bob :
Y / g =
1.8804983018798591071535222395 826307972747199199386197575329 613905324830496217005521009113 522268307860940694808959960937 5 × 10^-9
on retire 61 décimales :
1.8804983018798591071535222395 826307972747199199386197575329 ...

on change en entier :
E = 188049830187985910715352223958 26307972747199199386197575329
On calcule B = E * 2 :
376099660375971821430704447916 52615945494398398772395150658
Y + B =
376099660375971821430704447922 92516358648882320179965842785

Calcul de la clé :
Alice : A * (Y + B) =
156904696668542756429389984504 594021789642850534395991004561 468145499729008115067263257050 6234641349557409879871029340
Bob : B * (X + A) =
156904696668542756429389984504 594021789642850534395991004561 468145499729008115067263257025 1530841348082346717443362846

C (clé, section commune)
156904696668542756429389984504 594021789642850534395991004561 4681454997290081150672632570

Eve n'a d'autre choix que de procéder à une recherche brute de X ou Y. Elle peut aussi chercher un X tel que K * X = (X + A), avec (X + A) débutant par la série : 4171891474501502946890041061 ... Ce qui est improbable compte tenu de la grandeur du nombre.
Différences avec Diffie-Hellman :
- Economique, peu coûteux en nombres (pas de puissances, pas d'énormes nombres premiers)
- Pas de calcul possible, pas de prise à l'ordinateur quantique
- Simplicité d'utilisation, un PC individuel suffit au protocole

Modèle réduit d'exemple :
g = 2^3
Alice choisit X = 7151820111
Elle divise par g : 7151820111 / 8 = 893977513.875
Elle change le résultat en entier: 893977513.875 * 1000 = 893977513875
Elle enlève un chiffre à droite, le 5, et obtient : 89397751387
Elle calcule A:
A = 89397751387 * 2 = 178795502774
Elle ajoute X : (X + A) = 185947322885. Ce nombre est publique et est envoyé à Bob.

Bob choisit Y = 111212021
Il divise par g : 111212021 / 8 = 13901502.625
Il change le résultat en entier : 13901502.625 * 1000 = 13901502625
Il enlève un chiffre à droite, le 5, et obtient : 1390150262
Il calcule B :
B = 1390150262 * 2 = 2780300524
Il ajoute Y : (Y + B) = 2891512545. Ce nombre est publique et est envoyé à Alice.

Alice calcule la clé commune :
A * (Y + B) = 516 989 439 260 603 299 830
Bob calcule la clé commune :
B* (X + A) = 516 989 439 253 562 691 740

Partie commune de la clé : 516 989 439
516989439 est la clé

Il est impossible de retrouver X, A, Y ou B par le calcul si on ne connait pas ces nombres.

NB : ici, Y est plus petit que X. Evidemment, dans cet exemple, la clé est très courte et la partie décimale se reconstitue aisément.

YJCC
-----

[Deedee81]

SAlut,

Je ne me prononce pas sur la méthode mathématique.

Juste sur le coût :

Eve n'a d'autre choix que de procéder à une recherche brute de X ou Y [...]
Différences avec Diffie-Hellman :
- Economique, peu coûteux en nombres (pas de puissances, pas d'énormes nombres premiers)

Il faut quand même noter que si les méthodes DH utilisent des clefs énormes c'est justement parce que le calcul brute est devenu réalisable sur des nombres plus petits (bon pas vraiment avec un simple PC, mais ça peut se faire sur grosse bécane).
Comme tu le dits, Eve devrait faire un calcul brut mais cela signifie là aussi que pour éviter ça il faudrait des nombres énormes.
Je ne vois pas trop pourquoi cette méthode éviterait ça (mais un détail peut m'avoir échappé).

[akntn]

Bonjour Deedee, merci de ton commentaire. La différence réside essentiellement dans le fait que je n'utilise pas de puissances. Entre X (30 chiffres) et A ^ X (30 chiffres), il y a un abîme. D'où l'économie de matière numérique. De plus, il y a trop de paramètres connus dans DH (3). Un régal pour l'ordinateur quantique.

[akntn]

Bonjour,

Je me permet d'ajouter ce message non pas pour faire remonter la discussion mais parce que
j'ai besoin que le moteur de recherche trouve la discussion avec le mot clef "cryptographie" => voilà qui est fait.
(après conseil et accord de Deedee81 par MP)

Merci, Akntn

[A voir en vidéo sur Futura]

[akntn]

Salut Flyingbike, merci de ta précieuse collaboration.
Bon flyingbike

Yann JC Coudert (akntn), auteur du présent protocole.

[Denis10100]

On divise, on multiplie, bref ça revient à multiplier par une constante. Dans l'exemple simplifié, la constante est égale à 26.
Donc en connaissant (X + A) = 185947322885 (donnée publique) on divise par 26 et on obtient quasiment le X supposé secret : 7151820110,9615384615384615384 615
Inversement, (Y + B) = 2891512545, on divise par 26 et on obtient le Y à quelques poussières près : 111212020,96153846153846153846 154

[Denis10100]

Et pour la version longue, la constante est égale à 58774717541114375398436826862
(désolé pour le délai, ça dépassait les capacités de ma calculatrice)

[akntn]

Bonjour, enfin un commentaire intéressant. Tu peux peut-être me dire comment tu calcules ta constante à partir de (X + A) ?
Merci.

[akntn]

D'accord, c'est gagné. Echec et mat (hs).

[Denis10100]

Il y a deux façons de calculer :
1) Sachant que c'est quasi une constante (à l'arrondi près), faire le rapport (X + A) / X à partir d'un cas isolé, réel ou fictif.
2) Faire le calcul à partir des données du protocole (données connues de tous) :
Constante = 1 / g * 10^n * 2 + 1 (n étant le nombre de chiffres qu'on garde après la virgule)
Modèle réduit : 1 / 8 * 100 * 2 + 1 = 26
Premier exemple : 1 / 2^128 * 10^67 * 2 + 1 = 58774717541114375398436826862, 112...

[akntn]

J'ai été confronté à ce problème de constante au début. En fait, la seule constante vraiment dangereuse pour retrouver X ou Y est la première, car c'est un nombre entier qui divise exactement (X + A) ou (Y + B), le quotient étant X ou Y.

C = 1 / g * 10^k * 2 (+ 1), où k est le nombre total de décimales.

Avec g = 8 par exemple, cette constante initiale est 250 (+ 1). Les constantes qui apparaissent en éliminant des décimales sont plus inoffensives, car ce sont des nombres décimaux dont la traduction entière ne permet pas de trouver X ou Y dans leur totalité (la partie décimale étant fonction du X et Y choisis). C'est d'ailleurs le vrai point de départ de cet algo (l'idée du troncage).
Par exemple, les deux autres constantes avec g = 8 (troncage de 1 et 2 décimales) sont, comme tu l'as trouvé, 25 (+ 1) et 2,5 (+ 1).
Evidemment les petites constantes tronquées donnent des résultats pour les petits nombres, pour les grands c'est autre chose. Si tu multiplies par X ou Y la grande constante tronquée que tu as trouvée pour l'exemple 1, tu n'obtiens jamais (X + A) ou (Y + B) en totalité, et plus le troncage augmente, moins il est facile de retrouver ces nombres intégralement.

[Denis10100]

Le danger, ce n'est pas de trouver (X + A) à partir de X, puisque (X + A) est connu, ou sinon il suffit de suivre le protocole pour le calculer (c'est ce que fait Alice). La faille est dans le fait de retrouver X (secret) à partir de X + A (public). Et la division permet bien de le retrouver, à une unité près.

[akntn]

Vérification faite. Echec et Maths cette fois-ci. Et merci pour ta participation.
Akntn

[akntn]

Il est possible à mon sens de reprendre l'idée en modifiant quelques données.
A bientôt pour une nouvelle partie !
Akntn

[akntn]

Une première solution consiste à diviser X et Y par un g inférieur à X et Y, et à supprimer la partie entière pour casser la constante. On multiplie la partie décimale de Y / g par X et la partie décimale de X / g par Y. On prend la séquence finale du résultat (- 75) qui est la clé (après s'être mis d'accord sur un nombre de chiffres). La longueur de la clé augmente avec la grandeur de g.
Akntn

[akntn]

La deuxième solution n'expose plus g qui devient secret. La partie décimale est multipliée par 2 puis ajoutée à X et Y. Alice et Bob choisissent un g assez grand pour que la clé soit suffisamment longue. Même si Eve découvre un g, elle ne dispose d'aucun élément pour retrouver X et Y, l'opération A / X et B / Y donnant des quotients indépendants de la constante liée à g.
Akntn