Criptografia de chave pública

Criptografia de chave pública, também conhecida como criptografia assimétrica, é qualquer sistema criptográfico que usa pares de chaves: chaves públicas, que podem ser amplamente disseminadas, e chaves privadas que são conhecidas apenas pelo proprietário. Isto realiza duas funções: autenticação, onde a chave pública verifica que um portador da chave privada parelhada enviou a mensagem, e encriptação, onde apenas o portador da chave privada parelhada pode decriptar a mensagem encriptada com a chave pública.

Um número imprevisível (tipicamente grande e aleatório) é usado para começar a geração de um par de chaves adequado para uso por um algoritmo de chave assimétrica.

O termo assimétrica vem deste uso de diferentes chaves para realizar essas funções opostas, cada uma a inversa da outra – como contrapartida da criptografia ("simétrica") convencional, a qual depende da mesma chave para realizar ambos.

Em um sistema de criptografia de chave pública, qualquer pessoa pode criptografar uma mensagem usando a chave pública do destinatário. Essa mensagem criptografada só pode ser descriptografada com a chave privada do destinatário. Para ser prática, a geração de uma chave pública e privada deve ser computacionalmente econômica. A força de um sistema de criptografia de chave pública depende do esforço computacional (fator de trabalho em criptografia) necessário para encontrar a chave privada de sua chave pública emparelhada. Segurança efetiva requer apenas manter a chave privada. A chave pública pode ser distribuída abertamente sem comprometer a segurança.^[1]

Algoritmos de chave pública são baseados em problemas matemáticos que atualmente não admitem solução eficiente e são inerentes em determinados relacionamentos de fatoração inteira, logaritmo discreto, e curva elíptica. É computacionalmente fácil para um usuário gerar um par de chaves, uma pública e uma privada, e usá-lo para encriptação e decriptação. A força está na "impossibilidade" (computacionalmente impraticável) para uma chave privada gerada apropriadamente ser determinada pela sua chave pública correspondente. Assim, a chave pública pode ser publicada sem comprometer a segurança. Segurança depende apenas de manter secreta a chave privada, isto é, a chave privada nunca deve ser descoberta. Algoritmos de chave pública, diferente de algoritmos de chave simétrica, não exigem um canal seguro para a troca inicial de uma (ou mais) chave secreta entre as partes.

Por causa da complexidade computacional da encriptação assimétrica, ela é tipicamente usada apenas para transferir uma chave de encriptação simétrica pela qual a mensagem (e normalmente a conversa inteira) é encriptada. A encriptação/decriptação simétrica é baseada em algoritmos mais simples e muito mais rápidos.

Autenticação de mensagens envolve aplicar hash à mensagem para produzir um "resumo", e encriptar o resumo com a chave privada para produzir uma assinatura digital. Dessa forma qualquer um pode verificar essa assinatura (1) computando o hash da mensagem, (2) decriptando a assinatura com a chave pública do signatário, e (3) comparando o resumo computado com o resumo decriptado. A igualdade entre os resumos confirma que a mensagem não foi modificada já que ela foi assinada, e que o assinante, e ninguém mais, intencionalmente realizou a operação de assinatura — presumindo que a chave privada do assinante se manteve secreta para o assinante.

A descrição acima depende de um algoritmo de hash de tamanha qualidade tal que ele seja computacionalmente impossível de alterar ou encontrar uma mensagem substituta que produza o mesmo resumo. Porém estudos mostram que até com os algoritmos MD5 e SHA-1, produzir uma mensagem alterada ou substituta não é impossível.^[2] O padrão atual de hash para encriptação é SHA-2. A própria mensagem pode ser usada no lugar do resumo.

Algoritmos de chave pública são ingredientes de segurança fundamentais em criptosistemas, aplicações e protocolos. Eles dão sustentação a vários padrões da Internet, tais quais Segurança da Camada de Transporte (SCT), S/MIME, PBB, e GPG. Alguns algoritmos de chave pública fornecem distribuição de chave e sigilo (e.g., Troca de chaves de Diffie–Hellman), outros fornecem assinaturas digitais (e.g., Algoritmo de Assinatura Digital), e alguns fornecem ambos (e.g., RSA).

Criptografia de chave pública encontra aplicações na disciplina de segurança de TI segurança da informação, entre outras. Segurança da informação (SI) lida com todos os aspectos de proteção da informação eletrônica ativa contra ameaças de segurança.^[3] Criptografia de chave pública é usada como um método de garantir a confidencialidade, autenticidade e o não-repúdio de comunicações eletrônicas e de armazenamento de dados.

Entendendo

Criptografia de chave pública é frequentemente usada para garantir a segurança da comunicação eletrônica sobre um ambiente interconectado aberto tal como a internet, sem depender de um canal encoberto até para uma troca de chaves. Ambientes interconectados abertos são suscetíveis a uma variedade de problemas de segurança de comunicação tais quais ataque do homem-no-meio e outras ameaças à segurança. Propriedades de segurança necessárias para comunicação tipicamente incluem que a comunicação que está sendo enviada não deva ser legível durante a transição (preservando confidencialidade), a comunicação não deve ser modificada durante a transição (preservando a integridade da comunicação), a comunicação deve ser originada por uma parte identificada (autenticidade do remetente) e para assegurar o não-repúdio (a não negação de envio da mensagem). Combinar criptografia de chave pública com um método de Encriptação de Chave Pública Envelopada (ECPE),^[4] permite o envio seguro de uma comunicação sobre um ambiente interconectado aberto.

A técnica especial usada na criptografia de chave pública é o uso de algoritmos de chave assimétrica, nos quais a chave usada por uma das partes para realizar a encriptação ou a decriptação não é a mesma chave usada por outra parte em alguma operação. Cada usuário tem um par de chaves criptográficas – uma chave de encriptação pública e uma chave de decriptação privada. Por exemplo, um par de chaves usado para assinaturas digitais consiste em uma chave de assinatura privada e uma chave de verificação pública. A chave pública deve ser distribuída em larga escala, enquanto que a chave privada deveria ser conhecida somente pelo seu proprietário. As chaves são relacionadas matematicamente, mas os parâmetros são escolhidos de forma que seja inviável o cálculo da chave privada a partir da pública.

Em contraste, algoritmos de chave simétrica – variações dos quais tem sido usados por milhares de anos – usam apenas uma chave secreta, a qual deve ser compartilhada e mantida privada por ambos o remetente e o destinatário, por exemplo, em ambas encriptação e decriptação. Para usar um esquema de encriptação simétrico, o remetente e o destinatário devem, antecipadamente, compartilhar a chave de forma segura.

Como algoritmos de chave simétrica são quase sempre muito menos computacionalmente intensivos que os assimétricos, é comum trocar a chave usando um algoritmo de troca de chave, então transmitir dados usando uma chave e um algoritmo de chave simétrica. Privacidade Muito Boa (em inglês PGP) e a família SSL/TLS de esquemas usam esse procedimento, e são então chamados criptosistemas híbridos.

Descrição

Dois dos usos mais conhecidos de criptografia de chave pública são:

Encriptação de chave pública, na qual a mensagem é encriptada com a chave pública do destinatário. A mensagem não pode ser decriptada por ninguém que não possua a chave privada correspondente, o qual é presumidamente o proprietário da chave e a pessoa associada com a chave pública. Isto é utilizado numa tentativa de assegurar confidencialidade.
Assinaturas digitais, nas quais a mensagem é assinada com a chave privada do emissor e pode ser verificada por qualquer um que tenha acesso à chave pública do emissor. Essa verificação prova que o emissor teve acesso à chave privada, logo, ele provavelmente é a pessoa associada à chave pública. Isto também garante que a mensagem não foi adulterada, uma vez que qualquer manipulação da mensagem irá resultar em modificações no resumo de mensagem (em inglês message digest) codificado, a qual, caso contrário, se mantém imutável entre emissor e recipiente.

Uma analogia para encriptação de chave pública é a de uma caixa de correio. A caixa de correio é exposta e acessível ao público – sua localização (o endereço da rua) é, em essência, a chave pública. Qualquer um que saiba o endereço pode chegar e colocar uma mensagem escrita na caixa de correio. Porém, apenas a pessoa que possui a chave pode abrir a caixa e ler a mensagem.

Uma analogia para assinaturas digitais é a vedação de um envelope com um selo de cera pessoal. A mensagem pode ser aberta por qualquer um, porém a presença de um selo único autentica o remetente.

Um problema central com o uso da criptografia de chave pública é a confiança/prova que uma chave pública específica é autêntica, isto é, que ela é correta e pertence a pessoa ou entidade reivindicada, e não foi adulterada ou substituída por um terceiro malicioso. A abordagem mais comum para esse problema é usar uma infraestrutura de chave pública (ICP), na qual um ou mais terceiros – conhecidos como autoridades certificadoras – certificam a propriedade dos pares de chaves. Privacidade Muito Boa (em inglês PGP), além de ser uma estrutura de autoridade certificada, usa um esquema geralmente chamado de a "teia da verdade" (do inglês "web of trust"), que descentraliza essa autênticação de chaves públicas por um mecanismo central, e substitui endossos individuais do elo entre usuário e chave pública. Até agora, nenhuma solução completamente satisfatória para o "problema de autênticação de chave pública" foi encontrado. ^[^{carece de fontes?]}

História

Nos primórdios da história da criptografia clássica, duas partes comunicantes dependeriam de uma chave que eles iriam trocar entre eles por meio de um método seguro, mas não criptográfico. Por exemplo, um encontro cara-a-cara ou uma troca, através de um correio confiável, poderia ser usada. Essa chave, que ambas as partes manteriam em segredo absoluto, poderia então ser usada para trocar mensagens encriptadas. Um número significativo de dificuldades práticas surgem com essa abordagem para distribuir chaves.

Em 1874, um livro de William Stanley Jevons^[5] descreveu a relação de funções unidirecionais para criptografia, e continuou a debater o problema da fatoração usado para criar um função arapuca. Em Julho de 1996, o matemático Solomon Wolf Golomb disse: "Jevons antecipou a característica de chave do Algoritmo RSA para criptografia de chave pública, apesar de que ele certamente não inventou o conceito de criptografia de chave pública."^[6]

Em 1970, James H. Ellis, um criptógrafo britânico no Government Communications Headquarters (GCHQ) do Reino Unido, concebeu a possibilidade da "encriptação não secreta", (agora chamada de criptografia de chave pública), mas não conseguiu ver uma forma de implementá-la. Em 1973, seu colega Clifford Cocks inventou o que hoje é conhecido como RSA, dando um método prático de implementação, e, em 1974, outro matemático e criptógrafo do QGCG, Malcolm J. Williamson desenvolveu o que agora é conhecido como a troca de chaves Diffie–Hellman. Nenhum desses parece ter sido colocado para uso prático, e suas invenções iniciais não se tornaram de conhecimento público até a pesquisa ser reclassificada como não-confidencial pelo governo britânico em 1997.^[7]

Em 1976, um criptosistema de chave assimétrica foi publicado por Whitfield Diffie e Martin Hellman os quais, influenciados pelo trabalho de Ralph Merkle sobre distribuição de chave pública, divulgaram um método de acordo de chave pública. Esse método de troca de chave, que usa exponenciação em um corpo finito, se tornou conhecido como troca de chave Diffie–Hellman. Esse foi o primeiro método prático publicado para estabelecer uma chave secreta compartilhada sobre um canal de comunicações autenticado (mas não confidencial) sem o uso de um segredo compartilhado previamente. A "técnica de acordo de chave pública" se tornou conhecida como a técnica das charadas de Merkle, e foi inventada em 1974 e publicada em 1978.

Em 1977, uma generalização do esquema de Cocks foi independentemente inventado por Ron Rivest, Adi Shamir e Leonard Adleman, todos, na época, no Instituto de Tecnologia de Massachusetts (MIT). Esses autores publicaram seus trabalhos em 1978, e o algoritmo se tornou conhecido como RSA, de suas iniciais. RSA usa exponenciação modular do produto de dois números primos muito grandes, para encriptar e decriptar, realizando tanto a encriptação de chave pública como a assinatura digital de chave pública. Sua segurança está relacionada à extrema dificuldade de fatorar inteiros muito grandes, um problema para o qual não há uma técnica geral conhecida para resolver. Em 1979, Michael O. rabin publicou um criptosistema relacionado que provavelmente é seguro desde que a fatoração da chave pública permaneça difícil – mantém-se uma suposição que o RSA também desfruta dessa segurança.

Desde a década de 1970, um grande número e variedade de técnicas de encriptação, assinatura digital, acordo de chave, e outras técnicas vem sendo desenvolvidas no campo de criptografia de chave pública. O El Gamal, inventado por Taher ElGamal se baseia no similar e alto nível de dificuldade do problema do logaritmo discreto, assim como o aproximadamente relacionado DSA, o qual foi desenvolvido na Agência de Segurança Nacional (NSA) dos Estados Unidos e publicado pelo NIST como um padrão proposto.

A introdução de criptografia de curvas elípticas por Neal Koblitz e Victor S. Miller, independentemente e simultaneamente pela metade dos anos 80, tem obtido novos algoritmos de chave pública baseados no problema do logaritmo discreto. Apesar de ser matematicamente mais complexo, curvas elípticas fornecem menores tamanhos de chave e operações mais rápidas para segurança estimada aproximadamente equivalente.

Segurança

Alguns esquemas de encriptação podem ser provados como sendo seguros com base na dificuldade presumida de um problema matemático, como encontrar a fatoração inteira do produto de dois primos muito grandes ou computar logaritmos discretos. Note que "segurança" aqui tem um significado matematicamente preciso, e existem múltiplas definições (significativas) diferentes do que significa dizer que um esquema de encriptação é "seguro". A definição "correta" depende do contexto no qual o esquema será implantado.

A aplicação mais óbvia de um sistema de encriptação de chave pública é confidencialidade – uma mensagem que o emissor quer encriptar usando a chave pública do destinatário pode ser decriptada apenas pela chave privada correspondente do destinatário. Assumindo, claro, que nenhuma falha foi descoberta no algoritmo base usado.

Outro tipo de aplicação em criptografia de chave pública é o de esquemas de assinatura digital. Em tal esquema, o usuário que quer enviar uma mensagem computa uma assinatura digital para essa mensagem, e então envia essa assinatura digital (junto com a mensagem) para o remetente desejado. Esquemas de assinatura digital têm a propriedade de que assinaturas podem ser computadas apenas com o conhecimento da chave privada correta. Para verificar que a mensagem foi assinada pelo usuário e que não foi modificada, o destinatário precisa saber apenas a chave pública correspondente. Em alguns casos (e.g. RSA), um único algoritmo pode ser usado para encriptar e criar assinaturas digitais. Em outros casos (e.g., DAS) cada algoritmo pode ser usado apenas para um propósito específico.

Para alcançar tanto autênticação quanto confidencialidade, o emissor deve assinar a mensagem usando sua a chave privada, e então encriptar tanto a mensagem quanto a assinatura usando a chave pública do destinatário.

Essas características podem ser usadas para construir muitos outros (por vezes surpreendentes) protocolos criptográficos e aplicações, tais como moeda digital, acordo de chave de senha autenticada, acordo de chave de múltiplas partes, Serviços de marcação de tempo, protocolos de não-repúdio, etc.

Considerações práticas

Encriptação de Chave Pública Envelopada

Encriptação de Chave Pública Envelopada (EPKE) é o método que consiste em aplicar criptografia de chave pública e garantir que uma comunicação eletrônica é transmitida confidencialmente, tenha os conteúdos de comunicação protegidos contra modificações (integridade de comunicação) e não pode ser negado de ter sido enviado (não-repúdio). Esse é o método frequentemente usado quando se quer proteger a comunicação em um ambiente interconectado aberto como quando se utiliza o protocolo Transport Layer Security (TLS) ou o Secure Sockets Layer (SSL).

EPKE consiste de um processo de duas fases que inclui ambas a Encriptação de Chave pública (PKE) e uma assinatura digital. Ambas Encriptação de chave Pública e assinaturas digitais constituem o princípio da Encriptação de Chave Pública Envelopada (esses dois processos são descritos mais aprofundadamente em suas respectivas seções).

Para o EPKE funcionar efetivamente, é necessário que:

Todo participante da comunicação tenha seu par de chaves único. A primeira chave que é exigida é a chave pública e a segunda chave que é exigida é a chave privada.
As chaves pública e privada de cada pessoa devem ser matematicamente relacionadas nas quais a chave privada é usada para decriptar uma comunicação enviada usando a chave pública e vice-versa. Alguns algoritmos de encriptação assimétrica bem conhecidos são baseados no criptosistema RSA.
A chave privada deve ser mantida absolutamente privada pelo proprietário apesar de a chave pública poder ser publicada em um diretório público bem como com uma autoridade certificadora.

Para enviar uma mensagem usando EPKE, o emissor de uma mensagem primeiro assina a mensagem usando sua própria chave privada, isso garante o não-repúdio da mensagem. O emissor então encripta sua mensagem assinada digitalmente usando a chave pública do destinatário assim aplicando um envelope digital para a mensagem. Esse passo garante confidencialidade durante a transmissão da mensagem. O destinatário da mensagem então usa sua chave privada para decriptar a mensagem assim removendo o envelope digital e então utiliza a chave pública do emissor para decriptar a assinatura digital do remetente. Nesse ponto, se a mensagem não sofreu alteração durante a transmissão, a mensagem estará em aberto para o destinatário.

Por causa da natureza computacionalmente complexa dos algoritmos assimétricos baseados no RSA, o tempo que leva para encriptar documentos ou arquivos muito grandes para serem transmitidos pode levar muito grande até que a transmissão seja completada. Para agilizar esse processo de transmissão, em vez de aplicar a assinatura digital do emissor para os arquivos ou documentos muito grandes, o emissor pode preferencialmente aplicar uma função hash nos documentos ou arquivos usando uma função hash criptográfica e então assinar digitalmente o valor do hash gerado, reforçando assim a não-repúdio. Hashing é uma computação muito mais rápida para ser completada diferentemente de apenas o uso do algoritmo de assinatura digital baseado em RSA. O emissor então assinaria o novo valor do hash gerado e encriptaria os documentos ou arquivos originais com a chave pública do destinatário. A transmissão então ocorreria de forma segura e com confidencialidade e não-repúdio ainda intactos. O destinatário então verificaria a assinatura e decriptaria os documentos ou arquivos encriptados com sua própria chave privada.

Nota: O emissor e o destinatário normalmente não conduzem o processo mencionado acima manualmente, em vez disso, preferencialmente, dependem de software sofisticado para completar o processo EPKE automaticamente.

Encriptação de Chave Pública

O objetivo da Encriptação de Chave Pública (PKE) é garantir que a comunicação que esteja sendo enviada seja mantida confidencial durante o transporte.

Para enviar uma mensagem usando PKE, o emissor de uma mensagem usa a chave pública do destinatário para encriptar conteúdos da mensagem. A mensagem encriptada é então transmitida eletronicamente para o destinatário e o destinatário pode então usar sua própria chave privada correspondente para decriptar a mensagem.

O processo de encriptação que usa a chave pública do destinatário é útil para preservar a confidencialidade da mensagem já que apenas o destinatário tem a chave privada correspondente para decriptar a mensagem. Assim, o remetente da mensagem não pode decriptar a mensagem uma vez que ele a tenha encriptado usando a chave pública do destinatário. Porém, PKE não lida com o problema de não-repúdio, já que a mensagem poderia ter sido enviada por qualquer pessoa que tenha acesso à chave pública do destinatário.

Assinaturas Digitais

O objetivo de um esquema de assinatura digital é garantir que o emissor da comunicação que está sendo enviada seja conhecido para o destinatário e que o emissor da mensagem não possa repudiar uma mensagem que tiver enviado. Assim, o propósito das assinaturas digitais é garantir o não-repúdio de uma mensagem sendo enviada. Isso é útil em um cenário prático onde o remetente deseja fazer uma compra eletrônica de ações e o destinatário quer poder provar quem requisitou a compra. Assinaturas digitais não fornecem confidencialidade para a mensagem sendo enviada.

A mensagem é assinada usando a chave de assinatura privada do emissor. A mensagem assinada digitalmente é então enviada para o destinatário, que pode então usar a chave pública do remetente para verificar a assinatura.

Autoridade certificadora

Para a Encriptação de Chave Pública Envelopada ser o mais segura possível, é necessário haver um "porteiro" (em inglês "gatekeeper") das chaves privada e pública, ou então qualquer um poderia publicar sua chave pública e se mascarar como o emissor planejado de uma comunicação. Esse "porteiro" de chave digital é conhecido como a Autoridade Certificadora. Uma autoridade certificadora é um terceiro confiável que pode emitir chaves privadas e públicas e assim certificar chaves públicas. Ela também funciona como um depósito para armazenar cadeias de chaves e garantir o fator de confiança.

Uma analogia postal

Uma analogia que pode ser usada para entender as vantagens de um Sistema assimétrico é imaginar duas pessoas, Alice e Bob, que estão enviando entre si mensagens secretas através do correio público. Nesse exemplo, Alice quer enviar uma mensagem secreta para Bob, e espera uma resposta secreta de Bob.

Com um sistema chave simétrica, Alice primeiro coloca a mensagem secreta numa caixa, e tranca a caixa usando um cadeado para o qual ela tem a chave. Então, ela manda a caixa para Bob pelo correio normal. Quando Bob recebe a caixa, ele usa uma cópia idêntica da chave de Alice (que de alguma forma ele conseguiu obter previamente, talvez num encontro cara a cara) para abrir a caixa, e lê a mensagem. Bob pode então usar o mesmo cadeado para enviar sua resposta secreta.

Em um sistema de chave assimétrica, Alice e Bob têm cadeados separados. Primeiro, Alice pede a Bob para enviar o cadeado dele aberto através do correio normal, mas mantendo com ele a posse da chave. Quando Alice recebe o cadeado, usa-o para trancar a caixa contendo a mensagem dela, e manda a caixa trancada para Bob. Bob pode então destrancar a caixa com sua chave e ler a mensagem de Alice. Para responder, Bob deve fazer o mesmo, isto é, pegar o cadeado aberto de Alice e trancar a caixa antes de enviar de volta para ela.

A vantagem crítica em um sistema de chave assimétrica é que Bob e Alice nunca precisam enviar uma cópia da chave deles, um para o outro. Isso previne que um terceiro – talvez, nesse exemplo, um carteiro mal-intencionado que abrirá as caixas que não estiverem trancadas – copie uma chave enquanto a mesma está sendo transportada, permitindo que ele possa futuramente espiar as mensagens enviadas entre Alice e Bob. Então, no cenário de chave pública, Alice e Bob não precisam confiar tanto no serviço postal (o canal de comunicação). Além disso, se Bob fosse descuidado e permitisse que alguém copiasse a chave (privada) dele, as mensagens de Alice para Bob seriam comprometidas, mas as mensagens de Alice para outras pessoas continuariam sendo secretas, uma vez que outras pessoas forneceriam cadeados diferentes para Alice usar.

Outro tipo de Sistema de chave assimétrica, chamado um protocolo de três passos, não exige que nenhuma parte sequer toque o cadeado (ou a chave) do outro; Alice e Bob têm cadeados separados. Primeiramente, Alice coloca a mensagem secreta numa caixa, e tranca a caixa usando um cadeado para o qual apenas ela tem a chave. Ela então envia uma caixa para Bob através do correio comum. Quando Bob recebe a caixa, ele adiciona seu próprio cadeado para a caixa, e manda isso de volta para Alice. Quando Alice recebe a caixa com dois cadeados ela retira seu cadeado e manda a caixa de volta para Bob. Quando Bob recebe a caixa com apenas seu cadeado nela, Bob pode então destrancar a caixa com sua chave e ler a mensagem de Alice.

Note que esse esquema exige o uso de cifras comutativas para permitir que Alice possa remover a encriptação dela, até mesmo quando a encriptação de Bob estiver aplicada à caixa, e para Bob manter a caixa mesmo depois que Alice removeu a encriptação dela. -->Note que, nesse esquema, a ordem de decriptação NÃO é a mesma ordem de encriptação – isso só é possível se cifras comutativas forem utilizadas. Uma cifra comutativa é uma na qual a ordem de encriptação e decriptação é permutável, assim como a ordem dos fatores de uma multiplicação (i.e., A*B*C = A*C*B = C*B*A). Esse método é seguro para certas escolhas de cifras comutativas, mas inseguro para outras others (e.g., um simples XOR). Por exemplo, sejam E₁() e E₂() duas funções de encriptação, e seja "M" a mensagem tal que Alice a encripta usando E₁() e envia E₁(M) para Bob. Bob então novamente encripta a mensagem como E₂(E₁(M)) e a envia para Alice. Agora, Alice decripta E₂(E₁(M)) usando E₁(). Alice terá agora E₂(M), significando que quando ela enviar novamente para Bob, ele irá ser capaz de decriptar a mensagem usando E₂() e pegando "M". Apesar de nenhuma das chaves terem sido trocadas alguma vez, a mensagem "M" pode muito bem ser uma chave (e.g., a chave pública de Alice). Esse Protocolo de três passos é tipicamente usado na troca de chave.

Algoritmos reais: duas chaves ligadas

Nem todos os algoritmos de chave assimétrica operam precisamente dessa forma. Os algoritmos mais comuns têm a propriedade de que tanto Alice quanto Bob, são proprietários de duas chaves cada um, uma para encriptação e uma para decriptação. Em um esquema de encriptação de chave assimétrica seguro, a chave privada não deve ser dedutível a partir da chave pública. Isso é conhecido como encriptação de chave pública, já que uma chave de encriptação pode ser publicada sem comprometer a segurança das mensagens encriptadas com aquela chave.

Na analogia acima, Bob deve publicar instruções sobre como fazer um cadeado ("chave pública"). No entanto, os funcionamentos do cadeado são tais que é impossível (até onde se sabe) deduzir através das instruções dadas como exatamente fazer uma chave que pode abrir aquele cadeado (e.g., uma "chave privada"). Aqueles que desejam enviar mensagens a Bob devem usa a chave pública para encriptar a mensagem, Bob então pode usar sua própria chave privada para decriptá-la.

Em outro exemplo, temos Alice e Bob, cada um escolhendo uma chave aleatoriamente e então contactando o outro para comparar a profundidade de cada entalhe em suas chaves. Tendo determinado a diferença, uma caixa trancada é construída com um cadeado especial em que cada pino dentro dele é dividido em 2 pinos, combinando com os números das chaves deles. Agora a caixa poderá ser aberta com ambas as chaves, e Alice e Bob podem trocar mensagens dentro da caixa de maneira segura.

Fraquezas

Dos algoritmos de encriptação de chave simétrica, apenas a cifra de uso único (em inglês, One-Time Pad), ou OTP, pode ser provada como sendo segura contra qualquer adversário – não importando quanto poder computacional esteja disponível. Entretanto, não existe esquema de chave pública com essa propriedade, uma vez que todos os esquemas de chave pública estão suscetíveis a "ataques de procura de chave por força bruta". Tais ataques são impraticáveis se a quantidade de computação necessária para vencer – denominado o "fator trabalho" (em inglês "work factor") por Claude Shannon – estiver fora de alcance dos possíveis atacantes. Em muitos casos, o fator trabalho pode ser incrementado simplesmente escolhendo uma chave maior. Mas outros algoritmos podem ter fatores trabalho muito mais baixos, tornando irrelevante a resistência a um ataque de força bruta. Alguns algoritmos especiais e específicos foram desenvolvidos para auxiliar no ataque a alguns algoritmos de encriptação de chave pública – tanto o RSA como o ElGamal têm ataques conhecidos que são muito mais rápidos que a abordagem por força bruta. Esses fatores mudaram dramaticamente em décadas recentes, tanto com o decréscimo do custo do poder computacional como com as novas descobertas matemáticas.

À parte da resistência para atacar um par de chaves particular, a segurança da hierarquia de certificação deve ser considerada quando se for implementar um sistema de chave pública. Algumas autoridades certificadoras – normalmente um programa construído com um propósito rodando em um computador servidor – atestam as identidades atribuídas a chaves privadas específicas para produzir um certificado digital. Certificados digitais de chave pública são tipicamente válidos por vários anos, então as chaves privadas associadas devem ser mantidas seguras durante esse tempo. Quando a chave privada usada para criação de certificado mais alta na hierarquia do servidor PKI é comprometida, ou acidentalmente divulgada, então um "ataque do homem no meio" é possível, tornando completamente inseguro qualquer certificado subordinado.

As maiores fraquezas foram encontradas para vários algoritmos de chave assimétrica que, outrora, eram promissores. O algoritmo 'knapsack packing' foi descoberto como sendo inseguro depois do desenvolvimento de um novo ataque. Recentemente, alguns ataques baseados em medições cuidadosas da quantidade exata de tempo, que leva para um hardware conhecido encriptar purotexto, têm sido usados para simplificar a procura por chaves de decriptação prováveis (ver "ataque de canal colateral"). Assim, o simples uso de algoritmos de chave assimétrica não garante segurança. Uma grande negociação de pesquisa ativa está atualmente a caminho para descobrir, e para proteger contra, novos algoritmos de ataque.

Outra vulnerabilidade de segurança possível no uso de chaves assimétricas é a possibilidade de um ataque do "homem no meio", no qual a comunicação de chaves públicas é interceptada por um terceiro (o "homem no meio") e então modificada para prover diferentes chaves públicas. Mensagens encriptadas e respostas também devem ser interceptadas, decriptadas, e re-encriptadas pelo atacante usando as chaves públicas corretas para segmentos de comunicação diferentes, em todas as instâncias, para evitar suspeitas. Esse ataque pode parecer difícil de ser implementado na prática, mas não é impossível quando se utiliza mídia insegura (e.g., redes públicas, como a Internet ou formas de comunicação sem fio) – por exemplo, um funcionário mal-intencionado no provedor de serviço de internet (ISP) de Alice ou de Bob possivelmente achará a execução do ataque um tanto fácil. Na analogia postal anterior, Alice teria que se certificar que o cadeado retornado no pacote realmente pertence a Bob antes de ela remover o cadeado dela e enviar o pacote de volta. Caso contrário, o cadeado poderia ter sido colocado no pacote por um carteiro mal-intencionado fingindo ser Bob, enganando Alice.

Uma abordagem para prevenir tais ataques envolve o uso de uma autoridade certificadora, uma terceira parte confiável responsável pela verificação da identidade de um usuário no sistema. Essa autoridade emite um certificado digital resistente à adulteração e à fraude para os participantes. Tais certificados são blocos de dados assinados declarando que essa chave pública pertence àquela pessoa, companhia, ou outra entidade. Essa abordagem também tem suas fraquezas – por exemplo, a autoridade certificadora emitindo o certificado deve ser confiada como tendo checado apropriadamente a identidade do dono de uma chave, deve assegurar a corretude de uma chave pública quando emite um certificado, e deve ter feito preparativos com todos os participantes para checar todos os certificados deles antes que as comunicações protegidas possam iniciar. Navegadores web, por exemplo, são supridos com uma longa lista de "certificados de identidade assinados por si mesmos" pelos provedores PKI – esses são usados para checar a boa fé da autoridade de certificado e então, em um segundo passo, os certificados de possíveis comunicadores. Um atacante que poderia subverter qualquer uma dessas autoridades certificadoras a emitir um certificado para uma chave pública falsa poderia então montar um ataque do "homem no meio" tão facilmente quanto se o esquema de certificado não fosse usado. Apesar de seus problemas teóricos e em potencial, essa abordagem é amplamente utilizada. Exemplos incluem SSL e seu sucessor, TLS, que são comumente usados para providenciar segurança para navegadores web, por exemplo, de modo que eles possam ser usados para enviar detalhes de cartões de crédito para uma loja online de forma segura.

Custo computacional

Os algoritmos de chave pública são conhecidos até agora por serem relativamente caros computacionalmente comparados à maioria dos algoritmos de chave simétrica de segurança aparentemente equivalente. O fator diferença é o uso típico de chaves um tanto grandes. Isso tem importantes implicações para o uso prático deles. A maioria é usada em criptosistemas híbridos por razões de eficiência – em tal criptosistema, uma chave secreta compartilhada ("chave de sessão") é gerada por uma partem e essa chave de sessão bem mais breve é então encriptada pela chave pública de cada destinatário. Cada destinatário então utiliza a chave privada correspondente para decriptar a chave de sessão. Quando todas as partes tiverem obtido a chave de sessão, eles podem usar um algoritmo simétrico muito mais rápido para encriptar e decriptar mensagens. Em muitos desses esquemas, a chave de sessão é única para cada troca de mensagens, sendo pseudo-aleatoriamente escolhida por cada mensagem.

Associando chaves públicas a identidades

O elo entre a chave pública e seu "dono" deve ser correto, ou então o algoritmo deve funcionar perfeitamente e ainda assim pode ser completamente inseguro na prática. Assim como com a maioria das aplicações de criptografia, os protocolos usados para estabelecer e verificar esse elo são criticamente importantes. Associando uma chave pública ao seu dono é tipicamente feita por protocolos implementando uma infraestrutura de chave pública (ICP) – esses permitem que a validade da associação seja formalmente verificada por referência para uma terceira parte confiável na forma de uma autoridade certificadora hierárquica (e.g., X.509), um modelo confiável local (e.g., SPKI), ou um esquema de confiança da web, como o originalmente construído dentro do PGP e do GPG, e ainda até certo ponto usado com eles.

Seja qual for a garantia criptográfica dos protocolos, a associação entra a chave pública e seu proprietário é fundamentalmente uma questão de julgamento subjetivo na parte de terceira pessoa confiável, já que a chave é uma entidade matemática, enquanto que o dono – e a conexão entre dono e chave – não são. Por essa razão, o formalismo de uma infraestrutura de chave pública deve fornecer para afirmações explícitas da política seguida quando for fazer o julgamento. Por exemplo, o complexo e não totalmente implementado padrão X.509 permite a uma autoridade de certificado identificar sua política pelos meios de um identificador de objetos, o qual funciona como um índice em um catálogo de políticas registradas. Políticas devem existir por vários propósitos, indo do anonimato a classificações militares.

Relação aos eventos do mundo real

Uma chave pública será conhecida por um grande e, na prática, desconhecido conjunto de usuários. Todos os eventos exigindo revogação ou substituição de uma chave pública podem levar muito tempo para ter pleno efeito com todos que devem ser informados (i.e., todos aqueles usuários que possuírem a chave). Por essa razão, sistemas que devem reagir aos eventos em tempo real (e.g., sistemas de segurança crítica ou sistemas de segurança nacional) não devem usar encriptação de chave pública sem tomar muito cuidado. Existem quatro problemas de interesse:

Privilégio de revogação de chave

Uma revogação maliciosa (ou errônea) de algumas (ou todas) as chaves no sistema é provável, ou em segundo caso, certamente, para causar uma falha completa no sistema. Se chaves públicas podem ser revogadas individualmente, essa é a possibilidade. Todavia, existem abordagens de design que podem reduzir a chance real disso ocorrer. Por exemplo, por meio do certificado, nós podemos criar o que é chamado de "principal composto" (em inglês "compound principal") – tal principal pode ser "Alice e Bob tem Autoridade de Revogar". Agora, apenas Alice e Bob (em concerto) podem revogar uma chave, e nem Alice nem Bob podem revogar chaves sozinhos. Contudo, revogar uma chave agora requer ambos Alice e Bob estarem disponíveis, e isso cria um problema de dependência. Em termos concretos, do ponto de vista de segurança, existe agora um "único ponto de falha" no sistema de revogação de chave pública. Um ataque de Negação de serviço bem-sucedido contra tanto Alice como Bob (ou ambos) bloqueará a revogação exigida. Na verdade, qualquer partição de autoridade entre Alice e Bob terá esse efeito, independente de como será feito.

Pelo fato do principal que permite à autoridade revogação para chaves ser muito poderoso, os mecanismos usados para controlá-lo deveriam envolver ambos o máximo de participantes possível (para proteger contra ataques maliciosos desse tipo), enquanto que ao mesmo tempo o mínimo de participantes possível (para assegurar que a chave possa ser revogada sem atraso perigoso). Certificados de chave pública que incluem uma data de expiração deve não corresponder a uma necessidade de revogação no mundo real – mas ao menos tais certificados não precisam ser rastreados por todo o sistema, também não é necessário que todos os usuários estejam em contato constante com o sistema o tempo todo.

Distribuição de uma nova chave

Depois de uma chave ser revogada, ou quando um usuário é adicionado ao sistema, uma nova chave deve ser distribuída de alguma maneira predeterminada. Assuma que a chave de Carol foi revogada (e.g., por exceder a data de expiração, ou por causa de um acordo da chave privada combinante de Carol). Até uma nova chave ser distribuída, Carol está efetivamente "fora de contato". Ninguém poderá enviar mensagens a ela sem violar protocolos do sistema (i.e., sem uma chave pública válida, ninguém pode encriptar mensagens para ela), e mensagens vindas dela não podem ser assinadas, pela mesma razão. Ou, em outras palavras, a "parte do sistema" controlada por Carol está, em essência, indisponível. Requisitos de segurança têm sido classificados como de mais alta importância que a disponibilidade do sistema em tais designs.

Alguém poderia deixar o poder de criar (ou certificar) chaves (bem como revogá-las) nas mãos de cada usuário – o design original de PGP o fez – mas isso traz problemas para o entendimento e a operação do usuário. Por razões de segurança, essa abordagem tem dificuldades consideráveis – se nada mais, alguns usuários ficarão esquecidos, ou desatentos, ou confusos. Por um lado, uma mensagem revogando um certificado de chave pública deveria se espalhar o mais rápido possível, por outro lado, partes do sistema devem ficar inoperantes "antes" de uma nova chave ser instalada. A janela de tempo pode ser reduzida a zero emitindo-se sempre uma nova chave junto com um certificado que revoga a antiga, mas isso requer co-locação de autoridade para não apenas revogar chaves mas também gerar novas chaves.

É muito provável uma falha no sistema como um todo se o principal (possivelmente combinado) que emite novas chaves falhe por emissão imprópria de chaves. Essa é uma instância de uma "exclusão mútua comum" – um design pode fazer a confiança de um sistema ser alta, mas apenas ao custo da disponibilidade do Sistema (e "vice versa").

Espalhando a revogação

A notificação de revogação do certificado de uma chave de ser espalhada para todos aqueles que podem potencialmente carregá-lo, e o mais rápido possível.

Existem dois meios de espalhar informação (i.e., uma revogação de chave) em um sistema distribuído: ou a informação é "empurrada" para os usuários de um ponto central (ou pontos), ou então ela é "puxada" de um ponto central (ou pontos) pelos usuários finais.

Empurrar a informação é a solução mais simples, pois uma mensagem é enviada para todos os participantes. Entretanto, não existe forma de saber se todos os participantes irão realmente "receber" a mensagem. Se o número de participantes for muito grande, e algumas das distâncias físicas ou da rede também forem grandes, então a probabilidade de sucesso completo (o qual é, em circunstâncias ideais, exigido para a segurança do sistema) será um tanto baixa. Em um estado parcialmente atualizado, o sistema é particularmente vulnerável a ataques de "negação de serviço" já que a segurança foi violada, e uma janela de vulnerabilidade continuará a existir contanto que alguns usuários nunca "peguem a palavra" (em inglês "get the word"). Colocando de outra maneira, empurrando mensagens de revogação de certificado não é nem fácil para proteger, nem é muito confiável.

A alternativa para empurrar é puxar. No extremo, todos os certificados contém todas as chaves necessárias para certificar que a chave pública de interesse (i.e., a chave pertencente ao usuário para o qual alguém deseja enviar uma mensagem, ou para o qual a assinatura está para ser verificada) ainda é válida. Nesse caso, pelo menos algum uso do sistema será bloqueado se o usuário não puder alcançar o serviço de verificação (i.e., um dos sistemas que podem estabelecer a validade atual da chave de outro usuário). Novamente, tal design de sistema pode ser feito tão confiável quanto alguém queira, ao custo da redução da segurança – quanto mais servidores para verificar a possibilidade de revogação de uma chave, maior será a janela de vulnerabilidade.

Outro trade-off é usar um serviço de verificação um pouco menos confiável, porém mais seguro, mas incluir uma data de expiração para cada uma das fontes de verificação. Quanto tempo esse "timeout" deveria ter é uma decisão que exige um trade-off entre a disponibilidade e a segurança que serão decididas a seguir, durante o design do sistema.

Recuperação de uma chave vazada

Assuma que o principal autorizou a revogação de uma chave e que ele decidiu uma chave específica deveria ser revogada. Na maioria dos casos, isso acontece após um fato – por exemplo, se torna conhecido que em algum momento no passado um evento ocorreu que colocou a chave privada em perigo. Permita-nos denotar o tempo no qual é decidido que esse comprometimento ocorreu como T.

Tal comprometimento tem duas implicações. Primeiramente, mensagens encriptadas com uma chave pública combinante (agora ou no passado) não podem mais ser consideradas secretas. Uma solução para evitar esse problema é utilizar o protocolo que tem sigilo perfeito na frente. Segundo, assinaturas feitas com o não mais confiável para ser realmente chave privada depois de tempo T não pode mais ser assumido como sendo autêntico sem informação adicional (i.e., quem, quando, onde, etc.) sobre os eventos liderando para a assinatura digital. Esses não estarão sempre disponíveis, e então todas as tais assinaturas digitais serão menos que acreditáveis. Uma solução para reduzir o impacto de vazar uma chave privada de um esquema de assinatura é usar timestamps.

Perda de sigilo e/ou autenticidade, até para apenas um usuário, tem implicações de segurança em todo o sistema, e uma estratégia para recuperar deve então ser estabelecida. Tal estratégia determinará quem tem autoridade para, e sob que condições alguém deve, revogar um certificado de chave pública. Alguém deve também decidir como espalhar a revogação, e idealmente, como lidar com todas as mensagens assinadas com a chave desde o tempo T (o qual raramente será conhecido de forma precisa). Mensagens enviadas para aquele usuário (o qual requer a chave privada adequada – agora comprometida – para decriptar) devem ser consideradas comprometidas também, não importa quando elas foram enviadas.

Exemplos

Exemplos de técnicas de chave assimétrica para vários efeitos incluem:

Protocolo Diffie-Hellman
DSS (Digital Signature Standard), o qual incorpora o Algoritmo de Assinatura Digital
ElGamal
Várias técnicas de curvas elípticas
Várias técnicas de acordo de chave autenticada e senha
Criptosistema de Paillier
Algoritmo de encriptação RSA (PKCS#1)
Criptosistema de Cramer–Shoup
Protocolo de acordo de chave autenticada YAK

Exemplos de algoritmos de chave assimétrica não adotados vastamente incluem:

Criptosistema NTRUEncrypt
Criptosistema de McEliece

Exemplos de notáveis – mas ainda inseguros – algoritmos de chave assimétrica incluem:

Criptosistema de knapsack de Merkle–Hellman

Exemplos de protocolos usando algoritmos de chave assimétrica incluem:

S/MIME
GPG, uma implementação de OpenPGP
Troca de chave pela Internet
PGP
ZRTP, um protocolo seguro VoIP
Secure Socket Layer, agora codificado como o padrão IETF
Segurança de camada de transporte (TLS)
SILC
SSH
Bitcoin
Off-the-Record Messaging

Ver também

Referências

↑ Stallings, William (3 de maio de 1990). Cryptography and Network Security: Principles and Practice (em inglês). [S.l.]: Prentice Hall. p. 165. ISBN 9780138690175
↑ Selinger, Peter. «MD5 Collision Demo». Dalhousie University. Consultado em 23 de junho de 2015
↑ «Information Security Resources». SANS Institute. Consultado em 25 de maio de 2014
↑ «What is a digital envelope?». RSA Laboratories. Consultado em 25 de maio de 2014
↑ Jevons, William Stanley, The Principles of Science: A Treatise on Logic and Scientific Method p. 141, Macmillan & Co., London, 1874, 2nd ed. 1877, 3rd ed. 1879. Reprinted with a foreword by Ernst Nagel, Dover Publications, New York, NY, 1958.
↑ Golob, Solomon W. (1996). «ON FACTORING JEVONS' NUMBER». Cryptologia. 20 (3): 243. doi:10.1080/0161-119691884933
↑ Singh, Simon (1999). The Code Book. [S.l.]: Doubleday. pp. 279–292

Bibliografia

Hirsch, Frederick J. «SSL/TLS Strong Encryption: An Introduction § Cryptographic Techniques». Apache HTTP Server. Consultado em 17 de abril de 2013 . The first two sections contain a very good introduction to public-key cryptography.

Ferguson, Niels; Schneier, Bruce (2003). Practical Cryptography. [S.l.]: Wiley. ISBN 0-471-22357-3
Katz, Jon; Lindell, Y. (2007). Introduction to Modern Cryptography. [S.l.]: CRC Press. ISBN 1-58488-551-3
Menezes, A. J.; van Oorschot, P. C.; Vanstone, Scott A. (1997). Handbook of Applied Cryptography. [S.l.: s.n.] ISBN 0-8493-8523-7
IEEE 1363: Standard Specifications for Public-Key Cryptography
Christof Paar, Jan Pelzl, "Introduction to Public-Key Cryptography", Chapter 6 of "Understanding Cryptography, A Textbook for Students and Practitioners". (companion web site contains online cryptography course that covers public-key cryptography), Springer, 2009.

Ligações externas

Oral history interview with Martin Hellman, Charles Babbage Institute, University of Minnesota. Leading cryptography scholar Martin Hellman discusses the circumstances and fundamental insights of his invention of public key cryptography with collaborators Whitfield Diffie and Ralph Merkle at Stanford University in the mid-1970s.
«An account of how GCHQ kept their invention of PKE secret until 1997». ^{[ligação inativa]} [http://www.ladlass.com/intel/archives/010256.html Arquivado em 25 de junho de 2008, no Wayback Machine. ]

[1] Stallings, William (3 de maio de 1990). Cryptography and Network Security: Principles and Practice (em inglês). [S.l.]: Prentice Hall. p. 165. ISBN 9780138690175

[2] Selinger, Peter. «MD5 Collision Demo». Dalhousie University. Consultado em 23 de junho de 2015

[3] «Information Security Resources». SANS Institute. Consultado em 25 de maio de 2014

[4] «What is a digital envelope?». RSA Laboratories. Consultado em 25 de maio de 2014

[5] Jevons, William Stanley, The Principles of Science: A Treatise on Logic and Scientific Method p. 141, Macmillan & Co., London, 1874, 2nd ed. 1877, 3rd ed. 1879. Reprinted with a foreword by Ernst Nagel, Dover Publications, New York, NY, 1958.

[6] Golob, Solomon W. (1996). «ON FACTORING JEVONS' NUMBER». Cryptologia. 20 (3): 243. doi:10.1080/0161-119691884933

[singh-7] Singh, Simon (1999). The Code Book. [S.l.]: Doubleday. pp. 279–292

[1]

[2]

[3]

[4]

[5]

[6]

[7]