Cryptage asymétrique RSA

Posté par Nairod2 Nairod2

Bonjour je suis bloqué sur un exo :

On se propose de crypter un message avec le système RSA (asymétrique).
On choisi p et q deux nombres premiers, tel que p = 7 et q = 5.

1° Déterminer le nombre e premier avec (p - 1)(q - 1).
2° Déterminer r pour que le reste de la division de (e * r) par (p - 1)(q - 1) soit égal à 1.

1° je sais que deux nombres sont premiers entre eux si le pgcd de a par b = 1
Donc, (p - 1)(q - 1) = 24
pgcd(e, 24) = 1

ou alors par l'indentité de bézout :

x*e + 24y = 1
je pense pas que faut utilisé l'identité de bezout...

Je ne sais absolument pas comment faire pour trouver e sans faire d'essais successifs.

Si vous pouviez m'aidé ce serai vraiment extra!
Merci d'avance,

Posté par dhalte dhalte

(p-1)(q-1)=6*4

tu choisis un nombre premier avec 6*4. 7 va très bien

Posté par Nairod2 Nairod2

Oui je sais tout comme 5, 11, 13, 17, 19, 23 mais comment les trouver sans faire des essais ?

Posté par dhalte dhalte

On utilise de très gros ordinateurs car dans la pratique ces nombres sont très grands.
Ce genre de cryptage asymétrique à clef publique est efficace parce que il est extrêmement plus difficile de décomposer un grand entier en facteurs premiers que de trouver de nouveaux nombres premiers.

C'est pourquoi aussi la recherche est si active dans la mise au point d'algorithmes de plus en plus performants de factorisation des grands nombres.

Si un mathématicien fou découvrait un jour un moyen efficace de factoriser les grands nombres, c'est tout le système économique qui s'effondrerait.

Il existe d'ailleurs des théories de factorisation sur machines quantiques (pas encore opérationnelles) qui font trembler les grands argentiers.

Posté par Nairod2 Nairod2

Donc en gros si je me fait un programme, il faut que je test tout les nombres de 2 à N qui vérifie pgcd(N, (p-1)(q-1)) = 1 pour savoir si ils sont premiers entre eux.

Par exemple pour trouver e premier avec (p-1)(q-1)) il faut testé :
pgcd(2, (p-1)(q-1))) = 2
pgcd(3, (p-1)(q-1))) = 3
pgcd(4, (p-1)(q-1))) = 4
pgcd(5, (p-1)(q-1))) = 1


donc e = 5.

C'est bien ça?

Posté par dhalte dhalte

Non, il faut que tu en choisisses un seul.

Tu veux me transmettre un nombre x sans que personne que moi ne puisse connaitre x
x : ton secret, que tu veux me transmettre

Pour cela je choisis deux (très grands) nombres premiers p et q
p et q sont mon secret à moi seul.

Je calcule n=pq, f=(p-1)(q-1) et je choisis un nombre e premier avec f : il est "facile" de trouver un nombre premier avec un autre.

Je calcule aussi un nombre d tel que ed=1 [f] : ça aussi, c'est "facile" à faire et ça reste mon secret.

Je te fais connaitre sans me cacher les nombres e et n
Il est extrêmement difficile de retrouver p, q ou d en connaissant uniquement e et n

Toi, tu calcules , et tu me le transmets, sans prendre de précautions

Mois, je calcule et il se trouve que z=x

Si tu veux faire un essai, je te donne n=9167, e=1183
choisis un nombre x entre 0 et 9000 et calcule x^e[n]
pour cela, tu fais


...


Il te faut bien sur un petit programme pour faire ces 1183 itérations
tu me transmets ce y
et je te réponds en recalculant x

Posté par Nairod2 Nairod2


Comment tu fais sans faire des essais successifs?
Par exemple trouver e premier avec 24.


Idem, comment tu fais sans faire des essais successifs.

Posté par dhalte dhalte


tout nombre composé de facteurs premiers différents de 2 et 3 est premier avec 24

est premier avec 24

Ensuite, revois Bezout : p et q premiers entre eux
Une version légèrement modifiée de la division euclidienne permet de trouver un premier couple (a;b) et tous les autres en découlent.

Attention : l'expression que j'ai utilisée "ça reste mon secret" s'appliquait au nombre d, pas à la manière de l'obtenir.
Attention, quand je dis "facile", entre guillemets, je dis que les algorithmes adéquats associés aux ordinateurs actuels permettent en un temps très bref d'obtenir la réponse. Je n'ai jamais prétendu que dans les cas pratiques, il y avait un petit fonctionnaire avec gomme et crayon pour faire les calculs.

L'efficacité de RSA est que le nombre n=pq est beaucoup plus grand que p et q eux mêmes, puisque c'est leur produit, et que sa décomposition sur n'importe quel ordinateur, dans les cas pratiques, prendrait des années.

Posté par sloreviv sloreviv

joli tout ca , je le mets dans mes archives!!

Posté par sloreviv sloreviv

bonjour au fait Dhalte et Nairod2

Posté par dhalte dhalte

Bonjour sloreviv.

Posté par Nairod2 Nairod2

Soit x mon secret.

Tu dis que 35 est premier avec 24.
Ok mais du coups quand je vais devoir codé mon message je vais devoir elevé mon x à la puissance e.
Il se trouve que ton e est grand (35) donc forcément ça va être long à calculer pour toi avant de m'envoyer le message crypté.
Si je prends e = 5 (en effet pgcd(24, 5) = 1) tu vas être beaucoup plus rapide à m'envoyer le message.

Il faut donc choisir e petit pour accélérer les calculs mais perdons nous en "protection" ?

2° Déterminer r pour que le reste de la division de (e * r) par (p - 1)(q - 1) soit égal à 1.

Même question perdons nous de la protection si nous prenons r petit ?

Posté par dhalte dhalte

Il y a une chose dont tu n'es pas conscient :
Cette technique de cryptage RSA est destinée à être utilisée pour échanger des informations sur Internet. Ce sont des ordinateurs qui effectuent les calculs.
Les nombres p et q employés par ces techniques (ce que j'appelle "dans la pratique") sont de l'ordre de , c'est à dire qu'ils ont environ 77 chiffres en base 10.

Il existe des algorithmes très efficaces pour trouver des nombres premiers de cette longueur. Il n'en existe aucun qui permette de les retrouver connaissant uniquement leur produit n=pq, vu leur taille.

Ton exercice initial prend en exemple p=7, q=5 : il est très utile "pédagogiquement". Il n'a strictement aucune utilité pratique : connaissant 35, il est humainement très aisé, même pour un élève de Terminale, de retrouver 5 et 7, ses facteurs premiers.

Mon exemple cherchait à donner un moyen terme, n=9167, et voulait simplement proposer un cadre un tant soit peu plus réaliste, mais nécessitait de ta part l'écriture d'un bout de programme pour calculer .

Pour enfoncer le clou, sache aussi que nos chers ordis sont extrêmement efficaces pour effectuer les opérations , même sur les grands chiffres utilisés dans la pratique.

Sinon, avec p=5, q=7, tu peux faire la même chose, mais là encore, le résultat sera moins spectaculaire.
tu as donc n=35, produit de deux nombres premiers p et q super secrets et non recalculables, et e=5
choisis un nombre x entre 1 et 34 et calcule , mais sache qu'avec ces quantités, tu vas souvent tomber sur y=x, ce qui ne doit pas te surprendre, la valeur très faible de p et q en est responsable.

J'ai à ma disposition un ordinateur (tu t'en serais douté) grâce auquel j'ai généré les nombres p=5, q=7 très grands et top secrets et ensuite n=35, e=5 que je t'ai transmis, mais aussi un nombre que tu appelles r (il peut y en avoir plusieurs, il faut en choisir un) tel que 5r=1[(p-1)(q-1)] et qui reste ma propriété, mon secret, même si la valeur ridiculement faible de n=35 te permettrait de "casser" mon code en retrouvant p et q, puis de te calculer toi-même une valeur de r, peut-être différente de la mienne, mais qui marcherait tout aussi bien pour retrouver x à partir de y.

Moi, grâce à mon 'r' et à mon ordinateur, je recalcule x à partir de ton y.

Même avec des nombres p et q de 77 chiffres, un ordinateur met quelques micro secondes à calculer y à partir de x et inversement.

Posté par Nairod2 Nairod2

Juste une dernière question.
Ma calculatrice peut au maximum calculer 2^332.

Je réponds à la question 2° de mon exo.
Je prends r = 17 par exemple.

Si j'ai x^17 > 2^332 je vais avoir un message overflow de la part de ma calculatrice alors comment font les ordis pour calculer des nombres si énorme ?

Posté par dhalte dhalte

Déjà, quand on calcule , on utilise la remarque suivante :



Et alors, on peut calculer ces expressions, ces élévations au carré en restant toujours dans les parages de 'n'. Plus exactement entre 1 et .

par exemple :
est calculé ainsi :






Je n'ai jamais eu besoin de calculer explicitement , même si, évidemment, dans cet exemple, j'aurais pu le faire.

Ensuite, les ordinateurs actuels calculent fondamentalement en binaire, en base 2, et avec des nombres qui ne dépassent pas la plupart du temps mais ici ce n'est pas suffisant, alors on a écrit des programmes, toujours très efficaces, qui manipulent en fait des séries de nombres comme si c'était un seul nombre.
Par exemple, accoler deux nombres qui peuvent stocker , c'est se permettre de manipuler des nombres qui peuvent aller jusqu'à .

Avec 8 nombres, on va jusqu'à et ça devient intéressant.
Tu vois, il "suffit" d'écrire des programmes de multiplication de "nombres" stockés sur 16 nombres accolés les uns aux autres pour manipuler des expressions du style , avec n ayant 160 chiffres.
Et pour finir, ces "multiplications" de nombres en base 2 sont justement une des spécialités des architectures de nos beaux computers : elles représentent un "shift" des digits qui est vraiment l'opération basique pour eux.

Sais-tu ce qu'est la base 2 ?

Posté par Nairod2 Nairod2

Sais-tu ce qu'est la base 2 ?

Oui on la vu, on travaille même avec. (BAC STI)

Je te remercie de m'avoir aidé et d'avoir pris le temps de répondre à mes questions c'est vraiment un sujet très intéressant le cryptage RSA.

Posté par sloreviv sloreviv

je vais relire tout ca , fort interessant!!