Cryptage tout simple

[troudbibulle]

bonjour à tous
je fais un exercice tout simple sur le cryptage et meme ça je ne sais pas faire!!
bob envoie un message m à alice, la clé est k=2^35 et n=3^50 le message crypté est c(m)=km mod n
alice recoit c(m)=12345 retrouver m
merci à tout ceux qui voudront bien m'aider

[troudbibulle]

s'il vous plait si vous avez le temps jetez y un petit coup d'oeil
merci

[scroller]

Bonjour,
je vais répondre a ta question car je cherchais justement un petit algorithme de cryptage,
je reprends l’énoncé :C(m) = K*M mod N
C = 12345 | K = 2^35| N = 3^50
donc 2^35 * M mod 3^50 = 12345, 12345 étant le reste de la division de (k*M)/N
donné par la fonction mod.

Malheureusement il y a un hic : 'C' est le résultat d'une opération

exemple : 5 mod 2 = 1 car 5 = 2*2+1

si on inverse l'opération : X mod 2 = 1 alors X peut être égale à 3,5,7, tout les numéros impaires.
donc k * M = X * N + 12345 ou mieux M = (X * N + 12345) / K
Bref le résultat d'une opération ne permet pas de retrouver l'opération entière qui l'a créé donc pas le message M.
Il doit y avoir une erreur dans l’énoncé !!

[wserdx]

L'espace des messages possibles est compris entre 0 et
Dans l'exemple précédent, avec , ça fait nettement moins de message possibles!
Il s'agit de trouver tel que
On aura alors

[scroller]

Bonjour wserdx,
désolé, je ne suis pas d'accord avec toi car n est un reste entier d'une division non entière :
exemple : X mod 2 = 1 il y a comme réponse pour X tout les nombres impaires
=> 1 mod 2 = 3 mod 2 = 5 mod 2 = 7 mod 2 = ... = 1
Pour simplidfié avec une autre réponse décrypter le message tel que M + clé = Crypté
clé = 3, Crypté = 293,
on recheche le message M : trop de solutions quelque soit la valeur de la clé
Idem pour l'exercice : C(m) = X mod N

[wserdx]

Oui, mais comme dans l'énoncé on parle de chiffrement (cryptage), on convient implicitement qu'on limite l'ensemble des messages de sorte que la fonction de déchiffrement soit possible (la fonction inverse est calculable et ne donne qu'un seul résultat).
Un système de chiffrement/déchiffrement qui donne plusieurs messages clairs pour un même message chiffré, en général ce n'est pas très pratique.
Avec cette convention implicite, l'énoncé de "troudbidule" me paraît tout à fait légitime.
La solution que je trouve est:
m=195129832402323095594979
Maintenant, s'il manque des précisions dans l'énoncé, je veux bien qu'on les apporte...

[scroller]

Bien joué pour la solution,
c(m) = k * m mod n
k = 2^35 = 34359738368 et n = 3^50 = 717897987691852588770249
34359738368 x 195129832402323095594979 = 6704609989135510480047331734454272
6704609989135510480047331734454272 mod 717897987691852588770249 = 12345
l’arithmétique modulaire est pas trop mon domaine mais j'ai besoin d'éclaircir ceci : dans mon premier exemple j'indique qu'il n'y a pas qu'une seule solutions, mais c'est peut être a cause de mon incapaciter à traiter les solutions dans ce cas précis.
J'ai simplement créé un clone de cryptage selon la même méthode mais avec des valeurs plus petites : c(m) = k * m mod n
avec k = 123 et n = 99
message crypte => c = 75
123 * 32 mod 99 = 75
123 * 65 mod 99 = 75
123 * 98 mod 99 = 75
123 * 131 mod 99 = 75
123 * 1022 mod 99 = 75
123 * 19594970 mod 99 = 75
123 * 819594962 mod 99 = 75
voila, je cherche a trouver pourquoi il ne peut y avoir qu'une seule solution pour l'exercice !!
{MODIFICATION par scroller 19/12/2012 à 12h59.}
Supposons que l'on veuille chercher l'inverse modulaire u de 3 modulo 11.
u = 3^(-1) mod 11
Cela revient à calculer u vérifiant
3*u = 1 mod 11
Dans l'ensemble de Z_11, une solution est 4 car
3 * 4 = 12 = 1 mod 11
et c'est la seule. Par conséquent, l'inverse de 3 modulo 11 est 4.
À partir du moment où l'on a trouvé l'inverse de 3 dans Z_11, on peut trouver une infinité d'autres entiers u qui satisfont aussi cette congruence. Il suffit d'ajouter des multiples de n = 11 à l'inverse que nous avons trouvé. Autrement dit, les solutions sont
u = 4 + 11*k, k appartenant à Z
c'est-à-dire les éléments de {…, –18, –7, 4, 15, 26, …}.

{Last modif}
je recherche actuellement une valeur de M différente plus petite, pour commencer, répondant au cryptage12345
pour l'instant j'en suis au dénombrement de M :
M = 3 * 478727 * 135867159085326359
135867159085326359 est encore réductible !!

[math4pad]

Si k et n sont relativement premiers, l'inverse de k modulo n existe et est unique (modulo n).

On part du principe que m est plus petit que n, c'est ce qui fait que la solution sera unique (pgcd(k;n)=1).

C'est le cas avec 2^35 et 3^50

La solution est bien m = 195'129'832'402'323'095'594'979 < n, et elle est unique.

On a bien m * 2^35 = 12345 (mod n)

@scroller : dans ton clone de cryptage, 123 et 99 ne sont pas relativement premiers, c'est pourquoi tu trouves 3 solutions < 99.

Quant à la factorisation de m, il faut utiliser un CAS genre Mupad ou xcasenligne.fr

m = 3*478727*2286091*59432086949

[scroller]

[...]
La solution est bien m = 195 129 832 402 323 095 594 979 < n, et elle est unique.
[...]
@scroller : dans ton clone de cryptage, 123 et 99 ne sont pas relativement premiers, c'est pourquoi tu trouves 3 solutions < 99.
[...]
Quant à la factorisation de m, il faut utiliser un CAS genre Mupad ou xcasenligne.fr
m = 3*478727*2286091*59432086949

Ok, oui effectivement, j'ai fait l'erreur de prendre des nombres au hasard,
factorisation de M ça m'a pris un peu de temps avec mon ordi (ca lui a fait faire de tres nombreues boucles lol),
pour info :

[...] on convient implicitement qu'on limite l'ensemble des messages de sorte que la fonction de déchiffrement soit possible (la fonction inverse est calculable et ne donne qu'un seul résultat) [...]

c'etait pas clair pour moi car si je modifie mon clone de l'exercice avec k = 127 et n = 97 avec le meme resultat : 75
on a : 127 * (51 + 75 * q) mod 97 = 75
q appartenant aux entiers naturels !! m = 51 étant la seule solution m < n !! alors que sur mon précédent message j'aurais eu :
( 127 * 51 ) mod 97 = 75
( 127 * 148 ) mod 97 = 75
( 127 * 245 ) mod 97 = 75
etc...
donc très loin du seul résultat ^^
Merci de ta réponse pour le plus grand diviseur commun pour les couples k et n ^^
reste plus qu'a aider troudbibulle (2008 il en a surement plus besoin le pauvre )
car moi j'ai eu ma réponse mais pas lui :p