L'énigme du pouvoir magique

gloume · 25-01-2014 11:55:02

Bonjour,

Voici une énigme inspirée d'une problématique professionnelle réelle.
Je la soumets à ce forum car je suppose que la cryptographie pourrait apporter une solution...
Merci pour vos lumières...
-------------------------------------------------------------------------------------------------------------------------
Un pouvoir magique s'obtient dès qu'on prononce trois mots secrets. On désigne ces mots par a, b et c.

- trois personnes X, Y et Z connaissent seulement deux de ces mots: X connaît a et b (mais pas c), Y connaît b et c (mais pas a), et Z connaît a et c (mais pas b)

- chaque personne aimerait connaître les trois mots (et donc découvrir celui qui lui manque)

- chaque personne serait disposée à communiquer un mot qu'elle connaît en échange d'un mot qu'elle ne connaît pas, mais se méfie: en échange du mot qu'elle communiquerait, qui lui garantit que l'autre ne lui donnerait pas un mot bidon?

Voyez-vous un processus qui permettrait d'organiser un échange sécurisé* entre les trois personnes, de sorte qu'elles puissent toutes trois accéder au pouvoir magique?

(Un tel processus pourrait faire intervenir une personne extérieure, à condition de ne pas faire l'hypothèse que c'est une personne de confiance)

(*sécurisé=pas d'arnaque possible)

Dernière modification par gloume (25-01-2014 14:29:52)

nerosson · 25-01-2014 15:27:35

Salut à tous

▼une idée en l'air (mes idées sont toujours des idées en l'air. Il est rare qu'elles retombent...).

freddy · 25-01-2014 17:45:27

Salut,

est ce que chacune des trois personnes sait ce que les deux autres connaissent ?

LEG · 25-01-2014 18:01:21

oui mais X, avant d'obtenir le mot = c, il faut qu'il donne (a) ou (b) , rien ne garantie qu'il obtienne une bonne réponse est donc soit y ou z aura les trois mots..d'après le déroulement de l'énoncé...

donc je pense que X doit donner les bonnes réponses à Y et Z, en échange de C, mais en les intervertissant ce qui lui donne une garantie...
et par la suite Z, donne (a) à Y et Y donne (b) à Z ; X est témoin que le mot a et le mot b, sont bien les bons. et comme les deux mots C, sont identiques: car pour en être sur, Z et Y ne savent pas quel mot est donné à X. dans le cas contraire, X ne donne pas le deuxième mot à Y, qui donc ne pourra pas l'échanger avec Z et 0 partout...

X.....> (a) à Z
Z...> (c) à X
X....> (b) a Y
Y....> (c) à X
Z échange avec Y; leur (a) et (b)

chacun peut vérifier auprès de l'autre..

Fred · 25-01-2014 18:56:34

Salut,

En cryptographie, ce qu'il y a de plus proche, c'est le partage de secret....

F.

gloume · 25-01-2014 20:42:16

freddy a écrit :

Salut,
est ce que chacune des trois personnes sait ce que les deux autres connaissent ?

Oui, chacun sait ce que les deux autres connaissent.

Dernière modification par gloume (25-01-2014 20:43:07)

gloume · 25-01-2014 20:50:03

LEG a écrit :

donc je pense que X doit donner les bonnes réponses à Y et Z, en échange de C, mais en les intervertissant ce qui lui donne une garantie...

Mais Y et Z ne donneront pas c sans être sûrs que X ne les arnaque pas...

gloume · 25-01-2014 22:24:58

Fred a écrit :

Salut,
En cryptographie, ce qu'il y a de plus proche, c'est le partage de secret....
F.

Merci pour l'info. Je ne connaissais pas.
Mais dans les méthodes décrites sur cette page, il faut que quelqu'un connaisse au départ la totalité de l'info, et distribue des infos partielles.
Ici, c'est le contraire: on ne connaît au départ que des infos partielles, et on cherche à construire l'info complète.

LEG · 26-01-2014 14:32:51

Mais Y et Z ne donneront pas c sans être sûrs que X ne les arnaque pas.

c'est bien pour cela que X donne à Z le mot qui manque à Y et inversement il donne à Y le mot qui manque à Z, c'est deux mots étant donc en double, il peuvent donc vérifier que X ne les a pas arnaqué, d'où Z et Y peuvent donner (c) à X.(" étant donné que ce dernier, à bien donné les deux mots justes.")

Ensuite ce n'est plus qu'un échange entre Z et Y, et X est la pour vérifier donc il est le garant: que Z donne bien (a) à Y et que Y donne bien (b) à Z.

White · 26-01-2014 22:27:05

Bonjour,

une première idée qui me vient,
chacun des trois amis entre ses deux mots dans un programme,
à la fin de toutes les entrées, le programme vérifie s'il a bien trois paires de mots identiques :
si c'est le cas, il est très probable que chaque ami ait été honnête, et le programme fournit à chacun la liste des mots,
si ce n'est pas le cas, au moins un des amis s'est montré malhonnête.

gloume · 27-01-2014 00:39:33

LEG a écrit :

Ensuite ce n'est plus qu'un échange entre Z et Y, et X est la pour vérifier donc il est le garant: que Z donne bien (a) à Y et que Y donne bien (b) à Z.

Et pourquoi Z et Y feraient-ils confiance à X? Une fois qu'il aura le pouvoir magique, rien ne l'obligera plus à jouer le moindre rôle de garant, ni à communiquer la moindre info à X ou à Y

Dernière modification par gloume (27-01-2014 00:51:38)

gloume · 27-01-2014 00:43:03

White a écrit :

Bonjour,
chacun des trois amis entre ses deux mots dans un programme

Effectivement, cela peut théoriquement marcher...
Mais concrètement, quel programme utiliser?
En effet, le concepteur du programme pourrait récupérer les trois mots a, b et c, et prendre la poudre d'escampette avec.

LEG · 27-01-2014 10:13:07

@gloume

chaque personne serait disposée à communiquer un mot qu'elle connaît en échange d'un mot qu'elle ne connaît pas, mais se méfie: en échange du mot qu'elle communiquerait, qui lui garantit que l'autre ne lui donnerait pas un mot bidon?

Dans ce cas ton problème est truqué à la base, et cette citation est fausse : chaque personne n'est pas disposée à communiquer.

car même cette solution serait fausse:
ils prononcent en même temps les trois mots magiques X:a, Y:b, Z:c; et si ils ont bien prononcé les trois mots magiques, ils ont le pouvoir de se faire entuber...car Z prononcera en même temps un mot bidon et il aura le loisir de vérifier avec les deux mots prononcé.....LOL
car quelque soit la solution un au moins, aura les trois mots.

Ce qui est étonnant c'est que ton problème indique bien qu'ils obtiennent le troisième mot en échange du mot qui manque.

Or dans ma solution X à bien donné les deux mots qui manquent, par conséquent il ne ment pas , donc en échange Y et Z doivent bien donné (c) à X, même si il n'est pas le garant, qu'est ce qui empêche Y et Z d'échanger les deux mots justes, donné par X.... étant entendu que ces deux mots sont inscrits sur une feuille que seul la personne ayant ce mot peut vérifier, tout comme Y et Z écrivent le mot C sur une feuille qu'ils remettent à X en échange des deux mots justes...qui sont d'abord vérifiés par Y et Z...
X n'est donc plus concerné...seul Y et Z n'ont plus qu'à intervertir leur feuille, donnée par X.

Mais tu pourras aussi me dire, que c'est de l'encre invisible qui s'efface au bout de 4 secondes, de sorte que lors de l'échange entre Z et Y les deux mots disparaissent....etc etc....dans ce cas ont va à la pêche

gloume · 27-01-2014 18:53:37

@LEG

LEG a écrit :

...donc en échange Y et Z doivent bien donné (c) à X, même si il n'est pas le garant, qu'est ce qui empêche Y et Z d'échanger les deux mots justes, donné par X....

Bonjour,
Supposons que X et Y soient complices, et qu'ils ne connaissent tous deux que le mot "a". Ils ignorent "b" et "c".
Ils disent à Z qu'ils connaissent les mots indiqués dans la consigne (X prétend connaître "a" et "b", Y prétend connaître "b" et "c")

Selon ton scénario, X présente le mot "a" à Z , et prétend avoir présenté le mot "b" à Y, ce que Y confirme mensongèrement (puisqu'il est complice de X)

Z donne alors le mot "c" à X, qui s'enfuit à toutes jambes avec son compère Y, à la recherche d'un autre pigeon à plumer du mot "b" selon un scénario analogue.

White · 27-01-2014 22:57:41

gloume a écrit :

White a écrit :
Bonjour,
chacun des trois amis entre ses deux mots dans un programme
Effectivement, cela peut théoriquement marcher...
Mais concrètement, quel programme utiliser?
En effet, le concepteur du programme pourrait récupérer les trois mots a, b et c, et prendre la poudre d'escampette avec.

Mais ils écrivent ensemble un programme en basic tout bête !
Ils le lancent ensemble, et chacun son tour, ils écrivent les deux mots
(donc l'écran n'affiche pas ce qu'ils tapent, et ils cachent le clavier de la main),
quand ils ont tapé tous les trois,
le programme donne sa conclusion...

Je pourrais écrire l'algo là, ça me semble tellement simple....

tibo · 28-01-2014 01:47:30

Salut,

On peut imaginer le programme informatique suivant :
- chacun rentre les deux mots qu'il connait à l'abri des regards
- la machine compare les mots donnés pour vérifier s'ils sont bien par paire
- si oui elle affiche les 3 mots, sinon le programme s’arrête
- dans les deux cas au bout de 5 seconde, elle s'autodétruit en se jetant dans les flammes du Mordor afin d’être sur qu'aucun informaticien puisse récupérer les données.

Il y a une faille si deux personnes sont de mèche. Faille qui n'en est pas vraiment une en fait...
En effet, si deux personnes sont de mèche elle s'échange mutuellement les mots qui leur manque sans se préoccuper de la troisième personne.

LEG · 28-01-2014 09:22:16

@Tibo
Entièrement d'accord.....!
je pense que je vais jeter Gloume dans le Mordor...Au moins on pourra faire l'échange...LOL

gloume · 28-01-2014 09:28:11

tibo a écrit :

Il y a une faille si deux personnes sont de mèche. Faille qui n'en est pas vraiment une en fait...

Voir mon message #14 pour une exploitation de la faille.

Par ailleurs, si il s'agissait par exemple de codes de déclenchement de guerres atomiques, il apparaît comme évident que ce pocessus ne serait pas sufffisant.

J'aimerais trouver une solution qui élimine toute possibilité de s'emparer des codes manquants par la force physique, et qui empêche l'échange si un ou plusieurs des acteurs mentent sur la nature ou la quantité des infos qu'ils possèdent.

D'où le choix de ce forum pour poser ma question... j'imaginais plutôt une solution qui se terminerait par quelque chose du genre: "... et à la fin on a construit un bloc chiffré, que chacun des 3 acteurs peut alors décrypter grâce à sa clé privée"

LEG · 28-01-2014 14:19:23

Et qui la détient cette clé...? une quatrième personne qui est de combine avec un des trois....

Qui construirait ce bloc chiffré...idem, une quatrième personne corrompu...par un des trois..etc.

Si c'était des codes nucléaires, et bien le problème est résolu celui qui déclenche , déclenche automatiquement les autres armes nucléaires adverses...et plus de problèmes...

tu poses un problème avec des conditions précises; puis ensuite tu trouves des prétextes de méfiances ou d'une quatrième personne qui se casse avec le code...dixit: la solution de Wite. Et mieux, celle de tibo; la machine étant programmer pour donner la vérité, cela induit les trois quidam à donner la bonne solution à Big machine si ils ne veulent pas perdre tout espoir, par le suicide de Big machine dans les 5 secondes
..

tibo · 28-01-2014 15:00:34

Re,

Je comprend un peu le point de vue de Gloume ; d'après moi il a essayer de rendre "ludique" un problème qu'il a rencontré IRL afin qu'il soit compréhensible par tous. Mais c'est parfois difficile de transposer un problème réel en un problème mathématique, surtout en essayant de la vulgariser. Il devient alors facile de trouver des failles dans l'énoncé.

Bon du coup, je pense savoir d'où tu veux en venir avec ton problème : essayer d'imaginer un code RSA version 3 personnes.
Je tente un truc. Pour commencer, au lieu de considérer 3 mots, considérons 3 nombres (très grand de préférence, et peut-être premier, à voir...). Chacun publie le produit des deux nombres qu'il connais. Les autres sachant qui connait quels nombres peuvent aisément retrouver le nombre manquant.
Avantage : Une tierce personne qui découvrirait les 3 produits ne pourrait pas retrouver les 3 nombres initiaux.
Inconveniant : ça ne répond pas au problème posé car ça suppose l'honnetété de nos 3 protagonistes.

Dernière modification par tibo (28-01-2014 15:01:00)

LEG · 28-01-2014 16:17:26

pour moi ta réponse est parfaite:

le programme ne ment pas

il donne les trois mots si et seulement si on lui à rentrer les mots juste.

clause de restriction dans le programme:
si au moins une des personnes ne rentre pas les bons mots, le programme l'exclu et donne la bonne réponse aux deux autres, d'où: l'intérêt de ne pas mentir au programme.

car il suffit au programme d'avoir deux personnes qui donne la vérité...et chacun serra dans le doute, si je ment je l'ai dans le B.B.
De ce fait personne n'osera mentir...sous peine d'être exclu bêtement...!

dans ta proposition sur les nombres, il ne faut pas oublier que chacun à un des facteurs, donc qui divise le produit de l'autre, il ne resterait plus qu'à factoriser le reste....pour connaître le troisième nombre...
Avec un ordinateur quantique, je trouve le troisième facteur P....et je me tire, avec les nombres magiques, qui me donnent le résultat du loto....

White · 28-01-2014 19:49:26

Si je comprends bien,
la solution que j'ai proposée est devenue la solution de quelqu'un d'autre ^^

Cela donne super envie d'aider,
surtout pour un énoncé dont la résolution ne correspond pas précisément aux attentes concrète du demandeur : chapeau ! ;)

yoshi · 28-01-2014 20:45:18

Bonsoir,

@White.
LEG a écrit post #19 :

LEG a écrit :

dixit : la solution de White

Il a rendu à White ce qui appartenait à White... ^_^

@+

White · 28-01-2014 21:10:00

Arf, mince, j'ai fauté :

mes excuses sincères, c'est moi le malotru.

Merci yoshi ;)

yoshi · 28-01-2014 21:17:10

Ave,

Bah, j'ai pas vraiment tout lu en détail, peut-être que quelqu'un a donné l'impression de le faire...
Tout le monde peut se tromper.

C'est une discussion intéressante et je te rejoins : j'ai la sensation que notre ami ne donne pas le problème réel...
Mais je peux me tromper ^_^

@+

Forum de mathématiques - Bibm@th.net

#1 25-01-2014 11:55:02

L'énigme du pouvoir magique

#2 25-01-2014 15:27:35

Re : L'énigme du pouvoir magique

#3 25-01-2014 17:45:27

Re : L'énigme du pouvoir magique

#4 25-01-2014 18:01:21

Re : L'énigme du pouvoir magique

#5 25-01-2014 18:56:34

Re : L'énigme du pouvoir magique

#6 25-01-2014 20:42:16

Re : L'énigme du pouvoir magique

#7 25-01-2014 20:50:03

Re : L'énigme du pouvoir magique

#8 25-01-2014 22:24:58

Re : L'énigme du pouvoir magique

#9 26-01-2014 14:32:51

Re : L'énigme du pouvoir magique

#10 26-01-2014 22:27:05

Re : L'énigme du pouvoir magique

#11 27-01-2014 00:39:33

Re : L'énigme du pouvoir magique

#12 27-01-2014 00:43:03

Re : L'énigme du pouvoir magique

#13 27-01-2014 10:13:07

Re : L'énigme du pouvoir magique

#14 27-01-2014 18:53:37

Re : L'énigme du pouvoir magique

#15 27-01-2014 22:57:41

Re : L'énigme du pouvoir magique

#16 28-01-2014 01:47:30

Re : L'énigme du pouvoir magique

#17 28-01-2014 09:22:16

Re : L'énigme du pouvoir magique

#18 28-01-2014 09:28:11

Re : L'énigme du pouvoir magique

#19 28-01-2014 14:19:23

Re : L'énigme du pouvoir magique

#20 28-01-2014 15:00:34

Re : L'énigme du pouvoir magique

#21 28-01-2014 16:17:26

Re : L'énigme du pouvoir magique

#22 28-01-2014 19:49:26

Re : L'énigme du pouvoir magique

#23 28-01-2014 20:45:18

Re : L'énigme du pouvoir magique

#24 28-01-2014 21:10:00

Re : L'énigme du pouvoir magique

#25 28-01-2014 21:17:10

Re : L'énigme du pouvoir magique

Réponse rapide

Pied de page des forums