Criptografía de clave pública simplemente explicada

Foto de Liam Macleod en Unsplash

La criptografía de clave pública parece mágica para todos, incluso para aquellos que la entienden. En esta publicación, voy a explicar la criptografía de clave pública. La criptografía de clave pública se basa en la criptografía asimétrica, así que primero hablemos de la criptografía simétrica.

Criptografía simétrica

Su puerta de entrada generalmente está cerrada con llave. Esta llave desbloquea y bloquea la puerta principal. Con la criptografía simétrica, tiene una clave que usa para desbloquear y bloquear cosas.

Solo las personas con la llave o una copia de la llave pueden abrir la puerta. Ahora, imagina que estás de vacaciones en Bali. Quieres invitar a tu amigo a cuidar a tu gato 😺 mientras estás en las hermosas playas 🏖️.

Antes de las vacaciones, le das a tu amigo la llave de tu puerta. Luego le roban a su amigo, por lo que ahora alguien más tiene la llave de su puerta de entrada. O tu amigo lo deja tirado y alguien lo clona. El problema con la criptografía de clave simétrica es que esta clave es fácil de clonar, es fácil atacar su casa de muchas maneras diferentes.

Llevemos esto de una analogía a un ejemplo de la vida real de criptografía simétrica.

Cifrado de César

Julius Caeser usó un cifrado para enviar mensajes que nadie más podía leer excepto el destinatario previsto. Principalmente porque nadie podía leer en el año 100 a. C., y aquellos que podían no entenderían una cadena aleatoria de letras. Ese es el objetivo de la criptografía. Para crear formas de comunicarse sin que terceros escuchen. Este cifrado es el cifrado de César . Dado un alfabeto y una clave (la clave es un número entero entre 1 y 25), cambie todas las letras del alfabeto por clave.

Con un cambio de 3, como se ve en la imagen de arriba, A se convierte en D, B se convierte en E y así sucesivamente hasta que termina con X = A. El mensaje original se llama texto sin formato y el mensaje cifrado se llama texto cifrado .

La forma más fácil de realizar el Cifrado de César es convertir todas las letras en números, a = 1, b = 2, c = 3 y así sucesivamente.

Para cifrar, E, calcula esto para cada letra (donde s es el cambio):

Esto se llama una función. Le pones una entrada y sale una salida. Muchas funciones se conocen como funciones bidireccionales. Puede cifrar usando la función anterior, y tiene sentido que para descifrar simplemente haga lo contrario. Dada una función que duplica un número, si tienes un número duplicado y quieres invertir la función haz lo contrario de multiplicar por 2, divide el número por 2.

mod es el operador de módulo. Es el resto de dividir. Hacemos módulo porque no hay una letra número 27 en el alfabeto, simplemente pasa de la "z" a la "a". Hablaremos más sobre modular en este artículo. Mira este pequeño ejemplo a continuación:

Porque 4 dividido por 3 tiene un resto de 1.

Para descifrar el cifrado de César, D, calcula esto para cada letra:

Como puedes ver, no es muy seguro. Con 25 turnos en total, solo tiene que cambiar el texto 25 veces hasta encontrar el código descifrado, esto se llama ataque de fuerza bruta. Tomas el texto cifrado y lo cambias todo 25 veces hasta que encuentras el texto descifrado. Pero imaginemos por un segundo que se trata de un cifrado duro, que la fuerza bruta no es factible.

¿Cómo le dices a tu amigo que estás usando un turno de 9, por ejemplo? Tienes que comunicárselo a ellos de alguna manera. Se pueden escuchar todas y cada una de las formas de comunicación, ya sea escribiendo una carta o yendo a un bosque escondido en Suiza a 30 millas de la ciudad más cercana y contándoselo a su amigo.

Esto último no es muy factible, pero es mucho más seguro que decirle a tu amigo en Times Square, Nueva York 🗽 cuál es el turno.

Ahora, imagine que trajo su almuerzo al trabajo en una lonchera especial, la misma que ha tenido desde la guardería. Alguien roba tu comida y tu lonchera. No te importa perder la comida, pero quieres recuperar la lonchera. Desea una forma de que le devuelvan su lonchera de forma segura sin que usted sepa quién se la llevó, porque eso les quita presión.

Colocas una caja en la sala de profesores con un candado y una llave. Das copias de las llaves a todos en la oficina y esperas lo mejor: que alguien te devuelva la lonchera colocándola en la caja.

Desafortunadamente, las llaves que todos tienen también abren la caja y la cierran. Esto significa que alguien podría desbloquear la caja y volver a robar tu lonchera.

Necesitamos encontrar una manera de deshacernos de esta idea de compartir claves, deshacernos de la idea de que 'cualquier clave puede bloquear y desbloquear', y aquí es donde entra en juego la criptografía asimétrica.

Criptografía asimétrica

Instalas una cerradura extraordinaria en esta caja, una que tiene dos llaves separadas. La primera llave 🔑 solo puede girar en el sentido de las agujas del reloj, de A (bloqueado) a B (desbloqueado) a C (bloqueado).

La segunda llave 🗝️ solo puede girar en sentido antihorario, de C a B a A. Escoges la primera llave y te la guardas. Esto se llama clave privada. La segunda clave se llama clave pública. Esta clave se entrega a todos en la oficina. Quiere que todos tengan esta clave.

Cuando alguien devuelva su preciada lonchera, puede dejarla en esta caja. Todo lo que pueden hacer las claves públicas es cerrar la caja. Su clave privada es la única que puede abrirlo.

Esta es la criptografía de clave pública. Todo el mundo sabe que si meten algo en la caja y la cierran, solo tú puedes abrirla con tu clave privada.

Con la criptografía simétrica, cualquiera podría abrir tu caja si tuviera la clave. Ahora, nadie aparte de ti puede abrir la caja.

La criptografía de clave pública fue formulada por primera vez por Whitfield-Diffie o James Ellis (Ellis la descubrió primero, pero no la publicó. Whitfield-Diffie la publicó primero). Tanto Ellis como Whitfield-Diffie disfrutaron de que la criptografía de clave pública podría funcionar en teoría, pero nunca lograron descubrir cómo funcionaría en la práctica.

La producción de un sistema de cifrado de clave pública en funcionamiento se atribuye a Rivest-Shamir-Adleman (RSA) o Clifford Cocks . Como arriba, Cocks lo descubrió primero, pero no lo publicó. Rivest–Shamir–Adleman publicó primero.

Veamos cómo funciona esto matemáticamente.

Las matemáticas detrás de la criptografía de clave pública

Si bien la analogía de la caja era algo físico, vamos a volver a cifrar mensajes como lo hicimos con Caeser Cipher.

Cuando aplica la clave pública (K+) al mensaje cifrado y luego la clave privada (K-) al mensaje cifrado, obtiene el mensaje de texto sin formato. También estamos buscando estos atributos:

Es computacionalmente fácil:

• Generar un conjunto de claves.
• Cifrar/Descifrar usando estas claves

Pero también es computacionalmente inviable:

Convertir mensajes en números

Queremos convertir un mensaje en números. Previamente le asignamos un número a cada letra, A = 1 y así sucesivamente. El Código estándar estadounidense para el intercambio de información (ASCII) es una tabla de todas las letras en inglés y la mayoría de los símbolos junto con su código ASCII asociado y salida binaria.

Cuando presiona una tecla en el teclado, el teclado convierte esto a Ascii, ya que es más fácil trabajar con números que con letras para una computadora. Si desea obtener más información sobre ASCII, consulte este video .

Codifiquemos la palabra "gatos". En binario, según Ascii, esto es:

Si los suma todos y los convierte a base 10, obtiene 4430123. Para nuestro ejemplo, vamos a ver cómo Rivest–Shamir–Adleman (RSA), un cifrado de clave pública, calcula las claves públicas y privadas. También vamos a usar números mucho más pequeños, por lo que las matemáticas no son tan difíciles de leer.

A continuación se muestra una calculadora que creé para convertir ASCII en binario. Véalo mejor en mi sitio web ( https://skerritt.blog/how-does-public-key-cryptography-work/ ).

trinket: ejecute el código en cualquier lugar _Python en el navegador. No requiere instalación._trinket.io

RSA

1. Elige 2 números primos grandes, p y q.

Los números primos son números que solo tienen 2 divisores , el 1 y él mismo. Vamos a elegir 5 y 7, no números primos grandes pero pequeños por brevedad.

2. Calcule n = pq, z = (p-1)(q-1)

3. Elija e (con e < z) tal que e no tenga factores comunes con z.

mi = 5

5 no tiene factores comunes con 24 y es menor que 24.

4. Elija d tal que ed — 1 sea exactamente divisible por z.

La forma más fácil de hacer esto sería recorrer todos los valores posibles de d en el código. Este código está escrito en Python funcional , pero el lenguaje y el paradigma no importan.

Como estamos usando números tan pequeños, tenemos superposición. Tanto e como d son 5. Pongamos d en 29, solo para que no tengamos esta superposición.

re = 29

5. La clave pública es (n, e). La clave privada es (n, d)

A continuación se muestra el código para generar claves RSA. Tenga en cuenta que tenemos una superposición en d con p = 5 y q = 7, como se discutió anteriormente.

trinket: ejecute el código en cualquier lugar _Python en el navegador. No requiere instalación._trinket.io

Para enviar un mensaje encriptado, Bob calcula C = m^e mod n para el mensaje m y la clave e. Para descifrar el mensaje, Alice calcula m = c^d mod n.

Cifrar "gatos" nos da 42⁷⁵ mod 35 = 7.

Descifrar "gatos" nos da 4430123.

Luego, para enviar un mensaje m, Bob calcula c=m^e (mod N) y se lo envía a Alice y Alice descifra el mensaje usando su clave privada d con m=c^d (mod N)

¿Por qué funciona?

Factorización prima. Es fácil multiplicar dos números primos, pero es increíblemente difícil averiguar qué números primos se usaron para formar ese número. Puedes multiplicar fácilmente estos dos juntos:

Pero si te doy 992,474,117 y te digo que encuentres los números primos que se usaron para hacer este número, no es computacionalmente factible. Más aún cuando te das cuenta de que los números primos utilizados son muy, muy grandes.

Esto se conoce como función de trampilla o función unidireccional. Si bien es fácil pasar por un camino, es computacionalmente inviable ir por el otro. Hervir un huevo es una función unidireccional porque es fácil hervir un huevo, pero no es posible deshervirlo. Profundicemos en las matemáticas y exploremos la aritmética modular.

Volver a la aritmética modular

Imagine un rango finito de números, por ejemplo, del 1 al 12. Estos números están dispuestos en un círculo, como un reloj (la aritmética modular a veces se llama aritmética de reloj debido a esto)

Cuenta 13 alrededor de este reloj. Llegas a 12 y luego necesitas contar 1 más, por lo que vuelves a 1. La aritmética modular todavía se define como el resto de la división, sin embargo, también se puede definir (y se define más comúnmente) como un reloj.

Las funciones que utilizan aritmética modular tienden a funcionar de forma errática, lo que a su vez las convierte en funciones unidireccionales. Veamos esto con un ejemplo tomando una función regular y viendo cómo funciona cuando se convierte en una función aritmética modular.

3^x

Cuando insertamos 2 en esta función, obtenemos ³² = 6. Insertamos 3 y obtenemos ³³ = 9

Esta función es fácil de invertir. Si nos dan 9, podemos decir que la función tenía una entrada de 3, porque ³³ = 9.

Sin embargo, con la aritmética modular añadida, no se comporta con sensatez.

Imagen teníamos esta fórmula:

3^x módulo 7 = 1

¿Cómo averiguarías qué es x? No puedes poner el mod en el otro lado, porque en realidad no hay un inverso de la aritmética modular. ¿Qué hay de adivinar? Ingresemos 5:

³⁵ mod 7 = 5

Vale, eso era demasiado grande. Es posible que desee ir más bajo, tal vez 4 o 3, pero en realidad esta es la dirección equivocada. Cuando x es 6, es igual a 1.

En la aritmética normal, podemos probar números y tener una idea de si nos estamos calentando o enfriando, pero este no es el caso con la aritmética modular.

A menudo, la forma más fácil de invertir la aritmética modular es compilar una tabla para todos los valores de x hasta encontrar la respuesta correcta. Aunque esto puede funcionar para números más pequeños, es computacionalmente inviable hacerlo para números mucho más grandes. Esta es a menudo la razón por la cual la aritmética modular se conoce como función unidireccional.

Si le diera un número como 5787 y le dijera que encontrara la función para él, sería inviable. De hecho, si le diera la posibilidad de ingresar cualquier número en la función, aún sería difícil. Me tomó solo unos segundos hacer esta función, pero te tomará horas o incluso días averiguar qué es x.

RSA es una función unidireccional. Si bien es relativamente fácil llevar a cabo esta función, es computacionalmente inviable hacer lo contrario de la función y averiguar cuáles son las claves. Aunque es posible revertir un cifrado RSA si conoce algunos números como N.

hablemos de n

Recuerde anteriormente donde detallé cómo funcionaba el algoritmo RSA. Había un número, $n$. Esta n es especial porque bajo algunas circunstancias n puede hacer que esta función unidireccional sea reversible

N es un producto de 2 números primos. Como vimos anteriormente, si tomamos $5$ y $7$ y los multiplicamos, obtenemos:

n = 35

Para que Bob le envíe un mensaje a Alice, cifra el mensaje con la clave pública de Alice. Ahora que el mensaje está cifrado, tiene que haber alguna forma de que Alice lo descifre. Tiene que haber alguna manera para que Alice revierta esto, pero solo para que Alice lo haga. No puedes hacer que Eve, Niamh o Hannah lo inviertan, porque eso supera el punto de encriptarlo.

RSA está diseñado para que la persona que conoce P y Q (los dos números primos que se multiplican para dar N) pueda descifrar el mensaje.

Aunque Alice le ha dicho al mundo que su clave pública es n = 35, nadie aparte de Alice sabe que P = 7, Q = 5. Tenga en cuenta que los números primos son intencionalmente pequeños por razones de brevedad.

Puede que estés pensando “es fácil adivinar que los factores primos de 35 son 5 y 7” y estarías en lo cierto. Pero, con números lo suficientemente grandes, es virtualmente imposible encontrar p y q.

De hecho, con números lo suficientemente grandes, multiplicar p y q son esencialmente funciones unidireccionales. Es posible que en el futuro, quizás en un futuro cercano (con la invención de las computadoras cuánticas), la factorización de números se vuelva fácil. Los matemáticos han intentado sin éxito durante miles de años encontrar una forma eficiente de factorizar números, por lo que por ahora se considera seguro.

Veamos más en las matemáticas

Bien, veamos cómo funciona el módulo en todo esto. Entiendes por qué funciona la multiplicación y cómo funciona el módulo. Pero ¿qué pasa con las otras ecuaciones? ¿Para qué son?

Demostremos el algoritmo de descifrado usando una identidad debida a Euler y Fermate:

Para cualquier número entero (M), M es primo relativo a n:

Esta es la función totient de Euler que da el número de enteros positivos menores que n que son primos relativos a n. Relativamente primo es donde 2 números solo comparten el factor 1 entre sí. En la actualidad usamos la función de Carmichael sobre la función de Euler, ya que la función de Euler a veces puede producir números demasiado grandes para usar. Sin embargo, estamos usando la función totient de Euler, ya que es lo que usó el documento RSA original.

Esto suena confuso, pero vamos a desglosarlo. Por propiedades elementales de la función totient:

Dado que d es primo relativo a ϕ i (n), tiene un inverso multiplicativo e en el anillo de los números enteros módulo $ ϕ (n). Lo que esto significa es que la fórmula que usamos para RSA se puede revertir (la trampilla se puede revertir) si se tiene cierto conocimiento sobre los números utilizados.

Sin esta propiedad matemática especial, no sería posible revertir el cifrado y descubrir el texto cifrado si conoce algunos de los números utilizados.

El inverso multiplicativo modular del algoritmo de cifrado c = m^e mod n es m = c^d mod n. Todas estas matemáticas se han construido hasta esto. La aritmética modular y las funciones unidireccionales están muy involucradas aquí. Para cifrar, calcula c. Para descifrar, calcula m. Ambos requieren el conocimiento de n, que es el número especial del que hablamos antes.

Si desea obtener más información sobre las matemáticas de RSA, le recomiendo encarecidamente el documento RSA original y legible.

Autenticación

¿Cómo prueba que un mensaje enviado por Bob en realidad fue enviado por Bob y no por Eve? Necesita una forma de autenticarlos. En el mundo real, nos autenticamos mediante firmas. Aunque estos se pueden falsificar, puede autenticarse utilizando un escáner biométrico, pero sus huellas digitales se pueden levantar y copiar.

Puede usar un código de acceso, pero de nuevo, al igual que el cifrado Caeser y su clave única son inútiles, los métodos de autenticación que usan claves únicas no son tan perfectos.

Puede usar un código de acceso, pero de nuevo, al igual que el cifrado de Caeser y su clave única son inútiles, los métodos de autenticación que usan claves únicas no son tan perfectos.

Digamos que Bob quiere demostrarle a Alice que Bob escribió el mensaje que le envió. Bob envía su mensaje original con una versión cifrada del mensaje con su clave privada (K-). Alice usa la clave pública de Bob (K+) que, usando la fórmula anterior, convierte el mensaje encriptado en el mensaje normal. Luego, Alice verifica el mensaje que envió Bob con el mensaje que recibió del mensaje cifrado. Si coinciden, puede estar segura de que alguien con la clave privada de Bob (probablemente Bob) la envió.

Este método apesta para el cifrado porque si Bob cifra su mensaje con su clave privada, cualquiera puede leerlo con su clave privada. Además, es computacionalmente costoso demostrar que Bob envió algo. Es por eso que creamos un resumen del mensaje y lo encriptamos en su lugar para verificar a Bob. Este resumen de un mensaje se realiza mediante una función hash.

Para obtener más información sobre las funciones hash, escribí un artículo hermano que las explica aquí .

volver a la criptografía

Al cifrar el hash del mensaje, aceleramos el proceso de cifrado, lo que hace que la autenticación sea mucho más rápida. Ahora, vamos a hacerle una broma a Bob.

Creamos un pedido por correo electrónico a una pizzería solicitando 4 pizzas de pepperoni. Firmamos este correo electrónico con nuestra clave privada. Enviamos a la pizzería nuestra clave pública, pero les decimos que el teléfono de Bob no funciona y que nuestra clave pública es en realidad la clave pública de Bob.

La pizzería verifica la firma y envía 4 pizzas de pepperoni 🍕 a Bob. Lo peor es que a Bob ni siquiera le gusta el pepperoni. Aquí es donde entra en juego una autoridad de certificación .

Las autoridades de certificación (CA) vinculan una clave pública a una entidad específica. Esta entidad proporciona prueba de identidad a la CA, la CA luego crea un certificado que vincula a la entidad con su clave pública. La idea es eliminar la confianza de confiar en un individuo para las claves públicas. Todavía tienes que confiar en una organización, pero muchas personas encuentran que confiar en una organización es mejor que confiar en un individuo.

El certificado que contiene la clave pública de las entidades está firmado digitalmente por la CA. Esta firma es la CA que dice "esta es la clave pública de las entidades".

Cuando Alice quiere la clave pública de Bob, obtiene el certificado de Bob. Luego aplica la clave pública de la CA al certificado de Bob para obtener la clave pública de Bob.

Cloudflare tiene un artículo increíble sobre las autoridades de certificación aquí .

Correo electrónico seguro con muy buena privacidad

Phil Zimmerman inventó Pretty Good Privacy (PGP), el estándar de facto para el cifrado de correo electrónico. Zimmerman usó RSA en PGP. RSA está patentado y no tenía permiso de RSA inc (la compañía que posee la patente) para publicar otro cifrado usando RSA.

Zimmerman también fue objeto de una investigación federal de EE. UU. de 3 años porque en ese momento los programas de criptografía se consideraban municiones según la ley de EE. UU. Cuando se le preguntó si valió la pena todos los problemas para publicar PGP, dijo que "no se arrepiente". Veamos cómo funciona este algoritmo que solía ser ilegal.

Cuando Alice quiere enviar un correo electrónico confidencial a Bob, ella:

1. Genera clave privada simétrica aleatoria, K-.
2. Cifra su correo electrónico con K- (para mayor eficiencia)
3. También cifra K-con la clave pública de Bob.
4. Alice firma digitalmente el mensaje cifrado.
5. Alice le envía a Bob ambos

y su firma digital.

En total, Alice usa tres llaves. Su clave privada, la clave pública de Bob y la clave simétrica recién creada.

Esta idea de cifrar una clave simétrica con una clave pública se denomina Criptosistema Híbrido . Algunos mensajes de correo electrónico pueden ser increíblemente grandes, cifrarlos con un sistema de clave pública llevaría mucho tiempo.

Utilice un sistema de clave simétrica como AES , que es increíblemente difícil de romper (pero no tanto como RSA). Cifre la clave AES (y solo la clave, no todo el correo electrónico) con la clave pública. De esta forma, el receptor puede aplicar su clave privada y averiguar la clave simétrica AES para descifrar el correo electrónico.

No mucha gente usa PGP, debido a lo difícil que es configurarlo. Como máximo, necesita descargar un programa en el que confíe para implementar correctamente PGP. En 2018, se demostró que los clientes de correo electrónico como Apple Mail, Thunderbird y Outlook, que tienen configuraciones para habilitar PGP, pueden verse obligados a mostrar las versiones no cifradas.

Sin mencionar lo sospechoso que parece que una persona envíe correos electrónicos encriptados en una red de correos electrónicos no encriptados. El único cliente de correo electrónico (y proveedor de direcciones) que habilita PGP de manera predeterminada es ProtonMail, pero aun así es solo para correos electrónicos de protón a protón y debe confiar en que la empresa lo implementará correctamente.

Conclusión

La criptografía se ha utilizado durante miles de años, casi tanto tiempo como la humanidad ha mantenido secretos. En nuestro constante esfuerzo por mantener nuestros secretos en secreto para todos, excepto para unos pocos, hemos encontrado este algoritmo mágico que funciona bastante bien. Sin duda, en 300 o 400 años se habrá descifrado de la misma manera en que César pensó que su cifrado nunca se descifraría.

Oye 👋 ¿Quieres suscribirte a mi blog y estar al día con publicaciones similares a esta? Suscríbete a mi lista de correo electrónico a continuación. No te enviaré spam. Solo te enviaré publicaciones similares a esta 😊✨

Si te sientes más generoso, tengo un PayPal e incluso un Patreon . Soy un estudiante universitario que escribo estos artículos en mi tiempo libre. Este blog es mi trabajo de tiempo completo, por lo que todas y cada una de las donaciones son apreciadas.