807-Criptologia de Empleo ENS-mar11 PDF
807-Criptologia de Empleo ENS-mar11 PDF
807-Criptologia de Empleo ENS-mar11 PDF
MARZO 2011
SIN CLASIFICAR
SIN CLASIFICAR
CCN-STIC-807 v. 1.0 Criptografía de empleo en el Esquema Nacional de Seguridad
Edita:
Security Wisdom ha participado en la elaboración y modificación del presente documento y sus anexos
LIMITACIÓN DE RESPONSABILIDAD
El presente documento se proporciona de acuerdo con los términos en él recogidos, rechazando expresamente
cualquier tipo de garantía implícita que se pueda encontrar relacionada. En ningún caso, el Centro Criptológico
Nacional puede ser considerado responsable del daño directo, indirecto, fortuito o extraordinario derivado de la
utilización de la información y software que se indican incluso cuando se advierta de tal posibilidad.
AVISO LEGAL
Quedan rigurosamente prohibidas, sin la autorización escrita del Centro Criptológico Nacional, bajo las sanciones
establecidas en las leyes, la reproducción parcial o total de este documento por cualquier medio o procedimiento,
comprendidos la reprografía y el tratamiento informático, y la distribución de ejemplares del mismo mediante
alquiler o préstamo públicos.
PRÓLOGO
El uso masivo de las tecnologías de la información y las telecomunicaciones (TIC), en todos los ámbitos
de la sociedad, ha creado un nuevo espacio, el ciberespacio, donde se producirán conflictos y agresiones,
y donde existen ciberamenazas que atentarán contra la seguridad nacional, el estado de derecho, la
prosperidad económica, el estado de bienestar y el normal funcionamiento de la sociedad y de las
administraciones públicas.
La Ley 11/2002, de 6 de mayo, reguladora del Centro Nacional de Inteligencia, encomienda al Centro
Nacional de Inteligencia el ejercicio de las funciones relativas a la seguridad de las tecnologías de la
información en su artículo 4.e), y de protección de la información clasificada en su artículo 4.f), a la vez
que confiere a su Secretario de Estado Director la responsabilidad de dirigir el Centro Criptológico
Nacional en su artículo 9.2.f).
Partiendo del conocimiento y la experiencia del CNI sobre amenazas y vulnerabilidades en materia de
riesgos emergentes, el Centro realiza, a través de su Centro Criptológico Nacional, regulado por el Real
Decreto 421/2004, de 12 de marzo, diversas actividades directamente relacionadas con la seguridad de las
TIC, orientadas a la formación de personal experto, a la aplicación de políticas y procedimientos de
seguridad, y al empleo de tecnologías de seguridad adecuadas.
Una de las funciones más destacables del Centro Criptológico Nacional es la de elaborar y difundir
normas, instrucciones, guías y recomendaciones para garantizar la seguridad de los sistemas de las
tecnologías de la información y las comunicaciones de la Administración, materializada en la existencia
de la serie de documentos CCN-STIC.
Disponer de un marco de referencia que establezca las condiciones necesarias de confianza en el uso de
los medios electrónicos es, además, uno de los principios que establece la ley 11/2007, de 22 de junio, de
acceso electrónico de los ciudadanos a los servicios públicos, en su artículo 42.2 sobre el Esquema
Nacional de Seguridad (ENS).
Precisamente el Real Decreto 3/2010 de 8 de Enero de desarrollo del Esquema Nacional de Seguridad fija
los principios básicos y requisitos mínimos así como las medidas de protección a implantar en los
sistemas de la Administración, y promueve la elaboración y difusión de guías de seguridad de las
tecnologías de la información y las comunicaciones por parte de CCN para facilitar un mejor
cumplimiento de dichos requisitos mínimos.
En definitiva, la serie de documentos CCN-STIC se elabora para dar cumplimiento a los cometidos del
Centro Criptológico Nacional y a lo reflejado en el Esquema Nacional de Seguridad, conscientes de la
importancia que tiene el establecimiento de un marco de referencia en esta materia que sirva de apoyo
para que el personal de la Administración lleve a cabo su difícil, y en ocasiones, ingrata tarea de
proporcionar seguridad a los sistemas de las TIC bajo su responsabilidad.
Enero de 2011
ÍNDICE
1. INTRODUCCIÓN........................................................................................................................ 8
1.1. ORGANISMOS DE ESTANDARIZACIÓN.......................................................................... 8
2. OBJETIVO ................................................................................................................................... 9
3. ALGORITMOS ACREDITADOS............................................................................................... 9
3.1. CIFRADO SIMÉTRICO ......................................................................................................... 9
3.2. PROTOCOLOS DE ACUERDO DE CLAVE........................................................................ 9
3.3. ALGORITMOS ASIMÉTRICOS.......................................................................................... 10
3.4. FUNCIONES RESUMEN..................................................................................................... 10
4. PRODUCTOS CERTIFICADOS............................................................................................... 10
5. MEDIDAS DE SEGURIDAD ................................................................................................... 11
5.1. MECANISMOS DE IDENTIFICACIÓN ............................................................................. 11
5.1.1. NIVEL BAJO.................................................................................................................... 11
5.1.2. NIVEL MEDIO................................................................................................................. 11
5.1.3. NIVEL ALTO ................................................................................................................... 12
5.2. MECANISMOS DE AUTENTICACIÓN............................................................................. 12
5.2.1. NIVEL BAJO.................................................................................................................... 12
5.2.2. NIVEL MEDIO................................................................................................................. 12
5.2.3. NIVEL ALTO ................................................................................................................... 13
5.3. PROTECCIÓN DE LA CONFIDENCIALIDAD ................................................................. 13
5.3.1. NIVEL BAJO.................................................................................................................... 13
5.3.2. NIVEL MEDIO................................................................................................................. 13
5.3.3. NIVEL ALTO ................................................................................................................... 14
5.4. PROTECCIÓN DE LA AUTENTICIDAD Y DE LA INTEGRIDAD ................................ 14
5.4.1. NIVEL BAJO.................................................................................................................... 14
5.4.2. NIVEL MEDIO................................................................................................................. 15
5.4.3. NIVEL ALTO ................................................................................................................... 15
5.5. CIFRADO DE LA INFORMACIÓN .................................................................................... 15
5.5.1. NIVEL BAJO.................................................................................................................... 15
5.5.2. NIVEL MEDIO................................................................................................................. 15
5.5.3. NIVEL ALTO ................................................................................................................... 15
5.6. PROTECCIÓN DE CLAVES CRIPTOGRÁFICAS ............................................................ 16
5.6.1. NIVEL BAJO.................................................................................................................... 16
5.6.2. NIVEL MEDIO................................................................................................................. 16
5.6.3. NIVEL ALTO ................................................................................................................... 16
5.7. FIRMA ELECTRÓNICA ...................................................................................................... 16
5.7.1. NIVEL BAJO.................................................................................................................... 17
5.7.2. NIVEL MEDIO................................................................................................................. 17
5.7.3. NIVEL ALTO ................................................................................................................... 17
5.8. SELLOS DE TIEMPO........................................................................................................... 18
5.8.1. NIVEL BAJO.................................................................................................................... 18
5.8.2. NIVEL MEDIO................................................................................................................. 18
5.8.3. NIVEL ALTO ................................................................................................................... 18
ANEXO A. CRIPTOGRAFÍA DE CLAVE SIMÉTRICA: CIFRADORES EN FLUJO........... 19
1. SISTEMAS CRIPTOGRÁFICOS: CONCEPTOS BÁSICOS.............................................. 19
1.1. PRINCIPIOS DE SUSTITUCIÓN Y TRANSPOSICIÓN............................................... 21
1. INTRODUCCIÓN
1. El desarrollo de la sociedad actual repercute en la administración del estado al tener que
actualizar ésta los sistemas electrónicos con el fin de proporcionar a los ciudadanos los
mismos servicios electrónicos que ofrece de forma local. Tal actualización supone una
remodelación la seguridad de los sistemas para su adaptación a los nuevos requisitos y
posibles amenazas.
2. El Centro Criptológico Nacional (CCN) lleva años trabajando en la securización,
evaluación y acreditación de los sistemas de información de la administración del estado,
además de la formación del personal de dicha administración.
3. Dentro de la estructura del CCN se encuentra el Organismo de Certificación (OC) del
Centro Criptológico Nacional que comprende a las entidades públicas o privadas que
deseen ejercer como laboratorios de evaluación de la seguridad de las Tecnologías de la
Información (TI) en el marco del Esquema Nacional de Evaluación y Certificación de la
Seguridad de las Tecnologías de la Información (ENECSTI). También incluye a las
entidades públicas o privadas que sean fabricantes de productos o sistemas de TI que
pretendan certificar la seguridad de sus productos en el marco del ENECSTI (véase
http://www.oc.ccn.cni.es/index_es.html para mayor información). Los certificados
“Common Criteria” emitidos por el Organismo de Certificación están reconocidos
internacionalmente por más de veinte países. Además, el OC está acreditado por la
Entidad Nacional de Acreditación, conforme a los criterios recogidos en la Norma UNE-
EN 45011:1998 para la certificación de productos.
4. Por esta razón los sistemas, productos y equipos evaluados y certificados por el CCN
cumplen los requisitos de funcionalidad que tales productos afirman verificar en la
declaración de seguridad.
2. OBJETIVO
13. En la presente guía se presentan los algoritmos criptográficos que han sido acreditados
para el uso únicamente en el Esquema Nacional de Seguridad, cuando sus características
y requerimientos se consideren necesarios.
3. ALGORITMOS ACREDITADOS
14. La siguiente relación de algoritmos y protocolos criptográficos se consideran acreditados
por el CCN para su uso dentro del Esquema Nacional de Seguridad (ENS), siempre que
se realice una implementación correcta de los mismos según las especificaciones
adjuntas:
4. PRODUCTOS CERTIFICADOS
27. Se entiende por productos certificados todos aquellos que hayan sido evaludados
conforme a normas europeas o internacionales y que estén certificados por entidades
independientes de reconocida solvencia.
28. Tendrán la consideración de normas europeas o internacionales, ISO/IEC 15408, u otras
de naturaleza y calidad análogas.
29. Tendrán la consideración de entidades independientes de reconocida solvencia las
recogidas en los acuerdos o arreglos internacionales de reconocimiento mutuo de los
certificados de la seguridad.
30. Dado que la lista de los productos certificados es muy extensa y podría quedar obsoleta
por la certificación de nuevos productos, se recomienda consultar las listas actualizadas
de productos certificados de los organismos de acreditación y certificación anteriores. En
particular, son de especial interés la página web del Organismo de Certificación del
5. MEDIDAS DE SEGURIDAD
32. A continuación se listan cada una de las medidas de seguridad especificadas en el ENS
que utilizan algoritmos criptológicos acreditados, determinando la fortaleza criptológica
mínima necesaría para cada dimensión.
49. Para este nivel, el mecanismo de autenticación recurre a dos propiedades: algo que se
tiene (token) y algo que se es (patrón biométrico). No está aconsejado el uso de claves
concertadas, en el caso de utilización se permitirán aquellas que estén formadas de al
menos 8 caracteres alfanuméricos. Si estos últimos son generados de forma aleatoria o
pseudoaleatoria, deberán poseer la suficiente seguridad como para evitar repeticiones o
hipótesis acerca de su posible valor (ver el Anexo G).
50. De nuevo, para evitar posibles ataques por fuerza bruta, se recomienda la utilización de
políticas de bloqueo de contraseñas, de modo que después de determinado número de
intentos fallidos (se recomiendan hasta tres intentos) el acceso mediante contraseña quede
bloqueado o métodos de retardo de solicitud de contraseña.
deberán garantizar, para este nivel medio, una seguridad equivalente a 112 bits (ver el
Anexo B).
59. Por su parte, SSL y su sucesor TLS, son protocolos criptográficos que proporcionan
autenticidad y privacidad en una red, es decir, comunicaciones seguras, haciendo uso de
métodos criptográficos. En general, en estos protocolos únicamente se autentica el
servidor, quedando el cliente sin autenticar. Al igual que con IPsec, las claves que se
utilicen en estos protocolos deberán tener un nivel de seguridad de 112 bits.
60. Un nivel de seguridad de 112 bits se traduce en claves de 112 bits (o superiores) para los
sistemas de cifrado simétrico TDEA y AES (ver secciones 3 y 4 del Anexo B), en claves
de longitud 2048 bits (o superiores) para el criptosistema RSA (ver Anexo C) y en claves
de longitudes comprendidas entre los 224 y 255 bits para criptosistemas basados en
curvas elípticas (ver sección 2 del Anexo D).
77. Se entienden por sistemas de cifrado seguros los que garantizan una seguridad de, al
menos, 128 bits. Es decir, se emplearán claves para el cifrado/descifrado de información
de 128 bits (o mayores) para los criptosistemas de cifrado simétrico TDEA y AES (ver
secciones 3 y 4 del Anexo B) y claves de entre 256 y 283 bits para los criptosistemas
basados en curvas elípticas (ver sección 2 del Anexo D). Para el caso particular del
criptosistema RSA (ver Anexo C), se permiten claves de 2048 bits, si bien se recomienda
que dicha longitud sea mayor en la medida de lo posible.
112. Según sean las claves utilizadas en el proceso de cifrado/descifrado, existe una primera
clasificación de métodos criptográficos:
113. MÉTODOS CRIPTOGRÁFICOS DE CLAVE SIMÉTRICA: son aquellos en los que la
clave de cifrado coincide con la clave de descifrado. Esta clave única tiene que
permanecer secreta y ser conocida exclusivamente por A y B. Este hecho presupone que
emisor y receptor se han puesto previamente de acuerdo en la determinación de la misma
o que existe un centro de distribución de claves, que por un canal seguro, la hace llegar a
ambos comunicantes.
114. Estos métodos tienen pues que solventar el difícil problema de la distribución de claves.
115. MÉTODOS CRIPTOGRÁFICOS DE CLAVE ASIMÉTRICA: son aquellos en los que la
clave de cifrado es diferente a la de descifrado. En general la clave de cifrado es conocida
libremente por el público, mientras que la de descifrado es conocida únicamente por el
usuario sin tener que compartirla con nadie.
116. Estos métodos claramente evitan el problema de la distribución de claves.
117. La Criptografía simétrica también se denomina Criptografía clásica o Criptografía de
clave secreta, mientras que los métodos asimétricos se corresponden con la llamada
Criptografía de clave pública, introducida por Diffie y Hellman en 1976 ([Diffie and
Hellman, 1976]).
118. En los anexos subsiguientes se ahondará en cada uno de estos métodos criptográficos.
119. Conceptualmente hablando, los procedimientos de clave asimétrica resultan mucho más
satisfactorios puesto que evitan el complejo entramado de la gestión de claves. Sin
embargo, a la hora de implementarlos, son procedimientos muy lentos especialmente
cuando se comparan con los de clave simétrica. Esto los hace menos eficientes cuando
hay que proteger grandes cantidades de información.
120. En la práctica se tiende a una solución ecléctica: se utiliza la Criptografía de clave
asimétrica para la distribución de claves, puesto que éstas tiene una longitud corta. Una
vez que emisor y receptor disponen de una misma clave secreta, entonces ya se utiliza un
método criptográfico simétrico.
121. La Criptografía de clave simétrica se divide a su vez en dos grupos fundamentales:
122. MÉTODOS DE CIFRADO EN FLUJO: son aquellos en los que la transformación de
cifrado se aplica sobre cada símbolo del alfabeto en el que está escrito el mensaje
original. Actualmente toda la información está codificada en un alfabeto binario, luego la
transformación de cifrado se aplica sobre cada bit del texto claro.
123. MÉTODOS DE CIFRADO EN BLOQUE: son aquellos en los que la transformación de
cifrado se aplica sobre un grupo (bloque) de símbolos del alfabeto en el que está escrito el
mensaje original dando lugar a un bloque de texto cifrado. En la práctica estos bloques
pueden ser de 64, 128 ó 256 bits del mensaje original dependiendo del método de cifrado
utilizado.
124. Tradicionalmente la Criptografía se ha asociado con el concepto de confidencialidad, es
decir, que la información transmitida sea incomprensible para todos con excepción de los
dos comunicantes A y B.
125. Hoy en día la confidencialidad es tan sólo un elemento más entre otros muchos aspectos a
considerar en cuestiones de seguridad tales como:
Autenticidad tanto del criptograma (integridad) como del par emisor/receptor (que se trate
realmente del legítimo emisor/receptor).
No-repudio o negación de la recepción de un mensaje por parte del receptor.
Control de acceso a unos determinados dispositivos o servicios.
Protocolos criptográficos para establecer una comunicación, etc.
126. Todos ellos conforman ese concepto más amplio y general que actualmente se denomina
seguridad en comunicaciones.
135. Basándose en estas dos hipótesis, Shannon enunció sus condiciones de secreto perfecto
que se definen tal y como sigue:
136. Un sistema criptográfico verifica las condiciones de secreto perfecto si el texto claro X es
estadísticamente independiente del criptograma Y, lo que en lenguaje probabilístico
puede expresarse como
P(X = x | Y = y) = P(X = x)
para todos los posibles textos fuentes x y todos los posibles criptogramas y. Es decir la
probabilidad de que la variable aleatoria X tome el valor x es la misma con o sin
conocimiento del valor tomado por la variable aleatoria Y.
137. En términos más sencillos, esto equivale a decir que la información sobre el texto claro
aportada por el criptograma es nula. Por tanto, el enemigo criptoanalista no puede hacer
una mejor estimación de X con conocimiento de Y que la que haría sin su conocimiento,
independientemente del tiempo y recursos computacionales de los que disponga para el
procesado del criptograma.
138. Una vez establecidas las condiciones de secreto perfecto, la pregunta natural que uno
puede hacerse es: ¿existen cifradores perfectos?
139. La respuesta es afirmativa y a continuación se presenta una familia de cifradores que las
verifica.
140. Se considera un método de cifrado en el que tanto texto claro como criptograma y clave
tomen valores en un alfabeto de L elementos, esto es {0, 1, ..., L–1} y en el que la
longitud de la clave, del criptograma y del texto claro sean iguales entre sí e iguales a M.
En este caso el número de posibles textos claros, criptogramas y claves son iguales entre
sí e iguales a LM.
141. Se supone que:
142. La clave Z se elige de forma completamente aleatoria, es decir
P(Z = z) = L–M.
143. La transformación de cifrado es
donde ⊕ denota la adición módulo(1) L del i-ésimo elemento de texto claro Xi con el i-
ésimo elemento de la clave Zi para dar lugar al i-ésimo elemento de criptograma Yi.
144. Fijado un texto claro X = x, a cada posible valor de la clave Z = zj, (j = 1, ..., LM), le
corresponde unívocamente un criptograma Y = yj, (j = 1, ..., LM ). Entonces, de acuerdo
con las condiciones anteriores, es fácil ver que a un mismo texto claro X = x le puede
corresponder con igual probabilidad cualquiera de los LM posibles criptogramas.
145. Luego,
(1)
Una operación módulo un número dado consiste en realizar la operación y luego considerar como resultado de la
misma al resto de la división entre el resultado de la operación y el número dado.
146. Por tanto la información aportada por el criptograma sobre el texto claro es nula, X e Y
son estadísticamente independientes y la familia de cifradores basados en la suma módulo
L verifica las condiciones de secreto perfecto.
147. Hay que hacer notar que este tipo de cifrado módulo L ofrece una total seguridad respecto
a la estadística del texto claro. Se trata de una cualidad muy deseable, puesto que sería
extraordinariamente peligroso que la seguridad de un método de cifrado dependiera de la
naturaleza estadística del lenguaje utilizado en el mensaje a cifrar.
148. Cuando L = 2, resulta el cifrado Vernam.
Yi = Xi ⊕ Zi , (i = 1, ..., M ),
donde ⊕ denota ahora la adición módulo 2 y M es la longitud del texto claro, clave y
criptograma.
153. La operación de descifrado es una suma módulo 2 bit a bit (operación lógica OR-
exclusiva) entre los dígitos del criptograma y los dígitos de la clave, dando como
resultado los correspondientes dígitos del texto claro:
2. CIFRADO EN FLUJO
157. Aunque el cifrado Vernam ofrece teóricamente las máximas garantías de seguridad, en la
práctica presenta un inconveniente bastante evidente: requiere un dígito de clave secreta
por cada dígito de texto claro. Al mismo tiempo y para su implementación, hay que hacer
llegar por un canal seguro toda esa cantidad de clave tanto al emisor como al receptor.
158. Teniendo en cuenta la necesidad actual de cifrar grandísimas cantidades de información,
el método resulta poco factible para su aplicación generalizada. Queda más bien
reservado para aquellas circunstancias en las que se requieren unas condiciones máximas
de seguridad con un mínimo de información a proteger (por ejemplo, el teléfono rojo
Washington–Moscú en la época de la guerra fría, véase [Sgarro, 1990]).
159. Se trata, por tanto, de un procedimiento de cifrado incondicionalmente seguro pero poco
práctico a la hora de su implementación real. Así pues, debe ser modificado hasta
convertirlo en algo viable.
160. La estrategia para su modificación es la siguiente: en vez de usar como clave una
secuencia binaria perfectamente aleatoria se utilizan las secuencias generadas por
generadores pseudoaleatorios; es decir, algoritmos determinísticos que, a partir de una
clave corta elegida aleatoriamente (semilla del generador) y conocida únicamente por A y
B, generen simultáneamente en emisión y recepción una misma secuencia con la longitud
deseada.
161. Esta será la llamada secuencia cifrante que se sumará módulo 2 con el mensaje original
(en emisión) o con el criptograma (en recepción) y que hará las veces de clave en el
cifrado Vernam.
162. Esta versión modificada del cifrado Vernam es lo que se conoce como cifrado en flujo.
163. El aspecto más favorable es que un cifrado en flujo es ya implementable y susceptible de
ser utilizado masivamente, puesto que la clave que hay que hacer llegar a ambos
comunicantes es corta (128–256 bits).
164. El aspecto menos favorable es que estas secuencias cifrantes provienen de un algoritmo
determinístico, luego nunca serán auténticas secuencias aleatorias. Como mucho serán
secuencias pseudoaleatorias o secuencias que se asemejan a las aleatorias pero sin llegar a
serlo. Por tanto, dichas secuencias no verificarán propiamente las condiciones de secreto
perfecto de Shannon.
165. En cualquier caso, cuando el generador de secuencia pseudoaleatoria está bien diseñado,
el cifrado en flujo ofrece un nivel de seguridad suficientemente satisfactorio como para
permitir su uso generalizado.
166. En la Figura A.2 se ilustra el esquema general de un procedimiento de cifrado en flujo.
AC(k) = (A – D)/T
176. Una secuencia binaria finita que verifique estos tres postulados se denomina PN-
secuencia y verifica todas las propiedades de una secuencia binaria con distribución
uniforme.
177. El primer postulado establece que ceros y unos deben aparecer a lo largo de la secuencia
con igual probabilidad.
178. El segundo postulado comprueba que a lo largo de la secuencia las distintas muestras de n
dígitos consecutivos (n-gramas) ocurran con la probabilidad correcta. Véase para más
detalles el capítulo 2 de [Tilborg, 1988].
179. El tercer postulado comprueba que el cómputo de coincidencias entre una secuencia y su
versión desplazada no aporte ninguna información sobre el periodo de la misma, a menos
que ésta se desplace sobre sí misma un múltiplo de dicho periodo.
180. Toda secuencia binaria candidata a secuencia cifrante en un proceso de cifrado en flujo
debe cumplir necesariamente los tres postulados de pseudoaleatoriedad de Golomb.
181. IMPREVISIBILIDAD: La secuencia cifrante ha de ser imprevisible, quiere esto decir que
dada una porción de secuencia de cualquier longitud, un criptoanalista no debería
predecir el siguiente dígito con una probabilidad de acierto superior a ½.
182. Una medida de la imprevisibilidad de una secuencia es su complejidad lineal que denota
la cantidad de secuencia necesaria que hay que conocer para poder determinar el resto de
la misma. En términos criptográficos, la complejidad ha de ser tan grande como sea
posible pues eso quiere decir que se necesitaría una enorme cantidad de secuencia
cifrante interceptada para poder deducir los restantes bits.
183. Un algoritmo para calcular la complejidad lineal de una secuencia es el algoritmo de
Massey-Berlekamp ([Massey, 1969]) que corre en tiempo polinómico, es decir, que
emplea un corto periodo de tiempo para calcular la salida correspondiente a una entrada
dada.
184. EFECTO AVALANCHA: La secuencia cifrante producida por el generador
pseudoaleatorio tiene que depender de todos y cada uno de los bits de la clave o semilla.
Es decir, una variación de un único bit de la clave se ha de traducir en una nueva
secuencia donde al menos, en promedio, la mitad de los bits estén invertidos con relación
a la secuencia generada antes de la modificación de la clave. En caso contrario esto
significaría que algunos de los bits de clave son redundantes, lo que disminuiría el
tamaño del espacio de claves.
185. FACILIDAD DE IMPLEMENTACION: La secuencia tiene que ser fácil de generar con
medios electrónicos para su total aplicabilidad en el proceso de cifrado/descifrado. En
este apartado se incluyen una serie de aspectos técnicos: velocidad de generación
(adecuada para comunicaciones de banda ancha), coste de la implementación, tamaño del
hardware que la soporta, escalabilidad, consumo, facilidad para recuperar el sincronismo
entre emisión y recepción en caso de que se pierda, etc. Todos ellos han de tenerse en
cuenta a la hora de implementar el generador de secuencia cifrante.
195. Se denomina estado del registro al contenido de las etapas entre dos pulsos de reloj. El
estado inicial corresponde al contenido de las etapas en el momento de empezar el
proceso. En el caso representado en la figura este contenido inicial sería (1 0 0 0).
196. La sucesión de estados por los que va pasando el registro de la figura es: (1,0,0,0),
(0,0,0,1), (0,0,1,1), (0,1,1,1), … , (0,1,0,0). Es decir, la sucesión ordenada de todas las
configuraciones binarias de 4 bits a excepción del estado (0,0,0,0).
197. La PN-secuencia generada sería:1,0,0,0,1,1,1,1,0,1,0,1,1,0,0 de período T = 15, pues en
este caso el polinomio de realimentación es primitivo.
198. Las secuencias generadas por LFSRs con polinomios primitivos cumplen perfectamente
las propiedades exigibles a una secuencia cifrante (periodo largo, buena distribución
estadística de ceros y unos, buena correlación, facilidad de implementación, efecto
avalancha, etc.) pero la condición que no verifican es la referente a la imprevisibilidad.
199. Las PN-secuencias son fácilmente previsibles ya que conociendo L bits de la secuencia
de salida y el polinomio característico se puede deducir, mediante la resolución de un
sistema lineal de L ecuaciones con L incógnitas, el resto de la misma.
200. El problema de la previsibilidad de la secuencia de salida de los LFSRs es inherente al
hecho de que son estructuras lineales.
201. En Criptografía todo lo que sea lineal es susceptible de ser criptoanalizado. Sin embargo,
las restantes propiedades de las PN-secuencias son excelentes para su uso como
secuencias cifrantes.
202. Se trata por tanto de utilizar los LFSRs como estructuras básicas de los generadores pero
introduciendo algún elemento de no linealidad. Según sea esta manera de introducir no
linealidades se tendrán diversas familias de generadores de secuencia cifrante basadas en
LFSRs.
LC = (2L1 – 1) L2 + L3.
208. Nótese que esta manera de introducir la no linealidad mediante desplazamientos no
síncronos de los LFSRs provoca una complejidad lineal exponencial en la longitud de
uno de los registros, lo que supone una característica muy deseable desde el punto de
vista criptográfico.
209. Así y todo este tipo de generador sí presenta alguna vulnerabilidad a nivel de correlación
ya que la probabilidad de encontrar correlaciones entre valores consecutivos de la
secuencia de salida y de la secuencia generada por el LFSR3 es alta (véase [Brickell and
Odlyzko, 1988]).
210. GENERADOR SHRINKING: el generador shrinking ([Coppersmith, 1994]) es un
generador de secuencia cifrante constituido por sólo 2 registros de desplazamiento
LFSR1 y LFSR2.
211. Su creador ahondó en la idea de cómo con dos únicos LFSRs se puede diseñar un
generador sencillo, rápido y presumiblemente seguro desde un punto de vista
criptográfico.
212. El generador shrinking obedece al siguiente esquema, véase la Figura A.5.
236. La salida de cada uno de estos registros junto con la salida de una función no lineal se
suman módulo 2 para producir el correspondiente bit de secuencia cifrante.
237. La función no lineal incluye productos lógicos (AND) y una división aritmética.
238. La inicialización de este generador requiere el contenido inicial de los 4 LFSRs más 4
bits de memoria (nonces).
239. Al igual que la tecnología GSM, Bluetooth también funciona a nivel de un sistema de
tramas que se van cifrando sucesivamente. La longitud de trama es ahora de 2745 bits. La
diferencia con GSM es que la tecnología Bluetooth cifra cada trama con una clave
distinta.
240. Esto implica que el criptoanalista dispone solamente de 2746 bits para desarrollar su
criptoanálisis lo cual, en términos criptográficos, es demasiado poco. De ahí que ninguno
de los ataques criptoanalíticos desarrollados por vía algebraica o por correlación haya
resultado fructífero, véase como más representativo ([Armknecht, 2002]).
241. La inseguridad achacable al Bluetooth es más debida a un mal método de inicialización y
cambio de clave que a una debilidad detectada en el diseño del generador de secuencia
cifrante.
242. Hasta ahora se han enumerado algunos de los ejemplos más representativos de
generadores de secuencia cifrante encontrados en la literatura especializada. En la
siguiente sección se presentan las propuestas más recientes de cifradores en flujo
englobadas dentro del proyecto eSTREAM.
criptográfica etc. Las características de cada una de estas propuestas pueden encontrarse
en [eSTREAM, 2008].
249. En líneas generales los criterios exigidos a estas propuestas eran:
Criterios de seguridad: cualquier ataque criptoanalítico de recuperación de la clave tiene que ser al
menos tan costoso como la búsqueda exhaustiva.
Criterios de implementación: una longitud de clave de al menos 128 bits más un vector de
inicialización IV de entre 64–128 bits. Cualquiera de las propuestas tenía que tener unas
prestaciones superiores a las del AES (estándar criptográfico de cifrado en bloque).
Criterios de mercado: flexibilidad, eficiencia y posibilidad de un uso generalizado a nivel
mundial.
251. Tras una primera y segunda fase de evaluación, 16 propuestas pasaron a la tercera fase, 8
orientadas a su implementación software y otras tantas a su implementación hardware
(véase [eSTREAM, 2008], Phase 3 candidates).
252. Finalmente, la Comisión encargada de seleccionar un candidato de cada perfil se decantó
por un conjunto de cuatro algoritmos software Profile 1 (SW) y 3 hardware Profile 2
(HW), que son los que aparecen en la Cuadro A.1.
t1 ← s66 ⊕ s93
t2 ← s162 ⊕ s177
t3 ← s243 ⊕ s288
zi ← t1 ⊕ t2⊕ t3
5. CIFRADORES EN BLOQUE
268. Se denomina «Cifrado en bloque» a aquél en que se cifra el mensaje original agrupando
los símbolos en grupos (bloques) de dos o más. Algunos sistemas de cifra como el cifrado
poligráfico y el cifrado por transposición, son ejemplos elementales de cifrado en bloque.
269. Los cifrados en bloque pertenecen a la categoría de los cifradores de clave secreta,
también denominada clave simétrica. Es decir que la clave es única y se emplea tanto
para cifrar como para descifrar. La clave ha de ser distribuida mediante un mecanismo
seguro a los dos corresponsales que realizan el cifrado, bien mediante un correo seguro o
un sistema alternativo de cifrado.
F (K1) F (Kn)
K1 Kn
F (K2)
K2
F (K3)
F (K3) K3
K3
F (K2)
K2
F (Kn) F (K1)
Kn K1
279. Obsérvese que, en cada vuelta de cifrado i, el sub-bloque anterior derecho pasa al lugar
izquierdo posterior sin ninguna modificación; mientras que el sub-bloque anterior
izquierdo se suma módulo 2 (operación XOR) con la función F(Ki) del sub-bloque
derecho anterior y de la clave Ki de la correspondiente vuelta i, para constituir el sub-
bloque posterior derecho. Es decir, que cada vuelta (menos la última) termina con un
cruce como se muestra en la Figura B.2. Debido a este esquema, el número de
transformaciones que sufre cada bloque, a lo largo del algoritmo, es la mitad del número
de vueltas.
280. Es preciso destacar que dos vueltas impares sucesivas, o dos vueltas pares sucesivas, i e
i+2, que utilicen la misma clave de vuelta Ki = Ki+2, se neutralizan mutuamente; el
6. DES Y DEA
283. En 1977 el NBS (National Bureau of Standards, USA) publicó una norma especificando
un sistema de cifrado en bloque Data Encryption Standard (Norma o Estándar de Cifrado
de Datos), abreviadamente llamado DES. La aprobación y modificación de la propuesta
se hizo bajo la supervisión de la NSA (National Security Agency, USA). Este sistema
tenía que realizarse obligatoriamente con un microcircuito electrónico que se describió en
la Norma FIPS 46-1 ([NIST, FIPS46-1]).
284. En Diciembre de 1993 se revisó la norma y se publicó una nueva, la FIPS 46-2 ([NIST,
FIPS46-2]), que incluía la posibilidad de realizar el DES en software, firmware, hardware
o una combinación de ellos. El sistema, así realizado, pasó a denominarse Data
Encryption Algorithm (DEA).
285. El DEA es un algoritmo de cifrado en bloque cuya longitud de bloque es de 64 bits (ocho
símbolos ASCII). La longitud de la clave es de 64 bits; pero 8 de ellos se reservan para
paridad, quedando solamente 56 bits de clave útiles, lo que equivale a que existan 256
claves diferentes.
289. La norma que define el TDEA es la [NIST, SP800-67], de mayo de 2004. En ella se
redefine nuevamente el DEA como un componente del TDEA, su especificación coincide
enteramente con la de las anteriores normas retiradas. El TDEA se explica más adelante,
pero como sus componentes consisten en tres DEA, para comprenderlo es preciso
estudiar previamente el diseño del DEA.
K1
F(K1, D0)
Vuelta
nº 1
I1 D1
I15 D15
K16
F(K16, D15)
Vuelta
nº 16
I16 D16
Transformación
D16 I16
final
las 15 primeras con un cruce y la última sin cruce; pero por economía, para no construir o
programar dos tipos de vueltas diferentes, se llama 16 veces a una única rutina de
ejecución de vuelta con cruce, siendo entonces necesario el añadir el cruce de la
transformación final para anular el efecto del cruce de la última vuelta.
296. Después de la transformación final se obtiene el bloque cifrado:
I15 D15
K16
F(K16, D15)
Vuelta
nº 16 de
cifrado
I16 D16
Transformación
I ' 16 D' 16 final de
cifrado
K16
F(K16, D*0)
Vuelta
nº 1 de
descifrado
I*1 D*1
302. Como los desplazamientos han sido diferentes para cada vuelta, las 16 claves de 56 bits
del paso d son una permutación diferente de los 56 bits de entrada, pero el mecanismo de
selection del paso e, que reduce el número de bits a 48, implica que se utiliza un conjunto
diferente de bits en cada sub-clave; cada bit se usa aproximadamente en 14 de las 16 sub-
claves.
Mensaje Mensaje
n-2
claro Cifrado 1 Cifrado n cifrado
x ......... y
Clave K1 Clave Kn
3TDEA, variante en la que K1 ≠ K2 ≠ K3 ≠ K1, las tres claves son diferentes e independientes entre
sí. La seguridad efectiva frente a un ataque es de 112 bits, mientras que la longitud real de clave es
168 bits (más 24 bits de paridad). Se utiliza cuando el nivel de seguridad requerido es medio.
318. Nótese que ninguna de las variantes descritas del TDEA alcanza nivel de seguridad
elevado. En caso de necesidad de un nivel de seguridad elevado ha de recurrirse a otros
criptosistemas con claves de seguridad efectiva comprendida entre 128 y 256 bits.
Mensaje Mensaje
claro DES DES–1 DES cifrado
x y
8. AES Y RIJNDAEL
319. En 1996, el Instituto Nacional de Estándares y Tecnología (National Institute of
Standards and Technology, NIST) dio los primeros pasos para la creación de un Estándar
de Cifrado Avanzado (Advanced Encryption Standard, AES). Su objetivo fue desarrollar
una especificación para encontrar un algoritmo de cifrado que sustituyera al anticuado
DES, de manera que el nuevo algoritmo fuese capaz de proteger la información sensible
de los ciudadanos y del gobierno hasta bien entrado el siglo XXI. El algoritmo
seleccionado será utilizado por el Gobierno de Estados Unidos para proteger información
sensible no clasificada y voluntariamente por el sector privado. Por extensión,
presumiblemente, sería adoptado por el resto de países del mundo.
320. En septiembre de 1997, se realizó una convocatoria para la presentación de algoritmos,
los propuestos tenían que soportar obligatoriamente una longitud de bloque de 128 bits y
una longitud de clave de 128, 192 y 256 bits, al margen de cualesquiera otras longitudes
posibles.
321. A la citada convocatoria acudieron diversos diseñadores. La selección se llevó a cabo en
varias etapas eliminatorias; se hizo de forma pública basándose en las críticas, evaluación
y criptoanálisis realizados por la comunidad científica internacional.
322. Finalmente, el 2 de octubre de 2000, el NIST anunció el algoritmo ganador, denominado
Rijndael por sus autores Vincent Rijmen y Joan Daemen.
323. Los criterios considerados en la selección fueron los siguientes:
Seguridad (es decir, el esfuerzo necesario para criptoanalizarlos).
Eficiencia computacional.
Requisitos de memoria.
Adecuación hardware y software.
Simplicidad de diseño.
Flexibilidad.
Requisitos de licencia (no patentado, ni patentable).
324. El 26 de noviembre de 2001 el NIST publicó la norma definitiva, la FIP 197 ([NIST,
FIPS197]), que entró en funcionamiento el 26 de mayo de 2002. El texto completo se
puede localizar en http://csrc.nist.gov/publications/.
325. El Rijndael es un cifrador en bloque, que opera longitudes de Nb palabras de 32 bits; los
valores de Nb pueden ser 4, 6 y 8; la longitud de clave es de Nk palabras de 32 bits; los
valores de Nk pueden ser 4, 6 y 8. Es decir que tanto las longitudes de clave y como de
bloque pueden ser de 128, 192 ó 256 bits. El Rijndael es fácilmente adaptable a cualquier
longitud de bloque y/o clave múltiplo de 32 bits.
326. Este Anexo se limita a describir la versión finalmente aprobada y publicada por el NIST,
que restringe la longitud de bloque a 128 bits (Nb = 4), mientras que las claves pueden
ser de 128, 192 ó 256 bits.
330. En la Figura B.7 se ilustra el proceso de cifrado completo, que consta de tres etapas:
Una transformación inicial,
Nr–1 vueltas regulares,
Una vuelta final.
331. La transformación inicial consiste en una suma módulo 2 bit a bit (XOR bit a bit) de los
primeros 128 bits de la clave con el mensaje claro.
332. El número de vueltas Nr es función de la longitud de la clave: Nr = 10 para clave de 128
bits, Nr = 12 para clave de 192 bits y Nr = 14 para clave de 256 bits.
333. La transformación que tiene lugar en cada vuelta regular de cifrado está compuesta a su
vez por cuatro transformaciones diferentes:
Transformación inicial:
Texto claro Clave de Cifrado
AddRoundKey
Vuelta regular:
Expansión de
Nr -1 clave
vueltas SubBytes
ShiftRows
MixColumns
AddRoundKey
Vuelta final:
W0 W1 W2 W3
RW
SW
R c1 W4 W5 W6 W7
RW
SW
R c2 W8 W9 W 10 W 11
RW
Figura B.8. Principio del esquema de bloques de la expansión de claves del AES, para una
clave de 128 bits. Se muestran las 12 primeras palabras de las 44 totales.
341. Procesos análogos se llevan a cabo para la expansión de claves de 192 y 256 bits.
347. En los apartados siguientes se describen los diferentes modos de uso de los cifradores en
bloque. La nomenclatura utilizada es la siguiente: K es la clave que utiliza el cifrador;
CIFK significa la operación de cifrado en bloque utilizando la clave K; CIFK–1 significa
la operación inversa, con la misma clave K; b es la longitud del bloque correspondiente al
algoritmo de cifrado (en TDEA b = 64, en AES b = 128). Cuando el mensaje a cifrar
tenga más de un bloque se designará el número de bloques como N.
utilizado. En caso contrario se complementará el último trozo del texto claro con tantos
ceros como sea necesario, hasta alcanzar el tamaño de bloque cifrador utilizado.
pues al disponerse del mensaje solo es necesario hacer la operación de suma módulo 2,
que es sumamente rápida.
367. Para cada clave distinta que se use, el contenido de cada contador ha de ser diferente y no
reutilizarse; es decir si se usa una «clave de sesión» y cada sesión incluye el cifrado de
varios documentos, los contadores han de ser diferentes para cada documento que se
cifre. Una forma sencilla de conseguir este fin es construir de forma aleatoria un «número
de uso único» (en inglés, number used once: nonce) como cabecera del mensaje cifrado.
El contenido del contador nº1 sería el propio nonce, los contenidos de los contadores
serían los sucesivos incrementos del primer contador. El nonce cumple el mismo papel
que el vector inicial en otros modos.
368. Las propiedades del modo CTR de cifrado en bloque son:
Cada bloque cifrado es función del nonce, del incremento del contador, de la clave y del
correspondiente bloque de claro.
Cada bloque descifrado es función del nonce, del incremento del contador, de la clave y del bloque
cifrado correspondiente.
Cada error de transmisión afecta a un solo bit, es decir que cada bit de error aislado produce
únicamente 1 bit erróneo en el texto claro.
No es autosincronizante.
Se puede hacer que cifre mensajes iguales de forma diferente con solo cambiar cada vez el nonce.
No cambia el tamaño del espacio de claves.
Se puede cifrar y descifrar de forma paralelizada.
Para evitar ataques por distinción, la cantidad de bloques máxima del texto a cifrar, debe ser
inferior a la raíz cuadrada del número de estados posibles del cifrador en bloque usado, es decir
para el TDEA debe ser inferior a 232 bloques y para el AES inferior a 264 bloques.
373. Cuando el mensaje tiene un tamaño igual a un múltiplo del tamaño de bloque del cifrador
empleado se utiliza la primera subclave K1. En caso contrario se utiliza la segunda
subclave K2. En este caso, se completa el último bloque del mensaje con un bit «1»
seguido de tantos bits «0» como sea necesario hasta completar los bits necesarios.
374. En la Figura B.9 (a) se ilustra el diagrama de bloques del CMAC, en el caso en que el
mensaje tenga un tamaño igual a un múltiplo exacto de b bits. El mensaje se divide en N
bloques de b bits y se cifra de modo CBC durante los N–1 primeros bloques del mensaje;
pero el bloque MN se suma modulo 2 bit a bit con la clave K1 previamente a su cifrado,
una vez realizado este, se obtiene una palabra de b bits; de los cuales se retienen los T bits
más significativos MSBTlen, siendo T ≤ b. La elección adecuada de T depende de la
seguridad esperada del MAC y del número de bloques N del mensaje original.
375. En la Figura B.9 (b) se ilustra el diagrama de bloques del CMAC cuando el mensaje no
tenga un tamaño igual a un múltiplo exacto de b bits.
(a)
M1 M2 MN
K1
BMSLONG CMAC
(b)
M1 M2 MN 10...0
K2
MSBTlen CMAC
Figura B.9. Modo de Autenticación de Mensaje CMAC. (a) El mensaje tiene un tamaño
igual a un múltiplo de b bits. (b) El mensaje tiene un tamaño no múltiplo de b bits.
378. Nótese que solamente está aprobado para algoritmos de cifrado en bloque con 128 bits de
longitud de bloque, como el AES, no pudiéndose aplicar al DEA ni al TDEA.
399. Se han propuesto varias clases de grupos específicos para aplicar el protocolo de acuerdo
de clave Diffie-Hellman. Entre ellos destacan los siguientes:
Los grupos multiplicativos de cuerpos finitos grandes (cuerpos primos en [Diffie and Hellman,
1976] o extensiones finitas de los mismos),
Los grupos multiplicativos de clases de restos de números enteros módulo un número compuesto
([McCurley, 1988]),
Las curvas elípticas sobre cuerpos finitos ([Miller, 1986], [Koblitz, 1987]),
El jacobiano de una curva hiperelíptica sobre un cuerpo finito ([Koblitz, 1989]),
El grupo de clases de cuerpos cuadráticos imaginarios ([Buchmann and Williams, 1988]).
400. El «Problema de Diffie-Helman» (en inglés, Diffie-Hellman Problem, DHP) con respecto
al generador g del grupo G, consiste en calcular gab conociendo g, ga y gb.
401. Este problema está íntimamente relacionado con el «Problema del Logaritmo Discreto»
(en inglés, Discrete Logarithm Problem, DLP). Este problema consiste en calcular a
conociendo un generador g del grupo G y ga. De hecho, si el problema del logaritmo
discreto puede resolverse, entonces obviamente el DHP también; pero el recíproco no es
del todo exacto. Ahora bien, se conocen condiciones generales sobre el grupo G (que
básicamente afectan el tamaño de los factores primos del orden del grupo) bajo las cuales
el DHP y el DLP son equivalentes en tiempo polinómico probabilístico; para los detalles
de esta teoría pueden consultarse [Maurer, 1994], [Maurer and Wolf, 1996], [Maurer and
Wolf, 1999], [Maurer and Wolf, 2000].
402. Por otra parte, el «Problema de Decisión de Diffie-Hellman» (en inglés Diffie-Hellman
Decisional Problem, DHDP) consiste en lo siguiente: sea g un generador de G y
supóngase que ga, gb y gc se han elegido independiente y aleatoriamente en G según una
distribución uniforme. Dados los triples (ga, gb, gab) y (ga, gb, gc) en orden aleatorio, se
trata de decidir con probabilidad sustancialmente mayor que ½ cuál de los triples es el
correcto DHKA (ga, gb, gab).
403. El DHDP parece ser más fácil de resolver que el DHP en general. El DHP puede ser
difícil si el orden del grupo contiene al menos un factor primo grande, mientras que el
DHDP puede ser difícil sólo si el orden de G no tiene ningún factor primo pequeño.
404. Un protocolo de establecimiento de clave se dice que suministra «autenticación de clave»
si un usuario está seguro de que ningún otro usuario, aparte del destinatario legítimo,
puede conocer el valor de la clave de sesión.
405. Un protocolo de establecimiento de clave se dice que suministra «confirmación de clave»
si un usuario está seguro de que el destinatario legítimo tiene en realidad posesión de una
particular clave de sesión.
406. Si se proporciona la autenticación de clave o la confirmación de clave a ambos usuarios
implicados en el protocolo, entonces la autenticación se dice que es «mutua»; mientras
que si se proporciona a un solo usuario, la autenticación es «unilateral».
407. En términos generales, hay dos clases de protocolos de establecimiento de clave:
protocolos de «transferencia de clave» en los que se crea una clave por un usuario y se
transmite de modo seguro a un segundo usuario, y protocolos de «acuerdo de clave» en
los cuales ambas partes contribuyen información que establece conjuntamente la clave
secreta compartida. Para más detalles, véanse [Rueppel and Oorschot, 1994] y el capítulo
12 de [Menezes et al., 1997].
408. Existen tres protocolos de acuerdo de clave definidos en [Matsumoto et al., 1986] y
modificados en [Menezes et al., 1995] para evitar ciertos ataques, conocidos como
MTI/A0, MTI/B0 y MTI/C0, que son variantes del protocolo original de acuerdo de clave
de Diffie-Hellman.
409. También existe un protocolo para dos usuarios A y B que establece una clave de sesión k
transmitiendo solamente un mensaje de A a B; véanse [Nyberg and Rueppel, 1995] y
[Menezes et al., 1995].
410. En la sección 4 de [Menezes et al., 1995] se presentan dos protocolos de acuerdo de
clave. Difieren de los anteriores en que son simétricos, no interactivos y no requieren ni
funciones resumen (hash) ni cifrado.
2.1. DEFINICIONES
415. Dado un criptosistema de clave pública, si un usuario A quiere enviar al usuario B un
mensaje cifrado, tiene que seguir los pasos siguientes:
A selecciona en el directorio de claves públicas la clave pública correspondiente a B.
A cifra su mensaje aplicando la clave de B y se lo envía.
417. El sistema basa su seguridad en la dificultad que representa para cualquier usuario
distinto de B —desprovisto, por lo tanto, de la clave privada— descifrar el mensaje.
Cuanto mayor sea esa dificultad, más seguro se puede considerar el sistema y más difícil
será el trabajo del criptoanalista o atacante.
418. De forma más precisa, los criptosistemas de clave asimétrica pueden definirse a partir de
una función invertible entre el conjunto de todos los mensajes en claro, M, que se pueden
intercambiar dos usuarios y el conjunto de todos los textos cifrados, C, f: M→C, de modo
que sea «fácil» calcular el cifrado de un mensaje, f(m) = c, mientras que sea «difícil»
computar el descifrado del mismo, f ¹(c) = m, a no ser que se posea de determinada
información específica, como por ejemplo, la clave de descifrado.
419. Los términos «fácil» y «difícil» deben entenderse como que dicho cómputo requiere poco
o mucho tiempo de computación, respectivamente.
420. Una función que verifique las condiciones anteriores se denomina «Función
Unidireccional con Trampilla» (en inglés, Trapdoor One-Way Function, TOWF). La
información adicional extra es lo que se conoce como «trampilla».
421. En general, un «Criptosistema de Clave Pública» se puede definir como una familia de
funciones unidireccionales con trampilla, {fk}, de modo que para cada clave k∈K se debe
poder describir un algoritmo eficiente que permita calcular fk, pero de modo que sea
intratable, computacionalmente hablando, determinar tanto la clave k como (fk)–¹(·) sin
conocer el valor de k.
422. Hay dos funciones que, tradicionalmente, se emplean como funciones unidireccionales
con trampilla. La primera de ellas es el producto de números enteros, cuya inversa es la
factorización del número obtenido, y la segunda es la exponenciación discreta, cuya
inversa es el logaritmo discreto. Las dos funciones son fáciles de computar, mientras que
no lo son sus inversas. Es decir, dado un número compuesto n, es difícil determinar su
descomposición en factores primos y, por otra parte, dados a e y, es difícil calcular x de
modo que ax = y, en un grupo cíclico finito.
423. Estas dos funciones permiten implementar los dos criptosistemas de clave asimétrica más
extendidos en la actualidad, el criptosistemas RSA y el de ElGamal (y sus derivados).
424. Para simplificar la notación, se considera que e es la clave pública de un usuario A y que
d es su clave privada. Además, la función de cifrado utilizando una clave genérica k es
Ck, mientras que la función de descifrado con la misma clave sería Dk. Sea cual sea la
función unidireccional con trampilla que se emplee, un criptosistema de clave pública
para cifrar y descifrar un mensaje m sigue los siguientes pasos:
El usuario B desea enviar un mensaje cifrado al usuario A, para lo que obtiene su clave pública, e.
B cifra el mensaje m que quiere transmitir haciendo uso de esta clave pública: Ce(m) = c.
B envía a A el mensaje cifrado: c.
427. Este problema se resuelve en la práctica con un protocolo de certificado de clave pública
que se basa en la capacidad de firma disponible en los criptosistemas de clave pública y
en la autoridad de un «Tercero de Confianza» (en inglés, Trusted Third Party, TTP).
Pueden verse más detalles, por ejemplo, en [Menezes et al., 1997].
428. El gran desarrollo de la criptografía ha hecho que ésta no se limite únicamente a los
procesos de cifrado y descifrado de datos. Hoy en día, no puede entenderse esta ciencia
sin una nueva componente como es «Autenticación» o «Autentificación». En la mayoría
de las comunicaciones (ya sean electrónicas o no) es imprescindible la garantía de que
quien dice ser el remitente de una información sea realmente quien dice serlo. Esta
necesidad queda garantizada mediante los procesos de autenticación que proporciona la
criptografía de clave asimétrica, a través de los procedimientos de firma digital.
429. Por otra parte, mediante el uso de determinadas herramientas criptográficas, es posible
elaborar esquemas y protocolos que permitan algunas de las actuales aplicaciones a través
de Internet y comunicación con o sin cable, como son el pago con dinero electrónico,
votaciones en redes de ordenadores, demostrar que se posee determinada información sin
revelar parte alguna de la misma, distribuir un secreto entre varias personas de modo que
sea necesario que varias de estas personas se pongan de acuerdo para recuperar dicho
secreto, etc.
3. CRIPTOSISTEMA RSA
433. El criptosistema RSA fue introducido por Rivest, Shamir y Adleman en [Rivest et al.,
1978] (ver también [Durán et al., 2005], [Menezes et al., 1997]) y actualmente es el
criptosistema de clave pública más conocido y más ampliamente usado. La seguridad de
este criptosistema se basa en la dificultad que supone resolver el «Problema de la
Factorización Entera» (en inglés, Integer Factorization Problem, IFP). Dicho problema
puede plantearse en los siguientes términos: dado un número entero compuesto (no
primo), determinar los factores primos que lo dividen, es decir, calcular su factorización
como producto de números primos elevados a potencias.
434. Como todo criptosistema de clave pública, el protocolo del criptosistema RSA tiene tres
partes:
Generación de claves,
Cifrado de mensajes,
Descifrado de mensajes.
436. Los valores de p, q y φ(n) también deben mantenerse en secreto, aunque no forman parte
propiamente de la clave privada.
437. Los exponentes e y d reciben el nombre de «exponente de cifrado» y «exponente de
descifrado», respectivamente, y n recibe el nombre de «módulo» del criptosistema. Un
«mensaje en claro» es un número entero comprendido entre 1 y n, o equivalemente, es un
entero módulo n.
(2)
La palabra «grandes» debe entenderse en el sentido de que en cada momento los métodos de factorización no
permitan factorizar el producto p·q (véase la sección 3.4 de este Anexo C para más detalles). En la actualidad, se
recomienda que los primos p y q tengan alrededor de 512 bits cada uno.
m = cd (mod n).
3.4. SEGURIDAD
442. Los ataques a la seguridad se dividen en las siguientes categorías: relativos a la
factorización del módulo, exponentes de cifrado pequeños, exponentes de descifrado
pequeños, ataques cíclicos y sus generalizaciones, y mensajes inocultables.
443. ATAQUES RELATIVOS A LA FACTORIZACIÓN DEL MÓDULO. El primer ataque
contra el criptosistema RSA consiste en tratar de factorizar el módulo n del criptosistema.
Este tipo de ataque ha dado lugar a un gran número de publicaciones.
444. El Teorema Fundamental de la Aritmética establece que todo número entero puede
factorizarse como producto de números primos, cada uno con una cierta multiplicidad, y
que los factores primos y sus multiplicidades son únicos.
445. Ahora bien, obtener la factorización de un número entero es computacionalmente difícil
en general si el tamaño del número es grande.
446. Los mejores algoritmos para resolver el problema de la factorización de números enteros
tienen un tiempo de ejecución subexponencial; véanse por ejemplo: [Bach and Shallit,
1996], [Boneh, 1999], [Buhler et al., 1993], [Kleinjung et al., 2010], [Lenstra, 1993],
[Lenstra et al., 1993], [Pollard, 1974], [Sarkar and Maitra, 2009a].
447. Por tanto, este problema se considera muy difícil computacionalmente en la actualidad;
pero existen ciertas clases especiales de números enteros que sí pueden factorizarse
eficientemente por medio de algoritmos específicos; véanse, por ejemplo, los artículos
[Pollard, 1974] y [Williams, 1982].
451. Las dos primeras propiedades previenen de los ataques basados en los algoritmos de
Pollard ([Pollard, 1974]) y Williams ([Williams, 1982]), mientras que la tercera está
destinada a evitar los ataques cíclicos, que se describirán más adelante.
452. ATAQUES A EXPONENTES DE CIFRADO PEQUEÑOS. En general, para facilitar y
hacer más eficiente el proceso de cifrado del criptosistema RSA se eligen exponentes e de
cifrado pequeños. Pero bajo ciertas circunstancias esta práctica puede comprometer
potencialmente la seguridad del sistema. El problema surge cuando se envían e mensajes
cifrados del mismo mensaje en claro m con el mismo exponente de cifrado e (pequeño) a
usuarios cuyos módulos ni son primos entre sí dos a dos, o sea, mcd(ni, nj) = 1 para i < j,
pues en este caso, el algoritmo de Gauss (véase la sección 2.121 de [Menezes et al.,
1997]; véanse también [Hastad, 1988] y [Coppersmith et al., 1996]) permite recuperar el
mensaje m.
453. Este ataque permite obtener de nuevo el texto en claro bajo ciertas circunstancias, como
hemos explicado, pero no compromete la seguridad global del sistema, ya que no permite
averiguar el exponente de descifrado d de ningún usuario ni factorizar su módulo.
454. ATAQUES A EXPONENTES DE DESCIFRADO PEQUEÑOS. Estos ataques explotan
el hecho de que el tamaño de d sea menor que una cierta cota superior que depende del
ataque considerado, lo cual supone una debilidad del sistema.
455. Los más importantes son los siguientes:
456. El ataque de la fracción continua de Wiener, desarrollado en [Wiener, 1990]. Usando el
desarrollo en fracción continua de e/n, Wiener diseñó un algoritmo que permite recuperar
la clave privada si ésta verifica: d < n0.25 ; esto es, si el número de bits de d es inferior a
la cuarta parte del número de bits de n. Además, en este caso, el algoritmo que calcula d
se ejecuta en tiempo polinómico.
457. Extensiones y refinamientos de este resultado pueden consultarse en [Verheul and van
Tilborg, 1997], [Chen et al., 2004], [Bleichenbacher and May, 2006], [Jochemsz and
May, 2007], [Djuella, 2009] y [Luo et al., 2009].
458. El ataque de Boneh y Durfee desarrollado en [Boneh and Durfee, 1999], [Boneh and
Durfee, 2000], [Durfee and Nguyen, 2000] (véase también [Boneh, 1999]), que se basa
en el «Algoritmo de Lenstra-Lenstra-Lovász» (en inglés LLL Algorithm o L3 Algorithm)
y permite calcular d eficientemente siempre y cuando d < n0.292, lo cual mejora el
resultado de Wiener.
459. El ataque de Blömer y May ha sido desarrollado básicamente en [Blömer and May,
2001], [May, 2002] y [Maitra and Sarkar, 2008]. Este ataque es un refinamiento muy
técnico del de Boneh-Durfee.
460. Recientemente, se han efectuado algunos ataques al criptosistema RSA suponiendo que
se conocen, o bien los bits más significativos o bien los menos significativos de la clave
privada d; véanse [Sarkar and Maitra, 2009a], [Sarkar and Maitra, 2009b]. Otros ataques
suponen la existencia de dos exponentes de descifrado (por ejemplo, [Sarkar and Maitra,
2010]). Estos ataques pueden ser interesantes bajo ciertas circunstancias particulares,
pero no son de propósito general.
461. En resumen: todos los ataques anteriores consiguen recuperar la clave privada d a partir
de la clave pública (n, e) exclusivamente, suponiendo que el tamaño de d sea
suficientemente pequeño. Por tanto, en tales ataques la seguridad del criptosistema queda
completamente comprometida.
462. Sin embargo, todos estos ataques pueden evitarse tomando d suficientemente grande,
según indique la cota superior para d de cada uno de los ataques mencionados.
463. ATAQUES CÍCLICOS Y SUS GENERALIZACIONES. Si c = me (mod n) es un texto
cifrado, entonces se demuestra que existe un cierto entero k tal que verifica:
464. ce^k = c (mod n)(3).
465. Pueden consultarse [Cohen, 1993], [Menezes et al., 1997], [Gysin and Seberry, 1999]. En
este caso, se tiene:
466. ce^(k–1) = m (mod n).
467. Por tanto, si se conoce k se puede recuperar el mensaje en claro m.
468. Los ataques cíclicos permiten recuperar el texto en claro, pero no rompen el
criptosistema. Ahora bien, los ataques cíclicos generalizados sí pueden comprometer la
seguridad del criptosistema RSA, aunque, dada la dificultad de la factorización de
números enteros, no suponen una amenaza real, siempre y cuando los factores p y q se
elijan cumpliendo las recomendaciones explicadas.
469. MENSAJES INOCULTABLES. Este ataque tiene éxito siempre y cuando la potencia e-
ésima del texto en claro coincida con el propio texto en claro, lo cual puede formularse
con precisión como sigue: un mensaje m (0 < m < n) se dice que es «inocultable» si se
verifica: me = m (mod n). Véase [Blakley and Borosh, 1979], [Menezes et al., 1997],
[Chmielowiec, 2010].
(3)
La expresión e^k representa la potencia k-ésima del número entero e, es decir, e^k = ek.
470. Siempre hay por lo menos 9 mensajes inocultables pero su número es muy pequeño.
Tales mensajes no pueden ser cifrados. Por otra parte, existen ejemplos de módulos RSA
para los cuales todos los mensajes son inocultables. Un ejemplo famoso es el siguiente:
p = 97, q = 109, n = 10573, e = 865, d = 9505.
471. Este ataque se aplica sólo a valores excepcionales del módulo n; si p y q se toman de
modo aleatorio y, además, e y φ(n) son primos entre sí (es decir, mcd(e, φ(n)) = 1),
entonces la probabilidad de hallar un mensaje inocultable es menor que K(ln n)2/n,
siendo K una constante.
3.5. COMENTARIOS
472. En las implementaciones actuales del criptosistema RSA en tarjetas inteligentes, se usa el
«Teorema Chino del Resto» (en inglés, Chinese Remainder Theorem, CRT; véase [Bach
and Shallit, 1996] o [Menezes et al., 1997]) para que los cálculos sean más rápidos,
especialmente el proceso de descifrado; véanse [Quisquater and Couvreur, 1982], [Boneh
and Shacham, 2002], [Sun and Wu, 2005], [Sun et al., 2005], [Okeya and Takagi, 2006]).
473. En esta situación, el criptosistema RSA recibe el nombre de RSA-CRT.
474. Los procesos de cifrado y descifrado en este sistema modificado son distintos de los
correspondientes procesos en el sistema RSA estándar. En RSA-CRT,
Cada usuario A genera dos primos «grandes» p y q, y calcula los productos n = p·q, φ(n) = (p–
1)(q–1), como antes.
Después, toma dos enteros aleatorios dp, dq que verifiquen las siguientes propiedades:
El máximo común divisor de dp y p–1 es la unidad, es decir, mcd(dp, p–1) = 1.
Análogamente, el máximo común divisor de dq y q–1 es la unidad, o sea, mcd(dq, q–1) = 1.
Los enteros dp y dq tienen la misma paridad, es decir, dp = dq (mod 2).
Usando el Teorema Chino del Resto se determina un entero d que tiene el mismo resto que dp al
ser dividido por p–1 y el mismo resto que dq al ser dividido por q–1, esto es, d = dp (mod p–1) y
d = dq (mod q–1), y se calcula el inverso e de d módulo φ(n); es decir: e·d = 1 (mod φ(n)).
476. Recientemente (por ejemplo, véase [Hinek, 2008]), se ha propuesto también una
generalización del criptosistema RSA estándar, llamada «RSA multi-primo», en la cual el
módulo del sistema contiene más de dos factores primos. Cifrando y descifrando módulo
cada factor primo del módulo y usando el Teorema Chino del Resto en el criptosistema
RSA multi-primo, el coste computacional de estos procesos se reduce considerablemente.
477. Existen también ataques al exponente de descifrado pequeño para el criptosistema RSA-
CRT (pueden verse [Bleichenbacher and May, 2006], [Jochemsz and May, 2007]) y
ataques al criptosistema multi-primo ([Hinek, 2008], [Sarkar and Maitra, 2009b], [Sarkar
and Maitra, 2010]).
(4)
Las expresiones d_p y d_q denotan subíndices, es decir, d_p = dp y d_q = dq.
478. El mínimo común múltiplo de p–1 y q–1 recibe el nombre de «función lambda de
Charmichael» y se designa por λ(n) = mcm(p–1, q–1) . El entero λ(n) puede ser usado en
vez del indicador de Euler φ(n). Tiene la ventaja de poseer, en principio, un exponente de
descifrado d de tamaño menor, lo cual redunda en la rapidez del proceso de descifrado.
Ahora bien, si p y q se eligen «realmente» de modo aleatorio, entonces el máximo común
divisor de los enteros p–1 y q–1 es pequeño, de modo que λ(n) y φ(n) tienen un tamaño
muy parecido.
4. CUADRO RESUMEN
Cuadro C.1. Resumen de longitudes de claves del criptosistema RSA para el ENS
Cifrado simétrico: Nivel Bajo Nivel Medio Nivel Alto
RSA
2.5. Protección de la Permitido Permitido
No se aplica
confidencialidad Claves ≥ 2048 bits Claves ≥ 2048 bits
2.6. Protección de la
Permitido Permitido
autenticidad y de la No se aplica
Claves ≥ 2048 bits Claves ≥ 2048 bits
integridad
2.7. Cifrado de la Permitido
No se aplica No se aplica
información Claves ≥ 2048 bits
2.8. Protección de
Permitido Permitido Permitido
las claves
Claves ≥ 2048 bits Claves ≥ 2048 bits Claves ≥ 2048 bits
criptográficas
5. CRIPTOSISTEMA DE ELGAMAL
480. El Criptosistema de Taher ElGamal fue publicado en 1985 y es de gran relevancia hoy en
día ([ElGamal, 1985], [Fúster et al., 2004], [Menezes et al., 1997]). Por sí mismo, este
criptosistema no ha sido muy utilizado en implementaciones prácticas pero es importante
por cuanto es la base sobre la que se fundamenta uno de los criptosistemas más
prometedores: el basado en determinada clase de curvas elípticas.
481. La seguridad de criptosistema de ElGamal estriba en la dificultad computacional que
supone resolver el problema del logaritmo discreto, uno de los problemas matemáticos
cuya resolución requiere tiempos de computación muy elevados (conocidos como tiempo
exponencial o subexponencial, ver la sección A.3 de [Durán et al., 2005]) que son
considerados como problemas muy difíciles, de forma análoga a como lo es el problema
de la factorización de números enteros, utilizado con el criptosistema RSA.
482. El Problema del Logaritmo Discreto (DLP), en su forma más sencilla (ver la sección 3.6
de [Menezes et al., 1997] para una descripción más completa de este problema y su
expresión en grupos matemáticos concretos), consiste en calcular el logaritmo de un
número en una base dada pero en un conjunto finito de números (de ahí lo de discreto),
logg L = x.
483. Dicho de otro modo, se trata de determinar el exponente, x, al que hay que elevar una
base dada, g, para que dicha potencia proporcione otro número conocido de antemano, L:
gx = L. Definido de esta manera, el problema podría parecer sencillo, pero el conjunto
finito de números se elige de tal forma que calcular tal potencia requiere un tiempo de
computación, al menos, subexponencial.
484. A modo de ejemplo se considera el conjunto de los posibles restos de la división entre 23,
salvo el 0, denotado por Z23* = {1, 2, …, 21, 22}. La operación que se utiliza entre dos
números dados del conjunto, a y b, es la de su producto módulo 23, que se representa
como a·b (mod 23). Como ya se sabe, esta operación consiste en multiplicar los dos
números dados y luego tomar como resultado el resto de la división entera de tal producto
entre 23. Así, si se consideran los números 13 y 17, por ejemplo, se tiene que
485. 13·17 (mod 7) = 221 (mod 23) = (23·9+14) (mod 23) = 14,
486. dado que 14 es el resto de la división entera de 221 entre 23. La ventaja de esta operación
estriba en que al multiplicar dos números cualesquiera del conjunto, el resultado es
siempre otro número del mismo conjunto.
487. En este ejemplo, se verifica, además, que todos los elementos de dicho conjunto se
pueden obtener como potencias de uno de ellos, llamado generador. Así, se verifica que
un generador de Z23* es el número 5. En efecto, se tiene que todas las potencias de 5
módulo 23 recorren en conjunto completo:
488. 51 (mod 23) = 5, 52 (mod 23) = 2, 53 (mod 23) = 10, …, 522 (mod 23) = 1.
489. En esta situación, un problema particular de logaritmo discreto se puede plantear como
sigue: resolver el siguiente logaritmo: x = log5 21. Se trata de calcular el valor de x de
modo que se verifique: 5x = 21 (mod 23). En este caso, debido a la magnitud de los
números implicados, es inmediato que x = 13, por tanto, se puede afirmar que log5
21 = 13 en Z23*.
490. No obstante, la dificultad del DLP se pone de manifiesto cuando los números que se
emplean en lugar de ser de una o dos cifras, son de 300 ó 400 cifras.
491. Volviendo al criptosistema de ElGamal, como en todo sistema de clave pública, se tienen
tres fases:
Generación de claves,
Cifrado de mensajes,
Descifrado de mensajes.
de tal manera que todos los elementos de Zp* se pueden obtener como potencias de
elemento g, es decir,
493. En este caso, la mínima longitud recomendada de la clave pública, esto es, de p, es de
1024 bits; la misma longitud que la recomendada para el RSA. No obstante, debe
recordarse que para el criptosistema de ElGamal, p es un único primo mientras que para
el criptosistema RSA, n era el producto de dos primos, cada uno de ellos de longitud la
mitad.
496. En efecto, el producto anterior permite obtener m dado que se tiene lo siguiente:
5.4. SEGURIDAD
497. Un atacante al sistema o criptoanalista, C, podría conocer las claves públicas de A y de B,
es decir, podría conocer el conjunto de números que se emplea, Zp*, y los valores de p, g,
ga y gb, dado que todos estos valores son públicos.
498. Por otra parte, C podría haber interceptado la comunicación entre A y B y conocer los
valores de u y de v.
499. Para romper el criptosistema, es decir, para determinar cualquiera de las claves privadas
de los usuarios A o B, a o b, o para determinar el valor del parámetro secreto x que
permitió cifrar el mensaje, tendría que resolver un caso del problema del logaritmo
discreto, es decir, calcular a, b o x a partir de ga, gb o u = gx, lo que hoy por hoy, es un
problema computacionalmente inabordable, con los tamaños recomendados para las
claves.
500. Por esta razón, se dice que la seguridad del criptosistema de ElGamal es equivalente a la
del logaritmo discreto.
501. Los algoritmos que calculan logaritmos discretos, logg L = x, es decir, que determinan el
valor de x de modo que gx = L, se pueden clasificar de la siguiente manera. Los
algoritmos que trabajan en grupos arbitrarios, como la búsqueda exhaustiva o fuerza
bruta, el paso gigante-paso enano y el algoritmo rho de Pollard. Existen algoritmos que
funcionan en grupos arbitrarios pero que son especialmente eficientes si el tamaño
(orden) del grupo tiene factores o divisores pequeños, como por ejemplo, el algoritmo de
Pohlig-Hellman, y por último, los algoritmos de cálculo del índice, que solo son
eficientes en determinados grupos especiales (ver la sección 3.6 de [Menezes et al.,
1997]).
502. BÚSQUEDA EXHAUSTIVA O FUERZA BRUTA. El algoritmo más elemental para
determinar logaritmos discretos consiste en calcular las sucesivas potencias del generador
del grupo considerado hasta obtener el valor que se busca. Sin embargo, este algoritmo
requiere un tiempo de computación excesivamente elevado (de hecho el tiempo es
exponencial), por lo que es ineficiente si el tamaño del conjunto (grupo) considerado es
elevado, como sucede en los casos de interés en criptografía.
503. PASO GIGANTE-PASO ENANO. Este algoritmo es una mejora de la búsqueda
exhaustiva. Consiste en calcular una lista de los pares formados por un índice, i, y la
potencia del generador, g, elevada a dicho índice, gi, donde el índice recorre los valores
de 1 hasta en número entero más cercano por defecto a la raíz cuadrada del orden n del
grupo con el que se está trabajando, sea m = √n. Una vez determinada la lista, se ordena
por la segunda componente del par. Luego se determinan los productos de los inversos de
estas segundas componentes, ya ordenadas, por el valor dado, L, cuyo logaritmo se busca,
x = logg L, es decir, se determinan L·g–m·j, j = 1, …, m–1. Finalmente, se compara cada
uno de estos valores calculados con las segundas componentes de la lista original
ordenada. Si se encuentra una coincidencia, por ejemplo, L·g–m·j = gi, resulta que
despejando de la igualdad obtenida es: L = gi+m·j, de donde se tiene el logaritmo
buscado:
504. x = logg L = log gi+m·j = i+m·j.
505. Sin embargo, este algoritmo tampoco es eficiente dado que calcular las entradas de la
tabla, ordenar la tabla y hacer la comparación requiere de un tiempo también exponencial.
506. Una actualización muy reciente de este algoritmo se debe a Cheon ([Cheon, 2010]). La
modificación rebaja los tiempos de computación del logaritmo discreto cuando se trabaja
sobre un grupo de orden primo p, de modo que además de los valores g y ga, se conocen
otras entradas auxiliares (ga)i, para valores i = 1, …, d, siendo d un divisor de p–1.
507. ALGORITMO RHO DE POLLARD. Este algoritmo es aleatorio y requiere el mismo
tiempo de computación que el del paso gigante-paso enano. Sin embargo, es más
eficiente porque necesita menores recursos de memoria. Por tal motivo es preferible al
anterior.
508. ALGORITMO DE POHLIG-HELLMAN. Este algoritmo es especialmente eficiente en
grupos para los que se conoce la factorización de su orden y ésta tiene factores o
divisores pequeños ([Pohlig and Hellman, 1978]). En este caso, se tiene en cuenta y se
explota el hecho de que se conozca la factorización del orden del grupo sobre el que se
trabaja. Así, se resuelve el problema del logaritmo discreto planteado para cada uno de
los factores que dividen al orden y luego las soluciones particulares se unen haciendo uso
del algoritmo de Gauss, que proporciona una solución al Teorema Chino del Resto, ya
comentado (ver la sección 2.4.3 de [Menezes et al., 1997]).
509. ALGORITMO DE CÁLCULO DEL ÍNDICE. Este algoritmo es uno de los mejores para
calcular logaritmos discretos, si bien su tiempo de computación es subexponencial. El
algoritmo precisa de la selección de un subconjunto relativamente pequeño de elementos
del grupo considerado (llamado base de factores), de modo que una significativa parte de
los elementos del grupo puedan expresarse de forma eficiente como producto de
elementos de la base de factores.
E: y2+a1·x·y+a3·y = x3+a2·x2+a4·x+a6,
de modo que los valores de los números a1, a3, a2, a4 y a6 verifican determinadas
condiciones y pertenecen a un conjunto de llamado «cuerpo finito» (ver [Menezes et al.,
1993a]). Un ejemplo de cuerpo finito es el conjunto de los restos de la división entera
entre un número primo p, con las operaciones de suma y producto cuyo orden es p:
(1, 3), (1, 20), (2, 2), (2, 21), (4, 6), (4, 17), …, (21, 10), (21, 13).
519. Como se puede ver, todos ellos verifican la ecuación que define a la curva considerando
la operación definida en el conjunto F23, que consiste en multiplicar los números y luego
tomar como resultado el resto de la división del producto hallado entre 23:
32 = 9 (mod 23),
22 = 4 (mod 23),
x3 = z2–x1–x2,
y3 = z·(x1–x3)–y1,
donde
z = (x12+a)/(2·y1), si P = Q,
z = (y2–y1)/(x2–x1), si P ≠ Q.
522. Por ejemplo, la suma de los puntos cuyas coordenadas son P = (6, 16) y Q = (15, 8) de la
curva elíptica anterior es el punto R = (15, 15) (ver Figura D.2).
523. En efecto, como P = (6, 16) ≠ Q = (15, 8), resulta que, modulo 23, es
528. Con el fin de considerar una de las situaciones más sencillas, se supondrá que el grupo de
puntos de la curva elíptica E es cíclico, es decir, que posee un generador, G, y que tiene
orden primo (si no fuera así, se elegiría un subgrupo cíclico de la curva generado por un
punto con un orden primo, cercano al orden de la curva).
529. Dos usuarios A y B que quieran intercambiar una información común mediante el
ECDHKA proceden como sigue:
Seleccionan públicamente una curva elíptica E sobre un cuerpo finito de q elementos Fq y eligen
un elemento G de E que genere un subgrupo de orden primo suficientemente grande (en la
práctica, se supone que G genera la propia curva E).
El usuario A (respectivamente B) genera un número entero aleatorio a (resp. b), calcula el punto de
la curva dado por a·G (resp. b·G) en E y envía el resultado a B (resp. A).
A recibe b·G y calcula a·(b·G) = a·b·G. Análogamente, B recibe a·G y calcula b·(a·G) = b·a·G.
Por tanto, A y B poseen un punto en común de la curva elíptica: a·b·G = b·a·G, que es secreto, y
puede ser usado como clave secreta compartida por A y B.
532. En el Cuadro D.1 se presentan las longitudes en bits de las claves que proporcionan
seguridades equivalentes para los diferentes criptosistemas ([Hankerson et al., 2005],
[NIST, SP800-57]).
533. De forma análoga a otros criptosistemas de clave pública, los ECC constan de tres fases:
Generación de claves,
Cifrado de mensajes,
Descifrado de mensajes.
Q = M+x·(a·G),
6.7. SEGURIDAD
539. Dado que el problema matemático sobre el que se fundamentan los ECC es el logaritmo
discreto sobre curvas elípticas, los mejores ataques contra este tipo de criptosistemas son
los mismos que los ya presentados para el caso del criptosistema de ElGamal en la
sección 1.4 de este Anexo D. Sin embargo, existen otros ataques que son específicos de
las curvas elípticas, dado que éstas pueden elegirse sin las suficientes condiciones de
seguridad.
540. A continuación se presentan los principales ataques contra los ECC.
541. ATAQUE POR FUERZA BRUTA. Este ataque contra el ECDLP consiste en probar
todos los posibles valores de un entero k hasta que se obtenga la solución buscada k = a,
es decir, hasta obtener el valor conocido de a·G, lo que permitiría conocer la clave
privada del usuario al que se ataca. Este ataque puede evitarse si los parámetros del
criptosistema se eligen con los tamaños recomendados para las claves, según los
diferentes niveles de seguridad requeridos, de modo que el tiempo de computación
necesario sea lo suficientemente elevado.
542. ATAQUE DE POHLIG-HELLMAN ([Pohlig and Hellman, 1978]). El ataque trata de
resolver el ECDLP en subgrupos de orden primo pequeño del grupo original, de modo
que las soluciones parciales pueden ser luego complementadas mediante el Teorema
Chino del Resto para obtener la solución global. Con el fin de evitar este ataque, se
recomienda que el orden de la curva elíptica definida sobre el cuerpo finito, #E, tenga un
divisor primo grande, por ejemplo p, de modo que éste sea mayor que el máximo entre
2160 y 22·s–1, donde s es el nivel de seguridad deseado, en bits, es decir, uno de los
siguientes valores: 80, 112, 128, 192, 256, etc. Dicho de otro modo, si se cumple que
p > max{2160, 22·s–1}, donde s ∈ {80, 112, 128, 192, 256, …}.
543. ATAQUE DE FREY Y RÜCK ([Frey y Rück, 1994]). Este ataque generaliza el ataque de
Menezes, Okamoto y Vanstone ([Menezes et al., 1993b]) generalmente conocido como
ATAQUE MOV. El ataque reduce el ECDLP definido sobre una curva elíptica a un DLP
sobre conjuntos donde este problema es algo más sencillo de resolver. Ambos ataques
pueden ser evitados si la curva elítpica se define sobre el cuerpo Fq, de modo que se
verifique la siguiente condición: qi ≠ 1 (mod n), para todo i, con 1 ≤ i ≤ 100.
544. ATAQUES A CURVAS ANÓMALAS. Se dice que una curva elíptica definida sobre un
cuerpo finito Fq es «anómala» si se cumple que el orden de la curva verifica #E = q.
Semaev ([Semaev, 1998]), Smart ([Smart, 1999]) y Satoh y Araki ([Satoh and Araki,
1998]) mostraron que el ECDLP en curvas anómalas se puede resolver de modo eficiente.
Por tal motivo, dichas curvas deben ser evitadas. Los ataques a curvas anómalas se puede
prevenir si se comprueba que se verifica lo siguiente:
#E ≠ q.
545. Exiten otros ataques más sofisticados que los presentados anteriormente y que requieren
de conceptos matemáticos más complejos, por lo que remitimos al lector interesado a las
siguientes referencias: [Frey, 2001], [Gaudry et al., 2002], [Jacobson et al., 2001],
[Maurer et al., 2002] y [Menezes and Qu, 2001].
7. CUADRO RESUMEN
Cuadro D.2. Resumen de longitudes de claves de criptosistemas basados en curvas
elípticas para el ENS
Cifrado simétrico: Nivel Bajo Nivel Medio Nivel Alto
ECC
2.5. Protección de la Permitido Permitido
No se aplica
confidencialidad Claves: 224-255 bits Claves: ≥ 256 bits
2.6. Protección de la
Permitido Permitido
autenticidad y de la No se aplica
Claves: 224-255 bits Claves: ≥ 256 bits
integridad
2.7. Cifrado de la Permitido
No se aplica No se aplica
información Claves: ≥ 256 bits
2.8. Protección de
Permitido Permitido Permitido
las claves
Claves: 224-255 bits Claves: 224-255 bits Claves: ≥ 256 bits
criptográficas
1. FUNCIONES RESUMEN
546. En general, los protocolos que calculan la firma electrónica de un documento electrónico
son bastante lentos, tanto en software como en hardware. Con el fin de ahorrar tiempo de
computación, lo que se suele hacer es firmar una especie de resumen del documento en
lugar de firmar el documento completo. La ventaja de este procedimiento es que el
resumen del documento se limita a unos cientos de bits, sin importar cómo de grande sea
el documento original.
547. Para calcular esta especie de resumen del documento se utiliza un tipo especial de
función, denominada «Función Resumen» (en inglés, Hash Function). Para más
información sobre este tipo de funciones, véase [Fúster et al., 2004], [Katz and Lindell,
2008], [Menezes et al., 1997], [Stinson, 2006].
548. Una función resumen, por ejemplo, h, puede definirse como una función que asocia a
cualquier documento electrónico de cualquier tamaño, m, un resumen suyo, m, de
longitud fija, es decir, h(m) = m. Así, si los resúmenes que proporciona una función
resumen determinada son, por ejemplo, de 256 bits, resulta que para cualquier documento
o mensaje, sin importar su tamaño, siempre proporcionará resúmenes de 256 bits.
549. Sin embargo, no sirve cualquier función, las funciones resumen para ser utilizadas en los
protocolos criptográficos y de firma electrónica han de cumplir determinadas
condiciones.
550. En primer lugar, han de ser fácilmente computables, es decir, el cálculo del resumen de
un documento dado debe requerir muy poco tiempo de computación. Además, las
funciones resumen deben conocerse públicamente.
551. Por otra parte, si los resúmenes de los documentos para una determinada función resumen
tienen siempre una longitud fija, para cualquier longitud de los documentos, se deduce
que el número de posibles resúmenes es mucho menor que el de posibles documentos.
Dicho de otra manera, el número de mensajes de cualquier longitud es infinito, mientras
que el número de resúmenes de mensajes diferentes de, por ejemplo, 256 bits, es «sólo»
de 2256.
552. Además, como una de las principales aplicaciones de las funciones resumen es para la
firma electrónica de documentos, otra propiedad que deben cumplir estas funciones es
que no debe ser fácil encontrar dos documentos diferentes cuyo resumen sea el mismo,
porque en ese caso habría discrepancias acerca de cuál de los dos documentos es el que se
ha utilizado. Por todo ello, las funciones resumen deben cumplir las siguientes
propiedades:
Dependencia de bits: el resumen de un mensaje o documento, h(m) = m, debe ser una función
compleja dependiente de todos los bits del mensaje, de tal manera que si se modifica un único bit
del mensaje, su resumen debería cambiar, aproximadamente, la mitad de sus bits.
Resistencia a la preimagen: dado un resumen m, debe ser computacionalmente difícil obtener un
documento m de modo que h(m) = m.
Resistencia a la segunda preimagen: dado un documento m1, debe ser computacionalmente difícil
encontrar otro documento m2 diferente del anterior, m1 ≠ m2, de modo que ambos tengan el mismo
resumen, m, es decir, tales que h(m1) = h(m2) = m.
Resistencia a colisiones: debe ser computacionalmente difícil encontrar dos mensajes distintos
cualesquiera m1, m2, m1 ≠ m2, de modo que h(m1) = h(m2) = m.
553. Las propiedades C y D anteriores pueden parecer la misma, pero no lo son en absoluto.
Debe notarse que la propiedad D es menos restrictiva que la C. En efecto, en la propiedad
C se supone que el documento m1 es conocido y debe encontrarse otro documento m2
con la condición señalada; mientras que en la propiedad D no hay condiciones previas
sobre ninguno de los dos documentos, de hecho, ni siquiera tendrían por qué tener
sentido, gramaticalmente hablando.
554. Si no se cumplieran las propiedades anteriores, las funciones resumen serían vulnerables,
es decir, podrían ser rotas por el ataque conocido como de la «Paradoja del cumpleaños».
Esta paradoja procede de un problema matemático que puede plantearse en los siguientes
términos: «Si un año tiene n = 365 días, ¿cuántas personas debe haber en una sala para
que la probabilidad de que dos de ellas celebren su cumpleaños el mismo día sea mayor
del 50%?» Otra forma de plantearla sería la siguiente: «Determinar la confianza (es decir,
que la probabilidad sea mayor de 0,5) de que en una sala con k personas, dos de ellas
celebren su cumpleaños el mismo día».
555. La solución a este problema es sorprendente (de ahí el nombre de paradoja). En efecto,
basta con que haya k = 23 personas en una sala para tal probabilidad sea mayor de ½. De
hecho la probabilidad para 23 personas es 0,5072972343. Debe tenerse en cuenta que el
enunciado del problema anterior no especifica qué día concreto debe celebrarse el
cumpleaños, sólo exige que se celebre el mismo día, esto es, uno cualquiera de los 365
días del año.
556. La paradoja anterior se traduce para las funciones resumen equiparando los mensajes con
las personas y los resúmenes con los cumpleaños.
557. En las secciones siguientes se presentan las principales funciones resumen que se utilizan
en la actualidad.
2. MD5
558. La función resumen conocida como MD5 sigue siendo utilizada hoy en día a pesar de que
se han hallado algunas debilidades ([Wang and Yu, 2005]) y su uso no está permitido
para aplicaciones de seguridad. No obstante se ha incluido en esta guía dado que algunos
certificados digitales emitidos por determinadas autoridades de certificación siguen
empleándola. En cualquier caso, debe quedar claro que el uso de esta función no está
permitido en el ENS.
559. La función resumen MD5 fue propuesta por Rivest ([Rivest, 1992]) y proporciona
resúmenes de 128 bits, es decir, dado un mensaje o documento, m, de cualquier longitud,
la función MD5 proporciona un resumen del mismo, MD5(m) = m, de sólo 128 bits.
Debe tenerse en cuenta que la longitud del documento puede ser de 10 bits, 1 Kbits, 100
Gigabits o cualquier otra longitud. En todos los casos, el resumen de cada mensaje
siempre tendrá 128 bits.
560. Las iniciales MD de la función MD5 proceden de los apellidos de los dos primeros
autores que propusieron este tipo de funciones: Merckle ([Merkle, 1990]) y Damgård
([Damgård, 1990]).
561. El esquema general de cómo funciona la función resumen MD5 es el siguiente:
El documento a resumir, m, se expande de modo que su longitud sea múltiplo de 512 bits,
añadiendo, si fuera necesario, bits al final del mismo.
A continuación se seleccionan cuatro vectores, A, B, C y D, cada uno de los cuales tiene 32 bits de
longitud. Una vez que estos cuatro vectores se concatenan, es decir, se colocan uno tras de otro, se
obtiene un vector de 128 bits (32·4 = 128), llamado IV (Vector de Inicialización o en inglés,
Inicialization Vector).
Se considera el primer bloque de 512 bits del documento m y se llevan a cabo diferentes
operaciones lógicas con dicho bloque y con los 128 bits del IV = ABCD. La salida de esta
operación tiene 128 bits (ver [Menezes et al., 1997]).
La salida anterior se considera como un nuevo IV y se hace operar la misma con el segundo bloque
de 512 bits del documento m.
Este proceso se itera hasta agotar el mensaje extendido.
La salida del algoritmo MD5 es el resumen que corresponde a los 128 bits de la última de las
iteraciones anteriores.
2.1. EJEMPLOS
562. A modo de ejemplo, el resumen MD5 del mensaje «Funciones resumen», que tiene sólo
unos pocos bits, es, en hexadecimal, el siguiente:
95c576534dd748c1dae464146aeffd30;
df69635e7a18c7021cf79671088a8902.
3. SHA-1
563. La función resumen SHA-1, cuyo nombre procede de las iniciales Secure Hash
Algorithm (Algoritmo Resumen Seguro) es una función resumen propuesta a raíz de una
modificación de la función MD5. SHA-1 fue adoptada por el National Institute for
Standard and Technology americano (NIST) como función resumen estándar ([NIST,
FIPS180-1]) y proporciona resúmenes de 160 bits. SHA-1 es más segura que MD5,
debido, fundamentalmente, a que sus resúmenes son más largos que los de la función
MD5.
564. SHA-1 es actualmente la función resumen más utilizada, a pesar de que se han
encontrado algunas debilidades. De hecho, se han encontrado colisiones con menos de
269 operaciones, cuando los ataques por fuerza bruta necesitaban de 280 operaciones
([Wang et al., 2005]). En cualquier caso, el número de operaciones necesario para
encontrar colisiones es tan elevado que puede considerarse como una función segura a
corto plazo.
565. El diseño de esta función es muy similar al de la función MD5, si bien se deben tener en
cuenta las siguientes diferencias:
SHA-1 tiene 5 vectores iniciales: A, B, C, D y E, en lugar de los cuatro de MD5. Como cada uno
de ellos sigue siendo de 32 bits, el vector de inicialización IV en este caso tiene 160 bits y así, el
resumen de SHA-1 es de 128+32 = 160 bits.
A cada bloque de 512 bits del documento se le aplican 80 vueltas o iteraciones, mientras que MD5
sólo lleva a cabo 64 vueltas.
3.1. EJEMPLOS
566. Utilizando los mismos documentos que los empleados en el caso de la función MD5, el
resumen SHA-1 del mensaje «Funciones resumen», en hexadecimal, es el siguiente:
38d689b6ca9a19f84029fc2970a5134faa5889d5;
mientras que el resumen SHA-1 del fichero «A-2010-1330.pdf» que contiene el Real
Decreto 3/2010 (50 páginas) tiene la misma longitud que el anterior:
615a5de5a8de7f22c25348ce514817cd4de5bf04.
4. RIPEMD-160
567. La función RIPEMD-160 (Primitivas de Integridad de Resumen de Mensaje, o en inglés,
RACE Integrity Primitives Evaluation Message Digest) es una función resumen que
proporciona un resumen de 160 bits y fue desarrollada en 1996 ([Dobbertin et al., 1996]).
568. Existen versiones de esta función que tienen como salida resúmenes de 128, 256 y 320
bits, llamadas RIPEMD-128, RIPEMD-256 y RIPEMD-320, respectivamente.
569. La versión RIPEMD-160 es una versión mejorada de la primitiva RIPEMD, que estaba
basada en la MD4 función (predecesora de la MD5).
570. Dado que la longitud de su resumen es de 160 bits, su seguridad es similar a la de SHA-1,
si bien su uso está mucho menos extendido, por lo que ha sido menos analizada. De todos
modos, en 2004 se publicaron algunas debilidades para la versión de 128 bits de
RIPEMD que no afectan a las otras versiones ([Wang et al, 2004]).
571. La función de compresión general de RIPEMD-160 aplica entradas de 21 palabras
(variables encadenadas de 5 palabras más 16 bloques del mensaje, con palabras de 32
bits) en salidas 5 palabras. Cada bloque de entrada se procesa en paralelo con versiones
distintas de la función de compresión.
4.1. EJEMPLOS
572. Calculando los resúmenes RIPEMD-160 de los mismos documentos ya empleados en
otros ejemplos, se tiene que el resumen del mensaje «Funciones resumen», en
hexadecimal, es el siguiente:
811ec2c5694c7750b9a2d815fcdc150ebdc2ee91;
70183a62a52e01e9478eac1c47267d67b6e4fc52.
5. SHA-2
573. La función resumen SHA-2 es la sucesora de la SHA-1 y ha sido propuesta después de
conocerse que se pueden encontrar colisiones para la SHA-1 con 263 operaciones
(resultado debido a Shamir, no publicado).
574. El algoritmo de la función resumen SHA-2 contiene los subalgoritmos SHA-224, SHA-
256, SHA-384 y SHA-512, que proporcionan resúmenes de documentos de 224, 256, 384
y 512 bits, respectivamente, lo que aumenta considerablemente la seguridad del algoritmo
([NIST, FIPS180-2]).
575. SHA-256 y SHA-512 se calculan con palabras de 32 y 64 bits, respectivamente. Ambas
usan diferentes constantes y número de rondas, pero su estructura es, básicamente, la
misma.
576. La función SHA-224 se definió para que coincidiera con la longitud de dos claves de
Triple DES (TDES). Ésta función y la SHA-384, son versiones truncadas de las funciones
SHA-256 y SHA-512, respectivamente, además de que se calculan con vectores iniciales
diferentes.
577. SHA-2 no se utiliza en la actualidad tanto como la SHA-1 a pesar de que proporciona una
seguridad mucho mayor. Las razones hay que buscarlas en la falta de compatibilidad con
protocolos, implementaciones y dispositivos ya existentes en el mercado.
578. Conviene destacar que el DNIe incluye dentro de sus protocolos criptográficos para la
firma electrónica de documentos la posibilidad de calcular resúmenes mediante las
funciones SHA-1 y SHA-2, si bien la segunda de ellas no está activada por la razón
apuntada en el párrafo anterior
5.1. EJEMPLOS
579. Las funciones SHA-256, SHA-384 y SHA-512 proporcionan los siguientes resúmenes
(en hexadecimal), respectivamente, del siguiente mensaje: «Funciones resumen»:
SHA-256: 1bae916bd6fd589ceda7fcb9414d1e66
5de44f5316d1363ffd91a204962bd71d,
SHA-384: 53fcb71d121ba6c858fa774b0521f9c8
25c6de6710a4ea3b67eca611eeaad534
2553c8b12ab243d4acb09ec70192604b,
SHA-512: 634ead292f05389b6942f3d2eea5d33c
ffa16e7fbe194e206a56dad8c909fe1c
71400986d417d9a57680de75b24c3463
735bf9f37c67b341bbf780a39871f51a.
SHA-256: 51be21833a1db2a2c5ae018de49ccb03
6cb651cca0a3b30ae6db5d0e191d4c23,
SHA-384: fc5b0a75b8ad3c2c7a8e8b236391a548
e4fa6e45a2d1588fda1f73b8d8903d71
030dd825abcfb532657b44f57f2da9e3,
SHA-512: 1135651068d86010ff10b4a02be8647e
442ce01bef834c695efebc277fa03518
80a2ea8993d04e16c82fa6be7e66c909
be731ee041559238fc17f818334baa38.
6. SHA-3
581. En noviembre de 2007, el NIST anunció formalmente el inicio de una competición
internacional para elegir una nueva función resumen, para ser considerada como estándar
y que será llamada función resumen SHA-3 ([NIST, SHA-3]). La presentación de
funciones candidatas se terminó el 31 de octubre de 2008 y se espera que la función
ganadora se dé a conocer en 2012.
582. El NIST recibió 64 propuestas iniciales de funciones candidatas a ser SHA-3. Después de
una primera revisión, se seleccionaron las 51 que cumplían los requisitos solicitados en la
convocatoria original. Las 51 candidatas forman la lista de funciones que se ha dado en
llamar la Ronda 1.
583. En Febrero de 2009, el NIST celebró el congreso «First SHA-3 Candidate Conference»
en la Universidad Católica de Lovaina (Bélgica) para que los autores de las 51 funciones
candidatas admitidas en la Ronda 1 presentaran y defendieran sus algoritmos. Después de
este congreso, el NIST ha recibido comentarios a los algoritmos propuestos y ha
elaborado una segunda lista de funciones candidatas que son las que forman la llamada
Ronda 2. La lista de las 14 funciones candidatas a convertirse en la nueva SHA-3, que
configuran la Ronda 2, son las listadas en el Cuadro E.1.
584. La competición continuó con la celebración del «Second SHA-3 Candidate Conference»
en la Universidad de Los Ángeles en Santa Barbara (California, USA) durante los días 23
y 24 de Agosto de 2010. Los resultados de esta conferencia se han publicado el 9 de
diciembre de 2010 y han dado como resultado una lista de 5 algoritmos, que son los que
constituyen la Ronda final, de entre los que saldrá el futuro SHA-3. La lista de los 5
candidatos finales es: BLAKE, Grøstl, JH, Keccak y Skein.
7. HMAC
585. Los sistemas de cifrado de documentos y mensajes garantizan la confidencialidad de los
mismos, es decir, que su contenido se mantiene en secreto. Sin embargo, no aseguran que
tales documentos sean auténticos. Para garantizar esta propiedad, es necesarios hacer uso
de los llamados «Códigos de Autenticación de Mensajes» (en inglés, Authentication
Message Code, MAC).
586. En general, un MAC (ver [Menezes et al., 1997]) se calcula a partir de la última parte del
criptograma de un mensaje cuando el tipo de sistema de cifrado utilizado tenga la
propiedad de que todos los bits cifrados sean función de todos los bits del mensaje
original. Por ejemplo, en los cifradores en bloque de tipo TDES, el MAC de un mensaje
podría ser el último bloque de 64 bits del criptograma ([Katz and Lindell, 2008], [Stinson,
2006]).
587. Un tipo especial de códigos de autenticación de mensajes se obtiene cuando se considera,
además, una función resumen. En este caso se habla de «Código de Autenticación de
Mensaje con Resumen» (en inglés, Hash Message Authentication Code, HMAC). En el
caso particular en que tal código permita, además, el uso de claves, se conoce como
«Código de Autenticación de Mensaje con Resumen y Clave» (en inglés, Keyed-Hash
Message Authentication Code, KHMAC).
588. La versión más extendida de HMAC es la adoptada como estándar por el NIST ([ANSI,
X9.71], [NIST, FIPS198]) y usa una clave de 512 bits. La seguridad de este MAC
depende, obviamente, de la seguridad de la función resumen empleada.
589. El operador HMAC con una clave k sobre un mensaje m se define como sigue:
HMACk(m) = h((k⊕opad)||h((k⊕ipad)||m)),
7.1. EJEMPLOS
590. Los valores HMAC basados en las funciones resumen MD5, SHA-1, SHA-256, SHA-384
y SHA-512 del mensaje «Funciones resumen», con la clave «Hash» son,
respectivamente, los siguientes:
HMAC-MD5: f864dc3dced79b1b4b9940af8a1dfe48,
HMAC-SHA-1: 2cb93aabff961bae6fa3f73fb9700e1b8ed3b984,
HMAC-SHA256: 1054690d7dfeecca19e9008b0fc66c44
08f74a90a6a57fcf4ab2f0eee087f3ea,
HMAC-SHA384: d07374fcf65b354d17ce973f119d380f
ce50cfbe4a73b69d461ac98756bd2cd6
3aa2c9f8c5e0e10b34f598bb02a19042,
HMAC-SHA512: 3a12502ae8f06b97821bcd2b36da06ca
284a4fbdb80f93b9cac0cba5c979bdbb
50a168791c3b8bb625c417f91a085edc
24f5194b102fd519be1a6409edda52a4.
HMAC-MD5: de65e1ca6489452418070c02de331c86,
HMAC-SHA-1: 1a4f91dd71be565edf49953b19403c9f97fb0604,
HMAC-SHA256: b5148d6eeaa25b84007d6093fd899a49
3dcd30d40b9bf02f4e5959da6debedc5,
HMAC-SHA384: 92790c0bd169a8a30097365099af5348
3c3898644bce509c981de16309cc79f6
bea82e35dd12d2d15c024b710e613790,
HMAC-SHA512: c3c30530a0ba5594e6108876cb9f4c83
0ccb08cce836b492e1b8d5ab724b9d98
05ca2bcd4cbeb5fc1d0fb41be2520d31
38fce5885fdb1ac1db6f3578480845f4.
8. AUTENTICACIÓN DE USUARIOS
592. La posesión de claves privadas compartidas entre varios usuarios permite la creación de
protocolos de autenticación, para demostrar la personalidad del usuario ante otro usuario
o ante un equipo servidor.
593. Hay dos clases de protocolos, según el número de participantes. El más simple es aquel
en el que solo participan una pareja de usuarios que comparten una clave simétrica
secreta. El más complejo es aquel que además de la pareja de usuarios se requiere una
tercera parte confiable o tercero de confianza que actúa como servidor de seguridad.
594. El primer tipo de protocolo es adecuado para redes con pocos usuarios (del orden del
centenar, o menor), ya que cada uno puede almacenar y gestionar fácilmente la clave a
usar con cada uno de sus corresponsales. En cambio, cuando la cantidad de posibles
corresponsales es muy amplia (del orden de miles, o mayor) el único tipo manejable es el
segundo; en este caso cada usuario solo dispone de una clave que comparte con el
servidor de seguridad, mientras que el servidor de seguridad tiene un archivo con la clave
de cada uno de sus usuarios clientes.
595. Los protocolos de autenticación emplean una serie de valores conocidos y permanentes,
como los identificadores de los terminales de la red y otros que son números de un solo
uso, generalmente aleatorios. A continuación se listan las abreviaturas de los elementos
que se utilizan en ellos:
tA, tB: Sellos temporales, generados por Alicia o Benito (ver Anexo F, sección 6).
nA, nB: Números de uso único, generados por Alicia o Benito, también llamado
«nonce» (number used once).
597. Benito comprueba, tras descifrar el mensaje, que el sello temporal no ha caducado, que el
identificador es el suyo propio y que Alicia conoce la clave; así Alicia queda autenticada
frente a Benito. El sello temporal tA evita un ataque por reenvío retardado contra Benito.
El indicador de Benito B evita un ataque inmediato contra Alicia por reflexión. En este
protocolo Benito reconoce a Alicia, pero Alicia no sabe si realmente habla con Benito; si
se quiere asegurar ese extremo, ha de repetirse el protocolo en sentido contrario.
598. Como se puede observar, este método es sumamente económico, pues se consigue la
identificación segura con un solo mensaje. La desventaja que presenta es que se requiere
que los relojes locales sean seguros, exactos y estén en sincronismo con un reloj central.
El mecanismo de sincronización entre relojes se puede conseguir fácilmente mediante
protocolos adicionales de comunicación entre el servidor y los clientes; pero éstos deben
a su vez ser también seguros, lo que conduce a una nueva complicación del sistema, que
desvirtúa de alguna forma su supuesta sencillez.
600. Es parecido al método de desafío respuesta, pero perfeccionado. En este caso se añaden
sendos indicativos de Alicia y Benito. Los indicativos evitan el ataque por reflexión, pues
las respuestas son diferentes según a quién vayan dirigidas.
601. Para una identificación unilateral, hubiesen bastado los dos primeros pasos del protocolo
y no hubiese sido necesario el número rB.
602. Este método precisa un generador de números aleatorios, que ha de ser
criptográficamente seguro.
605. En el primer paso, Alicia contacta con una tercera parte confiable, Teresa, con la que
comparte la clave KAT. Le envía su identificación junto con un mensaje cifrado con
dicha clave; el mensaje incluye un sello temporal tA, el indicador de Benito y la clave
que quiere usar en la sesión de trabajo K. Teresa sabe que es Alicia porque demuestra
conocer su clave común.
606. En el segundo paso, Teresa envía a Benito, cifrado con la clave KBT, otro sello temporal,
el indicativo de Alicia y la clave de sesión K. Benito reconoce a Teresa porque ésta
demuestra conocer su clave común y acepta la clave de sesión que le traslada para
dialogar con Alicia.
607. Los sellos temporales tA y tT impiden los ataques por repetición.
608. La desventaja de este protocolo, aparentemente tan sencillo, es que se obliga a Teresa a
realizar el trabajo de abrir una sesión de comunicación con Benito. Otro inconveniente es
que ha de garantizarse que Alicia sepa desempeñar la tarea —no simple— de generar
claves aleatorias K, criptográficamente seguras, con todas las garantías necesarias. Y, por
supuesto, hay que contar con la exigencia de mantener relojes seguros sincronizados.
610. Todo el trabajo de generación de claves seguras queda localizado en Teresa, liberando a
los corresponsales de tal responsabilidad.
611. Alicia contacta directamente con Teresa, que le proporciona la credencial adecuada, y
posteriormente con Benito; éste se comunica únicamente con Alicia. Se supone que,
previamente, Alicia dispone de una clave secreta que comparte con Teresa, KAT, que
también comparte una clave secreta, KBT, con Benito.
612. Los números rA, rB y rB−1 sirven para evitar ataques por repetición.
613. En el segundo paso, Alicia verifica que Teresa es legítima y que no está contestando a un
protocolo antiguo gracias a rA. En el cuarto paso, Alicia reconoce a Benito. En el quinto
paso, Benito hace el reconocimiento de Alicia y se asegura de que ésta no está
reproduciendo un protocolo realizado anteriormente. Un mérito del protocolo es que
libera del mantenimiento de un reloj seguro sincronizado. Pero, a cambio, presenta el
problema de que las claves de sesiones anteriores son válidas siempre y se podrían
reutilizar si hubiesen sido capturadas por un atacante hostil.
615. Alicia se pone en contacto únicamente con Benito y le envía una solicitud de inicio de
sesión. Benito se encarga de contactar al servidor. El servidor reconoce a los solicitantes
gracias a que demuestran la posesión de sus claves particulares. Benito reconoce al
servidor porque éste demuestra conocer su clave particular. Alicia reconoce al servidor
porque éste conoce su clave particular, mientras que a Benito le reconoce de forma
implícita porque le suministra una información válida EKAT(rA,K) y además
explícitamente, porque le suministra EK(A,rB). Benito sabe que Alicia fue identificada
por el servidor en el paso 3; pero en el paso 5 obtiene una confirmación porque Alicia
demuestra estar en posesión de su clave particular.
618. Alicia contacta directamente con Kerberos, que le proporciona la credencial adecuada, y
posteriormente se pone en contacto con Benito. Benito se comunica únicamente con
Alicia. Se supone que, previamente, Alicia dispone de una clave secreta que comparte
con Kerberos, KAT. El servidor también comparte una clave secreta KBT con Kerberos.
Tiene varias versiones, aquí se presenta la versión 5 en su forma básica.
619. Alicia se identifica, solicita conexión con el servidor Benito, y envía un número rA a
Kerberos.
620. Kerberos, sin molestarse en saber si Alicia es auténtica o miente, le contesta y le devuelve
un «Tique» para el servidor B, junto con un paquete cifrado con la clave de Alicia, que
contiene una clave secreta de sesión K, y el número rA, el período de vida de la clave l y
el indicador del servidor B. Si Alicia es auténtica, puede seguir el protocolo, recuperando
rA (que le sirve para autenticar a Kerberos), K, l, y B.
621. A continuación, Alicia envía al servidor el Tique junto con un «Autenticador», que se
confecciona cifrando con la clave K el identificador A y un sello temporal tA. Entonces,
el servidor realiza la autenticación de Alicia comparando la información encerrada en el
Tique y el Autenticador.
622. Finalmente, el servidor devuelve a Alicia el sello temporal cifrado, para que Alicia tenga
la confirmación de la identidad del servidor B y de que no se trata de la repetición de un
protocolo antiguo.
623. En algunas versiones de este protocolo se sustituye el número aleatorio rA por un sello
temporal, elaborado por Alicia.
1. FIRMAS ELECTRÓNICAS
624. Los criptosistemas de clave pública, además de permitir la confidencialidad de los datos
cifrados, facilitan el diseño de otros protocolos, entre los que destacan los relacionados
con los de la firma electrónica de mensajes o documentos electrónicos.
625. La «firma electrónica» o «firma digital» de un mensaje o documento es un protocolo
electrónico cuyo objetivo es análogo al de la firma manuscrita, es decir, garantizar que
quien remite un mensaje es realmente quien dice serlo. Este protocolo electrónico puede
llevarse a cabo sin importar que la comunicación sea confidencial o no.
626. Dicho de otra forma, un protocolo de firma electrónica puede utilizarse bien con el único
fin de garantizar la propiedad de un documento público mediante la firma electrónica de
su autor, bien para garantizar la procedencia de una comunicación confidencial.
627. En general, ambos protocolos son diferentes, si bien en determinados casos, tal diferencia
es mínima y sólo afecta al proceso de verificación y no al de elaboración de la firma.
628. La firma se calcula para cada mensaje o documento y depende tanto del mensaje como
del remitente. Al contrario de lo que sucede con la firma manuscrita, que es siempre la
misma para cualquier documento y sólo varía cuando cambia el firmante, la firma
electrónica es única para cada mensaje. Además, las firmas deben ser fáciles de calcular,
verificar y difíciles de falsificar.
629. Las firmas digitales pueden clasificarse de la siguiente manera:
Implícita: la firma electrónica calculada se incluye en el propio fichero que contiene el documento
que se firma.
Explícita: la firma se añade al documento a firmar pero no forman parte de él, es decir, se
almacena en un fichero diferente.
Privada: la firma permite identificar al firmante sólo en el caso en que el destinatario comparta
una información confidencial o secreta con el firmante.
Pública: la firma identifica al firmante utilizando información públicamente conocida del propio
firmante.
Revocable: la firma no impide que el firmante pueda negar que fuera él quien firmó del
documento.
Irrevocable: la firma impide que el firmante pueda negar que la firma le pertenece.
630. En general, los protocolos de firma electrónica más extendidos son aquellos en los que la
firma calculada es explícita, pública e irrevocable.
631. Existen otros tipos de firma, como las firmas ciegas (o a ciegas), las delegadas, las que se
elaboran en nombre de un grupo, las múltiples, las autocertificadas, las basadas en la
identidad del firmante, etc., si bien su uso está menos extendido. De hecho, estos
protocolos de firma no se consideran estándares, por lo que no serán tratados en esta guía.
632. Un protocolo de firma electrónica consta de dos partes, supuesto que cada participante en
el protocolo posee su par de claves pública y privada. La primera fase del protocolo
consiste en la elaboración de la firma en sí y lo lleva a cabo el firmante del documento
haciendo uso de su clave privada; mientras que la segunda parte es la verificación de la
firma y es responsabilidad del destinatario o verificador del documento ([Fúster et al.,
2004], [Menezes et al., 1997], [Stinson, 2006]).
633. En los dos protocolos que siguen, la firma es explícita, puesto que la misma se añade al
mensaje y no forma parte del mismo; es pública dado que puede ser verificada a partir de
información del firmante conocida públicamente; y, finalmente, es irrevocable dado que
la única persona que puede llevarla a cabo es el propietario de la clave privada.
636. Para que el verificador V pueda comprobar la firma electrónica de F para el documento
m, lleva a cabo los siguientes pasos:
V determina el resumen del mensaje que F le envió mediante la función resumen acordada:
h(m) = mV.
V calcula el resumen del mensaje orginal descifrando con la clave pública de F, A, la rúbrica recibida:
DA(r) = DA(Ea(mF)) = mF.
V comprueba si los dos resúmenes calculados coinciden:
mV = mF.
637. En el caso en que ambos resúmenes coincidan, V considerará que la firma del documento
m recibido ha sido realmente hecha por F, dado que sólo F es capaz de lleva a cabo el
paso a. de la elaboración de la firma, dado que es el único que conoce su clave privada, a.
Además, la igualdad de los resúmenes permite afirmar que el documento original no ha
sido manipulado.
638. Si ambos resúmenes no coinciden, V no aceptará la firma como válida porque o bien se
ha firmado el documento con una clave privada diferente de la de F, o bien se ha
manipulado el documento original.
640. Para que V verifique la firma electrónica de F para el documento m, sigue los siguientes
pasos:
V recupera el documento original, m, descifrando el criptograma recibido, c, mediante su clave de
descifrado correspondiente y determina su resumen con la función resumen acordada:
h(m) = mV.
V recupera la rúbrica, r, calculada por F para el documento, descifrando la firma electrónica con
su clave privada, b:
Db(s) = Db(EB(r)) = r.
V obtiene el documento resumen del documento original, m, descifrando la rúbrica mediante la
clave pública de F:
DB(r) = DB(Eb(mF)) = mF.
V comprueba si el resumen del documento obtenido en el paso anterior, mF, coincide con el
resumen del documento, mV, que calculó en el paso a. de este protocolo:
mV = mF.
641. Si la verificación es incorrecta, tanto la firma como el propio documento se rechazan. Las
posibles razones son:
Que el documento, ha sido modificado.
Que el paquete de firma ha sido modificado.
Que la firma y el documento no están relacionados.
Que no se ha empleado la clave pública de verificación adecuada.
Que no se ha empleado la clave pública de cifrado adecuada.
642. Conviene señalar que en determinadas ocasiones se ha propuesto que dado que se firma
un resumen del documento y no el documento en sí, no es necesario ejecutar el paso c. en
el protocolo de elaboración de la firma anterior, ni, en consecuencia, el paso b. en el
protocolo de verificación. En estas ocasiones se aduce que como a las funciones resumen
se les exige ser seguras frente al ataque por colisiones, es decir, que obtener un
documento a partir del conocimiento de su resumen es computacionalmente muy difícil,
basta con cifrar el resumen con la clave privada del firmante, reduciendo la firma
electrónica a sólo la rúbrica.
643. Sin embargo, esta propuesta no es segura y no deben admitirse protocolos que se
implementen de esta forma. En efecto, si los protocolos de elaboración y verificación
anteriores se redujeran tal y como se ha dicho, cualquier usuario podría calcular la rúbrica
a partir de la clave pública del firmante y obtener el resumen de un documento que se
desea mantener en secreto.
644. Con este procedimiento, la seguridad del documento sólo dependería de la seguridad de
la función resumen empleada, puesto que invertir el proceso de dicha función daría el
mensaje original. Sin embargo, es importante señalar que aunque las funciones resumen
son seguras frente a ataques contra la pre-imagen y frente a colisiones, no emplean
ningún tipo de clave, por lo que el secreto del documento no dependería,
paradójicamente, de ninguna clave, a pesar de estar empleando criptosistemas de clave
pública.
649. El protocolo para la verificación de la firma digital del firmante llevado a cabo por el
verificador cuando el documento es público es el siguiente:
V calcula el resumen del documento recibido descifrando la firma electrónica mediante la clave
pública del firmante:
(5)
La expresión genérica a^b representa la potencia b-ésima de a, mientras que (a^b)^c representa el valor de a
elevado a la potencia b y todo ello elevado a c.
651. El protocolo de verificación de la firma digital del firmante que lleva a cabo el verificador
en el caso en que el documento no sea público es el siguiente:
V obtiene la rúbrica de F para el mensaje m descifrando la firma recibida haciendo uso de su clave
privada:
s^dB (mod nB) = (r^eB)^dB (mod nB) = r^(eB·dB) (mod nB) = r.
V calcula el resumen del mensaje descifrando la rúbrica mediante la clave pública del firmante:
r^eA (mod nA) = (m^dA)^eA (mod nA) = m^(dA·eA) (mod nA) = m.
V determina el resumen h(m) = m, del mensaje m, descifrando el criptograma recibido y verifica si
tal resumen coincide con el obtenido en el paso anterior:
m = m.
Sólo si ambos resúmenes coinciden, V da por válida y correcta la firma.
652. Los ataques contra el protocolo de firma digital RSA son los mismos que contra el propio
criptosistema dado que ambos protocolos se basan en el mismo problema matemático.
= ga·r+x·s (mod p)
= gm (mod p).
661. Para llevar a cabo la firma digital DSS de un mensaje, m, se ejecuta el protocolo
siguiente:
El firmante calcula el resumen del mensaje a firmar:
h(m) = m.
Luego selecciona un entero aleatorio k, con 0 < k < q y calcula
r = (gk (mod p)) (mod q).
Más tarde resuelve en la incógnita s la congruencia
m = –a·r+k·s (mod q),
662. Los posibles valores de L y N, es decir, las longitudes en bits recomendadas por el NIST
en 2009 ([NIST, FIPS186-3]) para los tamaños de p y q son los siguientes:
L = 1024, N = 160.
L = 2048, N = 224.
L = 2048, N = 256.
L = 3072, N = 256.
(6)
El valor de L no es único. Las posibles elecciones de este número se mencionan más abajo.
(7)
Tampoco el valor de N es único. Sus posibles valores, según el valor elegido para L, se incluyen posteriormente.
= r.
664. Debido a que la generación de las claves de la norma DSS anterior no es tan inmediata
como pudiera parecer, sobre todo porque no es fácil determinar la factorización de p–1 ni
tampoco localizar de forma rápida un divisor q de p–1, lo que se hace en la práctica es
utilizar un algoritmo que se conoce como Algoritmo de Firma Digital (DSA, Digital
Signature Algorithm).
665. El algoritmo determina los parámetros del protocolo DSS de modo más eficiente de la
siguiente forma:
En primer lugar, el firmante selecciona un número primo q de N bits, es decir, con 2N–1 < q < 2N.
Para ello repite la generación aleatoria de un entero impar, q, hasta que sea primo, haciendo uso
del test de pseudo-primalidad de Miller-Rabin.
A continuación selecciona un primo p de L bits, es decir, con 2L–1 < p < 2L. Para ello genera
aleatoriamente un entero n de modo que
(2L–1–1)/(2·q) < n < (2L–1)/(2·q)
666. Una vez generados los parámetros del protocolo, se procede como se ha indicado antes
para la elaboración y verificación de la firma digital de un documento.
r = x1 (mod q).
Si r = 0, el firmante selecciona otro valor para k.
Calcula k–1 (mod q) y determina
s = k–1·(m+a·r) (mod q),
La firma digital es el par (r, s).
670. Para verificar la firma del firmante, el verificador lleva a cabo el siguiente protocolo:
Calcula el resumen del mensaje, ya sea porque conoce el mensaje al ser éste público o porque lo ha
descifrado si era no público:
m = h(m).
Comprueba que los enteros r y s están en el intervalo [1, q–1].
Calcula
w = s–1 (mod q).
Calcula
u1 = m·w (mod q),
v = x0 (mod q).
El verificador acepta la firma como válida si y sólo si se cumple que v = r.
671. Las longitudes en bits recomendadas por el NIST en 2009 ([NIST, FIPS186-3]) para los
tamaños del orden de G, denotado por |n|; de su cofactor, c; del tamaño del cuerpo primo,
es decir, si el cuerpo tiene un número primo p de elementos; y de los cuerpos binarios, es
decir, cuerpos con 2m elementos, son los siguientes:
161 ≤ |n| ≤ 223, c < 210, |p| = 192, |m| = 163.
224 ≤ |n| ≤ 255, c < 214, |p| = 224, |m| = 233.
256 ≤ |n| ≤ 383, c < 216, |p| = 256, |m| = 283.
384 ≤ |n| ≤ 511, c < 224, |p| = 384, |m| = 409.
|n| ≥ 512, c < 232, |p| = 521, |m| = 571.
672. Por otra parte, las curvas elípticas cuyo uso recomienda el NIST están publicadas en el
Apéndice D de [NIST, FIPS186-3]. Existen tres tipos de curvas:
Curvas sobre cuerpos primos: P-192, P-224, P-256, P-384 y P-521.
Curvas sobre cuerpos binarios: K-163, B-163, K-233, B-233, K-283, B-283, K-409, B-409, K-571
y B-571.
673. El significado de los elementos utilizados en los identificadores de las curvas NIST es el
siguiente:
P: identifica las curvas sobre cuerpos primos.
B: indica que se trata de una curva sobre cuerpos binarios.
K: indica que se trata de una curva de Koblitz (definida sobre cuerpos binarios).
Cadena de dígitos: expresa el tamaño en bits del cuerpo sobre el que está definida la curva.
674. Finalmente, las curvas elípticas recomendadas por Brainpool (ver [Brainpool, 2005],
[Lochter and Merkle, 2010]) son las siguientes: P160r1, P192r1, P224r1, P256r1, P320r1,
P384r1 y P512r1; donde es importante señalar que Brainpool no propone curvas sobre
cuerpos binarios.
675. El significado de los elementos utilizados en los identificadores de las curvas Brainpool
es el siguiente:
P: identifica las curvas sobre cuerpos primos.
Primera cadena de dígitos: expresa el tamaño en bits del cuerpo sobre el que está definida la curva.
r : informa que los coeficientes de la curva se han generado aleatoriamente (random) según el
procedimiento descrito en [Brainpool, 2005].
Dígito final: permite identificar diferentes curvas donde el resto de los parámetros utilizados por
esta notación coinciden.
libremente por cada uno de los usuarios. En este caso, el punto G y su orden, n, deben
formar parte de la clave pública del firmante. Si F es fijo, entonces el hardware y el
software pueden construirse de modo que optimicen los cálculos en el cuerpo base,
teniendo en cuenta que hay una enorme cantidad de posibles elecciones para la curva
elíptica sobre un cuerpo base fijado de antemano.
6. SELLOS DE TIEMPO
680. El sellado de tiempo es una técnica criptográfica que se usa para proporcionar
información temporal sobre los documentos electrónicos. Permite a otras partes validar el
instante en el que un documento ha sido creado y comprobar que dicho documento no ha
sido alterado desde entonces.
681. Al hacer posible la trazabilidad temporal de la firma de documentos, el sellado de tiempo
ayuda significativamente a aumentar el nivel de confianza que se requiere hoy día en una
infraestructura de clave pública. En muchos casos el sellado de tiempo llega a ser la
principal prueba a la hora de determinar el estado de un documento. Ejemplos típicos de
uso de los sellos de tiempo pueden ser la validación de firmas electrónicas, solicitudes de
patentes, inicios de sesión en ordenadores (evaluación de aspectos de seguridad y
funcionamiento en sistemas y redes), suscripciones por ordenador (garantizando la
revocación de las suscripciones), servicios de notariado electrónico, voto electrónico,
órdenes de venta y recibos o factura electrónica, protección de la propiedad intelectual,
sellado de contenidos, etc.
682. La importancia de los sellos de tiempo resulta evidente cuando pensamos en la necesidad
de dar validez legal a los documentos electrónicos durante un largo periodo de tiempo
([Buldas et al., 1998]).
685. Es preciso que k sea suficientemente grande para que el usuario quede persuadido de que
no es posible haber corrompido a tantas personas simultáneamente. Esta técnica tiene
pues la enorme desventaja de que requiere mucha cooperación. Otra desventaja es el
tiempo de vida de las firmas que se envían de vuelta al remitente, un problema recurrente
siempre que se usan firmas.
686. Las técnicas que se basan en la existencia de una tercera parte de confianza dependen de
la imparcialidad de la entidad que está al cargo de emitir el sello de tiempo, la Autoridad
de Sellado de Tiempo (TSA, acrónimo inglés de Time Stamping Authority), que
garantiza la existencia de unos determinados datos electrónicos en una fecha y hora
concretos ([Pinkas et al., 2003]). Se suelen dividir en dos tipos: esquemas simples y
esquemas enlazados ([ISOIEC, 18014]).
687. En los esquemas simples la función de la TSA después de recibir el documento a sellar es
añadirle el tiempo actual (un sello de tiempo seguro) y firmar el resultado
electrónicamente por medio de un cifrado asimétrico basado en infraestructura de clave
pública.
688. El término «sello de tiempo» hace referencia al certificado digital que contiene el código
resumen del archivo que contiene el documento, más la indicación de tiempo. Nadie
salvo la propia TSA puede alterar el sello de tiempo así obtenido o fechar ningún dato del
documento con anterioridad. Este esquema se utiliza en el estándar de sellado de tiempo
propuesto para Internet ([Adams et al., 2001]) y en las especificaciones técnicas [ETSI,
TS-102023] y [ETSI, TS-101733] del Instituto Europeo de Normas de
Telecomunicaciones (European Telecommunications Standards Institute, ETSI).
689. Entre sus ventajas destacan que son compactos y fáciles de calcular, no dependen de otros
sellos de tiempo, el protocolo requiere un único paso y es posible comparar sellos de
tiempo emitidos por distintas TSAs.
690. El principal inconveniente de estos sistemas es que es preciso confiar absolutamente en la
TSA, la cual puede emitir de manera indetectable sellos de tiempo atrasados. Existe otro
inconveniente relacionado con las firmas criptográficas, cuyo tiempo de vida puede ser
menor que el del documento. Además, todos los sellos de tiempo quedan invalidados
cuando la clave privada de la TSA resulta comprometida.
691. El sellado de tiempo basado en esquemas enlazados proporciona autenticación temporal
relativa ([Massias and Quisquater, 1997], [Massias et al., 1999]). En ellos lo que se
verifica es el orden relativo de emisión entre dos sellos de tiempo cualesquiera. Utilizan
funciones resumen, pero no claves, es decir no usan información secreta. Se han
propuesto varios tipos de esquemas enlazados. En todos ellos, un certificado de tiempo de
un sello emitido en un instante depende de sellos emitidos con anterioridad.
692. Los esquemas enlazados en cadena enlazan, utilizando funciones resumen
unidireccionales, cada documento con el que la TSA firmó previamente, construyendo así
una cadena cronológica inmodificable ([Haber and Stornetta, 1991]). Resultan poco útiles
en la práctica, puesto que la longitud de cada certificado aumenta de modo lineal con el
número de sellos de tiempo emitidos hasta ese momento (el número de pasos necesarios
para comparar dos sellos depende del número de sellos que hay entre ellos).
693. En los esquemas enlazados en árbol todos los documentos sellados durante un periodo
corto (por ejemplo un segundo), se organizan como hojas de un árbol binario ([Merkle,
1979]).
694. El sellado de tiempo, para una petición individual procesada durante una determinada
ronda, consiste en información que permite a cada uno comprobar que su petición es
parte del proceso de acumulación que produjo el correspondiente valor de la ronda.
695. Los valores calculados en sucesivas rondas se enlazan unos a otros por medio de una
función resumen, creando así una cadena temporal infalsificable.
696. Periódicamente, uno de los valores de la ronda se publica en un medio inalterable y
ampliamente expuesto a testigos (por ejemplo, un periódico). Estos valores de ronda
especiales son la base de la confianza en todos los sellos de tiempo emitidos. Es preciso
confiar en esos valores, así como en el tiempo asociado a ellos, lo cual es un requisito
razonable puesto que tales valores han sido puestos a la vista de un gran número de
testigos. El tiempo absoluto en el que los potenciales verificadores confían es el tiempo
indicado en esos medios inalterables.
697. En la Figura F.1 se representa la construcción del árbol correspondiente a una ronda.
698. Cada petición de sellado consiste en un valor resumen de un documento dado. Las hojas
del árbol son cada uno de esos valores resumen, representadas por H1, …, H8 en la
Figura F.1. Los valores de las hojas se van concatenando de dos en dos, aplicando nuevas
funciones resumen y así sucesivamente hasta obtener el valor de la ronda actual.
699. Ese valor superior del árbol de cada ronda, L15, se concatena con el valor obtenido en la
ronda precedente Pi-1 y, por último, se aplica la función resumen para obtener el valor
real de la ronda, Pi.
700. El sello de tiempo solicitado durante la ronda actual contiene todos los valores necesarios
para reconstruir su correspondiente rama del árbol, hasta la raíz. En el ejemplo de la
Figura F.1, el sello de tiempo para H4 contiene H3, L9, L14 y Pi-1.
Figura F.1. Representación gráfica de una ronda construida usando un árbol binario.
701. El tamaño de los sellos de tiempo aumenta de modo logarítmico con el número de
peticiones procesadas en una ronda.
702. El proceso de verificación consiste en reconstruir la rama del árbol y la cadena enlazada
de valores de ronda hasta que se recalcule un valor en el que el verificador confía ([Haber
and Stornetta, 1991], [Massias and Quisquater, 1997]).
703. La seguridad se basa en la función resumen utilizada: si es inviable encontrar dos
entradas que conduzcan al mismo valor resumen (esto es, si la función no presenta
colisiones), entonces es imposible falsificar el árbol binario o la cadena de enlace.
704. Se podrían construir dos árboles para cada ronda, utilizando dos funciones resumen
diferentes, de modo que el sistema permaneciese seguro en caso de ruptura de una de las
funciones resumen.
705. Otro requisito de seguridad es forzar a los clientes a comprobar los sellos de tiempo tan
pronto como los reciban. De ese modo el proceso es auditado continuamente y la TSA no
podrá maniobrar de modo poco fiable.
706. Un modo de alargar la vida de los sellos de tiempo consiste en resellar tanto el
documento como el sello original antes de que se consiga romper la función resumen
([Haber and Stornetta, 1991]).
707. Estos sistemas tienen la ventaja de que su seguridad es independiente de la clave privada
de la TSA, es imposible emitir sellos atrasados y la verificación es muy rápida. Necesita
menos requisitos de almacenamiento y aumenta el número de partes interesadas que
sirven como testigos.
708. Sin embargo, se trata de un protocolo muy complejo y es difícil comparar sellos de
tiempo de diferentes TSAs.
709. En los esquemas de acumulador unidireccional ([Benaloh and de Mare, 1993]) se recogen
todas las peticiones recibidas durante una ronda yi, 1 <= i <= m, que son nuevamente
funciones resumen de documentos individuales. La acumulación se realiza por medio de
la operación de exponenciación modular:
710. Zm = Z0^(Π yi) (mod N), para 1 <= i <= m, con N un modulo tipo RSA.
711. Para verificar el sello de tiempo para una petición particular yi es preciso comprobar que
se verifica la siguiente ecuación:
712. Zm = Zj^(yi) (mod N), con Zj = Z0^(Π yi) (mod N), para 1 <= i <= m e i ≠ j.
713. Por tanto un sello de tiempo individual para la petición yi consiste en los valores Zj y Zm.
El tamaño de los sellos es independiente del número de peticiones procesadas en la ronda.
714. La desventaja de este método es que la operación de exponenciación modular es menos
eficiente que la función resumen.
715. La seguridad de este método se basa en la seguridad del RSA, de modo que si no se
conoce la factorización del módulo N es inviable producir un sello de tiempo falso.
7. CUADRO RESUMEN
Cuadro F.1. Resumen de longitudes de claves de criptosistemas asimétricos y tipos
funciones resumen en esquemas de firma electrónica para el ENS
2.9. Firma Nivel Bajo Nivel Medio Nivel Alto
electrónica
Permitido Permitido (a corto plazo) Permitido
RSA
Claves ≥ 1024 bits Claves ≥ 1024 bits Claves ≥ 2048 bits
Permitido Permitido (a corto plazo) Permitido
ECC
Claves: 224-255 bits Claves: 224-255 bits Claves: 256-283 bits
MD5 No permitido No permitido No permitido
SHA-1 Permitido (a corto plazo) Permitido (a corto plazo) Permitido (a corto plazo)
RIPEMD-160 Permitido (a corto plazo) Permitido (a corto plazo) Permitido (a corto plazo)
SHA-2 Permitido Permitido Permitido
723. La fuente de entropía consiste típicamente de una magnitud física, como el ruido en un
circuito eléctrico, la sincronización de los procesos de usuario (por ejemplo, pulsaciones
de teclas o movimientos del ratón), o de los efectos cuánticos en un semiconductor,
aunque generalmente se utilizan varias combinaciones de estas entradas. De cualquier
modo es muy difícil diseñar un dispositivo o un programa que explote esta aleatoriedad y
produzca una secuencia de bits que esté libre de sesgos y correlaciones.
724. El uso de un proceso de destilación es necesaria para superar cualquiera de las
debilidades en la fuente de entropía. La destilación suele consistir en hacer algunas
operaciones lógicas sobre la secuencia obtenida.
725. Las secuencias de salida de los generadores aleatorios se pueden utilizar directamente
como secuencias aleatorias o pueden utilizarse como entrada de un generador
pseudoaleatorio. En cualquier caso, cuando se utilice directamente como secuencia
aleatoria (es decir, sin transformación), ésta deberá al menos satisfacer estrictamente
todos los criterios de aleatoriedad que se analizan mediante pruebas estadísticas, que
serán explicadas más adelante. Para la mayoría de las aplicaciones criptográficas el
generador no deberá estar sujeto a observación o manipulación por parte de un
adversario, de modo que el dispositivo debe estar a buen recaudo.
735. Ataques basados en la entrada. Un ataque a la entrada del PRNG se produce cuando un
atacante es capaz de usar el conocimiento acerca de la secuencia de entrada al PRNG para
criptoanalizarla, es decir, distinguir entre la producción del PRNG y valores aleatorios.
Este ataque puede implementarse de varias formas: ataque por entrada conocida, ataque
por entrada repetida y ataque por entrada elegida. Los ataques de entrada elegida pueden
ser prácticos contra tarjetas inteligentes y otras manipulaciones durante un ataque
criptoanalítico/físico; también pueden ser prácticos para las aplicaciones donde se usan
las contraseñas de usuario, las estadísticas de red, etc. El ataque por repetición de entrada
es igualmente práctico en las mismas situaciones, pero requiere menos control y un poco
menos de sofisticación por parte del atacante.
736. Ataques por extensión de un estado comprometido. Este ataque intenta extender las
ventajas de un ataque previo exitoso donde se ha recobrado un estado S del generador. En
la práctica, es prudente asumir que un estado S del generador puede estar comprometido
en un momento dado, por lo que para preservar la solidez del sistema, el PRNG debe
diseñarse de modo que pueda resistir este ataque.
4.2. ALEATORIEDAD
741. Actualmente no se dispone de ninguna prueba matemática que determine de forma
categórica la propiedad de aleatoriedad de una secuencia de bits dada. El estudio y
análisis de la aleatoriedad de una secuencia cualquiera se lleva a cabo mediante diferentes
tests estadísticos. Cada test determina si la secuencia posee, o no, alguna propiedad que
permita considerarla como aparentemente aleatoria. Las conclusiones de los diferentes
tests nunca son definitivas, pero sí probabilísticas. Si la secuencia estudiada supera todos
los tests estadísticos a los que ha sido sometida, entonces se dice que la secuencia de bits
es aceptada como aleatoria (aceptada porque no ha podido ser rechazada). Desde el punto
4.3. IMPREDECIBILIDAD
743. Los números pseudoaleatorios y aleatorios generados para aplicaciones criptográficas
deben ser impredecibles. En el caso de los generadores pseudoaleatorios, si se desconoce
la semilla, la salida del próximo número en la secuencia tendrá que ser impredecible a
pesar de conocer cualquier número generado previamente. Esta propiedad se conoce
como «impredecibilidad hacia adelante». Tampoco debe ser posible determinar la semilla
del generador a partir del conocimiento de algunos valores generados («impredecibilidad
hacia atrás»). No debe existir correlación entre la semilla y cualquier valor generado a
partir de ella, es decir, cada elemento de la secuencia debe aparecer como la salida de un
nuevo evento aleatorio independiente, cuya probabilidad es ½.
744. Para asegurar la impredecibilidad hacia adelante se debe ser muy cuidadoso a la hora de
elegir la semilla. Los valores generados por un PRNG son completamente predecibles si
se conoce la semilla y el algoritmo de generación. Como en muchos casos los algoritmos
de generación son públicamente conocidos, la seguridad recae en mantener en secreto la
semilla, la cual no se podrá intuir a partir de la secuencia pseudoaleatoria que ésta
produce. Por tanto, la semilla por sí misma debe ser impredecible. Cuando se realizan
pruebas de aleatoriedad a secuencias binarias aleatorias se asume lo siguiente:
Uniformidad: en cualquier punto de la generación de una secuencia aleatoria o bits pseudo
aleatorios, la ocurrencia de un cero o un uno es igualmente probable, es decir, la probabilidad de
cada uno es exactamente ½. El número esperado de ceros (o unos) es n/2 , donde n es la longitud
de la secuencia.
Escalabilidad: cualquier prueba aplicable a una secuencia, podrá ser aplicada también a
subsecuencias extraídas aleatoriamente. Si la secuencia es aleatoria, entonces cada subsecuencia
extraída también será aleatoria, por tanto cualquier subsecuencia extraída deberá también pasar el
test de aleatoriedad.
Consistencia: el comportamiento de un generador será consistente con el valor inicial, es decir con
la semilla. Lo cual quiere decir que si la semilla es un parámetro débil, la secuencia generada
también lo será; por tanto es inadecuado comprobar un generador de secuencia pseudoaleatorio
basados en la utilización de una mala semilla o a un generador aleatorio sobre la base de una salida
producida a partir de una salida física poco aleatoria.
ANEXO F. REFERENCIAS
[Adams et al., 2001] C. Adams, P. Cain, D. Pinkas, and R. Zuccherato, Internet X.509 Public
Key Infrastructure Time-Stamp Protocol (TSP), Request for Comments RFC 3161, August
2001
[Armknecht, 2002] F. Armknecht, A Linealization Attack on the Bluetooth Key Stream
Generator. IACR e-print archive, 2002/191.
[ANSI, X9.30-1] American National Standards Institute, Public key cryptography using
irreversible algorithms-Part 1: The Digital Signature Algorithm (DSA), ANSI X9.30-1,
1997.
[ANSI, X9.42] American National Standards Institute, Public key cryptography for the financial
services industry: Agreement of symmetric keys using discrete logarithm cryptography,
ANSI X9.42, 2003.
[ANSI, X9.44] American National Standards Institute, Key establishment using integer
factorization cryptography, ANSI X9.44, 2007.
[ANSI, X9.62] American National Standards Institute, Public key cryptography for the financial
services industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), ANSI X9.62,
2005.
[ANSI, X9.63] American National Standards Institute, Public key cryptography for the financial
services industry: Key agreement and key transport using elliptic curve cryptography,
ANSI X9.63, 2001.
[ANSI, X9.71] American National Standards Institute, Keyed hash message authentication code,
ANSI X9.71, 2001.
[Anderson and Biham, 1996] R. Anderson and E. Biham, Tiger: A fast new hash function,
Lecture Notes in Comput. Sci.,1039 (1996), 89-97.
[Bach and Shallit, 1996] E. Bach and J. Shallit, Algorithmic number theory, Volume I: Efficient
algorithms, The MIT Press, Cambridge, MA, 1996.
[Benaloh and de Mare, 1993] J. Benaloh and M. de Mare, One-way accumulators: A
decentralized alternative to digital signatures, Lecture Notes in Comput. Sci., 765 (1993),
274-285.
[Beth and Piper, 1984] T. Beth and F.C. Piper, The Stop-and-Go Generator, Lecture Notes in
Comput. Sci., 209 (1984), 88-92.
[Biham and Shamir, 1993] E. Biham and A. Shamir, Differential cryptanalysis of the full 16-
round DES, Proc. of Crypto’92, Springer Verlag, 1993.
[Biryukov et al., 2000] A. Biryukov, A. Shamir and D. Wagner, Real-Time Cryptanalysis of
A5/1 on a PC, Lecture Notes in Comput. Sci., 1978 (2000), 127-139.
[Biryukov et al. 2009] A. Biryukov, D. Khovratovich, and I. Nikoli, Distinguisher and related-
key attack on the full AES-256, Lecture Notes in Comput. Sci., 5677 (2009), 231-249.
[Blake et al., 1999] I. Blake, G. Seroussi, and N. Smart, Elliptic curves in cryptography,
Cambridge University Press, Cambridge, 1999.
[Blake et al., 2005] I. Blake, G. Seroussi, and N. Smart, Advances in elliptic curve
cryptography., Cambridge University Press, Cambridge, 2005.
[Blakley and Borosh, 1979] G.R. Blakley and I. Borosh, Rivest-Shamir-Adleman public key
cryptosystems do not always conceal messages, Comp. Math. Appl., 5 (1979), no. 3, 169-
178.
[Bleichenbacher and May, 2006] D. Bleichenbacher and A. May, New attacks on RSA with
small secret CRT-exponents, Lecture Notes in Comput. Sci., 3958 (2006), 1-13.
[Blömer and May, 2001] J. Blömer and A. May, Low secret exponent RSA revisited, Lecture
Notes in Comput. Sci., 2146 (2001), 4-19.
[Boneh, 1999] D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices Amer.
Math. Soc., 46 (1999), no. 2, 203-213.
[Boneh and Durfee, 1999] D. Boneh and G. Durfee, Cryptanalysis of RSA with private key d
less tan n0.292, Lecture Notes in Comput. Sci., 1592 (1999), 1-11.
[Boneh and Durfee, 2000] D. Boneh and G. Durfee, Cryptanalysis of RSA with private key d
less tan n0.292. IEEE Trans. Inform. Theory, 46 (2000), no. 4, 1339-1349.
[Boneh and Shacham, 2002] D. Boneh and H. Shacham, Fast variants of RSA, CryptoBytes, 5
(2002), no. 1, 1-9.
[Brainpool, 2005] Brainpool, ECC Brainpool standard curves and curve generation. Ver. 1.0.
2005, http://www.ecc-brainpool.org/download/Domain-parameters.pdf
[Brickell and Odlyzko, 1988] E.F. Brickell and A.M. Odlyzko, Cryptanalysis: A Survey of
Recent Results, Proc. IEEE, 76 (1988), 578-593.
[Buchmann and Williams, 1988] J. Buchmann and H.C. Williams, A key-exchange system based
on imaginary quadratic fields, J. Cryptology 1 (1988), no. 2, 107-118.
[Buhler et al., 1993] J.P. Buhler, H.W. Lenstra, Jr., Carl Pomerance, Factoring integers with the
number field sieve, The development of the number field sieve, Lecture Notes in Math.,
1554 (1993), 50-94.
[Buldas et al., 1998] A. Buldas, P. Laud, H. Lipmaa, and J. Villemson, Time-stamping with
binary linking schemes, Lecture Notes in Comput. Sci., 1462 (1998), 486-501.
[Burrows et al., 1993] M. Burrows, M. Abadi, and R. Needham, A logic Authentication, ACM
Transactions on Computer Systems, 8 (1990), 18-36.
[BSI, 2009] Bundesamt Für Sicherheit in der Informationstechnik (BSI), Elliptic curve
cryptography, version 1.11, TR-03111, 2009.
[Chen et al., 2004] C.Y. Chen, C.Y. Ku, and D. C. Yen, Cryptanalysis of short secret exponents
modulo RSA primes, Inform. Sci., 160 (2004), no. 1-4, 225-233.
[Cheon, 2010], J.H. Cheon, Discrete logarithm problems with auxiliary inputs, J. Cryptology, 23
(2010), 457-476.
[Chmielowiec, 2010] A. Chmielowiec, Fixed points of the RSA encryption algorithm, Theoret.
Comput. Sci., 411 (2010), 288-292.
[Cohen, 1993] H. Cohen, A course in computational algebraic number theory, Springer-Verlag,
Berlin, 1993.
[Cohen et al., 2006] H. Cohen, G. Frey, et al., Handbook of elliptic and hyperelliptic curve
cryptography, Chapman & Hall/CRC, Boca Raton, FL, 2006.
[Coppersmith, 1994] D. Coppersmith, The Shrinking Generator, Lecture Notes in Comput.
Sci.,773 (1994), 22-39.
[Coppersmith et al., 1996] D. Coppersmith, M. Franklin, J. Patarin, and M. Reiter, Low-
exponent RSA with related messages, Lecture Notes in Comput. Sci., 1070 (1996), 1-9.
[Coron and May, 2007] J.S. Coron, A. May, Deterministic polynomial-time equivalence of
computing the RSA secret key and factoring, J. Cryptology, 20 (2007), no. 1, 39-50.
[Daemen and Assche, 2007] J. Daemen and G. van Assche, Producing collisions for Panama,
instantaneously, Lecture Notes in Comput. Sci., 4593 (2007), 1-18.
[Daemen and Clapp, 1998] J. Daemen and C. Clapp, Fast hashing and stream encryption with
Panama, Lecture Notes in Comput. Sci., 1372 (1998), 60-74.
[Damgård, 1990] I. Damgård, A design principle for hash functions, Lecture Notes in Comput.
Sci., 435 (1990), 416-427.
[de Weger, 2002] B. de Weger, Cryptanalysis of RSA with small prime difference, Appl.
Algebra Engrg. Comm. Comput., 13 (2002), no. 1, 17-28.
[Diffie and Hellman, 1976] W. Diffie and M.E. Hellman, New directions in cryptography, IEEE
Trans. Information Theory IT-22 (1976), no. 6, 644-654.
[Diffie et al., 1992] W. Diffie, P. van Oorschot, and M. Wiener, Authentication and
authenticated key exchanges, Des. Codes Cryptography, 2 (1992), 107-125.
[Dobbertin et al., 1996] H. Dobbertin, A. Bosselaers, and B. Preneel, RIPEMD-160: A
strengthened version of RIPEMD, Lecture Notes in Computer Science 1039 (1996), 71–82.
[Dujella, 2009] A. Dujella, A variant of Wiener's attack on RSA, Computing, 85 (2009), 77-83.
[Durfee and Nguyen, 2000] G. Durfee and P.Q. Nguyen, Cryptanalysis of the RSA schemes with
short secret exponent from Asiacrypt '99, Lecture Notes in Comput. Sci., 1976 (2000), 14-
29.
[Durán et al., 2005] R. Durán Díaz, L. Hernández Encinas y J. Muñoz Masqué, El Criptosistema
RSA, RA-MA, Madrid, 2005.
[ECRYPT II, 2009] ECRYPT II - The eSTREAM Portfolio, 2009 Annual Update, 2009.
http://www.ecrypt.eu.org/stream/D.SYM.3-v1.1.pdf
[EFF, 1998] Electronic Frontier Foundation. Cracking DES, O Reily, 1998.
[ElGamal, 1985] T. ElGamal, A public key cryptosystem and a signature scheme based on
discrete logarithms, IEEE Trans. Inform. Theory, 31 (1985), 469-472.
[Enge, 1999] A. Enge, Elliptic curves and their applications to cryptography: An introduction,
Kluwer Academic Publishers, Boston, MA, 1999.
[eSTREAM, 2008] eSTREAM-The ECRYPT Stream Cipher Project, last updated September 8,
2008. http://www.ecrypt.eu.org/stream/
[ETSI, TS-102023] European Telecommunications Standards Institute, Technical Specification
TS 102 023, V1.1.1, Policy requirements for Time-Stamping Authorities, April 2002.
[Luo et al., 2009] P. Luo, H. Zhou, D. Wang, and Y. Dai, Cryptanalysis of RSA for special case
with d > e, Sci. China Ser F-Inf. Sci., 52 (2009), no. 4, 809-616.
[Maitra and Sarkar, 2008] S. Maitra and S. Sarkar, A new class of weak encryption exponents in
RSA, Lecture Notes in Comput. Sci., 5365 (2008), 337-349.
[Marsaglia, 2002] G. Marsaglia, Diehard, a battery of tests for RNGS. http://stat.fsu.edu/
geo/diehard.html, 2002.
[Marsaglia and Tsang, 2002] G. Marsaglia and W.W. Tsang, Some difficult-to-pass tests of
randomness, Journal of Statistical Software, 7, 3 (2002), 1-9.
[Massey, 1969] J.L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. on
Informat Theory, 15 (1969), 122-127.
[Massias and Quisquater, 1997] H. Massias and J. Quisquater, Time and cryptography, Technical
report, TIMESEC project, Université catholique de Louvain, 1-19, 1997.
[Massias et al., 1999] H. Massias, X. Serret, and J. Quisquater, Timestamps: Main issues on their
use and implementation, In Proceedings of IEEE 8th International Workshops on enabling
Technologies (1999), 178-183.
[Matsumoto et al., 1986] T. Matsumoto, Y. Takashima, and H. Imai, On seeking smart public-
key distribution systems, The Transactions of the IECE of Japan, E69 (1986), 99-106.
[Maurer, 1994] U.M. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol
and computing discrete logarithms, Lecture Notes in Comput. Sci., 839 (1994), 271-281.
[Maurer and Wolf, 1996] U.M. Maurer and S. Wolf, Diffie-Hellman oracles, Lecture Notes in
Comput. Sci., 1109 (1996), 268-282.
[Maurer and Wolf, 1999] U.M. Maurer and S. Wolf, The relationship between breaking the
Diffie-Hellman protocol and computing discrete logarithms, SIAM J. Comput., 28 (1999),
no. 5, 1689-1721.
[Maurer and Wolf, 2000] U.M. Maurer and S. Wolf, The Diffie-Hellman protocol. Towards a
quarter-century of public key cryptography, Des. Codes Cryptography, 19 (2000), no. 2-3,
147-171.
[Maurer et al., 2002] M. Maurer, A. Menezes, and E. Teske, Analysis of the GHS Weil descent
attack on the ECDLP over characteristic two finite fields of composite degree, LMS J.
Comput. Math., 5 (2002), 127-174.
[May, 2002] A. May, Cryptanalysis of unbalanced RSA with small CRT-exponent, Lecture
Notes in Comput. Sci., 2442 (2002), 242-256.
[McCurley, 1988] K.S. McCurley, A key distribution system equivalent to factoring, J.
Cryptology 1 (1988), no. 2, 95-105.
[Menezes, 1993] A.J. Menezes, Elliptic curve public key cryptosystems, Kluwer Academic
Publishers, Boston, 1993.
[Menezes and Qu, 2001] A. Menezes and M. Qu, Analysis of the Weil descent attack of Gaudry,
Hess and Smart, Lecture Notes in Comput. Sci., 2020 (2001), 308-318.
[Menezes et al., 1993a] A.J. Menezes (editor), Applications of finite fields, Kluwer Academic
Publishers, Boston, 1993.
[Menezes et al., 1993b] A. Menezes, W. Okamoto, and S. Vanstone, Reducing elliptic curve
logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory, 39 (1993), 1639-
1646.
[Menezes et al., 1995] A. Menezes, M. Qu, and S. Vanstone, Some new key agreement protocols
providing implicit authentication, Proc. of Workshops on Selected Areas in Cryptography
(1995), 22-32.
[Menezes et al., 1997] A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of applied
cryptography, CRC Press, Boca Raton, FL, 1997.
[Merkle, 1979] R. Merkle, Secrecy, authentication, and public key systems, Ph.D. dissertation,
Dept. of Electrical Engineering, Stanford University, 1979.
[Merkle, 1990] R.C. Merkle, One way hash functions and DES, Lecture Notes in Comput.
Sci.,435 (1990), 428-446.
[Miller, 1986] V.S. Miller, Use of elliptic curves in cryptography, Lecture Notes in Comput. Sci.,
218 (1986), 417-426.
[Miller, 1976] G.L. Miller, Riemann's hypothesis and tests for primality, Working papers
presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque,
N.M., 1975), J. Comput. System Sci., 13 (1976), no. 3, 300-317.
[Needham and Schroeder, 1987] R. Needham and M. Schroeder, Using Encryption for
Authentication in Large Networks of Computers, Communications of the ACM, 21 (1987),
7.
[NIST, FIPS46-1] National Institute of Standards and Technology, Data encryption standard,
Federal Information Processing Standard Publication, FIPS 46-1, 1988.
[NIST, FIPS46-2] National Institute of Standards and Technology, Secure hash standard,
Federal Information Processing Standard Publication, FIPS 46-2, 1993.
[NIST, FIPS46-3] National Institute of Standards and Technology, Data encription standard
reafirmed, Federal Information Processing Standard Publication, FIPS 46-3, 1999.
[NIST, FIPS180-1] National Institute of Standards and Technology, Secure hash standard,
Federal Information Processing Standard Publication, FIPS 180-1, 1995.
[NIST, FIPS180-2] National Institute of Standards and Technology, Secure hash standard
(SHS), Federal Information Processing Standard Publication, FIPS 180-2, 2002.
[NIST, FIPS186-2] National Institute of Standards and Technology, Digital signature standard
(DSS), Federal Information Processing Standard Publication, FIPS 186-2, 2000.
[NIST, FIPS186-3] National Institute of Standards and Technology, Digital signature standard
(DSS), Federal Information Processing Standard Publication, FIPS 186-3, 2009.
[NIST, FIPS197] National Institute of Standards and Technology, Advanced Encryption
Standard (AES), Federal Information Processing Standard Publication 197, 2001.
[NIST, FIPS198] National Institute of Standards and Technology, The keyed-hash message
authentication code (HMAC), Federal Information Processing Standard Publication, FIPS
198, 2002.
[NIST, SP800-20] National Institute of Standards and Technology, Modes of operation
validation system for the triple data encryption algorithm (TMOVS): Requirements and
procedures, Special Publication, SP 800-20, 2000.
[NIST, SP800-22] National Institute of Standards and Technology, A Statistical Test Suite for
Random and Pseudorandom Number Generators for Cryptographic Applications, Special
Publication SP 800-22 Revision 1a, 2010.
[NIST, SP800-38A] National Institute of Standards and Technology, Recommendation for block
cipher modes of operation: Methods and techniques, Special Publication, SP 800-38A,
2001.
[NIST, SP800-38B] National Institute of Standards and Technology, Recommendation for block
cipher modes of operation: The CMAC mode for authentication, Special Publication, SP
800-38B, 2005.
[NIST, SP800-38C] National Institute of Standards and Technology, Recommendation for block
cipher modes of operation: The CCM mode for authentication and confidentiality, Special
Publication, SP 800-38C, 2004.
[NIST, SP800-38D] National Institute of Standards and Technology, Recommendation for block
cipher modes of operation: Galois/counter mode (GCM) and GMAC, Special Publication,
SP 800-38D, 2007.
[NIST, SP800-38E] National Institute of Standards and Technology, Recommendation for block
cipher modes of operation: The XTS-AES mode for confidentiality on storage devices,
Special Publication, SP 800-38E, 2010.
[NIST, SP800-57] National Institute of Standards and Technology, Recommendation for key
management–Part 1: General (Revised), Special Publication, SP 800-57, 2007.
[NIST, SP800-57A] National Institute of Standards and Technology, Recommendation for pair-
wise key establishment schemes using discrete logarithm cryptography (Revised), Special
Publication, SP 800-57A, 2007.
[NIST, SP800-67] National Institute of Standards and Technology, Recommendation for the
Triple Data Encryption Algorithm (TDEA) Block Cipher, Special Publication, SP 800-67
Version 1.1, 2008.
[NIST, SHA-3] National Institute of Standards and Technology, Cryptographic hash algorithm
competition, http://csrc.nist.gov/groups/ST/hash/sha-3/index.html
[NSA, SuiteB] National Security Agency, Suite B cryptography, 2005.
[Nyberg and Rueppel, 1995] K. Nyberg and R. Rueppel, Message recovery for signature
schemes based on the discrete logarithm problem, Lecture Notes in Comput. Sci., 950
(1995), 182-193.
[Okeya and Takagi, 2006] K. Okeya and T. Takagi, Security analysis of CRT-based
cryptosystems, Int. J. Inf. Secur., 5 (2006), no. 3, 177-185.
[Otway and Rees, 1987] D. Otway and O. Rees, Efficient and Timely Mutual Authentication,
Operating Systems Review, 21 (1987), 8-10.
[Peterson and Brown, 1961] W.W. Peterson and D.T. Brown, Cyclic codes for error detection,
Proceedings of the IRE, 49 (1961), no. 1, 228-235.
[Pinkas et al., 2003] D. Pinkas, N. Pope, and J. Ross, Requirements for Time-Stamping
Authorities, Request for Comments RFC 3628, 2003.
[Pohlig and Hellman, 1978] S.C. Pohlig and M.E. Hellman, An improved algorithm for
computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inform.
Theory, IT-24 (1978), 106-110
[Pollard, 1974] J.M. Pollard, Theorems on factorization and primality testing, Math. Proc.
Cambridge Philos. Soc., 76 (1974), 521-528.
[Quisquater and Couvreur, 1982] J.J. Quisquater and J.M. Couvreur, Fast decipherment
algorithm for RSA public-key cryptosystem, Electron. Lett., 17 (1982), no. 21, 905-907.
[Rijmen et al., 2002] V. Rijmen, B. van Rompay, B. Preneel, and J. Vandewalle, Producing
collisions for Panama, Lecture Notes in Comput. Sci., 2355 (2002), 259-275.
[Rivest, 1991] R.L. Rivest, The MD4 message digest algorithm, Lecture Notes in Comput. Sci.,
537 (1991), 303-311.
[Rivest, 1992] R.L. Rivest, RFC 1321: The MD5 message-digest algorithm, Internet Request for
Comments 1321, April, 1992, Rump session of Crypto'91.
[Rivest et al., 1978] R.L. Rivest, A. Shamir, and L.M. Adleman, A method for obtaining digital
signatures and public-key cryptosystems, Commun. ACM, 21 (1978), no. 2, 120-126.
[RSALab, 1993] RSA Laboratories, PKCS #3, Diffie-Hellman key agreement standard, version
1.4, 1993. http://www.rsa.com/rsalabs/node.asp?id=2126
[RSALab, 2002] RSA Laboratories, PKCS #3, RSA cryptography standard, version 2.1, 2002.
http://www.rsa.com/rsalabs/node.asp?id=2125.
[Rueppel and Oorschot, 1994] R. Rueppel and P. van Oorschot, Modern key agreement
techniques, Comput. Commun., 17 (1994), 458-465.
[Salomaa, 1990] A. Salomaa, Public-key cryptography, Springer-Verlag, EATCS Monographs
on Theoretical Computer Science, 23, Springer-Verlag, Berlin, 1990.
[Sarkar and Maitra, 2009a] S. Sarkar and S. Maitra, Further results on implicit factoring in
polynomial time, Adv. Math. Commun., 3 (2009), no. 2, 205-217.
[Sarkar and Maitra, 2009b] S. Sarkar and S. Maitra, Partial key exposure attacks on RSA and its
variant by guessing a few bits of one of the prime factors, Bull. Korean Math. Soc., 46
(2009), no. 4, 721-741.
[Sarkar and Maitra, 2010] S. Sarkar and S. Maitra, Cryptanalysis of RSA with two encryption
exponents, Inf. Processing Lett., 10 (2010), 178-181.
[Satoh and Araki, 1998] T. Satoh and K. Araki, Fermat quotients and the polynomial time
discrete log algorithm for anomalous elliptic curves, Comment. Math. Univ. St. Paul, 47
(1998), 81-92.
[Semaev, 1998] I.A. Semaev, Evaluation of discrete logarithms in a group of p-torsion points of
an elliptic curve in characteristic p, Math. Comp., 67 (1998), 353-356.
[Sgarro, 1990] A. Sgarro, Códigos Secretos, Editorial Pirámide, Madrid, 1990.
[Shannon, 1949] C.E. Shannon, Communication theory of secrecy systems, Bell. Syst. Tech. J.,
28 (1949), 656-715.
[Silverman, 1994] J.H. Silverman, Advanced topics in the arithmetic of elliptic curves, Springer-
Verlag, New York, 1994.
[Silverman, 2009] J.H. Silverman, The arithmetic of elliptic curves, 2nd ed., Springer-Verlag,
New York, 2009.
[Smart, 1999] N.P. Smart, The discrete logarithm problem on elliptic curves of trace one, J.
Cryptology, 12 (1999), 193-196.
[Simpson et al, 1998] L. Simpson, J. Golic and E. Dawson, Correlation Attack on the Shrinking
Generator, Lecture Notes in Comput. Sci.,1438 (1998), 147-158.
[SECG, SEC1] Standards for Efficient Cryptography Group, SEC 1: Elliptic curve cryptography,
version 2.0, 2009. http://www.secg.org/download/aid-773/sec1_1point9.pdf
[Stinson, 2006] D.R. Stinson, Cryptography: Theory and practice, Chapman & Hall/CRC, 3rd
ed., Boca Raton, FL, 2006.
[Sun and Wu, 2005] H.M. Sun and M.E. Wu, Design of rebalanced RSA-CRT for fast
encryption, Proc. of Information Security Conference, 2005, pp. 16-27.
[Sun et al., 2005] H.M. Sun, J. Hinek, and M.E. Wu, On the design of rebalanced RSA-CRT,
Technical Report CACR 2005-35, University of Waterloo.
[Tilborg, 1988] H.C. Tilborg, An Introduction to Cryptology, Kluwer Academic Publisher,
Boston, 1988.
[Trivium, 2008] The eSTREAM Project, eSTREAM Phase 3 Stream Cipher, Trivium, 2008.
http://www.ecrypt.eu.org/stream/triviump3.html
[Verheul and van Tilborg, 1997] E.R. Verheul and H.C.A. van Tilborg, Cryptanalysis of “less
short” RSA secret exponents, Appl. Algebra Engrg. Comm. Comput., 8 (1997), no. 5, 425-
435.
[Wang et al., 2004] X. Wang, D. Feng, X. Lai, and H. Yu, Collisions for hash functions MD4,
MD5, HAVAL-128 and RIPEMD, http://eprint.iacr.org/2004/199.pdf, 2004.
[Wang et al., 2005] X. Wang, Y.L. Yin, and H. Yu, Finding collisions in the full SHA-1, Lecture
Notes in Comput. Sci., 3621 (2005), 17-36.
[Wang and Yu, 2005] X. Wang and H. Yu, How to break MD5 and other hash functions, Lecture
Notes in Comput. Sci., 3494 (2005), 19-35.
[Wang et al., 2004] X. Wang, D. Feng, X. Lai, and H. Yu, Collisions for Hash Functions MD4,
MD5, HAVAL-128 and RIPEMD http://eprint.iacr.org/2004/199.pdf, 2004.
[Wiener, 1990] M.J. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Trans. Inform.
Theory, 36 (1990), no. 3, 553-558.
[Williams, 1982] H.C. Williams, A p+1 method of factoring, Math. Comp., 39 (1982), no. 159,
225-234.