RSA sans factorisation de n
tomalille
Messages postés
52
Date d'inscription
jeudi 16 juin 2005
Statut
Membre
Dernière intervention
5 juin 2007
-
20 sept. 2005 à 01:29
releu Messages postés 1 Date d'inscription mardi 19 février 2008 Statut Membre Dernière intervention 19 février 2008 - 19 févr. 2008 à 04:32
releu Messages postés 1 Date d'inscription mardi 19 février 2008 Statut Membre Dernière intervention 19 février 2008 - 19 févr. 2008 à 04:32
2 réponses
zinebmah
Messages postés
2
Date d'inscription
dimanche 26 février 2006
Statut
Membre
Dernière intervention
6 mars 2006
6 mars 2006 à 15:55
6 mars 2006 à 15:55
je necéssit a un code source en visuel c++
releu
Messages postés
1
Date d'inscription
mardi 19 février 2008
Statut
Membre
Dernière intervention
19 février 2008
19 févr. 2008 à 04:32
19 févr. 2008 à 04:32
tu peux essayer de factoriser N-1 ( c + facile )
si N=pq alors N-1=2xp'1xp'2x....xp'i , soit Q'=2xp'1xp'2x..xp'i-1 et P'=p'<sub>i
</sub>alors Q'(ed-1)/24=a
et PHI(N)=(24a)/Q' puis (N+1)-PHI(N)=p+q
apres c'est Fermat :
[(p+q)/2]2-pq=[(p-q)/2]2
(p+q)/2+(p-q)/2=p
(p+q)/2-(p-q)/2=q
exemple :
RSA(611,7) public
610=10x61 alors 10(7xd-1)/24=a donc 70d-24a=10 ( identite de bezout)
solution:
d=79 et a=230 donc PHI(N)=552 et p+q=60 et p-q=34 donc p=47 et q=13
si N=pq alors N-1=2xp'1xp'2x....xp'i , soit Q'=2xp'1xp'2x..xp'i-1 et P'=p'<sub>i
</sub>alors Q'(ed-1)/24=a
et PHI(N)=(24a)/Q' puis (N+1)-PHI(N)=p+q
apres c'est Fermat :
[(p+q)/2]2-pq=[(p-q)/2]2
(p+q)/2+(p-q)/2=p
(p+q)/2-(p-q)/2=q
exemple :
RSA(611,7) public
610=10x61 alors 10(7xd-1)/24=a donc 70d-24a=10 ( identite de bezout)
solution:
d=79 et a=230 donc PHI(N)=552 et p+q=60 et p-q=34 donc p=47 et q=13
