Los cifrados y los códigos utilizan muchas herramientas de álgebra abstracta, teoría de números. y álgebra lineal que incluye: congruencias, teoría de residuos cuadráticos, teoría de campo, matrices, grupos no conmutativos, varios algoritmos matemáticos, funciones hash y algoritmos cuánticos.
Todas estas herramientas son parte de matemáticas discretas.
Un ejemplo es el famoso algoritmo RSA que habilita un sistema de cifrado de clave pública, en el que todos saben cómo cifrar, pero solo alguien con una clave privada especial puede descifrar.
Así es como funciona (muy brevemente):
- ¿El curso de B.Com (F&A) en Cristo es demasiado agitado?
- ¿Qué hacen las personas con un título en arquitectura, excepto dibujar? ¿Cuál es su historia trabajando fuera del campo de la arquitectura?
- ¿Por qué la infraestructura de JBIMS es tan pobre a pesar de alumnos tan famosos?
- ¿Qué es la educación básica?
- ¿La universidad Shiv Nadar es buena para la ingeniería química? ¿Qué empresas ofrecen pasantías?
Dos números se hacen públicos. Juntos, estos se llaman la clave pública. Uno de estos números es un producto pq de dos números primos, y el otro es un número que llamaremos “e” que por razones técnicas debe ser relativamente primo para (p-1) * (q-1). Es decir, el máximo común divisor de e y (p-1) * (q-1) debe ser igual a 1. (La razón de esto es muy importante, pero lo distraería al explicar por qué aquí).
Por ejemplo, podemos elegir p = 5 y q = 11, y e = 21. Tenga en cuenta que (5–1) * (11–1) = 40, y que el mcd (21, 40) = 1.
Para cifrar un mensaje, primero se convierte a una secuencia de enteros. Hay muchas maneras de hacer esto, algunas mucho mejores que otras. Luego, uno por uno, encriptas los enteros. Para cifrar un entero x, calcule x ^ e mod pq.
Los números pq y e son públicos para que cualquiera pueda cifrar cualquier número entero. Por ejemplo, para cifrar el número 6 calculamos 6 ^ 21 mod 55 = 46. No es obvio cómo hacer esto en la cabeza, pero las matemáticas discretas proporcionan algoritmos rápidos (eficientes) para la exponenciación modular.
La mejor parte de este esquema es que la forma obvia de descifrar 46 es probar la fuerza bruta con todos los valores posibles para x, elevarlos a la novena potencia y modificar en 55. Esta idea de fuerza bruta es demasiado lenta porque cuando usamos p y q muy grandes, el número resultante de x posibles es demasiado grande para gestionarlo de manera eficiente.
Sin embargo, utilizando algunas matemáticas más discretas (el pequeño teorema de Fermat, la teoría de congruencia y el algoritmo extendido de Euclides), podemos calcular eficientemente un exponente mágico de decodificación d que tomará 46 y volverá a 6. La matemática es encontrar d tal que ed = 1 mod (p-1) (q-1). (Encontrar este exponente mágico de descifrado y comprender por qué funciona es complicado). Una vez más, las matemáticas discretas nos dan un algoritmo eficiente para hacer esto, siempre que sepamos qué es (p-1) (q-1). En nuestro caso, el exponente de decodificación mágica también es 9 (por lo general no es el mismo número), por lo que para descifrar 46 necesitamos calcular 46 ^ 9 mod 55 = 6.
Por lo tanto, lo único que impide que alguien descifre un mensaje RSA codificado públicamente es que no sabe (p-1) (q-1). Y, la única forma de averiguar ese número es obtenerlo de pq, lo que requeriría factorizar pq, y nadie sabe cómo hacerlo de manera eficiente. Por lo tanto, las únicas personas que pueden descifrar los mensajes RSA codificados públicamente son las personas que crearon pq en primer lugar, porque solo ellos saben pyq.
Esa es la punta del iceberg. Hay mucho más, pero este único ejemplo debería darle una idea de cómo las matemáticas discretas están intrínsecamente relacionadas con la criptología.