91 lines
2.6 KiB
C
91 lines
2.6 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
/* n = p * q => p et q sont des nombres premiers
|
|
e = pgcd(e,(p-1)(q-1))
|
|
d doit etre inverse de e modulo(p-1)(q-1)
|
|
--> d*e = 1 mod((p-1)(q-1))
|
|
(M^e) mod n = C
|
|
M = (C^d) mod n
|
|
|
|
(n=1028648100739351553,e=138115088263636411)
|
|
*/
|
|
|
|
/* Creation de la structure qui gardera le nombre premier p et q */
|
|
typedef struct nbPremier
|
|
{
|
|
unsigned long long int p;
|
|
unsigned long long int q;
|
|
} premier;
|
|
|
|
/* Verifier si un nombre est premier ou non */
|
|
int nombrePremier(unsigned long long int x)
|
|
{
|
|
/* Il faut que le nombre soit superieur a 1 */
|
|
if (x < 2)
|
|
{
|
|
return 0;
|
|
}
|
|
/* Test pour savoir si c'est un nombre premier */
|
|
for (unsigned long long int i = 2; i < x; i++)
|
|
{
|
|
if ((x % i) == 0)
|
|
{
|
|
return 0;
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
|
|
/* Trouver p et q a partir d'une boucle for : on va tester si un nombre est diviseur de n.
|
|
Si c'est le cas, on teste si ce nombre est premier et si nombre/n est premier (car nombre * (nombre/n) = n
|
|
Si les deux nombres sont premiers, alors on a nos 2 facteurs premiers qui multiplier ensemble donnent n */
|
|
premier findPq(unsigned long long int n)
|
|
{
|
|
premier pq;
|
|
for (unsigned long long int i = 2; i < n; i++){
|
|
if (n % i == 0) {
|
|
if (nombrePremier(i) && nombrePremier(n/i)){
|
|
pq.q = i;
|
|
pq.p = n/i;
|
|
printf("p = %llu\n", pq.p);
|
|
printf("q = %llu\n", pq.q);
|
|
return pq;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
unsigned long long int multiplicationRapide(unsigned long long int e, unsigned long long int i, unsigned long long int phi)
|
|
{
|
|
if (i < 1000 && e < 1000)
|
|
{
|
|
return i * e % phi;
|
|
}
|
|
return multiplicationRapide(e / 2, i / 2, phi) + multiplicationRapide(e / 2 ,i / 2, phi);
|
|
}
|
|
|
|
int main(void) {
|
|
/*Parametres RSA*/
|
|
unsigned long long int n = 1028648100739351553;
|
|
unsigned long long int e = 138115088263636411;
|
|
unsigned long long int d, nb, phi;
|
|
|
|
/* Recherche des nombres premiers p et q */
|
|
premier facteurs = findPq(n);
|
|
phi = (facteurs.p - 1)*(facteurs.q - 1);
|
|
printf("phi = %llu\n", phi);
|
|
|
|
/* Calcul de la cle privee d a partir de la formule : (e*d) mod phi = 1 */
|
|
for (unsigned long long int i = 1; i < phi; i++) {
|
|
unsigned long long int resultat = multiplicationRapide(e, i, phi);
|
|
printf("resultat = %llu\n", resultat);
|
|
if (resultat == 1) {
|
|
d = i;
|
|
break;
|
|
}
|
|
}
|
|
printf("La cle privee d est : %llu", d);
|
|
return EXIT_SUCCESS;
|
|
} |