Cómo implementar el algoritmo RSA en lenguaje C

El algoritmo RSA es el primer algoritmo que se puede utilizar tanto para cifrado de datos como para firmas digitales. Es fácil de entender y operar, y es popular. Los nombres de los algoritmos llevan el nombre de sus inventores: Ron Rivest, Adi Shamir y Leonard Adleman. Sin embargo, la seguridad de RSA no ha sido probada teóricamente. Ha sufrido varios ataques y aún no ha sido violada por completo.

1. Algoritmo RSA:

Primero, encuentre tres números, p, q, r.

Entre ellos, pyq son dos números primos. número, r es un número primo relativo con (p-1)(q-1)

Los tres números p, q, r son la clave privada

A continuación, encuentre saca m, tal que rm == 1 mod (p-1)(q-1)

Esta m debe existir, porque r y (p-1)(q-1) son primos relativos, usa el método euclidiano Puedes obtenerlo

A continuación, calcula n = pq

m, estos dos números n son la clave pública

El proceso de codificación es, si los datos son a, trátelos como un entero grande, suponiendo que a n

Si a gt = n, exprese a como s carry (s lt; = n, generalmente s = 2^ t) ,

Luego, cada dígito es menor que n, y luego la codificación segmentada

A continuación, calcula b == a^m mod n, (0 lt; = b lt ; n),

b son los datos codificados

El proceso de decodificación consiste en calcular c == b^r mod pq (0 lt; = c lt; pq),

Entonces, una vez completada la decodificación, se demostrará que c y a son realmente iguales :)

Si un tercero escucha a escondidas, obtendrá varios números: m, n( =pq), b

Si quiere decodificar, debe encontrar una manera de obtener r

Entonces, primero debe factorizar n en factores primos.

Para evitar su descomposición, la mayoría Una forma eficaz es encontrar dos números primos muy grandes p, q,

Esto dificultará que un tercero factorice

lt Teorema gt; > p>

Si p y q son números heterogéneos, rm == 1 mod (p-1)(q-1),

a es cualquier entero positivo, b == a^ m mod pq, c == b^r mod pq,

Entonces c == a mod pq

El proceso de demostración utilizará el pequeño teorema de Fermat, que se describe a continuación: < / p>

m es cualquier número primo, n es cualquier número entero, entonces n^m == n mod m

(En otras palabras, si n y m son primos relativos, entonces n^ (m -1) == 1 mod m)

Usando algunos conocimientos básicos de teoría de grupos, puedes probar fácilmente el pequeño teorema de Fermat

lt

Porque; rm == 1 mod (p-1)(q-1), entonces rm = k(p-1)(q-1) 1, donde k es un número entero

Porque en módulo se preserva multiplicación

(x == y mod z and u == v mod z =gt; xu == yv mod z),

Entonces, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1) 1) mod pq

1. Si a no es múltiplo de p o q,

entonces a^(p-1) == 1 mod p (Pequeño Teorema de Fermat) =gt; mod p

a^(q-1) == 1 mod q (tarifa

El pequeño teorema de Ma) =gt; a^(k(p-1)(q-1)) == 1 mod q

Por lo tanto, p y q pueden dividir a^(k(p-1) )) (q-1)) - 1 =gt; pq | a^(k(p-1)(q-1)) - 1

Es decir, a^(k(p-1) )(q- 1)) == 1 mod pq

=gt; c == a^(k(p-1)(q-1) 1) == a mod pq

2 . Si a es múltiplo de p, pero no múltiplo de q,

entonces a^(q-1) == 1 mod q (El pequeño teorema de Fermat)

=gt; 1) 1) == a mod q

=gt; q | c - a

porque p | (k(p -1)(q-1) 1) == 0 mod p

=gt | p | a

Por lo tanto, pq | ; c == a mod pq

3. Si a es múltiplo de q, pero no múltiplo de p, la prueba es la misma que la anterior.

4. un múltiplo de p y q,

Entonces pq | a

=gt; c == a^(k(p-1)(q-1) 1) == 0 mod pq

=gt; c - a

=gt; c == a mod pq

Q.E.D.

Este teorema muestra que a se codifica en b y luego se decodifica cuando c, a == c mod n (n = pq)

Pero cuando codificamos y decodificamos, el límite es 0 lt = a; lt; n, 0 lt; = c lt;

Entonces esto significa que a es igual a c, por lo que este proceso realmente puede realizar la función de codificación y decodificación

2. La seguridad de RSA

La seguridad de RSA depende de Se puede utilizar para descomponer números grandes, pero no se ha demostrado teóricamente si es equivalente a descomponer números grandes, porque no hay pruebas de que descifrar RSA requiera descomponer 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. Hoy en día, la gente puede factorizar números primos grandes con varios dígitos decimales. Por lo tanto, el módulo n

debe elegirse mayor, dependiendo de las condiciones específicas aplicables.

3. La velocidad de RSA

Dado que se realizan todos los cálculos con números grandes, el RSA más rápido es varias veces más lento que DES, ya sea implementado en software o hardware. La velocidad siempre ha sido un inconveniente de RSA. Generalmente solo se usa para pequeñas cantidades de cifrado de datos.

4. El ataque de texto cifrado elegido por RSA

RSA es vulnerable a los ataques de texto cifrado elegidos. Generalmente, un atacante disfraza cierta información (Blind) y le pide a una entidad con una clave privada que la firme. Luego, después del cálculo, se puede obtener la información que se desea.

De hecho, los ataques explotan la misma debilidad, que es el hecho de que la exponenciación preserva la estructura multiplicativa de la entrada:

(XM)^d = X^d *M^d mod n

Como se mencionó anteriormente, este problema inherente proviene de la característica más útil de la criptografía de clave pública: todos pueden usar la clave pública. Sin embargo, este problema no se puede resolver algorítmicamente. Hay dos medidas principales: una es utilizar un buen protocolo de clave pública para garantizar que la entidad no descifre información generada arbitrariamente por otras entidades durante el proceso de trabajo y no descifre ninguna información generada. Firme con información conocida; el otro es nunca firmar documentos aleatorios enviados por extraños. Al firmar, primero use la función Hash unidireccional para HASH del documento o use diferentes algoritmos de firma al mismo tiempo. En . se mencionan varios tipos diferentes de métodos de ataque.

5. Ataque de módulo público de RSA

Si hay un módulo en el sistema, pero diferentes personas tienen diferentes e y d, el sistema será peligroso. La situación más común es que la misma información se cifra con diferentes claves públicas. Estas claves públicas son completamente modulares y mutuamente primarias, por lo que la información se puede recuperar sin la clave privada. Supongamos que P es el texto sin formato del mensaje, las dos claves de cifrado son e1 y e2 y el módulo público es n, entonces:

C1 = P^e1 mod n

C2 = P^e2 mod n

Si el criptoanalista conoce n, e1, e2, C1 y C2, puede obtener P.

Debido a que e1 y e2 son primos mutuamente, r y s se pueden encontrar usando el algoritmo euclidiano, satisfaciendo:

r * e1 s * e2 = 1

Supongamos que r es un número negativo, debe usar el algoritmo euclidiano para calcular C1^(-1), luego

( C1^(-1) )^(-r) * C2^s = P mod n

Además, existen varios otros métodos para utilizar ataques de módulo público ***. En resumen, si conoce un par de e y d de un módulo dado, uno es útil para que el atacante descomponga el módulo y el otro es útil para que el atacante calcule otros pares de e' y d' sin descomponer el módulo. . Sólo hay una solución y es no compartir el módulo n.

Pequeño ataque exponencial a RSA. Una sugerencia para mejorar la velocidad de RSA es hacer que la clave pública e tome un valor menor, lo que facilitará la implementación del cifrado y mejorará la velocidad. Pero esto no es seguro. La solución es tomar valores mayores tanto para e como para d.

El algoritmo RSA es

el primer algoritmo que se puede utilizar tanto para cifrado como para firmas digitales. Además, es fácil de entender y operar. RSA es el algoritmo de clave pública más estudiado. Han pasado casi veinte años desde que se propuso. Ha experimentado varios ataques y gradualmente ha sido aceptado por la gente. En general, se lo considera uno de los mejores algoritmos de clave pública. los esquemas clave. La seguridad de RSA se basa en la factorización de números grandes, pero no se ha demostrado teóricamente que la dificultad de descifrar RSA sea equivalente a la dificultad de factorizar números grandes. Es decir, el principal defecto de RSA

es que es imposible comprender teóricamente su rendimiento de confidencialidad

, y la mayoría de las personas en la comunidad criptográfica tienden a creer que la factorización no es un problema de PNJ.

Las principales desventajas de RSA son: A) Es problemático generar la clave. Está limitado por la tecnología de generación de números primos, por lo que es difícil lograr un cifrado único. B) La longitud del bloque es demasiado grande para garantizar la seguridad, n debe ser de al menos 600

bits

o más, lo que hace que la operación cueste muy alto, especialmente cuanto más lento y más. los algoritmos criptográficos simétricos son varios órdenes de magnitud más lentos y con el desarrollo de la tecnología de descomposición de grandes números, esta longitud sigue aumentando, lo que no favorece la estandarización de los formatos de datos. Actualmente, el protocolo SET (Transacción electrónica segura) requiere que la CA utilice una clave de un bit y que otras entidades utilicen claves de un bit.

Implementación del lenguaje C

#include lt;stdio.hgt;

int candp(int a, int b, int c)

{ int r=1;

b=b 1;

mientras(b!=1)

{

r= r*a;

r=rc;

b--;

}

printf("d\n", r );

return r;

}

void main()

{

int p, q , e, d, m, n, t, c, r;

char s;

printf("ingrese p, q: "); p>scanf("dd",amp;p,amp;q);

n=p*q;

printf("la n es 3d\n",n) ;

t=(p-1)*(q-1);

printf("la t es 3d\n", t);

printf("ingrese la e: ");

scanf("d",amp;e);

if(elt;1||egt;t)

{

printf("e es un error, ingrese nuevamente: ");

scanf("d", amp; e