Explication a RSA

Fermé
stephane - 31 oct. 2001 à 16:16
 cryptoman - 3 nov. 2006 à 22:42
je vais peut-etre etre un peu lourd, mais j'ai rien compris au systeme de cryptage RSA.

p et q 2 nombres premiers ==> OK
d entier premier avec p-1 et q-1 ==> ???
e=1/d mod ((p-1)(q-1)) ==> ???

puis l'encodage
c=((m)puissance e) mod(n) ==> ???

et decodage
m=((c)puissance d) mod(n) ==> ???

alors SVP une explication et un petit exemple serait le bienvenu !!!
Merci

4 réponses

sebsauvage
Messages postés
32844
Date d'inscription
mercredi 29 août 2001
Statut
Modérateur
Dernière intervention
21 octobre 2019
15 653
31 oct. 2001 à 17:08
Et hop !

Une page avec un exemple:

http://sebsauvage.net/comprendre/encryptage/crypto_rsa.html


C'est pas beau, la vie ? ;-)
1
On va reprendre depuis le debut :
tu choisis deux entiers p et q premiers tres grands (~100chiffres)
=> n = p*q (n a donc environ 200 chiffres)
phi = (p-1)(q-1)

ensuite tu choisis un nombre e premier avec phi

et tu cherches le d tel que e*d (mod phi) = 1
Remarque: si tu es en 6eme c sur que tu vas avoir du mal a comprendre, je suppose donc que tu connais les % (modulo) et ce qu'est une factorisation en nb premiers

en fait pour trouver l'autre exposant quand tu en as dejà choisi un, il suffit d'utiliser l'algo etendu d'euclide :
au + bv =1
avec e et d a la place de a et b bien sur

En fait on part du principe que le cryptage n'utilise pas le meme exposant pour crypter que pour decrypter :
tu decoupe ton fichier en bloc de taille n , tu appliques a chaque bloc la puissance et le modulo

si tu fais cette operation deux fois avec d puis e tu retombes sur le texte original

Je n'ai pas le temps de te donner des ex maintenant essaies tout seul avec ca et si tu n'y arrives pas je t'enverrais des trucs
@+
0
Ma question va peut-être sembler bête mais comment fait-on pour
choisir 2 nombres entiers (facile) premiers (moins évident) de plus de 100 chiffres (carrement hard !) ?

Existe-t-il un algorithme qui donne la liste des nombres entiers de plus de 100, voir 200 chiffres ?

Juste pour ma culture perso

@+
Philippe
0
justement non il y a des generations de matheux qui se sont penchés et se penchent encore sur le pb , celui qui trouvera un algo pour generer facilement un tres gd nombre premiers gagnera des milliards :-)

en general tu cherche a distribuer les calculs : par exemple je suis en IUT et notre projet porte sur l'implementation de RSA => RSA c quedale a cote de la parallelisation des calculs en reseau...
notre site ouvrira bientot : pour l'instant c pas la peine d'y aller y marche pas encore (pas le temps de mettre en ligne) mais si ca interesse du monde ce sera son adresse :
http://membres.tripod.fr/ehehe

Pour parler de cryptage je suis la alors si ca interesse du monde n'hesitez pas ecrivez moi à batmat@tfz.net

@+
0
php > batmat
31 oct. 2001 à 23:52
Hum , hum !!!

J'ai vu aussi qu'un moyen simple et assez efficace de crypter était de cacher le message à l'intérieur des images en modifiant les informations non codantes (plutôt nombreuses vue les taux de compressions obtenus avec le format JPEG) et très difficile à décrypter pour les cryto-analystes.

Comment s'appelle cette technique ?

Philippe
0
batmat > php
1 nov. 2001 à 10:32
Il me semble que cette technique n'est pas tres agee ca s'appelle la steganographie, en fait il y a deux choses differentes dans ce que tu dis : mettre le message dans un fichier jpeg(par exemple) mai aussi pour s'assurer qu'un petit ne pourra pas le lire facilement on le crypte

On pourrait appeler ca de la crypto-steganographie mais je n'ai jamais vu le terme ecrit ou que ce soit :-)
@+
0
cryptoman > php
3 nov. 2006 à 22:42
Dans ces applications, le but n'est pas de crypter mais de cacher les donnees.

Crypter, c'est rendre des donnees accessibles a tous inintelligibles sauf pour les personnes qui possedent la cle.
Pour crypter des donnees, il existe des methodes plus simples basees sur des algorithmes plus ou moins resistants (DES,AES,RSA...).

Cacher, c'est rendre des donnees, pas necessairement cryptees, inaccessibles sauf pour les personnes qui connaissent la methode pour les trouver.

Il existe des methodes pour cacher des donnees dans des images mais aussi des fichiers audio ou video.
Ces techniques vont d'ailleurs tres probablement se developper pour lutter contre le piratage. Les donnees etant cachees et integrees au fichier, il sera impossible de les retirer. On pourra donc identifier la source du piratage.
0
mais au fait tu fais quoi dans la vie Stephane, je te demande ca pasque tout ce que tu demandes c ce dont j'ai besoin pour un projet à L'IUT et que ca fait dejà 6 mois que je cherche tout sur RSA, PVM, et interfacer une appli C++

@+
0
Je travaille comme ingénieur d'étude et de dév mais je recherche ces infos pour ma culture personnelle....et oui l'envie du codeur qui veut toujours en savoir plus...

j'ai pas pris l'option crypto a la fac et du coup j'ai rien compris au RSA.
Mais je dois dire qu'avec toutes vos reponses et meme une page avec un exemple de sebsauvage, j'ai tout capte.

Alors un grand merci a tous !!!
0