La Criptografía de Clave Pública (cómo funciona)

La Criptografía de Clave Pública

Quiero que cualquier persona pueda enviarme un mensaje secreto.  Pero también quiero que el sistema para hacerlo secreto sea público, es decir que cualquiera lo conozca y lo pueda utilizar. Sin embargo, aunque la “clave” sea pública sólo yo debo poder leer el mensaje.  Si quien lo envió olvidó qué escribió, ya no podrá saberlo a partir del texto en clave.

¿Es esto posible?  Sí.

Desde el momento mismo de la invención de la escritura, se generó la necesidad de enviar mensajes cuyo contenido sólo pudiera ser interpretado por el destinatario, manteniéndolo secreto para las miradas indiscretas.

Con la evolución y sofisticación de la organización social, esta necesidad se hizo fundamental para el funcionamiento de los ejércitos, las organizaciones políticas y diplomáticas, y luego también para el comercio y las finanzas.

La dificultad radica en que se pretende enviar un mensaje a través de una vía de comunicación “no segura”, es decir que puede ser interceptado y leído por un enemigo, un competidor, un cónyuge celoso, o la DGI.  Cualquiera de los medios de comunicación que usamos diariamente – internet, Wi-Fi, celulares – es claramente un canal de comunicación no seguro.

En algunos casos, existe el agravante de que podemos no enterarnos de que el mensaje ha sido interceptado, y que el sistema dejó de ser confiable.

La disciplina que comprende el estudio y desarrollo de los distintos métodos para intercambiar información en forma secreta y segura, se suele llamar “criptografía”.   Es uno de los más antiguos campos de conocimiento que pueden llamarse técnicos, y se remonta a por lo menos 4.000 años de antigüedad.

Los primeros sistemas fueron muy rudimentarios, similares a los que muchos hemos inventado para sobrevivir clases aburridas en la escuela y el liceo.  Consistían en la simple sustitución de un carácter por otro o por un símbolo arbitrario, usando una lista de sustituciones previamente acordada entre los interlocutores.

Si el texto cifrado es suficientemente extenso, o se usa la misma clave durante un período largo de tiempo en el que se genera una gran cantidad de texto, un simple análisis estadístico de las repeticiones de los símbolos, comparando con las frecuencias de uso en el idioma del que se trate, permite “quebrar” el sistema y descifrar la clave.

Por ejemplo, en español las letras más frecuentes son, en orden: e,a,o,s,r,n,i,d,l,c, …

En inglés: e,t,a,o,i,n,s,h,r,d,l,u, …

Nota -Dato interesante: esa estadística fue compilada inicialmente por los linotipistas para dimensionar su stock de tipos de plomo.

A lo largo de la historia se inventaron ingeniosos sistemas para esconder la información; algunos de ellos utilizaban artificios físicos, como el que se muestra en la figura, denominado “scitalia” y atribuido a los espartanos. Consiste en escribir a lo largo de un bastón sobre el que previamente se enrolló una cinta de pergamino.   Para leer el mensaje escrito en la cinta, se debía enrollar la misma alrededor de un bastón de igual diámetro que el original.

 figura

 Una variante del sistema “liceal” de sustitución por símbolos se utilizó en la práctica hasta hace relativamente poco, de la siguiente manera:

Se diseña la tabla de equivalencias, por ejemplo (la más sencilla):       A=1, B=2, …..Z=27. 

También puede ser: A=*, B=%, C=&, ….. Z=!,  o cualquier otra.  Incluso puede ser A=A, B=B, …, Z=Z (sin sustitución) como se verá en el ejemplo descripto más adelante.

Anualmente, se genera un “libro” con 366 páginas (una para cada día del año) llenas de números al azar entre 1 y n, con n menor que 26 y se reparten copias idénticas del libro entre todos los participantes del sistema, por ejemplo el gobierno de un país y sus embajadas en diferentes países.

Si imaginamos la tabla de equivalencias como dos regletas paralelas deslizantes (o mejor aún dos discos concéntricos), una con la sucesión de caracteres (A, B, C, … Z) y la otra con la sucesión de símbolos correspondientes, la idea es que para realizar la codificación  (y la decodificación) de un mensaje, hay que utilizar la página del libro correspondiente al día del año. Esta contiene una serie de números aleatorios, y para cada caracter sucesivo a codificar se desplaza la regleta tantos lugares como indica la siguiente posición en el libro compartido.

Ejemplo: Texto a encriptar = “HOLA”, Tabla de equivalencias: A=A, B=B, …. Z=Z (las dos regletas son iguales).

Supongamos que es el primer mensaje del día de hoy, y la página del libro de claves correspondiente a la fecha de hoy comienza con los números aleatorios  5, 2, 10, 21, …….

Desplazamiento

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

Regleta 1

A

B

C

D

E

F

G

H

I

J

K

L

M

N

Ñ

O

P

Q

R

S

T

U

V

W

X

Y

Z

Regleta 2

5

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

Ñ

O

P

Q

R

S

T

U

Regleta 1

A

B

C

D

E

F

G

H

I

J

K

L

M

N

Ñ

O

P

Q

R

S

T

U

V

W

X

Y

Z

Regleta 2

2

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

Ñ

O

P

Q

R

S

T

U

V

W

X

Regleta 1

A

B

C

D

E

F

G

H

I

J

K

L

M

N

Ñ

O

P

Q

R

S

T

U

V

W

X

Y

Z

Regleta 2

10

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

Ñ

O

P

Regleta 1

A

B

C

D

E

F

G

H

I

J

K

L

M

N

Ñ

O

P

Q

R

S

T

U

V

W

X

Y

Z

Regleta 2

21

G

H

I

J

K

L

M

N

Ñ

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

El texto original “HOLA”, se convierte en “CNBG” (casilleros celestes).

El mensaje cifrado aparecerá ante un eventual interceptor del mismo como compuesto por caracteres aleatorios y no le proporcionará ninguna información de utilidad.

Dado el texto cifrado “CNBG”, para proceder a descifrarlo se utiliza exactamente el mismo procedimiento.

La desencriptación es entonces el proceso inverso de la encriptación.

Este sistema, bastante engorroso para instrumentar manualmente, es de muy fácil implementación en una computadora o incluso en los primitivos sistemas mecánicos o electromecánicos de mediados del siglo XX.

El ejemplo anterior equivale en su forma abstracta, a enviar el mensaje dentro de una caja fuerte de combinación (la combinación sería el libro de desplazamientos aleatorios).   El remitente y el destinatario conocen la combinación, y nadie más.

La dificultad intrínseca a estos sistemas y muchos otros equivalentes, es que en todos los casos, para poder enviar los mensajes codificados utilizando una vía no segura, se necesita previamente una vía segura para enviar la “clave” (en el ejemplo el libro de desplazamientos), y si se dispone de una vía segura, ¿porqué no usarla para enviar el mensaje sin encriptar?

En la mayoría de los casos, esto es prácticamente imposible o prohibitivamente caro, especialmente cuando las personas que necesitan intercambiar los mensajes no se conocen previamente o cuando se trata de mantener la privacidad en una vasta red de comunicaciones.

Nota - Un aspecto importante y anti-intuitivo en esta situación es la necesidad de que el método de encriptación (y desencriptación) sea públicamente conocido. Uno tendería a pensar que manteniendo secreta la forma de codificar la información debería hacer al sistema más difícil de crackear. Sin embargo, la única forma de saber si un método de encriptado es seguro y no va a ser roto por un atacante, es hacerlo público para que sea analizado y probado por otros criptógrafos. La única cosa que debe ser mantenida en secreto es la clave.  Es el equivalente a una cerradura.  Los planos constructivos de la cerradura (salvo la forma de los tambores) se pueden dar a conocer, pero no la forma de la llave.

 La seguridad del sistema se reduce a la posibilidad de transmitir la clave en forma secreta y almacenarla de una manera segura.

Por lo tanto, poco a poco fueron quedando claras las características que debería reunir un sistema eficiente sobre el que basar las comunicaciones cifradas.

1)      El texto original debería ser fácilmente convertible en el texto cifrado utilizando un sistema de encriptación (función o transformación E) provisto por el destinatario y conocido públicamente (p.ej. publicado en la guía telefónica o en una página web).

2)      El texto original debería poder ser reconstruido a partir del texto cifrado por el destinatario, utilizando una función de descifrado D que sólo él conoce.

3)      De la función de encriptación pública E no debe poder deducirse la función de descifrado D secreta.

4)      Idealmente, el sistema debería tener características tales que aseguraran la autenticidad de los mensajes, en otras palabras, que permitiera incluir una “firma embebida”.  La característica de “firma embebida” es fundamental en las transacciones comerciales o bancarias, porque evita la posibilidad de que el destinatario fragüe un mensaje enviado a sí mismo como si hubiera sido enviado por un tercero.

La cuestión a resolver es cómo construir un sistema de clave pública como el descrito.

Los algoritmos desarrollados están construidos sobre un principio común, el de encontrar y hacer uso de una “función unidireccional”.  Una descripción informal de la misma sería la de encontrar una función (E) tal que su aplicación (Encriptación) sea computacionalmente sencilla, pero su inversa (D, es decir, invertir su acción para desencriptar), sea en la práctica imposible, o por lo menos, computacionalmente inobtenible.

El par de funciones E y su inversa D son el análogo a una “puerta trampa” como las de las películas de misterio.  De un lado se ve y del otro no.  Para utilizarla en el sentido secreto, se debe saber qué ladrillo apretar, qué lámpara girar, o qué libro desplazar en la antigua biblioteca inglesa.   Para volver desde el cuarto secreto, la puerta es una puerta ordinaria con pestillo.

En la década de los 70 comenzaron a aparecer desarrollos de algoritmos implementables en computadoras digitales que cumplían estos requisitos.

En todos los algoritmos propuestos, si bien es imposible demostrar la seguridad del sistema, se puede confiar en que ésta es suficiente debido a que su inviolabilidad no se basa en consideraciones teóricas sino prácticas.   Para deducir la función D conocida la función E, es muy sencillo escribir un algoritmo que lo intente por “fuerza bruta”, dedicando masivos recursos computacionales a probar alternativas, sabiendo que el número de combinaciones posibles es enorme pero finito.  Sin embargo, se puede demostrar que la computadora más grande concebible hoy y en el futuro (con tantos elementos lógicos como partículas hay en el universo) necesitaría billones de años para lograr el objetivo, lo cual garantiza la inviolabilidad práctica del sistema.

Se puede asegurar esto con confianza porque los sistemas diseñados pertenecen a un tipo de problemas identificados en la teoría de números como “polinomiales no determinísticos” (NP por su sigla en inglés).  Para ellos, las posibles soluciones pueden ser rápidamente verificadas, pero la cantidad de pasos computacionales necesarios para hallar soluciones generales aumenta muy rápidamente con el tamaño del problema.

Tempranamente quedó claro que las matemáticas que mejor se prestan para la construcción de funciones unidireccionales están vinculadas con la aritmética modular.

Se define A mod _B = C como el resto de la división entera de A por B  (A módulo B igual C, también se suele representar computacionalmente como mod(A,B)=C  ).

La característica de la función módulo que la hace apropiada para este uso es que, si bien el resultado de la aplicación de la función es único, su inversa no lo es, o sea que al incorporarla en la función E (encriptación) se obtiene un texto encriptado único, pero al pretender ir hacia atrás, se abren infinitas alternativas. Si conozco A y B obtengo C único, pero si conozco C y B, la solución es A, pero también A+nB, para cualquier valor de n.

Los primeros sistemas que hicieron historia son:

-          El sistema de Ralph Merkle, Whitfield Diffie y Martin Hellman, basado en el problema de la mochila (ver recuadro).

-          El sistema RSA (iniciales de sus inventores, Ronald Rivest, Adi Shamir y Leonard Adleman), basado en el problema de la factorización en números primos.

-          El sistema DES desarrollado por IBM (Data Encryption Standard) y el triple-DES.

Luego aparecieron múltiples variantes buscando mayor seguridad, más fácil implementación en computadoras pequeñas, menor tiempo de procesamiento para uso en internet, etc.

Cuando enviamos instrucciones al banco por internet o cuando le pedimos a Windows que encripte con contraseña la información de una carpeta en nuestro disco duro, seguramente estamos usando uno de estos sistemas sin saberlo explícitamente.

En el cuadro, se desarrolla un ejemplo simplificado del sistema basado en el “problema de la mochila”.

No ha tenido la generalizada aplicación de los sistemas RSA y DES por ser menos seguro, pero es suficientemente sencillo como para que la idea general, común a casi todos los sistemas, sea comprendida por un lego.

El problema de la mochila es un problema NP cuya idea conceptual es la siguiente:

Se tiene un conjunto abundante y ordenado de discos del mismo diámetro pero de espesores diferentes. Se elige un subconjunto de discos de distintos espesores, manteniendo el orden, se los coloca en una pila, y se construye una “mochila” o cilindro que los contenga con la misma altura.  Luego se devuelven los discos al conjunto, y se le pide a otra persona que llene la mochila nuevamente, volviendo a escoger los discos correctos.

Ocurre que dado un número grande de discos de distintos espesores, hacer una pila con algunos discos de tal manera que sumen cierta altura exacta (la altura de la mochila), es un problema difícil, de tipo NP.

Para cantidades grandes de discos la resolución por “fuerza bruta” consume enormes recursos computacionales, a pesar de que el algoritmo (receta) es trivial.

La altura de la mochila y los discos son sólo una metáfora para representar el proceso.  Lo que se hace en la práctica es, obviamente, operar con números.

Por ejemplo: si los espesores del conjunto de discos, medidos en milímetros, son:

43, 135, 8, 64, 227, 173, 58, 17, 39, 201 y la mochila mide 331 mm de alto, el subconjunto que soluciona el problema es (8,64,58,201)  porque 8+64+58+201=331.

Para aplicar la metáfora de la mochila y los discos a la encriptación de un texto, en el ejemplo que se muestra en el recuadro, se dividirá previamente el texto en bloques y se asignará a cada bloque un número proveniente de la sustitución de cada letra por un valor numérico de acuerdo a una convención prefijada. Estos números determinarán qué discos se escogerán, y la suma de sus espesores (altura de la mochila) será el número que represente al bloque de texto.

Para comprender lo anterior, veamos un ejemplo y su construcción matemática:

Veamos cómo funciona un algoritmo asimétrico, con un ejemplo simple tomado del artículo original de Martin Hellman en Scientific American (agosto 1979).                

------------------------------------------------------------------------------------------------------------------------------------------------------

Juan y Pedro acuerdan utilizar un sistema basado en el problema de la mochila, pero sumamente simplificado.  Pedro hace conocida su clave pública, y Juan le envía un mensaje.

Los textos a codificar se deberán transformar en una cadena de bits (unos y ceros).

Para ello se expresará en binario el sencillo método de equivalencia  A=0, B=1, …. , Z=26,  con 5 bits por carácter: 

A = 00000, B = 00001, C = 00010, …. , Z = 11010

Tomarán bloques de 2 caracteres, por lo tanto 10 dígitos binarios. 

En los sistemas reales, estos bloques deberían ser de por lo menos 100 dígitos binarios para que el sistema sea razonablemente seguro.

         1) Pedro confecciona su clave pública a partir de su clave secreta.

La clave secreta de Pedro consistirá en un vector supercreciente arbitrario de 10 números, tantos como dígitos binarios contiene cada bloque a codificar (un conjunto se llama supercreciente cuando cada elemento sucesivo es mayor que la suma de todos los anteriores):

as = (as₁, … as₁₀) = (3, 5, 11, 20, 41, 83, 169, 340, 679, 1358),               as = vector a secreto creado arbitrariamente

y dos números, también arbitrarios, primos entre sí:

 w = 764,    m = 2731.

Nuevamente, en un sistema real los elementos del vector deberían ser por lo menos 100, y los números w y m, de por lo menos 50 dígitos.

También necesita calcular w^-1, la inversa modular de w, definida como w x w^-1 mod m = 1.

w^-1 se obtiene mediante un método sencillo que es una extensión del algoritmo de Euclides para hallar los factores primos, y que no viene al caso desarrollar aquí.

Para w = 764 y m = 2731, resulta w^-1 = 1605.

A partir de su clave secreta, Pedro obtiene la clave pública mediante la siguiente transformación de cada término:

ap_n = (as_n x w) mod m;              para el primer término: ( 3 x 764 ) mod 2731 = 2292.

Así se obtiene el vector ap:                                       ap = vector a público para difundir

ap = (ap₁,…ap₁₀) = (2292, 1089, 211, 1625, 1283, 599, 759, 315, 2597, 2463)

Pedro difunde públicamente su clave consistente en el vector de 10 elementos ap.

------------------------------------------------------------------------------------------------------------------------------------------------------

                2) Método para preparar el mensaje a codificar.

Juan comienza por transformar el texto en una cadena de bits (unos y ceros).

Supongamos que el mensaje es “HOY ES EL DIA”.

El primer bloque a codificar será “HO”, en números “7, 14”, que con la convención de 5 bits por carácter, se traduce en “00111 01110”.

------------------------------------------------------------------------------------------------------------------------------------------------------

                3) Juan encripta el primer bloque.

Se encripta el bloque “HO” = 00111 01110, haciendo el producto escalar entre el vector “HO” y el vector de la clave pública ap.

El producto escalar se define como la suma de multiplicar entre sí las posiciones correspondientes de cada vector, y se suele representar por un punto:

“HO” :     0         0       1        1         1       0       1       1        1        0

 ap    :  2292, 1089, 211, 1625, 1283, 599, 759, 315, 2597, 2463

“HO” . ap = 0x2292 + 0x1089 + 1x211 + 1x1625 + 1x1283 + 0x599 + 1x759 + 1x315 + 1x2597 + 0x2463 = 6790

 Hacer el producto escalar es el equivalente a escoger un subconjunto de discos en la metáfora conceptual de la mochila.  El número del vector que se multiplica por 1 es escogido, el que se multiplica por 0 no; como si la cadena de unos y ceros fuera la receta de cómo “armar” el número correspondiente a la altura de la mochila C.

Por lo tanto, el primer bloque encriptado (C) a transmitir por vía no segura (ej. internet) es el número 6790.

------------------------------------------------------------------------------------------------------------------------------------------------------

                4) Pedro recibe el mensaje y lo decodifica.

Si se intentara deshacer el camino de codificación probando alternativas a partir de las combinaciones posibles de elementos de ap que den como resultado 6790, los tiempos necesarios no son viables en la práctica.

Pero Pedro tiene un atajo; previamente transforma el mensaje de manera que pueda ser descompuesto usando el vector secreto as en lugar del vector púbico ap:

La transformación es: C´ = (C x w^-1 ) mod m  = ( 6790 x 1605 ) mod 2731 = 1260

 Recordemos que w^-1  y m son secretos.  Sólo los conoce Pedro, así como el vector

as = (3, 5, 11, 20, 41, 83, 169, 340, 679, 1358)

Como el vector as es supercreciente, el proceso de descomposición de C´  usando el vector as es muy sencillo; simplemente se prueba primero con el número más grande.  Si es mayor que C´ se lo descarta (se le asigna un cero), si es menor se lo conserva (se le asigna un 1) y se resta de C´.  Luego se prueba el siguiente número más grande contra el resto de C´ que nos va quedando y se hace lo mismo, y así sucesivamente.

1260 = 0x3 + 0x5 + 1x11 + 1x20 + 1x41 + 0x83 + 1x169 + 1x340 + 1x679 + 0x1358

que se interpreta como el bloque original “HO” = 00111 01110.

Si alguien quisiera descifrar el bloque “6790” sin conocer los elementos secretos, la única manera es probar con combinaciones de los números del vector ap, primero de a uno, luego de a 2, luego de a 3, etc.

En nuestro ejemplo, las combinaciones posibles son 1.023, pero para un vector de 100 elementos, son 1,27x10³⁰ (un uno seguido de 30 ceros, un millón de millones de millones de millones de millones).

Posibilidad de “embeber” la firma en el mensaje.

Si Juan quiere enviarle el mensaje a Pedro asegurándose de que Pedro tenga la plena certeza de que el autor es Juan, hace lo siguiente: aplica al texto original su propia función de descifrado (secreta) D_Juan y al resultado le aplica la función de encriptación (pública) E_Pedro de Pedro.

Pedro, al recibirlo, sabiendo que es un mensaje de Juan, le aplica su función de descifrado (secreta) D_Pedro, y luego la de encriptación (pública) de Juan E_Juan.

Si de este procedimiento obtiene un texto legible, no sólo sabe que el mensaje no ha sido interceptado o modificado, sino que puede estar seguro de que Juan es el autor.

Resumen:

Existen básicamente dos tipos de algoritmos para encriptar información. Los algoritmos simétricos, que son los métodos en que pensamos naturalmente cuando imaginamos  cómo podría mandarse un mensaje en forma secreta. Se basan en que quien envía el mensaje y quien lo recibe tienen un método para encriptar y desencriptar la información, para el cual ambos comparten una clave secreta. Toda la criptografía desde la antigüedad hasta 1976 ha estado basada exclusivamente en este tipo de métodos, y continúan siendo ampliamente utilizados.

 Y los algoritmos asímétricos, o ‘de clave pública’, basados en una forma enteramente diferente de preservar el secreto e introducidos en 1976 por Whitfield Diffie, Martin Hellman y Ralph Merkle. En esta criptografía quien recibe el mensaje posee una clave secreta como en la criptografía simétrica, pero también una clave pública con la que se encriptó la información.

CLAVE PÚBLICA

Los métodos criptográficos modernos basados en algoritmos de clave simétrica o secreta son seguros, rápidos y de uso extendido. Sin embargo tienen varios inconvenientes, asociados principalmente al problema de distribución segura de las claves, al número de claves a distribuir y a que no proporcionan seguridad contra el engaño por parte de los participantes.

Para solucionar estos problemas es que Diffie, Hellman y Merkle hicieron una propuesta revolucionaria basada en la siguiente idea: no es necesario que la clave que posee la persona que encripta (envía) el mensaje sea secreta. Lo crucial es que sólo lo pueda descifrar quien recibe el mensaje, utilizando una clave secreta asociada de alguna manera a la pública. Para la realización de un sistema así, quien va a recibir la información secreta hace pública una clave de encriptación, accesible a todo el mundo.  Pero este receptor, tiene una clave secreta capaz de desencriptar el mensaje que consiste de dos partes, una pública y una privada.

Un sistema de tal tipo funciona en forma análoga a un buzón de correos: todo el mundo puede depositar en él correspondencia (encriptar), pero sólo una persona con una llave privada (secreta) puede retirar las cartas (desencriptar).

Referencias:

-          “The Mathematics of Public-Key Cryptography”

Martin E. Hellman

Scientific American, Agosto 1979

-          www.thawte.com/process/crypto/cryptoBriefHistory

-          Wikipedia

Bibliografía sugerida:

-          Modern Cryptography, Theory and Practice
Wenbo Mao