¿Cómo resolver problemas de algoritmo RSA?

El algoritmo RSA es un algoritmo criptográfico asimétrico, lo que significa que debe haber dos claves involucradas durante la comunicación, es decir, clave pública y clave privada. Hay pasos simples para resolver problemas en el Algoritmo RSA.

Ejemplo 1:

Paso 1: Elija dos números primos $p$ y $q$
Tomemos $p = 3$ y $q = 11$
Paso 2: Calcule el valor de y
se da como,
```
 and 
```
Aquí en el ejemplo,
$n = 3 \times 11 = 33$
$\phi = (3-1) \times (11-1) = 2 \times 10 = 20$
Paso 3: Encuentre el valor de $e$ (clave pública)
Elija $e$ , de modo que $e$ debería ser coprincipal. Co-prime significa que no debe multiplicarse por factores de $\phi$ y tampoco dividirse por $\phi$
Los factores de $\phi$ son, $20 = 5 \times 4 = 5 \times 2 \times 2$ por lo $e$ que no deben multiplicarse por $5$ y $2$ no deben dividirse por 20.

Entonces, los primos son 3, 7, 11, 17, 19…, como se toman 3 y 11 se elige $e$ como 7

Por lo tanto, $e = 7$
Paso 4: Calcule el valor de (clave privada)
La condición se da como,
donde y es el valor de .
Para calcular el valor de $d$ ,
1. Forme una tabla con cuatro columnas, es decir, a, b, d y k.
2. Inicialice a = 1, b = 0, d = $\phi$ , k = – en la primera fila.
3. Inicialice a = 0, b = 1, d = $e$ , $k = \frac{\phi}{e}$ en la segunda fila.
4. Desde la siguiente fila, aplique las siguientes fórmulas para encontrar el valor de los siguientes a, b, d y k, que se da como
  - $a_{i} = a_{i-2} - (a_{i-1} \times k_{i-1})$
  - $b_{i} = b_{i-2} - (b_{i-1} \times k_{i-1})$
  - $d_{i} = d_{i-2} - (d_{i-1} \times k_{i-1})$
  - $k_{i} = \frac{d_{i-1}}{d_{i}}$
Tan pronto como, $d = 1$ detenga el proceso y verifique la siguiente condición
```
if 
    
if 
    
```
Para un ejemplo dado, la tabla será,

a b d k

1 0 20 –

0 1 7 2

1 -2 6 1

-1 3 1 –

Como en la tabla anterior $d = 1$ , detenga el proceso y verifique la condición dada para el $b$
$\therefore b = 3$

Para verificar que $b$ es correcto, la condición anterior debe cumplirse, es decir,
$gcd(\phi, e) = \phi x + ey = (20 \times -1) + (7 \times 3) = 1$ . Por lo tanto $d$ es correcto.
Paso 5: realice el cifrado y el descifrado
El cifrado se proporciona como, el
$c = t^{e}\mod n$
descifrado se proporciona como,
$t = c^{d}\mod n$
Para el ejemplo dado, supongamos $t = 2$ que el
cifrado es $c = 2^{7}\mod 33 = 29$

El descifrado es $t = 29^{3}\mod 33 = 2$

Por lo tanto, en la final, $p = 3$ , $q = 11$ , $\phi = 20$ , $n = 33$ , $e = 7$ y $d = 3$

a	b	d	k
1	0	20	–
0	1	7	2
1	-2	6	1
-1	3	1	–

Ejemplo-2: GATE CS-2017 (Conjunto 1)
En un criptosistema RSA, un A en particular usa dos números primos p = 13 y q = 17 para generar sus claves públicas y privadas. Si la clave pública de A es 35. ¿Entonces la clave privada de A es?

$p = 13$ y $q = 17$
Calcular $n = 13 \times 17 = 221$ y $\phi = (13-1) \times (17-1) = 12 \times 16 = 192$
$e = 35$ (Llave pública)
Calcular $d$ (clave privada)

a b d k

1 0 192 –

0 1 35 5

1 -5 17 2

-2 11 1 –

$\therefore d = 11$ (llave privada)