Cryptage / Décryptage Simple

Cryptage / Décryptage Simple : Programme de BTS

TUTO : Cryptage / Décryptage Simple Partie A

énoncer

Pour ce genre d'exercice, je vous conseille de noter, sur un brouillon, toutes les variables que vous connaissez. Je vais donc le faire ici :

p = 5
q = 23
n = 115

Ces trois variables sont précisées dans l'énoncer.

On nous demande donc, dans la question 1, d'expliquer pourquoi 23 est un nombre premier.

Comme je l'ai déjà expliqué dans le précédent tutoriel sur le décryptage :

Cliquez ici

"Est un nombre premier tout nombre ne pouvant être divisé que par 1 et par lui même." 23 ne peut être divisé que par 1 ou 23, donc il s'agit bien d'un nombre premier.

Il nous est ensuite demandé de calculer K = (p-1) * (q-1) ce qui nous donne ici :

K = (5-1) * (23-1)
K = 4 * 22
K = 88

L'énoncer nous dis ensuite que c = 9, on va donc le rajouter sur notre brouillon.

p = 5
q = 23
n = 115
c = 9

Maintenant, il nous est demandé de décomposer en produit de facteurs premiers le nombre 88.

Il s'agit juste de faire ça :

88 = 2 * 44
44 = 2 * 22
22 = 2 * 11

Comme 11 est un nombre premier, on s'arrête ici :) et la réponse est donc :

88 = 2 * 2 * 2 * 11

Autrement dit :

88 = 2^3 * 11

Il nous est demandé ensuite d'expliquer pourquoi 9 et 88 sont premiers entre eux. Je l'avais déjà expliqué dans le tutoriel cité plus haut !

Au point où j'en suis... je vais le réécrire :D Pour que deux nombres soient premiers entre eux, il faut que leur PGCD soit égal à 1. Si le PGCD (Plus Grand Commun Diviseur...) est supérieur à 1, les deux nombres ne sont pas premiers entre eux.

Il est maintenant demandé d'expliquer pourquoi le modulo 88 du résultat de 49*9 est égal à 1.

49 et 9 sont tous deux premiers avec 88. Le PGCD de 88 et 9 est 1. Idem pour 88 et 49. On peut donc multiplier n'importe quels nombres entre eux, tant qu'ils sont premiers avec 88, le modulo 88 du résultat sera toujours égal à 1.

TUTO : Cryptage / Décryptage Simple Partie B

énoncer

Voici donc la seconde partie, je vais remettre mon brouillon en visuel pour voir ce qu'on a.

p = 5
q = 23
n = 115
c = 9

Voilà, il nous est donc demandé de déterminer le nombre crypté b que Bob envoie à Alyx. Le tout en sachant que b est égal au reste dans la division euclidienne de a^c par n. Autrement dit :

a^c % n

Bob veut transmettre le nombre 12 à Alyx donc a = 12.

p = 5
q = 23
n = 115
c = 9
a = 12
Je disais donc :

a^c % n
12^9 % 115 = 27

Le chiffre 12 devient donc 27 une fois crypté.

TUTO : Cryptage / Décryptage Simple Partie C

Passons à la dernière partie. Bob a envoyé un nouveau nombre à Alyx, nous devons parvenir à le décrypter. Il s'agit du nombre "2". Pour le décrypter, Alyx utilise sa clé de décryptage privée : la clé "d". Et "d" = 49

p = 5
q = 23
n = 115
c = 9
a = 12
d = 49

Seulement, la calculatrice ne permet pas de décrypter quelque chose de si grand... Il aurait fallu faire :

2^d % n
2^49 % 115

Mais la calculette ne le permet pas ! L'énoncer donne donc une façon de contourner le problème. On nous dit que :

2^33 = 8589934592
8589934592 % 115 = 47

2^16 = 65536
65536 % 115 = 101

33 + 16 = 49 Nous avons bien notre "puissance 49". On pourrait se dire "Hmmm... on a juste à additionner les résultats et on obtiendra le nombre décrypté !". Oui... mais non ! Pas tout à fait.

Comme vous pouvez le voir, les résultats obtenus sont 47 et 101.

47 + 101 = 148 et vous me voyez sûrement déjà venir...

148 > 115 et ça, ça n'est pas possible !

C'est comme si je vous demandais de me citer la 148 ème lettre de l'alphabet. Elle n'existe pas puisque la dernière lettre est Z, la 26ème... On va donc faire :

148 % 115 = 33

Et voilà ! Le 2, une fois décrypté, devient 33 ! C'est tellement beau...

Bon, du coup, j'vais m'pioter moi, bonne nuit :')