Factorisation de N=p*q

Maths lover · December 2018

Bonjour !
Notre prof nous a donné quelques questions d'examen chiffrés, si vous pouvez m'aider à trouver les clés p et q je serai reconnaissante !
Merci par avance.
Cette 1ère question est cryptée par RSA:

Voici les clés publiques :
Module
n :=542135034673809296672738518401173005245129962903624925620456918430128224
399688554440237387177916457931272948134584980801536066931671937361141586324
072699122149054828853586589169097;
Exposant publique
e :=3 ;
Le cryptogramme est :
C :=819887713138286510331553291552362432640086025365772904996749844633805499
662993681904221758695568989277982953601816822608745906297220913618026908250
03353764094677100044842981158219 ;

reuns · December 2018

C'est quoi ta question ? Si $C = m^e \bmod N$ alors on a besoin d'un $f$ tel que $ef = 1 +k \varphi(N)$ pour retrouver $m = m^{1+k \varphi(N)} = m^{ef} = C^f \bmod N$. Si $N = pq$ est produit de deux nombres premiers alors $\varphi(N) = (p-1)(q-1) = N+1-p-q$ donc on a besoin de factoriser $N$ pour retrouver $p+q$ et $\varphi(N)$ et $f$.

Maths lover · December 2018

Oui reuns, c'est ça le problème je n'arrive pas à trouver le p et le q, car N est grand il est composé de 180 chiffres et mon ordinateur ne peut pas effectuer cette factorisation !

Math Coss · December 2018

Tu peux peut-être essayer avec l'attaque de Wiener ? (Les suggestionneurs ne sont pas les payeurs...)

reuns · December 2018

Pari-gp n'arrive pas à factoriser en moins de 5min. Si ton prof t'a vraiment demandé ça alors il attend probablement que tu expliques le temps moyen que ça prend de factoriser une clé de 512bits.

Factorisation de N=p*q

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 6