Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
RSA in Practice
Loading...
Do curso por Stanford University
Cryptography I
2560 classificações
Na lição
Public-Key Encryption
Week 6. This week's topic is public key encryption: how to encrypt using a public key and decrypt using a secret key. Public key encryption is used for key management in encrypted file systems, in encrypted messaging systems, and for many other tasks. The videos cover two families of public key encryption systems: one based on trapdoor functions (RSA in particular) and the other based on the Diffie-Hellman protocol. We construct systems that are secure against tampering, also known as chosen ciphertext security (CCA security). There has been a ton of research on CCA security over the past decade and given the allotted time we can only summarize the main results from the last few years. The lectures contain suggestions for further readings for those interested in learning more about CCA secure public-key systems. The problem set this week involves a bit more math than usual, but should expand your understanding of public-key encryption. Please don't be shy about posting questions in the forum. This is the last week of this Crypto I course. I hope everyone learned a lot and enjoyed the material. Crypto is a beautiful topic with lots of open problems and room for further research. I look forward to seeing you in Crypto II where we will cover additional core topics and a few more advanced topics.
Conheça os instrutores
Dan BonehProfessor
Computer Science
Para concluir este módulo, quero dizer algumas coisas sobre como RSA é usada na prática.
Então, primeiro de tudo, se você quiser acelerar o RSA
criptografia, o seu perfeitamente possível utilizar um expoente criptografia pequena
"e" Então, ao invés de usar um "e" aleatório pode usar um
pequeno valor "e" e na verdade o valor do mínimo
Portanto, a sua não é difícil ver que o menor possível
valor de "e" é na verdade "e" = 3
Bem "e" = 1 é uma má idéia, porque isso não é particularmente difícil
"e" = 2 não é um expoente válido RSA porque
tinha que ser relativamente primo a fi de N.
que é um número par ... Se p ou q são primos ímpares,
(p-1) vezes (q-1) é um número par, mas se "e" é ainda
se "e" é igual a 2, a sua não vai ser relativamente primos
E então "e" = 3 é o valor mínimo primeiro que pode
ser usado e depois só temos de ter certeza de que
2 mod 3 de modo que (P-1) vezes (Q-1) não é divisível
Então, na verdade este é um expoente bem público a usar,
no entanto, o valor recomendado para usar é duas a 16 um, de modo
(65537) É uma boa idéia usar este valor recomendado
de "e" um para computar x ^ 3 mod N, você basicamente
X ^ 65537 quadratura mod N usando repetido, você
vai fazer é você repetidamente quadrado 16 vezes
e, em seguida, você iria multiplicar por X mais uma vez.
Ok? Então, só com 17 multiplicações você pode fazer isso
exponenciação de modo que este é ainda muito, muito mais rapidamente do que
usando um "e" aleatório que vai exigir algo como
Então, isso leva-nos naquilo que é chamado de assimetria da RSA
onde em criptografia fato é bastante rápido e criptografia requer apenas 17 multiplicações
descriptografia No entanto é muito, muito mais lento
exige algo da ordem de 2.000 multiplicações
Gostaria de salientar que há um truque padrão para
Isso é chamado RSA-CRT, o que significa RSA com remaindering chinês.
É um método para acelerar a decodificação RSA por um fator de quatro,
mas mesmo assim ele ainda vai ser muito, muito, muito mais lento do que a criptografia.
A proporção de criptografia para desencriptação no RSA é um factor de cerca de 10-30,
assim encriptação pode ser até 30 vezes mais rápido do gosto de descriptografia, dependendo do tamanho do seu módulo.
Curiosamente, esta é uma propriedade especial de RSA em que a criptografia é muito mais rápido do que descriptografia.
E outros sistemas de chave pública - por exemplo, no próximo módulo vamos olhar para criptografia ElGamal -
não têm esta propriedade onde a criptografia e descriptografia levar aproximadamente a mesma quantidade de tempo.
Nós já falamos sobre comprimentos de chave para RSA antes.
Então, eu só queria piscar esses números para lembrar que, se você estiver usando uma chave de 128 bits AES,
realmente, você deve estar usando um módulo de 3000 bits.
Embora todo mundo só usa um módulo bit 2048.
E se você está realmente usando uma chave AES longa, como um AES de 256 bit chave, o módulo RSA chega a ser muito grande.
Agora, eu gostaria de mencionar uma série de ataques de implementação em RSA.
Estes são os ataques que têm sido demonstradas contra particular,
implementações matematicamente corretas de RSA. No entanto, essas implementações eram vulneráveis
a ataques de lado certos canais que fazem a implementação completamente inseguro.
Assim, o primeiro exemplo disso é devido a Paul Kocher volta em 97.
Ele mostrou um ataque de temporização onde tudo que você faz é medir o tempo para uma decodificação RSA.
E simplesmente medindo o tempo, você pode realmente expor o segredo expoente d.
E assim, este diz que, se você estiver indo para implementar um descriptografia RSA,
é melhor você ter certeza de que o tempo de decodificação é independente dos argumentos.
Outro ataque também por Paul Kocher dois anos mais tarde mostrou que
se você tem um cartão inteligente que é a implementação de decodificação RSA
você pode realmente medir o consumo de energia do cartão enquanto ele está fazendo decodificação RSA
e depois simplesmente por olhar para os altos e baixos que você pode, literalmente, leu os pedaços de d
um pouco de cada vez, como o smart card está sendo executado através do algoritmo de quadratura repetido.
Então, usando um ataque de análise de poder é realmente bastante fácil de obter os bits secretos
da chave secreta, a menos que o cartão inteligente defende contra ataques de análise de energia.
E, finalmente, um outro ataque chamado um ataque falha mostra que a RSA é muito vulnerável a
erros de decodificação e, em particular, se por algum motivo ocorre um erro durante uma decodificação RSA,
um erro é na verdade suficiente para revelar completamente a chave secreta.
Portanto, este ataque é realmente bastante significativo. É só um erro completamente revela sua chave secreta.
E, como resultado, muitas cryptolibraries irá realmente verificar o resultado da descriptografia RSA
antes de retornar para o chamador. E do jeito que você gostaria de verificar é,
você levaria a saída deste exponenciação, e simplesmente aumentá-lo para o poder do e,
e verifique se você realmente voltar c módulo N.
E se assim for, você sabe que a sua decodificação foi feito corretamente.
Agora, a razão que você pode fazer isso é porque mais uma vez, e é muito menor do que d,
portanto, a verificação demora muito menos tempo do que, na verdade, algo elevar à potência de d.
No entanto, você sabe que, mesmo que a verificação é dez vezes mais rápido do que a decodificação atual,
este ainda apresenta uma desaceleração de 10%. E assim, por vezes, este é realmente desligado.
Mas, no entanto, é realmente uma boa idéia para verificar se a sua saída RSA está corretamente computado.
E assim todos estes tipos de ataques faz questão de recordar que, se você acabou de implementar RSA ingenuamente
seria matematicamente correto, ele iria trabalhar,
No entanto, haveria todos esses ataques potenciais na implementação
e como resultado, você nunca deve implementar RSA si mesmo.
Sempre, sempre usar bibliotecas-padrão e usar apenas a implementação disponível.
Assim, para ser concreto, eu queria mostrar um exemplo de um desses ataques.
E, em especial eu vou lhe mostrar os ataques de falha no RSA.
E, novamente, este será um ataque de culpa no que é chamado RSA com remaindering chinês.
Então, na verdade, como eu disse no início do segmento, descriptografia RSA é frequentemente implementada como segue:
O que você é, você decifrar o texto cifrado c módulo p, então você decifrar o texto cifrado c módulo q.
E então você combinar os dois para realmente começar a decodificação módulo N.
E essa combinação é feito usando o que é chamado um teorema restante chinês.
Que eu não vou explicar aqui, mas não é muito difícil ver como isso funciona.
Basicamente, quando você tem o resultado do mod p decodificação ea descriptografia mod q
Você pode combiná-lo para obter a decodificação mod N.
E não é que isso dá um fator de quatro velocidades até
sobre a implementação ingênua de fazer diretamente a exponencial módulo N.
Okay. Então, vamos ver por que isso é vulnerável a falhas.
Suponha que acontece que quando sua biblioteca de decodificação é calcular a descriptografia módulo q,
por algum motivo o processador faz com que uma mensagem de erro.
E, na verdade, o que fica não é a xq correta. Ela recebe uma xq incorreta,
então vamos chamar este chapéu xq. No entanto, quando computada a decodificação módulo p,
você sabe, não houve erro. Então, esses erros são bastante freqüentes.
E assim vamos assumir que ocorreu um erro de módulo um primo
mas isso não ocorreu modulo auge outro.
Bem, se esse é o caso do nosso cálculo é correto e incorreto módulo p módulo q.
Que diz que quando combinamos os dois resultados na verdade estamos indo para obter uma saída,
Eu vou chamá-lo x principal, de tal forma que a saída está correta módulo p.
Então, x principal é c realmente igual ao mod d p mas é incorreto módulo q.
Se levantou ambas estas equações para a alimentação de e, o que é obtemos as seguintes duas relações.
Bem, vamos ver. Esse cara que aumentá-lo para poder do e.
O que acontece é que o lado esquerdo se torna x primordial para o e.
O lado direito, aqui, é c ao d.
Se eu levantar c ao d para o poder do e - e e d, lembre-se são inversas uma da outra -
E, como resultado, se eu levantar c ao d para o poder do e, ambos os expoentes cancelar e eu simplesmente obter c volta.
Então eu sei que o primeiro-x para o e é igual a c. Mas módulo q, houve um erro.
Então x privilegiada para o e não é igual a c módulo q.
Assim, portanto, se eu olhar para esta diferença, x privilegiada para o e menos c.
Sabemos que é zero módulo p, e não é de zero módulo q.
Portanto, agora se calcular o GCD deste valor com N, o que temos?
Bem, como eu disse, isso é zero p mod, mas não é igual a zero mod q.
O que significa que esta quantidade aqui é divisível por p, mas não é múltiplo de q.
Assim, portanto, quando eu calcular o GCD, o que eu vou é simplesmente p.
E, novamente, é porque p divide essa quantidade aqui quando q não divide essa quantidade.
Então, agora, basicamente, o que acabo de obter é a fatoração de N.
Assim que eu tiver a fatoração de NI pode calcular phi (N)
e, então, dado phi (N) eu possa realmente me calcular o expoente de decodificação da chave pública.
Então agora eu só recuperou a chave secreta a partir da chave pública
a partir de um único erro que aconteceu durante descriptografia. Então é por isso normalmente
quando você faz descriptografia RSA é uma boa idéia para verificar os resultados
especialmente quando você usa remaindering chinesa para acelerar a decodificação RSA.
O último ataque que eu quero falar é uma observação muito recente
que foi observada por Heninger et al e et al Lenstra
que mostra que a geração de chaves RSA pode ser problemático quando ele é feito com a entropia ruim.
Então aqui está como as coisas vão mal. Então, o caminho aberto SSL gera chaves RSA é a seguinte.
Bem, começa por, basicamente, semear o gerador de números pseudo-aleatório.
E, em seguida ele utiliza os bits aleatórios a partir de um gerador de número pseudo aleatório para gerar o primeiro p primo.
Em seguida, ele vai em frente e semear o gerador de números aleatórios um pouco mais,
e irá gerar bits a partir do gerador de número pseudo aleatório para gerar q.
E, finalmente, a saída será o produto de p e q.
Ok então as duas etapas, onde vemos a semente do gerador de números pseudo-aleatório.
Agora, suponha que isso é implementado em um roteador ou um firewall de algum tipo,
e supor que a geração da chave acontece logo após o firewall inicia.
Então as botas de firewall para cima. No momento do arranque, não há um monte de entropia
no gerador de números pseudo aleatórios, e, como resultado
o firewall é susceptível de gerar um primo p que vem de uma entropia muito baixa.
O que significa que este p vai ser uma de um pequeno número de possibilidades.
No entanto, depois de ter gerado p, gerando o principal, na verdade, leva um pouco de tempo,
alguns microssegundos. E assim, então o firewall terá gerado mais entropia
e assim depois de adicionar mais entropia ao de entropia,
o primo q dizem que é gerada a partir de um pool de entropia muito maior e, portanto, exclusivo para este firewall.
Agora o problema é que muitos firewalls diferentes se gerar uma chave RSA
desta forma muitos deles vai realmente acabar usando o mesmo p nobre mas um diferente primo q.
Então, o que isso diz é que, se olharmos para dois módulos RSA de dois firewalls diferentes, N1 e N2.
Se calcular o MDC de N1 e N2, bem ambos tinham q diferente, mas o mesmo p.
Então, se calcularmos o MDC, na verdade, vamos acabar com uma fatoração de N,
de ambos N1 e N2 e então podemos realmente descobrir a chave privada, tanto para N1 e N2 para.
Portanto, este foi realmente observado na prática.
Ambos os grupos, o que eles fizeram é que eles digitalizados na web
e recuperou todas as chaves públicas lá fora, que são usados em vários servidores web.
Eles, então, passou a GCD maciço, usando alguns truques aritméticos
eles foram capazes de calcular este GCD maciça de todos os pares de chaves pública N1 e N2.
E eis que, na verdade, eles perceberam que um bom número destas teclas têm um fator comum.
Então, eles foram realmente capazes de integrar estas módulos.
Assim, no experimento, eles foram realmente capazes de fator sobre 0,4% de todas as chaves públicas SSL.
Este é um fato surpreendente, que, de fato, muitos web chaves públicas do servidor lá fora
são vulneráveis apenas porque aconteceu para gerar a chave RSA usando baixa entropia.
Então eles têm um fator comum com alguém fator de outra pessoa
GCDing e os dois juntos dá a fatoração.
Então, a lição de tudo isso é quando você gerar chaves,
não importa se eles são chaves RSA ou chaves ElGamal ou chaves simétricas,
é crucial que o número -, que o seu gerador está devidamente semeada.
Portanto, não gerar chaves imediatamente após a partida. Você tem que tipo de certificar-se
a semeadura do gerador tenha tido tempo suficiente para realmente gerar entropia suficiente.
E só então você pode começar a gerar chaves. Portanto, este é um exemplo muito bom
de como um, um gerador de números aleatórios ruim pode atrapalhar suas chaves públicas RSA.
Ok, então este é o fim de nossa discussão de criptografia de chave pública da RSA.
Eu queria mencionar algumas leituras adicionais, se você quiser ler mais sobre isso.
Portanto, há um papel bonito por Victor Shoup que fala sobre o porquê
segurança texto escolhido cifra é tão importante nas definições de chave pública.
Então, se o ataque Bleichenbacher não foi convincente o suficiente, há muitos outros ataques como este
que são possíveis se você não usar um sistema de codificação de texto escolhido seguro.
Então, se você quer aprender mais sobre segurança escolhido texto cifrado,
por favor, olhe para o papel de Victor Shoup.
Há uma pesquisa que eu acho que eu escrevi há alguns anos atrás, que se parece em muitos ataques diferentes
no sistema RSA. Eu acho que eu escrevi isso quando era RSA 20,
Eu realmente preciso atualizar esta a 30 anos de ataque ao sistema de criptografia RSA.
Há já alguns desenvolvimentos na última década, mas por enquanto esta é realmente uma pesquisa decente
para olhar e ler sobre mais ataques RSA.
Os resultados OAEP que eu mencionei são referenciados aqui, OAEP reconsiderada.
E, finalmente, se você estiver interessado em análise de comprimento de chave de RSA e outros sistemas de chave pública,
há um papel bonito por Arjen Lenstra que discute como você deve escolher
comprimentos de chave para os seus sistemas de chave pública, e até mesmo para os seus principais sistemas simétricos.
Ok, então esses são os quatro referências. Espero que você tenha tempo para olhar por eles.
E eu vou parar por aqui. E, no próximo módulo vamos olhar para
outra família de sistemas de criptografia de chaves públicas, desta vez com base no logaritmo discreto.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2019 Coursera Inc. Todos os direitos reservados.
