Discussion :

[Tagashy]

bonjour
je vous explique mon problème je suis actuellement en train de développe un petit logiciel de cryptage qui se base sur la formule

c=(a*x+b)%95

je vais toujours avoir a et b qui font partie de la clé de cryptage choisi par l'utilisateur (j'ai exclue les valeur 19 et 5 des valeur possible de choix) et x correspond au numéro du caractère à encoder

mon problème vient au niveau du décryptage en effet d’après mes recherche il n'y as pas de formule fixe pour faire l'inverse donc je me suis axée vers un moyen de récupérer l'inverse du modulo ( pas sur que ce soit exactement l'inverse)

mon objectif est a partir de c, a et b récupérer x

mais malheureusement moi et les math ça as toujours fait deux donc je vous demande votre aide

merci d'avance

Comandant Chaos

[plegat]

Salut

mon objectif est a partir de c, a et b récupérer x

Impossible.
Par exemple, 24%7=3... et 10%7=3 aussi... du coup, à partir de 3, on doit tomber sur 24 ou sur 10?

Sinon pour répondre à ta question, l'inverse de ton modulo revient à utiliser la formule:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

x=c+k*95

avec k entier>0... à toi de choisir quelle valeur de k tu veux prendre!

[Tagashy]

je suis d'accord avec toi qu'avec un modulo on pouvait obtenir plusieurs fois le même résultat c'est pour ca que a et b dans ma formule je les garde vu que x est contenue entre 1 et 94 je pensais qu'on pouvait remonter

pour ce qui est du

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

x=c+k*95

en gros si je veux remonter a c et avoir une valeur corecte il faut que je fasse un algorithme de ce genre ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
saisir c
a=1
b=1
 
k=1
 
valCryp=(a*c+b)%95
tant que c!=(valCryp+k*95)
k=k+1
fin tant que
afficher k

et le faire pour chacune des valeur possible de c (1 à 94) ?

[plegat]

en gros si je veux remonter a c et avoir une valeur corecte il faut que je fasse un algorithme de ce genre ?

Je croyais que tu voulais remonter à x à partir de c, a et b? Je persiste, à moins de borner l'intervalle que peut parcourir x, pas moyen de le retrouver...

[Tagashy]

vu que j'ai l'impression de m’être mal exprimer (et les lettres pour le nom des variable c'est pas top)
donc je réexplique
etape 1 cryptage
l'utilisateur va saisir crypt1 et crypt2 qui correspondent a la clé de cryptage pour crypt1 19 et 5 sont interdit ( valeur comprise entre 0 et 94 pour les deux)
l'utilisateur va saisir un caractere sur le clavier j'en ai compter 95 (donc on peut saisir que des valeur entre 0 et 94 je crois que c'est ça que tu entant par borné)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
saisir crypt1
saisir crypt2
saisir caracSaisie
resultat=(crypt1*caracSaisie+crypt2)%95

etape deux decryptage
on dispose de crypt1 et crypt2 (les meme que lors du cryptage)
on dispose de caracCrypt (qui correspond a resultat dans l'etape 1)

mon but est donc de récupérer caracSaisie(de l'etape 1) à partir de ce qui nous est fournis

donc je pensais que si on dispose justement de tous ces chiffres je pourrais surement remonter aux caractère avant qu'il soit crypter
et vu que le modulo peut donner deux fois la même valeur mon seul moyen de différencie deux valeur du caractère codée est la clé de cryptage
je pensait cherche toute les valeur qui permettent de récupéré le caractère originel
en gros

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
saisir caracTest             (c'est la même valeur qu'un utilisateur pourrait saisir pour caracSaisie dans l’étape 1  )
crypt1=1
crypt2=1
rexultatCrypt=(crypt1*caracTest+crypt2)%95
tant que caractTest!=(resultatCrypt+solution*95)
solution=solution+1
fin tant que
afficher solution

( je me demande si en fonction de crypt1 et crypt2 la valeur de solution ne changerais pas ?)
Merci de ton aide

[Invité]

Salut,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
saisir caracTest             (c'est la même valeur qu'un utilisateur pourrait saisir pour caracSaisie dans l’étape 1  )
crypt1=1
crypt2=1
rexultatCrypt=(crypt1*caracTest+crypt2)%95
tant que caractTest!=(resultatCrypt+solution*95)
solution=solution+1
fin tant que
afficher solution

( je me demande si en fonction de crypt1 et crypt2 la valeur de solution ne changerais pas ?)
Merci de ton aide

le problème, c'est que ton algo s'arrêtera à la première solution trouvée, qui n'est pas nécessairement caracSaisie.
Si tu peux donner une valeur minimale et maximale pour caracSaisie, tu auras plus de chances d'avoir quelque chose de bijectif.

Steph

[Tagashy]

bijectif ???

caracSaisie est forcement compris entre 0 et 94 ( il ne peut pas être supérieur ou inférieur car il s'agit d'une partie précédente du programme qui ne distribue que des valeurs entre ces deux nombre en excluant 19 et 5)
pour mon algo je dois donc lui mettre d'autre limitation ou contrainte ?
(du genre test avec toute les valeur et donne moi toute celle qui corresponde ?)

[Invité]

caracSaisie est forcement compris entre 0 et 94 ( il ne peut pas être supérieur ou inférieur car il s'agit d'une partie précédente du programme qui ne distribue que des valeurs entre ces deux nombre en excluant 19 et 5)

Condition pas suffisante...

Détaillons un peu les choses. Je reprends tes notations a,b,c,x qui sont tous des entiers naturels dans [0,94].

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
c congru à ax+b [95] <=> il existe k tel que ax+b-c = 95k
                     <=> il existe k tel que x=(95k+c-b)/a est entier

x étant dans N94, un tel k devra donc vérifier :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

0 < (95k+c-b)/a < 94

soit

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(b-c)/95 < k < (94a+b-c)/95

k sera donc unique si et seulement si (94a+b-c)/95 - (b-c)/95 < 1, ou encore ssi 94a < 95...

Ce qui ne sera vrai que pour a=1...

Exemple avec a=1

a=1
b=10

Je prends x=20, alors ax+b = 30 alors c=30.

Si je reprends l'inégalité concernant k :

(b-c)/95 < k < (94a+b-c)/95

ça donne

-20 < k < 95/74

et la seule valeur de k est 0, mon x sera donc unique et x=(c-b)/a=20.


Exemple avec a > 1

a=5
b=21

Je prends x=36 par exemple. Alors c=11 (5x36+21=95x2+11).
Je reprends mon inégalité sur k

(b-c)/95 < k < (94a+b-c)/95

qui donne

10/95 < k < 480/95 soit 0 < k < 5.

Tu constates bien qu'il y aura 5 valeurs de k pour lesquelles je peux trouver un x qui convient et compris entre 0 et 94...

k=0, x=-2 à écarter
k=1, x=17
k=2, x=36
k=3, x=55
k=4, x=74
k=5, x=93


En conclusion, il faudra des contraintes supplémentaires pour construire quelque chose de bijectif...

Steph

[Tagashy]

j'aurais vraiment due suivre les cours de maths

donc d’après ce que j'ai compris k peut avoir plusieurs valeur et il faut que j’écarte toute celle qui donnent un résultat négatif
par contre niveau des condition supplémentaire je te demanderais conseille parce que je sais pas du tout quel condition rajouter (ou du moins une piste )

merci d'avance
cordialement Comandant Chaos

[foetus]

Au grand hasard: stocker k qui est le résultat de la division entière/ le nombre de "tours de roue"

[Tagashy]

en gros ce que tu me dit de faire (dis moi si je me trompe)
c'est en gros imaginons je dois crypter A je dois le crypter V9
ou V est le caractère après cryptage et 9 le nombre de tour de roue (oui c'est beaucoup 9)
puis au décodage utiliser justement ce 9 pour faire [(9*95+c)/a]-b?

Merci d'avance
Cordialement Comandant Chaos

[Invité]

donc d’après ce que j'ai compris k peut avoir plusieurs valeur et il faut que j’écarte toute celle qui donnent un résultat négatif

Non... Ce que je t'ai démontré, c'est que ton x sera unique si et seulement si a=1.

Dans le cas a>1, tu auras plusieurs x qui conviennent. Et pour être plus spécifique, puisque

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

x = f(k) = (95k+c-b)/a

deux valeurs successives de x seront "espacées" d'une valeur f(k+1)-f(k)=95/a.

En reprenant l'exemple que je t'avais donné (a=5, b=21, c=11), tu constates bien que les x sont espacés de 95/a=19...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
x = 17
x = 17+19 = 36
x = 36+19 = 55, etc

par contre niveau des condition supplémentaire je te demanderais conseille parce que je sais pas du tout quel condition rajouter (ou du moins une piste )

Ton application f sera bijective pour tout triplet (a,b,c) à partir du moment que tu peux borner son ensemble d'arrivée dans un intervalle [min, Max] tel que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Max-min<(95/a)-1

En reprenant l'exemple précedent, si je te fourni (a=5, b=21, c=11) avec l'intervalle [40,58], alors la seule solution sera x=55...

Mais ça suppose que celui qui va te communiquer c devra te communiquer au moins une donnée supplémentaire...

Il y a plusieurs solutions. Celle qui me vient à l'esprit consisterait à demander à ton interlocuteur de faire un tirage aléatoire d'un entier dans l'intervalle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[x-(95/2a), x+(95/2a)]

Avec l'exemple (a=5, b=21, c=11), on utiliserait alors l'intervalle [26.5, 45.5].

Steph

[Tagashy]

en gros il faut lors du cryptage indiquer l’intervalle du nombre pour forcer à ce que il n'y ais qu'une seule et unique solution lors du décryptage?


en utilisant le caractère a coder (x) et la première lettre de la clé de cryptage (a) comme information sur l'intervalle via ta formule

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[x-(95/2a), x+(95/2a)]

une fois l'intervalle établie pour 1 caractère je tire un nombre dans cette intervalle puis je l'indique lors du cryptage

et au décryptage j'utilise

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

x = f(k) = (95k+c-b)/a

et je garde l'unique valeur de k compris dans l'intervalle ?

[Invité]

Si ton interlocuteur fait un tirage aléatoire d'un entier N compris dans l'intervalle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[x-(95/2a), x+(95/2a)]

alors x sera nécessairement dans l'intervalle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[N-(95/2a), N+(95/2a)]

et il sera unique...


Je reprends mon exemple...

Ton interlocuteur te fournit (a=5, b=21, c=11) avec la variable aléatoire 30.

Tu sais calculer les x :

k=1, x=17
k=2, x=36
k=3, x=55
k=4, x=74
k=5, x=93

Celui que tu cherches se trouvera dans l'intervalle [20.5, 39.5].

C'est donc 36.

Steph

EDIT : tu peux bien sûr calculer le k unique qui permettra de calculer x :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

k = INT [(aN+c-b)/95]+1

puis

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

x = (95k+c-b)/a

(a=5, b=21, c=11) et 30 donnent bien :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

k = INT (140/95)+1 = 2   et   x = 180/5 = 36

[Tagashy]

du coup je vais tester tout ça et je vous tient au courent de si je trouve des bug

UN GROS MERCI A VOUS DEUX

et IP_Steph
(Sucks driver nvidia new shit ) tu m'as tuer quand j'ai lue ca si c'est bien ca qui est ecris ^^

[Invité]

du coup je vais tester tout ça et je vous tient au courent de si je trouve des bug

UN GROS MERCI A VOUS DEUX

J'espère que tu vas pas te mettre aux groupes cycliques Z/pZ pour faire de la crypto

(Sucks driver nvidia new shit ) tu m'as tuer quand j'ai lue ca si c'est bien ca qui est ecris ^^

Un jour, j'ai voulu mettre à jour mon driver NVidia sur ma machine Linux. Quand j'ai redémarré, tout était sens dessus-dessous

Steph

[Tagashy]

Z/pZ je pense pas étant donnée que j'ai pas compris la définition (anneau modulaire )
par contre je rencontre un bug pour a=16 b=20 n=85 et c=86
je me demande si ce ne serait due a l'index (0 peut elle être une valeur?)
cordialement Comandant Chaos

[Invité]

Z/pZ je pense pas étant donnée que j'ai pas compris la définition (anneau modulaire )
par contre je rencontre un bug pour a=16 b=20 n=85 et c=86
je me demande si ce ne serait due a l'index (0 peut elle être une valeur?)
cordialement Comandant Chaos

(a=16, b=20, c=86) donne x=16 comme valeur possible. Je ne trouve pas de valeur de x possible au voisinage de 85.

C'est quoi ton x ?

Steph