Conteúdo principal
Curso: Computer science theory > Unidade 2
Lição 4: Criptografia moderna- Teorema fundamental da aritmética
- Criptografia de chave pública: o que é isso?
- O problema do logarítmo discreto
- Troca de chaves Diffie-Hellman
- Criptografia RSA: etapa 1
- Criptografia RSA: etapa 2
- Criptografia RSA: etapa 3
- Complexidade do Tempo (Exploração)
- Função totiente de Euler
- Exploração da Função Totiente de Euler
- Criptografia RSA: etapa 4
- O que devemos aprender em seguida?
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
Troca de chaves Diffie-Hellman
Orientação da troca de chaves de Diffie-Hellman. Versão original criada por Brit Cruise.
Quer participar da conversa?
- os dois devem ser primos?(1 voto)
Transcrição de vídeo
RKA4JL - Agora, esta é a nossa solução. Primeiro, Alice e Bob concordam publicamente em um módulo primo e um gerador, nesse caso, 17 e 3. Então, Alice escolhe um número confidencial aleatório, digamos 15, calcula 3¹⁵ potência módulo 17 e manda o resultado publicamente para Bob. Então, Bob seleciona seu número confidencial aleatório, por exemplo 13, calcula 3¹³ potência módulo 17 e manda
seu resultado publicamente para Alice. E agora, o principal do truque:
Alice pega o resultado público de Bob e eleva à potência do seu número
confidencial, o número 15, para que possa obter o segredo
compartilhado, que nesse caso é 10. Bob pega o resultado público de Alice e eleva ao potencial do seu número confidencial, o número 13, resultando no mesmo número que Alice. Ambos têm, então, um segredo compartilhado. Note que eles fizeram os mesmos cálculos,
embora não pareça à primeira vista. Considere Alice: o 12 que ela recebeu de Bob foi calculado como 3¹³ módulo 17. Então, seus cálculos foram a mesma coisa que 3 elevado a 13 elevado a 15 módulo 17. Agora, considere Bob: o 6 que ele recebeu de Alice foi calculado como 3¹⁵ módulo 17. Então, o que ele calculou foi o mesmo que
3 elevado a 15 elevado a 13. Note que eles realizaram os mesmos cálculos com os expoentes em ordens diferentes. Quando eles invertem os expoentes,
o resultado não é alterado. Então, ambos calcularam 3 elevado a seus próprios números confidenciais. Sem um desses números confidenciais, 15 ou 13, Eve não será capaz de encontrar a solução. E é assim que é feito. Eve está presa tentando resolver o problema do logaritmo discreto. E com números grandes o suficiente, podemos dizer que é praticamente impossível que ela quebre a encriptação em um tempo razoável. Isso resolve o problema da troca de chaves. Isso pode ser usado em conjunto
com o pseudogerador aleatório para criptografar mensagens entre
pessoas que nunca se conheceram.