Criptografia de chave pública: Diffie-Hellman e RSA

Curiosidade

1. Como dois estranhos concordam em uma chave secreta enquanto todos os outros estão ouvindo?
2. Por que multiplicar dois primos grandes é trivial, mas encontrar esses primos a partir de seu produto é quase impossível?
3. O que significa possuir algo se a posse é definida pela capacidade de assinar?

Explorar

1. Antes de 1976, a comunicação segura exigia um segredo compartilhado, trocado por meio de um canal confiável. Se um interceptador capturasse essa chave, todo o tráfego subsequente ficaria comprometido. Whitfield Diffie e Martin Hellman propuseram uma solução em “New Directions in Cryptography” (IEEE Transactions on Information Theory, novembro de 1976). Duas partes podiam derivar um segredo compartilhado por meio de um canal aberto, utilizando a exponenciação modular. A matemática envolvida é unidirecional: fácil de calcular no sentido direto, mas computacionalmente inviável de reverter sem o valor privado.
2. Ralph Merkle concebeu quebra-cabeças semelhantes entre 1974 e 1975, publicando-os em 1978. Uma das partes publicava vários quebra-cabeças criptografados pequenos; a outra resolvia um deles aleatoriamente e utilizava seu conteúdo como chave. A vantagem era apenas quadrática: com n quebra-cabeças, as duas partes realizavam cerca de n unidades de trabalho, enquanto um espião realizava cerca de n². A diferença proposta por Diffie-Hellman aumenta com o tamanho da chave, e quando pares de chaves novos são utilizados para cada sessão, um vazamento posterior de chaves de longo prazo não expõe o tráfego anterior.
3. Ron Rivest, Adi Shamir e Leonard Adleman, do MIT, desenvolveram o RSA em 1977. Martin Gardner descreveu o sistema em sua coluna da Scientific American de agosto de 1977, antes que o artigo formal fosse publicado nas Communications of the ACM (fevereiro de 1978). O RSA se baseia na dificuldade de fatorar o produto de dois números primos grandes em seus componentes. Ele possibilitou as assinaturas digitais: uma chave privada assina os dados, e a chave pública correspondente verifica-os sem revelar o segredo do signatário.
4. James Ellis, do GCHQ, concebeu a “criptografia não secreta” por volta de 1969 e a descreveu em 1970; Clifford Cocks desenvolveu um sistema equivalente ao RSA em 1973; Malcolm Williamson criou uma versão equivalente ao algoritmo Diffie-Hellman em 1974. Essas descobertas permaneceram classificadas até sua desclassificação em 1997. Esse desenvolvimento paralelo mostra que as bases matemáticas já estavam maduras no início dos anos 1970, mas sua adoção só ocorreu após publicações abertas por pesquisadores acadêmicos. Trabalhos secretos não constroem infraestruturas públicas.
5. Rivest, Shamir e Adleman receberam o Prêmio Turing em 2002; Diffie e Hellman o receberam em 2015. Essa distinção é importante para o Bitcoin: a propriedade não está mais vinculada à custódia física ou a registros bancários, mas à capacidade de gerar uma assinatura válida com uma chave privada. O Bitcoin utiliza criptografia baseada em curvas elípticas secp256k1 em vez de RSA, mas a estrutura fundamental permanece a mesma. Um usuário prova o controle sobre os fundos ao assinar transações; a rede verifica isso por meio das chaves públicas, sem nunca ver as chaves privadas.
6. Trabalhe com o algoritmo Diffie-Hellman usando números pequenos. Concordem publicamente em um número primo p = 23 e uma base g = 5. Alice escolhe um valor secreto a = 6 e envia 5^6 mod 23 = 8. Bob escolhe b = 15 e envia 5^15 mod 23 = 19. Alice calcula 19^6 mod 23 = 2; Bob calcula 8^15 mod 23 = 2. Agora ambos possuem o valor secreto 2, embora apenas 23, 5, 8 e 19 tenham sido transmitidos pelo canal aberto. Os sistemas reais utilizam números com centenas de dígitos, nos quais é inviável recuperar a ou b a partir dos valores públicos.

Fatos-chave

Exercício nove, seis, três, um

Verificação de fatos

Datas, números e afirmações verificados com as fontes publicadas listadas abaixo.

• W. Diffie & M. Hellman, 'New Directions in Cryptography', IEEE Transactions on Information Theory (Nov 1976)
• R. Rivest, A. Shamir & L. Adleman, 'A Method for Obtaining Digital Signatures and Public-Key Cryptosystems', Communications of the ACM (Feb 1978)
• S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (1999)
• S. Levy, Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age (2001)