A magia do protocolo de três passagens

Durante minha pesquisa recente, encontrei um bom protocolo criptográfico chamado: o “ Protocolo de três passagens ”, originalmente desenvolvido por Adi Shamir.

Neste post, vou demonstrar sua forma básica (existem outros desenvolvimentos e evoluções para este protocolo, por favor verifique o link da Wikipedia acima).

Para a implementação do algoritmo eu uso Python dentro do Google Colaboratory aqui .

Um piolho deseja enviar um segredo para Bob através de um canal de comunicação público sem que eles troquem chaves criptográficas de antemão.
O segredo compartilhado pode ser a própria mensagem secreta, ou uma chave secreta compartilhada, ou uma senha a ser usada em um mecanismo de criptografia para criptografar dados em uma sessão de comunicação posterior.
Aqui eu uso o segredo compartilhado como uma senha compartilhada que é usada para criptografar e descriptografar uma mensagem secreta.

Imagine o seguinte cenário:
Alice e Bob são alunos sentados na mesma sala de aula. Esta é uma sala de aula de alunos de diferentes faculdades (onde muitos deles não se conhecem).
Alice quer passar uma mensagem secreta para Bob, que está sentado do outro lado da sala.
Alice escreve sua mensagem secreta em um bilhete, coloca o bilhete em uma pequena caixa e a tranca com seu cadeado.
Ela escreve “Para Bob” na caixa e pede aos outros alunos que passem a caixa para Bob.
Quando Bob recebe a caixa, ele coloca seu cadeado na caixa, escreve “Para Alice” e pede aos alunos que devolvam a caixa para Alice.
Alice então recebe a caixa, tira seu cadeado, escreve na caixa “Para Bob” e pede para os alunos passarem a caixa novamente.
Nesse ponto, quando Bob recebe a caixa, ele remove o cadeado, abre a caixa e lê a mensagem secreta.

Observe que este é um protocolo não autenticado . Nenhum remetente ou destinatário confia na autenticidade do outro lado.
Em nosso exemplo, a caixa pode chegar a Mallory, que também está na turma.
Como as pessoas não se conhecem nesta classe, Mallory, que se senta do lado oposto de Alice e recebeu a caixa, pode colocar seu cadeado na caixa e devolvê-la a Alice.
Alice não consegue ver quem recebeu a caixa e ela realmente não sabe quem é o dono do outro cadeado na caixa. Alice acredita que está se comunicando com Bob, enquanto na verdade está se comunicando com Mallory.

No cenário da sala de aula, Bob coloca seu cadeado na caixa perto da caixa de Alice, e Alice pode remover seu cadeado enquanto o cadeado de Bob está trancado.
No protocolo de três passagens, colocamos uma segunda criptografia (criptografia = cadeado bloqueado) em cima da primeira.
É como se Bob colocasse a caixa trancada de Alice dentro de sua caixa e trancasse sua caixa usando seu cadeado.
Para que este protocolo funcione, deve ser possível remover a primeira criptografia (de Alice) após a execução de uma segunda criptografia (de Bob), o que significa que Alice destranca sua caixa enquanto ela está dentro da caixa trancada de Bob.

Frio!

ka : Chave de criptografia de Alice
dka : Chave de descriptografia de Alice
kb : Chave de criptografia de Bob
m : Mensagem
E : Criptografia
D : Descriptografia

D(dka, E(kb, E(ka, m))) = E(kb, m)

Isso é possível com uma criptografia comutativa, que é uma criptografia independente de ordem.

E(ka, E(kb, m)) = E(kb, E(ka, m))

E então:

D(dka, E(kb, E(ka, m))) = D(dka, E(ka, E(kb, m))) = E(kb, m)

O protocolo Three-Pass usa inverso multiplicativo modular para remover as chaves.

Vamos percorrer os passos do algoritmo:

Chave secreta compartilhada: ks
Chaves de Alice: ka , ka⁻¹
Chaves de Bob: kb , kb⁻¹

1. Decida o tamanho dos bits dos números (por exemplo, 128 bits).
2. Todos concordam com um número primo p como chave pública
3. Cada usuário seleciona um número aleatório k , que é um coprimo para p-1

4. Cada usuário calcula k⁻¹ , o inverso multiplicativo modular de seu k

k⁻¹k ≅ 1(mod p-1)

Chaves de Alice: ka, ka⁻¹
Chaves de Bob: kb kb⁻¹

5. Alice escolhe uma chave secreta compartilhada ks para ser compartilhada com Bob

6. Alice criptografa uma mensagem usando o segredo compartilhado:

7. Alice envia o seguinte para Bob:

8. Bob envia o seguinte para Alice:

9. Alice envia o seguinte para Bob:

10. Bob calcula o seguinte:

11. Verifique se as chaves secretas compartilhadas de Bob e Alice são idênticas:

afirmar ks' == ks

12. Bob descriptografa a mensagem criptografada de Alice usando a chave secreta compartilhada que ele calculou:

m'= D(ks', c)

13. Verifique se as mensagens originais e recebidas são idênticas:

afirmar m' == m

A execução do código do algoritmo no notebook colab produz a seguinte saída (você obterá diferentes números gerados):