problème de crypto

[akntn]

Bonjour,

Petit problème de crypto. La théorie interdit que Alice et Bob puissent échanger un nombre sans que Eve puisse finir par l'intercepter. L'algorithme qui suit donne le change.
Saurez-vous trouver l'erreur ?

A : a, b
B : c, d
Nombres de cryptage : e,f,g,h,i.

A : a + e = j ---> B
B : j + c + f = k ---> A
A : k - e + b + g = l ---> B
B : l - f + d + h = m ---> A
A : m - g - a + i = n ---> B
B : n - h - c = o
A : m - g + a = p ---> B
B : p - h - o = q ---> A
A : q - a + i = r


NB : a, b, c, d, ... sont secrets, évidemment. Seuls les nombres précédant la flèche de renvoi sont publics.
-----

[akntn]

Bonjour,

Je me suis rendu compte que mon message a été supprimé. Peut-être me suis-je mal exprimé ?
L'algorithme suivant permet d'échanger secrètement un message ou une clé entre Alice et Bob, uniquement par additions et soustractions. Le message (C) est décrypté par Alice. Il y a probablement (peut-être pas) une faille quelque part. Jusqu'à présent, personne n'en a trouvé. Il me semble que ce problème est censé intéresser les amateurs de cryptographie, je me permets donc de le republier.



A : a, b
B : c, d
Nombres de cryptage : e,f,g,h,i.

A : a + e = j ---> B
B : j + c + f = k ---> A
A : k - e + b + g = l ---> B
B : l - f + d + h = m ---> A
A : m - g - a + i = n ---> B
B : n - h - c = o
A : m - g + a = p ---> B
B : p - h - o = q ---> A
A : q - a + i = r (a + c)


NB : a, b, c, d, e, f, g, h, et i sont secrets, évidemment (de même que les totaux o et r). Seuls les nombres précédant la flèche de renvoi sont publics (j,k,l,m,n,p,q).

[albanxiii]

Bonjour,

Je me suis rendu compte que mon message a été supprimé. Peut-être me suis-je mal exprimé ?

Ce message là : https://forums.futura-sciences.com/m...al-de-cle.html ?

[akntn]

Bonjour,
Tout à fait, et effectivement il n'est pas clair, je n'ai pas précisé r = a + c.
Merci.

[A voir en vidéo sur Futura]

[albanxiii]

Bonjour,

J'ai fusionné les discussions, pour éviter les doublons.

albanxiii, pour la modération.

[Paraboloide_Hyperbolique]

Bonjour,

A première vue, je dirais que cela ressemble à du Diffie-Hellman* en moins pratique (plus de communications entre Bob et Alice pour partager un clef secrète).

*https://fr.wikipedia.org/wiki/%C3%89...Diffie-Hellman

[akntn]

Bonjour,

Eh bien non, pas du tout, mais c'est vrai qu'on a plus d'échanges entre A et B (7), bien que je pense pouvoir faire baisser ce chiffre à 5 ou même 4. L'énorme différence est dans l'utilisation exclusive d'additions et de soustractions (une addition est moins coûteuse qu'une multiplication). Diffie-Hellman utilisent des puissances énormes (c'est du lourd comme matériel). Mais ce qui différencie du tout au tout les deux systèmes est le fait que DH passe par une formule, donc par une seule solution possible de déchiffrage (les deux nombres choisis par A et B), ce qui rend le système vulnérable à l'ordinateur quantique. La solution de l'algorithme présent est soit un message direct, soit une clé. Si C est un message, il est détectable par l'ordinateur quantique. Mais, si C est une clé, on se trouve dans la situation du masque jetable : il y a un nombre astronomique de solutions possibles non triviales (donnant toutes un message clair).

[akntn]

En fait, message ou clé, c'est pareil. Autant pour moi.

[Paraboloide_Hyperbolique]

Bonsoir,

Ayant un peu de temps à perdre, j'ai fait quelques calculs élémentaires et je pense avoir trouvé une faille dans votre système (à vérifier). Voici les calculs:

En partant de votre schéma et en mettant en gras ce qui est connu par l'attaquant:

A : a + e = j ---> B
B : j + c + f = k ---> A
A : k - e + b + g = l ---> B
B : l - f + d + h = m ---> A
A : m - g - a + i = n ---> B
B : n - h - c = o
A : m - g + a = p ---> B
B : p - h - o = q ---> A
A : q - a + i = r (a + c)

Etape 1: expression des valeurs connues en terme des inconnues
j = a + e
k = a + e + c + f
l = a + c + b + g + f
m = a + c + b + g + d + h
n = c + b + d + h + i
p = 2a + c + b + d + h
q = 2a + c - i

des deux dernières lignes on déduit:

2a = p - c - b - d - h = q - c + i -> i = p - q - b - d - h

D'autre part on a:

n = c + b + d + h + i -> n = c + p - q

D'où c = n - p + q

Donc, si mon raisonnement est correct, on trouve au moins un secret de Bob (le nombre c) et par voie de conséquence le nombre f, via j et k. Même si mes calculs sont corrects, je ne sais pas encore si cela fait tomber tout le système, mais ce serait à vérifier.

[akntn]

Bonjour, bravo (champagne), j'appréhendais la faille. En l’occurrence, c'est bien C qu'il faut trouver, et cela casse le système. Je vais proposer un algo un peu différent, avec deux calculs sans échange au lieu d'un seul, mais sans illusion.
Merci d'avoir pris le temps.

[jacknicklaus]

Celà montre l'intérêt du Diffie-Helman : il est très compliqué d'inverser les calculs basés sur une exponentiation discrète. Alors qu'avec un système d'équations basées sur des additions ...

[Paraboloide_Hyperbolique]

Bonjour, bravo (champagne), j'appréhendais la faille. En l’occurrence, c'est bien C qu'il faut trouver, et cela casse le système. Je vais proposer un algo un peu différent, avec deux calculs sans échange au lieu d'un seul, mais sans illusion.
Merci d'avoir pris le temps.

Au lieu d'essayer des algorithmes au petit bonheur la chance (ce qui a peu de chance de fonctionner), je vous recommande de vous documenter sur ce qui se fait dans le domaine. La cryptographie peut s'avérer être un domaine de recherche très intéressant (autant du point de vue mathématique que des applications).

Par exemple, si ce n'est pas déjà fait, voyez comment fonctionne Diffie-Hellman (ne serait-ce que la page wikipédia) et qui montre l'intérêt d'avoir une fonction très difficile à inverser (ce que vous ne pouvez avoir avec juste des additions et des soustractions).

[akntn]

Merci, je connais bien Diffie-Hellman, mais c'est parfois plus drôle d'expérimenter des chos.es nulles et légères que d’assimiler des choses lourdes et efficaces.