chiffrement: algorithme RSA

Question

Je l'algorithme RSA de mise en œuvre pour le chiffrement et le déchiffrement comme indiqué ici:

http://www.di-mgt.com.au/rsa_alg.html

Mais ne pouvait pas comprendre la partie de génération de nombres premiers aléatoire dans la génération de clés. Donc, je prends deux nombres premiers comme entrées de l'utilisateur. J'ai eu des difficultés à générer le e aussi. donc je l'ai fait constant (e = 17)

Certaines entrées de nombres premiers fonctionnent correctement (c'est-à-dire codage et décodage correctement) dans gcc sous linux mais pas dans devcpp sous windows. (53,61 par exemple)

Voici le code de génération de clé:

/* Generates private and public keys and saves into two separate files */ 
void keygen() 
{ 
    int p,q,phi,d,e,n,s; 

    printf("\n Enter two prime numbers: "); 
    scanf("%d%d",&p,&q); 

    n = p*q; 
    phi=(p-1)*(q-1); 

    e=17; 

    // selec d such that d*e = 1+ k*phi for some integer k. 
    d = 0; 
    do 
    { 
     d++; 
     s = (d*e)%phi; 
    }while(s!=1); 

    printf("\n public key: { e=%d n=%d }",e,n); 
    printf("\n private key: { d=%d n=%d }\n",d,n); 

} 

Besoin d'aide et suggestions dans le nombre premier et génération e.

Answer 1

Je n'ai pas la réponse, mais si le même code compilé avec deux compilateurs différents donne des réponses différentes, je devinerais que certains types sont de taille différente ou que vous utilisez implicitement un comportement indéfini quelque part. La première chose à faire est de vérifier, à partir des mêmes paires de nombres premiers, que toutes les constantes que vous générez sont identiques dans les deux implémentations. Si ce n'est pas le cas, vos algorithmes de génération de paires de clés sont en cause. La prochaine chose à faire est de s'assurer que vos données d'entrée pour le chiffrement sont absolument identiques sur les 2 systèmes. Portez une attention particulière à la façon dont vous traitez les caractères de fin de ligne. Gardez à l'esprit que, sur Windows, la fin de ligne est \r\n et sur Linux, elle est \n. La plupart des implémentations de bibliothèque Windows convertissent \r\n en \n lorsque le fichier est lu si "r" est fourni en tant que paramètre de mode à fopen(). Votre implémentation peut être différente.

Enfin, quel que soit le problème, en aucun jamais utiliser gets() Si vous prenez vous-même à penser à l'utiliser à nouveau, vous devez supprimer les lobes frontaux du cerveau avec un pic à glace.

Answer 2

Après les notes pratiques à la fin de la page liée vous arriveriez à quelque chose comme ça pour la génération premier:

unsigned int get_prime(int e) 
{ 
    while (true) 
    { 
     unsigned int suspect = 1 + (unsigned int)(65535.0 * rand()/(RAND_MAX + 1.0)); 
     suspect &= 0x0000FFFF; // make sure only the lower 16bit are set 
     suspect |= 0xC001; // set the two highest and the lowest bit 
     while (!test_prime(suspect)) 
     { 
      suspect += 2; 
     } 
     if (suspect < 65536 && gcd(e, suspect - 1) == 1) 
      return suspect; 
    } 
} 

test_prime est censé être une mise en œuvre du Miller-Rabin test. La fonction ci-dessus fait certaines hypothèses et a quelques inconvénients:

• int est de 32 bits
• RAND_MAX est plus grand que 65536
• rand() est généralement pas un bon générateur de nombres aléatoires à utiliser pour le cryptage sérieux
• Le les nombres premiers générés sont 16 bits donc de toute évidence pas assez grands pour un cryptage sérieux de toute façon

N'utilisez pas ceci dans n'importe quel code de production.

Selon l'article, il semble correct de choisir e fixe.

Answer 3

si vous savez déjà que e * d doit être congru à 1 mod phi (n)

puisque vous connaissez phi (n) un tuple (e, d) peut être calculé en utilisant l'algorithme d'Euclide étendu (EEA):

choisir un entier pour e (généralement un petit entier, ce sera l'exposant public, le cryptage sera plus rapide avec des exposants plus petits) qui est inférieur à phi (n) et supérieur à 2 (? (je pense)

lorsque vous avez un candidat pour e, calculer le plus grand diviseur commun (gcd) de e et phi (n) ... devrait être 1 ... sinon, choisissez un nouveau candidat pour e et répétez (puisqu'il n'y aurait pas d'inverse modulaire, en d'autres termes, il n'y a pas d'exposant privé d pour cet e et phi (n))

après que vous savez que gcd (e, phi (n)) == 1 vous pouvez calculer d en utilisant l'EEE (ou en raccourci, calculer EEA directement car il fournira également le GCD ... si ce n'est pas 1, choisissez une nouvelle valeur pour e)

EEA (rapide et sale pour calculer l'inverse modulaire) :

imaginer une table avec 3 colonnes:

permet de dire que ces colonnes sont nommées: b, q et t

de sorte que les lignes de cette table ressemblera:

b0, q0, t0
b1, q1, t1 ...

(et ainsi de suite)

les 2 premières lignes seront initialement rempli. pour toutes les autres rangées, il existe une règle itterative qui peut être appliquée sur les deux dernières rangées qui se traduira par des valeurs pour la ligne suivante

les 2 premières lignes sont les suivantes:

phi (n), no_value, 0
e, le plancher (phi (n)/e), 1

la règle itterative pour créer la ligne suivante est la suivante: (où [] est un opérateur d'index pour sélectionner la rangée)

b [i ] = b [i-2] mod b [i-1]
q [i] = b [i-1]/b [i] (entier r division, no fractions ...)
t [i] = t [i-2] - (q [i-1] * t [i-1])

vous pouvez abandonner le schéma lorsque b [ i] devient 0 ou 1 ... vous n'avez pas vraiment besoin de q pour la dernière rangée ...

donc si b [i] est 0, b [i-1] ne peut pas être 1 puisque vous devriez avoir avorté lorsque vous avez calculé b [i-1] si c'était 1 ...

si vous atteignez b [i] == 0, b [i-1] est votre gcd ... puisque ce n'est pas 1 besoin d'une nouvelle valeur pour e

si b [i] == 1 votre gcd est 1, et il y a un inverse ...et qui est t [i] (si t est négatif, ajouter phi (n))

exemple avec des valeurs réelles:

disons phi (n) est de 120 disons que nous choisissons 23 en tant que candidat pour e

notre table ressemblera:

b  q  t 
120 –  0 
23 5  1 
5  4  -5 
3  1  21 
2  1  -26 
1  2  47 

la dernière calculée b est 1 so => ​​GCD (23120) == 1 (la preuve: l'inverse existe)
le dernier calculé t est 47 = > 23 * 47 mod 120 == 1 (t est l'inverse)

Answer 4

Dear Friend just follow this algorithm 

Key generation 
1) Pick two large prime numbers p and q, p != q; 
2) Calculate n = p × q; 
3) Calculate ø (n) = (p − 1)(q − 1); 
4) Pick e, so that gcd(e, ø (n)) = 1, 1 < e < ø (n); 
5) Calculate d, so that d · e mod ø (n) = 1, i.e., d is the multiplicative inverse of e in mod ø (n); 
6) Get public key as KU = {e, n}; 
7) Get private key as KR = {d, n}. 
Encryption 
For plaintext block P < n, its ciphertext C = P^e (mod n). 
Decryption 
For ciphertext block C, its plaintext is P = C^d (mod n). 

Code: 
#include<stdio.h> 
#include<conio.h> 
#include<stdlib.h> 
#include<math.h> 
#include<string.h> 

long int p,q,n,t,flag,e[100],d[100],temp[100],j,m[100],en[100],i; 
char msg[100]; 
int prime(long int); 
void ce(); 
long int cd(long int); 
void encrypt(); 
void decrypt(); 
void main() 
{ 
clrscr(); 
printf("\nENTER FIRST PRIME NUMBER\n"); 
scanf("%d",&p); 
flag=prime(p); 
if(flag==0) 
{ 
    printf("\nWRONG INPUT\n"); 
    getch(); 
    exit(1); 
} 
printf("\nENTER ANOTHER PRIME NUMBER\n"); 
scanf("%d",&q); 
flag=prime(q); 
if(flag==0||p==q) 
{ 
    printf("\nWRONG INPUT\n"); 
    getch(); 
    exit(1); 
} 
printf("\nENTER MESSAGE\n"); 
fflush(stdin); 
scanf("%s",msg); 
for(i=0;msg[i]!=NULL;i++) 
m[i]=msg[i]; 
n=p*q; 
t=(p-1)*(q-1); 
ce(); 
printf("\nPOSSIBLE VALUES OF e AND d ARE\n"); 
for(i=0;i<j-1;i++) 
printf("\n%ld\t%ld",e[i],d[i]); 
encrypt(); 
decrypt(); 
getch(); 
} 
int prime(long int pr) 
{ 
int i; 
j=sqrt(pr); 
for(i=2;i<=j;i++) 
{ 
    if(pr%i==0) 
    return 0; 
} 
return 1; 
} 
void ce() 
{ 
int k; 
k=0; 
for(i=2;i<t;i++) 
{ 
    if(t%i==0) 
    continue; 
    flag=prime(i); 
    if(flag==1&&i!=p&&i!=q) 
    { 
     e[k]=i; 
     flag=cd(e[k]); 
     if(flag>0) 
     { 
      d[k]=flag; 
      k++; 
     } 
     if(k==99) 
     break; 
    } 
} 
} 
long int cd(long int x) 
{ 
long int k=1; 
while(1) 
{ 
    k=k+t; 
    if(k%x==0) 
    return(k/x); 
} 
} 
void encrypt() 
{ 
long int pt,ct,key=e[0],k,len; 
i=0; 
len=strlen(msg); 
while(i!=len) 
{ 
    pt=m[i]; 
    pt=pt-96; 
    k=1; 
    for(j=0;j<key;j++) 
    { 
     k=k*pt; 
     k=k%n; 
    } 
    temp[i]=k; 
    ct=k+96; 
    en[i]=ct; 
    i++; 
} 
en[i]=-1; 
printf("\nTHE ENCRYPTED MESSAGE IS\n"); 
for(i=0;en[i]!=-1;i++) 
printf("%c",en[i]); 
} 
void decrypt() 
{ 
long int pt,ct,key=d[0],k; 
i=0; 
while(en[i]!=-1) 
{ 
    ct=temp[i]; 
    k=1; 
    for(j=0;j<key;j++) 
    { 
     k=k*ct; 
     k=k%n; 
    } 
    pt=k+96; 
    m[i]=pt; 
    i++; 
} 
m[i]=-1; 
printf("\nTHE DECRYPTED MESSAGE IS\n"); 
for(i=0;m[i]!=-1;i++) 
printf("%c",m[i]); 
}