[Powered by Google Translate] [RSA] [Rob Bowden] [Tommy MacWilliam] [Harvard University] [Esta é CS50.] [CS50.TV] Imos dar un ollo na RSA, un algoritmo utilizado para cifrar datos. Algoritmos de cifrado como César e cifras de Vigenère non son moi seguras. Coa cifra de César, o dianteiro só precisa probar 25 claves diferentes para texto simple da mensaxe. Aínda que a cifra de Vigenère é máis seguro que a cifra de César por mor do maior espazo de procura de claves, unha vez que un atacante coñece a lonxitude da clave de cifrado de Vigenère, que pode ser determinada a través dunha análise dos patróns de texto codificado, a cifra de Vigenère que non é moito máis seguro que a cifra de César. RSA, por outra banda, non é vulnerable a ataques como este. A cifra de César e Vigenère cifra de usar a mesma clave para cifrar e descifrar mensaxes. Esta propiedade fai que esas cifras de algoritmos de claves simétricas. Un problema fundamental con algoritmos de claves simétricas é que contan coa cifrar e enviar unha mensaxe eo de recepción e decodificación da mensaxe para xa acordaron adiantado na clave ambos han empregar. Pero nós temos un pouco de un problema de arranque aquí. Como dous ordenadores que queren comunicarse establecer unha clave secreta entre eles? Se a chave debe ser secreta, entón necesitamos un xeito de cifrar e descifrar a chave. Se todo o que temos é a criptografía de clave simétrica entón acabamos de volver para o mesmo problema. RSA, por outra banda, utiliza un par de chaves, un para cifrado e outro para a decodificación. Unha está chamada a clave pública, e outra é a clave privada. A clave pública é usada para cifrar mensaxes. Como podes imaxinar polo nome, podemos compartir a nosa chave pública con calquera persoa que queira, sen comprometer a seguridade dunha mensaxe cifrada. Mensaxes cifradas con unha chave pública só pode ser decifrada coa súa clave privada correspondente. Mentres pode compartir a súa chave pública, ten que sempre manter o seu segredo da clave privada. Como a chave privada debe ser mantida en segredo e só a chave privada pode ser usado para descifrar mensaxes, se dous usuarios queren enviar mensaxes cifrada con RSA e cara atrás ambos os usuarios precisan ter o seu par de chaves pública e privada propia chave. Mensaxes de usuario para un usuario 2 só usar un par de chaves dúas usuario, e mensaxes de usuarios do 2 ao 1 usuario utilizar só un usuario par de chaves. O feito de que hai dúas chaves separadas para cifrar e descifrar mensaxes RSA fai un algoritmo de clave asimétrica. Nós non precisamos para cifrar a clave pública, a fin de envialo a outro ordenador xa que a clave é pública calquera maneira. Isto significa que o RSA non teñen o mesmo problema de inicio como un algoritmo de chave simétrica. Como facer dous ordenadores que queren comunicarse establecer unha clave secreta entre eles? Se a chave debe ser secreta, entón necesitamos un xeito de cifrar e descifrar a chave. Se todo o que temos é a criptografía de clave simétrica, entón temos só volver para o mesmo problema. RSA, por outra banda, utiliza un par de chaves, un para cifrado e outro para a decodificación. Unha está chamada a clave pública, e outra é a clave privada. A clave pública é usada para cifrar mensaxes. Como podes imaxinar polo nome, podemos compartir a nosa chave pública con alguén que queremos sen comprometer a seguridade dunha mensaxe cifrada. Mensaxes cifradas con unha chave pública só pode ser decifrada coa súa clave privada correspondente. Mentres pode compartir a súa chave pública, ten que sempre manter o seu segredo da clave privada. Como a chave privada debe ser mantida en segredo e só a clave privada pode ser usado para descifrar as mensaxes dous usuarios queren enviar mensaxes cifradas con RSA adiante e cara atrás ambos os usuarios precisan ter o seu par de chaves pública e privada propia chave. Mensaxes de usuario para un usuario 2 usar só un par de chaves 2 usuarios e mensaxes de usuario a usuario 2 1 usar só un par de claves de usuario. O feito de que hai dúas chaves separadas para cifrar e descifrar mensaxes RSA fai un algoritmo de clave asimétrica. Nós non precisamos para cifrar a clave pública, a fin de envialo a outro ordenador xa que a clave é pública calquera maneira. Isto significa que o RSA non teñen o mesmo problema de inicio como os algoritmos de clave simétrica. Entón, se eu quero enviar unha mensaxe utilizando o cifrado RSA para Rob, eu vou primeiro precisa de clave pública de Rob. Para xerar un par de chaves, Rob necesita escoller dous números primos grandes. Eses números serán usados ​​en ambas as chaves, público e privado, pero a clave pública só vai usar o produto deses dous números, non os propios números. Unha vez que eu teño a mensaxe cifrada usando a chave pública de Rob Podo enviar a mensaxe a Rob. A un ordenador, fatorar números é un problema difícil. A clave pública, lembre, usou o produto de dous números primos. Este produto debe entón ter só dous elementos, que acontecen ser os números que compoñen a chave privada. A fin de descifrar a mensaxe, a RSA vai utilizar esta clave privada ou os números multiplicados xuntos no proceso de creación da clave pública. Por computacionalmente difícil fatorar o número utilizado en unha chave pública para os dous números utilizados na clave privada É difícil para un invasor descubrir a clave privada que será necesaria para descifrar a mensaxe. Agora imos entrar en algúns detalles de nivel máis baixo da RSA. Imos primeiro ver como podemos xerar un par de claves. En primeiro lugar, imos ter que dous números primos. Imos chamar eses dous números pe q. A fin de elixir p e q, na práctica, sería pseudorandomly xerar grandes números e, a continuación, usar unha proba para determinar se ou non estes números son probablemente primo. Podemos manter a xeración de números aleatorios e outra vez ata que teñamos dous curmáns que podemos utilizar. Aquí imos escoller p = 23 e q = 43. Lembra, na práctica, p e q deben ser números moi grandes. Tanto como sabemos, o maior dos números, o que é máis difícil para romper unha mensaxe cifrada. Pero tamén é máis caro para cifrar e descifrar mensaxes. Hoxe é frecuentemente recomendado que p e q son polo menos 1024 bits, o que pon cada número en máis de 300 díxitos decimais. Pero imos incorporarse eses números pequenos para este exemplo. Agora imos multiplicar p e q xuntos para obter un número de 3, que chamaremos de n. No noso caso, n = 23 * 43, que é = 989. Temos n = 989. A continuación, imos multiplicar p - 1 con q - 1 para obter un número 4, que chamaremos de m. No noso caso, m = 22 * ​​42, que é = 924. Temos m = 924. Agora imos ter un número e que é relativamente privilexiada para m e menos que m. Dous números son relativamente primos ou primos entre si o enteiro positivo só que divide os dous uniformemente é 1. Noutras palabras, o maior divisor común de e em debe ser 1. Na práctica, é común e ser o número primo 65537 mentres este número non ocorrer de ser un factor de m. Para os nosos chaves, nós imos busca-e = 5 desde 5 é relativamente privilexiada para 924. Finalmente, imos ter máis dun número, que chamaremos de d. D ten que ser un valor que satisfai a ecuación de = 1 (mod m). Este mod m significa que imos usar algo chamado aritmética modular. Na aritmética modular, xa que un número maior que recibe algún límite superior el volverá a 0. Un reloxo, por exemplo, usa aritmética modular. Un minuto despois da 1:59, por exemplo, é de 2:00, non 1:60. O punteiro dos minutos ten enrolado a 0 ao alcanzar un límite superior de 60 anos. Entón, podemos dicir que 60 é equivalente a 0 (mod 60) e 125 é equivalente a 65 é igual a 5 (mod 60). A nosa clave pública será o é par e n onde, neste caso, e 5 e n ​​é 989. A nosa clave privada será o par D e N, que no noso caso é de 185 e 989. Teña en conta que a nosa orixinal primos p e q non aparecen en calquera lugar nas nosas chaves privadas ou públicas. Agora que temos o noso par de chaves, imos dar un ollo a como podemos cifrar e descifrar mensaxes. Eu quero enviar unha mensaxe a Rob, entón el vai ser o único a xerar ese par de chaves. Entón eu vou pedir para Rob súa chave pública, que eu vou usar para cifrar unha mensaxe para enviar a el. Lembre, é totalmente ben para Rob para compartir a súa clave pública comigo. Pero non sería bo para compartir a súa clave privada. Eu non teño ningunha idea do que a súa clave privada é. Podemos romper a nosa mensaxe m-se ​​en varios anacos todos menores que n e, a continuación, cifrar cada un destes bloques. Imos cifrar o CS50 cadea, que pode dividirse en catro anacos, unha por letra. Para cifrar a miña mensaxe, eu vou ter que convertelo en algún tipo de representación numérica. Imos concatenar os valores ASCII cos personaxes da miña mensaxe. Para cifrar unha mensaxe m dado Vou ter para calcular c = m para o correo (mod n). Pero m debe ser menor que n, ou ben a mensaxe completa non pode ser expresada módulo n. Podemos dividir m por enriba en varios anacos, as cales son menores que n, e codificar cada unha destas partes. Criptografando cada un destes anacos, temos C1 = 67 para o 5 (mod 989) que = 658. Para o noso anaco segundo temos 83 a 5 (mod 989) cal = 15. Para o noso anaco terceiro temos 53 ao 5 (mod 989) que = 799. E, finalmente, para o noso último anaco temos 48 ao 5 (mod 989) que é = 975. Agora podemos enviar máis estes valores criptografada para Rob. Aquí está, Rob. Mentres que a nosa mensaxe está en voo, imos ter outro ollar como chegamos ese valor para d. O noso número d necesario para satisfacer 5D = 1 (mod 924). Isto fai que o d inverso multiplicativo módulo de 5 924. Dado dous enteiros, A e B, o algoritmo estendido de Euclides pode ser usada para atopar o maior divisor común destes dous números enteiros. Tamén pode dar-nos outros dous números, X e Y, que satisfán a ecuación ax + by = máximo divisor común de a e b. Como iso pode axudar? Ben, conectar e = 5 para un e m = 924 para b xa sabemos que estes números son primos entre si. O seu maior divisor común é 1. Iso nos dá 5x + 924y = 1 ou 5x = 1 - 924y. Pero, só se preocupan con todo o módulo 924 entón podemos deixar caer o - 924y. Pense de novo para o reloxo. Se o punteiro dos minutos é o 1 e, a continuación, exactamente 10 horas pasan, sabemos que o punteiro dos minutos vai aínda estar na 1. Aquí comezan o 1 e, a continuación, participa en torno a veces exactamente y, por iso aínda vai ser en 1. Temos 5x = 1 (mod 924). E aquí está x é o mesmo que o d estabamos buscando antes, así, usar o algoritmo estendido de Euclides para obter este número x, que é o número que debe usar como o noso d. Agora imos facer o algoritmo estendido de Euclides para a = 5 e b = 924. Imos usar un método chamado de método de táboa. Nosa mesa terá 4 columnas, x, y, d, e k. Nosa mesa comeza con dúas liñas. Na primeira liña temos 1, 0, entón o noso valor de un, o que é 5, ea nosa segunda liña é 0, 1, eo seu valor para b, que é 924. O valor da columna 4, k, será o resultado de dividir o valor d na liña anterior co valor de d na mesma liña. Temos 5 dividido por 924 é 0, con algún resto. Isto significa que temos k = 0. Agora, o valor de todas as outras células, será o valor da cela de 2 liñas por riba dela menos o valor da liña enriba k veces. Imos comezar con d na liña 3. Temos 5-924 * 0 = 5. A continuación, temos 0-1 * 0 que é 0 e 1-0 * 0 que é 1. Non é tan malo, entón imos pasar á seguinte liña. Primeiro necesitamos do noso valor de k. 924 dividido por 5 = 184 con algún resto, entón o seu valor para k é 184. Agora 924-5 * 184 = 4. 1-0 * 184 é 1, 0 - 1 * 184 é -184. Todo ben, imos facer a seguinte liña. O noso valor de k será 1 porque 5 dividido por 4 = 1 con algún resto. Imos encher as outras columnas. 5-4 * 1 = 1. 0-1 * 1 = -1. E 1 - 184 * 1 é 185. Imos ver o que o noso próximo valor de k sería. Ben, parece que temos 4 dividido por 1, que é 4. Neste caso en que estamos a dividir por 1 k tal que é igual á o valor d na liña anterior significa que estamos a facer co noso algoritmo. Podemos ver aquí que temos x = 185 e y = -1 na última fila. Imos agora volver ao noso obxectivo orixinal. Dixemos que o valor de x, como resultado da execución deste algoritmo sería o inverso multiplicativo dun (mod b). Isto significa que 185 é o inverso multiplicativo de 5 (mod 924) o que significa que ten un valor de 185 para d. O feito de que d = 1 na última liña comproba se e foi coprime m. Se non fose un entón teriamos que escoller un e novo. Agora imos ver se Rob recibiu a miña mensaxe. Cando alguén me envía unha mensaxe cifrada mentres eu mantiven a miña chave privada en segredo Eu son a única persoa que pode descifrar a mensaxe. Para descifrar un anaco c podo calcular a mensaxe orixinal é igual ao bloque de potencia d (mod n). Lembre que d e n son da miña clave privada. Para se ter unha mensaxe chea de seus anacos que descifrar cada peza e concatenar os resultados. Exactamente o quão seguro é o RSA? A verdade é que non sabemos. A seguridade está baseada en canto tempo levaría un atacante para romper unha mensaxe cifrada con RSA. Lembre que un atacante ten acceso á súa chave pública, a cal contén o correo e n. Se o atacante pode factor N seus dous primos, P e Q, entón ela podería calcular d usando o algoritmo estendido de Euclides. Isto dá-lle a clave privada, a cal pode ser usada para descodificar unha mensaxe. Pero a rapidez con que podemos fatorar números enteiros? Unha vez máis, non sabemos. Ninguén atopou unha forma rápida de facelo, o que significa que, dada suficientemente grande n levaría un atacante irrealisticamente longo factor para o número. Se alguén revelou unha maneira rápida de enteiros de factoring RSA sería roto. Pero mesmo se factorização enteira é lenta o algoritmo RSA aínda pode ter algunha falla nela que permite a fácil descodificación de mensaxes. Ninguén descubriu e revelou tal fallo, con todo, pero iso non significa que un non existe. En teoría, alguén podería estar alí fóra, lendo todos os datos criptografada con RSA. Hai un pouco de unha cuestión de privacidade. Se Tommy criptografía algunha mensaxe usando a miña chave pública e un dianteiro criptografía a mesma mensaxe utilizando a clave pública o dianteiro vai ver que as dúas mensaxes son idénticas e, polo tanto, sabe o que Tommy criptografada. A fin de evitar isto, as mensaxes son normalmente cubertos con bits aleatorios antes de ser codificado de xeito que a mesma mensaxe cifrada varias veces será diferente, sempre que a impregnación en que a mensaxe é diferente. Pero lembre-se así que temos que dividir as mensaxes en anacos de xeito que cada bloque é menor que n? Recheo dos anacos significa que podemos ter que dividir as cousas en anacos aínda máis desde o anaco acolchado debe ser menor que n. Criptografía e descriptografar son relativamente caros con RSA, e así a necesidade de acabar con unha mensaxe en anacos moitos pode ser moi caro. Un gran volume de datos debe ser criptografada e descriptografados podemos combinar os beneficios de algoritmos de claves simétricas cos da RSA para a seguridade e eficiencia. Aínda non entrarei aquí, AES é un algoritmo de chave simétrica, como o Vigenère e cifras de César pero moito máis difícil de descifrar. Por suposto, non podemos usar AES sen establecer unha clave secreta compartida entre os dous sistemas, e vimos o problema con iso antes. Pero agora podemos utilizar RSA para establecer a chave secreta compartida entre os dous sistemas. Imos chamar o ordenador que envía os datos do remitente E o ordenador recibe os datos do receptor. O receptor ten un par de claves RSA e envía a clave pública do remitente. O remitente xera unha clave AES, criptografía con chave RSA do receptor pública, e envía a clave AES para o receptor. O receptor decifra a mensaxe coa súa chave privada RSA. Tanto o remitente como o receptor teñen agora unha chave AES compartido entre eles. AES, que é moito máis rápido a codificación e decodificación de RSA, agora pode ser usado para cifrar os grandes volumes de datos e envialos para o receptor, que poden descifrar usando a mesma clave. AES, que é moito máis rápido a codificación e decodificación de RSA, agora pode ser usado para cifrar os grandes volumes de datos e envialos para o receptor, que poden descifrar usando a mesma clave. Nós só necesitabamos RSA para trasladar a clave compartida. Nós non precisamos máis usar RSA en todo. Parece que eu teño unha mensaxe. Non importa se alguén ler o que está no avión de papel antes de que eu peguei porque eu son o único a chave privada. Imos descifrar cada un dos anacos na mensaxe. O primeiro anaco, 658, que aumenta para poder d, que é de 185, mod n, que é 989, é igual a 67, que é a letra C en ASCII. Agora, para o segundo anaco. O anaco segundo ten valor 15, que levantamos o poder 185, mod 989, e esta é igual a 83 que é a letra S en ASCII. Agora, para o terceiro bloque, que ten un valor 799, elevamos a 185, mod 989, e esta é igual a 53, que é o valor do carácter 5 en ASCII. Agora, para o último anaco, que ten un valor 975, elevamos a 185, mod 989, e esta é igual a 48, o cal é o valor de 0 a personaxe en ASCII. O meu nome é Rob Bowden, e este é o CS50. [CS50.TV] RSA en todo. RSA en todo. [Risas] De todo.