online - rsa criptografia asimetrica




encriptaciĆ³n: algoritmo RSA (3)

Estoy implementando el algoritmo RSA para el cifrado y descifrado como se indica aquí:

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

Pero no pude entender la parte aleatoria de generación de números primos en la generación de claves. Así que estoy tomando dos números primos como entradas del usuario. Tuve dificultades para generar el e también. así que lo hice constante (e = 17)

Algunas entradas de números primos funcionan correctamente (es decir, codifican y decodifican correctamente) en gcc bajo Linux pero no en devcpp bajo Windows. (por ejemplo, 53,61)

Aquí está el código de generación de claves:

/* 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);

}

Necesito ayuda y sugerencias en el número primo y la generación e.


No tengo la respuesta, pero si el mismo código compilado con dos compiladores diferentes da respuestas diferentes, supongo que algunos de los tipos son de diferente tamaño o está implícitamente confiando en un comportamiento indefinido en alguna parte.

Lo primero que debe hacer es que, dados los mismos pares de números primos, compruebe que todas las constantes que genera sean iguales en ambas implementaciones. De lo contrario, los algoritmos de generación de par de claves tienen la culpa.

Lo siguiente es asegurarse de que sus datos de entrada para el cifrado sean absolutamente idénticos en ambos sistemas. Preste especial atención a la manera en que maneja los caracteres de final de línea. Tenga en cuenta que, en Windows, el final de línea es \r\n y en Linux es \n . La mayoría de las implementaciones de bibliotecas de Windows convertirán \r\n a \n medida que se lea el archivo si se proporciona "r" como parámetro de modo para fopen() . Su implementación puede ser diferente.

Finalmente, cualquiera que sea el problema, de ninguna manera el uso se gets() Si incluso te encuentras pensando en usarlo de nuevo, debes eliminar los lóbulos frontales de tu cerebro con un punzón.


Siguiendo las notas prácticas al final de la página enlazada, llegaría a algo así para la generación principal:

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 se supone que es una implementación de la prueba de Miller-Rabin . La función anterior hace ciertas suposiciones y tiene algunos inconvenientes:

  • int es 32 bit
  • RAND_MAX es más grande que 65536
  • rand() generalmente no es un buen generador de números aleatorios para usar en el cifrado serio
  • Los primos generados son de 16 bits por lo que obviamente no son lo suficientemente grandes como para una encriptación seria de todos modos

No use esto en ningún código de producción.

Según el artículo, parece correcto elegir e corregido.


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]); 
}