Captulo 1- Fundamentos

1.1 Terminologa.
Emisor y receptor
Supongamos que un remitente desea enviar un mensaje a un receptor. Por otra parte, este remitente desea enviar el mensaje de forma segura: Ella quiere asegurarse de que un intruso no pueda leer el mensaje.

Los mensajes y el cifrado

Un mensaje es texto plano (a veces llamado texto limpio). El proceso de disfrazar un mensaje de tal manera como para ocultar su contenido es el cifrado. Un mensaje cifrado es texto cifrado. El proceso de convertir texto cifrado de nuevo en texto plano es descifrado. Todo esto se muestra en la figura 1,1. (Si quieres seguir la norma ISO 7498-2, utilice los trminos "cifrar" y "descifrar." Parece que algunas culturas encontramos los trminos "cifrar" y "descifrar como ofensivo, ya que se refieren a los cadveres.) El arte y la ciencia de mantener mensajes seguros es la criptografa, y es practicada por los criptgrafos. Criptoanalistas son practicantes de criptoanlisis, el arte y la ciencia de romper cifrado, es decir, ver a travs del disfraz. La rama de las matemticas que abarca la criptografa y el criptoanlisis es la criptologia y sus practicantes son criptlogos. Criptlogos actuales suele estar formado en las matemticas tericas-que tiene que ser.

Figura 1.1 Cifrado y descifrado. El texto plano se denota por M, para el mensaje, o P, para texto plano. Puede ser una secuencia de bits, un archivo de texto, un mapa de bits, un flujo de voz digitalizada, una imagen de vdeo digital... lo que sea. Por lo que un ordenador se refiere, M es simplemente datos binarios. (Despus de este captulo, este libro se ocupa de los datos binarios y criptografa ordenador.) El texto completo puede ser destinado a una transmisin o almacenamiento. En cualquier caso, M es el mensaje a cifrar. Texto cifrado se denota por C. Es tambin datos binarios: a veces el mismo tamao que M, a veces ms grande. (Mediante la combinacin de encriptacin con la compresin, C puede ser menor que M. Sin embargo, el cifrado no logra esto.) La funcin de cifrado E, opera en M para producir C o, en notacin matemtica: E (M) = C En el proceso inverso, la funcin de descifrado D opera en C para producir M: D (C) = M

Desde el punto de cifrar y descifrar un mensaje entonces es recuperar el texto plano original, la siguiente identidad de ser verdaderas: D (E (M)) = M

Autenticacin, integridad y no repudio

Adems de proporcionar la confidencialidad, la criptografa se pregunta a menudo para hacer otros trabajos: - Autenticacin. Debe ser posible para el receptor de un mensaje para averiguar su origen; un intruso no debera ser capaz de hacerse pasar por otra persona. - Integridad. Debe ser posible para el receptor de un mensaje para verificar que no se ha modificado en trnsito; un intruso no debera ser capaz de sustituir un mensaje falso de una legtima. - No repudio. Un remitente no debera ser capaz de negar falsamente que ms tarde le envi un mensaje. Estos son requisitos indispensables para la interaccin social en los ordenadores, y son anlogas a las interacciones cara a cara. Ese alguien es quien dice ser... esas credenciales son de alguien, ya sea licencia de conducir, un ttulo de mdico, o un pasaporte... son vlidos... que un documento que pretende provenir de una persona en realidad procedan de esa persona. Estas son las cosas que la autenticacin, integridad y no repudio proporcionan.

Los algoritmos y claves

Un algoritmo criptogrfico, tambin llamado un sistema de cifrado, es la funcin matemtica utilizada para el cifrado y el descifrado. (En general, hay dos funciones relacionadas: uno para el cifrado y la otra para el descifrado) Si la seguridad de un algoritmo se basa en el mantenimiento de la forma en que funciona el algoritmo de un secreto, es un algoritmo restringido. Los algoritmos restringidos tienen inters histrico, pero son completamente inadecuados para los estndares de hoy. Un grupo grande o cambiante de los usuarios no pueden utilizarlo, ya que cada vez que un usuario deja el grupo todos lo dems debe cambiar a un algoritmo diferente. Si alguien accidentalmente revela el secreto, todo el mundo debe cambiar su algoritmo. An ms condenatorios, algoritmos restringidos no permita el control de calidad y la normalizacin. Cada grupo de usuarios debe tener su propio algoritmo nico. Ese grupo no puede utilizarlo por fuera de la plataforma de productos de hardware o de software, un fisgn puede comprar el mismo producto y conocer el algoritmo. Ellos tienen que escribir sus propios algoritmos e implementaciones. Si no hay nadie en el grupo que sea un buen criptgrafo, entonces ellos no saben si tienen un algoritmo seguro. A pesar de estos inconvenientes importantes, los algoritmos restringidos son muy populares para aplicaciones de baja seguridad. Los usuarios no se dan cuenta o no se preocupan por los problemas de seguridad inherentes a su sistema.

La criptografa moderna resuelve este problema con una clave, denotada por K. Esta clave puede ser cualquiera de un gran nmero de valores. El rango de posibles valores de la clave se llama el espacio de claves. Tanto el cifrado y las operaciones de descifrado, utilizan esta clave (es decir, son dependientes de la clave y este hecho es denotado por el subndice k), por lo que las funciones que ahora se convierten en:

EK(M) = C DK(C) = M
Esas funciones tienen la propiedad de que (vase la Figura 1.2):

DK(EK(M)) = M
Algunos algoritmos utilizan una clave de cifrado y clave de descifrado diferente (vase la figura 1,3). Es decir, la clave de cifrado, K1, es diferente de la clave de descifrado correspondiente, K2. En este caso:

EK1(M) = C DK2(C) = M DK2(EK1 (M)) = M

Todos lo referente a la seguridad en estos algoritmos se basa en la clave (o claves), ninguno se basa en los detalles del algoritmo. Esto significa que el algoritmo puede ser publicado y analizado. Los productos que utilizan el algoritmo pueden ser producidos en masa. No importa si un espa conoce su algoritmo; si no sabe cual es su clave privada, no puede leer sus mensajes.

Figura 1.2 cifrado y descifrado con una clave.

Figura 1.3 Cifrado y descifrado con dos claves diferentes. Un criptosistema es un algoritmo, adems de todos los posibles textos planos, textos cifrados y claves.

Algoritmos simtricos
Hay dos tipos generales de algoritmos basados en clave: simtricos y de clave pblica. Los algoritmos simtricos, a veces llamados algoritmos convencionales, son algoritmos donde el cifrado de la clave puede ser calculada a partir de la clave de descifrado y viceversa. En la mayora de los algoritmos simtricos, la clave de cifrado y la clave de descifrado son la misma. Estos algoritmos, tambin llamados algoritmos de clave secreta, algoritmos de clave simple, o algoritmos de una sola clave, requieren que el remitente y el receptor acuerden sobre una clave antes de que puedan comunicarse de forma segura. La seguridad de un algoritmo simtrico descansa en la clave; divulgar la clave significa que cualquier persona puede cifrar y descifrar mensajes. Siempre y cuando la comunicacin tiene que mantenerse en secreto, la clave debe permanecer en secreto. El cifrado y descifrado con un algoritmo simtrico se denotan por:

EK(M) = C DK(C) = M
Los algoritmos simtricos se pueden dividir en dos categoras. Algunas de ellas actan en el texto plano de un nico bit (o, a veces byte) a la vez; estos son llamados algoritmos de cifrados de flujo o corriente. Otros operan en el texto plano en grupos de bits. Los grupos de bits se denominan bloques, y los algoritmos se llaman algoritmos de bloque o sistemas de cifrado de bloque. Para los algoritmos de ordenador modernos, un tamao de bloque tpico es 64 bits-lo suficientemente grande como para excluir el anlisis y lo suficientemente pequeo como para ser viable. (Antes de las computadoras, los algoritmos funcionan generalmente en texto plano, un carcter a la vez. Usted puede pensar en esto como un algoritmo operativo corriente en un flujo de caracteres.)

Algoritmos de clave pblica

Algoritmos de clave pblica (tambin llamados algoritmos asimtricos) estn diseados de manera que la clave utilizada para el cifrado es diferente de la clave utilizada para el descifrado. Adems, la clave de descifrado no puede (al menos en una cantidad razonable de tiempo) se calcula a partir de la clave de cifrado. Los algoritmos se denominan "clave pblica", porque la clave de cifrado se puede hacer pblico: un completo extrao puede utilizar la clave de cifrado para cifrar un mensaje, pero slo una persona especfica con la clave de descifrado correspondiente puede descifrar el mensaje. En estos sistemas, la clave de cifrado se llama a menudo la clave pblica, y la clave de descifrado se llama a menudo la clave privada. La clave privada es conocida tambin como la clave secreta, pero para evitar la confusin con los algoritmos simtricos, esa etiqueta no se utilizar aqu. El cifrado usando la clave pblica K se representa por:

EK(M) = C
A pesar de que la clave pblica y la clave privada son diferentes, el descifrado con la clave privada correspondiente se representa por:

DK(C) = M
A veces, los mensajes se cifran con la clave privada y descifrar con la clave pblica, lo que se utiliza en las firmas digitales (ver seccin 2.6). A pesar de la posible confusin, estas operaciones son denotadas por, respectivamente:

EK(M) = C DK(C) = M Criptoanlisis

El punto entero de la criptografa es mantener el texto claro (o la clave, o ambos) en secreto para los espas (tambin llamado adversarios, atacantes, interceptores, entrometidos, intrusos, adversarios, o simplemente el enemigo). Los fisgones suponen que tienen un acceso completo a las comunicaciones entre el remitente y el receptor. El Criptoanlisis es la ciencia de recuperar el texto plano de un mensaje sin acceso a la clave. El Criptoanlisis exitoso puede recuperar el texto plano o la clave. Tambin puede encontrar puntos dbiles en un sistema de cifrado que pueden dar lugar a los resultados anteriores. (La prdida de una llave a travs de medios noncryptanalytic se llama un compromiso.) Un intento de criptoanlisis es llamado un ataque. Una suposicin fundamental en criptoanlisis, enunciada por primera vez por los Kerckhoffs holands A. en el siglo XIX, es que el secreto debe residir en su totalidad en la clave [794]. Kerckhoffs supone que el Criptoanalista tiene todos los detalles del algoritmo criptogrfico e implementacion. (Por supuesto, uno puede pensar que la CIA no tiene el hbito de decir Mossad sobre sus algoritmos criptogrficos, pero Mossad probablemente se entera de todos modos.) Mientras que en el mundo real Criptoanalista no siempre tienen informacin tan detallada, es una buena suposicin para hacer. Si los dems no pueden romper un algoritmo, incluso con el conocimiento de cmo funciona, entonces ciertamente no ser capaz de romperlo sin ese conocimiento. Hay cuatro tipos generales de ataques criptogrficos. Por supuesto, cada uno de ellos se supone que el Criptoanalista tiene pleno conocimiento del algoritmo de cifrado utilizado: 1. Ataque slo a texto cifrado. El Criptoanalista tiene el texto cifrado de varios mensajes, los cuales todos han sido cifrados usando el mismo algoritmo de cifrado. El trabajo del Criptoanalista es recuperar el texto en claro de tantos mensajes como sea posible, o mejor an, para deducir la tecla (o teclas) que se utiliza para cifrar los mensajes, con el fin de descifrar los mensajes cifrados con otros que tengan las mismas teclas. Dado: C1 = Ek (P1), C2 = Ek (P2),...Ci = Ek (Pi) Deducir: cualquiera de los dos P1, P2,...Pi; k; o un algoritmo para inferir Pi+1 de Ci+1 = Ek(Pi+1)

2. Ataque a texto plano conocido. El Criptoanalista tiene acceso no solo al texto cifrado de varios mensajes, sino tambin al texto plano de esos mensajes. Su trabajo consiste en deducir la llave (o llaves) que se utilizan para cifrar los mensajes, o un algoritmo para descifrar los mensajes nuevos cifrados con la misma clave (o teclas). Dado: P1, C1 = Ek (P1), P2, C2 = Ek (P2), ... Pi, Ci = Ek (Pi) Deducir: O k, o un algoritmo para inferir Pi +1 de Ci +1 = Ek (Pi +1) 3. Ataque a texto plano elegido. El Criptoanalista no slo tiene acceso al texto cifrado y texto claro asociado para varios mensajes, pero tambin elige el texto plano que se cifrara. Esto es ms poderoso que un ataque de texto plano conocido, porque el Criptoanalista puede elegir bloques especficos para cifrar texto plano, los que podran producir ms informacin acerca de la clave. Su trabajo consiste en deducir la clave (o claves) que se utilizan para cifrar los mensajes, o un algoritmo para descifrar los mensajes nuevos cifrados con la misma clave (o teclas). Dado: P1, C1 = Ek (P1), P2, C2 = Ek (P2), ... Pi, Ci = Ek (Pi), donde el criptoanalista tiene que elegir P1, P2, ... Pi Deducir: O k, o un algoritmo para inferir Pi +1 de Ci +1 = Ek (Pi +1) 4. Ataque adaptativo de texto plano escogido. Este es un caso especial de un ataque de texto plano escogido. No slo puede el Criptoanalista elegir el texto claro que esta encriptado, pero tambin puede modificar su eleccin en base a los resultados de cifrado anterior. En un ataque de texto plano escogido, un Criptoanalista podra ser capaz de elegir un gran bloque de texto claro a cifrar; en un ataque adaptativa de texto plano escogido se puede elegir un bloque ms pequeo de texto claro y luego elegir otro basado en los resultados de la primero, y as sucesivamente. Hay al menos otros tres tipos de ataque de criptoanlisis. 5. Ataque de texto cifrado elegido. El Criptoanalista puede elegir diferentes textos cifrados a ser descifrados y tiene acceso al texto normal descifrado. Por ejemplo, el Criptoanalista tiene acceso a una caja a prueba de manipulaciones que hace el descifrado automtico. Su trabajo consiste en deducir la clave. Dado: C1, P1 = Dk (C1), C2, P2 = Dk (C2), ... Ci, Pi = Dk (Ci) Deducir: k Este ataque es principalmente aplicable a los algoritmos de clave pblica y se discuten en la Seccin 19,3. Un ataque de texto cifrado elegiido es a veces eficaz contra un algoritmo simtrico tambin. (A veces un ataque de texto plano escogido y un ataque del texto cifrado elegido son conocidos en conjunto como un ataque de texto elegido) 6. Ataque de clave elegida. Este ataque no significa que el Criptoanalista puede elegir la clave, sino que significa que tiene algn conocimiento acerca de la relacin entre diferentes claves. Es extrao y oscuro, no muy prctico, y se discuten en la Seccin 12.4. 7. Criptoanlisis manguera de goma. El Criptoanalista amenaza, chantajea, tortura alguien hasta que le diera la llave. Soborno se refiere a veces como un ataque de comprar la clave. Estos son todos los ataques muy poderosos y, a menudo la mejor manera de romper un algoritmo.

El ataque a texto plano conocido y ataque de texto plano escogido es ms comn de lo que se piensa. No es inaudito para un Criptoanalista que para obtener un mensaje de texto que ha sido cifrado sobornar a alguien para cifrar un mensaje elegido. Puede que ni siquiera tienen que sobornar a alguien, si se le da un mensaje a un embajador, usted probablemente encontrar que se cifran y se enva de vuelta a su pas para su consideracin. Muchos mensajes tienen un estndar de iniciacin y finalizacin que pueden ser conocidos por el Criptoanalista. El cdigo fuente cifrado es especialmente vulnerable debido a la aparicin regular de las palabras clave: # define, struct, else, return. El cdigo ejecutable cifrado tiene los mismos tipos de problemas: funciones, estructuras de bucle, y as sucesivamente. El texto plano conocido (e incluso los ataques de texto plano escogido) fueron utilizados con xito contra los alemanes y los japoneses durante la Segunda Guerra Mundial. Libro de David Kahn [794795796] tenemos ejemplos histricos de este tipo de ataques. Y no olvidarnos de la suposicin de Kerckhoffs: si la fuerza de su nuevo sistema de cifrado se basa en el hecho de que el atacante no conoce el funcionamiento interno del algoritmo, ests hundido. Si usted cree que mantener en secreto el funcionamiento interno del algoritmo mejora la seguridad de su sistema criptogrfico es mejor que dejar que la comunidad acadmica lo analice, te equivocas. Y si usted piensa que alguien no va a desmontar el cdigo y aplicara la ingeniera inversa de su algoritmo, eres ingenuo. (En 1994 esto sucedi con el algoritmo RC4 - vase la seccin 17.1.) Los mejores algoritmos que tenemos son los que se han hecho pblicos, los cuales han sido atacados por los mejores criptgrafos del mundo durante aos, y siguen siendo inquebrantable. (La Agencia de Seguridad Nacional mantiene en secreto sus algoritmos de los forasteros, pero tienen los mejores criptgrafos del mundo que trabajan dentro de sus paredes, no es as. Adems, discuten sus algoritmos entre s, apoyndose en la revisin por pares para descubrir los puntos dbiles en su trabajo.) Los Criptoanalistas no siempre tienen acceso a los algoritmos, como cuando los Estados Unidos rompieron el cdigo diplomtico japons PURPLE durante la Segunda Guerra Mundial [794], pero a menudo lo hacen. Si el algoritmo est siendo utilizado en un programa de seguridad comercial, es simplemente una cuestin de tiempo y dinero para desmontar el programa y recuperar el algoritmo. Si el algoritmo est siendo utilizado en un sistema de comunicaciones militares, es simplemente una cuestin de tiempo y dinero para comprar (o robar) el equipo y aplicarle la ingeniera inversa al algoritmo. Los que afirman tener un sistema de cifrado irrompible, simplemente porque no se puede romper son genios o los locos. Desafortunadamente, hay ms de estos ltimos en el mundo. Tenga cuidado con las personas que ensalzan las virtudes de sus algoritmos, pero se niegan a hacerlos pblicos, confiando en sus algoritmos es como el aceite de serpiente confianza. Los buenos Criptgrafos cuentan con revisin por pares para separar los buenos algoritmos de los malos.

Seguridad de los Algoritmos

Diferentes algoritmos ofrecen diferentes grados de seguridad, eso depende de la fuerza con que se quiebren. Si el costo necesario para romper un algoritmo es mayor que el valor de los datos cifrados, entonces usted est probablemente seguro. Si el tiempo necesario para romper un algoritmo es ms largo que el tiempo de los datos cifrados deben mantenerse en secreto, entonces usted est probablemente seguro. Si la cantidad de datos cifrados con una clave nica es menor que la cantidad de datos necesarios para romper el algoritmo, entonces usted est probablemente seguro. Digo "probablemente" porque siempre hay una posibilidad en los nuevos avances en criptoanlisis. Por otra parte, el valor de la mayora de los datos se reduce con el tiempo. Es importante que el valor de los datos permanecen siempre menor que el costo de romper la seguridad de la proteccin de la misma. Lars Knudsen clasificado estas diferentes categoras de romper un algoritmo. En orden decreciente de gravedad [858]: 1. Total descanso. Un Criptoanalista encuentra la clave, K, de tal manera que DK (C) = P. 2. Deduccin global. Un Criptoanalista encuentra un algoritmo alternativo, A, equivalente a DK (C), sin saber K. 3. Instancia (o local) deduccin. Un Criptoanalista encuentra el texto claro de un texto cifrado interceptado. 4. Deduccin de la informacin. Un Criptoanalista gana un poco de informacin acerca de la clave o texto plano. Esta informacin podra ser unos pocos bits de la clave, algo de informacin sobre la forma del texto plano, y as sucesivamente. Un algoritmo es incondicionalmente seguro si, no importa cunto texto cifrado de un Criptoanalista tiene, no hay informacin suficiente para recuperar el texto en claro. De hecho, slo un one-time pad (ver seccin 1.5) es irrompible con los recursos infinitos. Todos los Criptosistemas de otros son frgiles en un ataque de texto cifrado slo, simplemente por tratar cada una de las claves posible por uno y comprobar si el texto claro resultante es significativo. Esto se conoce como un ataque de fuerza bruta (ver seccin 7.1). La criptografa est ms preocupada por los Criptosistemas que son computacionalmente imposibles de romper. Un algoritmo es considerado computacionalmente seguro (a veces llamado fuerte) si no se puede romper con los recursos disponibles, corrientes o futuras. Exactamente lo que constituye "recursos disponibles" est abierto a la interpretacin. Se puede medir la complejidad (ver seccin 11.1) de un ataque de diferentes maneras: 1. Complejidad en los datos. La cantidad de datos necesarios como entrada para el ataque. 2. Complejidad en el procesamiento. El tiempo necesario para realizar el ataque. Esto a menudo se llama el factor trabajo.

3. Los requisitos de almacenamiento. La cantidad de memoria necesaria para realizar el ataque. Como regla general, la complejidad de un ataque es tomado para ser el mnimo de estos tres factores. Algunos ataques implican la negociacin fuera de los tres complejidades: un ataque ms rpido podra ser posible a expensas de un requisito de almacenamiento mayor. Complejidades se expresan como rdenes de magnitud. Si un algoritmo tiene una complejidad de procesamiento de 2128, entonces las operaciones de 2128 se requieren para romper el algoritmo. (Estas operaciones pueden ser complejas y requieren mucho tiempo.) Sin embargo, si se asume que tiene suficiente velocidad para realizar el clculo de un milln de operaciones por segundo y se establece un milln de procesadores paralelos en contra de la tarea, todava se har cargo de 1019 aos para recuperarse la clave. Eso es mil millones de veces la edad del universo. Aunque la complejidad de un ataque es constante (hasta que algn Criptoanalista encuentra un mejor ataque, por supuesto), potencia de clculo es todo lo contrario. Ha habido avances fenomenales en potencia de clculo durante el ltimo medio siglo y no hay razn para pensar que esta tendencia no continuar. Muchos ataques criptogrficos son perfectos para las mquinas paralelas: La tarea puede ser dividida en miles de millones de pequeos pedazos y ninguno de los procesadores necesitan interactuar unos con otros. Pronunciando un algoritmo de seguridad, simplemente porque es imposible de romper, dada la tecnologa actual, es incierto en el mejor. Buenas Criptosistemas estn diseados para ser factible para romper con el poder de cmputo que se espera que evolucione desde hace muchos aos en el futuro.

Condiciones histricas
Histricamente, el cdigo se refiere a un sistema de cifrado que se ocupa de las unidades lingsticas: palabras, frases, oraciones, etc. Por ejemplo, la palabra "Ocelot" podra ser el texto cifrado para toda la frase "giro a la izquierda 90 grados," la palabra "LOLLIPOP" podra ser el texto cifrado para "girar a la derecha 90 grados", y las palabras "BENT EAR" podra ser el texto cifrado para "HOWITZER " los cdigos de este tipo no se tratan en este libro, ver [794.795]. Los cdigos son slo tiles para circunstancias especiales. Los cifrados son tiles para cualquier circunstancia. Si el cdigo no tiene una entrada para "oso hormiguero", entonces no se puede decir. Se puede decir cualquier cosa con una cifra.

1.2 Steganography
La Esteganografa sirve para ocultar mensajes secretos en otros mensajes, de modo que el secreto de la existencia misma est oculto. En general, el remitente escribe un mensaje inocuo y luego oculta un mensaje secreto en el mismo pedazo de papel. Trucos histricos incluyen tintas invisibles, pinchazos de pequeos pines en caracteres seleccionados, las diferencias de minutos entre caracteres escritos a mano, marcas de lpiz en caracteres mecanografiados, rejillas que cubren la mayor parte del mensaje de excepcin de unos pocos caracteres, etc.

Ms recientemente, las personas esconden mensajes secretos en las imgenes grficas. Sustituir el bit menos significativo de cada byte de la imagen con los bits del mensaje. La imagen grfica no cambiar apreciablemente, la mayora de los estndares grficos especifican ms gradaciones de color que el ojo humano puede notar, y el mensaje puede ser despojado a cabo en el extremo receptor. Puede almacenar un mensaje de 64 kilobyte en una resolucin de 1024 1024 en una imagen de escala de grises de esta manera. Varios programas de dominio pblico hacen este tipo de cosas. Peter Wayner imitan las funciones de ofuscar mensajes. Estas funciones modifican un mensaje de modo que su perfil estadstico se asemeja a la de otra cosa: la seccin de clasificados del time de Nueva York, una obra de teatro de Shakespeare, o un grupo de noticias en Internet [1584,1585]. Este tipo de Esteganografa no va a engaar a una persona, pero puede engaar a algunos equipos grandes de exploracin de Internet para mensajes interesantes.

1.3 Cifrado por sustitucin y cifrado por transposicin.

Antes de las computadoras, la criptografa consiste en algoritmos basados en caracteres. Diferentes algoritmos criptogrficos o bien sustituido por caracteres uno por el otro o transpuesto caracteres uno con el otro. Los mejores algoritmos hicieron ambos cosas, muchas veces cada uno. Las cosas son ms complejas en estos das, pero la filosofa sigue siendo la misma. El cambio principal es que los algoritmos funcionan sobre los bits en lugar de caracteres. En realidad es un cambio en el tamao del alfabeto: a partir de 26 elementos a dos elementos. Algoritmos criptogrficos mayora de los buenos todava combinan elementos de sustitucin y transposicin.

Cifrado por sustitucin

Un sistema de cifrado por sustitucin es aquella en la que se sustituye cada carcter en el texto plano por otro caracter en el texto cifrado. El receptor invierte la sustitucin en el texto cifrado para recuperar el texto plano. En la criptografa clsica, existen cuatro tipos de cdigos de sustitucin: - Un cifrado por sustitucin simple, o en cifra mono alfabtico, es uno en el que se sustituye cada carcter del texto en claro con un carcter correspondiente de texto cifrado. Los criptogramas en los peridicos son simples cifrado por sustitucin. - Un cifrado por sustitucin homofnica, es como un sistema de cifrado por sustitucin simple, salvo que un solo carcter de texto plano puede asignar uno de varios caracteres de texto cifrado. Por ejemplo, "A" puede corresponder a cualquiera de 5, 13, 25, o 56, "B" puede corresponder a cualquiera de 7, 19, 31, o 42, y as sucesivamente. - Un cifrado por sustitucin poligrmico, es uno en el que los bloques de caracteres se codifican en grupos. Por ejemplo, "ABA" podra corresponder a "RTQ", "ABB" podra corresponder a "SLL", y as sucesivamente. - Un cdigo por sustitucin polialfabtico, se compone de mltiples cdigos de sustitucin simples. Por ejemplo, podra ser de cinco cifras distintas de sustituciones

sencillas utilizadas, Una partcula usada cambia con la posicin de cada carcter del texto en claro. El famoso cifrado de Cesar, en la que se sustituye cada carcter del texto claro por la de tres caracteres a la derecha modulo 26 ("A" se sustituye por "D", "B" se sustituye por "E",..., "W" es sustituyen por "Z", "X" se sustituye por "A", "Y" se sustituye por "B" y "Z" se sustituye por "C") es un cifrado de sustitucin simple. De hecho, es incluso ms simple, debido a que el alfabeto de texto cifrado es una rotacin del alfabeto de texto claro y no es una permutacin arbitraria. ROT13 es un programa de encriptacin simple comnmente encontrado en los sistemas UNIX, sino que tambin es un cifrado de sustitucin simple. De esta cifra, "A" se sustituye por "N", "B" se sustituye por "O", y as sucesivamente. Cada letra se gira 13 plazas. Cifrar un archivo dos veces con ROT13 restaura el archivo original. P = ROT13 (ROT13 (P)) ROT13 no est diseado para la seguridad, sino que se utiliza a menudo en mensajes de Usenet para ocultar el texto potencialmente ofensivo, para evitar dar la solucin a un rompecabezas, y as sucesivamente. El Sistemas de cifrado por sustitucin simple puede romperse con facilidad debido a que el cifrado no oculta las frecuencias fundamentales de las distintas letras del texto plano. Todo lo que toma es de 25 caracteres en ingls ante un buen Criptoanalista puede reconstruir el texto plano [1434]. Un algoritmo para resolver este tipo de sistemas de cifrado se pueden encontrar en [578, 587, 1600, 78, 1475, 1236,880]. Es un buen algoritmo de computadora [703]. El Sistemas de cifrado por sustitucin homofnica ya fue utilizado en 1401 por el Ducado de Mantua [794]. Son mucho ms difciles de romper que los cifrados por sustitucin simple, pero todava no oscurecen todas las propiedades estadsticas del lenguaje de texto plano. Con un ataque de texto plano conocido, las cifras son triviales de romper. Un ataque de texto cifrado slo es ms difcil, pero slo tarda unos segundos en un ordenador. Los detalles se encuentran en [1261]. El cifrado por sustitucin poligramico es cifrado en los que grupos de letras se cifran juntos. La cifra de Playfair, inventado en 1854, fue utilizado por los britnicos durante la Primera Guerra Mundial [794]. Cifra pares de letras. Su criptoanlisis se discute en [587, 1475,880]. La cifra Hill es otro ejemplo de un cifrado de sustitucin Polygram [732]. A veces ves Huffman utilizado como un sistema de cifrado, este es un sistema de cifrado por sustitucin Polygram inseguro. Los Sistemas de cifrado por sustitucin polialfabticos fueron inventados por Leon Battista en 1568 [794]. Ellos fueron utilizados por el ejrcito de la Unin durante la Guerra Civil Americana. A pesar del hecho de que pueden romperse fcilmente [819, 577, 587, 794] (especialmente con la ayuda de ordenadores), muchos productos comerciales de seguridad informtica utilizan este sistemas de cifrado de esta forma [1387, 1390,1502]. (Los detalles sobre cmo romper este esquema de cifrado, tal como se utiliza en WordPerfect, puede encontrarse en [135.139].) El cifrado Vigenre, publicado por primera

vez en 1586, y la cifra de Beaufort tambin son ejemplos de cdigos de sustitucin polialfabticos. Los Sistemas de cifrado por sustitucin polialfabticos tienen mltiples claves para una letra, cada uno de los cuales se utiliza para cifrar una letra del texto claro. La primera clave cifra la primera letra del texto en claro, la segunda clave cifra la segunda letra del texto plano, y as sucesivamente. Despus de que todas las teclas son utilizadas, las claves son recicladas. Si hubo 20 claves de una letra, entonces cada veinteava letra sera cifrada con la misma clave. Esto se denomina el perodo de la cifra. En la criptografa clsica, el cifrado con perodos ms largos fueron significativamente ms difcil de romper que los cifrados con perodos cortos. Hay tcnicas informticas que pueden romper fcilmente el cifrado por sustitucin con perodos muy largos. Un sistema de cifrado, a veces de rodaje clave de cifrado llamado un libro-en el que se utiliza para cifrar un texto a otro texto, es otro ejemplo de este tipo de cifrado. A pesar de que este sistema de cifrado tiene un perodo de la longitud del texto, sino que tambin se puede romper fcilmente [576.794].

Cifrados de transposicin
En un cifrado por transposicin del texto plano sigue siendo el mismo, pero el orden de los caracteres es movido de un lado al otro. En un sistema de cifrado por transposicin simple de columna, el texto plano se escribe horizontalmente sobre una hoja de papel cuadriculado de ancho fijo y el texto cifrado se lee verticalmente (ver Figura 1.4). La Desencriptacin es una cuestin de escribir el texto cifrado verticalmente sobre un trozo de papel grfico de anchura idntica y luego se lee el texto claro de forma horizontalmente. El Criptoanlisis de este cifrado se discute en [587,1475]. Puesto que las letras del texto cifrado son los mismos que los del texto plano, un anlisis de frecuencia en el texto cifrado revelara que cada letra tiene aproximadamente la misma probabilidad como en ingls. Esto da una idea muy buena para un Criptoanalista, que luego puede utilizar una variedad de tcnicas para determinar el orden correcto de las letras para obtener el texto completo. Poner el texto cifrado a travs de un segundo cifrado de transposicin mejora en gran medida la seguridad. Hay incluso sistemas de cifrado de transposicin ms complicados, pero los ordenadores pueden romper casi todos ellos. El cifrado alemn ADFGVX, utilizado durante la Primera Guerra Mundial, es un cifrado de transposicin se combinado con una sustitucin simple. Fue un algoritmo muy complejo para su poca, pero fue roto por Georges Painvin, un Criptoanalista francs [794]. Aunque muchos algoritmos modernos utilizan transposicin, es problemtico, ya que requiere una gran cantidad de memoria y, a veces requiere mensajes a ser slo de ciertas longitudes. La sustitucin es mucho ms comn.

Mquinas rotor En la dcada de 1920, varios dispositivos de cifrado mecnicos fueron inventados para automatizar el proceso de cifrado. La mayora se basan en el concepto de un rotor, una rueda mecnica con cable para realizar una sustitucin general. Una mquina de rotor tiene un teclado y una serie de rotores, e implementa una versin del cifrado de Vigenre. Cada rotor es una permutacin arbitraria del alfabeto, cuenta con 26 posiciones, y realiza una sustitucin simple. Por ejemplo, un rotor puede ser conectado a sustituir "F" por "A", "U" para "B", "L" por "C", y as sucesivamente. Y las clavijas de salida de un rotor estn conectadas a las clavijas de entrada de la siguiente.

Figura 1.4 Columna cifrado de transposicin. Por ejemplo, en una mquina de 4 rotores del primer rotor puede sustituir "F" por "A", el segundo podra sustituir "Y" por "F", el tercero podra sustituir "E" por "Y", y el cuarto poder sustituir "C" por "E", "C" sera el texto cifrado de salida. A continuacin, algunos de los rotores de cambio, la prxima vez que las sustituciones sern diferentes. Es la combinacin de varios rotores y engranajes mviles que hacen que la mquina sea segura. Debido a que todos los rotores se mueven a diferentes velocidades, el perodo para una mquina de rotor es 26n. Algunas mquinas de rotor pueden tambin tener un nmero diferente de posiciones de cada rotor, adicional frustrante para el criptoanlisis. El dispositivo ms conocido es el rotor Enigma. El enigma fue utilizado por los alemanes durante la Segunda Guerra Mundial. La idea fue inventada por Arthur Scherbius y Arvid Gerhard Damm en Europa. Fue patentado en los Estados Unidos por Arthur Scherbius [1383]. Los alemanes reforzaron considerablemente el diseo bsico para su uso en tiempos de guerra. El sistema alemn Enigma tena tres rotores, escogido de un conjunto de cinco, un panel de conexiones que ligeramente permutado el texto plano, y un rotor que refleja que ha generado cada rotor para operar en cada letra de texto claro dos veces. Tan complicado como fue el Enigma, que se rompi durante la Segunda Guerra Mundial. En primer lugar, un equipo de criptgrafos polacos rompe Enigma alemana y explic su ataque a los britnicos. Los alemanes modificaron su Enigma a medida que la guerra avanzaba, y los britnicos continuaron criptoanalizando las nuevas versiones. Para explicaciones de cmo funciona el cifrado de rotor y cmo se rompieron, ver [794, 86, 448, 498, 446, 880, 1315, 1587,690]. Dos relatos fascinantes de cmo el enigma se rompi son [735, 796]. Para leer ms Este no es un libro sobre criptografa clsica, por lo que no me extender ms sobre estos temas. Dos excelentes libros anteriores a la criptografa informtica son [587,1475], [448] presenta algunas criptoanlisis moderno de mquinas de cifrado. Dorothy Denning explica

muchos de estos sistemas de cifrado en [456] y [880] tiene algn anlisis matemtico bastante complejo de las cifras mismas. Otro texto cifrado anterior, que trata sobre criptografa analgico, es [99]. Un artculo que presenta una visin general de la asignatura es [579]. Libros histricos David Kahn criptografa tambin son excelentes [794795796].

1.4 XOR simple.

XOR es una operacin O exclusiva: '^' en C o en notacin matemtica. Es una operacin estndar en bits: 00=0 01=1 10=1 11=0 Tambin tenga en cuenta que:

aa=0 abb=a
El algoritmo simple XOR es realmente una vergenza, no es nada ms que un cifrado de Vigenre polialfabtica. Es aqu slo por su prevalencia en paquetes de software comerciales, al menos los de la MS-DOS y Macintosh mundos [1502,1387]. Por desgracia, si un programa de software de seguridad anuncia que tiene un "propietario" de cifrado del algoritmo mucho ms rpido que DES-lo ms probable es que se trata de una variante de esto.
/* Usage: crypto key input_file output_file */

void main (int argc, char *argv[]) { FILE *fi, *fo; char *cp; int c; if ((cp = argv[1]) && *cp!='\0') { if ((fi = fopen(argv[2], rb)) != NULL) { if ((fo = fopen(argv[3], wb)) != NULL) while ((c = getc(fi)) != EOF) { if (!*cp) cp = argv[1]; c ^= *(cp++); putc(c,fo); } fclose(fo); } fclose(fi); } } }

Este es un algoritmo simtrico. El texto completo se XOR con una palabra clave para generar el texto cifrado. Desde XORing el mismo valor dos veces restaura la codificacin original y descifrado, utilizan exactamente el mismo programa: PK=C CK=P No hay seguridad real aqu. Este tipo de cifrado es trivial de romper, incluso sin las computadoras [587,1475]. Slo le tomar unos segundos con un ordenador. Supongamos que el texto plano esta en Ingls. Adems, supongamos que la longitud de la clave es cualquier pequeo nmero de bytes. As es como para romperlo: 1. Descubre la longitud de la clave por un procedimiento conocido como recuento de coincidencias [577]. XOR del texto cifrado en contra de s mismo desplazado varios nmeros de bytes, y contar los bytes que son iguales. Si el desplazamiento es un mltiplo de la longitud de la clave, entonces algo ms de 6 por ciento de los bytes sern iguales. Si no lo es, a continuacin, a menos de 0,4 por ciento ser igual (asumiendo una clave aleatoria cifrar texto ASCII normal; texto claro otro tendrn nmeros diferentes). Esto se conoce como el ndice de coincidencia. El ms pequeo de desplazamiento que indica un mltiplo de la longitud de la clave es la longitud de la clave. 2. Cambie el texto cifrado por esa longitud y XOR con s mismo. Esto elimina la clave y le deja con texto claro XOR con el texto en claro cambi la longitud de la clave. Desde Ingls tiene 1,3 bits de informacin real per byte (vase la Seccin 11.1), hay un montn de redundancia para determinar un descifrado nica. A pesar de esto, la lista de proveedores de software que promocionan este algoritmo juguete como "casi tan seguro como DES" se tambaleaba [1387]. Es el algoritmo (con un 160-bit repetido "clave") que la NSA finalmente permiti a los EE.UU. la industria digital de telfono celular para usar la privacidad de voz. Un XOR puede mantener a su hermana pequea de la lectura de los archivos, pero no va a detener a un Criptoanalista por ms de unos pocos minutos.

1.5 Almohadilla de una sola vez.

Lo creas o no, no es un esquema de cifrado perfecto. Se llama un cojn de una sola vez, y fue inventado en 1917 por el Mayor Joseph Mauborgne y Gilbert Vernam de AT&T [794]. (En realidad, un one-time pad es un caso especial de un esquema umbral; Ver seccin 3.7) Clsicamente, un cojn de una sola vez no es nada ms que un juego no se repite muchas cartas claves verdaderamente aleatorias, escrito en hojas de papel, y pegadas entre s en una almohadilla. En su forma original, que era una cinta de una sola vez para teletipos. El emisor utiliza cada letra clave en el teclado para cifrar exactamente un carcter de texto plano. El cifrado es la adicin mdulo 26 del carcter del texto claro y el personaje clave de una sola vez almohadilla. Cada letra clave se utiliza una sola vez, para un solo mensaje. El remitente cifra el mensaje y despus destruye las pginas utilizadas de la almohadilla o de la seccin de la cinta utilizada. El receptor tiene una almohadilla idnticos y utiliza cada tecla en el teclado, a su vez, para descifrar cada letra del texto cifrado. El receptor destruye las pginas misma almohadilla o seccin de la cinta despus de descifrar el mensaje. Nuevos mensajes nuevos cartas clave. Por ejemplo, si el mensaje es:

ONETIMEPAD

y la secuencia de teclas en el teclado es

TBFRGFARFM

a continuacin, el texto cifrado es

IPKLPSFHGQ

porque O + T mod 26 = I N + B mod 26 = P E + F = K mod 26 etctera Suponiendo que un intruso no pueda tener acceso a la plataforma de una sola vez utilizado para cifrar el mensaje, este esquema es perfectamente seguro. Un mensaje de texto cifrado dado es igualmente probable que correspondan a cualquier mensaje de texto simple posible de igual tamao. Debido a que cada secuencia de teclas es igualmente probable (recuerde, las cartas clave son generados aleatoriamente), un adversario no tiene informacin con la que criptoanalizar el texto cifrado. La secuencia de teclas bien podra probablemente ser: POYYAEAAZX que hara descifrar a: SALMONEGGS o BXFGBMTMXM que hara descifrar a: GREENFLUID Este punto suele repetir: Puesto que cada mensaje de texto simple es igualmente posible, no hay manera para el Criptoanalista para determinar qu mensajes de texto claro es la correcta. Una secuencia aleatoria aadido clave a un mensaje de texto sin formato no aleatoria produce un mensaje de texto cifrado completamente al azar y ninguna cantidad de potencia de clculo puede cambiar eso. La advertencia, y esto es un grande, es que las cartas claves tienen que ser generados al azar. Cualquier ataque contra este rgimen ser contra el mtodo utilizado para generar las cartas clave. El uso de un generador de nmeros pseudo-aleatorios no cuenta, sino que siempre tienen propiedades aleatorias. Si utiliza una fuente real aleatoria, esto es mucho ms difcil de lo que aparenta, consulte la Seccin 17.14. Es seguro.

El otro punto importante es que usted no puede utilizar la secuencia de teclas de nuevo, nunca. Aunque se utilice una almohadilla de mltiples gigabytes, si un Criptoanalista tiene varios textos cifrados cuyas claves se superponen, se puede reconstruir el texto en claro. Se desliza cada par de textos cifrados uno contra el otro y cuenta el nmero de coincidencias en cada posicin. Si estn alineados a la derecha, la proporcin de partidos salta de pronto-los porcentajes exactos dependen del idioma de texto plano. Desde este punto de criptoanlisis es fcil. Es como el ndice de coincidencia, pero con slo dos "perodos" para comparar [904]. No lo hagas. La idea de una almohadilla de una sola vez se puede extender fcilmente a los datos binarios. En lugar de una almohadilla de una sola vez consta de cartas, utilizar un cojn de una sola vez de bits. En lugar de aadir el texto en claro a la almohadilla de una sola vez, usar una operacin XOR. Para descifrar el texto cifrado XOR con el mismo tiempo de pad. Todo lo dems sigue siendo el mismo y la seguridad es tan perfecta. Todo esto suena muy bien, pero hay algunos problemas. Puesto que los bits de la clave deben ser al azar y no puede ser utilizado de nuevo, la longitud de la secuencia de teclas debe ser igual a la longitud del mensaje. Un cojn de una sola vez puede ser adecuado para un mensaje corto, pero no va a funcionar para un canal de comunicaciones de 1,544 Mbps. Puede almacenar 650 megabytes de bits aleatorios en un CD-ROM, pero hay problemas. En primer lugar, usted quiere exactamente dos copias de los bits aleatorios, pero los CD-ROM son econmicos slo para grandes cantidades. Y en segundo lugar, que desea ser capaz de destruir los bits ya utilizados. CD-ROM no tiene instalaciones de borrado a excepcin de destruir fsicamente el disco completo. La cinta digital es un medio mucho mejor para este tipo de cosas. Incluso si se resuelve el problema de distribucin de claves y almacenamiento, usted tiene que asegurarse de que el emisor y el receptor estn perfectamente sincronizados. Si el receptor est fuera por un poco (o si algunos bits son eliminados durante la transmisin), el mensaje no tiene ningn sentido. Por otro lado, si algunos bits estn alterados durante la transmisin (sin ningn bit que se aade o elimina-algo mucho ms probable que ocurra debido a ruido aleatorio), slo los bits sern descifrados incorrectamente. Pero por otro lado, una almohadilla de una sola vez no proporciona ninguna autenticidad. Las almohadillas de una sola vez tienen aplicaciones en el mundo de hoy, sobre todo para canales de bajo ancho de banda ultra seguras. La lnea directa entre los Estados Unidos y la antigua Unin Sovitica se (sigue estando activo?) rumoro estar encriptado con un cojn de una sola vez. Muchos mensajes de espas soviticos a los agentes fueron cifrados utilizando almohadillas una sola vez. Estos mensajes son todava seguros hoy y seguir siendo as para siempre. No importa cunto tiempo las supercomputadoras trabajar en el problema. Incluso despus de que los extraterrestres de la tierra Andrmeda con sus naves espaciales masivas e insospechadas de potencia de clculo, no ser capaz de leer los mensajes cifrados de los espas soviticos con almohadillas de una sola vez (a menos que tambin se puede volver atrs en el tiempo y la almohadillas de una sola vez).

1.6 Algoritmos informticos.

Hay muchos algoritmos criptogrficos. Estos son tres de los ms comunes: - DES (Data Encryption Standard) es el algoritmo de cifrado de ordenador ms populares. DES es un estndar de EE.UU. e internacional. Se trata de un algoritmo simtrico, y la misma clave se utiliza para el cifrado y el descifrado. - RSA (llamado as por su creador-Rivest, Shamir y Adleman) es el ms popular algoritmo de clave pblica. Se puede utilizar tanto para el cifrado y las firmas digitales. - DSA (Digital Signature Algorithm, que se utiliza como parte de la Digital Signature Standard) es otro algoritmo de clave pblica. No se puede utilizar para el cifrado, pero slo para las firmas digitales. Este es el tipo de cosas este libro.

1.7 Grandes Nmeros.

A lo largo de este libro, utilizo varios grandes nmeros para describir cosas diferentes en criptografa. Debido a que es muy fcil perder de vista estos nmeros y lo que significan, tabla 1.1 da anlogos fsicos para algunos de ellos. Estos nmeros son el orden de magnitud de las estimaciones, y se han extrado de una variedad de fuentes. Muchos de los nmeros astrofsica se explican en Freeman.

TABLE 1.1 Large Numbers Physical Analogue Odds of being killed by lightning (per day) Odds of winning the top prize in a U.S. state lottery Odds of winning the top prize in a U.S. state lottery and being killed by lightning in the same day Odds of drowning (in the U.S. per year) Odds of being killed in an automobile accident(in the U.S. in 1993) Odds of being killed in an automobile accident(in the U.S. per lifetime) Time until the next ice age Time until the sun goes nova Age of the planet Age of the Universe Number of atoms in the planet Number of atoms in the sun Number 1 in 9 billion (233) 1 in 4,000,000 (222) 1 in 255 1 in 59,000 (216) 1 in 6100 (213) 1 in 88 (27) 14,000 (214) years 109 (230) years 109 (230) years 1010 (234) years 1051 (2170) 1057 (2190)

Number of atoms in the galaxy Number of atoms in the Universe (dark matter excluded) Volume of the Universe If the Universe is Closed: Total lifetime of the Universe If the Universe is Open: Time until low-mass stars cool off Time until planets detach from stars Time until stars detach from galaxies Time until orbits decay by gravitational radiation Time until black holes decay by the Hawking process Time until all matter is liquid at zero temperature Time until all matter decays to iron Time until all matter collapses to black holes

1067 (2223) 1077 (2265) 1084 (2280) cm3 1011 (237) years 1018 (261) seconds 1014 (247) years 1015 (250) years 1019 (264) years 1020 (267) years 1064 (2213) years 1065 (2216) years 101026 years 101076 years

Papel de Dyson, "Tiempo sin fin: la fsica y la biologa en un universo abierto", en Reviews of Modern Physics, v 52, n. 3 de julio de 1979, pp 447-460. Muertes por Accidentes de Automviles se calculan desde el Departamento de Estadstica de Transporte de 163 muertes por cada milln de habitantes en 1993 y un promedio de vida de 69,7 aos.

Parte I Protocolos criptogrficos Captulo 2 - Bloques de construccin de Protocolo.

2.1 Introduccin a los Protocolos
El punto total de la criptografa es resolver problemas. (En realidad, ese es el punto entero de los ordenadores, algo que muchas personas tienden a olvidar.) La criptografa resuelve problemas que implican el secreto, la autenticacin, la integridad y la gente deshonesta. Usted puede aprender todo acerca de los algoritmos criptogrficos y tcnicas, pero stas son menos acadmicas que puedan resolver un problema. Por ello, vamos a mirar primero los protocolos. Un protocolo es una serie de etapas, que implican dos o ms partes, diseado para realizar una tarea. Esta es una definicin importante. Una "serie de medidas" significa que el protocolo tiene una secuencia, desde el principio hasta el final. Cada paso debe ser ejecutado, a su vez, y ningn paso se puede tomar antes de que la etapa anterior haya terminado. "La participacin de dos o ms partes" significa que al menos se necesitan dos personas para completar el protocolo, una sola persona no tiene un protocolo. Una sola persona puede realizar una serie de pasos para realizar una tarea (como hornear un pastel), pero esto no es un protocolo. (Alguien ms tiene que comer el pastel para que sea un protocolo.) Finalmente, "diseado para realizar una tarea" significa que el protocolo debe lograr algo. Algo que se parece a un protocolo, pero no realiza una tarea que no es un protocolo que es una prdida de tiempo. Los Protocolos tienen otras caractersticas as: - Todos los involucrados en el protocolo deben conocer el protocolo y todos los pasos a seguir en adelantado. - Todas las personas involucradas en el protocolo deben estar de acuerdo en seguirlo. - El protocolo debe ser inequvoca, cada paso debe estar bien definido y no debe haber ninguna posibilidad de un malentendido. - El protocolo debe ser completo, debe haber una accin especifica para cada situacin posible. Los protocolos de este libro se organizan como una serie de pasos. La ejecucin del protocolo procede linealmente a travs de los pasos, salvo instrucciones para pasar a otro paso. Cada paso involucra al menos una de dos cosas: computaciones mediante una o ms de las partes, o los mensajes enviados entre las partes.

Un protocolo es un protocolo criptogrfico que utiliza la criptografa. Las partes pueden ser amigos y confiar en los dems implcitamente o pueden ser adversarias y no confiar en los dems para dar la hora correcta del da. Un protocolo criptogrfico implica algn algoritmo criptogrfico, pero generalmente el objetivo del protocolo es algo ms all de un simple secreto. Las partes que participan en el protocolo que desee compartir parte de sus secretos para calcular un valor, en conjunto generar una secuencia aleatoria, convencer a los otros de su identidad, o simultneamente firmar un contrato. El punto entero de la utilizacin de la criptografa en un protocolo es prevenir o detectar espionaje y el engao. Si usted nunca ha visto antes estos protocolos, se va a cambiar radicalmente sus ideas de lo que las partes mutuamente desconfiados puede lograr a travs de una red informtica. En general, esto se puede indicar como: - No debe ser posible hacer ms o aprender ms de lo que se especifica en el protocolo. Esto es mucho ms difcil de lo que parece. En los prximos captulos se discute ms de protocolos. En algunos de ellos es posible que uno de los participantes engae al otro. En otros, es posible que un intruso para subvertir el protocolo o conocer informacin secreta. Algunos protocolos fallan porque los diseadores no eran lo suficientemente completa en su definicin de requerimientos. Otros fracasan porque sus diseadores no eran lo suficientemente completa en su anlisis. Como algoritmos, es mucho ms fcil de demostrar la inseguridad de lo que es para probar la seguridad.

El propsito de los protocolos

En la vida diaria, hay protocolos informales para casi todo: pedido de bienes a travs del telfono, jugar poker, votar en una eleccin. Nadie piensa mucho acerca de estos protocolos, sino que han evolucionado con el tiempo, todo el mundo sabe cmo usarlos, y funcionan razonablemente bien. Estos das, la interaccin ms y ms humano se lleva a cabo a travs de redes de ordenador en lugar de cara a cara. Los ordenadores necesitan protocolos formales para hacer las mismas cosas que la gente hace sin pensar. Si usted se mud de un estado a otro y encontr una cabina de votacin que se vea totalmente diferente a los que estbamos acostumbrados, usted puede fcilmente adaptarse. Las computadoras no son casi tan flexibles. Muchos cara a cara protocolos se basan en la presencia de personas para garantizar la equidad y la seguridad. Quieres envian un extrao un montn de dinero en efectivo para comprar alimentos para usted? Quieres jugar al poker con alguien si no poda verlo shuffle y trato? Le enviaremos el gobierno de su votacin secreta sin alguna garanta de anonimato? Es ingenuo pensar que la gente en las redes de computadoras son honestos. Es ingenuo suponer que los gestores de las redes de ordenadores son honestos. Incluso es ingenuo suponer que los diseadores de redes informticas son honestos. La mayora son, pero los deshonestos pocos pueden hacer mucho dao. Al formalizar los protocolos, podemos examinar las formas en que las partes deshonestas pueden subvertir. Entonces podemos desarrollar protocolos que son inmunes a la subversin.

Adems de la formalizacin de protocolos de comportamiento, abstracto el proceso de llevar a cabo una tarea en el mecanismo por el cual se lleva a cabo la tarea. Un protocolo de comunicaciones es el mismo ya sea implementado en los ordenadores o VAXs. Podemos examinar el protocolo sin empantanarse en los detalles de implementacin. Cuando estamos convencidos de que tenemos un buen protocolo, podemos ponerlo en prctica en todo, desde computadoras hasta telfonos inteligentes a tostadoras mollete.

Los Jugadores
Para ayudar a demostrar los protocolos, he solicitado la ayuda de varias personas (ver Tabla 2.1). Alice y Bob son los dos primeros. Se llevar a cabo todos los generales de dos protocolos de personas. Como regla general, Alicia iniciar todos los protocolos y Bob responder. Si el protocolo requiere una tercera o cuarta persona, Carol y Dave llevar a cabo esas funciones. Otros actores que desempean funciones de apoyo especializados, sino que ser presentado ms adelante.

Protocolos de arbitraje
Un rbitro es una parte desinteresada tercero de confianza para completar un protocolo (ver Figura 2.1a). Medios desinteresados que el rbitro no tiene ningn inters personal en el protocolo y ninguna lealtad particular a ninguna de las partes involucradas. Trusted significa que todas las personas involucradas en el protocolo de aceptar lo que dice como verdad, lo que hace como correcta, y que va a cumplir su parte del protocolo. Los rbitros pueden ayudar protocolos completos entre dos partes mutuamente desconfiados. En el mundo real, los abogados se utilizan a menudo como rbitros. Por ejemplo, Alice es la venta de un coche a Bob, un extrao. Bob quiere pagar con cheque, pero Alice no tiene manera de saber si el cheque es bueno. Alice quiere que el cheque sea antes de cumplir el ttulo a Bob. Bob, que no confa en Alice, como no confa en l, no quiere entregar un cheque sin recibir un ttulo. CUADRO 2.1 dramatis Personae -------------------------------------------------- -----------------------------Alice primer participante en todos los protocolos Bob segundo participante en todos los protocolos Carol Participante en los de tres y cuatro bandas protocolos David Participante en los protocolos de cuatro partes Eva espa Mallory activo atacante malicioso Trent confianza rbitro Walter Warden, que estar vigilando Alice y Bob en algunos protocolos Peggy Prover Victor Verificador

Figura 2,1 tipos de protocolos. Introduzca un abogado de confianza por ambos. Con su ayuda, Alice y Bob puede utilizar el siguiente protocolo para asegurar que ni los trucos del otro: (1) Alice da el ttulo al abogado. (2) Bob le da el cheque a Alice. (3) Alice deposita el cheque. (4) Despus de esperar un perodo de tiempo especificado para el cheque sea, el abogado le da el ttulo a Bob. Si el cheque no se soluciona dentro del perodo de tiempo especificado, Alice muestra una prueba de ello al abogado y el abogado devuelve el ttulo a Alice. En este protocolo, Javier confa en que el abogado no dar Bob el ttulo a menos que el cheque ha sido cobrado, y que se lo devuelva a ella si el cheque no se borra. Bob confa en que el abogado de celebrar el ttulo hasta que el cheque, y darle a l una vez que lo hace. El abogado no le importa si el cheque. l har su parte del protocolo, en cualquier caso, porque se pagar en ningn caso. En el ejemplo, el abogado est representando el papel de un agente de plica. Los abogados tambin actuar como rbitros de voluntades ya veces para las negociaciones del contrato. Las bolsas de valores distintos actuar como rbitros entre compradores y vendedores. Los banqueros tambin arbitrar protocolos. Bob puede usar un cheque certificado a comprar un coche de Alice: (1) Bob escribe un cheque y se lo entrega al banco. (2) Despus de poner suficiente dinero de Bob en espera para cubrir el cheque, el banco certifica el cheque y se lo devuelve a Bob. (3) Alice da el ttulo a Bob y Bob le da el cheque certificado a Alice. (4) Alice deposita el cheque.

Este protocolo funciona porque Javier confa en la certificacin de la banca. Javier confa en el banco para tener dinero de Bob para ella, y no utilizarlo para financiar temblorosas operaciones inmobiliarias en los pases infestados de mosquitos. Un notario pblico es otro rbitro. Cuando Bob recibe un documento notarial de Alice, que est convencido de que Alicia firm el documento voluntariamente y con su propia mano. El notario puede, si es necesario, de pie en el tribunal y dar fe de este hecho. El concepto de un rbitro es tan antigua como la sociedad. Siempre ha habido personasgobernantes, sacerdotes, etc-que tienen la autoridad para actuar con justicia. Los rbitros tienen un cierto papel social y posicin en la sociedad, traicionando la confianza del pblico que pondra en peligro. Los abogados que participan en juegos con cuentas de depsito en garanta frente inhabilitacin casi segura, por ejemplo. Esta imagen de confianza no siempre existe en el mundo real, pero es el ideal. Este ideal se puede traducir en el mundo de la informtica, pero hay varios problemas con los rbitros informticos: - Es ms fcil de encontrar y confiar en un tercero neutral si usted sabe que el partido es y puede ver su cara. Dos partidos sospechosos de unos a otros tambin son susceptibles de ser sospechoso de un rbitro annimo en otro lugar de la red. - La red de computadora debe correr con los gastos de mantenimiento de un rbitro. Todos sabemos lo que los abogados cobran, quin quiere tener ese tipo de sobrecarga en la red? - Hay un retraso inherente en cualquier protocolo arbitrado. - El rbitro debe tratar con cada transaccin, es un cuello de botella en implementaciones a gran escala de cualquier protocolo. Aumentar el nmero de rbitros en la aplicacin puede mitigar este problema, pero eso aumenta el coste. - Como todo el mundo en la red debe confiar en el rbitro, representa un punto vulnerable para cualquiera que trate de subvertir la red. Aun as, los rbitros tienen un papel que desempear. En los protocolos que utilizan un rbitro de confianza, la pieza ser interpretada por Trent.

Protocolos adjudicados
Debido al alto costo de contratar rbitros, protocolos arbitradas se puede subdividir en dos de nivel inferior subprotocols. Se trata de una nonarbitrated subprotocolo, ejecuta cada vez que las partes quieren completar el protocolo. La otra es una arbitrado subprotocolo, ejecutado slo en circunstancias excepcionales, cuando hay una disputa. Este tipo especial de rbitro se llama un juez (ver Figura 2.1b). Un juez es tambin un tercero desinteresado y de confianza. A diferencia de un rbitro, que no est directamente involucrado en cada protocolo. El adjudicador se llama en solamente para determinar si un protocolo se realiz bastante.

Los jueces son jueces profesionales. A diferencia de un notario pblico, un juez se trae slo si hay una disputa. Alice y Bob pueden celebrar un contrato sin un juez. Un juez nunca ve el contrato hasta que uno de ellos transporta el otro en la corte. Este protocolo de firma del contrato se puede formalizar de esta manera: Nonarbitrated subprotocolo (ejecutado cada vez): (1) Alice y Bob negociar los trminos del contrato. (2) Alice firma el contrato. (3) Bob firma el contrato. Adjudicados subprotocolo (ejecutado slo en caso de una disputa): (4) Alice y Bob comparecer ante un juez. (5) Alicia presenta su evidencia. (6) Bob presenta su evidencia. (7) El juez pronuncia sobre las pruebas. La diferencia entre un rbitro y un rbitro (como se usa en este libro) es que el juez no es siempre necesario. En una disputa, un juez es llamado a pronunciarse. Si no hay disputa, usando un juez no es necesario. Hay protocolos informticos adjudicados. Estos protocolos se basan en los partidos para ser honesto, pero si alguien sospecha de hacer trampa, un cuerpo de datos existe para que un tercero de confianza puede determinar si alguien engaado. En un protocolo bien adjudicado, el juez podra determinar la identidad del tramposo. En lugar de evitar el engao, protocolos adjudicados detectar el engao. La inevitabilidad de deteccin acta como preventivo y desalienta la trampa.

Alquiler de cumplimiento de Auto Protocolos

Un protocolo de auto-cumplimiento es el mejor tipo de protocolo. Este protocolo garantiza la equidad (vase la Figura 2.1c). No rbitro es necesario para completar el protocolo. No juez tiene la obligacin de resolver las controversias. El protocolo est construido de modo que no puede haber cualquier conflicto. Si una de las partes trata de engaar, la otra parte inmediatamente detecta la trampa y se detiene el protocolo. Cualquiera que sea el partido trampa esperaba que sucediera haciendo trampa, no sucede. En el mejor de los mundos posibles, cada protocolo sera auto-cumplimiento. Desafortunadamente, no es un protocolo de auto-aplicacin para cada situacin.

Los ataques contra los protocolos

Ataques criptogrficos pueden ser dirigidos contra los algoritmos criptogrficos usados en los protocolos, en contra de las tcnicas criptogrficas utilizadas para aplicar los algoritmos y protocolos, o en contra de los protocolos. Desde esta seccin del libro discute los protocolos, voy a asumir que los algoritmos criptogrficos y tcnicas son seguras. Slo voy a examinar los ataques contra los protocolos.

Las personas pueden tratar de varias maneras para atacar a un protocolo. Alguien que no participan en el protocolo puede interceptar todas o algunas del protocolo. Esto se conoce como un ataque pasivo, ya que el atacante no afecta al protocolo. Lo nico que podemos hacer es observar el protocolo y tratar de obtener informacin. Este tipo de ataque corresponde a un ataque de texto cifrado de slo, como se discute en la Seccin 1,1. Desde los ataques pasivos son difciles de detectar, los protocolos de tratar de prevenir los ataques pasivos en lugar de detectarlos. En estos protocolos, la parte de la eavesdropper ser interpretado por Eva. Alternativamente, un atacante podra modificar el protocolo para su propio beneficio. Poda fingir ser otra persona, introducir nuevos mensajes en el protocolo, borrar los mensajes existentes, sustituir un mensaje por otro, reproducir mensajes antiguos, interrumpir un canal de comunicaciones, o alterar la informacin almacenada en un ordenador. Estos se llaman ataques activos, debido a que requieren intervencin activa. La forma de estos ataques depende de la red. Atacantes pasivos tratar de obtener informacin acerca de las partes involucradas en el protocolo. Recogen mensajes que pasan entre las diversas partes y tratar de criptoanalizar. Ataques activos, por otro lado, puede tener objetivos mucho ms diversas. El atacante podra estar interesado en obtener informacin, degradar el rendimiento del sistema, corrupcin de la informacin existente, o el acceso no autorizado a los recursos. Ataques activos son mucho ms graves, sobre todo en los protocolos en los que los distintos partidos no necesariamente confiar entre s. El atacante no tiene que ser un completo extrao. Poda ser un usuario del sistema legtimo. l podra ser el administrador del sistema. Incluso podra haber muchos atacantes activos que trabajan juntos. Aqu, la parte del atacante malintencionado activo ser interpretado por Mallory. Tambin es posible que el atacante podra ser una de las partes implicadas en el protocolo. l puede estar en el protocolo o no seguir el protocolo en absoluto. Este tipo de atacante se llama un tramposo. Tramposos pasivos seguir el protocolo, sino tratar de obtener ms informacin que el protocolo pretende que lo hagan. Tramposos activos interrumpir el protocolo en curso con la intencin de engaar. Es muy difcil mantener la seguridad de un protocolo si la mayora de las partes involucradas son tramposos activos, pero a veces es posible que las partes legtimas para detectar que el engao activo que est pasando. Ciertamente, los protocolos deben ser seguras contra el fraude pasivo.

2.2 Comunicaciones utilizando criptografa simtrica.

Cmo dos partes comunicarse de forma segura? Ellos cifrar sus comunicaciones, por supuesto. El protocolo completo es ms complicado que esto. Echemos un vistazo a lo que debe suceder para Alice para enviar un mensaje cifrado a Bob. (1) Alice y Bob estn de acuerdo en un sistema de cifrado. (2) Alice y Bob ponerse de acuerdo sobre una clave. (3) Alice lleva su mensaje de texto y lo cifra utilizando el algoritmo de cifrado y la clave. Esto crea un mensaje de texto cifrado. (4) Alicia enva el mensaje cifrado a Bob. (5) Bob descifra el mensaje de texto cifrado con el mismo algoritmo y la clave y lo lee.

Qu puede hacer Eva, sentada entre Alice y Bob, aprender escuchando en este protocolo? Si lo nico que oye es la transmisin en el paso (4), se debe tratar de criptoanalizar el texto cifrado. Este ataque pasivo es un ataque de texto cifradosolamente, tenemos algoritmos que son resistentes (hasta donde sabemos) a lo que Eva capacidad de clculo realista podra ejercer sobre el problema. Eva no es estpido, sin embargo. Tambin quiere escuchar en pasos (1) y (2). Entonces, ella conoce el algoritmo y la clave-tan bien como Bob. Cuando el mensaje llega a travs del canal de comunicaciones en el paso (4), todo lo que tiene que hacer es descifrar por s misma. Un criptosistema buena es una en la que toda la seguridad est inherente en el conocimiento de la clave y ninguna es inherente en el conocimiento del algoritmo. Esta es la razn por la gestin de claves es tan importante en la criptografa. Con un algoritmo simtrico, Alice y Bob puede realizar el paso (1) en pblico, pero deben realizar el paso (2) en secreto. La clave debe permanecer secreto antes, durante, y despus del protocolo, siempre que el mensaje debe permanecer secreta, de lo contrario el mensaje ya no ser seguro. (Criptografa de clave pblica resuelve este problema de otra manera, y se discuten en la Seccin 2,5.) Mallory, un atacante activo, podra hacer algunas otras cosas. Se podra tratar de romper la ruta de comunicaciones en el paso (4), asegurndose de que Alice no poda hablar con Bob en absoluto. Mallory tambin podra interceptar los mensajes de Alice y sustituir la suya. Si saba que la llave (mediante la interceptacin de la comunicacin en el paso (2), o por romper el criptosistema), podra cifrar su propio mensaje y enviarlo a Bob en lugar del mensaje interceptado. Bob no tendra forma de saber que el mensaje no haba venido de Alice. Si Mallory no conoce la clave, slo poda crear un mensaje de reemplazo que descifrar a un galimatas. Bob, pensando que el mensaje proviene de Alicia, podramos concluir que la red o Alice tena algunos problemas serios. Qu pasa con Alice? Qu puede hacer para romper el protocolo? Ella puede dar una copia de la llave a Eva. Ahora Eva puede leer lo que dice Bob. Ella puede reimprimir sus palabras en el New York Times. Aunque grave, esto no es un problema con el protocolo. No hay nada que impida a Alice Eve de dar una copia del texto en claro, en cualquier momento durante el protocolo. Por supuesto, Bob tambin podra hacer cualquier cosa que Alice poda. Este protocolo asume que Alice y Bob confiar en los dems. En resumen, criptosistemas simtricos tienen los siguientes problemas: - Las claves deben ser distribuidos en secreto. Ellos son tan valiosas como todos los mensajes que cifrar, ya que el conocimiento de la clave da el conocimiento de todos los mensajes. Para los sistemas de cifrado que abarcan todo el mundo, esto puede ser una tarea desalentadora. A menudo mensajeros a mano llevar las llaves a sus destinos. - Si una tecla se ve comprometida (robado, adivin, extorsin, soborno, etc), despus Eva puede descifrar todo el trfico de mensajes cifrados con esa clave. Tambin puede hacerse pasar por una de las partes y producir mensajes falsos para engaar a la otra parte.

- Suponiendo una tecla separada se utiliza para cada par de usuarios en una red, el nmero total de claves aumenta rpidamente a medida que aumenta el nmero de usuarios. Una red de n usuarios necesita n (n - 1) / 2 claves. Por ejemplo, los usuarios requieren 10 45 claves diferentes para comunicarse entre s y 100 usuarios requieren claves 4950. Este problema se puede minimizar manteniendo el nmero de usuarios pequeos, pero que no siempre es posible.

2.3 funciones unidireccional

La nocin de una funcin unidireccional es central para criptografa de clave pblica. Aunque no son en s mismos protocolos, funciones unidireccionales son un elemento fundamental para la mayora de los protocolos descritos en este libro. Funciones unidireccionales son relativamente fciles de calcular, pero significativamente ms difcil de revertir. Es decir, dado x es fcil de calcular f (x), pero dado f (x), es difcil de calcular x. En este contexto, "duro" se define como algo as: Se necesitaran millones de aos para calcular x de f (x), incluso si todos los ordenadores del mundo se les asign al problema. Romper un plato es un buen ejemplo de una funcin unidireccional. Es fcil romper un plato en mil pedazos. Sin embargo, no es fcil de poner todas esas pequeas piezas de nuevo juntos en un plato. Esto suena bien, pero es una gran cantidad de humo y espejos. Si estamos siendo estrictamente matemtico, no tenemos ninguna prueba de que funciones unidireccionales existe, ni ninguna evidencia real de que se puede construir [230530600661]. Aun as, muchas funciones verse y oler un solo sentido: Podemos calcular de manera eficiente y, hasta el momento, no conozco ninguna manera fcil de revertir. Por ejemplo, en un campo finito x2 es fcil de calcular, pero x1 / 2 es mucho ms difcil. Para el resto de esta seccin, voy a pretender que hay un solo sentido funciones. Voy a hablar ms sobre esto en la seccin 11.2. As que, de qu sirven funciones unidireccionales? No podemos utilizar para el cifrado de inmediato. Un mensaje cifrado con la funcin de un solo sentido no es til, nadie poda descifrarlo. (Ejercicio:... Escribir un mensaje en un plato, romper la placa en pequeos trozos, y luego dar los bits a un amigo Pregunte a su amigo para leer el mensaje Observe lo impresionado que est con la funcin de un solo sentido) de colaboracin pblicocriptografa de clave, necesitamos algo ms (aunque hay aplicaciones criptogrficas para funciones unidireccionales-ver seccin 3.2). Una trampa de un sentido funcin es un tipo especial de la funcin de un solo sentido, una con una trampilla secreta. Es fcil de calcular en una direccin y difcil de calcular en la otra direccin. Sin embargo, si usted sabe el secreto, es fcil calcular la funcin en la otra direccin. Esto es, es fcil de calcular f (x) dado x, y difcil de calcular x dada f (x). Sin embargo, hay una cierta informacin secreta, y, dada tal que f (x) e y es fcil de calcular x. Tomando un reloj aparte es un buen ejemplo de una trampilla unidireccional funcin. Es fcil de desmontar un reloj en cientos de pedazos minsculos. Es muy difcil poner esas pequeas piezas de nuevo juntos en un reloj de trabajo. Sin embargo, con la informacin

en secreto-las instrucciones de montaje del reloj, es mucho ms fcil poner el reloj de nuevo juntos. 2.4 unidireccionales Funciones Hash. Una funcin hash unidireccional tiene muchos nombres: funcin de compresin, la funcin de contraccin, sntesis del mensaje, huella digital, la suma de comprobacin criptogrfica, Message Integrity Check (MIC), y el cdigo de manipulacin de deteccin (MDC). Como se llame, es central a la criptografa moderna. De una va funciones hash son otro elemento fundamental para muchos protocolos. Las funciones hash se han utilizado en la informtica por un largo tiempo. Una funcin de hash es una funcin, matemtico o de otra manera, que toma una cadena de entrada de longitud variable (llamada pre-imagen) y lo convierte en una cadena de salida de longitud fija (generalmente ms pequeas) (denominado valor hash). Una funcin hash simple sera una funcin que toma pre-imagen y devuelve un byte que consiste en el XOR de todos los bytes de entrada. El punto aqu es que la huella digital de pre-imagen: para producir un valor que indica si un candidato pre-imagen es probable que sea el mismo que el real pre-imagen. Dado que las funciones hash son tpicamente de varios a uno, no se puede utilizar para determinar con certeza que las dos cadenas son iguales, pero podemos usarlos para obtener una seguridad razonable de exactitud. Una funcin hash unidireccional es una funcin hash que funciona en una direccin: es fcil de calcular un valor hash a partir de pre-imagen, pero es difcil de generar una imagen previa que los hashes a un valor particular. La funcin de hash se ha mencionado anteriormente no es de un solo sentido: Dado un valor de byte particular, es trivial para generar una cadena de bytes cuyo XOR es ese valor. Usted no puede hacer eso con una funcin hash unidireccional. Una buena funcin hash unidireccional es tambin libre de colisiones: Es difcil para generar dos pre-imgenes con el mismo valor hash. La funcin hash es pblico, no hay secreto en el proceso. La seguridad de una funcin hash unidireccional es su primer wayness. La salida no depende de la entrada de forma discernible. Un cambio de un solo bit en los cambios de pre-imagen, en el medio promedio, de los bits en el valor hash. Dado un valor hash, es computacionalmente inviable encontrar una imagen previa que los hashes a ese valor. Piense en ello como una forma de archivos de huellas digitales. Si desea comprobar que alguien tiene un archivo en particular (que tambin tiene), pero no quiere que se lo enve a usted, entonces le pregunte por el valor hash. Si se le enva el valor hash correcto, entonces es casi seguro que tiene ese archivo. Esto es particularmente til en las operaciones financieras que no desea un retiro de $ 100 para convertirlo en un retiro de $ 1000 en algn lugar de la red. Normalmente, se utiliza una funcin hash unidireccional sin una clave, para que cualquiera pueda comprobar el hash. Si desea que slo el destinatario pueda verificar el hash, a continuacin, lea la siguiente seccin.

Cdigos de autenticacin de mensajes. Un cdigo de autenticacin de mensaje (MAC), tambin conocido como un cdigo de autenticacin de datos (DAC), es una funcin hash unidireccional con la adicin de una clave secreta (vase la Seccin 18.14). El valor hash es una funcin tanto de la imagen previa y la tecla. La teora es exactamente la misma que las funciones de hash, excepto alguien slo con la llave puede verificar el valor hash. Se puede crear un MAC de una funcin hash o un algoritmo de cifrado de bloques, tambin hay MACs dedicados. 2.5 Comunicaciones Usando Public-Key Cryptography. Piense en un algoritmo simtrico como una caja fuerte. La clave est en la combinacin. Alguien con la combinacin puede abrir la caja fuerte, poner un documento en el interior, y vuelva a cerrarla. Otra persona con la combinacin puede abrir la caja fuerte y llevar el documento fuera. Cualquier persona sin la combinacin se ve obligado a aprender safecracking. En 1976, Whitfield Diffie y Martin Hellman cambiado el paradigma de la criptografa para siempre [496]. (La NSA ha cobrado el conocimiento del concepto ya en 1966, pero no ha ofrecido ninguna prueba.) Ellos describieron criptografa de clave pblica. Utilizaron dos claves diferentes-uno pblico y el otro privado. Es computacionalmente difcil deducir la clave privada de la clave pblica. Cualquier persona con la clave pblica puede cifrar un mensaje, pero no descifrarlo. Slo la persona con la clave privada puede descifrar el mensaje. Es como si alguien encendiera la seguridad criptogrfica en un buzn. Poner el correo en el buzn de correo es anloga a cifrar con la clave pblica, cualquier persona puede hacerlo. Slo tiene que abrir la ranura y sultela pulg Obtener correo de un buzn es anloga a descifrar con la clave privada. Por lo general es difcil, que hay antorchas de soldadura. Sin embargo, si usted tiene el secreto (la tecla fsica para el buzn), es fcil conseguir el correo de un buzn. Matemticamente, el proceso se basa en la puerta-trampa funciones unidireccionales previamente discutidos. El cifrado es la direccin fcil. Instrucciones para la codificacin son la clave pblica, cualquiera puede cifrar un mensaje. El descifrado es la direccin difcil. Se hace bastante difcil que las personas con computadoras Cray y miles (incluso millones) de aos no pudo descifrar el mensaje sin el secreto. El secreto, o trampa, es la clave privada. Con ese secreto, el descifrado es tan fcil como el cifrado. As es como Alicia puede enviar un mensaje a Bob usando criptografa de clave pblica: (1) Alice y Bob estn de acuerdo en un criptosistema de clave pblica. (2) Bob enva su clave pblica de Alice. (3) Alicia encripta su mensaje utilizando la clave pblica de Bob y lo enva a Bob. (4) Bob descifra el mensaje de Alice utilizando su clave privada. Note como criptografa de clave pblica resuelve el problema central de gestin con sistemas criptogrficos simtricos. Antes, Alice y Bob tuvo que ponerse de acuerdo sobre una clave secreta. Alice podra elegir uno al azar, pero ella todava tena que llegar a Bob. Ella podra entregrselo a l en algn momento antes, pero que requiere de previsin. Poda enviar a l por mensajera segura, pero eso lleva tiempo. Criptografa de clave pblica hace que sea fcil. Con acuerdo previo, Alice puede enviar un mensaje seguro a Bob. Eva, escuchando en todo el intercambio, tiene la clave pblica de Bob y un mensaje

cifrado en esa clave, pero no se puede recuperar cualquier clave privada de Bob o el mensaje. Ms comnmente, una red de usuarios de acuerdo en un sistema de cifrado de clave pblica. Cada usuario tiene su propia clave pblica y la clave privada y la clave pblica se publican en una base de datos en alguna parte. Ahora que el protocolo es an ms fcil: (1) Alice recibe la clave pblica de Bob de la base de datos. (2) Alice encripta su mensaje utilizando la clave pblica de Bob y lo enva a Bob. (3) Bob descifra el mensaje de Alice utilizando su clave privada. En el primer protocolo, Bob tuvo que enviar a Alice su clave pblica antes de que pudiera enviar un mensaje. El segundo protocolo es ms que el correo tradicional. Bob no est involucrado en el protocolo hasta que l quiere leer su mensaje. Criptosistemas hbridos. Los primeros algoritmos de clave pblica se hizo pblico al mismo tiempo que el DES se est debatiendo como una norma propuesta. Esto dio lugar a algunas polticas partidistas en la comunidad criptogrfica. Como lo describi Diffie [494]: Los sistemas criptogrficos de clave pblica entusiasmo provocado en la prensa popular y cientfica no fue acompaado por la aceptacin correspondiente en el establecimiento de cifrado, sin embargo. En el mismo ao en que la criptografa de clave pblica se descubri, la Agencia Nacional de Seguridad (NSA), propuso un sistema criptogrfico convencional, diseado por International Business Machines (IBM), como federal Data Encryption Standard (DES). Marty Hellman y critic la propuesta por considerar que su llave era demasiado pequea, pero los fabricantes se preparan para apoyar a la norma propuesta y nuestra crtica fue visto por muchos como un intento de perturbar el proceso de elaboracin de normas en beneficio de nuestro propio trabajar. Criptografa de clave pblica a su vez, fue atacado, en la literatura de ventas [1125] y los documentos tcnicos [849,1159] por igual, ms como si se tratara de un producto de la competencia de un descubrimiento reciente investigacin. Sin embargo, esto no impidi que la NSA de reclamar su parte del crdito. Su director, en palabras de la Enciclopedia Britnica [1461], seal que "dos criptografa de clave haba sido descubierto en la agencia hace una dcada", aunque no hay evidencia para esta afirmacin fue ofrecido nunca pblicamente. En el mundo real, algoritmos de clave pblica no son un sustituto para algoritmos simtricos. No se utilizan para cifrar los mensajes, sino que se utiliza para cifrar las claves. Hay dos razones para esto: 1. Algoritmos de clave pblica son lentos. Los algoritmos simtricos son generalmente de al menos 1000 veces ms rpido que algoritmos de clave pblica. S, las computadoras son cada vez ms rpido, y en 15 aos las computadoras sern capaces de hacer criptografa de clave pblica a velocidades comparables a la criptografa simtrica hoy. Sin embargo, los requisitos de ancho de banda tambin estn aumentando, y siempre habr la necesidad de encriptar datos ms rpido de criptografa de clave pblica puede manejar.

2. Criptosistemas de clave pblica son vulnerables a los ataques de texto plano escogido. Si C = E (P), cuando P es un texto plano de un conjunto de textos planos n posibles, a continuacin, un criptoanalista slo tiene que codificar todos los posibles textos planos n y comparar los resultados con C (recuerde que la clave de cifrado es pblico). l no ser capaz de recuperar la clave de descifrado de esta manera, pero ser capaz de determinar P. Un ataque de texto plano escogido puede ser particularmente eficaz si hay relativamente pocos mensajes cifrados posibles. Por ejemplo, si P fuera una cantidad de dinero inferior a $ 1.000.000, este ataque iba a funcionar, el criptoanalista prueba todas las posibles cantidades millonarias de dlares. (Cifrado probabilstico resuelve el problema, vase la Seccin 23,15.) Incluso si P no es tan bien definido, este ataque puede ser muy eficaz. Simplemente saber que un texto cifrado no se corresponde con un texto claro en particular puede ser informacin til. Criptosistemas simtricos no son vulnerables a este ataque porque un criptoanalista no puede realizar encriptaciones de prueba con una clave desconocida. En la mayora de las implementaciones prcticas criptografa de clave pblica se utiliza para asegurar y distribuir claves de sesin, las claves de sesin se utilizan con algoritmos simtricos para asegurar el trfico de mensajes [879]. Esto se denomina a veces un criptosistema hbrido. (1) Bob enva su clave pblica de Alice. (2) Alice genera una clave de sesin aleatoria, K, lo encripta usando la clave pblica de Bob, y lo enva a Bob. EB (K) (3) Bob descifra el mensaje de Alice utilizando su clave privada para recuperar la clave de sesin. DB (EB (K)) = K (4) Los dos cifrar sus comunicaciones empleando la misma clave de sesin. Usando criptografa de clave pblica para la distribucin de claves resuelve un importante problema clave de gestin. Con la criptografa simtrica, la clave de cifrado de datos se encuentra alrededor hasta que se utiliza. Si Eva nunca consigue sus manos en ella, ella puede descifrar los mensajes cifrados con la misma. Con el protocolo anterior, la clave de sesin se crea cuando se necesita para cifrar las comunicaciones y destruidas cuando ya no se necesita. Esto reduce drsticamente el riesgo de comprometer la clave de sesin. Por supuesto, la clave privada es vulnerable a un compromiso, pero es de menor riesgo, ya que slo se utiliza una vez por la comunicacin para cifrar una clave de sesin. Esto se discute en la Seccin 3.1. Puzzles de Merkle. Ralph Merkle invent la primera construccin de criptografa de clave pblica. En 1974 se inscribi en un curso de seguridad informtica en la Universidad de California, Berkeley, impartido por Lance Hoffman. El tema de su trabajo final, presentado a principios de este trmino, abord el problema de la "comunicacin segura sobre canales inseguros" [1064]. Hoffman no pudo entender la propuesta de Merkle y, finalmente, cay Merkle el curso. l continu trabajando en el problema, a pesar del fracaso continuo para que sus resultados entendido.

Merkle tcnica se bas en "rompecabezas" que eran ms fciles de resolver para el emisor y el receptor que para un espa. As es como Alice enva un mensaje cifrado a Bob sin tener que intercambiar una llave con l. (1) Bob genera 220, o alrededor de un milln, mensajes del tipo: "Este es x rompecabezas numrico. Este es el secreto y nmero de clave ", donde x es un nmero aleatorio e y es una clave secreta aleatoria. Tanto x como y son diferentes para cada mensaje. El uso de un algoritmo simtrico, se encripta cada mensaje con una diferente de 20-bit clave, y enva a todos a Alice. (2) Alice elige un mensaje al azar y realiza un ataque de fuerza bruta para recuperar el plaintext. Esta es una gran cantidad, pero no imposible, de trabajo. (3) Alice cifra su mensaje con la clave secreta se recuper y algn algoritmo simtrico, y la enva a Bob junto con x. (4) Bob sabe que la clave secreta y se encripta en x mensajes, as que l puede descifrar el mensaje. Eva puede romper este sistema, pero ella tiene que hacer mucho ms trabajo que Alicia o de Bob. Para recuperar el mensaje en el paso (3), que tiene que realizar un ataque de fuerza bruta contra cada uno de 220 mensajes de Bob en el paso (1); este ataque tiene una complejidad de 240. Los valores x no ayudar a Eva tampoco, que fueron asignados al azar en el paso (1). En general, Eve tiene que gastar aproximadamente el cuadrado del esfuerzo que Alice gasta. Esta ventaja a n n2 es pequeo por normas de cifrado, pero en algunas circunstancias puede ser suficiente. Si Alice y Bob pueden probar diez mil llaves por segundo, que les llevar un minuto cada uno para llevar a cabo sus pasos y otro minuto para comunicar los rompecabezas de Bob a Alicia en un enlace MB 1,544. Si Eva tena unas instalaciones comparables de computacin, se la llevara alrededor de un ao para romper el sistema. Otros algoritmos son an ms difciles de romper. 2.6 Firmas Digitales. Firmas manuscritas han sido utilizados como prueba de la autora de, o por lo menos acuerdo con, el contenido de un documento. Qu es lo que tiene una firma que es tan convincente [1392]? 1. La firma es autntica. La firma convence destinatario del documento que el firmante deliberadamente firmado el documento. 2. La firma es infalsificable. La firma es la prueba de que el firmante, y nadie ms, deliberadamente firmado el documento. 3. La firma no es reutilizable. La firma es parte del documento, una persona sin escrpulos no puede sacar la firma a un documento diferente. 4. El documento firmado es inalterable. Despus de la firma del documento, no puede ser alterado.

5. La firma no puede ser repudiado. La firma y el documento son las cosas fsicas. La firma no puede reclamar ms tarde que l o ella no lo firm. En realidad, ninguna de estas afirmaciones sobre firmas es del todo cierto. Las firmas pueden ser falsificados, las firmas pueden ser levantados de un pedazo de papel y se traslad a otro, y los documentos pueden ser modificadas despus de la firma. Sin embargo, estamos dispuestos a vivir con estos problemas debido a la dificultad en la trampa y el riesgo de deteccin. Nos gustara hacer este tipo de cosas en los ordenadores, pero hay problemas. En primer lugar, los archivos de computadora son triviales para copiar. Incluso si la firma de una persona eran difciles de falsificar (una imagen grfica de una firma manuscrita, por ejemplo), sera fcil de cortar y pegar una firma vlida de un documento a otro documento. La mera presencia de una firma no significa nada. En segundo lugar, los archivos informticos son fciles de modificar despus de su firma, sin dejar ninguna evidencia de modificacin. Firmar documentos con criptosistemas simtricos y un rbitro. Alicia desea firmar un mensaje digital y enviarla a Bob. Con la ayuda de Trent y un criptosistema simtrico, es ella. Trent es un rbitro de gran alcance, confiable. Se puede comunicar con Alice y Bob (y todos los dems que quieran firmar un documento digital). l comparte una clave secreta, KA, con Alice, y una clave diferente, KB, con Bob. Estas teclas se han establecido mucho antes de que el protocolo comienza y puede ser reutilizado varias veces para mltiples firmas. (1) Alice encripta su mensaje a Bob con KA y lo enva a Trent. (2) Trent desencripta el mensaje con KA. (3) Trent lleva el mensaje descifrado y una declaracin de que ha recibido este mensaje de Alice, y cifra todo el conjunto con KB. (4) Trent enva el paquete de cifrado a Bob. (5) Bob descifra el paquete con KB. Ahora puede leer el mensaje y certificacin de Trent que Alice lo envi. Cmo Trent saber que el mensaje proviene de Alicia y no de un impostor? Se infiere del mensaje, el cifrado de AOS. Dado que slo l y Alice comparten su clave secreta, slo Alice poda cifrar un mensaje de usarlo. Es esto tan bueno como una firma en papel? Que, el AM fijamos en las caractersticas que desee: 1. Esta firma es autntica. Trent es un rbitro confiable y Trent sabe que el mensaje proviene de Alicia. Trent, el AM certificacin sirve como prueba para Bob. 2. Esta firma es infalsificable. Slo Alice (y Trent, pero todo el mundo confa en l) sabe KA, por lo que slo Alice podra haber enviado Trent un mensaje cifrado con KA. Si alguien intentara hacerse pasar por Alice, Trent habra inmediatamente se dio cuenta de esto en el paso (2) y no certificar su autenticidad.

3. Esta firma no es reutilizable. Si Bob trat de tomar Trent, certificacin del AM y adjuntarlo a otro mensaje, Alice grito en el cielo. Un rbitro (que podra ser Trent o podra ser un rbitro completamente diferente con acceso a la misma informacin) pedira Bob para producir tanto el mensaje y Alice, AOS mensaje cifrado. El rbitro entonces cifrar el mensaje con KA y ver que no coincida con el mensaje cifrado que Bob le dio. Bob, por supuesto, no puede producir un mensaje cifrado que coincida porque no sabe KA. 4. El documento firmado es inalterable. Fueron Bob tratar de alterar el documento despus de la recepcin, Trent poda probar el juego sucio exactamente de la misma manera que se ha descrito. 5. La firma no puede ser repudiado. Aunque Alice despus afirma que nunca le envi el mensaje, Trent, el AM certificacin diga lo contrario. Recuerde que Trent es la confianza de todos, lo que dice es cierto. Si Bob quiere mostrar Carol un documento firmado por Alice, que puede, AOT revelar su clave secreta con ella. l tiene que ir a travs de Trento de nuevo: (1) Bob lleva el mensaje y Trent, la declaracin de apoyo administrativo y operacional que el mensaje proviene de Alicia, los cifra con KB y lo enva de vuelta a Trento. (2) Trent descifra el paquete con KB. 3) Trent revisa su base de datos y confirma que el mensaje original vino de Alice. (4) Trent vuelve a cifrar el paquete con la clave secreta que comparte con Carol, KC, y lo enva a Carol. (5) Carol descifra el paquete con KC. Ahora puede leer el mensaje y Trent, el AM certificacin de que Alice lo envi. Estos protocolos de trabajo, pero ellos, Aore mucho tiempo para Trent. Tiene que pasar sus das de descifrar y cifrar los mensajes, que acta como intermediario entre cada par de personas que quieren enviar documentos firmados entre s. Se debe mantener una base de datos de mensajes (aunque esto puede evitarse mediante el envo al destinatario una copia del remitente, AOS mensaje cifrado). Es un cuello de botella en cualquier sistema de comunicaciones, incluso si, el AM un programa de software sin sentido. Ms difcil an es la creacin y el mantenimiento de una persona como Trent, alguien que todo el mundo en los fideicomisos de red. Trent tiene que ser infalible, si hace un solo error en un milln de firmas, nadie va a confiar en l. Trent tiene que estar completamente seguro. Si su base de datos de claves secretas nunca sali o si alguien se las arregl para modificar su programacin, todo el mundo, las firmas de apoyo administrativo y operacional sera completamente intil. Documentos falsos supuestos que se firm hace aos podra aparecer. El caos se producira. Los gobiernos se derrumbara. La anarqua reinara. Esto podra funcionar en teora, pero el trabajo doesn, AOT muy bien en la prctica.

Los rboles de firma digital. Ralph Merkle propuesto un esquema de firma digital basada en la criptografa de clave secreta, la produccin de un infinito nmero de firmas de una sola vez utilizando una estructura de rbol [1067,1068]. La idea bsica de este esquema es colocar la raz del rbol en algn archivo pblico, con lo que la autenticacin. La raz firma un mensaje autentica y sus sub-nodos en el rbol. Cada uno de estos nodos de firma de un mensaje y autentica sus sub-nodos, y as sucesivamente. Firmar documentos con Public-Key Cryptography. Hay algoritmos de clave pblica que se pueden utilizar para las firmas digitales. En algunos algoritmos RSA-es un ejemplo (vase la Seccin 19.3), ya sea la clave pblica o la clave privada puede ser utilizada para el cifrado. Cifrado de un documento con su clave privada, y usted tiene una firma digital segura. En otros casos-DSA es un ejemplo (vase la Seccin 20.1)-hay un algoritmo separado para las firmas digitales que no pueden ser utilizados para el cifrado. Esta idea fue inventado por Diffie y Hellman [496] y ampliado y elaborado en otros textos [1282,1328,1024,1283,426]. Ver [1099] para un buen estudio del campo. El protocolo bsico es simple: (1) Alicia encripta el documento con su clave privada, con lo que la firma del documento. (2) Alicia enva el documento firmado a Bob. (3) Bob desencripta el documento con la clave pblica de Alicia, con lo que la verificacin de la firma. Este protocolo es mucho mejor que la anterior. Trent no se necesita o firmar o verificar firmas. (. l es necesaria para certificar la clave pblica de Alice es en realidad la clave pblica), las partes ni siquiera necesita Trent para resolver disputas: si Bob no puede realizar el paso (3), entonces l sabe que la firma no es vlida. Este protocolo tambin satisface las caractersticas que estamos buscando: 1. La firma es autntica, cuando Bob verifica el mensaje con la clave pblica de Alicia, l sabe que ella lo firm. 2. La firma es infalsificable, slo Alice conoce su clave privada. 3. La firma no es reutilizable; de la firma es una funcin del documento y no puede ser transferido a cualquier otro documento. 4. El documento firmado es inalterable; si hay alguna alteracin en el documento, la firma no puede ser verificada con la clave pblica de Alice. 5. La firma no puede ser repudiado. Bob no necesita la ayuda de Alice para verificar su firma.

La firma de documentos y sellos de tiempo. En realidad, Bob puede engaar a Alice en determinadas circunstancias. Se puede volver a utilizar el documento y la firma juntos. Esto no es problema si Alicia firm un contrato (lo que es otra copia del mismo contrato, ms o menos?), Pero puede ser muy emocionante si Alice firm un cheque digital. Supongamos que Alice enva a Bob un cheque firmado digital por $ 100. Bob lleva el cheque al banco, que verifica la firma y se mueve el dinero de una cuenta a otra. Bob, que es un personaje sin escrpulos, guarda una copia del cheque digital. A la semana siguiente, de nuevo se necesita para el banco (o tal vez a un banco diferente). El banco verifica la firma y se mueve el dinero de una cuenta a otra. Si nunca Alice balancea su talonario de cheques, Bob puede seguir as por aos. En consecuencia, las firmas digitales suelen incluir marcas de tiempo. La fecha y hora de la firma se adjunta al mensaje y firmada junto con el resto del mensaje. El banco almacena esta marca de tiempo en una base de datos. Ahora, cuando Bob intenta cobrar de Alice comprobar una segunda vez, el banco comprueba la marca de tiempo en contra de su base de datos. Puesto que el banco ya cobr un cheque de Alice con la misma marca de tiempo, el banco llama a la polica. Bob luego pasa 15 aos en una prisin de Leavenworth leyendo sobre protocolos criptogrficos. Documentos de firma de clave pblica Criptografa y funciones unidireccionales hash. En implementaciones prcticas, algoritmos de clave pblica son a menudo demasiado ineficiente para firmar documentos largos. Para ahorrar tiempo, los protocolos de firma digital a menudo se implementan con funciones hash unidireccionales [432.433]. En lugar de firmar un documento, Alice firma el hash del documento. En este protocolo, tanto la funcin hash unidireccional y el algoritmo de firma digital se acuerdan de antemano. (1) Alice produce un hash unidireccional de un documento. (2) Alicia encripta el hash con su clave privada, con lo que la firma del documento. (3) Alicia enva el documento y el hash firmado a Bob. (4) Bob produce un hash unidireccional de la que Alice documento enviado. Luego, utilizando el algoritmo de firma digital, descifra el hash firmado con la clave pblica de Alicia. Si el hash firmado coincide con el hash que genera, la firma es vlida. Velocidad aumenta drsticamente y, ya que las posibilidades de dos documentos diferentes que tienen el mismo hash de 160-bit son slo uno de 2160, cualquier persona con seguridad se puede equiparar a la firma del hash con la firma del documento. Si una funcin no-hash unidireccional se utilizaron, sera un asunto fcil para crear documentos de mltiples ordenadas por el mismo valor, por lo que cualquier persona que firma un documento en particular podra ser engaado para firmar un gran nmero de documentos. Este protocolo tiene otros beneficios. En primer lugar, la firma pueden ser separados de los del documento. En segundo lugar, los requisitos del receptor de almacenamiento para el documento y la firma son mucho ms pequeos. Un sistema de archivos puede utilizar

este tipo de protocolo para verificar la existencia de documentos sin almacenar los contenidos. La base de datos central slo poda almacenar los valores hash de los archivos. No tiene que ver los archivos en absoluto, los usuarios envan sus hashes a la base de datos y base de datos de las marcas de tiempo de las presentaciones y las almacena. Si existe alguna discrepancia en el futuro acerca de quin cre un documento y cundo, la base de datos podra resolverlo por encontrar el hash en sus archivos. Este sistema tiene enormes implicaciones sobre la privacidad: Alice podra derechos de autor de un documento, pero an mantienen el secreto de documentos. Slo si quisiera probar su autor iba a tener que hacer pblico el documento. (Ver Seccin 4.1). Algoritmos y Terminologa. Hay muchos algoritmos de firma digital. Todos ellos son algoritmos de clave pblica con informacin secreta para firmar los documentos y la informacin pblica para verificar las firmas. A veces, el proceso de firma se llama el cifrado con una clave privada y el proceso de verificacin se llama descifrado con una clave pblica. Esto es engaoso y slo es vlido para un algoritmo RSA. Y algoritmos diferentes tienen diferentes implementaciones. Por ejemplo, en un solo sentido funciones de hash y marcas de tiempo a veces agregar pasos extra al proceso de firma y verificacin. Muchos algoritmos se pueden utilizar para las firmas digitales, pero no para el cifrado. En general, me voy a referir a los procesos de firma y verificacin sin ningn detalle de los algoritmos involucrados. La firma de un mensaje con la clave privada K es: SK (M) y comprobacin de una firma con la clave pblica correspondiente es: VK (M) La cadena de bits adjunta al documento firmado cuando (en el ejemplo anterior, el valor hash unidireccional del documento cifrado con la clave privada) se denomina firma digital, o simplemente la firma. El protocolo completo, por lo que est convencido de que el receptor de un mensaje de la identidad del remitente y la integridad del mensaje, se denomina autenticacin. Para ms detalles sobre estos protocolos estn en la Seccin 3.2. Varias firmas. Cmo Alice y Bob firmar el mismo documento digital? Sin funciones hash unidireccionales, hay dos opciones. Una de ellas es que Alice y Bob firmar copias separadas del propio documento. El mensaje resultante sera ms del doble del tamao del documento original. La segunda es que Alice firma el documento primero y luego la firma de Bob signos de Alice. Esto funciona, pero es imposible verificar la firma de Alicia sin haber verificado Bob. Con funciones hash unidireccionales, varias firmas son fciles: (1) Alice firma el hash del documento. (2) Bob firma el hash del documento.

(3) Bob enva su firma a Alice. (4) Alice enva el documento, su firma, y la firma de Bob a Carol. (5) Carol verifica tanto Alice firma y la firma de Bob. Alice y Bob pueden hacer pasos (1) y (2) ya sea en paralelo o en serie. En el paso (5), Carol puede verificar una firma sin tener que verificar la otra. No repudio y firmas digitales. Alice puede engaar con las firmas digitales y no hay nada que se pueda hacer al respecto. Se puede firmar un documento y luego pretender que no lo hizo. En primer lugar, se firma el documento con normalidad. Entonces, ella annimamente publica su clave privada, convenientemente pierde en un lugar pblico, o simplemente pretende hacer cualquiera de ellos. Alicia entonces afirma que su firma ha sido comprometida y que los dems lo estn utilizando, fingiendo ser ella. Ella rechaza firmar el documento y cualesquiera otros que firm con la clave privada. Esto se llama repudio. Marcas de tiempo puede limitar los efectos de este tipo de engao, pero Alice siempre se puede afirmar que la llave estaba comprometida antes. Si Alice veces las cosas bien, se puede firmar un documento y luego con xito afirman que no lo hizo. Por eso se habla tanto acerca de las claves privadas enterradas en mdulos a prueba de manipulaciones, para que Alice no puede llegar a ella y abusar de ella. Aunque nada se puede hacer acerca de este posible abuso, se pueden tomar medidas para garantizar que las firmas de edad no son invalidadas por las acciones tomadas en disputar unos nuevos. (Por ejemplo, Alice podra "perder" la clave para dejar de pagar Bob para el coche chatarra vendi el da anterior y, en el proceso, la nulidad de su cuenta bancaria.) La solucin es que el receptor de un documento firmado para que lo timestamped [453]. El protocolo general se da en [28]: (1) Alicia firma un mensaje. (2) Alice genera una cabecera que contiene algunos datos identificativos. Ella se concatena con el encabezado del mensaje firmado, los signos que, y lo enva a Trent. (3) Trent verifica la firma fuera y confirma la informacin de identificacin. Y aade una marca de tiempo con el mensaje firmado de Alice y la informacin de identificacin. Luego se firma todo y lo enva a Alice y Bob. (4) Bob verifica la firma de Trent, la informacin de identificacin y firma de Alicia. (5) Alicia verifica el mensaje enviado a Trent Bob. Si ella no se origin el mensaje, habla rpidamente. Otro esquema utiliza Trent despus de los hechos [209]. Despus de recibir un mensaje

firmado, Bob puede enviar una copia a Trento para su verificacin. Trent dar fe de la validez de la firma de Alicia. Las aplicaciones de firma digital. Una de las primeras aplicaciones propuestas de las firmas digitales es facilitar la verificacin de los tratados de prohibicin de pruebas nucleares [1454,1467]. Los Estados Unidos y la Unin Sovitica (alguien se acuerda de la Unin Sovitica?) Permitido entre s para colocar sismgrafos en el otro suelo para controlar los ensayos nucleares. El problema era que cada pas deba cerciorarse de que el pas anfitrin no ha sido la manipulacin de los datos de los sismgrafos de la nacin de monitoreo. Al mismo tiempo, el pas anfitrin necesario para cerciorarse de que el monitor se enva slo la informacin especfica necesaria para el seguimiento. Las tcnicas convencionales de autenticacin puede resolver el primer problema, pero slo las firmas digitales pueden resolver ambos problemas. El pas anfitrin puede leer, pero no modificar, los datos del sismmetro, y la nacin de monitoreo sabe que los datos no han sido alterados. 2.7 Firmas digitales con encriptacin. Mediante la combinacin de firmas digitales con criptografa de clave pblica, desarrollamos un protocolo que combina la seguridad de la encriptacin con la autenticidad de la firma digital. Piense en una carta de su madre: La firma proporciona la prueba de la autora y la envolvente proporciona privacidad. (1) Alice firma el mensaje con su clave privada. SA (M) (2) Alicia encripta el mensaje firmado con la clave pblica de Bob y lo enva a Bob. EB (SA (M)) (3) Bob desencripta el mensaje con su clave privada. DB (EB (SA (M))) = SA (M) (4) Bob verifica con la clave pblica de Alice y se recupera el mensaje. VA (SA (M)) = M La firma antes de cifrar parece natural. Cuando Alicia le escribe una carta, ella lo firma y luego la pone en un sobre. Si ella guard la carta en el sobre y luego firmar el sobre firmado, entonces Bob podra preocuparse si la carta no haba sido reemplazado en secreto. Si Bob mostr a la carta de Carol Alice y sobre, Carol podra acusar de mentir sobre Bob que lleg la carta en la que sobre. En correspondencia electrnica, as, la firma antes de cifrar es una prctica prudente [48]. No slo es ms seguro, un adversario no puede quitar una firma de un mensaje cifrado y aadir su propio, pero existen consideraciones legales: Si el texto a firmar, no es visible para el firmante cuando se estampar su firma, entonces el firma puede tener fuerza legal

poco [1312]. Y hay algunos ataques criptogrficos contra esta tcnica con firmas RSA (ver Seccin 19.3). No hay ninguna razn Alice tiene que usar el mismo par de clave pblica clave para cifrar y firmar. Ella puede tener dos pares de claves: uno para el cifrado y el otro para la firma. La separacin tiene sus ventajas: puede entregar su clave de cifrado a la polica sin comprometer su firma, una llave puede ser custodiados (ver Seccin 4.13), sin afectar a la otra, y las teclas pueden tener diferentes tamaos y pueden caducar en diferentes momentos.

Por supuesto, las marcas de tiempo se debe usar con este protocolo para evitar la reutilizacin de mensajes. Las marcas de tiempo tambin puede proteger contra otros peligros potenciales, tales como la descrita a continuacin. Reenviar el mensaje como una confirmacin de. Considere la posibilidad de una implementacin de este protocolo, con la caracterstica adicional de los mensajes de confirmacin. Cuando Bob recibe un mensaje, se lo devuelve como una confirmacin de recibo. (1) Alicia firma un mensaje con su clave privada, lo cifra con la clave pblica de Bob, y lo enva a Bob. EB (SA (M)) (2) Bob desencripta el mensaje con su clave privada y comprueba la firma con la clave pblica de Alice, verificando as que Alice firmado el mensaje y recuperar el mensaje. VA (DB (EB (SA (M)))) = M (3) Bob firma el mensaje con su clave privada, lo cifra con la clave pblica de Alicia, y lo enva de vuelta a Alice. EA (SB (M)) (4) Alice descifra el mensaje con su clave privada y verifica la firma con la clave pblica de Bob. Si el mensaje resultante es el mismo que envi a Bob, ella sabe que Bob recibi el mensaje con exactitud. Si el mismo algoritmo que se utiliza para el cifrado y verificacin de firmas digitales hay un posible ataque [506]. En estos casos, la operacin de firma digital es la inversa de la operacin de cifrado: VX = EX y SX = DX. Supongamos que Mallory es un usuario del sistema legal con su propia clave pblica y privada. Ahora, vamos a ver como se lee el correo de Bob. En primer lugar, se registra el mensaje de Alice a Bob en el paso (1). Entonces, en algn momento ms tarde, se enva el mensaje a Bob, alegando que se trataba de l (Mallory). Bob cree que se trata de un mensaje legtimo de Mallory, por lo que descifra el mensaje con su clave privada y luego trata de verificar la firma de Mallory por descifrar con la clave pblica de Mallory. El mensaje resultante, que es galimatas, es:

EM (DB (EB (DA (M)))) = EM (DA (M)) Aun as, Bob contina con el protocolo y Mallory enva un recibo: EM (DB (EM (DA M))))

Ahora, todo Mallory tiene que hacer es descifrar el mensaje con su clave privada, cifrarlo con la clave pblica de Bob, descifrarlo nuevo con su clave privada, y cifrarlo con la clave pblica de Alicia. Voil! Mallory tiene M. No es descabellado imaginar que Bob Mallory puede enviar automticamente un recibo. Este protocolo puede estar incorporado en su software de comunicaciones, por ejemplo, los recibos y enviar automticamente. Es esta voluntad de acusar recibo de galimatas que crea la inseguridad. Si Bob comprobado el mensaje de comprensin antes de enviar un recibo, podra evitar este problema de seguridad. Hay mejoras a este ataque que permiten Mallory enviar Bob un mensaje diferente de la que l espiado. Nunca firme los mensajes arbitrarios de otras personas o descifrar mensajes arbitrarios y dar los resultados a otras personas. Frustrar el ataque Resend. El ataque se acaba de describir funciona porque la operacin de cifrado es la misma que la operacin de firma y verificacin de la operacin de descifrado es la misma que la operacin de firma. Un protocolo seguro podra utilizar incluso un funcionamiento ligeramente diferente para el cifrado y las firmas digitales. Utilizacin de diferentes claves para cada operacin resuelve el problema, al igual que el uso de algoritmos diferentes para cada operacin, al igual que las marcas de tiempo, que hacen que el mensaje entrante y el mensaje de salida diferente, al igual que las firmas digitales con funciones hash unidireccionales (ver seccin 2.6). En general, entonces, el siguiente protocolo es seguro como el algoritmo de clave pblica utilizada: (1) Alicia firma un mensaje. (2) Alicia encripta el mensaje y la firma con la clave pblica de Bob (usando un algoritmo de cifrado diferente que para la firma) y lo enva a Bob. (3) Bob desencripta el mensaje con su clave privada. (4) Bob verifica la firma de Alicia. Los ataques contra Public-Key Cryptography. En todos estos protocolos de criptografa de clave pblica, que pasa por alto cmo Alice recibe la clave pblica de Bob. Seccin 3.1 discute esto en detalle, pero vale la pena mencionar aqu.

La manera ms fcil de obtener la clave pblica de alguien es de una base de datos segura en alguna parte. La base de datos tiene que ser pblico, por lo que cualquier persona puede obtener de cualquier otra persona clave pblica. La base de datos tambin tiene que ser protegido de acceso de escritura por nadie excepto Trent, de lo contrario Mallory podra sustituir cualquier clave pblica de Bob. Despus de que l hizo eso, Bob no poda leer los mensajes dirigidos a l, pero pudo Mallory.

Incluso si las claves pblicas se almacenan en una base de datos segura, Mallory todava podra sustituir uno por otro durante la transmisin. Para evitar esto, Trent puede firmar cada clave pblica con su propia clave privada. Trent, cuando se usa de esta manera, es a menudo conocido como una autoridad de certificacin Key o Key Distribution Center (KDC). En las aplicaciones prcticas, el KDC firma un mensaje compuesto formado por el nombre del usuario, su clave pblica, y cualquier otra informacin importante sobre el usuario. Este mensaje compuesto firmado se almacena en la base de datos del KDC. Cuando Alicia llega clave de Bob, que verifica la firma del KDC para cerciorarse de la validez de la clave. A fin de cuentas, esto no es hacer cosas imposibles para Mallory, pero ms difcil. Alice todava tiene la clave pblica del KDC almacenada en alguna parte. Mallory tendra que sustituir su propia clave pblica correspondiente a esa tecla, corromper la base de datos y sustituir sus propias llaves para las claves vlidas (todos firmados con su clave privada como si fuera el KDC), y entonces l est en el negocio. Pero, incluso en papel se pueden falsificar firmas si Mallory va a bastantes problemas. El intercambio de claves se discutir en detalle en la Seccin 3.1. 2.8 Generacin aleatoria y Pseudo-Random Sequence. Por qu se molest con la generacin de nmeros aleatorios en un libro sobre criptografa? Ya hay un generador de nmeros aleatorios incorporado en la mayora de cada compilador, una mera funcin telefnica. Por qu no usar eso? Desafortunadamente, esos generadores de nmeros aleatorios son casi definitivamente no es lo suficientemente seguro para la criptografa, y probablemente ni siquiera azar muy. La mayora de ellos son excesivamente mala. Generadores de nmeros aleatorios no son al azar, ya que no tiene que ser. Las aplicaciones ms simples, como juegos de ordenador, necesita nmeros aleatorios tan pocos que apenas darse cuenta. Sin embargo, la criptografa es extremadamente sensible a las propiedades de los generadores de nmeros aleatorios. Utilice un pobre generador de nmeros aleatorios y comienza a recibir extraas correlaciones y resultados extraos [1231,1238]. Si usted est en funcin de su generador de nmeros aleatorios para la seguridad, las correlaciones extraas y resultados extraos son las ltimas cosas que usted desea. El problema es que un generador de nmeros aleatorios-no produce una secuencia aleatoria. Probablemente no produce nada que se parezca ni remotamente como una secuencia aleatoria. Por supuesto, es imposible producir algo verdaderamente aleatorio en un equipo. Donald Knuth cita a John von Neumann como diciendo: "Toda persona que considere mtodos aritmticos para producir dgitos aleatorios es, por supuesto, en un estado de pecado" [863]. Las computadoras son bestias deterministas: Stuff entra por un

extremo, completamente predecibles ocurren dentro de las operaciones, y cosas diferentes que sale del otro extremo. Ponga la misma materia en dos ocasiones diferentes y el mismo material que sale dos veces. Ponga la misma materia en dos equipos idnticos y del mismo material que sale de los dos. Un equipo slo puede ser en un nmero finito de estados (un nmero finito grande, pero un nmero finito, no obstante), y el material que sale siempre ser una funcin determinista de la materia que entraba y estado actual del ordenador. Esto significa que cualquier generador de nmeros aleatorios en un ordenador (por lo menos, en una mquina de estado finito) es, por definicin, peridica. Cualquier cosa que es peridica es, por definicin, predecible. Y si algo es previsible, no puede ser aleatoria. Un verdadero generador de nmeros aleatorios requiere cierta entrada al azar, un equipo no puede proporcionar esto. Secuencias pseudoaleatorias. Lo mejor que un ordenador puede producir es un generador pseudo-aleatorio de secuencia. Qu, el AM que? Muchas personas han tomado una pualada a definir de manera formal, pero aqu, ll mano de onda. Una secuencia pseudo-aleatoria es uno que se parece al azar. La secuencia, perodo AOS debe ser lo suficientemente largo para que una secuencia finita de tiempo razonable, that es decir, que se utiliza realmente, no AIIS peridica. Si usted necesita un billn de bits aleatorios, Don, AOT elegir un generador de secuencia que se repite despus de slo diecisis mil pedazos. Estos subsecuencias no peridicas relativamente cortos deben ser tan indistinguibles como sea posible a partir de secuencias aleatorias. Por ejemplo, deben tener aproximadamente el mismo nmero de unos y ceros, aproximadamente la mitad de las carreras (secuencias de la misma bits) debe ser de longitud uno, un cuarto de longitud de dos, un octavo de longitud tres, y as sucesivamente. No deben ser compresible. La distribucin de longitudes de ejecucin para ceros y unos debe ser la misma [643,863,99,1357]. Estas propiedades se pueden medir empricamente y luego se compara con las expectativas de estadstica mediante la prueba de chi-cuadrado. Para nuestros propsitos, es un generador de secuencia pseudoaleatoria si tiene esta propiedad: 1. Se ve aleatorio. Esto significa que se pasa todas las pruebas estadsticas de aleatoriedad que podemos encontrar. (Comience con los que est en [863].) Una gran cantidad de esfuerzo en producir buenas secuencias pseudoaleatorias en el ordenador. Las discusiones de los generadores abundan en la literatura acadmica, junto con varias pruebas de aleatoriedad. Todos estos generadores son peridicas (all, AOS que no hay escape); pero con perodos de potenciales de 2256 bits y los ms altos, se pueden utilizar para las aplicaciones ms grandes. El problema es todava esas extraas correlaciones y resultados extraos. Cada generador pseudo-aleatorio-secuencia se va a producir si se utilizan de una manera determinada. Y que, el AM lo que un criptoanalista se utilizan para atacar el sistema. Criptogrficamente seguro secuencias pseudoaleatorias. Aplicaciones criptogrficas exigen mucho ms de un generador pseudo-aleatoriosecuencia que hacen la mayora de las otras aplicaciones. Aleatoriedad criptogrfica no significa slo el azar estadstico, aunque eso es parte de ella. Para una secuencia para

ser criptogrficamente seguro pseudo-aleatoria, sino que tambin debe tener esta propiedad: 2. Es impredecible. Debe ser computacionalmente imposible de predecir lo que el bit aleatorio siguiente ser, dado el conocimiento completo del algoritmo o hardware y la generacin de la secuencia de todos los bits anteriores en la secuencia. Criptogrficamente seguro secuencias pseudoaleatorias no debe ser compresible ... a menos que sepa la clave. La clave es generalmente la semilla utilizada para establecer el estado inicial del generador. Al igual que cualquier algoritmo criptogrfico, criptogrficamente seguro pseudo-randomsecuencia generadores estn sujetos a los ataques. As como es posible romper un algoritmo de cifrado, es posible romper un criptogrficamente seguro pseudo-aleatorio generador de secuencia. Haciendo generadores resistentes al ataque es lo que tiene que ver con la criptografa. Secuencias reales de azar. Ahora estamos a la deriva en el dominio de los filsofos. Existe tal cosa como la aleatoriedad? Qu es una secuencia al azar? Cmo se sabe si una secuencia es aleatoria? Es "101110100" ms aleatoria que "101010101"? La mecnica cuntica nos dice que no es honesto a la bondad aleatoriedad en el mundo real. Pero, podemos conservar esa aleatoriedad en el mundo determinista de chips de computadoras y mquinas de estados finitos? Filosofa aparte, desde nuestro punto de vista de un generador de secuencia aleatoria es real si tiene esta caracterstica adicional tercera: 3. No se puede reproducir con fiabilidad. Si se ejecuta el generador de secuencia dos veces con la misma entrada exacta (por lo menos tan exacta como sea humanamente posible), obtendr dos secuencias al azar sin ninguna relacin. La salida de un generador que satisface estas tres propiedades ser lo suficientemente bueno para una pastilla de una sola vez, la generacin de claves, y cualesquiera otras aplicaciones criptogrficas que requieren un generador de secuencia verdaderamente aleatoria. La dificultad est en determinar si una secuencia es realmente aleatoria. Si repetidamente cifrar una cadena con DES y una clave determinada, voy a tener un agradable, de aspecto aleatorio de salida, usted no ser capaz de decir que es no aleatoria a menos que alquilar tiempo en la galleta de la NSA DES.