¿Qué es la criptografía de clave pública en términos simples? ¿Cómo se relaciona con los números primos?

Para comprender realmente la importancia de la criptografía de clave pública (a partir de ahora PKC), uno debe comprender la alternativa.

Antes de PKC, uno tenía que confiar en esquemas de criptografía simétrica. Un ejemplo simple es un cambio del alfabeto. Por ejemplo, podríamos elegir el mapeo:

ABCDEFGHIJKLMNOPQRSTU VWXYZ

qslonpbvwjhukcgyxirmdfeatz

Ahora es fácil enviar un mensaje, diga:

Hola

que se convierte en:

vnuug mvnin

Del mismo modo, es fácil para el receptor recuperar el mensaje original si ambas partes tienen la clave (es decir, el alfabeto de conversión). Por supuesto, hay muchos esquemas no PKC mucho más avanzados; Sin embargo, todos confían en el hecho de que una clave debe ser compartida.

Esto significa que los bancos, por ejemplo, necesitan personas que viajen por todo el mundo para distribuir estas claves. Nunca podría comunicarse de forma segura con nadie si no hubiera compartido un código en una reunión anterior.
Puedes ver cómo esto simplemente no es factible en la sociedad moderna.

Aquí es donde entra en juego la idea de la criptografía asimétrica. ¿Qué pasa si las dos personas no necesitan usar la misma clave? ¿Se podría imaginar un esquema de codificación en el que una clave se usa para encriptar y otra clave para desencriptar? Si esto fuera realmente posible, entonces el problema está resuelto.

Imagine un sistema así y diga que quiero enviarle un mensaje. Le escribo, sin encriptar, que quiero enviarle un mensaje seguro. Luego me envía su clave de cifrado (esta es la clave pública, ya que cualquiera puede obtenerla) y la uso para cifrar el mensaje. Una vez que lo he cifrado, ni siquiera puedo descifrarlo yo mismo. La clave de descifrado es necesaria para hacer eso. Pero, por supuesto, eres el único que tiene ese.
Así que ahora puedo enviarle el mensaje de manera segura y, aunque muchas otras personas podrían leer este mensaje cifrado, también pueden descifrarlo, ya que también poseen la clave de cifrado pública.

Esta es una idea En realidad, sin embargo, dicho sistema no existe. Siempre podrá descifrar el mensaje utilizando la clave pública de cifrado (un método simple es que intente cifrar cada combinación de caracteres hasta que la salida sea la cadena cifrada, entonces sabe que debe haber sido el mensaje original. Pero bruto- forzar así es muy lento). No obstante, puede ser extremadamente difícil descifrar usando solo la clave de cifrado.

Una realización de tal sistema es el sistema RSA. Simplificado mucho, la idea es esta:

Encuentra dos números primos, llámalos [matemáticas] p [/ matemáticas] y [matemáticas] q [/ matemáticas]. Este par [math] (p, q) [/ math] es su clave privada de descifrado.
Multiplíquelos para formar [math] n = p \ cdot q [/ math]. Esta [matemática] n [/ matemática] es su clave de cifrado pública. Las personas inteligentes detrás de RSA encontraron un sistema en el que el cifrado se puede hacer solo con [math] n [/ math], pero el descifrado necesita [math] (p, q) [/ math].

Si solo recibe [math] n [/ math], y [math] n [/ math] es muy grande, entonces es extremadamente difícil encontrar el par único (math) ] (p, q) [/ math] que produce [math] n [/ math]. Esta es la seguridad detrás de RSA. Si alguien encontrara un algoritmo eficiente para factorizar primos (es decir, encontrar [matemáticas] (p, q) [/ matemáticas] de [matemáticas] n [/ matemáticas]), entonces RSA está condenado y todas nuestras transferencias bancarias son básicamente abierto al público.
Se ha encontrado uno de estos algoritmos (Shor’s), pero requiere una computadora cuántica, por lo que probablemente sea un tiempo. Y si de hecho tuviéramos computadoras cuánticas, también tendríamos un cifrado perfecto, pero ese es otro asunto.

Supongamos que Alice quiere enviarle un secreto a Bob. En el cifrado regular de una sola clave, Alice cifrará el secreto con una clave ‘k’ y Bob tendrá que descifrarlo utilizando la ‘misma clave’. Sin embargo, el desafío aquí es tener que ‘comunicar’ la clave a Bob (que es otro secreto otra vez, y que podría tener que enviarse previamente a través de un canal inseguro).

El cifrado de clave pública es donde, Alice puede cifrar usando la clave públicamente conocida de Bob (que no es ningún secreto), mientras que Bob descifra usando una clave privada que solo él conoce . Los ‘pares’ de claves públicas y privadas se han generado a priori para Bob utilizando pocas técnicas, y la clave pública se ha publicado para que todos la conozcan en un directorio de claves públicamente disponible. Esto también se llama ‘criptografía de clave asimétrica’. Las claves de cifrado y descifrado son diferentes, y es muy difícil descifrar la clave de descifrado dada la clave de cifrado conocida públicamente. Esta técnica ahora no sufre la limitación anterior.

Pocas técnicas de generación de ‘pares de claves público-privadas’ implican ‘factorización prima’ (descomponer un gran número compuesto en factores no triviales). Así es como probablemente se relaciona con los números primos (a nivel de técnica matemática).

Aquí hay una descripción general interesante que usa pintura de colores para ilustrar todo el proceso, incluyendo por qué los números primos son importantes: