Une homothétie à sens unique ?

[oss117]

Bonjour à tous,

Je me pose une question :

Une transformation peut-elle présenter simultanément les deux propriétés suivantes :

• L’homothétie.
• Non réversible (ou à sens unique). Si y = f(x), alors on ne peut connaître x même si l’on connait f et y.

Autrement dit, existe-t-il des homothéties « à sens unique »;)?

Note : je n’ai pas fait de mathématique depuis 15 ans;)!

Merci,

Denis

[oss117]

UPDATE: je pense que cela n’existe pas. En effet, une homothétie ne fait que « changer la taille » (agrandir ou rétrécir). Donc, peu importe ce que l’on fait passer dans la transformation, ce qui en ressort est toujours à l’image de ce qui a ce qui y est entré. Et si on connaît la transformation, alors on connaît le « facteur de changement de taille », et donc on est capable de retrouver le vecteur dont on connaît « la transformée ».

Toutefois, mes connaissances en mathématiques sont faibles... et je ne suis pas certain que mon raisonnement soit valable.

[Robic]

Bonjour ! Tu as raison. L'homothétie est en effet un changement de taille. En jargon mathématique, ta question revient à se demander si, connaissant une homothétie, on connaît obligatoirement sa réciproque. La réponse est oui parce que sa réciproque est l'homothétie de rapport inverse et de même centre (par exemple la réciproque d'un doublement des dimensions, c'est une division par deux des dimensions).

Par contre il existe des transformations qui admettent une réciproque (bien définie, unique), mais qui sont telles que si on ne la connaît pas, on ne peut pas la retrouver en un temps plus court que l'âge de l'univers même avec des super-ordinateurs. Ce sont ces fonctions qui servent en cryptage : connaître le code, c'est connaître en quelque sorte la réciproque d'une certaine transformation.

[oss117]

Bonjour ! Tu as raison. L'homothétie est en effet un changement de taille. En jargon mathématique, ta question revient à se demander si, connaissant une homothétie, on connaît obligatoirement sa réciproque. La réponse est oui parce que sa réciproque est l'homothétie de rapport inverse et de même centre (par exemple la réciproque d'un doublement des dimensions, c'est une division par deux des dimensions).

Par contre il existe des transformations qui admettent une réciproque (bien définie, unique), mais qui sont telles que si on ne la connaît pas, on ne peut pas la retrouver en un temps plus court que l'âge de l'univers même avec des super-ordinateurs. Ce sont ces fonctions qui servent en cryptage : connaître le code, c'est connaître en quelque sorte la réciproque d'une certaine transformation.

Merci Robic,

C’est intéressant.

Je pense à autre chose : existe-t-il des transformations « à sens unique » qui n’engendrent pas de « perte d’information » lors de la transformation;)?


Je clarifie un peu ma pensée, car je ne sais pas si je suis clair :

Transformation à « sens unique » : si y = f(x), alors même si l’on connaît y et f, alors on ne peut pas connaître x.

Une transformation de type MD5 est « forcément à sens unique », car, lors de la transformation, il y a « perte d’information ». En revanche, une transformation de type ZIP « conserve l’information » (mais elle n'est pas à sens unique).

Merci,

Denis

[Robic]

Transformation à « sens unique » : si y = f(x), alors même si l’on connaît y et f, alors on ne peut pas connaître x.

Dans ce modèle, est-ce qu'on peut envisager une transformation telle que pour chaque image y, il existe un x de départ unique et bien déterminé, mais c'est juste qu'on ne peut pas le connaître ?

Parce que je vois deux choses différentes :

- On ne peut pas connaître x parce qu'il n'est pas défini : c'est le cas des transformations avec perte d'information, et c'est justement pour ça qu'on ne peut pas le définir. Si pour une image y on a plusieurs choix de x de départ, on ne peut en effet pas connaître le x. Exemple : on ne peut pas reconstituer une scène tridimensionnelle à partir d'une photo parce qu'une projection n'est pas injective (pour une image y, il peut exister plusieurs x de départ). Mais si, de plus, on veut une transformation sans perte d'information, donc pour qui un y donné est l'image d'un x bien défini, en théorie on peut forcément remonter au x. En théorie. (Si y=f(x), il suffit d'écrire x=f'(y) où f' est la réciproque.)

- On ne peut pas connaître x parce que le calcul est impossible, ou irréalisable. Dans ce cas, ça correspond aux procédés de cryptage dont je parlais plus haut, qui sont bien des transformations sans perte.

C'est ce que je comprends du truc en tout cas.

[oss117]

Merci Robic,

J’aime beaucoup l’analogie avec la photographie. C’est très parlant.

Effectivement, dans une transformation dite « à sens unique » de type MD5 (ou SHA), qui entraine une « perte d’information », plusieurs valeurs distinctes « en entrées » (de la transformation) peuvent avoir la même transformée.

Autrement dit : il existe des valeurs a et b distinctes telles que MD5(a) = MD5(b).

Mais, ce qui rend ces transformations remarquables c’est qu’on démontre que l’on ne peut pas calculer la transformation réciproque. Note: je n’ai pas lu la démonstration, et je ne suis pas sûr d’être en mesure de la comprendre. Autrement dit:

Si r = MD5(a) = MD5(b) = MD5(c).

On ne peut pas calculer MD5’ telle que:

MD5’(r) = a | b | c (et peut-être une infinité de valeurs)

Note: j’utilise la notation utilisée dans les langages de programmation « | = OR » (OU logique).

Note: dans le cas de la transformation MD5, un résultat (r, dans l’exemple) donné peut, a priori, être associé à une infinité d’entrées (a, b, c, dans l’exemple).

Note: la transformation MD5 présente la propriété intéressante suivante: la probabilité pour que MD5(a) = MD5(b) est extrêmement faible (ce qui en fait une fonction intéressante en informatique).

Lorsque vous dites que, pour les transformations cryptographiques, on ne peut pas calculer la transformation réciproque : est-ce démontré;)(mathématiquement);)?

J’utilise des algorithmes de chiffrage, car je travaille dans le secteur de l’informatique. Par exemple, j’utilise 3DES (clé sécrète, chiffrage par bloc) ou RSA (clé public, chiffrage par bloc).

Prenons le cas de 3DES, par exemple:

Si r = 3DES(x, clé)

Si je connais r et clé, alors je peux connaître x (il me suffit d’appeler la fonction de déchiffrage). Donc, a priori, il existe une transformation « inverse ».

Note : s’il n’existait pas de transformation « inverse », les fonctions de chiffrage ne serviraient à rien.

Par conséquent, je suppose que vous parlez d’autres fonctions de chiffrage (autres que 3DES, IDEA, BlowFish, ElGamal, RSA...).

Denis

[Robic]

Lorsque vous dites que, pour les transformations cryptographiques, on ne peut pas calculer la transformation réciproque : est-ce démontré;)(mathématiquement);)?

Je ne connais pas les détails, mais il me semble qu'on utilise exprès des fonctions mathématiques qui ont les propriétés qu'il faut, donc à mon avis c'est démontré (ce serait risqué s'il y avait un doute).

J’utilise des algorithmes de chiffrage, car je travaille dans le secteur de l’informatique. Par exemple, j’utilise 3DES (clé sécrète, chiffrage par bloc) ou RSA (clé public, chiffrage par bloc).

Donc tu t'y connais mieux que moi ! C'est moi qui devrais te poser des questions...

[oss117]

Salut Robic,

Oui, je connais très bien l’aspect « pratique » des fonctions cryptographiques : je sais les utiliser à bon escient.

Je connais un peu la théorie... Mais je ne suis pas un mathématicien.

En revanche, je suis suffisamment bien informé et suffisamment intelligent pour savoir et comprendre que tous les algorithmes standards disponibles (AES, 3DES, IDEA...) ne sont pas sécurisés si l’on adopte le point de vue des services de l’état.

J’ai mis au point des algorithmes « faits maison », qui, de mon point de vue, sont très sécurisés. En revanche, n’étant pas mathématicien, je ne peux pas en apporter une preuve formelle. Je ne peux que fonder mon opinion sur des considérations liées à la physique (thermodynamique...). Bref, je raisonne par analogie, ce n’est pas une démonstration formelle.

Cordialement,

Denis

[jwtdd]

Salut, une fonction de hachage comme MD5 est à sens unique, le but n’étant pas te chiffrer une information mais d'en créer une "signature", c'est la principale raison pour laquelle lorsqu'on perds un mot de passe, si il a été stocké par sa signature, on ne peut pas le retrouver, on peut juste en créer un autre.
Après si le mot de passe est petit, on peut le retrouver en essayant de hasher toute les combinaisons jusqu'a qu'on retrouve le hash qui correspond.
Sachant que le hash a une taille fixe mais que la taille total des données à hasher n'est pas limité, il existe une infinité de collisions, ça veux dire que l'on peut retrouver une combinaison donnant ce hash qui n'a rien à voir avec la combinaison utilisé pour générer ce hash.
En bref la fonction de hashage n'est bonne que pour vérifier l'intégrité de données ou pour stocker des mots de passes sans vraiment les stocker.