[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Esta é CS50.] [CS50.TV]
Vamos dar uma olhada na RSA, um algoritmo utilizado para encriptar dados.
Algoritmos de criptografia como César e cifras de Vigenère não são muito seguras.
Com a cifra de César, o atacante só precisa tentar 25 chaves diferentes
para obter texto simples da mensagem.
Embora a cifra de Vigenère é mais seguro do que a cifra de César
por causa do maior espaço de busca de chaves, uma vez que um atacante
conhece o comprimento da chave de cifra de Vigenère,
que pode ser determinada através de uma análise dos padrões de texto codificado,
a cifra de Vigenère que não é muito mais seguro do que a cifra de César.
RSA, por outro lado, não é vulnerável a ataques como este.
A cifra de César e Vigenère cifra de usar a mesma chave
para criptografar e descriptografar uma mensagem.
Esta propriedade faz com que essas cifras de algoritmos de chaves simétricas.
Um problema fundamental com algoritmos de chaves simétricas
é que eles contam com a criptografar e enviar a mensagem
e o de recepção e descodificação da mensagem
para já concordaram adiantado na chave ambos irão usar.
Mas nós temos um pouco de um problema de inicialização aqui.
Como dois computadores que querem se comunicar estabelecer uma chave secreta entre eles?
Se a chave deve ser secreta, então precisamos de uma maneira de criptografar e descriptografar a chave.
Se tudo o que temos é a criptografia de chave simétrica
então acabamos de voltar para o mesmo problema.
RSA, por outro lado, utiliza um par de chaves,
um para criptografia e outro para a descodificação.
Uma é chamada a chave pública, e a outra é a chave privada.
A chave pública é usada para criptografar mensagens.
Como você pode imaginar pelo nome, podemos partilhar a nossa chave pública com
qualquer pessoa que quiser, sem comprometer a segurança de uma mensagem criptografada.
Mensagens criptografadas com uma chave pública
só pode ser decifrada com a sua chave privada correspondente.
Enquanto você pode compartilhar sua chave pública, você deve sempre manter o seu segredo da chave privada.
e apenas a chave privada pode ser utilizada para decifrar as mensagens
se dois usuários querem enviar mensagens criptografadas com RSA
frente e para trás ambos os usuários precisam ter seu par de chaves pública e privada própria chave.
Mensagens de usuário para um usuário 2
usar apenas um par de chaves 2 usuário e mensagens de usuário para usuário 2 1
usar apenas um par de chaves de usuário do.
O fato de que há duas chaves separadas para criptografar e descriptografar as mensagens
RSA faz um algoritmo de chave assimétrica.
Nós não precisamos para criptografar a chave pública, a fim de enviá-lo para outro computador
vez que a chave é pública qualquer maneira.
Isto significa que o RSA não têm o mesmo problema de inicialização
como os algoritmos de chave simétrica.
Então, se eu quero enviar uma mensagem usando a criptografia RSA
para Rob, eu vou primeiro precisa de chave pública de Rob.
Para gerar um par de chaves, Rob precisa escolher dois números primos grandes.
Esses números serão usados ​​em ambas as chaves, público e privado,
mas a chave pública só vai usar o produto desses dois números,
não os próprios números.
Uma vez que eu tenho a mensagem criptografada usando a chave pública de Rob
Posso enviar a mensagem para Rob.
Para um computador, fatorar números é um problema difícil.
A chave pública, lembre-se, usou o produto de dois números primos.
Este produto deve então ter apenas dois elementos,
que acontecem ser os números que compõem a chave privada.
A fim de decifrar a mensagem, a RSA vai usar esta chave privada
ou os números multiplicados em conjunto no processo de criação da chave pública.
Porque é computacionalmente difícil fatorar o número
utilizado em uma chave pública para os dois números utilizados na chave privada
É difícil para um invasor descobrir a chave privada
que será necessária para desencriptar a mensagem.
Agora vamos entrar em alguns detalhes de nível mais baixo da RSA.
Vamos primeiro ver como podemos gerar um par de chaves.
Primeiro, vamos precisar de dois números primos.
Vamos chamar esses dois números pe q.
A fim de escolher p e q, na prática, seria pseudorandomly gerar
grandes números e, em seguida, usar um teste para determinar se ou não
esses números são provavelmente primo.
Podemos manter a geração de números aleatórios e outra vez
até que tenhamos dois primos que podemos usar.
Aqui vamos escolher p = 23 e q = 43.
Lembra-te, na prática, p e q devem ser números muito maiores.
Tanto quanto sabemos, o maior dos números, o que é mais difícil
para quebrar uma mensagem criptografada.
Mas também é mais caro para criptografar e descriptografar mensagens.
Hoje é frequentemente recomendado que p e q são pelo menos 1024 bits,
o que coloca cada número em mais de 300 dígitos decimais.
Mas vamos pegar esses números pequenos para este exemplo.
Agora vamos multiplicar p e q juntos para obter um número de 3,
que chamaremos de n.
No nosso caso, n = 23 * 43, que é = 989.
Temos n = 989.
Em seguida, vamos multiplicar p - 1 com q - 1
para obter um número 4, que chamaremos de m.
No nosso caso, m = 22 * ​​42, que é = 924.
Temos m = 924.
Agora vamos precisar de um número e que é relativamente privilegiada para m
e menos do que m.
Dois números são relativamente primos ou primos entre si
se o inteiro positivo apenas que divide os dois uniformemente é 1.
Em outras palavras, o maior divisor comum de e e m
deve ser 1.
Na prática, é comum e ser o número primo 65537
enquanto este número não acontecer de ser um fator de m.
Para os nossos chaves, nós vamos buscá-e = 5
desde 5 é relativamente privilegiada para 924.
Finalmente, vamos precisar de mais um número, que chamaremos de d.
D tem de ser um valor que satisfaz a equação de = 1 (mod m).
Este mod m significa que vamos usar algo chamado aritmética modular.
Na aritmética modular, uma vez que um número maior do que recebe algum limite superior
ele voltará para 0.
Um relógio, por exemplo, usa aritmética modular.
Um minuto após a 1:59, por exemplo, é de 2:00,
não 1:60.
O ponteiro dos minutos tem enrolado a 0
ao atingir um limite superior de 60 anos.
Então, podemos dizer que 60 é equivalente a 0 (mod 60)
e 125 é equivalente a 65 é igual a 5 (mod 60).
Nossa chave pública será o e par e n
onde, neste caso, e é 5 e n ​​é 989.
Nossa chave privada será o par d e n,
que no nosso caso é de 185 e 989.
Observe que nossa original primos p e q não aparecem
em qualquer lugar em nossas chaves privadas ou públicas.
Agora que temos o nosso par de chaves, vamos dar uma olhada em como podemos criptografar
e decifrar uma mensagem.
Eu quero enviar uma mensagem para Rob,
então ele vai ser o único a gerar esse par de chaves.
Então eu vou pedir para Rob sua chave pública, que eu vou usar
para criptografar uma mensagem para enviar para ele.
Lembre-se, é totalmente bem para Rob para compartilhar sua chave pública comigo.
Mas não seria bom para compartilhar sua chave privada.
Eu não tenho nenhuma idéia do que a sua chave privada é.
Nós podemos quebrar nossa mensagem m-se ​​em vários pedaços
todos menores que n e, em seguida, criptografar cada um desses blocos.
Vamos criptografar o CS50 string, que pode dividir-se em quatro pedaços,
uma por letra.
Para criptografar a minha mensagem, eu vou ter de convertê-lo em
algum tipo de representação numérica.
Vamos concatenar os valores ASCII com os personagens de minha mensagem.
Para criptografar uma mensagem m dado
Vou precisar para calcular c = m para o e (mod n).
Mas m deve ser menor do que n,
ou então a mensagem completa não pode ser expressa módulo n.
Podemos dividir m acima em vários pedaços, todas as quais são menores do que n,
e codificar cada uma destas porções.
Criptografando cada um desses pedaços, temos c1 = 67 para o 5 (mod 989)
que = 658.
Para o nosso pedaço segundo temos 83 a 5 (mod 989)
qual = 15.
Para o nosso pedaço terceiro temos 53 para o 5 (mod 989)
que = 799.
E, finalmente, para o nosso último pedaço temos 48 para o 5 (mod 989)
que é = 975.
Agora podemos enviar mais estes valores criptografados para Rob.
Aqui está, Rob.
Enquanto a nossa mensagem está em vôo, vamos ter um outro olhar
como chegamos esse valor para d.
Nosso número d necessário para satisfazer 5D = 1 (mod 924).
Isso faz com que o d inverso multiplicativo modulo de 5 924.
Dado dois inteiros, A e B, o algoritmo estendido de Euclides
pode ser usada para encontrar o maior divisor comum destes dois números inteiros.
Ele também irá dar-nos dois outros números, X e Y,
que satisfazem a equação ax + by = máximo divisor comum de a e b.
Como isso pode nos ajudar?
Bem, ligar e = 5 para um
e m = 924 para b
já sabemos que estes números são primos entre si.
Seu maior divisor comum é 1.
Isso nos dá 5x + 924y = 1
ou 5x = 1 - 924y.
Mas, se só se preocupam com tudo o modulo 924
então podemos deixar cair o - 924y.
Pense novamente para o relógio.
Se o ponteiro dos minutos é em 1 e, em seguida, exatamente 10 horas passam,
sabemos que o ponteiro dos minutos vai ainda estar na 1.
Aqui nós começam em 1 e, em seguida, envolver em torno de vezes exatamente y,
por isso ainda vai ser em 1.
Temos 5x = 1 (mod 924).
E aqui esta x é o mesmo que o d estávamos procurando antes,
assim, se usar o algoritmo estendido de Euclides
para obter este número x, que é o número que deve usar como nosso d.
Agora vamos executar o algoritmo estendido de Euclides para a = 5
e b = 924.
Vamos usar um método chamado de método de tabela.
Nossa mesa terá 4 colunas, x, y, d, e k.
Nossa mesa começa com duas linhas.
Na primeira linha temos 1, 0, então o nosso valor de um, o que é 5,
e nossa segunda linha é 0, 1, e o nosso valor para b, que é 924.
O valor da coluna 4, k, será o resultado
de dividir o valor de d na linha acima com o valor de d
na mesma linha.
Temos 5 dividido por 924 é 0, com algum remanescente.
Isso significa que temos k = 0.
Agora, o valor de todas as outras células, será o valor da célula de 2 linhas acima dela
menos o valor da linha acima k vezes.
Vamos começar com d na linha 3.
Nós temos 5-924 * 0 = 5.
Em seguida, temos 0-1 * 0 que é 0
e 1-0 * 0 que é 1.
Não é tão ruim, então vamos passar para a próxima linha.
Primeiro precisamos de nosso valor de k.
924 dividido por 5 = 184 com algum remanescente,
então o nosso valor para k é 184.
Agora 924-5 * 184 = 4.
1-0 * 184 é 1 e 0 - 1 * 184 é -184.
Tudo bem, vamos fazer a próxima linha.
Nosso valor de k será 1 porque
5 dividido por 4 = 1 com algum remanescente.
Vamos preencher as outras colunas.
5-4 * 1 = 1.
0-1 * 1 = -1.
E 1 - 184 * 1 é 185.
Vamos ver o que o nosso próximo valor de k seria.
Bem, parece que temos 4 dividido por 1, que é 4.
Neste caso em que estamos a dividir por 1 k tal que é igual à
o valor de d na linha acima significa que estamos a fazer com o nosso algoritmo.
Podemos ver aqui que temos x = 185 e y = -1 na última fila.
Vamos agora voltar ao nosso objetivo original.
Dissemos que o valor de x, como resultado da execução deste algoritmo
seria o inverso multiplicativo de um (mod b).
Isso significa que 185 é o inverso multiplicativo de 5 (mod 924)
o que significa que tem um valor de 185 para d.
O fato de que d = 1 na última linha
verifica se e foi para coprime m.
Se não fosse um então teríamos que escolher um e novo.
Agora vamos ver se Rob recebeu minha mensagem.
Quando alguém me envia uma mensagem criptografada
enquanto eu mantive a minha chave privada em segredo
Eu sou a única pessoa que pode decifrar a mensagem.
Para descriptografar um pedaço c eu posso calcular a mensagem original
é igual ao bloco de potência d (mod n).
Lembre-se que d e n são de minha chave privada.
Para se ter uma mensagem cheia de seus pedaços que decifrar cada pedaço
e concatenar os resultados.
Exatamente o quão seguro é o RSA?
A verdade é que nós não sabemos.
A segurança é baseada em quanto tempo levaria um atacante para quebrar uma mensagem
criptografada com RSA.
Lembre-se que um atacante tem acesso a sua chave pública,
a qual contém o e e n.
Se o atacante consegue fator N em seus dois primos, P e Q,
então ela poderia calcular d usando o algoritmo estendido de Euclides.
Isto dá-lhe a chave privada, a qual pode ser usada para descodificar qualquer mensagem.
Mas a rapidez com que podemos fatorar números inteiros?
Mais uma vez, nós não sabemos.
Ninguém encontrou uma maneira rápida de fazê-lo,
o que significa que, dada suficientemente grande n
levaria um atacante irrealisticamente longo
fator para o número.
Se alguém revelou uma maneira rápida de inteiros de factoring
RSA seria quebrado.
Mas mesmo se factorização inteira é lenta
o algoritmo RSA ainda pode ter alguma falha nela
que permite a fácil descodificação de mensagens.
Ninguém descobriu e revelou tal falha, no entanto,
mas isso não significa que um não existe.
Em teoria, alguém poderia estar lá fora, lendo todos os dados criptografados com RSA.
Há mais um pouco de uma questão de privacidade.
Se Tommy criptografa alguma mensagem usando a minha chave pública
e um atacante criptografa a mesma mensagem utilizando a chave pública
o atacante vai ver que as duas mensagens são idênticas
e, portanto, sabe o que Tommy criptografados.
A fim de evitar isto, as mensagens são normalmente preenchidos com bits aleatórios
antes de ser codificado de modo a que a mesma mensagem criptografada
várias vezes será diferente, desde que a impregnação em que a mensagem é diferente.
Mas lembre-se assim que temos de dividir as mensagens em pedaços
de modo que cada bloco é menor do que n?
Preenchimento dos pedaços significa que poderemos ter que dividir as coisas
em pedaços ainda mais desde o pedaço acolchoado deve ser menor do que n.
Criptografia e descriptografia são relativamente caros com RSA,
e assim a necessidade de acabar com uma mensagem em pedaços muitos pode ser muito caro.
Se um grande volume de dados precisa ser criptografados e descriptografados
nós podemos combinar os benefícios de algoritmos de chaves simétricas
com os da RSA para obter a segurança e eficiência.
Embora não entrarei aqui,
AES é um algoritmo de chave simétrica, como o Vigenère e cifras de César
mas muito mais difícil de decifrar.
Claro, não podemos usar AES sem estabelecer uma chave secreta compartilhada
entre os dois sistemas, e vimos o problema com isso antes.
Mas agora podemos usar RSA para estabelecer a chave secreta compartilhada entre os dois sistemas.
Vamos chamar o computador que envia os dados do remetente
e o computador recebe os dados do receptor.
O receptor tem um par de chaves RSA e envia
a chave pública do remetente.
O remetente gera uma chave AES,
criptografa com a chave RSA do receptor pública,
e envia a chave AES para o receptor.
O receptor decifra a mensagem com sua chave privada RSA.
Tanto o remetente quanto o receptor têm agora uma chave AES compartilhado entre eles.
AES, que é muito mais rápida a codificação e descodificação de RSA,
agora pode ser usado para criptografar os grandes volumes de dados e enviá-los para o receptor,
que podem descriptografar usando a mesma chave.
AES, que é muito mais rápida a codificação e descodificação de RSA,
agora pode ser usado para criptografar os grandes volumes de dados e enviá-los para o receptor,
que podem descriptografar usando a mesma chave.
Nós só precisávamos RSA para transferir a chave compartilhada.
Nós não precisamos mais usar RSA em tudo.
Parece que eu tenho uma mensagem.
Não importa se alguém ler o que está no avião de papel antes que eu peguei
porque eu sou o único com a chave privada.
Vamos decifrar cada um dos pedaços na mensagem.
O primeiro pedaço, 658, que aumenta para o poder d, que é de 185,
mod n, que é 989, é igual a 67,
que é a letra C em ASCII.
Agora, para o segundo pedaço.
O pedaço segundo tem valor 15,
que levantamos ao poder 185,
mod 989, e esta é igual a 83
que é a letra S em ASCII.
Agora, para o terceiro bloco, que tem valor 799, elevamos a 185,
mod 989, e esta é igual a 53,
que é o valor do carácter 5 em ASCII.
Agora, para o último pedaço, que tem valor 975,
elevamos a 185, mod 989,
e esta é igual a 48, o qual é o valor de 0 a personagem em ASCII.
Meu nome é Rob Bowden, e este é o CS50.
[CS50.TV]
RSA em tudo.
RSA em tudo. [Risos]
De todo.