Romper la criptografía

En este artículo, discutiremos la descripción general de los protocolos de cifrado simétrico y cómo surgió la necesidad del cifrado asimétrico . Aquí discutiremos la descripción general, los ejemplos de criptografía y las reglas para romper la criptografía. Discutámoslos uno por uno.

Descripción general: 
una clave codifica los mensajes y esa misma clave puede descifrar los mensajes. Luego, Alice y Bob pueden intercambiar mensajes una vez que acuerden una clave. Pero, ¿cómo pueden ambos ponerse de acuerdo sobre una clave secreta en una red que es monitoreada por espías? ¡Supongamos que el espía es Eaves! Ahora, para resolver el problema, usamos la clave asimétrica en su lugar.

Ejemplo –

Alice cifra su mensaje con la clave pública de Bob porque solo Bob puede descifrar el mensaje con su propia clave privada. Del mismo modo, Bob encripta su mensaje con la clave pública de Alice que solo puede descifrarse con la clave privada de Alice. Ahora, Alice también puede usar este método para autenticarse ante Bob. Puede cifrar su mensaje con su clave privada y luego cifrar ese resultado con la clave pública de Bob. Cuando Bob descifra el mensaje con su propia clave privada, ve que ya existe una capa interna de cifrado. Ahora, si esto se puede encriptar con la clave pública de Alice, entonces estará seguro de que fue Alice quien lo encriptó.

Generar una clave privada:
ahora entremos en la esencia de cómo se generaron estas claves en primer lugar de la siguiente manera.

Acercarse –

1. Generar una clave privada es computacionalmente muy difícil de producir. Simplemente no se puede producir mediante ingeniería inversa de la clave pública producida por un algoritmo llamado algoritmo RSA.
2. ¿Cuál es el protocolo del algoritmo RSA?
3. Producimos un número (N) que es un producto de dos números primos (digamos p y q)
4. Ahora, el número producido es bastante grande (casi cien a mil dígitos).

p ∗q = N

Ejemplo:
entendámoslo con un ejemplo simple de la siguiente manera.

Paso 1:
Usando el protocolo anterior, definamos n usando la multiplicación de dos números primos. (Tomar un número primo directamente puede hacer que los cálculos sean complejos).

p=61, q =53.
compute N.  
N = p*q
N = 3233
Applying Euler's Totient function,  
∅(n) = ∅(p*q)
     = ∅(p) * ∅(q)
     = (p-1)*(q-1)
     = 60*52
     = 3120

Paso 2:
No tomamos N directamente porque se habría vuelto complejo para nosotros calcular una cantidad de números que son coprimos.

Choose 'e' ; 1<=e<= ∅(n), co prime to  ∅(n)
Going by that, if we take e = 17
Then,  Gcd(17,3120) should be = 1 
(that means the numbers should be co-prime to each other.)

our public key is :(e,N)= (17,3233)

Paso 3:
ahora determinemos la clave privada: (d, N)

e d = 1 mod ∅(n)
here e and ∅(n) are co primes to each other
Now going by the concept of Multiplicative Inverse we have,
d =  e-1 mod ∅(n)
Finding d:
d is calculated using the formula:
= [(∅(n) * i)+1]/e

Paso 4:
Seguimos calculándolo cambiando los valores de i. Aquí tomamos I como 1,2,3…, etc. hasta llegar a una respuesta donde obtenemos un número no decimal.

at i = 15, we get d as 2753
hence our private key becomes:
(d,N)=(2753,3233)

Paso 5:
Después de generar las claves públicas y privadas, realizamos el cifrado y descifrado.

(m e)d ≡ m mod N, 
 where 
 m - It is the message. Such computation is a one way function.

La fuerza del algoritmo RSA radica en N. Cuanto mayor es el número N, más lento se vuelve para sacar sus factores primos.

Romper la criptografía:
Habiendo discutido esto, ¡vamos a ver cómo podemos romper la criptografía!

1. Descifrar sistemas seguros abiertos sería fácil si supiéramos cómo tener en cuenta grandes cantidades.
2. RSA utiliza estos factores primos como claves para descifrar estos mensajes. ¡Para eso, necesitaremos encontrar los factores primos de un número realmente enorme!
3. Ahora, esto puede volverse bastante aburrido y llevar mucho tiempo.
4. Tendremos que tener un plan estratégico para tenerlos en cuenta. Euler, un famoso matemático vino al rescate. Contempló los números primos y
5. Dio varios postulados como la aritmética modular. Básicamente, dio todas las matemáticas bajo criptografía RSA.
6. Aritmética modular:
7. Aquí consideramos el resto al dividir dos números.

a ≡ x mod N
when we divide a/N, the remainder is --> x
2 × 3 = 6
6/5 = 1
so,  
2 × 3 mod 5 is 1
its written as:
2*3 ≡ 1 mod 5

Relación entre exponenciación y aritmética modular:
Veamos la relación entre exponenciación y aritmética modular de la siguiente manera. 

Entendamos con la ayuda de ejemplos.

1. Si tomamos potencias de 3 (3 ^k ) obtendremos los números como 3,9.27,81,243
2. Ahora, si tomamos la moda de los números con 10, obtenemos una secuencia como 9,7,1,3,9,7,1,3… y así sucesivamente.
3. Observamos que la secuencia de potencia aumenta, pero el ciclo modular se repite.
4. También observamos que el último dígito del patrón siempre es 1.
5. Ahora, siempre que x y N sean coprimos, x mod N, x ² mod N, x ³ mod N… todos ellos mantendrán esta propiedad.
6. Llamamos período a la duración del patrón repetitivo.
7. Aquí, el período de 3 mod 10 es 4 (ya que después de cada cuarto dígito se repite el patrón).
8. El período es el número más pequeño ‘r’, tal que,

x r ≡ 1 mod N

Cálculo del factor de un número:
ahora veamos cómo la aritmética modular, la exponenciación y el período se relacionan con el cálculo de los factores del número.

Digamos que te dan un número N y también te dan sus factores, p y q. No se sabe nada acerca de p y q.

N = p .q

Paso 1: 
Elija cualquier número menor que N. Llamémoslo ‘a’. Comprueba si a y N son primos. Comprobamos esto tomando el MCD de ambos. MCD(a, N)=1, entonces son coprimos entre sí.

Paso 2: 
el segundo paso es calcular el período de un mod N. En este ejemplo, tomamos N = 32 y asumimos a = 8 (ya que ambos son primos entre sí). Supongamos que el período ser ‘r’.

powers of 8 = 8,64,512,4096.....
mod 35 = 8,29,22,..1
We compute r to be as 4.

Para hacer el ejercicio aritmético, necesitaremos dividir r entre 2. Entonces, necesitamos saber que r es par. Más tarde, también necesitaremos saber que a ^r/2 + 1 ≇ 0 mod N. Si alguna de estas cosas falla, necesitaremos elegir una ‘a’ diferente en el paso inicial.

Paso 3: 
Para el paso 3, tenemos que hacer algo de álgebra de la siguiente manera. Comencemos con las cosas que sabemos.

ar ≡ 1 mod N
which on subtracting 1, gives  
ar  - 1 ≡ 0 mod N

Decir algo como arriba es equivalente a decir que es un múltiplo de N (ya que el resto obtenido aquí es 0). Entonces, debe existir algún número entero ‘k’ tal que:

ar - 1  = k .N
Since we assumed 'r' as an even number here, we can write it as : 
(a r/2 - 1 )(a r/2 +1 )= k. N

Since N=p .q, so we replace N with  p . q
(a r/2 - 1 ) (a r/2 +1 ) = k. p .q

Since, we have the period of 8 mod 35 as 4, we can write it as:
84 ≡ 1 mod 35

so, 84 - 1 ≡ 0 mod 35 (its equivalent to saying that its a multiple of N)
So we can re write it as: 84 - 1 = k . 35
rewriting this as (since r is even here):

(8r/2 - 1)(8r/2 + 1) = k. p .q (where p .q are the prime factors of N)

Paso 4: 
Ahora, el paso 4 es calcular p & q. Asumimos aquí que MCD((a ^r/2 – 1), N) es uno de los factores primos. Llamémoslo p. Y MCD((a ^r/2 + 1), N) es otro factor primo. Llamémoslo q. En la ecuación (a ^r/2 – 1)(a ^r/2 + 1) = kp q asumimos que p debe dividir uno de los factores del lado izquierdo y q también debe dividir uno de los factores del lado izquierdo . Ambos no pueden dividir los mismos factores en el lado izquierdo ya que ese factor sería divisible por N.

Algoritmo de Shor:
hacemos suposiciones de la siguiente manera.

p divides (ar/2 - 1) and q divides (ar/2 + 1)
We get, p = Gcd(63,35) = 7
and q is the Gcd(65,35) = 5

Hagamos un resumen rápido de lo que hicimos de la siguiente manera.

1. Tome ‘a’ menos que N.
2. Encuentre el período de un mod N
3. Reorganizar con álgebra
4. Sean p = Mcd ((a ^r/2 – 1), N) y q = Mcd ((a ^r/2 + 1), N)

¡Y listo! Has destruido el sistema de seguridad. Pero sabemos que RSA todavía funciona y sacar el período lleva mucho tiempo. Pero aquí viene el papel de las computadoras cuánticas. Son excelentes para calcular el período. Lo anterior fue el esquema del Algoritmo de Shor.