PDF de programación - Criptografía: historia. Teoría de números. Sistemas de clave pública. Sistemas de clave privada

55. Criptografía: historia. Teoría de números.
Sistemas de clave pública. Sistemas de clave

privada.

Antonio Villalón Huerta
Colegiado número 00033

Resumen: En este capítulo vamos a profundizar relativamente en los aspectos
relacionados con la criptografía en los sistemas de información actuales; tras
repasar los conceptos básicos relacionados con esta ciencia, haciendo especial
hincapié en sus bases matemáticas, comentaremos aspectos y detalles
relacionados con diferentes aproximaciones al cifrado: las clásicas (meramente
informativas), la cifra de clave privada y la cifra de clave pública. Para acabar,
hablaremos brevemente de aspectos adyacentes al cifrado pero íntimamente
ligados a este, como las funciones resumen o la esteganografía.

1 Introducción

En el mundo físico, si una universidad quiere proteger los expedientes de sus alumnos los
guardará en un armario ignífugo, bajo llave y vigilado por guardias, de forma que sólo las
personas autorizadas puedan acceder a ellos para leerlos o modificarlos; si queremos
proteger nuestra correspondencia de curiosos, simplemente usamos un sobre; si no
queremos que nos roben dinero, lo guardamos en una caja fuerte... Lamentablemente, en
un sistema de información no disponemos de todas estas medidas que nos parecen
habituales: la principal (podríamos decir única) forma de protección va a venir de la mano
de la criptografía. El cifrado de los datos nos va a permitir desde proteger nuestro correo
personal para que ningún curioso lo pueda leer, hasta controlar el acceso a nuestros
archivos de forma que sólo personas autorizadas puedan examinar (o lo que quizás es
más importante, modificar) su contenido, pasando por proteger nuestras claves cuando
conectamos a un sistema remoto o nuestros datos bancarios cuando realizamos una
compra a través de Internet. En este capítulo vamos a intentar dar unas bases teóricas

Antonio Villalón Huerta

mínimas sobre términos, algoritmos, funciones... utilizadas en ese tipo de aplicaciones.
Para más referencias es imprescindible la obra (Schneier, 1994); otras publicaciones
interesantes son (Menezes, 1996), (Denning, 1983), (Salomaa, 1990) y, para temas de
criptoanálisis, (US Army, 1990). Un texto básico para aquellos que no disponen de mucho
tiempo o que sólo necesitan una perspectiva general de la criptografía puede ser
(Caballero, 1996); el presente capítulo ha sido extraído en gran parte de (Villalón, 2002).

La criptología (del griego krypto y logos, estudio de lo oculto, lo escondido) es la ciencia
(hemos de dejar patente que la Criptología es una ciencia, aunque en muchos lugares aún
se la considera un arte: por ejemplo, en el Diccionario de la Real Academia de la Lengua
Española) que trata los problemas teóricos relacionados con la seguridad en el intercambio
de mensajes en clave entre un emisor y un receptor a través de un canal de
comunicaciones (en términos informáticos, ese canal suele ser una red de computadoras).
Esta ciencia está dividida en dos grandes ramas: la criptografía, ocupada del cifrado de
mensajes en clave y del diseño de criptosistemas (hablaremos de estos más adelante), y
el criptoanálisis, que trata de descifrar los mensajes en clave, rompiendo así el
criptosistema. En lo sucesivo nos centraremos más en la criptografía y los criptosistemas
que en el criptoanálisis, ya que nos interesa, más que romper sistemas de cifrado (lo cual
es bastante complicado cuando trabajamos con criptosistemas serios), el saber cómo
funcionan estos y conocer el diseño elemental de algunos sistemas seguros.

La criptografía es una de las ciencias consideradas como más antiguas, ya que sus
orígenes se remontan al nacimiento de nuestra civilización. Su uso original era el proteger
la confidencialidad de informaciones militares y políticas, pero en la actualidad es una
ciencia interesante no sólo en esos círculos cerrados, sino para cualquiera que esté
interesado en la confidencialidad de unos determinados datos: actualmente existe multitud
de software y hardware destinado a analizar y monitorizar el tráfico de datos en redes de
computadoras; si bien estas herramientas constituyen un avance en técnicas de seguridad
y protección, su uso indebido es al mismo tiempo un grave problema y una enorme fuente
de ataques a la intimidad de los usuarios y a la integridad de los propios sistemas. Aunque
el objetivo original de la criptografía era mantener en secreto un mensaje, en la actualidad
no se persigue únicamente la privacidad o confidencialidad de los datos, sino que se busca
además garantizar la autenticidad de los mismos (el emisor del mensaje es quien dice ser,
y no otro), su integridad (el mensaje que leemos es el mismo que nos enviaron) y su no
repudio (el emisor no puede negar el haber enviado el mensaje).

Podemos dividir la historia de la criptografía en tres periodos fundamentales; hasta
mediados de siglo, tenemos la criptografía precientífica, considerada no una ciencia sino
más bien un arte. En 1949, Shannon logró cimentar la criptografía sobre unas bases
matemáticas (Shannon, 1949), comenzando el período de la criptografía científica. Poco

2



COIICV 2003

Criptografía

más de diez años después se comenzó a estudiar la posibilidad de una comunicación
secreta sin que ambas partes conocieran una clave común (hasta ese momento la
existencia de dicha clave era la base de toda la seguridad en el intercambio de
información), de forma que esos estudios dieron lugar a diversos artículos sobre el tema
durante la década de los setenta ((Ellis, 1970), (Cocks, 1973), (Williamson, 1974),
(Williamson, 1976)...). Finalmente, en 1976 Diffie y Hellman publicaron sus trabajos sobre
criptografía de clave pública (Diffie, 1976), dando lugar al período de criptografía de clave
pública, que dura hasta la actualidad.

2 Teoría de números

La criptografía es una ciencia rodeada desde la antigüedad de un halo de misterio:
secretos, ocultación, espías... No obstante, y a pesar de las infinitas historias que se
podrían contar relacionadas con los sistemas de cifra, es necesario recordar que su base
es puramente matemática, y que está estrechamente relacionada con otras ciencias como
la estadística, la teoría de la complejidad, o la teoría de números. En este punto vamos a
presentar unas bases matemáticas elementales para poder comprender diferentes
aspectos de la criptografía que iremos tratando a lo largo de todo el capítulo; para
profundizar más en estas bases matemáticas y obtener referencias adicionales podemos
consultar (como casi siempre al hablar de criptografía) la obra (Schneier, 1994).

2.1 Números primos

Se denomina número primo a cualquier entero mayor que 1 divisible únicamente por él
mismo y por la unidad: estos son sus únicos factores. Ejemplos de números primos son 2,
3 o 5, aunque en criptografía (sobre todo en la de clave pública) es únicamente útil la
utilización de números primos extremadamente grandes, de 512 bits o incluso más, como
2756839-1; el conjunto de números primos es obviamente infinito.

Se dice que dos números a y b son relativamente primos si no comparten entre sí más
factores que la unidad; un número primo es relativamente primo al resto de números,
excepto a sus múltiplos. Otra forma de decir que dos números son relativamente primos
es que su máximo común divisor sea la unidad (mcd(a,b)=1), definiendo el máximo
común divisor de dos números como el número más grande que divide a ambos. Una
forma habitual de calcular el máximo común divisor de dos números es mediante el
algoritmo de Euclides (que no lo inventó realmente, sino que sólo lo publicó en torno al
año 300 a.C.)

COIICV 2003



3

Antonio Villalón Huerta

2.2 Aritmética modular

Definimos la relación de congruencia módulo p, denotada por a ≡ b mod p, si se cumple
que a=b+k·p, para un entero dado p (dicho de otra forma, si a-b es múltiplo de p). En
esta relación, b se denomina residuo de a mod p, y se dice que a es congruente con b
mod p. Al conjunto de enteros de 0 a p-1 se le denomina conjunto completo de residuos
módulo p: esto significa que para cada entero a, su residuo módulo p es un número
entero entre 0 y p-1. La operación a mod p se denomina reducción modular, y denota
el residuo de a, de forma que este residuo es un entero entre 0 y p-1; por ejemplo,
100=34 mod 11, ya que 100=34+11·6. Como la aritmética entera, la modular cumple las
propiedades conmutativa, asociativa y distributiva.

En criptografía es habitual el uso de la aritmética modular debido a que el cálculo de
logaritmos discretos y raíces cuadradas mod p pueden ser problemas computacionalmente
duros; además, la aritmética modular utiliza cálculos que se realizan cómodamente en
ordenadores, ya que restringe tanto el rango de valores intermedios calculados como el
resultado final: no tenemos que utilizar grandes números (y por tanto, grandes reservas
de memoria) para almacenar resultados, ya que su tamaño siempre estará limitado.

Cuando el número p al que hemos hecho referencia es primo forma lo que se denomina
un Campo de Galois módulo p, denotado GF(p), en el que se cumplen las leyes habituales
de la aritmética entera, y que es enormemente utilizado en protocolos criptográficos,
como veremos a continuación.

2.3 Exponenciación y logaritmo discreto

Muchos sistemas criptográficos utilizan operaciones