Bonjour à tous, pour un projet je souhaite utiliser un cryptage asymétrique, j'ai donc réécrit en C le programme présent sur ce tutoriel du sdz

Tout va bien jusqu'au calcul de la clé privée, pour simplifier je ne mettrait que le code de la partie qui se charge de ça, vous trouverez les valeurs des variables utilisée dans le rendu posté plus bas

int d=0;
    i=0;
    while(i==0&&d<f)
    {
        if(e*d%f==1 && p<d && q<d && d<f)
        {

            i=1;
        }
        else
        {
            d++;
        }
    }
    if(i==1)
    {
        d=d-1;
        printf("d=%d", d);
    }
    else
    {
        printf("Impossible de definir une cle privee");
    }

Si les deux nombres entrés pour calculer les clés sont 35422 et 38877 le programme donne ça:

Lancement du programme
p=35422
q=38877
n=1377101094
f=1377026796
e=38879
d=596684466

Ce qui est tout à fait le résultat escompté

Si par contre ces nombres sont 35472 et 38877 voici le résultat:

Lancement du programme
p=35472
q=38877
n=1379044944
f=1378970596
e=38879
Impossible de definir une cle privee

Voyez vous une erreur quelque part?
Le cas contraire y a t'il une autre solution pour le calcul d'une clé privée d'un chiffrement RSA ou dois-je creer un autre algorythme qui se chargera de modifier p et q en cas d'echec? (sachant que ces derniers devront au final être calculé en fonction d'un mot de passe)

Merci d'avance pour vos réponses

Nico-teeN

Alors déjà p et q doivent être premiers... sinon tu n'as pas la garantie que ça marche...

essaye déjà par tester ça ( tu as des librairies qui testent la primalité des nombres si besoin...)

Alors plusieurs remarque :

-Comme dit ci-dessus les nombres p et q doivent êtres premiers

-Ta méthode pour calculer l'inverse de e modulo (p-1)(q-1) est horrible, tu parcours tout les valeurs possibles. Ca marche ici car tu a des petites valeurs, mais en pratique on utilise rsa avec des nombres trés grands ce qui te donnerait un temps de calcul absolument deraisonnable.

-Pourquoi tu impose à d d'être plus grand que p et q ? (En pratique ce sera souvent le cas mais absolument pas une obligation)

Et si tu veux vraiment programmer rsa pour quelque chose de pratique utilise une bibliothèque qui gère des grands nombres comme gmp ou BIGNUM de openssl.

Citation : darkantoine

Alors déjà p et q doivent être premiers... sinon tu n'as pas la garantie que ça marche...

essaye déjà par tester ça ( tu as des librairies qui testent la primalité des nombres si besoin...)

Oki, j'ai fait une fonction qui teste la primalitée de p et q et les incrémente s'ils ne sont pas premiers puis renvoi la valeur du premier entier au dessus de p ou q, ce problème est résolu, merci beaucoup

Citation : Phacog

-Comme dit ci-dessus les nombres p et q doivent êtres premiers

Problème résolu

Citation : Phacog

-Ta méthode pour calculer l'inverse de e modulo (p-1)(q-1) est horrible, tu parcours tout les valeurs possibles. Ca marche ici car tu a des petites valeurs, mais en pratique on utilise rsa avec des nombres trés grands ce qui te donnerait un temps de calcul absolument deraisonnable.

En effet, le temps de calcul de d me dérange un peu mais je ne voit pas trop comment faire ce calcul, comment me conseillerais tu de procéder?

Citation : Phacog

-Pourquoi tu impose à d d'être plus grand que p et q ? (En pratique ce sera souvent le cas mais absolument pas une obligation)

Je ne sais pas, sur le tuto il est dit

Citation

e*d mod n = 1 et p,q < d < f.

( f=(p-1)*(q-1) )
ne comprenant pas vraiment tout les tenants et les aboutissants de cet algorythme j'ai considéré ça comme une vérité sans aller chercher plus loin

Citation : Phacog

Et si tu veux vraiment programmer rsa pour quelque chose de pratique utilise une bibliothèque qui gère des grands nombres comme gmp ou BIGNUM de openssl.

Bien noté, je verrais ça une fois que mon programme fonctionnera sans soucis avec des petits nombres et que j'aurais reglé le problème du calcul de d

Quoi qu'il en soit merci beaucoup pour votre aide

J'ai regardé rapidement ce tuto, je le trouve vraiment pas terrible.

Déja, il n'y a aucune raison d'imposer à e et d d'être supérieur à p et q. Par contre, on évite de prendre des valeurs trop petite pour des raisons de sécurité.
Mais l'exposant publique e souvent utilisé est 65537 qui est plus petit que les nombres premiers.

Ensuite si tu veux trouver d tel que e*d = 1 mod (p-1)(q-1), il existe un algo très efficace : l'algorithme d'Euclide étendu

voilà, cherche d'autre source sur l'explication de rsa, celle là m'a l'air pas très fiable.

Ok, je suis allé voir la page wikipédia, j'ai pas tout compris mais j'ai compris le principe, en cherchant une explication plus simple je suis tombé sur ce site qui explique le fonctionnement de manière on ne peux plus simple
J'ai bêtement rentranscrit ce qui est écrit en C et je suis arrivé à cette fonction

int algo_euclide_etendu(int b, int n)
{
    int t0=0;
    int t=1;
    int q=n/b;
    int r=n-q*b;
    int temp=0;
    while(r>0)
    {
        temp=t0-q*t;
        if(temp>=0)
        {
            temp=temp%n;
        }
        else
        {
            temp=n-((-temp)%n);
        }
        t0=t;
        t=temp;
        n=b;
        b=r;
        q=n/b;
        r=n-q*b;
    }
    if(b!=1)
    {
        printf("Pas d'inverse modulo n");
    }
    else
    {
        printf("%d", t);
    }
}

Lorsque je fait
algo_euclide_etendu(4, 9); j'obtient effectivement 7
Lorsque je fait
algo_euclide_etendu(6, 9); mon programme me signale que 6 n'a pas d'inverse modulo 9
Par contre lorsque je fait
algo_euclide_etendu(7, 13); j'obtient 3 alors que 7*3%13=8 et non 1
Ou est le soucis? j'ai du mal à comprendre ce qui ne va pas

Ben en fait le probleme arrive quand tu calcule :

if(temp>=0)
{
    temp=temp%n;
}
else
{
    temp=n-((-temp)%n);
}

en fait le n que tu utilise ici est le n que tu appelle au début de la fonction, or toi dans ton programme tu modifie n. Il faut que tu utilise une autre variable qui aura la valeur de n au début et que tu pourras modifier ensuite.

Regarde bien le lien que tu donne, on a au début :

n0 := n

Ok merci, ce coup ci quand je test la fonction avec 7 et 13 comme argument j'ai le bon résultat par contre après avec inseré ma fonction dans mon programme de génération des clés j'ai de nouveau des soucis avec certains chiffres

ici l'algorithme d'euclide étendu tel qu'il est dans mon programme:

int algo_euclide_etendu(int b, int n)
{
    int n0=n;
    int b0=b;
    int t0=0;
    int t=1;
    int q=n0/b0;
    int r=n0-q*b0;
    int temp=0;
    while(r>0)
    {
        temp=t0-q*t;
        if(temp>=0)
        {
            temp=temp%n;
        }
        else
        {
            temp=n-((-temp)%n);
        }
        t0=t;
        t=temp;
        n0=b0;
        b0=r;
        q=n0/b0;
        r=n0-q*b0;
    }
    if(b0!=1)
    {
        return 0;
    }
    else
    {
        return t;
    }
}

Et la, la façon dont je le traite dans main()

int d=0;
    d=algo_euclide_etendu(e, n);
    if(e*d%n==1)
    {
        printf("d=%d", d);
    }
    else
    {
        printf("Impossible de definir une cle privee");
    }

Avec p=9 et q=5 le programme me sort

Lancement du programme
p=11
q=5
n=55
f=40
e=13
d=17

Par contre avec p=31900 et q=37900 j'obtient

Lancement du programme
p=31907
q=37907
n=1209498649
f=1209428836
e=37909
Impossible de definir une cle privee

Pourtant le programme présent sur le site d'ou je tire l'algo me dit que l'inverse de 37909 % 1209498649 est 585303034 ce que ma calculatrice confirme

Est-ce un problème dut au fait qu'algo_euclide_etendu() essaye de stocker sur un int un nombre trop grand ou cela vient t'il d'autre chose?

En tout cas merci encore une fois pour toute l'aide que tu m'a apporté jusqu'ici

Ca doit être quand tu calcule d*e%n avec d = 585303034 et e = 37909
la valeur est trop grande pour être stocké dans un int.