Comment fonctionne le cryptage RSA - Page 1

Je suis en train d'essayer de comprendre comment fonctionne cet algorithme magique
Je pense que je vais avoir plein de questions.

La première :
Dans tous les tutos que j'ai trouvé, il y a écrit "soit e un entier premier à (p-1)(q-1)"
Ca veut dire quoi qu'"un nombre est premier à un autre nombre"

que leur pgcd est 1?

c ca ..

Tu veux mon tipe ya meme la demo de la fiabilité de l'algo

y a qqch à dire sur le RSA, en TIPE

Ya carrement trop de chose a dire...

heu ... que y'a mieux

Ha oui je veux bien, s'il est plus clair que les tutos que j'ai trouvé !
Jusqu'ici j'ai trouvé des cours qui demandent d'avoir BAC+50

bon je vais zieuter ca.. mais j'ai que la partie diapo fait avec powerpoint...
J'espere la retrouvé

Merci

Bon j'ai pas retrouver le cd... peut etre sur le server de ma prepa.

puisque j'y suis
quelqu'un a l'algorithme DES pour VB?
Merci d'avance

Deux nombre sont premiers entre eux si ils n'ont que deux diviseurs communs (dans Z) : 1 et -1. Ce qui équivaut à dire que leur PGCD est de 1.


n=pq
e est un entier compris entre 2 et (p-1)(q-1)-1 et premier avec (p-1)(q-1)


Alors, il existe un seul entier d 1<d<(p-1)(q-1) tel que ed est congru à 1 modulo (p-1)(q-1)

Verstand> nope, pas de VB pour moi

Thibaut> je pense qu'un BAC+2 bien ajusté suffit pour comprendre ça ...

nEUrOne> C'est mon programme de terminale (nombres premiers)

Titane : merci

De rien

Bon j'va faire plaisir a bcp de monde :

http://godzil.free.fr/chiffrement.pdf

Alors ya qq'un qui est allé voir ?

Pas encore. J'y vais

Hé ! C'est plus clair que ce que j'ai pû trouver jusqu'ici
Un seul défaut : certaines lignes se chevauchent, difficile de lire.

Concernant la réversibilité :
- C'est quoi un problème "NP complet" ?
- Pourquoi tu dis que l'algorithme a un temps de recherche polynominal ?

(le texte est po de moi)

NP complet> Je l'avait vu mais g oublié depuis, mais si je me rapelle c une mesure de complexité, notemment le probleme du voyageur du commerce est NP complet (si je me rapelle bien)

Quand a une recherche polynomial (si je me trompe pas) c qq chose du genre
O(x ^ 1 + x ^ 2) etc...
Une complexité ss forme de polynome quoi

Dans O(x ^ 1 + x ^ 2), x est la clé publique p*q ?

aucune id
je donnait cette notation O pour donner un exemple de forme polynomyale

G recup cette doc, mais je my etait pas trop penché dessus

Moi je fé un TPe la dessus, si kk un a kk chose a me filer ...

Mais les algorithmes de "cassage" des clés RSA itèrent moins de sqrt(pq) fois

ah tiens le RSA
g eu un tp là-dessu mais on était trop occupé à jouer à Blobby Volley et Mario Kart pour le faire

godzil a écrit :
Quand a une recherche polynomial (si je me trompe pas) c qq chose du genre
O(x ^ 1 + x ^ 2) etc... Une complexité ss forme de polynome quoi

Une complexité polynomiale s'expirme sous la forme O(x^n)
(un seul terme, pas un polynome)



Tiens vous savez qu'il existe des algos de factorisation d'un entier n en O(ln(n)) ? Celà permet de casser le RSA facilement, mais bien sûr, ça ne marche pas encore : il faut un ordinateur quantique....

Intéressant
On ne peut pas émuler un µprocesseur quantique sur lequel on ferait tourner l'algo ?

O(x^n) : Donc on casse le RSA en (pq)^n itérations ?

Lol, c tu au moins ce que c kun processeur quantique ?