Cómo utilizar VC para generar aleatoriamente un número primo grande (satisfaciendo el algoritmo RSA)
Lo que necesitas está incluido en este programa. Genera un número grande y luego haz la prueba de números primos RM. Si pasa, asumimos que es un número primo.
Algoritmo RSA
Este algoritmo apareció en 1978. Fue el primer algoritmo que pudo usarse tanto para cifrado de datos como para firmas digitales. Es fácil de entender y operar, y es popular. El algoritmo lleva el nombre de sus inventores: Ron Rivest, AdiShamir y Leonard Adleman. Sin embargo, la seguridad de RSA no ha sido probada teóricamente.
La seguridad de RSA se basa en el hecho de que grandes cantidades son difíciles de descomponer. Tanto la clave pública como la privada son funciones de dos números primos grandes (más de 100 dígitos decimales). Se especula que deducir el texto claro a partir de una clave y un texto cifrado es tan difícil como factorizar el producto de dos números primos grandes.
Generación de pares de claves. Elija dos números primos grandes, p y q. Cálculo: n = p * q Luego seleccione aleatoriamente la clave de cifrado e, lo que requiere que e y (p - 1) * (q - 1) sean primos relativos. Finalmente, se utiliza el algoritmo de Euclides para calcular la clave de descifrado d, que satisface e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) donde n y d también deben ser primos relativos. Los números e y n son claves públicas y d es la clave privada. Los dos números primos p y q ya no son necesarios y deben descartarse sin que nadie los sepa. Al cifrar información m (representación binaria), primero divida m en bloques de datos de igual longitud m1, m2,..., mi, con una longitud de bloque s, donde 2^s lt = n, s es lo más grande posible. El texto cifrado correspondiente es: ci = mi^e ( mod n ) ( a ) Al descifrar, se realiza el siguiente cálculo: mi = ci^d ( mod n ) ( b )
RSA se puede utilizar para firmas digitales, esquemas Se firma utilizando el tipo (a) y se verifica utilizando el tipo (b). Durante la operación específica, considerando factores como la seguridad y la gran cantidad de información m, la operación HASH generalmente se realiza primero. Seguridad RSA. La seguridad de RSA se basa en la descomposición de grandes números, pero no se ha demostrado teóricamente si es equivalente a la descomposición de grandes números, porque no hay pruebas de que romper RSA requiera una descomposición de grandes números. Supongamos que hay un algoritmo que no requiere descomposición de números grandes, entonces definitivamente se puede modificar a un algoritmo para descomposición de números grandes. En la actualidad, se ha demostrado que algunas variantes de algoritmos de RSA son equivalentes a la descomposición de números grandes. De todos modos, descomponer n es el método de ataque más obvio. Ahora, la gente puede descomponer números primos grandes con más de 140 dígitos decimales. Por lo tanto, el módulo n debe elegirse mayor, dependiendo de las condiciones específicas aplicables.
Dado que se realizan todos los cálculos de números grandes, RSA es 100 veces más lento que DES en su forma más rápida, ya sea que se trate de implementación de software o hardware. La velocidad siempre ha sido un inconveniente de RSA. Generalmente solo se usa para pequeñas cantidades de cifrado de datos.
*/
#include lt;iostreamgt;
#include lt;stdlib.hgt;
#include lt;time. hgt;
usando el espacio de nombres std; //parámetros necesarios para el algoritmo RSA
typedef struct RSA_PARAM_Tag
{
unsigned __int64 p, q ; //Dos números primos, no participan en operaciones de cifrado y descifrado
unsigned __int64 f; //f=(p-1)*(q-1), no participan en operaciones de cifrado y descifrado
unsigned __int64 n, e; //Clave pública, n=p*q, gcd(e, f)=1
unsigned __int64 d //Clave privada, e* d=1 (mod f), gcd(n, d)=1
unsigned __int64 s; // La longitud del bloque satisface el máximo s de 2^slt;=n, es decir, log2(n )
} RSA_PARAM; // Tabla de números primos pequeños
const static long g_PrimeTable[]=
{
3,
5,
p>7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71 ,
73,
79,
83,
89,
97
};
const static long g_PrimeCount=sizeof(g_PrimeTable) / sizeof(long); const unsigned __int64 multiplicador=12747293821
>const unsigned __int64 adder=1343545677842234541; //clase de número aleatorio
clase RandNumber
{
privado:
unsigned __int64 randSeed;
público:
p>
RandNumber(unsigned __int64 s=0);
unsigned __int64 Random(unsigned __int64 n);
};
RandNumber::RandNumber (__int64 s sin firmar)
{
si
(!s)
{
randSeed= (unsigned __int64)time(NULL
}
else
);{
randSeed=s;
}
}
unsigned __int64 RandNumber::Random(unsigned __int64 n)
{
randSeed=multiplicador * sumador randSeed
return randSeed n
}static RandNumber g_Rnd; >en línea sin firmar __int64 MulMod(sin firmar __int64 a, sin firmar __int64 b, sin firmar __int64 n)
{
return a * b n;
}
PowMod __int64 sin firmar (__int64 sin firmar y base, __int64 sin firmar y pow, __int64 sin firmar y n)
{
__int64 sin firmar a=base, b=pow, c=1 ;
mientras(b)
{
mientras(!(b amp; 1))
{
p>
bgt; gt; = 1; //a=a * a n; //La función parece ser capaz de manejar enteros de 64 bits, pero debido a que a*a aquí ha provocado un desbordamiento cuando agt; 2^32, por lo que el rango de procesamiento real no es de 64 bits
a=MulMod(a, a, n);
} b--; //c=a * c n ; // Aquí también se desbordará. Me pregunto si este problema se puede resolver si el entero de 64 bits se divide en dos enteros de 32 bits.
c=MulMod(a, c, n);
} return c;
}
long RabinMillerKnl(unsigned __int64 amp ;n)
{
unsigned __int64 b, m, j, v, i
m=n - 1; j=0; //0, primero calcula myj, de modo que n-1=m*2^j, donde m es un número impar positivo y j es un entero no negativo
while( !(m amperio; 1 ))
{
j;
mgt; Elija aleatoriamente a b, 2lt;=blt;n-1
b=2 g_Rnd.Random(n - 3); //2. > v=PowMod( b, m, n); //3. Si v==1, pasa la prueba
if(v == 1)
{
return 1 ;
} //4. Sea i=1
i=1 //5. p>
while( v != n - 1)
{
//6. Si i==l, número no primo, finaliza
if(i == j)
{
return 0;
} //7. 1
unsigned __int64 tmp1 = 2;
v=PowMod(v, tmp1, n);
i //8, bucle a 5
} return 1;
}
long RabinMiller(unsigned __int64 amp; n, bucle largo)
{
//Primer filtro con números primos pequeños, mejora la eficiencia
for(long i=0; i lt; g_PrimeCount; i )
{
if( n g_PrimeTable[i] == 0)
{
return 0;
}
} //Llame a Rabin-Miller tiempos de bucle de prueba para hacer que los números no primos pasen la prueba La probabilidad se reduce a (1/4)^loop
for(long i=0; i lt; loop; i )
{
if(! RabinMillerKnl(n))
{
return 0;
}
}
devuelve 1;
}
unsigned __int64 RandomPrime(char bits)
{
unsigned __int64 base;
do
{
base= (unsigned long)1 lt; (bits - 1); // Se garantiza que el bit más alto será 1
> base = g_Rnd.Random(base); //Agrega un número aleatorio
base|=1; // Se garantiza que el bit más bajo será 1, es decir, se garantiza que será un número impar.
} while(! RabinMiller(base, 30)); //Realiza la prueba de Rabin-Miller 30 veces
return base; //Todos los números pasados se consideran primos
}
unsigned __int64 EuclidGcd(unsigned __int64 amp; p, unsigned __int64 amp; q)
{
unsigned __int64 a=p gt; q ? p : q;
sin firmar __int64 b=p lt; q p : q; )
{
p>return p; //Si dos números son iguales, el máximo común divisor es él mismo
}
else
{
while(b) //División euclidiana, mcd(a, b)=mcd(b, a-qb)
{
a=a b;
t=a;
a=b
b=t
} return a;
}
}
unsigned __int64 SteinGcd(unsigned __int64 amp; p, unsigned __int64 amp; q)
{
sin signo __int64 a=p gt;
sin signo __int64 t; , r=1;
if(p == q)
{
return p; //Si dos números son iguales, el máximo común divisor es mismo
}
else
{
while((!(a amp; 1)) amp; amp; (!( b amp; 1)))
{
rlt;lt;=1; //Cuando a y b son números pares, gcd(a, b)=2*gcd(a/2, b/2)
agt;gt;=1
bgt; gt; = 1;
} if(!(a amp; 1))
{
t= a ; //Si a es un número par, intercambia a, b
a=b
b=t
} do
;{
while(!(b amp; 1))
{
bgt; = 1; número y a es un número impar, mcd(b, a)=mcd(b/2, a)
} if(b lt; a)
{
t=a; // Si b es menor que a, intercambia a, b
a=b
b=t
} b=(b - a) gt; gt; 1; //b y a son números impares, gcd(b, a)=gcd((b-a)/2, a)
} while( b);
return r * a;
}
}
unsigned __int64 Euclid(unsigned __int64 amp; a, unsigned __int64 amp; b)
{
unsigned __int64 m,e,i,j,x,y;
long xx,yy;
m=b;
e=a;
x=0;
y=1;
yy=1 ;
mientras(e)
{
i=m / e
j=m e;
m=e;
e=j;
j=y
y*=i; /p>
si(xx = = yy)
{
si(x gt; y)
{
y=x - y;
}
más
{
y-=x
;
yy=0;
}
}
más
{
y =x;
xx=1 - xx;
yy=1 - yy
} x=j; } if(xx == 0)
{
x=b - x
} return x; p>
RSA_PARAM RsaGetParam(void)
{
RSA_PARAM Rsa={ 0 };
unsigned __int64 t;
Rsa.p=RandomPrime(16); //Generar aleatoriamente dos números primos
Rsa.q=RandomPrime(16);
Rsa.n=Rsa.p * Rsa.q ;
Rsa.f=(Rsa.p - 1) * (Rsa.q - 1);
hacer
{
Rsa.e=g_Rnd.Random(65536); //Menos de 2^16, 65536=2^16
Rsa.e|=1; // Se garantiza que el bit más bajo será 1, es decir, se garantiza que será un número impar, porque f debe ser un número par y debe ser primo relativo, solo puede ser un número impar
} while(SteinGcd(Rsa.e, Rsa. f) != 1); Rsa.d=Euclid(Rsa.e, Rsa.f);
Rsa.s=0
t=Rsa.n gt; ; 1;
mientras(t)
{
Rsa.s; //s=log2(n)
tgt; gt;=1;
} return Rsa;
}
void TestRM(void)
{
unsigned long k=0;
cout lt; " - Rabin-Miller prime check.n" lt;
for(unsigned __int64 i=4197900001; i lt; 4198000000; i =2)
{
if(RabinMiller(i, 30))
{
k;
cout lt; i lt; endl;
}
} cout lt;
lt; lt; k lt; endl; /p>
char pSrc[]="abcdefghijklmnopqrstuvwxyz";
const unsigned long n=sizeof(pSrc);
unsigned char *q, pDec[n];
sin firmar __int64 pEnc[n];
r=RsaGetParam();
cout lt; ; endl;
cout lt;lt; "q=" lt;lt; r.q lt;lt; endl;
cout lt;lt; *(q-1)=" lt; lt; r.f lt; lt; endl;
cout lt; lt; "n=p*q=" lt; lt; r.n lt; lt; endl;
cout lt;lt; "e=" lt;lt; r.e lt;lt;
cout lt;lt; "d=" lt;lt; lt; endl;
cout lt;lt; "s=" lt;lt; r.s lt;lt; endl;
cout lt;lt; ; pSrc lt; lt;
q= (carácter sin firmar *)pSrc;
cout lt; unsigned long i=0; i lt; i )
{
unsigned __int64 tmp2 = q[i];
pEnc[i]=PowMod (tmp2, r.e, r.n);
cout lt;lt; hex lt;lt; pEnc[i] lt;lt; " ";
} cout lt;lt; ;
cout lt; "Decodificar:";
for(unsigned long i=0; i lt; n; i)
{
p>
pDec[i]=PowMod(pEnc[i], r.d, r.n);
cout lt;lt; hex lt;lt; (sin firmar largo)pDec[ i] lt; lt; " ";
} cout lt;
cout lt; (char *)pDec lt; >
}
int main(void)
{
TestRSA(
);
devuelve 0;
}