[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.
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.