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
Criptografia RSA: etapa 4
Exemplo trabalhado de RSA. Versão original criada por Brit Cruise.
Quer participar da conversa?
Why is k value equal to 2 at2:50of the video?(3 votos)
That is a good question.
In my opinion the video doesn't make very clear how to obtain the value of k. (Maybe because we know that there is some k and we can calculate d without knowing k using some modular algebra)
However, if we manipulate the formula presented in the video we get:
d = (k * phi(n) + 1) / e
Which is equal to:
d * e = k * phi(n) + 1
And by definition can be understood as:
d * e = 1 (Mod phi(n))
Because of this last equation, we know that d is the modular inverse of e.
Now we have to use the Extended Euclidean Algorithm to find the modular inverse of 3 (mod 3016).Index quot(q_{i-1}) rem(r_i) s_i t_i
0 - 3016 1 0
1 - 3 0 1
2 3016/3 = 1005 3016-1005*3=1 1 -1005*0=1 0-1005*1 = -1005
Since the remainder is 1 in just one iteration, we now know that the modular inverse of 3 is -1005.
However, we need the positive modular inverse and in this case it is 3016-1005=2011.
Now, going back to the equation:
d * e = k * phi(n) + 1
We have that:
2011 * 3 = k * 3016 + 1
6033 = 3016k + 1
k = 2(4 votos)
- 1) In0:45is told that "m" an "n" must be coprimes.
2) In2:38is told that "e" and "phi(n)" must be coprimes.
What is the rule I must follow to do RSA?(1 voto)
2:50Transcrição de vídeo
RKA4JL - Agora, temos um atalho para resolver Φ (phi). Se soubermos os valores de N,
então achar Φ(N) será fácil. Por exemplo, os fatores primos de 77 são 7 vezes 11. Logo, Φ(77) é 6 vezes 10, que é 60. Passo 3: como associar a função Φ
à exponenciação modular? Recorremos, então, ao teorema de Euler, que é uma relação entre a função Φ e a exponenciação modular, como segue. m elevado a Φ(n) é igual a 1 módulo n. Significa que podemos pegar dois números quaisquer, contanto que eles não compartilhem fatores comuns. Vamos chamá-los de "m" e "n". Seja "m" igual a 5 e "n" igual a 8. Agora, elevando "m" a Φ(8) e dividindo por "n", o resultado sempre será 1. Precisamos apenas modificar essa equação, obedecendo duas regras simples. Primeiro: elevando o número 1 a qualquer expoente "k". Sempre resulta em 1. Da mesma forma, podemos multiplicar o expoente Φ(n) por qualquer número "k" e a solução ainda será 1. Segundo: multiplicando 1 por qualquer número, digamos "m", sempre resultará em "n". Por analogia, podemos multiplicar o lado esquerdo de "m" para conseguir um "m" do lado direito, o que pode ser simplificado como
"m" elevado a "k" vezes Φ(n) mais 1. É aqui que está a mágica: agora temos uma equação para encontrar "e vezes d", que depende de Φ(n). Portanto, é fácil calcular "d".
Somente os fatores de "n" são conhecidos. Por isso, "d" deve ser sempre a chave privada de Alice. É o atalho que permitirá
que ela desfaça os efeitos de "e". Vamos mostrar um exemplo
para ver tudo isso na prática. Bob tem uma mensagem que ele converteu em números usando um esquema de enchimento. Vamos chamar isso de "m". Então, Alice gera suas chaves pública e privada, como a seguir. Primeiro, ela gera dois números primos aleatórios de tamanho similar e os multiplica para obter "n". 3127. Depois, calcula Φ(n) facilmente pois conhece os fatores de "n", que vêm a ser 3016. Então, escolhe um expoente
público e pequeno chamado "e", com a condição de que seja um número ímpar que não compartilhe fatores com Φ(n). Nesse caso, ela escolhe "e" igual a 3. Por fim, encontra o valor de seu expoente privado "d", que nesse caso é 2 vezes Φ(n) mais 1 dividido por 3. Ou 2011. Agora, ela esconde tudo,
exceto o valor de "n" e o valor de "e", porque tanto "n" quanto "e"
compõem sua chave pública. Pense nisso como um cadeado aberto. Ela o envia para que Bob tranque sua mensagem. Bob tranca sua mensagem calculando
"m" elevado a "e" módulo "n". Chamemos isso de "c", sua mensagem criptografada, que ele devolve a Alice. Finalmente, Alice decripta a mensagem
usando sua chave privada "d", acessada por seu atalho: "c" elevado a "d" módulo "n" é igual à mensagem original de Bob, "m". Note que Eve, ou qualquer outra pessoa
de posse de "e", "c" e "n", somente pode encontrar o expoente
"d" se puder calcular Φ(n), o que requer que ela saiba os fatores primos de "n". Se "n" for grande o suficiente,
Alice sabe que isso levará centenas de anos, mesmo com a mais poderosa rede de computadores. Esse truque foi imediatamente
patenteado depois de sua publicação. No entanto, foi redescoberto
de forma independente em 1977 por Ron Rivest, Adi Shamir e Leonard Adleman, motivo pelo qual é conhecido como criptografia RSA. RSA é o algoritmo de chave pública mais usado no mundo e o software mais copiado da história. Cada usuário de internet na Terra está usando RSA ou uma variação dele, ainda que não saiba disso. Sua força se baseia na dificuldade
de encontrar números primos e surge das profundas questões sobre
distribuição dos números primos, questões que permanecem sem
respostas por milhares de anos.