CIFRAS ASSIMÉTRICAS

PRINCÍPIOS DE CRIPTOSSISTEMAS DE CHAVE PÚBLICA

O desenvolvimento da criptografia de chave pública é a maior e talvez a única verdadeira revolução na história inteira da criptografia. Desde o seu início até os tempos modernos, praticamente todos os sistemas criptográficos têm sido baseados nas ferramentas elementares da substituição e permutação. Depois de milênios de trabalho com algoritmos que, em essência, poderiam ser calculados à mão, um avanço na criptografia simétrica ocorreu com o desenvolvimento da máquina de encriptação/decriptação de rotor. O rotor eletromecânico permitiu a elaboração de sistemas de cifra incrivelmente complexos. Com a disponibilidade dos computadores, sistemas ainda mais complexos foram criados, e o mais importante foi o esforço Lucifer na IBM, que culminou com o Data Encryption Standard (DES). Mas tanto as máquinas de rotor quanto o DES, embora representando avanços significativos, ainda contavam com ferramentas básicas de substituição e permutação.

A criptografia de chave pública oferece uma mudança radical de tudo o que foi feito antes. Por um lado, os algoritmos de chave pública são baseados em funções matemáticas, em vez de substituição e permutação. Mais importante, a criptografia de chave pública é assimétrica, envolvendo o uso de duas chaves separadas, ao contrário da criptografia simétrica, que utiliza apenas uma chave. O uso de duas chaves tem profundas consequências nas áreas de confidencialidade, distribuição de chave e autenticação, conforme veremos.

Antes de prosseguirmos, temos que mencionar várias concepções erradas comuns com relação à criptografia de chave pública. Uma delas é que ela é mais segura contra criptoanálise do que a criptografia simétrica. Na verdade, a segurança de qualquer esquema de criptografia depende do tamanho da chave e do traibalho computacional envolvido para quebrar uma cifra. Não há nada em princípio sobre a criptografia simétrica ou de chave pública que torne uma superior à outra, do ponto de vista de resistência à criptoanálise.

Um segundo erro de conceito é o de que a criptografia de chave pública é uma técnica de uso geral que tornou a criptografia simétrica obsoleta. Ao contrário, por conta do overhead computacional dos esquemas de criptografia de chave pública atuais, parece não haver probabilidade previsível de que a criptografia simétrica será abandonada. Conforme um dos inventores da criptografia de chave pública disse:

“A restrição da criptografia de chave pública às aplicações de gerenciamento de chave e assinatura é aceita quase universalmente”.

Por fim, há uma sensação de que a distribuição de chave é trivial quando se usa a criptografia de chave pública, em comparação com o tratamento um tanto desajeitado envolvido com os centros de distribuição de chave para a criptografia simétrica. Na verdade, é preciso haver alguma forma de protocolo, geralmente abrangendo um agente central, e os procedimentos envolvidos não são mais simples nem mais eficientes do que aqueles exigidos para a criptografia simétrica.

Grande parte da teoria dos criptossistemas de chave pública é baseada na teoria dos números. Se alguém estiver preparado para aceitar os resultados dados neste capítulo, uma noção da teoria dos números não é estritamente necessária. Porém, para apreciar por completo os algoritmos de chave pública, algum conhecimento desse assunto é exigido.

TERMINOLOGIA RELACIONADA À CRIPTOGRAFIA ASSIMÉTRICA

Chaves assimétricas – duas chaves relacionadas, uma pública e uma privada, que são usadas para realizar operações complementares, como encriptação e decriptação ou geração e verificação de assinatura.

Certificado de chave pública – um documento emitido e assinado digitalmente pela chave privada de uma autoridade de Certificação, que vincula o nome de um assinante a uma chave pública. O certificado indica que o assinante identificado tem o único controle e acesso à chave privada correspondente.

Algoritmo criptográfico de chave pública (assimétrica) – um algoritmo criptográfico que usa duas chaves relacionadas, uma pública e uma privada. as duas têm a propriedade de ser computacionalmente inviável derivar a chave privada a partir da pública.

Infraestrutura de chave pública (PKI) – um conjunto de políticas, processos, plataformas de servidor, software e estações de trabalho usadas para fins de admi­nistrar certificados e pares de chave pública­ privada, incluindo a capacidade de emitir, manter e revogar certificados de chave pública.

PRINCÍPIOS DE CRIPTOSSISTEMAS DE CHAVE PÚBLICA

O conceito de criptografia de chave pública evoluiu de uma tentativa de atacar dois dos problemas mais difíceis associados à encriptação simétrica. O primeiro é o da distribuição de chaves.

A distribuição de chaves sob a encriptação simétrica requer que dois comunicantes já compartilhem uma chave, que de alguma forma foi distribuída a eles; ou o uso de um centro de distribuição de chaves. Whitfield Diffie, um dos descobridores da encriptação de chave pública (com Martin Hellman, ambos da Stanford University, na época), raciocinou que esse segundo requisito anulava a essência da criptografia: a capacidade de manter sigilo total sobre a sua própria comunicação. Conforme foi dito por Diffie:

“Afinal, qual seria a vantagem de desenvolver criptossistemas impenetráveis, se seus usuários fossem forçados a compartilhar suas chaves com um CDC que poderia ser comprometido por roubo ou suborno?”

O segundo problema sobre o qual Diffie ponderou, e que estava aparentemente não relacionado com o primeiro, foi o de assinaturas digitais. Se o uso da criptografia tivesse que se tornar comum, não apenas nas situações militares, mas para fins comerciais e particulares, então as mensagens e documentos eletrônicos precisariam do equivalente das assinaturas usadas nos documentos em papel. Ou seja, poderia ser criado um método para estipular, para a satisfação de todas as partes, que uma mensagem digital foi enviada por determinada pessoa? Esse é um requisito um pouco mais amplo do que o da autenticação.

Diffie e Hellman fizeram uma descoberta incrível em 1976, surgindo com um método que resolvia os dois problemas e que era radicalmente diferente de todas as técnicas anteriores de criptografia, quatro milênios atrás.

CRIPTOSSISTEMAS DE CHAVE PÚBLICA

Os algoritmos assimétricos contam com uma chave para encriptação e uma chave diferente, porém relacionada, para a decriptação. Eles têm a seguinte característica importante:

• É computacionalmente inviável determinar a chave de decriptação dado apenas o conhecimento do algoritmo de criptografia e da chave de encriptação.

Além disso, alguns algoritmos, como RSA, também exibem esta característica:

• Qualquer uma das duas chaves relacionadas pode ser usada para encriptação, com a outra para a decriptação.

Um esquema de encriptação de chave pública possui cinco elementos:

• Texto claro: essa é a mensagem ou dados legíveis que são alimentados no algoritmo como entrada.
• Algoritmo de encriptação: realiza várias transformações no texto claro.
• Chaves pública e privada: esse é um par de chaves que foi selecionado de modo que, se uma for usada para encriptação, a outra é usada para decriptação. As transformações exatas realizadas pelo algoritmo dependem da chave pública ou privada que é fornecida como entrada.
• Texto cifrado: essa é a mensagem embaralhada produzida como saída. Ela depende do texto claro e da chave. Para determinada mensagem, duas chaves diferentes produzirão dois textos cifrados diferentes.
• Algoritmo de decriptação: aceita o texto cifrado e a chave correspondente e produz o texto claro original.

As etapas essenciais são as seguintes:

1. Cada usuário gera um par de chaves a ser usado para a encriptação e a decriptação das mensagens.
2. Cada usuário coloca uma das duas chaves em um registrador público ou em outro arquivo acessível. Essa é a chave pública. A chave acompanhante permanece privada. Como a Figura “Criptografia de chave pública a” sugere, cada usuário mantém uma coleção de chaves públicas obtidas de outros.
3. Se Bob deseja enviar uma mensagem confidencial para Alice, ele a encripta usando a chave pública de Alice.
4. Quando Alice recebe a mensagem, ela a decripta usando sua chave privada. Nenhum outro destinatário pode decriptar a mensagem, pois somente Alice conhece a chave privada de Alice.

O Quadro “encriptação convencional e de chave pública” resume alguns dos aspectos importantes da encriptação simétrica e de chave pública. Para discriminar entre as duas, vamos nos referir à chave usada na encriptação simétrica como uma chave secreta. As duas chaves utilizadas para a encriptação assimétrica são denominadas chave pública e chave privada. Invariavelmente, a chave privada é mantida secreta, mas ela é conhecida como chave privada, em vez de secreta, para evitar confusão com a encriptação simétrica.

Vamos examinar mais de perto os elementos essenciais de um esquema de encriptação de chave pública usando a Figura “Criptossistema de chave pública: sigilo”. Existe alguma origem A que produz uma mensagem em texto claro, X = [X₁, X₂, …, X_M]. Os M elementos de X são letras em algum alfabeto finito. A mensagem é intencionada para o destino B. Este gera um par de chaves relacionado: uma chave pública, PU_b , e uma chave privada, PR_b . Esta última é conhecida apenas por B, enquanto PU b está disponível publicamente e, portanto, acessível a A.

Com a mensagem X e a chave de encriptação PU b como entrada, A forma o texto cifrado Y = [Y₁, Y₂, …, Y_N ]:

Y = E(PU_b , X)

O receptor intencionado, de posse da chave privada correspondente, é capaz de inverter a transformação:

X = D(PR_b , Y)

Um invasor, observando Y e tendo acesso à PU_b , mas não à PR_b ou X, precisa tentar recuperar X e/ou PR_b. Considera-se que ele tem conhecimento dos algoritmos de encriptação (E) e decriptação (D). Se o invasor estiver interessado apenas nessa mensagem em particular, então o foco do esforço é recuperar X, gerando um texto claro estimado X̂. Normalmente, porém, o invasor também está interessado em poder ler mensagens futuras, quando tentará recuperar PR_b gerando um PR̂_b estimado.

Já mencionamos que qualquer uma das duas chaves relacionadas pode ser usada para encriptação, com a outra sendo voltada para decriptação. Isso permite a implementação de um esquema criptográfico diferente.

Enquanto o esquema ilustrado na Figura 9.2 oferece confidencialidade, as figuras 9.1b e 9.3 mostram o uso da encriptação de chave pública para oferecer autenticação:

Y = E(PR_a, X)

X = D(PU_a, Y)

Nesse caso, A prepara uma mensagem para B e a encripta usando a própria chave privada antes de transmiti-la. B pode decriptar a mensagem empregando a chave pública de A. Como a mensagem foi encriptada com a chave privada de A, somente A poderia ter preparado a mensagem. Portanto a mensagem encriptada inteira serve como uma assinatura digital. Além disso, é impossível alterar a mensagem sem acesso à chave privada de A, de modo que ela é autenticada em termos da origem e da integridade dos dados.

No esquema anterior, a mensagem inteira é encriptada, o que, embora validando autor e conteúdo, requer bastante armazenamento. Cada documento tem que ser mantido em texto claro para ser usado a fins práticos. Uma cópia também necessita ser armazenada em texto cifrado, para que a origem e o conteúdo possam ser verificados em caso de uma disputa. Uma forma mais eficiente de conseguir os mesmos resultados é encriptar um pequeno bloco de bits que é uma função do documento. Esse bloco, chamado autenticador, precisa ter a propriedade de ser inviável alterar o documento sem alterar o autenticador. Se este for encriptado com a chave privada do emissor, ele serve como uma assinatura que verifica origem, conteúdo e sequência.

 

É importante enfatizar que o processo de encriptação representado nas figuras Criptografia de chave pública b e Criptossistema de chave pública: autenticação. não oferece confidencialidade. Ou seja, a mensagem sendo enviada é segura contra alteração, mas não contra à observação não autorizada. Isso é óbvio no caso de uma assinatura baseada em uma parte da mensagem, pois o restante dela é transmitido às claras. Mesmo no caso de encriptação completa, como mostra a figura Criptossistema de chave pública: autenticação., não existe proteção de confidencialidade, pois qualquer observador pode decriptar a mensagem usando a chave pública do emissor.

Contudo, é possível oferecer a função de autenticação e confidencialidade com um uso duplo do esquema de chave pública (Criptossistema de chave pública: autenticação e sigilo):

Z = E(PU_b, E(PR_a, X))

X = D(PU_a, D(PR_b, Z))

Nesse caso, começamos como antes, encriptando uma mensagem e usando a chave privada do emissor. Isso oferece a assinatura digital. Em seguida, encriptamos novamente, com a chave pública do receptor. O texto cifrado final só pode ser decriptado pelo receptor intencionado, que tem a chave privada equivalente. Assim, a confidencialidade é fornecida. A desvantagem dessa técnica é que o algoritmo de chave pública, que é complexo, precisa ser exercido quatro vezes, em vez de duas, em cada comunicação.

Aplicações para criptossistemas de chave pública

Antes de prosseguir, precisamos esclarecer um aspecto dos criptossistemas de chave pública que, de outra forma, poderia causar confusão. Os sistemas de chave pública são caracterizados pelo uso de um algoritmo criptográfico com duas chaves, uma mantida privada e uma disponível publicamente. Dependendo da aplicação, o emissor utiliza a chave privada do emissor ou a chave pública do receptor, ou ambas, para realizar algum tipo de função criptográfica. Em termos gerais, podemos classificar o uso dos criptossistemas de chave pública em três categorias:

• Encriptação/decriptação: o emissor encripta uma mensagem com a chave pública do destinatário.
• Assinatura digital: o emissor “assina” uma mensagem com sua chave privada. A assinatura é feita por um algoritmo criptográfico aplicado à mensagem ou a um pequeno bloco de dados que é uma função da mensagem.
• Troca de chave: dois lados cooperam para trocar uma chave de sessão. Várias técnicas diferentes são possíveis, envolvendo a(s) chave(s) privada(s) de uma ou de ambas as partes.

Alguns algoritmos são adequados para todas as três aplicações, enquanto outros só podem ser usados para uma ou duas delas.

Requisitos para criptografia de chave pública

O criptossistema estudado depende de um algoritmo criptográfico baseado em duas chaves relacionadas. Diffie e Hellman postularam esse sistema sem demonstrar que esses algoritmos existem. Porém, eles estabeleceram as condições a que esses algoritmos precisam atender [DIFF76b]:

1. É computacionalmente fácil para uma parte B gerar um par (chave pública PU_b, chave privada PR_b).

2. É computacionalmente fácil que um emissor A, conhecendo a chave pública e a mensagem a ser encriptada, M, gere o texto cifrado correspondente:

C = E(PU_b, M)

3. É computacionalmente fácil que o receptor B decripte o texto cifrado resultante usando a chave privada para recuperar a mensagem original:

M = D(PR_b, C) = D[PR_b, E(PU_b, M)]

4. É computacionalmente inviável que um invasor, conhecendo a chave pública, PU_b, determine a chave privada, PR_b.

5. É computacionalmente inviável que um invasor, conhecendo a chave pública, PU_b, e um texto cifrado, C, recupere a mensagem original, M.

Podemos incluir um sexto requisito que, embora útil, não é necessário para todas as aplicações de chave pública:

6. As duas chaves podem ser aplicadas em qualquer ordem:

M = D[PU_b, E(PR_b, M)] = D[PR_b, E(PU_b, M)]

Esses são requisitos formidáveis, conforme evidenciado pelo fato de que somente alguns algoritmos (RSA, criptografia de chave elíptica, Diffie-Hellman, DSS) receberam ampla aceitação nas várias décadas desde que o conceito de criptografia de chave pública foi proposto.

Antes de ponderarmos sobre por que os requisitos são tão formidáveis, vamos primeiro reformulá-los. Os requisitos se resumem à necessidade de uma função de mão única com alçapão. Uma função de mão única é aquela que mapeia um domínio em um intervalo, de modo que o valor de cada função tem um único inverso, com a condição de que o cálculo da função seja fácil, enquanto o cálculo do inverso seja inviável.

Y = f(X) – fácil

X = f ⁻¹ (Y) – inviável

Geralmente, fácil significa um problema que pode ser resolvido em tempo polinomial como função do tamanho da entrada. Assim, se o tamanho da entrada for n bits, então o tempo para calcular a função é proporcional a n^a, onde a é uma constante fixa. Diz-se que esses algoritmos pertencem à classe P. O termo inviável é um conceito muito mais vago. Em geral, podemos dizer que um problema é inviável se o esforço para solucioná-lo aumentar mais rapidamente do que o tempo polinomial em função do tamanho da entrada. Por exemplo, se o tamanho da entrada for n bits e o tempo para calcular a função for proporcional a 2ⁿ , o problema é considerado inviável. Infelizmente, é difícil determinar se um algoritmo em particular exibe essa complexidade. Além do mais, noções tradicionais de complexidade computacional focam na do pior caso e do caso médio de um algoritmo. Essas medidas são inadequadas para a criptografia, que exige que seja inviável reverter uma função para praticamente todas as entradas, e não para o pior caso ou o caso médio.

Agora, passamos para a definição de uma função de mão única com alçapão, que é fácil de se calcular em uma direção e inviável na outra, a menos que certa informação adicional seja conhecida. Com a informação adicional, o inverso pode ser calculado em tempo polinomial. Tem como resumir da seguinte forma: uma função de mão única com alçapão é uma família de funções reversíveis f_k , tal que

 

Y = f k (X) – fácil, se k e X forem conhecidos
X = f_k^–1 (Y) – fácil, se k e Y forem conhecidos
X = f_k ^-1 (Y) – inviável, se Y for conhecido, mas k não

Assim, o desenvolvimento de um esquema de chave pública prático depende da descoberta de uma função de mão única com alçapão adequada.

Criptoanálise de chave pública

Assim como a encriptação simétrica, um esquema de encriptação de chave pública é vulnerável a um ataque de força bruta. A contramedida é a mesma: use chaves grandes. Contudo, existe um dilema a ser considerado. Os sistemas de chave pública dependem do uso de algum tipo de função matemática reversível. A complexidade do cálculo dessas funções pode não crescer linearmente com o número de bits na chave, mas sim mais rapidamente do que isso. Assim, o tamanho da chave precisa ser grande o suficiente para tornar o ataque de força bruta impraticável, mas pequeno para que a encriptação e a decriptação sejam viáveis. Na prática, os tamanhos de chave que foram propostos tornam o ataque por força bruta impraticável, mas resultam em velocidades de encriptação/decriptação muito lentas para o uso geral. Em vez disso, conforme já dissemos, a encriptação de chave pública atualmente é confinada a aplicações de gerenciamento de chave e assinatura.

Outra forma de ataque é encontrar alguma maneira de calcular a chave privada, dada a chave pública. Até o momento, não foi provado matematicamente que essa forma de ataque é inviável para determinado algoritmo de chave pública. Assim, qualquer algoritmo, incluindo o RSA bastante utilizado, é suspeito. A história da criptoanálise mostra que um problema que parece insolúvel de um ponto de vista pode ter uma solução se for visto de uma maneira inteiramente diferente.

Finalmente, existe uma forma de ataque que é peculiar aos sistemas de chave pública. Esse, basicamente, é um ataque de mensagem provável. Suponha, por exemplo, que uma mensagem tivesse que ser enviada contendo exclusivamente uma chave DES de 56 bits. Um invasor conseguiria encriptar todas as chaves DES possíveis de 56 bits usando a chave pública e descobrir a chave encriptada testando com o texto cifrado transmitido. Assim, não importa o tamanho de chave do esquema de chave pública, o ataque é reduzido a um por força bruta em uma chave de 56 bits. Esse ataque pode ser impedido acrescentando-se alguns bits aleatórios a essas mensagens simples.

Algoritmo RSA

Fim da aula 03