PDF de programación - 32 años de cartografía asimétrica y de clave pública

>> Jorge Dávila

32 años de criptografía asimétrica

y de clave pública

Hace más de treinta años que se inventó el concepto de criptografía de
clave pública y uno de sus inventores, Martin Hellman, tuvo ocasión
de rememorarlo recientemente en Madrid. Con la perspectiva que
da el tiempo, y con pocas alternativas en este sector, empieza a ser
el momento en el que plantearse si se puede seguir confiando en el
RSA, si hay que pasar a las curvas elípticas o si, por el contrario,
todavía queda mucho que hacer en la criptografía asimétrica.

toda la criptografía.

Ellos identificaron a las fun-
ciones de sentido único como
una pieza clave para poder
construir la criptografía moder-
na. Dentro de esas cavilaciones,
se plantearon la posibilidad de
que hubiese funciones que fue-
sen de sentido único para todos
y no para unos pocos. Con esa
segunda asimetría esencial, acu-
ñaron el concepto de funciones

todo este ultimo, percibieron la
utilidad que tendrían ese tipo de
sistemas para resolver el proble-
ma esencial de la criptografía
simétrica convencional, que no
es otro que el de la distribución
de claves simétricas.

En su conferencia, Hellman
contó, con la tranquilidad de
quien puede hacerlo de primera
mano, lo fácil que fue pergeñar
el protocolo de negociación de

Con un sencillo juego conceptual, Diffie, Hellman y Merkle
–sobre todo este último–, percibieron la utilidad que tendrían
ese tipo de sistemas para resolver el problema esencial de
la criptografía simétrica convencional, que no es otro que
el de la distribución de claves simétricas.

A principios del pasado
diciembre pasó por España
para dar un par de conferen-
cias el Dr. Martin Hellman.
La primera de ellas fue para
hablar de su participación en
el invento de la criptografía
de clave pública y del pro-
tocolo que lleva su nombre,
y la segunda como parte de su
activismo contra la guerra.

Hellman, de pura cepa neo-
yorquina, se licenció en 1966 en
la Universidad de Nueva York,
para luego cambiar de costa e
irse a la Universidad de Stanford
donde adquirió primero el grado
de máster en 1967, y luego el
de doctor en 1969; todo ello
en ingeniería eléctrica. Durante
los años 1968–1969 trabajó en
el Watson Research Center de
IBM donde coincidió con Horst
Feistel. Entre 1969 y 1971 fue
profesor titular del MIT, para ter-
minar regresando a Stanford en
1971 donde desarrolló sus acti-
vidades hasta 1996, fecha en la
que pasó a ser Profesor Emérito
de dicha institución.

En la citada conferencia
–auspiciada por la Cátedra
UPM Applus+ de Seguridad
y Desarrollo de la Sociedad
de la Información– rememoró
el nacimiento del concepto de
criptografía de clave pública
hace ya treinta y un años. Todo
empezó a principios de la década
de los setenta, tiempos en los
que Hellman, Diffie y Merkle,
meditaban sobre cuál era el
componente elemental y más
sencillo sobre el que construir

de sentido único con trampa, y
con ello la Criptografía de clave
pública.

De hecho, la clave pública
es esa función de sentido único
que todos pueden calcular con
cierta eficiencia, pero nadie pue-
de invertir, y la clave privada es
esa información que se mantiene
en secreto y que desbarata la
característica de sentido único
de la función anterior. Con
este sencillo juego conceptual,
Diffie, Hellman y Merkle, sobre

claves que lleva su nombre.
Buscando una función asimé-
trica, preguntó a un amiguete
matemático, que era John Gill
–un gran desconocido en todo
este tinglado–, y a él le atribuye
el mérito de haber elegido el lo-
garitmo discreto en aritmética
modular como función difícil,
como función de sentido único 1.
Así pues, en ese punto ya tenían
establecido un protocolo que
permite a dos agentes negociar
en absoluto público una clave

1 La operación cortaría al cálculo de logaritmos discretos en una aritmética modular, es la operación de exponenciación que, aun siendo pesada,
es fácil de calcular. El cálculo de logaritmos discretos no es tarea fácil, y en algunos casos es realmente difícil. Ver http://en.wikipedia.org/
wiki/Discrete_logarithm

2 Ver http://en.wikipedia.org/wiki/Diffie-Hellman o http://tools.ietf.org/html/rfc2631
3 W. Diffie, M. E. Hellman, New Directions in Cryptography, IEEE Trans. on Information Theory, Vol. IT-22, Nov. 1976, pp. 644-654. Ver en http:

//www-ee.stanford.edu/%7Ehellman/publications/24.pdf

4 M. E. Hellman, An Overview of Public Key Cryptography, IEEE Communications Magazine 50th Anniversary Issue: Landmark 10 Papers, May

2002, pp. 42-49 (Invited Paper). disponible en http://www-ee.stanford.edu/%7Ehellman/publications/73.pdf

5 Taher ElGamal, A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory,

v. IT-31, n. 4, 1985, pp 469–472 , o bien en las actas de la conferencia CRYPTO 84, pp10–18, Springer-Verlag.

6 En 1996 se publicó una revisión del algoritmo en la publicación FIPS 186-1, y su validez se amplió en el año 2000 como la publicación del

documento FIPS 186-2.

7 N. Koblitz, Elliptic curve cryptosystems, en Mathematics of Computation 48, pp. 203–209 1987.
8 V. Miller, Use of elliptic curves in cryptography, CRYPTO 85 Proceedings, 1985.

102

esencialmente secreta. A ese
protocolo, según el Dr. Hell-
man, debería llamársele de
“Diffie-Hellman-Merkle” 2, y
esos tres autores solicitaron
su patente en EEUU al año
siguiente de su publicación 3
(USA Patent 4.200.770).

Revisiones

Desde su publicación, son
varias las revisiones que se han
hecho de aquel artículo seminal.
La primera fue por parte de los
mismos autores a los diez años
de la publicación del original. La
segunda se produjo en 2003,
donde se recurrió a volver a
publicar el artículo original in-
cluyendo algunos nuevos ma-

teriales 4. En la primera de ellas,
la del año 1978, ya se incluye el
descubrimiento del algoritmo
RSA, y con ello parecen fraguar
todas las posibilidades disponi-
bles. Sin embargo, en 1984 Ta-
her ElGamal publica 5 un nuevo
sistema de cifrado basado en el
problema del logaritmo discreto,
que luego, en 1993, inspiró el
estándar DSA de firma digital
(FIPS 186) 6 del NIST.

Criptografía de Curvas
Elípticas

Contemporánea con la
propuesta de ElGamal, llegó la
Criptografía de Curvas Elípti-
cas que es otra aproximación
al concepto de clave pública.
Este nuevo planteamiento se
construye sobre la estructura
algebraica de las curvas elípti-
cas sobre cuerpos finitos, y el
uso de estas curvas con fines
criptográficos se lo debemos a
Neal Koblitz 7 y Víctor S. Miller 8

F E B R E R O 2 0 0 8 / N º 7 8 / S i C

que, independientemente, lo
propusieron en 1985. Con esto
se cierra la oferta de distintos
sistemas de clave pública. Es
cierto que se han publicado
algunas variantes de cifrado y,
sobre todo muchas de firma
digital, pero realmente no hay
nada esencialmente nuevo en
el panorama de la criptografía
asimétrica.

De todos los sistemas
mencionados, el más popular
y conocido es el RSA, pero con
el paso de los años, está viendo
cómo necesita aumentar rápida-
mente las longitudes de clave si
quiere mantener el mismo nivel
de seguridad. En 2002 se consi-
deraba que la longitud mínima
de una clave RSA debía ser de
1.024 bits y se estimaba que su
seguridad real era equivalente a
80 bits en una clave simétrica.
Esos mismos cálculos decían que
2.048 bits RSA equivalen a 112
bits y que 3.072 bits RSA serían
la contraparte asimétrica de una
clave simétrica de 128 bits. La
misma compañía recomienda
que las claves RSA de 1.024 bits
se utilicen hasta el año 2010,
que las de 2.048 bits puedan
aguantar hasta el año 2030 y,
por ultimo, que se utilicen las
claves RSA de 3.072 bits si se
persigue tener seguridad más
allá del umbral del año 2030.
Un borrador de una guía sobre
la gestión de claves que está
desarrollando el NIST va más
allá y sugiere que las claves
RSA de 15.360 bits tienen una
resistencia equivalente a 256 bits
de clave simétrica.

Previsiones del NIST

En su documento del pa-
sado mes de agosto 9, titulado
“SP800-78: Cryptographic
Algorithms and Key Sizes for
Personal Identity Verification”,
el NIST considera que, para el

primer día del año 2011, los
cifrados con seguridades equi-
valentes a 80 bits de cifrado
simétrico ya estarán fuera de
juego, al menos para la identi-
ficación personal, y los sistemas
deberán haber migrado a una
seguridad equivalente a 112 bits
o hacia cotas más elevadas. Para
los sistemas asimétricos basados
en criptografía de curvas elípticas
se especifica un mínimo de 112
bits de resistencia, lo que supo-
ne utilizar claves de 224 bits de
longitud.

uso, protocolos criptográficos,
etc. La NSA norteamericana
obtuvo en 2003 la licencia de
explotación por quince años, de
26 de las patentes esenciales de
Certicom, por lo cual pagó 25
millones de dólares, y así poder
desarrollar los algoritmos de la
denomina Suite B de la NSA. La
razón de este gasto, no es otro
que el de dejar expedito el ca-
mino a todas aquellas empresas
que desarrollen productos para
la NSA, y que vayan a incluir en
ellos algo relativo a la ECC.

lineales creados al azar, 6) el
problema del viajante, y otros
problemas NP-completos. Aun-
que de estos últimos hay muchos
ejemplos, sólo los cinco primeros
anteriores se han asomado, y al-
gunos anidado, en los pagos de
la criptografía.

Está claro que no es fácil
diseñar funciones matemáticas
de sentido único, pero nuestra
experiencia natural está llena
de ellas. Quizás un buen ejem-
plo de ello sea la ecuación de
propagación del calor que, ma-

El NIST considera que, para el primer día del año 2011, los cifrados
con seguridades e