[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Esta es CS50.] [CS50.TV]
Vamos a echar un vistazo a RSA, un algoritmo utilizado para cifrar datos.
Los algoritmos de cifrado como César y sistemas de cifrado Vigenère no son muy seguras.
Con el cifrado César, un atacante sólo necesita tratar 25 diferentes claves
para obtener texto sin formato del mensaje.
Mientras que el sistema de cifrado Vigenère es más seguro que el cifrado César
por el espacio de búsqueda grande para las llaves, una vez que un atacante
conoce la longitud de la clave en un sistema de cifrado Vigenère,
que se puede determinar a través de un análisis de los patrones en el texto cifrado,
el cifrado Vigenère no es mucho más seguro que el cifrado César.
RSA, por otra parte, no es vulnerable a los ataques de este tipo.
El cifrado César y cifrado Vigenère utilizar la misma clave
para cifrar y descifrar un mensaje.
Esta propiedad hace que estos algoritmos cifrados simétricos clave.
Un problema fundamental con algoritmos de clave simétrica
es que se basan en la codificación y el envío del mensaje
y el que recibe y descifra el mensaje
que ya han acordado por adelantado en la llave que ambos utilizan.
Pero tenemos un poco de un problema de inicio aquí.
¿Cómo dos equipos que quieren comunicar establecer una clave secreta entre ellos?
Si la clave tiene que ser secreto, entonces necesitamos una manera de cifrar y descifrar la clave.
Si todo lo que tenemos es la criptografía de clave simétrica
entonces he regresado al mismo problema.
RSA, por otra parte, utiliza un par de claves,
una para encriptación y otro para desencriptación.
Uno se llama la clave pública, y el otro es la clave privada.
La clave pública se utiliza para cifrar mensajes.
Como se puede adivinar por su nombre, podemos compartir nuestra clave pública con
cualquier persona que quiera sin comprometer la seguridad de un mensaje cifrado.
Los mensajes cifrados con una clave pública
sólo se puede descifrar con su clave privada correspondiente.
Mientras que usted puede compartir su clave pública, siempre se debe mantener en secreto su clave privada.
y sólo la clave privada se puede utilizar para descifrar los mensajes
2 usuarios si desea enviar mensajes de cifrado con RSA
de ida y vuelta los usuarios necesitan tener su propio par de claves pública y privada.
Mensajes de usuario 1 a usuario 2
sólo utilizan par de claves de usuario 2, y los mensajes de usuario a usuario 2 1
sólo utilizan un par de claves de usuario.
El hecho de que hay 2 teclas separadas para cifrar y descifrar mensajes
RSA hace un algoritmo de clave asimétrica.
No necesitamos para cifrar la clave pública con el fin de enviar a otro ordenador
ya que la clave pública es de todos modos.
Esto significa que RSA no tiene el mismo problema de inicio
como los algoritmos de clave simétrica.
Así que si quiero enviar un mensaje utilizando cifrado RSA
a Rob, primero tendrás la clave pública de Rob.
Para generar un par de claves, Rob tiene que escoger dos números primos grandes.
Estos números se utilizan tanto en las llaves públicas y privadas,
pero la clave pública sólo se utiliza el producto de estos números 2,
no los propios números.
Una vez que haya cifrado el mensaje con la clave pública de Rob
Puedo enviar el mensaje a Rob.
Para un equipo, los números de factoring es un problema difícil.
La clave pública, recuerda, utiliza el producto de dos números primos.
Este producto debe tener sólo 2 factores,
que resultan ser los números que componen la clave privada.
Con el fin de descifrar el mensaje, RSA se utiliza esta clave privada
o los números multiplicados entre sí en el proceso de creación de la clave pública.
Debido a que es computacionalmente difícil factorizar el número
utilizado en una clave pública en los 2 números utilizados en la clave privada
es difícil para un atacante descifrar la clave privada
que será necesario para descifrar el mensaje.
Ahora vamos a entrar en algunos detalles de menor nivel de RSA.
Primero vamos a ver cómo podemos generar un par de claves.
En primer lugar, vamos a necesitar dos números primos.
Vamos a llamar a estos números 2 p y q.
Con el fin de recoger p y q, en la práctica seudoaleatoria generaría
grandes cantidades y luego usar una prueba para determinar si existe o no
esos números son probablemente mejor momento.
Podemos mantener la generación de números aleatorios y otra vez
hasta que tengamos dos primos que podemos utilizar.
Aquí vamos a escoger p = q = 23 y 43.
Recuerde, en la práctica, p y q debe ser un número mucho mayor.
Por lo que sabemos, cuanto mayores sean los números, más difícil será
para romper un mensaje cifrado.
Pero también es más caro para cifrar y descifrar mensajes.
Hoy en día es a menudo se recomienda que p y q son al menos 1024 bits,
que pone a cada número en más de 300 dígitos decimales.
Pero vamos a recoger estos pequeños números de este ejemplo.
Ahora vamos a multiplicar p y q en conjunto para obtener un número de 3 º,
que llamaremos n.
En nuestro caso, n = 23 * 43, que = 989.
Tenemos n = 989.
A continuación vamos a multiplicar p - 1 con q - 1
para obtener un número de cuarto, que llamaremos m.
En nuestro caso, m = 22 * ​​42, que = 924.
Contamos con m = 924.
Ahora vamos a necesitar un número e que es primo con m
y menos de m.
Dos números son primos relativos o primos entre sí,
si el número entero único positivo que los divide de manera uniforme tanto: 1.
En otras palabras, el máximo común divisor de e y m
debe ser 1.
En la práctica, es común que e sea el número primo 65537
siempre y cuando este número no pasa de ser un factor de m.
Para las llaves, vamos a recoger e = 5
ya que 5 es primo con 924.
Por último, vamos a necesitar un número más, que llamaremos d.
D debe ser un valor que satisface la ecuación de = 1 (mod m).
Este mod m significa que vamos a usar algo llamado aritmética modular.
En la aritmética modular, una vez que recibe un número más alto que algunas límite superior
que bajara a 0.
Un reloj, por ejemplo, utiliza la aritmética modular.
Un minuto después de 1:59, por ejemplo, es 2:00,
no 1:60.
El minutero se ha envuelto alrededor de 0
al llegar a un límite superior de 60.
Por lo tanto, podemos decir que 60 es equivalente a 0 (mod 60)
y 125 es equivalente a 65 es equivalente a 5 (mod 60).
Nuestra clave pública será el par electrónico y n
donde en este caso e es 5 y n es 989.
Nuestra llave privada será el par d y n,
que en nuestro caso es de 185 y 989.
Observe que nuestro original de números primos p y q no aparecen
en cualquier parte de nuestras claves privadas o públicas.
Ahora que tenemos nuestro par de llaves, vamos a echar un vistazo a cómo podemos cifrar
y descifrar un mensaje.
Quiero enviar un mensaje a Rob,
por lo que será el de generar este par de claves.
Entonces voy a pedir Rob por su clave pública, que voy a utilizar
para cifrar un mensaje para enviar a él.
Recuerda, es totalmente aceptable para Rob para compartir su clave pública conmigo.
Pero no estaría bien compartir su clave privada.
No tengo ni idea de lo que su clave privada.
Podemos dividir nuestro mensaje m para arriba en varios trozos
todo menor que n y luego encriptar cada uno de los trozos.
Vamos a cifrar la cadena CS50, que podemos dividir en 4 trozos,
uno por cada letra.
Para encriptar mi mensaje, voy a tener que convertirlo en
algún tipo de representación numérica.
Vamos a concatenar los valores ASCII con los personajes de mi mensaje.
Con el fin de cifrar un mensaje dado m
Voy a tener que calcular c = m al E (mod n).
Pero m debe ser menor que n,
o bien el mensaje completo no puede ser expresado módulo n.
Podemos romper m hasta en varios trozos, todos los cuales son más pequeñas que n,
y cifrar cada uno de esos trozos.
Cifrado de cada uno de estos trozos, obtenemos c1 = 67 a la 5 (mod 989)
que = 658.
Para nuestro segundo fragmento que tenemos 83 a la 5 (mod 989)
que = 15.
Para nuestro trozo tercera tenemos 53 a la 5 (mod 989)
que es = 799.
Y por último, para nuestro trozo fin tenemos 48 a la 5 (mod 989)
que = 975.
Ahora podemos enviar a través de estos valores cifrados a Rob.
Aquí tienes, Rob.
Mientras que nuestro mensaje está en vuelo, vamos a echar otro vistazo
en cómo hemos llegado hasta ese valor para d.
Nuestro número d necesaria para satisfacer 5d = 1 (mod 924).
Esto hace que d el inverso multiplicativo de 5 modulo 924.
Dado 2 enteros, A y B, el algoritmo de Euclides extendido
se puede utilizar para encontrar el máximo común divisor de estos 2 números enteros.
También nos dan 2 otros números, x e y,
que satisfacen la ecuación ax + by = el máximo común divisor de a y b.
¿Cómo nos ayuda?
Bueno, conectar e = 5 para una
y m = 924 para b
ya sabemos que estos números son primos entre sí.
Su máximo común divisor es 1.
Esto nos da 5x + 924y = 1
o 5x = 1 - 924y.
Pero si sólo se preocupan por todo modulo 924
entonces podemos abandonar la - 924y.
Piense en el reloj.
Si el minutero está en 1 y luego pasar exactamente 10 horas,
sabemos que la manecilla de los minutos todavía estará en el 1.
Aquí empezamos a 1 y luego envolver veces exactamente de y,
por lo que todavía va a estar en 1.
Tenemos 5x = 1 (mod 924).
Y aquí esta x es el mismo que el d buscábamos antes,
por lo que si se utiliza el algoritmo de Euclides extendido
para obtener este número x, que es el número que debe usar como nuestro d.
Ahora vamos a ejecutar el algoritmo extendido de Euclides para a = 5
y b = 924.
Vamos a utilizar un método llamado el método de la tabla.
La mesa contará con 4 columnas, x, y, d, k.
Nuestra mesa comienza con 2 filas.
En la primera fila tenemos 1, 0, entonces nuestro valor de a, que es 5,
y nuestra segunda fila es 0, 1, y nuestro valor de b, que es 924.
El valor de la columna cuarta, k, será el resultado
de dividir el valor de d en la fila de arriba con el valor de d
en la misma fila.
Tenemos 5 dividido por 924 es 0 con algún resto.
Eso significa que tenemos k = 0.
Ahora el valor de todas las demás células será el valor de la celda 2 filas por encima de lo
menos el valor de la fila por encima de ella k veces.
Vamos a empezar con d en la 3 ª fila.
Tenemos 5 a 924 * 0 = 5.
Siguiente tenemos 0 - 1 * 0 que es 0
y 1 - 0 * 0 que es 1.
No está mal, así que vamos a pasar a la siguiente fila.
En primer lugar tenemos nuestro valor de k.
924 dividido por 5 = 184 con algún resto,
por lo que nuestro valor de k es 184.
Ahora 924 a 5 * 184 = 4.
1 a 0 * 184 es 1 y 0 - 1 * 184 es -184.
Muy bien, vamos a hacer la siguiente fila.
Nuestro valor de k será 1 porque
5 dividido por 4 = 1 con algún resto.
Vamos a llenar las otras columnas.
5-4 * 1 = 1.
0 a 1 * 1 = -1.
Y 1 - 184 * 1 es 185.
Vamos a ver lo que nuestro siguiente valor de k sería.
Bueno, parece que tenemos 4 dividido por 1, que es 4.
En este caso en el que estamos dividiendo por 1 tal que k es igual a
el valor de d en la fila de arriba significa que hemos terminado con nuestro algoritmo.
Podemos ver aquí que tenemos x = 185 ey = -1 en la última fila.
Ahora vamos a volver a nuestra meta original.
Hemos dicho que el valor de x, como resultado de la ejecución de este algoritmo
sería el inverso multiplicativo de un (b mod).
Esto significa que 185 es el inverso multiplicativo de 5 (mod 924)
lo que significa que tienen un valor de 185 para d.
El hecho de que d = 1 en la última fila
verifica que el correo fue primos entre sí a m.
Si no fuera 1, entonces tendríamos que escoger un correo nuevo.
Ahora vamos a ver si Rob ha recibido mi mensaje.
Cuando alguien me envía un mensaje cifrado
siempre que he mantenido mi clave privada en secreto
Yo soy la única persona que puede descifrar el mensaje.
Para descifrar un pedazo c puedo calcular el mensaje original
es igual a la cantidad de potencia d (mod n).
Recuerde que d y n son de mi clave privada.
Para obtener un mensaje lleno de sus fragmentos que descifrar cada bloque
y concatenar los resultados.
Exactamente qué tan seguro es RSA?
La verdad es que no lo sé.
La seguridad se basa en el tiempo que le tomaría a un atacante descifrar un mensaje
encriptada con RSA.
Recuerde que un atacante tiene acceso a su clave pública,
que contiene tanto e y n.
Si el atacante consigue factorizar n en sus 2 primos, p y q,
entonces podría calcular d usando el algoritmo de Euclides extendido.
Esto le da la clave privada, que se puede utilizar para descifrar cualquier mensaje.
Pero la rapidez podemos factorizar enteros?
Una vez más, no lo sé.
Nadie ha encontrado una manera rápida de hacerlo,
lo que significa que dado n suficientemente grande
que llevaría a un atacante irrealmente largo
factorizar el número.
Si alguien revela una forma rápida de factorizar enteros
RSA se rompería.
Pero incluso si factorización de enteros es inherentemente lento
el algoritmo RSA todavía podría tener algún defecto en ella
que permite la fácil descifrado de mensajes.
Nadie ha encontrado y revela una falla, sin embargo,
pero eso no significa que no existe uno.
En teoría, alguien podría estar por ahí leyendo todos los datos cifrados con RSA.
Hay otro poco de un problema de privacidad.
Si Tommy encripta algún mensaje con mi clave pública
y un atacante cifra el mensaje mismo con mi clave pública
el atacante se verá que los dos mensajes son idénticos
y así saber lo que Tommy cifrado.
A fin de evitar esto, los mensajes son típicamente rellenado con bits aleatorios
antes de ser cifrados para que el mismo mensaje cifrado
múltiples veces será diferente, siempre y cuando el relleno en el mensaje es diferente.
Pero recuerda cómo tenemos que dividir los mensajes en trozos
de modo que cada fragmento es menor que n?
Relleno los trozos significa que tengamos que dividir las cosas
en trozos aún más desde el trozo acolchado debe ser menor que n.
El cifrado y descifrado son relativamente caros con RSA,
y por lo tanto necesidad de romper un mensaje en trozos muchos puede ser muy costoso.
Si un gran volumen de datos tiene que ser cifrados y descifrados
podemos combinar los beneficios de algoritmos de clave simétrica
con los de RSA para obtener la seguridad y la eficiencia.
Aunque no voy a entrar en ello aquí,
AES es un algoritmo de clave simétrica como el cifrado Vigenère y César
pero mucho más difícil de roer.
Por supuesto, no podemos usar AES sin establecer una clave secreta compartida
entre los 2 sistemas y vimos el problema con eso antes.
Pero ahora podemos utilizar RSA para establecer la clave secreta compartida entre los 2 sistemas.
Llamaremos a la computadora que envía los datos del remitente
y el equipo que recibe los datos del receptor.
El receptor tiene un par de claves RSA y envía
la clave pública al remitente.
El emisor genera una clave de AES,
cifra con la clave pública RSA del receptor,
y envía la clave AES para el receptor.
El receptor descifra el mensaje con su clave privada RSA.
Tanto el emisor como el receptor tienen ahora una clave compartida AES entre ellos.
AES, que es mucho más rápido en el cifrado y descifrado de RSA,
Ahora se puede utilizar para cifrar los grandes volúmenes de datos y enviarlos al receptor,
que puede descifrar utilizando la misma clave.
AES, que es mucho más rápido en el cifrado y descifrado de RSA,
Ahora se puede utilizar para cifrar los grandes volúmenes de datos y enviarlos al receptor,
que puede descifrar utilizando la misma clave.
Sólo necesitábamos RSA para transferir la clave compartida.
Ya no necesita usar RSA en absoluto.
Parece que tengo un mensaje.
No importa si alguien lee lo que hay en el avión de papel antes de que me llamó
porque yo soy el único que tiene la clave privada.
Vamos a descifrar cada uno de los trozos en el mensaje.
El primer trozo, 658, elevamos a la potencia d, que es de 185,
mod n, que es 989, es igual a 67,
que es la letra C en ASCII.
Ahora, en el segundo fragmento.
El segundo fragmento tiene un valor 15,
que elevamos a la potencia 185a,
mod 989, y esto es igual a 83
que es la letra S en ASCII.
Ya por el trozo tercero, que tiene un valor 799, elevamos a 185,
mod 989, y esto es igual a 53,
que es el valor del carácter ASCII en 5.
Ahora, para el último fragmento, que tiene un valor 975,
elevamos a 185, mod 989,
y esto es igual a 48, que es el valor de 0 en el carácter ASCII.
Mi nombre es Rob Bowden, y esto es CS50.
[CS50.TV]
RSA en absoluto.
RSA en absoluto. [Risas]
En todas.