Cryptage
Salut à tous !
Je sais pas trop si je dois poster ici ou bien dans maths du supérieur.. dsl
Admettons que l'on veuille créer une sorte d'algorithme de cryptage. Comme peut-on être sûr (je crois que c'est impossible, mais comment peut-on avoir une probabilité quasimment nulle) qu'il n'y a pas deux images possibles d'un même mot, par exemple ?
Cordialement,
Thor HDA
il faut que pour tout element de ton ensemble de départ, son image par la fonction utilisé soit unique. je pense que ca doit suffire ( à verifier )
Ouais je sais XD mais, par exemple, si ta fonction de cryptage utilise la fonction reste() d'une division euclidienne, tu fais comment ?
Salut,
en fait je ne vois pas tellement pourquoi ça te pose un problème qu'un même mot puisse être codé de plusieurs sortes. C'est même plutôt une bonne nouvelle du moment que dans le sens de la traduction, tu es certain de récupérer le bon mot. Si ton (a) se code un coup en AB et un autre en AC et que de toute façon tu es sûr de traduire en (a), c'est plutôt un avantage fasse à des attaques par études de fréquences.
Là où ça devient plus complexe, c'est qu'il faut pouvoir retrouver le mot. Mais quand on regarde le système RSA (qui utilise les restes comme tu veux le faire), on se rend compte qu'il est possible de retrouver le mot d'origine avec certitude moyennant quelques calculs et l'utilisation d'une clé.
Cordialement,
Ecthelion
Salut !
Pour la division euclidienne c'était avant tout un exemple.
"en fait je ne vois pas tellement pourquoi ça te pose un problème qu'un même mot puisse être codé de plusieurs sortes. C'est même plutôt une bonne nouvelle du moment que dans le sens de la traduction, tu es certain de récupérer le bon mot."
>> non justement mon problème c'est : comment être sûr que plusieurs mots n'ont pas la même image.
ex:
a -> FG
b -> FG
??? je crois que c'est impossible, mais comment faire un calcul de proba sur ça ?
Salut,
alors avoir A->FG et B->FG est possible en fonction. Et justement le reste de division euclidienne est l'exemple rêvé :
Imagine une fonction f qui à X associe Y avec Y le reste de la division euclidienne de X par 26. Tu as donc 26 résultats possibles pour Y : [0 ; 25].
Et tu décides alors que A correspond à 0, B à 1, C à 2, etc.
Tu prends X1=28 et X2=54.
f(X1) = 2 et f(X2) = 2
Donc X1 et X2 se traduisent par "C".
Moralité tu as un problème : quand tu as C, comment savoir s'il faut le traduire en X1 ou en X2 voire même un X3 = 80 ? Là ton chiffre est mauvais car inutilisable. Le chiffre RSA résoud ce problème grâce à des théorèmes et des puissances mais aussi une clé, la faille du chiffre RSA. Faille comblée par le fait que la clé est très très longue et donc difficile à trouver.
Mais quoi qu'il en soit, il ne faut pas démontrer par des probabilités car 99% ne suffisent pas. En fait, on se moque de savoir si f est surjective ou non. Par contre, il est impératif que f soit injective (voire bijective si f est surjective, mais ce n'est pas essentiel).
Et la démonstration de l'injectivité d'une fonction passe par :
montrer que si f(x)=f(y) alors x=y.
Mais à 16 ans, il n'est pas sûr que tu es encore les outils pour le faire.
Cordialement,
Ecthelion
PS : si tu veux citer tape [QUOTE] puis ton message et [ /QUOTE] (sans l'espace entre [ et /, je l'ai mis pour que les instructions apparaissent)
J'avais la flemme de citer, tkt je connais bien le bbcode...
Sinon je pense que c'est faisable, tout de même. Et puis on n'a qu'à utiliser directement une fonction bijective ce sera plus simple...
par contre, pour utiliser reste(), je connais pas le statut de cette 'fonction'... ça doit un peu être comme '!' non ? Je ne me suis jamais intéressé à ça.
Pour ton injectivité je vais réfléchir tt de suite - j'ai pas fait de maths depuis deux mois XD...
Houlà mais ou bien je suis bête & j'ai pas vu un truc ou bien c'est simple XD :
Pour avoir : "Si f(x)=f(y) alors f(x)=f(y)" il faut f strictement croissante ou strictement décroissante, d'après le théorème des valeurs intermédiaires...montrer que si f(x)=f(y) alors x=y, dans ce cas f est injective
tu veux que je le démontre aussi
